OUC操作系统第三章处理机调度与死锁.ppt

《OUC操作系统第三章处理机调度与死锁.ppt》由会员分享，可在线阅读，更多相关《OUC操作系统第三章处理机调度与死锁.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 处理机调度的基本概念3.2 调度算法3.3 实时调度3.4 多处理机系统中的调度(略)3.5 产生死锁的原因和必要条件3.6 预防死锁的方法3.7 死锁的检测与解除 3.1 处理机调度的基本概念处理机调度的概念处理机调度的概念采用一定的算法(方法、规则)，从就绪队列中选择一个进程，让CPU来执行它。调度的三个级别调度的三个级别高级调度（作业调度）中级调度（与挂起状态有关）低级调度（进程调度）23.1.1 高级、中级和低级调度1.1.高级调度高级调度批处理系统特有的调度批处理系统特有的调度 (分时、实时没有分时、实时没有)作用作用决定把后

2、备队列中的哪些作业调入内存，并为其创建进程、分配资源，并将其插入到就绪队列。执行作业调度时，须作两个决定(考虑两个问题)：接纳多少作业不易过多，也不能太少接纳哪些作业取决于调度算法32.2.低级调度（进程调度）低级调度（进程调度）三种操作系统都必须有的调度三种操作系统都必须有的调度作用作用决定把CPU分配给就绪队列中的哪个进程，具体分派CPU的操作由分派程序执行。两种调度方式两种调度方式非抢占方式非抢占方式抢占方式抢占方式注：进程调度比较频繁，因此进程调度算法不能太复杂，以免占用太多CPU时间4非抢占方式非抢占方式一旦将CPU分配给某进程，便让它一直运行，直到它完成或阻塞，才让另一个来执行可能

3、引起调度的原因进程执行完毕，或因某事件不能执行下去提出I/O请求而暂停执行wait、block等原语优点实现简单、系统开销小，适用于大多数的批处理系统环境缺点难以满足紧急任务的要求立即执行，因而可能造成难以预料的后果在要求比较严格的实时系统中，不宜采用5抢占方式抢占方式允许按照某种原则暂停正在执行的进程，让另一个来执行抢占的原则优先权原则短作业(进程)优先原则时间片原则63.3.中级调度中级调度引入的目的引入的目的提高内存利用率和系统吞吐量作用作用把暂时不运行的进程放到外存等待，留出内存给其他进程使用在外存上的进程称为“挂起状态挂起状态”当这些进程又具备运行条件、且内存有空位时，便选择一些调入

4、内存，进入就绪状态78处理机的三级调度3.1.2 调度队列模型仅有进程调度的调度队列模型仅有进程调度的调度队列模型9就就绪绪队队列列阻阻塞塞队队列列CPU进程完成进程调度等待事件交互用户事件出现时间片完就绪状态的进程常组织成栈、树、无序链表就绪状态的进程常组织成栈、树、无序链表分时系统中，常组织成分时系统中，常组织成FIFOFIFO队列队列来了一个新进程，便放到队尾，并按时间片执行来了一个新进程，便放到队尾，并按时间片执行具有高级调度和低级调度的调度队列模型具有高级调度和低级调度的调度队列模型10就就绪绪队队列列阻阻塞塞队队列列CPU进程完成进程调度等待事件1事件1出现时间片完阻阻塞塞队队列列

5、阻阻塞塞队队列列等待事件2等待事件n事件2出现事件3出现后备队列作业调度批处理系统批处理系统具有三级调度的调度队列模型具有三级调度的调度队列模型11就就绪绪队队列列就绪就绪挂起挂起队队列列CPU进程完成进程调度等待事件时间片完阻塞阻塞挂起挂起队队列列阻阻塞塞队队列列事件出现后备队列作业调度挂起事件出现中级调度3.1.3 选择调度方式和调度算法的若干准则主要取决于主要取决于OSOS的类型和目标的类型和目标1.面向用户的准则面向用户的准则周转时间短批处理系统响应时间快分时系统截止时间的保证实时系统优先权准则适用于三种OS系统2.面向系统的准则面向系统的准则系统吞吐量高批处理系统CPU利用率好各类资

6、源的平衡利用123.2 调度算法调度的实质是一种资源分配调度的实质是一种资源分配调度算法的定义调度算法的定义根据系统的资源分配策略资源分配策略所规定的资源分配算法调度算法的选择调度算法的选择根据OS的类型和目标13先来先服务先来先服务(FCFS)调度算法调度算法最简单的算法，可用于作业调度、进程调度最简单的算法，可用于作业调度、进程调度基本思想谁先来，先为谁服务(类似食堂排队打饭)特点有利于长作业(进程)，不利于短作业(进程)因为长作业的带权周转时间短14进程名进程名到达到达时间时间服务服务服务服务时间时间时间时间开始执开始执行时间行时间完成完成时间时间周转周转时间时间带权带权带权带权周转周转

