deadlock.pptx-operating systems -unit 2 notes

deadlock notes

1. Silberschatz,GalvinandGagne©209 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n C h a pt e r 7 : Deadl o cks

2. Chapter 7: Deadlocks Silberschatz,GalvinandGagne©209 7 . 2 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ ■ ■ ■ ■ ■ ■ ■ TheDeadlockProblem S y s t e m M od e l DeadlockCharacterization M e t ho d s f o r H a n d l i n g D e a d l o c k s DeadlockPrevention DeadlockAvoidance DeadlockDetection R e c o v e r y f r o m D e ad l o ck

3. Chapter Objectives Silberschatz,GalvinandGagne©209 7 . 3 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Todevelopadescriptionofdeadlocks,whichpreventsetsof concurrentprocessesfrom completingtheirtasks ■ Topresentanumberofdifferentmethodsforpreventingoravoiding deadlocksinacomputersystem

4. The Deadlock Problem Silberschatz,GalvinandGagne©209 7 . 4 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Asetofblockedprocesseseachholdingaresourceandwaitingto acquirearesourceheldbyanotherprocessintheset ■ E x a m pl e  S y s t e m h a s 2 di s k d r i v e s P 1 and P 2 eachholdonediskdriveandeachneedsanotherone ■ E x a m pl e  semaphores A and B ,initializedto1 P P 1 w a i t ( A ) ; w a i t ( B ) w a i t ( B ) ; w a i t ( A )

5. Bridge Crossing Example ■ ■ ■ Trafficonlyinonedirection Eachsectionofabridgecanbeviewedasaresource I f a d e ad l o c k o cc u r s , i t c a n b e r e s o l v e d i f o n e c a r b a c k s up (preemptresourcesandrollback) Severalcarsmayhavetobebackedupifadeadlockoccurs Starvationispossible Note–MostOSesdonotpreventordealwithdeadlocks ■ ■ ■ Silberschatz,GalvinandGagne©209 7 . 5 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

6. System Model Silberschatz,GalvinandGagne©209 7 . 6 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n R e s o u r c e t y p e s R 1 , R 2 , . . , R m CPUcycles,memoryspace,I/Odevices Eachresourcetype R i has W i instances. ■ Eachprocessutilizesaresourceasfollows:  r e q ues t use release  

7. Deadlock Characterization Silberschatz,GalvinandGagne©209 7 . 7 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ ■ Mutualexclusion: onlyoneproces atatimecanusea resource Holdandwait: aprocessholdingatleastoneresourceiswaiting toacquireadditionalresourcesheldbyotherprocesses Nopreemption: aresourcecanbereleasedonlyvoluntarilyby theprocessholdingit,afterthatprocesshascompleteditstask Circularwait: thereexistsaset{ P , P 1 ,…, P n }ofwaiting processessuchthat P iswaitingforaresourcethatisheldby P 1 , P 1 iswaitingforaresourcethatisheldby P 2 ,…, P n –1 iswaitingforaresourcethatisheldby P n ,and P n is waitingforaresourcethatisheldby P . Deadlockcanariseifourconditionsholdsimultaneously.

8. Resource-Allocation Graph Silberschatz,GalvinandGagne©209 7 . 8 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Asetofvertices V andasetofedges E . Vispartitionedintotwotypes: P = { P 1 , P 2 , … , P n } , t h e s e t c on s i s t i n g o f a l t h e p r o c e ss e s i n thesystem R ={ R 1 , R 2 ,…, R m },thesetconsistingofallresourcetypesin thesystem requestedge –directededge P i  R j a ssig n m en t e dg e – d i r e c t e d e d g e R j  P i

9. Resource-Allocation Graph (Cont.) ■ Process ■ ResourceTypewith4instances P i requestsinstanceof R j P i R j P i P i isholdinganinstanceof R j R j Silberschatz,GalvinandGagne©209 7 . 9 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

10. Example of a Resource Allocation Graph Silberschatz,GalvinandGagne©209 7 . 10 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

11. Resource Allocation Graph With A Deadlock Silberschatz,GalvinandGagne©209 7 . 1 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

12. Graph With A Cycle But No Deadlock Silberschatz,GalvinandGagne©209 7 . 12 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

13. Basic Facts Silberschatz,GalvinandGagne©209 7 . 13 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Ifgraphcontainsnocycles  nodeadlock ■ Ifgraphcontainsacycle   ifonlyoneinstanceperesourcetype,thendeadlock i f s e v e r a l in s t an c e s p e r e s ou r c e t y p e , p o ss i b i l i t y o f d e ad l o ck 

