Four Things Must All Be True, So Breaking Any One of Them Is Enough
Last timeOnly One at a Time
Deadlock needs four conditions at once. That is good news, because it means there are four places to attack it, and in practice one of them wins almost every time.
The four conditions
The previous lesson ended with a transfer that needs to hold two locks at once.
That is where deadlock enters, and the subject has an unusually clean structure:
four conditions must all hold at the same time, and removing any one of them
makes deadlock impossible.
The first is exclusive holding. A resource is held by one thread at a time. If
anything can be shared freely, nobody waits for it.
The second is holding while waiting. A thread keeps what it has while asking
for more. A thread that acquired everything in one go, or nothing, would never
be stuck mid-collection.
The third is that nothing is taken away by force. A thread keeps a lock until
it chooses to release it. If the system could remove a lock from a thread, it
could always break a jam.
The fourth is a cycle of waiting. Thread one waits for something thread two
holds, and following that chain brings you back to thread one.
thread one, transferring from A to B:
take lock A
take lock B
move the money
release lock B
release lock A
thread two, transferring from B to A:
take lock B
take lock A
move the money
release lock A
release lock B| step | step | thread one | thread two | state | what happened |
|---|---|---|---|---|---|
| 1 | 1 | takes lock A | runs | both threads progressing | Nothing unusual. Thread one holds one of the two locks it needs. |
| 2 | 2 | runs | takes lock B | one lock each | Still nothing wrong. Each thread holds exactly one lock and intends to take the other. |
| 3 | 3 | asks for lock B, waits | runs | thread one is blocked | Thread one is waiting for thread two to release B. That is ordinary and would resolve in a moment under any other order. |
| 4 | 4 | waits | asks for lock A, waits | nobody will ever move | Thread two now waits for thread one. Each holds what the other needs and neither will release until it gets what it is waiting for. |
The cycle
Drawing the waiting makes the fourth condition concrete and gives a diagnostic
that works on real incidents.
This is the practical skill. When a service hangs, take a thread dump, write
down each blocked thread with what it holds and what it wants, and look for a
loop. If there is one, you have both the diagnosis and the fix, because the fix
is always to break the loop at the cheapest point.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents