李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第 8 讲 处理机调度与死锁(2) 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 1/

教学目标 教学内容 掌握高优先权优先调度算法； 掌握时间片轮转调度算法； 理解实时调度； 高优先权优先调度算法； 时间片轮转调度算法； 计算机科学与技术系 信息与教育技术中心 2/

复习 调度的层次 调度队列模型 选择调度方式和调度算法的若干准则 面向用户的准则 面向系统的准则 常用的调度算法 3/

调 度 算 法 高优先权优先调度算法 优先权调度算法的类型 非抢占式优先权算法 抢占式优先权调度算法 4/

调 度 算 法 优先权的类型 静态优先权 确定进程优先权的依据有如下三个方面： 进程类型 进程对资源的需求 用户要求 动态优先权 5/

调 度 算 法 高响应比优先调度算法 优先权的变化规律可描述为： 调 度 算 法 高响应比优先调度算法 优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 6/

调 度 算 法 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。 调 度 算 法 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。 7/

例： 使用非抢占优先权调度算法求出以下进程的开始执行时间，完成时间，周转时间以及带权周转时间。 进程名 到达时间 服务时间 优先权 A 3 2  0  3  1 B 1 4  8  12  11 11/4  C 5  6  6/5 D  13  10 8/

例： 使用抢占优先权调度算法求出以下进程的开始执行时间，完成时间，周转时间以及带权周转时间。 进程名 到达时间 服务时间 优先权 A 3 2  0(2),7(1)  8  8/3 B 1 4  12  11  11/4 C 5  2  7  5  1 D  13  10 9/

调 度 算 法 基于时间片的轮转调度算法 时间片轮转法 基本原理 时间片大小的确定 10/

例： 当时间片q=1和q=3时，分别使用时间片轮转算法求出以下进程的开始执行时间，完成时间，周转时间以及带权周转时间。（这里以q=1为例） 进程名 到达时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间 A 3 7 7/3 B 1 4 11 10 10/4 C 2 5 13 11/5 D 6 3/1 11/

执行次数与序列 最外边的A表示正在执行 次数 序列 1 A 2 AB 3 BCA 4 ADBC 5 CADB 6 BCAD 7 8 BC 9 CB 10 11 12 C 13 最外边的A表示正在执行

调 度 算 法 多级反馈队列调度算法 应设置多个就绪队列，并为各个队列赋予不同的优先级。 13/

图 3-5 多级反馈队列调度算法 14/

调 度 算 法 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。 调 度 算 法 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行； 仅当第1~(i-1) 队列均空时，才会调度第i队列中的进程运行。 15/

调 度 算 法 多级反馈队列调度算法的性能 终端型作业用户。 大多属于交互型作业，作业较小，若在第一个队列所规定的时间片内完成，便可使其满意。 短批处理作业用户。 长批处理作业用户。 16/

实 时 调 度 实现实时调度的基本条件 提供必要的信息，如就绪时间，开始截止时间和完成截止时间，处理时间，资源要求，优先级。 系统的处理能力 采用抢占式调度机制 具有快速切换机制，如对外部中断的快速响应能力，快速的任务分派能力 17/

实 时 调 度 实时调度算法的分类 非抢占式调度算法 抢占式调度算法 非抢占式轮转调度算法 非抢占式优先调度算法 基于时钟中断的抢占式优先权调度算法 立即抢占式的优先权调度算法 18/

实 时 调 度 图 3-8 实时进程调度 19/

实 时 调 度 最早截止时间优先即EDF(Earliest Deadline First)算法 非抢占式调度方式用于非周期实时任务 20/

实 时 调 度 抢占式调度方式用于周期实时任务 21/

实 时 调 度 22/

实 时 调 度 图 3-10 最早截止时间优先算法用于抢占调度方式之例 23/

实 时 调 度 最低松弛度优先即LLF(Least Laxity First)算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高， 以使之优先执行。 例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms。又如，另一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。 24/

实 时 调 度 在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。 假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。 25/

实 时 调 度 图 3-11 A和B任务每次必须完成的时间 26/

实 时 调 度 在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出：  A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms 27/

类似地，可算出B1的松弛度为15ms，故调度程序应选择B1运行。在t3=30 ms时，A2的松弛度已减为0(即40-10-30)，而B1的松弛度为15 ms(即50-5-30)，于是调度程序应抢占B1的处理机而调度A2运行。在t4=40 ms时，A3的松弛度为10 ms(即60-10-40)，而B1的松弛度仅为5 ms(即50-5-40)，故又应重新调度B1执行。在t5=45 ms时，B1执行完成，而此时A3的松弛度已减为5 ms(即60-10-45)，而B2的松弛度为30 ms(即100-25-45)，于是又应调度A3执行。在t6=55ms时，任务A尚未进入第4周期，而任务B已进入第2周期，故再调度B2执行。在t7=70 ms时，A4的松弛度已减至0 ms(即80-10-70)，而B2的松弛度为20 ms(即100-10-70)，故此时调度又应抢占B2的处理机而调度A4执行。 28/

实 时 调 度 图 3-12 利用LLF算法进行调度的情况 29/

小结 高优先权优先调度算法 基于时间片的轮转调度算法 实时调度算法 30/

作业 P118 16-17 31/