Deadlocks are a critical issue in operating systems, occurring when processes are stuck waiting for each other's resources. This section explores strategies to handle deadlocks, including prevention, avoidance, detection, and recovery methods.

Understanding deadlock management is crucial for efficient process scheduling and resource allocation. We'll examine the trade-offs between different approaches and how they impact system performance and reliability in various scenarios.

Deadlocks and their conditions

Defining deadlocks and their essential conditions

• Deadlock occurs when two or more processes cannot proceed due to waiting for resources held by each other
• Four necessary conditions for deadlock
  • Mutual exclusion allows only one process to use a resource at a time
  • Hold and wait enables processes to hold resources while requesting more
  • No preemption prevents forcible resource removal from processes
  • Circular wait creates a closed loop of processes waiting for resources
• Resource-Allocation Graphs (RAGs) model resource allocation and detect potential deadlocks

Visualizing and modeling deadlock scenarios

• RAGs use nodes to represent processes and resources
• Edges in RAGs show resource requests and allocations
• Cycle detection in RAGs indicates potential deadlock
• Example RAG:
  • Process P1 holds Resource R1 and requests R2
  • Process P2 holds R2 and requests R1
  • This forms a cycle, indicating a potential deadlock
• Practical deadlock scenario
  • Two processes need exclusive access to a printer and a scanner
  • Process A acquires the printer, Process B acquires the scanner
  • Process A now needs the scanner, Process B needs the printer
  • Neither can proceed, resulting in a deadlock

Deadlock handling methods

Preventive strategies

• Deadlock prevention ensures at least one necessary condition cannot occur
• Strategies target each condition:
  • Mutual exclusion eliminated by using sharable resources (spooling)
  • Hold and wait prevented by requiring all resource requests upfront
  • No preemption addressed by allowing resource reclamation
  • Circular wait avoided through resource ordering
• Implementation challenges
  • Reduced resource utilization
  • Increased system overhead
  • Potential starvation of processes

Avoidance techniques

• Deadlock avoidance requires knowledge of future resource requests
• Banker's Algorithm determines safe resource allocation states
  • Maintains information on available, allocated, and maximum required resources
  • Checks if granting a request leads to a safe state
  • Example:
    • System with 10 instances of a resource type
    • Process P1 can use max 5, currently holds 2
    • Process P2 can use max 7, currently holds 3
    • Remaining 5 instances ensure a safe state
• Limitations of avoidance
  • Requires advance knowledge of resource needs
  • May lead to unnecessary blocking of processes

Detection and recovery approaches

• Detection algorithms periodically check for deadlock occurrence
• Wait-for graph construction and cycle detection used to identify deadlocks
• Recovery techniques
  • Process termination eliminates deadlocked processes
  • Resource preemption forcibly reallocates resources
• Considerations for recovery
  • Minimizing the number of terminated processes
  • Ensuring system consistency after recovery
  • Avoiding starvation during repeated recoveries

Deadlock strategies: trade-offs

Comparing prevention and avoidance

• Prevention offers guaranteed deadlock-free operation but with lower resource utilization
• Avoidance allows higher resource utilization but requires more runtime overhead
• System characteristics influencing choice
  • Resource types and their sharability
  • Process behavior predictability
  • System performance requirements

Evaluating detection and recovery

• Detection and recovery provide higher resource utilization
• Potential drawbacks
  • Increased system complexity
  • Possible data loss during recovery
  • Performance impact of periodic detection
• Suitable for systems where deadlocks are rare

Factors influencing strategy selection

• Frequency of potential deadlock situations
• Cost of prevention or avoidance vs. impact of occasional deadlocks
• System reliability requirements
• Performance constraints
• Resource utilization goals
• Implementation complexity tolerance

Deadlock detection and recovery

Detection algorithms and techniques

• Periodic system state examination to identify deadlocks
• Wait-for graph construction and analysis
  • Nodes represent processes
  • Edges show resource wait relationships
  • Cycle in the graph indicates deadlock
• Detection frequency considerations
  • Too frequent leads to high overhead
  • Too infrequent may delay deadlock resolution

Recovery strategies and their implications

• Process termination approaches
  • Terminate all deadlocked processes
  • Terminate one process at a time until deadlock resolves
• Resource preemption methods
  • Select resources to preempt
  • Reallocate preempted resources to break deadlock
• Factors in selecting processes or resources
  • Process priority
  • Computation time invested
  • Resources held and needed
  • Number of processes to terminate
• Ensuring system consistency after recovery
  • Rolling back transactions
  • Restarting affected processes
  • Potential domino effect in roll-backs