Operating Systems - Deadlocks Notes

Operating Systems - Deadlocks Notes

Introduction to Deadlocks

• Definition: A deadlock is a situation where a set of processes cannot proceed because each one is waiting for a resource held by another process.

• Example:

  • Two Tape Drives:

    • Processes P1 and P2 each have one tape drive and need another to proceed. Both are waiting indefinitely.

  • Semaphores:

    • Processes attempting to wait on semaphores in an interdependent loop can lead to deadlock (e.g., waiting for A and B).

• Real-World Analogy:

  • Bridge Crossing: Cars from both directions wait on a one-lane bridge, causing a deadlock until one car backs off to let the other cross.

System Model and Resource Types

• Resource Types: Resources can be physical (printers, CPU) or logical (files, semaphores).

• Pre-emptible vs Non-preemptible:

  • Pre-emptible resources can be taken back without issue, such as memory.

  • Non-preemptible resources, like printers, cannot be forcibly reassigned.

• Resource Management:

  • Processes must request resources, use them, and then release them.

Necessary Conditions for Deadlock

1. Mutual Exclusion: Only one process can use a resource at a time.

2. Hold and Wait: Processes holding resources can request additional resources.

3. No Preemption: Resources cannot be forcibly taken from a process.

4. Circular Wait: A cycle of processes exists, each waiting for a resource held by another in a circle.

Deadlock Modelling

• Graph Representation: A system can be represented as a directed graph:

  • Nodes represent processes and resources.

  • Edges signify request (Pi → Rj) and assignment (Rj → Pi).

Conditions Indicating Deadlock

• Cycle Detection in Graphs:

  • If a directed graph has cycles, deadlock may exist depending on resource instance allocations.

Handling Deadlocks

Methods of Handling

1. Prevention: Ensure that the system never enters a deadlock state.

2. Avoidance: Allow deadlocks but prevent their occurrence through resource management strategies.

3. Detection and Recovery: Periodically check for deadlocks and recover if they occur.

4. Ignoring the Problem: Accepting that deadlocks are minimal and ignoring in non-critical systems (Ostrich algorithm).

Deadlock Prevention Techniques

1. Deny Mutual Exclusion: Not feasible for all resources.

2. Deny Hold and Wait: Prevent processes from holding resources while requesting others.

   • Reduce resource utilization, risk of starvation.

3. Allow Preemption: Force a process to release resources if it cannot get what it needs.

4. Deny Circular Wait: Implement a resource order for requests to avoid cycles.

Deadlock Avoidance

• Banker's Algorithm:

  • Processes declare max resource needs; the system checks for safe states before allocation. A system is safe if it can guarantee all processes can finish.

Recovery from Deadlocks

• Termination:

  • Terminate all deadlocked processes or one at a time based on a set priority.

• Resource Preemption:

  • Temporarily remove resources from one process to resolve deadlocks.

Combined Approach to Handling Deadlocks

• Utilize prevention, avoidance, and detection techniques as appropriate for different resource types and states.

Key Concepts

• Safe State: Condition where the system can allocate resources in a way that allows all processes to finish.

• Unsafe State: Condition where resource allocation could potentially lead to a deadlock.

• Detection Algorithms: Used periodically to check for deadlock occurrence and decide recovery measures.

Introduction to Deadlocks

• Definition: A deadlock is a situation where a set of processes cannot proceed because each one is waiting for a resource that is currently held by another process. As a result, none of the processes can continue their execution.

• Example:

  • Two Tape Drives: Processes P1 and P2 each hold one tape drive and require an additional tape drive to proceed with their tasks. As each process is holding a resource and waiting on the other, they become deadlocked and cannot make progress.

  • Semaphores: A common scenario leading to deadlocks occurs when processes are organized in an interdependent loop, where each process waits for a semaphore held by another process. For instance, if process A is waiting for resource X and process B is waiting for resource Y, both resources may be indefinitely unavailable.

• Real-World Analogy:

  • Bridge Crossing: An appropriate analogy for understanding deadlocks is the scenario of cars trying to cross a one-lane bridge from both directions. If cars from opposing directions reach the bridge simultaneously, they may become completely halted, unable to proceed until one vehicle backs off to let the other cross, mirroring how processes can get stuck in a deadlock.

System Model and Resource Types

