第4 章 处理机调度

1、第第4 4 章章 处理机调度处理机调度 廖俊 晓庄学院 第四章 处理机调度与死锁 n4.1 处理机调度的层次 n4.2 调度队列模型和调度准则 n4.3 调度算法 n4.4 实时调度 4.1 4.1 处理机调度的层次处理机调度的层次 n在多道程序系统中，一个作业从提交到执行，通常都要经 历多级调度 如高级调度、低级调度、中级调度以及IO调度等 n系统的运行性能在很大程度上取决于调度 如吞吐量的大小、周转时间的长短、响应的及时性等 n调度是多道系统的关键 n CPU资源管理多道程序设计面临的挑战 批处理系统：如何安排内存中多个作业的运行顺序？ 交互式系统：如何更好应对不同的交互式请求？ 实时系统

2、：如何保证实时服务的高质量？ n 进程调度有效的管理CPU资源 When：何时进行进程调度？ How：遵循何种规则完成调度？ What：调度过程中需要完成哪些工作？ n 进程调度的级别 高级调度：也称宏观调度，决定哪些程序可以进入系统 中级调度：也称内存调度，决定内存中程序的位置和状态 低级调度：也称微观调度，决定CPU资源在就绪进程间的分配 4.1.1 高级调度 l 又称作业调度或长程调度，其主要功能是按照某种原则从磁盘 某些盘区的作业队列中选取作业进入主存，并为作业做好运行前的 准备工作和作业完成后的善后工作。 l 其调度对象是作业 作业作业 n作业（JOB）是用户在一次算题过程中或一次事

3、务处理中，要求计算 机系统所做的工作的集合 n作业是比进程更广泛的概念，不仅包含了通常的程序和数据，而且还 配有一份作业说明书，系统根据作业说明书对程序运行进行控制。在 批处理系统中，以作业为单位从外存调入内存 n用户为了让计算机完成某个特定任务，首先编写成源程序，然后提交 给计算机通过编译或汇编、连接、装配、运行等步骤，最终由计算机 送出用户所需要的运行结果。从计算机管理的角度看，上述一系列的一系列的 由计算机执行的任务的集合就是作业由计算机执行的任务的集合就是作业。 中国民航大学计算机科学与 技术学院 $END $RUN Data for program $LOAD Fortran pro

4、gram $FORTRAN $JOB, 10,429754 Cherry Chen 作业步作业步 编辑 编译或 汇编 连接装入运行 n计算机完成作业是通过执行一系列有序的工作步骤进行的，每个步骤完 成作业的一部分特定工作 n把计算机系统完成一个作业所需的一系列有序的相对独立的工作步骤称 为作业步 n作业的各个作业步虽然功能相对独立，但它们之间相互关联，往往是一 个作业步的执行需要使用上一个作业步的执行结果。 n若干个作业进入系统后，被依次存放在外存上，形 成输入的作业流；在操作系统控制下，逐个作业进 行处理，形成处理的作业流 作业流作业流 作业控制块作业控制块 u 作业提交给系统进入后备状态后

5、，系统将为每个作业建立一个作业控制 块JCB。 u JCB在作业的整个运行过程中始终存在，并且其内容与作业的状态同步 地动态变化。只有当作业完成并退出系统时，JCB才被撤消。可以说，JCB 是一个作业在系统中存在的惟一标志，系统根据JCB才感知到作业的存在 u 作业控制块JCB中包含了对作业进行管理的必要信息，JCB中的信息一 部分是从用户提供的作业控制卡或作业说明书中得到，另一部分是记录作 业运行过程中的动态信息 u JCB的具体内容因系统不同而异 作业名作业名 资源要求预估的运行时间 最迟完成时间 要求的内存量 要求外设类型、台数 要求的文件量和输出量 资源使用情况进入系统时间 开始运行时

6、间 已运行时间 内存地址 外设台号 类型级别控制方式 作业类型 优先级 状态 用户账户 作 业 控 制 块 4.1.1 高级调度高级调度 根据JCB，审 查系统能否 满足用户作 业的资源需 求 按一定算法算法， 从外存后备 队列中选取 某些作业调 入内存 为它们创建 进程、分配 必要资源 将新创建的 进程插入就 绪队列，准 备执行 作业调度功能作业调度功能 4.1.1 高级调度高级调度 u用户希望：自己作业的周转时间尽可能少 u系统希望：作业的平均周转时间尽可能少 u作业调度： 1）决定接纳多少个作业 2）决定接纳哪些作业 u先来先服务（FCFS）、 短作业优先（SF）、 优先级高优先（HPF

7、） 、 响应比高者优先（RPF） 作业调度算法作业调度算法 4.1.1 高级调度高级调度 u主要用于批处理系统。其设计目标是最大限度地发挥各种资源的利用 率和保持系统内各种活动的充分并行 一个例子：对资源需求不同的作业进行合理搭配 科学计算往往需要占用大量的CPU时间，属于CPUCPU繁忙型作业繁忙型作业，对于I/O设备 的使用少；而数据处理则相反，它们要求占用较少的CPU时间，但要求大量 I/O时间，属于I/OI/O繁忙型作业繁忙型作业；有些递归计算，产生大量中间结果，需要 很多内存单元存放它们，这属于内存繁忙型作业内存繁忙型作业。如果能把它们搭配在一 起，程序A在使用处理机，程序B在利用通

8、道l，而程序C恰好利用通道2等， 这样一来，A、B和C从来不在同一时间使用同一资源，每个程序就好像单独 在一个机器上运行 l 又称进程调度或短程调度，其主要功能是按照某种原则 将处理机分配给就绪进程将处理机分配给就绪进程。执行低级调度功能的程序称为 进程调度程序进程调度程序，由它实现处理机在进程间的转换。它必须 常驻主存，是操作系统内核内核的主要部分 l 实际上，进程调度程序主要是完成一台物理的CPU转变 成多台虚拟(或逻辑)的CPU的工作 l 在多道批处理、分时和实时系统中都必须配备 4.1.2 低级调度低级调度 进程调度程序的主要功能 n保存现场。当前运行的进程调用进程调度程序时，即表示该

9、进程要求 放弃CPU(因时间片用完或等待I/O等原因)。这时，进程调度程序把它 的现场信息，如程序计数器及通用寄存器的内容等保留在该进程PCB 的现场信息区中 n挑选进程。根据一定的调度算法调度算法(如优先级算法)，从就绪队列中选出 一个进程来，并把它的状态改为运行态，准备把CPU分配给它 n恢复现场把处理器分配给进程。为选中的进程恢复现场信息，并把 CPU的控制权交给该进程,它接着上次间断的地方继续运行 进程调度中的三个基本机制 n排队器。将就绪进程按一定方式排成队列 n分派器（分派程序）。把进程调度程序选定的进程，从就绪 队列中取出，进行上下文切换，把处理器分配给它 n上下文切换机制。保存

10、当前进程上下文，装入分派程序上下 文，分派程序运行；移出分派程序，装入新选进程上下文 进程调度方式 1 1非抢占方式非抢占方式(Non-Preemptive Mode)(Non-Preemptive Mode) u 一旦处理机分配，便让进程一直执行，直至该进程完成或发生某事件而被 阻塞时，才再把处理机分配给其它进程 u 优点：实现简单、系统开销小，适用于大多数的批处理系统环境 u 缺点：难于满足需要立即执行的紧急任务，在要求比较严格的实时系统中 不宜采用 u 在采用非抢占调度方式时，可能引起进程调度的因素： u 正在执行的进程执行完毕，或因发生某事件而不能再继续执行 u 执行中的进程因提出I/

11、O请求而暂停执行 u 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、 Block原语、Wakeup原语等 2 2抢占方式抢占方式(Preemptive Mode)(Preemptive Mode) u 允许调度程序停止正在执行的进程，将已分配给该进程的处理机， 重新分配重新分配给另一进程 u 抢占的原则有 u 时间片原则 u 优先权原则 u 短作业(进程)优先原则 u 优点：可防止长进程长时间占有处理机，为多数进程提供公平服务 u 缺点：系统开销较大 进程调度方式 u 中级调度又称中程调度(Medium-Term Scheduling) u 引入中级调度的主要目的，是为了

12、提高内存利用率和系统吞吐量 u 使那些暂时不能运行的进程不再占用宝贵的内存资源，将它们调至外 存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态 u 当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来 决定把外存上的那些又具备运行条件的就绪进程，重新调入内存，并修 改其状态为就绪状态，挂在就绪队列上等待进程调度 u 对换(存储器管理) u 短期调整系统负荷，平顺系统操作 4.1.3 中级调度中级调度 调度类型调度类型运行频率运行频率运行时间运行时间算法复杂性算法复杂性 进程调度进程调度高高短短低低 中程调度中程调度中等中等较短较短中等中等 作业调度作业调度低低长长高高 三级调度

13、比较三级调度比较 三级调度的相互比较三级调度的相互比较 高级调度中级调度低级调度 外存到内存 内外存互换 内存中 批处理 实时 分时 运行频率高 运行频率适中 运行频率低 第四章 处理机调度 n4.1 处理机调度的层次 n4.2 调度队列模型和调度准则 n4.3 调度算法 n4.4 实时调度 n高级调度、中级调度、低级调度，都将涉及到作业或进 程队列，共有三种类型的调度队列模型。 4.2 4.2 调度队列模型和调度准则调度队列模型和调度准则 4.2.1 4.2.1 调度队列模型调度队列模型 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 就 绪队 列 阻 塞队列 进程调度 CPU 进程完

14、成 等待事件 交互用户 事 件 出 现 时间片完 分时系统通常仅设置进程调度。每个进程执行都可能出现三种情况： (1)任务在该时间片内已完成，释放CPU进入完成状态； (2)任务在本次时间片内尚未完成，OS便将该任务放在就绪队列的后面； (3)执行期间，进程因某事件而被阻塞，放人阻塞队列。 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 就绪队列 阻塞队列 CPU 时间片完 进程调度 完成 等待事件 1 事件 1 出现 阻塞队列 等待事件 2 阻塞队列 等待事件 n 事件 2 出现 事件 n 出现 后备队列 进程调度 作业调度 实例：批处理操作系统 (1) 引入了作业调度：从

15、外存的后备队列中选择选择一批作业调入内存，为之 创建进程后送入就绪队列。最常用的是优先权队列。 (2) 设置多个阻塞队列，每个对应一种阻塞原因。 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 n在OS中引人中级调度后， 就绪状态分为：内存就绪和外存就绪两种状态； 阻塞状态分成：内存阻塞和外存阻塞两种状态。 内存紧张换出时，内存就绪转变为外存就绪、内存阻 塞转变为外存阻塞；在中级调度的作用下，又可使外 存就绪转为内存就绪。 就绪队列 CPU 时间片完 后备队列 进程调度 完成 中级调度 事 件 出 现 阻塞队列 等待事件 事件出现 挂起 就绪队列 就绪，挂起队列 阻塞，挂起队列

16、挂起 作业调度 交互作业 批量作业 4.2.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 n取决于操作系统的类型和目标 n不同的操作系统，有不同的调度方式和算法 n有面向用户的准则，也有面向系统的准则 面向用户的准则面向用户的准则 n周转时间周转时间短（批处理系统） n响应时间快（分时系统） n截止时间的保证（实时系统） 截止时间，是指某任务必须开始执行的最迟时间，或必须完 成的最迟时间。 n优先权准则（批处理、分时、实时） 让某些紧急的作业得到及时的处理。在要求较严格的场合可 采用抢占调度方式。 u周转时间，是指从作业提交给系统开始，到作业完成为 止的这段时间间隔(称

17、为作业周转时间)，它包括： (1)作业在外存后备队列上等待(作业)调度的时间； (2)进程在就绪队列上等待进程调度的时间； (3)进程在CPU上执行的时间； (4)等待IO操作完成的时间。 平均周转时间平均周转时间短会有效地提高资源利用率，且可使大多数用户感到满意。短会有效地提高资源利用率，且可使大多数用户感到满意。 平均周转时间可描述为：平均周转时间可描述为： n i i T n T 1 1 若系统为作业提供的实际服务时间为若系统为作业提供的实际服务时间为TsTs，W=TW=TTsTs称为带权周转时间，称为带权周转时间， 平均带权周转时间平均带权周转时间可表示为：可表示为： n i si i

18、 T T n W 1 1 u 响应时间是从用户通过键盘提交一个请求开始，直至系统首次 产生响应为止的时间，或者说直到在屏幕上显示为止的一段时 间间隔。它包括： (1)从键盘输入的请求信息传送到处理机的时间； (2)处理机对请求信息进行处理的时间； (3)将所形成的响应回送到终端显示器的时间 面向系统的准则面向系统的准则 1系统吞吐量高（批处理） 吞吐量是指在单位时间内所完成的作业数。 2处理机利用率好 大、中型多用户系统，CPU昂贵， 处理机的利用率成为衡量系统性能的重要指标 3各类资源的平衡利用 第四章 处理机调度 n4.1 处理机调度的层次 n4.2 调度队列模型和调度准则 n4.3 调度

19、算法 n4.4 实时调度 4.3 调度算法 n在OS中，调度的实质是资源分配。 n调度算法是指：根据系统的资源分配策略所规定的资源分配算法。 n不同的系统和系统目标，采用不同的调度算法。 先来先服务调度算法 短作业优先调度算法 高优先权优先调度算法 基于时间片的轮转调度算法 4.3.1 先来先服务调度算法先来先服务调度算法 n最简单的调度算法。 n既可用于作业调度作业调度，也可用于进程调度进程调度。 n每次调度都是选择一个或多个最先进入队列的作业或进程，为它们分配 资源，创建进程或分配CPU，使之投入运行。 先来先服务调度算法(FCFS)的特点 l作业调度和进程调度均可，最简单简单，本质上属非

20、剥夺方式 l有利于长作业/进程，不利于短作业 l有利于CPU繁忙型的作业(如通常的科学计算)，而不利于I O繁忙的作业/进程（如大多数的事务处理) 例例 4.3.2 短作业短作业(进程进程)优先调度算法优先调度算法 n短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度 的算法。分别用于作业调度和进程调度作业调度和进程调度 n短作业作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估 计运行时间最短的作业，将它们调入内存运行 n短进程进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间 最短的进程，将处理机分配给它，使它立即执行并一直执行到完成， 或发生某事

21、件而被阻塞放弃处理机时，再重新调度 例例 图 4-4 FCFS和SJF调度算法的性能 nSJ(P)F调度算法有利于短作业，与FCFS算法相比，大大降低短作业 的周转时间，平均周转时间短，系统吞吐量高 nSJ(P)F调度算法对长作业不利。甚至可能导致长作业(进程)长期不 被调度，发生“饥饿”现象 n该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进 程)会被及时处理 n此外，由于作业(进程)的长短只是根据用户所提供的估计执行时间 而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间， 致使该算法不一定能真正做到短作业优先调度 短作业短作业( (进程进程) )优先调度优先调度的特点的

22、特点 4.3.3 高优先权优先调度算法高优先权优先调度算法 n既可用于作业调度作业调度，也可用于进程调度进程调度。 n为照顾紧迫性作业，使之进入系统后获得优先处理，引入最高优先 权优先调度算法。 n按照进程的优先级大小来调度，使高优先级进程得到优先的处理的 高度策略称为优先权调度算法。 n在许多采用优先级调度的系统中，通常采用动态优先数策略。进程 的优先级不是固定的，往往随许多因素的变化而变化。尤其随作业 （进程）的等待时间、已使用的处理机时间或其它资源的使用情况 而定。 优先级调度方法又可分为： 非抢占的优先级调度法：即一旦某个高优先级的进程占有了处理 机，就一直运行下去，直到由于其自身的原

