操作系统概念(第七版_英文版)ch6

Chapter6:ProcessSynchronization6.2Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005Module6:ProcessSynchronizationBackgroundTheCritical-SectionProblemPeterson’sSolutionSynchronizationHardwareSemaphoresClassicProblemsofSynchronizationMonitorsSynchronizationExamplesAtomicTransactions6.3Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005BackgroundConcurrentaccesstoshareddatamayresultindatainconsistencyMaintainingdataconsistencyrequiresmechanismstoensuretheorderlyexecutionofcooperatingprocessesSupposethatwewantedtoprovideasolutiontotheconsumer-producerproblemthatfillsallthebuffers.Wecandosobyhavinganintegercountthatkeepstrackofthenumberoffullbuffers.Initially,countissetto0.Itisincrementedbytheproducerafteritproducesanewbufferandisdecrementedbytheconsumerafteritconsumesabuffer.6.4Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005SharedMemoryProducer:/*produceanitemandputinnextProduced*/while(true){while(count==BUFFER_SIZE);//donothingbuffer[in]=nextProduced;in=(in+1)%BUFFER_SIZE;count++;}Consumer:/*consumetheiteminnextConsumed*/while(true){while(count==0);//donothingnextConsumed=buffer[out];out=(out+1)%BUFFER_SIZE;count--;}6.5Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005RaceConditioncount++couldbeimplementedasregister1=countregister1=register1+1count=register1count--couldbeimplementedasregister2=countregister2=register2-1count=register2Considerthisexecutioninterleavingwith“count=5”initially:S0:producerexecuteregister1=count{register1=5}S1:producerexecuteregister1=register1+1{register1=6}S2:consumerexecuteregister2=count{register2=5}S3:consumerexecuteregister2=register2-1{register2=4}S4:producerexecutecount=register1{count=6}S5:consumerexecutecount=register2{count=4}WhataboutthecaseifwereversedtheorderofthestatementsatS4andS5?RaceCondition:theoutcomeoftheexecutiondependsontheparticularorderinwhichtheaccesstakesplace.register1andregister2maybethesamephysicalregister,whatwillhappen?6.6Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005Critical-SectionProblemCritical-Section:inwhichtheprocessesmaybechangingcommonvariables,updatingatable,writingafile,andsoonWemustdesignaprotocolthattheprocessescanusetocooperate,whenoneprocessisexecutinginitscriticalsection,nootherprocessistobeallowedtoexecuteinthiscriticalsection.Entrysection:eachprocessmustrequestpermissiontoenteritscriticalsection.Exitsection:followthecriticalsection,informotherprocessenterinthecriticalsection.Remaindersection.6.7Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005SolutiontoCritical-SectionProblem1.MutualExclusion-IfprocessPiisexecutinginitscriticalsection,thennootherprocessescanbeexecutingintheircriticalsections2.Progress-Ifnoprocessisexecutinginitscriticalsectionandthereexistsomeprocessesthatwishtoentertheircriticalsection,thentheselectionoftheprocessesthatwillenterthecriticalsectionnextcannotbepostponedindefinitely3.BoundedWaiting-AboundmustexistonthenumberoftimesthatotherprocessesareallowedtoentertheircriticalsectionsafteraprocesshasmadearequesttoenteritscriticalsectionandbeforethatrequestisgrantedAssumethateachprocessexecutesatanonzerospeedNoassumptionconcerningrelativespeedoftheNprocessesHandlecriticalsectionsinOS:PreemptivekernelandNonpreemptivekernel6.8Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005Peterson’sSolutionTwoprocesssolutionThetwoprocessessharetwovariables:intturn;Booleanflag[2]Thevariableturnindicateswhoseturnitistoenterthecriticalsection.Theflagarrayisusedtoindicateifaprocessisreadytoenterthecriticalsection.flag[i]=trueimpliesthatprocessPiisready!6.9Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005AlgorithmforProcessPiP0:while(true){flag[0]=TRUE;turn=1;while(flag[1]&&turn==1)//nooperation;//CRITICALSECTIONflag[0]=FALSE;//REMAINDERSECTION}P1:while(true){flag[1]=TRUE;turn=0;while(flag[0]&&turn==0)//nooperation;//CRITICALSECTIONflag[1]=FALSE;//REMAINDERSECTION}6.10Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005AproblemsolutionP0:while(true){while(turn!=false)//nooperation;//CRITICALSECTIONturn=true;//REMAINDERSECTION}P1:while(true){while(turn!=true)//nooperation;//CRITICALSECTIONturn=false;//REMAINDERSECTION}6.11Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005SynchronizationHardwareManysystemsprovidehardwaresupportforcriticalsectioncodeUniprocessors–coulddisableinterruptsCurrentlyrunningcodewouldexecutewithoutpreemptionGenerallytooinefficientonmultiprocessorsystemsOperatingsystemsusingthisnotbroadlyscalableModernmachinesprovidespecialatomichardwareinstructionsAtomic=non-interruptableEithertestmemorywordandsetvalue(TestAndSet())Orswapcontentsoftwomemorywords(Swap())6.12Silberschatz,GalvinandGagne©2005OperatingSystemConcepts–7thEdition,Feb8,2005TestAndndSetInstructionDefinition:booleanTestAndSet(boolean*target){booleanrv=*target