Basics of Futexes - Eli Bendersky's website
Toggle navigation
Eli Bendersky's website
About
Projects
Archives
The futex (short for "Fast userspace mutex") mechanism was proposed by Linux<br>contributors from IBM in 2002 [1]; it was integrated into the kernel in late 2003.<br>The main idea is to enable a more efficient way for userspace code to<br>synchronize multiple threads, with minimal kernel involvement.
In this post I want to provide a basic overview of futexes, how they work, and<br>how they're used to implement the more familiar synchronization primitives in<br>higher-level APIs and languages.
An important disclaimer: futexes are a very low-level feature of the Linux<br>kernel, suitable for use in foundational runtime components like the C/C++<br>standard libraries. It is extremely unlikely that you will ever need to<br>use them in application code.
Motivation
Before the introduction of futexes, system calls were required for locking and<br>unlocking shared resources (for example semop). System calls are relatively<br>expensive, however, requiring a context switch from userspace to kernel space;<br>as programs became increasingly concurrent, locks started showing up on<br>profiles as a significant percentage of the run time. This is very unfortunate,<br>given that locks accomplish no real work ("business logic") but are only there<br>to guarantee that access to shared resources is safe.
The futex proposal is based on a clever observation: in most cases, locks are<br>actually not contended. If a thread comes upon a free lock, locking it<br>can be cheap because most likely no other thread is trying to lock it at the<br>exact same time. So we can get by without a system call, attemping much cheaper<br>atomic operations first [2]. There's a very high chance that the atomic<br>instruction will succeed.
However, in the unlikely event that another thread did try to take the lock at<br>the same time, the atomic approach may fail. In this case there are two options.<br>We can busy-loop using the atomic until the lock is cleared; while this is 100%<br>userspace, it can also be extremely wasteful since looping can significantly<br>occupy a core, and the lock can be held for a long time. The alternative is to<br>"sleep" until the lock is free (or at least there's a high chance that it's<br>free); we need the kernel to help with that, and this is where futexes come in.
Simple futex use - waiting and waking
The futex(2) system call<br>multiplexes a lot of functionality on top of a single interface. I will not<br>discuss any of the advanced options here (some of them are so esoteric they're<br>not even officially documented) but will focus on just FUTEX_WAIT and<br>FUTEX_WAKE. The man page description starts with a good introduction:
The futex() system call provides a method for waiting until a certain<br>condition becomes true. It is typically used as a blocking construct<br>in the context of shared-memory synchronization. When using futexes,<br>the majority of the synchronization operations are performed in user<br>space. A user-space program employs the futex() system call only<br>when it is likely that the program has to block for a longer time<br>until the condition becomes true. Other futex() operations can be<br>used to wake any processes or threads waiting for a particular<br>condition.
Simply stated, a futex is a kernel construct that helps userspace code<br>synchronize on shared events. Some userspace processes (or threads) can wait on<br>an event (FUTEX_WAIT), while another userspace process can signal the event<br>(FUTEX_WAKE) to notify waiters. The waiting is efficient - the waiters are<br>suspended by the kernel and are only scheduled anew when there's a wake-up<br>signal.
Be sure to read the futex man page beyond the introduction; blog posts<br>are not a substitute for documentation! At the very least read about the<br>FUTEX_WAIT and FUTEX_WAKE calls, the arguments they take, their return<br>values and possible errors.
Let's study a simple example<br>demonstrating basic usage of futexes to coordinate two processes. The main<br>function sets up the machinery and launches a child process that:
Waits for 0xA to be written into a shared memory slot.
Writes 0xB into the same memory slot.
Meanwhile, the parent:
Writes 0xA into the shared memory slot.
Waits for 0xB to be written into the slot.
This is a simple handshake between two processes. Here's the code:
int main(int argc, char** argv) {<br>int shm_id = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0666);<br>if (shm_id 0) {<br>perror("shmget");<br>exit(1);<br>int* shared_data = shmat(shm_id, NULL, 0);<br>if (shared_data == (void*)-1) {<br>perror("shmat");<br>exit(1);<br>*shared_data = 0;
int forkstatus = fork();<br>if (forkstatus 0) {<br>perror("fork");<br>exit(1);
if (forkstatus == 0) {<br>// Child process
printf("child waiting for A\n");<br>wait_on_futex_value(shared_data, 0xA);
printf("child writing B\n");<br>// Write 0xB to the shared data and wake up parent if it's waiting.<br>*shared_data = 0xB;<br>wake_futex(shared_data);<br>} else {<br>// Parent process.
printf("parent writing A\n");<br>// Write 0xA to the shared data...