What is deadlock, and what four conditions are required for it?
Interview preparation resource from Gate Smashers.
Deadlock is a state in which two or more processes or threads are indefinitely blocked because each is waiting for a resource or event that another member of the set must provide. The four Coffman conditions required for deadlock are mutual exclusion, hold and wait, no preemption, and circular wait. All four are necessary; preventing any one of them prevents deadlock, although their presence alone does not guarantee that a deadlock will occur.
Definition
A deadlock occurs when a group of processes or threads cannot make progress because each is waiting on another member of the group. Progress requires an external action, such as terminating a process, releasing a resource, or otherwise breaking the wait cycle.
Four necessary conditions
The following conditions must hold simultaneously for a resource deadlock to be possible:
- Mutual exclusion: At least one resource is non-shareable, so only one process can use it at a time.
- Hold and wait: A process holds one or more resources while waiting to acquire additional resources held by other processes.
- No preemption: A resource cannot be forcibly taken from its holder; the holder releases it voluntarily.
- Circular wait: A circular chain exists in which each process waits for a resource held by the next process in the chain, with the last process waiting for a resource held by the first.
Why the conditions cause blocking
Mutual exclusion makes a resource unavailable to other processes while it is held, and no preemption prevents the operating system from simply reclaiming it. Hold and wait allows processes to retain resources while requesting more, and circular wait creates a closed dependency cycle. As a result, no process in the cycle can obtain what it needs and continue.
Important qualification
The four conditions are necessary, not sufficient: their presence means deadlock is possible, not certain. In a resource-allocation graph, a cycle proves deadlock when every resource type in the cycle has a single instance. When resource types can have multiple instances, a cycle indicates possible deadlock but does not by itself prove it.