第三章 处理机调度

1、 实用操作系统教程实用操作系统教程2本章内容本章内容3.1 3.1 三级调度体系三级调度体系3.2 3.2 进程调度目标和调度方式进程调度目标和调度方式3.3 3.3 调度算法的评价准则调度算法的评价准则3.4 3.4 典型进程调度算法典型进程调度算法3.5 3.5 线程调度算法线程调度算法3.6 3.6 实时调度算法实时调度算法3本章学习目标本章学习目标v理解三级调度的含义和比较；理解三级调度的含义和比较；v理解抢占式调度、非抢占式调度的区别与联系；理解抢占式调度、非抢占式调度的区别与联系；v了解调度算法的评价准则；了解调度算法的评价准则；v掌握常见调度算法及其比较；掌握常见调度算法及其比较

2、；v理解等待时间、周转时间、加权周转时间的含义，理解等待时间、周转时间、加权周转时间的含义，并会计算；并会计算；v了解实时调度和多处理机调度的特点了解实时调度和多处理机调度的特点43.1 3.1 三级调度体系三级调度体系3.1.1 高级调度高级调度1高级调度（高级调度（high-level scheduling）又称作业调度）又称作业调度或长程调度，它是根据某种算法将外存上处于后或长程调度，它是根据某种算法将外存上处于后备作业队列中的若干作业调入内存，为作业分配备作业队列中的若干作业调入内存，为作业分配所需资源并建立相应进程。所需资源并建立相应进程。2作业通常分成若干个既相对独立又互相关联的加

3、作业通常分成若干个既相对独立又互相关联的加工步骤，每个步骤称为一个作业步。每个作业步工步骤，每个步骤称为一个作业步。每个作业步可能对应一个或多个进程。可能对应一个或多个进程。53.1.1 3.1.1 高级调度高级调度v作业一般要经历作业一般要经历“提交提交”、“后备后备”、“执行执行”和和“完成完成”四个状态。四个状态。63.1.1 3.1.1 高级调度高级调度v高级调度决定允许哪些作业可进入内存，参与竞高级调度决定允许哪些作业可进入内存，参与竞争争CPUCPU和系统其他资源，将一个或一批作业从后和系统其他资源，将一个或一批作业从后备状态变为运行状态。备状态变为运行状态。73.1.1 3.1.

4、1 高级调度高级调度v在多道批处理系统中，为了管理和调度作业，系统在多道批处理系统中，为了管理和调度作业，系统为每个作业设置了一个作业控制块为每个作业设置了一个作业控制块(JCB)(JCB)，它记录作，它记录作业的相关信息。业的相关信息。83.1.1 3.1.1 高级调度高级调度9重点回顾重点回顾v 管程由四部分组成：管程由四部分组成：管程的名称管程的名称局部于管程内部的共享数据结构说明局部于管程内部的共享数据结构说明对该数据结构进行操作的一组过程对该数据结构进行操作的一组过程对管程内部共享数据设置初始值的语句对管程内部共享数据设置初始值的语句v 高级进程通信机制可分为：高级进程通信机制可分为

5、：共享存储器系统共享存储器系统 消息传递系统消息传递系统 管道通信管道通信10重点回顾重点回顾v 线程线程在引入线程之后，进程作为资源分配的基本在引入线程之后，进程作为资源分配的基本单位，而线程作为独立调度和运行的基本单单位，而线程作为独立调度和运行的基本单位位v 高级调度（高级调度（high-level schedulinghigh-level scheduling）又称作业调度或长程调度，它是根据某种算又称作业调度或长程调度，它是根据某种算法将外存上处于后备作业队列中的若干作业法将外存上处于后备作业队列中的若干作业调入内存，为作业分配所需资源并建立相应调入内存，为作业分配所需资源并建立相应

6、进程。进程。113.1.2 3.1.2 中级调度中级调度v中级调度中级调度(middle-level scheduling)(middle-level scheduling)又称内存调度，又称内存调度，它是进程在内存和外存之间的对换。它是进程在内存和外存之间的对换。v具有中级调度的系统中，进程除了具有三个基本具有中级调度的系统中，进程除了具有三个基本状态外，还具有静止就绪和静止阻塞两个状态。状态外，还具有静止就绪和静止阻塞两个状态。123.1.3 3.1.3 低级调度低级调度v 低级调度低级调度（low-level schedulinglow-level scheduling）又称进程调度、短

