§28.15–28.17Different OS, Different Support … Summary

Solaris gave us park and unpark. Other kernels support sleeping locks their own way — and Linux’s way is worth reading closely, because it’s what actually runs beneath your pthread_mutex.

28.15 Different OS, Different Support

Linux provides the futex futex Linux's kernel-assisted lock support: a memory word with a per-futex in-kernel queue; futex_wait(addr, expected) sleeps iff the word still holds expected, futex_wake wakes one. glibc packs held-bit (sign) + waiter count into one integer, making the uncontended path a single atomic op. defined in ch. 28 — open in glossary : each one is a physical memory word with a per-futex in-kernel queue. Two calls: futex_wait(address, expected) puts the caller to sleep — unless the value at address no longer equals expected, in which case it returns immediately (closing the wakeup/waiting race by construction); futex_wake(address) wakes one queued waiter. The real glibc lock built on them (Figure 28.10, from lowlevellock.h):

void mutex_lock (int *mutex) {
  int v;
  /* Bit 31 was clear, we got the mutex (the fastpath) */
  if (atomic_bit_test_set (mutex, 31) == 0)
    return;
  atomic_increment (mutex);
  while (1) {
      if (atomic_bit_test_set (mutex, 31) == 0) {
          atomic_decrement (mutex);
          return;
      }
      /* We have to wait. First make sure the futex value
         we are monitoring is truly negative (locked). */
      v = *mutex;
      if (v >= 0)
        continue;
      futex_wait (mutex, v);
  }
}

void mutex_unlock (int *mutex) {
  /* Adding 0x80000000 to counter results in 0 if and
     only if there are not other interested threads */
  if (atomic_add_zero (mutex, 0x80000000))
    return;

  /* There are other threads waiting for this mutex,
     wake one of them up. */
  futex_wake (mutex);
}

Two elegances. One integer carries everything: the high bit says held-or-free (set it and the integer goes negative — locked), and the remaining bits count waiters. And the common case is optimized: an uncontended acquire-release is one atomic bit-test-set in, one atomic add out — no kernel, no queue, no waiting machinery. Puzzle through the rest and become a master of Linux locking (or at least somebody who listens when a book tells you to do something).

28.16 Two-Phase Locks

The Linux lock echoes an old idea — Dahm locks, early 1960s — now called the two-phase lock two-phase lock Spin briefly first (the lock may free any moment), THEN sleep if not acquired (Dahm locks, 1960s; Linux's futex lock is a one-spin variant). A hybrid whose payoff depends on hardware, thread counts, and workload. defined in ch. 28 — open in glossary . Insight: spinning is useful when the lock is about to be released. So phase one spins a while, hoping to grab the lock cheaply; failing that, phase two sleeps, waking only when the lock frees. The glibc code above is a one-spin variant; a generalization spins in a loop for a fixed time first. Another hybrid, like so many before — and whether it wins depends on hardware, thread counts, and workload details. Making a single general-purpose lock, good for all cases, remains quite a challenge.

28.17 Summary

Real locks today: some hardware support (a powerful atomic instruction) plus some OS support (park/unpark, futex) — highly tuned, endlessly refined. The full lineup, graded:

For more, read the Solaris or Linux lock code itself — a fascinating read — or David et al.’s comparison of locking strategies on modern multiprocessors.