操作系统课件第3章

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

2、处理机获得处理机 调度方式1) 非抢占方式：不允许其它进程抢占已经分配出去的处理机。实时系统中，不宜采用这种调度方式。2)抢占方式：允许调度程序将已分配出去的处理机重新分配给另一进程。3. 中级调度中级调度主要目的：提高内存利用率和系统吞吐量。 实现方式：对换暂时不能运行的进程调至外存上的挂起队列去等待。当进程重新具备运行条件时，中级调度将挂起队列中某个进程重新调入内存，挂在就绪队列上等待进程调度。 3.2 调度队列模型和调度准则调度队列模型和调度准则调度队列模型1. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型就 绪 队 列阻 塞 队 列进程调度CPU进程完成等待事件交互用户事件出现

3、时间片完这种调度适合于哪种系统？2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型就 绪 队 列进程调度CPU进程完成等待事件 1作业调度事件1出现时间片完等待事件 2事件2出现等待事件 n事件n出现后 备 队 列这种调度适合于哪种系统？3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现高高低低中中调度准则 1. 面向用户的准则面向用户的准则 周转时间短。周转时间短。周转时间周转时间T：从作业被提交给系统，到作业完

4、成为止的时间间隔。由由4个部分组成：在后备队列个部分组成：在后备队列等待的时间、进程在就绪队列中等待的时间、在 CPU中执行的时间、I/O操作完成的时间。平均周转时间： 11niiTTn平均带权周转时间：带权周转时间： W=T/TS（ TS系统服务时间即CPU执行时间）niSiiTTnW11(2) 响应时间快。（评价分时系统，输入、处理、返回）响应时间快。（评价分时系统，输入、处理、返回） (3) 截止时间的保证。（评价实时系统）截止时间的保证。（评价实时系统） (4) 优先权准则优先权准则。 2. 面向系统的准则面向系统的准则(1)系统吞吐量高q吞吐量是指单位时间内完成的作业数(2)处理机利

5、用率好(3)各类资源的平衡利用 -各类资源处于忙碌状态3.3 调调 度度 算算 法法 调度算法调度算法 ：资源分配方法。不同的系统，通常采用不同的调度算法。不同的系统，通常采用不同的调度算法。1. 先来先服务调度算法（既可用于作业调度又可用于进程调度）先来先服务调度算法（既可用于作业调度又可用于进程调度） 2. 短作业短作业(进程进程)优先调度算法优先调度算法 3. 高优先权优先调度算法高优先权优先调度算法(FPF)v 静态优先权：静态优先权：创建进程时确定且在进程的整个运行期间保持不变。优先权是利用某一范围内的一个整数来表示。v 动态优先权：可以改变。动态优先权：可以改变。高响应比优先调度算

6、法高响应比优先调度算法v 优先权优先权=(等待时间等待时间+要求服务时间要求服务时间)/要求服务时间要求服务时间 响应比响应比 Rp=响应时间响应时间/要求服务时间要求服务时间例：在一个批处理单道系统中，采用响应比高者优先的作业调度算法。现有3个作业，进入系统的时间和需要计算的时间如下表所示：（1）求出每个作业的开始时间、完成时间及周转时间并填入表中。（2）计算三个作业的平均周转时间为多少？ （1）平均周转时间：（60+120+70）分钟/3=83.33分钟（2）带权平均周转时间：？作作 业业进进 入入 时时 间间 估估 计计 运运 行行时时 间间（ 分分 钟钟 ）开开 始始 时时 间间 结结

7、 束束 时时 间间 周周 转转 时时 间间（ 分分 钟钟 ）带带 权权 周周 转转时时 间间J O B 18 ： 0 01 2 08 ： 0 01 0 ： 0 01 2 01J O B 28 ： 5 05 01 0 ： 0 01 0 ： 5 01 2 02 .4J O B 39 ： 0 01 01 0 ： 5 01 1 ： 0 01 2 01 2J O B 49 ： 5 02 01 1 ： 0 01 1 ： 2 09 04 .5作作 业业 平平 均均 周周 转转 时时 间间 T = 1 1 2 .5作作 业业 带带 权权 平平 均均 周周 转转 时时 间间 W = 4 .9 7 54 5 01

