操作系统第6章

Chapter6CPU的调度BasicConcepts基本概念SchedulingCriteria调度程序的评价标准SchedulingAlgorithms调度算法Multiple-ProcessorScheduling多处理机的调度Real-TimeScheduling实时调度AlgorithmEvaluation算法评价CPU调度why？计算机得以完成计算，必须依赖CPU需要运行的程序数计算机CPU个数Possible？CPU的速度用户的速度CPU与I/O可以并发Principle让CPU不停地忙，公平地做有用功，考虑任务的轻重缓急车轮战，以一敌百BasicConceptsMaximumCPUutilizationobtainedwithmultiprogramming（通过多道程序设计得到CPU的最高利用率）CPU–I/OBurstCycle–ProcessexecutionconsistsofacycleofCPUexecutionandI/Owait.（CPU-I/O脉冲周期-进程的执行包括进程在CPU上执行和等待I/O）CPUburstdistribution（CPU脉冲的分布）AlternatingSequenceofCPUAndI/OBurstsHistogramofCPU-burstTimesCPUScheduling两个重要角色CPUschedulerDispatcherCPUSchedulerSelectsfromamongtheprocessesinmemorythatarereadytoexecute,andallocatestheCPUtooneofthem.（选择内存中的就绪进程，并分配CPU给其中之一）preemptiveandnonpreemptivenonpreemptive–onceCPUgiventotheprocessitcannotbepreempteduntilcompletesitsCPUburst（非抢占式调度–一旦进程拥有CPU，它的使用权限只能在该CPU脉冲结束后让出).Preemptive–ifanewprocessarriveswithCPUburstlengthlessthanremainingtimeofcurrent法executingprocess,preempt.ThisschemeisknowastheShortest-Remaining-Time-First(SRTF).（抢占式调度–发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度）什么时候调度？记得我们的原则：让CPU不停忙、公平做有用功、考虑轻重缓急让出CPU让出CPU剥夺CPU可能剥夺别的CPU什么时候调度？CPUschedulingdecisionsmaytakeplacewhenaprocess（CPU调度可能发生在当一个进程）:1.Switchesfromrunningtowaitingstate（从运行转到等待）.2.Switchesfromrunningtoreadystate（从运行转到就绪）.3.Switchesfromwaitingtoready（从等待转到就绪）.4.Terminates（终止运行）.Schedulingunder1and4isnonpreemptive（发生在1、4两种情况下的调度称为非抢占式调度）.Allotherschedulingispreemptive（其他情况下发生的调度称为抢占式调度）.DispatcherDispatchermodulegivescontroloftheCPUtotheprocessselectedbytheshort-termscheduler;thisinvolves（进程调度模块负责将对CPU的控制权转交给由CPU调度程序，包括）:switchingcontext（切换上下文）switchingtousermode（切换到用户态）jumpingtotheproperlocationintheuserprogramtorestartthatprogram（跳转到用户程序的适当位置并重新运行之）Dispatchlatency–timeittakesforthedispatchertostoponeprocessandstartanotherrunning（调度时间–调度程序终止一个进程的运行并启动另一个进程运行所花的时间）.SchedulingCriteria调度好坏的评判CPUutilization–keeptheCPUasbusyaspossible（CPU利用率–使CPU尽可能的忙碌）Throughput–thenumberofprocessesthatcompletetheirexecutionpertimeunit（吞吐量–单位时间内运行完的进程数）Turnaroundtime–theintervalfromsubmissiontocompletion（周转时间–进程从提交到运行结束的全部时间）Waitingtime–amountoftimeaprocesshasbeenwaitinginthereadyqueue（等待时间–进程在就绪队列中等待调度的时间片总和）Responsetime–amountoftimeittakesfromwhenarequestwassubmitteduntilthefirstresponseisproduced,notoutput(fortime-sharingenvironment)（响应时间–从进程提出请求到首次被响应[而不是输出结果]的时间段[在分时系统环境下]）OptimizationCriteriaMaxCPUutilization（最大的CPU利用率）Maxthroughput（最大的吞吐量）Minturnaroundtime（最短的周转时间）Minwaitingtime（最短的等待时间）Minresponsetime（最短的响应时间）First-Come,First-Served(FCFS)SchedulingExample:ProcessBurstTimeP124P23P33Supposethattheprocessesarriveintheorder（假定进程到达顺序如下）:P1,P2,P3TheGanttChartforthescheduleis（该调度的Gantt图为）:Waitingtime（等待时间）forP1=0;P2=24;P3=27Averagewaitingtime（平均等待时间）:(0+24+27)/3=17P1P2P32427300First-Come,First-Served(FCFS)SchedulingExample:ProcessBurstTimeP124P23P33Supposethattheprocessesarriveintheorder（假定进程到达顺序如下）:P1,P2,P3TheGanttChartforthescheduleis（该调度的Gantt图为）:Waitingtime（等待时间）forP1=0;P2=24;P3=27Averagewaitingtime（平均等待时间）:(0+24+27)/3=17P1P2P32427300First-Come,First-Served(FCFS)SchedulingExample:ProcessBurstTimeP124P23P33Supposethattheprocessesarriveintheorder（假定进程到达顺序如下）:P1,P2,P3TheGanttChartforthescheduleis（该调度的Gantt图为）:Waitingtime（等待时间）forP1=0;P2=24;P3=27Averagewaitingtime（平均等待时间）:(0+24+27)/3=17P1P2P32427300First-Come,First-Served(FCFS)SchedulingExample:ProcessBurstTimeP124P23P33Supposethattheprocessesarriveintheorder（假定进程到达顺序如下）:P1,P2,P3TheGanttChartforthescheduleis（该调度的Gantt图为）:Waitingtime（等待时间）forP1=0;P2=24;P3=27Averagewaitingtime（平均等待时间）:(0+24+27)/3=17P1P2P32427300First-Come,First-Served(FCFS)SchedulingExample:ProcessBurstTimeP124P23P33Supposethattheprocessesarriveintheorder（假定进程到达顺序如下）:P1,P2,P3TheGanttChartforthescheduleis（该调度的Gantt图为）:Waitingtime（等待时间）forP1=0;P2=24;P3=27Averagewaitingtime（平均等待时间）:(0+24+27)/3=17P1P2P32427300First-Come,First-Served(FCFS)SchedulingExample:ProcessBurstTimeP124P23P33Supposethattheprocessesarriveintheorder（假定进程到达顺序如下）:P1,P2,P3TheGanttChartforthescheduleis（该调度的Gantt图为）:Waitingtime（等待时间）forP1=0;P2=24;P3=27Averagewaitingtime（平均等待时间）:(0+24+27)/3=17P1P2P32427300FCFSScheduling(Cont.)Supposethattheprocessesarriveintheorder（假定进程到达顺序如下）P2,P3,P1.TheGanttchartforthescheduleis（该调度的Gantt图为）:Waitingtime（等待时间）forP1=6;P2=0;P3=3Averagewaitingtime（平均等待时间）:(6+0+3)/3=3Muchbetterthanpreviouscase（比前例好得多）.Convoyeffectshortprocessbehindlongprocess（此种结果产生是由于长进程先于短进程到达“同牌不同命”）P1P3P26330030Shortest-Job-First(SJF)Scheduling金手指-化偶然为必然AssociatewitheachprocessthelengthofitsnextCPUburst.Usetheselengthstoscheduletheprocesswiththeshortesttime.（关联到每个进程下次运行的CPU脉冲长度，调度最短的进程）SJFisoptimal–givesminimumaveragewaitingtimeforagivensetofprocesses.（SJF是最优的–对一组指定的进程而言，它给出了最短的平均等待时间）ProcessArrivalTimeBurstTimeP10.07P22.04P34.01P45.04SJF(non-preemptive)Averagewaitingtime=(0+6+3+7)/4=4ExampleofNon-PreemptiveSJFP1P3P273160P481216ExampleofPreemptiveSJF（更彻底SJF）ProcessArrivalTimeBurstTimeP10.07P22.04P34.01P45.04SJF(