Deadlock

Learning outcomes:

Define deadlock, livelock, and indefinite postponement, using everyday examples and the dining philosophers
Identify the four necessary conditions for deadlock, and explain how breaking one prevents it
Compare deadlock prevention, avoidance, detection, and recovery, and apply the Banker's algorithm to a simple example
Describe how real systems, such as Linux, Windows, and databases, handle deadlock today

Would you like to download my PowerPoint to follow along?

Deadlock

Deadlock: processes are each waiting for something that will never happen, because they're waiting on each other
System deadlock: one or more processes are stuck this way
Like gridlock: every car is waiting for the car ahead to move, so nobody moves

Deadlock in Spooling Systems

A spooler holds print jobs in a waiting area (a spool) until the printer is ready
If the spool fills up with half-finished jobs, the printer waits for a whole job and the jobs wait for space
Fix: stop taking in new jobs when the spool is nearly full, and start printing before a job is finished
Video streaming uses the same idea: it starts playing before the whole video has downloaded (Week 6, bounded buffer)

Examples of Deadlock

Two programs each need the same two files

Program A opens the spreadsheet and waits for the report. Program B opens the report and waits for the spreadsheet

Two bank transfers at the same moment

One moves money from account 1 to 2 and locks account 1 first. The other moves money from 2 to 1 and locks account 2 first. Each waits for the other's lock

Everyday versions: two roommates, one holding the TV remote and waiting for the charger, the other holding the charger and waiting for the remote
Historical note: textbooks often use two tape drives. Still worth knowing because the example works the same with any two resources

Dining Philosophers: A Recap

Five philosophers, five chopsticks, and each needs both chopsticks next to them to eat (Week 6)
A good solution must:

Never deadlock
Never let anyone starve
Never let two philosophers use the same chopstick at once (mutual exclusion)

Dining Philosophers: A Solution

Number the chopsticks 1 to 5, and every philosopher picks up the lower-numbered chopstick first
Then nobody can be waiting in a full circle, so deadlock is impossible
This is called resource ordering. It breaks the circular wait condition (below), and real systems use it too
Several earlier attempts didn't work. They led to deadlock, to everyone trying and failing over and over (livelock), or to only one person eating at a time (E.W. Dijkstra: Hierarchical ordering of sequential processes (EWD 310), where the problem first appeared)

Curious about those attempts and how the solutions improved? See Dijkstra's original paper above, or this overview (Wikipedia: Dining philosophers problem)

Starvation and Livelock

Indefinite postponement (starvation): a process waits forever because the system keeps choosing others

Fixed with aging: raise its priority the longer it waits (Week 5)

Livelock: processes keep reacting to each other, so they're busy but make no progress

Like two people in a hallway who keep stepping the same way to let each other pass

Deadlock: nobody moves. Livelock: everybody moves, but nobody gets anywhere

Resource Concepts

Preemptible resources can be taken away without losing work

The CPU and memory: the OS can pause a process and give them to someone else

Nonpreemptible resources cannot be taken away without losing work

A printer halfway through a page, a file in the middle of being saved, or a lock on a bank account mid-transfer

Deadlocks happen over nonpreemptible resources

Four Necessary Conditions for Deadlock

Deadlock can only happen if all four are true at once:

Mutual exclusion: only one process can use the resource at a time. Only one person can hold the remote
Hold and wait: a process keeps what it has while waiting for more. Holding the remote while waiting for the charger
No preemption: you can't take a resource away. Nobody grabs the remote out of someone's hand
Circular wait: a circle of processes, each waiting on the next. Each roommate waits on the other

Break any one of the four, and deadlock cannot happen

Deadlock Prevention

Prevention: design the system so one of the four conditions can never be true
Mutual exclusion usually can't be removed, since some things really can only be used by one at a time
Deny hold and wait: ask for everything you need at once. Wasteful, because resources sit unused
Deny no preemption: take resources away when needed. Processes may lose work and have to restart
Deny circular wait: number the resources and always request them in order. Usually the most efficient choice, and the dining philosophers solution

