操作系统课件_ProcessManagement.ppt

OperatingSystem Chapter3 ProcessesandThreadsGuangShunShiDepartmentofComputerScience NanKaiUniversityEmail gsshi WebSite http 202 113 15 72 osteach FeatureofOS VirtualandabstractOSisanunifiedshell coverforuserstocontrolcomputerOSprovidesanabstractinterfacefordifferentkindsofhardwareCocurrentandsharingPseudoparallelism runmultipleprogramsinsametimeSharingandmutualexclusion howtoenhancefunctionandimproveperformanceUncertaintyThecontextofCPUcannotrecurredexactlyintime sharingOSTheenvironmentofcomputercannotbeestablishedduringrunningcycleofaprogram OperatingSystem CITS NanKaiUniversity 2 DefinitionofOS Howtodefine OperatingSystem OperatingSystem CITS NanKaiUniversity 3 Aspecialkindofsystemsoftwarethatcanmanagecomputerinefficientandreasonableway Itisinchargeofmanaginghardwareresource controllingtherunningofprogramsandprovidingusefulservices Itisaconvenientplatformforpeopletousecomputer ConceptofProcess BasicdatastructuretouseCPULogicalProgram designedandimplementedbyuserCPUInstructionsequence essentialoflogicalprogramProcess internalDSbetweenprogramandinstructionDiscussionaboutProgrammingDataStructure theformatandoperationaboutspecifiedkindofdata information Algorithm therulesandstepsofcomputingforspecifiedpurposeEngineering theprocedureabouthowtodesignandimplementDSandalgorithms OperatingSystem CITS NanKaiUniversity 4 EvolutionofProcessmodel Firstgeneration relay vacuumtubesandplugboardsNoprogram noprocessSecondgeneration BatchsystemSingleprogramtoprocessalljobsThirdgeneration Multiprogramming timesharingIBM7094 OS 360 Morethanonejobscanbestoredinmemory butmustbeprocessedinFIFOmode static CTSS 1962 CPUcanswitchfromidlejobstoactivatedjobs dynamicandcocurrent Forthgeneration modernoperatingsystemMorematureprocessmodelMoreefficientmechanismforprocessschedulingandcommunicationMorecomplexalgorithmformemoryprotectionandmanagement OperatingSystem CITS NanKaiUniversity 5 EssentialofCocurrency StaticmultiprogrammingMorethanoneprocessarestoredinmemoryEachprocessoccupiesCPUexclusivelybeforeterminationCPUhastobeidlewhenprocesswaitingforI OoperationLifecycleofstaticmultiprogrammingSequential close exclusiveandcertainTherunningofprogramcanreoccurexactlyCocurrentmultiprogrammingEachprocessoccupiesCPUonlywhenitneedCPUTheidleprocessshouldgiveupCPUandotherprocesswilloccupyCPULifecycleofcocurrentmultiprogrammingCocurrent discontinuous preemptiveanduncertainTherunningofprogramdependsonuncertainenvironment OperatingSystem CITS NanKaiUniversity 6 EssentialofCocurrency StaticmultiprogrammingMorethanoneprocessarestoredinmemoryEachprocessoccupiesCPUexclusivelybeforeterminationCPUhastobeidlewhenprocesswaitingforI OoperationLifecycleofstaticmultiprogrammingSequential close exclusiveandcertainTherunningofprogramcanreoccurexactlyCocurrentmultiprogrammingEachprocessoccupiesCPUonlywhenitneedCPUTheidleprocessshouldgiveupCPUandotherprocesswilloccupyCPULifecycleofcocurrentmultiprogrammingCocurrent discontinuous independent preemptiveanduncertainTherunningofprogramdependsonuncertainenvironment OperatingSystem CITS NanKaiUniversity 7 CocurrentVSParellel ParellelMorethanonejobsareexecutedatthesametimeForexample thesuperscalarandsuper pipelineinCPUCocurrentOnlyonejobisexecutedatanytimeMorethanonejobsarefinishedinsametimezone OperatingSystem CITS NanKaiUniversity 8 EfficiencyofCocurrency OperatingSystem CITS NanKaiUniversity 9 EfficiencyofCocurrency EfficiencyundersequentialmodeTimeconsumingfor2jobs 80EfficiencyofCPU 40 80 50 EfficiencyofDEV1 15 80 18 75 EfficiencyofDEV2 25 80 31 25 EfficiencyundercocurrentmodeTimeconsumingfor2jobs 45EfficiencyofCPU 40 45 89 EfficiencyofDEV1 15 45 33 EfficiencyofDEV2 25 45 55 6 OperatingSystem CITS NanKaiUniversity 10 Challengecausedbycocurrent Sharing resourceallocationandconflictresolvingReasonableandefficientstrategySystemstability deadlockavoidingUncertainty mutualexclusionandsynchronismDiscontinuousrunningcausedshareddatachaosHowtorealizecooperationbetweenprocessesIndependency schedulingandprotectionHowtoprotectmemoryofeachprocessHowtoscheduledifferentprocesstooccupyCPUUtilitiesforhigh levelapplicationCommunicationbetweenprocessesProcess threadhierarchies OperatingSystem CITS NanKaiUniversity 11 Sampleofsynchronism cocurrentprocesses Get CopyandPutFandG databufferthatcanstoremanydataitemsSandT databufferthancanonlystoreonedataitemPurpose transferdatafromFtoGViaSandTDanger therunningorderof3processes OperatingSystem CITS NanKaiUniversity 12 Sampleofsynchronism cont OperatingSystem CITS NanKaiUniversity 13 Sampleofsynchronism cont OperatingSystem CITS NanKaiUniversity 14 ConceptofProcess Whatisprocess OperatingSystem CITS NanKaiUniversity 15 Description theprocedureofprogram software running Differencebetweenprocessandprogram ProcessVSProgram OperatingSystem CITS NanKaiUniversity 16 阅读菜谱 准备原料 烹制菜肴 饭菜 阅读洗衣机手册 准备衣服 洗衣粉 设定参数 洗衣服 干净衣服 程序 输入 运行 输出 程序 输入 运行 输出 分时切换 洗衣进程 做饭进程 DefinitionofProcess Whatisprocess OperatingSystem CITS NanKaiUniversity 17 Processistherunningprocedureofspecifiedprogram itcontainsinput output programandstatusIntime sharingOS CPUissharedbymultipleprocesses differentalgorithmsareusedtoscheduleprocesses ProcessStates 1 OperatingSystem CITS NanKaiUniversity 18 UsageofprocessstatesIndicatethesituationofrunningprocedureBasicstatesRunning actuallyusingtheCPUincurrentinstanceReady runnableandiswaitingforCPUBlocked unabletorununtilwaitingsomeexternaleventhappensOtherstatesNew datastructureoftheprocesshasbeencreated buttherunningimageisnotreadyExit theprocesshasfinishedalljobs butthedatastructurehasnotbeendeletedSuspend therunningimagehasbeenswappedtoharddisk ProcessStates 2 OperatingSystem CITS NanKaiUniversity 19 Running Blocked Ready Theprocessisreadytorun Pausedforexternalevent OSisinchargeofprocessscheduling ProcessStatestransitions OperatingSystem CITS NanKaiUniversity 20 RunningtoReadyTheprocesshasbeenscheduledtogiveupCPURunningtoBlockedTheprocessexecutedsomeoperationdependonexternaldevicesorevents soitpausedBlockedtoReadyTheexternaleventhashappened theblockedprocesscanexecuterestoperationReadytoRunningTheprocessgottheprivilegetouseCPU ComplexProcessStates 1 OperatingSystem CITS NanKaiUniversity 21 ProcessStatesinWinXP 2K OperatingSystem CITS NanKaiUniversity 22 ProcessstatesinLinux 1 TASK RUNNINGTheprocessiseitherexecutingonaCPUorwaitingtobeexecutedTASK INTERRUPTIBLETheprocessissuspended sleeping untilsomeconditionbecomestrue Raisingahardwareinterrupt releasingasystemresourcetheprocessiswaitingfor ordeliveringasignalareexamplesofconditionsthatmightwakeuptheprocess putitsstatebacktoTASK RUNNING TASK UNINTERRUPTIBLELikeTASK INTERRUPTIBLE exceptthatdeliveringasignaltothesleepingprocessleavesitsstateunchanged OperatingSystem CITS NanKaiUniversity 23 ProcessstatesinLinux 2 TASK STOPPEDProcessexecutionhasbeenstopped theprocessentersthisstateafterreceivingaSIGSTOP SIGTSTP SIGTTIN orSIGTTOUsignalTASK TRACEDProcessexecutionhasbeenstoppedbyadebugger Whenaprocessisbeingmonitoredbyanother suchaswhenadebuggerexecutesaptrace systemcalltomonitoratestprogram eachsignalmayputtheprocessintheTASK TRACEDstateEXIT ZOMBIEProcessexecutionisterminated buttheparentprocesshasnotyetissuedawait4 orwaitpid systemcalltoreturninformationaboutthedeadprocessEXIT DEADThefinalstate parentprocesshasjustissuedawait4 orwaitpid systemcallfortheprocessanditisbeingremovedbythesystem OperatingSystem CITS NanKaiUniversity 24 ProcessstatesinLinux 3 OperatingSystem CITS NanKaiUniversity 25 Running Interruptible Uninterruptible STOP Traced ZOMBIE DEAD CPU Schedule Timeout Schedule Interruptible sleep on Schedule Sleep on Wakeup Wakeup interruptible Do fork SIGSTOPSIGTSTPSIGTTINSIGTTOUT Ptrace SIG KILL SIG CONTWakeup Do Exit DataStructureofProcess ProcessControlBlock PCB DatastructuredesignedforprocessMaintainedbyOSkernel usercan tmodifyitdirectlyOthernames processdescriptor processattributePCBTableorPCBListPCBsofallprocessesaremanagedandstoredinspecifiedmemoryregion namePCBtable listThesizeofPCBtabledeterminesconcurrencydegreeProcesseswithdifferentstatesarestoredindifferentPCBtables OperatingSystem CITS NanKaiUniversity 26 ContentofPCB OperatingSystem CITS NanKaiUniversity 27 Task StructinLinux OperatingSystem CITS NanKaiUniversity 28 PCBTable OperatingSystem CITS NanKaiUniversity 29 ProcessImage ConceptofprocessimageDescriptionaboutwholelifecycleofprocessContentofprocessimageUser levelcontextUserspaceoftheprocessSuchastext stack anddatasectionRegister levelcontextPC PSW IRStackpointerandothergeneralregistersSystem levelcontextPCBandresourceassociatedwiththeprocessDynamickernelstack OperatingSystem CITS NanKaiUniversity 30 OperatingSystem CITS NanKaiUniversity 31 Scheduling WhenProcessiscreatedorProcessexitProcessblocksonI OI OinterruptoccursWhyMakeproperchoiceAssureefficiencyofCPUHowSelecttheprocesstorunaccordingsomepolicySwitchCPUcontextbetweenprocessesNoticeThefrequencyofschedulingisveryimportantNonpreemptiveandpreemptivealgorithmsCPU boundandI O boundprocess OperatingSystem CITS NanKaiUniversity 32 GoalofScheduling AllsystemsFairness giveeachprocessafairshareoftheCPUPolicyenforcement seeingthatstatedpolicyiscarriedoutBalance keepingallpartsofthesystembusyBatchsystemsThroughput maximizejobsperhourTurnaroundtime minimizetimebetweensubmissionandterminationCPUutilization keeptheCPUbusyallthetimeInteractivesystemResponsetime respondtorequestquicklyProportionality meetusers expectationsReal timesystemMeetingdeadlines avoidlosingdataPredictability avoidqualitydegradationinmultimediasystems OperatingSystem CITS NanKaiUniversity 33 Schedulinginbatchsystem First comeFirst served nonpreemptiveSimpleandeasy alsofairinmanyconditionLowCPUefficiencyforI O boundprocessShortestjobfirst nonpreemptiveFewTurnaroundtimeNotoptimalinrealenvironmentShortestremainingtimenext preemptiveComparenewjob stimewithcurrentprocessNewjobwilloccupyCPUifshorterthancurrentprocessThree levelschedulingAdmissionschedulerMemoryschedulerCPUscheduler OperatingSystem CITS NanKaiUniversity 34 Three levelscheduling OperatingSystem CITS NanKaiUniversity 35 Schedulingininteractivesystem Round robinscheduling preemptiveAssignquantumtoeachprocessBlockingorfinishingwillcauseprocessswitchProcessswitchalsooccurwhenquantumisexhaustedOpenissue howtodefinethelengthofquantum Priorityscheduling preemptiveEachprocesshasitpriorityandsortedinascendingorderCPUpicksuptheprocesswithhighestpriorityDynamicpriority avoidingstarvingMultiplequeueMultiplepriorityclass processwithsamepriorityisstoredinsamequeueSelectqueueaccordingpriority RRinqueueFairness shorterquantumhigherpriority longerquantumlowerpriority OperatingSystem CITS NanKaiUniversity 36 Schedulingininteractivesystem ShortestprocessnextAgingalgorithm estimatesaboutnextrunGuaranteedschedulingShareCPUtimewithallprocessesequallyComputetheratioofactualCPUtimeconsumedtoCPUtimeentitledRuntheprocesswithlowestratioLotteryschedulingGivelotteryticketstoeachprocessTheticketscanexchangedbetweenprocessesSelectlotteryrandomlyandtheprocessownsthelotterywillgotCPU OperatingSystem CITS NanKaiUniversity 37 Schedulingimplementation CasestudyUnix dynamicpriority5 3BSD multiplequeueWindows priorityschedulingLinux preemptivescheduling OperatingSystem CITS NanKaiUniversity 38 Communicationbetweenprocesses IssuesaboutInterprocessCommunicationAsynchronism passinformationtootherprocessesExclusion competewithotherprocessesforsomeresouceSynchronism maintainproperrunningsequenceDifficultyofInterprocesscommunicationInformationformat signal switch messageExclusionandsynchronism cooperationissuesPyramidrules20 difficultproblemsand80 easyproblems20 energyfor80 easyproblems while80 energyfor20 difficultproblems OperatingSystem CITS NanKaiUniversity 39 Exclusion Spoolerdirectory OperatingSystem CITS NanKaiUniversity 40 Out 4 In 7 ProcA N f s In In 7InsertFileIntoSpooler N f s In N f s In 8 ProcB N f s In In 8InsertFileIntoSpooler N f s In N f s In 9 Exclusion Spoolerdirectory OperatingSystem CITS NanKaiUniversity 41 Out 4 In 7 ProcA N f s In In 7 ProcB N f s In In 7InsertFileIntoSpooler N f s In N f s In 8 ProcA InsertFileIntoSpooler N f s In N f s In 8 Synchronism Driver Conductor OperatingSystem CITS NanKaiUniversity 42 DriverWhile True Startbus Driving Stopbus ConductorWhile True Closedoor Sellticket Opendoor PropersequenceWhile True D Startbus C Closedoor D Driving C Sellticket D Stopbus C Opendoor AnalysisaboutIPCproblem ReasonofIPCproblemPhysicalsequence dependsonschedulingLogicalsequence dependsonapplicationpurposeRacecondition ExclusiveresourceallocationIPCprobleminkernelanduserspaceKernelspace I OdevicemanagementUserspace networkapplication database KeyofIPCproblemRealizebothphysicalandlogicalsequenceThelogicalsequenceisindependentonschedulingThelogicalsequencecanbecontrolledbyuser OperatingSystem CITS NanKaiUniversity 43 IPCproblem producer consumer OperatingSystem CITS NanKaiUniversity 44 ProblemdescriptionAfixed sizebufferforstoringinformationProducer putnewitemintobuffer sleepwhenFULLConsumer Getnewitemfrombuffer sleepwhenEMPTY IPCproblem diningphilosophers OperatingSystem CITS NanKaiUniversity 45 ProblemdescriptionPhilosopher eatingandthinking alternativelyEating getleftandrightchopsticksandeatThinking puttwochopsticksStarvation allphilosophersgetonechopsticks IPCproblem Reader Writer OperatingSystem CITS NanKaiUniversity 46 ProblemdescriptionWriter putinformationintosharedbufferReader getinformationfromsharedbufferExclusion reader writercan taccessthebufferwhenanywriterisputtingitem butmultiplereadercangetitematsametimeSynchronism WritersleepwhenFULL whileReadersleepwhenEMPTY IPCproblem SleepingBarber OperatingSystem CITS NanKaiUniversity 47 ProblemdescriptionOnechairforbarbering andNchairsforwaitingCustomer occupybarberingchair orsitonwaitingchair orleavingwhenallchairsarefullBarber 0customersleeping orworking Conceptaboutmutualexclusion RaceconditionMorethanoneprocessesarecompeteforsomeexclusiveresource otherprocessesshouldn taccesstheresourcewhenaprocessisoccupyingtheresourceCriticalregion criticalsectionThecodesectionthataccesstheexclusiveresourceiscalledcriticalregionCriteriaforgoodsolutionNotwoprocessmaybesimultaneouslyinsidetheircriticalregionNoassumptionsmybemadeaboutspeedsorthenumberofCPUsNoprocessrunningoutsideitscriticalregionmayblockotherprocessesNoprocessshouldhavetowaitforevertoenteritscriticalregion OperatingSystem CITS NanKaiUniversity 48 Conceptaboutmutualexclusion OperatingSystem CITS NanKaiUniversity 49 ProcB ProcA Aenterscriticalregion Aleavescriticalregion BtrytoenterCR BentersCR BleavesCR T1 T2 T3 T4 Time ConceptaboutSynchronism LogicalsequenceCausedbyapplicationpurpose can tbepredictedMaybebrokenbyschedulingDifferencebetweensynchronismandmutualexclusionMutualexclusion preventotherprocessenterCRSynchronism realizetheproperlogicalsequenceHowtodesignpropermethod General withoutassumptionorlimitationSimple easytorealizeandmaintainEfficientandsafe OperatingSystem CITS NanKaiUniversity 50 Modeling OperatingSystem CITS NanKaiUniversity 51 51 Model Method Technology Naturalworld Applicationpurpose 改 造 世 界 界 世 识 认 Problemdescription Resolution processingstepsbasedondesignrules Implementationofthemethodindifferentways ProblemmodelsofIPC Producer ConsumerBounded bufferproblemDinningphilosophersSynchronismbasedonmutualexclusionReader WritherMulti processsynchronismbasedonmutualexclusionSleepingbarberSynchronismandmutualexclusionundercomplexapplicationenvironment OperatingSystem CITS NanKaiUniversity 52 SolutionsofIPCproblems BusywaitingSleepandwakeupMessagepassing OperatingSystem CITS NanKaiUniversity 53 Busywaiting DesignrulesSetaglobalvariabletostorethestatusofCRProcesschecksthisvariablebeforeentersCRMethodsDisablinginterruptsLockvariablesStrictalternationPeterson ssolutionTSLinstruction OperatingSystem CITS NanKaiUniversity 54 Disablinginterrupts StrongpointSolvemutualexclusionproblemsdrasticallyWeaknessDangerousforuserscancloseinterruptsUselessundermultipleCPUscondition OperatingSystem CITS NanKaiUniversity 55 ProcAClose INT Critical region Open INT ProcBClose INT Critical region Open INT Lockvariable WeaknessDoesn tresolvetheproblemessentially OperatingSystem CITS NanKaiUniversity 56 ProcAWhile lock 0 lock 1 Critical region lock 0 ProcBWhile lock 0 lock 1 Critical region lock 0 Lock 0 Drawbackoflockvariable OperatingSystem CITS NanKaiUniversity 57 Lock 0 ProcAWhile lock 0 ProcBWhile lock 0 ProcAlock 1 Critical Region ProcBlock 1 Critical Region CPUswitch CPUswitch ProcAentersCR CPUswitch ProcBentersCR Strictalternation WeaknessWasteCPUtimeProcessrunningoutsideofCRblocksotherprocess OperatingSystem CITS NanKaiUniversity 58 ProcAWhile TRUE While turn 0 Critical region turn 1 Nocritical region turn 0 ProcBWhile TRUE While turn 1 Critical region turn 0 Nocritical region Drawbackofstrictalternation OperatingSystem CITS NanKaiUniversity 59 ProcAEnter LeaveCR Nocritical region turn 0 ProcBEnter LeaveCR Nocritical region WaitforenteringCR Propersequenceinfirstturn ProcBwaitfornextturn butprocAblockedprocBwhileprocAisnotinCR Dekker ssolution OperatingSystem CITS NanKaiUniversity 60 版权所有 转载请注明出处 ProcPWhile TRUE Pturn TRUE While Qturn if turn 2 Pturn FALSE While turn 2 Pturn TRUE Critical region turn 2 Pturn FALSE Pturn FALSE Qturn FALSE enumturn Initvalue 1 2 ProcQWhile TRUE Qturn TRUE While Pturn if turn 1 Qturn FALSE While turn 1 Qturn TRUE Critical region turn 1 Qturn FALSE Peterson ssolution OperatingSystem CITS NanKaiUniversity 61 defineFALSE0 defineTRUE1 defineN2intturnintinterested N voidenter region intiProcessID intother other 1 iProcessID interested iProcessID TRUE turn iProcessID while turn iProcessID ApplicationofPeterson ssolution OperatingSystem CITS NanKaiUniversity 62 ProcPWhile TRUE enter region PID Critical region leave region PID ProcQWhile TRUE enter region QID Critical region leave region QID TestandSetLock TSL solution OperatingSystem CITS NanKaiUniversity 63 版权所有 转载请注明出处 TSLRXLOCK1 TSLisahardwareinstruction2 LOCKisamemoryword3 StorevalueofLOCKtoRXandsetnonzerovaluetoLOCK enter region TSLREGISTER LOCKCMPREGISTER 0JNEenter regionRETleave region MOVELOCK 0RET Analysisof Busywaiting St