14 Deadlocks – Prevention, Avoidance

Mary Anitha Rajam

17.1  Introduction

In a multi-programming environment, many processes compete for a finite number of resources. If the resources requested by a process are not available, the process waits. If the resources requested by this process are held by other waiting processes, the situation may lead to a deadlock. The different ways to handle deadlocks are deadlock prevention,  deadlock avoidance, deadlock detection and recovery. In this module, we learn different methods used for deadlock prevention and deadlock avoidance.

17.2  Deadlock Prevention 

To prevent deadlocks, it is necessary to ensure that at least one of the necessary conditions for deadlocks to occur in a system (Mutual exclusion, Hold and wait, No preemption, Circular wait) does not hold. That is mutual exclusion is not allowed in the system or hold and wait is not allowed or no preemption is not allowed or circular wait is not allowed. We now examine each of these four conditions

17.2.1  Mutual Exclusion 

Mutual exclusion can hold only for non-sharable resources. This condition is not required for sharable resources. Say, if there is a read-only file, the file can be shared by any number of processes at the same time. Therefore, mutual exclusion is not applicable for the read-only file.

If there are non-sharable resources, we cannot prevent deadlocks by denying mutual-exclusion condition. Suppose there is a printer that cannot be shared by many processes at the same time, mutual exclusion holds for the printer. That is, the printer cannot be shared.

17.2.2  Hold and Wait 

If the hold and wait condition must not happen in a system, it must be guaranteed that whenever a process requests a resource, it should not hold any other resource.

One way to ensure this is that it requires a process to request and all its resources be allocated before it begins its execution. For this to happen, the system calls requesting the resources should precede all other system calls in the process.

Consider the following example. Suppose a process wants to copy data from a tape drive to a file in the disk, sort the contents of the file in the disk and print the results to a printer. The resources needed for these operations are the tape drive, the disk and the printer. According to the method given in the previous paragraph to prevent hold and wait, the tape drive, the disk and the printer must be acquired by the process even before it starts executing other system calls. While copying data from the tape drive to the disk, the printer is not used. If the copying process takes an hour, another process waiting for the printer would have to wait, even though the printer resource is actually idle. Still, the process acquires the printer also beforehand. Similarly, while printing the file, only the printer and the disk are used; the tape drive is not used. Thus, this method results in low resource utilization.

The second way to ensure that hold and wait does not happen is to allow the process to request for resources only when the process has none. For the example in the scenario mentioned above, the process acquires the tape drive and the disk first, copies data from the tape drive to the disk file and then releases both the tape drive and the disk. After this, the process acquires the disk and the printer and prints the file. Thus, it can be seen that the disk is released and then acquired again. The process does not hold the disk while it is requesting for the printer.

Starvation is possible with these methods. A process that needs several popular resources may have to wait indefinitely because at least one of the resources that it needs is always allocated to some other process.

17.2.3  No Preemption 

No preemption means that resources that are already allocated should not be preempted. To ensure that this condition does not hold, two protocols can be used.

In the first protocol, if a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all the resources currently being held by that process are released. Released (preempted) resources are added to the list of free resources for which another process may be waiting. The process that released the resources will be restarted only when it can regain its old resources, as well as the new ones that it is requesting

In the second protocol, if a process requests resources, the system checks if the requested resources are available. If resources are available, the resources are allocated. If the requested resources are not available, check if the resources are allocated to some other process that is waiting to get more resources. If so, preempt the resources held by the waiting process and allocate to the requesting process. If nothing is possible, the process waits. This second protocol is often applied to resources whose state can be easily saved and restored later, such as CPU registers and memory space. It cannot generally be applied to such resources as printers and tape drives.

17.2.4 Circular Wait

To ensure that this circular wait condition does not hold, it is needed to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration.

Let R = {R1, R2, …, Rn} be the set of resource types. Each resource type is assigned a unique integer number. Formally, define a one-to-one function F: R → N, where N is the set of natural numbers. For example, if the set of resource types R includes tape drives, disk drives, and printers, then the function F might be defined as follows:

F(tape drive) = 1

F(disk drive)  = 5

F(printer)      = 12

With numbers assigned for each resource type, the following protocol can be used for preventing deadlocks. Each process requests for resources only in an increasing order of enumeration. That is, after requesting for the resource type Ri, a process can request for resource type Rj only if F(Rj) > F(Ri). For example, if a process needs a printer and a disk drive, the process has to request for the disk drive first and only then it can request for the printer. This is because, the number assigned to the disk drive is less than the number assigned to the printer. If a process requests several instances of the same resource type, a single request for all of them must be issued.

Also, when a process requests an instance of Rj, the process must release all instances of Ri, if F(Ri) ≥ F(Rj). That is, if a process is holding an instance of a resource type with a smaller number and needs a resource type with a higher number than the one the process is holding, the process should release the resource that it is already holding and then request for the new resource type.

