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

1、1单处理器调度单处理器调度第第 9 章章2调度调度n目标目标 公平地将处理器分配给多个进程使用公平地将处理器分配给多个进程使用 响应时间响应时间 吞吐量吞吐量 处理器的效率和低开销处理器的效率和低开销n调度类型（不仅仅是）调度类型（不仅仅是） 长程调度：决定加入到待执行的进程池中长程调度：决定加入到待执行的进程池中 中程调度：分配内存，对换中程调度：分配内存，对换 短程调度：分配处理器短程调度：分配处理器 I/O调度：分配调度：分配I/O设备设备(章章)9.1 处理器调度的类型处理器调度的类型3给一个进程分配内存空间加入一个新进程选择某个就绪进程执行4处理机三级调度处理机三级调度 外存外存(盘

2、盘)交换区交换区作 业作 业后 备后 备状态状态作 业作 业提 交提 交状态状态进程进程完完成状态成状态终止终止进程进程就绪就绪态态阻塞阻塞态态主存主存 短程调度短程调度运行运行态态就绪就绪态态阻塞阻塞态态长程调度长程调度运行状态运行状态外存外存5长程调度（长程调度（Long-Term Scheduling）n决定哪一个程序可以进入到系统中被处理；决定哪一个程序可以进入到系统中被处理；n加入的进程越多，每个进程可以执行的时间加入的进程越多，每个进程可以执行的时间百分比越小，因此长程调度可能限制系统并百分比越小，因此长程调度可能限制系统并发度；发度；n一个进程终止时可以执行该调度，选择某个一个进

3、程终止时可以执行该调度，选择某个程序加入到就绪队列或就绪程序加入到就绪队列或就绪/挂起队列中，供挂起队列中，供短程调度或中程调度处理；短程调度或中程调度处理；n可基于简单的先来先服务或优先级进行调度。可基于简单的先来先服务或优先级进行调度。6中程调度（中程调度（Medium-Term Scheduling）n对换功能（内存管理）对换功能（内存管理）n目的是为了提高主存利用率和系统吞吐量。目的是为了提高主存利用率和系统吞吐量。为了充分发挥内存的效能，需将那些暂时不能为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，运行的进程从内存调到外存盘交换区去等待，而将那些在盘

4、交换区的等待事件已经发生急需而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存。调度运行的进程从盘交换区调入内存。有时内存中进程数目过多也需将处于就绪态的有时内存中进程数目过多也需将处于就绪态的进程从内存调到盘交换区，当然在盘交换区等进程从内存调到盘交换区，当然在盘交换区等待时间过长的就绪态的进程也要调入内存。待时间过长的就绪态的进程也要调入内存。在在UNIXUNIX系统中系统中, ,中程调度就是存储管理中的对中程调度就是存储管理中的对换，即进程在磁盘的交换区和内存间的对换。换，即进程在磁盘的交换区和内存间的对换。采用虚拟存储技术的分时系统往往设立中程调采用虚拟存储技术的

5、分时系统往往设立中程调度。度。 7短程调度（短程调度（Short-Term Scheduling）n通常称为分派程序通常称为分派程序n执行得最频繁执行得最频繁n决定将处理器分配给哪个就绪进程决定将处理器分配给哪个就绪进程n是最基本的调度，任何操作系统都有短程调度是最基本的调度，任何操作系统都有短程调度/进程调度进程调度n短程调度可由以下事件激发：短程调度可由以下事件激发： 时钟中断时钟中断 I/O 中断中断 操作系统调用操作系统调用 信号信号89.2.1 调度算法的选择准则和评价调度算法的选择准则和评价 1.1.面向用户面向用户(User-oriented)(User-oriented)的准则

