Home

Learning Hub

Articles

An Introduction to Deadlock Avoidance in OS (Operating System)

Deadlock is a very complex and critical situation that occurs mostly in multiprocessing operating systems. In a deadlock, two or more resources are waiting for the resources to acquire and execute which are being held by each other for an infinite period. Deadlocks have the potential to bring down the system as a whole, resulting in severe resource waste and performance deterioration. For this reason, knowing how to prevent deadlock and putting it into practice are essential for system efficiency and dependability.

In this article, we will learn about deadlock avoidance along with some techniques to avoid it in multiprocessing systems. We will see the common algorithm called Banker’s algorithm that is used for deadlock avoidance. Apart from this, we will see the difference between deadlock prevention and detection and explore various strategies to maintain system stability.

What is Deadlock?

Deadlock is a situation in an operating system when two or more processes wait for an infinite amount of time to acquire resources held by each other. Deadlock occurs in a multitasking system when a group of processes enters a state of indefinite time, with each process waiting on resources held by other processes within the same group.

At its core, deadlock is a circular dependence where every process halts progress, resulting in the entire system grinding to a halt. Deadlock commonly arises in multi-processing— where numerous processes share a particular kind of mutually exclusive resource referred to as a soft lock or software. In effect, deadlock acts like a stopper for any flow — it does not permit anything that would go past it.

For example, there is an operating system in which there are two processes, P1 and P2. Also, there are two resources, R1 and R2, which are initially free. Now,

• Process P1 starts and acquires Resource R1.
• Process P2 starts and acquires Resource R2.

Now, there is a situation when P1 now wants the R2 resource to execute but is being held by P2, similarly, P2 wants the R1, which is being held by P1. Here, as P1 can’t access R2, so P1 is put on hold and waits and similarly, P2 can’t access R1, so P2 is put on hold and waits.

In this situation, both P1 and P2 are waiting for a resource held by each other, creating a cycle of dependency with no way to proceed, resulting in a deadlock.

Necessary Conditions for Deadlock

To cause a deadlock in an operating system, there are mainly four conditions that need to be there simultaneously. Here are the four conditions for deadlock:

1. Mutual Exclusion

According to the mutual exclusion condition, only one process at a time can access certain resources. It implies that a minimum of one resource needs to be maintained in a non-shareable mode, which restricts resource usage to a single process at a time.

 2. Hold and Wait

When a process has at least one resource in hand and is waiting to obtain more, the hold and wait condition occurs.  To put it another way, a process that has at least one resource is waiting to obtain more resources than other processes have.

 3. No Preemption

In preemption, it is forbidden to forcibly remove resources from a process according to the no preemption condition. A process can only release a resource that it has obtained voluntarily. This means that to free up resources for use by other processes, a process cannot be stopped or preempted. Resources must be freed willingly from processes that are retaining them.

 4. Circular Wait

In circular wait, every part in a circular chain of processes has at least one resource that is required by the process after it. It is a never-ending wait loop that stops any process from obtaining the resources it needs to keep running.

Also read: What is process in OS

What is Deadlock Avoidance?

As the name implies, it means to avoid the deadlock in the operating system. Deadlock avoidance ensures that requests for any resource are fulfilled as long as the system’s final state avoids causing deadlock. The system’s condition will be monitored continually to identify safe and harmful conditions.

In order to guarantee that the system stays in a secure state where deadlock is impossible, it requires rigorous resource allocation planning, which can be done using various algorithms, including Banker’s algorithm. Its main objective is to dynamically allocate resources according to the expected actions of processes.

Understanding Deadlock Avoidance vs. Deadlock Prevention vs. Deadlock Detection

In operating systems, there are various terms to understand including deadlock prevention, deadlock avoidance, and deadlock detection. Let’s understand each of these terms in detail.

Deadlock Prevention

Deadlock prevention is a technique to remove at least one of the four necessary conditions for deadlock, as it ensures that there shall be no deadlock in any operating system. This method is very useful and can be highly restrictive for better computing utilisation and decreased system throughput. To prevent the deadlock from occurring, we can eliminate one or more of the following:

• Mutual Exclusion: To prevent mutual exclusion, we can reduce the use of exclusive locks in the operating systems. But it is not possible to remove this condition as some of the resources like printers, are inheritable non-shareable resources.
• Hold and Wait: To eliminate the hold and wait condition, the required processes need to request all the required resources upfront.
• No Preemption: To eliminate this condition, start allowing preemption of resources.
• Circular Wait: To eliminate the circular wait, we can force a total ordering on CPU resource acquisition.

Deadlock Avoidance

As the name implies, it means avoiding some conditions for a deadlock to not occur in the OS> Deadlock avoidance is another technique that requires a dynamic examination of resource allocation to ensure that a circular wait condition does not occur in the operating system.