7、程调度，）又称进程调度、短程调度，它决定哪个就绪态进程获得处理机，即选择某个进程从就它决定哪个就绪态进程获得处理机，即选择某个进程从就绪态变为执行态。执行低级调度的原因多是处于执行态的绪态变为执行态。执行低级调度的原因多是处于执行态的进程由于某种原因放弃或被剥夺处理机。进程由于某种原因放弃或被剥夺处理机。v 低级调度是三级调度中的低级调度是三级调度中的最终调度最终调度，又称底层调度。在这，又称底层调度。在这级调度中真正实现了处理机的分配，级调度中真正实现了处理机的分配，它是系统不可缺少的它是系统不可缺少的最基本调度最基本调度。133.1.3 3.1.3 低级调度低级调度v进程调度的功能主要包括

8、以下两部分：进程调度的功能主要包括以下两部分： 选择就绪进程选择就绪进程 进程切换进程切换143.1.4 3.1.4 三级调度关系三级调度关系v分级调度系统中，各级调度分别在不同的调度时分级调度系统中，各级调度分别在不同的调度时机进行。对于一个用户作业来说，通常要经历高机进行。对于一个用户作业来说，通常要经历高级调度、中级调度和低级调度才能完成整个作业级调度、中级调度和低级调度才能完成整个作业程序的运行。程序的运行。153.1.4 3.1.4 三级调度关系三级调度关系163.2 3.2 进程进程调度目标和调度方式调度目标和调度方式3.2.1 3.2.1 进程调度目标进程调度目标（1 1）公平性

9、）公平性（2 2）高效率）高效率（3 3）低响应时间）低响应时间（4 4）高吞吐量）高吞吐量（5 5）特殊应用要求）特殊应用要求173.2.1 3.2.1 进程调度目标进程调度目标（1 1）多道批处理操作系统）多道批处理操作系统 多道批处理系统强调高效利用系统资源和高作业吞吐多道批处理系统强调高效利用系统资源和高作业吞吐量。进程提交给处理机后就不再与外部进行交互，系统量。进程提交给处理机后就不再与外部进行交互，系统按照调度策略安排它们运行，直到诸进程完成为止。按照调度策略安排它们运行，直到诸进程完成为止。（2 2）分时操作系统）分时操作系统 分时系统更关心多个用户的公平性和及时响应性，它分时系

10、统更关心多个用户的公平性和及时响应性，它不允许某个进程长时间占用处理机。分时系统多采用时不允许某个进程长时间占用处理机。分时系统多采用时间片轮转调度算法或在其基础上改进的其他调度算法。间片轮转调度算法或在其基础上改进的其他调度算法。但处理机在各个进程之间频繁切换会增加系统时空开销，但处理机在各个进程之间频繁切换会增加系统时空开销，延长各个进程在系统中的存在时间。分时系统最关注的延长各个进程在系统中的存在时间。分时系统最关注的是交互性和各进程的均衡性，对进程的执行效率和系统是交互性和各进程的均衡性，对进程的执行效率和系统开销往往要求并不苛刻。开销往往要求并不苛刻。183.2.1 3.2.1 进程

11、调度目标进程调度目标（3 3）实时操作系统）实时操作系统 实时操作系统必须保证实时进程的请求得到及时实时操作系统必须保证实时进程的请求得到及时响应，往往不考虑处理机的使用效率。实时系统响应，往往不考虑处理机的使用效率。实时系统采取的调度算法和其他类型系统采取的调度算法采取的调度算法和其他类型系统采取的调度算法相比有很大不同，其调度算法的最大特点是可抢相比有很大不同，其调度算法的最大特点是可抢占性。占性。（4 4）通用操作系统）通用操作系统 通用操作系统中，对进程调度没有特殊限制和要通用操作系统中，对进程调度没有特殊限制和要求，选择进程调度算法时主要追求处理机使用的求，选择进程调度算法时主要追求

