• preemptable resource
• nonpreemptable resource

deadlock

• conditions: (known as the Coffman conditions)
  • Mutual exclusion
  • Hold and wait or resource holding
  • No preemption:
  • Circular wait: There is a set of waiting processes $P=\{p_1,p_2,\dots ,p_n\}$, s.t. $p_i$ is waiting for a resource held by $p_{(i+1)\mathrm{mod}n}$.
• handling:
  • ignoring
    • ostrich algorithm
  • detection and recovery
    • detection
      • (system) resource-allocation graph
        • $T=\{T_1,T_2,\dots ,T_n\}$: set of active threads
        • $R=\{R_1,R_2,\dots ,R_m\}$: set of resource types
        • request edge $T_i\to R_j$: thread $T_i$ has requested an instance of resource type $R_j$
        • assignment edge $R_j\to T_i$: an instance of resource type $R_j$ has been allocated to thread $T_i$
      • Multiple Resources
        • current allocation matrix
          • $(E_1,E_2,\dots ,E_m)$: total number of each resource type
          • $C[i,j]=$ number of instances of resource type $R_j$ currently allocated to thread $T_i$
        • request matrix
          • $(A_1,A_2,\dots ,A_m)$: number of available instances of each resource type
          • $R[i,j]=$ number of instances of resource type $R_j$ requested by thread $T_i$
        • invariant: ${\sum }_{i=1}^{n}C[i,j]+A_j=E_j$
    • recovery
      • preemption
      • rollback
        • checkpoints
      • procces killing
  • avoidance
    • resource trajectories
    • safe states
    • Banker’s algorithm
  • prevention