OUC-操作系统-第三章-处理机调度与死锁课件

1第三章处理机调度与死锁

3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度(略)3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除1第三章处理机调度与死锁3.1处理机调度的基本概念13.1处理机调度的基本概念处理机调度的概念采用一定的算法(方法、规则)，从就绪队列中选择一个进程，让CPU来执行它。调度的三个级别高级调度（作业调度）中级调度（与挂起状态有关）低级调度（进程调度）23.1处理机调度的基本概念处理机调度的概念223.1.1高级、中级和低级调度高级调度批处理系统特有的调度(分时、实时没有)作用决定把后备队列中的哪些作业调入内存，并为其创建进程、分配资源，并将其插入到就绪队列。执行作业调度时，须作两个决定(考虑两个问题)：接纳多少作业——不易过多，也不能太少接纳哪些作业——取决于调度算法33.1.1高级、中级和低级调度高级调度33低级调度（进程调度）三种操作系统都必须有的调度作用决定把CPU分配给就绪队列中的哪个进程，具体分派CPU的操作由分派程序执行。两种调度方式非抢占方式抢占方式注：进程调度比较频繁，因此进程调度算法不能太复杂，以免占用太多CPU时间4低级调度（进程调度）44非抢占方式一旦将CPU分配给某进程，便让它一直运行，直到它完成或阻塞，才让另一个来执行可能引起调度的原因进程执行完毕，或因某事件不能执行下去提出I/O请求而暂停执行wait、block等原语优点实现简单、系统开销小，适用于大多数的批处理系统环境缺点难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果在要求比较严格的实时系统中，不宜采用5非抢占方式55抢占方式允许按照某种原则暂停正在执行的进程，让另一个来执行抢占的原则优先权原则短作业(进程)优先原则时间片原则6抢占方式66中级调度引入的目的提高内存利用率和系统吞吐量作用把暂时不运行的进程放到外存等待，留出内存给其他进程使用在外存上的进程称为“挂起状态”当这些进程又具备运行条件、且内存有空位时，便选择一些调入内存，进入就绪状态7中级调度778处理机的三级调度8处理机的三级调度83.1.2调度队列模型仅有进程调度的调度队列模型9就绪队列阻塞队列CPU进程完成进程调度等待事件交互用户事件出现时间片完就绪状态的进程常组织成栈、树、无序链表分时系统中，常组织成FIFO队列来了一个新进程，便放到队尾，并按时间片执行3.1.2调度队列模型仅有进程调度的调度队列模型9就绪队列9具有高级调度和低级调度的调度队列模型10就绪队列阻塞队列CPU进程完成进程调度等待事件1事件1出现时间片完阻塞队列阻塞队列等待事件2等待事件n事件2出现事件3出现后备队列作业调度批处理系统具有高级调度和低级调度的调度队列模型10就绪队列阻塞队列CP10具有三级调度的调度队列模型11就绪队列就绪挂起队列CPU进程完成进程调度等待事件时间片完阻塞挂起队列阻塞队列事件出现后备队列作业调度挂起事件出现中级调度具有三级调度的调度队列模型11就绪队列就绪挂起队列CPU进程113.1.3选择调度方式和调度算法的若干准则主要取决于OS的类型和目标面向用户的准则周转时间短——批处理系统响应时间快——分时系统截止时间的保证——实时系统优先权准则——适用于三种OS系统面向系统的准则系统吞吐量高——批处理系统CPU利用率好各类资源的平衡利用123.1.3选择调度方式和调度算法的若干准则主要取决于OS的123.2调度算法调度的实质是一种资源分配调度算法的定义根据系统的资源分配策略所规定的资源分配算法调度算法的选择根据OS的类型和目标133.2调度算法调度的实质是一种资源分配1313先来先服务(FCFS)调度算法最简单的算法，可用于作业调度、进程调度基本思想谁先来，先为谁服务(类似食堂排队打饭)特点有利于长作业(进程)，不利于短作业(进程)因为长作业的带权周转时间短14先来先服务(FCFS)调度算法1414进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C(短作业)21101102100100D(长作业)31001022021991.9915长作业有利的例子进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时15短作业(进程)优先调度算法(SJF、SPF)

可用于作业调度、进程调度基本思想哪个估计运行时间最短，先运行哪个优点有效降低平均等待时间，提高系统吞吐量和FCFS相比，SJ(P)F中，平均周转时间、平均带权周转时间有明显改善缺点对长作业(进程)不利没考虑作业(进程)的紧急程度由于是估计的运行时间，所以不一定能真正做到短的优先16短作业(进程)优先调度算法(SJF、SPF)1616高优先权优先调度算法(FPF)目的照顾紧迫型作业，使之进入系统后能被优先处理两种类型非抢占式一旦选择了优先权最高的进程执行，直到它结束或阻塞后，才选另一个执行抢占式若出现优先权更高的，则让出CPU这样可更好的满足紧迫性FPF算法的关键优先权是静态的，还是动态的？如何确定进程的优先权？17高优先权优先调度算法(FPF)1717优先权类型静态优先权基本思想：创建进程时分配，保持不变确定优先权的依据进程类型：系统进程的>一般用户的进程对资源的需求：估计执行时间、内存需求少的，优先权高用户要求：根据用户的紧迫度、用户所付费用来确定优点：简单易行、系统开销小缺点：不精确,优先权低的可能长时间无法执行适用：要求不高的系统18优先权类型1818动态优先权基本思想随进程的执行或等待时间的增加而改变优先权低的等待一定时间后，优先权会提高规定当前执行的进程优先权随时间下降优点在抢占方式下，可防止长进程长期霸占CPU19动态优先权1919高响应比优先权调度算法动态优先权

