(5)--第5章 处理机调度操作系统原理.ppt

《(5)--第5章 处理机调度操作系统原理.ppt》由会员分享，可在线阅读，更多相关《(5)--第5章 处理机调度操作系统原理.ppt（69页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、本章目录 5.1 分级调度与调度目标 5.2 常用调度算法 5.3 实时系统的调度5.1 分级调度与调度目标 5.1.1 作业的概念 5.1.2 处理机调度的层次 5.1.3 进程调度方式与时机 5.1.4 调度算法选择依据与性能评价 5.1.1 作业的概念1作业和作业步作业：我们把计算机业务处理过程中，从程序输入开始到输出建档，用户要求计算机所做的有关该次业务的全部工作称为一个作业。作业由若干相互独立又相互联系的加工步骤顺序组成。每一个加工步骤称为一个作业步。作业用于早期批处理系统和现在的大型机、巨型机系统。5.1.1 作业的概念2作业说明书和作业控制块在批处理系统中，一个作业提交给系统之后

2、，系统还需要获知每个作业步的先后顺序及处理要求等信息。所以，作业在提交系统时，还需要编制作业说明书，并一起提交给系统。作业说明书体现了用户的控制意图，由作业说明书在系统中生成一个称为作业控制块的数据结构，从而达到管理和调度作业的目的。作业控制块保存了系统对作业进行管理和调度所需的全部信息，主要包含作业基本描述、作业控制描述和资源要求描述。5.1.1 作业的概念作业由程序、数据和作业说明书三部分组成。从系统的角度来看，作业是一个比进程更广的概念。一个作业总是由一个以上的进程组成。首先，系统为每个作业创建一个根进程；然后，按照作业控制语句的要求，系统或根进程为每个作业步创建至少一个相应的子进程；最

3、后，为各个子进程分配资源及调度各子进程执行以完成作业要求的任务。5.1.2 处理机调度的层次处理机调度按照层次可以分为三级：高级调度、中级调度和低级调度。用户作业从进入系统成为后备作业开始，直到运行结束退出系统为止，均需经历不同层次的调度。5.1.2 处理机调度的层次1高级调度又称为作业调度或长程调度，主要用于批处理系统。在批处理系统中，作业提交输入系统后，先驻留在外存输入井的后备队列上。高级调度负责从后备队列中选择多个作业调入内存，为它们创建进程并分配必要的资源，然后链接到就绪队列上。在分时系统中，为了做到及时响应，通过键盘输入的命令或数据等，都被直接送入内存创建进程，因而不需要设置高级调度

4、这个层次。类似地，通常实时系统也不需要高级调度。5.1.2 处理机调度的层次每当有作业执行完毕并撤离时，高级调度会选择一个或多个作业调入内存。此外，如果CPU 的空闲时间超过一定的阈值，系统也会触发高级调度选择后备队列中的作业进入内存。选择多少个作业进入内存取决于系统可以处理程序的数量，选择什么类型的作业进入内存取决于系统采用的高级调度算法。当进入内存的作业数目很多时，资源的利用率虽然有所提高，但每个作业的周转时间被拉长了；当进入内存的作业数目太少时，虽然作业的周转时间缩短了，但系统的资源利用率和系统吞吐量又降低了。因此，系统处理程序的数量应根据系统的规模和运行速度等情况做适当的调整。5.1.

5、2 处理机调度的层次2低级调度又称为进程调度或短程调度。低级调度负责按照某种调度算法，从内存的就绪队列中选择一个就绪进程获得CPU，并分派程序执行进程切换的具体操作。低级调度是最基本的一级调度，是各类操作系统必备的功能，其调度算法的优劣将直接影响整个系统的性能。因此，这部分代码是操作系统最为核心的部分，要求精心设计并常驻内存。在多线程系统中，线程成为调度的基本单位，此时还存在线程调度这个层次。5.1.2 处理机调度的层次3中级调度又称为交换调度或中程调度。为了缓解内存压力，中级调度负责按照一定的策略，把内存中的进程交换到外存交换区，或将外存交换区中的挂起进程调入内存。中级调度常用于分时操作系统

