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.
Coffman conditions
All four must hold at the same time:
- Mutual exclusion: a resource is held by one process at a time.
- Hold and wait: a process holds resources while waiting for others.
- No pre-emption: resources cannot be forcibly taken.
- Circular wait: a cycle of processes each waiting for the next.
Example
deadlock.py
import threading, time
a, b = threading.Lock(), threading.Lock()
def t1():
with a:
time.sleep(0.1)
with b: pass # waits for b
def t2():
with b:
time.sleep(0.1)
with a: pass # waits for a -> deadlock
Handling deadlocks
| Strategy | How |
|---|---|
| Prevention | Break one Coffman condition, e.g. always acquire locks in a fixed global order (breaks circular wait) |
| Avoidance | Grant a request only if the system stays in a safe state (Banker's algorithm) |
| Detection and recovery | Build a resource-allocation graph, find cycles, then kill or roll back processes |
| Ignore | The "ostrich algorithm" used by most general-purpose OSes |
Banker's algorithm (idea)
Before granting a request, pretend to grant it, then check whether there is some order in which every process can still finish with the resources available. If yes the state is safe; if not, the request waits.
NOTE
A safe state guarantees no deadlock. An unsafe state does not always deadlock, but it might.
Loading Comments...