Deadlocks

• Conditions
  • Mutual exclusion in resource use
  • Processes may hold and wait
  • There is no resource preemption
  • There is a circular wait condition
• Handling Strategies
  • Ignore
  • Detect and recover
  • Dynamic avoidance
    • Tries to prevent entering unsafe states
    • Not usually practical
    • Assumes
      • No resources fail
      • No process needs more than available resources
      • Any process that gets the resources it needs will complete
    • Bankers Algorithm
      • Identifies safe states
      • Do a matrix model using the maximum number of resources
  • Structural prevention
• Modeling
  • Holt Graph
    • Graph processes and resources
    • Arrow point to what something needs
    • If there is a circle, a deadlock is possible
      • Keep removing leaves and if you are left with nodes at the end, you have a potential deadlock
      • Depth-first traversal can detect cycles (if a node appears more than once)
        • Only for unique resources
        • Not efficient
    • Can point out how to fix deadlocks by reordering accesses to break the cycle
  • Matrices
• Prevention
  • Avoid mutual exclusion
    • Can abstract mutually exclusive resources at the OS level so there is a hidden job queue
  • Avoid hold and wait
    • Deny process holding a lock from making additional requests
    • Require all requests for locks to be simultaneous
    • Multi resource locks
    • One option: use a lock server
  • Avoid No Preemption
    • Two-phase locking
      1. Growth: Attempt to get all required locks
      2. Shrinking: If failed, release all locks. If acquired, do work then release all locks
  • Avoid Circular Wait
    • Dining philosopher
    • Order all resources
    • Require requests to be made in order
• Variants
  • Livelock
    • Where a request for an exclusive lock is denied repeatedly as many overlapping shared locks keep on interfering with each other
    • The processes keep on changing their status, preventing them from completing the task
    • They seem alive but they are dead inside
    • Two-phase locks can cause deadlocks
      • Technically not deadlocked, but no progress can be made
  • Starvation
    • When one or more processes never make progress, but some do