UNIT- 3.

Deadlock

In multiprogramming os, several processes can suun

at a time, so programs are required to specify

in advance what resources ore reqired to

specify they need, so conflicts can be avoided.

But now os offers dynanic allocation of resourсes

le, progranis could request further allocations

of after they had begun running

resources
several processes may compete for finite no of
resources. A process requests resources, if the
resource are not available, the process enters

a wait state. Waiting processes may never change

again state, because resources they have requested
are held by other processes. This situation is
called deadlock.
s o u r ces.
e.g. d re example2
P
Quene P2 P2
P3
Pi
Resource
Allocated T2
T3
Tapel
R K R2 K

(tape drive) (printer) circular wait

and received Ri. R23

Pi requested
Ri

and received R2. P P2

Pr requested
R2

R
 2

Pi requests resource R2 and is queued up, pending

the release of R2.

P2 request resowice Ri and is queed up, pending the

release of RI.
In this case, neither of the programs can proceed
until the other program releases a resources.
Def

A set of process is in a deadlock state if each

process in the set is woiting for an event that

be coused by only another process in set

can
bystem is in dealock because each process holds

a resource which is requested by other process

& neither of processes are willing to release

the resorices they hold.

is situation where in two or more
* A deadlock a

waiting for to finich

competing actions are
does.
other

and thus neither ever

Resources :-

A system consists of a finite no of resouices to be

distributed ameng a no of competing processes.

partitioned into several kypes
The resouices are
of
of which con consists of some no
each
identical instances.

Thew The resources may either be physical or

logical.
Physical resources:- prienters,
CPU
Jape drivers, memory space
cуcles.
 3

Logical resources :- files, semaphores and monitors.

Resowce Allocation* Preemptable and Non-preemtakle

be divided into 2 categories :-

Resources can

and non- prcemtable.

preemtable taken
that can be
is
preemtable resources one
A
the process with n
ill ef fects.
away from
o

Example:- memory
be
ta bl e so ur ce s is one that cannet
Non- preemp
re
process ( without cousing ill efect)
taken away from
and
eg., if we are writing data in a cD

er away
suddenly the system TRAP the corerucoprd
ted.
e w i l l b e
from CD-ROM, th C D

Resource Allo
cation / System Model.
resource before using it,
t r e quest a
A p r o c e s s m u s
resource after resing it.
and must re
lease the
reees reque sted
m a r y re so wu
A process may request a s
ed esk.
to coro ry o u t it s de si gn at ttha
requires n o t e x c e e d
as it
No. of resources requested may system.
of resources available in the
total no
major operations
Following are the three

which are processed on a resource :-

 4
Request 下 Resouices

Use Resovices
T
Release Resources

(T
Request:- to use resouice, a process must
request for resource. of resourue
is not available at that moment, then
can

requesting perocess must wait untill it

aq acquire resource.

If requested is available to
22 Use:- resource

it is utilized to its full efficiency.

process,
The resouece that is curently acquired is

blocked for other processes.

3) Rellase After the utilization of resource by

it must be released as soon as

a process,
possible for the use of other processes.

The request and release of resources are

system calls. Request and rrelease of other

sources can be acomplished through the wait

efore
and signal operations on semaphores. Ther
for each use the operating systom checks
u s i n g
theprocess has
that
to make sure
al lo ca te d, and, a
requesteidd a n d be en

at to ca te d t h e re so ur ce. A system
resouree is
whether each resource is free
table records
or allocated. the resouree of a process
 5

requests a resource that is wiently allocated

to anothete process, it can be added to a
queue of processes waiting for this resourice.
A
set of processes is in a deadlock state

when every proces in the set is waiting

event that be caused only by
for an can

set. The events with

another process in the

which we are mainly concerned are resoure

acquisition and release.

Conditions for Deadlo

ck.
Necessary finish executing
deadlock, processes
never
In a
are tied up, preventing
and sy st em re so ur ce s

other jobs from starting.

arise if the following 4
A deadlock situation system
conditions hold simultan
cously in a

of them is absent, there is no

