OS2: Deadlocks-Unit 1: Deadlock Characterization

In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available, at that time, the process enters a wait state. Waiting processes may never again change state, because the resources they have requested are held by other waiting processes. This situation is called deadlock. We have already mentioned this briefly in module 4 in connection with semaphores.In this module, you will be taken through methods that an operating system can use to prevent or deal with deadlocksObjectivesAt the end of this unit, you should be able to:Define deadlock State the necessary conditions for deadlock to occur Describe Resource-Allocation graph Explain how it can be used to describe deadlocks Describe some of the methods for handling deadlocks.


System Model

A system consists of a finite number of resources to be distributed among a number of competing processes. The resource are partitioned into several types, each of which consists of some number of identical instances. Memory space, CPU cycles, files, and I/O devices (such as printers and tape drives) are examples of resource types. If a system has two CPUs, then the resource type CPU has two instances. Similarly, the resource type printer may have five instances.

A process must request a resource before using it, and must release the resource after using it. A process may request as many resources as it requires to carry out its designated task. Obviously, the number of resources requested may not exceed the total number of resources available in the system. i.e. a process cannot request three printers if the system has only two.

Under normal mode of operation, a process may utilize a resource in only the following sequence.

  1. Request: If the request cannot be granted immediately (for example, if the resource is been used by another process), then the requesting process must wait until it can acquire the resource.
  2. Use: The process can operate on the resource (for example, if the resource is a printer, the process can print on the printer)
  3. Release: The process releases the resource.

Request and release of resources can be accomplished through the wait and signal operations on semaphores. Therefore, for each use, the operating system checks to make sure that the using process has requested and been allocated the resource. A system table records whether each resource is free or allocated, and, if a resource is allocated, to which process. If a process requests a resource that is currently allocated to another process, it can be added to a queue of processes waiting for this resource.

A set of processes is in a deadlock state when every process in the set is waiting for an event that can only be caused by another process in the set.

To illustrate deadlock state, consider a system with three tape drives. Suppose each of three processes holds one of these tape drives. If each process now requests another tape drive, the three processes will be in deadlock. Each is waiting for the event “tape drive is released” which can be caused only by one of the other waiting processes. This example illustrates a deadlock involving the same resource type.

Deadlocks may also involve different resource type. E.g. consider a system with one printer and one tape drive. Suppose that process P1 is holding the tape drive and process

P2 is holding the printer. If P1 requests the printer and P2 requests the tape drive, a deadlock occurs.

A deadlock is also called a deadly embrace.


Deadlocks occur most commonly in multitasking and client/server environments.

Therefore, a programmer who is developing multithreaded applications must pay particular attention to this problem: Multithreaded programs are good candidates for deadlock because multiple threads can compete for shared resources.


Deadlock Characterization

In a deadlock, processes never finish executing and system resources are tied up, preventing other jobs from starting. Before we discuss the various methods for dealing with the deadlock problem, we shall describe to you features that characterized deadlocks.

3.2.1 Necessary Conditions

A deadlock situation can arise if the following conditions hold simultaneously in a system:

  1. Mutual exclusion condition: At least one resource must be held in a non-sharable mode; i.e. 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 condition: 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 condition: Resources cannot be preempted; i.e. only a process holding a resource may voluntarily release the resource after completing its task.
  4. Circular-wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds. i.e. A set (P0, P1, …, Pn) of waiting processes must exist 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.

Deadlock only occurs in systems where all these four conditions hold. You should note that the hold-and-wait condition leads to the circular-wait condition implies. So, the four conditions are not completely independent.

3.2.2 Resource-Allocation (R-A) Graph

Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph. This graph consists of a set of vertices V and a set of edges E.

The set 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 requested an instance of resource type Rj and is currently waiting for that resource. 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 Pi. A directed edge Pi → Rj is called a request edge; a directed edge Rj → Pi is called an assignment edge.

Pictorially, each process Pi is represented as a circle, and each resource type Rj as a square. Since resource type Rj may have more than one instance, we represent each such instance as a dot within the square. You should note that a request edge points only to the square whereas an assignment edge must also designate one of the dots in the square.

When a process Pi request 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, and as a result the assignment edge is deleted.


resource allocation graph


Figure 3.1: Resource-Allocation Graph (RAG)

The resource-allocation graph shown in figure 3.1 depicts the following situation:

