# Exercise 01 — The transfer that freezes
**Failure mode:** ABBA lock-order inversion (circular wait)
**Language:** C, pthreads · **Runtime:** about 20 seconds · **Difficulty:** the classic
---
## The prompt
> A money-transfer feature locks the source account, then the destination account, then
> moves the balance. It passed review and it passes its unit tests. In production it
> freezes a few times a week, always under load, and the process has to be killed.
>
> You have the source and a live wedged process. Reproduce it deterministically, prove
> from the process what it is waiting on, and fix it. Then tell me what your fix costs.
Answer out loud before you run anything: **what has to be true of two threads for a
deadlock to be possible at all?** If you cannot name the four conditions, you will fix
the symptom rather than the cause.
---
## What you are given
| Path | What it is |
| --- | --- |
| `broken/transfer.c` | The starting point. Deadlocks on every run. Do not edit it — copy it. |
| `fixed/transfer.c` | One correct repair, for comparison after you have written your own. |
| `solution.patch` | The diff between the two, applies with `patch -p1`. |
| `check.sh` | Proves the broken symptom and the fixed result. |
`transfer.c` contains a rendezvous gate. It is **test scaffolding, not the bug**: it
removes the timing luck that normally hides an ordering defect, so the failure happens on
the first run instead of once a week. The gate itself can never stall — it gives up after
one second.
---
## Reproduce the failure
```bash
cd exercises/01-abba-deadlock
clang -O0 -g -Wall -Wextra -pthread broken/transfer.c -o /tmp/transfer_broken
/tmp/transfer_broken ; echo "exit status: $?"
```
Expected output:
```
EX01 build=broken (watchdog budget 5s)
thread-1 checking->savings: holds account 1, waiting at the gate
thread-2 savings->checking: holds account 2, waiting at the gate
thread-2 savings->checking: gate open, now reaching for account 1
thread-1 checking->savings: gate open, now reaching for account 2
main: joining both threads
WATCHDOG: no progress within budget - forcing _exit(75).
exit status: 75
```
**Timeout and safety.** The program carries a 5-second in-process watchdog that calls
`_exit(75)`. It reports through `write(2)` and exits through `_exit(2)` rather than
`printf`/`exit`, because a deadlocked process may hold a lock that stdio or an `atexit`
handler needs. `check.sh` adds a second, external hard timeout that `SIGKILL`s at 20
seconds. **Exit status 75 is the correct outcome here.** A run that reported
`result=COMPLETED` would be the failure.
---
## The evidence to collect
Do not diagnose this from the source. Get it from the running process, the way you would
have to in production:
```bash
/tmp/transfer_broken /tmp/marker & PID=$!
sleep 1
sample "$PID" 1 10 -file /tmp/transfer.sample
kill -9 "$PID"
grep -c __psynch_mutexwait /tmp/transfer.sample
```
Three things in that report together identify the failure, and no one of them is enough:
1. **Two or more threads parked in `__psynch_mutexwait`** — they are blocked on a
userspace mutex that has gone into the kernel.
2. **One frame holding every sample** — the thread never moved for the whole sampling
window, so this is a stall rather than slow progress.
3. **The wait is mutual** — each thread's stack shows it inside a function that already
holds the other's lock.
The third point is what separates a deadlock from ordinary contention. A busy lock also
shows `__psynch_mutexwait`; what it does not show is a cycle.
---
## Success criteria
Your repair passes when all of these hold:
- [ ] The broken build still deadlocks — you have not edited it.
- [ ] Your fixed build exits **0**, never 75.
- [ ] It prints `conserved=true`: opening and closing totals match.
- [ ] It performs all `transfers=100002` transfers.
- [ ] It passes twice in a row. A deadlock fix that works once has not been tested.
- [ ] You can state, in one sentence, which of the four Coffman conditions you removed.
Run `./check.sh` to have all of that checked for you.
---
## Hints
Hint 1 — where to look
Print the account id each thread locks first, and the one it locks second. Run it a few
times. The two threads disagree about the order, and that disagreement is the entire bug.
Nothing about the *amount* of money, the *direction* of the transfer, or the *duration*
of the critical section matters.
Hint 2 — the four conditions
A deadlock needs all four of: mutual exclusion, hold-and-wait, no preemption, and
circular wait. Three of those are properties of using locks at all. Only one is a
property of *your* code, and it is the one you can delete.
Hint 3 — the shape of the repair
The direction money moves and the order locks are acquired do not have to be the same
thing. Sort the two accounts by something stable that every call site can compute
independently — an id, an address, a name — and always take the lower one first.
There is a second, weaker repair: keep the inconsistent order but never block while
holding. Take the first lock, `trylock` the second, and if that fails drop *everything*
and retry after a backoff. Know why it is weaker before you reach for it.
---
## Solution
Reveal the solution
### The repair
Impose a **total order** over the locks and obey it at every acquisition site:
```c
static void transfer(account_t *from, account_t *to, long amount, const char *who) {
account_t *first = from->id < to->id ? from : to;
account_t *second = from->id < to->id ? to : from;
pthread_mutex_lock(&first->m);
pthread_mutex_lock(&second->m);
from->balance -= amount;
to->balance += amount;
pthread_mutex_unlock(&second->m);
pthread_mutex_unlock(&first->m);
}
```
That is the whole patch. See `solution.patch`, or `fixed/transfer.c`.
### Why it works
A deadlock requires a **cycle** in the wait-for graph. If every thread acquires locks in
increasing id order, a thread can only ever wait on a lock with a higher id than every
lock it holds. Following waits therefore strictly increases the id, and a strictly
increasing sequence cannot return to where it started. **Circular wait — Coffman
condition 4 — is not merely unlikely; it is impossible.**
The ordering key can be anything total and stable. Address order works and needs no
field, but it is not stable across runs, so it is harder to assert in a test. An id is
easier to state in a comment and easier to check in review.
### What it costs
Almost nothing at run time — two comparisons. The real cost is a **discipline you now
have to maintain**: every future call site must agree, including one written by somebody
who has never read this file. Write the order down next to the lock declarations, and
treat "acquires two locks" as a review trigger.
### The other repair, and why it is weaker
```c
pthread_mutex_lock(first);
if (pthread_mutex_trylock(second) == 0) {
/* got both */
} else {
pthread_mutex_unlock(first); /* drop EVERYTHING, then retry */
usleep(backoff);
}
```
This removes **hold-and-wait** (condition 3) rather than circular wait. It works, and it
is sometimes the only option when you do not control every acquisition site — for example
when one of the locks is inside a framework. But:
- its worst case is **unbounded**: two threads can livelock, each repeatedly grabbing and
dropping, making no progress while burning CPU;
- it needs a backoff, and the backoff needs jitter, and now you have tuning parameters;
- it is much harder to reason about in review than "we always take the lower id first".
Prefer the total order when you control the code. Reach for trylock when you do not.
### What the interviewer is listening for
- That you got the evidence from the **process**, not from reading the source.
- That you named **circular wait** specifically, rather than saying "they deadlock".
- That you volunteered the **cost** of your fix without being asked.
- That you know the rendezvous gate made the bug reproducible and was not the bug.
---
## Limitations
- `sample` reports **user-space stacks of a live process**. It shows that a thread is
parked in `__psynch_mutexwait`; it does not tell you *which* mutex, and it cannot draw
the wait-for graph for you. You still have to connect two stacks by reading the code.
- The rendezvous gate makes this failure reproducible on demand. A real ABBA inversion is
probabilistic, which is why it reaches production: the window is real but narrow, and it
widens under load, on slower hardware, and under a debugger.
- Exit status 75 is this fixture's convention, not a system one. A real deadlocked process
does not exit at all; that is what makes it a hang rather than a crash.