Operating Systems Module 5 – Synchronisation: races, locks, semaphores and monitors

Mutexes, futexes and lock contention

What a mutex promises, how a futex lets it be taken and released without a system call while nobody waits, and what lock contention costs.

Advanced
20 minutes
Examples run with Python 3.14.8, Pyodide 314.0.7, Clang 21.0.0 and GCC 16.2.0
By MySmartCoPilot

Free: A mutex has an owner, and only the owner may release it · A futex keeps the uncontended lock in user space · Lock contention turns a mutex into a queue · Practise: write a futex mutex. With a pass: 3 in-depth parts and 3 interview answers, about 12 minutes.

What you will learn

Use pthread mutexes correctly, including the error-checking and recursive types
Explain how a futex keeps an uncontended lock out of the kernel, and why a waiter marks the lock
Measure what a lock costs with and without contention
Choose a lock's granularity, and recognise a lock convoy

Before you start

Hardware atomics, memory order and spinlocks

What you’ll learn · Before you start

What you will learn

Use pthread mutexes correctly, including the error-checking and recursive types
Explain how a futex keeps an uncontended lock out of the kernel, and why a waiter marks the lock
Measure what a lock costs with and without contention
Choose a lock's granularity, and recognise a lock convoy

Before you start

Hardware atomics, memory order and spinlocks

On this page

A thread that waits 10 ms for a spinlock burns 10 ms of a core; spinning pays only for short holds by running threads. Most locks are mutexes: a thread that finds one taken sleeps until the kernel wakes it. Linux builds them on futexes, so a mutex that nobody else wants costs one atomic instruction to take and one to release, with no system call. When many threads want the same mutex at once, that is lock contention: they queue for it, and the lock, not the processors, sets the pace.

A mutex has an owner, and only the owner may release it

A mutex: A lock with an owner: a thread that finds it held sleeps until it is free, and only the thread that locked it may unlock it. is a lock with an owner. pthread_mutex_lock takes it, blocking while another thread holds it, and pthread_mutex_unlock gives it back, which POSIX allows only the owner to do. What a broken rule does depends on the type, PTHREAD_MUTEX_ followed by one of these names; PTHREAD_MUTEX_INITIALIZER gives the default type:

Type	Its owner locks it again	Another thread releases it
NORMAL	Deadlock	Undefined
ERRORCHECK	EDEADLK	EPERM
RECURSIVE	A count goes up	EPERM
DEFAULT	Undefined	Undefined

A recursive mutex is free again once its owner has released it as often as it locked it. mutex_types.c breaks both rules on purpose:

mutex_types.c: locking twice and releasing from another thread C · types/mutex_types.c

// What each pthread mutex type does when a thread locks it twice, or unlocks a
// mutex that another thread holds.
#include <errno.h>
#include <pthread.h>
#include <stdio.h>

static pthread_mutex_t m;

static const char *result(int error) {
  return error == 0         ? "ok"
         : error == EDEADLK ? "EDEADLK"
         : error == EPERM   ? "EPERM"
         : error == EBUSY   ? "EBUSY"
                            : "another error";
}

static void *intruder(void *arg) {
  (void)arg;
  printf("  another thread unlocks it: %s\n", result(pthread_mutex_unlock(&m)));
  printf("  another thread tries it: %s\n", result(pthread_mutex_trylock(&m)));
  return NULL;
}

static void make(int type) {
  pthread_mutexattr_t attr;
  pthread_mutexattr_init(&attr);
  pthread_mutexattr_settype(&attr, type);
  pthread_mutex_init(&m, &attr);
  pthread_mutexattr_destroy(&attr);
}

static void another_thread(void) {
  pthread_t t;
  pthread_create(&t, NULL, intruder, NULL);
  pthread_join(t, NULL);
}

int main(void) {
  puts("error-checking mutex:");
  make(PTHREAD_MUTEX_ERRORCHECK);
  printf("  lock: %s\n", result(pthread_mutex_lock(&m)));
  printf("  lock again: %s\n", result(pthread_mutex_lock(&m)));
  another_thread();
  printf("  unlock: %s\n", result(pthread_mutex_unlock(&m)));
  printf("  unlock again: %s\n", result(pthread_mutex_unlock(&m)));
  pthread_mutex_destroy(&m);

  puts("recursive mutex:");
  make(PTHREAD_MUTEX_RECURSIVE);
  printf("  lock: %s\n", result(pthread_mutex_lock(&m)));
  printf("  lock again: %s\n", result(pthread_mutex_lock(&m)));
  printf("  unlock: %s\n", result(pthread_mutex_unlock(&m)));
  another_thread(); // the count is 1, so it is still held
  printf("  unlock: %s\n", result(pthread_mutex_unlock(&m)));
  printf("  unlock again: %s\n", result(pthread_mutex_unlock(&m)));
  pthread_mutex_destroy(&m);
  return 0;
}

Output

error-checking mutex:
  lock: ok
  lock again: EDEADLK
  another thread unlocks it: EPERM
  another thread tries it: EBUSY
  unlock: ok
  unlock again: EPERM
recursive mutex:
  lock: ok
  lock again: ok
  unlock: ok
  another thread unlocks it: EPERM
  another thread tries it: EBUSY
  unlock: ok
  unlock again: EPERM

Recorded with Apple clang version 21.0.0 (clang-2100.3.34.2) on macOS 26 arm64. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined mutex_types.c -o mutex_types && ./mutex_types

Use the error-checking type in tests, so that a second lock or a release by another thread fails at once, with the EDEADLK and EPERM above, instead of hanging. A recursive mutex: A mutex that its owner may lock again; it keeps a count and is free only after as many unlocks as locks. is rarely the fix it seems: it lets code that holds the lock call code that takes it again, which hides who holds what. Split such code into an entry point that takes the lock and a helper that does not.

Checkpoint

Check: Mutex ownership and the pthread mutex types

Question 1 of 2 A thread that holds an error-checking mutex calls pthread_mutex_lock on it again. What happens?
Choose one answer.

The call succeeds and a count goes up The call returns EDEADLK and the thread still holds the mutex once The mutex is released The thread blocks for ever

Show the answer: Question 1 of 2

Answer: The call returns EDEADLK and the thread still holds the mutex once

mutex_types.c printed "lock again: EDEADLK" for the error-checking mutex.
Question 2 of 2 A thread locks a recursive mutex twice and unlocks it once. Can another thread take it now?
Choose one answer.

Yes, but only after an EPERM No, the count is still 1, so the mutex is still held Yes, one unlock always frees a mutex No, a recursive mutex can never be taken by another thread

Show the answer: Question 2 of 2

Answer: No, the count is still 1, so the mutex is still held

In the run, another thread's unlock got EPERM and its trylock EBUSY until the second unlock.

A futex keeps the uncontended lock in user space

A futex: A 32-bit word in memory with two Linux system calls on it: FUTEX_WAIT sleeps only while the word holds an expected value, and FUTEX_WAKE wakes threads sleeping on it. is a 32-bit word in the program’s memory and two operations on it: FUTEX_WAIT sleeps only if the word still holds the value the caller passes, checking and sleeping in one atomic step, and FUTEX_WAKE wakes threads that sleep on the word. Mutexes built on futexes change the word with atomic instructions and enter the kernel only to sleep or to wake.

Ulrich Drepper’s mutex keeps in the word whether anyone may be asleep: 0 is free, 1 is locked, and 2 is locked with a thread that may be asleep. Locking compare-and-swaps 0 to 1; if that fails, it writes 2 and waits while the word is 2. Releasing puts 0 back and calls FUTEX_WAKE only if it took out a 2.

The checker below writes two designs in a small instruction set: xchg v exchanges v in; cas e n stores n if the word holds e; wait v b sleeps while the word holds v, then goes on at step b; wake wakes the other thread; jeq v b jumps to step b if the value just read was v. Both release the mutex alike, and only the three-state design marks the word before it sleeps:

One program · 14 languages Two futex mutexes, every schedule of two threads checked for a lost wake-up

Python 3.14 · main.py

DESIGNS = {
    "unmarked waiters": "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake",
    "three states": "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3;"
    " cs; xchg 0; jeq 1 10; wake",
}


Step = tuple[str, int, int]  # a step: its name and the numbers a and b


def explore(
    code: list[Step], pcs: list[int], word: int, asleep: list[bool], tally: list[int]
) -> None:
    runnable = [t for t in (0, 1) if pcs[t] < len(code) and not asleep[t]]
    if not runnable:  # over: stuck if a thread still sleeps
        tally[0] += 1
        tally[1] += True in asleep
    for t in runnable:
        op, a, b = code[pcs[t]]
        word2 = a if op == "xchg" else b if op == "cas" and word == a else word
        pc = b if op == "wait" else pcs[t] + 1
        while pc < len(code) and code[pc][0] == "jeq":  # jeq a b: to b if it read a
            pc = code[pc][2] if word == code[pc][1] else pc + 1
        pcs2 = pcs.copy()
        pcs2[t] = pc
        # wait sleeps while the word is a; wake wakes the other thread
        asleep2 = [False, False] if op == "wake" else asleep.copy()
        asleep2[t] = op == "wait" and word == a
        explore(code, pcs2, word2, asleep2, tally)


for name, text in DESIGNS.items():
    steps = [(s + " 0 0").split()[:3] for s in text.split("; ")]
    code = [(op, int(a), int(b)) for op, a, b in steps]
    tally = [0, 0]  # schedules, and those stuck with a thread asleep
    explore(code, [0, 0], 0, [False, False], tally)
    print(f"{name}: stuck in {tally[1]} of {tally[0]} schedules")

In Python: Each step is a tuple (name, a, b), and explore copies the lists it changes before it tries the next thread.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

const DESIGNS = {
  "unmarked waiters": "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake",
  "three states":
    "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; cs; xchg 0; jeq 1 10; wake",
};

function explore(code, pcs, word, asleep, tally) {
  const runnable = [0, 1].filter((t) => pcs[t] < code.length && !asleep[t]);
  if (runnable.length === 0) {
    // over: stuck if a thread still sleeps
    tally.schedules++;
    if (asleep.includes(true)) tally.stuck++;
  }
  for (const t of runnable) {
    const [op, a, b] = code[pcs[t]];
    const word2 = op === "xchg" ? a : op === "cas" && word === a ? b : word;
    let pc = op === "wait" ? b : pcs[t] + 1;
    while (pc < code.length && code[pc][0] === "jeq") {
      pc = word === code[pc][1] ? code[pc][2] : pc + 1; // jeq a b: to b if it read a
    }
    const pcs2 = [...pcs];
    pcs2[t] = pc;
    // wait sleeps while the word is a; wake wakes the other thread
    const asleep2 = op === "wake" ? [false, false] : [...asleep];
    asleep2[t] = op === "wait" && word === a;
    explore(code, pcs2, word2, asleep2, tally);
  }
}

for (const [name, text] of Object.entries(DESIGNS)) {
  const code = text.split("; ").map((s) => {
    const [op, a = 0, b = 0] = s.split(" ");
    return [op, Number(a), Number(b)];
  });
  const tally = { schedules: 0, stuck: 0 };
  explore(code, [0, 0], 0, [false, false], tally);
  console.log(`${name}: stuck in ${tally.stuck} of ${tally.schedules} schedules`);
}

In JavaScript: Steps are arrays [name, a, b]; a step without numbers gets 0 for both through default values in the destructuring.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.Arrays;

public class Main {
  static final String[] NAMES = {"unmarked waiters", "three states"};
  static final String[] CODES = {
    "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake",
    "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; cs; xchg 0; jeq 1 10; wake"
  };

  record Op(String op, int a, int b) {}

  static int schedules, stuck;

  static void explore(Op[] code, int[] pcs, int word, boolean[] asleep) {
    boolean over = true;
    for (int t = 0; t < 2; t++) {
      if (pcs[t] == code.length || asleep[t]) continue;
      over = false;
      Op s = code[pcs[t]];
      int word2 =
          s.op().equals("xchg") ? s.a() : s.op().equals("cas") && word == s.a() ? s.b() : word;
      int pc = s.op().equals("wait") ? s.b() : pcs[t] + 1;
      while (pc < code.length && code[pc].op().equals("jeq")) {
        pc = word == code[pc].a() ? code[pc].b() : pc + 1; // jeq a b: to b if it read a
      }
      int[] pcs2 = pcs.clone();
      pcs2[t] = pc;
      // wait sleeps while the word is a; wake wakes the other thread
      boolean[] asleep2 = s.op().equals("wake") ? new boolean[2] : asleep.clone();
      asleep2[t] = s.op().equals("wait") && word == s.a();
      explore(code, pcs2, word2, asleep2);
    }
    if (over) { // stuck if a thread still sleeps
      schedules++;
      stuck += asleep[0] || asleep[1] ? 1 : 0;
    }
  }

