Deadlock in Operating system
Deadlock
A process in a multiprogramming system is said to be in dead lock if it is
waiting for a particular event that will never occur. OR
In a multiprogramming
environment several processes may compete for a fixed number of resources. A
process requests resources and if the resources are not available at that time,
it enters a wait state. It may happen that the waiting process will never gain
access to the resources. Since those resources are being held by other waiting
processes.
For example, take a
system with one tape drive and one plotter. Process P1 requests the tape drive
and process P2 requests the plotter. Both requests are granted. Now P1 requests
the plotter (without giving up the tape drive) and P2 requests the tape drive
(without giving up the plotter). Neither request can be granted so both
processes enter a deadlock situation.
A deadlock is a situation
where a group of processes is permanently blocked as a result of each process
having acquired a set of resources needed for its completion and having to wait
for release of the remaining resources held by others thus making it impossible
for any of the deadlocked processes to proceed.
Deadlocks can occur in concurrent environments
as a result of the uncontrolled granting of the system resources to the
requesting processes.
Deadlock Example:
·
All automobiles trying to cross.
·
Traffic completely stopped.
·
Not possible without backing some.
System
Model:
Deadlocks can occur when
processes have been granted exclusive access to devices, files and so forth. A
system consists of a finite number of resources to be distributed among a
number of competing processes.
The resources can be divided into several
types, each of which consists of some number of identical instances. CPU cycles,
memory space, files and I/O devices (such as printers and tape drives) are
examples of resource types. If a system has two tape drives then the resource type
tape drive has two instances.
Whenever a process wants
to utilize any resource, it must make a request for it. It may request as many
resources as it wants but it should not exceed the total number of resources
available with the system. Once the process has utilized the resource it must
release it. Therefore, a sequence of events to use a resource is:
i.
Request the resource:
ii.
Use the resource:
iii.
Release the resource:
Request and release of
resources can be accomplished through the wait and signal operations on
semaphores.
A system table records
whether each resource is free or allocated, and, if a resource is allocated, to
which process. If a process requests a resource that is currently allocated to
another process, it can be added to a queue of processes waiting for this
resource.
Deadlock
Characterization (Condition for Deadlock):
Deadlocks are undesirable
features. In the most of deadlock situation process is waiting for the release
of some resource concurrently possessed by some deadlocked process. A deadlock
situation can arise if the following four conditions hold simultaneously in a
system:
•
Mutual exclusion
•
Hold and wait
•
No preemption
•
Circular wait
Mutual
exclusion:
At least one resource
must be held in a non-sharable mode; that is only one process at a time can use
the resource. If another process requests that resource, the requesting process
must be delayed until the resource has been released.
Hold
and wait:
A
process must be holding at least one resource and waiting to acquire additional
resources that are currently being held by other processes.
No
preemption:
Resources cannot be
preempted; that is, a resource can be released only voluntarily by the process
holding it, after that process has completed its task.
Circular
wait:
A set {P0, P1, …, Pn} of
waiting processes must exist such that P0 is waiting for a resource that is
held by P1, P1 is waiting for a resource that is held by P2, …, Pn-1 is waiting
for a resource that is held by Pn, and Pn is waiting for a resource that is held
by P0.
Graphical
Representation and Resource Allocation Graph
|
Deadlock Situation
|
Deadlock can be described
more precisely in terms of a directed graph called a system resource-allocation
graph. This graph consist of a set of vertices V and a set of edges. The set of
vertices V is partitioned into two types of nodes: P= {p1, p2, ….., pn}, the
set of process in the system. R= {R1, R2, R3,……..Rn}, the set of resource types
in the system.
A directed edge
from process pi to resource type Rj is denoted by pi
→Rj which signifies that process pi is waiting for
resource Rj. A directed edge from resource type Rj to process pi is denoted by Rj→Pi
, which signifies that an instance of resource type Rj has been allocated to process pi .
A directed edge pi →Rj is called request edge; a directed
edge Rj→Pi is called assignment edge.
Pictorially we
represent each process pi as a circle and each resource type Rj
as square. Since resource type Rj may have more than one instance,
we represent each such instance as a dot with in a square. Given the definition
of a resource allocation graph, if the graph contains no cycles, the no process
in the system is deadlocked. If the graph does contain cycle, then a deadlock
may exist.
Method
for Handling Deadlock
·
We can use a protocol to prevent or avoid
deadlocks, ensuring that the system never enter a deadlock state.
·
We can allow the system to enter a
deadlock state, detect it, and recover.
·
We can ignore the problem all to gather,
and pretended that deadlock never occur in the system.
Deadlock
Prevention
If any one of the four
necessary conditions is denied, a deadlock can not occur. By implementing
policy that makes one of the conditions impossible, the system will be assured
to be deadlock free.
1. Denying
Mutual Exclusion:
Sharable resources do not require mutually
exclusive access such as read only shared file. Problem: Some resources are
strictly non sharable, mutually exclusive control required.
2. Denying
Hold and Wait
Resources
grant on all or none basis. If all resources needed for processing are
available then granted and allowed to process. If complete set of resources is
not available, the process must wait set available. While waiting, the process
should not hold any resources.
Problem:
Low
resource utilization, Starvation is possible
3. Denying
No-preemption:
When a process
holding resources is denied a request for additional resources, that process
must release its held resources and if necessary, request them again together
with additional resources.
When process releases
resources the process may loose all its works to that point. Indefinite
postponement or starvation may occur.
4.
Denying Circular Wait:
All resources are
uniquely numbered, and processes must request resources in linear ascending
order. The only ascending order prevents the circular.
Problem:
Difficult to maintain the resource order; dynamic update in addition of new
resources. Indefinite postponement or starvation.
Deadlock Avoidance
Deadlock can be avoided by never allocating a resource if it may lead
to deadlock. A simple way to do this is to allocate resources to only one
process at a time. Although not efficient, deadlock can not occur.
A system is said to be in safe state if there is a safe execution
sequence. An execution sequence is an ordering for process execution such that
each process when executed runs until terminates or is blocked and all request
for resources are immediately granted if the resource is available.
An unsafe state is a state that is not safe, not necessarily a deadlocked
state. An unsafe state may currently not be deadlocked but there is at least
one sequence of request from process that would make the system deadlocked. If
that sequence of request occurs, no set of response to those requests would
allow the operating system to avoid deadlocked state.
The figure illustrates the concept of safe, unsafe and deadlocked
state.
If a system is in a safe state ⇒No
deadlocks.
If a system is in unsafe state ⇒Possibility
of deadlock.
Avoidance ⇒ensure that
a system will never reach an unsafe state.
The idea of deadlock avoidance is to ensure that the system will
remains in a safe state. Intially the system is in safe state. Whenever a
process request resource that is currently available, the system must decide
whether the resource can be allocated immediately or whether the process must
wait. The request is granted only if the allocation leaves the system in safe
state.
1. The resource allocation graph algorithm (for
deadlock avoidance)
The resource allocation graph can be used for deadlock avoidance when
there is only one instance of each resource type. The basic facts in graph are
1. Claim edge: Pi →Rj indicates that process Pi
may request resource Rj. it is represented by a dashed line.
2. Claim edge converts to request edge when a
process requests a resource.
3. When a resource is released by a process,
assignment edge reconverts to claim edge.
4. Resources must be claimed a priori (advance)
in the system by each process.
If request assignment does not result in the formation of a cycle in
the resource allocation graph -safe state, else unsafe state.
Example
Suppose the following graph is there at any
instance in system
The system cannot allocate resource R2 to process P2 because resulting
state is unsafe as shown below
2. Banker’s algorithms
The resource allocation graph is not applicable to system with multiple
instance of each resource type. The banker’s algorithm is applicable to such
system.
The name was chosen because the algorithm could be used in banking
system to ensure that the bank never allocated its available cash in such a way
that it could no longer satisfy the needs of all its customer.
When
a process request the set of resources, the system determine whether the
allocation of these resources will left the system in safe state, if it will
the resources are allocated, otherwise process must wait until some other
process release enough resources. The banker algorithm uses the data
structures: Max, Allocated, Available, Needs. Let n = number of processes m
= number of resource types
Available: A vector of length m giving the number of
resources currently available for each type. Available = total resources of each type - amount
allocated of each type
Available[j] = k means that there
are k instances of resource Rj available
MAX matrix: An n x m matrix which defines the maximum
demand of each process. If MAX [i,j] = k then Pi may request at most k instances of resource
type Rj .
Allocation matrix: An n x m matrix which defines the
number of resources of each type currently allocated to each process.
Allocation [i,j] = k means that process
Pi is currently allocated k instances of resource type Rj
.
Need Matrix: An n x m matrix which indicates the remaining
resources needed by each process to complete. Need [i,j] = k means that Pi may need k more
instances of resource type Rj . Note that Need = max –allocation.
Total Resource Vector (TRV): an m element
vector giving the total amount of each resource belonging to the system, or the
available resources before anything is allocated to any process.
TRV = available + total allocated
Lemma: Safety Algorithm (part of the bankers Algorithm):
Let m = number of
resource types, and n = number of processes
1.
Let
work and finish be vectors of length m and n respectively.
Initialize: work =
available, and finish [i] = all
zeros for i = 1, 2, ..., n.
2.
Find
an i such that both
a.
Finish[i] == false
b.
Needi
<= work. (Needi is the ith row of
need[i,j].)
If no such i
exists goto step 4
3.
Work=work+allocationi , //where allocationi is the ith row
if allocation[i,j]
Finish[i] = true
Go to step 2
4.
If
finish[i] = true for all i, then the
system is in a safe state.
else
not safe.
This algorithm may require an order of m x n2 operations to
decide whether a state is safe.
Notation: X and Y are vectors of length n. Then X £ Y iff X[i] £ Y[i] for all
i=1, ... n.
Banker’s Algorithm (or Resource-Request
Algorithm) – the “main” Algorithm
Let requesti be the request
vector for process Pi . If
requesti[j] = k, then process Pi wants k instances of
resource type Rj
When a request for
resources is made by Pi , the following actions are taken:
1.If requesti
£ needi (the old or original needi), goto
step 2. Otherwise, raise an error
condition, since the process has exceeded its maximum claim
2.If requesti £ available (ie., old or original
available), goto step 3. Otherwise, Pi
must wait
since the resources are not available. .... all must
be available to go on.
3. Have the system pretend to have allocated
the requested resources to Pi by modifying the state as follows:
Available =
available – requesti;
Allocationi
= allocationi + requesti;
Needi =
needi – requesti;
Now using the
safety algorithm, check the “new” state for safety. If the resulting resource-allocation state is
safe, the transaction is completed
and process Pi is allocated its resources. If the new state is unsafe, then Pi must wait for requesti and
the old resource- allocation state is restored.
NOTE that steps 1 and 2 are a preliminary “sanity” or consistency check, and not part of the main “loop”
NOTE that steps 1 and 2 are a preliminary “sanity” or consistency check, and not part of the main “loop”
Banker’s Algorithm - Example
Given: 5
processes: p0, p1, p2, p3, p4
3 resource types:
A, B, C
A
has 10 instances
B
has 5 instances
C
has 7 instances
Total Resource Vector = TRV = [10, 5, 7]
Resource-Allocation State:
MAX - Allocation =
Process
Allocation MAX Available Need
ABC ABC ABC ABC
p0 0 1 0 7 5 3 3
3 2 7 4 3
p1 2 0 0 3 2 2 =
[10, 5, 7] - [7, 2, 5] 1 2 2
p2 3 0 2 9 0 2 6
0 0
p3 2 1 1 2 2 2 0
1 1
p4 0 0 2 4 3 3 4
3 1
------
Total Alloc: 7 2 5
Show that this is a Safe State using the safety
algorithm:
Initialization:
work = available = [3 3 2]
finish = 0 0 0 0 0
Notation: “>”
means “NOT <=”
Search for a safe
sequence:
p0: need0 = 7 4 3
> work = 3 3 2, doesn’t work - try
later, finish = 0 0 0 0 0
p1: need1 = 1 2 2
<= work = 3 3 2, finish = 0 1 0 0 0, work = 3 3 2 + 2 0 0 = 5 3 2
p2: need2 = 6 0 0
> work = 5 3 2, doesn’t work - try
later, finish = 0 1 0 0 0
p3: need3 = 0 1 1
<= work = 5 3 2, finish = 0 1 0 1 0, work = 5 3 2 + 2 1 1 = 7 4 3
p4: need4 = 4 3 1
<= work = 7 4 3, finish = 0 1 0 1 1, work = 7 4 3 + 0 0 2 = 7 4 5
p2: need2 = 6 0 0
<= work = 7 4 5, finish = 0 1 1 1 1, work = 7 4 5 + 3 0 2 = 10, 4, 7
p0: need0 = 7 4 3
<= work = 10 4 7, finish = 1 1 1 1 1, work = 10 4 7 + 0 1 0 = 10, 5, 7
State is Safe:
sequence is <p1, p3, p4, p2, p0>
Solution is not unique:
Alternate Safe
Sequence: <p1, p3, p4, p0, p2> ... reverse p0 and p2
The Bankers Algorithm (putting it all together):
Assume the
resource-allocation state of the previous example.
Suppose p1
requests one additional instance of resource type A and two instances of type
C.
Thus request1 = [1 0 2]
Application of the steps of the algorithm:
1. Request1
= 1 0 2 <= need1 = 1 2 2, “Sanity” check
2. Request1
= 1 0 2 <= available = 3 3 2,
“Sanity check”
3. Pretend
to make the allocation and check to see if new state is safe:
The changes are:
allocation1 = 2 0
0 + 1 0 2 = 3 0 2
need 1 = 1 2 2 - 1 0 2 = 0 2 0
available = 3 3
2 - 1 0 2 = 2 3 0
The “new” resource allocation state is now (changes
indicated by “==>”):
MAX - Allocation =
Process Allocation MAX Available Need
ABC ABC ABC ABC
p0 0 1 0 7 5 3 ==>2 3 0 7
4 3
p1 3 0 2 <== 3 2 2 ==>0
2 0
p2 3 0 2 9 0 2 6
0 0
p3 2 1 1 2 2 2 0
1 1
p4 0 0 2 4 3 3 4
3 1
------
Total Alloc: 8 2 7
Determine if this
is a safe state, by using the safety algorithm:
Search for a safe
sequence:
work = available = 2 3 0, finish = 0 0 0 0
0
p1: need1 = 0 2 0
<= work = 2 3 0, finish = 0 1 0 0 0, work = 2 3 0 + 3 0 2 = 5 3 2
p3: need3 = 0 1 1
<= work = 5 3 2, finish = 0 1 0 1 0, work = 5 3 2 + 2 1 1 = 7 4 3
p4: need4 = 4 3 1
<= work = 7 4 3, finish = 0 1 0 1 1, work = 7 4 3 + 0 0 2 = 7 4 5
p0: need0 = 7 4 3
<= work = 7 4 5, finish = 1 1 0 1 1, work = 7 4 5 + 0 1 0 = 7 5 5
p2: need2 = 6 0 0
<= work = 7 5 5, finish = 1 1 1 1 1, work = 7 5 5 + 3 0 2 = 10, 5, 7
New state is safe thus grant the request.
Supposed the next request is [3 3 0] by process p4.
Cannot be granted because step 2 is not satisfied:
request4=330>available=230
However that when the system is in this state, a request for (3,3,0) by
process can not be granted, since the resource are not available.
Furthermore, a request for (0,2,0) by p0 can not be granted, even
though the resource are available, since the resulting state is unsafe.
Deadlock
detection and recovery
Instead of trying to prevent or avoid
deadlock, system could allow deadlock to happen and recover from deadlock when
it does occur. Such a strategy requires mechanism for detecting and recovering
from deadlock.
If a system does not employ either deadlock prevention ot a deadlock
avoidance algorithm, then a deadlock situation may occur. In this environment,
the system must provide:
·
An
algorithm that examine the state of the system to determine whether a deadlock
has occurred.
·
An
algorithm to recover from the deadlock.
At this point, however, we note that a
detection and recovery scheme requires overhead that includes not only the run
time costs of maintaining the necessary information and executing the detection
algorithm but also the potential losses inherent in recovering from a deadlock.
Deadlock detection algorithm
If all
resources have only a single instance, then we can define a deadlock detection
algorithm that uses a variant of resource allocation graph, called a wait for
graph.
1. Wait for graph:
A n edge from process pi to pj
in a wait for graph implies that process pi is waiting for process pj
to release resources that pi needs. An edge Pi
-> Pj exists if and only if resource allocation graph (RAG) contains 2 edges
Pi -> Rq and Rq -> Pj for some resource
Rq.
a) Resource allocation graph b)wait for graph
A deadlock exits in the system if and only if the wait for graph
contains cycle. To detect deadlock the system needs to maintain the wait for
graph and periodically invoke an algorithm that searches for a cycle in the
graph.
2
Several instances of a resource type (Banker’s algorithm for detection)
The wait-for graph
scheme is not applicable to a resource-allocation system with multiple
instances of each resource type. Detection algorithm is similar to bankers for
avoidance – there are some differences in data structures.
Still use: Available vector as before, Allocation
matrix as before
Replace MAX
(Claim) matrix by Request
matrix (Assumes “request” is granted):
Request: An n x m matrix indicates the current
request of each process. If Request [i,j] = k, then process pi requests k units of
resource Rj … current request. Note: Need
Matrix is not used for detection algorithm
Algorithm for Detection:
1.
Let
Work and finish be defined as for avoidance algorithm. Initialize Work = available. Initialization of
finish matrix: For i = 1, 2, …, n = number of processes, if Allocationi
¹ 0, then Finish[i]
= false Else Finish[i] = true
2.
Find
an index i such that
- Finish[i] = false
- Requesti £
work //for
“avoidance”, it used to be needi £
work
//
work initialized to available
If no such i exists,
go to step 4.
- Work = Work +
Allocationi
Finish[i]
= true
Go to step 2
- if Finish[i] = false, for some 1 £ i £ n, then:
System is in a deadlocked state. Moreover, if finish[i] = false, then pi is deadlocked.
Deadlock Detection Examples
Modifying the
example used for the bankers Algorithm (deadlock avoidance) we have:
5 processes: p0,
p1, p2, p3, p4
Case I:
allocation = ABC request= ABC available= ABC
p0 0 1 0 0 0 0 0
0 0
p1 2 0 0 2 0 2
p2 3 0 3 0 0 0
Total resource = 7 2 6
p3 2 1 1 1 0 0
p4 0 0
2 0 0 2
Total: 7 2 6
work = available =
0 0 0
finish = 0 0 0 0 0 ... each row of allocation is not 0
(all processes unmarked)
Notation:
“>”means “NOT £”
Search for a sequence:
p0: request0 = 0 0
0 £ work = 0 0 0,
finish = 1 0 0 0 0, work = 0 0 0 + 0 1 0 = 0 1 0
p1: request1 = 2 0
2 > work = 0 1 0, doesn’t work try
later
p2: request2 = 0 0
0 £ work = 0 1 0,
finish = 1 0 1 0 0, work = 0 1 0 + 3 0 3 = 3 1 3
p3: request3 = 1 0
0 £ work = 3 1 3,
finish = 1 0 1 1 0, work = 3 1 3 + 2 1 1 = 5 2 4
p1: request1 = 2 0
2 £ work = 5 2 4,
finish = 1 1 1 1 0, work = 5 2 4 + 2 0 0 = 7 2 4
p4: request4 = 0 0
2 £ work = 7 2 4,
finish = 1 1 1 1 1, work = 7 2 4 + 0 0 2 = 7 2 6
sequence is <p0, p2, p3, p1, p4> ... No deadlock
An alternate
sequence:
p0: request0 = 0 0
0 £ work = 0 0 0,
finish = 1 0 0 0 0, work = 0 0 0 + 0 1 0 = 0 1 0
p2: request2 = 0 0
0 £ work = 0 1 0,
finish = 1 0 1 0 0, work = 0 1 0 + 3 0 3 = 3 1 3
p1: request1 = 2 0
2 £ work = 3 1 3,
finish = 1 1 1 0 0, work = 3 1 3 + 2 0 0 = 5 1 3
p4: request4 = 0 0
2 £ work = 5 1 3,
finish = 1 1 1 0 1, work = 5 1 3 + 0 0 2 = 5 1 5
p3: request3 = 1 0
0 £ work = 5 1 5,
finish = 1 1 1 1 1, work = 5 1 5 + 2 1 1 = 7 2 6
sequence is <p0,
p2, p1, p4, p3 >.No deadlock
Case II:
Same problem with new request matrix (change p2
request from 0 0 0 to 0 0 1):
allocation = ABC request= ABC available= ABC
p0 0 1 0 0 0 0 0
0 0
p1 2 0 0 2 0 2 Total resource = 7 2 6
p2 3 0 3 0 0 1 <== changed
p3 2 1 1 1 0 0
p4 0 0 2 0 0 0
Total: 7 2 6
work = available =
0 0 0
finish = 0 0 0 0 0
find a sequence:
p0: request0 = 0 0
0 £ work = 0 0 0,
finish = 1 0 0 0 0, work = 0 0 0 + 0 1 0 = 0 1 0
for all pi, i
>= 1
requesti
> work // work initialized to available
(previously
request2 £ work)
No sequence exists.
Remaining processes are in deadlock
A final example:
four processes: p0, p1, p2, p3
allocation = ABC
DE request = ABC DE available=ABC DE
p0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1
p1 1 1 0 0 0 0 0 1 0 1 Total resource = 2 1 1 2 1
p2 0 0 0 1 0 0 0 0 0 1
p3 0 0 0 0 0 1 0 1 0 1
total: 2 1 1 2 0
finish = 0 0 0
1 since allocation3 = 0 0 0 0 0, p3 has
no resources,
Does not
participate in deadlock.
Find a sequence:
Only one choice to start with p2:
p2: request2 = 0 0
0 0 1 £ work = 0 0 0 0 1,
finish = 0 0 1 1, work = 0 0 0 0 1 + 0 0 0 1 0
= 0 0 0 1 1
the remaining pi: p0, and p1:
requesti > work = 0 0 0 1 1 for
i = 0, 1
ie.,0 1 0 0 1 >
0 0 0 1 1 For i = 0
0 0 1 0 1 > 0 0
0 1 1 For i = 1,
no sequence exists
p0 and p1 are in deadlock.
Recovery from Deadlock
When detection algorithm determines that deadlocks exist, several alternatives
are available.
One possibility is to inform the operator that a deadlock has occurred
and to let the operator deal with deadlock manually.
Another possibility is to let the system recover from the deadlock
automatically. There are two options for breaking deadlock.
a) Process
termination: it eliminate
deadlock by terminating or killing process.
Two method may employed.
1. Abort all deadlocked process
2. Abort one process at a time until the
deadlock cycle is eliminated.
Aborting a process may not be easy. If the process was in the midst of
updating file, terminating it will leave file in incorrect state. If the
partial termination method is used, then system must determine which deadlocked
process should be terminated. This termination is a policy decision similar to
CPU scheduling decisions. The decision is made based on the termination cost. A
process is terminated for which the termination cost is minimum.
The minimum cost depend on the following factors
·
Priority
of the process
·
How long
the process has computed, and how much longer to completion.
·
Resources
the process has used.
·
Resources
process needs to complete.
·
How many
processes will need to be terminated?
·
Is
process interactive or batch?
b)
Resource Preemption
In this method system preempts some resources temporarily from
processes and gives these resources to other processes until the deadlock cycle
is broken.
The following issues are needed to be addressed during resource
preemption
·
Selecting
a victim: which process and which resources are to be preempted? System should
select the order of preemption to minimize the cost.
·
Rollback:
if we preempt some resource from a process, clearly it can not continue with
normal execution. We must roll back the process to some safe state and restart
process from that state.
·
Starvation:
we should guarantee that same process
may not always be picked as victim, otherwise it may lead to starvation to that
process. For this we may include number of rollback as a factor in cost
calculation.
Ostrich Algorithm
It assume that here is no good way of dealing with deadlock, so it ignore
the problem altogether.
For most operating systems, deadlock is a rare occurrence; so the
problem of deadlock is ignored, like an ostrich sticking its head in the sand
and hoping the problem will go away.
Exercise
1. Distinguish indefinite postponement and Deadlock.
2. State the conditions necessary for deadlock to exist. Give reason,
why all conditions are necessary.
3. A system has two processes and three identical resources. Each process
needs a maximum of two resources. Is deadlock possible? Explain your answer.
4. Show that four necessary conditions hold in traffic deadlock
example. State a simple rule that will avoid deadlock in traffic system.
Post a Comment