第3章处理机调度与死锁

第三章

处理机调度与死锁3.1

处理机调度的基本概念3.2

调度算法3.3

实时调度(*)3.4产生死锁的原因和必要条件3.5死锁问题的解决方法低级调度中级调度高级调度高级调度提交收容外存就绪阻塞完成就绪执行阻塞内存3.1

处理机调度的基本概念高/中/低级调度调度队列模型调度方式和算法的选择准则3.1.1处理机调度的层次1、高级调度（作业调度/长程调度/接纳调度）多用于批处理系统，决定外存上处于后备队列中的哪些作业调入内存。每次调度时要考虑：

(1)接纳多少作业：取决于多道程序度

(2)接纳哪些作业：取决于调度算法作业调度运行频率低，几分钟一次系统规模运行速度2、低级调度（进程调度/短程调度）用来决定就绪队列中哪个进程应获得处理机，然后再由分派程序(Dispatcher)执行处理机分配操作。进程状态：Ready<－>Running引起进程调度的原因有：进程正常终止或异常终止正在执行的进程因某种原因而阻塞（I/O请求）分时系统中时间片用尽当有一个优先级更高的进程就绪（可抢占式）在进程通信中，执行中的进程执行了某种原语操作。如：wait/signal操作、Block原语、wakeup原语等运行频率高，几十毫秒一次，算法不能太复杂，以免占用太多的CPU时间。进程调度采用两种方式：①非抢占方式：一旦分配处理机，进程就一直执行，直至完成或发生某事件而被阻塞，不允许其它进程抢占处理机。优点：简单、系统开销小，适合大多数批处理系统缺点：无法满足紧急任务的需要，不适合实时系统②抢占方式：允许调度程序根据某原则，暂停正在执行的进程，将处理机重新分配。抢占原则：优先权原则、短作业(进程)优先原则、时间片原则3、中级调度（中程调度）目的：为了缓解内存紧张问题，将那些暂时不能运行的进程调到外存上去等待。当进程运行条件具备、且内存又空闲时，中级调度程序决定将外存上的哪些进程重新调入内存。进程状态：Ready<－>Readysuspend,Blocked<－>Blockedsuspend运行频率介于高级调度和低级调度之间。3.1.2调度队列模型仅具有进程调度的调度队列模型就绪队列阻塞队列CPU时间片完交互用户进程调度进程完成等待事件事件发生……具有高、低两级调度的调度队列模型就绪队列阻塞队列CPU时间片完作业调度进程调度进程完成等待事件1阻塞队列阻塞队列等待事件2等待事件n事件1发生事件2发生事件n发生后备队列

具有高、低、中三级调度的调度队列模型就绪队列挂起就绪队列CPU时间片完作业调度进程调度进程完成事件出现阻塞队列挂起等待事件中级调度事件发生后备队列挂起阻塞队列挂起3.1.3调度方式和算法的选择准则面向用户的准则周转时间短——评价批处理系统响应时间快——评价实时，分时系统截止时间保证——评价实时系统优先权准则——三种系统中皆适用公平性原则——分时系统面向系统的准则系统吞吐量高——评价批处理系统处理机利用率好——针对大中型系统各类资源的平衡利用——对大中型系统周转时间(通常作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一)：

是指从作业被提交系统开始，到作业完成为止的这段时间间隔。包括四部分：等待作业调度时间(高级调度)等待进程调度时间(低级调度)执行时间进程等待I/O操作完成时间

平均周转时间：

ti:作业周转时间，tci：作业完成时间，tsi:作业提交（到达）时间ti=tci-tsi带权周转时间：

平均带权周转时间：

tr:作业实际运行时间响应时间(用来评价分时系统的性能，选择分时系统中进程调度算法的重要准侧之一)：从用户通过键盘提交一个请求开始直至系统首次产生响应为止的时间。

响应时间包括三部分时间：从键盘输入的请求信息传送到处理机的时间、处理时间、响应信息回送终端的时间。3.2

