Deadlock Characterization

Deadlock characterization describes the distinctive features that are the cause of deadlock occurrence. Deadlock is a condition in the multiprogramming environment where the executing processes get stuck in the middle of execution waiting for the resources that have been held by the other waiting processes thereby preventing the execution of the processes.

In this content, we will discuss the characteristics that are essential for the occurrence of deadlock. The four conditions that must sustain at the same time to eventuate a deadlock are: mutual experience, hold and wait, no preemption, circular wait.

Deadlock Characterization

1. Deadlock Prerequisites
2. Systems Resource Allocation Graph

Deadlock Prerequisites

i) Mutual Exclusion

In a multiprogramming environment, there may be several processes requesting the same resource at a time. The mutual exclusion condition, allow only a single process to access the resource at a time. While the other processes requesting the same resource must wait and delay their execution until it has been released. The mutual exclusion condition prevents two or more processes to access the same resource at a time.

ii) Hold and wait

The hold and wait condition simply means that the process must be holding access to one resource and must be waiting to get hold of other resources that have been acquired by the other processes.

iii) No Preemption

A process acquiring a resource, cannot be preempted in between, to release the acquired resource. Instead, the process must voluntarily release the resource it has acquired when the task of the process has been completed.

iv) Circular Wait

The processes must be waiting in a circular pattern to acquire the resource. This is similar to hold and waits the only difference is that the processes are waiting in a circular pattern.

Let us discuss this with an example there are five processes i.e. P₀, P_1, P_2, P_3, P₄. Now the process P₀ is waiting to acquire the process held by the P₁, further the process P₁ is waiting to acquire the resource held by P₂, …., process P₄ is waiting to acquire the resource held by P_0.

System Resource Allocation Graph

The system reallocation graph is a directed graph that briefs you about the deadlock more precisely. Like every graph, it also has a set of vertices and a set of edges. Further, the set of vertices can be classified into two types of nodes P and R. Where P is the set of vertices indicating the set of active processes and R is the set of vertices indicating all types of resources in the system.

When a process requests for a resource it denoted by the request edge in the resource-allocation graph. The request edge is a directed edge from the requesting process P_i to requested resource R_j i.e. P_i -> R_j.

Well, when a resource is allotted to some process then it is denoted by the assignment edge. The assignment edge is the directed edge from the instance of resource R­_j to the process P­_i i.e. R_j -> P_i.

In the graph, resources are denoted by the rectangles and the processes are denoted by the circles. If a resource has multiple instances then it is denoted by the dots inside the rectangle.

When a process request for an instance of the resource it directs a request edge to the resource. If the resource is able to allocate the resource instance to the requesting process then immediately the request edge is converted to assignment edge.

The request edge always points to the resource rectangle in the graph, not to dots (instance) inside the rectangle. Although the assignment edge nominates the dot (instance) to a process.

To understand deadlock we let us take an example. Consider we have following set of nodes and edges.

1. There are three active processes P = {P₁, P₂, P₃}
2. There are four resources R = { R_1, R₂, R₃, R₄}
3. The set of request edge and assignment edges we have
   E = { P1 -> R₁, P₂ -> R₃, R₁ -> P₂, R₂ -> P₂, R₂ -> P₁, R₃ -> P₃}

Observe the figure above that the resource R­₁ has only one instance, resource R₂ has two instances, resource R₃ has one instance, and resource R₄ has three instances. Let us check the status of the processes.

The figure below shows that the process P₁ has requested for the instance of resource R₁ is already holding the instance of resource R₂. The process P₂ has requested for the instance of resource R₃ and is already holding the instances of resource R₁ and R₃. The process P₃ has not requested for any resource instance but is holding the instance for resource R₃.

Remember if the resource allocation graph has a cycle and every resource has a single instance then it implies that a deadlock has occurred. In case, the resources have multiple instances then a cycle in the graph need not be indicating the occurrence of deadlock.

Consider that the process P₃ is requesting for the instance of resource R₂ which is already held by the process P₁ and P₂. In this case, you will observe that there are two cycles in the resource allocation graph:

• P₁ -> R ₁ -> P₂ -> R₃ -> P₃ -> R₂ -> P₁
• P₂ -> R₃ -> P₃ -> R₂ -> P₂

Process P₁, P₂ and P₃ are now in deadlock as each process in the cycle is waiting for the resource held by another process. But every cycle in the resource allocation graph does not indicate the deadlock, you have to observe the cycle carefully while dealing with deadlock problem. So, this is how you can characterize the deadlock in the system.