Deadlock prevention methods tend
to be wasteful in terms of machine resources. Deadlock avoidance attempts to predict the possibility of a deadlock
dynamically as each resource is made. The basic idea of deadlock avoidance
is to grant only those requests for available resources that cannot possibly
result in a state of deadlock. This strategy is usually implemented by checking
the effect of granting a particular resource request by the resource
allocator. If granting of the resource
cannot possibly lead to deadlock, the resource is granted to the requester.
Otherwise, the requesting process is suspended until its pending request can be
safely granted.
The most famous deadlock
avoidance algorithm is Dijikstra’s
Banker’s Algorithm. The algorithm is called by this name because it
involves a banker who makes loan and receives payments from a given source of
capital. The banker will only grant a loan if he can still meet the needs of
other customers, based on their projected future loan requirements.
In order to evaluate the safety
of the individual system states, deadlock avoidance algorithms generally
require all processes to preclaim their maximum resource requirements prior to
execution. Once its execution begins each process requests its resources as and
when needed, up to the maximum preclaimed limit. Processes whose preclaimed
resource requirements exceed the total capacity of the system are not admitted
for execution.
The resource allocator keeps
track of the number of the allocated and available resources of each type. The
resource allocator also keeps track of the remaining number of resources
preclaimed but not yet requested by each process. A process that requests a temporarily
unavailable resource is made to wait. If the requested resource is available
for allocation, the resource allocator examines whether the granting of the
request can lead to deadlock by checking whether each of the active processes
could safely complete.
The resource allocation state at
any instant is considered safe if
resources can be allocated to each process, in some order, such that deadlock
will not occur. An unsafe sate is a
state in which a deadlock is possible.
As an example, consider a system
with three processes P1, P2 and P3 and ten resources of the same type (e.g.
magnetic tape). The maximum resource requirements and the current allocations
are shown below:
|
PROCESS
|
MAX. NEED
|
CURRENT USAGE
|
|
P1
|
8
|
3
|
|
P2
|
5
|
1
|
|
P3
|
8
|
2
|
The state is safe because it is
still possible for all three processes to finish. Process P2 could use the four
available resources and finish its execution. This would release five
resources, which could be taken up by process P1. This would produce eight
resources, which would enable process P3 to finish. So the state is safe. Thus
the key to a state being sage is that there is at least one way for all
processes to finish.
Now consider the following state:
|
PROCESS
|
MAX. NEED
|
CURRENT USAGE
|
|
P1
|
9
|
3
|
|
P2
|
5
|
1
|
|
P3
|
8
|
2
|
This state is unsafe. Process P2
could use the four available resources and finish its execution. This would
release five resources. But the available resources at this point cannot meet
the maximum needs of either P1 or P3. So this state is unsafe. An unsafe state does not mean that a
deadlock will happen, since the process may not in fact require their
declared maximum needs, or some resources may be temporarily released. What an
unsafe state does imply that some unfortunate sequence of events might lead to
a deadlock.
After checking the effect of
granting a request, the resource is allocated to the requesting process if the
resource allocation can lead to a safe state; otherwise, the resource allocator
suspends the requesting process until the desired resource can safely be
granted.
The advantage of the deadlock avoidance is that it does not require the
acquisition of all resources at once and it will not force preemption of
resources. This eliminates the problem of resource idling due to premature
acquisition.
The disadvantage of the deadlock avoidance is that process has to
preclaim its maximum resource requirement. Preclaiming of resource need is not
realistic for interactive systems and it has the tendency to overestimate the
resource requirements. Another disadvantage of the deadlock avoidance is that
the algorithm must be executed every time a resource request is made. For a
multi-user system with a large number of user processes, the processing
overhead would be severe.
No comments:
Post a Comment