deadlocks for Engenerring for he purpose

deadlock

1. Deadlocks

2. TheDeadlockProblem
●A deadlock consists of a setof blocked processes, each
holdingaresourceandwaitingtoacquirearesourceheldby
anotherprocessintheset
●Example#1
●Asystemhas2diskdrives
●P
1andP
2eachholdonediskdriveandeachneedstheotherone
●Example#2
●SemaphoresAandB,initializedto1
P0
wait(A);
wait(B);
P1
wait(B)
wait(A)

3. BridgeCrossingExample
●Trafficonlyinonedirection
●Theresourceisaone-lanebridge
●Ifadeadlockoccurs,itcanberesolvedifonecarbacks
up(preemptresourcesandrollback)
●Severalcarsmayhavetobebackedupifadeadlock
occurs
●Starvationispossible

4. SystemModel
●ResourcetypesR1,R2,...,Rm
CPUcycles,memoryspace,I/Odevices
●EachresourcetypeRi has1ormoreinstances
●Eachprocessutilizesaresourceasfollows:
●request
●use
●release

5. DeadlockCharacterization
Deadlockcanariseif fourconditionshold
simultaneously.
●Mutualexclusion:onlyoneprocessatatimecanusea
resource
●Holdandwait:aprocessholdingatleastoneresourceis
waiting to acquire additional resources held by other
processes
●Nopreemption:a resource can be released only
voluntarilybytheprocessholdingitafterthatprocesshas
completeditstask
●Circularwait:there exists a set {P0, P1, …, P0} of waiting
processessuchthatP0iswaitingforaresourcethatisheld
byP1,P1iswaitingforaresourcethatisheldby
P2,…,Pn–1iswaitingforaresourcethatisheldby
Pn,andPniswaitingforaresourcethatisheldbyP0

6. Resource-AllocationGraph
AsetofverticesVandasetofedges
E.
●Vispartitionedintotwotypes:
●P={P
1,P
2,…,P
n},thesetconsistingofall
theprocessesinthesystem
●R={R
1,R
2,…,R
m},thesetconsistingofall
resourcetypesinthesystem
●requestedge–directededgeP1→Rj
●assignmentedge–directededgeRj→Pi

7. Resource-AllocationGraph(Cont.)
●Process
●ResourceTypewith4instances
●PirequestsinstanceofRj
P
i
P
i
●PiisholdinganinstanceofRj
R
j
R
j

8. ResourceAllocationGraphWithADeadlock
BeforeP3requestedan
instanceofR2
AfterP3requestedan
instanceofR2

9. GraphWithACycleButNoDeadlock
ProcessP4mayreleaseitsinstanceofresourcetypeR2.That
resource can then be allocated to P3, thereby breaking the
cycle.

10. Relationshipofcyclestodeadlocks
●Ifaresourceallocationgraphcontainsnocycles⇒nodeadlock
●Ifaresourceallocationgraphcontainsacycleandifonlyoneinstanceexists
perresourcetype⇒deadlock
●Ifaresourceallocationgraphcontainsacycleandandifseveralinstances
existsperresourcetype⇒possibilityofdeadlock

11. MethodsforHandlingDeadlocks
●Prevention
●Ensurethatthesystemwillneverenteradeadlockstate
●Avoidance
●Ensurethatthesystemwillneverenteranunsafestate
●Detection
●Allowthesystemtoenteradeadlockstateandthenrecover
●DoNothing
●Ignoretheproblemandlettheuserorsystemadministratorrespondtothe
problem;usedbymostoperatingsystems,includingWindowsandUNIX

12. DeadlockPrevention
Topreventdeadlock,wecanrestrainthewaysthatarequestcanbe
made
●MutualExclusion–Themutual-exclusionconditionmust
holdfornon-sharableresources
●Hold and Wait –we must guarantee that whenever a
processrequestsaresource,it doesnotholdanyother
resources
●Require a process to request and be allocated all its
resourcesbeforeitbeginsexecution,orallowaprocessto
requestresourcesonlywhentheprocesshasnone
●Result:Lowresourceutilization;starvationpossible

13. DeadlockPrevention(Cont.)
●NoPreemption–
●Ifaprocessthatisholdingsomeresourcesrequestsanother
resource that cannot be immediately allocated to it, then all
resourcescurrentlybeingheldarereleased
●Preemptedresourcesareaddedtothelistofresourcesfor
whichtheprocessiswaiting
●Aprocesswillberestartedonlywhenitcanregainitsold
resources,aswellasthenewonesthatitisrequesting
●Circular Wait –impose a total orderingof all resource types, and
requirethateachprocessrequestsresourcesinanincreasingorder
ofenumeration.Forexample:
F(tapedrive)=1
F(diskdrive)=5
F(printer)=12

14. DeadlockAvoidance
Requiresthatthesystemhassomeadditionalapriori
information
available.
●Simplest and most useful model requires that each process
declarethemaximumnumberofresourcesofeachtypethatit
mayneed
●Thedeadlock-avoidancealgorithmdynamicallyexaminesthe
resource-allocation state to ensure that there can neverbe a
circular-waitcondition
●Aresource-allocationstateisdefinedbythenumberofavailable
and allocated resources, and the maximum demands of the
processes
apriori:formedorconceived
beforehand

