DEADLOCKS

• System Model
• Deadlock Characterization
• Methods for Handling Deadlocks
• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection
• Recovery from Deadlock
• Combined Approach to Deadlock Handling

The Deadlock Problem

• A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.
• Example
• System has 2 tape drives.
• P₁ and P₂ each hold one tape drive and each needs another one.
• Example




semaphores A and B , initialized to 1

  P0      P1 
------  ------ 
wait(A) wait(B) 
wait(B) wait(A)

• Example: bridge crossing




 
• Traffic only in one direction.
• Each section of a bridge can be viewed as a resource.
• If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback).
• Several cars may have to be backed up if a deadlock occurs.
• Starvation is possible.

System Model

• Resource types R₁ , R₂ , ..., R_m-1


Examples of resource types -  CPU cycles, memory space, I/O devices
• Each resource type R_i has W_i instances.


e.g. 2 CPUs, 1 Floppy Disk, 2 Hard Disks
• Each process utilizes a resource (using system calls) as follows:
• request
• use
• release

Deadlock Characterization - deadlock can arise if four conditions hold simultaneously.

• Mutual exclusion: only one process at a time can use a resource.
• Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.
• No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task.
• Circular wait: there exists a set {P₀ , P₁ , ..., P_n } of waiting processes such that P₀ is waiting for a resource that is held by P₁ , P₁ is waiting for a resource that is held by P₂ , ..., P_{n -1} is waiting for a resource that is held by P_n , and P_n is waiting for a resource that is held by P ₀ .

Resource-Allocation Graph - a diagram showing allocations

• V is partitioned into two types:
• P = {P₁ , P₂ , ..., P_n }, the set consisting of all the processes in the system.
• R = {R ₁ , R ₂ , ..., R_m }, the set consisting of all resource types in the system.
• request edge - directed edge P_i -> R_j
• assignment edge - directed edge R_j -> P_i 

Example

• Process





 
• Resource type with 4 instances





 
• P_i requests instance of R _j



• P_i is holding an instance of R _j



• Example of a resource-allocation graph with no cycles.

• Example of a resource-allocation graph with a cycle.



• If graph contains no cycles -> no deadlock.
• If graph contains a cycle ->
• if only one instance per resource type, then deadlock.
• if several instances per resource type, possibility of deadlock.




e.g. R={1r₁,2r₂,1r₃},E={(p₁,r₁),(p₂,r₃),(r₁,p₂),(r₂,p₂),(r₂,p₁),(r₃,p₃),(p₃,r₂)}
e.g. R={2r₁,2r₂},E={(p₁,r₁),(r₁,p₂),(r₁,p₃),(r₂,p₁),(p₃,r₂),(r₂,p₄)}

Methods for Handling Deadlocks

• Ensure that the system will never enter a deadlock state. (traffic lights)
• Allow the system to enter a deadlock state and then recover. (back up cars)
• Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.

Deadlock Prevention - restrain the ways resource requests can be made.

• Mutual Exclusion - not required for sharable resources; must hold for nonsharable resources.
• Hold and Wait - must guarantee that whenever a process requests a resource, it does not hold any other resources.
• Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none.
• Low resource utilization; starvation possible.
• No Preemption -
• If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.
• Preempted resources are added to the list of resources for which the process is waiting.
• Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.
• Circular Wait - impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.

Deadlock Avoidance - requires that the system has some additional a priori information available.

• Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.
• The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.
• Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

Safe State - when a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.

• System is in safe state if there exists a safe sequence of all processes.
• Sequence <P₁ , P₂ , ..., P_n > is safe if for each P_i , the resources that P_i can still request can be satisfied by the currently available resources plus the resources held by all the P_j , with j < i.
• If P_i resource needs are not immediately available, then P_i can wait until all P_j have finished.
• When P_j is finished, P_i can obtain needed resources, execute, return allocated resources, and terminate.
• When P_i terminates, P_i+1  can obtain its needed resources, and so on.
• If a system is in safe state -> no deadlocks.
• If a system is in unsafe state -> possibility of deadlock.
• Avoidance -> ensure that a system will never enter an unsafe state.

     Max Needs  Current Needs
p0      10           5
p1       4           2
p2       9           2

Resource-Allocation Graph Algorithm

• Claim edge P_i -> R_j indicates that process P_i may request resource R_j ; represented by a dashed line.
• Claim edge converts to request edge when a process requests a resource.
• When a resource is released by a process, assignment edge reconverts to a claim edge.
• Resources must be claimed a priori in the system.

Example

E={(r₁,p₁)} C={(p₁,r₂),(p₂,r₁),(p₂,r₂)}
no cycles -> system is safe
now if p₂ requests r₂ -> system is unsafe.

Banker's Algorithm (Dijkstra 1965)

• Multiple resource types.
• Each process must a priori claim maximum use.
• When a process requests a resource it may have to wait.
• When a process gets all its resources it must return them in a finite amount of time.
• Data Structures for the Banker's algorithm where n = number of processes, and m = number of resource types.
• Available: Vector of length m. If Available[j] = k, there are k instances of resource type R_j available.
• Max: n x m matrix. If Max[i,j] = k, then process P_i may request at most k instances of resource type R _j .
• Allocation: n x m matrix. If Allocation[i,j] = k, then P_i is currently allocated k instances of R _j .
• Need: n x m matrix. If Need[i,j] = k, then P_i may need k more instances of R_j to complete its task.
Need[i,j] = Max[i,j] - Allocation[i,j].

Safety Algorithm

1. Let Work and Finish be vectors of length m and n, respectively.


