In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources and if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change state because the resources it has requested are held by other waiting processes. This situation is called deadlock.

Scope

This article explains deadlock in detail.

Definition

When a process runs it needs resources and it runs in its own address space. It is the responsibility of the operating system to make sure that the resources are allocated in the proper manner. The resources might be shareable or non-shareable. For example, a printer is a non-shareable resource. Only one process can print at a time. The operating system ensures that only one process is assigned to the printer. Let’s understand the deadlock with an example, let’s say there are two processes P1 and P2, and two resources R1 and R2. Say R1 is a printer, which is non-shareable. R2 is a file that is also non-shareable in write mode. Only one process can write at a time. So process P1 begins. It asks the operating system to get the hold of the printer and since nobody else was using the printer, the operating system assigns the printer to it. Next P2 is assigned to the processor and it starts running. P2 asks the operating system to get write access to the file R2 and since nobody else was using it, the operating system assigns R2 to P2. P1 resumes its execution and requests R2. But R2 is already assigned to P2 and cannot be assigned to more than one process at a time. So the operating system asks P1 to wait for R2 till P2 finishes writing into the R2’s file. Now P2 resumes its execution and it requests the printer. The same happens with P2 since the printer is already assigned to the P1, and the operating system asks P2 to wait for R2. So none of the processes can progress further because both of them are holding one non-shareable resource and waiting for other non-shareable resources. This situation is called deadlock.

There can be multiple processes waiting in the cycle for each other. Let’s take an example with three processes. Process P1 requests for R1, process P2 requests for R2, and Process P3 requests for R3. The operating system assigned them resources since nobody else was using them. Now, P1 asks for R2 which is held by P2, P2 asks for R3 which is currently with P3 and P3 asks for R1 which is with P1. They are all waiting in a circular manner.

Four important conditions for deadlock are:

1. Mutual exclusion

Deadlock can happen only when resources are non-shareable If either R1 or R2 can be shared then both P1 and P2 can make progress because they both can get hold of it. Therefore mutual exclusion is required. 

2. Hold and wait

A process must be handled at least one resource and waiting to require additional resources that are currently being held by the other processes.

3. No resource preemption

The operating system assigns a resource to a process and cannot take it back if another process requests it because if it happens then deadlock will never occur. Resources cannot be preempted i.e. a resource can be released only voluntarily by the process holding it after that process has completed its task. 

4. Circular wait.

In circular wait, processes are waiting in a circle for each other. All four conditions are necessary for a deadlock to happen. If a deadlock happens in the system then either the operating system has to do some work or we need to reboot the system.

We can understand deadlock by a real-world example. For example, consider a railway track where two trains are coming from opposite sides. Both trains are in front of each other and they are stopped because they both need the other side of the track. So this is a situation where no train can make progress because both trains are holding one side of the track waiting for the other side of the track. And both are waiting in a circular manner and we cannot do preemption. We cannot make the train go out of the track and free the track. This situation is a deadlock. 

Resource allocation graph

• Deadlocks are represented in terms of directed graphs called a system resource-allocation graph.
• This graph consists of a 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 of all active processes in the system.

  R = {R1,R2……Rn} – the set consisting of all resources types in the system

• A directed edge from Pi to 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.
• A directed edge from Rj to 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.

• Each process is represented as a circle and resource type Rj as a rectangle. Since resource types may have more than one instance, we represent each instance as a dot within the rectangle.
• A request edge points to only the rectangle Rj whereas an assignment edge must also point to one of the dots in the rectangle.
• When a process Pi requests an instance of resource type Rj a request edge is inserted in the resource-allocation graph. When this request is fulfilled, the request edge is transformed into an assignment edge. When the process no longer needs access to the resource, it releases the resource, so the assignment edge is deleted. 

Example:

The sets P,R,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 R1.
• Two instances of R2
• One instance of R3
• Three instances of R4

Process states:

• P1 is holding an instance of R2 and is waiting for an instance of R1.
• P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance of R2.
• P3 is holding an instance of R3.

Note

• If the graph does not have a cycle, then the system is not in a deadlock state.
• If there is a cycle, then the system may or may not be in a deadlock state.    

Summary

In a deadlock, processes cannot progress further because each process is holding a resource and waiting for another resource acquired by some other process. The necessary conditions for deadlock to happen are Mutual exclusion, Hold and Wait, No preemption, and Circular wait. These conditions should happen simultaneously for the deadlock to happen.  

Special thanks to Avaneet Kaur Saluja for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article