Introduction to Deadlock

• When two or more processes are in a deadlock, they cannot go forward because they are both waiting for the other to relinquish a resource. 

• This situation leads to a halt in program execution, potentially affecting system performance and reliability.

• Deadlocks can occur in various environments, including operating systems, database management systems, and distributed computing systems.

• Understanding deadlock handling, recovery from deadlock, and how to detect deadlocks is essential for maintaining system stability.

Deadlock Handling Strategies

Deadlock Handling includes the following strategies:

Prevention

• Deadlock prevention focuses on designing the system to avoid one or more of the conditions that lead to deadlocks.

• Breaking the conditions: Deadlock can be avoided by ensuring that at least one of the four necessary conditions cannot occur.

Methods of Deadlock Prevention

• Mutual exclusion: In some cases, resources can be made sharable, reducing the chance of deadlock.

• Hold and wait prevention: Processes can be required to request all resources at once, ensuring that they either get all the resources they need or none at all, preventing a hold-and-wait scenario.

• No preemption: In some instances, preemption can be allowed by forcibly taking resources away from processes when necessary.

• Circular wait prevention: Impose an ordering on the resource types, forcing processes to request resources in a predefined order to avoid circular dependencies.

Banker's Algorithm for Deadlock Avoidance

• The Banker's Algorithm checks whether resource allocation will lead to a safe state before allocating the requested resources.

• The system can avoid deadlock scenarios by simulating the resource allocation and determining if all processes can be completed.

• This method ensures that deadlock is avoided but requires prior knowledge of resource needs and introduces overhead in resource management.

Recovery from Deadlock

Deadlock Detection and Recovery

• Unlike prevention or avoidance, deadlock detection allows the system to enter a deadlocked state but provides mechanisms to detect and recover.

• Recovery From Deadlock method is used in systems where deadlock situations are rare or when prevention and avoidance methods are too costly or complex.

How Deadlock Detection Works

• Deadlock detection algorithms are run periodically to check for circular wait conditions in the system.

• Wait-for graphs are often used to represent processes and resource dependencies. If a cycle is detected in the graph, a deadlock is present.

Techniques for Recovery from Deadlock

Process Termination:

• One recovery method is to terminate one or more of the processes involved in the deadlock.

• This can be done by either aborting all deadlocked processes (drastic but effective) or terminating them one by one until the deadlock is resolved.

• Choosing which process to terminate can be based on factors like process priority, the amount of resources used, or how long the process has been running.

Resource Preemption:

• Another method is to preempt resources from some processes and assign them to others to break the deadlock.

• Resource preemption involves taking resources away from processes, which can be challenging to implement because it requires the system to maintain the state of the preempted processes and restart them later.

Rollback:

• Suppose a process has been holding resources for a significant amount of time. In that case, the system may roll back the process to a previous checkpoint and restart it, releasing all the resources it holds.

• Rollback is proper when preemption or termination is not feasible, but it requires the system to support process checkpointing.

Costs and Challenges of Recovery Methods

• Recovery from deadlock often involves significant overhead through resource preemption or rolling back processes.

• Termination or preemption can lead to data inconsistency or loss of work if not handled properly.

• Selecting the optimal process for termination or preemption requires complex decision-making, often involving trade-offs between system performance and fairness.

Deadlock Detection

When to Use Deadlock Detection

• Detection is typically used in systems where deadlocks are rare but cannot be entirely prevented or avoided.

• Useful in environments where resources are frequently requested and released and where implementing avoidance strategies is impractical due to dynamic resource needs.

Algorithms for Deadlock Detection

• Detection algorithms typically involve building a wait-for graph, where nodes represent processes and edges represent resources being waited for.

• The system periodically scans the wait-for graph for cycles, which indicates the presence of deadlock.

Wait-For Graph Method

• A node represents each process in the system.

• An edge is drawn from process A to process B if process A is waiting for a resource that process B holds.

• A cycle in this graph indicates a deadlock, as the processes involved are mutually waiting on each other.

Frequency of Detection

• Detection algorithms can be run regularly or when resource utilization exceeds certain thresholds.

• The Deadlock Detected frequency depends on the likelihood of deadlock and the system's tolerance for downtime or delays.

Pros and Cons of Deadlock Detection

Advantages:

• Deadlock detection allows for more flexible resource management since it doesn't require strict ordering or prevention mechanisms.

• It can be used in systems where resource usage patterns are unpredictable or constantly changing.

Disadvantages:

• Detection introduces overhead, as the system must periodically check for deadlocks.

• Resolving detected deadlocks can be costly, especially if preemption or process termination is required.

Balancing Deadlock Handling Approaches

• Choosing between prevention, avoidance, detection, and recovery depends on system requirements and trade-offs between efficiency, resource utilization, and system complexity.

• Prevention is proactive but may limit flexibility, while avoidance requires knowledge of resource needs.

• Detection and recovery allow for more flexible resource allocation but involve dealing with the consequences of a deadlock after it occurs.