6、和应用虚拟内存技术的系统中，中级调度是交换功能的一部分。5.1.2 处理机调度的层次通常一个作业经过高级调度后，在内存会创建至少一个进程。进程在内存可能分多次被CPU 执行才能结束工作。当然该进程在此期间可能还经历几次内存与外存的交换过程。在三个调度层次中低级调度的执行频率最高，高级调度的执行频率最低，中级调度的执行频率居中。考虑到低级调度会频繁地发生，因此低级调度算法不宜太复杂。相反，高级调度的执行频率低，允许高级调度算法花费时间多一些。5.1.3 进程调度方式与时机进程调度有两种基本方式：非抢占式调度方式和抢占式调度方式。1非抢占式调度方式，也称为非剥夺式调度方式。采用非抢占式调度方式时，

7、一旦把CPU 分派给某个进程，该进程将一直执行下去，直至运行结束或因某种原因阻塞而不能运行，才将CPU 分派给其他进程，即不允许其他进程抢占正在运行的进程的CPU 的使用权。在非抢占式调度方式下，只有当系统中有进程退出或进程阻塞时，才会引发进程调度，选择另外一个就绪进程投入运行。优点：实现简单，系统开销小；缺点：难以满足有紧急任务的进程要求。分时系统和对时间要求比较严格的实时系统不使用这种方式。5.1.3 进程调度方式与时机2抢占式调度方式，也称为剥夺式调度方式。系统允许调度程序根据某个抢占原则，强行抢占正在运行的进程的CPU的使用权，将其分派给另外一个就绪进程。抢占原则有下面三种：优先权原则

8、，即就绪的高优先级进程有权抢占低优先级进程的CPU使用权。短进程优先原则，即就绪的短进程有权抢占长进程的CPU使用权。时间片原则，即正在运行的进程的时间片用完后，系统暂停该进程的执行而重新进行调度。在抢占式调度方式下，进程调度的执行频率相当频繁，因此增加了进程切换的开销，但避免了任何一个进程独占CPU太长时间，可以为进程提供较好的服务。5.1.4 调度算法选择依据与性能评价处理机调度方式和调度算法的选择取决于操作系统的类型及其设计目标。批处理操作系统会选择资源利用率高、平均周转时间短和系统吞吐量大的调度算法；分时操作系统会选择交互性好、响应时间短的调度算法；实时操作系统会选择能够处理紧急任务、

9、保证时间要求的调度算法。评价调度算法的性能是十分复杂的事情。面向用户的性能评价准则与单个用户感知的系统行为有关，如响应时间、周转时间、优先权和截止时间保证等。面向系统的性能评价准则主要考虑系统的效率和性能，如系统吞吐率、处理机利用率和各类资源的平衡利用等。5.1.4 调度算法选择依据与性能评价1调度算法性能评价的共同准则资源利用率。CPU 利用率成为衡量操作系统性能的重要准则。公平性。在用户或系统没有特殊要求时，进程应该被公平地对待，避免出现进程饥饿现象。5.1.4 调度算法选择依据与性能评价1调度算法性能评价的共同准则（续）各类资源的平衡利用。一个好的调度算法应尽可能使系统中的所有资源都处于

10、忙碌状态，尽可能保持系统资源使用的平衡性。策略强制执行。系统对所制定的策略，如抢占策略、安全策略等，必须予以准确执行，即使会造成某些工作的延迟也要执行。优先级。在批处理系统、分时系统和实时系统中都可以引入优先级准则，以保证某些紧急的作业能够得到及时处理。5.1.4 调度算法选择依据与性能评价2批处理系统调度算法常用评价准则周转时间是指从作业提交给系统开始，到作业完成为止的这段时间间隔。包括作业在外存后备队列中等待的时间、进程进入内存后在就绪队列中等待的时间、进程在CPU 上执行的时间及进程等待I/O 操作完成的时间。如果作业提交给系统的时刻是t1，完成的时刻是t2，那么作业的周转时间为Tw表示

11、作业在系统中的等待时间，Ts 表示作业在系统中的运行时间。即周转时间为作业在系统中的等待时间和运行时间之和。5.1.4 调度算法选择依据与性能评价2批处理系统调度算法常用评价准则（续）平均周转时间其中，Ti是第i 个作业的周转时间，n是作业流的个数。带权周转时间用于衡量周转时间中的有效工作时间。带权周转时间总是大于1 的，而且越接近1 越好。平均带权周转时间5.1.4 调度算法选择依据与性能评价2批处理系统调度算法常用评价准则（续）系统吞吐率是指单位时间内系统完成作业的个数。显然，若处理的长作业多，则系统吞吐率低；若处理的短作业多，则系统吞吐率高。系统吞吐率是评价批处理系统性能的重要指标。3分

12、时系统调度算法常用评价准则响应时间是指用户提交一个请求到系统响应（通常是系统有一个输出）的时间间隔。5.1.4 调度算法选择依据与性能评价4实时系统调度算法常用评价准则截止时间是衡量实时系统时限性能的主要指标，也是选择实时系统调度算法的重要准则。截止时间可以分为：开始截止时间：某任务必须开始执行的最迟时间完成截止时间：某任务必须完成的最迟时间。可预测性。可预测性是解决实时系统快速工作能力的一个有力工具。例如，在视频播放任务中，视频的连续播放可以提供请求的可预测性。若系统采用了双缓冲，则可以实现第i 帧的播放和第i+1帧的读取并行处理，从而提高其实时性。5.2 常用调度算法 5.2.1 先来先服

13、务调度算法 5.2.2 短进程（作业）优先调度算法 5.2.3 轮转调度算法 5.2.4 优先级调度算法 5.2.4 最高响应比优先调度算法 5.2.4 多级队列调度算法 5.2.4 多级反馈队列调度算法 5.2 常用调度算法以表5-1所示的作业流（或进程流）为例介绍常用的调度算法。5.2.1 先来先服务调度算法先来先服务（First Come First Served，FCFS）调度算法是一种最简单的调度算法。既可以用于高级调度，又可以用于低级调度。按照作业或进程到达系统的先后次序进行调度的。用于高级调度时，每次从后备队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、

14、创建进程，然后将进程链接到就绪队列。用于低级调度时，每次从就绪队列中选择一个最先就绪的进程，把CPU分派给它，使之投入运行，一直到该进程运行完毕或阻塞后，才让出CPU。FCFS调度算法是一种非抢占式调度算法。5.2.1 先来先服务调度算法以低级调度为例，讨论FCFS调度算法的性能。各进程的调度顺序及详细执行情况如图5-3所示。表5-2列出了各进程的周转时间、带权周转时间等调度性能指标值。5.2.1 先来先服务调度算法优点：FCFS调度算法简单、易于实现。缺点：有利于长进程，不利于短进程。FCFS调度算法只考虑了进程等待时间的长短，未考虑进程要求服务时间的长短，不利于短进程，尤其对于短进程紧随长

15、进程的情况更不适用（举例见下一页）。有利于CPU繁忙的进程，不利于I/O操作繁忙的进程。对于I/O操作繁忙的进程，每进行一次I/O操作都要等待系统中其他进程一个运行周期结束后才能再次获得CPU，故大大延长了进程运行的总时间，也不能有效利用各种外设资源。5.2.1 先来先服务调度算法不利于短进程示例。从表5-3可以看出，短进程P3的带权周转时间高达100，而长进程P4的带权周转时间仅为1.99。短进程P3为了等待长进程P2执行结束，其周转时间和带权周转时间将变得很大，从而使进程的平均周转时间和平均带权周转时间也变得很大。5.2.2 短进程（作业）优先调度算法Shortest Process Fi

16、rst，SPF 或 Shortest Job First，SJF该算法优先选择短进程（作业）投入运行，可分别用于高级调度和低级调度。SJF调度算法是从后备队列中选择一个或多个估计运行时间最短的作业，将它们调入内存运行。SPF调度算法是从就绪队列中选择一个估计运行时间最短的就绪进程，将CPU分派给它，使其执行。5.2.2 短进程（作业）优先调度算法下面以非抢占式为例介绍SPF 调度算法。各进程的调度顺序及详细执行情况如下所示。表5-4列出了各进程周转时间、带权周转时间等指标值。5.2.2 短进程（作业）优先调度算法优点：由于优先执行短进程（作业），故可以缩短进程（作业）的平均周转时间，提高系统的

17、吞吐量。缺点：（1）不利于长进程（作业），尤其是在系统不断地有短进程（作业）到达的情况下，会导致长进程（作业）的饥饿现象。（2）没有考虑进程（作业）的紧迫程度，不利于处理紧急任务，对于分时、实时操作处理仍然不理想。（3）需要预先知道进程（作业）所需的运行时间，由于估计的运行时间不准确，不一定能真正做到短进程（作业）优先，从而影响调度性能。5.2.3 轮转调度算法基于时钟的轮转（Round Robin，RR）调度算法用于低级调度，专为分时操作系统设计。假设系统有n 个就绪进程，RR调度算法是将CPU的处理时间划分成n个大小相等的时间片，系统将所有的就绪进程按先来先服务原则排成一个就绪队列，每次调

18、度时将就绪队列的队首进程分派到CPU上执行，并令其只能执行一个时间片；当时间片用完时，调度程序中止当前进程的执行，将它送到就绪队列的队尾，再调度下一个队首进程执行。也就是说，RR 调度算法是以时间片为单位轮流为每个就绪进程服务的，从而保证所有的就绪进程在一个确定的时间段内，都能够获得一次CPU 执行。RR 调度算法是一种抢占式调度算法。5.2.3 轮转调度算法时间片是一个很小的时间单位，通常为10100ms。时间片的长度是影响调度性能的一个重要指标。如果时间片很长，长到大多数进程在一个时间片内都能够完成，RR调度算法就退化为FCFS调度算法；如果时间片很短，短到用户的一次交互需要若干调度才能完

19、成，那么频繁地切换进程会导致切换开销增大，用户响应时间增长。因此，时间片的长度要略大于一次典型交互活动所需的时间。5.2.3 轮转调度算法在时间片q=1和q=4 的情况下，各进程的调度顺序及详细执行情况如下图所示。5.2.3 轮转调度算法在时间片q=1和q=4 的情况下，表5-5 列出了各进程周转时间、带权周转时间等指标值。5.2.3 轮转调度算法特点：RR调度算法简单易行，进程的平均响应时间短，交互性好，但不利于处理紧急任务。因此，RR 调度算法适用于分时操作系统，但不适用于实时系统。另外，RR 调度算法不利于处理I/O 操作频繁的进程，因为这些进程通常运行不完一个时间片就阻塞了，等它完成了

20、I/O 操作后，又要和其他进程一样排队。所以这类进程的周转时间会比不需要I/O 操作或I/O 操作少的进程要长得多。改进的RR 调度算法新进程到达后，首先进入就绪队列。度时，按照先来先服务原则，以时间片为单位进行调度。如果该进程的时间片用完后，仍然转入就绪队列的队尾排队。当该进程因I/O 操作而被阻塞时，会转入一个阻塞队列。当I/O 操作完成，该阻塞进程被唤醒时不是进入就绪队列而是进入一个辅助队列。在调度时，辅助队列的进程优于就绪队列的进程。改进的RR 调度算法在公平性方面优于一般的RR调度算法。5.2.4 优先级调度算法调度程序总是选择优先级最高的就绪进程，分派占用CPU。优先级相同的进程，

21、则按照先来先服务原则进行调度。SPF 调度算法就是优先级调度算法的一个特例，进程的优先级依赖于进程的长度。优先级调度算法同样适用于高级调度。5.2.4 优先级调度算法1优先级调度算法的类型非抢占式优先级调度算法在这种方式下，系统一旦把CPU 分派给优先级最高的就绪进程后，该进程便一直执行下去，直到完成；或因某事件阻塞使该进程放弃CPU 时，系统方可调度另一优先级最高的进程。非抢占式优先级调度算法主要用于批处理系统，也可用于某些对实时性要求不严的实时系统中。5.2.4 优先级调度算法1优先级调度算法的类型（续）抢占式优先级调度算法在这种方式下，系统同样将CPU分派给优先级最高的就绪进程，使之执行

22、。但在执行期间，如果出现一个优先级更高的就绪进程，该进程可以抢占CPU，使正在执行的低优先级进程中断执行。每当一个进程就绪后，系统都要按照优先级抢占原则判断是否进行抢占，导致调度开销大为增加。因为抢占式优先级调度算法能更好地满足紧急任务的要求，因而常用于比较严格的实时系统及对性能要求较高的批处理和分时系统中。5.2.4 优先级调度算法2优先级的类型静态优先级。静态优先级是在创建进程时确定的，且在进程的整个生命周期内保持不变。简单易行，但灵活性较差，容易导致低优先级进程饥饿。动态优先级。动态优先级是指在创建进程时确定的优先级，可以随进程的推进或进程等待时间的增加而改变，以便获得更好的调度性能。例

23、如，一个进程的优先级可以随等待时间的增长而提高；在抢占式系统中，正在执行的进程的优先级逐渐下降，以防止一个长进程长期占有CPU。5.2.5 最高响应比优先调度算法最高响应比优先（Highest Response-Ratio Next，HRRN）调度算法是一种非抢占式调度算法。HRRN 调度算法同时考虑每个作业的等待时间和要求服务时间，从中选出响应比最高的作业投入执行。一个进程（作业）的响应比R 定义如下：其中，Ts 为该进程（作业）要求服务时间，Tw为进程（作业）的等待时间。5.2.5 最高响应比优先调度算法若等待时间相同，则要求服务时间越短，其响应比越高，因而HRRN 调度算法有利于短进程（

24、作业）。若要求服务时间相同，则等待时间越长，其响应比越高，此时HRRN 调度算法等价于FCFS 调度算法。对于长进程（作业），响应比可以随着等待时间的增加而相应地提高，使长进程获得CPU 的可能性逐步提高，从而避免了饥饿现象。因此，HRRN 调度算法既照顾了短进程（作业），又不会使长进程（作业）的等待时间过长，有效提高了调度的公平性。HRRN 调度算法的本质是一种以响应比作为优先级的动态优先级调度算法。但是，由于每次调度前都需要计算响应比，计算开销大。5.2.5 最高响应比优先调度算法最高响应比优先（Highest Response-Ratio Next，HRRN）调度算法是一种非抢占式调度算

25、法，HRRN调度算法同时考虑每个作业的等待时间和要求服务时间，从中选出响应比最高的作业投入执行。一个进程（作业）的响应比R定义如下：其中，Ts为该进程（作业）要求服务时间，Tw为进程（作业）的等待时间。5.2.5 最高响应比优先调度算法分析：若等待时间相同，则要求服务时间越短，其响应比越高，因而HRRN调度算法有利于短进程（作业）。若要求服务时间相同，则等待时间越长，其响应比越高，此时HRRN调度算法等价于FCFS调度算法。对于长进程（作业），响应比可以随着等待时间的增加而相应地提高，使长进程获得CPU 的可能性逐步提高，从而避免了饥饿现象。因此，HRRN调度算法既照顾了短进程（作业），又不会

26、使长进程（作业）的等待时间过长，有效提高了调度的公平性。HRRN调度算法的本质是一种以响应比作为优先级的动态优先级调度算法。但是，由于每次调度前都需要计算响应比，计算开销大。5.2.5 最高响应比优先调度算法对表5-1 所示的进程流实施HRRN 调度算法。开始时刻，由于系统中只有一个进程A，因此调度它投入运行。在进程A 运行完成后，只有进程B到达，因此调度进程B 投入运行。在进程B运行完成后，进程C、D、E都已到达，此时就需要计算它们的响应比。进程C、D、E的响应比分别为：因为进程C的响应比最高，故调度进程C 运行。5.2.5 最高响应比优先调度算法在进程C运行完成后，再次计算进程D 的响应比

27、和进程E 的响应比。因为进程E的响应比最高，所以调度进程E运行。在进程E 运行完成后，只剩下进程D，接下来调度它运行。因此，进程的调度顺序为ABCED。5.2.5 最高响应比优先调度算法表5-6给出了HRRN 调度算法的算法调度性能。通过对比可以看出，HRRN 调度算法的平均带权周转时间介于FCFS 调度算法和SPF 调度算法之间。5.2.6 多级队列调度算法在没有特别说明的情况下，上述的几种调度算法通常只设置一个就绪队列，采用的进程调度算法也是单一的。如果系统需要根据进程的类型采用不同的进程调度算法，可以考虑采用多级队列调度算法。多级队列调度算法的主要思想：组建多个就绪队列，进程就绪后根据其

28、类型或性质链接到相应的就绪队列，不同的就绪队列可以设置不同的优先级，同一个就绪队列中的进程也可以设置不同的优先级。由于设置多个就绪队列，允许对每个就绪队列实施不同的调度算法，以满足不同用户进程的需求，实现调度策略的多样性。5.2.7 多级反馈队列调度算法如果没有各个进程相对长度的信息，SPF 调度算法、HRRN 调度算法等基于进程长度的调度算法都不能使用。既然无法获得要求服务时间的信息，人们就考虑利用进程的已执行时间来进行调度。多级反馈（Feedback，FB）队列调度算法就不必事先知道各进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。现在，F

29、B 调度算法被很多操作系统所采用，最典型的有Windows NT 和UNIX统。5.2.7 多级反馈队列调度算法FB 调度算法描述如下：（1）系统设置多个就绪队列，每个就绪队列具有不同的优先级，如图5-5 所示。第1级就绪队列的优先级最高，以下各级就绪队列的优先级逐次降低。优先级高的队列会优先调度执行。同一就绪队列的进程优先级相同，按照先来先服务原则排序调度。（2）为每个队列设置大小不同的时间片。为优先级最高的第1 级就绪队列中的进程设置的时间片最小，随着队列的级别增加，其进程的优先级逐级降低，但被赋予的时间片逐级增加。例如，在图5-5中，q=2 i-1，其中i 为队列编号。5.2.7 多级反

30、馈队列调度算法（3）新进程先进入第一个就绪队列，并按先来先服务原则等待调度。当调度到该进程时，该进程若能在一个时间片内完成，便可退出；若它在规定的时间片内未能完成，就转入下一级队列末尾等待调度，依此类推。在第n个队列中便采取时间片轮转的方式运行。（4）系统总是从第一个就绪队列里的进程开始调度；只有前i-1 级就绪队列都为空时，才调度第i 级就绪队列中的进程。当一个进程在运行时，更高优先级的就绪队列中来了一个进程，那么高优先级的进程可以抢占当前运行进程的CPU。被抢占的进程可以排到原就绪队列末尾，也可仍留在队首，以便下次重新获得CPU 时把原先分配到的时间片的剩余部分用完。5.2.7 多级反馈队

31、列调度算法FB 调度算法是一种抢占式、具有动态优先级机制的调度算法。它根据进程运行情况的反馈信息，能够动态地调整不同类型的进程在不同运行阶段的优先级，重新调整所处队列，因此具有自适应的能力。可以看出，FB 调度算法向短进程、I/O 操作繁忙进程和交互式进程倾斜。对于长进程，它将依次在n 个就绪队列中运行，然后按照轮转方式执行，用户也不必担心进程长期得不到处理。FB 调度算法贯彻了处理机调度策略中“要得越多，等待的时间也应越长”的原则，能较好地满足各种类型用户的需要。5.2.7 多级反馈队列调度算法当然，在FB 调度算法下，进程仍然存在饥饿的可能。因为一个长进程会很快沉底，位于优先级最低的就绪队

