搜索
1Concurrency:DeadlockandStarvationChapter62Deadlock•Eachprocessinaprocessgroupiswaitingforsomeresourceoccupiedbyanotherprocessofthesamegroup,sothateveryprocessofthegroupisinstarvation•Permanentblockingofasetofprocessesthateithercompeteforsystemresourcesorcommunicatewitheachother•Noefficientsolution•Involveconflictingneedsforresourcesbytwoormoreprocesses3P1P2P3P44ProcessPProcessQ…………GetAGetB…………GetBGetA…………ReleaseAReleaseB…………ReleaseBReleaseA…………5ProcessPProcessQ…………GetAGetB…………ReleaseAGetA…………GetBReleaseB…………ReleaseBReleaseA…………6ReusableResources•Usedbyonlyoneprocessatatimeandnotdepletedbythatuse•Processesobtainresourcesthattheylaterreleaseforreusebyotherprocesses•Processors,I/Ochannels,mainandsecondarymemory,devices,anddatastructuressuchasfiles,databases,andsemaphores•Deadlockoccursifeachprocessholdsoneresourceandrequeststheother7ExampleofDeadlockDeadlockwouldbehappenedifExecutingsequenceisp0p1q0q1p2q28AnotherExampleofDeadlock•Spaceisavailableforallocationof200Kbytes,andthefollowingsequenceofeventsoccur•DeadlockoccursifbothprocessesprogresstotheirsecondrequestP1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;9ConsumableResources•Created(produced)anddestroyed(consumed)•Interrupts,signals,messages,andinformationinI/Obuffers•DeadlockmayoccurifaReceivemessageisblocking•Maytakeararecombinationofeventstocausedeadlock10ExampleofDeadlock•DeadlockoccursifreceivesareblockingP1......Receive(P2);Send(P2,M1);P2......Receive(P1);Send(P1,M2);11ResourceAllocationGraphs•Directedgraphthatdepictsastateofthesystemofresourcesandprocesses12ResourceAllocationGraphs13ConditionsforDeadlock•Mutualexclusion–Onlyoneprocessmayusearesourceatatime•Hold-and-wait–Aprocessmayholdallocatedresourceswhileawaitingassignmentofothers•Nopreemption–Noresourcecanbeforciblyremovedfromaprocessholdingit14ConditionsforDeadlock•Circularwait–aclosedchainofprocessesexists,suchthateachprocessholdsatleastoneresourceneededbythenextprocessinthechain–consequenceofthefirstthreeconditions1516ConditionsforDeadlock•MutualExclusion•Nopreemption•Holdandwait•Circularwait•Eachofthesefourconditionsisnecessary,andfourconditionstakentogetherconstitutenecessaryandsufficientconditionsfordeadlock17DeadlockPrevention•Designasysteminsuchawaythatthepossibilityofdeadlockisexcluded–MutualExclusion•Impracticable,operatingsystemsmustsupportthefeature–HoldandWait•Requireaprocessrequestallofitsrequiredresourcesatonetime•blocktheprocessuntilallrequestscanbegrantedsimultaneously•processmaybeheldupforalongtimewaitingforallitsrequests•resourcesallocatedtoaprocessmayremainunusedforalongtime.Theseresourcescouldbeusedbyotherprocesses18DeadlockPrevention•NoPreemption–Ifaprocessisdeniedafurtherrequest,itmustreleaseresourceandrequestagain–Ifaprocessrequestsaresourcethatiscurrentlyheldbyanotherprocess,OSmaypreemptthisprocesstorequireitreleasesitsresources–Practicalonlywhenthestatecanbeeasilysavedandrestoredlater,suchasprocessors•CircularWait–Definealinearorderingofresourcetypessuchthatoncearesourceisobtained,onlythoseresourceshigherinthelistcanbeobtained–Maydenyresourcesunnecessarily19DeadlockAvoidance•Adecisionismadedynamicallywhetherthecurrentresourceallocationrequestwill,ifgranted,potentiallyleadtoadeadlock•Requiresknowledgeoffutureprocessrequest20TwoApproachestoDeadlockAvoidance•Donotstartaprocessifitsdemandsmightleadtodeadlock•Resourceallocationdenial:Donotgrantanincrementalresourcerequesttoaprocessifthisallocationmightleadtodeadlock21ResourceAllocationDenial•ReferredtoasBanker’sAlgorithm•Stateofthesystemisthecurrentallocationofresourcestoprocess•Safestateisoneinwhichthereisatleastoneorderinwhichalltheprocessescanberuntocompletionwithoutresultinginadeadlock•Unsafestateisastatethatisnotsafe22DeterminationofaSafeStateInitialStateFigure6.7DeterminationofasafeState23DeterminationofaSafeStateP2RunstoCompletionFigure6.7DeterminationofasafeState24DeterminationofaSafeStateP1RunstoCompletionFigure6.7DeterminationofasafeState25DeterminationofaSafeStateP3RunstoCompletionFigure6.7DeterminationofasafeState26DeterminationofanUnsafeStateFigure6.8DeterminationofanUnsafeState27DeterminationofanUnsafeStateFigure6.8DeterminationofanUnsafeStateP1request:10128DeadlockAvoidanceLogic-Banker’sAlgorithm29DeadlockAvoidanceLogic-Banker’sAlgorithm30DeadlockAvoidance•ProsandCons–Norollbackandnopreemption–Lessrestrictivethandeadlockprevention–Maximumresourcerequirementmustbestatedinadvance–Processesunderconsiderationmustbeindependent;nosynchronizationrequirements–Theremustbeafixednumberofresourcestobeallocated–Noprocessmayexitwhileholdingresources31DeadlockDetection•Donotlimitresourcesaccessorrestrictprocessactions•Requestedresourcesaregrantedtoprocesseswheneverpossible•SomedeadlockdetectionalgorithmperformedperiodicallybyOStodetectthecircularwaitcondition•Oncedeadlockhasbeendetected,somerecoverystrategyistaken32DeadlockDetection•Detectionalgorithmdatastructure–Allocationmatrix,Resourcevector,andAvailablevector–RequestmatrixQisdefinedsuchthatqijrepresentstheamountofresourcesoftypejrequest