调度算法先来先服务短作业（进程）优先高优先权先调度时间片轮转多级反馈队列1、先来先服务（FCFS）可用于作业调度和进程调度进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D3100周转时间=完成时间–

到达时间带权周转时间=周转时间/服务（运行）时间0111011011021022021100100199111001.99优缺点：实现简单有利于长作业（进程），不利于短作业（进程）。有利于CPU繁忙型作业，不利于I/O繁忙型作业。2、短作业/进程优先（SJF/SPF）短作业优先（SJF）从后备队列中选择估计运行时间最短的作业，调入内存运行。短进程优先（SPF）从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。直到运行完成，或发生某事件而被阻塞，进程才会让出处理机——非抢占式。优点：有效地降低了作业的平均等待时间，提高系统的吞吐量。缺点：对长作业不利，有可能长期不被调度。完全没考虑作业的紧迫程度（某些特殊的）。用户做出的估计时间带有很大的主观性。2.259133.5141844E3.216182101252C2.678926731B1.5365.5111423D2.11带权周转时间84周转时间4完成时间SJF2.81带权周转时间94周转时间4完成时间FCFS4服务时间0到达时间平均A进程名

作调业度情算况法3、高优先权优先调度算法（HPF）作业调度：从后备队列中选择若干个优先权最高的作业装入内存。进程调度：把处理机分配给就绪队列中优先权最高的进程非抢占式优先权算法：一旦分配处理机给优先权最高的进程，进程便一直执行直至完成，或发生某事件而被阻塞。主要用于批处理系统和实时性要求不严的实时系统。抢占式优先权算法：一旦系统中出现一个新的就绪进程Pi，就将其优先权与正在执行的进程Pj进行比较，如果Pi>Pj，那么就做进程切换，使Pi投入运行。常用于要求严的实时系统，以及对性能要求高的批处理和分时系统中。关键：优先权的确定优先权类型一：静态优先权在进程创建时确定的，在进程整个运行期间保持不变。通常根据进程类型、进程对资源的要求、用户要求来确定进程优先权简单易行，但不够精确，可能出现优先权低的进程长期得不到执行的情况。t(等待)优先权t(运行)优先权优先权类型二：动态优先权在进程创建时创立的优先权，可随进程的推进或等待时间的增加而改变。如等待时间长，优先权升高。高响应比优先调度算法（FCFS和SJF的折中）为每个进程引入动态优先权，随着等待时间增加优先权提高。W1+T+WT=TRp=响应时间作业估计运行时间=T——作业估计运行时间（要求服务时间）W——作业在后备队列中的等待时间作业等待时间相同，则作业要求的服务时间愈短，优先权愈高，因而有利于短作业。当要求的服务时间相同，则等待时间愈长，优先权愈高，因而实现了先来先服务。长作业也能保证得到执行。

例2：下表说明了采用响应比高者(HRRN)优先调度算法时上述作业组合运行的情况。表中单位：小时，并以十进制计作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.0028.500.5039.000.1049.500.20平均周转时间t=1.625平均带权周转时间w=5.6758.0010.0010.0010.1010.1010.6010.6010.802.002.101.101.3014.2116.5采用HRN算法时，这四个作业的执行次序为：J1，J3，J2，J4。之所以会是这样的次序，是因为该算法在一个作业运行完时要计算剩下的所有作业的响应比，然后选响应比高者去运行。例如，当J1结束时，J2、J3、J4的响应比计算如下：

rp2=1+作业等待时间／执行时间

=1+(10.00-8.50)／0.5 =1+3rp3=1+作业等待时间／执行时间

=1+(10.00-9.00)／0.10 =1+10rp4=1+作业等待时间／执行时间