Deadlock Detection

Deadlock detection is a technique that permits deadlock to happen but offers ways to identify and break it. This includes looking for cycles in the resource allocation graph regularly and then taking the necessary steps to break the impasse, such as killing off some processes or forcing resources to be preempted.

To avoid deadlock, there are two techniques. We will discuss both these techniques to see how we can avoid deadlock. Note that the deadlock prevention methods need a lot of processing power and can be complicated. So, try balancing between the requirement to allocate resources and the avoidance of deadlocks.

Resource Allocation Graph (RAG)

The very first technique to avoid deadlock is the resource allocation graph (RAG). It is a type of directed graph that is used to show how resources are allocated in a system. RAG is also a representation of the system’s state. Every process, every resource that has been assigned to it, and every resource that each process has requested are all included in the graph.

In RAG, the resources and processes are represented by nodes and resource allocation and requests are represented by edges. The resources in RAG can be allocated using two methods: Dynamic and static allocation.

In the dynamic allocation method, the processes are allocated dynamically in real-time as required by the OS to reduce the chances of deadlock.

In the static allocation method, the processes are allocated using the scheduled time but not in real time. This method is not recommended as it reduces resource utilisation and makes inflexibility.

An example of understanding the resource allocation graph (RAG) is given below.

Banker’s Algorithm

To understand the banker’s algorithm, we need to understand two concepts called safe state and unsafe state.

Safe and Unsafe State

The idea of safe and unsafe states is essential to avoiding deadlocks. If there is a sequence of resource allocations that permits all processes to complete without creating a stalemate, then that state is safe. In a safe state, the OS allocates the maximum resources of all processes.

A state where there is no such sequence and deadlock is possible is considered an unsafe state. In an unsafe state, the OS is not able to prevent the processes from requesting CPU resources.

What is a Banker’s Algorithm?

A banker’s algorithm uses the concept of a safe state where it checks for deadlock avoidance. This algorithm determines whether a system is in a safe state or unsafe state by simulating the allocation of resources (maximum available) using techniques like RAG.

The banker’s algorithm evaluates every resource request made by processes, looks for the safe state, and grants requests only if the system is still in the safe state. If the system is not in a safe state, it denies requests made by processes. Let’s see how a banker’s algorithm works with the help of an example.

Example:

Consider three resources (R1, R2, R3) with the processes P1, P2, and P3. The available resources are 3, 3, and 2. Check whether the system is in a safe state or unsafe state.

Given,

Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2]]

Allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2]]

We are given the max, allocation, and available resources. Now to check for a safe or unsafe state, we have to first check how much resources each process needs. Therefore, we calculate the Need using the formula: Need = Max – Allocation.

Need = [[7, 4, 3], [1, 2, 2], [6, 0, 0]]

So, now we have the need for each process (i.e., [[7, 4, 3], [1, 2, 2], [6, 0, 0]]) and the available resources (3, 3, 2). So, we will now allocate the resources in order of the available resources.

As per the algorithm,

1. Initialize Work and Finish:

Work = Available = [3, 3, 2]

Finish = [False, False, False]

1. Find a Process that Can Be Satisfied:

Check if there is a process whose Need <= Work and is not finished.

Iteration 1:

Check which process Need <= work.

P1: Need = [7, 4, 3], which is not <= Work = [3, 3, 2]

P2: Need = [1, 2, 2], which is <= Work = [3, 3, 2]

Here, in the first iteration, P2 satisfies the condition; therefore, we allocate resources to P2 and mark it as finished. Now, our new work becomes: Work + Allocation[P2] = [3, 3, 2] + [2, 0, 0] = [5, 3, 2]

Iteration 2:

P1: Need = [7, 4, 3], which is not <= Work = [5, 3, 2]

P3: Need = [6, 0, 0], which is <= Work = [5, 3, 2]

Here, as no other process satisfies the condition, therefore we will check if we can satisfy any process with the updated Work:

Process P3: Need = [6, 0, 0], which is not <= Work = [5, 3, 2]

Since no other process satisfies the condition, we determine that the system is in an unsafe state. As the system is in an unsafe state, we also can’t create its Gantt Chart.

Let’s see a code example in C language for the implementation of Banker’s algorithm:

Code:

// import statements

#include <stdio.h>

#include <stdbool.h>

// no of processes and resources

#define P 4

#define R 3

// Check if the system is in a safe state

