Deadlock in Operating System | BCA 4th Semester OS Notes | Deadlock Prevention & Detection

In an operating system, the system model describes how processes interact with resources. A system consists of multiple processes (P1, P2, ..., Pn) that request access to a set of resources (R1, R2, ..., Rm), such as CPU time, memory, files, or I/O devices. Resources can be either single-instance (e.g., a printer) or multiple-instance (e.g., memory blocks). Each process can request a resource, use it once allocated, and release it after use. This cycle of request, use, and release is the foundation for understanding how resource management can lead to problems like deadlocks if not handled properly.

 System Resources

System resources are divided into two main types based on whether they can be safely taken away from a process:

1. Preemptable Resources:
   These resources can be taken away from a process without causing any harm or inconsistency.The system can reassign them as needed.
   Examples: CPU registers, main memory (RAM).
2. Non-Preemptable Resources: These cannot be forcibly taken from a process without causing issues or corrupting data.Resource must be released voluntarily by the process using them.
   Examples: Printers, open files, I/O devices.

Necessary Conditions for Deadlock

Deadlock occurs when a set of processes are blocked because each process is holding a resource and waiting for another held by some other process.

All 4 conditions must hold simultaneously for deadlock to occur:

Deadlock Modeling

Deadlock modeling is a technique used to visualize how processes and resources interact within a system and to analyze situations that may lead to deadlock. The most common model used is the Resource Allocation Graph (RAG). In this graph, processes are represented as circles and resources as squares. A request edge from a process to a resource indicates that the process is waiting for that resource, while an assignment edge from a resource to a process indicates that the resource has been allocated to that process. In systems where each resource has only one instance, the presence of a cycle in the graph indicates a deadlock. However, in systems with multiple instances of resources, a cycle does not always mean a deadlock has occurred—it only suggests the possibility. Resource allocation graphs are helpful for detecting and understanding deadlocks, especially in theoretical or simulation-based analysis.

The Ostrich Algorithm

The Ostrich Algorithm is a deadlock-handling strategy where the operating system simply ignores the problem of deadlocks. This approach is based on the assumption that deadlocks occur so rarely that the cost of preventing or detecting them outweighs the benefits. It gets its name from the idea that, like an ostrich burying its head in the sand to avoid danger, the system chooses not to deal with the issue proactively. This method is commonly used in general-purpose operating systems like UNIX, where occasional deadlocks can be tolerated and resolved manually, such as by restarting the affected application or system. While the Ostrich Algorithm is easy to implement and introduces no overhead during runtime, it carries the risk of allowing deadlocks to halt critical processes, which may not be acceptable in real-time or safety-critical systems.

Methods of Handling Deadlocks

1. Deadlock Prevention

   • Ensure that at least one of the four necessary conditions for deadlock never occurs.

   • Prevents deadlocks by denying conditions such as mutual exclusion, hold and wait, no preemption, or circular wait.

   • May lead to inefficient resource utilization.

2. Deadlock Avoidance

   • The system dynamically examines each resource request to decide if granting it keeps the system in a safe state.

   • Uses algorithms like the Banker’s Algorithm to avoid unsafe states that might cause deadlocks.

   • More flexible than prevention but requires more overhead.

3. Deadlock Detection and Recovery

   • Deadlocks are allowed to occur, but the system has mechanisms to detect them (e.g., Resource Allocation Graphs).

   • Once detected, the system recovers by terminating or rolling back processes or preempting resources.

   • Involves overhead but allows better resource utilization.

4. Ignoring Deadlocks (Ostrich Algorithm)

   • The system ignores deadlocks, assuming they are rare and not worth the overhead of handling.

   • Deadlocks may be resolved by manual intervention or system restart.

   • Common in general-purpose operating systems.

Banker’s Algorithm

• Purpose:
  Banker’s Algorithm is a deadlock avoidance technique that ensures the system remains in a safe state by carefully allocating resources.

• Key Concepts:

  • Safe State: A state where there is at least one sequence of process execution that can complete without causing deadlock.

  • Unsafe State: A state where no such sequence exists; risk of deadlock is possible.

