处理机调度与死锁

第三章处理机调度与死锁3.1处理机调度的基本概念3.2作业调度3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除3.1处理机调度的基本概念3.1.1高级、中级和低级调度

处理器调度分为三级：高级调度（作业调度）（长程调度）中级调度（中期调度）低级调度（进程调度）（短程调度）按某种原则从后备状态挑选作业调入内存运行为作业创建进程为选中作业分配资源1.高级调度(LowLevelScheduling)2.中程调度决定哪些作业允许参于竞争处理机资源。作用：起到短期调整系统负荷，以平顺系统。方式：“挂起”，“解挂”。3.低级调度按某种原则将处理机分配给就绪进程。进程调度属操作系统内核，执行频率很高。进程调度是最基本的一种调度，它可以采用非抢占方式或抢占方式。

1)非抢占方式(Non-preemptiveMode)在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：①正在执行的进程执行完毕，或因发生某事件而不能再继续执行；②执行中的进程因提出I/O请求而暂停执行；③在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。3.1.2调度队列模型1.仅有进程调度的调度队列模型仅具有进程调度的调度队列模型2.具有高级和低级调度的调度队列模型具有高、低两级调度的调度队列模型就绪队列的形式。

(2)设置多个阻塞队列。图3-2示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。3.同时具有三级调度的调度队列模型具有三级调度时的调度队列模型就绪队列进程调度CPU就绪挂起队列中级调度阻塞挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.2.1作业调度的职能记录已进入系统的作业情况JCB调度算法：按照某种调度算法从后备状态挑选作业运行。运行准备：为选中作业创建进程，分配主存和外设。结束善后处理：收回资源，输出必要信息。作业进入后备状态建立作业退出系统时撤消3.2作业调度3.2.2作业控制块作业存在唯一标志作业调度的依据记录作业的有关信息，反映作业运行情况内容进入系统时建立退出系统时撤消作业名资源要求资源使用情况类型说明状态3.2.3调度性能的衡量平均周转时间：作业kTk=Tck-Tsk=T等待+T运行平均周转时间T=1/nTk带权周转时间：作业kWk=Tk/TRk

平均带权周转时间W=1/nWkK=1nK=1

nTck：作业K完成时间Tsk：作业K提交时间TRk：作业K运行时间3.2.4选择调度方式和调度算法的若干准则1.面向用户的准则

周转时间短。响应时间快。(3)截止时间的保证。(4)优先权准则。

2.面向系统的准则

系统吞吐量高。(2)处理机利用率好。(3)各类资源的平衡利用。

3.3调度算法

先进先服务调度算法短作业优先调度算法高优先权优先调度算法最高响应比优先时间片轮转调度算法最短剩余时间优先调度算法均衡法多级反馈队列调度算法3.3.1先来先服务调度算法其原则按照作业到达系统或进程进入就绪队列先后次序来选择。FIFO是一种非抢占算法。例题

进程到达时间服务时间优先数10322265344346565821作业1作业2作业3作业4作业5039131820T=1/5（3+7+9+12+12）=8.60W=1/5（1+1.17+2.25+2.40+6.00）=2.56

特点:吞吐量不定、耗费最小、无饥饿、对偏重于I/O进程不利，响应时间很高，尤其是进程执行时间变化很大时3.3.2短作业(进程)优先调度算法

短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。作业1作业2作业5作业3作业4039111520T=1/5（3+7+11+14+3）=7.60W=1/5（1+1.17+2.75+2.80+1.50）=1.84SJ(P)F调度算法也存在不容忽视的缺点：(1)该算法对长作业不利，更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。特点：吞吐量高、能提供较好的响应时间，对长进程不利、可能产生饥饿3.3.3高优先权优先调度算法选择优先级高的进程和作业作为调度对象。按抢占与否优先数可分：非抢占的优先调度算法可抢占的优先调度算法按静态，动态优先数可分：静态优先数动态优先数

1）非抢占式优先权算法在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。2)抢占式优先权调度算法在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi＞Pj,则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