  public static void main(String[] args) {
    for (int i = 0; i < NAMES.length; i++) {
      Op[] code =
          Arrays.stream(CODES[i].split("; "))
              .map(s -> (s + " 0 0").split(" "))
              .map(p -> new Op(p[0], Integer.parseInt(p[1]), Integer.parseInt(p[2])))
              .toArray(Op[]::new);
      schedules = stuck = 0;
      explore(code, new int[2], 0, new boolean[2]);
      System.out.println(NAMES[i] + ": stuck in " + stuck + " of " + schedules + " schedules");
    }
  }
}

In Java: A record holds each step, and the two tallies are static fields that main resets for each design.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <array>
#include <print>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

const std::array<std::pair<const char *, const char *>, 2> kDesigns{{
    {"unmarked waiters",
     "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake"},
    {"three states", "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; "
                     "cs; xchg 0; jeq 1 10; wake"},
}};

struct Op {
  std::string op;
  int a = 0, b = 0;
};
int schedules, stuck;

void explore(const std::vector<Op> &code, std::array<int, 2> pcs, int word,
             std::array<bool, 2> asleep) {
  bool over = true;
  for (int t = 0; t < 2; t++) {
    if (pcs[t] == std::ssize(code) || asleep[t])
      continue;
    over = false;
    const auto &[op, a, b] = code[pcs[t]];
    int word2 = op == "xchg" ? a : op == "cas" && word == a ? b : word;
    int pc = op == "wait" ? b : pcs[t] + 1;
    while (pc < std::ssize(code) && code[pc].op == "jeq") // to b if it read a
      pc = word == code[pc].a ? code[pc].b : pc + 1;
    auto pcs2 = pcs;
    pcs2[t] = pc;
    // wait sleeps while the word is a; wake wakes the other thread
    auto asleep2 = op == "wake" ? std::array<bool, 2>{} : asleep;
    asleep2[t] = op == "wait" && word == a;
    explore(code, pcs2, word2, asleep2);
  }
  if (over) { // stuck if a thread still sleeps
    schedules++;
    stuck += asleep[0] || asleep[1];
  }
}

int main() {
  for (const auto &[name, text] : kDesigns) {
    std::vector<Op> code;
    std::istringstream steps(text);
    for (std::string step; std::getline(steps, step, ';');)
      std::istringstream(step) >> code.emplace_back().op >> code.back().a >>
          code.back().b;
    schedules = stuck = 0;
    explore(code, {0, 0}, 0, {false, false});
    std::println("{}: stuck in {} of {} schedules", name, stuck, schedules);
  }
}

In C++: pcs and asleep are std::array values, so each recursive call works on its own copy of the state.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

(string Name, string Code)[] designs =
[
    ("unmarked waiters", "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake"),
    ("three states",
        "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; cs; xchg 0; jeq 1 10; wake"),
];

foreach (var (name, text) in designs)
{
    var code = text.Split("; ").Select(s => (s + " 0 0").Split(' '))
        .Select(p => (Op: p[0], A: int.Parse(p[1]), B: int.Parse(p[2]))).ToArray();
    int[] tally = [0, 0]; // schedules, and those stuck with a thread asleep
    Explore(code, [0, 0], 0, [false, false], tally);
    Console.WriteLine($"{name}: stuck in {tally[1]} of {tally[0]} schedules");
}

static void Explore(
    (string Op, int A, int B)[] code, int[] pcs, int word, bool[] asleep, int[] tally)
{
    bool over = true;
    for (int t = 0; t < 2; t++)
    {
        if (pcs[t] == code.Length || asleep[t])
        {
            continue;
        }
        over = false;
        var (op, a, b) = code[pcs[t]];
        int word2 = op == "xchg" ? a : op == "cas" && word == a ? b : word;
        int pc = op == "wait" ? b : pcs[t] + 1;
        while (pc < code.Length && code[pc].Op == "jeq") // jeq a b: to b if it read a
        {
            pc = word == code[pc].A ? code[pc].B : pc + 1;
        }
        int[] pcs2 = (int[])pcs.Clone();
        pcs2[t] = pc;
        // wait sleeps while the word is a; wake wakes the other thread
        bool[] asleep2 = op == "wake" ? [false, false] : (bool[])asleep.Clone();
        asleep2[t] = op == "wait" && word == a;
        Explore(code, pcs2, word2, asleep2, tally);
    }
    if (over) // stuck if a thread still sleeps
    {
        tally[0]++;
        tally[1] += asleep[0] || asleep[1] ? 1 : 0;
    }
}

In C#: The steps are named tuples, and Clone() copies the small arrays before each branch.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>
#include <string.h>

static const char *const DESIGNS[][2] = {
    {"unmarked waiters",
     "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake"},
    {"three states", "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; "
                     "cs; xchg 0; jeq 1 10; wake"}};

typedef struct {
  char op[8];
  int a, b;
} Op;
static Op code[16];
static int len, schedules, stuck;

static bool is(int pc, const char *op) { return !strcmp(code[pc].op, op); }

static void explore(int *pcs, int word, bool *asleep) {
  bool over = true;
  for (int t = 0; t < 2; t++) {
    if (pcs[t] == len || asleep[t])
      continue;
    over = false;
    Op s = code[pcs[t]];
    int word2 = is(pcs[t], "xchg")                 ? s.a
                : is(pcs[t], "cas") && word == s.a ? s.b
                                                   : word;
    int pc = is(pcs[t], "wait") ? s.b : pcs[t] + 1;
    while (pc < len && is(pc, "jeq")) // jeq a b: to b if it read a
      pc = word == code[pc].a ? code[pc].b : pc + 1;
    int pcs2[2] = {pcs[0], pcs[1]};
    pcs2[t] = pc;
    // wait sleeps while the word is a; wake wakes the other thread
    bool wake = is(pcs[t], "wake");
    bool asleep2[2] = {asleep[0] && !wake, asleep[1] && !wake};
    asleep2[t] = is(pcs[t], "wait") && word == s.a;
    explore(pcs2, word2, asleep2);
  }
  if (over) { // stuck if a thread still sleeps
    schedules++;
    stuck += asleep[0] || asleep[1];
  }
}

int main(void) {
  for (int i = 0; i < 2; i++) {
    memset(code, 0, sizeof code);
    len = schedules = stuck = 0;
    for (const char *s = DESIGNS[i][1]; s; s = strchr(s, ';')) {
      s += *s == ';' ? 2 : 0;
      sscanf(s, "%7[a-z] %d %d", code[len].op, &code[len].a, &code[len].b);
      len++;
    }
    explore((int[]){0, 0}, 0, (bool[]){false, false});
    printf("%s: stuck in %d of %d schedules\n", DESIGNS[i][0], stuck,
           schedules);
  }
}

