操作系统习题3.ppt

《操作系统习题3.ppt》由会员分享，可在线阅读，更多相关《操作系统习题3.ppt（76页珍藏版）》请在优知文库上搜索。

1、操作系统原理操作系统原理 第三章第三章 处理机调度与死锁处理机调度与死锁v 计算机科学与技术学院内 容 产生死锁的原因和必要条件产生死锁的原因和必要条件 多处理机系统中的调度多处理机系统中的调度 实时调度实时调度 调度算法调度算法处理机调度的基本概念处理机调度的基本概念 预防死锁的方法预防死锁的方法 死锁的检测与解锁死锁的检测与解锁处理机调度的基本概念处理机调度的基本概念v高级、中级和低级调度高级、中级和低级调度 高级调度高级调度(High Scheduling) 又称为作业调度或长程调度，用于决定把外存上处又称为作业调度或长程调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创

2、建于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。有时也称接纳调度。在就绪队列上，准备执行。有时也称接纳调度。 需需 要要 性性批处理系统批处理系统分时系统分时系统实时系统实时系统 分时与实时系统中，由分时与实时系统中，由键盘输入的命令或数据，键盘输入的命令或数据，直接送入内存，以做到及直接送入内存，以做到及时响应。时响应。处理机调度的基本概念处理机调度的基本概念v高级、中级和低级调度高级、中级和低级调度 高级调度高级调度 在每次执行作业调度时，都须做出在每次执行作业调度时，都须做出 以

3、下两个决定。以下两个决定。 1) 接纳多少个作业接纳多少个作业 2) 接纳哪些作业接纳哪些作业 低级调度低级调度(Low Level Scheduling) 低级调度通常又称为进程调度、短程调度，用来决定就绪队列低级调度通常又称为进程调度、短程调度，用来决定就绪队列中的哪个进程应获得处理机，然后由分派程序执行把处理机分中的哪个进程应获得处理机，然后由分派程序执行把处理机分配给该进程的具体操作。配给该进程的具体操作。 进程调度可采取下述两种方法进程调度可采取下述两种方法 非抢占方式非抢占方式 抢占方式抢占方式处理机调度的基本概念处理机调度的基本概念v高级、中级和低级调度高级、中级和低级调度 低级

4、调度低级调度 非抢占方式非抢占方式 主动交出处理机主动交出处理机 实现简单，系统开销小，适用于大多批处理系统实现简单，系统开销小，适用于大多批处理系统. 难以解决紧急任务的要求难以解决紧急任务的要求 抢占方式抢占方式 根据某种原则，新进程抢占当前进程处理机根据某种原则，新进程抢占当前进程处理机 原则：原则： 优先权；优先权； 短作业优先；短作业优先； 时间片原则（分时系统）时间片原则（分时系统）处理机调度的基本概念处理机调度的基本概念v高级、中级和低级调度高级、中级和低级调度 中级调度中级调度(High Scheduling) 对换功能对换功能 目的：提高资源利用率、目的：提高资源利用率、系统

5、吞吐量系统吞吐量 三种调度频率及时间三种调度频率及时间进程调度进程调度 最高最高 10100ms 中级调度中级调度 居中居中 居中居中作业调度作业调度 最低最低 几分钟几分钟名称名称 频率频率 周期周期 处理机调度的基本概念处理机调度的基本概念v调度队列模型调度队列模型 仅有进程调度的调度队列模型仅有进程调度的调度队列模型就 绪 队 列阻 塞 队 列进程调度CPU进程完成等待事件交互用户事件出现时间片完就绪队列为就绪队列为FIFO分时系统分时系统处理机调度的基本概念处理机调度的基本概念v调度队列模型调度队列模型 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型就 绪队列进程调度