12、处理机使用的公平性以及各类资源使用的均衡性公平性以及各类资源使用的均衡性193.2.2 3.2.2 进程调度方式进程调度方式v进程调度有两种基本方式：进程调度有两种基本方式：非抢占方式非抢占方式和和抢占抢占方式方式。（1）非抢占方式（）非抢占方式（Nonpreemptive）v进程一旦获得处理机执行，其他进程就不能中断它的执进程一旦获得处理机执行，其他进程就不能中断它的执行，即使当前等待进程中出现了优先级更高的请求进程行，即使当前等待进程中出现了优先级更高的请求进程也不允许该进程抢占处理机。直到执行态进程完成或发也不允许该进程抢占处理机。直到执行态进程完成或发生某个事件主动放弃处理机，才能调度

13、其他进程获得处生某个事件主动放弃处理机，才能调度其他进程获得处理机执行。理机执行。v这种调度方式的优点是实现简单、系统开销小，适用于这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统。但它难以满足实时任务的要求，在大多数批处理系统。但它难以满足实时任务的要求，在要求比较严格的实时操作系统中，一般不宜采用此类调要求比较严格的实时操作系统中，一般不宜采用此类调度方式。度方式。 203.2.2 3.2.2 进程调度方式进程调度方式（2 2）抢占方式（）抢占方式（PreemptivePreemptive） 抢占式调度是指在进程并发执行中，如果就绪进程中抢占式调度是指在进程并发执行中，如果

14、就绪进程中某个进程优先级比当前运行进程的优先级还高，无论某个进程优先级比当前运行进程的优先级还高，无论当前正在运行的进程是否结束，允许高优先级进程抢当前正在运行的进程是否结束，允许高优先级进程抢占当前运行进程的处理机并立即执行。占当前运行进程的处理机并立即执行。 抢占式调度可确保高优先级进程立即获得处理机。抢占式调度可确保高优先级进程立即获得处理机。抢占式调度在实际系统中具有重要意义。抢占式调度在实际系统中具有重要意义。213.2.2 3.2.2 进程调度方式进程调度方式支持抢占式调度的系统中，一般的抢占原则如下：支持抢占式调度的系统中，一般的抢占原则如下：优先权原则优先权原则 就绪的高优先权

15、进程有权抢占低优先权进程的就绪的高优先权进程有权抢占低优先权进程的CPUCPU。 短作业优先原则短作业优先原则 就绪的短作业有权抢占长作业的就绪的短作业有权抢占长作业的CPUCPU。 时间片原则时间片原则 一个时间片用完后，系统重新进行进程调度一个时间片用完后，系统重新进行进程调度223.3 3.3 调度算法的评价准则调度算法的评价准则(1) (1) 作业周转时间作业周转时间 所谓作业周转时间是指从作业被提交给系统开始，所谓作业周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。到作业完成为止的这段时间间隔。平均周转时间：平均周转时间： 平均带权周转时间平均带权周转时间：niiT

16、nT11niSiiTTnW11233.3.1 3.3.1 面向用户的评价准则面向用户的评价准则(2) (2) 响应时间响应时间 响应时间是指从进程输入第一个请求到系统给响应时间是指从进程输入第一个请求到系统给出首次响应的时间间隔。用户请求的响应时间出首次响应的时间间隔。用户请求的响应时间越短，用户的满意度越高。越短，用户的满意度越高。 响应时间通常由三部分时间组成：进程请求传响应时间通常由三部分时间组成：进程请求传送到处理机的时间、处理机对请求信息进行处送到处理机的时间、处理机对请求信息进行处理的时间、响应信息回送到显示器显示的时间。理的时间、响应信息回送到显示器显示的时间。243.3.1 3

17、.3.1 面向用户的评价准则面向用户的评价准则(3)(3)截止时间截止时间 截止时间是指用户或其他系统对运行进程可容忍的最截止时间是指用户或其他系统对运行进程可容忍的最大延迟时间。在实时系统中，通常用该准则衡量一个大延迟时间。在实时系统中，通常用该准则衡量一个调度算法是否合格。在实际系统评价中，主要考核的调度算法是否合格。在实际系统评价中，主要考核的是开始截止时间和完成截止时间。是开始截止时间和完成截止时间。(4) (4) 优先权准则优先权准则 在批处理、分时和实时系统中选择调度算法时，为保在批处理、分时和实时系统中选择调度算法时，为保证某些紧急作业得到及时处理，必须遵循优先权准则。证某些紧急

