Deadlocks: Deadlocks Chapter 3 3.1. Resource
3.2. Introduction to deadlocks
3.3. The ostrich algorithm
3.4. Deadlock detection and recovery
3.5. Deadlock avoidance
3.6. Deadlock prevention
3.7. Other issues
Resources: Resources Examples of computer resources
printers
tape drives
tables
Processes need access to resources in reasonable order
Suppose a process holds resource A and requests resource B
at same time another process holds B and requests A
both are blocked and remain so
Hardware and software deadlocks
Resources: Resources Deadlocks occur when …
processes are granted exclusive access to devices
we refer to these devices generally as resources
Resources may have multiple copies
Preemptable resources
can be taken away from a process with no ill effects (for example memory)
Nonpreemptable resources
will cause the process to fail if taken away (e.g. CDR)
Resources: Resources Sequence of events required to use a resource
request the resource
use the resource
release the resource
Must wait if request is denied
requesting process may be blocked
may fail with error code
Nature of requesting a resource is highly system dependent (e.g. request system call)
Resource Acquisition: Resource Acquisition t
Introduction to Deadlocks: Introduction to Deadlocks Formal definition : A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause
Usually the event is release of a currently held resource
None of the processes can …
run
release resources
be awakened
Number of processes and resources is unimportant
Introduction to Deadlocks: Introduction to Deadlocks Different from starvation and livelock
Starvation – one process is active, but never gets the resource
Livelock – all processes starve
Four Conditions for Deadlock: Four Conditions for Deadlock Mutual exclusion condition
Each resource assigned to 1 process or is available
Hold and wait condition
Process holding resources can request additional
No preemption condition
Assigned resources cannot be involuntarily claimed
Circular wait condition
Must be a circular chain of 2 or more processes
Each is waiting for resource held by next member of the chain
Dealing with Deadlocks: Dealing with Deadlocks Strategies
Just ignore the problem altogether (Ostrich Alg.)
Allow deadlock, detect it, break it
Prevention
Negate one of the four necessary conditions
Dynamic avoidance
Careful resource allocation – each resource request is analyzed and denied if deadlock might result
The Ostrich Algorithm: The Ostrich Algorithm Pretend there is no problem
Reasonable if
deadlocks occur very rarely
cost of prevention is high
UNIX and Windows takes this approach
It is a trade off between
convenience
correctness
Deadlock Prevention & Avoidance: Deadlock Prevention andamp; Avoidance Deadlock prevention
Define a global ordering of all resources
Each process locks resources in order
Resource can be unlocked at any time
Useful within multi-threaded programs
Deadlock avoidance – 'Banker’s Algorithm'
Detection: Deadlock Modeling: Detection: Deadlock Modeling Modeled with directed graphs
resource R assigned to process A
process B is requesting/waiting for resource S
process C and D are in deadlock over resources T and U
Deadlock Modeling: How deadlock occurs A B C Deadlock Modeling
Detection with One Resource of Each Type: Detection with One Resource of Each Type A…G: processes; R…W: resources
Note the resource ownership and requests
Is this system deadlocked and if yes, which processes are involved?
A cycle can be found within the graph, denoting deadlock
Detection with One Resource of Each Type: Detection with One Resource of Each Type We need a formal algorithm for detecting deadlocks
A simple one to detect cycles:
Use resource graph
Perform DFS (depth first search) starting at each node, looking for cycles (recurrence of starting node)
If it comes to a node it has encountered in this run, then there exists a cycle.
Why use DFS and not BFS?
Review DFS vs. BFS.
Pseudocode for Deadlock Detection: Pseudocode for Deadlock Detection For i=1 to N nodes {
reset graph to unmarked;
L = empty list;
traverse_graph (node[i]);
} traverse_graph (node) {
add node to L;
check for cycle in L;
if (there exists outgoing unmarked arcs from node) {
mark node-andgt;outgoing;
traverse_graph (node-andgt;outgoing);
}
}
Detection: Time Complexity: Detection: Time Complexity N nodes, E arcs
Time complexity for DFS is O (N + E)
Need to do DFS N times (once for each node)
O (N (N + E))
Check for cycles
Simple way: can check every node visited to see if it is equal to root – O(1) complexity
Better: check for any cycle in branch – worse case O (N )
Total complexity
O (N (N + E) + N ) = O (2N + NE) = O (N + NE)
N andlt;andlt; E, so N andlt;andlt; N E, total complexity is O (NE) 2 2 2 2 2
Detection: How often to run?: Detection: How often to run? After every allocation of resource is too expensive
Every few minutes
When CPU is idle – indication of blocked processes waiting for resources
Detection with Multiple Resources of Each Type: Detection with Multiple Resources of Each Type Basic idea: Allocate resources to a process that can be run to completion
4 data structures:
Vector of resources in existence
E = # of resource i in system
Vector of available resources,
A = # of available resource i
Allocation matrix
C = # of resource j that are being held by process i
Request matrix
R = # of resource j that are requested by process i i i ij ij
Detection with Multiple Resources of Each Type: Detection with Multiple Resources of Each Type Invariant property: Σi=1Cij + Aj = Ej
n
Detection with Multiple Resources of Each Type: Detection with Multiple Resources of Each Type Deadlock detection is based on comparing vectors:
Algorithm
Look for an unmarked process, Pi for which the i-th row of R is less or equal to A
If such a process is found, add the i-th row of C to A, mark the process and go back to step 1
If no such process exists the algorithm terminates
Detection with Multiple Resources of Each Type: Detection with Multiple Resources of Each Type Unmark all processes;
While (there exists unmarked processes)
for i = 1to n processes {
can_satisfy = TRUE;
for j = 1 to r resources {
if (Rij andgt; Aj) {
can_satisfy = FALSE;
break;
}
}
if (can_satisfy) {
for j = 1 to r resources // Release resources since alloted to process i
Aj += Cij; // process i can finish and release its resources
mark process;
}
}
Detection with Multiple Resources of Each Type: Detection with Multiple Resources of Each Type An example for the deadlock detection algorithm
(3/2/1)
Recovery from Deadlock: Recovery from Deadlock Recovery through preemption
Take a resource from some process to allow others to complete
Depends on nature of the resource
Recovery through rollback
Checkpoints are written to a file and include memory image, resource state, and other state variables
Lose work that was done after checkpoint since roll back returns machine back to checkpoint state
Checkpoints are considered safe states
Total rollback means that no safe state existed; restart process
Kill process to release resources
Need to make sure process can be started again later w/o ill effects
Recovery from Deadlock: Recovery from Deadlock Abort all deadlocked processes
Expensive – lose data and results of computation
Deadlock may occur again if all processes restarted
Abort one process at a time until no deadlock
Lots of overhead – after each process is aborted, must do detection again
Which process to abort?
Abort the one that incurs minimal cost
Factors – priority, how long process has run, type of resource process has, requested resources, type of process
Deadlock Prevention: Attack 4 Deadlock Conditions: Deadlock Prevention: Attack 4 Deadlock Conditions Condition Approach Problem
Mutual -Spooling – exp. only printer -Not all devices can be spooled
Exclusion daemon requests printer Competition for spooler space
can become deadlocked
Hold andamp; Wait -Require all processes to
Condition request all resources before
running (then, can use Banker’s)
-Allow processes access to only -Not practical for some cases
1 resource at a time. (exp. Copy between 2 disks)
No Preemption -Allow preemption -Not viable for some resources
(exp. Printers)
Circular Wait -Order resources numerically -There may be too many
Processes must make requests resources to numerically order
in order. (database tables, for exp.)
Deadlock PreventionAttacking the Mutual Exclusion Condition: Deadlock Prevention Attacking the Mutual Exclusion Condition Some devices (such as printer) can be spooled
only the printer daemon uses printer resource
thus deadlock for printer eliminated
Not all devices can be spooled
Principle:
avoid assigning resource when not absolutely necessary
as few processes as possible actually claim the resource
Attacking the Hold and Wait Condition: Attacking the Hold and Wait Condition Goal: Prevent processes that hold resources from waiting for more resources
Require processes to request resources before starting
a process never has to wait for what it needs
Problems
may not know required resources at start of run
also ties up resources other processes could be using
Variation:
process must give up temporarily all resources before requesting a new one
then request all immediately needed
Attacking the No Preemption Condition: Attacking the No Preemption Condition This is not a viable option
Consider a process given the printer
halfway through its job
now forcibly take away printer
!!??
Attacking the Circular Wait Condition: Attacking the Circular Wait Condition Normally ordered resources
A resource graph (a) (b)
Attacking the Circular Wait Condition: Attacking the Circular Wait Condition Rule: All requests of a process must be made in numerical order =andgt; the resource allocation graph can not have cycles
Either i andlt; j or i andgt; j =andgt; can’t have deadlocks
Same logic with multiple resources: at every instant one assigned resource will be the highest
Problem: impossible to find an ordering to satisfy everyone
Deadlock Avoidance: Deadlock Avoidance So far we assumed that all requests take place at the beginning
The system must be able to decide whether granting a resource request is safe or not
Is there an algorithm that can always avoid deadlocks?
Yes, if certain information is known in advance
State of Resource Allocation: Safe & Unsafe States: State of Resource Allocation: Safe andamp; Unsafe States Safe
System is not deadlocked and can guarantee that all processes will finish. There is some scheduling order such that all processes finish.
Unsafe
System may not be deadlocked, but cannot guarantee that all processes can finish
No scheduling order that guarantees all processes will finish, but process may be lucky and finish due to some processes releasing resources early
Determining Safe/Unsafe Using Banker’s Alg.: Determining Safe/Unsafe Using Banker’s Alg. Similar to deadlock detection
Consider each request as it occurs and see if granting it leads to a safe state
If a granting a resource leads to a deadlock cycle, then state is unsafe and do not grant
Key assumptions:
All processes need to declare their max resources
#of processes and resources are fixed. Need to dynamically update resource allocation table for entering/exiting processes to handle dynamic environment
Determining Safe & Unsafe States: Determining Safe andamp; Unsafe States Use resource allocation table
Examples for a single resource. Can be scaled to multiple resources
Proc. Has Max (Needs) Proc. Has Max (Needs)
A 3 9 6 A 4 9 5
B 2 4 2 B 2 4 2
C 2 7 5 C 2 7 5
Free: 3 Free: 2
What is the difference between detection alg. And Banker’s?
Other IssuesTwo-Phase Locking: Other Issues Two-Phase Locking Deadlock avoidance and prevention are difficult to use in practice for large dynamic systems
Detection and recovery is more practical
Two-phase locking is practical solution often used in databases
Phase 1
process tries to lock all records it needs, one at a time
if needed record found locked, start over
(no real work done in phase one)
If phase 1 succeeds, start phase 2
perform updates
release locks
Note similarity to requesting all resources at once
Applicable in small-scale, such as process that updates a few records in a few tables
Not useful for processes where release and restart is not possible
Non-resource Deadlocks: Non-resource Deadlocks Possible for two processes to deadlock
Each is waiting for the other to do some task
Can happen with semaphores
Each process required to do a down() on two semaphores (mutex and another)
If done in wrong order, deadlock results
Solution is more careful programming