13 Deadlocks – Introduction

Mary Anitha Rajam

 

16.1  Introduction

 

Any system has many processes and a number of different resources. In such a system, processes request for resources, use them and then release them. If a process requests for resources and the resources are not available, the process waits. If the requested resources are held by other waiting processes, the requesting process continues to wait forever. This situation is called a deadlock.

 

This module explains what is meant by a deadlock, the methods for handling deadlocks, what a resource-allocation graph is and how a resource-allocation graph can be used to handle deadlocks.

 

16.2  ridge Crossing Example 

Fig. 16.1 Bridge crossing – deadlock

 

Consider vehicles crossing a bridge as shown in Figure 16.1. Vehicles can cross the bridge only in one direction at a particular time. If two vehicles that are moving in opposite directions try to cross the bridge at the same time, both get into a deadlocked situation. The deadlock can be resolved only if one vehicle backs up. To back up one vehicle, several other vehicles may also have to be backed up if a deadlock occurs.

 

16.3 Deadlock Problem in a System

 

A situation similar to that of crossing a bridge can happen in a system as well. Suppose there is a set of blocked processes, each holding a resource and waiting to acquire a resource held by another process in the set. All the processes will be waiting for each other to release resources. Then, the system will be in a deadlocked state.

 

Consider the following example: A system has 2 tape drives. There are two processes P1 and P2. Each process holds one tape drive and needs another one. Since there are only two tape drives in the system, each of the two processes is waiting for the tape drive held by the other waiting process. Now, both the processes are unable to proceed and are deadlocked.

 

Let us see another example. Though this example was explained in an earlier module, it is given here for better clarity. There are two semaphores, A and B, initialized to 1. Since the initial value is 1, each of the semaphores A and B is guarding resources that can be accessed only by one process at a time. Let P0 and P1 be two processes that are executing the following sequence of statements respectively.

    P0                                 P1

 

wait (A);                       wait(B);

wait (B);                       wait(A);

 

Suppose P0 executes wait(A) first. This operation decrements the value of semaphore A from 1 to 0. Suppose there is a context switch and P1 executes wait(B). This will decrement the value of semaphore B from 1 to 0. Next, P1 continues to execute wait(A). Since the value of semaphore A is 0, process P1 waits. There is a context switch now and process P0 executes wait(B). Since the value of semaphore B is 0, process P0 waits. Here, we see that process P0 is waiting for semaphore B held by process P1 and process P1 is waiting for semaphore A held by process P0. Thus, both the processes are in a deadlocked state.

 

16.4 System Model

 

Any system has a finite number of resources, distributed among a number of competing processes. The resources are categorized into several resource types R1, R2, …, Rm . The resource types in a system may be CPU cycles, memory space, I/O devices and so on. Each resource type Ri has Wi instances. For example, if there are 5 printers, then there are 5 instances of the resource type printer.

 

Each process utilizes resources as follows: Each process requests for resources, uses the resources and releases the resources after using the resources. A process may request as many resources as it requires to carry out its designated task. The number of resources requested by the process cannot exceed the total number of resources available in the system. That is, if there are five printers, the process cannot request for six.

 

There are system calls available for the request and release of resources like the request and release device, open and close file, allocate and free memory. Request and release of resources can be accomplished through the wait and the signal operations on semaphores.

 

A table is maintained in the system that records whether each resource is free or allocated. If a resource is allocated, information is maintained as to which process the resource is allocated. If a process requests a resource currently allocated to another process, the process is added to a queue of processes waiting for that resource.

 

16.5 Deadlock Characterization

 

In a deadlocked system, processes never finish executing and system resources are tied up, preventing other jobs from starting. We shall now understand the features that characterize deadlocks.

 

16.5.1 Necessary conditions

 

Deadlocks can arise if the following four conditions hold simultaneously in a system:

  • Mutual exclusion: If there is a non-shareable resource, only one process can use a resource at a time.
  • Hold and  wait:  A process holding at least one resource is waiting to acquire additional resources held by other waiting processes.
  • No preemption: A resource can be released only voluntarily by the process that is holding it after the process has completed its task. It is not possible to preempt a resource forcibly from a process.
  • Circular wait: If there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

 

16.5.2 Resource-Allocation Graph

 

Any system can be described by means of a directed graph called a system resource-allocation graph. The graph consists of a set of vertices V and a set of edges E. The set of vertices V is partitioned into two types, P = {P1, P2, …, Pn}, the set consisting of all the processes in the system and R = {R1, R2, …, Rm}, the set consisting of all the resource types in the system. A directed edge from Pi to Rj is denoted as Pi ® Rj and is called a request edge. A directed edge from Rj to Pi is denoted as Rj ® Pi and is called an assignment edge.

 

