第三章 处理机调度

1、12本章内容本章内容3.1 三级调度体系三级调度体系3.2 进程调度目标和调度方式进程调度目标和调度方式3.3 调度算法的评价准则调度算法的评价准则3.4 典型进程调度算法典型进程调度算法3.5 线程调度算法线程调度算法3.6 实时调度算法实时调度算法33.1 三级调度体系三级调度体系3.1.1 高级调度高级调度1高级调度（高级调度（high-level scheduling）又称作业调度）又称作业调度或长程调度，它是根据某种算法将或长程调度，它是根据某种算法将外存上外存上处于处于后后备作业队列备作业队列中的若干作业中的若干作业调入内存调入内存，为作业分配，为作业分配所需资源并建立相应进程。所

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

3、状态变为运行状态。63.1.1 高级调度高级调度v在多道批处理系统中，为了管理和调度作业，系统在多道批处理系统中，为了管理和调度作业，系统为每个作业设置了一个作业控制块为每个作业设置了一个作业控制块(JCB)(JCB)，它记录，它记录作业的相关信息作业的相关信息。73.1.1 高级调度高级调度83.1.2 中中级调度级调度v中级调度中级调度(middle-level scheduling)又称内存调度，又称内存调度，它是它是进程在内存和外存进程在内存和外存之间的对换之间的对换。v具有中级调度的系统中，进程除了具有三个基本具有中级调度的系统中，进程除了具有三个基本状态外，还具有静止就绪和静止阻塞

4、两个状态。状态外，还具有静止就绪和静止阻塞两个状态。93.1.3 低低级调度级调度v 低级调度低级调度（low-level scheduling）又称进程调度、短程调）又称进程调度、短程调度，它决定哪个度，它决定哪个就绪态进程获得处理机就绪态进程获得处理机，即选择某个进程，即选择某个进程从就绪态变为执行态。执行低级调度的原因多是处于执行从就绪态变为执行态。执行低级调度的原因多是处于执行态的进程由于某种原因放弃或被剥夺处理机。态的进程由于某种原因放弃或被剥夺处理机。v 低级调度是三级调度中的低级调度是三级调度中的最终调度最终调度，又称底层调度。在这，又称底层调度。在这级调度中真正实现了处理机的分

5、配，级调度中真正实现了处理机的分配，它是系统不可缺少的它是系统不可缺少的最基本调度最基本调度。103.1.3 低低级调度级调度v进程调度的功能主要包括以下两部分：进程调度的功能主要包括以下两部分： 选择就绪进程选择就绪进程 进程切换进程切换113.1.4 三三级调度级调度关系关系v分级调度系统中，各级调度分别在不同的调度时分级调度系统中，各级调度分别在不同的调度时机进行。对于一个用户作业来说，通常要经历高机进行。对于一个用户作业来说，通常要经历高级调度、中级调度和低级调度才能完成整个作业级调度、中级调度和低级调度才能完成整个作业程序的运行程序的运行。123.1.4 三三级调度级调度关系关系13

6、3.2 进程进程调度目标和调度方式调度目标和调度方式3.2.1 进程调度目标进程调度目标（1）公平性）公平性（2）高效率）高效率（3）低响应时间）低响应时间（4）高吞吐量）高吞吐量（5）特殊应用要求）特殊应用要求143.2 进程进程调度目标和调度方式调度目标和调度方式不同类型的操作系统有不同的调度目标。不同类型的操作系统有不同的调度目标。(1)多道批处理操作系统多道批处理操作系统 多道批处理系统强调高效利用系统资源和高作业吞吐多道批处理系统强调高效利用系统资源和高作业吞吐量。量。(2)分时操作系统分时操作系统 分时系统更关心多个用户的公平性和及时响应性，它分时系统更关心多个用户的公平性和及时响

7、应性，它不允许某个进程长时间占用处理机。不允许某个进程长时间占用处理机。( (3 3) )实时操作系统实时操作系统 实时操作系统必须保证实时进程的请求得到及时响应，实时操作系统必须保证实时进程的请求得到及时响应，往往不考虑处理机的使用效率。其调度算法的最大特往往不考虑处理机的使用效率。其调度算法的最大特点是可抢占性。点是可抢占性。153.2.2 进程调度进程调度方式方式v进程调度有两种基本方式：进程调度有两种基本方式：非抢占方式非抢占方式和和抢占方式抢占方式。（1）非抢占方式（）非抢占方式（Nonpreemptive）v进程一旦获得处理机执行，其他进程就不能中断它的执进程一旦获得处理机执行，其