14. Methods for Handling Deadlocks Silberschatz,GalvinandGagne©209 7 . 14 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ E n s u r e t h a t h e s y s t e m w i l l n ev e r e n t e r a d e a d l o c k s t a t e ■ A l lo w t h e sy s t e m t o en t e r a de a dl o c k s t a t e a n d t h e n r e c o v e r ■ Ignoretheproblem andpretendthatdeadlocksneveroccurinthe system;usedbymostoperatingsystems,includingUNIX

15. Deadlock Prevention Silberschatz,GalvinandGagne©209 7 . 15 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Restrainthewaysrequestcanbemade MutualExclusion –notrequiredforsharableresources;must holdfornonsharableresources HoldandWait –mustguarante thatwheneveraprocess requestsaresource,itdoesnotholdanyotheresources  R e q u i r e p r o c e s s t o r e qu e s t a n d b e a l l o c a t e d a l i t s r e s ou r c e s beforeitbeginsexecution,oralowprocesstorequest resourcesonlywhentheprocesshasnone Lowresourceutilization;starvationpossible 

16. Deadlock Prevention (Cont.) Silberschatz,GalvinandGagne©209 7 . 16 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ NoPreemption –  I f a p r o c e s s t ha t i s ho ldi n g s o m e r e s ou r c e s r eq u e s t s an o t h e r resourcethatcannotbeimmediatelyalocatedtoit,thenall resourcescurrentlybeingheldarereleased Premptedresourcesareaddedtothelistofresourcesforwhich theproces iswaiting Processwillberestartedonlywhenitcanregainitsoldresources, aswelasthenewonesthatitisrequesting   ■ CircularWait –imposeatotalorderingofalresourcetypes,and r e q u i r e t h a t e a c h p r o c e s s r e qu e s t s r e s o u r c e s i n a n in c r e a s in g o r d e r o f enumeration

17. Deadlock Avoidance Silberschatz,GalvinandGagne©209 7 . 17 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Requiresthathesystem hassomeadditional apriori information available Simplestandmostusefulmodelrequiresthateachprocessdeclare the maximum number ofresourcesofeachtypethatitmayneed Thedeadlock-avoidancealgorithm dynamicallyexaminesthe resource-alocationstatetoensurethatherecanneverbea circular-waitcondition Resource-allocation state isdefinedbythenumberofavailableand allocatedresources,andthemaximum demandsoftheprocesses

18. Safe State Silberschatz,GalvinandGagne©209 7 . 18 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Whenaprocessrequestsanavailableresource,system mustdecideif immediateallocationleavesthesystem inasafestate System isin safestate ifthereexistsasequence< P 1 ,P 2 ,…,P n >of A L L t h e p r o c e ss e s i n t h e sy s t e m s s u c h t h a t f o r ea c h P i , t he resourcesthatP i canstillrequestcanbesatisfiedbycurrently availableresources+resourcesheldbyallthe P j ,with j < I ■ Thatis:  IfP i resourceneedsarenotimmediatelyavailable,then P i canwait untilal P j havefinished When P j isfinished, P i canobtainneededresources,execute, returnallocatedresources,andterminate When P i terminates, P i +1 canobtainitsneededresources,andso on  

19. Basic Facts Silberschatz,GalvinandGagne©209 7 . 19 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ I f a s y s t e m i s i n s a f e s t a t e  n o d e ad l o c k s ■ Ifasystem isinunsafestate  possibilityofdeadlock ■ Avoidance  ensurethatasystem willneverenteranunsafestate.

20. Safe, Unsafe, Deadlock State Silberschatz,GalvinandGagne©209 7 . 20 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

21. Avoidance algorithms Silberschatz,GalvinandGagne©209 7 . 21 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Singleinstanceofaresourcetype  Usearesource-allocationgraph ■ Multipleinstancesofaresourcetype  Usethebanker’salgorithm

22. Resource-Allocation Graph Scheme Silberschatz,GalvinandGagne©209 7 . 2 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Claim edge P i  R j indicatedthatprocess P j mayrequestresource R j ;representedbyadashedline ■ Claim edgeconvertstorequestedgewhenaprocessrequestsa resource ■ R e q u e s t ed g e c o n v e r t e d t o a n a ss i g n m e n t e d g e w he n t h e r e s o u r c e isalocatedtotheprocess ■ Whenaresourceisreleasedbyaprocess,assignmentedge reconvertstoaclaim edge ■ Resourcesmustbeclaimed apriori inthesystem

23. Resource-Allocation Graph Silberschatz,GalvinandGagne©209 7 . 23 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

24. Unsafe State In Resource-Allocation Graph Silberschatz,GalvinandGagne©209 7 . 24 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

25. Resource-Allocation Graph Algorithm Silberschatz,GalvinandGagne©209 7 . 25 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Supposethatprocess P i requestsaresource R j ■ Therequestcanbegrantedonlyifconvertingtherequestedgetoan assignmentedgedoesnotresultintheformationofacycleinthe resourceallocationgraph