t e on
deadlock.
must
Exclusion :- At least one resource
Mutual
mode, that is,
held in a non sharable
be
time can use the
process at a
only one
another process requests that
resource. of delayed
resource, "the rrequest
ing process must be
has been released.
until the resource
 6

2) Hold and wait :- A process must be holding

at least one resource and waiting to acquire
additional resources that ace curently
being held by other processes.

3) No preemption :- Resources cannot be pre- empted

die., the perocesses can not be forced togive up

the resources they are holding before completion.

Circular waiting :- There must be a et of

perocesses EPI, Pz- Prj:
that is held by
Pi is waiting for a

resouce or signal from P2, Pz is waiting for Ps

and In is waiting for Pi.

Resource Allocation Graph.

Deadlocks can be described more precisely in

terms of a directed guaph called a system

resource allocation graph.

g= {E, VS. The set of vertices V is partitioned

2

#
into tiwe different type of nodes Po { Pi, P2, ... Pn3.
the set of all active processes in the bystem
and R={ R1, R2, --Rm?, the set of all resources
types in the system
A edge from
directed process Pi to resource type
Rj is denoted by Pi Rj. and it is called
a request edge
A directed edge from resource type Rj to Process Pe
is by Rj
det denoted Pi and it is called an

assignment edge.
We represent process Pi as a circle and each
resource type Rj as a iquare, since resource
type Rj may have more than one instance,
wwe represent instance as a dot within the

square.

When. process Pi requests an instance of resourе

type Rj, a request edge is inserted in resource

rrequest be
graph.
can
allocation when this

fulfilled, the request edge is instantancously

traniformed to an assignment edge. When

the process no longer needs access to the resource

result
it releases the resource, and as a

edge is deleted.
assignment
RI R3

Pi P2 Pa

R2
R4.

Fig.. Resource - allocation graph.

 8
In graph we have
above
The sets P. R and E,
→P =EPl, P2, P3}
R {R1, R2, R3, R43
→ E = { P →R1, P2R3, RI→P 2, R2P2, R →P1, R3 P33
Process states;-

Process Pi is holding an instance resource type Rz

and is waiting for of resae
resource type Ri.
instance

Process Pr is holding an instance of Ri and R2, and

is waiting for an instance of resource type R3.
Process P3 is holding an instance of R3.

no

If the graph contains cycles, then no

process in the system is deadlocked. If
the graph does contain a cycle, then a dead-
-lock may exists.
If each ressurck type has exactly one instance
then a cycle implies that dead lock har
oceurred. Each process involved in the cycle
is deadlocked. In this case, a cycle in the
graph is both necessary and a sufficient
condition for the existence of deadlock.

If each resource type has several instances

then a cycle des not necessarity imply that
a deadlock has eccurred. In this case, cycle
graph
in the is a
necessary but mot a
sufficient condition for existence of deadlock.
 9
Suppose trat Process Ps requests an instance of
type Rz. Since
‫المد‬
resource no resouce instance

currently available, a request edge P3 4h2 s

added to graph. At this point, 2 minimal

cycles exist in system :

R.P2 R3 P3 7R2 P
PIRI
P2 R3 P3 → R2 P2

R R3
९

P2 P3
PD

R2 R4.

graph with a deadlock

Resource allocation
Processes Pi, Pz, and P3 are deadlocked. Process P2
R3, which is
is waiting for the resource
other hand,
. Pr P 3 , n the
held by process P3
oc es s o

pr oc es s o r Pr to release
is waiting for either Pi
ti on , es s is wa it ing
R2. In addi oc
pr i
resource
release resource R1.
for pr oc es s P2 to

ressurce -allocation
graph dees
In summory, if a

ycle. system is not in a

not have a then
other hand, of there
deadlock state. On the

is a
cycle then the system may or may
not be in a deadlock state.
 10

Methods for handling Deadlock

1) Ignore /Ostrich Algorithm

In general, this is a reasenable stratayy. Deadlock
is unlikely to occur very often, a ystem run
oc cu rring
for ye ar s wi th ou t de ad lo ck
ra th er a sbrategy of
ri th m bu t
Its not an algo
s that they
le ms ba si
ignoring potential prob
o n

are rare.

Most of the operating systems including UNIX d

y , p r o b l e m an
and windews generall ig no re t h e
w o u l d p r e f e r
that most of theuser s
restructing
assume l ock to a rule
d e a d
an occas i o n a l
esss one open file,
pr oces
coc
all users to on e

and one of everything

2) Prevention
by constraining hew request
Preventing deadlocke
he syeteevmention
made in Dt pr
for resources can be handled. eadlock
and how they are
rules that
strategies involve changing the so

notre qu es t that could

make
procese will

result in a deadlock. The goal

is to ensure

that atleast one of the necessary conditions

er hold.
can nev
for deadlock
 3) Dynamic Avoidance by careful resource allocation
of av oi da nc e th e sy st em dy na mi ca lly
In the ca se

y dec ide s whether it it

consid er s ev er re qu es t an d
E. Deadlock can be
to grant it at th
is point.
safe
by only egr anting in resouideceasdlocifk gran ting
sitaation
avoided sult
r a
them cannot

later. However, this worksonly if system knows

will demandfor which resource
which process e
in the near future but this is an urrealisti
assumption.

4) Deadlock detection and recovelo ry. state and there

