Deadlock in Operating Systems: Prevention, Avoidance, Detection & Recovery

Deadlock is a situation in operating systems where two or more processes are unable to proceed because each is waiting for a resource that the other holds. Understanding deadlock, its necessary conditions, and ways to handle it is crucial for building robust operating systems.

What is Deadlock?​

Before diving into deadlock, let's first understand the typical operations involved when a process acquires a resource:

1. Request: The process requests the operating system to allocate a specific resource.

2. Use: Once the OS allocates the resource, the process can use it.

3. Release: After using the resource, the process releases it.

Necessary Conditions for Deadlock​

For a deadlock to occur, the following four conditions must be simultaneously present:

Mutual Exclusion​

Only one process can use a resource at a time. For instance, if you and your sibling both want to watch TV, only one can watch at a time, depending on who grabs the remote first.

Hold & Wait​

A process holding a resource is also waiting for another resource held by another process. This situation can cause multiple processes to get stuck, waiting for each other to release resources.

No-preemption​

Resources cannot be forcibly taken away from the process holding them until they voluntarily release the resource.

Circular Wait​

There must be a circular chain of processes, where each process holds a resource that the next process in the chain needs. For example, P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3, and P3 is waiting for a resource held by P1.

Strategies for Handling Deadlock​

Handling deadlock involves using various strategies to prevent, avoid, detect, and recover from deadlock situations.

1. Deadlock Prevention​

Deadlock prevention ensures that at least one of the necessary conditions for deadlock cannot occur.

• Mutual Exclusion: Make resources sharable whenever possible. For example, use read-only access for files that don't need exclusive control.

• Hold and Wait: Require processes to request all resources they need at once or only when they hold no other resources.

• No Preemption: Allow the system to take resources away from a process if necessary. For example, preempt a resource if another process needs it.

• Circular Wait: Impose a strict order on resource acquisition, requiring processes to request resources in a predefined order.

2. Deadlock Avoidance​

Deadlock avoidance requires the system to be aware of the current state of resources and processes, ensuring that resource allocation always results in a safe state.

Banker's Algorithm​

This algorithm helps find a safe sequence of process execution to avoid deadlock. It checks the maximum need of each process and ensures that it can be met without causing a deadlock.

In our example, let's say we have three types of resources: A, B, and C. We also have three processes named P1, P2, and P3 that need these resources to operate.

1. Total Resources Available Initially:

   • Resource A: 10 units

   • Resource B: 5 units

   • Resource C: 7 units

2. Resources Currently Allocated to Each Process (Total Allocated):

   • A: 5 units

   • B: 1 unit

   • C: 2 units

3. Available Resources After Allocation (Available = Total Resources - Allocated):

   • A: 10 - 5 = 5 units

   • B: 5 - 1 = 4 units

   • C: 7 - 2 = 5 units

Understanding the Table​

• Allocated: Resources already given to each process.

• Max Need: Maximum resources each process might request.

• Remaining Need: Calculated as Max Need - Allocated.

Step-by-Step Execution of the Banker's Algorithm​

1. Initial Available Resources: (A, B, C) = (5, 4, 5)

   This means we have 5 units of Resource A, 4 units of Resource B, and 5 units of Resource C available to distribute among processes.

2. Check Process P1:

   • Remaining Need for P1: (7, 4, 3)

   • Available Resources: (5, 4, 5)

   Here, P1 needs 7 units of A but we only have 5 units of A available. So, we cannot meet P1's request. Therefore, P1 cannot proceed right now.

3. Check Process P2:

   • Remaining Need for P2: (1, 2, 2)

   • Available Resources: (5, 4, 5)

   P2 only needs 1 unit of A, 2 units of B, and 2 units of C. We have enough resources to meet P2's needs.

   • Action: Allow P2 to proceed.

   • After P2 completes, it releases its allocated resources: (2, 0, 0).

   • New Available Resources: (5 + 2, 4 + 0, 5 + 0) = (7, 4, 5)

4. Check Process P3:

   • Remaining Need for P3: (6, 0, 0)

   • Available Resources: (7, 4, 5)

   P3 needs 6 units of A, which we can provide since we now have 7 units of A available.

   • Action: Allow P3 to proceed.

   • After P3 completes, it releases its allocated resources: (3, 0, 2).

   • New Available Resources: (7 + 3, 4 + 0, 5 + 2) = (10, 4, 7)

5. Check Process P1 Again:

   • Remaining Need for P1: (7, 4, 3)

   • Available Resources: (10, 4, 7)

   Now, we have enough resources to meet P1’s needs. P1 can proceed.

   • Action: Allow P1 to proceed.

   • After P1 completes, it releases its allocated resources: (0, 1, 0).

   • New Available Resources: (10 + 0, 4 + 1, 7 + 0) = (10, 5, 7)

Safe Sequence​

We can see that the processes can be executed in the following sequence without causing a deadlock: P2 -> P3 -> P1. This sequence is considered safe because, at each step, the available resources are sufficient to meet the remaining needs of the processes.

What Happens in a Deadlock Scenario?​

If at any point none of the processes could proceed (i.e., their remaining needs exceed the available resources), then the system would be in an unsafe state, potentially leading to a deadlock. In such cases, some processes may need to be terminated or rolled back to release resources and break the deadlock cycle.

3. Deadlock Detection & Recovery​

Allow deadlocks to happen but use mechanisms to detect and recover:

• Detection: Regularly check for cycles in the resource allocation graph.

• Recovery: Once a deadlock is detected, break the cycle by aborting a process. For example, terminating P2 might release resources, allowing P1 and P3 to continue.

4. Deadlock Ignorance​

Deadlock ignorance is a strategy where the operating system does not handle deadlocks explicitly.

Advantages​

• Simplicity: No need for complex deadlock handling mechanisms.

• Performance: Avoids overhead associated with detecting and preventing deadlocks.

• Practicality: Deadlocks may be rare, and handling them might not justify the cost.

Risks​

• System Hang: Deadlocks can cause the system to freeze, requiring manual intervention.

• Resource Wastage: Resources involved in a deadlock cannot be used, leading to inefficiency.

Use Cases​

• Single-User Systems: Users can restart processes or reboot the system if a deadlock occurs.

• Applications with Timeout Mechanisms: Applications that can reset or terminate operations after a certain period, indirectly handling deadlocks.

Conclusion​

Understanding deadlock and implementing strategies like prevention, avoidance, detection, and recovery are essential for maintaining system stability and performance. While deadlock ignorance might work for simpler systems, more robust solutions are required for complex, multi-user environments.