8、他进程就不能中断它的执行，即使当前等待进程中出现了优先级更高的请求进程行，即使当前等待进程中出现了优先级更高的请求进程也不允许该进程抢占处理机。直到执行态进程完成或发也不允许该进程抢占处理机。直到执行态进程完成或发生某个事件主动放弃处理机，才能调度其他进程获得处生某个事件主动放弃处理机，才能调度其他进程获得处理机执行。理机执行。v这种调度方式的优点是实现简单、系统开销小，适用于这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统。但它难以满足实时任务的要求，在大多数批处理系统。但它难以满足实时任务的要求，在要求比较严格的实时操作系统中，一般不宜采用此类调要求比较严格的实时操作系统中

9、，一般不宜采用此类调度方式。度方式。 163.2.2 进程调度进程调度方式方式（2）抢占方式（）抢占方式（Preemptive） v 抢占式调度是指在进程并发执行中，如果就绪进抢占式调度是指在进程并发执行中，如果就绪进程中某个进程优先级比当前运行进程的优先级还高，程中某个进程优先级比当前运行进程的优先级还高，无论当前正在运行的进程是否结束，允许高优先级无论当前正在运行的进程是否结束，允许高优先级进程抢占当前运行进程的处理机并立即执行。进程抢占当前运行进程的处理机并立即执行。v 抢占式调度可确保高优先级进程立即获得处理机。抢占式调度可确保高优先级进程立即获得处理机。抢占式调度在实际系统中具有重要

10、意义。抢占式调度在实际系统中具有重要意义。173.2.2 进程调度进程调度方式方式支持抢占式调度的系统中，一般的抢占原则如下：支持抢占式调度的系统中，一般的抢占原则如下：优先权原则优先权原则 就绪的高优先权进程有权抢占低优先权进程的就绪的高优先权进程有权抢占低优先权进程的CPU。 短作业优先原则短作业优先原则 就绪的短作业有权抢占长作业的就绪的短作业有权抢占长作业的CPU。 时间片原则时间片原则 一个时间片用完后，系统重新进行进程调度一个时间片用完后，系统重新进行进程调度183.3 调度算法的评价准则调度算法的评价准则3.3.1 面向用户的评价准则面向用户的评价准则(1) (1) 作业周转时间

11、作业周转时间 所谓作业周转时间是指从作业被提交给系统所谓作业周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。开始，到作业完成为止的这段时间间隔。平均周转时间：平均周转时间： 平均带权周转时间平均带权周转时间：niiTnT11niSiiTTnW11193.3.1 面向用户的评价准则面向用户的评价准则(2) (2) 响应时间响应时间 响应时间是指从进程输入第一个请求到系统响应时间是指从进程输入第一个请求到系统给出首次响应的时间间隔。用户请求的响应时给出首次响应的时间间隔。用户请求的响应时间越短，用户的满意度越高。间越短，用户的满意度越高。 响应时间通常由三部分时间组成：进程请求响

12、应时间通常由三部分时间组成：进程请求传送到处理机的时间、处理机对请求信息进行传送到处理机的时间、处理机对请求信息进行处理的时间、响应信息回送到显示器显示的时处理的时间、响应信息回送到显示器显示的时间。间。203.3.1 面向用户的评价准则面向用户的评价准则(3)(3)截止时间截止时间 截止时间是指用户或其他系统对运行进程可容忍的截止时间是指用户或其他系统对运行进程可容忍的最大延迟时间。在实时系统中，通常用该准则衡量一最大延迟时间。在实时系统中，通常用该准则衡量一个调度算法是否合格。在实际系统评价中，主要考核个调度算法是否合格。在实际系统评价中，主要考核的是开始截止时间和完成截止时间。的是开始截

13、止时间和完成截止时间。(4) (4) 优先权准则优先权准则 在批处理、分时和实时系统中选择调度算法时，为在批处理、分时和实时系统中选择调度算法时，为保证某些紧急作业得到及时处理，必须遵循优先权准保证某些紧急作业得到及时处理，必须遵循优先权准则。因此，系统对不同进程设立优先级，高优先级进则。因此，系统对不同进程设立优先级，高优先级进程优先获得处理机的使用权程优先获得处理机的使用权。213.3.2 面向面向系统的评价准则系统的评价准则v对计算机系统而言，在保证用户请求被高效处理的对计算机系统而言，在保证用户请求被高效处理的基础上，尽量使计算机系统中的各类资源得到充分基础上，尽量使计算机系统中的各类