Initialize:
Work := Available 
Finish[i] := false for i = 1, 2, ..., n. 
2. Find an i such that both:
1. Finish[i] = false
2. Need _i <= Work  (every element in Need_i < every element in Work)
If no such i exists, go to step 4.
3. Work := Work + Allocation _i


Finish[i] := true
go to step 2.
4. If Finish[i] = true for all i, then the system is in a safe state.

Resource-Request Algorithm for process P_i 

1. If Request _i <= Need _i , go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.
2. If Request _i <= Available, go to step 3. Otherwise, P_i must wait, since resources are not available.
3. Pretend to allocate requested resources to P_i by modifying the state as follows:
Available := Available - Request _i ;
Allocation _i := Allocation _i + Request _i ;
Need _i := Need _i - Request _i ;
• If safe -> the resources are allocated to P_i .
• If unsafe -> P_i must wait, and the old resource-allocation state is restored.

Example of Banker's algorithm

• 5 processes P ₀ through P₄ ; 3 resource types A (10 instances), B (5 instances), and C (7 instances).
• Snapshot at time T ₀ :

 Allocation   Max      Available   Need 
 ----------   ---      ---------   -----
    A B C     A B C      A B C     A B C 
P0  0 1 0     7 5 3      3 3 2     7 4 3 
P1  2 0 0     3 2 2                1 2 2 
P2  3 0 2     9 0 2                6 0 0 
P3  2 1 1     2 2 2                0 1 1 
P4  0 0 2     4 3 3                4 3 1

• Sequence <P₁, P₃, P₄, P₂, P₀> satisfies safety criteria.
• P₁ now requests resources.


Request ₁ = (1,0,2).
• Check that Request ₁ <= Available (that is, (1,0,2) <= (3,3,2)) -> true.

 Allocation   Need      Available    
 ----------   ---      ---------    
    A B C    A B C      A B C      
P0  0 1 0    7 4 3      2 3 0    
P1  3 0 2    0 2 0                 
P2  3 0 2    6 0 0              
P3  2 1 1    0 1 1                
P4  0 0 2    4 3 1

• Executing safety algorithm shows that sequence <P₁, P₃, P₄, P₀, P₂> satisfies safety requirement.
• From this state, can request for (3,3,0) by P₄ be granted?
• From this state, can request for (0,2,0) by P₀ be granted?

Deadlock Detection

• Allow system to enter deadlock state
• Detection algorithm
• Recovery scheme

Single Instance of Each Resource Type

• Maintain wait-for graph
• Nodes are processes.
• P_i ->P_j if P_i is waiting for P_j .
• Periodically invoke an algorithm that searches for a cycle in the graph.
• An algorithm to detect a cycle in a graph requires an order of n ² operations, where n is the number of vertices in the graph.

Several Instances of a Resource Type

• Data structures
• Available: A vector of length m indicates the number of available resources of each type.
• Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
• Request: An n x m matrix indicates the current request of each process. If Request[i,j] = k, then process P_i is requesting k more instances of resource type R_j .

Detection Algorithm

1. Let Work and Finish be vectors of length m and n, respectively. Initialize:

Work := Available.
For i = 1, 2, ..., n, if Allocation_i <> 0, then Finish[i] := false; otherwise, Finish[i] := true.
2. Find an index i such that both:
1.  Finish[i] = false.
2.  Request _i <= Work.
If no such i exists, go to step 4.
3. Work := Work + Allocation _i
   Finish[i] := true

go to step 2.
4. If Finish[i] = false, for some i, 1 <= i <= n, then the system is in a deadlock state. Moreover, if Finish[i] = false, then P_i is deadlocked.

Example of Detection algorithm

• Five processes P ₀ through P₄ ; three resource types A (7 instances), B (2 instances), and C (6 instances).
• Snapshot at time T ₀ :

 Allocation  Request    Available    
 ----------  -------    ---------    
    A B C    A B C      A B C      
P0  0 1 0    0 0 0      0 0 0    
P1  2 0 0    2 0 2                 
P2  3 0 3    0 0 0              
P3  2 1 1    1 0 0                
P4  0 0 2    0 0 2

• Sequence <P₀, P₂, P₃, P₁, P₄> will result in Finish[i] = true for all i.
• P₂ requests an additional instance of type C.

   Request      
   -------    
    A B C            
P0  0 0 0        
P1  2 0 2                 
P2  0 0 1              
P3  1 0 0                
P4  0 0 2

• State of system?
• Can reclaim resources held by process P₀ , but insufficient resources to fulfill other processes' requests.
• Deadlock exists, consisting of processes P₁ , P₂ , P₃ , and P₄ .

Detection-Algorithm Usage

• When, and how often, to invoke depends on:
• How often a deadlock is likely to occur?
• How many processes will need to be rolled back?
• one for each disjoint cycle
• If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes ``caused'' the deadlock.

Recovery from Deadlock

• Process termination
• Abort all deadlocked processes.
• Abort one process at a time until the deadlock cycle is eliminated.
• In which order should we choose to abort?
• Priority of the process.
• How long process has computed, and how much longer to completion.
• Resources the process has used.
• Resources process needs to complete.
• How many processes will need to be terminated.
• Is process interactive or batch?
• Resource Preemption
• Selecting a victim - minimize cost.
• Rollback - return to some safe state, restart process from that state.
• Starvation - same process may always be picked as victim; include number of rollback in cost factor.

Combined Approach to Deadlock Handling

• Combine the three basic approaches (prevention, avoidance, and detection), allowing the use of the optimal approach for each class of resources in the system.
• Partition resources into hierarchically ordered classes.
• Use most appropriate technique for handling deadlocks within each class.