Knives and boards: deadlock

Night five, eleven o'clock. The kitchen is strangely quiet. Minho is gripping the knife and staring at the cutting board. Sua is hugging the cutting board and staring at the knife. Both keep saying the same thing: "I'll hand it over once I'm done."

Mr. Tak stops halfway through a scallion and mutters, "If you both just stand there, nobody finishes."

Chef Yoon Seoyeon stops the timer around her neck. "Both of you, put them down. This didn't happen because someone was slow. It happened because there was no rule."

5-1. Two cooks waiting on each other (7 min)

Like last night's burner rule, the knife and the cutting board are locks: only one person can use each at a time. Minho grabs knife → board. Sua grabs board → knife.

import threading
import time

knife = threading.Lock()
board = threading.Lock()

def minho():
    with knife:              # pick up the knife
        time.sleep(0.1)
        with board:          # wait for the board
            print("minho done")

def sua():
    with board:              # pick up the board
        time.sleep(0.1)
        with knife:          # wait for the knife
            print("sua done")

a = threading.Thread(target=minho, daemon=True)
b = threading.Thread(target=sua, daemon=True)
a.start(); b.start()
a.join(timeout=1); b.join(timeout=1)
print("alive:", a.is_alive(), b.is_alive())
# alive: True True

• After a full second, both threads are still alive. They aren't working; each is frozen, waiting for the other to let go. This is a deadlock.
• join(timeout=1) waits at most one second and then returns. Because the threads are daemon=True, the program can still exit. Whenever you experiment with deadlocks, always leave yourself a way out like this.
• time.sleep(0.1) is there to make both cooks grab their first tool at almost the same moment. In real programs that gap opens up only rarely, which turns deadlock into an even nastier bug: one that happens "only sometimes."

To notice from inside the program that you're stuck, use acquire(timeout=...). It returns True if it got the lock and False if time ran out. You can't give with lock: a time limit, so here you call acquire and release yourself.

knife = threading.Lock()   # a fresh knife and a fresh board
board = threading.Lock()

def cook(name, first, second, patience):
    with first:
        time.sleep(0.1)
        if second.acquire(timeout=patience):   # wait at most `patience` seconds
            second.release()
            print(name, "done")
        else:
            print(name, f"gave up after {patience}s")

a = threading.Thread(target=cook, args=("minho", knife, board, 1.0))
b = threading.Thread(target=cook, args=("sua", board, knife, 0.5))
a.start(); b.start()
a.join(); b.join()
# sua gave up after 0.5s
# minho done

Sua gives up after 0.5 seconds and puts the board down, so Minho, still waiting, grabs it and finishes his dish. One person backing off is enough to break the deadlock. The four conditions in the next section explain why.

5-2. The four conditions for deadlock (8 min)

A deadlock happens only when all four of these conditions hold at the same time. Turn that around: break any one of them and deadlock can't happen.

• Mutual exclusion is the whole reason a lock exists, so you usually leave it alone. If there were plenty of knives, you wouldn't need a lock in the first place.
• The fix used most in practice is breaking circular wait. If everyone grabs in the same order, no loop can form.
• Next comes breaking hold-and-wait and no-preemption together: if you can't get the second lock within a set time, you put down what you're holding.

5-3. Fix 1: everyone grabs in the same order (8 min)

The chef writes a rule on the chalkboard: "Every tool gets a number. Knife is 1, board is 2. Always grab the lowest number first."

If Minho and Sua both start with the knife, only the person holding the knife ever waits for the board. Whoever didn't get the knife waits empty-handed, so no loop can form. Don't leave the rule to people's memory; put it in a single function.

from contextlib import contextmanager

KNIFE = (1, threading.Lock())   # (number, lock)
BOARD = (2, threading.Lock())

@contextmanager
def hold(*tools):
    ordered = sorted(tools, key=lambda t: t[0])   # lowest number first
    for _, lock in ordered:
        lock.acquire()
    try:
        yield
    finally:
        for _, lock in reversed(ordered):        # release in reverse
            lock.release()

done = []

def minho():
    for _ in range(100):
        with hold(KNIFE, BOARD):
            time.sleep(0)
    done.append("minho")

