What is deadlock

Hold, Then Wait

In the race-condition lesson we picked up a good habit: to change something, first take hold of it, and make everyone else wait until you are done, like queuing for a single-stall restroom. That made the accident of two people overlapping and ruining the result go away.
Now suppose a job needs two resources. Call them tool 1 and tool 2; the job can only be finished with both. A takes tool 1 first and waits for tool 2. B takes tool 2 first and waits for tool 1. Each simply took one tool by the rule, yet neither ever gets the other.
Keep what you hold, wait for what you lack. This hold-and-wait is where all the trouble starts.

Press the two buttons so that A and B each take one tool. A holds tool 1 and waits for tool 2; B holds tool 2 and waits for tool 1. Neither lets go and each waits only for what it lacks, so neither can move on (red).

Strange, isn't it? Neither did anything wrong. Each took one tool in turn, exactly the way the race-condition lesson called safe. And still both are stuck.
The problem is not the holding itself but the shape: holding while waiting for each other. A familiar scene makes that shape easier to see.

Two People Face to Face on a Narrow Bridge

Picture a bridge so narrow that only one person can cross at a time. One person steps on at one end and another at the other end at the same moment. They walk toward the middle and meet head-on.
To go on, each needs the other to make way. But neither gives up the spot they are standing on: I was here first, I am in more of a hurry. Since nobody backs up, both stand frozen in the middle for good.
The spots on the bridge are tool 1 and tool 2 from before, and the two people are A and B. Each holds their own spot while waiting for the other's, exactly the shape we just saw.

Use the two buttons to move A and B toward the middle one square at a time. When they meet in the center, neither gives way, so both stop and can go no further (red).

On the bridge the two stopped as soon as they faced each other. But the jam need not involve only two. If three, four, or more people stand not in a line but in a circle, each waiting for the next, the same freeze happens on a larger scale.
This time we seat people around a table and make the loop of waiting close ourselves.

When the Loop Closes, Everyone Stops

Five people sit around a table, with one chopstick between each pair of neighbors. To eat, you need both the chopstick on your left and the one on your right, and everyone has agreed to pick up the left one first and then wait for the right.
If only one or two do this, nothing goes wrong: someone gets both, eats, and puts them down again. But if everyone picks up the left one at the same time, everyone's right chopstick is in a neighbor's hand. Everyone waits for a neighbor, and the waiting runs all the way around the table and comes back to where it started.
Once the arrows of waiting form a closed loop like this, no one on the loop can ever move. The two people on the narrow bridge have grown into a whole ring around the table.

Each press of the button makes the next person pick up their left chopstick. The moment the fifth person picks one up, the loop closes: everyone's right chopstick is in a neighbor's hand, and everything stops (red).

With that last step closing the loop, a table that was working fine froze solid. The frightening part is that no one did anything especially wrong. Everyone picked up the left chopstick first, the same sensible way, and the whole table stopped.
So how do we thaw it? Fortunately the answer is surprisingly simple, and there are two ways.

The Way Out: Yield, or Agree on an Order

The first way is to yield. Someone on the loop puts down what they were holding for a moment. The neighbor who was waiting for it now has both chopsticks, eats, and puts them down when finished. One spot frees up, then the next, and the jam clears like falling dominoes, because a loop with even one gap is no longer a closed loop.
The second way is smarter: stop the loop from ever closing. Give everyone the same rule, "always take the lower-numbered one first." Then anyone who cannot get tool 1 does not take tool 2 either, but waits. Since everyone takes things in the same order, no two people end up crossed and facing each other, and a loop can never form.

First close the loop so everyone stops, then have one person yield. When that person puts down what they hold, the loop breaks, and starting with the neighbor everyone is freed in turn and moves again (green).

Yielding undoes a loop that has already stopped; agreeing on an order keeps the stop from ever happening. One is first aid after the accident, the other is prevention before it.
Both come down to the same thing: never letting the round loop of waiting close. Break it at even one point, and the freeze turns back into flow.

On One Page

Four things are worth remembering.
First, when each side holds one thing and waits for the other's, hold-and-wait begins. Second, like the two people on the narrow bridge, if they face each other and neither yields, both stop.
Third, when that standoff runs all the way around and the loop closes, everyone on the loop stops. That is deadlock. Fourth, if someone puts down what they hold and yields, or if everyone agrees to take things in the same order, the loop breaks or never forms, and things can flow again.

Press the four steps in order and the whole story of a deadlock fits on one panel: hold-and-wait, the face-off on the bridge, the closed loop, and the two ways out, yielding and ordering.

In the race-condition lesson we learned that taking turns one at a time is safe; this time we saw that the very same taking of turns can bring everything to a halt. The same tool depends on how you use it.
Safe queuing and a deadlock that never ends are separated by a hair. Whether everyone takes things in the same order, and whether someone knows how to yield, is what decides which side of that hair you land on.
One lesson remains in the operating-systems area: how a computer wakes itself up, from the moment you press the power button until the screen comes on.