Deadlocks

A deadlock is a state where a set of processes are each waiting for a resource held by another process in the set, so none can proceed.

Necessary Conditions (Coffman)

Mutual exclusion
Hold and wait
No preemption
Circular wait

All four must hold at the same time for a deadlock to occur.

Handling Deadlocks

Strategy	Idea
Prevention	Break one of the four conditions (e.g. order resources to prevent circular wait)
Avoidance	Grant requests only if the system stays in a safe state (Banker's algorithm)
Detection and recovery	Allow deadlock, detect it (wait-for graph), then kill or preempt processes
Ignorance	Ostrich algorithm (most desktop OSs)

Banker's Algorithm Example

Text

Resources A B C, Available = (3, 3, 2)

       Allocation   Max      Need = Max − Allocation
P0     0 1 0        7 5 3    7 4 3
P1     2 0 0        3 2 2    1 2 2
P2     3 0 2        9 0 2    6 0 0
P3     2 1 1        2 2 2    0 1 1
P4     0 0 2        4 3 3    4 3 1

Work = (3,3,2)
P1: Need (1,2,2) ≤ Work → Work = (3,3,2) + (2,0,0) = (5,3,2)
P3: Need (0,1,1) ≤ Work → Work = (7,4,3)
P4: Need (4,3,1) ≤ Work → Work = (7,4,5)
P0: Need (7,4,3) ≤ Work → Work = (7,5,5)
P2: Need (6,0,0) ≤ Work → Work = (10,5,7)

Safe sequence: <P1, P3, P4, P0, P2>  ⇒ the system is in a SAFE state

Track your progress through the Operating System course

← Prev Next →