第九章单处理器调度浙江工业大学.

1单处理器调度第9章2调度目标–公平地将处理器分配给多个进程使用–响应时间–吞吐量–处理器的效率和低开销调度类型（不仅仅是ＣＰＵ）–长程调度：决定加入到待执行的进程池中–中程调度：分配内存，对换–短程调度：分配处理器–I/O调度：分配I/O设备(１１章)9.1处理器调度的类型3给一个进程分配内存空间加入一个新进程选择某个就绪进程执行4处理机三级调度外存(盘)交换区作业后备状态作业提交状态进程完成状态终止进程就绪态阻塞态中程调度主存短程调度运行态就绪态阻塞态长程调度运行状态外存5长程调度（Long-TermScheduling）决定哪一个程序可以进入到系统中被处理；加入的进程越多，每个进程可以执行的时间百分比越小，因此长程调度可能限制系统并发度；一个进程终止时可以执行该调度，选择某个程序加入到就绪队列或就绪/挂起队列中，供短程调度或中程调度处理；可基于简单的先来先服务或优先级进行调度。6中程调度（Medium-TermScheduling）对换功能（内存管理）目的是为了提高主存利用率和系统吞吐量。–为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存。–有时内存中进程数目过多也需将处于就绪态的进程从内存调到盘交换区，当然在盘交换区等待时间过长的就绪态的进程也要调入内存。–在UNIX系统中,中程调度就是存储管理中的对换，即进程在磁盘的交换区和内存间的对换。–采用虚拟存储技术的分时系统往往设立中程调度。7短程调度（Short-TermScheduling）通常称为分派程序执行得最频繁决定将处理器分配给哪个就绪进程是最基本的调度，任何操作系统都有短程调度/进程调度短程调度可由以下事件激发：–时钟中断–I/O中断–操作系统调用–信号89.2.1调度算法的选择准则和评价1.面向用户(User-oriented)的准则和评价(1)周转时间(TurnaroundTime)短它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。周转时间Ti=完成时间－到达(提交)时间平均周转时间T=1/n×平均带权周转时间W=1/n×（Tsi指实际服务时间）(2)响应时间(ResponseTime)快响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。(3)截止时间(Deadline)的保证它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。(4)优先权(EnforcingPriorities)准则在选择批处理、分时和实时系统的调度算法时，都可引用优先权准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到及时的处理。][1niTi]/[1niTsiTi9.2调度算法92.面向系统(System-oriented)的准则(1)达到系统设计目标系统的设计目标是选择算法的主要依据。例如批处理系统所追求的是充分发挥和提高计算机的效率，分时系统则侧重于保护用户的请求及时给予响应，实时系统所关心的是不要丢失实时信息并给予处理。(2)系统吞吐量(throughput)大这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。(3)处理机利用率(ProcessorUtilization)高对于大中型多用户系统，由于CPU价格十分昂贵，所以处理机利用率成为衡量大、中型系统性能的十分重要指标，但对单用户微机或某些实时系统，该准则就不那么重要。(4)各类资源的平衡利用(BalancingResources)在大中型系统中，有效地利用各类资源（包括CPU、外存、I/O设备等）也是一个重要指标，对于微型机和某些实时系统，该准则也不重要。109.2.2优先级的使用总是选择具有较高优先级的进程运行按优先级维护多个就绪队列，按优先级递减的顺序排列低优先级的进程可能饿死–动态优先级：允许进程随着时间和执行历史的变化而动态地修改优先级119.2.3选择调度策略选择函数决定在就绪进程中选择哪一个进程分配处理机执行–可基于优先级、资源需求或进程的执行特性选择•w=等待的时间•e=到目前为止，花费的执行时间•s=进程所需的总服务时间，包括e决策模式说明选择函数在被执行的瞬间的处理方式–非抢占：进程一旦运行则不断执行直到终止或自己阻塞自己–抢占：操作系统可打断正在执行的进程将其转移到就绪态12进程调度示例13先来先服务(First-Come-First-Served,FCFS)当当前正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行–非抢占模式–选择函数为max(w)14进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３Ｂ２６Ｃ４４Ｄ６５Ｅ８２FCFS15进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６Ｃ４４Ｄ６５Ｅ８２16进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３０３31Ｂ２６3９71.17Ｃ４４91392.25Ｄ６５1318122.4Ｅ８２182012617进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３０３31Ｂ２６3９71.17Ｃ４４91392.25Ｄ６５1318122.4Ｅ８２1820126平均周转时间（3+7+9+12+12）/5=8.6平均带权周转时间（1+1.17+2.25+2.4+6）/5=2.5618FCFS调度算法有利于CPU繁忙型的作业，FCFS调度算法不利于I/0繁忙型作业。为什么？进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３０３31Ｂ２６3９71.17Ｃ４４91392.25Ｄ６５1318122.4Ｅ８２182012619FCFS的特点算法易于实现，表面上很公平有利于长进程，对短进程不利，短进程可能需要等待较长时间才能运行有利于受CPU限制的进程，不利于受I/O限制的进程–I/O限制的进程会经常阻塞在I/O事件上，因此需要等待较长的时间可与优先级调度算法相结合缺点：平均周转时间长20时间片轮转(Round-Robin,RR)分时系统采用的主要调度算法总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行的时间片用完时，调度程序便停止该进程的执行，并将它送到就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。–采用基于时间片的抢占模式–周期性地发生时钟中断，使操作系统获得控制权–每次就绪进程的选择都基于FCFS策略21时间片q=1时间片的大小决定了每个进程每次所能占用处理器的时间，其值对性能有影响–如果时间片太大，大到每个进程都能在该时间片内执行完毕，则RR算法已退化为FCFS调度算法–如果时间片过小，在一个时间片内切换开销相对增加，一个进程要花费更多的时间片才能运行结束，一个进程在系统中的周转时间大大增长。22进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0Ｂ２６Ｃ４４Ｄ６５Ｅ８２时刻0：A到达就绪队列：（队头）AA运行RR：q=123进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0Ｂ２６2Ｃ４４Ｄ６５Ｅ８２时刻2：B到达就绪队列：（队头）B时钟中断，A暂停，排到就绪队列；轮到B运行就绪队列：（队头）A24进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0Ｂ２６2Ｃ４４Ｄ６５Ｅ８２时刻3：就绪队列：（队头）A时钟中断，B暂停，排到就绪队列；轮到A运行就绪队列：（队头）B25进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３04Ｂ２６2Ｃ４４Ｄ６５Ｅ８２时刻4：C到达就绪队列：（队头）BC时钟中断，A完成；轮到B运行就绪队列：（队头）C26进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３04Ｂ２６2Ｃ４４5Ｄ６５Ｅ８２时刻5：就绪队列：（队头）C时钟中断，B暂停，排到就绪队列；轮到C运行……27进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0441.33Ｂ２６218162.67Ｃ４４517133.25Ｄ６５720142.8Ｅ８２101573.5平均周转时间（4+16+13+14+7）/5=10.8平均带权周转时间（1.33+2.67+3.25+2.8+3.5）/5=2.7128RR算法分析时间片的大小对计算机性能的影响①时间片＜进程执行时间，进程需交替执行②时间片＞进程执行时间，退化为FCFS存在的问题：受CPU限制和受I/O限制进程，体现出不公平的使用处理机时间.29Virtualroundrobin（虚拟轮转法,又称:VRR）30最短进程优先(ShortestProcessNext，SPN)在就绪队列中选择所需服务时间最短的进程–非抢占模式–选择函数为min(s)31进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３Ｂ２６Ｃ４４Ｄ６５Ｅ８２SPN32进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６Ｃ４４Ｄ６５Ｅ８２33进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６3971.17Ｃ４４Ｄ６５Ｅ８２34进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６3971.17Ｃ４４Ｄ６５Ｅ８２91131.535进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６3971.17Ｃ４４1115112.75Ｄ６５1520142.5Ｅ８２91131.536SPN的特点有利于短进程，对长进程不利–短进程将越过长进程，跳到就绪队列头被调度–如果不断地有短进程进入系统，长进程可能会饿死。这一算法有利于短作业，对长作业不利。需要估计每个进程的服务时间，如果估计不准确，系统可能终止该作业有利于系统减少平均周转时间和平均带权周转时间37最短剩余时间优先(ShortestRemainingTime,SRT)在就绪队列中选择运行所需剩余时间最短的进程–抢占模式–选择函数min(s-e)同样需要估计服务时间比SPN有更好的周转时间38进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３Ｂ２６Ｃ４４Ｄ６５Ｅ８２时刻0：A运行SRT39进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0Ｂ２６Ｃ４４Ｄ６５Ｅ８２时刻2：B到达预期剩余时间：A:1B:6A继续运行40进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６Ｃ４４Ｄ６５Ｅ８２时刻3：A完成预期剩余时间：B:6B运行41进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６3Ｃ４４Ｄ６５Ｅ８２时刻4：C到达预期剩余时间：B:5C:4B暂停,排到就绪队列,C运行就绪队列:(队头)B42进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６3Ｃ４４4Ｄ６５Ｅ８２时刻6：D到达预期剩余时间：B:5C:2D:5C运行就绪队列:(队头)BD43进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６3Ｃ４４4844Ｄ６５Ｅ８２时刻8：C完成，E到达预期剩余时间：B:5D:5E：2E运行就绪队列:(队头)BD44进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６3Ｃ４４4841Ｄ６５Ｅ８２81021时刻10：E完成预期剩余时间：B:5D:5B运行就绪队列:(队头)D45进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间Ａ０３0331Ｂ２６3Ｃ４４4841Ｄ６５Ｅ８２8