操作系统第三章.

《操作系统第三章.》由会员分享，可在线阅读，更多相关《操作系统第三章.（118页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁 第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.1.1 高级、中级和低级调度 3.1.2 调度队列模型 3.1.3 选择调度方式和调度算法的若干原则 第三章 处理机调度与死锁 高级调度： 又称为作业调度或长程调度。 用于决定把后备队列中的哪些作业调入内存，为它 们创建进程、分配必要的资源，再将新创建的进程排 在就绪队列上，准备执行。 在批处理系统中，大多

2、配有作业调度，但在分时和 实时系统中，却往往不配置作业调度。作业调度的运 行频率较低，通常为几分钟一次。 3.1.1 高级、中级和低级调度调度的类型 第三章 处理机调度与死锁 执行作业调度时，需要解决： （1）一次接纳多少作业：即允许多少个作业同时在 内存中运行。 （2）接纳哪些作业：即哪些作业调入内存，取决于 所采用的算法。 比如先来先服务调度算法；或者是短作业优 先调度算法；还有基于作业优先权的调度算法，响 应比高者优先调度算法等。 第三章 处理机调度与死锁 2. 低级调度： 又称为进程调度、短程调度。 用于决定就绪队列中的哪个进程能获得处理器, 并将处理机分配给该进程。 进程调度程序是操

3、作系统最为核心的部分，进程 调度策略的优劣直接影响到整个系统的性能。 三种类型的操作系统中，都必须配置此级调度。 第三章 处理机调度与死锁 有两类低级调度方式： (1) 非抢占方式 一旦把处理机分配给某个进程后，让该进程一直 执行，直到该进程完成或者发生某事件而阻塞。 引起进程调度的因素： 正在执行的进程执行完毕； 执行中的进程因为提出I/O请求而暂停执行； 进程通信或同步过程中执行了原语操作。 第三章 处理机调度与死锁 (2) 抢占方式 当一进程正在处理机上执行时，系统可根据某种 原则暂停它的执行，并将已分配给它的处理机重新 分配给另一个进程。 抢占的原则有： 优先权原则：优先权原则：就绪的

4、高优先权进程有权抢占低优 先权进程的 CPU。 短作业优先原则：短作业优先原则：就绪的短作业(进程)有权抢占 长作业(进程)的 CPU。 时间片原则：时间片原则：一个时间片用完后，系统重新进行 进程调度。 第三章 处理机调度与死锁 3. 中级调度 又称平衡负载调度、中程调度。 目的是为了提高内存利用率和系统吞吐量。 实质是进程的内外存对换功能：将外存中已具 备运行条件的进程换入内存，而将内存中处于阻 塞状态的某些进程换出至外存。 在三种调度中，进程调度的运行频率最高， 作业调度的周期较长，中级调度的运行频率在上 述两者之间。 第三章 处理机调度与死锁 3.1.2 调度队列模型 根据os中所引入

5、的调度的类型，形成了三种类 型的调度队列模型： 仅有进程调度的调度队列模型； 具有高级和低级调度的调度队列模型； 同时具有三级调度的调度队列模型。 第三章 处理机调度与死锁 1. 仅具有进程调度的调度队列模型 就 绪 队 列 阻 塞 队 列 进程调度 CPU 进程完成 等待事件 交互用户 事 件 出 现 时间片完 第三章 处理机调度与死锁 2. 具有高级和低级调度的调度队列模型 就 绪 队 列 进程调度 CPU 进程完成 等待事件 1 作业 调度 事件1出现 时间片完 等待事件 2 事件2出现 等待事件 n 事件n出现 后 备 队列 第三章 处理机调度与死锁 3. 同时具有三级调度的调度队列模