优先权=(等待时间+要求服务时间)/要求服务时间

即

响应比=响应时间/要求服务时间由上可知等待时间相同，要求服务时间越短，优先权越高——有利于短作业要求服务时间相同，等待时间越长，优先权越高——相当于FCFS长作业的优先权可随等待时间增加而提高优点：短、长作业都考虑到了缺点：调度之前，须计算响应比，增加了系统开销20高响应比优先权调度算法2020基于时间片的轮转调度算法——分时系统早期的时间片轮转法系统将就绪进程按先来先服务原则，排成一个队列每次调度时，把CPU分配给队首进程，让它执行一个时间片时间片用完时，调度程序根据计时器发出时钟中断停止进程的执行，并将它插至就绪队列末尾然后，把CPU分配给就绪队列中新的队首进程，也让它执行一个时间片这样，可保证就绪队列中所有进程，均能获得一时间片的执行时间21基于时间片的轮转调度算法——分时系统2121多级反馈队列调度算法基本思想设多个就绪队列(按优先级划分)，优先权越高，获得的时间片越小新进程进入系统后，放入第一个队列，按FCFS原则等待。第i个时间片执行完后，便放入i+1队列尾仅当队列L1—Li空时，才从Li+1队列中调度进程——可以抢占22就绪队列1L1就绪队列2L2就绪队列nLnS1CPUS2S3优先级：L1>L2>Ln时间片：S1<S2<Sn新进程多级反馈队列调度算法22就绪队列1L1就绪队列222多级反馈队列调度算法的性能性能较好能较好满足各类用户的需求短进程可在一两个时间片内完成长进程也不必担心长期得不到处理23多级反馈队列调度算法的性能23233.3实时调度实时系统与其他系统的最大区别处理和控制的正确性不仅取决于计算的结果，还取决于计算和处理结果产生的时间实时系统具有的特点进程往往带有一定的紧迫度实时系统中，任务往往联系着一个截止时间所以，要引入一种新的调度——“实时调度”243.3实时调度实时系统与其他系统的最大区别24243.3.1实现实时调度应具备以下几个条件提供必要的信息就绪时间：任务何时进入就绪状态的？截止时间：开始截止时间、完成截止时间处理时间：任务从开始执行到完成所需时间资源要求：需要哪些资源优先级：描述进程的紧迫度系统处理能力强如果CPU处理能力弱，可能导致某些任务不能及时被处理采用抢占方式硬实时任务的实时系统中，广泛采用抢占方式具有快速的切换机制保证任务能快速切换253.3.1实现实时调度应具备以下几个条件25253.3.2实时调度算法的分类非抢占式调度算法应用于小型系统、要求不严的系统抢占式调度算法应用于要求严格的系统263.3.2实时调度算法的分类2626非抢占式调度算法非抢占式轮转调度算法计算机控制多个相同的对象,为每个创建一个实时任务,排成轮转队列。用于工业生产的群控系统。非抢占式优先调度算法用于有一定要求的实时控制系统抢占式调度算法基于时钟中断的抢占式优先权调度算法时钟中断到来后才进行抢占，有较好的响应效果。用于大多数的实时控制立即抢占的优先权调度算法只要当前任务未处于临界区可立即抢占，可获得非常快的响应。用于发生外部中断的紧急任务27非抢占式调度算法272728实时进程调度28实时进程调度28293.3.3常用的几种实时调度算法最早截止时间优先(EDF,EarliestDeadlineFirst)算法根据开始截止时间确定优先级越早，优先级越高就绪队列按优先级排序可用于抢占、非抢占调度293.3.3常用的几种实时调度算法2930EDF算法用于非抢占调度方式开始截止时间：3早于2，4早于2

