Skip to content

Latest commit

 

History

History
62 lines (57 loc) · 2.5 KB

7.deadlocks.md

File metadata and controls

62 lines (57 loc) · 2.5 KB

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
      • No Deadlock
    • Deadlock
      • No Deadlock
    • Cycle but no deadlock
      • 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)