In C: The design being checked lives in a global array of steps, and sscanf leaves a and b at 0 for a step without numbers.

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

const DESIGNS = [
    'unmarked waiters' => 'xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake',
    'three states' => 'cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; '
        . 'cs; xchg 0; jeq 1 10; wake',
];

/**
 * @param list<array{string, int, int}> $code
 * @param list<int> $pcs
 * @param list<bool> $asleep
 * @param list<int> $tally
 */
function explore(array $code, array $pcs, int $word, array $asleep, array &$tally): void
{
    $runnable = array_filter([0, 1], fn(int $t): bool => $pcs[$t] < count($code) && !$asleep[$t]);
    if (!$runnable) { // over: stuck if a thread still sleeps
        $tally[0]++;
        $tally[1] += in_array(true, $asleep, true) ? 1 : 0;
    }
    foreach ($runnable as $t) {
        [$op, $a, $b] = $code[$pcs[$t]];
        $word2 = $op === 'xchg' ? $a : ($op === 'cas' && $word === $a ? $b : $word);
        $pc = $op === 'wait' ? $b : $pcs[$t] + 1;
        while ($pc < count($code) && $code[$pc][0] === 'jeq') { // jeq a b: to b if it read a
            $pc = $word === $code[$pc][1] ? $code[$pc][2] : $pc + 1;
        }
        $pcs2 = $pcs;
        $pcs2[$t] = $pc;
        // wait sleeps while the word is a; wake wakes the other thread
        $asleep2 = $op === 'wake' ? [false, false] : $asleep;
        $asleep2[$t] = $op === 'wait' && $word === $a;
        explore($code, $pcs2, $word2, $asleep2, $tally);
    }
}

foreach (DESIGNS as $name => $text) {
    $code = array_map(function (string $step): array {
        [$op, $a, $b] = explode(' ', "$step 0 0");
        return [$op, (int) $a, (int) $b];
    }, explode('; ', $text));
    $tally = [0, 0]; // schedules, and those stuck with a thread asleep
    explore($code, [0, 0], 0, [false, false], $tally);
    echo "$name: stuck in $tally[1] of $tally[0] schedules\n";
}

In PHP: Arrays are values in PHP, so $pcs2 = $pcs copies the state, and the tally is passed by reference.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

const NAMES: [&str; 2] = ["unmarked waiters", "three states"];
const CODES: [&str; 2] = [
    "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake",
    "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; cs; xchg 0; jeq 1 10; wake",
];

type Op<'a> = (&'a str, i32, i32);

/// Counts the schedules, and those that leave a thread asleep for ever.
fn explore(code: &[Op], pcs: [usize; 2], word: i32, asleep: [bool; 2], tally: &mut [u32; 2]) {
    let mut over = true;
    for t in (0..2).filter(|&t| pcs[t] < code.len() && !asleep[t]) {
        over = false;
        let (op, a, b) = code[pcs[t]];
        let word2 = match op {
            "xchg" => a,
            "cas" if word == a => b,
            _ => word,
        };
        let mut pc = if op == "wait" { b as usize } else { pcs[t] + 1 };
        while pc < code.len() && code[pc].0 == "jeq" {
            let (_, seen, to) = code[pc]; // jeq a b: to b if it read a
            pc = if word == seen { to as usize } else { pc + 1 };
        }
        let mut pcs2 = pcs;
        pcs2[t] = pc;
        // wait sleeps while the word is a; wake wakes the other thread
        let mut asleep2 = if op == "wake" { [false; 2] } else { asleep };
        asleep2[t] = op == "wait" && word == a;
        explore(code, pcs2, word2, asleep2, tally);
    }
    if over {
        tally[0] += 1;
        tally[1] += u32::from(asleep.contains(&true));
    }
}

fn main() {
    let number = |n: Option<&str>| n.map_or(0, |n| n.parse().unwrap());
    for (name, text) in NAMES.iter().zip(CODES) {
        let mut code = Vec::new();
        for step in text.split("; ") {
            let mut words = step.split(' ');
            let op = words.next().unwrap();
            code.push((op, number(words.next()), number(words.next())));
        }
        let mut tally = [0, 0];
        explore(&code, [0, 0], 0, [false; 2], &mut tally);
        println!("{name}: stuck in {} of {} schedules", tally[1], tally[0]);
    }
}

In Rust: Arrays such as [usize; 2] are Copy, so let mut pcs2 = pcs gives each branch its own state; the tally is a &mut borrow.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

const DESIGNS: Record<string, string> = {
  "unmarked waiters": "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake",
  "three states":
    "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; cs; xchg 0; jeq 1 10; wake",
};

type Op = [op: string, a: number, b: number];
type Tally = { schedules: number; stuck: number };

function explore(code: Op[], pcs: number[], word: number, asleep: boolean[], tally: Tally): void {
  const runnable = [0, 1].filter((t) => pcs[t] < code.length && !asleep[t]);
  if (runnable.length === 0) {
    // over: stuck if a thread still sleeps
    tally.schedules++;
    if (asleep.includes(true)) tally.stuck++;
  }
  for (const t of runnable) {
    const [op, a, b] = code[pcs[t]];
    const word2 = op === "xchg" ? a : op === "cas" && word === a ? b : word;
    let pc = op === "wait" ? b : pcs[t] + 1;
    while (pc < code.length && code[pc][0] === "jeq") {
      pc = word === code[pc][1] ? code[pc][2] : pc + 1; // jeq a b: to b if it read a
    }
    const pcs2 = [...pcs];
    pcs2[t] = pc;
    // wait sleeps while the word is a; wake wakes the other thread
    const asleep2 = op === "wake" ? [false, false] : [...asleep];
    asleep2[t] = op === "wait" && word === a;
    explore(code, pcs2, word2, asleep2, tally);
  }
}

for (const [name, text] of Object.entries(DESIGNS)) {
  const code = text.split("; ").map((s): Op => {
    const [op, a = "0", b = "0"] = s.split(" ");
    return [op, Number(a), Number(b)];
  });
  const tally: Tally = { schedules: 0, stuck: 0 };
  explore(code, [0, 0], 0, [false, false], tally);
  console.log(`${name}: stuck in ${tally.stuck} of ${tally.schedules} schedules`);
}

In TypeScript: A labelled tuple type names the parts of a step; otherwise the program is the JavaScript one.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"strings"
)

var designs = [][2]string{
	{"unmarked waiters", "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake"},
	{"three states", "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; " +
		"cs; xchg 0; jeq 1 10; wake"},
}

type op struct {
	name string
	a, b int
}

// explore counts the schedules, and those that leave a thread asleep for ever.
func explore(code []op, pcs [2]int, word int, asleep [2]bool, tally *[2]int) {
	over := true
	for t := 0; t < 2; t++ {
		if pcs[t] == len(code) || asleep[t] {
			continue
		}
		over = false
		s := code[pcs[t]]
		word2, pc, asleep2 := word, pcs[t]+1, asleep
		switch {
		case s.name == "xchg":
			word2 = s.a
		case s.name == "cas" && word == s.a:
			word2 = s.b
		case s.name == "wait": // sleeps while the word is a
			pc, asleep2[t] = s.b, word == s.a
		case s.name == "wake": // wakes the other thread
			asleep2 = [2]bool{}
		}
		for pc < len(code) && code[pc].name == "jeq" { // jeq a b: to b if it read a
			if word == code[pc].a {
				pc = code[pc].b
			} else {
				pc++
			}
		}
		pcs2 := pcs
		pcs2[t] = pc
		explore(code, pcs2, word2, asleep2, tally)
	}
	if over {
		tally[0]++
		if asleep[0] || asleep[1] {
			tally[1]++
		}
	}
}

func main() {
	for _, d := range designs {
		var code []op
		for _, step := range strings.Split(d[1], "; ") {
			var s op
			fmt.Sscan(step, &s.name, &s.a, &s.b) // a step without numbers keeps a and b at 0
			code = append(code, s)
		}
		var tally [2]int
		explore(code, [2]int{}, 0, [2]bool{}, &tally)
		fmt.Printf("%s: stuck in %d of %d schedules\n", d[0], tally[1], tally[0])
	}
}

In Go: Arrays are values, so pcs2 := pcs copies the state, and fmt.Sscan leaves a and b at 0 when a step has no numbers.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

let designs = [
  ("unmarked waiters", "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake"),
  (
    "three states",
    "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; cs; xchg 0; jeq 1 10; wake"
  ),
]

typealias Op = (op: String, a: Int, b: Int)

// Counts the schedules, and those that leave a thread asleep for ever.
func explore(_ code: [Op], _ pcs: [Int], _ word: Int, _ asleep: [Bool], _ tally: inout [Int]) {
  let runnable = [0, 1].filter { pcs[$0] < code.count && !asleep[$0] }
  if runnable.isEmpty {
    tally[0] += 1
    tally[1] += asleep.contains(true) ? 1 : 0
  }
  for t in runnable {
    let (op, a, b) = code[pcs[t]]
    let word2 = op == "xchg" ? a : op == "cas" && word == a ? b : word
    var pc = op == "wait" ? b : pcs[t] + 1
    while pc < code.count && code[pc].op == "jeq" {  // jeq a b: to b if it read a
      pc = word == code[pc].a ? code[pc].b : pc + 1
    }
    var pcs2 = pcs
    pcs2[t] = pc
    // wait sleeps while the word is a; wake wakes the other thread
    var asleep2 = op == "wake" ? [false, false] : asleep
    asleep2[t] = op == "wait" && word == a
    explore(code, pcs2, word2, asleep2, &tally)
  }
}

for (name, text) in designs {
  let code = text.split(separator: ";").map { step -> Op in
    let words = step.split(separator: " ").map(String.init) + ["0", "0"]
    return (words[0], Int(words[1]) ?? 0, Int(words[2]) ?? 0)
  }
  var tally = [0, 0]
  explore(code, [0, 0], 0, [false, false], &tally)
  print("\(name): stuck in \(tally[1]) of \(tally[0]) schedules")
}

In Swift: Arrays are values, so var pcs2 = pcs copies them, and the tally is an inout parameter passed with &.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

DESIGNS = {
  'unmarked waiters' => 'xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake',
  'three states' => 'cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; ' \
                    'cs; xchg 0; jeq 1 10; wake'
}.freeze

# A point in a schedule: each thread's next step, the futex word and who sleeps.
State = Struct.new(:pcs, :word, :asleep)

# Follows the jumps from step pos: jeq a b goes to b if seen is a.
def jump(code, pos, seen)
  pos = seen == code[pos][1] ? code[pos][2] : pos + 1 while pos < code.size && code[pos][0] == 'jeq'
  pos
end

# The word after a step: xchg a writes a, and cas a b writes b if the word was a.
def written(instr, word)
  op, arg, to = instr
  return arg if op == 'xchg'

  op == 'cas' && word == arg ? to : word
end

# Who sleeps after a thread's step: wait sleeps while the word is a; wake wakes the other.
def sleepers(state, thread, instr)
  slept = instr[0] == 'wake' ? [false, false] : state.asleep.dup
  slept[thread] = instr[0] == 'wait' && state.word == instr[1]
  slept
end

# The state after a thread takes its next step.
def step(code, state, thread)
  instr = code[state.pcs[thread]]
  pcs = state.pcs.dup
  pcs[thread] = jump(code, instr[0] == 'wait' ? instr[2] : pcs[thread] + 1, state.word)
  State.new(pcs, written(instr, state.word), sleepers(state, thread, instr))
end

# Counts the schedules that finish, and those that leave a thread asleep for ever.
def explore(code, state, tally)
  runnable = [0, 1].select { |t| state.pcs[t] < code.size && !state.asleep[t] }
  tally[state.asleep.any? ? :stuck : :done] += 1 if runnable.empty?
  runnable.each { |t| explore(code, step(code, state, t), tally) }
end

DESIGNS.each do |name, text|
  code = text.split('; ').map { |s| "#{s} 0 0".split.then { |w| [w[0], w[1].to_i, w[2].to_i] } }
  tally = { done: 0, stuck: 0 }
  explore(code, State.new([0, 0], 0, [false, false]), tally)
  puts "#{name}: stuck in #{tally[:stuck]} of #{tally.values.sum} schedules"
end

In Ruby: A Struct holds a point in the schedule, and small methods compute each part of the next one.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

val designs =
    listOf(
        "unmarked waiters" to "xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake",
        "three states" to
            "cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; cs; xchg 0; jeq 1 10; wake",
    )

// A step: its name and the numbers a and b.
typealias Op = Triple<String, Int, Int>

