Deadlocks

Dr. Noman Islam

Deadlock condition

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. If another process requests that resource, the requesting process must be delayed until the resource has been released.

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 it, after that process has completed its task.

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.

Handling deadlock

• 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, including Linux and Windows. It is then up to the application developer to write programs that handle deadlocks.

• Deadlock prevention provides a set of methods to ensure that at least one of the necessary conditions 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. With this additional knowledge, the operating system can decide for each request whether or not the process should wait.
• To decide whether the current request can be satisfied or must be delayed, the system must consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.

• If a system does not employ either a deadlock-prevention or a dead lock avoidance algorithm, then a deadlock situation may arise. In this environment, 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

Deadlock prevention - Mutual Exclusion

• Sharable resources, in contrast, do not require mutually exclusive access and thus cannot be involved in a deadlock.
• Read-only files are a good example of a sharable resource.
• In general, however, we cannot prevent deadlocks by denying the mutual-exclusion condition, because some resources are intrinsically nonsharable. For example, a mutex lock cannot be simultaneously shared by several processes.

Hold and wait

• We can implement this provision by requiring that system calls requesting resources for a process precede all other system calls.
• An alternative protocol allows a process to request resources only when it has none.
• A process may request some resources and use them. Before it can request any additional resources, it must release all the resources that it is currently allocated.

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.
• Alternatively, if a process requests some resources, we first check whether they are available.
• If they are, we allocate them. If they are not, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process

Circular wait

• One way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration.
• Each process can request resources only in an increasing order of enumeration.
• That is, a process can initially request any number of instances of a resource type —say, R_i.
• After that, the process can request instances of resource type R_j if and only if F(R_j) > F(R_i).

Deadlock avoidance

• Possible side effects of preventing deadlocks by this method, however, are low device utilization and reduced system throughput.
• With the knowledge of the complete sequence of requests and releases for each process, the system can decide for each request whether or not the process should wait in order to avoid a possible future deadlock
• Each request requires that in making this decision the system consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.

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
• Consider the example below
• The sequence <P1, P0, P2> satisfies the safety condition.

Total resources = 12

• A system can go from a safe state to an unsafe state. Suppose that, at time t1, process P2 requests and is allocated one more tape drive.
• The system is no longer in a safe state.
• Initially, the system is in a safe state.
• Whenever a process requests a resource that is currently available, the system must decide whether the resource can be allocated immediately or whether the process must wait.
• The request is granted only if the allocation leaves the system in a safe state.

Resource Allocation Graph Algorithm

• Now 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

Banker’s algorithm

• The resource-allocation-graph algorithm is not applicable to a resource allocation system with multiple instances of each resource type
• The name was chosen because 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

Data structure required

• Available. A vector of length m indicates the number of available resources of each type. If Available[j] equals k, then k instances of resource type Rj are available.
• Max. An n × m matrix defines the maximum demand of each process. If Max[i][j] equals k, then process Pi may request at most k instances of resource type Rj .
• Allocation. An n × m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i][j] equals k, then process Pi is currently allocated k instances of resource type Rj .
• Need. An n × m matrix indicates the remaining resource need of each process. If Need[i][j] equals k, then process Pi may need k more instances of resource type Rj to complete its task. Note that Need[i][j] equalsMax[i][j] − Allocation[i][j].

Safety algorithm

Resource Request algorithm

• The content of the matrix Need is defined to be Max − Allocation and is as follows:

• We claim that the system is currently in a safe state. Indeed, the sequence <P1, P3, P4, P2, P0> satisfies the safety criteria
• Suppose now that process P1 requests one additional instance of resource type A and two instances of resource type C, so Request1 = (1,0,2).
• To decide whether this request can be immediately granted, we first check that Request1 ≤ Available—that is, that (1,0,2) ≤ (3,3,2), which is true.
• We then pretend that this request has been fulfilled, and we arrive at the following new state:

• We must determine whether this new system state is safe.
• To do so, we execute our safety algorithm and find that the sequence <P1, P3, P4, P0, P2> satisfies the safety requirement. Hence, we can immediately grant the request of process P1
• You should be able to see, however, that when the system is in this state, a request for (3,3,0) by P4 cannot be granted, since the resources are not available.
• Furthermore, a request for (0,2,0) by P0 cannot be granted, even though the resources are available, since the resulting state is unsafe.

Deadlock detection

• In this environment, the system may provide:
• An algorithm that examines the state of the system to determine whether a deadlock has occurred
• An algorithm to recover from the deadlock

Wait-for graph

Multiple instances of resource

• The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type
• Available. A vector of length m indicates the number of available resources of each type.
• Allocation. An n × m matrix defines the number of resources of each type currently allocated to each process.
• Request. An n × m matrix indicates the current request of each process. If Request[i][j] equals k, then process Pi is requesting k more instances of resource type Rj .

Detection algorithm usage

• How often is a deadlock likely to occur?
• How many processes will be affected by deadlock when it happens?
• Invoking the deadlock-detection algorithm for every resource request will incur considerable overhead in computation time.
• A less expensive alternative is simply to invoke the algorithm at defined intervals
• If the detection algorithm is invoked at arbitrary points in time, the resource graph may contain many cycles.
• In this case, we generally cannot tell which of the many deadlocked processes “caused” the deadlock.

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
• One solution 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

Process termination

• Abort all deadlocked processes
• Abort one process at a time until the deadlock cycle is eliminated
• 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

Resource preemption

• Selecting a victim
• Rollback
• Starvation