32、列中。不断到来的短进程如果形成稳定的进程流，长进程就会永远等待下去。一个改进的方法是：记录一个进程在某个队列中已经等待的时长。若这个时长超出了允许范围，则将该进程提升到上一级就绪队列。这样，获得CPU 的可能性也随之增加。在实际应用中，FB 调度算法还有很多的变体。例如，为了保证I/O 操作能及时完成，可以在进程发出I/O 请求后进入最高优先级队列，并执行一个时间片来响应I/O 操作。5.3 实时系统的调度 5.3.1 实时调度实现要求 5.3.2 实时调度算法 5.3.3 优先级倒置 5.3 实时系统的调度实时系统的进程或任务往往带有某种程度的紧迫性。计算机必须在一定的时间内对它们做出正确的

33、反应。例如，医院里的重病监护系统、飞行器的自动导航和核反应堆的安全控制等。实时操作系统具有以下特点：有限等待时间（决定性）；有限响应时间；用户控制；可靠性高；系统处理能力强。5.3.1 实时调度实现要求1实时任务的类型根据处理时限的要求不同，实时任务可以分为：硬实时任务：要求系统必须完全满足任务的时限要求。软实时任务：允许系统对任务的时限要求有一定的延迟，其时限要求只是一个相对条件。根据外部事件的发生频率不同，实时任务还可以分为：周期任务和非周期任务。5.3.1 实时调度实现要求当系统处理的是多种周期任务时，计算机能否及时处理所有的事件取决于事件的到达周期和需要处理的时间。假设系统有m个周期事

34、件，如果事件i 的到达周期为Pi，所需CPU的处理时间为Ci，那么只有满足 限制条件时，系统才是可以调度的。例如，系统有6个硬实时任务，它们的周期时间都是50ms，若每次的处理时间为10ms，通过计算不能满足限制条件，因而系统是不可调度的。5.3.1 实时调度实现要求2实时调度的实现要求具有快速的切换机制对中断的快速响应能力、快速的任务分派能力。采用基于优先级的抢占式调度策略基于优先级的固定点抢占式调度算法、基于优先级的随时抢占式调度算法系统处理能力强5.3.2 实时调度算法实时任务都有截止时间的要求：开始截止时间、完成截止时间。1保证开始截止时间的实时调度算法最早截止时间优先（Earlies

35、t Deadline First，EDF）调度算法是广泛使用的一种保证开始截止时间的实时调度算法。EDF调度算法根据任务的开始截止时间来确定任务的优先级。任务的开始截止时间越早，其优先级越高。具有最早开始截止时间的任务排在就绪队列队首，被优先调度执行。5.3.2 实时调度算法EDF调度算法既可以用于非抢占式系统，也可以用于抢占式系统。其最优性体现在：若一组任务可以被调度（指所有任务的截止时间在理论上能够得到满足），则EDF 调度算法可以满足时限要求；若一组任务不能全部满足，则EDF调度算法也是能够满足的任务数最多的调度算法。5.3.2 实时调度算法下面以抢占式系统周期实时任务为例说明EDF调度

36、算法的调度过程。假定系统有两个周期任务，任务A 和任务B 的周期分别为200ms 和500ms，每个周期的处理时间分别为100ms 和250ms。任务A 和任务B 在0时刻同时到达系统，如图5-6 所示。图中的第一行标识了两个任务每个周期的到达时间、任务长度和开始截止时间。任务A 每个周期的开始止时间为200ms、400ms、600ms、，任务B 每个周期的开始截止时间为500ms、1000ms、1500ms、。5.3.2 实时调度算法图中的第二行和第三行说明了优先级抢占式调度不能满足实时任务的需求。第四行说明EDF调度算法满足了该实时系统所有任务的时限要求。5.3.2 实时调度算法2保证完成

