@ARTICLE {
Holt1971,
AUTHOR      = "Holt, R.C.",
TITLE       = "Comments on Prevention of System Deadlock",
JOURNAL     = "Communications of the ACM",
VOLUME      = "14",
NUMBER      = "1",
MONTH       = "January",
YEAR        = "1971",
PAGES       = "36 - 38",
READ_BY     = "Mary Beth Young",
READ_DATE   = "2/15/93",
LOCATION    = "Marquette University Science Library QA76.A772",
SUMMARY     = "
    There are three purposes for the writing of this article.
This article 1) shows how the scheduler may create an 'artificial'
deadlock, 2) shows that permanent blocking can occur when deadlock
is not possible and 3) presents a technique to prevent permanent
blocking as well as deadlock.  Deadlock is defined as the idea that
the resources of a system have been allocated among certain processes
in a way that it is impossible to grant additional requests to these
processes.  The author corrects a conclusion made by A.N. Habermann
that a scheduler which grants only safe requests will avoid all
deadlocks and will grant all requests.  The author states that in
his method for preventing deadlock, 'the system will never reach a
state where, regardless of what the scheduler does, certain requests
cannot be granted.'
    The scheduler can produce an 'artificial' deadlock.  There is an
example with three processes, P1, P2 and P3, and two resources,
R1 and R2.   P1 and P2 claim R1 and R2, and P3 has R2 while P2 and P1
request R2 respectively.  If P3 releases R2 and since P2 requested R2
before P1 made the same request, the scheduler will grant R2 to P2 if
it results in a safe state.  But since the result would not be a safe
state, the request is not granted by the scheduler.  So, although safe
states are entact, 'artificial' deadlock occurs.  In order to prevent
this the meaning of FIFO must be changed so that the scheduler can move
on if the First In will result in an unsafe state.
    The author also suggests that even if deadlock is not possible
permanent blocking may occur.  He gives an example where there are
two resources and three processes where P1 claims one resource, P2
claims one resource, and P3 claims both resources.  If P1 gets one
resource and P2 gets the other resource before P1 releases its resource
P3 will not have the chance to get both resources.  Permanent blocking
can occur in this situation.
    The technique for preventing permanent blocking involves a timing
feature to time how long a process has been waiting for a resource.  If
that process waits beyond its maximum time the scheduler must find a
safe sequence including the process that has reached its max in waiting
time and other processes with resources allocated to them.  Requests are
granted only to the processes in this sequence until the waiting process
of interest is allowed to continue.  Each process' waiting time is
checked and, if needed, this sequencing will start again.  Holt ends his
article by stating that encorporating this technique in the scheduler
will alter the overall response of the system.
",
COMMENT      = "
    This article addresses two major problems in the area of deadlock.
The problems faced delve deeper into the origins of deadlock.  One
problem was the idea of 'artificial' deadlock.  The conclusion to this
problem involves changing the meaning of FIFO to enable the scheduler
to move past unsafe states.  The idea that Holt is trying to get across
is that FIFO is not always the best way for a scheduler to handle
requests for shared resources.  Maybe a different solution could be
having three FIFO queues for requesting a shared resource.  If the
request could be tested before entering a queue to enter the resource,
then the safe states could be fed into one queue while the unsafe
states could be fed into another.  Then after a processes is taken
off the safe queue and returns its resources, the queue of unsafe
processes could be tested to see if any have become safe.  As the
unsafe processes are taken off and tested, the ones that are still
unsafe would go into the third queue.  The unsafe states would
oscillate between these two queues so that no processes would be
indefinitely postponed in a single queue waiting for the other unsafe
processes before it to become safe while it is itself safe.
    The second problem was permanent blocking while deadlock does not
exist.  The conclusion to this problem was more specific, in that it
was a technique, rather than the first conclusion.  Yet, Holt concluded
that this technique would alter the overall response time of the system.
This is also the case in my solution for the first problem.  There is
a question of efficiency v.s. correctness in the two conclusions.  It
is ideal to be both efficient (in the sense of time utilization)  and
correct.  But since both are hard to achieve in deadlock prevention,
the system needs to be analyzed in order to decide whether efficiency
with possible deadlocks would be more practical or if correctness with
minimal deadlock is deamed more practical.  A system with less shared
resources might want an efficient scheduler in order that time is not
wasted in overhead.  On the other hand, a system that has many processes
sharing many resources might find it more convenient to have more
overhead in order that deadlock and permanent blocking (which has a
greater tendency to occur in this environment) can be avoided the
majority of the time.
",
}