第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 淮海工学院计算机科学系

批处理系统才有作业的概念，分时系统没有作业的概念； 作业的状态分为：提交、后备、运行和完成 3.1 处理机调度的基本概念 作业的状态及其转换 批处理系统才有作业的概念，分时系统没有作业的概念； 作业的状态分为：提交、后备、运行和完成 淮海工学院计算机科学系

提交状态：作业在输入设备上并准备进入外存输入井前的状态。用户作业通常包括：程序、数据和作业说明书 后备状态：由SPOOLing输入程序输入到外存输入井中，为其建立作业控制块（JCB），并将JCB插入到后备作业队列中的状态 运行状态：作业被作业调度程序选中，由外存输入井调入到内存，为其分配了所需的资源并建立了进程，此时作业就进入到运行状态。 完成状态：当作业正常结束或异常终止时，就进入完成状态。由作业调度程序做收尾工作：撤销JCB、回收分给该作业的系统资源等。 淮海工学院计算机科学系

作业调度程序 SPOOLing 内存 运行 程序 进程调度 程序 提交 后备 就绪 阻塞 完成 输入设 外存输 备 入井 中级调度 就绪 作业的状态及其转换 作业调度程序 SPOOLing 内存 运行 程序 进程调度 程序 提交 后备 就绪 阻塞 完成 输入设 外存输 备 入井 中级调度 就绪 阻塞 外存 淮海工学院计算机科学系

3.1.1 处理机调度的层次 在多道批处理系统中，一个作业可能需要经历三级调度： 1. 高级调度（High Scheduling) 高级调度又称为作业调度或宏观调度或长程调度（多道批处理系统需要作业调度；分时系统和实时系统一般不需要高级调度。 ） 2. 中级调度(Intermediate-Level Scheduling) 引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。 3.低级调度(Low Level Scheduling) 低级调度又称进程调度或微观调度或短程调度 淮海工学院计算机科学系

引起调度的原因：1）当前进程运行结束或发生某事件而终止；2）当前进程因提出I/O请求而阻塞；3）进程之间通信或同步而由于执行原语而等待。 4、进程调度方式 非抢占方式（Nonpreemptive）：在这种调度方式下，一旦一个进程被选中运行，它就一直运行下去，直到它运行结束并自愿放弃CPU，或者因等待某一事件而被阻塞或终止时为止，才把CPU出让给其他进程，即得到CPU的进程不管运行多长时间，都一直运行下去，不会因为当前进程以外的原因而被迫让出CPU。 引起调度的原因：1）当前进程运行结束或发生某事件而终止；2）当前进程因提出I/O请求而阻塞；3）进程之间通信或同步而由于执行原语而等待。 淮海工学院计算机科学系

抢占方式（Preemptive）：抢占方式允许调度程序根据某种策略中止当前进程的执行，将其移入就绪队列，并将处理机分派给另一个进程使之投入运行。 抢占原则：1）优先权原则：允许高优先权进程抢占低优先权的CPU；2）短作业原则：允许短进程抢占长进程的处理机；3）时间片原则：分时系统中的当前进程，若时间片规定的时间用完，不管是否运行结束，都要立即中止放到就绪队列中，再将CPU分派给其它进程。 淮海工学院计算机科学系

3.1.2 调度队列模型 不同OS对高级、中级和低级调度的选取形成了不同的调度队列模型，共有3种类型。 1.仅有进程调度的调度队列模型 2. 具有高级和低级调度的调度队列模型 3. 同时具有三级调度的调度队列模型 淮海工学院计算机科学系

具有三级调度时的调度队列模型 作业 CPU 就绪挂起队列 阻塞挂起队列 阻塞队列 就绪队列 时间片到 作业调度 调入 中级调度 事件出现 进程调度 作业调度 调入 中级调度 事件出现 交互式用户 等待事件 进程完成 挂起调出 具有三级调度时的调度队列模型 淮海工学院计算机科学系

3.1.3 选择调度方式和调度算法的若干准则 1. 面向用户的准则 周转时间短：周转时间是指作业从提交给系统开始，到作业完成为止所消耗的时间。常用于衡量系统性能、作业调度算法的优劣的重要指标。 可把平均周转时间描述为： 作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为: 淮海工学院计算机科学系

响应时间快：分时系统性能的主要评价指标。响应时间指用户从键盘键入一个命令开始，到系统首次给出响应信息为止这段时间。 截止时间的保证：评价实时系统性能的重要指标。截止时间是指系统为处理某事件/任务必须开始执行的最迟时间，或必须完成的最迟时间。 优先权准则：批处理、分时和实时系统中的调度算法都应该遵循的原则。这种调度思想就是“急事急办”，优先权高者为急。 淮海工学院计算机科学系

处理机利用率好：CPU的利用率是衡量大中型系统性能的重要指标。 2. 面向系统的准则 系统吞吐量高：评价批处理系统整体性能的重要指标。吞吐量是指单位时间内系统所完成的作业数。作业调度算法对系统吞吐量有直接影响，选择确定时应考虑这一准则。 处理机利用率好：CPU的利用率是衡量大中型系统性能的重要指标。 各类资源的平衡利用：选择适当调度算法，保证各种资源的利用都处于忙碌状态。 淮海工学院计算机科学系

3.2 调度算法 1、先来先服务（FCFS）调度算法 适应范围：适应作业调度和进程调度； 3.2 调度算法 1、先来先服务（FCFS）调度算法 适应范围：适应作业调度和进程调度； 调度过程：FCFS用于作业（进程）调度时，从后备（就绪）队列中选择若干或一个先到来的作业（进程）投入运行。进程在分派到CPU进入运行过程中，只有当进程运行结束或因某事件发生而被阻塞才放弃CPU。 算法特点：算法容易实现，但效率不高；只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业(CPU繁忙型作业)；作业调度不分轻重缓急，人人平等；FCFS为非抢占式调度。 淮海工学院计算机科学系