// Counts the schedules, and those that leave a thread asleep for ever.
fun explore(
    code: List<Op>,
    pcs: IntArray,
    word: Int,
    asleep: BooleanArray,
    tally: IntArray,
) {
    val runnable = (0..1).filter { pcs[it] < code.size && !asleep[it] }
    if (runnable.isEmpty()) {
        tally[0]++
        if (asleep.any { it }) tally[1]++
    }
    for (t in runnable) {
        val (op, a, b) = code[pcs[t]]
        val word2 =
            when {
                op == "xchg" -> a
                op == "cas" && word == a -> b
                else -> word
            }
        var pc = if (op == "wait") b else pcs[t] + 1
        while (pc < code.size && code[pc].first == "jeq") { // jeq a b: to b if it read a
            pc = if (word == code[pc].second) code[pc].third else pc + 1
        }
        val pcs2 = pcs.copyOf()
        pcs2[t] = pc
        // wait sleeps while the word is a; wake wakes the other thread
        val asleep2 = if (op == "wake") BooleanArray(2) else asleep.copyOf()
        asleep2[t] = op == "wait" && word == a
        explore(code, pcs2, word2, asleep2, tally)
    }
}

fun main() {
    for ((name, text) in designs) {
        val code =
            text.split("; ").map {
                val words = "$it 0 0".split(" ")
                Op(words[0], words[1].toInt(), words[2].toInt())
            }
        val tally = IntArray(2)
        explore(code, IntArray(2), 0, BooleanArray(2), tally)
        println("$name: stuck in ${tally[1]} of ${tally[0]} schedules")
    }
}

In Kotlin: A Triple holds each step, and copyOf() copies the arrays before each branch.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

const designs = [
  ('unmarked waiters', 'xchg 1; jeq 0 3; wait 1 0; cs; xchg 0; jeq 1 7; wake'),
  (
    'three states',
    'cas 0 1; jeq 0 6; jeq 2 5; xchg 2; jeq 0 6; wait 2 3; cs; xchg 0; jeq 1 10; wake',
  ),
];

typedef Op = ({String op, int a, int b});

// Counts the schedules, and those that leave a thread asleep for ever.
void explore(
  List<Op> code,
  List<int> pcs,
  int word,
  List<bool> asleep,
  List<int> tally,
) {
  final runnable = [0, 1].where((t) => pcs[t] < code.length && !asleep[t]);
  if (runnable.isEmpty) {
    tally[0]++;
    if (asleep.contains(true)) tally[1]++;
  }
  for (final t in runnable) {
    final (:op, :a, :b) = code[pcs[t]];
    final word2 = op == 'xchg' ? a : (op == 'cas' && word == a ? b : word);
    var pc = op == 'wait' ? b : pcs[t] + 1;
    // jeq a b: to b if it read a
    while (pc < code.length && code[pc].op == 'jeq') {
      pc = word == code[pc].a ? code[pc].b : pc + 1;
    }
    final pcs2 = [...pcs];
    pcs2[t] = pc;
    // wait sleeps while the word is a; wake wakes the other thread
    final asleep2 = op == 'wake' ? [false, false] : [...asleep];
    asleep2[t] = op == 'wait' && word == a;
    explore(code, pcs2, word2, asleep2, tally);
  }
}

void main() {
  for (final (name, text) in designs) {
    final code = [
      for (final step in text.split('; '))
        if ('$step 0 0'.split(' ') case [final op, final a, final b, ...])
          (op: op, a: int.parse(a), b: int.parse(b)),
    ];
    final tally = [0, 0];
    explore(code, [0, 0], 0, [false, false], tally);
    print('$name: stuck in ${tally[1]} of ${tally[0]} schedules');
  }
}

In Dart: Each step is a record with named fields, built by a pattern that matches the split words.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

What every language printed

unmarked waiters: stuck in 6 of 12 schedules
three states: stuck in 0 of 50 schedules

Without the mark, 6 of 12 schedules end with a thread asleep for ever, a lost wake-up: A thread asleep waiting for a wake-up that never comes, because the thread that should wake it saw nothing that said anyone was waiting.; with it, none of the 50 do. Step through one of the 6:

Interactive · message by message A lost wake-up in a futex mutex without the mark Step through two threads using a mutex whose waiters sleep on 1 without writing 2, and see the unlock miss the sleeper.

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text

A takes the lock. Thread A exchanges 1 into the word and gets back 0, so the mutex was free and is now A's. No system call.
B finds it taken. Thread B exchanges 1 too and gets back 1, so A holds the mutex. Writing 1 over 1 tells nobody that B is waiting.
B sleeps. B calls futex wait with the value 1. The word still holds 1, so the kernel puts B to sleep on it.
A unlocks. A exchanges 0 in and gets back 1, the value that means nobody waits. So A skips the wake, as a cheap unlock should.
B sleeps for ever. The mutex is free, but B is still asleep and nothing will wake it. With the three-state design B would have written 2 before sleeping, and A's exchange would have returned 2 and woken it.

Checkpoint

Check: How a futex mutex avoids system calls, and why waiters mark it

Question 1 of 2 Why does FUTEX_WAIT take the value the caller expects the word to hold?
Choose one answer.

To tell the kernel how many threads to wake later To choose how long to sleep So that the kernel can store that value in the word So that the kernel sleeps only if the word has not changed since the caller looked, in one atomic step

Show the answer: Question 1 of 2

Answer: So that the kernel sleeps only if the word has not changed since the caller looked, in one atomic step

Checking and sleeping as one step is what lets a wake-up that comes just before the sleep still count.
Question 2 of 2 In the checker, the design whose waiters sleep on 1 without writing 2 got stuck in 6 of 12 schedules. Why?
Choose one answer.

The unlock makes too many system calls Two threads entered the critical section at once Its unlock wakes only when it takes out a 2, and nobody ever writes 2, so a sleeper is never woken The waiter spins for ever

Show the answer: Question 2 of 2

Answer: Its unlock wakes only when it takes out a 2, and nobody ever writes 2, so a sleeper is never woken

Writing 2 before sleeping is how a waiter tells the next unlock that a wake is needed.

Lock contention turns a mutex into a queue

lock contention: Threads waiting for a lock that another thread holds; when it is high, the lock behaves like a queue, and waiting grows fast as requests near what the lock can serve. is threads waiting for a lock that another thread holds. A lock serves one holder at a time, like a single server with a queue: held for h seconds, it can serve at most 1/h acquisitions a second. Treat a lock held for 10 ms, around a disk write for example, as a server with μ = 100 a second, and drag the arrival rate:

Interactive · change it and see Getting through a lock held for 10 ms Requests arrive at random at an average rate and one server handles them one at a time. Raise the arrival rate towards the service rate and watch the time in the system.

At 80 % utilisation a request spends 50 ms in the system on average, 5 times its 10 ms of service: the rest is waiting. Little's law: L = λW = 4 requests in the system.

Mean time in the system (W) 50 ms