3)静态优先权静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，0~7或0~255中的某一整数，又把该整数称为优先数。只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。确定进程优先权的依据有如下三个方面：进程类型。(2)进程对资源的需求。(3)用户要求。4)动态优先权动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。非抢占的优先调度作业1作业2作业4作业3作业5039141820T=1/5（3+7+14+8+12）=8.8W=1/5（1+1.17+3.5+1.6+6）=2.853.3.4高响应比优先调度算法

优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：(1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。作业1作业2作业3作业5作业4039131520T=1/5（3+7+9+14+7）=8.00W=1/5（1.00+1.17+2.25+2.80+3.5）=2.14最高响应比是一种非抢占算法3.3.5时间片轮转调度算法把CPU的时间分割成时间片，处于就绪状态的进程轮流获得时间片。时间片轮转调度算法是抢占算法。其调度算法的性能取决于时间片Q。Q=4（时间片为4）作业1作业2作业3作业4作业2作业5作业40371115171920T=1/5（3+15+7+14+11）=10.00W=1/5（1.00+2.50+1.75+2.80+5.50）=2.71Q=1（时间片为1）12123243254325

4324402345678910111213141516171819T=1/5（4+16+13+14+7）=10.8W=1/5（1.33+2.67+3.25+2.80+3.50）=2.71RR算法主要用于分时系统或事务处理系统，可保证对各终端用户的及时响应。但它对偏重CPU的进程和偏重I/O的进程有不同的处理结果，可以采用虚拟时间片轮转(VRR)策略来避免这个问题。新加入的特性是附加一个FCFS策略队列来收集从I/O等待中释放的进程。特点：吞吐量在时间片小的时候可能很低，对所有进程公平对待、特别是短进程提供好的响应时间，无饥饿3.3.6最短剩余时间优先调度算法最短剩余时间：从作业当前运行到完成所需时间。最短剩余时间优先调度是抢占算法。用于分时系统其轮转时间最优作业1作业2作业3作业5作业2作业40348101520T=1/5（3+13+4+14+2）=7.20W=1/5（1.00+2.17+1.00+2.80+1.00）=1.59

特点：吞吐量高、能提供较好的响应时间，对长进程不利、可能产生饥饿3.3.7均衡法作业分类A——I/O量多B——比较适中C——占用CPU时间A、C按一定比列搭配。B类不受限制。3.3.8多级反馈队列调度算法系统中有多个就绪队列各级就绪队列具有不同的时间片各级队列均按FIFO原则排队调度方法：首先调度优先级高的进程，当优先级高的进程为空，才调度下一级。Q=1（每级反馈队列每一级时间片为1）1121324354523423424201234567891011121314151617181920T=1/5（4+18+12+13+3）=10.00W=1/5（1.33+3.00+3.00+2.60+1.50）=2.29Q=2**N（每级反馈队列每一级时间片以2幂次方递增）11213224533445222344T=1/5（4+15+14+14+6）=10.06W=1/5（1.33+2.50+3.50+2.80+3.00）=2.6301234567891011121314151617181920

特点：吞吐量不定，消耗可能高、有利于偏重I/O进程，可能会饥饿多级反馈队列调度算法的性能

终端型作业用户。(2)短批处理作业用户。(3)长批处理作业用户。3.4实时调度3.4.1实现实时调度的基本条件1.提供必要的信息就绪时间。(2)开始截止时间和完成截止时间。(3)处理时间。(4)资源要求。(5)优先级。2.系统处理能力强

3.采用抢占式调度机制4.具有快速切换机制(1)对外部中断的快速响应能力。(2)快速的任务分派能力。3.4.2实时调度算法的分类1.非抢占式调度算法非抢占式轮转调度算法。(2)非抢占式优先调度算法。

非抢占时间片轮转调度

非抢占式优先权调度

2.抢占式调度算法基于时钟中断的抢占式优先权调度算法。(2)立即抢占(ImmediatePreemption)的优先权调度算法。基于时钟抢占的优先权抢占调度

立即抢占优先权调度3.4.3常用的几种实时调度算法最早截止时间优先即EDF(EarliestDeadlineFirst)算法

根据任务的开始截止时间或完成截止时间来确定任务的优先级，截止时间越早，其优先级越高最早截止时间优先调度算法有抢占式和非抢占式1）非抢占式调度用于非周期性实时任务2）抢占式调度方式用于周期实时任务假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。进程到达时间执行时间完成期限进程到达时间执行时间完成期限A101020B102550A2201040B25025100A3401060A4601080A58010100

B1A1A2A30102030405060708090100B2A4A5A1期限A2期限A3期限A4期限A5期限B1期限B2期限B1期限B2期限0102030405060708090100A1B1A2B1A3B2A1期限A2期限A3期限A4期限A5期限B1误期A4B2A5B固定优先级（A优先级高，且可抢占）B1期限B2期限0102030405060708090100B1A2A3B2A5固定优先级（B优先级高）A1期限A2期限A3期限A4期限A5期限A1误期A4误期B1期限B2期限0102030405060708090100A1B1A2B1A3BA4B2A5A1期限A2期限A3期限A4期限A5期限使用完成期限最早期限调度都能完成2.最低松弛度优先即LLF(LeastLaxityFirst)算法该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式A和B任务每次必须完成的时间A每隔20MS执行一次，执行时间为10MSB每隔50MS执行一次，执行时间为25MS

松弛度=必须完成时间-其本身的运行时间-当前时间

利用ELLF算法进行调度的情况t1A1(10)10203040506080t0t1=0B1(15)t2t370A2(10)A3(5)A4(10)t4t5t6t7t8B1(5)B2(20)B2(10)3.5产生死锁的原因和必要条件3.5.1死锁问题的提出1.死锁的定义死锁是指计算机系统和进程所处的一种状态。常定义为：在系统中的一组进程，由于竞争系统资源或由于彼此通信而永远阻塞，我们称这些进程处于死锁状态。例1银行借款假定某行有一笔法郎可供一批顾客借用，并假定：每个顾客预知他的最大借款总额，且不超过银行拥有可用资金总和。每次借款以一法郎为单位。每当顾客提出借款请求，银行可立即给予，或让顾客等一段时间。只有当顾客达到他的预定最大借款额时，他才在有限时间一次归还。死锁的产生：当各顾客借款总额之和大于银行可借用资金总和，而每顾客都未达到他的预定最大借款额。安全状态：如果在某时刻，银行有可能使它当时的所有的顾客在以后有限时间内完成全部成交，则此刻的状态是安全。不安全状态：永远不具有成交的可能，则为不安全。

C2P4（4）Q2（1）R2（7）C4P4（4）R2（7）C8R2（7）C10安全状态C1P4（4）Q2（1）R3（6）C3P4（4）R3（6）

不安全状态C：借款总额，P，Q，R：顾客例2相同类型资源假设内存有M个页面，N个进程，这里M，N满足2MN，如果分配和回收以页为单位，且每个进程以如下方式申请和释放资源。

申请一页申请一页释放一页释放一页死锁的产生：各进程的执行次序轮转R1R2R3P1P2P3P4M=3，N=4框：资源圈：进程圈框：分配边框圈：请求边例3：不同类型资源假定系统有N种外部设备R1，R2•••RN，系统又有N个进程P1，P2•••PN，它们以这种方式要求资源。P1：申请R1申请R2释放R1释放R2P2：申请R2申请R3释放R2释放R3PN：申请RN申请R1释放RN释放R1•••

死锁的产生：各进程的执行次序轮转P3R1

R2P2P1R32.产生死锁的原因

(1)竞争资源。(2)进程间推进顺序非法。(1)竞争资源引起进程死锁

资源：可以引起一个进程进入等待状态的事物可抢占资源、不可抢占资源共享资源、独享资源可重用资源(永久)、消耗性资源(临时)（2）进程推进顺序不当引起死锁进程推进顺序合法图3-14进程推进顺序对死锁的影响进程推进顺序非法若并发进程P1和P2按曲线④所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1,P2保持了资源R2,系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2:Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。3.产生死锁的必要条件互斥条件(2)请求和保持条件(3)不剥夺条件(4)环路等待条件3.5.2处理死锁的基本方法预防死锁。(2)避免死锁。(3)检测死锁。(4)解除死锁。

3.6预防死锁

通过设置某些限制条件，以破坏产生死锁的必要条件一个或几个，来防止死锁。预防死锁是一种较可取的方法，但资源的利用率较低。3.6.1摒弃“互斥条件”条件互斥是正确使用非共享资源的唯一手段。故不能通过取消互斥来预防死锁。3.6.2摒弃“请求和保持”条件

采用资源静态分配：每个进程执行前，一次分配其所有资源允许进程仅当自己未占有资源时才申请资源。例1：如果有这样进程，它从读卡机中拷贝磁盘文件，排序磁盘文件，然后将结果打印在打印机上，并将起拷贝到磁带。按第一种制约：在进程运行前。为其分配所有资源，读卡机，磁盘文件，打印机，磁带机按第二种制约：先申请读卡机，磁盘文件释放两者申请磁盘文件，打印机释放两者申请磁盘文件，磁带机释放两者。3.6.3摒弃“不剥夺”条件适用于状态容易保护，稍后又容易恢复的资源。如CPU，内存。3.6.4摒弃“环路等待”条件为使“循环等待”条件不满足，我们把所有资源按类型进行排队，并赋予不同的编号。

每个进程

释放按序号递减次序进行申请按序号递增次序进行

优点：资源的申请与分配逐步进行，比预分配策略的资源利用率高；缺点：严格限制资源的顺序性，不允许增加资源请求在使用资源的顺序与系统规定不一致时，资源利用率降低；不能抢占。

3.7死锁的避免和银行家算法

3.7.1安全状态在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。所谓安全状态，是指系统能按某种进程顺序(P1,P2,…，Pn)(称〈P1,P2,…,Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。3.7.2利用银行家算法避免死锁1.银行家算法中的数据结构

Resource:一个长度为m向量,表示系统拥有的资源数目Available：一个长度为m向量，表示每类资源的可用数目如果Available[j]=k，表明Rj类资源有k个。Max：一个m×n矩阵，定义每个进程的最大资源需求数如果Max[i,j]=k,表示进程i需要Rj类资源有k个。Allocation：一个m×n矩阵，定义当前分配给每个进程每类资源的数目。如果Allocation[i,j]=k，则表示进程i获得Rj类资源有k个。Need：一个m×n矩阵，表示每个进程还需多少资源。如果

Need[i,j]=k，表示进程i还需要Rj类资源有k个。2.银行家算法设：Requesti是进程Pi的请求向量当Pi发出资源请求后，系统按如下步骤进行检查：如果Requesti

Needi则goto2,否则认为出错。如果Requesti

Available则goto3，否则表示无足够资源，Pi等待。系统进行试探分配，并求该相应数据结构数据

Available：=Available-RequestiAllocationi：=Allocationi+RequestiNeedi：=Needi-Requesti系统执行安全性算法：安全，把资源分配给Pi，否则，Pi等待。3.安全性算法设Work和Finish是长度分别为m,n的向量初试值Work：=Available，Finishi：=False（所有）从进程集合中找到一个能满足下列条件的进程

a.Finishi=Falseb.Needi

Work如找到goto3否则goto4

当进程Pi

获得资源后，顺利执行，直至完成，并释放分配给它的资源。Work：=Work+AllocationiFinishi：=Truegoto2如果所有进程的Finishi=True则表示系统安全，否则为不安全。4.银行家算法之例假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。图3-15T0时刻的资源分配表(1)T0时刻的安全性：图3-16T0时刻的安全序列(2)P1请求资源：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向量，由此形成的资源变化情况如图3-15中的圆括号所示。④再利用安全性算法检查此时系统是否安全。图3-17P1申请资源时的安全性检查(3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)Available(2,3,0)，让P4等待。(4)P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。图3-18为P0分配资源后的有关资源数据3.8死锁的检测与解除3.8.1死锁的检测1.资源分配图(ResourceAllocationGraph)图3-19每类资源有多个时的情况