18、作业得到及时处理，必须遵循优先权准则。因此，系统对不同进程设立优先级，高优先级进程优因此，系统对不同进程设立优先级，高优先级进程优先获得处理机的使用权先获得处理机的使用权。253.3.2 3.3.2 面向面向系统的评价准则系统的评价准则v对计算机系统而言，在保证用户请求被高效处理的基础对计算机系统而言，在保证用户请求被高效处理的基础上，尽量使计算机系统中的各类资源得到充分利用。上，尽量使计算机系统中的各类资源得到充分利用。 面向系统的调度指标有：面向系统的调度指标有： (1) (1) 系统吞吐量系统吞吐量 (2) (2) 处理机利用率处理机利用率 (3) (3) 各类资源均衡利用各类资源均衡利

19、用 (4) (4) 调度算法实现准则调度算法实现准则263.4 3.4 典型进程调度算法典型进程调度算法3.4.1 3.4.1 先来先服务调度算法先来先服务调度算法3.4.2 3.4.2 短作业短作业（进程）优先调度算法（进程）优先调度算法3.4.4 3.4.4 时间片轮转调度算法时间片轮转调度算法3.4.5 3.4.5 优先级优先级调度算法调度算法3.4.6 3.4.6 高响应比优先高响应比优先调度算法调度算法3.4.7 3.4.7 多级多级反馈队列调度算法反馈队列调度算法重点重点273.4.1 先来先服务调度算法先来先服务调度算法vFCFS( First Come First Servic

20、e)算法按照进程就算法按照进程就绪的先后顺序调度进程，越早到达的进程，越先绪的先后顺序调度进程，越早到达的进程，越先执行。执行。FCFS算法的优缺点：算法的优缺点： 有利于长进程，不利于短进程，排在长进程后有利于长进程，不利于短进程，排在长进程后边的短进程往往等待的时间较长，导致其周转时边的短进程往往等待的时间较长，导致其周转时间过长，没有体现出短进程优先原则。间过长，没有体现出短进程优先原则。 有利于处理机繁忙的进程，不利于输入输出繁有利于处理机繁忙的进程，不利于输入输出繁忙的进程。忙的进程。 算法简单，易于实现，系统开销小。算法简单，易于实现，系统开销小。283.4.2 3.4.2 短作业

21、短作业（进程）优先调度算法（进程）优先调度算法又称为又称为“短进程优先短进程优先”SPN(Shortest Process SPN(Shortest Process Next)Next)；这是对；这是对FCFSFCFS算法的改进，其目标是算法的改进，其目标是减少平均周转时间。减少平均周转时间。其思想是：对其思想是：对预计执行时间预计执行时间短的作业（进短的作业（进程）优先分派处理机。通常后来的短作业程）优先分派处理机。通常后来的短作业不抢先不抢先正在执行的作业。正在执行的作业。29SJ(P)FSJ(P)F的特点的特点v优点：优点： 比比FCFSFCFS改善改善平均周转时间平均周转时间和和平均带

22、权周转时间平均带权周转时间，缩短作业的等待时间；，缩短作业的等待时间； 提高系统的提高系统的吞吐量吞吐量；v缺点：缺点： 对长作业非常不利对长作业非常不利，可能长时间得不到执行；，可能长时间得不到执行； 未能依据作业的未能依据作业的紧迫程度紧迫程度来划分执行的优先级；来划分执行的优先级； 难以准确估计作业（进程）的执行时间难以准确估计作业（进程）的执行时间，从而影，从而影响调度性能。响调度性能。303.4.4 3.4.4 时间片轮转调度算法时间片轮转调度算法v时间片轮转算法（时间片轮转算法（RRRR，Round RobinRound Robin）依据公平服）依据公平服务的原则，将处理机的运行时

