What is Deadlock in OS?

Key Takeaways

1. Resource conflicts can prevent processes from progressing when each depends on resources already held elsewhere.

2. Mutual exclusion, hold and wait, no pre-emption and circular wait are the four necessary conditions associated with deadlock.

3. Operating Systems can address deadlocks using prevention, avoidance, detection and recovery approaches.

4. Banker’s Algorithm evaluates resource requests to help the system remain in a safe state and avoid deadlock.

5. Deadlock involves processes blocking one another, while starvation occurs when a process repeatedly fails to receive the resources it needs.

In an operating system, processes require resources to execute. These resources can include memory, files, locks, and input/output devices. Once a resource is no longer needed, it can be released for use by other processes. However, when multiple processes occur simultaneously, they may compete for resources. If each process holds a resource while waiting for another in a circular dependency, a deadlock can occur.

Understanding how these resource conflicts develop can help you identify and handle deadlock more effectively. In this blog, we will delve into what deadlock is, with detailed examples to help you understand it better. We will also cover various methods for handling deadlock.

What is Deadlock in Operating System (OS)?

Deadlock in OS refers to a situation where two or more processes or threads are unable to run because each is waiting for the other to release a resource. In other words, it’s a state where a group of processes become stuck in a way that they can’t make any progress. 

Deadlock can occur when multiple processes compete for resources that are held in a non-shareable or exclusive mode, such as locks or other exclusively allocated resources.

Necessary Conditions for Deadlock

There are four necessary conditions for a deadlock to occur, often referred to as deadlock conditions. Here are the following essential conditions for deadlock:

1) Mutual Exclusion: At least one resource must be non-shareable, meaning only one process can use it at a time. This condition means that exclusive access to the resource is required while it is allocated to a process.

2) Hold and Wait: The process must hold at least one resource while waiting to obtain additional resources. This condition allows processes to retain resources while waiting for others, contributing to the possibility of deadlock.

3) No Pre-emption: Resources cannot be pre-empted or forcibly taken away from a process. This means that a resource can only be released voluntarily by the process holding it. If a process continues holding a resource while waiting for another, this can contribute to a potential deadlock.

4) Circular Wait: There must be a circular chain of two or more processes, where every process is waiting for a resource held by the next process in the chain. This circular waiting pattern means that no process in the cycle can make progress because another process blocks it.

Quick Recall

Mutual Exclusion + Hold and Wait + No Pre-emption + Circular Wait = Deadlock Conditions

Example of Deadlock in OS

Here's a simple example of a deadlock involving two processes, Process A and Process B, competing for two resources, Resource X and Resource Y:

1) Initial Stage

1) Process A holds Resource X and requests Resource Y

2) Process B holds Resource Y and requests Resource X

2) Execution Sequence

1) Process A starts and acquires Resource X

2) Process B starts and acquires Resource Y

3) Stalemate

1) Process A requires Resource Y to complete its task, but it can’t proceed because Process B is holding it.

2) Process B requires Resource X to complete its task but can’t proceed because Process A is holding it.

Neither Process A nor Process B can release their held resource because they are still waiting for another resource to be released. Together with mutual exclusion, hold and wait and no pre-emption, this circular waiting pattern satisfies the four necessary conditions for deadlock, resulting in a deadlock situation.

Deadlock in One Line

Process A waits for a resource held by Process B, while Process B waits for a resource held by Process A.

What is Deadlock Detection?

Identifying deadlocks is essential for efficient resolution. Detecting deadlock involves checking the system's state to identify whether a deadlock has occurred. Methods such as resource-allocation graphs and deadlock detection algorithms can help identify deadlocks.

The system's resources and processes are visually depicted in the resource-allocation graph. It contains nodes representing processes and resources, connected by edges that show resource requests and allocations. If each resource type has a single instance, a cycle indicates a deadlock. If resource types have multiple instances, however, a cycle alone does not necessarily confirm a deadlock.

