Resource Allocation Graph

no cycle IMPLIES no deadlock
deadlock IMPLIES cycle (necessary condition)
cycle IMPLIES maybe deadlock (but not sufficient condition)
single instance resource AND cycle IMPLIES deadlock
(necessary and sufficient)

Deadlock: Multiple Instance Resources
DEADLOCK:

NO DEADLOCK:

Methods for Handling Deadlock
1. never let deadlock occur
2. prevention: break one of the 4 conditions
3. avoidance: resources give advance notice of maximum use
4. let deadlock occur and do something about it
5. detection: search for cycles periodically
6. recovery: preempt processes or resources
7. don't worry about it (UNIX and other OS)
8. cheap: just reboot (it happens rarely)

Deadlock: Prevention
1. break mutual exclusion:
2. read-only files are shareable
3. but some resources are intrinsically nonshareable (printers)
4. break hold and wait:
5. request all resources in advance
6. request (tape, disk, printer) 7. release all resources before requesting new batch
8. request (tape,disk), release (tape,disk), request (disk,printer)
9. disadvantages: low resource utilization, starvation

Deadlock: Prevention
1. break no preemption:
2. process 1 requests resources already allocated to process 2:
3. process 1 forfeits its current resources
4. if process 2 is waiting for other resources: process 2 forfeits
5. used for resources whose state is easily saved/restored
6. CPU registers and memory space
7. not printers or tape drives
8. break circular wait:
9. order all resources by unique numbers (tape drives, etc.)
10. processes request resources in increasing order

Deadlock: Avoidance
1. processes give advance notice about maximum usage of resources
2. processes make actual requests when they need a resource
3. avoidance algorithm: allocate request only if it yields a safe state
4. a sequence of processes exists such that each process can still get their maximum in sequence
5. conceptually the processes could be run in this order

Deadlock: Example of Avoidance

assume that system has 12 tape drives