http:^^www.cs.wisc.edu^~cs537-1^deadlock.html

This data set contains WWW-pages collected from computer science departments of various universities

starvation, if we always choose the same victim.
We can avoid this problem by always choosing the <em>youngest</em>
process in a cycle.
After being rolled back enough times, a process will grow old enough
that it never gets chosen as the victim--at the least by the time it
is the oldest process in the system.
If deadlock recovery involves killing a process altogether and restarting
it, it is important to mark the ``starting time'' of the reincarnated process
as being that of its ordinal version, so that it will look older that new
processes started since then.
<p>
When should we check for deadlock?
There is no one best answer to this question; it depends on the situation.
The most ``eager'' approach is to check whenever we do something that
might create a deadlock.
Since a process cannot create a deadlock when releasing resources,
we only have to check on allocation requests.
If the OS always grants requests as soon as possible, a successful
request also cannot create a deadlock.
Thus the we only have to check for a deadlock when a process becomes
blocked because it made a request that cannot be immediately granted.
However, even that may be too frequent.
The deadlock-detection algorithm can be quite expensive if there
are a lot of processes and resources, and if deadlock is rare,
we can waste a lot of time checking for deadlock every time a request
has to be blocked.
<p>
What's the cost of delaying detection of deadlock?
One possible cost is poor CPU utilization.
In an extreme case, if all processes are involved in a deadlock,
the CPU will be completely idle.
Even if there are some processes that are not deadlocked, they
may all be blocked for other reasons (e.g. waiting for I/O).
Thus if CPU utilization drops, that might be a sign that it's time
to check for deadlock.
Besides, if the CPU isn't being used for other things, you might
as well use it to check for deadlock!
<p>
On the other hand, there might be a deadlock, but enough non-deadlocked
processes to keep the system busy.
Thing's look fine from the point of view of the OS, but from the
selfish point of view of the deadlocked processes, things are definitely
<em>not</em> fine.
If the processes may represent interactive users, who can't understand why
they are getting no response.
Worse still, they may represent time-critical processes (missile defense,
factory control, hospital intensive care monitoring, etc.) where
something disastrous can happen if the deadlock is not detected and
corrected quickly.
Thus another reason to check for deadlock is that a process has been
blocked on a resource request ``too long.''
The definition of ``too long'' can vary widely from process to process.
It depends both on how long the process can reasonably expect to wait
for the request, and how urgent the response is.
If an overnight run deadlocks at 11pm and nobody is going to look
at its output until 9am the next day, it doesn't matter whether the
deadlock is detected at 11:01pm or 9:59am.
If all the processes in a system are sufficiently similar, it may
be adequate simply to check for deadlock at periodic intervals (e.g.,
one every 5 minutes in a batch system; once every millisecond in
a real-time control system).

<a name="prevention"> <h4> Deadlock Prevention </h4> </a>
<p>
There are four necessary condition for deadlock.
<ol>
<li><strong>Mutual Exclusion.</strong>
Resources are not sharable.
<li><strong>Non-preemption.</strong>
Once a resource is given to a process, it cannot be revoked until the
process voluntarily gives it up.
<li><strong>Hold/Wait.</strong>
It is possible for a process that is holding resources to request more.
<li><strong>Cycles.</strong>
It is possible for there to be a cyclic pattern of requests.
</ol>
It is important to understand that <em>all four</em> conditions are necessary
for deadlock to occur.
Thus if we can get rid of deadlock by removing any one of them.
<p>
There's not much hope of getting rid of condition (1)--some resources are
inherently non-sharable--but
attacking (2) can be thought of as a weak form of attack on (1).
By borrowing back a resource when another process needs to use it,
we can make it appear that the two processes are sharing it.
Unfortunately, not all resources can be preempted at an acceptable cost.
Deadlock recover, discussed in the previous paragraph, is an extreme form
of preemption.
<p>
We can attack condition (3) either by forcing a process to allocate all
the resources it will ever need at startup time, or by making it release
<em>all</em> of its resources before allocating any more.
The first approach fails if a process needs to do some computing before
it knows what resources it needs, and even it is practical, it may be
very inefficient, since a process that grabs resources long before
it really needs them may prevent other processes from proceeding.
The second approach (making a process release resources before allocating more)
is in effect a form of preemption and may be impractical for the same
reason preemption is impractical.
<p>
An attack on the fourth condition is the most practical.
The algorithm is called <em>hierarchical allocation</em>.
The first algorithm in
<!WA5><!WA5><!WA5><!WA5><a href="http://www.cs.wisc.edu/~cs537-1/project2.html">
Project 2
</a>
is an example of this approach.
If resources are given numbers somehow (it doesn't matter how the numbers
are assigned), and processes always request resources in increasing order,
deadlock cannot occur.
<dl>
<dt><b>Proof.</b>
<dd>
As we have already seen, a cycle in the waits-for graph is necessary
for there to be deadlock.
Suppose there is a deadlock, and hence a cycle.
A cycle consists of alternating resources and processes.
As we walk around the cycle, following the arrows, we see that each
process holds the resource preceding it and has requested the one
following it.
Since processes are required to request resources in increasing order,
that means the number of the resources must be increasing as we go
around the cycle.
But it is impossible for the number to keep increasing <em>all</em>
the way around the cycle; somewhen there must be drop.
Thus we have a contradiction:
Either some process violated the rule on requesting resources, or
there is no cycle, and hence no deadlock.
</dl>
<p>
More precisely stated, the hierarchical allocation algorithm is as follows:
<ol>
When a process requests resources, the requested resources must all 
have numbers <em>strictly greater</em> than the number of any resource
currently held by the process.
</ol>
This algorithm will work even if some of the resources are given the
same number.
In fact, if they are all given the same number, this rule reduces to
the ``hold-wait'' condition, so hierarchical allocation can also be
thought of as a relaxed form of the hold-wait condition.