When a deadlock is identified, steps can be implemented to solve it, allowing processes to continue running. Detecting deadlocks is a crucial part of managing deadlocks, providing important information about the system's status and helping to make well-informed choices for solving them.

Build stronger JVM development skills with our Kotlin Engineer Training - Join today!

Methods of Handling Deadlock

The following are the methods of handling deadlocks.

1) Deadlock Prevention: Deadlock prevention is focused on removing the chance of deadlocks by ensuring that at least one of the four necessary conditions for deadlock cannot hold. In practice, prevention techniques often target conditions such as hold and wait, no pre-emption or circular wait, as mutual exclusion may be unavoidable for some resources.

2) Deadlock Detection and Recovery: In this approach, the system regularly looks for deadlocks. If a deadlock is found, the system can resolve it through actions such as terminating one or more processes, pre-empting resources where feasible or rolling back processes or transactions where supported.

3) Deadlock Avoidance: This method involves the system making real-time resource allocation decisions to maintain its safety. The Banker’s Algorithm assesses resource requests and grants them only if the resulting system state remains safe.

4) Wound-wait Scheme: In transaction and lock-management systems, wound-wait is a timestamp-based deadlock prevention scheme. If a younger transaction holds a resource requested by an older transaction, the younger transaction is rolled back so the older one can proceed. If a younger transaction requests a resource held by an older transaction, the younger transaction waits. This ordering prevents circular waits between transactions.

5) Resource Allocation Controls: Resource allocation limits can reduce contention, but they do not by themselves guarantee deadlock prevention. Such controls can complement formal deadlock handling methods by reducing excessive competition for limited resources.

Benefits of Deadlock Handling Methods

The following are the benefits of deadlock handling methods:

1) Proactive Approach: Deadlock prevention can stop deadlocks from occurring by eliminating at least one of the necessary conditions.

2) Resource Reclamation: The recovery method can potentially free up resources, allowing another process to continue execution. This can minimise the impact of deadlock on system performance.

3) Risk Reduction: Deadlock prevention and avoidance methods can reduce the risk of processes entering a deadlock state. They achieve this by controlling resource allocation or ensuring that allocation keeps the system in a safe state.

4) Improved Resource Availability: Effective deadlock handling can prevent resources from remaining indefinitely tied up in blocked process cycles, improving their availability for other processes.

5) Detection and Resolution: Deadlock detection and recovery methods allow systems to detect and resolve deadlocks when they do occur. This capability helps the system recover from deadlocks and resume normal operation.

Limitations of Deadlock Handling Methods

Here are some limitations of deadlock handling methods:

1) Complexity and Overhead: Many deadlock handling methods add complexity to the system. Implementing and maintaining these methods can be resource-intensive.

2) Process Interruption: Deadlock resolution methods such as process termination can interrupt process execution or transactions. This can affect critical tasks and potentially cause inconsistencies.

3) Complex Decision-making: Deadlock handling can involve complex decision-making to determine which process to abort or wait for. This decision makes the handling of deadlock more intricate.

4) Performance Impact: The mechanisms used for deadlock handling can introduce performance overhead. For example, frequent deadlock detection and recovery processes can consume CPU time and system resources.

5) Increased Latency: In some cases, deadlock handling methods can introduce latency into system operations. This latency can impact real-time or time-sensitive applications where responsiveness is critical.

Quick Tip

Deadlock blocks a group of processes waiting on each other, while starvation affects a process that keeps waiting because resources are repeatedly given elsewhere.

Differences Between Deadlock and Starvation

There is often confusion between deadlocks and starvation in Operating Systems. However, these two concepts are actually quite different. Deadlocks happen when two or more processes are blocked, waiting for each other to release resources. In contrast, starvation occurs when a process is unable to access resources due to competition from other processes.

Get familiar with Android Architecture with our Android App Development Training now!