8、 9 .9分别采用FCFS、SJF、FPF求出每个作业的开始时间、完成时间、周转时间、带权周转时间并填入表中。计算系统的平均周转时间和平均带权周转时间。先来先服务调度算法计算结果先来先服务调度算法计算结果作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）开开始始时时间间结结束束时时间间周周转转时时间间（分分钟钟）带带权权周周转转时时间间JOB18：001208：0010：001201JOB28：505010：0010：501202.4JOB39：001010：5011：0012012JOB49：502011：0011：20904.5作作业业平平均均周周转转时时间间 T = 112.5

9、作作业业带带权权平平均均周周转转时时间间 W = 4.97545019.9最短作业优先作业算法计算结果最短作业优先作业算法计算结果作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）开开始始时时间间结结束束时时间间周周转转时时间间（分分钟钟）带带权权周周转转时时间间JOB18：001208：0010：001201JOB28：505010：3011：201503JOB39：001010：0010：10707JOB49：502010：1010：30402作作业业平平均均周周转转时时间间 T = 95作作业业带带权权平平均均周周转转时时间间 W = 3.2538013最高响应比优先作业算法计

10、算结果最高响应比优先作业算法计算结果 作作业业 进进入入时时间间 估估计计运运行行时时间间 （分分钟钟） 开开始始时时间间 结结束束时时间间 周周转转时时间间 （分分钟钟） 带带权权周周转转时时间间 JOB1 8：00 120 8：00 10：00 120 1 JOB2 8：50 50 10：10 11：00 130 2.6 JOB3 9：00 10 10：00 10：10 70 7 JOB4 9：50 20 11：00 11：20 90 4.5 作作业业平平均均周周转转时时间间 T =102.5 作作业业带带权权平平均均周周转转时时间间 W = 3.775 410 15.1 4.基于时间片的

11、轮转调度算法基于时间片的轮转调度算法 基本原理：系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。确定时间片大小考虑的因素系统对响应时间的要求：响应时间=时间片*进程数。就绪队列中的进程数目：时间片与就绪进程数成反比。系统处理能力：人所能承受的响应时间一定，系统速度快则时间片可增长。q=1q=4ABCDEBCDEABCEACEABCDEAA1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17时间片大小对进程执行时间的影响5. 多级反馈队列调度算法多级反馈队列调度算法：不需事先知道各进程的执行时间，且还可

12、以满足各种类型进程需要优优先先权权降降低低时时间间片片增增大大就绪队列1就绪队列2就绪队列3就绪队列nCPUCPUCPUCPUS1S2S3Sn(时间片： S1S2 S3Sn)3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件死锁死锁:多个进程在运行过程中因争夺资源而造成的一种僵局，多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，进程都将无法再向前推进。若无外力作用，进程都将无法再向前推进。 产生死锁的原因产生死锁的原因 非剥夺资源：磁带机、打印机R1R2P1P2资源追逐，各不相让资源追逐，各不相让占有并等待占有并等待临时性资源：由一个进程产生，被另一个进程使用后便无用的资源

13、。进程进程P1进程进程P2消息S3消息S1进程进程P3消息消息S2P1：Release(S1);Request(S3)P2：Release(S2);Request(S1)P3：Release(S3);Request(S2)不可能发生死锁P1：Request(S3);Release(S1)P2：Request(S1);Release(S2)P3：Request(S2);Release(S3)可能发生死锁产生死锁的必要条件产生死锁的必要条件 互斥条件互斥条件 (2) 请求和保持条件（占有并等待）请求和保持条件（占有并等待）(3) 不剥夺条件不剥夺条件 (4) 环路等待条件环路等待条件 1.必要条件

14、（缺一不可）必要条件（缺一不可）2.必须同时成立或存在必须同时成立或存在处理死锁的基本方法处理死锁的基本方法 预防死锁预防死锁 (2) 避免死锁避免死锁(3) 检测死锁检测死锁 (4) 解除死锁解除死锁 最好是预防，逐最好是预防，逐个降格个降格主动措施主动措施（被动措施）（被动措施）（挽救措施）（挽救措施）3.6 预防死锁的方法预防死锁的方法 预防死锁预防死锁 摒弃摒弃“请求和保持请求和保持”条件条件 2. 摒弃摒弃“不剥夺不剥夺”条件条件 3. 摒弃摒弃“环路等待环路等待”条件条件 由于互斥条件由于互斥条件不可破坏不可破坏,至少至少破坏破坏1/4变成要变成要破坏破坏1/3.形成死锁形成死锁,

15、要要求求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台空闲未分配，如下表所示： 进 程 最 大 需 求 已 分 配

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

17、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 = Needi1出 错N等 待NRequesti = AvailableY是否有足够

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

19、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请求资源：请求