Chapter 8 : Deadlock

• System model
• Deadlock Characterization
• Methods of Handling Deadlocks
• Deadlocks Prevention
• Deadlocks Avoidance
• Deadlock Detection
• Recovery of Deadlock
• Combined Approach to Deadlock Handling

[TOC]

SYSTEM MODEL

• A set of processes each holding a resource and waiting to acquire a resource held by another process in the set.

• Example

  • System has two tape drives.
  • $P_1$ and $P_2$ each hold one tape drive and each needs another one.

• Example

  Semaphores A and B, initialized to:

  ​ $P_0$ $P_1$

  ​ wait(A); wait(B);

  ​ wait(B); wait(A);

Bridge Crossing Example

ch8_1.png

• 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 a car backs up(preempt resources and rollback).
• Several cars may be back up if a deadlock occurs.
• Starvation is possible.

The general model

• Resource types $R_1, R_2, \dots, R_m$ : CPU resource, memory space, I/O devices
• Each resource $R_i$ has $W_i$ instances.
• Each process utilize a resource as follows:
  • Request
  • use
  • release
• A set of process is ==in a deadlock== state when every process in this set is waiting for an event that can only be caused by another process in this set

Deadlock Characterization

• ==Mutual execlusion== : only one process at a time can use a resource.
• ==Hold and wait== : a process holding at least one resources are waiting to acquire additional resources held by other processes.
• ==No preempt== : a resource can be released only voluntarily by a process holding it, after that process has completed its task.
• ==Circular wait== : there is a set of waiting processes such that $P_0$ is waiting a resource that is held by for $P_1$, $P_1$ is waiting for a resource that is held by $P_2$, … , $P_{n-1}$ is waiting for a resource that is held $P_n$, and $P_n$ is waiting for a resource that is held by $P_0$.

Resource-Allocation Graph

• A set of vertices V and a set of edgs E.

  • V is partitioned into two types:
    • $P = {P_1, P_2, \dots, P_n}$, the set consists of all the processes in the system.
    • $R = {R_1, R_2, \dots, R_m}$, the set consists of all resource types in the system.
  • E is also partitioned into two types:
    • request edge: directed edge $P_I \rightarrow R_j$
    • assignment edge: directed edge $R_j \rightarrow P_i$

• illustrate:

  • Process ch8_2_1
  • Resource Type with 4 instances ch8_2_2.png

    $R_j$

  • $P_i$ requests instance of $R_j$ ch8_2_3.png
  • $P_i$ is holding an instance of $R_j$ ch8_2_4.png

    ​

• Example

  • $begin \Rightarrow R_3 \rightarrow P_3 \Rightarrow {R_1,R_2, R_3} \rightarrow P_2 \Rightarrow {R_1,R_2} \rightarrow P_1 \Rightarrow end$

    ch8_3_1.png

  • $begin \Rightarrow R_1\rightarrow P_2, R_2 \rightarrow P_4, \Rightarrow {R_1,R_2} \rightarrow P_1, {R_1,R_2} \rightarrow P_3 \Rightarrow P_2 \Rightarrow end$

    ch8_3_2.png

  • $begin \Rightarrow R_1 \rightarrow P_2, R_2 \rightarrow P_4 \Rightarrow {R_1, R_2}\rightarrow P_1, {R_1, R_2}\rightarrow P_3 \Rightarrow end$

    ch8_3_3.png

Basic Facts

• If the graph contains no circle => no deadlock
• If the graph contains a circle =>
  • If only one instance per resource type, then deadlock.
  • If several instance per resource type, possible of deadlock.

Methods for Handling Deadlocks

• Ensure that the system will never enter a deadlock state.
• Allow the system enter a deadlock state and then recover.
• Ignore the problem and pretend that deadlock never occur in the system; used by most operating systems, include UNIX.

Deadlock Prevention

• Mutual Exclusion - not required for sharable resources; must hold for nonsharable resources.
• Hold and Wait - must guarantee that whenever a process requires 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.
  • Problem : low utilization; starvation possible.
• No Preempt -
  • If a process that is holding some resources requests some resources 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.
• Cicular Wait - impose a ==total ordering== of all resource types, and require that each process requests resources in an increasing order of enumeration.

Deadlock Prevention => low utilization of devices and reduce system throughput.

Deadlock Avoidance

• Given the complete sequence of requests and releases for each process, we can decide for each request whether or not the process should wait.
• For ever request, the system
  • considers the resources currently available, the resources currently allocated, and the future requests and releases of each process
  • decides whether the current requests can be satisfied or must wait to avoid a possible future deadlock.
• The simplest and most useful deadlock avoidance algorithm 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 (unsafe state).
• 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 for an available resource, the system must decide if immediate allocation leaves the system in a safe state.
• The system is in ==safe state== if there exists a ==safe sequence== of all processes. The sequence $<P_1, P_2, \dots, P_n>$ is safe if for each $P_i$, the resource that $P_i$ request can be satisfied by ==current available resources== ==+== ==resources== held by all the $P_j$, with $i < j$.
  • If resource that $P_i$ needs are not available immediately, 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$ is terminated, $P_{i+1}$ can obtain its needed resources, and so on.

Basic facts

• If a system is in safe state => no deadlocks.
• If a system is in unsafe state => possibility of deadlock.
• Avoidance => to ensure a system will never enter in an unsafe state.
• Two algorithms
  • Resource-allocation algorithm (Every resource type has a single instance)
  • Banker's algorithm (Every resource type has any number of instances).

