Tom Kelliher, CS42
Oct. 18, 1996
- Processes competing for resources. Process model:
request some resources;
release some resources;
- Resource: anything a process may block on. Examples:
- Device (disk read/write, printer, etc.)
Two types of resources:
- Serially reusable resources: printer, tape drive, CPU, etc.
- Consumable resources: semaphores, messages, etc.
semaphore A(0), B(0);
Process 1 is waiting for process 2 is waiting for process 1...
System has five tape drives.
Resource allocation graph.
Why aren't these sufficient conditions?
- Mutual exclusion --- A resource is not sharable.
- Hold and wait --- A process is allowed to hold a resource while it's
waiting for other resources.
- No preemption --- A process cannot be forced to give up a resource.
- Circular wait --- P1 is blocked because of P2; P2 is blocked because
of P3; ...; Pn is blocked because of P1.
How does deadlock differ from starvation?
- Collections of resources of same type.
- Ignorance. More common than you'd think.
- Detection and recovery.
- Prevention --- Prevent one of the four necessary conditions.
- Avoidance --- Manage resources so that a deadlock never occurs:
Removal of one of the four necessary conditions.
- Share the resource.
- A process must release all resources before requesting more.
- Limitations? (Request everything at once or wait a lot.)
- Kernel forcibly reclaims resources.
- Impose a total order on all resources.
- Resource i may only be requested if process holds no resource
j with j > i.
- Determining the order.
- How does an ``out of order'' process proceed?
- Works for specific resources.
- No one mechanism is generally applicable.
Thomas P. Kelliher
Wed Oct 16 23:15:41 EDT 1996