=1+(10.00-9.50)／0.20 =1+2.5从计算结果可看出，J3的响应比最高，所以让J3先运行。当J3运行结束以及以后选中的作业运行结束时，都用上述方法计算出当时各作业的响应比，然后选出响应比高的去运行。4、时间片轮转RR特别适用于分时系统的抢占方式调度算法。系统将所有的就绪进程按FIFO原则排成一个队列，将CPU分配给队首进程，执行一个时间片。在时间片内进程未完，则插入就绪队列未尾，CPU交给下一个进程。时间片选择问题：固定时间片、可变时间片与时间片大小有关的因素：系统响应时间、就绪进程个数、CPU能力时间片的大小对系统性能有很大影响：时间片小，意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统开销；时间片太长，则RR算法退化为FCFS算法，无法满足短作业和交互式用户的需求；一个较为可取的时间片大小是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间。3.2513173.25131744E2.259113.5141642C2673.67111231B5101336923D2.71带权周转时间8.44周转时间4完成时间RRq=43.433.75带权周转时间11.815周转时间15完成时间RRq=14服务时间0到达时间平均A进程名

作时业间情片况

5、多级反馈队列多级反馈队列调度算法的思想：设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；在优先权愈高的队列中，为每个进程设置的执行时间片就愈小。新创建的进程，首先被挂到第一优先级的队列，然后按FCFS原则排队等待调度。当轮到其执行时，如它能在设定时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列的末尾，……，最后一级队列采用时间片轮转法；仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推……；如果有优先权高的新进程到来，那么将抢占低级进程的处理机。……多级反馈队列调度算法示意图CPU时间片完进程调度进程完成就绪队列一就绪队列二就绪队列三就绪队列n时间片完时间片完时间片小－－－－大优先级高－－－－低多级反馈队列调度算法的性能多级反馈队列调度算法不必事先知道各种进程所需的执行时间，能较好地满足各种类型用户(进程)的需要，是目前公认的一种较好的进程调度算法。终端（交互）型作业用户短批处理作业用户长批处理作业用户6、基于公平原则的调度算法保证调度算法保证处理机分配的公平性。如果系统有n个相同类型的进程同时运行，为公平起见，须保证每个进程获得相同的处理机时间1/n。公平共享调度算法调度的公平性主要针对用户而言，使每个用户能获得相同的处理机时间。3.5

产生死锁的原因和必要条件产生死锁的原因产生死锁的必要条件1、产生死锁的原因死锁（Deadlock）：是指两个或两个以上的进程在运行过程中，因争夺资源而造成的一种互相等待（谁也无法再继续推进）的现象，若无外力作用，它们都将无法推进下去。例如，系统有5台打印机，进程A需要4台，进程B需要4台，进程AB并发执行，A已经占3台，B已经占2台，此时陷入死锁。产生死锁的原因：竞争资源进程间推进顺序非法1、竞争资源引起进程死锁：可剥夺性资源：CPU、RAM等；非剥夺性资源：打印机、磁带机等；竞争非剥夺性资源：系统中配备的非剥夺性资源的数量不能满足诸进程运行的需要时，会使进程因争夺资源而陷入僵局。打印机P1磁带机P2永久性资源：打印机临时性资源：进程通信中的消息、数据等竞争临时性资源：P1Request(s3);Release(s1);P2Request(s1);Release(s2);P3Request(s2);Release(s3);s1P1s2P2P3s3P1Release(s1);Request(s3);P2Release(s2);Request(s1);P3Release(s3);Request(s2);2、进程间推进顺序不当引起死锁进程推进顺序合法——不会导致死锁进程推进顺序非法——可能会导致死锁顺序合法s1P1s2P2P3s3顺序非法s1P1s2P2P3s3请求R2请求R1请求R1请求R2释放R1释放R2释放R2释放R1ttP1进程P2进程不安全区2、产生死锁的必要条件互斥条件一个资源一次只能被一个进程使用。请求和保持条件（部分分配）保留已经得到的资源，还要求其它的资源。不可剥夺条件（不可抢占）资源只能被占有者释放，不能被其它进程强行抢占。环路等待条件（循环等待）系统中的进程形成了环形的资源请求链。打印机P1磁带机P23.6死锁问题的解决方法预防死锁避免死锁检测与解除死锁1、预防死锁预防：通过设置某些限制条件，破坏导致死锁的四个必要条件之一。“互斥条件”——由资源的性质决定。摒弃“请求和保持”条件------一次性预分配法在开始运行前（创建时），一次性分配给进程它所需的“全部”资源。简单易实现，安全性高；资源浪费。摒弃“不可剥夺”条件------先释放后申请分配法当进程有新的资源请求时，如果得不到满足，要先释放原先占有的资源，待以后重新申请。等价于此进程“被剥夺”了已经占有的资源。实现比较复杂，系统代价很高。摒弃“循环等待”条件------资源顺序分配法把系统资源按类型排序，进程要按照资源的序号递增的次序提出资源申请。较上述两种方法的综合性能要好；但系统配置资源的序号要稳定，固定的访问顺序不一定合理。例如：

