Deadlock is when two or more processes are unable to proceed because each is waiting for the other to release resources.

<aside> 💡 Consider an example when two trains are coming toward each other on the same track and there is only one track, none of the trains can move once they are in front of each other. This is a practical example of deadlock.

</aside>

Conditions for a Deadlock:

• Mutual Exclusion: When only one process can use a resource.
• Hold and wait: A process is waiting for a resource while holding to at least one other resource.
• No preemption: A resource cannot be taken by another process until the process releases the resource.
• Circular wait: A set of processes waiting for each other in a circular form.

Methods for handling deadlocks:

1. Deadlock prevention or avoidance
2. Deadlock recovery
3. Deadlock ignorance

Deadlock prevention

The goal of deadlock prevention is to avoid fulfilling the conditions for a deadlock.

• Mutual exclusion: Only lock non-shareable resources and ensure shareable data (like read-only files) is available for multiple processes to access.
• Hold and wait: We must guarantee that a process requesting for a resource is not holding onto other resources.
• No preemption: Processes requesting for a resource held by a different process must preempt their current resource, and request for the resources it needs after a while. Can cause Live Lock. A situation where two or more processes continuously changing their state in response to each other without making any real progress.
• Circular wait: Organize the resources acquired by processes. Example, if there are r1 and r2, they must be sequential so that r1 is acquired first.

Deadlock avoidance

By using the strategy of “Avoidance”, we have to make an assumption of all the resources needed for the process before execution.

Deadlock recovery

Deadlock detection and recovery have two phases:

1. The first phase examines the state of the process, whether the deadlock is in the system or not.
2. If a deadlock is found, a deadlock recovery algorithm is executed.

Deadlock detection and recovery ensures data integrity, but degrades performance.

Deadlock recovery techniques

1. Manual intervention: When a deadlock is detected, one option is to inform the operator and let them handle the situation manually.
2. Automatic recovery: This approach enables the system to recover from deadlock automatically. It involves breaking the deadlock cycle by either aborting processes or preempting resources.
3. Process termination: We can terminate all deadlocked processes or abort one process at a time. However, terminating all deadlocked processes can cause in partial computation loss. Alternatively, terminating one process at a time can cause overhead as a deadlock-detection algorithm must be invoked after each process termination.
4. Resource preemption

Resource preemption involves choosing which resources and processes should be preempted to break the deadlock. If a resource is preempted from a process, the process cannot continue its normal execution as it lacks the required resource.

Rolling back the process to a safe state and restarting it is a common approach. Determining a safe state can be challenging, leading to the use of total rollback, where the process is aborted and restarted from scratch.

Deadlock ignorance

If a deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.