Deadlock Detection And Recovery in OS

January 31, 2023

Detection and Recovery of Deadlock in Operating System

Deadlock detection and recovery refer to the process of identifying and resolving instances of deadlock in a system. Deadlock detection involves identifying when a deadlock has occurred and recovery involves resolving the deadlock.

Deadlock detection involves identifying when a deadlock has occurred in the system. Recovery can be once a deadlock has been detected, it must be resolved.

Deadlock in Operating System

Deadlock detection involves identifying when a deadlock has occurred in the system. This can be done through the use of algorithms, such as the Banker’s Algorithm or the Wait-For Graph Algorithm, which check for the presence of the necessary conditions for deadlock.

Detection

There are 2 different cases in case of Deadlock detection –

Deadlock detection using a centralized algorithm: In this approach, a single entity, such as the operating system, is responsible for detecting and resolving deadlocks in the system. This entity periodically checks for the presence of deadlocks and takes appropriate action to resolve them.
Deadlock detection using a distributed algorithm: In this approach, multiple entities, such as processes or nodes in a distributed system, work together to detect and resolve deadlocks. Each entity maintains information about the resources it holds and requests, and communicates with other entities to detect and resolve deadlocks. This approach can be more efficient and scalable than a centralized approach, but it can also be more complex to implement.

Both centralized and distributed algorithms have their own advantages and disadvantages. Centralized algorithms are simpler to implement but may have scalability issues, while distributed algorithms can be more efficient and handle large systems, but they can be more complex to implement.

If Resources has Single Instance

If there is only one instance of a resource in a system, deadlock detection and recovery is not necessary. This is because there can be no situation where multiple processes are competing for the same resource, and therefore no possibility of a deadlock occurring.

However, if there are multiple instances of a resource, then deadlock detection and recovery is necessary to prevent and resolve any potential deadlocks.

The Wait-for graph is made by looking at the resource-allocation graph. An edge between P1 to P2 exists if P1 needs some resources which P2 has.

In the above wait-for graph P1 is waiting for resources currently in use by P2
And P2 is waiting for resources currently in use by P3 and so on…
P5 is waiting for a resource currently in use by P1. Which creates a cycle thus deadlock is confirmed.

Wait-for-graph A wait-for graph is made. A Wait-for graph vertex denotes process. The edge implies process waiting for Process 2 to release resources. A deadlock is detected if one wait-for graph contains a cycle.

Deadlock Introduction

Deadlock Detection And Recovery

Deadlock detection Algorithm

Deadlock Avoidance and Prevention

To detect cycle, system maintains the wait state of graph and periodically invoke an algorithm to detect cycle in graph.

If there are multiple instances of resources –

By multiple instance we mean one resource may allow 2 or more accesses concurrently, in such cases –

Wait for graph is not applicable.
In this, a new algorithm is used. It’s a bit similar to Banker’s Algorithm, but Bankers Algorithm is different.
It too uses 3 data structures –
- Available
  - Vector of length m
  - Indicates number of available resources of each type.
- Allocation
  - Matrix of size n*m
  - A[i,j] indicates the number of j th resource type allocated to i th process.
- Request
  - Matrix of size n*m
  - Indicates request of each process.
  - Request[i,j] tells number of instance Pi process is request of jth resource type.

The Algorithm for detection is –

Check this page here to learn how to solve Deadlock Detection Algorithm.

Time Complexity is O(m*n*n).

Deadlock Recovery

Once a deadlock has been detected, it must be resolved. There are several methods for deadlock recovery, including:

Killing one or more processes: This is known as the “abort” method, where the operating system kills one or more of the processes involved in the deadlock in order to release the resources and resolve the deadlock.
Resource preemption: This method involves forcibly taking resources from a process and giving them to another process in order to resolve the deadlock.
Resource allocation: This method involves changing the way resources are allocated in order to prevent deadlocks from occurring in the future.

It’s worth noting that, besides the above mentioned methods, there’s another one called “Rollback” which involves rolling back one or more processes to a previous state in order to release resources and resolve the deadlock.

It’s important to note that any chosen method should be used with care, as it may cause other issues or problems.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Summary

Reviewer

Navneet

Review Date

2018-06-10

Reviewed Item

Deadlock Detection & Recovery in OS

Author Rating