When Nobody Yields: Deadlock

Hold, and Then Wait

Last lesson we learned one good habit. To fix something you first take it, and the others wait until you are done. Like lining up for a single restroom. That way the accident of two clashing and ruining it disappeared.
Now suppose the job grows to two parts. There are two resources. Call them tool 1 and tool 2. To finish the job you need both tools. A takes tool 1 first and waits for tool 2. B takes tool 2 first and waits for tool 1. Each only took one thing by the rule, yet neither can get hold of the other one.
Hold what you have, wait for what you lack. This holding and waiting is where the whole thing begins.

Let A and B each take one. A holds tool 1 and waits for tool 2 (red), while B holds tool 2 and waits for tool 1. Neither releases what they hold and both wait for what they lack, so neither can advance.

Is it not strange? Neither did anything wrong. Each just took one thing in turn. Exactly the method we learned was safe last lesson. And yet both froze.
The problem is not the holding itself, but the shape of holding while waiting for each other. To see this shape more clearly it helps to picture one scene. Next, let us switch to a familiar one.

Two Facing Off on a Narrow Bridge

There is a narrow bridge that only one person can cross. At one end a person steps onto it, and at the other end another steps on at the same time. They walk toward the middle and meet head-on.
To go forward each needs the other to step aside. But neither yields the square they stand on. I came first, I am in more of a hurry. Since nobody backs up, both stay frozen in the middle forever.
Here each square of the bridge is tool 1 and tool 2 from before. The people are A and B. Each holding their own spot while waiting for the other spot, exactly the shape we saw earlier.

Step the two people forward one square at a time toward the middle. When they meet at the center of the bridge, neither yields, so both stop and cannot pass (red).

On the bridge two faced each other. So they stopped. But the stuck ones need not be just two. If three, four, or more line up not in a row but in a circle, each waiting for the next, the same freeze happens on a bigger scale.
Next, let us seat people in a circle. Let us make the moment the loop closes with our own hands.

When the Loop Closes, Everyone Stops

Several people sit in a circle at a table. Between each pair of people lies one chopstick. To eat you need both chopsticks, but everyone alike decides to grab the left one first and wait for the right.
If only one or two do this, it is fine. Someone gets both, eats, and puts them down when done. But if everyone grabs the left at the same time, everyone’s right chopstick is in their neighbor’s hand. Everyone waits for the neighbor. The waiting goes all the way around and comes back to oneself.
When the arrows of waiting form a round loop like this, nobody on that loop can ever move. The two on the narrow bridge have grown to many, ringed around a table.

Have the seated people grab their left chopstick one by one. The instant the last one grabs and the loop closes, everyone’s right is in a neighbor’s hand, so all freeze (red).

At that last step where the loop closed, a table that had been turning fine froze solid all at once. The scary part is that no single person did anything specially wrong. Everyone simply, reasonably, grabbed the left one first, and the whole thing stopped.
So how do we thaw this frozen table? Happily the way is surprisingly simple. Next, let us see two paths to break the loop.

The Fix: Yield, or Fix an Order

The first path is to yield. One person on the loop briefly puts down what they were holding. Then the neighbor who was waiting for them gathers both pieces, eats, and puts them down when done. One spot frees up, so the next frees up, and the jam clears in turn like dominoes. As soon as a single break appears in the loop, it is no longer a round loop.
The second path is cleverer. Stop the loop from ever closing in the first place. Give everyone the same rule: whoever you are, always take the lower-numbered one first. Then anyone who cannot get tool 1 never takes tool 2 either. Since everyone takes in the same order, two people crossing and facing off never happens. A loop simply cannot form.

First close the loop so everyone freezes, then make one person yield. When they put down what they hold, the loop breaks, and starting from the neighbor everyone is freed in turn and moves again (green).

Yielding is the path to undo a loop that has already stopped, and fixing an order is the path so the stop never arises at all. One is first aid after the accident, the other is prevention before it.
Both come down to the same thing: keeping the round loop of waiting from closing. If even one spot is broken, the freeze turns back into flow.

Put It on One Page

Just remember four things.
First, when each holds one thing and waits for the other, holding and waiting begins. Second, like the two on the narrow bridge, if they face off and do not yield, both stop.
Third, when that stop goes 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 is set to take in the same order, the loop breaks or never forms, and things can flow again.

Tap the steps in order to follow one full loop. From hold-and-wait to facing off, from the closed loop to breaking it by yielding or ordering. The life of a deadlock on one panel.

Last lesson we learned that going one at a time is safe, and today we saw that the very same taking in turn can instead bring everyone to a stop. The same tool depends on how you use it. Safe lining up and a forever-frozen deadlock are a hair apart. Whether everyone takes in the same order, and whether someone knows how to yield, is what decides that hair.