Utilisation (ρ) 80 %

Mean wait before service 40 ms

Mean number in the system (L = λW) 4

The numbers as a table

Mean time in the system with μ = 100 a second
Utilisation	Mean time in the system
50 %	20 ms
70 %	33.3 ms
80 %	50 ms
90 %	100 ms
95 %	200 ms
99 %	1,000 ms

At 80 acquisitions a second a thread spends 50 ms on average getting through the lock, 40 of them waiting; at 95 a second, 200 ms. A faster lock does not cure that: hold the lock for less time, or split the data so that threads need different locks. When a holder stops running, the others queue behind it, and a lock that serves them strictly in order keeps them in that queue, a lock convoy: A queue of threads behind a busy lock that outlasts its cause, started by a holder that stops running and kept going by a lock that serves waiters strictly in order..

Key idea

A mutex costs an atomic instruction while it is free and a sleep and a wake-up when it is not, so the work is to keep it free: hold it briefly, and split it where a measurement shows threads waiting.

Checkpoint

Check: Lock contention as a queue

Question 1 of 2 A lock is held for 10 ms on average and asked for 95 times a second. In the queueing model, how many milliseconds does a thread spend getting through the lock on average?
Type a number.
Your answer ms

Show the answer: Question 1 of 2

Answer: 200 ms

With μ = 100 and λ = 95 the mean time in the system is 1 / (100 − 95) s, 200 ms, twenty times the 10 ms hold.
Question 2 of 2 Which situation starts a lock convoy?
Choose one answer.

A lock held for a few nanoseconds Two threads that take two locks in opposite orders A lock that nobody else wants The holder of a busy lock stops running, and the other threads queue behind it

Show the answer: Question 2 of 2

Answer: The holder of a busy lock stops running, and the other threads queue behind it

Convoys come from a hot lock plus a holder that is preempted or blocks while holding it.

Practise: write a futex mutex

The exercise models the futex word as a dictionary and the kernel as an object with wait and wake. Write lock and unlock so that a free mutex never calls the kernel and no waiter is lost:

Exercise · Medium · Python

Write the lock and unlock of a futex mutex

The mutex is one word, word["value"]: 0 means free, 1 locked, and 2 locked with a thread that may be asleep. Two helpers change it in one indivisible step and return the old value: cas(word, expected, new) stores new only if the value is expected, and exchange(word, new) always stores new.

The kernel is an object with two calls. kernel.wait(word, expected) sleeps only while the value is still expected and returns when another thread wakes it; kernel.wake(word) wakes one sleeping thread.

Write lock(word, kernel) and unlock(word, kernel). A free mutex must be taken and given back without calling the kernel at all, a thread that waits must mark the word with 2 before it sleeps, and unlock must wake a thread only when the value it takes out says that one may be asleep.

Starter code · futex.py

def cas(word, expected, new):
    """Stores new in word["value"] if it holds expected, and returns the old value."""
    old = word["value"]
    if old == expected:
        word["value"] = new
    return old


def exchange(word, new):
    """Stores new in word["value"] and returns the old value."""
    old = word["value"]
    word["value"] = new
    return old


def lock(word, kernel):
    """Takes the mutex: 0 free, 1 locked, 2 locked with a thread that may be asleep."""
    # Replace this line with your code.
    word["value"] = 1


def unlock(word, kernel):
    """Gives the mutex back, waking one thread only if one may be asleep."""
    # Replace this line with your code.
    word["value"] = 0

The sample tests · test_futex.py

from futex import lock, unlock


class Kernel:
    """Records the calls; a wait that would sleep lets the holder unlock, then returns."""

    def __init__(self):
        self.calls = []

    def wait(self, word, expected):
        self.calls.append(("wait", expected))
        if word["value"] == expected:
            word["value"] = 0  # the holder unlocks and wakes this thread

    def wake(self, word):
        self.calls.append(("wake",))


def test_free_mutex_is_taken_without_the_kernel():
    """takes a free mutex with no system call"""
    word, kernel = {"value": 0}, Kernel()
    lock(word, kernel)
    assert word["value"] == 1
    assert kernel.calls == []


def test_unlock_without_waiters_skips_the_wake():
    """gives back a mutex that nobody waits for with no system call"""
    word, kernel = {"value": 1}, Kernel()
    unlock(word, kernel)
    assert word["value"] == 0
    assert kernel.calls == []


def test_waiter_marks_the_word_before_it_sleeps():
    """marks a held mutex with 2, sleeps on 2 and takes the mutex when it is woken"""
    word, kernel = {"value": 1}, Kernel()
    lock(word, kernel)
    assert kernel.calls == [("wait", 2)]
    assert word["value"] == 2


def test_unlock_wakes_when_someone_may_sleep():
    """wakes one thread when the value it takes out is 2"""
    word, kernel = {"value": 2}, Kernel()
    unlock(word, kernel)
    assert word["value"] == 0
    assert kernel.calls == [("wake",)]

A hint

Try cas(word, 0, 1) first: if it returns 0 the mutex was free and is now yours. Otherwise write 2 with exchange and wait on 2 until an exchange returns 0. In unlock, exchange(word, 0) tells you whether the value was 2.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

The self-check below begins with the idea your answers so far show you know least.

Inside the three-state mutex: a handoff step by step, and its system calls counted Pro: opens with a Pro, Premium or Ultimate pass

The three-state mutex is a few lines long, and each line answers a race. This part steps through a contended handoff, shows why a waiter loops and why a release can wake nobody, counts the real calls on this Mac, and covers what the kernel adds for priorities.

In this part:

A contended handoff, step by step
The calls of the real thing on this Mac
What the kernel adds for priorities

1 diagram · 2 runnable examples (C, Python) · about 5 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

What a lock costs with and without contention, and what fairness costs, measured Pro: opens with a Pro, Premium or Ultimate pass

A lock’s price depends almost entirely on whether another thread wants it at the same moment. This part times four locks on this Mac, alone and shared by four threads, and shows how a lock that serves waiters strictly in order can be thousands of times slower than one that does not.

In this part:

Four locks, alone and shared by four threads
Why first come, first served is so slow

2 runnable examples (C, Python) · about 3 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Choosing a lock's granularity, and breaking up a lock convoy Pro: opens with a Pro, Premium or Ultimate pass

Contention is cured by changing who needs a lock and for how long, not by a faster lock. This part compares the usual ways to split a lock, follows a convoy from its start to its end, and gives the rules that keep fine-grained locking free of deadlock.

In this part:

One lock, stripes, a lock per object, or shards
How a convoy forms, and how to break it
Rules for locking finely without deadlock

