操作系统课件第3章.

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

1、第三章 处理机调度与死锁 v为提高处理机利用率、改善系统性能（吞吐量、响 应时间）需对处理机进行合理分配调度 v处理机调度的目的：分配处理机 3.1 处理机调度的层次 高级、中级和低级调度 调度分三级 1. 高级调度 也称为作业调度 作业：用户在一次执行过程中或一个事务处理中 要求计算机系统所做工作的集合 作业调度：将外存上后备队列的作业调入内存、 创建进程并分配资源、插入就绪队列 接纳多少个作业 接纳哪些作业 分时系统、实时系统中不需要作业调度，作业直 接送入内存 2. 低级调度称为进程 调度 选择就绪队列中某个进程获得处理机 调度方式 1) 非抢占方式：不允许其它进程抢占已经分配出去 的处

2、理机。实时系统中，不宜采用这种调度方式。 2)抢占方式：允许调度程序将已分配出去的处理机 重新分配给另一进程。 3. 中级调度 主要目的：提高内存利用率和系统吞吐量。 实现方式：对换 暂时不能运行的进程调至外存上的挂起队列去等待。 当进程重新具备运行条件时，中级调度将挂起队列中 某个进程重新调入内存，挂在就绪队列上等待进程调 度。 3.2 调度队列模型和调度准则 调度队列模型 1. 仅有进程调度的调度队列模型 这种调度适合 于哪种系统？ 2. 具有高级和低级调度的调度队列模型 这种调度适合于 哪种系统？ 3. 同时具有三级调度的调度队列模型 高 低 中 调度准则 1. 面向用户的准则 (1)

3、周转时间短。 周转时间T：从作业被提交给系统，到作业完成为止的时间间隔 。 (1) 由4个部分组成：在后备队列等待的时间、进程在就绪队列 中等待的时间、在 CPU中执行的时间、I/O操作完成的时间 。 平均周转时间： 平均带权周转时间： 带权周转时间： W=T/TS（ TS系统服务时间即CPU执行时间） (2) 响应时间快。（评价分时系统，输入、处理、返回） (3) 截止时间的保证。（评价实时系统） (4) 优先权准则。 2. 面向系统的准则 (1)系统吞吐量高 q吞吐量是指单位时间内完成的作业数 (2)处理机利用率好 (3)各类资源的平衡利用 -各类资源处于忙碌状态 3.3 调 度 算 法

4、调度算法 ：资源分配方法。 不同的系统，通常采用不同的调度算法。 1. 先来先服务调度算法（既可用于作业调度又可用于进程调度） 2. 短作业(进程)优先调度算法 3. 高优先权优先调度算法(FPF) v 静态优先权：创建进程时确定且在进程的整个运行期间保持不 变。优先权是利用某一范围内的一个整数来表示。 v 动态优先权：可以改变。 高响应比优先调度算法 v 优先权=(等待时间+要求服务时间)/要求服务时间 响应比 Rp=响应时间/要求服务时间 例：在一个批处理单道系统中，采用响应比高者优先的 作业调度算法。现有3个作业，进入系统的时间和需要 计算的时间如下表所示： （1）求出每个作业的开始时间

5、、完成时间及周转时间并 填入表中。 （2）计算三个作业的平均周转时间为多少？ （1）平均周转时间：（60+120+70）分钟/3=83.33分钟 （2）带权平均周转时间：？ 分别采用FCFS、SJF、FPF求出每个作业的开始时间、 完成时间、周转时间、带权周转时间并填入表中。 计算系统的平均周转时间和平均带权周转时间。 先来先服务调度算法计算结果 最短作业优先作业算法计算结果 最高响应比优先作业算法计算结果 4.基于时间片的轮转调度算法 基本原理：系统将所有的就绪进程按先来先服务的原则， 排成一个队列，每次调度时，把CPU分配给队首进程，并令 其执行一个时间片。 确定时间片大小考虑的因素 系统

6、对响应时间的要求：响应时间=时间片*进程数。 就绪队列中的进程数目：时间片与就绪进程数成反比 。 系统处理能力：人所能承受的响应时间一定，系统速 度快则时间片可增长。 q=1 q=4 A B C D E B C D E A B C E A C E A B C D E A A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 时间片大小对进程执行时间的影响 5. 多级反馈队列调度算法：不需事先知道各进程的执行时间， 且还可以满足各种类型进程需要 优 先 权 降 低 时 间 片 增 大 就绪队列1 就绪队列2 就绪队列3 就绪队列n CPU CPU CPU CPU

