System Deadlocks

Coffman, et. al.

Conditions required for deadlock:

1) Mutual exclusion. A process claims exclusive control of a required resource.

2) Wait For condition. Processes hold resources already allocated to them while waiting for additional resources.

3) No preemption. A resource cannot be forcibly taken away from a process once that process has claimed the resource.

4) Circular Wait. A circular chain of processes exists where by each process in the chain is waiting to obtain a resource currently held by another process in the chain such that a process, in effect, is indirectly waiting for itself.

Dealing with Deadlock: 1) Prevention, or 2) Detection + Recovery

1) Prevention

a. Processes request all resources at once.

b. If process is denied a resource, it must release all its resources and try again later.

c. Impose a total ordering on resources, and processes must request resources in a sequence that respects the total ordering.

d. (Avoidance, as described by paper) Build a “waits-for” graph, and check that each action will not lead to an “unsafe state” after which deadlock will be inevitable, before executing the next action. Do not execute any action that leads to an “unsafe state” or a direct deadlock.

2) Detection

a. Build “waits-for” graph. Some extra accounting must be used if there exist many instances of a resource of a given type, and any of those instances can satisfy a request. Algorithm is quadratic in number of processes. (Paper claims there exists another paper which describes a linear algorithm if resource requests can be ordered and a count of the number of resources being requested can be maintained for each process.)

b. Abort one or more processes when deadlock is detected. (Paper describes algorithm that can be used to abort the process that incurs the least “cost.”) Preemption of a resource does not necessarily mean that the process needs to be “aborted” but this depends upon the type of resource.

Issues in deciding which approach to take:

· How often deadlock might occur? In many systems, deadlock is an exceptional case.

· What is the impact of deadlock? Will a user simply be inconvenienced and have to reboot, or will a deadlock in the control module of a rocket booster endanger the lives of astronauts? This might guide the decision of whether to use a detection/recovery scheme vs. an avoidance scheme.

· What will be the performance cost of an avoidance scheme? There may be a significant performance degradation.

· Some processes may need many resources to accomplish their goal. Will they be discriminated against because of this? How can we ensure they make forward progress? (while avoiding deadlock)

· If we do use a recovery scheme, how should we decide which process to abort? Maybe we should abort those processes that have made the least progress, or those processes whose progress won’t be impaired (freeze it and restart it later once I give it back the resource, assuming the resource is of the type for which this is acceptable)?

Deadlock prevention/avoidance is usually too expensive, and most of the time, detection/recovery schemes are used instead.

Note: two phase locking gives db systems serializability, but does not avoid deadlock. Strict two phase locking gives recoverability, but still does not avoid deadlock.