bool isSafe(int processes[], int avail[], int max[][R], int allot[][R]) {

int resNeed[P][R];

int completionStatus[P] = {0}; // To track finished processes

int safetySequence[P]; // Safe sequence

// Calculate the need matrix

for (int i = 0; i < P; i++)

for (int j = 0; j < R; j++)

resNeed[i][j] = max[i][j] – allot[i][j];

// Copy available resources to work

int work[R];

for (int i = 0; i < R; i++)

work[i] = avail[i];

int cnt = 0;

while (cnt < P) {

bool found = false;

for (int p = 0; p < P; p++) {

if (completionStatus[p] == 0) {

int j;

for (j = 0; j < R; j++)

if (resNeed[p][j] > work[j])

break;

if (j == R) {

for (int k = 0; k < R; k++)

work[k] += allot[p][k];

safetySequence[cnt++] = p;

completionStatus[p] = 1;

found = true;

}

}

}

if (found == false) {

printf(“System is in unsafe staten”);

return false;

}

}

printf(“System is in safe state.nSafe sequence is: “);

for (int i = 0; i < P; i++)

printf(“%d “, safetySequence[i]);

printf(“n”);

return true;

}

// Request resources for a process

bool reqRes(int process, int request[], int avail[], int max[][R], int allocatedRes[][R]) {

int need[P][R];

for (int i = 0; i < P; i++)

for (int j = 0; j < R; j++)

need[i][j] = max[i][j] – allocatedRes[i][j];

for (int i = 0; i < R; i++) {

if (request[i] > need[process][i]) {

printf(“Sorry, process has exceeded its max need.n”);

return false;

}

if (request[i] > avail[i]) {

printf(“resources not available.n”);

return false;

}

}

for (int i = 0; i < R; i++) {

avail[i] -= request[i];

allocatedRes[process][i] += request[i];

need[process][i] -= request[i];

}

if (isSafe((int[]) {0, 1, 2, 3, 4}, avail, max, allocatedRes)) {

printf(“Your request is granted.n”);

return true;

} else {

for (int i = 0; i < R; i++) {

avail[i] += request[i];

allocatedRes[process][i] -= request[i];

need[process][i] += request[i];

}

printf(“Request ungranted as it is unsafe state.n”);

return false;

}

}

// Main function

int main() {

int processes[] = {0, 1, 2, 3};

int avail[] = {4, 3, 2};

int max[P][R] = {

{7, 5, 3},

{9, 0, 2},

{3, 2, 2},

{2, 2, 2}

};

int allot[P][R] = {

{0, 1, 0},

{3, 0, 2},

{2, 0, 0},

{2, 1, 1}

};

isSafe(processes, avail, max, allot);

int req1[] = {1, 0, 2};

reqRes(1, req1, avail, max, allot);

return 0;

}

Output:

System is in safe state.

Safe sequence is: 2 3 0 1

Sorry, process has exceeded its max need.

Tools and Techniques for Deadlock Avoidance

There are various tools and techniques used for deadlock avoidance apart from the above-discussed techniques, and they include:

1. Distributed Locking:

In a distributed system, it manages the sharing and access of resources between several processes or nodes. By doing this, concurrent problems like deadlocks may be avoided.

2. Simulation Tools:

Developers can uncover possible deadlock problems by modelling and testing resource allocation scenarios using simulation tools. By simulating various workloads and configurations, these tools can shed light on how well deadlock avoidance techniques operate.

3. Formal Verification:

The discussed deadlock avoidance algorithms can have their correctness demonstrated by formal verification techniques including model checking and theorem proving. These methods offer mathematical assurances that under given circumstances, the system will not be deadlocked.

Advantages And Disadvantages Of Deadlock In OS

While deadlock is always considered a negative thing in operating systems, it also comes with various advantages and disadvantages. Let’s see some of them:

Advantages

• In some situations, deadlocks might be beneficial, such as when programs execute in short bursts and don’t need to share resources.
• Useful when data accuracy matters more than system performance as a whole, deadlocks can offer simplicity and efficiency.
• It is useful in various specific situations where data integrity is more important.
• Compile-time checks can be used to enforce deadlocks, which eliminates the requirement for runtime computation and lowers the possibility of unexpected system behaviour.

Disadvantages

• When processes are stalled while waiting for resources they will never be able to obtain, deadlocks can result in the waste of system resources.
• Processes that experience deadlock may get stuck in an endless cycle, which may lead to a system crash.
• It may lead to data integrity issues when not handled properly.
• It may lead to an increase in the costs of the CPU.

Conclusion

Operating systems can experience deadlock, a serious problem that arises when cyclic dependencies in resource allocation prevent processes from moving forward. In this article, we learned about Deadlock avoidance, including the necessary conditions for deadlock to occur and different deadlock avoidance techniques.

We have seen how the banker’s algorithm in deadlock avoidance helps in determining the system’s state and checking for deadlock. Even though it is intricate, this proactive strategy is required to avoid the severe repercussions of the deadlock. In conclusion, deadlock is a very complex situation that needs constant and careful consideration and the best techniques or methods to avoid deadlock so that we can ensure a better, stable, and efficient operating system.