Deadlock

  • Resources
  • why do deadlocks occur?

Resource

  • something a process or thread wants
  • e.g.
    • printer
    • semaphore/lock
    • memory
    • database table
  • processes need to access resources in a reasonable order
  • 2 types:
    • preemptable: can be taken away with no ill effects
    • nonpreemptable: will cause the process to fail if taken away
  • sequence of events required to use:
    • request
    • use
    • release
  • can’t use the resource if request is denied
    • requesting process has options:
      • block
      • continue without it
      • fail with error code

Occurances

Deadlocks occur when processes are granted exclusive access to devices or software constructs, and each deadlocked process needs a resource held by another deadlocked process

4 conditions for deadlock:

  • mutual exclusion
    • each resource is assigned to at most one process
  • hold and wait
    • a process holding resources can request more resources
  • no preemption
    • previously granted resources cannot be forcibly taken away
  • circular wait
    • there must be a chain of 2 or more processes where each is waiting for a resource held by the next member of the chain

We can model them using resource allocation graphs - draw an arrow from a resource to a process if the process hold it, draw an arrow from the process to the resource if it wants it

We get a deadlock if there is a circle in the graph

Dealing With It

OS solutions:

  • do nothing: the ostrich algorithm
    • reasonable if it’s rare and high cost to prevent
  • detect deadlock and recover from it
    • use a graph to detect deadlocks
    • kill a process in the deadlock circle
  • dynamically avoid deadlock
    • careful resource allocation
  • prevent deadlock
    • remove at least 1 of the 4 conditions
_images/ex1.png

In this image, process 3 is not deadlocked, but process 2 is deadlocked

Recovery

  • preemption
    • take a resource from another process (depends on nature of resource/process)
  • rollback
    • checkpoint a process periodically
    • use saved state to restart process if in deadlock
    • may present a problem if the process affects a lot of external things
  • kill process
    • kill one in the deadlock cycle
    • other process can loot its corpse
    • try and choose a process that can be rerun from the start - pick one that hasn’t run too far already

Prevention

We can prevent deadlock by removing one of the conditions:

Eliminating mutex

  • some devices can be spooled/queued
    • e.g. printer - only the printer daemon uses printer resource
    • eliminates deadlock for printer
  • not all devices though
  • principle:
    • avoid assigning resource when not absolutely necessary
    • as few processes as possible actually claim resource

Attacking Hold/Wait

  • require processes to request resources before starting
    • a process never has to wait for what it needs
  • can add problems
    • a process may not know the resources it requires
    • also ties up resources other processes could be using
  • variation: a process must give up all resources before making a new request
    • process is then granted all prior resources as well as new ones
    • problem: what if someone grabs the resources in the meantime?

Attacking no-preemption

  • just forcibly take away resources
  • No one does this apparently

Attacking circular wait

  • assign an order to resources
  • always require resources in numerical order
    • need not acquire them all at once
  • circular wait is prevented
    • a process holding resource n can’t wait for resource m if m < n
    • no way to complete a cycle
      • place processes above the highest resource they hold and below any they require
      • all arrows point up
_images/ex2.png

Livelock

Sometimes, processes can still run, but not make progress

  • e.g. 2 processes want to use resourves A and B
    • P0 gets A, P1 gets B
    • they realize that they will deadlock if they continue
    • P0 drops A, P1 drops B
    • P0 gets B, P1 gets A
    • this continues…
  • e.g. ethernet transmission collisions
    • multiple processes retrying at the exact same time…