• Data Structures Used:

  • Available: Vector showing the number of available resources of each type.

  • Max: Matrix specifying the maximum demand of each process for each resource.

  • Allocation: Matrix showing the current allocation of resources to each process.

  • Need: Matrix showing the remaining resource needs of each process (Need = Max - Allocation).

• How It Works:
  When a process requests resources, the algorithm checks if granting the request keeps the system in a safe state. If yes, resources are allocated; otherwise, the process must wait.

• Steps:

  1. Check if request ≤ Need (process cannot request more than its declared maximum).

  2. Check if request ≤ Available (resources must be available).

  3. Temporarily allocate requested resources and check system state using the safety algorithm.

  4. If safe, allocation is committed; if unsafe, the process waits.

• Benefit:
  Banker’s Algorithm prevents deadlocks by avoiding unsafe states, ensuring smooth process execution.

Deadlock Detection: Resource Allocation Graph

Deadlock detection using the Resource Allocation Graph (RAG) involves representing processes and resources as nodes in a directed graph to identify the presence of deadlocks. In this graph, processes are depicted as circles and resources as squares. An edge from a process node to a resource node indicates that the process has requested that resource, while an edge from a resource node to a process node indicates that the resource has been allocated to that process. For systems where each resource has only one instance, a cycle in the graph directly implies a deadlock, since the cycle represents a closed chain of processes each waiting for a resource held by the next. However, in systems with multiple instances of resources, the presence of a cycle does not necessarily mean a deadlock exists; further analysis is needed to confirm deadlock. The detection algorithm periodically examines the RAG to check for cycles and, if found, initiates recovery procedures to resolve the deadlock.

Recovery from Deadlock

Recovery from deadlock involves taking actions to break the deadlock cycle once it has been detected. There are two main approaches to recovery: process termination and resource preemption.

1. Process Termination: In process termination, the system can terminate one or more processes involved in the deadlock to free their resources. This can be done by terminating all deadlocked processes or one at a time until the deadlock is resolved. Terminating all is simple but costly, while terminating processes selectively requires careful consideration to minimize impact.
2. Resource Preemption: In resource preemption, the system temporarily takes resources away from some processes and reallocates them to others to break the deadlock. However, this approach can lead to inconsistent states and requires mechanisms to roll back processes to safe states. Recovery strategies often involve trade-offs between system performance and data integrity, and the chosen method depends on the system’s requirements and criticality.

Questions for Practice:

Short answer

1. Define deadlock and list the four necessary conditions for a deadlock to occur.

2. Differentiate between preemptable and non-preemptable resources with examples.

3. Explain the Resource Allocation Graph and how it is used in deadlock detection.

4. Describe the Ostrich Algorithm and discuss when it is used.

5. Briefly explain the Banker’s Algorithm and its purpose in deadlock avoidance.

6. List and explain the main methods used for handling deadlocks.

7. What is a safe state in the context of deadlock avoidance?

8. Describe two techniques used to recover from deadlock once it is detected.

9. Explain why deadlock prevention may lead to inefficient resource utilization.

10. What is the difference between deadlock detection and deadlock avoidance?

Long answer question.

1. Explain the four necessary conditions for deadlock with examples and discuss how each condition can be prevented.

2. Discuss the Resource Allocation Graph model. How does it help in detecting deadlocks in systems with single-instance and multiple-instance resources?

3. Describe the Banker’s Algorithm in detail. Explain how it ensures the system remains in a safe state with a suitable example.

4. Compare and contrast the four methods of handling deadlocks: prevention, avoidance, detection and recovery, and ignoring deadlocks.

5. Explain the process of deadlock detection and recovery. Discuss the pros and cons of process termination and resource preemption as recovery methods.

6. Describe the Ostrich Algorithm and justify its use in some operating systems despite the risk of deadlocks.

7. A system has three resources A, B, and C with multiple instances. Explain how deadlocks can be detected using the Resource Allocation Graph and why cycle detection alone may not be sufficient.

8. Explain deadlock prevention methods with a focus on breaking each of the four necessary conditions. Discuss their impact on system performance.

9. Illustrate with an example how the Banker’s Algorithm checks for safe and unsafe states when granting resource requests.

10. Discuss the trade-offs involved in choosing between deadlock avoidance and deadlock detection techniques in an operating system.