Deadlock Avoidance

Avoidance: before granting a request, check whether it could lead to deadlock later. If it could, make the process wait
Safe state: the OS can guarantee every process will be able to finish
Unsafe state: not deadlocked yet, but the OS can't guarantee everyone finishes
Dijkstra's Banker's algorithm only grants requests that keep the system in a safe state (E.W. Dijkstra: The mathematics behind the Banker's Algorithm (EWD 623))

Like a bank that only lends money if it can still cover every customer's maximum loan

Banker's Algorithm: An Example

The system has 12 of a resource. Three processes each say up front the most they will ever need
P1: needs at most 4, holds 1, may still ask for 3
P2: needs at most 6, holds 4, may still ask for 2
P3: needs at most 8, holds 5, may still ask for 3
10 are in use, so 2 are free. This is safe: P2 can finish with the 2 free ones and return 6. Then P1 can finish, and then P3
If P1 asks for 1 more now, only 1 would be free, and no process could be sure to finish. That would be unsafe, so P1 has to wait

Weaknesses of the Banker's Algorithm

It needs a fixed number of resources and a fixed group of processes
Every process must know its maximum needs in advance
Requests are only promised to be granted within some "finite time", which could be a long wait
These rules don't fit real computers, where programs start and stop all the time, so it's rarely used as is

Deadlock Detection

Detection: let deadlocks happen, notice them, then fix them
The OS keeps a graph of who is waiting for whom (a wait-for graph). A circle in the graph means deadlock
The check can run every time a resource is requested, which catches deadlock early but adds overhead, or every so often
Detection finds which processes and resources are involved, so recovery knows what to fix

A Wait-For Graph

Diagram: P1 waits for P2, P2 waits for P3, and P3 waits for P1. The arrows form a circle, which means these three processes are deadlocked

Deadlock Recovery

Stop processes: end all of them, or one at a time until the circle is broken
Take resources back: give a resource to another process, then let the first one try again
Roll back: return a process to a saved checkpoint and restart it from there (File Systems week)
Suspend and resume: put a process on hold without losing its work

Choosing Which Process to Stop

Things to consider:

Its priority
How long it has run, and how much it has left
What resources it holds, and what it still needs
How many processes have to be stopped
Whether someone is waiting on it, like an open app, or it is a background job

Watch out for starvation: if the same process is picked every time, it never finishes

What Real Systems Do

Linux and Windows mostly don't stop deadlocks between your apps. Deadlocks are rare, and the checks would slow everything down, so programs are left to avoid them (the ostrich approach)

If an app freezes this way, you force quit it (Week 2)

Inside the kernel, Linux uses a tool called lockdep to catch locks taken in the wrong order before they cause a deadlock (Linux kernel documentation: Runtime locking correctness validator (lockdep))
Databases detect deadlocks and cancel one of the transactions involved (PostgreSQL: Explicit locking and deadlocks)

That's why an app sometimes says "something went wrong, please try again" (Microsoft: SQL Server deadlocks guide)

Suggested Activities and Discussion Topics:

Discussion: describe a deadlock from everyday life, such as a four-way stop or a traffic jam. Which of the four conditions does it meet?
Activity: think of a deadlock in a group project, a shared apartment, or at work. Describe who was holding what and waiting for what. Which one of the four conditions would you break to fix it, and how?
Activity: work through the Banker's algorithm example. Then try a new request: P3 asks for 2 more. Would you grant it? Show why the system would be safe or unsafe
Discussion: deadlock and livelock both mean nothing gets done. Using the hallway example, explain the difference. Can you think of another everyday livelock?
Discussion: Linux and Windows mostly don't prevent deadlocks between apps, but databases do detect them. Why do you think they made different choices?

Would you like to see some more classes? Click here