26. Banker’s Algorithm Silberschatz,GalvinandGagne©209 7 . 26 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Multipleinstances ■ E a c h p r o c e s s m u s t a p r i o r i c l a i m m a x i m u m u s e ■ Whenaproces requestsaresourceitmayhavetowait ■ Whenaproces getsallitsresourcesitmustreturnthem inafinite amountoftime

27. Data Structures for the Banker’s Algorithm Silberschatz,GalvinandGagne©209 7 . 27 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n L e t n = n u m b e r o f p r o c e s e s , a n d m = n u m b e r o f r e s o u r c e s t y pe s . Available : Vectoroflength m .Ifavailable[ j ]= k ,thereare k instancesofresourcetype R j available Ma x : n x m m a t r i x . I f Ma x [ i, j ] = k , t h e n p r o c e s s P i m a y r e qu e s t a t most k instancesofresourcetype R j All o c ati o n : n x m m a t r i x . I f A ll o c a t i on [ i , j ] = k t he n P i i s c u r r e n t l y allocated k instancesof R j Need :n x m matrix.If Need [ i,j ]= k ,then P i mayneed k more instancesof R j tocompleteitstask Need [ i,j] = Max [ i,j ]– Allocation [ i,j ]

28. Safety Algorithm Silberschatz,GalvinandGagne©209 7 . 28 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Let Work and Finish bevectorsoflength m and n ,respectively. Initialize: Work = Available Finish [ i ]= false for i =0,1,…, n- 1 F in d a n i s u c h t ha t b o t h : (a ) F i ni s h [ i ] = f al s e ( b ) N e e d i  W o r k Ifnosuch i exists,gotostep4 W or k = W o r k + All o c ati o n i Fin i s h [ i ] = t r ue gotostep2 If Finish [ i ]= trueforal i ,thenthesystem isinasafestate

29. Resource-Request Algorithm for Process P i Silberschatz,GalvinandGagne©209 7 . 29 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n R equ e s t = r e q u e s t v e c t o r f o r p r o c e s s P i . I f R equ e s t i [ j ] = k t h e n process P i wants k instancesofresourcetype R j If Request i  Need i gotostep2.Otherwise,raiseerrorcondition, sinceprocesshasexceededitsmaximum claim If Request i  Available ,gotostep3.Otherwise P i mustwait, sinceresourcesarenotavailable Pretendtoallocaterequestedresourcesto P i bymodifyingthe stateasfolows: A v a i l ab l e = A v a i l a bl e – R e q u e s t ; A l o c a t i o n i = A l o c a t i o n i + R e q ue s t i ; Need i = Need i – Request i ; Ifsafe  theresourcesareallocatedtoPi Ifunsafe  Pimustwait,andtheoldresource-a l ocationstate isrestored

30. Example of Banker’s Algorithm Silberschatz,GalvinandGagne©209 7 . 30 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n 5 p r o c e ss e s P t h r o u g h P 4 ; 3resourcetypes: A ( 1 in s t an c e s ) , B ( 5 in s t a n c e s ) , a n d C ( 7 i n s t a n c es ) Snapshotatime T : Allocation Max Available P ABC 010 ABC 753 ABC 332 P 1 200 322 P 2 302 902 P 3 211 222 P 4 002 433

31. Example (Cont.) Silberschatz,GalvinandGagne©209 7 . 31 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Thecontentofthematrix Need isdefinedtobe Max – Allocation Need P ABC 743 P 1 122 P 2 600 P 3 011 P 4 431 T h e sys t e m i s i n a s a f e s t a t e s i n c e t h e s e q u en c e < P 1 , P 3 , P 4 , P 2 , P > satisfiessafetycriteria