进程A占有3号资源，现在又申请5号资源——占有资源号小于申请资源号，此申请可以满足。进程B占有5号资源，现在又申请3号资源——由于5>3，所以此申请不能满足。进程B要想得到3号资源，必须先放弃5号以及所有编号比3大的资源。例：哲学家就餐——给哲学家和筷子编号0－4

信号量定义：semaphorechopstick[4]={1,1,1,1,1};

第i(i=0,1,2,3)位哲学家活动描述：第4位哲学家活动描述:while(true){while(true){wait(chopstick[i]);wait(chopstick[0]);wait(chopstick[(i+1)]);wait(chopstick[4]); …………eating;eating; …………signal(chopstick[i]);signal(chopstick[0]);signal(chopstick[(i+1)]);signal(chopstick[4]); …………thinking;thinking;}}2、避免死锁避免死锁的方法：在资源的动态分配过程中，用某种方法防止系统进入不安全状态。安全状态：系统能按某种进程顺序(P1,P2,…,Pn)

，来为每个进程Pi分配其所需资源，直至最大需求，使每个进程都可以顺利完成。（称(P1,P2,…,Pn)为安全序列）反之，则系统处于不安全状态。不安全状态不一定发生死锁，但死锁一定属于不安全状态。安全状态进程最大需求已分配系统可用P1P2P310495223系统资源总数：12不32利用银行家算法避免死锁银行家算法的实质就是要设法保证系统动态分配资源后仍然保持安全状态，从而避免死锁的发生。要求进程预先告知自己的最大资源需求，并且假设系统拥有固定的资源总量。数据结构：可用资源向量Available

Available[j]=k

最大需求矩阵MaxMax[i,j]=k

分配矩阵AllocationAllocation[i,j]=k

需求矩阵NeedNeed[i,j]=k

资源请求向量RequestiRequesti[j]=k安全性算法：工作向量Work、Finish1、Requesti[j]<=Need[i,j]，则转向步骤2；否则出错2、Requesti[j]<=Available[j]，则转向步骤3；否则进程i等待3、系统试探着把资源分给进程i；Available[j]=Available[j]-Requesti[j]；Allocation[i,j]=Allocation[i,j]+Requesti[j]Need[i,j]=Need[i,j]-Requesti[j]4、执行安全性算法，检查分配后是否处于安全状态，若安全将资源分配；否则将试探分配作废，恢复原来状态，进程i等待银行家算法1、设置2个向量Work=Available，Finish[i]=false2、找满足条件的进程i：Finish[i]=falseNeed[i,j]<=Work[j]，若找到执行步骤3，否则执行步骤43、当进程Pi获得资源后，顺利执行至完成，并释放出分配给它的资源Work[j]=Work[j]+Allocation[i,j]；Finish[i]=true；gotostep24、如果所有进程Finish[i]=true,处于安全状态，否则处于不安全状态。安全性算法MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200302211002743122600011431332资源总数

1057进程资源某时刻资源分配情况ABCWork＋AllocationABCABCABCFinishAllocationNeedWork进程资源安全序列302020230(2)若此时P1请求资源，发出请求向量Request1(1,0,2)系统按银行家算法进行检查：