37、截止时间的实时调度算法最低松弛度优先（Least Laxity First，LLF）调度算法是一种保证完成截止时间的实时调度算法。LLF调度算法根据任务紧急或松弛程度确定任务的优先级。任务的松弛度可定义为：任务的松弛度=完成截止时间还需运行的时间当前时间任务的松弛度越低（即紧急程度越高），其优先级越高，越优先调度执行。5.3.2 实时调度算法例如，某实时系统任务A 和任务B同时到达。任务A 的完成截止时间和所需的运行时间分别为400ms和250ms，则该任务的松弛度为150ms；任务B 的完成截止时间和所需的运行时间分别为300ms 和100ms，则该任务的松弛度为200ms；LLF 调度算法

38、会优先调度任务A 执行。实现上，该系统的就绪队列按照优先级自高到低排列，即松弛度最低的任务排在就绪队列的队首，调度程序总是选择就绪队列中的队首任务执行。随着时间的推移，当某一就绪进程的松弛度减为0 时，为保证实时任务的完成，它必须抢占CPU。故LLF 调度算法属于抢占式调度算法。5.3.2 实时调度算法图5-7 是LLF 调度算法用于周期实时任务调度。系统有两个周期任务，任务A 和任务B 的周期分别为20 ms 和50 ms，每个周期的处理时间分别为10 ms 和25 ms。任务A 每个周期的完成截止时间为20ms、40ms、60ms、；任务B 每个周期的完成时间为50ms、100ms、150

39、ms、。5.3.2 实时调度算法5.3.3 优先级倒置优先级倒置是发生在基于优先级的抢占式调度策略下的一种现象。1优先级倒置的形成优先级倒置是指系统出现了高优先级的进程被低优先级的进程延迟或阻塞，对实时任务的及时完成造成很大破坏的现象。系统有进程A、进程B和进程C，优先级依次从低到高。进程A 和进程C 共享同一个临界资源R，P(mutex)是实现临界资源R 互斥访问的信号量。在t3时刻，高优先级的进程C被低优先级的进程A 阻塞，出现了优先级倒置的现象。5.3.3 优先级倒置2优先级倒置的解决方案两种解决方法：规定进程进入临界区后，不允许被更高优先级的进程抢占CPU，从而可以让该进程尽快执行完临

40、界区，避免阻塞竞争同一临界资源的更高优先级的进程。采用动态优先级继承策略。规定某进程进入临界区后，若存在竞争同一临界资源的更高优先级的进程也要进入临界区，则阻塞更高优先级的进程，并把更高优先级转移到正占有临界资源的进程作为其优先级。5.3.3 优先级倒置例如在图5-8中，在t3时刻，进程C因执行P(mutex)获得不了临界资源而阻塞，此时进程A正占有该临界资源，则进程A继承进程C 的优先级。这样在t3时刻，因为进程A 的优先级高于进程B 的优先级，系统调度进程A 执行，从而可以促使进程A尽快执行完临界区。如图5-9所示，进程A执行完临界区，会唤醒进程C，同时进程C和进程A的优先级恢复原来的初始

41、设置，维护了进程本来的紧要程度。小结处理机调度是操作系统中的核心问题，它根据某种调度算法选择合适的进程，并把CPU分配给该进程使用。处理机调度分为三级。高级调度用于确定何时允许一个新进程进入系统。中级调度与进程挂起和进程交换有关，用于确定何时把一个程序的部分或全部在内存与外存之间进行交换。低级调度用于确定哪一个就绪进程被CPU执行。调度算法体现了调度策略。不同的系统适用于不同的环境，它们选择的调度算法也不同。因而，无法找到统一的性能评价准则来判断调度算法的好坏。常用的性能评价准则有CPU利用率、系统吞吐率、周转时间、等待时间和响应时间等。一般来说，调度算法的复杂度不宜过高。常用的调度算法有FCFS调度算法、SPF调度算法、SJF调度算法、RR调度算法、HRRN调度算法、FB调度算法、EDF调度算法、LLF调度算法等。