23、因而主动让出处理机 时(任务完成或等待事件)才让另一高优先级进程运行。主要用于 批处理系统批处理系统中；也可用于某些对实时性要求不严的实时系统实时性要求不严的实时系统中。 可抢占的优先级调度法：任何时刻都严格按照高优先级进程在处 理机上运行的原则进行进程的调度。常用于要求比较严格的实时要求比较严格的实时 系统系统中， 以及对性能要求较高的批处理和分时系统对性能要求较高的批处理和分时系统中。 1、优先权调度算法的类型、优先权调度算法的类型 思考：I/O繁忙型的进程，大部分时间是在等待I/O操作完成 对于这一类进程，当它们要求CPU运行时，应立即给予满足，以便让它们开 始下一个I/O操作和其它计算

24、型的进程并行工作。否则，这些I/O繁忙型的进 程将长时间占据存储器，降低系统并行度。 解决方案：一个行之有效的算法是在进程每次获取CPU运行后，重新指 定该进程的优先级为 1/f。这里的f表示进程上次在CPU上实际运行时间实际运行时间 与时间片之比与时间片之比。例如，若时间片为100毫秒，进程上次在CPU上的实际运 行时间为2毫秒，则它的优先级为50；若它上次实际运行时间为50毫秒， 则它的优级为2。由于I/O繁忙型的进程每次在CPU上运行的时间很短， 依此算法，它们的优先级将较高，从而优先得到服务。 实际中，优先权算法常和轮转法结合使用，也就 是按优先级将进程分组，组间组间采用优先级调度算法

25、， 而组内组内优先级相同的进程则按轮转法调度。显然，若 优先级不动态地进行调整，则优先级低的就绪进程就 可能饿死。 2. 优先权的类型优先权的类型 1) 静态优先权。静态优先权是在创建进程时确定的， 且在进程的整个运行期间保持不变 确定进程优先权的依据有如下三个方面：确定进程优先权的依据有如下三个方面： (1)(1) 进程类型进程类型 (2) (2) 进程对资源的需求进程对资源的需求 (3) (3) 用户要求用户要求 2) 动态优先权。在创建进程时所赋予的优先权，是可以随进程的推 进或随其等待时间的增加而改变的，以便获得更好的调度性能 例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长

26、，其优先权 以速率a提高 a) 若所有的进程都具有相同的优先权初值相同的优先权初值，则显然是最先进入就绪队列的进 程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法 b) 若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低 的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获 得处理机 c) 当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下 降，则可防止一个长作业长期地垄断处理机 3. 高响应比优先调度算法高响应比优先调度算法 n短作业优先算法的不足之处是长作业的运行得不到保证 n为每个作业引入动态优先权，使长作业在等待一段时间后，有机