23、间划分成等长的时间务的原则，将处理机的运行时间划分成等长的时间片，轮转式分配给各个就绪进程使用。片，轮转式分配给各个就绪进程使用。v采用此算法的系统中，所有就绪进程按照先来先服采用此算法的系统中，所有就绪进程按照先来先服务的原则排成一个队列，每次调度时将处理机分派务的原则排成一个队列，每次调度时将处理机分派给队首进程。如果进程在一个时间片内没执行完，给队首进程。如果进程在一个时间片内没执行完，那么调度程序强行将该进程中止，进程由执行态变那么调度程序强行将该进程中止，进程由执行态变为就绪态并把处理机分配给下一个就绪进程。该算为就绪态并把处理机分配给下一个就绪进程。该算法能保证就绪队列中的所有进程

24、在一给定的时间段法能保证就绪队列中的所有进程在一给定的时间段内均能获得处理机运行。内均能获得处理机运行。31v时间片轮转法的原理见图所示。时间片轮转法的原理见图所示。图 轮转法调度323.4.5 3.4.5 优先级优先级调度算法调度算法v 优先级调度算法（优先级调度算法（Priority SchedulingPriority Scheduling）为每个进程赋予一个整）为每个进程赋予一个整数，表示其优先级。就绪进程按照优先级的大小顺序排队，调数，表示其优先级。就绪进程按照优先级的大小顺序排队，调度程序选择优先级最高的进程获得度程序选择优先级最高的进程获得CPUCPU。该算法常被用于批处。该算法

25、常被用于批处理系统中。理系统中。1 1优先权调度算法的类型优先权调度算法的类型v 为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先入了最高优先权优先(FPF)(FPF)调度算法。调度算法。v 此算法常被用于此算法常被用于批处理系统批处理系统中，作为中，作为作业调度作业调度算法，也作为多算法，也作为多种操作系统中的种操作系统中的进程调度进程调度算法，还可用于算法，还可用于实时系统实时系统中。中。v 当把该算法用于作业调度时，系统将从后备队列中选择若干个当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高优先

26、权最高的作业装入内存。的作业装入内存。v 当用于进程调度时，该算法是把处理机分配给就绪队列中优先当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。权最高的进程，这时，又可进一步把该算法分成如下两种。331 1优先优先级级调度算法的类型调度算法的类型1) 1) 非抢占式优先权算法非抢占式优先权算法v 系统一旦把处理机分配给就绪队列中优先权最高的进程后系统一旦把处理机分配给就绪队列中优先权最高的进程后，该，该进程便一直执行下去，直至完成进程便一直执行下去，直至完成；或因发生某事件使；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分

27、配给另该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。一优先权最高的进程。v 这种调度算法主要用于批处理系统中；也可用于某些对实这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。时性要求不严的实时系统中。 2) 2) 抢占式优先权调度算法抢占式优先权调度算法v 系统同样是把处理机分配给优先权最高的进程，使之执行系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个。但在其执行期间，只要又出现了另一个其优先权更其优先权更高的高的进程，进程调度程序就进程，进程调度程序就立即停止立即停止当前进程当前进程( (原优先权最高

28、的原优先权最高的进程进程) )的执行，重新将处理机分配给新到的优先权最高的进的执行，重新将处理机分配给新到的优先权最高的进程。程。v 显然，这种抢占式的优先权调度算法能更好地满足紧迫作显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。对性能要求较高的批处理和分时系统中。 342 2优先优先级级的类型的类型v对于最高优先权优先调度算法，其关键在于：它对于最高优先权优先调度算法，其关键在于：它是使用是使用静态优先权静态优先权，还是用，还是用动态优先权动态优先权，以

29、及如，以及如何确定进程的优先权。何确定进程的优先权。1) 1) 静态优先权静态优先权v静态优先权是在静态优先权是在创建进程时确定创建进程时确定的，且在进程的的，且在进程的整个运行期间整个运行期间保持不变保持不变。一般地，优先权是利用。一般地，优先权是利用某一范围内的一个整数来表示的。某一范围内的一个整数来表示的。v确定进程优先权的依据有如下三个方面：确定进程优先权的依据有如下三个方面：(1) (1) 进程类型。进程类型。(2) (2) 进程对资源的需求。进程对资源的需求。(3) (3) 用户要求。用户要求。352优先级级的类型2) 2) 动态优先动态优先级级v动态优先权是指在创建进程时所赋予的

