What is deadlock?
A situation where two or more processes are unable to proceed because each is waiting for a resource held by another process in the group, forming a circular dependency
How do we detect deadlock and what can be done if it happens?
Grant resources freely and test for deadlock, and if deadlock:
- Kill all deadlocked processes
- Kill random processes until cycle broken
- Take resources from selected processes
- Restart the process and remove all resources
- Rollback processes (will probably deadlock again!)
What are the methods for handling deadlocks?
- Deadlock prevention or avoidance (ensure that the system will never enter a deadlock state)
- Deadlock detection (allow the system to enter a deadlock state and then recover)
- Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX
… ignore the problem and maybe it will go away! If it
doesn’t - re-boot the machine!
What conditions are needed for deadlock to occur?
- Mutual exclusion
- Hold and wait
- No preemption
- Circular wait
What is Mutual Exclusion?
Only one process at a time can use a resource
How does Mutual Exclusion work?
It can’t be used for sharable resources; must hold for non-sharable resources
What is Hold and Wait?
A process holding at least one resource is waiting to acquire additional resources held by other processes in order to proceed
How does Hold and Wait work?
It can’t be used for sharable resources; must hold for non-sharable resources
What is No Preemption?
A resource can be released only voluntarily by the process holding it, after that process has completed its task
How does Mutual Exclusion work?
It can’t be used for sharable resources; must hold for non-sharable resources
What is Circular Wait?
There exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.
How does Mutual Exclusion work?
It can’t be used for sharable resources; must hold for non-sharable resources
Do these conditions need each other?
These four conditions are not independent. The first three are necessary condition, and the circular wait condition is necessary and sufficient. The circular wait condition incorporates the first three.