15. SafeState
●When a process requests an available resource, the system
mustdecideifimmediateallocationleavesthesysteminasafe
state
●Asystemisinasafestateonlyifthereexistsasafesequence
●Asequenceofprocesses<P1,P2,…,Pn>isasafesequencefor
the current allocation state if, for each Pi, the resource requests
that Pi can still make, can be satisfied by currently available
resourcesplusresourcesheldbyallPj,withj<i.
●Thatis:
●IftheP
iresourceneedsarenotimmediatelyavailable,thenP
ican
waituntilallP
jhavefinished
●WhenP
jisfinished,P
icanobtainneededresources,execute,return
allocatedresources,andterminate
●WhenP
iterminates, P
i+1canobtainitsneededresources,andsoon

16. SafeState(continued)
●Ifasystemisinsafestate⇒nodeadlocks
●Ifasystemisinunsafestate⇒possibilityofdeadlock
●Avoidance⇒ensurethatasystemwillneverenteran
unsafestate

17. Safe,Unsafe,DeadlockState

18. Avoidancealgorithms
●Forasingleinstanceofaresourcetype,usearesource-
allocationgraph
●Formultipleinstancesofaresourcetype,usethebanker’s
algorithm

19. Resource-Allocation GraphScheme
●Introduceanewkindofedgecalledaclaimedge
●ClaimedgeP
i R
jindicates that process Pjmay
requestresourceR
j;whichisrepresentedbyadashedline
●Aclaimedgeconvertstoarequestedgewhenaprocess
requestsaresource
●Arequestedgeconvertstoanassignmentedgewhenthe
resourceisallocatedtotheprocess
●Whenaresourceisreleasedbyaprocess,anassignment
edgereconvertstoaclaimedge
●Resourcesmustbeclaimedaprioriinthesystem

20. Resource-Allocation Graphwith
ClaimEdges
Requ
e st
edge
Assignm
e nt
edge
Clai
m
edg
e
Clai
m
edge

21. UnsafeStateInResource-AllocationGraph
Assignm
e nt
edge
Requ
e st
edge
Assignm
e nt
edge
Clai
m
edg
e

22. Resource-AllocationGraphAlgorithm
●SupposethatprocessP
irequestsaresourceR
j
●The request can be granted only if converting the
requestedgetoanassignmentedgedoesnotresult
in the formation of a cyclein the resource allocation
graph

23. Banker’sAlgorithm
●Usedwhenthereexistsmultipleinstancesofaresourcetype
●Eachprocessmustaprioriclaimmaximumuse
●Whenaprocessrequestsaresource,itmayhavetowait
●Whenaprocessgetsallitsresources,itmustreturntheminafinite
amountoftime

24. DataStructuresfortheBanker’sAlgorithm
Letn=numberofprocesses,andm=numberofresources
types.
●Available:Vector of length m. If available [j] =k, there are k instances
ofresourcetypeRjavailable.
●Max:nxmmatrix.IfMax[i,j]=k,thenprocessPimayrequestat
mostkinstancesofresourcetypeRj.
●Allocation:nxmmatrix.IfAllocation[i,j]=kthenPiiscurrently
allocatedkinstancesofRj.
●Need:nxmmatrix.IfNeed[i,j]=k,thenPimayneedkmore
instancesofRjtocompleteitstask.
Need[i,j]=Max[i,j]–Allocation[i,j]

25. Operating
System
SafetyAlgorithm
1.LetWorkandFinishbevectorsoflengthmandn,respectively.
Initialize:
Work:=Available
Finish[i]=false fori-1,3,…,n.
2.Findandisuchthatboth:
(a)Finish[i]=false
(b)Needi≤Work
Ifnosuchiexists,gotostep4.
3.Work:=Work+Allocationi
Finish[i]:=true
gotostep2.
4.IfFinish[i]=trueforalli,thenthesystemisinasafestate.

26. Operating
System
Resource-RequestAlgorithmfor
ProcessP
i
Requesti= request vector for process Pi.If Requesti [j] =k then
processPiwantskinstancesofresourcetype Rj.
1.IfRequesti≤Needigotostep2.Otherwise,raiseerror
condition,sinceprocesshasexceededitsmaximumclaim.
2.If Requesti≤Available,gotostep3.OtherwisePimustwait,
sinceresourcesarenotavailable.
3.PretendtoallocaterequestedresourcestoPibymodifying
thestateasfollows:
Available:=Available-Requesti;
Allocationi:=Allocationi+Requesti;
Needi:=Needi–Requesti;;
•Ifsafe⇒theresourcesareallocatedtoPi.
•Ifunsafe⇒Pi mustwait,andtheoldresource-allocation
stateisrestored

27. 7.6DeadlockDetection

