Section07-Deadlocks_operating_system.ppt

deadlock in operating system.
prevention of deadlock and types of deadlock. deadlock avoidance in operating system

1. 7: Deadlocks 1
Jerry Breecher
OPERATING SYSTEMS
DEADLOCKS

2. 7: Deadlocks 2
What Is In This Chapter?
•What is a deadlock?
•Staying Safe: Preventing and Avoiding Deadlocks
•Living Dangerously: Let the deadlock happen, then
detect it and recover from it.
OPERATING SYSTEM
Deadlocks

3. 7: Deadlocks 3
DEADLOCKS
EXAMPLES:
•"Ittakesmoneytomakemoney".
•Youcan'tgetajobwithoutexperience;youcan'tgetexperiencewithouta
job.
BACKGROUND :
Thecauseofdeadlocks:Eachprocessneedingwhatanotherprocesshas.This
resultsfromsharingresourcessuchasmemory,devices,links.
Undernormaloperation,aresourceallocationsproceedlikethis::
1.Requestaresource(suspenduntilavailableifnecessary).
2.Usetheresource.
3.Releasetheresource.

4. 7: Deadlocks 4
•Traffic only in one direction.
•Each section of a bridge can be viewed as a resource.
•If a deadlock occurs, it can be resolved if one car backs up (preempt
resources and rollback).
•Several cars may have to be backed up if a deadlock occurs.
•Starvation is possible.
DEADLOCKS
Bridge Crossing
Example

5. 7: Deadlocks 5
DEADLOCKS
NECESSARYCONDITIONS
ALLofthesefourmusthappensimultaneouslyforadeadlocktooccur:
DEADLOCK
CHARACTERISATION
Mutualexclusion
Oneormorethanoneresourcemustbeheldbyaprocessinanon-sharable
(exclusive)mode.
HoldandWait
Aprocessholdsaresourcewhilewaitingforanotherresource.
NoPreemption
Thereisonlyvoluntaryreleaseofaresource-nobodyelsecanmakeaprocess
giveuparesource.
CircularWait
ProcessAwaitsforProcessBwaitsforProcessC....waitsforProcessA.

6. 7: Deadlocks 6
DEADLOCKS
Avisual(mathematical)waytodetermineifadeadlockhas,ormayoccur.
G=(V,E)Thegraphcontainsnodesandedges.
VNodesconsistofprocesses={P1,P2,P3,...}andresourcetypes
{R1,R2,...}
EEdgesare(Pi,Rj)or(Ri,Pj)
Anarrowfromtheprocesstoresourceindicatestheprocessisrequestingthe
resource.Anarrowfromresourcetoprocessshowsaninstanceoftheresource
hasbeenallocatedtotheprocess.
Processisacircle,resourcetypeissquare;dotsrepresentnumberofinstancesof
resourceintype.Requestpointstosquare,assignmentcomesfromdot.
RESOURCE
ALLOCATION GRAPH
P
i
R
j
P
i
R
j
P
i

7. 7: Deadlocks 7
•Ifthegraphcontainsnocycles,thennoprocessisdeadlocked.
•Ifthereisacycle,then:
a)Ifresourcetypeshavemultipleinstances,thendeadlockMAYexist.
b)Ifeachresourcetypehas1instance,thendeadlockhasoccurred.
DEADLOCKS
RESOURCE
ALLOCATION GRAPH
Resource allocation graph
P2 Requests P3
R3 Assigned to P3

8. 7: Deadlocks 8
DEADLOCKS
RESOURCE
ALLOCATION GRAPH
Resource allocation graph
with a deadlock.
Resource allocation graph
with a cycle but no deadlock.

9. 7: Deadlocks 9
HOW TO HANDLE DEADLOCKS –GENERAL STRATEGIES
Therearethreemethods:
IgnoreDeadlocks:
Ensuredeadlockneveroccursusingeither
PreventionPreventanyoneofthe4conditionsfromhappening.
AvoidanceAllowalldeadlockconditions,butcalculatecyclesaboutto
happenandstopdangerousoperations..
Allowdeadlocktohappen.Thisrequiresusingboth:
DetectionKnowadeadlockhasoccurred.
Recovery Regaintheresources.
DEADLOCKS
Strategy
Most Operating systems do this!!

10. 7: Deadlocks 10
Donotallowoneofthefourconditionstooccur.
Mutualexclusion:
a)Automaticallyholdsforprintersandothernon-sharables.
b)Sharedentities(readonlyfiles)don'tneedmutualexclusion(andaren’t
susceptibletodeadlock.)
c)Preventionnotpossible,sincesomedevicesareintrinsicallynon-sharable.
Holdandwait:
a)Collectallresourcesbeforeexecution.
b)Aparticularresourcecanonlyberequestedwhennoothersarebeing
held.Asequenceofresourcesisalwayscollectedbeginningwiththe
sameone.
c)Utilizationislow,starvationpossible.
DEADLOCKS
Deadlock
Prevention