30、优先动态优先权是指在创建进程时所赋予的优先权，是权，是可以可以随进程的推进或随其等待时间的随进程的推进或随其等待时间的增加而增加而改变改变的，以便获得更好的调度性能。的，以便获得更好的调度性能。363.4.6 3.4.6 高响应比优先高响应比优先调度算法调度算法最高响应比作业优先算法是对最高响应比作业优先算法是对FCFS方式和方式和SJF方式方式的一种综合平衡。响应比的一种综合平衡。响应比R定义为系统对作业的响定义为系统对作业的响应时间与作业要求运行时间的比值。应时间与作业要求运行时间的比值。一个作业或进程的响应比一个作业或进程的响应比R HRRF调度程序开始调度时，首先计算各个后备作调度程序

31、开始调度时，首先计算各个后备作业或各个就绪进程的响应比业或各个就绪进程的响应比 ,然后选择然后选择 值最大的作值最大的作业或进程。业或进程。需运行时间需运行时间需运行时间需运行时间等待时间等待时间需运行时间需运行时间响应时间响应时间/R需需运运行行时时间间等等待待时时间间1R37举例举例例：假定在一个处理机上执行以下五个作业：例：假定在一个处理机上执行以下五个作业： 作业号作业号 A B C D E 到达时间到达时间 0 1 2 3 4 运行时间运行时间 4 3 5 2 4 优先数优先数 1 4 2 5 3(优先数越大代优先数越大代表优先级越高表优先级越高)分别采用分别采用FCFS、SJF、R

32、R（时间片（时间片1），），HRRF (响应比高者优先响应比高者优先)和和四种调度算法时，试做：四种调度算法时，试做：（1） 计算每个作业的周转时间和带权周转时间计算每个作业的周转时间和带权周转时间 ；（2） 计算平均周转时间和平均带权周转时间。计算平均周转时间和平均带权周转时间。382.11.518342.25913 6 3.11618 2.6789 4 SJF带权周转时间带权周转时间周转时间周转时间完成时间完成时间2.83.55.5221带权周转时间带权周转时间914111064周转时间周转时间18 14 12 7 4 完成时间完成时间FCFSFCFS42534运行时间运行时间43210到

33、达时间到达时间平均平均EDCBA作业号作业号39图图3-5 qq=1和和qq=4时的进程运行情况时的进程运行情况 ABED(b) qq =4(a) qq =112345678910 11 1213 14 151617t18C4 3 5 2 4ACBDABAECECEC403.2911.63.251317 4811 3.21618 3910 31212 带权周转时间带权周转时间周转时间周转时间完成时间完成时间RRRR42534运行时间运行时间43210到达时间到达时间平均平均EDCBA作业号作业号2.388.43.51418 369 2.41214 267 144 带权周转时间带权周转时间周转时

34、间周转时间完成时间完成时间HRRF41带权周转时间带权周转时间周转时间周转时间完成时间完成时间优先级优先级42534运行时间运行时间43210到达时间到达时间平均平均EDCBA作业号作业号2.25913 1.536 3.21618 2.6789 144 作业号作业号 A B C D E到达时间到达时间 0 1 2 3 4运行时间运行时间 4 3 5 2 4优先数优先数 1 4 2 5 3(优优先数越大代表优先级越高先数越大代表优先级越高)423.4.7 3.4.7 多级多级反馈队列调度算法反馈队列调度算法v 多级反馈队列调度算法（多级反馈队列调度算法（MFQMFQ，Multilevel Fee

35、dback QueueMultilevel Feedback Queue）是综合时间片轮转调度算法和优先级调度算法并加以改进而是综合时间片轮转调度算法和优先级调度算法并加以改进而得到的算法。得到的算法。433.4.7 3.4.7 多级多级反馈队列调度算法反馈队列调度算法443.4.7 3.4.7 多级多级反馈队列调度算法反馈队列调度算法v 多级反馈队列调度算法的优点：多级反馈队列调度算法的优点： 保证了短进程的优先，可让终端型用户满意。短进程需要保证了短进程的优先，可让终端型用户满意。短进程需要的服务时间少，在前几级就绪队列中就能够完成。的服务时间少，在前几级就绪队列中就能够完成。 满足输入输