7、 S1 S2 S3 Sn (时间片： S1S2 S3Sn) 3.5 产生死锁的原因和必要条件 死锁:多个进程在运行过程中因争夺资源而造成的一种僵局， 若无外力作用，进程都将无法再向前推进。 产生死锁的原因 1. 非剥夺资源：磁带机、打印 机 资源追逐，各不相让 占有并等待 临时性资源：由一个进程产生，被另一个进程使用后便无用 的资源。 进程P1 进程P2 消息S3 消息S1 进程P3 消息S2 P1：Release(S1);Request(S3) P2：Release(S2);Request(S1) P3：Release(S3);Request(S2) 不可能发生死锁 P1：Request(S

8、3);Release(S1) P2：Request(S1);Release(S2) P3：Request(S2);Release(S3) 可能发生死锁 产生死锁的必要条件 (1)互斥条件 (2) 请求和保持条件（占有并等待） (3) 不剥夺条件 (4) 环路等待条件 1.必要条件（缺一不可） 2.必须同时成立或存在 处理死锁的基本方法 (1) 预防死锁 (2) 避免死锁 (3) 检测死锁 (4) 解除死锁 最好是预防，逐 个降格 主动措施 （被动措施） （挽救措施） 3.6 预防死锁的方法 预防死锁 1. 摒弃“请求和保持”条件 2. 摒弃“不剥夺”条件 3. 摒弃“环路等待”条件 由于互斥条

9、件 不可破坏,至少 破坏1/4变成要 破坏1/3. 形成死锁,要 求4个条件同 时成立, 至少 破坏其中1个 就行! 系统安全状态 v安全状态：系统能按某种顺序如 P1,P2, Pn （ 称 P1,P2, Pn 为安全序列 ），为每个进程分配资源，使每 个进程都能顺利完成。 v不安全状态：不存在安全序列的状态。 v避免死锁的实质：如何使系统不进入不安全状态。 安全状态例 假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进 程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设 在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带 机，尚有3台空闲未分配，如下表所示：

10、 进 程 最 大 需 求 已 分 配 可 用 P1 P2 P3 10 4 9 5 2 2 3 安全序列？p1p2p3 ， p2p3p1 ，p2p1 p3 利用银行家算法避免死锁 银行家算法中的数据结构 可利用资源向量Available：一个含有m个元素的数组，其中， 每一个元素代表一类可用的资源数目，其初始值是系统中所 配置的该类全部可用资源数目。其值随资源的分配和回收而 动态地改变。 最大需求矩阵Max：是一个nm的矩阵，定义了系统中n个进 程中的每一个进程对m类资源的最大需求。 分配矩阵Allocation：是一个nm的矩阵，定义了系统中每一 类资源当前已分配给每一进程的资源数。 需求矩阵

11、Need：是一个nm的矩阵，表示每个进程尚需的该 类资源数。 v上述三个矩阵的关系： Need i, j = Max i , j Allocation i , j 其中： Need i, j =k表示进程i还需要 Rj 类资源 k 个。 Max i , j =k 表示进程i 需要 Rj 类资源的最大数 目为 k 。 Allocation i , j =k 表示进程i 当前已分得 Rj类 资源的数目为 k 。 Availablej=k表示系统中现有Rj类资源k个。 银行家算法：Requesti j = k 进程尚需要的资源 Requesti = Needi 1 出 错 N 等 待 N Reque

12、sti = Available Y 是否有足够的 可利用资源 2 系统把要求的资源试探分配给进程Pi Available := Available - Requesti; Allocation := Allocationi + Requesti; Needi :=Needi - Requesti Y 3 系统执行安全性算法 4 分配资源给进程 Y 试探分配作废 N v安全性算法： v 向量 Work 表示系统可提供给进程继续运行所需的各类资源数目，其初始 化为当前可用的资源数。 v 向量 Finish 是布尔型数组，表示系统是否有足够的资源分配给进程，使 之运行完成。初始化为 false。 v

13、 安全性检查的步骤： (1) Work:=Available; Finish:=false; (2) 寻找满足条件的i： a. Finishi=false; b. NeediWork; 如果不存在，则转(4) (3) Work:=Work+Allocationi; Finishi:=true; 转(2) (4) 若对所有i，Finishi=true，则系统处于安全状态，否则处于不 安全状态 银行家算法之例 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源 A, B, C，各种资源的数量分别为10、5、7。 T0时刻的资源分配表 T0时刻的安全性： T0时刻的安全序列 P1请求

14、资源：P1发出请求向量Request1(1，0，2)，系 统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 试分配：系统先假定可为P1分配资源，并修改 Available, Allocation1和Need1向量。 再利用安全性算法检查此时系统是否安全。 P1申请资源时的安全性检查 P4请求资源：P4发出请求向量Request4(3，3，0)，系统按 银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，让P4等待。 P0请求资源：P0发出请求向量Requst0(0，2，0)，系 统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系统暂时先假定可为P0分配资源，并修改有 关数据。 为P0分配资源后的有关资源数据