表注：周转时间=完成时间-到达时间；带权周转时间=周转时间/服务时间 先来先服务（FCFS）调度算法效率举例 表注：周转时间=完成时间-到达时间；带权周转时间=周转时间/服务时间 这两个时间都是越小越好！ 淮海工学院计算机科学系

2、短作业/进程（SJF/SPF）优先调度算法 适应范围：适应作业调度和进程调度。SJF/SPF算法以进入系统的作业/进程所要求的CPU时间为标准，总选取估计计算时间最短的作业/进程投入运行。 算法特点：算法易于实现，效率不高；忽视长作业等待时间，会出现饥饿现象；不考虑紧迫作业/进程的需求；长短时间人为估计，不可靠，会出现以长乱短。 SPF算法类型：抢占或非抢占式。抢占式SPF调度算法在新进程进入就绪队列时，将其运行时间与当前进程的剩余运行时间相比，若更短时，可抢占CPU；非抢占式SPF算法允许当前运行进程先执行直到释放CPU为止。可抢占SPF调度有时称为最短剩余时间优先（shortest-remaining-time-first）调度。 淮海工学院计算机科学系

FCFS和SJF调度算法的性能分析 淮海工学院计算机科学系

例题：假如5个就绪进程其到达系统和所需CPU时间如下表所示（单位：毫秒），如果忽略I/O以及其他开销，分别计算采用FCFS、非抢占式SPF和抢占式SPF调度算法进行CPU调度的平均周转时间和平均带权周转时间。 进程到达和运行时间 进程 到达时间 运行时间 A 3 B 2 6 C 4 D 5 E 8 淮海工学院计算机科学系

T=((3-0)+(9-2)+(13-4)+(18-6)+(20-8))/5=8.6 带权平均周转时间为：W=2.56 解答如下： （1）采用FCFS的调度顺序为： A B C D E 3 9 13 18 20 平均周转时间为： T=((3-0)+(9-2)+(13-4)+(18-6)+(20-8))/5=8.6 带权平均周转时间为：W=2.56 淮海工学院计算机科学系

（2）采用非抢占SJF的调度顺序为： 平均周转时间为：T=7.6 带权平均周转时间为：W=1.84 A B E C D 3 9 11 15 3 9 11 15 20 平均周转时间为：T=7.6 带权平均周转时间为：W=1.84 淮海工学院计算机科学系

（3）采用抢占SJF的调度顺序为： 平均周转时间为：T=7.2 带权平均周转时间为：W=1.59 A B1 E C B2 3 8 10 15 3 8 10 15 20 D 4 平均周转时间为：T=7.2 带权平均周转时间为：W=1.59 淮海工学院计算机科学系

3、高优先权优先调度算法（priority-scheduling algorithm） 1）优先权调度算法的类型 非抢占式优先权算法：系统一旦把CPU分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成或因发生某事件使该进程放弃处理机时。主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。 抢占式优先权算法：系统把处理机分配给优先权最高的进程使之执行。只要又有更高优先权新进程进入就绪队列，进程调度程序就立即停止当前进程的执行，将处理机重新分配。适应较严格的实时系统、性能要求较高的批处理和分时系统。 淮海工学院计算机科学系

静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。 2）优先权的类型 静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。 优先权的确定准则：系统进程者优先；资源需求少者优先；用户需求紧迫者优先。 动态优先权：动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进而改变的，以便获得更好的调度性能。（如等待时间与优先权成正比） 淮海工学院计算机科学系

4、高响应比优先调度算法 动态优先权的变化规律可描述为： 系统对作业的响应时间=等待时间+服务时间，故该优先权又相当于响应比RP。据此，优先权变化规律又可表示为： 淮海工学院计算机科学系

如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业； 高响应比优先调度算法特点： 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业； 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务； 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机，避免了长作业饥饿现象。 淮海工学院计算机科学系

5、基于时间片的轮转调度算法 时间片调度算法适用于分时系统。划分为时间片轮转和多级反馈队列调度算法 1）时间片轮转法（Round Robin） 轮转法调度做法是：系统将所有的就绪进程按FIFO原则排队，每次调度时，把CPU分配给队首进程，并令其执行一个时间片（如20ms）。当执行的时间片用完时，停止该进程的执行，并将它送往就绪队尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。如此反复和轮转，就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。 淮海工学院计算机科学系

多级反馈队列调度算法是目前公认的一种性能比较优良的调度算法，兼备了前述各种算法的优点。原理如下： 2）多级反馈队列调度算法 多级反馈队列调度算法是目前公认的一种性能比较优良的调度算法，兼备了前述各种算法的优点。原理如下： 设置多个就绪队列，并赋予不同的优先级和时间片：第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。图 3-5 是多级反馈队列算法的示意。 淮海工学院计算机科学系

新进程进入 （64ms） 多级反馈队列调度算法 淮海工学院计算机科学系

调度原则：当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。 淮海工学院计算机科学系

抢占原则：仅当第一队列空闲时，调度程序才调度第二队列中的进程运行； 仅当第1~i 队列均空时，才会调度第i+1队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。 淮海工学院计算机科学系

多级反馈队列调度算法的性能与特点 终端型作业用户：短小作业及时完成，用户满意。 (2) 短批处理作业用户：短作业优先运行结束。 (3) 长批处理作业用户：不出现饥饿现象。 淮海工学院计算机科学系

作业3-1 P101：1、4、6、7 淮海工学院计算机科学系