Tom Kelliher, CS42
Oct. 21, 1996
- Permit deadlocks to occur, subsequently recover from them.
- Periodically run deadlock detection routines.
- Choose victim processes.
Algorithmic deadlock detection:
- n processes.
- m resource types.
- Available --- vector of length m.
- Allocation --- matrix of size n by m. Rows: processes; columns:
- Request --- matrix of size n by m.
- Finish --- vector of length n.
- Work --- vector of length m.
work = available;
for (i = 0; i < n; ++i)
finish[i] = false;
while there is an i such that finish[i] == false
and request[i] <= work
finish[i] = true;
work = work + allocation[i];
- Running time?
- How often should this be run? What are the tradeoffs?
- Any processes for which finish is false are deadlocked.
Using a resource allocation graph to detect deadlock (5 processes, 3
Retry with this request matrix:
Some recovery mechanisms:
- Terminate all deadlocked processes. What about threads (say
only some of the threads in a task are deadlocked)?
- Terminate processes one at a time.
- How do you choose the victim?
- When do you stop terminating victims?
- ``Rolling back'' a process and preempting resources.
- Process termination is drastic and messy.
- How much state has to be checkpointed?
Always maintain the system in a safe state:
Grant a resource request only if resulting state is safe.
- There exists a sequence in which all resource requests can be
- The operating system is in control of the resource situation.
- The operating system is no longer in control of the resource
- Processes are in control and can cause a deadlock.
Banker's algorithm used to maintain safe state.
Additional matrix required: Claim --- maximum number of each resource type
needed by each process.
For each resource request which can be satisfied
satisfy the request;
update state matrices;
turn all remaining claims into requests;
test for deadlock;
if simulation resulted in deadlock
defer the request;
grant the request;
Assume a maximum-claim serially reusable system with four processes and
three resource types. The claim matrix is given by
where denotes the maximum claim of process i for resource j.
The total units of each resource type are given by the vector .
The allocation of resources is given by the matrix
where denotes the number of units of resource j that are
allocated to process i.
Determine if the current state of the system is safe.
Determine if granting a request by process 1 for 1 unit of resource 1 can
be safely granted.
Determine if granting a request by process 3 for 6 units of resource 3 can
be safely granted.
- Some resources are easy to keep out of deadlock: CPU cycles, memory.
- No one ``silver bullet'' --- must combine mechanisms.
- Must tradeoff between cost of protection and cost of deadlock.
Thomas P. Kelliher
Fri Oct 18 11:11:45 EDT 1996