Chapter 7: Deadlocks (3721)

Chapter 7: Deadlocks (3721)

1. In a multiprogramming environment, several processes may compete for a finite number of resources.

2. if the resources are not available at that time, the process enters a waiting state.a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes

3. it remains the responsibility of programmers to ensure that they design deadlock-free programs

4. 7.1 System Model

   • resources (CPU cycles, files, and I/O devices) may be partitioned into several types (or classes), each consisting of some number of identical instances
     • If a system has two CPUs, then the resource type CPU has two instances.
     • Process request of resource type, the allocation of any instance of the type should satisfy the request.
     • synchronization tools, such as mutex locks and semaphores are also resources and often in deadlock
     • a lock is typically associated with protecting a specific data structure—that is, one lock may be used to protect access to a queue, another to protect access to a linked list
       • each lock is typically assigned its own resource class
     • a process may utilize a resource in only the following sequence:
       • Request
         • If the request cannot be granted immediately, the requesting process must wait until it can acquire the resource.
       • Use
         • The process can operate on the resource
       • Release
         • The process releases the resource
     • request and release of resources may be system calls
       • request() and release() device, open() and close() file, and allocate() and free() memory system calls.
       • request and release of semaphores can be accomplished through the wait() and signal()
       • acquire() and release() of a mutex lock
     • A set of processes is in a deadlocked state when every process in the set is waiting for an event that can be caused only by another process in the set.
     • Developers of multithreaded applications must remain aware of the possibility of deadlocks.
     • mainly concerned here are resource acquisition and release.

5. 7.2 Deadlock Characterization

   • DEADLOCK WITH MUTEX LOCKS (example)
   • 7.2.1 Necessary Conditions
     • deadlock situation can arise if the following four conditions hold simultaneously in a system:
     • 1. Mutual exclusion. At least one resource must be held in a nonsharable mode; that is, only one process at a time can use the resource.
     • 2. Hold and wait. A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
     • 3. No preemption. Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding i
     • 4. Circular wait. A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn−1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.
   • 7.2.2 Resource-Allocation Graph
     • Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph.
     • set of vertices V and a set of edges E. The set of vertices V is partitioned into two different types of nodes: P = {P1, P2, ..., Pn}, the set consisting of all the active processes in the system, and R = {R1, R2, ..., Rm}, the set consisting of all resource types in the system.
     • A directed edge from process Pi to resource type Rj is denoted by Pi → Rj; it signifies that process Pi has requested an instance of resource type Rj and is currently waiting for that resource.
       • called a request edge
     • A directed edge from resource type Rj to process Pi is denoted by Rj → Pi; it signifies that an instance of resource type Rj has been allocated to process P
       • called an assignment edge.
     • each process Pi as a circle and each resource type Rj as a rectangle.
       • resource type Rj may have more than one instance, we represent each such instance as a dot within the rectangle.
     • Note that a request edge points to only the rectangle Rj, whereas an assignment edge must also designate one of the dots in the rectangle.
     • 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.
     • 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. In addition, process P1 is waiting for process P2 to release resource R1.

6. 7.3 Methods for Handling Deadlocks

   • deal with the deadlock problem in one of three ways:
     • We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocked state.
     • We can allow the system to enter a deadlocked state, detect it, and recover.
     • We can ignore the problem altogether and pretend that deadlocks never occur in the system.
       • The third solution is the one used by most operating systems
       • It is then up to the application developer to write programs that handle deadlocks.
       • Ignoring the possibility of deadlocks is cheaper than the other approaches.
     • none of the basic approaches alone is appropriate for the entire spectrum of resource-allocation problems in operating systems.
   • Deadlock prevention provides a set of methods to ensure that at least one of the necessary conditions (Section 7.2.1) cannot hold.
   • 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.
     • operating system can decide for each request whether or not the process should wait
   • The system can provide an algorithm that examines the state of the system to determine whether a deadlock has occurred and an algorithm to recover from the deadlock

7. 7.4 Deadlock Prevention

   • at least one of these conditions cannot hold, we can prevent the occurrence of a deadlock
   • 7.4.1 Mutual Exclusion
     • Sharable resources, in contrast, do not require mutually exclusive access and thus cannot be involved in a deadlock.
   • 7.4.2 Hold and Wait
     • 1. whenever a process requests a resource, it does not hold any other resources.
     • 2. One protocol that we can use requires each process to request and be allocated all its resources before it begins execution.
       • system calls requesting resources for a process precede all other system calls
     • Both these protocols have two main disadvantages.
       • First, resource utilization may be low, since resources may be allocated but unused for a long period
       • Second, starvation is possible. A process that needs several popular resources may have to wait indefinitely
   • 7.4.3 No Preemption
     • If a process is holding some resources and requests another resource that cannot be immediately allocated to it (that is, the process must wait), then all resources the process is currently holding are preempted
   • 7.4.4 Circular Wait
     • impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration.
     • We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering.
     • Keep in mind that developing an ordering, or hierarchy, does not in itself prevent deadlock.
   • Possible side effects of preventing deadlocks by this method, however, are low device utilization and reduced system throughput.