36、出型进程的要求。输入输出型进程经常需要等满足输入输出型进程的要求。输入输出型进程经常需要等待输入输出设备而阻塞，但阻塞的进程仍然处在较高优先级待输入输出设备而阻塞，但阻塞的进程仍然处在较高优先级队列中。队列中。 照顾了计算型长进程的执行。对于计算型的长进程，由于照顾了计算型长进程的执行。对于计算型的长进程，由于其执行时间长，往往要不断的向优先级低的调度队列转换。其执行时间长，往往要不断的向优先级低的调度队列转换。但是该算法中，优先级越低的调度队列其执行的时间片越长但是该算法中，优先级越低的调度队列其执行的时间片越长，这可以有效地减少长进程的调度次数，保证长进程能够较，这可以有效地减少长进程的调

37、度次数，保证长进程能够较快执行完毕。快执行完毕。 系统开销小。由于不需要动态计算时间片和优先级，进程系统开销小。由于不需要动态计算时间片和优先级，进程的优先级和时间片等于他所在调度队列的优先级和时间片的优先级和时间片等于他所在调度队列的优先级和时间片45典型调度算法比较典型调度算法比较46重点回顾重点回顾v中级调度中级调度(middle-level scheduling)(middle-level scheduling)又称内存调度，又称内存调度，它是进程在内存和外存之间的对换。它是进程在内存和外存之间的对换。v低级调度低级调度（low-level schedulinglow-level sc

38、heduling）又称进程调度、）又称进程调度、短程调度，它决定哪个就绪态进程获得处理机，短程调度，它决定哪个就绪态进程获得处理机，即选择某个进程从就绪态变为执行态。执行低级即选择某个进程从就绪态变为执行态。执行低级调度的原因多是处于执行态的进程由于某种原因调度的原因多是处于执行态的进程由于某种原因放弃或被剥夺处理机。放弃或被剥夺处理机。47重点回顾重点回顾典型进程调度算法典型进程调度算法 先来先服务调度算法先来先服务调度算法 短作业短作业（进程）优先调度算法（进程）优先调度算法 时间片轮转调度算法时间片轮转调度算法 优先级优先级调度算法调度算法 高响应比优先高响应比优先调度算法调度算法 多级

39、多级反馈队列调度算法反馈队列调度算法483.5 3.5 线程调度算法线程调度算法3 3.5.1 .5.1 用户级线程调度用户级线程调度 用户级线程是在用户态下创建的，系统内核并不知道线程的存在用户级线程是在用户态下创建的，系统内核并不知道线程的存在。此时系统内核和只支持进程的系统内核一样，只为进程服务，。此时系统内核和只支持进程的系统内核一样，只为进程服务，从就绪进程队列中选中一个进程并分配给它一个从就绪进程队列中选中一个进程并分配给它一个CPUCPU时间片。时间片。493.5.2 3.5.2 核心核心级线程调度级线程调度 在核心支持线程技术的系统中，内核直接调度线程。线程调度时在核心支持线程

40、技术的系统中，内核直接调度线程。线程调度时，内核不考虑该线程属于哪个进程。被选中的线程获得一个时间，内核不考虑该线程属于哪个进程。被选中的线程获得一个时间片，如果执行时间超过此时间片，该线程被系统强制挂起。如线片，如果执行时间超过此时间片，该线程被系统强制挂起。如线程在给定时间片内阻塞，处于内核的线程调度程序调度另一线程程在给定时间片内阻塞，处于内核的线程调度程序调度另一线程运行。后者和前者可能同属于一个进程，也可能属于不同进程。运行。后者和前者可能同属于一个进程，也可能属于不同进程。503 3.6 .6 实时调度算法实时调度算法v 实时系统是一种时间起主导作用的系统，对时间有着严格的要求实时

41、系统是一种时间起主导作用的系统，对时间有着严格的要求。在实时系统中，每一个实时任务都有一个时间约束要求。实时。在实时系统中，每一个实时任务都有一个时间约束要求。实时调度（调度（real-time schedulingreal-time scheduling）的目标就是合理地安排这些任务的执）的目标就是合理地安排这些任务的执行次序，使之满足各个实时任务的时间约束要求。行次序，使之满足各个实时任务的时间约束要求。v 通常，一个特定任务与一个截止时间相关联。截止时间包括：开通常，一个特定任务与一个截止时间相关联。截止时间包括：开始截止时间（任务在某时间以前，必须开始执行）和完成截止时始截止时间（任务

