第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度

Presentation on theme: "第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18 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 淮海工学院计算机科学系

19 （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 淮海工学院计算机科学系

20 （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 淮海工学院计算机科学系

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

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

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

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

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

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

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

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

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

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

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