Necessary and Sufficient Deadlock Conditions
- Coffman (1971) identified four (4) conditions that must hold simultaneously for
there to be a deadlock.
1. Mutual Exclusion Condition
- The resources involved are non-shareable.
At least one resource (thread) must be held in a non-shareable mode, that is,
only one process at a time claims exclusive control of the resource. If another
process requests that resource, the requesting process must be delayed until the
resource has been released.
2. Hold and Wait Condition
- Requesting process hold already, resources while waiting for requested
- Explanation: There must exist a process that is holding a resource already allocated to it
while waiting for additional resource that are currently being held by other
3. No-Preemptive Condition
- Resources already allocated to a process cannot be preempted.
Resources cannot be removed from the processes are used to completion or
released voluntarily by the process holding it.
- 4. Circular Wait Condition
- The processes in the system form a circular list or chain where each process in
the list is waiting for a resource held by the next process in the list.
As an example, consider the traffic deadlock in the following figure
Consider each section of the street as a resource.
- Mutual exclusion condition applies, since only one vehicle can be on a section of the
street at a time.
- Hold-and-wait condition applies, since each vehicle is occupying a section of
the street, and waiting to move on to the next section of the street.
- No-preemptive condition applies, since a section of the street that is a
section of the street that is occupied by a vehicle cannot be taken away from
- Circular wait condition applies, since each vehicle is waiting on the next
vehicle to move. That is, each vehicle in the traffic is waiting for a section
of street held by the next vehicle in the traffic.
The simple rule to avoid traffic deadlock is that a vehicle should only enter an
intersection if it is assured that it will not have to stop inside the
It is not possible to have a deadlock involving only one single process. The
deadlock involves a circular “hold-and-wait” condition between two or more
processes, so “one” process cannot hold a resource, yet be waiting for another
resource that it is holding. In addition, deadlock is not possible between two
threads in a process, because it is the process that holds resources, not the
thread that is, each thread has access to the resources held by the process.