Chapter 7: Deadlock

Chapter 7: Deadlock

1. Deadlock in Multiprogramming

   • Definition: Two or more processes permanently waiting for each other to release resources. Each holds a resource and requests one held by another.
   • Example: P1 holds RA and wants RB; P2 holds RB and wants RA.
   • Four Necessary Conditions (all must be satisfied simultaneously):
     • Mutual Exclusion: At least one resource is non-sharable (only one process at a time).
     • Hold and Wait: A process holds at least one resource and waits for others.
     • Circular Wait: A cyclic chain of processes waiting for resources held by the next process in the chain.
     • No Preemption: Resources cannot be forcibly taken; only voluntarily released.

2. System Model

   • Processes & Resources: Multiprogramming environment, concurrent processes needing resource access.
   • Resources Examples: Physical (Printers, CPU), Logical (Files, Semaphores). Instances exist (e.g., 2 printers).
   • Process Cycle: Request -> Use -> Release.
   • Resource Types: Reusable (CPU, Memory, I/O devices - focus of chapter), Consumable (Signals, Messages).

3. Deadlock Handling Methods

   • Deadlock Prevention: Violating one of the four necessary conditions
     • Violating Mutual ExclusionViolating Mutual Exclusion
     • Violating Hold and Wait
     • Violating Circular Wait
     • Violating No Preemption
   • Deadlock Avoidance :System checks requests to ensure no unsafe state
   • Deadlock Detection & Recovery : Allows deadlock to occur, then detects and recovers

4. Dangers of Deadlock

   • Difficult to Diagnose/Debug
   • System Hang.
   • Reduced Throughput.
   • Resource Waste
   • Negative Impact on End-Users
   • System Instability.
   • Data/Work Loss.

5. Conclusion on Deadlock Handling

   • Avoidance: More efficient, but strict info requirements.
   • Prevention: Simple, but inefficient resource utilization.
   • Practice: Often a combination of methods. Prevention for critical resources, avoidance less common in general OS, detection & recovery for higher-level resources (e.g., databases).
   • Detection & Recovery: Most flexible, but high costs for detection/recovery.