enter a dead ck
The system may th e de adlock.
must be some algo
rith m to de te ct

ca te go ri es o f the detection
There two
are
s y s t e m s h a v i n g on ly one
algoruithms: one for t
he
ty pe , and another
instance of ea c h re so ri ce

h a v i n g m u l t i p l e instances
for the syetems
each resource tуpe

Deadlock Prevention.
Mutual Exclusion
1) Prevention from hold
condition must
mutual ext exclusion
The
resiources. That is, several
for non- sharable
processes cannot simultaneously share a single
is not possible for all time to
resources. It
share the ressurces os signals which are

being waited for le.g. a printer, CD drive, etc.)

 12.

However, if we can to violate resources behaving

be able
in the mutually exctusive manner then the
deadlock can be prevented.
for example printer [Link]
device like printer, spooling can work. There
For a

associated with the printer which

is memory
into it.
a
of process
stores jobs for from each the

l the job print each

and
Later, printer collects al FCFS. By using
o f t h e m a c c o r d i n g to
one have to wait
process doesn't
this mechanism, the
continue whatever
for the printer and it can

tater, it collects the vutput when

it wais doing.
it is produced.
an effective approach
Although, spooling
be
sreffers
can

exclusion but it
to violate mutual
kinds of problems.
from two

1) This cannot be applied to every resowice.

2) sfter some point of time, there may arge ise
t processes to
a

condition between the

race
sace in that spool.
space

2) Prevention from Hold and wait.

This condition can be vislated in following ways
a Approach 1:-
A process has to first request for all reesources

it requires for execution.

 13

Once it has acquired all the resources, only then

it can starit its execution.

this approach ensures that the process does not

hold some resourees and wait for other

resources.

* Drawbacks :-

It is less efficient.
It is not implementable since it is not possible
to predict in advance which resorces will be

required during executtion.

Approach 2.
process is alloved to acquice the resources
A
desires at the curent moment.
it

Aftercution. acquiring the resourices, it start its

exe
fo re ma ki ng an y re qu es t, it thas to
Now be
new
resources that
comp ul so ri ly re le as e al l the

it holds curently.
oa ch is ef fi ci en t an d im pl ementable.
This appr
Approach 3:-

A timer is set after the process acquires any

resovrce
process has to
expivres,
a
After the timer
compulsorily release the неsоrce.
 14

3) Prevention from No preemption:-

• This condition can be vislated by forceful preemption
• consider a process is holding some resources

and request other rusovices that can not be

immediately ace allocatet to it.
• Then, by forcefully preemtin
ion
g the wrently
violated.
hild
resources, the condit can be

Note :-

A process is allowed to forcefully preempt the

resouices possessed by some other perocess

only if
It is a high priority process or a system
process.

• The victim process is in the waiting state

4) Prevention from circular wa