about 6 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

The warm-up comes with its full answer:

Fresher to mid · Warm-up

What is a futex, and why are Linux mutexes built on one?

A futex is a 32-bit word in the program's memory plus two system calls on it: FUTEX_WAIT sleeps only if the word still holds the value the caller expects, checking and sleeping in one atomic step, and FUTEX_WAKE wakes threads that sleep on the word. A mutex built on it keeps its state in the word, such as 0 for free, 1 for locked and 2 for locked with possible waiters. Taking a free mutex is one compare-and-swap, and releasing one that nobody waits for is one exchange, so the uncontended case never enters the kernel; only a thread that must wait, or an unlock that may have a sleeper to wake, makes a system call. Most locks are free most of the time, so most lock operations cost a few nanoseconds instead of a system call each.

Three harder questions follow: a lock held across a network call, a cache that stops scaling behind one lock and a mutex used as a signal. Pick a first move for two of them; each choice explains itself:

Checkpoint

Your first decision

Question 1 of 2 A service holds a mutex while it sends a log line over the network; under load p99 latency jumps while CPU stays low. What do you check first?
Choose one answer.

Whether the log line is too long How long the mutex is held, since a network call inside it makes every other thread queue Whether more threads would use the idle CPU Whether a faster mutex is available

Show the answer: Question 1 of 2

Answer: How long the mutex is held, since a network call inside it makes every other thread queue

Contention is about how long the lock is held, and a network call makes that long.
Question 2 of 2 A colleague locks a mutex in thread A and unlocks it in thread B to say that data is ready. What do you say first?
Choose one answer.

Use a recursive mutex instead Only the owner may unlock a mutex; this needs a signalling tool such as a semaphore or a condition variable It works, as long as B unlocks only once Add a sleep in B before the unlock

Show the answer: Question 2 of 2

Answer: Only the owner may unlock a mutex; this needs a signalling tool such as a semaphore or a condition variable

mutex_types.c showed EPERM for exactly this unlock on the error-checking and recursive types.

Mid to senior

A service writes a log line to a network collector while holding the mutex that guards its request table. Under load, p99 latency rises from 5 ms to 400 ms while CPU use stays at 30 %. Explain what is happening and fix it.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Senior to staff

An in-memory cache behind one mutex serves 300,000 lookups a second on 4 cores but does not get faster on 32. How do you show that the lock is the limit, and how would you split it without new bugs?

Model answer, Pro. First step and follow-ups
Mid to senior

To signal that data is ready, thread A locks a pthread mutex at start-up and thread B unlocks it when the data is written; a waiting thread then locks it. It passes tests on Linux. What is wrong, and what should it use?

Model answer, Pro. First step and follow-ups

Key takeaways

A mutex has an owner, and the error-checking type reports a second lock or a release by another thread instead of hanging.
A futex mutex handles a free lock with atomic instructions alone and calls the kernel only to sleep or wake.
A waiter must mark the word before it sleeps, or a release can miss it.
Contention makes a lock a queue: hold it briefly and split the data before looking for a faster lock.

Terms in this lesson

futex: A 32-bit word in memory with two Linux system calls on it: FUTEX_WAIT sleeps only while the word holds an expected value, and FUTEX_WAKE wakes threads sleeping on it.
lock contention: Threads waiting for a lock that another thread holds; when it is high, the lock behaves like a queue, and waiting grows fast as requests near what the lock can serve.
lock convoy: A queue of threads behind a busy lock that outlasts its cause, started by a holder that stops running and kept going by a lock that serves waiters strictly in order.
lost wake-up: A thread asleep waiting for a wake-up that never comes, because the thread that should wake it saw nothing that said anyone was waiting.
mutex: A lock with an owner: a thread that finds it held sleeps until it is free, and only the thread that locked it may unlock it.
recursive mutex: A mutex that its owner may lock again; it keeps a count and is free only after as many unlocks as locks.

References

pthread_mutex_lock, pthread_mutex_trylock, pthread_mutex_unlock (POSIX.1-2024) (The Open Group (The Open Group Base Specifications Issue 8))
futex(2): fast user-space locking (Linux man-pages project)
futex(7): fast user-space locking, overview (Linux man-pages project)
Futexes are tricky (U. Drepper) (Ulrich Drepper)
os_sync_wait_on_address (Apple Developer Documentation)
os_unfair_lock_lock (Apple Developer Documentation)
pthread_mutexattr(3): mutex policies, first fit and fair share (Apple (libpthread open source))
Slim Reader/Writer (SRW) Locks (Microsoft Learn)
Generic mutex subsystem (The Linux Kernel Organization)
RT-mutex subsystem with PI support (The Linux Kernel Organization)
The convoy phenomenon (Blasgen, Gray, Mitoma and Price, 1979) (ACM (SIGOPS Operating Systems Review))

Report a problem with this lesson

In this module: Synchronisation: races, locks, semaphores and monitors

Race conditions and the critical-section problem Free lesson, Pro answers: 15 minutes
Peterson, Dekker and the bakery algorithm Free core, Pro depth: 6 of 20 minutes free
Hardware atomics, memory order and spinlocks Free core, Pro depth: 8 of 25 minutes free
Mutexes, futexes and lock contention Free core, Pro depth: 8 of 20 minutes free
Semaphores: counting, binary and ordering Free core, Pro depth: 7 of 20 minutes free

Your country

Mutexes, futexes and lock contention

What you will learn

Before you start

What you will learn

Before you start

A mutex has an owner, and only the owner may release it

A futex keeps the uncontended lock in user space

Lock contention turns a mutex into a queue

Practise: write a futex mutex

Write the lock and unlock of a futex mutex

Results of the sample tests

Inside the three-state mutex: a handoff step by step, and its system calls counted Pro: opens with a Pro, Premium or Ultimate pass

What a lock costs with and without contention, and what fairness costs, measured Pro: opens with a Pro, Premium or Ultimate pass

Choosing a lock's granularity, and breaking up a lock convoy Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What is a futex, and why are Linux mutexes built on one?

A service writes a log line to a network collector while holding the mutex that guards its request table. Under load, p99 latency rises from 5 ms to 400 ms while CPU use stays at 30 %. Explain what is happening and fix it.

An in-memory cache behind one mutex serves 300,000 lookups a second on 4 cores but does not get faster on 32. How do you show that the lock is the limit, and how would you split it without new bugs?

To signal that data is ready, thread A locks a pthread mutex at start-up and thread B unlocks it when the data is written; a waiting thread then locks it. It passes tests on Linux. What is wrong, and what should it use?

Key takeaways

References