CHAP4

• Deadlock


  Two or more jobs placed in HOLD state, waiting for unavailable vital resource, causing the system to come to a standstill
• Livelock


  Two people on a landing, each time one takes a step to the side, the other mirrors that step, neither moves forward
• Starvation


  People wait on landing for a break, but the break never comes
• Deadlock is more serious than starvation, affects the entire system, and is more prevalent in interactive and real-time systems
• Seven cases of deadlock or livelock

  • Deadlocks on file requests
  • Deadlocks in databases
  • Deadlocks in dedicated device allocation
  • Deadlocks in multiple device allocation
  • Deadlocks in spooling
  • Deadlocks in a network
  • Deadlocks in disk sharing
• Necessary conditions for deadlock or livelock

  • Mutual exclusion
  • Resource holding
  • No preemption
  • Circular wait
• Resolving deadlock requires removing one of the necessary conditions
• Directed graphs


  Used to model deadlocks, with circles representing processes and squares representing resources
• Three graph scenarios to help detect deadlocks

  • No deadlock (resources released before next process request)
  • Deadlock (processes waiting for resource held by another)
  • No deadlock (resources released before deadlock)
• No deadlock


  • Resources released before next process request
• Scenario 1


  Events shown in directed graph in Figure 5.8

  
• The system will stay free of deadlocks if each resource is released before it is requested by the next process
• Deadlock


  • Processes waiting for resource held by another
• Scenario 2


  Sequence of events shown in two directed graphs in Figure 5.9
• The system becomes deadlocked when P3 requests R1. Notice the circular wait.
• No deadlock


  • Resources released before deadlock
• Scenario 3


  Sequence of events shown in directed graph in Figure 5.10

  
• After event 4, P2 is blocked because P1 is holding on to R1. However, event 5 breaks the deadlock.
• Resources of same type

  • Allocated individually or grouped in same process
  • Allocated individually or grouped in different process
• Strategies for Handling Deadlocks

  • Prevention
  • Avoidance
  • Detection
  • Recovery
• Prevention


  • Prevent occurrence of one condition
  • Mutual exclusion
  • Resource holding
  • No preemption
  • Circular wait
• Avoidance


  • Avoid deadlock if it becomes probable
  • System knows ahead of time sequence of requests associated with each active process
  • Dijkstra's Bankers Algorithm
• Banker's Algorithm


  • No customer granted loan exceeding bank's total capital
  • All customers given maximum credit limit
  • No customer allowed to borrow over limit
  • Sum of all loans will not exceed bank's total capital
• The bank is in a "safe state" when the remaining capital is sufficient for all outstanding loans
• The bank is in an "unsafe state" when the remaining capital is insufficient for all outstanding loans
• Operating systems deadlock avoidance assurances: Never satisfy request if job state moves from safe to unsafe
• Problems with Banker's Algorithm


  • Jobs must state maximum number needed resources
  • Requires constant number of total resources for each class
  • Number of jobs must remain fixed
  • Possible high overhead cost
  • Resources not well utilized
• Detection


  1. Build directed resource graphs

  2. Look for cycles

  3. Algorithm detecting circularity executed whenever appropriate

  4. Remove process using current resource and not waiting for one

  5. Remove process waiting for one resource class not fully allocated

  6. Repeat until all connecting lines removed
• The system is deadlock-free if the graph can be completely reduced
• The system is deadlocked if the graph cannot be completely reduced
• Recovery


  • Deadlock untangled once detected
  • System returns to normal quickly
  • Nearly all recovery methods have at least one victim
• Recovery methods


  • Terminate every job active in system
  • Terminate only jobs involved in deadlock
  • Identify jobs involved in deadlock and terminate one at a time
  • Interrupt jobs with record (snapshot) of progress
  • Select nondeadlocked job, preempt its resources, and allocate to deadlocked process
  • Stop new jobs from entering system
• Factors to consider when selecting victim

  • Job priority
  • CPU time used by job
  • Number of other jobs affected
  • Jobs modifying data
• Starvation


  Job execution prevented due to waiting for resources that never become available
• Starvation avoidance


  • Implement algorithm tracking how long each job has been waiting for resources (aging)
  • Block new jobs until starving jobs satisfied
• The dining philosophers problem illustrates the issue of starvation