<a name="avoidance"> <h4> Deadlock Avoidance </h4> </a>
<p>
The final approach we will look at is called <em>deadlock avoidance</em>.
In this approach, the OS may delay granting a resource request, even
when the resources are available, because doing so will put the
system in an <em>unsafe</em> state where deadlock may occur later.
The best-known deadlock avoidance algorithm is called the ``Banker's
Algorithm,'' invented by the famous E. W. Dijkstra.
<p>
This algorithm can be thought of as yet another relaxation of the
the hold-wait restriction.
Processes do not have to allocate all their resources at the start,
but they have to declare an upper bound on the amount of resources
they will need.
In effect, each process gets a ``line of credit'' that is can drawn on
when it needs it (hence the name of the algorithm).
<p>
When the OS gets a request, it ``mentally'' grants the request, meaning
that it updates its data structures to indicate
it has granted the request, but does not immediately let the requesting
process proceed.
First it checks to see whether the resulting state is ``safe''.
If not, it undoes the allocation and keeps the requester waiting.
<p>
To check whether the state is safe, it assumes the <em>worst</em>
case: that all running processes immediately request all the remaining
resources that their credit lines allow.
It then checks for deadlock using the algorithm
<!WA6><!WA6><!WA6><!WA6><a href="#deadlock_alg">above</a>.
If deadlock occurs in this situation, the state is unsafe, and the
resource allocation request that lead to it must be delayed.
<p>
In somewhat more detail, we maintain a matrix <samp><font color="0f0fff">M</font></samp> of unmet demand.
When a process <samp><font color="0f0fff">p</font></samp> starts, <samp><font color="0f0fff">M[p][r]</font></samp> is set to <samp><font color="0f0fff">p</font></samp>'s
``credit line'' for resource <samp><font color="0f0fff">r</font></samp>.
Whenever <samp><font color="0f0fff">p</font></samp> is granted some resource, not only is the amount
deducted from <samp><font color="0f0fff">A</font></samp>, it is also deducted from <samp><font color="0f0fff">M</font></samp>.
When a new request arrives, instead of running the
<!WA7><!WA7><!WA7><!WA7><a href="#deadlock_alg">deadlock algorithm</a>, we simply check whether
<samp><font color="0f0fff">A</font></samp> has enough resources on hand to grant the request immediately.
If so, we update our data structures to grant it (increase <samp><font color="0f0fff">C</font></samp>
and decrease <samp><font color="0f0fff">A</font></samp> and <samp><font color="0f0fff">M</font></samp>)
<pre><font color="0f0fff">
    for all r
        C[requester][r] += request[r];
        M[requester][r] -= request[r];
        A[r] -= request[r].
</font></pre>
We then test for safety.
To do that, we increase the <samp><font color="0f0fff">R</font></samp> matrix of requests by the entire
unmet demand <samp><font color="0f0fff">M</font></samp>
<pre><font color="0f0fff">
    for all p and r
        R[p][r] += M[p][r],
</font></pre>
run the
<!WA8><!WA8><!WA8><!WA8><a href="#deadlock_alg">deadlock algorithm</a>,
and restore <samp><font color="0f0fff">R</font></samp> and <samp><font color="0f0fff">M</font></samp> to their previous values.
If the deadlock algorithm reported that there was no deadlock, we
allow the requesting process to proceed--the request is safe.
Otherwise, we ``take back'' the allocation and add it to our list
of unmet allocations instead.
<pre><font color="0f0fff">
    for all r
        C[requester][r] -= request[r];
        M[requester][r] += request[r];
        A[r] += request[r].
        R[requester][r] += request[r];
</font></pre>

<hr>

<address>
<i>
<!WA9><!WA9><!WA9><!WA9><a HREF="mailto:[e-mail]">
[e-mail]
</a>
<br>
Thu Oct 31 15:38:53 CST 1996
</i>
</address>
<br>
Copyright &#169; 1996 by Marvin Solomon.  All rights reserved.

</body>

</html>