Deadlock

• Deadlock


  A situation where two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes
• System Model


  • A process requests resources; if the resources are not available at that time, the process enters a waiting state
  • Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes
• Resource types


  • CPU cycles, files, I/O devices (such as printers and DVD drives)
• Resource type


  • Denoted by R1, R2, ..., Rm
  • Each resource type Ri has Wi instances
• Process utilization of resources

  1. Request

  2. Use

  3. Release
• Deadlocked state


  Every process in the set is waiting for an event that can be caused only by another process in the set
• Resource-Allocation Graph


  V is partitioned into two types: P = {P1, P2, …, Pn}, the set consisting of all the processes in the system

  R = {R1, R2, …, Rm}, the set consisting of all resource types in the system

  request edge – directed edge Pi → Rj

  assignment edge – directed edge Rj → Pi
• Resource-Allocation Graph


  • When process Pi requests an instance of resource type Rj, a request edge is inserted in the resource-allocation graph.

  When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge.

  When the process no longer needs access to the resource, it releases the resource. As a result, the assignment edge is deleted.
• Resource Allocation Graph With A Deadlock

  • Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by process P3. Process P3 is waiting for either process P1 or process P2 to release resource R2.
• Graph With A Cycle But No Deadlock

  • However, there is no deadlock. Observe that process P4 may release its instance of resource type R2. That resource can then be allocated to P3, breaking the cycle.
• Basic Facts


  • If graph contains no cycles, no deadlock

  If graph contains a cycle, if only one instance per resource type, then deadlock

  If graph contains a cycle, if several instances per resource type, possibility of deadlock
• Example on RAG


  Represents the resource allocation graph (RAG) in a table and capture all the allocations of resources.

  2. Using the current available resources, determine the order in which the processes get executed.

  3. Determine if deadlock exist in the system represented in the RAG. Give reason.

  4. What will be the value of the current available resources after the last process finish executing?
• From the RAG, there is a circular wait but no deadlock exists because processes p1, p2 and p3 executed successfully.
• Methods for Handling Deadlocks

  Ensure that the system will never enter a deadlock state:

  Deadlock prevention

  Deadlock avoidance

  Allow the system to enter a deadlock state and then detect and recover it.

  Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX
• Deadlock Avoidance and Prevention

  Deadlock prevention provides a set of methods to ensure that at least one of the necessary conditions cannot hold. These methods prevent deadlocks by constraining how requests for resources can be made.

  Deadlock avoidance requires that the operating system be given additional information in advance concerning which resources a process will request and use during its lifetime.
• Deadlock Prevention


  Mutual Exclusion: At least one resource must be non-sharable.

  Hold and Wait: Must guarantee that whenever a process requests a resource, it does not hold any other resources.

  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.

  Circular Wait: Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.
• For a deadlock to occur, each of the four necessary conditions must hold. By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of a deadlock.
• Each process can request resources only in an increasing order of enumeration. That is, a process can initially request any number of instances.
• Deadlock


  (e.g., read-only files)
• Necessary conditions for deadlock

  • Hold and Wait
  • No Preemption
  • Circular Wait
• Deadlock Prevention


  1. Guarantee that whenever a process requests a resource, it does not hold any other resources

  2. 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 allocated to it

  3. 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

  4. 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
• Safe State


  When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state
• If a system is in safe state, no deadlocks
• If a system is in unsafe state, possibility of deadlock
• Avoidance ensures that a system will never enter an unsafe state
• Safe, Unsafe, Deadlock State

  • P0 requires 10 tape drives, P1 may need up to 4 tape drives, P2 may need up to 9 tape drives
  • At time t0, P0 is holding 5 tape drives, P1 is holding 2 tape drives, P2 is holding 2 tape drives, and there are 3 free tape drives
• Resource-Allocation Graph


  • Claim edge indicates that process Pi may request resource Rj
  • Request edge when a process requests a resource
  • Assignment edge when the resource is allocated to the process
  • When a resource is released, assignment edge reconverts to a claim edge
  • Resources must be claimed a priori in the system
• 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
• A cycle indicates that the system is in an unsafe state
• Banker's Algorithm


  • 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
• Example of Banker's Algorithm


  • 5 processes P0 through P4, 3 resource types: A (10 instances), B (5 instances), and C (7 instances)
  • Snapshot at time T0 of Allocation, Max, and Available resources
• The system is in a safe state since the sequence <P1, P3, P4, P2, P0> satisfies safety criteria
• Example: P1 Request (1,0,2)


  • Check that Request Available
  • Executing safety algorithm shows that sequence <P1, P3, P4, P0, P2> satisfies safety requirement
  • Request for (3,3,0) by P4 cannot be granted
  • Request for (0,2,0) by P0 cannot be granted
• Deadlock Detection and Recovery

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