Request1(1,0,2)<=Need1(1,2,2)

Request1(1,0,2)<=Available(3,3,2)

系统先假定可为P1分配资源，并修改向量的值。

再利用安全性算法检查此时系统是否安全。

ABCWork＋AllocationABCABCABCFinishAllocationNeedWork进程资源安全序列P1332122200532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057trueP1230020302532trueP3532011211743trueP4743431002745trueP0745743010755trueP27556003021057trueABCABCABCABC332资源总数

1057743122600011431010200302211002753322902222433P0P1P2P3P4AvailableNeedAllocationMax进程资源某时刻资源分配情况302020230（3）若此时P4请求资源，发出请求向量Request4(3,3,0)系统按银行家算法进行检查：

Request4(3,3,0)<=Need4(4,3,1)

Request4(3,3,0)>Available(2,3,0)

因此，让P4等待。ABCABCABCABC332资源总数

1057743122600011431010200302211002753322902222433P0P1P2P3P4AvailableNeedAllocationMax进程资源某时刻资源分配情况302020230（4）若此时P0请求资源，发出请求向量Request0(0,2,0)系统按银行家算法进行检查：

Request0(0,2,0)<=Need0(7,4,3)

Request0(0,2,0)<=Available(2,3,0)

系统暂时先假定可为P0分配资源，并修改有关数据进行安全性检查，Available(2,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。0307232103、检测与解除死锁当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段。为此，系统必须：（1）保存有关资源的请求和分配信息；（2）提供—种算法，以利用这些信息来检测系统是否已进入死锁状态。死锁的检测方法资源分配图的化简，检查是否存在循环等待。周期性检测进程阻塞的时间，当超过限度；或CPU利用率降到某个值时则视为死锁。资源分配图凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e={pi,rj}是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e={rj,pi}是资源分配边，由资源rj指向进程pi,它表示把一个单位的资源rj分配给进程pi。死锁定理把资源分配图加以简化的方法，来检测系统处于S状态时，是否为死锁状态。简化方法如下：在资源分配图中，找出—个既不阻塞又非独立的进程结点pi。在顺利情况下，pi可获得所需资源而继续执行，直至运行完毕，再释放其所占有的全部资源。这相当于消去pi所有的请求边和分配边，使之成为孤立的结点。pi释放资源后．便可使p2获得资源而继续运行，直到p2完成后又释放出它所占有的全部资源。在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。S为死锁状态的充分条件是，当且仅当S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理。P1P2r1r2资源分配图的化简过程：死锁检测中的数据结构可利用资源向量Available,表示m类资源中每一类资源的可用数目；把不占用资源也无资源请求的进程记入L表中，进程集合即Li∪L从进程集合中找到一个Requesti≤Work的进程，将其资源分配图简化，增加Work=Work+Allocationi

,将其记入L若不能把所有进程都记入L表中，则系统状态S的资源分配图不可完全简化，系统将发生死锁。死锁检测中的数据结构Work∶=Available;L∶={Li|Allocationi=0∩Requesti=0}forallLiLdobeginforallRequesti≤WorkdobeginWork∶=Work+Allocationi;Li∪L;endenddeadlock∶=﹁(L={p1,p2,…,pn});将进程从死锁状态中解脱出来。剥夺资源：从其他进程剥夺足够的资源给死锁进程，以解除死锁状态。撤销进程：撤销全部死锁进程或者选择被撤进程代价最小的。终止所有死锁进程，代价较大逐个终止进程，每终止一个进程，都需要用死锁检测算法确定系统死锁是否已经解除。死锁的解除第三章小结进程调度、三种调度队列模型调度算法：FCFS、SJF/SPF、HPF/HRRN、RR(平均)周转时间、(平均)带权周转时间死锁、产生死锁的必要条件安全序列银行家算法第三章作业1、设系统中有4个进程P1，P2，P3和P4.在某一时刻系统状态如下：最大需求量已分配资源量P162P274P332P42