7、周转周转时间时间时间时间A A0 01 10 01 11 11 1B B1 11001001 11011011001001 1C(C(短作业短作业)2 21 1101101102102100100100100D(D(长作业长作业)3 31001001021022022021991991.991.9915长作业有利的例子长作业有利的例子短作业短作业(进程进程)优先调度算法优先调度算法(SJF、SPF)可用于作业调度、进程调度可用于作业调度、进程调度基本思想基本思想哪个估计估计运行时间最短，先运行哪个 优点优点有效降低平均等待时间，提高系统吞吐量和FCFS相比，SJ(P)F中，平均周转时间、平均带

8、权周转时间有明显改善缺点缺点对长作业(进程)不利没考虑作业(进程)的紧急程度由于是估计的运行时间，所以不一定能真正做到短的优先16高优先权优先调度算法高优先权优先调度算法(FPF)目的照顾紧迫型作业，使之进入系统后能被优先处理两种类型非抢占式非抢占式一旦选择了优先权最高的进程执行，直到它结束或阻塞后，才选另一个执行抢占式抢占式若出现优先权更高的，则让出CPU这样可更好的满足紧迫性FPF算法的关键算法的关键优先权是静态的，还是动态的？如何确定进程的优先权？17优先权类型优先权类型静态优先权静态优先权基本思想：创建进程时分配，保持不变确定优先权的依据进程类型：系统进程的 一般用户的进程对资源的需求

9、：估计执行时间、内存需求少的，优先权高用户要求：根据用户的紧迫度、用户所付费用来确定优点：简单易行、系统开销小缺点：不精确,优先权低的可能长时间无法执行适用：要求不高的系统18动态优先权动态优先权基本思想随进程的执行或等待时间的增加而改变优先权低的等待一定时间后，优先权会提高规定当前执行的进程优先权随时间下降优点在抢占方式下，可防止长进程长期霸占CPU19高响应比优先权调度算法高响应比优先权调度算法动态优先权 优先权优先权 =(等待时间等待时间+要求服务时间要求服务时间)/要求服要求服务时间务时间 即 响应比响应比 =响应时间响应时间 /要求服务时间要求服务时间由上可知由上可知等待时间相同，要

10、求服务时间越短，优先权越高有利于短作业要求服务时间相同，等待时间越长，优先权越高相当于FCFS长作业的优先权可随等待时间增加而提高优点：优点：短、长作业都考虑到了缺点：缺点：调度之前，须计算响应比，增加了系统开销20基于时间片的轮转调度算法基于时间片的轮转调度算法分时系统分时系统1.1.早期的时间片轮转法早期的时间片轮转法系统将就绪进程按先来先服务原则，排成一个队列每次调度时，把CPU分配给队首进程，让它执行一个时间片时间片用完时，调度程序根据计时器发出时钟中断停止进程的执行，并将它插至就绪队列末尾然后，把CPU分配给就绪队列中新的队首进程，也让它执行一个时间片这样，可保证就绪队列中所有进程，

11、均能获得一时间片的执行时间212.2.多级反馈队列调度算法多级反馈队列调度算法基本思想基本思想设多个就绪队列(按优先级划分)，优先权越高，获得的时间片越小新进程进入系统后，放入第一个队列，按FCFS原则等待。第i个时间片执行完后，便放入i+1队列尾仅当队列L1Li空时，才从Li+1队列中调度进程可以抢占22就绪队列就绪队列1 L1就绪队列就绪队列2 L2就绪队列就绪队列n LnS1CPUS2S3优先级：优先级：L1 L2 Ln时间片：时间片：S1 S2 Available(2,3,0)，让P4等待4.P0请求资源P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查Reques

12、t0(0,2,0)Need0(7,4,3);Request0(0,2,0)Available(2,3,0);系统先假定可为P0分配资源，并修改有关数据，如下图所示6061为P0分配资源后的有关资源数据n 已不能满足任何进程的需要，所以无法进入安全状态，已不能满足任何进程的需要，所以无法进入安全状态，此时不能分配资源此时不能分配资源3.7 死锁的检测与解除1.死锁的检测死锁的检测资源分配图62每类资源有多个时的情况 死锁定理死锁定理基本思想通过简化资源分配图,检测死锁基本方法不断寻找既不阻塞又不独立的进程结点Pi顺利时，Pi可获得所需资源，并执行完相当于，消去连接Pi的各条边，使之成为孤立结点死

13、锁定理S为死锁状态的充分必要条件是，当且仅当S状态的资源分配图是不可完全简化的63死锁的解除死锁的解除两种方法剥夺资源从其他进程剥夺足够资源给死锁的进程撤消进程（有两种方法）a)撤销全部死锁进程b)按某顺序逐个撤销，直到有足够资源为止策略撤销进程数目最小撤销进程所付代价最小，等等64小结三种级别的调度(高、中、低)调度和死锁的基本概念常用的调度算法常用的调度算法死锁概念、产生的必要条件死锁概念、产生的必要条件(四个条件四个条件)死锁的预防和避免方法银行家算法银行家算法死锁的检测及解除65练习题1.避免死锁的一个著名的算法是()A.先入先出法；B银行家算法；C优先级算法；D资源按序分配法2.在一