42、在某时间以前，必须开始执行）和完成截止时间（任务在某时间以前必须完成）间（任务在某时间以前必须完成）v 实时调度策略主要考虑如何使硬实时任务在规定的截止时间内完实时调度策略主要考虑如何使硬实时任务在规定的截止时间内完成（或开始）。同时，尽可能使软实时任务也能在规定的截止时成（或开始）。同时，尽可能使软实时任务也能在规定的截止时间内完成（或开始）。公平性和最短平均响应时间等准则不再显间内完成（或开始）。公平性和最短平均响应时间等准则不再显得重要。大多数现代操作系统都无法实现直接依据任务截止时间得重要。大多数现代操作系统都无法实现直接依据任务截止时间进行调度，它们一般通过提高响应速度，保证任务在其

43、截止时间进行调度，它们一般通过提高响应速度，保证任务在其截止时间内完成。内完成。513.6.1 3.6.1 实时调度目标和所需必要信息实时调度目标和所需必要信息v 一般情况下，实时系统中可能同时有多个周期性任务并发执行，一般情况下，实时系统中可能同时有多个周期性任务并发执行，形成任务流，这些实时任务都要求系统做出实时响应。系统能否形成任务流，这些实时任务都要求系统做出实时响应。系统能否对它们全部予以处理，取决于每个任务要求的处理时间和该任务对它们全部予以处理，取决于每个任务要求的处理时间和该任务出现的周期。例如，系统中有出现的周期。例如，系统中有n n个周期性任务，其中任务出现的个周期性任务，

44、其中任务出现的周期为周期为Pi,Pi,处理所需的处理所需的CPUCPU时间为时间为CiCi，那么系统能处理这个任务流，那么系统能处理这个任务流的条件是：的条件是：niPiCi11523.6.2 3.6.2 抢占调度和快速切换机制抢占调度和快速切换机制v 在要求严格的实时系统中，如硬实时系统，允许一个优先权高的在要求严格的实时系统中，如硬实时系统，允许一个优先权高的实时任务抢占优先权低的实时任务，从而满足实时任务对截止时实时任务抢占优先权低的实时任务，从而满足实时任务对截止时间的要求。如果一个实时任务不抢占就能够满足自己的截止时间间的要求。如果一个实时任务不抢占就能够满足自己的截止时间要求，则不

45、宜采取抢占调度，因为抢占调度系统开销较大。要求，则不宜采取抢占调度，因为抢占调度系统开销较大。v 在实际应用中，系统判断能否满足截止时间要求并不是一件容易在实际应用中，系统判断能否满足截止时间要求并不是一件容易的事。如系统小，需处理的任务较少，则容易判断能否满足截止的事。如系统小，需处理的任务较少，则容易判断能否满足截止时间要求；如系统较大，则很难判断能否满足其截止时间要求。时间要求；如系统较大，则很难判断能否满足其截止时间要求。v 快速切换机制可以实现对实时任务的快速切换。快速切换机制常快速切换机制可以实现对实时任务的快速切换。快速切换机制常用硬件装置实现快速中断机构，做到尽量不漏掉实时任务

46、的中断用硬件装置实现快速中断机构，做到尽量不漏掉实时任务的中断。在软件实现上，可通过提高分派程序对任务切换的速度来提高。在软件实现上，可通过提高分派程序对任务切换的速度来提高系统的性能。系统的性能。533.6.3 3.6.3 典型实时调度算法典型实时调度算法1最早截止时间优先调度算法（最早截止时间优先调度算法（EDF, Earliest Deadline First） 最早截止时间优先调度算法中根据实时任务的开始截止时间最早截止时间优先调度算法中根据实时任务的开始截止时间确定任务的优先级，截止时间越早，其优先级越高。调度程确定任务的优先级，截止时间越早，其优先级越高。调度程序把所有可以运行的进程按照其截止时间先后顺序放在一个序把所有可以运行的进程按