6、和评价的准则和评价(1)(1)周转时间周转时间( (Turnaround TimeTurnaround Time) )短短 它是评价批处理系统的重要性能指标。它是评价批处理系统的重要性能指标。作业周转时间作业周转时间TiTi是指从作业提是指从作业提交给系统开始，到作业完成为止的这段时间间隔。交给系统开始，到作业完成为止的这段时间间隔。周转时间周转时间Ti = Ti = 完完成时间到达成时间到达( (提交提交) )时间时间 平均周转时间平均周转时间T = 1/nT = 1/n 平均带权周转时间平均带权周转时间 W = 1/nW = 1/n （TsiTsi指实际服务时间）指实际服务时间） (2)(

7、2)响应时间响应时间(Response Time)(Response Time)快快 响应时间是评价分时系统的性能指标。响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。提交一个请求开始，直至系统首次产生响应为止的时间。(3)(3)截止时间截止时间( (Deadline) )的保证的保证 它是用来评价实时系统的重要指标，截止时间是某任务必须执行它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。的最迟时间，或完成的最迟时间。(4)(4)优先权优先权(Enforcing Prior

8、ities)(Enforcing Priorities)准则准则 在选择批处理、分时和实时系统的调度算法时，都可引用优先权在选择批处理、分时和实时系统的调度算法时，都可引用优先权准则，以便让那些紧急的作业（或事件），得到及时的处理。在要准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到及时的处理。得到及时的处理。1niTi/1niTsiTi9.2 调度算法调度算法92. 面向系统面向系统(System-oriented)(System-oriented)的准则的准则(

9、1)(1)达到系统设计目标达到系统设计目标 系统的设计目标是选择算法的主要依据。例如批处理系系统的设计目标是选择算法的主要依据。例如批处理系统所追求的是充分发挥和提高计算机的效率，分时系统则统所追求的是充分发挥和提高计算机的效率，分时系统则侧重于保护用户的请求及时给予响应，实时系统所关心的侧重于保护用户的请求及时给予响应，实时系统所关心的是不要丢失实时信息并给予处理。是不要丢失实时信息并给予处理。(2)(2)系统吞吐量系统吞吐量(throughput)(throughput)大大 这是用来评价批处理系统的重要指标。这是用来评价批处理系统的重要指标。系统吞吐量是单系统吞吐量是单位时间内完成的作业

10、数位时间内完成的作业数，它与批处理作业的平均长度具有，它与批处理作业的平均长度具有密切关系。密切关系。(3)(3)处理机利用率处理机利用率(Processor Utilization)(Processor Utilization)高高 对于大中型多用户系统，由于对于大中型多用户系统，由于CPUCPU价格十分昂贵，所以价格十分昂贵，所以处理机利用率成为衡量大、中型系统性能的十分重要指标，处理机利用率成为衡量大、中型系统性能的十分重要指标，但对单用户微机或某些实时系统，该准则就不那么重要。但对单用户微机或某些实时系统，该准则就不那么重要。(4)(4)各类资源的平衡利用各类资源的平衡利用(Balan

11、cing Resources)(Balancing Resources) 在大中型系统中，有效地利用各类资源（包括在大中型系统中，有效地利用各类资源（包括CPUCPU、外、外存、存、I/OI/O设备等）也是一个重要指标，对于微型机和某些设备等）也是一个重要指标，对于微型机和某些实时系统，该准则也不重要。实时系统，该准则也不重要。109.2.2 优先级的使用优先级的使用n总是选择具有较高优先总是选择具有较高优先级的进程运行级的进程运行n按优先级维护多个就绪按优先级维护多个就绪队列，按优先级递减的队列，按优先级递减的顺序排列顺序排列n低优先级的进程可能饿低优先级的进程可能饿死死 动态优先级：允许进

12、程动态优先级：允许进程随着时间和执行历史的随着时间和执行历史的变化而动态地修改优先变化而动态地修改优先级级119.2.3 选择调度策略选择调度策略n选择函数选择函数决定在就绪进程中选择哪一个进程分决定在就绪进程中选择哪一个进程分配处理机执行配处理机执行 可基于优先级、资源需求或可基于优先级、资源需求或进程的执行特性进程的执行特性选择选择 w=等待的时间等待的时间 e=到目前为止，花费的执行时间到目前为止，花费的执行时间 s=进程所需的总服务时间，包括进程所需的总服务时间，包括en决策模式决策模式说明选择函数在被执行的瞬间的处理说明选择函数在被执行的瞬间的处理方式方式 非抢占：进程一旦运行则不断

13、执行直到终止或自己非抢占：进程一旦运行则不断执行直到终止或自己阻塞自己阻塞自己 抢占：操作系统可打断正在执行的进程将其转移到抢占：操作系统可打断正在执行的进程将其转移到就绪态就绪态12进程调度示例进程调度示例13先来先服务先来先服务 (First-Come-First-Served, FCFS)n当当前正在运行的进程停止执行时，选择在当当前正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行就绪队列中存在时间最长的进程运行 非抢占模式非抢占模式 选择函数为选择函数为max(w)14进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带

14、权周带权周转时间转时间FCFS15进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间033116进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间31371.1791392.251318122.4182012617进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间31371.1791392.251318122.4182012618 FCFS调度算法有利于调度算法有利于CPU繁

15、忙型的作业，繁忙型的作业， FCFS调度算法不利于调度算法不利于I/0繁忙型作业。繁忙型作业。为什么？为什么？进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间31371.1791392.251318122.4182012619FCFS的特点的特点n算法易于实现，表面上很公平算法易于实现，表面上很公平n有利于长进程，对短进程不利，短进程可能需有利于长进程，对短进程不利，短进程可能需要等待较长时间才能运行要等待较长时间才能运行n有利于受有利于受CPU限制的进程，不利于受限制的进程，不利于受I/O限制限制的进程的进程 I/O