The sets P, R and E

  • P = (P1, P2,, P3)
  • R = (R1, R2,, R3, R4)
  • E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}

Resource instances:

  • One instance of resource type R1
  • Two instances of resource type R2
  • One instance of resource type R3
  • Two instances of resource type R4

Process states:

Process is P1 is holding an instance of resource type R2, and is waiting for an instance of resource type R1.

Process is P2 is holding an instance of resource type R1 and R2, and is waiting for an instance of resource type R3.

Process is P3 is holding an instance of resource type R3.

Given the definition of a RAG, it can be shown that, if the graph contains no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist.

If each resource type has exactly one instance, then a cycle implies that deadlock has occurred. If the cycle involves only a set resource types, each of which has only a single instance, then a deadlock has occurred. Each process involved the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence of deadlock.

If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has occurred. In this case, a cycle in the graph is both a necessary but not a sufficient condition for the existence of deadlock.

To illustrate this concept, let us return to the R-A graph depicted in figure 3.1 above.

Suppose process P3 requests an instance of resource type R2. Since no resource instance is currently available, a request edge P3 → R2 is added to the graph (see figure

3.2). At this point, two minimal cycles exist in the system:

P 1 → R 1 → P2 → R 3 → P3 → R 2 → P1

P2 → R 3 → P3 → R 2 → P2

resource allocation graph with deadlock

Figure 3.2: Resource-Allocation Graph with a Deadlock

Processes P1, P2, and P3 are deadlocked. Process P2 is waiting for resource R3, which is held by process P3. Process P3, on the other hand, is waiting for either process P1 or P2 to release resource R2. In addition, process P1 is waiting for P2 to release resource R1.

Now consider the R-A graph in figure 3.3.

resource allocation graph with a cycle but no deadlock

Figure 3.2: Resource-Allocation Graph with a cycle but no Deadlock

In this example, you also have a cycle:

P 1 → R 1 → P3 → R 2 → P1

However, there is no deadlock. Observe that process P4 may release its instance of resource type R4 and that resource could then be allocated to P3, breaking the cycle

Conclusively, if a resource-allocation graph does not have a cycle, then the system is not in a deadlock state. On the other hand, if there is a cycle, then the system may or may not be in a deadlock state. This observation is important when you deal with deadlock problem.


Methods for Handling Deadlocks

Principally, we can 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 add state.
  • We can allow the system to enter a deadlock state, detect it, and recover.
  • We can ignore the problem altogether, and pretend that deadlocks never occur in the system. This method is use by most operating system including UNIX.

We shall elaborate briefly on each method. Then in the later units, we shall present you detailed algorithms.

To ensure that deadlocks never occur, the system can use either deadlock-prevention or a deadlock-avoidance scheme. Deadlock-prevention is a set of methods for ensuring that at least one of the necessary conditions (unit 2) cannot hold. These methods prevent deadlocks by constraining how requests for resources can be made. These methods are discussed in unit 2.

Deadlock avoidance, on the other hand, requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime. With this additional knowledge, we 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 allocated to each process, and the future requests and releases of each process. These schemes are discussed in later units.

If system does not employ either a deadlock-prevention or a deadlock-avoidance algorithm, then a deadlock situation may occur. 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 (if a deadlock has indeed occurred). This issue is discussed in unit 2.

If the system does not ensure that a deadlock will never occur, and also does not provide, a mechanism for deadlock detection and recovery, then we may arrive at a situation where the system is in deadlock state yet has no way of recognizing what has happened.

In this case, the undetected deadlock will result in the deterioration of the system performance, because resources are being held by processes that cannot run, and because more and more processes, as they make requests for resources, enter a deadlock state.

Eventually, system will stop functioning and will need to be restarted manually.

Although this method does not seem to be a viable approach to the deadlock problem, it is nevertheless used in some operating systems. In many systems, deadlocks occur infrequently like once in a year. Therefore, this method is cheaper than the costly deadlock-prevention, deadlock-avoidance, or deadlock-detection and recovery methods that must be used constantly.

4.0 Conclusion

In this unit, you have been exposed to the concept of deadlock problem, necessary conditions for its occurrence and some of the ways it can be handled when it occurs. In subsequent units, you will be taken through some specific algorithms on each of the methods for handling deadlock problems.



SEE ALLAdd a note
Add your Comment