Deadlock

Definition:

• a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process
• System model:
  • system consists of resources with resource types $R_1,R_2,...,R_m$
    • ex: cpu, ram. I/O, …
  • Each resource type of $R_i$ has $W_i$ instances
  • each process utilize a resource as follows:
    • request: to utilize resource
    • use
    • release
• Deadlock can arise if the following four conditions hold simultaneously:
  1. Mutual Exclusion: only one thread at a time can use a resource
  2. Hold and Wait: a thread holding at least one resource is waiting to acquire additional resources held by other threads
  3. No Preemption: a resource can be released only voluntarily by the thread holding it, after it has completed its task
  4. Circular Wait: $T_0$ waits for $T_1$, $T_1$ waits for $T_2$,…$T_n$ waits for $T_{n+1}$, $T_n$ waits for $T_0$
• Rsource Allocation Graph
  • A set of vertices $V$ and a set of edges $E$
    • Two types of vertices: $T$ and $R$
    • Two types of edges:
      • request edge – directed edge $T_i\to R_j$
      • assignment edge – directed edge $R_j\to T_i$
    • Cycle:
      • if one instance request only 1 resource type each → deadlock
        • 
      • if several instances per resource type → possible deadlock
        • 
      • ex: meaning resource A assigned to a task A, which request another resource B; and resource B is assigned to another task B, while task B request resource A
        • or it can be involve with more pairs
    • No cycle → No deadlock
• To handle deadlock:
  • ensure that the system will never enter a deadlock state:
    • Deadlock prevention
    • Deadlock avoidance
  • recover from deadlock state
    • deadlock detection & recovery
    • ignore deadlock

Deadlock prevention and avoidance:

• Deadlock prevention: Invalidate one of the four necessary conditions for deadlock
  1. Prevent “Mutual Exclusion”: allow processes to use same resource at same time → no deadlock. However, some resources (tape drive, printers, …) are inherently non-sharable
  2. Prevent “Hold and Wait”: when process request a new resource, it does not hold any other resource (make other processes wait for this) or give all resources it needed at once. However, leads to low resource utilization and starvation
  3. Prevent “No Preemption”: if a process have resources ABC, and requests resource D that is not immediately available, then all current resources ABC are released. Preempted resources, ABC, are added to the list of resources that the thread is waiting. Problem: Low resource utilization; starvation
  4. Prevent “Circular Wait”: when a Cycle of two or more processes exists, where each process is waiting for a resource held by the next process in the cycle. To prevent this, we can impose priority systme for the resources. Problem: Complex, Inflexible
• Deadlock avoidance:
  • Requires each thread declares the maximum number of resources of each type needed.
    • resource allocation state, based on:
      • the number of available & allocated resources
      • the maximum demands of the processes
    • Safe State: a state of processes and their requested resource that there exists a safe order/sequence, which the system could allocate needed resources to threads to be finished, i.e., no deadlock
    • Safe Sequence: an order of threads $<T_1,T_2,...,T_n>$ that any request from $T_i$ could be satisfied given the information:
      • Available resources
      • Allocated resources by other threads
    • Claim edge: $T_i\to R_j$ indicated that process $T_i$ may request resource $R_j$; represented by a dashed line
      • Claim edge → request edge → assignment edge → claim edge (might request again)
      • 
  • Resource allocation graph algorithm:
    • The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph
    • Graph cycle detection algorithms, worst-case $O(N^2)$
  • Banker’s algorithm:
    • let $n$ be nb of processes and $m$ be nb of resource types
    • Available (vector lengh $m$): if $avai[j]=k$ meaning there are $k$ instances of resource type $R_j$ available
    • Max ($n\times m$ matrix): $max[i,j]=k$ then process $T_i$ may request at most $k$ instances of resource type $R_j$
    • Allocation ($n\times m$ matrix): $allo[i,j]=k$ then process $T_i$ currently allocated $k$ instances of resource type $R_j$
    • Need ($n\times m$ matrix): $need[i,j]=k$ then process $T_i$ may need $k$ more instances of resource type $R_j$
    • $need[i,j]=max[i,j]-allo[i,j]$
    • Safe state check:
      1. Let work and finished be vectors of length $m$ and $n$
         • $Work=avail$
         • $finished[i]=false$ for all i
      2. Find a process $i$ such that both
         • $finished[i]=false$
         • and $need[i]\le work$
         • if no such i exist, go to stop 4
      3. $work=work+allo[i]$
         • $finished[i]=true$
      4. if $finished[i]==true$ for all $i$, then system is in safe state
    • Resource request check:
      • $Reques{t}_i=$ request vector for process $T_i$. If $Request[i][j]=k$ then process $T_i$ wants $k$ instances of resource type $R_j$
      1. If $Request[i]\le Need[i]$ go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim
      2. If $Request[i]\le Available$, go to step 3. Otherwise $T_i$ must wait, since resources are not available
      3. Pretend to allocate requested resources to $T_i$ as follows:
         • $Available=Available–Request[i];$
         • $Allocation[i]=Allocation[i]+Request[i];$
         • $Need[i]=Need[i]–Request[i];$
      4. Safe state check: Safe ⇒ Allocate to $T_i$, else rollback, $T_i$ must wait

Deadlock detection and recovery:

• Dection with Wait-for graph: resources with single instance
  • Simplify the resource allocation graph to build the wait-for graph: $T_i\to T_j$ if $T_i$ is waiting for $T_j$
  • worst-case $O(N^2)$
  • 
• Banker-like: resource with multiple instance
  • Let $\mathrm{n}=$ number of processes, and $m=$ number of resources types.
    • Available (Vector of length $m$ ): If available $[j]=k$, there are $k$ instances of resource type $R_j$ available
    • $\mathrm{Max}$ ( $n\times m$ matrix): If $\mathrm{Max}[i,j]=k$, then process $T_i$ may request at most $k$ instances of resource type $R_j$
    • Allocation ( $n\times m$ matrix): If Allocation $[i,j]=k$ then $T_i$ is currently allocated $k$ instances of $R_j$
  • Detection algorithm: Complexity: $\mathrm{O}\left(m\times {\mathbf{n}}^2\right)$
    1. Let Work and Finish be vectors of length $m$ and $n$, respectively. Initialize:
       • Work = Available
       • Finish $[i]=$ false for $i$ with Allocation $[i]\ne 0$, Finish $[i]=$ true otherwise
    2. Find a process $i$ such that both:
       • (a) Finish [i] = false
       • (b) Request[i] <= Work
       • If no such $i$ exists, go to step 4
    3. $Work=Work+Allocation[i]$
       • Finish $[i]=$ true, then go to step 2
    4. If $Finish[i]==false$, for some $\mathbf{i}$, then the system is in a deadlock state. Moreover, if Finish $[i]==$ false, then ${\mathbf{T}}_{\mathbf{i}}$ is deadlocked
  • If a detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph, it is not easy to tell which of the many deadlocked threads “caused” the deadlock.
• Recovery from Deadlock:
  • Process Termination
    • Abort all deadlocked threads
    • Abort one process at a time until the deadlock cycle is eliminated
    • In which order should we choose to abort?
      • Priority of the thread
      • How long has the thread computed, and to completion?
      • Resources that the thread has used
      • Resources that the thread needs to complete
      • How many threads will need to be terminated?
      • Is the thread interactive or batch?
  • Resource Preemption
    • Selecting a victim – minimize cost
    • Rollback – return to some safe state, restart the thread for that state
    • Starvation – same thread may always be picked as victim, include number of rollback in cost factor