27、会分配到处理机 要求服务时间 要求服务时间等待时间 优先权 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该 优先权又相当于响应比RP。据此，又可表示为： 要求服务时间 响应时间 要求服务时间 要求服务时间等待时间 优先权 (1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈 高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等 待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其 等待时间足够长时，其优先级便可升到很高， 从而也可获得处 理机。 调度之前，计算响

28、应比，增加系统开销！ 要求服务时间 响应时间 要求服务时间 要求服务时间等待时间 优先权 l 分时系统普遍采用 l 早期,简单的时间片轮转 l 20世纪90年代以后,广泛采用多级反馈队列调度算法 4.3.4 基于时间片的轮转调度算法基于时间片的轮转调度算法 l本质：属于剥夺方式,分时系统中无例外采用(为确保响应时间) l方法：每个进程依次按时间片q轮流执行，q的大小从几ms到几 百ms。时间片用完则计时器触发一中断，重新调度，在一给定 的时间内，就绪进程均能获得一时间片的执行时间 时间片大小是关键问题时间片大小是关键问题 1.时间片q正比于响应时间，反比于就绪进程数目。 2.计算机的处理能力。

29、速度快，q可小些。通常q值是这样决定的： 分时系统：q=T/Nmax T-响应时间上限 Nmax-最大进程数 1 基于基于时间片的轮转调度算法时间片的轮转调度算法 练习题练习题 有下述五个进程，按照时间片轮转法进行调度。每个进程的到达时 间和服务时间如下表所示。时间片长度为1个单位，请描述各个时 间片的执行情况，并计算每个进程的结束时间、周转时间和带权周 转时间。 时间片长度为1个单位 时间片长度为4个单位 2. 2. 多级反馈队列调度算法多级反馈队列调度算法 n不必不必事先知道各进程所需执行时间，可满足各种进程需要，是目前被 公认较好的调度算法。 n设置多个就绪队列，每个队列赋予不同的优先级

30、。队列按FCFS原则排列 n各队列时间片不同时间片不同 n当一个新进程进入内存后，首先放在第一队列尾，按FCFS原则调度；如果该 时间片内未结束，转入第二队队列尾转入第二队队列尾；直到最后的第N队列，在第N队列采取 按时间片轮转方式调度 n仅当第当第I I队列空闲时队列空闲时，才调度第i+1队列 n如有新进程进入优先级较高的队列，则剥夺CPU执行新进程，旧进程放入原队 列尾 例如，若一个进程总共需运行例如，若一个进程总共需运行100100个时间片个时间片 l 初始时指定它在优先级最高的进程组中，很快就会在CPU上运行 一个时间片，之后优先级也降低一个级别 l 当它第二次有机会在CPU上运行时，

31、它将运行2t l 以后它将在CPU上运行的时间长度依次是4，8，16，32和64个t， 最后一次运行时，只须64个t中的37个 t 就可完成 l 总共需总共需调度调度7 7次。次。比较单纯的轮转法，节省了93次切换时间 练习题练习题 有下述五个进程，按照多级反馈调度算法进行调度。每个进程 的到达时间和服务时间如下表所示。分别描述当时间片长度P=1和 P= 时，各个时间片的执行情况，并计算每个进程的结束时间、 周转时间和带权周转时间。 3. 3. 多级反馈队列调度算法的性能多级反馈队列调度算法的性能 u终端型作业终端型作业用户用户 u在第一队列中完成，作业短，交互型； u短短批处理作业批处理作业

32、用户用户 u周期时间较短，通常三个队列即可完成； u长长批处理作业批处理作业用户用户 u依次在前n个队列中执行，然后再按轮转方式运行。 第四章 处理机调度与死锁 4.1 处理机调度的层次 4.2 调度队列模型和调度准则 4.3 调度算法 4.4 实时调度 4.4 4.4 实时调度实时调度 n实时进程或任务，用来反应或控制某个外部事件，带有某 种程度的紧迫性，对调度提出了特殊要求特殊要求 n实时调度必须满足实时任务对截止时间的要求 4.4.1 4.4.1 实现实时调度的基本条件实现实时调度的基本条件 1. 1. 提供必要的信息（向调度程序提供）提供必要的信息（向调度程序提供） (1) 就绪时间

33、(2) 开始截止时间和完成截止时间 (3) 处理时间 (4) 资源要求 (5) 优先级 2. 2. 系统处理能力强系统处理能力强 l 实时系统中通常都有着多个实时任务 l 若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务 不能得到及时处理， 从而导致发生难以预料的后果 l 假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期 时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件： m i i i P C 1 1 4.4.1 4.4.1 实现实时调度的基本条件实现实时调度的基本条件 3. 3. 采用抢占式调度机制采用抢占式调度机制 l 当一个优先权更高的任

34、务到达时，允许将当前任务暂时挂起，而 令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时 间的要求。这种调度机制比较复杂 l 对于一些小的实时系统，如果能预知预知任务的开始截止时间，则对 实时任务的调度可采用非抢占调度机制，简化简化调度程序和对任务调度 时所花费的系统开销。 但在设计这种调度机制时，应使所有的实时任务都比较小，并在 执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便 释放出处理机，供调度程序去调度那种开始截止时间即将到达的 任务 4.4.1 4.4.1 实现实时调度的基本条件实现实时调度的基本条件 4. 4. 具有快速切换机制具有快速切换机制 该机制应具有如下两

35、方面的能力： (1) 对外部中断的快速响应能力。为使在紧迫的外部事件请求中 断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止 中断的时间间隔尽量短，以免耽误时机(其它紧迫任务) (2) 快速的任务分派能力。在完成任务调度后，便应进行任务切 换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运 行功能单位适当的小，以减少任务切换的时间开销 4.4.1 4.4.1 实现实时调度的基本条件实现实时调度的基本条件 4.4.2 4.4.2 实时调度算法的分类实时调度算法的分类 实时任务性质的不同 硬实时调度算法 软实时调度算法 调度方式的不同 非抢占调度算法 抢占调度算法 调度时间的

36、不同 静态调度算法 动态调度算法 多处理机环境 集中式调度算法 分布式调度算法 1. 1. 非抢占式调度算法非抢占式调度算法 (1) 非抢占式轮转轮转调度算法 常用于工业生产群控系统，可获得数秒至数十秒的响应时间常用于工业生产群控系统，可获得数秒至数十秒的响应时间 (2) 非抢占式优先优先调度算法。 可获得数秒至数百毫秒的响应时间可获得数秒至数百毫秒的响应时间 2. 2. 抢占式调度算法抢占式调度算法 (1) 基于时钟中断的抢占式优先权抢占式优先权调度算法。 较好的响应效果，调度延迟降为几十毫秒至几毫秒较好的响应效果，调度延迟降为几十毫秒至几毫秒 (2) 立即抢占立即抢占(Immediate

37、Preemption)的优先权调度算法。 非常快的响应，调度延迟降为几毫秒至非常快的响应，调度延迟降为几毫秒至100100微秒微秒 4.4.3 4.4.3 常用的几种实时调度算法常用的几种实时调度算法 1. 1. 最早截止时间优先级最早截止时间优先级EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法 u 根据任务的开始截止时间开始截止时间确定任务的优先级 u 截止时间越早，优先级越高 u 实时任务就绪队列按开始截止时间排序 u 可用于抢占式调度，也可用于非抢占式调度 1 1）非抢占式调度方式用于非周期实时任务）非抢占式调度方

38、式用于非周期实时任务 图图 EDF EDF算法用于非抢占调度方式算法用于非抢占调度方式 2 2）抢占式调度方式用于）抢占式调度方式用于周期实时周期实时任务任务 B2B1 0102030405060708090100时间t/ms A1A2A3A4A5 A1 最后期限 A2 最后期限 A3 最后期限 A4 最后期限 B1 最后期限 B2 最后期限 A5 最后期限 到达时间 执行时间 最后期限 B2 B1B2 B1A1A2A3A4B2A5 固定优先级固定优先级调 度（A优先级高） B1错过 B1 B2B1 2 2）抢占式调度方式用于周期实时任务）抢占式调度方式用于周期实时任务 01020304050

39、60708090100时间t/ms A1A2A3A4A5 A1 最后期限 A2 最后期限 A3 最后期限 A4 最后期限 B1 最后期限 B2 最后期限 A5 最后期限 到达时间 执行时间 最后期限 A1错过 A2A3A5 固定优先级固定优先级调 度（B优先级高） B2 A4错过 B2 B1 B1 B2 B2B1 2 2）抢占式调度方式用于周期实时任务）抢占式调度方式用于周期实时任务 0102030405060708090100时间t/ms A1A2A3A4A5 A1 最后期限 A2 最后期限 A3 最后期限 A4 最后期限 B1 最后期限 B2 最后期限 A5 最后期限 到达时间 执行时间

40、最后期限 A2A3 最早截止时间 优先 A1A4A5 2. 2. 最低松弛度优先级最低松弛度优先级LLF(Least Laxity First)LLF(Least Laxity First)算法算法 u 根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程 度愈高，为该任务所赋予的优先级就愈高 松弛程度=必须完成时间-运行时间 例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有 100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度 (松弛程度)为100 ms u 要求系统有一个按松弛度排序的实时任务就绪队列，松弛度最低的任 务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行 u 主要用于可抢占调度方式可抢占调度方式中 图图 A和和B任务每次必须完成的时间任务每次必须完成的时间 A1A2A3A4A5A6A7A8 20406080100120140160 B