11. 7: Deadlocks 11
Donotallowoneofthefourconditionstooccur.
Nopreemption:
a)Releaseanyresourcealreadybeingheldiftheprocesscan'tgetan
additionalresource.
b)Allowpreemption-ifaneededresourceisheldbyanotherprocess,which
isalsowaitingonsomeresource,stealit.Otherwisewait.
Circularwait:
a)Numberresourcesandonlyrequestinascendingorder.
b)EACHofthesepreventiontechniquesmaycauseadecreaseinutilization
and/orresources.Forthisreason,preventionisn'tnecessarilythebest
technique.
c)Preventionisgenerallytheeasiesttoimplement.
DEADLOCKS
Deadlock
Prevention

12. 7: Deadlocks 12
Ifwehavepriorknowledgeofhowresourceswillberequested,it'spossibleto
determineifweareenteringan"unsafe"state.
Possiblestatesare:
Deadlock Noforwardprogresscanbemade.
UnsafestateAstatethatmayallowdeadlock.
SafestateAstateissafeifasequenceofprocessesexistsuchthatthere
areenoughresourcesforthefirsttofinish,andaseachfinishes
andreleasesitsresourcesthereareenoughforthenexttofinish.
Theruleissimple:Ifarequestallocationwouldcauseanunsafestate,donothonor
thatrequest.
NOTE:Alldeadlocksareunsafe,butallunsafesareNOTdeadlocks.
DEADLOCKS
Deadlock
Avoidance

13. 7: Deadlocks 13
NOTE:Alldeadlocksareunsafe,butallunsafesareNOTdeadlocks.
SAFE
DEADLOCK
UNSAFE
Only with luck will
processes avoid
deadlock.
O.S. can avoid
deadlock.
DEADLOCKS
Deadlock
Avoidance

14. 7: Deadlocks 14
Let'sassumeaverysimplemodel:eachprocessdeclaresitsmaximum
needs.Inthiscase,algorithmsexistthatwillensurethatnounsafestateis
reached.
EXAMPLE:
Thereexistsatotalof12tapedrives.Thecurrentstatelookslikethis:
Inthisexample,<p1,p0,p2>
isaworkablesequence.
Supposep2requestsandis
givenonemoretapedrive.
Whathappensthen?
ProcessMax NeedsAllocatedCurrent
Needs
P0 10 5 5
P1 4 2 2
P2 9 2 7
DEADLOCKS
Deadlock
Avoidance
There are multiple instances of
the resource in these examples.

15. 7: Deadlocks 15
Amethodusedtodetermineifaparticularstateissafe.It'ssafeifthereexistsa
sequenceofprocessessuchthatforalltheprocesses,there’sawaytoavoid
deadlock:
Thealgorithmusesthesevariables:
Need[I]–theremainingresourceneedsofeachprocess.
Work -Temporaryvariable–howmanyoftheresourcearecurrently
available.
Finish[I]–flagforeachprocessshowingwe’veanalyzedthatprocessornot.
need<=available+allocated[0]+..+allocated[I-1]<-Signofsuccess
Letworkandfinishbevectorsoflengthmandnrespectively.
DEADLOCKS
Safety Algorithm
Deadlock
Avoidance

16. 7: Deadlocks 16
1. Initializework =available
Initializefinish[i] =false,fori=1,2,3,..n
2. Findanisuchthat:
finish[i]==falseandneed[i]<=work
Ifnosuchiexists,gotostep4.
3. work =work+allocation[i]
finish[i] =true
gotostep2
4. iffinish[i]==trueforalli,thenthesystemisinasafestate.
DEADLOCKS Deadlock
Avoidance
Safety Algorithm

17. 7: Deadlocks 17
Dotheseexamples:
Considerasystemwith:fiveprocesses,P0P4,threeresourcetypes,A,B,C.
TypeAhas10instances,Bhas5instances,Chas7instances.
AttimeT0thefollowingsnapshotofthesystemistaken.
Is the system
in a safe state?
DEADLOCKS Deadlock
Avoidance
Safety Algorithm
134200P4
110112P3
006203P2
020002P1
233347010P0
CBACBACBA
AvailReqAlloc
Max Needs = allocated + can-be-requested

