Resource deadlock: When processes are infinitely waiting for each other for a resource to be released

Conditions for resource deadlocks:

  1. Mutual exclusion: each resource can be used by at most one process
  2. Hold and wait: processes holding resources can request multiple resources
  3. No preemption: resources granted earlier can not be taken away
  4. Circular chain of requests: One process is waiting for another which is waiting on another etc...

Resource Allocation Graph: processes circles and resources square. Holding a resource: edge from resource to process. Requesting a resource: edge from process to resource. Cycles in this graphs are deadlocks.


  • Graph cycle detection using DFS
  • Detection with multiple resources of each type
    1. Look for unmarked processes $i$ where $R_i \leq A$
    2. Add $C_i$ to $A$ and mark processes
    3. Terminate if so process found
  • Banker's algorithm: checks if the next state is safe. With multiple resources it

Safe sate: there exists an scheduling order in which every process can run to completion (even if all of them request their maximum number of resources at once)

Deadlock recovery #

  1. Ignoring the problem (used by Windows/Linux)
  2. Preemption
  3. Rollback
  4. Killing processes

Other things #

Two-phase locking: useful in databases. A process tries to lock all the records it needs first. If a record is already locked it releases all locks and tries again after some time. Livelock: when processes try to to get the same lock at the same time, no process is blocked so it is not a deadlock Communication deadlock: in networked systems, solved by resending a message after a timeout