7.deadlocks.md

Deadlock

A deadlock occurs when two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes.

Characterizing Deadlocks

• Four necessary conditions for deadlocks
  • Mutual exclusion
    • only one process at a time can use a resource
  • Hold and wait
    • a process holding at least one resource is waiting to acquire additional resources held by other processes
  • No Preemption
    • a resource can be released only voluntarily by the process holding it, after that process has completed its task
  • Circular Wait
    • there exists a set {P0, P1, …, Pn} of waiting processes such that
      • P0 is waiting for a resource that is held by P1,
      • P1 is waiting for a resource that is held by P2, …,
      • Pn–1 is waiting for a resource that is held by Pn,
      • Pn is waiting for a resource that is held by P0

Resource allocation graph

A set of vertices V and a set of edges E.

• V is partitioned into two types:
  • P = {P1, P2, …, Pn}, the set consisting of all the processes in the system
  • R = {R1, R2, …, Rm}, the set consisting of all resource types in the system
• Request edge – directed edge P1 → Rj
• Assignment edge – directed edge Rj → P
• Examples
  • No Deadlock
    • 
  • Deadlock
    • 
  • Cycle but no deadlock
    • 

Basic Facts

• If graph contains no cycles ⇒ no deadlock
• If graph contains a cycle ⇒
  • if only one instance per resource type, then deadlock
  • if several instances per resource type, possibility of deadlock

Three methods for dealing with deadlocks:

• Prevention or avoidance
  • Ensure that system will never enter a deadlock state
    • Ensure that at least one of the necessary conditions never holds
    • Have a priori information on how each process will be utilizing the resources to decide whether or not the system is the safe state for each resource allocation.
• Detection
  • Allow the system to enter deadlock state, detect it, and then recover
• Ignorance
  • Ignore the problem completely assuming that deadlocks never occur in the system.
  • used by most operating systems, including UNIX (mostly because overhead)