Deadlock Prevention Strategies
A deadlock requires four conditions to hold at once, known as the Coffman conditions. Break any one and deadlock becomes impossible. Prevention strategies each target one condition.
The four conditions are:
- Mutual exclusion A resource is held by only one thread
- Hold and wait A thread holds resources while waiting for more
- No preemption Resources cannot be forcibly taken away
- Circular wait A cycle of threads each waits on a resource the next holds
Prevention strategies attack these:
- Resource ordering Impose a global order on locks and always acquire them in that order. This makes a circular wait impossible because a cycle would require acquiring out of order. This is the most practical and widely used technique.
- Acquire all at once Require a thread to request every resource it needs up front, atomically. This breaks hold and wait but reduces concurrency and needs you to know all needs in advance.
- Allow preemption Let a thread that cannot get a lock release the ones it holds and retry. This breaks no preemption but can cause livelock if threads keep backing off in step.
- Use timeouts A thread that waits too long for a lock gives up and releases its held locks, turning a potential deadlock into a recoverable failure.
Distinct from prevention is deadlock avoidance, such as the banker algorithm, which grants requests only if the system stays in a safe state, and detection and recovery, which lets deadlocks happen then breaks them by aborting a thread.
Key idea
Deadlock needs all four Coffman conditions, so prevention works by breaking one, and imposing a global lock ordering to kill circular wait is the most practical approach.