Module 5: Deadlocks

In a multiprogramming environment, multiple processes compete for a finite set of hardware and software resources. A deadlock occurs when two or more processes are permanently blocked because each process holds a resource that another process needs, and is waiting for a resource that the other process holds — meaning none of them can ever make progress.

The Four Coffman Conditions

A deadlock can arise if and only if all four of the following conditions hold simultaneously in the system:

1. Mutual Exclusion: At least one resource must be non-shareable. Only one process may use the resource at any given time.
2. Hold and Wait: A process must be currently holding at least one resource and simultaneously waiting to acquire additional resources held by other processes.
3. No Preemption: Resources cannot be forcibly seized from a process. They can only be released voluntarily by the holding process after completing its task.
4. Circular Wait: A closed chain of processes ${P_0, P_1, dots, P_n}$ exists such that $P_0$ is waiting for a resource held by $P_1$, $P_1$ is waiting for $P_2$, and $P_n$ is waiting for a resource held by $P_0$.

Operating systems approach deadlock management using two proactive strategies: Prevention (constraining resource requests to mathematically eliminate at least one Coffman condition) and Avoidance (dynamically assessing resource allocation states to ensure the system never enters an unsafe state).

Deadlock Prevention Techniques

• Eliminate Hold and Wait: Require processes to request all needed resources at once before starting execution. If any resource is unavailable, none are allocated. Drawback: Severely reduces resource utilization.
• Allow Preemption: If a process holding resources requests an unavailable resource, all of its currently held resources are preempted and returned to the free pool.
• Eliminate Circular Wait: Impose a strict global total ordering on all resource types (e.g., $F( ext{Disk}) = 1, F( ext{Printer}) = 2, F( ext{Tape}) = 3$). A process can only request resources in strictly increasing numerical order. Mathematically makes circular cycles impossible!

Deadlock Avoidance: Banker's Algorithm

Banker's Algorithm requires each process to declare its maximum possible resource claims in advance. When a process requests resources, the OS temporarily allocates them in memory and runs the Safety Algorithm:

If there exists an execution sequence $langle P_1, P_2, dots, P_n angle$ where each process can finish using currently available resources plus resources freed by previously finished processes, the state is Safe, and the allocation is granted. If no safe sequence exists, the process must wait.

If a system employs neither deadlock prevention nor avoidance, deadlocks may occur at runtime. In this environment, the operating system must periodically execute a Deadlock Detection Algorithm and invoke a recovery mechanism to restore normal operation.

Recovery Strategies in Detail

• Process Termination:
  • Abort all deadlocked processes: Guaranteed to break the deadlock immediately, but discards partial computations at great cost.
  • Abort one process at a time: Abort one victim, release its resources, re-run the cycle detection algorithm, and repeat until the deadlock is resolved.
• Resource Preemption:
  • Victim Selection: Determine which process has consumed the least CPU time and holds the most critical resources.
  • Rollback: Roll the victim back to a previously saved checkpoint rather than killing it outright.
  • Starvation Prevention: Ensure a process is not repeatedly selected as a victim by factoring victim count into cost metrics.