操作系统精髓与设计原理英文pptCha.ppt

1,Concurrency:DeadlockandStarvation,Chapter6,2,Deadlock,Eachprocessinaprocessgroupiswaitingforsomeresourceoccupiedbyanotherprocessofthesamegroup,sothateveryprocessofthegroupisinstarvationPermanentblockingofasetofprocessesthateithercompeteforsystemresourcesorcommunicatewitheachotherNoefficientsolutionInvolveconflictingneedsforresourcesbytwoormoreprocesses,3,P1,P2,P3,P4,4,ProcessPProcessQGetAGetBGetBGetAReleaseAReleaseBReleaseBReleaseA,5,ProcessPProcessQGetAGetBReleaseAGetAGetBReleaseBReleaseBReleaseA,6,ReusableResources,UsedbyonlyoneprocessatatimeandnotdepletedbythatuseProcessesobtainresourcesthattheylaterreleaseforreusebyotherprocessesProcessors,I/Ochannels,mainandsecondarymemory,devices,anddatastructuressuchasfiles,databases,andsemaphoresDeadlockoccursifeachprocessholdsoneresourceandrequeststheother,7,ExampleofDeadlock,DeadlockwouldbehappenedifExecutingsequenceisp0p1q0q1p2q2,8,AnotherExampleofDeadlock,Spaceisavailableforallocationof200Kbytes,andthefollowingsequenceofeventsoccurDeadlockoccursifbothprocessesprogresstotheirsecondrequest,P1,.,.,Request80Kbytes;,Request60Kbytes;,P2,.,.,Request70Kbytes;,Request80Kbytes;,9,ConsumableResources,Created(produced)anddestroyed(consumed)Interrupts,signals,messages,andinformationinI/ObuffersDeadlockmayoccurifaReceivemessageisblockingMaytakeararecombinationofeventstocausedeadlock,10,ExampleofDeadlock,Deadlockoccursifreceivesareblocking,P1,.,.,Receive(P2);,Send(P2,M1);,P2,.,.,Receive(P1);,Send(P1,M2);,11,ResourceAllocationGraphs,Directedgraphthatdepictsastateofthesystemofresourcesandprocesses,12,ResourceAllocationGraphs,13,ConditionsforDeadlock,MutualexclusionOnlyoneprocessmayusearesourceatatimeHold-and-waitAprocessmayholdallocatedresourceswhileawaitingassignmentofothersNopreemptionNoresourcecanbeforciblyremovedfromaprocessholdingit,14,ConditionsforDeadlock,Circularwaitaclosedchainofprocessesexists,suchthateachprocessholdsatleastoneresourceneededbythenextprocessinthechainconsequenceofthefirstthreeconditions,15,16,ConditionsforDeadlock,MutualExclusionNopreemptionHoldandwaitCircularwaitEachofthesefourconditionsisnecessary,andfourconditionstakentogetherconstitutenecessaryandsufficientconditionsfordeadlock,17,DeadlockPrevention,DesignasysteminsuchawaythatthepossibilityofdeadlockisexcludedMutualExclusionImpracticable,operatingsystemsmustsupportthefeatureHoldandWaitRequireaprocessrequestallofitsrequiredresourcesatonetimeblocktheprocessuntilallrequestscanbegrantedsimultaneouslyprocessmaybeheldupforalongtimewaitingforallitsrequestsresourcesallocatedtoaprocessmayremainunusedforalongtime.Theseresourcescouldbeusedbyotherprocesses,18,DeadlockPrevention,NoPreemptionIfaprocessisdeniedafurtherrequest,itmustreleaseresourceandrequestagainIfaprocessrequestsaresourcethatiscurrentlyheldbyanotherprocess,OSmaypreemptthisprocesstorequireitreleasesitsresourcesPracticalonlywhenthestatecanbeeasilysavedandrestoredlater,suchasprocessorsCircularWaitDefinealinearorderingofresourcetypessuchthatoncearesourceisobtained,onlythoseresourceshigherinthelistcanbeobtainedMaydenyresourcesunnecessarily,19,DeadlockAvoidance,Adecisionismadedynamicallywhetherthecurrentresourceallocationrequestwill,ifgranted,potentiallyleadtoadeadlockRequiresknowledgeoffutureprocessrequest,20,TwoApproachestoDeadlockAvoidance,DonotstartaprocessifitsdemandsmightleadtodeadlockResourceallocationdenial:Donotgrantanincrementalresourcerequesttoaprocessifthisallocationmightleadtodeadlock,21,ResourceAllocationDenial,ReferredtoasBankersAlgorithmStateofthesystemisthecurrentallocationofresourcestoprocessSafestateisoneinwhichthereisatleastoneorderinwhichalltheprocessescanberuntocompletionwithoutresultinginadeadlockUnsafestateisastatethatisnotsafe,22,DeterminationofaSafeStateInitialState,Figure6.7DeterminationofasafeState,23,DeterminationofaSafeStateP2RunstoCompletion,Figure6.7DeterminationofasafeState,24,DeterminationofaSafeStateP1RunstoCompletion,Figure6.7DeterminationofasafeState,25,DeterminationofaSafeStateP3RunstoCompletion,Figure6.7DeterminationofasafeState,26,DeterminationofanUnsafeState,Figure6.8DeterminationofanUnsafeState,27,DeterminationofanUnsafeState,Figure6.8DeterminationofanUnsafeState,P1request:,28,DeadlockAvoidanceLogic-BankersAlgorithm,29,DeadlockAvoidanceLogic-BankersAlgorithm,30,DeadlockAvoidance,ProsandConsNorollbackandnopreemptionLessrestrictivethandeadlockpreventionMaximumresourcerequirementmustbestatedinadvanceProcessesunderconsiderationmustbeindependent;nosynchronizationrequirementsTheremustbeafixednumberofresourcestobeallocatedNoprocessmayexitwhileholdingresources,31,DeadlockDetection,DonotlimitresourcesaccessorrestrictprocessactionsRequestedresourcesaregrantedtoprocesseswheneverpossibleSomedeadlockdetectionalgorithmperformedperiodicallybyOStodetectthecircularwaitconditionOncedeadlockhasbeendetected,somerecoverystrategyistaken,32,DeadlockDetection,DetectionalgorithmdatastructureAllocationmatrix,Resourcevector,andAvailablevectorRequestmatrixQisdefinedsuchthatqijrepresentstheamountofresourcesoftypejrequestedbyprocessIInitially,allprocessesareunmarkedAdeadlockexistsiffthereareatleasttwounmarkedprocessesattheendofthealgorithm,33,DeadlockDetection,DetectionalgorithmMarkeachprocessthathasarowintheAllocationmatrixofallzerosInitializeatemporaryvectorWtoequaltheAvailablevectorFindanindexIsuchthatprocessIiscurrentlyunmarkedandtheithrowofQislessthanorequaltoW.IfnosuchrowisfoundterminatethealgorithmIfsucharowisfound,markprocessIandaddthecorrespondingrowoftheAllocationmatrixtoW.Returntostep3,34,DeadlockDetection,35,StrategiesonceDeadlockDetected,AbortalldeadlockedprocessesBackupeachdeadlockedprocesstosomepreviouslydefinedcheckpoint,andrestartallprocessOriginaldeadlockmayoccurSuccessivelyabortdeadlockedprocessesuntildeadlocknolongerexistsSuccessivelypreemptresourcesuntildeadlocknolongerexists,36,SelectionCriteriaDeadlockedProcesses,LeastamountofprocessortimeconsumedsofarLeastnumberoflinesofoutputproducedsofarMostestimatedtimeremainingLeasttotalresourcesallocatedsofarLowestpriority,37,StrengthsandWeaknessesoftheStrategies,38,DiningPhilosophersProblem,fork0,f