14、资源得到充分利用。利用。 面向系统的调度指标有：面向系统的调度指标有： (1) (1) 系统吞吐量系统吞吐量 (2) (2) 处理机利用率处理机利用率 (3) (3) 各类资源均衡利用各类资源均衡利用 (4) (4) 调度算法实现准则调度算法实现准则223.4 典型进程调度算法典型进程调度算法3.4.1 先来先服务调度算法先来先服务调度算法3.4.2 短作业短作业（进程）优先调度算法（进程）优先调度算法3.4.4 时间片轮转调度算法时间片轮转调度算法3.4.5 优先级优先级调度算法调度算法3.4.6 高响应比优先高响应比优先调度算法调度算法3.4.7 多级多级反馈队列调度算法反馈队列调度算法重

15、点重点233.4.1 先来先服务调度算法先来先服务调度算法vFCFS( First Come First Service)算法按照进程就算法按照进程就绪的先后顺序调度进程，越早到达的进程，越先绪的先后顺序调度进程，越早到达的进程，越先执行。执行。FCFS算法的优缺点：算法的优缺点： 有利于长进程，不利于短进程，排在长进程后有利于长进程，不利于短进程，排在长进程后边的短进程往往等待的时间较长，导致其周转时边的短进程往往等待的时间较长，导致其周转时间过长，没有体现出短进程优先原则。间过长，没有体现出短进程优先原则。 有利于处理机繁忙的进程，不利于输入输出繁有利于处理机繁忙的进程，不利于输入输出繁忙

16、的进程。忙的进程。 算法简单，易于实现，系统开销小。算法简单，易于实现，系统开销小。243.4.2 短作业短作业（进程）优先调度算法（进程）优先调度算法 “短作业优先短作业优先”SJF 又称为又称为“短进程优短进程优先先”SPF(Shortest Process First)；这是对；这是对FCFS算法的改进，其目标是减少平均周转算法的改进，其目标是减少平均周转时间。时间。 其思想是：对其思想是：对预计执行时间预计执行时间短的作业（进短的作业（进程）优先分派处理机。通常后来的短作业程）优先分派处理机。通常后来的短作业不抢先不抢先正在执行的作业。正在执行的作业。25SJ(P)F的特点的特点v优点

17、：优点： 比比FCFS改善改善平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间，缩短作业的等待时间；，缩短作业的等待时间； 提高系统的提高系统的吞吐量吞吐量；v缺点：缺点： 对长作业非常不利对长作业非常不利，可能长时间得不到执行；，可能长时间得不到执行； 未能依据作业的未能依据作业的紧迫程度紧迫程度来划分执行的优先级；来划分执行的优先级； 难以准确估计作业（进程）的执行时间难以准确估计作业（进程）的执行时间，从而影，从而影响调度性能。响调度性能。263.4.4 时间片轮转调度算法时间片轮转调度算法v时间片轮转算法（时间片轮转算法（RR，Round Robin）依据公平服）依据公平服

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

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

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

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

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

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

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

25、进程的推进或随其等待时间的增加而增加而改变改变的，以便获得更好的调度性能。的，以便获得更好的调度性能。323.4.6 高响应比优先高响应比优先调度算法调度算法最高响应比作业优先算法是对最高响应比作业优先算法是对FCFS方式和方式和SJF方式方式的一种综合平衡。响应比的一种综合平衡。响应比R定义为系统对作业的响定义为系统对作业的响应时间与作业要求运行时间的比值。应时间与作业要求运行时间的比值。一个作业或进程的响应比一个作业或进程的响应比R HRRF调度程序开始调度时，首先计算各个后备作调度程序开始调度时，首先计算各个后备作业或各个就绪进程的响应比业或各个就绪进程的响应比 ,然后选择然后选择 值最

26、大的作值最大的作业或进程。业或进程。需运行时间需运行时间需运行时间需运行时间等待时间等待时间需运行时间需运行时间响应时间响应时间/R需运行时间需运行时间等待时间等待时间1R33重点回顾重点回顾v 线程线程在引入线程之后，进程作为资源分配的基本在引入线程之后，进程作为资源分配的基本单位，而线程作为独立调度和运行的基本单单位，而线程作为独立调度和运行的基本单位位34重点回顾重点回顾v高级调度（高级调度（high-level scheduling）又称作业调）又称作业调度或长程调度，它是根据某种算法将度或长程调度，它是根据某种算法将外存上外存上处处于于后备作业队列后备作业队列中的若干作业中的若干作业