• Resource Types: Resources are essential components in computing that can be categorized as either physical (e.g., printers, CPU, disk drives) or logical (e.g., files, semaphores, databases). Each type of resource can have significant implications for the performance and operation of processes.

• Pre-emptible vs Non-preemptible:

  • Pre-emptible resources can be reclaimed without any negative consequences, such as memory or CPU time slices, which can be allocated to other processes as needed.

  • Non-preemptible resources, like printers or locks, cannot be forcibly taken back; they must be voluntarily released by the owning process. This distinction is critical in understanding potential deadlocks in system resource allocation.

• Resource Management: Processes must follow a systematic approach to resource management: they must formally request resources before using them, utilize the resources as required, and then ultimately release them back to the system for future use.

Necessary Conditions for Deadlock

There are four conditions that are necessary for a deadlock to occur within a system:

1. Mutual Exclusion: Only one process can use a resource at any given time. If another process requests that resource, it must wait until the resource is released.

2. Hold and Wait: Processes that are holding at least one resource are allowed to request additional resources. This creates a situation where processes can be halted while still holding resources.

3. No Preemption: Resources cannot be forcibly removed from a process that is holding them. A resource must be voluntarily released by the process holding it.

4. Circular Wait: A scenario exists where a group of processes are each waiting for a resource held by the next process in the cycle. This condition creates a cycle of dependence, reinforcing the deadlock.

Deadlock Modelling

• Graph Representation: A system can be visually represented using a directed graph, where:

  • Nodes correspond to processes and resources (e.g., Processes P1, P2, and Resource R1).

  • Edges illustrate relationships, including requests (Pi → Rj) and assignments (Rj → Pi), providing a clear picture of resource allocation and potential deadlock scenarios.

Conditions Indicating Deadlock

• Cycle Detection in Graphs: One effective method for identifying potential deadlocks is to detect cycles within the directed graph. If a cycle is present, it indicates that deadlock may exist, especially if the resources are currently allocated in a way that satisfies the wait conditions.

Handling Deadlocks

Methods of Handling

Several strategies can be implemented to handle deadlocks effectively:

1. Prevention: Employ approaches that ensure the system cannot enter a deadlock state by addressing the necessary conditions of deadlock.

2. Avoidance: Allow the occurrence of deadlocks but take proactive measures to prevent their occurrence through intelligent resource management strategies. This may involve the careful allocation of resources.

3. Detection and Recovery: Regularly check for deadlocks and design mechanisms to recover from them when they occur, which may involve process termination or resource reassignment.

4. Ignoring the Problem: In some cases, particularly within non-critical systems, the overhead of deadlock management may be deemed too costly, leading to the acceptance of deadlocks as a rare occurrence (also known as the Ostrich algorithm).

Deadlock Prevention Techniques

1. Deny Mutual Exclusion: This technique is often impractical, as some resources inherently require exclusive access.

2. Deny Hold and Wait: Prevent processes from holding resources while awaiting additional ones. This can reduce resource utilization and increase the risk of starvation for some processes.

3. Allow Preemption: Implement policies that enable a process to be interrupted and temporarily release its resources if it is unable to acquire additional resources needed for execution.

4. Deny Circular Wait: Establish a strict order for resource requests that prevents circular dependencies among processes, which is one of the key conditions for a deadlock.

Deadlock Avoidance

• Banker's Algorithm: This algorithm assists in determining whether to allocate resources to a process by requiring that processes declare their maximum resource needs a priori. The system evaluates the current state to ensure it can maintain a safe state, where all processes can proceed to completion without deadlock.

Recovery from Deadlocks

• Termination: One method for recovering from a deadlock is to terminate all processes involved in the deadlock or to terminate them one by one based on priority or resource needs.

• Resource Preemption: Resources may be temporarily removed from certain processes to resolve the deadlock, reassigning them as necessary to ensure system progress.

Combined Approach to Handling Deadlocks

• Practical solutions often involve integrating prevention, avoidance, and detection techniques tailored to suit different resource types and the specific states of the system to effectively manage deadlocks without sacrificing performance.

Key Concepts

• Safe State: A state in which the system can allocate resources in such a way that all processes can complete their execution successfully without leading to a deadlock.

• Unsafe State: A state that may lead to potential deadlock scenarios if resources are allocated beyond the existing system capabilities.

• Detection Algorithms: Algorithms employed to periodically assess for deadlock occurrences, evaluate resource allocation patterns, and implement recovery measures when necessary.