计算机操作系统原理6

[e-mail]20106.1OperatingSystemConceptsChapter6:CPUSchedulingBasicConceptsSchedulingCriteriaSchedulingAlgorithmsReal-TimeSchedulingProcessSchedulingModels*[e-mail]20106.2OperatingSystemConcepts6.1BasicConceptsTheobjectiveofmultiprogrammingistomaximumCPUutilizationwithseveralprocessesrunningatalltimes.Inuniprocessorsystem,onlyoneprocessmayrunatatime.AnyotherprocessesmustwaituntilCPUisfreeandcanberescheduled.SchedulingisafundamentalOSfunction.Asoneoftheprimarycomputerresource,[e-mail]20106.3OperatingSystemConcepts6.1BasicConcepts(1)CPUscheduler--Selectsfromamongtheprocessesinmemorythatarereadytoexecute,andallocatestheCPUtooneofthem.CPUschedulingdecisionsmaytakeplacewhenaprocess:1.Switchesfromrunningtowaitingstate.2.Switchesfromrunningtoreadystate.3.Ahighpriorityswitchesfromwaitingtoready.4.Terminates.Schedulingmodes--Schedulingunder1and4is[e-mail]20106.4OperatingSystemConcepts6.1BasicConcepts(2)Nonpreemptivescheduling–onceCPUhasbeenallocatedtoaprocess,itkeepsCPUuntilitreleasetheCPUeitherbyterminatingorbyswitchingtothewaitingstate.Preemptivescheduling–schedulercanswitchCPUfromarunningprocesstoanotheraccordingtothepolicy.Availablepolicies–suchastimeslice,priority,andshortest-jobfirstRequiresspecialhardwaresupportandhasaneffectonthedesignofoperatingsystemkernel.[e-mail]20106.5OperatingSystemConcepts6.1BasicConcepts(2)Dispatcher--givescontroloftheCPUtotheprocessselectedbytheshort-termscheduler;thisinvolves:switchingcontextswitchingtousermodejumpingtotheproperlocationintheuserprogramtorestartthatprogramDispatchlatency–thetimeittakesforthedi[e-mail]20106.6OperatingSystemConcepts6.2SchedulingCriteriaCPUutilization–keeptheCPUasbusyaspossible.Throughput–thenumberofprocessesthatcompletetheirexecutionpertimeunit.Turnaroundtime–amountoftime(fromsubmissiontocompletion)toexecuteaparticularprocess.Waitingtime–amountoftimeaprocesshasbeenwaitinginthereadyqueue.Responsetime–amountoftimeittakesfromwhenarequestwassubmitteduntilthefirstresponseisproducedOptimizationCriteria--MaxCPUutilization,Maxthroughput,Minturnaroundtime,Minwaitingtime,[e-mail]20106.7OperatingSystemConcepts6.3SchedulingAlgorithmsFirst-Come,First-Served(FCFS)SchedulingShortest-Job-First(SJF)SchedulingPrioritySchedulingRound-RobinSchedulingMultilevelQueueScheduling[e-mail]20106.8OperatingSystemConcepts6.3.1FCFSSchedulingFCFS–whicheverrequestsCPUfirstisallocatedtheCPUfirst.ImplementedasaFIFOqueue.Averagewaitingtimeisoftenquitelong.exampleProcessBurstTimeP124P23P33Supposethattheprocessesarriveattime0,intheorder:P1,P2,P3,theGanttChartforthescheduleis:WaitingtimeforP1=0;P2=24;P3=27Averagewaitingtime:(0+24+27)/3=[e-mail]20106.9OperatingSystemConcepts6.3.1FCFSScheduling(1)Supposethattheprocessesarriveintheorder:P2,P3,P1.TheGanttchartforthescheduleis:WaitingtimeforP1=6;P2=0;P3=3Averagewaitingtime:(6+0+3)/3=3Thisismuchbetterthanpreviouscase.Thusaveragewaitingtimeforthisisnotminimal,andmayvarysubstantiallyifprocessCPU-bursttimesvarygreatly.Thecauseistheshortprocessbehindlongprocess.ThiseffectmayresultinlowerCPUanddeviceutilizat[e-mail]20106.10OperatingSystemConcepts6.3.2SJFSchedulingSJF--AssociatewitheachprocessthelengthofitsnextCPUburst.Usetheselengthstoscheduletheprocesswiththeshortesttime.Twoschemes:nonpreemptive–onceCPUgiventotheprocessitcannotbepreempteduntilcompletesitsCPUburst.preemptive–ifanewprocessarriveswithCPUburstlengthlessthanremainingtimeofcurrentexecutingprocess,preempt.ThisschemeisknowastheShortest-Remaining-Time-First(SRTF).SJFisoptimal–givesminimumaveragewaitingtimeforagivensetofprocesses.SJFisusedfrequentlyinlong-termscheduling,andcannotbeimplementedinCPU-scheduling.[e-mail]20106.11OperatingSystemConceptsExampleofNon-PreemptiveSJFProcessArrivalTimeBurstTimeP107P224P341P454SJF(non-preemptive)Averagewaitingtime=(0+6+3+7)/4=46.3.2SJFScheduling(1)[e-mail]20106.12OperatingSystemConceptsP1P3P242110P457P2P1166.3.2SJFScheduling(2)ExampleofPreemptiveSJFProcessArrivalTimeBurstTimeP107P224P341P454SJF(preemptive)Averagewaitingtime=(9+1+0+2)/4=[e-mail]20106.13OperatingSystemConcepts6.3.3PrioritySchedulingPriority--Anumber(integer)isassociatedwitheachprocess.CPUisallocatedtotheprocesswiththehighestpriority.Equal-priorityprocessesarescheduledinFCFSorder.Preemptive–preemptCPUifthepriorityofnewlyarrivedprocessishigherthanthatofthecurrentlyrunningprocess.Nonpreemptive–simplyputthenewprocessattheheadofreadyqueue.SJFisapriorityschedulingwherepriorityisthepredictednextCPUbursttime.ProblemStarvation–lowpriorityproce