Safe ,Unsafe and Deadlock state

ch8_4.png

Resource-Allocation Graph Algorithm

• ==Claim edge== : $P_i \rightarrow R_j$ indicated 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.
• ==Initially==, resources must be claimed in the system.

Resource-allocation graph for Deadlock avoidance

ch8_5_1.png ch8_5_2.png

Banker's Algorithm

• Multiple instances.
• Each process must a priori claim maximum use.
• When a process requests a resource, it may have to wait.
• When a process get all its resources, it must return them i==n a final amount of time==.

Data Structures of Banker's Algorithm

• ==Available== : Vector of length m. If available[j] = k, there are k instances of resource type $R_j$ available.

• ==Max== : $n \times m$ matrix. If Max[i, j] = k, then process $P_i$ may resuest at most k instances of resource type $R_j$.

• ==Allocation== : $n \times m$ matrix. If Allocation[i, j] = k, then $P_i$ is allocated k instances of $R_j$.

• ==Need== : $n \times 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 the vector of 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$== $\le$ $Work$

   If no such i exist, go to step 4.

3. $Work = Work + Allocation_i$

   $Finish[i] = true$

   go to step 2.

4. If Finish[i] == true ==for all i==

   ​ =>safa state;

   otherwise

   ​ => unsafe state.

   ch8_sa.png

Resource-Request Algorithms

For $P_i$

• Request = request vector for process $P_i$.

  If $Request_i[j] = k$ then process $P_i$ wants k instances of resource type $R_j$.

  1. If $Request_i \le Need_i$, go to step 2. Otherwise, error.

  2. If $Request_i \le Available$, go to step 3. Otherwise, $P_i$ wait.

  3. ==Pretend== to allocate resources to process $P_i$ by motified the state as follows:

     $Available = Available - Request_i$

     $Allocation_i = Allocation_i + Request_i$

     $Need_i = Need_i - Request_i$

     Safety Algorithm

     If safe => the resource are allocated to $P_i$

     If unsafe => $P_i$ must wait, and the old resource-allocation state is restored.

     ch8_rssa.png

• Example

  ch8_e1.png

Order: $P_1 \rightarrow P_3 \rightarrow P_4 \rightarrow P_0 \rightarrow P_2$

​

Deadlock Detection

• If a system don't implement either a deadlock-prevent algorithm or deadlock-avoidance algorithm, then a deadlock situation may occur.
  • ==Detection Algorithm==: An algorithm examines the state of system to determine whether a deadlock has occurred.
  • ==Recovery Algorithm==: An algorithm to recover from the deadlock.
• Two ==Detection Algorithms==
  • Wait-for graph (Every type has one single instance).
  • Detection-algorithm (similar to safety algorithm) (Every type has any number of instances)

Single instance of each resource type

• Generate a wait-for graph for its corresponding resource allocation graph.

  • Nodes are processes
  • $P_i \rightarrow P_j$ if $P_i$ is waiting for $P_j$.

• Periodically invokes an algorithm that searches a circle in the graph.

• An algorithm to detect a circle in the graph requires an order of $n^2$ operations, where n is the number of vertices in the graph.

  [图片上传失败...(image-a691a-1523593871019)]

Several Instances of a resource type

• Data structures:

  • ==Available== : A vector of length m indicates the number of available resource instances of each type.

  • ==Allocation== : An $n \times m$ matrix defines the number of each type currently allocated to each process.

    Every row of Allocation is a vector.

  • ==Request== : An $n \times m$ matrix indicates the currently request of each process. If Request[i, j] = k, then process $P_i$ is requesting k more instances of resource type R_j.

    Every row of Request is a vector.

Detection Algorithm

1. Let Work and Finish be the vectors of m and n. Respectively initialize:

   Work = Available

   For i = 1,2, …, n

   ​ if $Allocation_i \ne 0$ Finish[i] = false;

   ​ Otherwise Finish[i] = true;

2. Find an index i such that both:

   1. Finish[i] == false
   2. $Request_i \le Work$

   If no such i exist, 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 \le i \le n$, then the system is in deadlock state.

   Moreover, if Finish[i] == false, then $P_i$ is deadlocked.

   ch8_da.png

• Example

  OK

  ch8_e2.png

Deadlock

ch8_e3.png

• Usage

  • When, and how often to invoke detection algorithm.
  • It depends on:
    • How often a deadlock is likely to occur?
    • How many processes will need to be rolled back.

Deadlock Recovery

• Process Termination
• Resources Preemption

Process Termination

• Abort all processes
• Abort one process a time until the deadlock cycle is eliminated.
• In which order should we choose to abort?
  • Priority of the processes
  • How long the 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 iteractive or batch?

Resource Preemption

• Selecting a victim — minimize cost.
• Rollback — return to some safe state, restart process from that state.
• Starvation — the same process may always be picked as victim, include number of rollback in cost factor.

Summary

• Combine the three basic approaches (presentation, avoidance, detection), allowing the use of the optimal approach for the class of resources in the system.
• Partition resources into hierarchically ordered classes.
• Use most appropriate technique for handing deadlock within each class.
• An example:
  • Internal resources (Prevention through resource ordering)
  • Central memory (Prevention through preemption)
  • Job resources (Avoidance)
  • Swappable space (Preallocation)