What is Deadlock and Starvation in Operating Systems

What is Deadlock and Starvation in Operating Systems

In a multiprogramming environment, several processes request the resources like I/O devices, clocks, etc… from the operating system. If the resources are available at that time, then the operating system grants the resources to that process. If the resource is not available then the process has to wait until the resource is released. Sometimes the processes are not released and the resources are blocked by some other process. This situation is said to be Deadlock.

What is Deadlock?

A process requests the resources, but the resources are not available at that time, so the process enters into the waiting state. But the requesting resources are already held by another waiting process, so both are in the waiting state, this situation is said to be Deadlock.

For example, P1 and P2 are two processes; R1 and R2 are two resources. P1 requests the resource R1, but R1 is held by process P2. The P2 requests the resource R2, but R2 is held by process P1 then both are entered into the waiting state. Because of this, there is no work progress for processes P1 and P2. This situation is a deadlock.


Resource Allocation Graph

A resource allocation graph is a directed graph used to represent the deadlocks. There are two types of nodes in the graph, one for processes represented by circles and the second for resources represented by squares. The graph consists of two types of edges requesting edge and assignment edge. Consider the figure below.

An edge from a process to a resource is said to be a requesting edge and an edge from a resource to a process is said to be an assignment edge. If a resource allocation graph consists of cycles (P1 -> R1 -> P2 -> R2 -> P1) then the system may or may not be in a deadlock. But if the system is in a deadlock state then the resource allocation graph must have cycles.


The Conditions for Deadlock

The following are the four conditions that should satisfy a deadlock system.

1. Mutual Exclusion

A mutual exclusion means resources are in non-sharable mode only. The non-sharable mode means only one process at a time can use a resource. If some other process requests that resource then the requesting process must wait until the resources have been released. For example, the printers are always in non-sharable mode only and just one process can use the resource at a time.

2. Hold and Wait

In the hold and wait condition, each and every process in the deadlock state must hold at least one resource and it is waiting for additional resources that are currently held by other processes. Consider the below figure.

As shown in the above figure P1, P2, and P3 are three processes with R1, R2, R3, and R4 being four resources. The holding/waiting status is shown in the table.

ProcessHolding ResourcesWaiting for Resources
P1R3R1
P2R1, R4R2, R3
P3R2R4

3. No Preemption

No Preemption means resources are not released in the middle of the work. They are released only after the process has completed its task.

4. Circular Wait

Consider the below figure, P1 is waiting for a resource R1 which is held by P2, but P2 is waiting for R2, and R2 is held by P3, P3 waiting for R3, and R3 is held by P1. This condition is called Circular Wait.


Deadlock Prevention

Deadlock prevention is using preventive methods before attacking the deadlock. We can prevent the occurrence of the deadlock by ensuring that at least one of four necessary conditions can’t hold. So apply this technique to four necessary conditions separately.

1. Mutual Exclusion

A mutual exclusion means only one process can use the resource at a time. It means the resources are not shared by the number of processes at a time. We can deny this condition with a simple protocol by converting all non-sharable resources to sharable resources. So this condition is not satisfied by the deadlock and we can prevent the deadlock.

A printer is not shared by the number of processes at a time, so we can’t convert the printer from non-sharable to sharable mode.

2. Hold and Wait

Hold and wait means each and every process in the deadlock state must hold at least one resource and wait for at least one resource.

We can deny this condition by allowing a process to request the resources only when the process has none. This protocol is very expensive and time-consuming. For example, a process wants to copy the data from a pen drive to a hard disk, and then take a printout. Initially, the process holds the pen drive and hard disk. Now the copy process is completed, it needs to request by the printer. Applying the above-said protocol the process should release both the pen drive and hard disk before the request to the printer. So it is time-consuming.

The second protocol is each process request and allocates all its resources before it begins execution. It is also very difficult to implement because more resources are required to begin the execution. For example, P1, P2, P3 … P50 is 50 processes, each requiring a printer to complete their jobs. Applying this protocol, the system must consist of 50 printers. So it is very difficult to implement.

