# Threads, concurrency and locks — fixing exercises Six deliberately broken programs, one per failure mode. For each one you get the broken starting point, an interview-style prompt, the exact command that reproduces the failure, the evidence to collect, bounded success criteria, progressive hints, a revealable solution, a separate fixed source file, a `.patch` from one to the other, and a check that proves both halves. These are companion material to the **Threads, concurrency and locks** chapter of the *macOS operating-system concepts* reference. They stand alone: nothing here reads that page, and nothing here needs a network. ```bash ./run-all.sh # validate the entire bundle — about 2 minutes ``` --- ## Safety — read this before running anything **Several of these programs deadlock, stall or oversubscribe the machine on purpose.** They cannot wedge it, because every one of them carries two independent bounds: 1. an **in-process watchdog thread** that calls `_exit(75)` after a fixed budget, reporting through `write(2)` and exiting through `_exit(2)` rather than `printf`/`exit` — a deadlocked process may be holding a lock that stdio or an `atexit` handler needs; 2. an **external hard timeout** in every `check.sh`, which `SIGKILL`s the process at several times that budget. **Exit status 75 means the watchdog fired.** For the deadlock exercise that is the expected, correct outcome — a run that *completed* would be the failure. Every deliberately broken file carries a prominent `UNSAFE CODE WARNING` header. None of it should be copied into production, and several of the broken forms compile without a single warning under Swift 6 strict concurrency, which is exactly why they are worth studying. --- ## The six exercises | | Directory | Failure mode | Language | Broken symptom | The repair | | --- | --- | --- | --- | --- | --- | | **01** | `exercises/01-abba-deadlock` | ABBA lock-order inversion | C | Hangs; watchdog exits 75; two threads in `__psynch_mutexwait` | A total order over the locks | | **02** | `exercises/02-data-race` | Data race | Swift | Lost updates; `WARNING: ThreadSanitizer` | One critical section around the whole read-modify-write | | **03** | `exercises/03-priority-inversion` | Priority inversion | C | Holder's priority stays at 4 while a UI thread waits | A primitive that records an owner | | **04** | `exercises/04-lost-wakeup` | Lost wakeup / semaphore misuse | Swift | 1.5 s stall on data already published; wakeups treated as promises | A predicate loop around the wait | | **05** | `exercises/05-lock-convoy` | Lock convoy | C | 3.8× *slower* with more threads | Narrow the critical section, batch, shard | | **06** | `exercises/06-thread-explosion` | Thread explosion | Swift | 73 threads on 14 cores | Admission before submission | Each directory contains: ``` README.md prompt, commands, expected evidence, criteria, hints, solution broken/ the starting point — immutable; copy it, do not edit it fixed/ one correct repair, same filename solution.patch broken -> fixed, applies with `patch -p1` check.sh machine-checkable validation of BOTH the symptom and the fix ``` --- ## How to work through one ```bash cd exercises/01-abba-deadlock cat README.md # read the prompt, and answer it before running anything cp broken/transfer.c /tmp/mine.c # never edit broken/ clang -O0 -g -Wall -Wextra -pthread /tmp/mine.c -o /tmp/mine /tmp/mine ; echo "exit: $?" # reproduce the failure first # ... diagnose from the running process, then repair /tmp/mine.c ... ./check.sh # validates the shipped pair, not your copy ``` `check.sh` validates the **shipped** broken/fixed pair. To check your own repair, apply the same criteria from the README's *Success criteria* section by hand, or drop your file over a copy of `fixed/` and re-run. To see the intended repair as a diff instead of reading the whole file: ```bash cat solution.patch # or apply it to your own copy of the broken file: cp broken/transfer.c /tmp/w/transfer.c && (cd /tmp/w && patch -p1 < .../solution.patch) ``` The hints and solutions are in `
` blocks. In a Markdown renderer — GitHub, most editors, the study-site page — they are collapsed until you click. **In a plain-text viewer they are not**, so if you are reading these in a terminal, stop at the `` line. --- ## Requirements - macOS with the Xcode command line tools (`xcode-select --install`) - `clang` and `swiftc` — Swift 6 language mode, and `Mutex` from `Synchronization` (macOS 15+) in exercises 02, 04 and 06 - `patch`, and `sample` for exercise 01's backtrace evidence (optional — that step reports `skip` rather than failing if `sample` is unavailable) No package manager, no network, no Xcode project, no GUI. Every source file compiles **alone in an empty directory**, and `check.sh` enforces that by copying each file into a fresh temporary directory before building it. --- ## What the bundle validator proves `./run-all.sh` runs every exercise's `check.sh` and reports one aggregate result. For each exercise it asserts: 1. the broken source and the fixed source each compile **from a clean copy** with the expected number of warnings (zero, in every case here); 2. `solution.patch` applies cleanly to a copy of the broken file and reproduces the fixed file **byte for byte**; 3. the broken build produces its **documented symptom** — the right exit status, the right evidence in its output, the right measurement; 4. the fixed build produces its **documented success**; 5. every timing-sensitive measurement is taken at least **twice**. ``` ./run-all.sh # everything ./run-all.sh --quick # skip the Thread Sanitizer builds (exercise 02) ./run-all.sh 03 05 # only the named exercises ``` Exit status 0 means every broken build failed as documented and every fixed build succeeded. --- ## How the measurements are bounded Where a measurement is deterministic it is asserted exactly. Where it is timing-sensitive it is asserted as a **ratio with a generous bound**, so the exercise still validates on hardware quite different from the machine it was written on: | Exercise | Asserted exactly | Asserted as a loose bound | | --- | --- | --- | | 01 | exit 75; `conserved=true`; 100002 transfers | — | | 02 | Thread Sanitizer positive / silent; fixed total exact | lost updates: only "≤ expected" and "at least one run lost something" | | 03 | semaphore donates in **0** trials (structural) | lock donates in a **majority** of trials (kernel policy) | | 04 | `wouldHaveCrashed=0`; all items consumed; part A under 250 ms | broken bad-wakeup count: "≥ 1", never a figure | | 05 | acquisition counts; checksums equal | broken worst ≥ 1.8×; fixed ≤ 0.60×; 16-thread ratio ≥ 2× | | 06 | `permitHolders=4` in both builds | broken peak ≥ 2× cores; fixed peak ≤ 24; ratio ≥ 3× | The reference machine was an **Apple M4 Pro (10 performance + 4 efficiency cores), macOS 26.3 (25D125), Swift 6.2.4, Apple clang 17.0.0**. Absolute figures on other machines will differ, sometimes by a lot. **Reproduce them; do not quote them.** --- ## What these exercises do not cover - **Instruments GUI workflows.** Every step here is command line. Where an Instruments view would show the same thing, the README says which one, but there is no `.trace` to open and no screenshot to compare against. - **Thread Performance Checker**, which finds priority inversions and is an Xcode Run-action tool with no supported command-line invocation. Exercise 03 measures the kernel behaviour directly instead. - **The textbook unbounded priority-inversion stall.** It does not reproduce on modern Darwin with a donating lock, and exercise 03 says so rather than manufacturing it. - **Thread Sanitizer's limits.** It is a runtime detector: it finds races on paths that actually executed, costs roughly 5–10× memory and 2–20× time, and cannot see race conditions at all. Exercise 02 demonstrates a correctly-locked program that is still wrong with the sanitizer completely silent. - **Memory-ordering formalism.** Acquire/release is used as a working model, not treated formally. --- ## Layout ``` README.md this file run-all.sh the one command that validates everything lib/common.sh shared bounded-run, clean-build and assertion helpers tools/pack.sh rebuilds the distributable archive deterministically exercises/NN-name/ one exercise per directory, described above ```