Locks and deadlock — every question, written out
Where a critical section must start and end, what a lock does to the set of possible orderings, and the cycle that forms when two of them meet.
A lock is added around a racy increment. What happened to the eighteen losing interleavings?
Invariant identification
They no longer exist — a thread waiting on a held lock cannot be scheduled.
The scheduler can only pick a thread that is able to take a step, and a thread blocked on a held mutex is not. The orderings that required it to run are unreachable rather than unlikely.
See every interleaving — Twenty interleavings become two.
A mutex is taken after the read and released after the write, and the counter is still wrong. Why?
Code diagnosis
The critical section must span the whole read-modify-write, and it starts too late.
Both threads can read before either acquires, so both enter with the same stale value and the lock only serialises the writes. The section has to cover every operation the invariant depends on.
See every interleaving — A correctly used lock protecting nothing.
What does a mutex cost when uncontended, and when contended?
Complexity derivation
Tens of nanoseconds uncontended; microseconds when a thread actually blocks.
An uncontended acquisition is a compare-and-swap on the lock word. Blocking means descheduling the thread and waking it later, which is dominated by the context switch — roughly a hundredfold difference.
Which of the four Coffman conditions do you usually break in practice?
Invariant identification
Circular wait, by imposing a total order on lock acquisition.
The other three are usually properties of the problem rather than choices. A total order over locks makes a cycle impossible to form, because forming one requires somebody to acquire backwards.
See every interleaving — Zero deadlocking interleavings, not merely fewer.
Three threads take locks A→B, B→C and C→A. Every pair is consistent. Is it safe?
Edge case reasoning
No — the three form a cycle even though no two of them disagree.
A cycle needs three edges here rather than two, and each thread individually looks consistent with each other. This is why a lock ordering is only a policy when it covers every lock in the system.
See every interleaving — Every pair agrees; the ring still closes.
Two threads take two locks in opposite orders. Why does this reach production?
Code diagnosis
Most interleavings complete normally, so testing sees nothing wrong.
Two of six interleavings deadlock and four are fine. A bug that failed reliably would be caught in development; this one passes and then waits.
See every interleaving — 2 of 6 deadlock; 4 complete perfectly.
What is a wait-for graph, and what does a cycle in it mean?
Explain it plainly
Threads as nodes, "waiting for a resource held by" as edges. A cycle is a deadlock, exactly — no extra condition needed. It is useful because it discards everything about what the threads were doing and keeps only the blocking relationship.
Nodes are threads and an edge from A to B means A is waiting for a lock B holds. A cycle means none of the threads on it can ever proceed, because each is waiting for one that is itself waiting.
See every interleaving — Drive it to the stuck state and the cycle is drawn.
Can a single thread deadlock with a single lock?
Edge case reasoning
Yes, on a non-reentrant mutex, by acquiring a lock it already holds.
A public method takes the lock and calls another public method that takes it too. On a non-reentrant mutex the thread blocks waiting for itself, and no scheduling decision can resolve it.
See every interleaving — One schedule, and it is a deadlock.
Why would a language deliberately make its mutex non-reentrant?
Trade-off & selection
Recursive acquisition lets code re-enter a critical section whose invariant is currently broken.
The lock is held because the data is mid-update. Recursive acquisition means a function can observe that half-finished state while holding the lock and believing it is safe — a much harder bug than the hang would have been.
Is a released mutex handed to the longest-waiting thread?
Trade-off & selection
Usually not — most mutexes let a running thread barge ahead of queued waiters.
Handing the lock to a queued thread means waking it — a context switch and a cold cache — while letting the running thread take it costs nothing. Fair locks exist and trade real throughput for the guarantee.
See every interleaving — One of four interleavings starves the waiter entirely.
One lock guards a 100ns critical section. What is the throughput ceiling with sixteen threads?
Complexity derivation
Ten million operations a second — one critical section at a time, whatever the thread count.
The lock turns its critical section into a serial region, so the ceiling is one divided by its duration. This is Amdahl’s law with a mutex in place of the sequential fraction.
See every interleaving — The line goes flat and stays flat.
The lock is a bottleneck. What should you try before striping it into sixteen locks?
Trade-off & selection
Shorten the critical section — halving it doubles the ceiling and costs nothing.
Moving computation, allocation and I/O outside the lock is free, simple, and doubles the ceiling for every halving. Striping adds memory, a lock-ordering hazard across stripes, and false sharing if the locks sit together.
Why is "never call unknown code while holding a lock" a real rule?
Trade-off & selection
The callee may acquire a lock you have never heard of, creating an ordering you cannot audit.
Lock ordering can only be maintained over locks you know about. A callback, virtual method or event handler can acquire anything, so holding a lock across one makes the ordering unverifiable.
Does `tryLock` with a timeout fix a deadlock?
Trade-off & selection
No — it converts a hang into a failure and leaves the cycle in place.
Turning an indefinite hang into an alert is genuinely valuable, and the acquisition order is unchanged. Worse, symmetric retry after a timeout is how livelock appears, so the retry needs jitter.
See every interleaving — 927 of 3,000 runs make no progress with symmetric backoff.
How do deadlock and livelock differ in a thread dump?
Comparison
Deadlock shows threads parked with CPU idle; livelock shows threads running with CPU pinned.
In deadlock nobody can run; in livelock everybody runs and nothing progresses. High CPU with flat throughput and threads in a running state is the livelock signature.
What does a lock actually protect?
Explain it plainly
It protects data, by convention. The lock knows nothing about which fields it guards — the invariant is that everybody who touches those fields takes that lock, and it is enforced by discipline rather than by the primitive. Rust is the exception: the mutex owns the data, so the compiler enforces it.
Data, not code. The guarantee holds only if every thread that touches the data takes the same lock, so one unlocked read path anywhere removes the protection entirely.