6、型 就绪队列 进程调度 CPU 就绪，挂起队列 中级调度 阻塞，挂起队列 阻塞队列 等待事件 进程完成 时间片完作业调度 交互型作业 后备队列 批量作业 挂起 事件出现 事 件 出 现 第三章 处理机调度与死锁 3.1.3 选择调度方式和调度算法的若干原则 面向用户的准则 (1) 周转时间短 作业周转时间：作业提交计算机到作业完成为止的时 间间隔。它是作业在系统里的等待时间与运行时间之和 。 平均作业周转时间： 带权周转时间： W=T /Ts 注意：带权周转时间总大于注意：带权周转时间总大于 1 1 。 平均作业带权周转时间： 主要用于评价批处理系统。 T :作业的周转时 间， Ts :作业的

7、运 行时间。 第三章 处理机调度与死锁 (2) 响应时间快 从用户通过键盘提交一个请求到系统首次产生 响应之间的时间间隔称响应时间。 主要用于评价分时系统。 (3) 截止时间的保证 任务必须开始执行的最迟时间或必须完成的最 迟时间称截止时间。 主要用于评价实时系统。 (4) 优先权准则 在三种OS中，都可遵循。 第三章 处理机调度与死锁 2. 面向系统的准则 (1)系统吞吐量高 (2) 吞吐量:单位时间内系统所完成的作业数。 (3)(2) 处理机利用率好 CPU总的运行时间=CPU有效工作时间 +CPU空闲等待时间 CPU利用率=CPU有效工作时间 /CPU总的运行时间 (3) 各类资源的平衡

8、利用 第三章 处理机调度与死锁 3.2 调度算法 3.2.1 先来先服务和短作业优先调度算法 3.2.2 高优先权优先调度算法 3.2.3 基于时间片轮转调度算法 第三章 处理机调度与死锁 调度算法 : 根据系统的资源分配策略所规定的资源分配算 法称为调度算法。 通常将作业或进程归入各种就绪或阻塞队列。 有的算法适用于作业调度，有的算法适用于进程 调度，有的两者都适应。 第三章 处理机调度与死锁 3.2.1 先来先服务和短作业优先调度算法 最简单的调度算法。 用于作业调度时：用于作业调度时：按照作业进入系统的先后次序 来挑选作业，先进入系统的作业优先被挑选。 用于进程调度时：用于进程调度时：按

9、照进程就绪的先后次序来调 度进程。 算法容易实现，效率不高，只顾及作业等候时间 ，没考虑作业要求服务时间的长短，不利于短作业 而优待了长作业。 1. 先来先服务调度算法（FCFS） 第三章 处理机调度与死锁 例：在单道环境下，某批处理显然有四道作业，已 知他们的进入系统的时刻、估计运算时间如下： 作业进入时刻(h)运行时间(h) A B C D 0 1 2 3 1 100 1 100 用FCFS算法计算作业的运行情况、平均周转时间和 平均带权周转时间： 第三章 处理机调度与死锁 作业进入时刻运行时间开始时刻完成时刻 周转时间带权周转 时间 A B C D 0 1 2 3 1 100 1 100

10、 0 1 101 102 1 101 102 202 1 100 100 199 1 1 100 1.99 平均周转时间T100（h） 平均带权周转时间T26.00（h） 第三章 处理机调度与死锁 2. 短作业(进程)优先调度算法（SJF/ SPF） 用于作业调度时：用于作业调度时： SJF调度算法。以进入系统的作 业所要求的CPU时间为标准，总选取估计计算时间最 短的作业投入运行。 用于进程调度时：用于进程调度时： SPF调度算法。从就绪队列中选 出估计运行时间最短的进程，将处理机分配给它。 算法易于实现，能有效降低作业的平均等待时间。 缺点是：对长作业不利，有可能导致长作业（进程） 长期不

11、被调度；未能依据作业的紧迫程度来划分执行 的优先级；难以准确估计作业（进程）的执行时间， 从而影响调度性能。 第三章 处理机调度与死锁 13524 运行步骤 例 ： 第三章 处理机调度与死锁 3.2.2 高优先权优先调度算法 用于作业调度时：用于作业调度时：系统将从后备队列中选择若 干个优先权最高的作业装入内存。 用于进程调度时：用于进程调度时：该算法把处理机分配给就绪 队列中优先权最高的进程。 非抢占式优先权算法 抢占式优先权调度算法 第三章 处理机调度与死锁 优先权的类型： 静态优先权 在创建进程时确定的，且在进程的整个运行期间保 持不变。 静态优先权法简单易行，但随着进程的推进，其优 先