6、CPU进程完成等待事件 1作业调度事件1出现时间片完等待事件 2事件2出现等待事件 n事件n出现后备 队列就绪队列为优先权队列就绪队列为优先权队列批处理系统批处理系统处理机调度的基本概念处理机调度的基本概念v调度队列模型调度队列模型 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 就绪分为内存就绪和外存就绪（挂起）就绪分为内存就绪和外存就绪（挂起） 阻塞分为内存阻塞和外存阻塞（挂起）阻塞分为内存阻塞和外存阻塞（挂起） 通过内外存对换转换为挂起状态通过内外存对换转换为挂起状态v选择调度方式和算法的准则选择调度方式和算法的准则 面向用户面向用户（批）周转时间短（批）周转时间短 定义定

7、义（分）响应时间快（分）响应时间快 定义定义（实）截止时间保证（实）截止时间保证 定义定义优先权准则（三种都可遵循）优先权准则（三种都可遵循）处理机调度的基本概念处理机调度的基本概念v选择调度方式和算法的准则选择调度方式和算法的准则面向系统面向系统系统吞吐量高系统吞吐量高处理机处理效率好处理机处理效率好各类资源的平衡利用各类资源的平衡利用内 容 产生死锁的原因和必要条件产生死锁的原因和必要条件 多处理机系统中的调度多处理机系统中的调度 实时调度实时调度 调度算法调度算法处理机调度的基本概念处理机调度的基本概念 预防死锁的方法预防死锁的方法 死锁的检测与解锁死锁的检测与解锁调度算法调度算法v先来

8、先服务先来先服务(FCFS) 既可用于作业调度，也可用于进程调度既可用于作业调度，也可用于进程调度 算法描述算法描述 有利于长作业（进程），不利有利于长作业（进程），不利 于短作业（进程）于短作业（进程）进程名进程名到达时到达时间间服务时服务时间间开始执开始执行时间行时间完成时完成时间间周转时周转时间间带权周带权周转时间转时间A01B1100C 21D 3 10011011110011001991.9910220210001101102其中短作业其中短作业C C的带权周转时间竞高达的带权周转时间竞高达100100，这是，这是不能容忍的；而长作业不能容忍的；而长作业D D的带权周转时间仅为的带权

9、周转时间仅为1.991.99。据此可知：据此可知：FCFSFCFS调度算法有利于调度算法有利于CPUCPU繁忙型的作业，繁忙型的作业，而不利于而不利于I/OI/O繁忙型的作业进程。繁忙型的作业进程。 采用采用FCFS调度算法时的调度性能调度算法时的调度性能 进程名进程名 A B C D E平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 4 3 5 2 4FCFS完成时间完成时间 4 7 12 14 18周转时间周转时间 4 6 10 11 149带权周转时间带权周转时间 1 2 2 5.5 3.52.8调度算法调度算法v短作业（进程）优先短作业（进程）优先(SJF) 既可用于作业

10、调度，也可用于进程调度既可用于作业调度，也可用于进程调度 算法描述算法描述 有效降低作业平均等待时间，提高系统吞吐有效降低作业平均等待时间，提高系统吞吐量。量。调度算法调度算法.例题：例题： 1# 1#4#4#任务几乎同时到达的，并先后就任务几乎同时到达的，并先后就绪，估计运行时间分别为绪，估计运行时间分别为2 2、8 8、4 4、6 6秒，分秒，分析调度过程和性能析调度过程和性能调度算法调度算法采用采用SJ（P）F算法后，不论是平均周转时间还是平均带权算法后，不论是平均周转时间还是平均带权周转时间都有较明显的改善，尤其是对短作业周转时间都有较明显的改善，尤其是对短作业D，其周转时其周转时间由

11、间由FCFS算法的算法的11降为降为SJF算法中的算法中的3；而平均带权周转；而平均带权周转时间是从时间是从5.5降到降到1.5。 进程名 A B C D E 平 均到达时间 0 1 2 3 4服务时间 4 3 5 2 4FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间4 4 17 6 212 10 214115.518143.5441 9 82.6718163.2 6 31.5 13 92.25 92.8 82.1v SJ（P）F调度算法也存在不容忽视的缺点调度算法也存在不容忽视的缺点 （1）该算法对长作业非常不利。）该算法对长作业非常不利。 （2）该算法完全未考虑作业

