Core · Operating systemsLesson 5 of 6Free to read

Deadlock · Operating Systems

How can two programs get stuck waiting for each other forever?

Why you need it

A deadlock freezes a program, a database or a whole service with no error and no CPU use: everyone is politely waiting. Databases detect them and kill one transaction; in your own code you prevent them by design. Spotting the pattern saves days of debugging.

The intuition

Two friends, one pen and one notebook. Ann holds the pen and waits for the notebook; Ben holds the notebook and waits for the pen. Nobody lets go.

Draw a wait-for graph: an arrow from each waiting process to the process holding what it wants. A deadlock is a cycle in that graph.

Deadlock needs all four: exclusive resources, holding while waiting, no taking things away, and a circular wait. Break any one. The usual fix: always acquire locks in the same global order (pen before notebook), so a cycle can't form.

Definition

Deadlock

A set of processes each waiting for a resource held by another in the set, so none can proceed.

Lock ordering

A rule that every thread acquires locks in the same fixed order. It removes circular waits.

Examples

Find the cycle

Try it yourself

waits[p] is the process p is waiting for. Follow the arrows; returning to a process already on the path means deadlock.

def deadlocked(waits):
    for start in waits:
        seen = []
        p = start
        while p in waits:
            if p in seen:
                return seen[seen.index(p):]
            seen.append(p)
            p = waits[p]
    return None

print(deadlocked({"A": "B", "B": "C", "C": "A"}))
print(deadlocked({"A": "B", "B": "C"}))

Step by step

L5Keep following while the current process is waiting for someone.
L6Back at a process already on this path: a cycle.
L12A waits for B, B for C, C for A.['A', 'B', 'C']
L13C isn't waiting, so it will finish and free the others.None

Common mistakes

Fixing it with sleep

Adding a delay changes the timing so the bug hides. The lock order is still wrong and the deadlock will come back under load.

Holding locks while calling out

Calling unknown code (a callback, a network request) while holding a lock invites it to take other locks in the wrong order. Release first.

Quick quiz

1. Thread 1 locks `accounts` then `log`. Thread 2 locks `log` then `accounts`. What's the simplest fix?

AMake both lock accounts first, then log
BAdd a sleep in thread 2
CUse more threads

Show the answer

Answer: A

One global order makes a circular wait impossible.

2. What does this print?

1
2
3

order = {"pen": 1, "book": 2, "lamp": 3}
wanted = ["lamp", "pen", "book"]
print(sorted(wanted, key=order.get))

A
```
['pen', 'book', 'lamp']
```
B
```
['lamp', 'pen', 'book']
```
C
```
['book', 'lamp', 'pen']
```

Show the answer

Answer: A

Sorting the locks you need by a global rank gives the order to take them in.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictWho waits for whom?
Type exactly what this program prints.
ModifyOrder the locks
lock_plan(needed) returns the order in which a thread should take its locks. It currently takes them in whatever order they're listed, which can deadlock. Use the global ranking in RANK so every thread takes locks in the same order.
WriteDetect a deadlock
Write has_deadlock(holds, wants). holds maps each process to the resource it holds; wants maps each process to the resource it's waiting for (or None). Build who-waits-for-whom and return True if there is a cycle.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Deadlock	死锁	Processes waiting on each other in a cycle, so none can continue.
Wait-for graph	等待图	Arrows from each waiting process to the one it waits for.
Lock ordering	锁顺序	Always taking locks in one fixed order to prevent deadlock.