14、般操作系统中必不可少的调度是()A高级调度；B中级调度；C作业调度；D进程调度 66BD3.资源的有序分配算法在解决死锁问题中是用于()A.预防死锁 B.避免死锁 C.检测死锁 D.解除死锁4.一进程在获得资源后，只能在使用完资源时由自己释放，这属于死锁必要条件的（）A.互斥条件 B.请求和释放条件 C.不剥夺条件 D.环路等待条件 67AC5.在下列进程调度算法中，哪一个算法会对优先权进行调整（）A.先来先服务 B.短进程优先 C.高响应比优先 D.时间片轮转6.下面()算法不是进程调度算法A.LRUB.FCFSC.SJFD.FPF7.既考虑作业等待时间，又考虑作业执行时间的调度算法是()A

15、.高响应比优先B.短作业优先 C优先级调度 D.先来先服务 68CAA8.作业调度算法从()队列中选取适当的作业投入运行A.执行 B.就绪 C.完成 D.后备9.()是指从作业提交给系统到作业完成的时间间隔A.周转时间 B.响应时间 C.等待时间 D.运行时间10.下述作业调度算法中，()调度算法与作业的估计运行时间有关A.先来先服务B.短作业优先 C.均衡 D.时间片轮转 69DAB11.采用资源剥夺法可解除死锁，还可以采用()方法解除死锁A.执行并行操作 B.撒消进程 C.拒绝分配新资源 D.修改信号量12.产生死锁的四个必要条件是：互斥、()、循环等待和不剥夺A.请求与阻塞 B.请求与保

16、持 C.请求与释放 D.释放与阻塞 70BB13.发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏()条件是不太实际的A.互斥 B.不剥夺 C.请求与保持 D.循环等待14.银行家算法是一种()算法A.解除死锁 B.避免死锁C.预防死锁 D.检测死锁15.当进程数大于资源数时，进程竞争资源()会产生死锁A.一定 B.不一定 C.不可能 D.以上答案都不对71ABB16.()优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变A.先来先服务 B.静态 C.动态 D.短作业17.OS中，出现死锁指的是()A.计算机发生故障 B.资源数少于进程数 C.若干进程因竞

17、争资源而无限等待其他进程释放已占用的资源 D.进程同时申请的资源数超过资源总数72BC18.哪种说法对抢占式调度来说是正确的()A.系统采用轮转调度，则系统采用的是抢占式调度B.若当前进程等待某一事件时引起调度，则该系统采用的是抢占式调度C.实时系统通常采用抢占式调度D.采用抢占式调度的系统中，进程的周转周期较非抢占式的系统是可预测的73C19.3个进程各需要4个同类资源，问该资源最少要有几个才不会产生死锁()A.9B.10C.11D.1274B20.现有8台打印机，N个进程争用，每个可能用3台，N最大为多少时没有死锁的危险()A.1B.2C.3D.475C判断题进程实体由PCB和数据集，及对数据集进行操作的程序组成 ()并发是并行的不同表述，原理相同 ()所谓多道程序设计，指每一时刻可以有若干个进程在执行 ()银行家算法用来检测死锁 ()只要破坏产生死锁的四个必要条件中的其中一个就可以预防死锁的发生 （）76XXX填空题系统中有n个进程，就绪队列中最多可有()个进程不让死锁发生的策略可分为静态、动态两种，避免死锁属于()系统中有m个进程，死锁涉及了k个进程，问k应满足的条件()77n-1n-1动态策略动态策略2 2 k k m m