12、的紧迫程度）该算法完全未考虑作业的紧迫程度 （3）不一定能真正做到短作业优先调度。）不一定能真正做到短作业优先调度。调度算法调度算法v高优先权优先调度算法高优先权优先调度算法 既可用于作业调度，既可用于作业调度， 也可用于进程调度也可用于进程调度 优先权调度算法类型优先权调度算法类型 非抢占式优先权算法非抢占式优先权算法主动交出主动交出CPUCPU，用于批处理系统用于批处理系统 抢占式优先权算法抢占式优先权算法被动交出被动交出CPUCPU，实时性更好实时性更好调度算法调度算法v高优先权优先调度算法高优先权优先调度算法 优先权类型优先权类型 静态优先权静态优先权进程的整个运行期间保持不变进程的整

13、个运行期间保持不变特点：简单，特点：简单， 但低优先权作业可能长期不被调度。但低优先权作业可能长期不被调度。 动态优先权动态优先权 如：优先权随执行时间而下降，如：优先权随执行时间而下降， 随等待时间而升高。随等待时间而升高。 调度算法调度算法调度算法调度算法v优先数优先数调度算法（不可剥夺）例题调度算法（不可剥夺）例题有有5个批处理作业（个批处理作业（A、B、C、D、E）几乎同时到达，几乎同时到达，估计运行时间分别为估计运行时间分别为2、8、6、10、4分钟，分钟，它们的优先数分别为它们的优先数分别为1、4、3、 5、 2 （1为最低优先数）。为最低优先数）。求平均周转时间求平均周转时间 调

14、度算法调度算法v 高响应比优先算法高响应比优先算法 响应比响应比Rp= 特点特点 1）短作业）短作业Rp大。大。 2）ts（要求服务时间）相同的进程间相当于要求服务时间）相同的进程间相当于FCFS。 3）长作业等待一段时间仍能得到服务。长作业等待一段时间仍能得到服务。 长短兼顾，又考虑到了先后次序，不饥饿长短兼顾，又考虑到了先后次序，不饥饿 缺点：需计算缺点：需计算Rp要求服务时间响应时间要求服务时间要求服务时间等待时间优先权调度算法调度算法例题：例题：高响应比优先高响应比优先调度算法（非抢占）调度算法（非抢占）在一个批处理单道系统中，采用在一个批处理单道系统中，采用响应比高者优先响应比高者优

15、先的作业调度的作业调度算法。一个作业进入系统后就可以开始调度，假定作业都是算法。一个作业进入系统后就可以开始调度，假定作业都是仅计算，忽略调度花费的时间。仅计算，忽略调度花费的时间。现有现有三个作业三个作业，进入系统的时间和需要计算的时间进入系统的时间和需要计算的时间如下表：如下表： 作业进入系统时间 需要计算时间开始时间完成时间周转时间19:0060分钟分钟29:1045分钟分钟39:1525分钟分钟9:0010:0060分分10:2511:10120分分10:0010:2560分分v基于时间片的轮转调度算法基于时间片的轮转调度算法 时间片轮转法时间片轮转法 时钟中断时钟中断 时间片大小的确

16、定时间片大小的确定 太大：退化为太大：退化为FCFS； 太小：系统开销过大太小：系统开销过大 多级反馈队列调度多级反馈队列调度调度算法调度算法就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3S1S2S3队列队列1 1优先级最高优先级最高v基于时间片的轮转调度算法基于时间片的轮转调度算法 多级反馈队列调度多级反馈队列调度 特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间 （1）短作业一次完成；）短作业一次完成； （2）中型作业周转时间不长；）中型作业周转时间不长； （3）大型作业不会长期不处理。）大型作业不会长期不处理。调度算法调度算法 有有5个批处理作业（个批处理作业（A、B、C、D、E）几乎同几乎同时到达，估计的运行时间分别为时到达，估计的运行时间分别为2、4、6、8、10分钟，它们的优先数分别为分钟，它们的优先数分别为1、2、3、4、5（1为为最低优先数）。对下面的每种调度算法，分别计最低优先数）。对下面的每种调度算法，分别计算作业