16、限制的进程会经常阻塞在限制的进程会经常阻塞在I/O事件上，因事件上，因此需要等待较长的时间此需要等待较长的时间n可与优先级调度算法相结合可与优先级调度算法相结合n缺点：平均周转时间长缺点：平均周转时间长20时间片轮转时间片轮转 (Round-Robin, RR)n分时系统采用的主要调度算法分时系统采用的主要调度算法n总是选择就绪队列中第一个进程，允许其占总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行的时间有处理机一个时间片的时间。当执行的时间片用完时，调度程序便停止该进程的执行，片用完时，调度程序便停止该进程的执行，并将它送到就绪队列的末尾，等待分配下一并将它送到就绪队

17、列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时列中新的队首进程，同时也让它执行一个时间片。间片。 采用基于时间片的采用基于时间片的抢占抢占模式模式 周期性地发生时钟中断，使操作系统获得控周期性地发生时钟中断，使操作系统获得控制权制权 每次就绪进程的选择都基于每次就绪进程的选择都基于FCFS策略策略21时间片时间片q=1n时间片的大小决定了每个进程每次所能占用处理器的时间，其值对性能有影响 如果时间片太大，大到每个进程都能在该时间片内如果时间片太大，大到每个进程都能在该时间片内执行完毕，则执行完毕，则RRR

18、R算法已退化为算法已退化为FCFSFCFS调度算法调度算法如果时间片过小，在一个时间片内切换开销相对增如果时间片过小，在一个时间片内切换开销相对增加，一个进程要花费更多的时间片才能运行结束，加，一个进程要花费更多的时间片才能运行结束，一个进程在系统中的周转时间大大增长。一个进程在系统中的周转时间大大增长。22进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0时刻0：A到达就绪队列：（队头）AA运行RR：q=123进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带

19、权周转时间转时间02时刻2：B到达就绪队列：（队头） B时钟中断， A 暂停，排到就绪队列；轮到B运行 就绪队列：（队头） A24进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间02时刻3：就绪队列：（队头） A时钟中断，B暂停，排到就绪队列；轮到A运行 就绪队列：（队头） B25进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间042时刻4：C到达就绪队列：（队头） BC时钟中断，A完成；轮到B运行 就绪队列：（队头） C26进程进程名名到达到

20、达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0425时刻5：就绪队列： （队头） C时钟中断，B暂停，排到就绪队列；轮到C运行27进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0441.33218162.67517133.25720142.8101573.528RRRR算法分析算法分析时间片的大小对计算机性能的影响时间片的大小对计算机性能的影响 时间片进程执行时间，进程需交替时间片进程执行时间，进程需交替执行执行 时间片进程执行时间，退化为时间片进程执行时

21、间，退化为FCFSFCFS存在的问题：存在的问题： 受受CPUCPU限制和受限制和受I/OI/O限制进程，体现出限制进程，体现出不公平的使用处理机时间不公平的使用处理机时间. .29Virtual round robin （虚拟轮转法（虚拟轮转法,又称又称:VRR）30最短进程优先最短进程优先(Shortest Process Next ，SPN)n在就绪队列中选择所需服务时间最短的进在就绪队列中选择所需服务时间最短的进程程 非抢占模式非抢占模式 选择函数为选择函数为min(s)31进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周

22、转时间转时间SPN32进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间033133进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间03313971.1734进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间03313971.1791131.535进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间03

23、313971.171115112.751520142.591131.536SPN的特点的特点n有利于短进程，对长进程不利有利于短进程，对长进程不利 短进程将越过长进程，跳到就绪队列头被调短进程将越过长进程，跳到就绪队列头被调度度 如果不断地有短进程进入系统，长进程可能如果不断地有短进程进入系统，长进程可能会饿死。会饿死。这一算法有利于短作业，对长作业这一算法有利于短作业，对长作业不利。不利。n需要估计每个进程的服务时间，如果估计不准需要估计每个进程的服务时间，如果估计不准确，系统可能终止该作业确，系统可能终止该作业n有利于系统减少平均周转时间和平均带权周转有利于系统减少平均周转时间和平均带权周

24、转时间时间37最短剩余时间优先最短剩余时间优先 (Shortest Remaining Time,SRT)n在就绪队列中选择运行所需剩余时间最短的进在就绪队列中选择运行所需剩余时间最短的进程程 抢占模式抢占模式 选择函数选择函数min(s-e) n同样需要估计服务时间同样需要估计服务时间n比比SPN有更好的周转时间有更好的周转时间38进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间时刻0：A运行SRT39进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时