30EDF算法用于非抢占调度方式3031最低松弛度优先(LLF,LeastLaxityFirst)算法主要用于抢占调度方式根据任务紧急(或松弛)的程度，松弛度越低(紧急度越高)，优先级越高松弛度=完成截止时间–剩余运行时间-当前时间31最低松弛度优先(LLF,LeastLaxityFi3132A和B任务每次必须完成的时间例：两个周期性实时任务A、B，A：每20ms执行一次，执行时间为10msB：每50ms执行一次，执行时间为25ms32A和B任务每次必须完成的时间例：两个周期性实时任务A、3233在t=0ms时A1松弛度=20–10–0=10B1松弛度=50–25–0=25

故应先调度A1执行。在t=10ms时，

A2的松弛度=必须完成时间-剩余运行时间-当前时间=40-10-10=20B1的松弛度=必须完成时间-剩余运行时间-当前时间

=50-25-10=15

故应先调度B1执行。33在t=0ms时333.5产生死锁的原因和必要条件3.5.1产生死锁的原因死锁的定义多个进程在运行过程中，因争夺资源而造成的一种僵局。当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。产生死锁的原因竞争资源由于系统中的资源不够进程用的，可能引起对资源的竞争而死锁进程间推进顺序非法进程在请求和释放资源时，顺序不当343.5产生死锁的原因和必要条件3.5.1产生死锁的原34竞争资源引起死锁两个概念可剥夺资源进程获得该种资源后，还可被剥夺(CPU、内存)非可剥夺资源一旦获得，用完后才能被收回(打印机)35竞争资源引起死锁3535竞争非剥夺性资源36I/O设备共享时的死锁情况

竞争非剥夺性资源36I/O设备共享时的死锁情况36竞争非剥夺性资源临时性资源一个进程产生，被另一个用了一段时间后便无用的资源(如：消息)37进程之间通信时的死锁

竞争非剥夺性资源37进程之间通信时的死锁3738图3-14进程推进顺序对死锁的影响Rel(R1)Rel(R2)Req(R1)Req(R2)Req(R1)Req(R2)Rel(R1)Rel(R2)P2

P1

②①④③进程推进顺序不当引起死锁D不安全区38图3-14进程推进顺序对死锁的影响Rel(R1)R383.5.2产生死锁的必要条件互斥条件进程在使用某资源时，不允许其他进程使用

请求和保持条件进程已保持至少一个资源，请求另一个资源时无法获得，便阻塞，但又不放弃已占用的资源不剥夺条件资源使用完前，不允许剥夺，直至其用完环路等待条件发生死锁，一定会有“进程-资源”环形链

注：只有四个条件同时满足时，才会死锁393.5.2产生死锁的必要条件39393.5.3处理死锁的基本方法预防死锁设置限制条件，破坏四个条件中的一个或几个简单易行，但限制条件往往较严格，影响效率避免死锁动态分配资源时，防止系统进入不安全状态限制条件不必很苛刻，但实现较难检测死锁不用任何限制条件，也不检查系统是否进入安全区。允许发生死锁。可通过机制及时检测出死锁解除死锁撤销或挂起一些进程，以便回收一些资源，再将它们分给陷入死锁的其他进程403.5.3处理死锁的基本方法40403.6预防死锁的方法基本思想使四个条件中的2、3、4不成立条件1(互斥条件)是设备固有的，所以不应限制，反而应加强413.6预防死锁的方法基本思想4141摒弃“请求和保持”条件基本思想规定所有进程在开始之前，都必须一次性申请其在整个运行过程中所需的全部资源只要有一种资源不够，便全不分配优点简单易行，安全缺点资源浪费进程延迟执行(仅当全部资源都获得后，才能运行)42摒弃“请求和保持”条件4242摒弃“不剥夺”条件基本思想进程可以逐个申请资源，一旦申请的资源无法满足，立即释放已经保持的所有资源缺点复杂代价大(资源被迫释放，可能导致以前的工作无效)反复申请资源，可能使进程执行被无限推迟43摒弃“不剥夺”条件4343摒弃“环路等待”条件基本思想按类型给资源赋序号进程申请资源必须按序号递增次序提出如：输入机=1,打印机=2,磁带机=3,磁盘=4优点利用率、吞吐量明显改善缺点资源序号相对稳定，不利新设备加入进程使用资源次序和序号次序不同，浪费对用户编程不利44摒弃“环路等待”条件44443.6.2系统安全状态

安全状态定义系统能按某顺序(P1,P2,…，Pn)，为每个进程Pi分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成称〈P1,P2,…,Pn〉序列为安全序列如果系统无法找到这样一个安全序列，则称系统处于不安全状态——可能导致死锁避免死锁实质进行资源分配时，如何使系统不进入不安全状态453.6.2系统安全状态454546安全状态举例设有进程P1、P2和P3，及12台磁带机P1、P2、P3分别需要10、4、9台磁带机T0时刻，P1、P2和P3已分别获得5台、2台和2台，尚有3台未分配请问T0时刻是否是安全的？解答：实质是问，T0时刻是否存在一个安全序列进程最大需求已分配可用P1P2P31049522

3安全序列(P2,P1,P3)5101212346安全状态举例进程最大需求已分配可用46由安全状态向不安全状态的转换如果不按照安全序列分配资源，系统可能会由安全状态进入不安全状态。比如：P3又请求1台磁带机以后：47进程最大需求已分配可用P1P2P31049523

24不安全了！109

所以，尽管系统尚有可用的磁带机，也不能分配给P3由安全状态向不安全状态的转换47进程最大需求已473.6.3利用银行家算法避免死锁提出者：Dijkstra最著名的避免死锁的算法基本思想当用户申请一组资源时，系统首先判断如果把这些资源分配出去，系统是否还处于安全状态。若是，就可以分配；否则，该申请暂不予满足483.6.3利用银行家算法避免死锁484849银行家算法中的数据结构可利用资源向量Available[1…m]

表示m种资源中每种可供使用的数量，初始值是系统中每类资源的全部数量Available［j］=K表示目前资源j有K个可供使用最大需求矩阵Max[1..n,1..m]表示n个进程中的每个进程对m种资源的最大需求量Max［i,j］=K表示进程i对资源j的最大需求量为K49银行家算法中的数据结构49已分配矩阵Allocation[1..n,1..m]

每种资源已分配给每个进程的数量Allocation［i,j］=K,进程i当前已获得资源j的数目为K需求矩阵Need[1..n,1..m]

每个进程还需要资源的数量Need［i,j］=K,表示进程i还需要K个资源j，才能执行完50已分配矩阵Allocation[1..n,1..m]5050数据结构的小结Available［j］：目前资源j可供使用的数量Max［i,j］：进程i需要资源j的最大数量Allocation［i,j］：进程i当前已获得资源j的数量Need［i,j］：进程i还需要多少资源j，才能执行完51所以，Need［i,j］=Max［i,j］-Allocation［i,j］

数据结构的小结51所以，Need［i,j］=Max［i,j5152银行家算法设向量Requesti[1...m]

如果Requesti［j］=K，表示进程Pi需要K个资源jPi申请资源时，OS如下进行检查：如果Requesti［j］≤Need［i,j］，执行下一步；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。如果Requesti［j］≤Available［j］，执行下一步；否则，表示尚无足够资源，Pi须等待。52银行家算法5253OS假设把资源分配给进程Pi，并作如下修改：

Available［j］:=Available［j］-Requesti［j］;Allocation［i,j］:=Allocation［i,j］+Requesti［j］;Need［i,j］:=Need［i,j］-Requesti［j］;执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才真正把资源分配给进程Pi；否则，本次假设的分配作废，恢复原来的资源分配状态，让进程Pi等待。53OS假设把资源分配给进程Pi，并作如下修改：53安全性算法作用查看是否存在一个安全序列算法设置两个数组向量①工作向量Work[1..m]OS可提供给进程继续运行所需的各种资源数量安全性算法初始时，Work:=Available;Finish[1..n]系统是否有足够的资源分配给进程，使之运行完成。初始时Finish［i］:=false;当有足够资源分配给进程i时，便令Finish［i］:=true54安全性算法5454从所有的进程中找到一个能满足下述条件的进程:Finish［i］=false;Need［i,j］≤Work［j］;若找到，执行步骤3;否则，执行步骤4执行以下两步修改Finish［i］∶=true;

Work［j］∶=Work［j］+Allocation［i,j］;

因为进程Pi获得所需的资源后，便可畅通无阻的执行完，并释放出已分配给它的资源，从而使系统里的可用资源增多。如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态55从所有的进程中找到一个能满足下述条件的进程:5555银行家算法举例五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示56银行家算法举例565657T0时刻的安全性：57T0时刻的安全性：57P1请求资源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向量，由此形成的资源变化情况如图中的圆括号所示再利用安全性算法检查此时系统是否安全58P1请求资源585859P1申请资源时的安全性检查存在安全序列：(P1，P3，P4，P0，P2)59P1申请资源时的安全性检查存在安全序列：(P1，P3，59P4请求资源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分配资源，并修改有关数据，如下图所示60P4请求资源606061为P0分配资源后的有关资源数据已不能满足任何进程的需要，所以无法进入安全状态，此时不能分配资源61为P0分配资源后的有关资源数据已不能满足任何进程的需要613.7死锁的检测与解除死锁的检测资源分配图62每类资源有多个时的情况3.7死锁的检测与解除死锁的检测62每类资源有多个时的情62死锁定理基本思想通过简化资源分配图,检测死锁基本方法不断寻找既不阻塞又不独立的进程结点Pi顺利时，Pi可获得所需资源，并执行完相当于，消去连接Pi的各条边，使之成为孤立结点死锁定理S为死锁状态的充分必要条件是，当且仅当S状态的资源分配图是不可完全简化的63死锁定理6363死锁的解除两种方法剥夺资源从其他进程剥夺足够资源给死锁的进程撤消进程（有两种方法）撤销全部死锁进程按某顺序逐个撤销，直到有足够资源为止策略撤销进程数目最小撤销进程所付代价最小，等等64死锁的解除6464小结三种级别的调度(高、中、低)调度和死锁的基本概念常用的调度算法死锁概念、产生的必要条件(四个条件)死锁的预防和避免方法银行家算法死锁的检测及解除65小结三种级别的调度(高、中、低)6565练习题避免死锁的一个著名的算法是(

)A.先入先出法；B．银行家算法；C．优先级算法；D．资源按序分配法在一般操作系统中必不可少的调度是(

)A．高级调度；B．中级调度；C．作业调度；D．进程调度66BD练习题避免死锁的一个著名的算法是()66BD66资源的有序分配算法在解决死锁问题中是用于()A.预防死锁B.避免死锁C.检测死锁D.解除死锁一进程在获得资源后，只能在使用完资源时由自己释放，这属于死锁必要条件的（）A.互斥条件B.请求和释放条件C.不剥夺条件D.环路等待条件67AC资源的有序分配算法在解决死锁问题中是用于(67在下列进程调度算法中，哪一个算法会对优先权进行调整（）

A.先来先服务B.短进程优先C.高响应比优先D.时间片轮转下面()算法不是进程调度算法A.LRUB.FCFSC.SJFD.FPF既考虑作业等待时间，又考虑作业执行时间的调度算法是()

A.高响应比优先

B.短作业优先

C．优先级调度

D.先来先服务

68CAA在下列进程调度算法中，哪一个算法会对优先权进行调整（68作业调度算法从()队列中选取适当的作业投入运行A.执行

B.就绪

C.完成

D.后备()是指从作业提交给系统到作业完成的时间间隔A.周转时间

B.响应时间C.等待时间

D.运行时间下述作业调度算法中，()调度算法与作业的估计运行时间有关A.先来先服务

B.短作业优先C.均衡

D.时间片轮转69DAB作业调度算法从()队列中选取适当的作业投69采用资源剥夺法可解除死锁，还可以采用()方法解除死锁A.执行并行操作 B.撒消进程C.拒绝分配新资源D.修改信号量产生死锁的四个必要条件是：互斥、()、循环等待和不剥夺A.请求与阻塞B.请求与保持C.请求与释放D.释放与阻塞70BB采用资源剥夺法可解除死锁，还可以采用()70发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏()条件是不太实际的A.互斥B.不剥夺C.请求与保持D.循环等待银行家算法是一种()算法A.解除死锁B.避免死锁C.预防死锁D.检测死锁当进程数大于资源数时，进程竞争资源()会产生死锁A.一定B.不一定C.不可能D.以上答案都不对71ABB发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必71()优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变A.先来先服务B.静态C.动态D.短作业OS中，出现死锁指的是()A.计算机发生故障B.资源数少于进程数

C.若干进程因竞争资源而无限等待其他进程释放已占用的资源

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

3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度(略)3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除1第三章处理机调度与死锁3.1处理机调度的基本概念783.1处理机调度的基本概念处理机调度的概念采用一定的算法(方法、规则)，从就绪队列中选择一个进程，让CPU来执行它。调度的三个级别高级调度（作业调度）中级调度（与挂起状态有关）低级调度（进程调度）793.1处理机调度的基本概念处理机调度的概念2793.1.1高级、中级和低级调度高级调度批处理系统特有的调度(分时、实时没有)作用决定把后备队列中的哪些作业调入内存，并为其创建进程、分配资源，并将其插入到就绪队列。执行作业调度时，须作两个决定(考虑两个问题)：接纳多少作业——不易过多，也不能太少接纳哪些作业——取决于调度算法803.1.1高级、中级和低级调度高级调度380低级调度（进程调度）三种操作系统都必须有的调度作用决定把CPU分配给就绪队列中的哪个进程，具体分派CPU的操作由分派程序执行。两种调度方式非抢占方式抢占方式注：进程调度比较频繁，因此进程调度算法不能太复杂，以免占用太多CPU时间81低级调度（进程调度）481非抢占方式一旦将CPU分配给某进程，便让它一直运行，直到它完成或阻塞，才让另一个来执行可能引起调度的原因进程执行完毕，或因某事件不能执行下去提出I/O请求而暂停执行wait、block等原语优点实现简单、系统开销小，适用于大多数的批处理系统环境缺点难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果在要求比较严格的实时系统中，不宜采用82非抢占方式582抢占方式允许按照某种原则暂停正在执行的进程，让另一个来执行抢占的原则优先权原则短作业(进程)优先原则时间片原则83抢占方式683中级调度引入的目的提高内存利用率和系统吞吐量作用把暂时不运行的进程放到外存等待，留出内存给其他进程使用在外存上的进程称为“挂起状态”当这些进程又具备运行条件、且内存有空位时，便选择一些调入内存，进入就绪状态84中级调度78485处理机的三级调度8处理机的三级调度853.1.2调度队列模型仅有进程调度的调度队列模型86就绪队列阻塞队列CPU进程完成进程调度等待事件交互用户事件出现时间片完就绪状态的进程常组织成栈、树、无序链表分时系统中，常组织成FIFO队列来了一个新进程，便放到队尾，并按时间片执行3.1.2调度队列模型仅有进程调度的调度队列模型9就绪队列86具有高级调度和低级调度的调度队列模型87就绪队列阻塞队列CPU进程完成进程调度等待事件1事件1出现时间片完阻塞队列阻塞队列等待事件2等待事件n事件2出现事件3出现后备队列作业调度批处理系统具有高级调度和低级调度的调度队列模型10就绪队列阻塞队列CP87具有三级调度的调度队列模型88就绪队列就绪挂起队列CPU进程完成进程调度等待事件时间片完阻塞挂起队列阻塞队列事件出现后备队列作业调度挂起事件出现中级调度具有三级调度的调度队列模型11就绪队列就绪挂起队列CPU进程883.1.3选择调度方式和调度算法的若干准则主要取决于OS的类型和目标面向用户的准则周转时间短——批处理系统响应时间快——分时系统截止时间的保证——实时系统优先权准则——适用于三种OS系统面向系统的准则系统吞吐量高——批处理系统CPU利用率好各类资源的平衡利用893.1.3选择调度方式和调度算法的若干准则主要取决于OS的893.2调度算法调度的实质是一种资源分配调度算法的定义根据系统的资源分配策略所规定的资源分配算法调度算法的选择根据OS的类型和目标903.2调度算法调度的实质是一种资源分配1390先来先服务(FCFS)调度算法最简单的算法，可用于作业调度、进程调度基本思想谁先来，先为谁服务(类似食堂排队打饭)特点有利于长作业(进程)，不利于短作业(进程)因为长作业的带权周转时间短91先来先服务(FCFS)调度算法1491进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C(短作业)21101102100100D(长作业)31001022021991.9992长作业有利的例子进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时92短作业(进程)优先调度算法(SJF、SPF)

可用于作业调度、进程调度基本思想哪个估计运行时间最短，先运行哪个优点有效降低平均等待时间，提高系统吞吐量和FCFS相比，SJ(P)F中，平均周转时间、平均带权周转时间有明显改善缺点对长作业(进程)不利没考虑作业(进程)的紧急程度由于是估计的运行时间，所以不一定能真正做到短的优先93短作业(进程)优先调度算法(SJF、SPF)1693高优先权优先调度算法(FPF)目的照顾紧迫型作业，使之进入系统后能被优先处理两种类型非抢占式一旦选择了优先权最高的进程执行，直到它结束或阻塞后，才选另一个执行抢占式若出现优先权更高的，则让出CPU这样可更好的满足紧迫性FPF算法的关键优先权是静态的，还是动态的？如何确定进程的优先权？94高优先权优先调度算法(FPF)1794优先权类型静态优先权基本思想：创建进程时分配，保持不变确定优先权的依据进程类型：系统进程的>一般用户的进程对资源的需求：估计执行时间、内存需求少的，优先权高用户要求：根据用户的紧迫度、用户所付费用来确定优点：简单易行、系统开销小缺点：不精确,优先权低的可能长时间无法执行适用：要求不高的系统95优先权类型1895动态优先权基本思想随进程的执行或等待时间的增加而改变优先权低的等待一定时间后，优先权会提高规定当前执行的进程优先权随时间下降优点在抢占方式下，可防止长进程长期霸占CPU96动态优先权1996高响应比优先权调度算法动态优先权

优先权=(等待时间+要求服务时间)/要求服务时间

即

响应比=响应时间/要求服务时间由上可知等待时间相同，要求服务时间越短，优先权越高——有利于短作业要求服务时间相同，等待时间越长，优先权越高——相当于FCFS长作业的优先权可随等待时间增加而提高优点：短、长作业都考虑到了缺点：调度之前，须计算响应比，增加了系统开销97高响应比优先权调度算法2097基于时间片的轮转调度算法——分时系统早期的时间片轮转法系统将就绪进程按先来先服务原则，排成一个队列每次调度时，把CPU分配给队首进程，让它执行一个时间片时间片用完时，调度程序根据计时器发出时钟中断停止进程的执行，并将它插至就绪队列末尾然后，把CPU分配给就绪队列中新的队首进程，也让它执行一个时间片这样，可保证就绪队列中所有进程，均能获得一时间片的执行时间98基于时间片的轮转调度算法——分时系统2198多级反馈队列调度算法基本思想设多个就绪队列(按优先级划分)，优先权越高，获得的时间片越小新进程进入系统后，放入第一个队列，按FCFS原则等待。第i个时间片执行完后，便放入i+1队列尾仅当队列L1—Li空时，才从Li+1队列中调度进程——可以抢占99就绪队列1L1就绪队列2L2就绪队列nLnS1CPUS2S3优先级：L1>L2>Ln时间片：S1<S2<Sn新进程多级反馈队列调度算法22就绪队列1L1就绪队列299多级反馈队列调度算法的性能性能较好能较好满足各类用户的需求短进程可在一两个时间片内完成长进程也不必担心长期得不到处理100多级反馈队列调度算法的性能231003.3实时调度实时系统与其他系统的最大区别处理和控制的正确性不仅取决于计算的结果，还取决于计算和处理结果产生的时间实时系统具有的特点进程往往带有一定的紧迫度实时系统中，任务往往联系着一个截止时间所以，要引入一种新的调度——“实时调度”1013.3实时调度实时系统与其他系统的最大区别241013.3.1实现实时调度应具备以下几个条件提供必要的信息就绪时间：任务何时进入就绪状态的？截止时间：开始截止时间、完成截止时间处理时间：任务从开始执行到完成所需时间资源要求：需要哪些资源优先级：描述进程的紧迫度系统处理能力强如果CPU处理能力弱，可能导致某些任务不能及时被处理采用抢占方式硬实时任务的实时系统中，广泛采用抢占方式具有快速的切换机制保证任务能快速切换1023.3.1实现实时调度应具备以下几个条件251023.3.2实时调度算法的分类非抢占式调度算法应用于小型系统、要求不严的系统抢占式调度算法应用于要求严格的系统1033.3.2实时调度算法的分类26103非抢占式调度算法非抢占式轮转调度算法计算机控制多个相同的对象,为每个创建一个实时任务,排成轮转队列。用于工业生产的群控系统。非抢占式优先调度算法用于有一定要求的实时控制系统抢占式调度算法基于时钟中断的抢占式优先权调度算法时钟中断到来后才进行抢占，有较好的响应效果。用于大多数的实时控制立即抢占的优先权调度算法只要当前任务未处于临界区可立即抢占，可获得非常快的响应。用于发生外部中断的紧急任务104非抢占式调度算法27104105实时进程调度28实时进程调度1051063.3.3常用的几种实时调度算法最早截止时间优先(EDF,EarliestDeadlineFirst)算法根据开始截止时间确定优先级越早，优先级越高就绪队列按优先级排序可用于抢占、非抢占调度293.3.3常用的几种实时调度算法106107EDF算法用于非抢占调度方式开始截止时间：3早于2，4早于2

30EDF算法用于非抢占调度方式107108最低松弛度优先(LLF,LeastLaxityFirst)算法主要用于抢占调度方式根据任务紧急(或松弛)的程度，松弛度越低(紧急度越高)，优先级越高松弛度=完成截止时间–剩余运行时间-当前时间31最低松弛度优先(LLF,LeastLaxityFi108109A和B任务每次必须完成的时间例：两个周期性实时任务A、B，A：每20ms执行一次，执行时间为10msB：每50ms执行一次，执行时间为25ms32A和B任务每次必须完成的时间例：两个周期性实时任务A、109110在t=0ms时A1松弛度=20–10–0=10B1松弛度=50–25–0=25

故应先调度A1执行。在t=10ms时，

A2的松弛度=必须完成时间-剩余运行时间-当前时间=40-10-10=20B1的松弛度=必须完成时间-剩余运行时间-当前时间

=50-25-10=15

故应先调度B1执行。33在t=0ms时1103.5产生死锁的原因和必要条件3.5.1产生死锁的原因死锁的定义多个进程在运行过程中，因争夺资源而造成的一种僵局。当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。产生死锁的原因竞争资源由于系统中的资源不够进程用的，可能引起对资源的竞争而死锁进程间推进顺序非法进程在请求和释放资源时，顺序不当1113.5产生死锁的原因和必要条件3.5.1产生死锁的原111竞争资源引起死锁两个概念可剥夺资源进程获得该种资源后，还可被剥夺(CPU、内存)非可剥夺资源一旦获得，用完后才能被收回(打印机)112竞争资源引起死锁35112竞争非剥夺性资源113I/O设备共享时的死锁情况

竞争非剥夺性资源36I/O设备共享时的死锁情况113竞争非剥夺性资源临时性资源一个进程产生，被另一个用了一段时间后便无用的资源(如：消息)114进程之间通信时的死锁

竞争非剥夺性资源37进程之间通信时的死锁114115图3-14进程推进顺序对死锁的影响Rel(R1)Rel(R2)Req(R1)Req(R2)Req(R1)Req(R2)Rel(R1)Rel(R2)P2

P1

②①④③进程推进顺序不当引起死锁D不安全区38图3-14进程推进顺序对死锁的影响Rel(R1)R1153.5.2产生死锁的必要条件互斥条件进程在使用某资源时，不允许其他进程使用

请求和保持条件进程已保持至少一个资源，请求另一个资源时无法获得，便阻塞，但又不放弃已占用的资源不剥夺条件资源使用完前，不允许剥夺，直至其用完环路等待条件发生死锁，一定会有“进程-资源”环形链

注：只有四个条件同时满足时，才会死锁1163.5.2产生死锁的必要条件391163.5.3处理死锁的基本方法预防死锁设置限制条件，破坏四个条件中的一个或几个简单易行，但限制条件往往较严格，影响效率避免死锁动态分配资源时，防止系统进入不安全状态限制条件不必很苛刻，但实现较难检测死锁不用任何限制条件，也不检查系统是否进入安全区。允许发生死锁。可通过机制及时检测出死锁解除死锁撤销或挂起一些进程，以便回收一些资源，再将它们分给陷入死锁的其他进程1173.5.3处理死锁的基本方法401173.6预防死锁的方法基本思想使四个条件中的2、3、4不成立条件1(互斥条件)是设备固有的，所以不应限制，反而应加强1183.6预防死锁的方法基本思想41118摒弃“请求和保持”条件基本思想规定所有进程在开始之前，都必须一次性申请其在整个运行过程中所需的全部资源只要有一种资源不够，便全不分配优点简单易行，安全缺点资源浪费进程延迟执行(仅当全部资源都获得后，才能运行)119摒弃“请求和保持”条件42119摒弃“不剥夺”条件基本思想进程可以逐个申请资源，一旦申请的资源无法满足，立即释放已经保持的所有资源缺点复杂代价大(资源被迫释放，可能导致以前的工作无效)反复申请资源，可能使进程执行被无限推迟120摒弃“不剥夺”条件43120摒弃“环路等待”条件基本思想按类型给资源赋序号进程申请资源必须按序号递增次序提出如：输入机=1,打印机=2,磁带机=3,磁盘=4优点利用率、吞吐量明显改善缺点资源序号相对稳定，不利新设备加入进程使用资源次序和序号次序不同，浪费对用户编程不利121摒弃“环路等待”条件441213.6.2系统安全状态

安全状态定义系统能按某顺序(P1,P2,…，Pn)，为每个进程Pi分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成称〈P1,P2,…,Pn〉序列为安全序列如果系统无法找到这样一个安全序列，则称系统处于不安全状态——可能导致死锁避免死锁实质进行资源分配时，如何使系统不进入不安全状态1223.6.2系统安全状态45122123安全状态举例设有进程P1、P2和P3，及12台磁带机P1、P2、P3分别需要10、4、9台磁带机T0时刻，P1、P2和P3已分别获得5台、2台和2台，尚有3台未分配请问T0时刻是否是安全的？解答：实质是问，T0时刻是否存在一个安全序列进程最大需求已分配可用P1P2P31049522

3安全序列(P2,P1,P3)5101212346安全状态举例进程最大需求已分配可用123由安全状态向不安全状态的转换如果不按照安全序列分配资源，系统可能会由安全状态进入不安全状态。比如：P3又请求1台磁带机以后：124进程最大需求已分配可用P1P2P31049523

24不安全了！109

所以，尽管系统尚有可用的磁带机，也不能分配给P3由安全状态向不安全状态的转换47进程最大需求已1243.6.3利用银行家算法避免死锁提出者：Dijkstra最著名的避免死锁的算法基本思想当用户申请一组资源时，系统首先判断如果把这些资源分配出去，系统是否还处于安全状态。若是，就可以分配；否则，该申请暂不予满足1253.6.3利用银行家算法避免死锁48125126银行家算法中的数据结构可利用资源向量Available[1…m]

表示m种资源中每种可供使用的数量，初始值是系统中每类资源的全部数量Available［j］=K表示目前资源j有K个可供使用最大需求矩阵Max[1..n,1..m]表示n个进程中的每个进程对m种资源的最大需求量Max［i,j］=K表示进程i对资源j的最大需求量为K49银行家算法中的数据结构126已分配矩阵Allocation[1..n,1..m]

每种资源已分配给每个进程的数量Allocation［i,j］=K,进程i当前已获得资源j的数目为K需求矩阵Need[1..n,1..m]

每个进程还需要资源的数量Need［i,j］=K,表示进程i还需要K个资源j，才能执行完127已分配矩阵Allocation[1..n,1..m]50127数据结构的小结Available［j］：目前资源j可供使用的数量Max［i,j］：进程i需要资源j的最大数量Allocation［i,j］：进程i当前已获得资源j的数量Need［i,j］：进程i还需要多少资源j，才能执行完128所以，Need［i,j］=Max［i,j］-Allocation［i,j］

数据结构的小结51所以，Need［i,j］=Max［i,j128129银行家算法设向量Requesti[1...m]

如果Requesti［j］=K，表示进程Pi需要K个资源jPi申请资源时，OS如下进行检查：如果Requesti［j］≤Need［i,j］，执行下一步；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。如果Requesti［j］≤Available［j］，执行下一步；否则，表示尚无足够资源，Pi须等待。52银行家算法129130OS假设把资源分配给进程Pi，并作如下修改：

Available［j］:=Available［j］-Requesti［j］;Allocation［i,j］:=Allocation［i,j］+Requesti［j］;Need［i,j］:=Need［i,j］-Requesti［j］;执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才真正把资源分配给进程Pi；否则，本次假设的分配作废，恢复原来的资源分配状态，让进程Pi等待。53OS假设把资源分配给进程Pi，并作如下修改：130安全性算法作用查看是否存在一个安全序列算法设置两个数组向量①工作向量Work[1..m]OS可提供给进程继续运行所需的各种资源数量安全性算法初始时，Work:=Available;Finish[1..n]系统是否有足够的资源分配给进程，使之运行完成。初始时Finish［i］:=false;当有足够资源分配给进程i时，便令Finish［i］:=true131安全性算法54131从所有的进程中找到一个能满足下述条件的进程:Finish［i］=false;Need［i,j］≤Work［j］;若找到，执行步骤3;否则，执行步骤4执行以下两步修改Finish［i］∶=true;

Work［j］∶=Work［j］+Allocation［i,j］;

因为进程Pi获得所需的资源后，便可畅通无阻的执行完，并释放出已分配给它的资源，从而使系统里的可用资源增多。如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态132从所有的进程中找到一个能满足下述条件的进程:55132银行家算法举例五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示133银行家算法举例56133134T0时刻的安全性：57T0时刻的安全性：134P1请求资源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向量，由此形成的资源变化情况如图中的圆括号所示再利用安全性算法检查此时系统是否安全135P1请求资源58135136P1申请资源时的安全性检查存在安全序列：(P1，P3，P4，P0，P2)59P1申请资源时的安全性检查存在安全序列：(P1，P3，136P4请求资源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分配资源，并修改有关数据，如下图所示137P4请求资源60137138为P0分配资源后的有关资源数据已不能满足任何进程的需要，所以无法进入安全状态，此时不能分配资源61为P0分配资源后的有关资源数据已不能满足任何进程的需要1383.7死锁的检测与解除死锁的检测资源分配图139每类资源有多个时的情况3.7死锁的检测与解除死锁的检测62每类资源有多个时的情139死锁定理基本思想通过简化资源分配图,检测死锁基本方法不断寻找既不阻塞又不独立的进程结点Pi顺利时，Pi可获得所需资源，并执行完相当于，消去连接Pi的各条边，使之成为孤立结点死锁定理S为死锁状态的充分必要条件是，当且仅当S状态的资源分配图是不可完全简化的140死锁定理63140死锁的解除两种方法剥夺资源从其他进程剥夺足够资源给死锁的进程撤消进程（有两种方法）撤销全部死锁进程按某顺序逐个撤销，直到有足够资源为止策略撤销进程数目最小撤销进程所付代价最小，等等141死锁的解除64141小结三种级别的调度(高、中、低)调度和死锁的基本概念常用的调度算法死锁概念、产生的必要条件(四个条件)死锁的预防和避免方法银行家算法死锁的检测及解除142小结三种级别的调度(高、中、低)65142练习题避免死锁的一个著名的算法是(

)A.先入