12、权可能与进程的情况不再相符。 动态优先权 在创建进程时所确定的优先权，可以随着进程的推 进而改变。 例如：可以规定就绪进程的优先权随着等待时间的 增长以速度 a 增加；正在执行进程的优先权以速度 b 下降，这样便可防止一个长作业长期垄断处理机。 第三章 处理机调度与死锁 3. 高响应比优先调度算法（HRRF） ： 实际上是一种动态优先权调度算法。 FCFS与SJF/SPF是片面的调度算法。FCFS只 考虑作业等候时间而忽视了作业的计算时间， SJF /SPF只考虑用户估计的作业计算时间而忽视 了作业等待时间。 HRRF是介乎这两者之间的折衷算法，既考虑 作业等待时间，又考虑作业的运行时间，既照

13、顾 短作业又不使长作业的等待时间过长，改进了调 度性能。但每次调度前，都要进行响应比的计算 ，会增加系统开销。 第三章 处理机调度与死锁 要求服务时间 要求服务时间等待时间 优先权 + = 优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作 业的响应时间，故该优先权又相当于响应比RP。 据此，又可表示为： 要求服务时间 响应时间 要求服务时间 要求服务时间等待时间 RP = + = 第三章 处理机调度与死锁 如果等待时间相同，短作业容易得到较高优先权 。 长作业等待时间足够长后，也将获得足够高的优 先级。 如果要求服务时间相同时，作业的优先权决定于 其等待时间，实现的是先来

14、先服务。 第三章 处理机调度与死锁 例如：以下四个作业先后到达系统进入调度： 作业名 到达时间 所需CPU时间 作业1 0 20 作业2 5 15 作业3 10 5 作业4 15 10 第三章 处理机调度与死锁 FCFSFCFS调度算法：调度算法： 平均作业周转时间 T = (20+30+30+35)/4 = 28.75 平均带权作业周转时间 W = (20/20+30/15+30/5+35/10)/4 = 3.13 SJF SJF调度算法：调度算法： 调度顺序为作业1、3、4、2， 平均作业周转时间 T=(20+15+20+45)/4 =25 平均带权作业周转时间 W = (20/20+15

15、/5+25/10+45/15)/4 = 2.25 第三章 处理机调度与死锁 高响应比调度算法：高响应比调度算法： 1) 开始只有作业1，被选中执行时间20； 作业1执行完毕，响应比依次为1+15/15、1+10/5 、1+5/10，作业3被选中，执行时间5； 作业3执行完毕，响应比依次为1+20/15、1+10/10 ，作业2被选中，执行时间15； 作业2执行完毕，作业4被选中，执行时间10； 平均作业周转时间T = (20+15+35+35)/4 = 26.25 平均带权作业周转时间W = (20/20+15/5+35/15+35/10)/4 = 2.42 第三章 处理机调度与死锁 3.2.

16、3 基于时间片轮转调度算法 把CPU划分成若干时间片,并且按顺序赋给就绪队 列中的每一个进程，进程轮流占有CPU，当时间片 用完时，即使进程未执行完毕，系统也剥夺该进程 的CPU，将该进程排在就绪队列末尾。同时系统选 择另一个进程运行。 时间片长度的选取非常重要，时间片长度的选择 会直接影响系统开销和响应时间。 1. 时间片轮转法（RR） 第三章 处理机调度与死锁 2. 多级反馈队列调度算法（FB ） 将就绪队列分为N级，每个就绪队列分配给不同的 时间片，队列级别越高，时间片越长，级别越小，时 间片越短； 新进程进入内存后，放入第一队列末尾，按FCFS原 则等待调度，如果在一个时间片结束时没完成，将该 进程转入第二队列末尾重新等待调度执行如此下 去，当一个长作业