def sua():
    for _ in range(100):
        with hold(BOARD, KNIFE):     # written in a different order, grabbed in the same order
            time.sleep(0)
    done.append("sua")

ts = [threading.Thread(target=f, daemon=True) for f in (minho, sua)]
for t in ts: t.start()
for t in ts: t.join(timeout=2)
print(sorted(done), [t.is_alive() for t in ts])
# ['minho', 'sua'] [False, False]

• Even though Sua writes hold(BOARD, KNIFE), hold sorts by number, so she really grabs knife → board.
• The two of them take turns 100 times each and never get stuck, even with time.sleep(0) giving the other thread a chance to cut in.
• A person can assign the numbers, or, if the locks only live inside one program, you can use any unique value such as id(lock). What matters is that all the code uses the same ordering.
• The release order has nothing to do with deadlock, but releasing in the reverse of the grab order is a habit that makes code easier to read.

As soon as some piece of code needs more than one lock, write this rule down in a comment at the top of the file or in the docs. The moment a newcomer who doesn't know the order grabs them backwards, the deadlock is back.

5-4. Fix 2: if you can't get it, put it down (7 min)

Sometimes a fixed order is hard to arrange, for example when you can't know in advance which locks you'll need. Then you use a different rule: "If you still can't get it after waiting a while, put down what you're holding too, and start over."

import random

tries = {}

def polite_cook(name, first, second):
    tries[name] = 0
    while True:
        tries[name] += 1
        with first:
            time.sleep(0.05)
            if second.acquire(timeout=0.1):     # if not grabbed within 0.1 s
                try:
                    return                       # got both: dish done
                finally:
                    second.release()
        # leaving the with block put `first` down
        time.sleep(random.uniform(0, 0.1))       # rest a random moment, then retry

a = threading.Thread(target=polite_cook, args=("minho", knife, board))
b = threading.Thread(target=polite_cook, args=("sua", board, knife))
a.start(); b.start()
a.join(); b.join()
print(tries)
# e.g. {'minho': 2, 'sua': 3}  (different on every run)

They bump into each other a few times, but both finish in the end. Take out random.uniform(0, 0.1), though, and a new problem can show up: livelock.

It's like two people meeting in a hallway who keep stepping aside in the same direction. Unlike a deadlock, both are busy moving, yet nobody ever finishes cooking. Mix in a random rest and sooner or later someone moves first, which breaks the cycle.

Real threads wobble a little in their timing, so a short example rarely reproduces livelock every time. That makes it more dangerous: it shows up only on heavy-load days. Whenever you use fix 2, always add the random rest.

5-5. Five cooks and five knives (6 min)

Computer science has a famous puzzle called the dining philosophers problem. Five people sit at a round table with one fork between each pair. To eat, you need both forks next to you. Move it into the kitchen and you get five cooks around a round counter with five knives.

N = 5

def service(ordered):
    knives = [threading.Lock() for _ in range(N)]   # five knives
    meals = [0] * N

    def cook(i):
        left, right = i, (i + 1) % N
        if ordered:
            first, second = min(left, right), max(left, right)
        else:
            first, second = left, right
        for _ in range(3):
            with knives[first]:
                time.sleep(0.05)          # pause holding the first knife
                with knives[second]:
                    meals[i] += 1

    ts = [threading.Thread(target=cook, args=(i,), daemon=True) for i in range(N)]
    for t in ts: t.start()
    for t in ts: t.join(timeout=1)
    return sum(t.is_alive() for t in ts), meals

print("left first:", service(ordered=False))
print("small first:", service(ordered=True))
# left first: (5, [0, 0, 0, 0, 0])
# small first: (0, [3, 3, 3, 3, 3])

• Everyone grabs left first: if all five pick up their left knife at once, the right knife is always in a neighbor's hand. The waiting forms a loop around all five, and after a second all five threads are still stuck.
• Lower-numbered knife first: cooks 0 to 3 (the code counts from 0) still start with their left knife, but cook 4 alone now starts with the right one (knife 0). One link in the loop breaks, and everyone finishes three dishes.

