Four Necessary and Sufficient Conditions for Deadlock
This handout describes the four conditions necessary and sufficient
to cause deadlock.
- mutual exclusion
The resources involved must be unshareable;
otherwise, the processes would not be prevented from using
the resource when necessary.
- hold and wait or partial allocation
The processes must hold the resources they have already been allocated
while waiting for other (requested) resources. If the process had to
release its resources when a new resource or resources were requested,
deadlock could not occur because the process would not prevent others
from using resources that it controlled.
- no pre-emption
The processes must not have resources taken away while that resource is
being used. Otherwise, deadlock could not occur since the operating
system could simply take enough resources from running processes to
enable any process to finish.
- resource waiting or circular wait
A circular chain of processes, with each process holding resources
which are currently being requested by the next process in the chain,
cannot exist. If it does, the cycle theorem (which states that "a
cycle in the resource graph is necessary for deadlock to occur")
indicated that deadlock could occur.
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 6/7/99