Chapter 7 Deadlocks
Finite resources & competing processes
Pattern - request, use, release
Conditions
Mutual exclusion - exclusive ownership of resource
Holding and waiting
No preemption of resources
Circular waiting
System resource-allocation graph
Resource & process nodes
Request & assignment edges
Look for cycle
No cycle - no deadlock
Cycle - maybe deadlock, maybe not
Deadlock prevention vs. deadlock avoidance
Prevention - eliminate one of the conditions
Mutual exclusion - sharable resources
Hold & wait - release before new allocation (starvation is possible)
No preemption - allow preemption (preemption causes problems such as restart)
Circular wait - impose an ordering on resource allocation
Deadlock avoidance
Safe states
Resource-allocation graph
Banker's algorithm
Deadlock detection - detect & recover
Algorithm
When to run?
Recovery
Process termination
All processes - expensive
One at a time - expensive since need to
rerun detection algorithm
Selecting a process - priority, time remaining, resources, how many process, etc.
Rollback, starvation