Havender in his pioneering work showed that since all four of the conditions are
necessary for deadlock to occur, it follows that deadlock might be prevented by
denying any one of the conditions.
- Elimination of “Mutual Exclusion” Condition
The mutual exclusion condition must hold for non-sharable resources. That is,
several processes cannot simultaneously share a single resource. This condition
is difficult to eliminate because some resources, such as the tap drive and
printer, are inherently non-shareable. Note that shareable resources like
read-only-file do not require mutually exclusive access and thus cannot be
involved in deadlock.
- Elimination of “Hold and Wait” Condition
There are two possibilities for elimination of the second condition. The first
alternative is that a process request be granted all of the resources it needs
at once, prior to execution. The second alternative is to disallow a process
from requesting resources whenever it has previously allocated resources. This strategy requires that all of the resources a process will need must be
requested at once. The system must grant resources on “all or none” basis.
If the complete set of resources needed by a process is not currently available,
then the process must wait until the complete set is available. While the
process waits, however, it may not hold any resources. Thus the “wait for” condition is denied and deadlocks simply cannot occur. This strategy can lead to serious waste of resources. For example, a program requiring ten tap drives must request and receive all ten
derives before it begins executing. If the program needs only one tap drive to
begin execution and then does not need the remaining tap drives for several
hours. Then substantial computer resources (9 tape drives) will sit idle for
several hours. This strategy can cause indefinite postponement (starvation). Since not all the
required resources may become available at once.
- Elimination of “No-preemption” Condition
The nonpreemption condition can be alleviated by forcing a process waiting for a
resource that cannot immediately be allocated to relinquish all of its currently
held resources, so that other processes may use them to finish. Suppose a system
does allow processes to hold resources while requesting additional resources.
Consider what happens when a request cannot be satisfied. A process holds
resources a second process may need in order to proceed while second process may
hold the resources needed by the first process. This is a deadlock. This
strategy require that when a process that is holding some resources is denied a
request for additional resources. The process must release its held resources and, if necessary, request them
again together with additional resources.
Implementation of this strategy denies the “no-preemptive” condition
High Cost When a process release resources the process may lose all its work to that
One serious consequence of this strategy is the possibility of indefinite
postponement (starvation). A process might be held off indefinitely as it
repeatedly requests and releases the same resources.
- Elimination of “Circular Wait” Condition
The last condition, the circular wait, can be denied by imposing a total
ordering on all of the resource types and than forcing, all processes to request
the resources in order (increasing or decreasing). This strategy impose a total ordering of all resources types, and to require
that each process requests resources in a numerical order (increasing or
decreasing) of enumeration.
With this rule, the resource allocation graph can never have a cycle.
For example, provide a global numbering of all the resources, as shown
Now the rule is this: processes can request resources whenever they want to, but
all requests must be made in numerical order. A process may request first
printer and then a tape drive (order: 2, 4), but it may not request first a
plotter and then a printer (order: 3, 2). The problem with this strategy is that
it may be impossible to find an ordering that satisfies everyone.