Deadlocks

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.

Algorithms:

• 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