deadlock
A set of processes is deadlocked if:
- Each process in the set waiting for an event
- That event can be caused only by another
process
livelock
operations are being executed but no progress is made
conditions for resource deadlocks
- mutual exclusion
- hold and wait
- no preemption
- circular wait condition
mutual exclusion
each resource is assigned to at most one process
hold and wait
processes can request a resource when holding another one
no preemption
resources cannot be taken away from a process
circular wait condition
chain of two or more processes must be waiting for a resource held by next process in the chain
deadlock handling
- ignore the problem
- deadlock detection
- deadlock avoidance
- deadlock prevention
ignore the problem
no action taken
the OS doesn’t handle deadlocks, it is up to the programmer, i.e. manual
- Also known as the ostrich algorithm
- Cost-effective solution to deadlocks
- Assumes deadlocks are rare
- Assumes cost of handling deadlocks is high
- Assumes effects of deadlocks are tolerable
- Simplest solution to manage system resources, i.e., process table, inode table, swap space, etc.
deadlock detection
detect deadlock and perform recovery actions
algorithm for detection + algorithm/mechanism for recovery
- Detection
- Check for cycles in the resource allocation graph
- Track progress and time out
- Explicit detection (e.g., OOM)
- Useful in practice when simple and efficient detection mechanisms (e.g., progress tracking or explicit detection) along with recovery actions are available
deadlock avoidance
carefully allocate resources to avoid deadlocks
requires additional information about resources a process might need during its lifeitme
deadlock prevention
structurally prevent any of the deadlock conditions
provides a method for ensuring at least one of the 4 conditions cannot hold
recovery from a deadlock
force preemption
checkpoint-rollback
killing the offending process
killing the offending process
- abort all deadlocked processes
⇒ expensive, computations done so far have to be done again - abort one process at a time until the deadlock cycle is eliminated
⇒ considerable overhead, after each process is aborted a deadlock check algorithm is invoked
abort processes whose termination will incur the minimum cost; think about:- what the priority of the process is
- how long the process has computed how much longer the process will compute completing its designated task
- resources the process is using and needs to use
- how many processes will be terminated
- whether the process is interactive or batch
issues with aborting a process
it was modifying a file→ it leaves a file in an incorrect state
force preemption
- reassign the resources so that the deadlock is resolved
- issues:
- select a victim process: minimise cost
- rollback: what to do with the victim (can’t continue execution) → roll back to some safe state and restart it from that state
- hard to find a safe state → total rollback (abort and restart essentially)
- starvation: if victim selection is based primarily on cost factors, it may be chosen every time and as a result it will never complete
deadlock avoidance
- safe state: the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock
- safe sequence: all requests will be satisfied
- not all unsafe states are deadlock
Banker’s algorithm
- Customers (processes) request credits (resources)
- Banker (OS) only satisfies requests resulting in safe states
- A state is safe iff there exists a sequence of other states that allows all the customers to complete
- Maximum credit demands are known in advance
- safe state: anybody can obtain new credits and complete, then others can obtain credits and complete
- unsafe state: nobody can obtain new credits and complete
- not enough resources for everyone’s max
deadlock prevention with mutual exlusion
- must hold for non-shareable processes → hard to avoid
- spool everything: typically shifts the problem somewhere else
- not really an option
deadlock prevention with hold and wait
- requests all resources initially (or reacquire them)
- one protocol that can be used requires each process to request and be allocated to its resources before it begins execution
- instead: release current resources and the request new ones
- poor parallelism and resource utilisation, starvation is possible
deadlock prevention with no preemption
- take resources away
- if a process is requesting something it releases everything → preemption
- applicable only to resources whose state can be easily saved and restored later, such as CPU registers and memory space
- N/A in many cases (e.g. printer vs. memory)
deadlock prevention with circular wait
- order resources numerically
- process requests resources in an increasing order
- example: P1 has R5, it then needs R4 and R3 → the requests won’t be granted (3,4 < 5)
- hard to consistently enforce in practice
deadlock handling in practice
deadlock avoidance: rarely an option (hard to know a resource a priori)
deadlock prevention: adopted in particular domains
ignore the problem: last resort when nothing is available
deadlock detection: solution of choice when adequate detection (and recovery) mechanism are available
global OOM killer
- resource: memory
- mechanisms: explicit detection
