# Exercise 03 — The "lock" that makes the UI wait for a background import
**Failure mode:** priority inversion caused by an ownerless primitive
**Language:** C, Dispatch + Mach · **Runtime:** about 90 seconds · **Difficulty:** the one that separates people
---
## The prompt
> A thumbnail cache is protected by a `DispatchSemaphore(value: 1)`. It excludes
> correctly — exactly one thread is ever inside. Nothing crashes, nothing hangs, and the
> tests pass.
>
> A performance engineer says user-interactive work waiting on this cache "runs at the
> speed of whatever background thread happens to hold it". Prove or disprove that from the
> system, not from first principles. Then tell me what you would change and what evidence
> would show the change worked.
Answer before you run anything: **a lock and a semaphore initialised to 1 both allow
exactly one holder. Is there any difference the kernel can see?**
---
## What you are given
| Path | What it is |
| --- | --- |
| `broken/gate.c` | The starting point: mutual exclusion built from a dispatch semaphore. |
| `fixed/gate.c` | The same program with `os_unfair_lock`. |
| `solution.patch` | The diff between the two, applies with `patch -p1`. |
| `check.sh` | Proves the broken measurement and the fixed one. |
Both programs run the identical experiment: a **BACKGROUND**-QoS thread takes the gate and
holds it for 400 ms; halfway through, a **USER_INTERACTIVE** thread blocks on the same
gate. The holder samples its own scheduling priority before and during that contention.
---
## Reproduce the measurement
```bash
cd exercises/03-priority-inversion
clang -O0 -g -Wall -Wextra broken/gate.c -o /tmp/gate_broken
clang -O0 -g -Wall -Wextra fixed/gate.c -o /tmp/gate_fixed
/tmp/gate_broken 3
/tmp/gate_fixed 3
```
Expected (Apple M4 Pro, macOS 26.3):
```
EX03 build=broken primitive=dispatch_semaphore(1)
trial 1 dispatch_semaphore(1) holderPriUncontended=4 holderPriWhileUIWaits=4 donated=NO
trial 2 ... donated=NO
trial 3 ... donated=NO
EX03 build=broken primitive=dispatch_semaphore(1) trials=3 donatedTrials=0
EX03 build=fixed primitive=os_unfair_lock
trial 1 os_unfair_lock holderPriUncontended=4 holderPriWhileUIWaits=31 donated=YES
trial 2 ... donated=YES
trial 3 ... donated=YES
EX03 build=fixed primitive=os_unfair_lock trials=3 donatedTrials=3
```
**Timeout and safety.** Every wait in both programs is finite by construction — the holder
always releases after a fixed sleep — and a watchdog force-exits with 75 if the budget is
exceeded. Both builds exit 0. **Neither program hangs, and that is the point of the
exercise.**
---
## The evidence to collect
The signal is `thread_info(mach_thread_self(), THREAD_EXTENDED_INFO, …).pth_curpri` — the
thread's **current** scheduling priority, after any override the kernel has applied. It is
the same number `sample` and `spindump` print as `priority N`.
Use that rather than `pthread_get_qos_class_np()`, which reports only the QoS the thread
**requested**. A donated thread still requests BACKGROUND; what changes is what it is
actually running at.
```
4 -> 4 nothing happened. The kernel had no thread to raise.
4 -> 31 the kernel boosted the holder into the user-interactive band.
```
Notice what you can **not** measure here: an indefinite stall. The background holder keeps
running and keeps finishing either way. What you are measuring is a **scheduling** defect,
not a liveness one — which is precisely why it survives functional testing and shows up in
the field as "the UI is janky when a background import is running".
---
## Success criteria
- [ ] The broken build still reports `donatedTrials=0` — you have not edited it.
- [ ] Your fixed build reports donation in a **majority** of trials, across two runs.
- [ ] Both builds exit 0. If your repair introduced a hang, it is not a repair.
- [ ] You can say which property of the primitive makes donation possible, in one
sentence, without using the word "better".
Run `./check.sh` to have all of that checked for you.
---
## Hints
Hint 1 — ask what the kernel knows
For the kernel to speed up the thread that is holding things up, it has to know **which
thread that is**. Look at what each primitive stores. One of them keeps a thread
identifier; the other keeps an integer.
Hint 2 — why a semaphore cannot know
`dispatch_semaphore_signal` may legitimately be called by a thread that never called
`wait`. That is not a misuse — it is the whole point of a semaphore, which is a signalling
and counting primitive. But it means "the thread that holds this semaphore" is not a
well-defined idea, so there is nothing for the kernel to boost.
Hint 3 — the substitution
Replace the gate with a primitive that records an owner: `os_unfair_lock`,
`pthread_mutex`, or in Swift `Mutex` / `OSAllocatedUnfairLock` / `NSLock`. Change nothing
else — same QoS bands, same hold duration, same measurement — and re-read `pth_curpri`.
---
## Solution
Reveal the solution
### The repair
```c
typedef struct { os_unfair_lock lock; } gate_t;
static void gate_init(gate_t *g) { g->lock = (os_unfair_lock)OS_UNFAIR_LOCK_INIT; }
static void gate_acquire(gate_t *g) { os_unfair_lock_lock(&g->lock); }
static void gate_release(gate_t *g) { os_unfair_lock_unlock(&g->lock); }
```
Nothing else changes. The measured priority of the background holder goes from **4 → 4**
to **4 → 31** while a USER_INTERACTIVE thread waits.
### Why
`os_unfair_lock` stores the **owning thread's port** in the lock word. When a
higher-priority thread blocks on it, the kernel can see exactly which thread is in the
way and raises that thread's priority until it releases — *priority donation*. The thread
that the high-priority work is waiting for now runs at high-priority speed, so the wait is
bounded by the critical section rather than by the holder's QoS band.
A semaphore is a **counter**. `signal` may come from any thread. "The owner" is not a
well-defined concept, so there is no thread to raise and the high-priority waiter is stuck
behind background-rate work.
`pthread_mutex`, Swift's `Mutex`, `OSAllocatedUnfairLock`, `NSLock` and `NSRecursiveLock`
all carry ownership and all donate. `DispatchSemaphore` and `DispatchGroup` do not.
### The rule, stated properly
**Use a semaphore to count permits or to signal between threads. Use a lock for mutual
exclusion.** Not because locks are faster — they may not be — but because only a lock can
tell the kernel who is holding things up.
### What this exercise does NOT claim
It does **not** reproduce the textbook unbounded priority inversion, where a high-priority
thread waits forever because a medium-priority thread keeps preempting the low-priority
holder. On modern Darwin that outcome does not reproduce with a donating lock; an attempt
in the source material for this chapter measured only about a 1.5× penalty. Presenting the
textbook stall as something you can demonstrate on a Mac today would be dishonest.
What is reproducible — and what an interviewer can check — is the **donation signal
itself**: one primitive causes a measurable kernel override, the other does not.
Donation is also kernel **policy**, not a documented API guarantee. It is observed here on
one OS build. Treat it as a strong reason to prefer an owning lock, not as something to
assert in a test that must pass on every future OS.
### The related trap worth mentioning
Apple's **Thread Performance Checker** reports priority inversions during a Run action in
Xcode. It has no supported command-line invocation, which is why this exercise measures the
kernel behaviour directly instead. If an interviewer asks which tool finds this, name
Thread Performance Checker — and be honest that it is an IDE-only tool.
---
## Limitations
- **One machine, one OS build.** The specific priority numbers (4 and 31) are this
machine's; the *direction* of the change is what matters. Reproduce rather than quote.
- `pth_curpri` is a **Mach** interface. It is the same number Apple's own sampling tools
print, but it is a scheduling observation, not a contract.
- Priority donation is not documented as a guaranteed behaviour of `os_unfair_lock`. The
bundled check therefore requires a majority of trials to show it, not all of them.
- The measurement deliberately uses a long, fixed hold time so the contention window is
reliable. A critical section of realistic length may be too short for the override to be
observable, which does not mean it did not happen.