操作系统基础基本理论、基本方法复习

Chapter1Introduction1.AbstractViewofSystemComponents2.MultiprogrammedBatchSystemsSeveraljobsarekeptinmainmemoryatthesametime,andtheCPUismultiplexedamongthem.Chapter2:Computer-SystemStructures1.Computer-SystemArchitecture2.InterruptTimeLineForaSingleProcessDoingOutput3.Moving-HeadDiskMechanism4.DirectMemoryAccessStructureSixStepProcesstoPerformDMATransfer5.Storage-DeviceHierarchy6.UseofABaseandLimitRegister7.HardwareAddressProtectionChapter3:Operating-SystemStructures1.MS-DOSExecution2.MS-DOSLayerStructureChapter4:Processes1.DiagramofProcessState2.ProcessControlBlock(PCB)3.CPUSwitchFromProcesstoProcess4.RepresentationofProcessScheduling5.AdditionofMediumTermSchedulingChapter5:Threads1.SingleandMultithreadedProcesses2.Many-to-OneModel3.One-to-oneModel4.Many-to-ManyModelChapter6:CPUScheduling1.AlternatingSequenceofCPUAndI/OBursts2.First-Come,First-Served(FCFS)SchedulingProcessBurstTimeP124P23P33Supposethattheprocessesarriveintheorder:P1,P2,P3TheGanttChartforthescheduleis:WaitingtimeforP1=0;P2=24;P3=27Averagewaitingtime:(0+24+27)/3=173.ExampleofNon-PreemptiveSJFProcessArrivalTimeBurstTimeP10.07P22.04P34.01P45.04SJF(non-preemptive)Averagewaitingtime=(0+6+3+7)/4-44.ExampleofPreemptiveSJFProcessArrivalTimeBurstTimeP10.07P22.04P34.01P45.04SJF(preemptive)Averagewaitingtime=(9+1+0+2)/4-35.ExampleofRRwithTimeQuantum=20ProcessBurstTimeP153P217P368P424TheGanttchartis:Typically,higheraverageturnaroundthanSJF,butbetterresponse.6.DispatchLatencyChapter7:ProcessSynchronization1.Implementation•Semaphoreoperationsnowdefinedaswait(S):S.value--;if(S.value0){addthisprocesstoS.L;block;}signal(S):S.value++;if(S.value=0){removeaprocessPfromS.L;wakeup(P);}2.Deadlock•–twoormoreprocessesarewaitingindefinitelyforaneventthatcanbecausedbyonlyoneofthewaitingprocesses.•LetSandQbetwosemaphoresinitializedto1P0P1wait(S);wait(Q);wait(Q);wait(S);signal(S);signal(Q);signal(Q)signal(S);3.Bounded-BufferProblem•Shareddatasemaphorefull,empty,mutex;Initially:full=0,empty=n,mutex=1ProblemProducerProcessdo{…produceaniteminnextp…wait(empty);wait(mutex);…addnextptobuffer…signal(mutex);signal(full);}while(1);ProblemConsumerProcessdo{wait(full)wait(mutex);…removeanitemfrombuffertonextc…signal(mutex);signal(empty);…consumetheiteminnextc…}while(1);4.Readers-WritersProblem•Shareddatasemaphoremutex,wrt;Initiallymutex=1,wrt=1,readcount=0WriterProcesswait(wrt);…writingisperformed…signal(wrt);ReaderProcesswait(mutex);readcount++;if(readcount==1)wait(rt);signal(mutex);…readingisperformed…wait(mutex);readcount--;if(readcount==0)signal(wrt);signal(mutex):5.Dining-PhilosophersProblem•Shareddatasemaphorechopstick[5];Initiallyallvaluesare1•Philosopheri:do{wait(chopstick[i])wait(chopstick[(i+1)%5])…eat…signal(chopstick[i]);signal(chopstick[(i+1)%5]);…think…}while(1);Chapter8:Deadlocks1.ExampleofaResourceAllocationGraph2.BasicFacts•Ifgraphcontainsnocyclesnodeadlock.•Ifgraphcontainsacycle–ifonlyoneinstanceperresourcetype,thendeadlock.–ifseveralinstancesperresourcetype,possibilityofdeadlock.3.SafeState•Whenaprocessrequestsanavailableresource,systemmustdecideifimmediateallocationleavesthesysteminasafestate.•Systemisinsafestateifthereexistsasafesequenceofallprocesses.•SequenceP1,P2,…,PnissafeifforeachPi,theresourcesthatPicanstillrequestcanbesatisfiedbycurrentlyavailableresources+resourcesheldbyallthePj,withjI.–IfPiresourceneedsarenotimmediatelyavailable,thenPicanwaituntilallPjhavefinished.–WhenPjisfinished,Picanobtainneededresources,execute,returnallocatedresources,andterminate.–WhenPiterminates,Pi+1canobtainitsneededresources,andsoon.4.Banker’sAlgorithm•Multipleinstances.•Eachprocessmustaprioriclaimmaximumuse.•Whenaprocessrequestsaresourceitmayhavetowait.•Whenaprocessgetsallitsresourcesitmustreturntheminafiniteamountoftime.DataStructuresfortheBanker’sAlgorithmLetn=numberofprocesses,andm=numberofresourcestypes.•Available:Vectoroflengthm.Ifavailable[j]=k,therearekinstancesofresourcetypeRjavailable.•Max:nxmmatrix.IfMax[i,j]=k,thenprocessPimayrequestatmostkinstancesofresourcetypeRj.•Allocation:nxmmatrix.IfAllocation[i,j]=kthenPiiscurrentlyallocatedkinstancesofRj.•Need:nxmmatrix.IfNeed[i,j]=k,thenPimayneedkmoreinstancesofRjtocompleteitstask.Need[i,j]=Max[i,j]–Allocation[i,j].SafetyAlgorithm1)LetWorkandFinishbevectorsoflengthmandn,respectively.Initialize:Work=AvailableFinish[i]=falsefori-1,3,…,n.2)Findandisuchthatboth:(a)Finish[i]=false(b)NeediWorkIfnosuchiexists,gotostep4.3)Work=Work+AllocationiFinish[i]=truegotostep2.4)IfFinish[i]==trueforalli,thenthesystemisinasafestate.Resource-RequestAlgorithmforProcessPiRequest=requestvectorforprocessPi.IfRequesti[j]=kthenprocessPiwantskinstancesofresourcetypeRj.1)IfRequestiNeedigotostep2.Otherwise,raiseerrorcondition,sinceprocesshasexceededitsmaximumclaim.2)IfRequestiAvailable,gotostep3.OtherwisePimustwait,sinceresourcesarenotavailable.3)PretendtoallocaterequestedresourcestoPibymodifyingthestateasfollows:Available=Available=Requesti;Allocationi=Allocationi+Requesti;Needi=Needi–Requesti;;•Ifsafetheresourcesareallocated