CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 4 of 7 · 3 min read

The futex

Think of it this way. A restaurant manager sits at the door and is called by waiters only when a table is truly stuck. Most of the time, waiters sort things out by themselves and never disturb the manager. The analogy stops in one place: the manager is called by a shout, and a thread calls the kernel by a system call, which costs far more.

In plain words: If every lock and unlock were a system call, mutexes would be slow, since a system call costs far more than an atomic instruction (Level 0). Linux gives a better way: the futex (fast user-space mutex). A futex is an integer in the program's memory, together with two kernel operations on it: wait (sleep if the integer still has this value) and wake (wake some threads sleeping on this integer). Locking and unlocking use atomic instructions on the integer, as in page 2, and the kernel is entered only when a thread has to sleep or to wake another.

A mutex built this way (after Drepper's description, 2011) has three states in one integer:

State Meaning
0 Free
1 Held, nobody waiting
2 Held, and some thread may be waiting
void lock(void) {
    int c = 0;
    if (CAS(&state, &c, 1)) return;                /* 0 -> 1: fast path, no system call */
    if (c != 2) c = exchange(&state, 2);           /* announce that a waiter exists      */
    while (c != 0) {
        futex_wait(&state, 2);                     /* sleep, if state is still 2         */
        c = exchange(&state, 2);                   /* woke up: try to take it            */
    }
}
void unlock(void) {
    if (fetch_sub(&state, 1) != 1) {               /* it was 2: someone may wait         */
        state = 0;
        futex_wake(&state, 1);                     /* wake one waiter                    */
    }
}

The trace for two threads:

Step Thread A Thread B state
1 lock: CAS 0 to 1 succeeds, owns it 1
2 lock: CAS fails, sees 1; exchange to 2 returns 1, so not free 2
3 futex_wait(state, 2): sleeps 2
4 unlock: fetch_sub returns 2, so not 1; sets 0 and wakes one 0
5 wakes, exchange(2) returns 0: owns the lock 2
6 unlock: fetch_sub returns 2; sets 0 and wakes (no one waits, harmless) 0

Step 5 leaves the state at 2 although nobody waits. That is safe: at worst, B's unlock makes one needless wake call.

A version of this lock was written and tested, with 4 threads each doing a million lock and unlock pairs, and all runs gave the exact total of 4,000,000. The real counts of system calls show the benefit. Running a million lock/unlock pairs per thread under strace -c, the pthread mutex made:

1 thread :     1 futex call      (for 1,000,000 lock/unlock pairs)
2 threads:    17 futex calls     (for 2,000,000 pairs)
4 threads: 1,869 futex calls     (for 4,000,000 pairs)

Uncontended locking uses no system call at all (the single call was for thread exit and joining). Even with four threads fighting, fewer than one in two thousand lock operations went to the kernel, because the spinners' atomic instructions settle most of them. (strace itself slows the program and changes the timing, so the counts shown are only a rough guide.)

Futex

A futex is a Linux mechanism consisting of an integer in user memory and two kernel operations on it, wait (sleep if the integer still holds a given value) and wake (wake sleeping threads), which lets locks complete in user space with atomic instructions and call the kernel only under contention.

Example: an unlocked mutex is taken by a compare-and-swap with no system call, and a thread that must wait calls futex_wait to sleep.

Check yourself: 1. What are the three states of the mutex integer? 2. Why does futex_wait check that the value is still 2? 3. Why did one thread make almost no futex calls?