28. DeadlockDetection
●Fordeadlockdetection,thesystemmustprovide
●Analgorithmthatexaminesthestateofthesystemtodetectwhethera
deadlockhasoccurred
●Andanalgorithmtorecoverfromthedeadlock
●Adetection-and-recoveryschemerequiresvariouskindsofoverhead
●Run-timecostsofmaintainingnecessaryinformationandexecutingthe
detectionalgorithm
●Potentiallossesinherentinrecoveringfromadeadlock

29. SingleInstanceofEachResourceType
●Requiresthecreationandmaintenanceofawait-forgraph
●Consistsofavariantoftheresource-allocationgraph
●Thegraphisobtainedbyremovingtheresourcenodesfrom
a resource-allocation graph and collapsing the appropriate
edges
●Consequently;allnodesareprocesses
●P
i→P
jif P
iiswaitingforP
j.
●Periodicallyinvokeanalgorithmthatsearchesforacycle
inthegraph
●Ifthereisacycle,thereexistsadeadlock
●Analgorithmtodetectacycleinagraphrequiresanorderof
n
2
operations,wherenisthenumberofverticesinthegraph

30. Resource-Allocation GraphandWait-forGraph
Resource-Allocation
Graph
Correspondingwait-for
graph

31. MultipleInstancesofaResourceType
Requireddata
structures:
●Available:Avectoroflengthmindicatesthenumberof
availableresourcesofeachtype.
●Allocation:Annxmmatrixdefinesthenumberof
resourcesofeachtypecurrentlyallocatedtoeachprocess.
●Request:Annxmmatrixindicatesthecurrentrequestof
eachprocess.IfRequest[ij]=k,thenprocessPiis
requestingkmoreinstancesofresourcetype.Rj.

32. Detection-AlgorithmUsage
●When,andhowoften,toinvokethedetectionalgorithmdependson:
●Howoftenisadeadlocklikelytooccur?
●Howmanyprocesseswillbeaffectedbydeadlockwhenithappens?
●If the detection algorithm is invoked arbitrarily, there may be many
cyclesintheresourcegraphandsowewouldnotbeabletotellwhich
oneofthemanydeadlockedprocesses“caused”thedeadlock
●Ifthedetectionalgorithmisinvokedforeveryresourcerequest,suchan
actionwillincuraconsiderableoverheadincomputationtime
●AlessexpensivealternativeistoinvokethealgorithmwhenCPU
utilizationdropsbelow40%,forexample
●Thisisbasedontheobservationthatadeadlockeventuallycripplessystem
throughputandcausesCPUutilizationtodrop

33. 7.7RecoveryFromDeadlock

34. RecoveryfromDeadlock
●TwoApproaches
●Processtermination
●Resourcepreemption

35. RecoveryfromDeadlock:ProcessTermination
●Abortalldeadlockedprocesses
●Thisapproachwillbreakthedeadlock,butatgreatexpense
●Abortoneprocessatatimeuntilthedeadlockcycleiseliminated
●Thisapproachincursconsiderableoverhead,since,aftereachprocessis
aborted,adeadlock-detectionalgorithmmustbere-invokedtodetermine
whetheranyprocessesarestilldeadlocked
●Manyfactorsmayaffectwhichprocessischosenfortermination
●Whatisthepriorityoftheprocess?
●Howlonghastheprocessrunsofarandhowmuchlongerwilltheprocess
needtorunbeforecompletingitstask?
●Howmanyandwhattypeofresourceshastheprocessused?
●Howmanymoreresourcesdoestheprocessneedinordertofinishits
task?
●Howmanyprocesseswillneedtobeterminated?
●Istheprocessinteractiveorbatch?

36. Recovery fromDeadlock:ResourcePreemption
●With this approach, we successively preempt some resources
fromprocessesandgivetheseresourcestootherprocessesuntil
thedeadlockcycleisbroken
●Whenpreemptionisrequiredtodealwithdeadlocks,thenthree
issuesneedtobeaddressed:
●Selectingavictim–Whichresourcesandwhichprocessesaretobe
preempted?
●Rollback–Ifwepreemptaresourcefromaprocess,whatshouldbe
donewiththatprocess?
●Starvation–Howdoweensurethatstarvationwillnotoccur?Thatis,
how can we guarantee that resources will not always be preempted
fromthesameprocess?

37. Summary
●Fournecessaryconditionsmustholdinthesystemforadeadlock
tooccur
●Mutualexclusion
●Holdandwait
●Nopreemption
●Circularwait
●Fourprincipalmethodsfordealingwithdeadlocks
●Usesomeprotocolto(1)preventor(2)avoiddeadlocks,ensuring
thatthesystemwillneverenteradeadlockstate
●Allowthesystemtoenteradeadlockstate,(3)detectit,andthen
recover
Recoverbyprocessterminationorresourcepreemption
●(4) Do nothing; ignore the problem altogether and pretend that
deadlocksneveroccurinthesystem(usedbyWindowsandUnix)
●Topreventdeadlocks,wecanensurethatatleastoneofthefour
necessaryconditionsneverholds