There are two main disadvantages to these protocols. First resource utilization is very poor and second starvation is possible. 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.

3. No Preemption

The third necessary condition is no preemption. It means resources are not released in the middle of the processing of a resource. We can use the following protocol to ensure that this condition does not hold.

We first check if requesting resources are available, if they are available we allocate them. If they are not available, we check if they are allocated to some other process that is waiting for additional resources. If they are waiting then we preempt the desired resources from the waiting process and allocate them to the requesting process. If resources are not available or held by a waiting process then the requesting process must wait. But till the process is in the waiting state some of its resources may be used by other processes.

4. Circular Wait

To ensure that circular wait must not happen we can be numbering all the resource types and each process requests resources in increasing order of enumeration.

Whenever a process requests an instance of resource type Rj then it must have released any resource Ri such that F(Ri) > F(Rj).

The second protocol is a process that can initially request any number of instances of a resource type Ri, only after that, the process can request the instances of resource type Rj, if and only if F(Rj) > F(Ri).

If we use these two protocols then the circular wait condition cannot hold.


Deadlock Detection

The deadlocks detection mechanism for single instances and multiple instances of the resource type is different. We can detect the deadlocks using a wait-for graph for a single instance resource type and a detection algorithm for multiple instances of the resource type.

1. Single Instance of Resource Type

In the single instance of resource type, the system consists of only one resource for one type. We can detect this type of deadlock with the help of a wait-for-graph. A wait for the graph is derived from a resource allocation graph and consists only of processes instead of resources.

wait-for-graph

If the wait-for-graph contains cycles then a system is in a deadlock state. In the above figure, there are 2 cycles one is P1 to P2 to P1, the second is P2 to P3 to P2, so the system consists of two deadlocks.

2. Multiple (Several) Instances of Resource Type

The wait-for-graph method is not applicable to several instances of the resource type. Therefore we need a deadlock detection algorithm method for this type. This algorithm is similar to Banker’s Algorithm and it has several similar data structures used in the Bankers algorithm.

Data Structures

Available: A vector of length of m indicates the number of available resources of each type.
Allocation: An n X m matrix indicates the number of resources of each type currently allocated to each process.
Request: An n X m matrix indicates the current request of each process. If request [i, j] = k, then process Pi is requesting K more instances of resource type Rj.

Detection algorithm:

Step 1:Available = i, for i = 1, 2, 3, 4 …
If Allocation[i] ≠ 0, then Finish [i] := false
Otherwise Finish [i] := true.
Step 2:Find an index i such that both
(i) Finish [i] = false
(ii) Request [i] < Available.
Step 3:Available = Available + Allocation [i]
Finish [i] := true
Go to Step 2.
Step 4:If Finish [i] =false, for some i then the system (process Pi) is in a deadlock state.

Recovery from Deadlock

There are two methods for breaking a deadlock.

  1. Abort one by one processes to break the circular wait.
  2. Preempt some resources from one or more of the deadlocked processes.

1. Process Termination

Process termination is one method to recover from deadlock. We use one of two methods for process termination:

i. Abort all deadlocked processes: In this method, we release all processes in the dead-locked state and start the allocation from the starting point. It is a very expensive method to recover from deadlock.

ii. Abort process one by one until the deadlock cycle is eliminated: In this method, we first abort one process from the deadlocked state processes and allocated the resources from the abort process to some other process in the deadlock state. Then we check whether the deadlock is broken, if not then abort another process from the deadlock state. We will continue this process until we recover from the deadlock. This method is also expensive but better than the first method.

2. Resource Preemption

There are three methods to eliminate deadlocks using resource preemption. These are:

i. Selecting a victim: Select a victim resource from the deadlock state, and preempt that one.

ii. Rollback: Roll back the processes and resources up to some safe state, and restart them from that state. This method requires the system to keep more information on all the running processes’ states.

iii. Starvation: A process or a resource can be picked as a victim a finite number of times, it is said to be starvation. The most common solution is to include the number of rollbacks in the cost factor.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top