DEADLOCKS

The Deadlock Problem

System Model

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

Resource-Allocation Graph - a diagram showing allocations

A set of vertices V and a set of edges E.

Example

Methods for Handling Deadlocks

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

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

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

e.g.  12 instances of a resource. systems is safe because <p1, p0, p2> satisfies safety condition.
The following diagram shows how deadlock can occur.
At point t, any move upwards would enter an unsafe state.
 

Resource-Allocation Graph Algorithm

Example

Banker's Algorithm (Dijkstra 1965)

Example: consider the following:

A banker 10 thousand dollars and four customers Florence,  Dougal, Dylan and Zebedee. each customer has a maximum need and and starts owing nothing.
Name  Used  Max 
Florence 
Dougal 
Dylan 
Zebedee 
Available = 10
Safe
Name  Used  Max 
Florence 
Dougal 
Dylan 
Zebedee 
Available = 2
Safe, because any requests for loans, except to Dylan, can wait until Dylan repays his loan.
Name  Used  Max 
Florence 
Dougal 
Dylan 
Zebedee 
Available = 1
Unsafe, since if all customers ask for their maximum, none will get it, causing deadlock.

Safety Algorithm

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


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


  5. Finish[i] := true
    go to step 2.
  6. If Finish[i] = true for all i, then the system is in a safe state.
May require an order of m x n 2 operations to decide whether a state is safe.

Resource-Request Algorithm for process Pi 

Request i = request vector for process Pi .

If Request i [ j ] = k , then process Pi wants k instances of resource type R j .
  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, Pi must wait, since resources are not available.
  3. Pretend to allocate requested resources to Pi by modifying the state as follows:

Example of Banker's algorithm

Deadlock Detection

Single Instance of Each Resource Type

Several Instances of a Resource Type

Detection Algorithm

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

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

  5. go to step 2.
  6. If Finish[i] = false, for some i, 1 <= i <= n, then the system is in a deadlock state. Moreover, if Finish[i] = false, then Pi is deadlocked.
  • Algorithm requires an order of m x n2 operations to detect whether the system is in a deadlocked state.
  • Example of Detection algorithm

    Detection-Algorithm Usage

    Recovery from Deadlock

    Combined Approach to Deadlock Handling