18. 7: Deadlocks 18
Dotheseexamples:
NowtryitagainwithonlyaslightchangeintherequestbyP1.
P1requestsoneadditionalresourceoftypeA,andtwomoreoftypeC.
Request1=(1,0,2).
IsRequest1<available?
Alloc  Req Avail
A B C AB C A B C
P0 0 1 0 74 3 1#30#
P1 3# 02# 02 0
P2 3 0 2 60 0
P3 2 1 1 01 1
P4 0 0 2 43 1
Produce the state
chart as if the
request is Granted
and see if it’s safe.
(We’ve drawn the
chart as if it’s
granted.
DEADLOCKS Deadlock
Avoidance
Safety Algorithm
Can the request
be granted?

19. 7: Deadlocks 19
Needanalgorithmthatdetermines
ifdeadlockoccurred.
Alsoneedameansofrecovering
fromthatdeadlock.
DEADLOCKS
Deadlock Detection
SINGLEINSTANCEOFARESOURCETYPE
•Wait-forgraph==removetheresources
fromtheusualgraphandcollapseedges.
•Anedgefromp(j)top(i)impliesthatp(j)is
waitingforp(i)torelease.

20. 7: Deadlocks 20
SEVERALINSTANCESOFARESOURCETYPE
Complexityisoforderm*n*n.
Weneedtokeeptrackof:
available -recordshowmanyresourcesofeachtypeareavailable.
allocation-numberofresourcesoftypemallocatedtoprocessn.
request -numberofresourcesoftypemrequestedbyprocessn.
Letworkandfinishbevectorsoflengthmandnrespectively.
DEADLOCKS
Deadlock Detection

21. 7: Deadlocks 21
1.Initialize work[]=available[]
Fori=1,2,...n,ifallocation[i]!=0then
finish[i]=false;otherwise,finish[i]=true;
2.Findanisuchthat:
finish[i]==falseandrequest[i]<=work
Ifnosuchiexists,gotostep4.
3.work=work+allocation[i]
finish[i]=true
gotostep2
4.iffinish[i]==falseforsomei,thenthesystemisindeadlockstate.
IFfinish[i]==false,thenprocessp[i]isdeadlocked.
DEADLOCKS
Deadlock Detection

22. 7: Deadlocks 22
EXAMPLE
Wehavethreeresources,A,B,andC.Ahas7instances,Bhas2instances,andChas6
instances.Atthistime,theallocation,etc.lookslikethis:
Is there a
sequence that will
allow deadlock to
be avoided?
Is there more than
one sequence that
will work?
200200P4
001112P3
000303P2
202002P1
000000010P0
CBACBACBA
AvailReqAlloc
DEADLOCKS
Deadlock Detection

23. 7: Deadlocks 23
EXAMPLE
SupposetheRequestmatrixischangedlikethis.Inotherwords,themaximumamountstobe
allocatedareinitiallydeclaredsothatthisrequestmatrixresults.
USAGE OF THIS
DETECTION ALGORITHM
Frequency of check
depends on how often a
deadlock occurs and how
many processes will be
affected.
Is there now a
sequence that will
allow deadlock to be
avoided?
200200P4
001112P3
1#00303P2
202002P1
000000010P0
CBACBACBA
AvailReqAlloc
DEADLOCKS
Deadlock Detection

24. 7: Deadlocks 24
So,thedeadlockhasoccurred.Now,howdowegettheresourcesbackandgainforward
progress?
PROCESSTERMINATION:
Coulddeletealltheprocessesinthedeadlock--thisisexpensive.
Deleteoneatatimeuntildeadlockisbroken(timeconsuming).
Selectwhototerminatebasedonpriority,timeexecuted,timetocompletion,needs
forcompletion,ordepthofrollback
Ingeneral,it'seasiertopreempttheresource,thantoterminatetheprocess.
RESOURCEPREEMPTION:
Selectavictim-whichprocessandwhichresourcetopreempt.
Rollbacktopreviouslydefined"safe"state.
Preventoneprocessfromalwaysbeingtheonepreempted(starvation).
DEADLOCKS
Deadlock Recovery

25. 7: Deadlocks 25
COMBINEDAPPROACHTODEADLOCKHANDLING:
•Typeofresourcemaydictatebestdeadlockhandling.Lookateaseofimplementation,and
effectonperformance.
•Inotherwords,thereisnoonebesttechnique.
•Casesinclude:
Preemptionformemory,
Preallocationforswapspace,
Avoidancefordevices(canextractNeedsfromprocess.)
DEADLOCKS
Deadlock Recovery

26. 7: Deadlocks 26
Inthissectionwehave:
Lookedatnecessaryconditionsforadeadlocktooccur.
Determinedhowtoprevent,avoid,detectandrecoverfromdeadlocks.
DEADLOCKS
WRAPUP