27、调入内存调入内存，为作，为作业分配所需资源并建立相应进程。业分配所需资源并建立相应进程。v中级调度中级调度(middle-level scheduling)又称内存调度又称内存调度，它是，它是进程在内存和外存之间进程在内存和外存之间的对换的对换。v低级调度低级调度（low-level scheduling）又称进程调度）又称进程调度、短程调度，它决定哪个、短程调度，它决定哪个就绪态进程获得处理就绪态进程获得处理机机，即选择某个进程从就绪态变为执行态。执，即选择某个进程从就绪态变为执行态。执行低级调度的原因多是处于执行态的进程由于行低级调度的原因多是处于执行态的进程由于某种原因放弃或被剥夺处理机

28、。某种原因放弃或被剥夺处理机。35重点回顾重点回顾v典型进程调度算法典型进程调度算法 先来先服务调度算法先来先服务调度算法 短作业短作业（进程）优先调度算法（进程）优先调度算法 时间片轮转调度算法时间片轮转调度算法 高响应比优先调度算法高响应比优先调度算法 优先级优先调度算法优先级优先调度算法36举例举例例：假定在一个处理机上执行以下五个作业：例：假定在一个处理机上执行以下五个作业： 作业号作业号 A B C D E 到达时间到达时间 0 1 2 3 4 运行时间运行时间 4 3 5 2 4 优先数优先数 1 4 2 5 3(优先数越大代优先数越大代表优先级越高表优先级越高)分别采用分别采用F

29、CFS、SJF、RR（时间片（时间片1），），HRRF (响应比高者优先响应比高者优先)和静态优先权优先和静态优先权优先五种调度算法时，试做：五种调度算法时，试做：（1） 计算每个作业的周转时间和带权周转时间计算每个作业的周转时间和带权周转时间 ；（2） 计算平均周转时间和平均带权周转时间。计算平均周转时间和平均带权周转时间。372.11.518342.25913 6 3.11618 2.6789 4 SJF带权周转时间带权周转时间周转时间周转时间完成时间完成时间2.83.55.5221带权周转时间带权周转时间914111064周转时间周转时间18 14 12 7 4 完成时间完成时间FCFS

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

31、267 144 带权周转时间带权周转时间周转时间周转时间完成时间完成时间HRRF40带权周转时间带权周转时间周转时间周转时间完成时间完成时间优先级优先级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(优优先数越大代表优先级越高先数越大代表优先级越高)413.4.7 多级多级反馈队列调度算法反馈队列调度算法v多级反馈队列调度算法（多级反馈队列调度算法（MFQ，M

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

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

34、 系统开销小。由于不需要动态计算时间片和优先级，进程系统开销小。由于不需要动态计算时间片和优先级，进程的优先级和时间片等于他所在调度队列的优先级和时间片的优先级和时间片等于他所在调度队列的优先级和时间片44典型调度算法比较典型调度算法比较453.5 线程调度算法线程调度算法3.5.1 用户级线程调度用户级线程调度 用户级线程是在用户态下创建的，系统内核并不知道线程的存在用户级线程是在用户态下创建的，系统内核并不知道线程的存在。此时系统内核和只支持进程的系统内核一样，只为进程服务，。此时系统内核和只支持进程的系统内核一样，只为进程服务，从就绪进程队列中选中一个进程并分配给它一个从就绪进程队列中选

35、中一个进程并分配给它一个CPU时间片。时间片。463.5.2 核心核心级线程调度级线程调度 在核心支持线程技术的系统中，内核直接调度线程。线程调度时在核心支持线程技术的系统中，内核直接调度线程。线程调度时，内核不考虑该线程属于哪个进程。被选中的线程获得一个时间，内核不考虑该线程属于哪个进程。被选中的线程获得一个时间片，如果执行时间超过此时间片，该线程被系统强制挂起。如线片，如果执行时间超过此时间片，该线程被系统强制挂起。如线程在给定时间片内阻塞，处于内核的线程调度程序调度另一线程程在给定时间片内阻塞，处于内核的线程调度程序调度另一线程运行。后者和前者可能同属于一个进程，也可能属于不同进程。运行