8. 7.5 Deadlock Avoidance

   • . The simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.
   • A deadlockavoidance algorithm dynamically examines the resource-allocation state to ensure that a circular-wait condition can never exist.
   • The resource-allocation state is defined by the number of available and allocated resources and the maximum demands of the processes.
   • two deadlock-avoidance algorithms.
     • 7.5.1 Safe State
       • A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock
       • More formally a system is in a safe state only if there exists a safe sequence
     • 7.5.2 Resource-Allocation-Graph Algorithm
       • In addition to the request and assignment edges already described, we introduce a new type of edge, called aclaim edge.
       • Aclaim edge Pi → Rj indicates that process Pi may request resource Rj at some time in the future. This edge resembles a request edge in direction but is represented in the graph by a dashed line. When process Pi requests resource Rj, the claim edge Pi → Rj is converted to a request edge. Similarly, when a resource Rj is released by Pi, the assignment edge Rj → Pi is reconverted to a claim edge Pi → Rj.
       • before process Pi starts executing, all its claim edges must already appear in the resource-allocation graph
       • suppose that process Pi requests resource Rj. The request can be granted only if converting the request edge Pi → Rj to an assignment edge Rj → Pi does not result in the formation of a cycle in the resource-allocation graph.
       • using a cycle-detection algorithm. An algorithm for detecting a cycle in this graph requires an order of n2 operations, where n is the number of processes in the system
       • If a cycle is found the Process will have to wait
   • 7.5.3 Banker’s Algorithm
     • The resource-allocation-graph algorithm is not applicable to a resource allocation system with multiple instances of each resource type
     • the algorithm could be used in a banking system to ensure that the bank never allocated its available cash in such a way that it could no longer satisfy the needs of all its customers.
     • Several data structures must be maintained to implement the banker’s algorithm.
       • data structures encode the state of the resource-allocation system.
         • n is the number of processes in the system and m is the number of resource types:
     • We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocationi and Needi. The vector Allocationi specifies the resources currently allocated to process Pi; the vector Needi specifies the additional resources that process Pi may still request to complete its task.
     • 7.5.3.1 Safety Algorithm
       • the algorithm for finding out whether or not a system is in a safe state
     • 7.5.3.2 Resource-Request Algorithm
       • the algorithm for determining whether requests can be safely granted.
         • Let Requesti be the request vector for process Pi. If Requesti [j] == k, then process Pi wants k instances of resource type Rj. When a request for resources is made by process Pi, the following actions are taken:

9. 7.6 Deadlock Detection

   • If a system does not employ either a deadlock-prevention or a deadlockavoidance algorithm, then a deadlock situation may occur.
   • An algorithm that examines the state of the system to determine whether a deadlock has occurred
   • An algorithm to recover from the deadlock
   • 7.6.1 Single Instance of Each Resource Type
     • If all resources have only a single instance, then we can define a deadlockdetection algorithm that uses a variant of the resource-allocation graph, called a wait-for graph
     • We obtain this graph from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges.
     • an edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a resource that Pi needs
     • As before, a deadlock exists in the system if and only if the wait-for graph contains a cycle.
     • the system needs to maintain the waitfor graph and periodically invoke an algorithm that searches for a cycle in the graph.
     • An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.
   • 7.6.2 Several Instances of a Resource Type
     • The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type
     • The algorithm employs several time-varying data structures that are similar to those used in the banker’s algorithm
     • This algorithm requires an order of m × n2 operations to detect whether the system is in a deadlocked state.
     • To illustrate this algorithm, we consider a system with five processes P0 through P4 and three resource types A, B, and C. Resource type A has seven instances, resource type B has two instances, and resource type C has six instances. Suppose that, at time T0, we have the following resource-allocation state:
   • 7.6.3 Detection-Algorithm Usage
     • When should we invoke the detection algorithm?
       • 1. How often is a deadlock likely to occur?
       • 2. How many processes will be affected by deadlock when it happens?
     • In the extreme, then, we can invoke the deadlockdetection algorithm every time a request for allocation cannot be granted immediately. (very costly)
     • alternative is simply to invoke the algorithm at defined intervals, such as when the CPU is idle

10. 7.7 Recovery from Deadlock

    • One possibility is to inform the operator that a deadlock has occurred and to let the operator deal with the deadlock manually. Another possibility is to let the system recover from the deadlock automatically
    • two options for breaking a deadlock. One is simply to abort one or more processes to break the circular wait. The other is to preempt some resources from one or more of the deadlocked processes.
    • 7.7.1 Process Termination
      • Two methods
        • • Abort all deadlocked processes. -> Lose all work done
          • the results of these partial computations must be discarded
        • • Abort one process at a time until the deadlock cycle is eliminated.
          • after each process is aborted, a deadlock-detection algorithm must be invoked to determine whether any processes are still deadlocked.
          • determination is a policy decision, similar to CPU-scheduling decisions
      • Many factors may affect which process is chosen, including:
        • 1. What the priority of the process is 2. How long the process has computed and how much longer the process will compute before completing its designated task 3. How many and what types of resources the process has used (for example, whether the resources are simple to preempt) 4. How many more resources the process needs in order to complete 5. How many processes will need to be terminated 6. Whether the process is interactive or batch
    • 7.7.2 Resource Preemption
      • we successively preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken.
      • If preemption is required to deal with deadlocks, then three issues need to be addressed:
        • 1. Selecting a victim
          • Which resources and which processes are to be preempted?
        • 2. Rollback.
          • We must roll back the process to some safe state and restart it from that state.
          • simplest solution is a total rollback: abort the process and then restart it
        • 3. Starvation
          • we must ensure that a process can be picked as a victim only a (small) finite number of times. (not over and over)

Imágenes y archivos del mapa