Deadlock
CS 273 (OS), Fall 2020
Preliminaries
(A hard problem with no easy solution)
-
Deadlock: A situation in which a set of process exists, each of which is blocked awaiting a resource that is already allocated to another process in that set.
-
Resource: Hardware or software entity allocated to a particular process.
Examples: file, tape, printer; kernel table entry, database record, shared data structure, monitor procedure. -
Preemptable resources, e.g., memory (can swap to disk).
Non-preemptable resources, e.g., printer (during print job) - Four necessary and sufficient
conditions for deadlock
(if all hold then a deadlock exists and
if a deadlock exists then all four hold)-
Mutual exclusion - (of resources)
-
Hold and wait
-
No preemption
-
Circular wait
-
-
Resource allocation graphs illustrate the four conditions
Ignoring the problem of deadlock
Idea: Avoid obvious sources of deadlock (e.g., use a print spool directory and a printer daemon), and don't worry about most other sources of deadlock.
E.g., UNIX/Linux: panic or hang if deadlock detected in kernel.
Simple design and implementation, but may be impractical for critical systems.
Deadlock detection and recovery
Idea: Identify any deadlocks that occur, and take action to break them.
-
Detecting cycles, e.g., by backtracking on resource allocation graph.
- Assumptions: processes allocate specific resource objects; the kernel maintains graph somehow.
- But processes don't always need specific peripherals, in which case allocating from a pool of similar resources can improve performance.
-
Current allocation matrix, request matrix, availability vector of resources.
- Assumptions: processes allocate from pools of similar resources; kernel maintains matrices.
- Issue: Overhead of CPU time for this analysis.
Recovery from deadlock.
-
Preemption.
- Not always feasible, e.g., with tape drive.
- What makes for a good preemption policy?
-
Rollback, checkpoints.
- Complicated to catch all lost state changes.
-
Kill processes until the deadlock goes away.
- Practical and simple (actually used!)
- Policy...
- What about non-reversible state changes by incomplete killed processes?
-
Deadlock avoidance
Idea: Refuse to allocate unless system will be safe from deadlock.
-
Assumption: System knows current allocation and potential maximum need for each process, and current resources free.
- But, do processes really know maximum needs in advance? Overestimates could lead to inferior system performance, and some programs (e.g., server) may have no way to predict future requirements.
-
Bankers algorithm (Dijkstra '65): delay requests that lead to unsafe states.
Free: 2process has max A 1 6 B 1 5 C 2 4 D 4 7 -
Multiple resources
Assigned: process tape plotter printer CD A 3 0 1 1 B 0 1 0 0 C 1 1 1 0 D 1 1 0 1 E 0 0 0 0 Needed: process tape plotter printer CD A 1 1 0 0 B 0 1 1 2 C 3 1 0 0 D 0 0 1 0 E 2 1 1 0 Available: (1, 0, 2, 0) Note: These algorithms must be modified to allow for processes and resources to come and go dynamically.
- If a resource goes down, a deadlock may arise. Plan for this by holding spares in reserve?
Deadlock prevention
Idea: Negate one of the four conditions required for deadlock.
-
Negate mutual exclusion
- Author's example: print spooling. But, doesn't this negate circular wait instead of mutual exclusion? Printer daemon still holds mutually exclusive access to printer, but it never holds anything else, so daemon and printer can never be involved in a circular wait.
- Even then, conceivable for multiple processes to block on full print spool area, each partially filling that area.
- Principle: Avoid allocating resources until absolutely necessary (cf., "progress" criterion in IPC).
-
Negate hold and wait.
- Request all resources before starting execution? Same difficulties in prediction as for deadlock avoidance.
- Release and re-request all resources when trying to add another? Might not make headway on the algorithm...
-
Negate no-preemption? Not practical for all devices.
-
Negate circular wait
- One strategy: globally number all resources and require that resources be requested in increasing numerical order, to avoid cycles in graphs.
- But this suggests a linear prioritization of all resources, which probably isn't reasonable.
Other issues
Two-phase locking
- Lock all resources. If a prior lock encountered, release all locks and try again.
- Do work
- Release locks
-
Policies that lead to starvation.