Pictorially, a process is denoted using a circle as shown below:

A resource type is denoted using a square. The instances of a resource type are shown using dots inside the square. A resource type with 4 instances is denoted pictorially as shown below:

When Pi requests an instance of Rj, it is denoted as an edge from Pi to Rj in the resource-allocation graph.

When Pi is holding an instance of Rj, it is shown as an edge from a dot in Rj to Pi in the resource-allocation graph.

Figure 16.2 shows an example of a resource-allocation graph. P1, P2 and P3 are the three processes in the system. There are four resource types, R1, R2, R3 and R4. There is one instance of R1, two instances of R2, one instance of R3 and three instances of R4. P1 is holding one instance of R2 and is requesting for one instance of R1. P2 is holding one instance of R1 and one instance of R2 and is requesting for one instance of R3. P3 is holding one instance of R3.

Fig. 16.2 Resource-allocation graph (Source: [1])

 

Deadlocks can be detected from a resource-allocation graph. If the resource-allocation graph contains no cycles, no process is deadlocked. If the resource-allocation graph contains cycles, deadlocks may exist. If there is only one instance of each resource type and there is a cycle in the graph, there is a deadlock in the system.

 

16.5.3  Resource-Allocation Graph With a Deadlock

 

Figure 16.3 shows a resource-allocation graph with a deadlock. In this figure, process P1 is waiting for an instance of resource type R1. There is only one instance of R1 which is held by process P2. P2 is waiting for an instance of resource R3. There is only one instance of R3, which is held by process P3. Process P3 is waiting for an instance of R2. There are two instances of R2, each of which is held by P1  and P2 respectively. Thus, P1, P2 and P3 are waiting for resources held by other waiting processes.

 

It is seen that there is a cycle P1 ® R1 ® P2 ® R3 ® P3 ® R2 ® P1. All the processes that are part of the cycle are waiting and there is no free instance  of resource. Therefore, all the processes in the cycle are deadlocked. None of the processes is able to proceed further.

Fig. 16.3 Resource-allocation graph with a deadlock (Source: [1])

 

16.5.4  Resource Allocation Graph With A Cycle But No Deadlock

Fig. 16.4 Resource allocation graph with a cycle but no deadlock (Source: [1])

 

It is always not necessary to have a deadlock if there is a cycle. We now look at an example scenario where there is a cycle in the resource-allocation graph, but there is no deadlock. Figure 16.4 shows a resource-allocation graph with a cycle P1 ® R1 ® P3 ® R2 ® P1. But, in this scenario, an instance of R1 is held by process P2, which is not a waiting process. Once P2 finishes using the resource, it will release the resource. R1 will now be available for process P3. Similarly, an instance of R2 is held by process P4 and P4 is not waiting for any other resource. Therefore, P4 releases the resource R2 after using the resource. Now, R2 is available for process P1.

 

Thus, from the examples given above, it is seen that

 

– If a resource-allocation graph contains no cycles Þ no deadlock.

– If there are several instances per resource type and there is a cycle in the resource-allocation graph, there is a possibility of deadlock.

– If a resource-allocation graph contains a cycle Þ  if there is only one instance per resource type, then there is deadlock.

 

16.6 Methods for Handling Deadlocks 

 

We can deal with the deadlock problem in one of three ways:

 

1. We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state.

2. We can allow the system to enter a deadlock state, detect it, and recover.

3. We can ignore the problem altogether, and pretend that deadlocks never occur in the system.

 

To ensure that deadlocks never occur in a system, deadlock prevention or deadlock avoidance scheme can be used. Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions (Mutual exclusion, Hold and wait, No preemption, Circular wait) does not hold. These methods prevent deadlocks by constraining how requests for resources can be made.

 

Deadlock avoidance requires that the operating system should be given additional information about which resources a process will request and use during its life time. With this information, whenever a request for a resource comes from a process, the system can decide whether the request can be granted immediately or not. The system simulates and finds out if the system will go to a deadlocked state if the request is granted. Based on that, the system decides if the request can be granted or not.

 

If there is no mechanism employed in the system for deadlock prevention and avoidance, then deadlocks can occur. In this case, the system must employ algorithms for deadlock detection and recovery.

 

If the system does not employ algorithms even for deadlock detection and recovery, that is, if the problem is ignored altogether, then the system may be in a deadlock state and may not recognize what has happened. In this case, the system performance deteriorates and the system should be restarted manually. Although this method does not seem to be a viable approach, it is used in some operating systems.

 

16.7  Summary

 

Deadlocks may occur in a system that has shared resources. A system in which processes use resources can be depicted using a resource-allocation graph. A cycle in a resource-allocation graph may or may not indicate a deadlock.

 

References

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