32. Example: P 1 Request (1,0,2) Silberschatz,GalvinandGagne©209 7 . 32 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ C h e c k t h a t R e q u e s t  A v a i l a b l e ( t h a t i s , ( 1 , , 2 )  ( 3 , 3 , 2 )  t r u e Allocation Need Available ABC ABC ABC P 010 743 230 P 1 302 020 P 2 302 600 P 3 211 011 P 4 002 431 E x e c u t i n g s a f e t y a l g o r i t h m s h o w s t h a t s equ e n c e < P 1 , P 3 , P 4 , P , P 2 > satisfiessafetyrequirement Canrequestfor(3,3,0)by P 4 begranted? Canrequestfor(0,2,0)by P begranted?

33. Deadlock Detection Silberschatz,GalvinandGagne©209 7 . 3 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ A l lo w s y s t e m t o e n t e r d e a d l o c k s t a t e ■ Detectionalgorithm ■ Recoveryscheme

34. Single Instance of Each Resource Type Silberschatz,GalvinandGagne©209 7 . 34 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Maintain wait-for graph  Nodesareprocesses P i  P j i f P i i s w a i t in g f o r P j  ■ P e r i od i c a l y i n v o k e a n a l g o r i t h m t h a t s e a r c he s f o r a c y c l e i n t h e g r a ph . Ifthereisacycle,thereexistsadeadlock ■ A n a l g o r i t h m t o d e t e c t a c y c l e i n a g r a p h r e q u i r e s a n o r de r o f n 2 operations,where n isthenumberofverticesinthegraph

35. Resource-Allocation Graph and Wait-for Graph Resource-AllocationGraph C o r r e s po n di n g w a i t - f o r g r a p h Silberschatz,GalvinandGagne©209 7 . 35 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n

36. Several Instances of a Resource Type Silberschatz,GalvinandGagne©209 7 . 36 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ Available : Avectoroflength m indicatesthenumberofavailable resourcesofeachtype. ■ Alocation : An n x m matrixdefinesthenumberofresourcesofeach typecurrentlyallocatedtoeachproces. ■ R eq u e st : A n n x m m a t r i x in d i c a t e s t h e c u r r e n t r e q u e s t o f ea c h proces.If Request [ i ][ j ]= k ,thenprocess P i isrequesting k more instancesofresourcetype. R j .

37. Detection Algorithm Silberschatz,GalvinandGagne©209 7 . 37 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Let Work and Finish bevectorsoflength m and n ,respectivelyInitialize: (a) Work = Available (b)For i =1,2,…, n ,if Allocation i  0,then Finish [i]=false;otherwise, Finish [i]= true F in d a n in d e x i s u c h t h a t b o t h : (a ) Fin i s h [ i ] = f a l s e ( b ) R e q u e s t i  W or k Ifnosuch i exists,gotostep4

38. Detection Algorithm (Cont.) Silberschatz,GalvinandGagne©209 7 . 38 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Work = Work + Allocation i Finish [ i ]= true gotostep2 I f Fin i s h [ i ] = f a l s e , f o r s o m e i , 1  i  n , t h e n t h e sys t e m i s i n d e a d l o c k state.Moreover,if Finish [ i ]= false ,then P i isdeadlocked Algorithm requiresanorderofO( m x n 2) operationstodetect w h e the r th e s y s t e m i s i n de a d loc k e d s ta t e

39. Example of Detection Algorithm Silberschatz,GalvinandGagne©209 7 . 39 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Fiveprocesses P through P 4 ;threeresourcetypes A(7instances), B (2instances),and C (6instances) Snapshotatime T : Allocation RequestAvailable ABC ABC ABC P 010 00 00 P 1 200 202 P 2 303 000 P 3 211 100 P 4 002 002 Sequence< P , P 2 , P 3 , P 1 , P 4 >willresultin Finish [ i ]=trueforall i

40. Example (Cont.) Silberschatz,GalvinandGagne©209 7 . 40 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n P 2 requestsanadditionalinstanceoftype C Request ABC P 000 P 1 202 P 2 001 P 3 100 P 4 002 ■ Stateofsystem?  C a n r e c l a i m r e s ou r c e s h e l d b y p r o c e s s P , b u t in s u ffi c i e n t resourcestofulfilotherprocesses;requests Deadlockexists,consistingofprocesses P 1 , P 2 , P 3 ,and P 4 

41. Detection-Algorithm Usage Silberschatz,GalvinandGagne©209 7 . 41 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ When,andhowoften,toinvokedependson:  Howoftenadeadlockislikelytooccur? H o w m a n y p r o c e s e s w i l l n e e d t o b e r o l l e d b a ck ? oneforeachdisjointcycle  ■ Ifdetectionalgorithm isinvokedarbitrarily,theremaybemanycyclesin theresourcegraphandsowewouldnotbeabletotellwhichofthe manydeadlockedprocesses“caused”thedeadlock.

42. Recovery from Deadlock: Process Termination Silberschatz,GalvinandGagne©209 7 . 42 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n Abortaldeadlockedprocesses Abortoneprocessatatimeuntilthedeadlockcycleiseliminated Inwhichordershouldwechoosetoabort?  Priorityoftheproces Howlongprocesshascomputed,andhowmuchlongerto completion Resourcestheprocesshasused Resourcesprocessneedstocomplete Howmanyproceseswillneedtobeterminated Isproces interactiveorbatch?     

43. Recovery from Deadlock: Resource Preemption Silberschatz,GalvinandGagne©209 7 . 43 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n ■ S e l e c t i n g a v i c t i m – m i n i m i z e c o s t ■ Rollback–returntosomesafestate,restartprocessforthatstate ■ Starvation– sameprocessmayalwaysbepickedasvictim, includenumberofrollbackincostfactor

44. End of Chapter 7 Silberschatz,GalvinandGagne©209 Op e r a t i n g S y s t e m Conc e p t s– 8 t h E ditio n