In
multiprogramming environment, several processes may complete
for finite number of resources. A process requests resources, and
if the resources are not available at that time, the process enters a
wait state. It may happen that waiting processes will never
again change state, because the resources that they have requested
are held by other waiting processes. This situation is called a Deadlock.
For example,
a system contains four tape drives and two processes. i.e.., each process holds
two tape drives but needs three, then each will wait for the other
release its tape drives. This situation is a "deadlock". The
system resources are partitioned into several types, each of
which consist of some
number of identical instances. If a system has two CPU's, then the
resource type CPU has two instances. All instances of a resource
type must be identical, if not the resource type classes have to be properly
defined. A process must request the resource before using it and release the
resource after using it. A process may request as may resources as it requires,
but the number of resources requested may not exceed the total number of
resources available in the system. A
process may utilize a resource only in the following sequence.
Request : if the request cannot be immediately granted,
then the requesting process must wait until it can acquire the
resources.
Use : the process can operate on the resource.
Release : the process release the resource.
DEADLOCK Definition : A set of
processes is in a deadlock state when every process in the set is waiting
an event that can only caused by another process in the set,
consider a system with three tape drives. Suppose that there are
three processes, each holding one of these tape drives. If
each process not requests another tape drive, the three processes will be
in a deadlock state. Each is waiting for an
event "tape drive is released", which can
only caused by one of the other waiting processes.
DEADLOCK 2nd
Definition : A process request resources and
if the resources are not available at that time, the process
enters a wait state. The process will never change
state because the resources they have requested are held by after
waiting process. This situation is known as DEADLOCK.
2. What are the necessary conditions for
a DEADLOCK ?
A
deadlock situation can arise if and only if the
following four conditions hold simultaneously in a system.
1) Mutual Exclusion :
At least one resource is help in a non-sharable mode, i.e., only
one process at a time can use the resource. If the another process
requests that resource, the requesting process must be delayed
until the resource has been released.
2) Hold and Wait : There
must exist a process that is holding at least one resource
and i.e., waiting to acquire additional resources that are currently
being help be other processes.
3) No preemption : Resources can not be
preempted; that is, a resource can be released only
voluntarily by the process holding it, after the
process has completed its task.
4) Circular wait :
There must exist a set { p0,p1.......pn)
of waiting processes such that p is waiting for a resource which is held
by p is waiting for a resource which is held by p1.p1
is waiting for a resource which is held by p2……. Pn-1
is waiting for a resource that is held by pn. We
emphasize that all four conditions must hold for a
deadlock to occur.
3. Explain Resource Allocation Graph
(RAG).
Deadlocks
can be described more precisely in terms of a directed graph called a
“(system) resource allocation graph".
This graph consists of a pair G = (V1
Each
element in the set E is an ordered pair (pi,rj) or (rj,pi),
where pi is a process and rj is a resource
type. If (pi,rj)
belongs to E, then there is a directed edge from
resource type rj to process pi implying
that an instance of resource type r has been allocated
to process pi. An
edge (pi,rj) is called a request edge, while an
edge(rj,pi ) is called an assignment edge.
Pictorially, we represent each process Pi as a circle
and each resource type rj as a square. The instance can
be represented by a dot within the edge must also disignate
one of the dots in the square. Whenever a process
requests an instance of resource type, an request edge is inserted
in the graph. When this request can be fulfilled, the request edge is
instance resource, the assignment edge is deleted.
Resource
type r1 is having one instance, r2 is having two
instances, r3 is having one instance and r4 is having
three instances. Process p1 is holding an instance of resource
type r2 and is waiting for an instance of r1.
Process p2 is holding an instance of r1 and is waiting for an
instance of r3. Process p3 is holding an instance of r3.
If a graph contains no cycles, then no
process in the system is deadlocked. Otherwise a deadlock may exist.
4.
What are the methods for handling DEADLOCKS ?
There are two methods
of ensuring that deadlocks never occur.
a)
Deadlock prevention.
b)
Deadlock avoidance.
5.
Explain DEADLOCK PREVENTION .
We know that, there are four necessary conditions
must hold to occur a dead lock. By ensuring that atleast one
of these conditions cannot hold. We can prevent the
occurrence of a DEADLOCK.
Mutual Exclusion :
If all the resources are sharable, then mutual
exclusion will not hold. Sharable resources do not require
mutual exclusive access, and cannot be involved in a deadlock. But
we can't put all resources in the sharable mode. for example A printer cannot
be simultaneously shared by several processes. In general, it is not possible
to prevent deadlocks by denying the mutual exclusion condition.
Hold And Wait : In order to
ensure that the hold and wait condition never holds in the system, we
must guarantee that whenever a process requests a resource it does
not hold any other resources.
One protocol that can be used requires
each process to request and be allocated all of its resources before it
begins execution.
An alternative protocol allows a process to
request resources only when it has none. A process may request some
resources and use them. Before it can request any additional
resources, it must release all the resources that it is currently allocated.
There are two main disadvantages to these
protocols.
First one
is , resource utilization may be very low, since many of the resources
may be allocated but unused for a long period. Second one is,
starvation is possible. A process that needs several popular resources
may have to wait indefinitely because atleast one of the resources that
it needs is always allocated to some other process.
No Preemption : To ensure that this condition does hold,
the following protocol is
If a process is holding some resources requests another
resources that cannot be immediately allocated to it then all resources
currently being held are preempted. The preempted resources are added to the
list of resources for which the process is waiting. The process
will not only be restarted when it can regain its old resources, as
well as the new ones that it is requesting.
Alternatively, if a process requests some
resources, we first check whether they are available. If they are
available, we allocate them. If they are not available, we check
whether they are allocated to some other process that is
waiting for additional resources. If
so, we
preempt the desired resources from the waiting
process and allocate them to the requesting process. If the
resources are not either available or help by a waiting process,
the requesting process must wait. While it is waiting, some of its
resources may be preempted, but only if another process
requests them. A process can be re started. Only when it is
allocated the new resources it is requesting and recovers any
resources that were preempted while it was waiting.
Circular Wait : To ensure that this condition does not
hold, each resource type is assigned a unique integer number,
which allows to compare two resources and determine whether one preceeds
another in our ordering. Each process can only request resources in an
increasing order of enumeration.
Let R= { R1,R2,....Rn
} be the set of resource types. We assign to each resource a unique
integer number, say F: R - N, where N is
the set of natural numbers. For example set of resource types are tape
drive, disk drive, printer, then the function F might defined as follows :
F( tape drive ) = 1
F( disk drive ) = 5
F( printer ) = 12
We now consider the following protocol to
prevent deadlocks. Each process can request resources only in
an increasing order of enumeration. That is, a process can initially
request any number of instances of a resource type, say Ri.
After that the process can request instances of resource type
Rj, if and only if F(Rj)>F(Ri). If this protocol is used, the circular wait
condition cannot hold. We can demonstrate this fact by assuming
that a circular wait exists (proof by contradiction).
Let the set of processes in the circular wait be { P0,P1,
...Pn}.
P0
is waiting for a resource R0, which is held
by P1. Then according to our protocol F(R0)1
).
P1 is
waiting for a resource R1, which is held by
P2. Then according to our protocol F(R1)2
).
P2
is waiting for a resource R2, which is held by
P3. Then according to our protocol F(R2)3
).
Pn-1 is
waiting for a resource Rn-1, which is held by Pn.
Then according to our protocol F(Rn-1)n
).
Pn
is waiting for a resource Rn, which is held by P0. Then
according to our protocol F(Rn)0
).
This
means that F(R0) < F(R1)
< .......< F(Rn) < F(R0) implies that F(R0) < F(R0) which
is impossible.
Therefore,
there can be no circular wait.
6. Explain DEADLOCK AVOIDANCE.
In
this method, it is necessary to obtain additional information about
how resources are to be requested. With the knowledge of complete sequence of
requests and releases for each process, one can decide for each
request whether or not the process should wait.
Each request requires that the system consider the resources
currently available, the resources currently allocated to
each process, and the future re-quests and releases of each
process, to decide if the current request can be satisfied or must wait
to avoid a possible future deadlock.
It is better to know the maximum number of
resources of each type each process needs. A deadlock
avoidance algorithm dynamically checks the resource allocation state
(i.e., the number of available and allocated resources, and the maximum
demands of the processes) to ensure that there can never be a
circular wait condition. A state is safe if the system can allocate
resources to each process (up to its maximum) in some order and
still avoid a deadlock. A system is in a same state only if there exists
a safe sequence of process
is a safe sequence for the current
allocation state if for each p1, presources which p1 can still
request can be satisfied by the currently available resources plus the
resources held by all the Pj, with j>i. If no such a sequence exists, then
the system state is said to be unsafe.
A safe state is not a deadlock state, and a
deadlock state is an unsafe state. An unsafe state may lead to a
deadlock.
Several Instances Of A Resource Type : An algorithm, known
as banker's algorithm, is used for deadlock avoidance is as follows.
When
a process enters the system, it must declare the
maximum number of instances of each resource type that
it may need. This number may not exceed of the total
number of resources in the system.
When a user requests a set of resources, it must be determined
whether the allocation of these allocated, otherwise, the
process must wait until some other process releases enough
resources. Let n be the number of processes in the system and m be
the number resource types. The following data structures are needed.
Available : A vector of length 'm' indicating the number of
available resources of each type.
If Available [j] = k, there are 'k' instances of resource type rj
available.
Max : An n x m matrix defining the maximum demand of each
process. If Max[i,j] = k,
then process p may request at most 'k' instances of resource
type rj.
Allocation : An n x m matrix defining the number of resources of
each type currently allocated to each process. If Allocation[i,j] = k, then process pi
is currently allocated 'k' instances of resource type rj.
Need : An n x m matrix
indicating the remaining resource need of each process. If Need[i,j]= k, then process pi
may need 'k' more instances of resource type rj, in order to
complete its task.
Need[i,j] = Max[i,j] - Allocation[i,j].
If X and Y are vectors
of length n, then x <= y if and only if x[i] <= y[i]
for all i = 1,2...n. For example, if x = (1,7,3,2) and y = (0,3,2,1) then Y
<= x.
Each row
of matrices Allocation and Need are treated as vectors Allocation and
Need respectively. Allocation specifies the resources currently
allocated to process P, while Need specifies the additional
resources the process P may still request in order to complete
its importance.
Banker's Algorithm :
Let
Request ti be the request vector for process Pi .
If
Request ti [j] = k, then process Pi wants 'k' instances
of resource type rj. When a request for resources is made by process Pi,
the following steps are taken.
1. If Request ti <= Need then
proceed to step 2. Else an error message occurs, since the process has
exceeded its maximum claim.
2.
If Request ti <= Available then proceed to step 3.
Else the resources are not available process Pi
must wait.
3.
Available =
Available - Request .
Allocation = Allocation + Request
Need = Need - Request .
If the resulting resource allocation state is
safe, process P allocated resources. If the new state is unsafe, then P must
wait for Request and the old resource allocation state is restored. This
Banker's Algorithm require m x n operations.
Safety Algorithm : This algorithm finds out whether a system
is in safe state or not.
1. Let Work and Finish be vectors of length m and n
respectively.
Work = Available
Finish [i] = False for i = 1,2,3, ...., n.
2.
Find an 'i' such that :
(i)
Finish[i] = false, and
(ii) Need
<= Work.
If no such 'i' exists, go to step 4.
3. work :=
work+allocation I finish[i]:=true , go to step2.
4. If Finish[i] = true for all i, then the system
is in a safe state.
Single Instance Of Each Resource Type : If we
have a resource allocation system with only one instance of each
resource type, a more efficient algorithm can be defined. In this
algorithm, in addition to the request and assignement edges of a resource
allocation graph, a claim edge is introduced. A claim edge (pi,rj)
indicated that process Pi may request resource r in future. This
edge is indicated by a dashed line and resembles the direction of a request
edge. When process Pi requests resource rj, then this
claim edge is converted to a
request edge. When a resource is released, the assignement edge is
converged to a claim edge. Before process Pi starts executing
all of its claim edges must already appear in the resource
allocation graph. A requesting edge is converted to an assignment edge
only if this assignment does not result lin the formation of cycle
in the resource allocation
graph. If a cycle is found, then process Pi must wait
for its requests in order not to enter in an unsafe state.
For
example, in the following allocation graph, p2 requests r2.
Even if is currently free, we cannot
allocate it to P2 since this allocation will create a cycle in
the graph. If Pi requests rj, a deadlock will
occur.