If the above-said protocol is used, then the circular-wait condition cannot hold. This can be shown by assuming that a circular wait exists. Let P1, …, Pn be the processes involved in the circular wait. Process Pi is waiting for a resource held by process Pi+1 as shown in Figure 17.1. Let F(R1) be the number of the resource R1 assigned to process P1, F(R2) be the number of the resource assigned to process P2 and so on. Since there is a circular wait, F(R1) < F(R2) < … < F(R5) < F(R1). This means that F(R1) should be less than F(R1), which is not possible. Therefore, circular wait cannot happen if this protocol used.

Fig. 17.1 Circular wait of processes

17.3   Deadlock Avoidance

The deadlock avoidance algorithms require that the system knows beforehand the sequence of requests and releases for all the processes. The simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need. Whenever any process requests for one or more resources, the system decides if the request can be satisfied immediately or the process should wait, based on the prior knowledge about the needs of all the other processes. The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.

The resource-allocation state of a system is defined by the number of available and allocated resources, and the maximum demands of the processes. Any deadlock avoidance algorithm ensures that the system is in a safe state. We now learn what is meant by a safe state.

17.3.1  Safe State

When a process requests an available resource, the system must decide if immediate allocation of the resource leaves the system in a safe state. Even if the resource  is  available,  the  system  should  check  if  the  resource  can  be  allocated immediately. Only if the allocation of the resource will not lead to a deadlocked situation, the resource is allocated. The system is in the safe state if the system can allocate resources to each process in some order and still avoid a deadlock. That is, the system is in a safe state, if there exists a safe sequence of all processes.

A sequence of processes <P1, P2, …, Pn> is safe if for each Pi, the resources that Pi can still request can be satisfied by the currently available resources + the resources held by all the Pj, with j < i. If the needs of any process Pi are not immediately available, then Pi can wait until all Pj have finished. When Pj is finished, Pi can obtain the needed resources, execute, return the resources allocated to it and terminate. When Pi terminates, Pi+1 can obtain its needed resources, and so on.

Fig. 17.2 Safe, unsafe and deadlock states (Source: [1])

In a system, if there is no safe sequence, then the system is unsafe. If the system is in an unsafe state, there is a possibility of a deadlock. If the system is in a safe state, then there are no deadlocks in the system. Deadlock avoidance methods ensure that a system will never enter an unsafe state. Figure 17.2 shows a diagram depicting safe, unsafe and deadlock states. Mostly the system is in a safe state. When the system is unsafe, there is a possibility of deadlocks.

17.3.2  Safe, unsafe states – Example 

There are 12 magnetic tape drives in the system totally and there are three processes P0, P1, P2. The maximum needs of each process and the resources currently allocated to each process are given below: For example, the maximum need of process P0 is 10 tape drives and it is currently allocated 5 tape drives. In future, P0 will need 5 more tape drives.

Maximum Needs                     Current Needs

P0	10	5
P1	4	2
P2	9	2

We will now see if this system is currently in a safe state, with the current allocation of resources. Out of the 12 tape drives, 5 are currently allocated to process P0, 2 are allocated to process P1 and 2 are allocated to process P2. Therefore, 3 tape drives (12 – (5+2+2)) are free. The future needs of processes P0, P1 and P2 are 5, 2 and 7 respectively. With the 3 tape drives that are free, the future need of process P1 (which is only 2) can be satisfied. Therefore, process P1 can complete its work and free all the resources allocated to it. Thus, process P1 releases 4 tape drives. Therefore, there are now 5 free tape drives. With these 5 tape drives, the future need of process P0 can be satisfied. After completing its work, P0 releases all the 10 tape drives allocated to it. With these 10 tape drives, the need of P2 can be satisfied. Thus, the system is safe if resources are allocated in the sequence < P1, P0, P2>. < P1, P0, P2> is called a safe sequence.

A system may go from a safe state to an unsafe state. Suppose, after the current allocation, P2 requests for one more tape drive. If the request of P2 is satisfied because there are 3 free tape drives, the system goes into an unsafe state. The current allocation after P2 is given one more tape drive as shown below:

Maximum Needs                     Current Needs

P0	10	5
P1	4	2
P2	9	3

Now, the future needs of P0, P1 and P2 are 5, 2 and 6 respectively. There are 2 free tape drives now. With these 2 tape drives, the future need of P1 can be satisfied. When P1 completes it work, P1 releases 4 tape drives. But with 4 tape drives neither the future need of P0 (5 tape drives) nor the future need of P2 (6 tape drives) can be satisfied. The system now goes to an unsafe state. If the resources are allocated in the order P1, P0 and P2, then the system remains in a safe state.

5.3 Summary

This module discussed how deadlocks can be prevented. To prevent deadlocks, at least one of the conditions mutual exclusion, hold and wait, no preemption, circular wait should not exist. We discussed different protocols to prevent these conditions. Deadlocks can be avoided, with prior knowledge about all the requests of all the processes in the system.

References

1. Abraham Silberschatz,  Peter  B.  Galvin,  Greg  Gagne,  “Operating  System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.