Deadlock in Operating System

Deadlock is the state when two or more processes fight for same resource.This article will be exploring deadlock necessary conditions and methods for handling deadlock.

Operating systems manage and control all the tasks running on a computer. As you can imagine, conflicts can arise with so many tasks simultaneously. This is where the term “deadlock” comes into play. Deadlocks can be caused by user actions or by software malfunctions. In this post, we’ll explore what causes deadlock in the operating system and how to prevent them.

Table of content

• What is Deadlock?
• Necessary Conditions for Deadlock
• Difference between Deadlock and Starvation
• What are the Consequences of a Deadlock?
• Methods For Handling Deadlocks
  • Deadlock Avoidance
  • Deadlock Detection
  • Deadlock Prevention

What is Deadlock?

Deadlock is when two or more processes wait for each other to release a resource. This creates a standstill, and the system becomes unresponsive until one of the processes is killed.

Let’s understand with a real-life analogy.

1. Consider a very narrow one-way road where two persons, A and B, coming from opposite directions, have blocked each other’s passage. Consider road as a resource. And the other people moving on the road can be taken as processes. As the path is very narrow, none of these two-person can proceed further and is blocked. Now they are in a deadlock state.
2. John and Amy are brother-sister. They both are in a deadlock state as Amy wants a laptop which John is having and is not in the mood to give it to his sister. And Amy has a TV remote which John wants, But Amy is not giving it to him.

Also read: What is Operating Systems (OS) – Types, Functions, and Examples

Necessary Conditions for Deadlock

These four conditions must be met for a deadlock to happen in an operating system.

1. Mutual Exclusion

In this, two or more processes must compete for the same resources. There must be some resources that can only be used one process at a time. This means the resource is non-sharable. This could be a physical resource like a printer or an abstract concept like a lock on a shared data structure.

2. Hold and Wait

Hold and wait is when a process is holding a resource and waiting to acquire another resource that it needs but cannot proceed because another process is keeping the first resource. Each of these processes must have a hold on at least one of the resources it’s requesting. If one process doesn’t have a hold on any of the resources, it can’t wait and will give up immediately. 

3. No Preemption

Preemption means temporarily interrupting a task or process to execute another task or process. Preemption can occur due to an external event or internally within the system. If we take away the resource from the process that is causing deadlock, we can avoid deadlock. But is it a good approach? The answer is NO because that will lead to an inconsistent state. For example, if we take away memory from any process(whose data was in the process of getting stored) and assign it to some other process. Then will lead to an inconsistent state.

4. Circular Wait

The circular wait is when two processes wait for each other to release a resource they are holding, creating a deadlock. There must be a cycle in the graph below. As you can see, process 1 is holding on to a resource R1 that process 2 in the cycle is waiting for. This is an example of a circular wait.To better understand let’s understand with another example. For example, Process A might be holding on to Resource X while waiting for Resource Y, while Process B is holding on to Resource Y while waiting for Resource Z, and so on around the cycle.

Difference between Deadlock and Starvation

What are the Consequences of a Deadlock?

When a deadlock occurs, it can cause your computer to freeze up, making it difficult to even restart. This can cause you to lose important work or data and in some cases, may even damage your computer.

To prevent a deadlock state, it’s important to be aware of what causes deadlocks and how to avoid them.

Methods For Handling Deadlocks

1. Deadlock avoidance

Deadlock avoidance is the process of taking steps to prevent deadlock from occurring. Operating system uses the deadlock Avoidance method to ensure the system is in a safe state(when the system can allocate resources and can avoid being in a deadlock state). We have a Deadlock avoidance algorithm-Banker’s algorithm for this. When a new process is to be executed, it requires some resources. So banker’s algorithm needs to know

• How many resources the process could request
• Which processes hold many resources.
• How many resources the system has.

And accordingly, resources are being assigned if available resources are more than requested to avoid deadlock. Tell the operating system about the maximum number of resources a process can request to complete its execution. The deadlock avoidance graph(shown in fig-2) assesses the resource-allocation state to check if a circular wait situation is not occurring.

If a deadlock does occur, it can sometimes be resolved by terminating one of the processes involved. However, this can cause data loss or corruption, so it’s always preferable to try and prevent the deadlock from happening in the first place.

Bankers algorithm Pseudocode:

1. In starting all the processes are to be executed. Define two data structure finish and work:

Finish[n]=False.

Work=Available

Where n is a number of processes to be executed.

2. Find the process for which Finish[i]=False

And Need <=Work(This means a request is valid as the number of requested resources of each resource type is less than the available resources, In case no such process is there then go to step

3. Work=Work+Allocation

Finish[i]=True

Go to step 2 to find other processes 

Any process says process ‘i’ finishes its execution. So that means the resources allocated to it previously, get free. So these resources are added to Work and Finish(i) of the process is set as true.

4. If Finish[i]=True for n processes then the system is in a safe state(If all the processes are executed in some sequence). Otherwise, it is in an unsafe state

Also read: Real-time operating system

Must explore: Distributed operating system 

2. Deadlock Detection

Detecting deadlocks is one of the most important steps in preventing them. A deadlock can happen anytime when two or more processes are trying to acquire a resource, and each process is waiting for other processes to release the resource.

The deadlock can be detected in the resource-allocation graph as shown in fig below.

This graph checks if there is a cycle in the Resource Allocation Graph and each resource in the cycle provides only one instance, If there is a cycle in this graph then the processes will be in a deadlock state.

So always remember detecting deadlocks is one of the most important steps in preventing them. 

Also read: Operating System Online Courses & Certifications

3. Deadlock Prevention

The best way to prevent deadlocks is by understanding how they form in the first place. Deadlock can be prevented by eliminating the necessary conditions for deadlock(explained above).

Some ways of prevention are as follows

1. Preempting resources: Take the resources from the process and assign them to other processes.
2. Rollback: When the process is taken away from the process, roll back and restart it.
3. Aborting: Aborting the deadlocked processes.
4. Sharable resource: If the resource is sharable, all processes will get all resources, and a deadlock situation won’t come.

Conclusion

A deadlock is a situation that can occur in an operating system when two or more processes, each waiting for an event that only the other can cause, lock up the system so that no process can continue execution. We covered the necessary conditions of deadlock(a very important topic). If you liked the blog, please share it with your friends.

Happy Learning!!!

Top Trending Articles:
Data Analyst Interview Questions | Data Science Interview Questions | Machine Learning Applications | Big Data vs Machine Learning | Data Scientist vs Data Analyst | How to Become a Data Analyst | Data Science vs. Big Data vs. Data Analytics | What is Data Science | What is a Data Scientist | What is Data Analyst