36、。后者和前者可能同属于一个进程，也可能属于不同进程。473.6 实时调度算法实时调度算法v 实时系统是一种时间起主导作用的系统，对时间有着严格的实时系统是一种时间起主导作用的系统，对时间有着严格的要求。在实时系统中，每一个实时任务都有一个时间约束要要求。在实时系统中，每一个实时任务都有一个时间约束要求。实时调度（求。实时调度（real-time scheduling）的目标就是合理地安）的目标就是合理地安排这些任务的执行次序，使之满足各个实时任务的时间约束排这些任务的执行次序，使之满足各个实时任务的时间约束要求。要求。v 通常，一个特定任务与一个截止时间相关联。截止时间包括通常，一个特定任务与

37、一个截止时间相关联。截止时间包括：开始截止时间（任务在某时间以前，必须开始执行）和完：开始截止时间（任务在某时间以前，必须开始执行）和完成截止时间（任务在某时间以前必须完成）成截止时间（任务在某时间以前必须完成）483.6.1 实时调度目标和所需必要信息实时调度目标和所需必要信息v 一般情况下，实时系统中可能同时有多个周期性任务并发执行一般情况下，实时系统中可能同时有多个周期性任务并发执行，形成任务流，这些实时任务都要求系统做出实时响应。系统，形成任务流，这些实时任务都要求系统做出实时响应。系统能否对它们全部予以处理，取决于每个任务要求的处理时间和能否对它们全部予以处理，取决于每个任务要求的处

38、理时间和该任务出现的周期。该任务出现的周期。493.6.2 抢占调度和快速切换机制抢占调度和快速切换机制v 在要求严格的实时系统中，如硬实时系统，允许一个优先权高的在要求严格的实时系统中，如硬实时系统，允许一个优先权高的实时任务抢占优先权低的实时任务，从而满足实时任务对截止时实时任务抢占优先权低的实时任务，从而满足实时任务对截止时间的要求。如果一个实时任务不抢占就能够满足自己的截止时间间的要求。如果一个实时任务不抢占就能够满足自己的截止时间要求，则不宜采取抢占调度，因为抢占调度系统开销较大。要求，则不宜采取抢占调度，因为抢占调度系统开销较大。v 在实际应用中，系统判断能否满足截止时间要求并不是

39、一件容易在实际应用中，系统判断能否满足截止时间要求并不是一件容易的事。如系统小，需处理的任务较少，则容易判断能否满足截止的事。如系统小，需处理的任务较少，则容易判断能否满足截止时间要求；如系统较大，则很难判断能否满足其截止时间要求。时间要求；如系统较大，则很难判断能否满足其截止时间要求。v 快速切换机制可以实现对实时任务的快速切换。快速切换机制常快速切换机制可以实现对实时任务的快速切换。快速切换机制常用硬件装置实现快速中断机构，做到尽量不漏掉实时任务的中断用硬件装置实现快速中断机构，做到尽量不漏掉实时任务的中断。在软件实现上，可通过提高分派程序对任务切换的速度来提高。在软件实现上，可通过提高分

40、派程序对任务切换的速度来提高系统的性能。系统的性能。503.6.3 典型实时调度算法典型实时调度算法1最早截止时间优先调度算法（最早截止时间优先调度算法（EDF, Earliest Deadline First） 最早截止时间优先调度算法中根据实时任务的开始截止时间最早截止时间优先调度算法中根据实时任务的开始截止时间确定任务的优先级，截止时间越早，其优先级越高。调度程确定任务的优先级，截止时间越早，其优先级越高。调度程序把所有可以运行的进程按照其截止时间先后顺序放在一个序把所有可以运行的进程按照其截止时间先后顺序放在一个以表格形式存在的就绪队列中，队首的任务具有最早截止时以表格形式存在的就绪队列中，队首的任务具有最早截止时间。调度程序调度时，总是选队首进程。间。调度程序调度时，总是选队首进程。 对于新到达的实时任务，系统查看其截止时间。如截止时间对于新到达的实时任务，系统查看其截止时间。如截止时间先于正在运行任务的截止时间，新进程抢占当前进程的先于正在运行任务的截止时间，新进程抢占当前进程的CPU使用权。使用权。 最早截止时间优先调度算法是抢占式调度算法，适用于周期最早截止时间优先调度算法是抢占式调度算法，适用于周期性和非周期实时任务的调度。性和非周期实时任务的调度。511最早截止时间