25、间转时间0时刻时刻2：B到达到达预期剩余时间：预期剩余时间： A :1 B:6A继续运行继续运行40进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0331时刻时刻3：A完成完成预期剩余时间：预期剩余时间： B:6B运行运行41进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间03313时刻时刻4：C到达到达预期剩余时间：预期剩余时间： B:5 C:4B暂停暂停,排到就绪队列排到就绪队列,C运行运行就绪队列就绪队列:(队头队头)B42进程进程名名

26、到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间033134时刻时刻6：D到达到达预期剩余时间：预期剩余时间： B:5 C:2 D:5C运行运行就绪队列就绪队列:(队头队头)BD43进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间033134844时刻时刻8：C完成，完成，E到达到达预期剩余时间：预期剩余时间： B:5 D:5 E：2E运行运行就绪队列就绪队列:(队头队头)BD44进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成

27、时间时间周转周转时间时间带权周带权周转时间转时间03313484181021时刻时刻10： E 完成完成预期剩余时间：预期剩余时间： B:5 D:5B运行运行就绪队列就绪队列:(队头队头)D45进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0331348418102146进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0331315132刻时刻15： B 完成完成预期剩余时间：预期剩余时间： D:5D运行运行47进程

28、进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0331315132.1748411520142.881021时刻时刻20： D 完成完成48最高响应比优先最高响应比优先 (Highest Response Ratio Next，HRRN)n在就绪队列中选择在就绪队列中选择响应响应比最高的进程来调度比最高的进程来调度 非抢占模式非抢占模式 选择函数选择函数max(R)=max(1+w/s)n折中策略，综合考虑服务时间和等待时间折中策略，综合考虑服务时间和等待时间49进程进程名名到达到达时间时间服务服务时间时间开始执开始执行

29、时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间时刻0：A运行HRRN50进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0331时刻3：A完成，B到达B运行51进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间03313971.17时刻9：B完成，CDE到达响应比： C：(5+4)/4=2.25,D：(3+5)/5=1.6,E:(1+2)/2=1.5C运行52进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间

30、完成完成时间时间周转周转时间时间带权周带权周转时间转时间03313971.1791392.25时刻13：C完成响应比： D：(9+5)/5=2.8,E:(5+2)/2=3.5E运行53进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间03313971.1791392.25131573.5时刻15：E完成 D运行54进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间03313971.1791392.251520142.8131573.5时刻20： D

31、 完成55反馈反馈 (Feedback)n原则：处罚运行时间较长的作业原则：处罚运行时间较长的作业 基于抢占原则（按时间片）并使用动态优先级机制基于抢占原则（按时间片）并使用动态优先级机制 新进程进入新进程进入RQ0，每当它被抢占每当它被抢占，则降到下一个优，则降到下一个优先级队列中先级队列中 优先级最低队列采用轮转法，其他队列采用优先级最低队列采用轮转法，其他队列采用FCFS机制机制固定时间片可变时间片5657进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间时刻0:A到达RQ0:（队头）AA执行反馈法反馈法 时间片：

32、q=158进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0时刻2:B到达RQ0:（队头）B时钟中断，A暂停，A排到RQ1队列RQ1： （队头） AB执行59进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间02时刻3:时钟中断，B暂停，B排到RQ1队列RQ0:（队头）空RQ1： （队头） ABA执行60进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间042时刻4:C到达

33、时钟中断，A完成RQ0:（队头）CRQ1： （队头） BC执行61进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0424时刻5:时钟中断， C暂停，C排到RQ1队列RQ0:（队头）RQ1： （队头） BCB执行62进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间04246时刻6:D到达时钟中断， B暂停，B排到RQ2队列RQ0:（队头）DRQ1： （队头） CRQ2： （队头） BD执行63进程进程名名到达到达时间时间服务服务时间时间开始执开

34、始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间04246时刻7:时钟中断， D暂停，D排到RQ1队列RQ0:（队头）RQ1： （队头） CDRQ2： （队头） BC执行64进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间042468时刻8:E到达时钟中断， C暂停，C排到RQ2队列RQ0:（队头）ERQ1： （队头） DRQ2： （队头） BCE执行65进程进程名名到达到达时间时间服务服务时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权周带权周转时间转时间0441.33220183416123619132.681131.5666768例题分别采用FCFS、SPN和HRRN调度算法填充空白处。69FCFS70SPN71HRRN72作业nP301 9.2nP303 9.1673本章结束！本章结束！74作业的基本概念n作业作业: 包含程序、数据和一份作业说明书，系统包含程序、数据和一份作业说明书，系统根据说明书来对程序的运行进行控制。根据说明书来对程序的运行进行控制。n作业步：作业步： 在作业的运行期间，每个作业都必须经过在作业的运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能若干个相对独立又相互关联的