deadlock

• Deadlocks


  A set of processes is deadlocked when every process in the set is waiting for a resource that is currently allocated to another process in the set (and which can only be released when that other waiting process makes progress)
• For the purposes of deadlock discussion, a system can be modeled as a collection of limited resources, which can be partitioned into different categories, to be allocated to a number of processes, each having different needs
• Resource categories


  • Memory
  • Printers
  • CPUs
  • Open files
  • Tape drives
  • CD-ROMS
• By definition, all the resources within a category are equivalent, and a request of this category can be equally satisfied by any one of the resources in that category
• If there is some difference between the resources within a category, then that category needs to be further divided into separate categories
• Some categories may have a single resource
• Normal operation of a process


  1. Request

  2. Use

  3. Release
• For all kernel-managed resources, the kernel keeps track of what resources are free and which are allocated, to which process they are allocated, and a queue of processes waiting for this resource to become available
• Application-managed resources can be controlled using mutexes or wait() and signal() calls, (i.e. binary or counting semaphores)
• Deadlock


  A set of processes is deadlocked when every process in the set is waiting for a resource that is currently allocated to another process in the set (and which can only be released when that other waiting process makes progress)
• Necessary conditions for deadlock

  • Mutual Exclusion
  • Hold and Wait
  • No preemption
  • Circular Wait
• Resource-Allocation Graph


  A graph with resource categories as square nodes, and processes as nodes, with request edges from processes to resources, and assignment edges from resources to processes
• If a resource-allocation graph contains no cycles, then the system is not deadlocked
• If a resource-allocation graph does contain cycles AND each resource category contains only a single instance, then a deadlock exists
• If a resource category contains more than one instance, then the presence of a cycle in the resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one
• Methods for handling deadlocks

  • Deadlock prevention or avoidance
  • Deadlock detection and recovery
  • Ignore the problem
• To avoid deadlocks, the system must have additional information about all processes, in particular the resources a process will or may request in the future
• Ways to prevent deadlocks

  • Prevent Mutual Exclusion
  • Prevent Hold and Wait
  • Allow Preemption
  • Prevent Circular Wait
• Safe state


  A state is safe if the system can allocate all resources requested by all processes (up to their stated maximums) without entering a deadlock state
• If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to deadlock
• Resource-Allocation Graph Algorithm


  1. Add claim edges from processes to resources they may request in the future

  2. When a process makes a request, convert the claim edge to a request edge

  3. When a resource is released, revert the assignment back to a claim edge

  4. Deny requests that would produce cycles in the resource-allocation graph
• Banker's Algorithm


  When a process starts up, it must state in advance the maximum allocation of resources it may request, up to the amount available on the system<|>When a request is made, the scheduler determines whether granting the request would leave the system in a safe state
• Deadlock avoidance


  The resulting resource-allocation graph would have a cycle in it, and so the request cannot be granted
• Figure 7.8 - An unsafe state in a resource allocation graph
• Banker's Algorithm


  A method for resource categories that contain more than one instance where the resource-allocation graph method does not work
• The Banker's Algorithm gets its name because it is a method that bankers could use to assure that when they lend out resources they will still be able to satisfy all their clients
• Banker's Algorithm


  1. When a process starts up, it must state in advance the maximum allocation of resources it may request, up to the amount available on the system

  2. When a request is made, the scheduler determines whether granting the request would leave the system in a safe state. If not, then the process must wait until the request can be granted safely
• Available[ m ]


  Indicates how many resources are currently available of each type
• Max[ n ][ m ]


  Indicates the maximum demand of each process of each resource
• Allocation[ n ][ m ]

  Indicates the number of each resource category allocated to each process
• Need[ n ][ m ]


  Indicates the remaining resources needed of each type for each process
• Need[ i ][ j ] = Max[ i ][ j ] - Allocation[ i ][ j ] for all i, j
• Safety Algorithm


  1. Let Work and Finish be vectors

  2. Initialize Work to Available, and Finish to 0 for all elements

  3. Find an i such that Finish[ i ] == 0, and Need[ i ] < Work

  4. Set Work = Work + Allocation[ i ], and set Finish[ i ] to ++s

  5. If Finish[ i ] > 0 for all i, or s >= n, then the state is a safe state
• Resource-Request Algorithm (The Bankers Algorithm)


  1. If Request[ i ] > Need[ i ] for any process i, raise an error condition

  2. If Request[ i ] > Available for any process i, then that process must wait for resources to become available

  3. Check to see if the request can be granted safely, by pretending it has been granted and then seeing if the resulting state is safe. If so, grant the request, and if not, then the process must wait until its request can be granted safely

  4. Available = Available - Request

  5. Allocation = Allocation + Request

  6. Need = Need - Request
• Consider the following situation: [table of resource allocation data]
• If process P1 requests 1 instance of A and 2 instances of C, can this be safely granted?
• If process P4 requests (3, 3, 0), or P0 requests (0, 2, 0), can these be safely granted? Why or why not?
• Deadlock Detection


  If deadlocks are not avoided, then another approach is to detect when they have occurred and recover somehow
• Wait-for graph


  A variation of the resource-allocation graph used when each resource category has a single instance, where resources and associated edges are eliminated and processes are connected by arcs indicating a process is waiting for a resource held by another process
• Cycles in the wait-for graph indicate deadlocks