it.
It ca n be de ni ed by im po si ng a total
of urces types and
ordering on al l th e re so
re quest the
then fo rc in g, al l pr oc es se s to
in or de r Ci nc re as in g or decreasing).
re so ui ce s
ordering of all
Ihis strategy impose a total

require that each

resouices types, and to
mnumerical
proces requests resources in a

order ( increcising or
decreasing) of enumeration.
For example,
card reader
1 =

2 = printer
3= HDD and so on.

4 = Optical driver
 15

Now the rule is :- process can request

resources whenever they want toy but all
requests must be made in numerical
order. A proress may request first printer and
then a HOD C order 2, 3), but it may not
request for opttical driver first and thon a
printer Corder 4,2)

Deadlock Avoidance.

This approach to deadlock problem anticipates

deadlock before it actually occurs. This approach
employs an algorithm to access the possibility
th at de ad lo ck co ul d occ ur an d ac ti ng acc oudingly
If the nece
n ssary conditions for a deadlock are in
lace, it is still possible to avoid deadlock
bi ng ca re fu l ces are allocated.
"by wh en res oui

Safe and unsafe state

A system is said to be in a safe state, if
there is a safe execution sequence. em execution

sequence is an ordering for puocess execution

such that each process runs until it
terminates or blocked and all request for
resources are immediately granted if the
resovices ott is available.

A system is said to be in an Unsafe state

if there is no safe execution sequence. An

may not be deadlocked,

but
unsafe state
 16

there is at least one sequence of requests from

processes that would make the system
deadlocked.

unsafe
Deadlock

cafe

Relation between Safe, unsafe and deadlock states

Forexample,
We conseder a system with 12 magnetic tape
drives and 3 processes Po, Pi and P2.
Max Needs Needs
Currently Needs
Po acquired
lo 5 5
Pi 4 2 2
P2 ‫و‬
2 ‫ד‬

Currently, tapes are

5 acquired by Po, 2 by
Pi and 2 P2 so out of 12 (5+2+2 =9)
are acquirred and 3 deives are a cworentty
free
so out of 3 tape drives we can
allot 2 to Pi.
Now Pi will execute and rellase itT

resources. Now 5 tape drives are available

so, now Po can be executed.
<PI, Po, P2Y.
so, safe sequence
 17

A system may go from a safe state to an uunsafe

state. Suppose that, at time ti, Pz requests
and is allocated 1 more tape trve drive. The
system is no longer in a safe state.

Max Needs. Cwrently acquired Needs.

5
5
Po 10
2
4 2
P

P2 9 3. 6

Resource Allocation Graph SHgorithm.

(Deadlock owvoidance for single instance resources)
In addition to the request and assignment
edges, we introduce a new type of edge,
called a claim edge. A claim edge PiRj
indicates that process Pi may request resource
Rj at some time in the fut future.
This edge resembles a request edge in

represented by dashed line.

direction, but is a

• When process Pi requests resowrce Rj, then claim

edge Pi→ Rj is converted to request edge.
• When a resource Rj is released by Pi, the

assignment edge Rj Pi is reconverted to a

claim edge PiRj

The resources must be claimed apriori in

the system. That is, before proces Pi starts

 18

executing, all its claim edges must abready

appear in the resource allocation graph
suppose that process
cocess Pi requests resource Rj. The

request can be granted only if converting

the req uest edge Pi Rj to an assignment

edge Rj Pi does not result in formation

of a cycle in the resource -allocation graph.
R
RI

P2
P P2 P

R2
R2 K

An. Unsafe state in

RAG for deadlock cwoidance RAG.

If no cycle exists,then the allocation of

resoureces will leave the system in a safe
the allocation
state. If a cycle is found,
will put the system in unsafe state

Therefore, process Pi will have to wait for

its requests to be satisfied.
In above fig, suppose that P2 requests R2

Although R2 is cuorentty fuee, cannot

we

allocate it to Pz, since this action will

create a cycle in graph. A cyle indicater

that the syctem is in an unsafe state

If P. requests R2 and P2 requests R2, thena
deadlock will occur.