The lab below plays this out one step at a time. If we pushed real threads on the server into a deadlock, there would be no way to free them, so this one lab runs as a simulation. The number on a knife is the cook holding it.

• Everyone grabs left first: on the first step all five cooks pick up one knife each, and the red deadlock warning appears. After that, nothing changes no matter how many times you press.
• Lower-numbered knife first: cook 5 tries to grab knife 1 first and has to wait. That leaves knife 5 free, so cook 4 starts cooking on the second step. Turn on auto-play and the dish counts rise evenly.
• Put it down if stuck: the first two steps look like a deadlock, and the warning even appears. On the third step the waiting cooks put their knives down, and cook 5 grabs a free knife and starts cooking. Remember that if everyone put down and picked up on exactly the same beat, this could turn into a livelock.

5-6. Investigating a frozen kitchen: faulthandler (4 min)

When a program has frozen and you don't know where, the standard library's faulthandler can help. It prints the line every thread is currently on. Save the code below as stuck.py and run it.

import faulthandler
import threading
import time

knife = threading.Lock()
board = threading.Lock()

def minho():
    with knife:
        time.sleep(0.1)
        with board:
            pass

def sua():
    with board:
        time.sleep(0.1)
        with knife:
            pass

faulthandler.dump_traceback_later(1)        # if still here after 1 s, print every thread
crew = [threading.Thread(target=f, name=f.__name__, daemon=True) for f in (minho, sua)]
for t in crew: t.start()
for t in crew: t.join(timeout=2)
faulthandler.cancel_dump_traceback_later()  # finished in time: cancel the scheduled dump

Timeout (0:00:01)!
Thread 0x00009560 [sua] (most recent call first):
  File "stuck.py", line 17 in sua
  ...
Thread 0x0000a670 [minho] (most recent call first):
  File "stuck.py", line 11 in minho
  ...

The output is trimmed (addresses and paths differ on every run). Sua is stuck at line 17, with knife:, and Minho at line 11, with board:. You can see at a glance who is waiting for what.

• faulthandler.dump_traceback_later(timeout): schedules a dump of every thread's position to standard error after timeout seconds. With repeat=True it keeps repeating; with exit=True it exits the program after the dump.
• faulthandler.dump_traceback(all_threads=True): dumps right now, no scheduling. Handy for snapshotting the state in the middle of a long job.
• If a test hangs now and then, set dump_traceback_later at the start of the test. On the day it hangs, the culprit leaves a trace.

Closing time (10 min)

Tonight's goal was for three cooks who each need a knife and a board to cook 100 times apiece without ever freezing. Mr. Tak uses three tools, a pan included. Give every tool a number and have everyone grab through hold, and it no longer matters what order anyone writes them in.

PAN = (3, threading.Lock())
meals = {}

def cook(name, *tools):
    for _ in range(100):
        with hold(*tools):            # always the lowest-numbered tool first
            time.sleep(0)
            meals[name] = meals.get(name, 0) + 1

crew = [threading.Thread(target=cook, args=a, daemon=True) for a in [
    ("minho", KNIFE, BOARD), ("sua", BOARD, KNIFE), ("tak", PAN, BOARD, KNIFE)]]
for t in crew: t.start()
for t in crew: t.join(timeout=3)
print([meals[n] for n in ("minho", "sua", "tak")], sum(t.is_alive() for t in crew))
# [100, 100, 100] 0

All three cooked 100 times, and zero are stuck. Next to the rule on the chalkboard, the chef adds one more line: "Knife 1, board 2, pan 3. Lowest number first."

"Tonight the tools froze us. Tomorrow it'll be the people. When orders pour in, who decides which cook makes which order?"

Practice

1. In the first example of 5-1, delete time.sleep(0.1) and run it several times. Does the deadlock happen every time? In one sentence, write down why a bug that "only freezes sometimes" is more dangerous.
2. In service from 5-5, use print to confirm that with ordered=True only cook 4 grabs in a different order. Using the four conditions, explain why changing the order for just one cook is enough to break the deadlock.
3. In the lab, pick "Put it down if stuck," run 24 steps with auto-play, and compare the dish count with "Lower-numbered knife first."