调度与死锁-课件

第4章调度与死锁本章要点●调度类型与准则

●调度算法

●死锁的预防与避免

●死锁的基本概念

●死锁的检测与解除

●4.1调度类型与准则调度类型●高级调度●低级调度●中级调度调度的层次高级调度又称作业调度、宏观调度任务：决定将外存上后备队列中的哪些作业调入内存。调度工作决定接纳多少作业：取决于多道的程度，即内存允许放多少个作业。接纳哪些作业：有调度算法决定。适用于批处理系统提交SPOOLING输入作业调度作业调度SPOOLING输出图

作业状态转换图后备退出完成活动空间阻塞运行就绪调度的层次低级调度又称进程调度、微观调度任务：决定就绪队列中的哪些进程将获得处理机。调度方式非剥夺式剥夺式抢占原则时间片优先权进程长短适用于分时、实时、批处理系统I/O(完成)中断申请I/O服务I/O完成调度时间片到自愿性中断阻塞队列就绪队列时钟中断就绪阻塞运行磁盘调度的层次中级调度又称对换程序主要作用：内存和外存对换区之间进行进程对换，以解决内存紧张问题。进程调度方式非剥夺方式（非抢占方式）进程调度基本方式可分为非抢占和抢占方式：

进程被选中就一直运行下去（不会因为时钟中断而被迫让出CPU），直至完成工作、自愿放弃CPU、或因某事件而被阻塞才把CPU让出给其它进程。剥夺方式（抢占方式）抢占方式发生的情况可为：新进程到达、出现中断且将阻塞进程转变为就绪进程、以及用完规定的时间片等。好处为进程提供更好的服务，防止一个进程长期占有CPU，但开销大。

练习1.作业是由用户提交的，进程是由系统自动生成，除此之外，两者的区别是（）。（A）两者执行不同的程序段（B）前者以用户任务为单位，后者是操作系统控制的单位（C）前者是批处理的，后者是分时的（D）后者可并发执行，前者则不行练习2.当一进程运行时，系统可基于某种原因强行将其撤下，把处理机分配给其他进程，这种调度方式是（）。(Ａ)非抢占式(Ｂ)抢占式(Ｃ)中断方式(Ｄ)查找方式进程调度时机●进程退出●进程阻塞●新进程创建●中断发生●时钟中断

调度的性能准则●面向用户的准则●响应时间快响应时间：从用户通过键盘提交请求到首次得到响应的时间●周转时间短：周转时间：作业从提交到完成的时间间隔。●优先权准则●截止时间的保证●面向系统的准则●系统吞吐量单位时间内完成的作业数。●处理机利用率●各类资源平衡利用●公平周转时间定义●周转时间Ti●平均周转时间

●带权周转时间●平均带权周转时间tci为完成时间tsi为到达系统的时间响应时间定义

响应时间；响应时间就是从任务就绪到处理开始（也有的称为等待时间）。

►

在交互式系统中，周转时间不可能是最好的评价准则。因为不断请求与不断输出在同时发生。►通常，响应时间一般用于分时系统性能评价，指用户通过键盘或终端提出一个请求开始到系统给出相应的响应结果的时间（与上面有所不同）。系统开销；系统开销就是系统调度任务的过程中所付出的时/空代价。练习1.从进程提交给系统开始到进程完成为止的时间间隔称为（）。（A）进程周转时间（B）进程运行时间（C）进程响应时间（D）进程等待时间练习2.设有4个作业同时到达，每个作业的执行时间为2小时，它们在单处理机上按单道方式运行，则平均周转时间是（）小时。(Ａ)1(Ｂ)5(Ｃ)2.5(Ｄ)8练习3.以下关于选择进程调度算法的准则错误的是(）。(Ａ)尽量提高处理机利用率(Ｂ)尽可能提高系统吞吐量(Ｃ)适当增长进程在就绪队列中等待时间(Ｄ)尽快响应交互式用户的请求

作业调度算法与进程调度算法基本概念相通或相近的，只是空间位置有所不同。系统中处于可运行状态进程的个数通常比处理机的个数要多，特别是在单处理机系统中尤为如此。这样就存在从就绪队列中选择哪一个进程，这就是调度算法问题。

●先来先服务调度算法●短作业（进程）优先调度算法●时间片轮转调度算法●优先权调度算法●多级反馈队列……●4.2调度算法先来先服务FCFS算法思想对于作业调度，从后备作业中选择最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。对于进程调度，从就绪队列中选择最先进入该队列的进程，分配处理机，使之运行。FCFS

例1．有四个作业（或进程），他们相应的时间见表：作业到达时间Tin服务时间Tr开始时间TS结束时间Tc周转时间T带权周转时间WA01B1100C21D3100平均问题：C的周转时间是所需要处理时间的100倍！作业D的周转时间近乎是C的两倍，但它的带权周转时间却低于2.0。

例2．更一般的情况，设有五个作业，见表表更一般作业类型的FCFS的调度性能作业到达时间Tin服务时间Tr开始时间Ts结束时间Tc周转时间T带权周转时间WA0303TA=3WA=1B2639TB=7WB=1.17C44913TC=9WC=2.25D651318TD=12WD=2.40.E821820TE=12WE=6平均=8.60=2.56同样，看到作业E的不利情况。FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业(进程)。

CPU繁忙型作业是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙型作业。

I/O繁忙型作业是指CPU进行处理时需频繁地请求I/O。目前的大多数事务处理都属于I/O繁忙型作业。先来先服务FCFS与短作业优先SJF算法思想短作业优先是从后备队列中选择估计运行时间最短的作业，将它们调入内存。短进程优先是从就绪队列中选择估计运行时间最短的进程，将处理机分配给它，使之执行并一直到完成或因发生某事件而阻塞放弃处理机时，再重新调度。SJF作业到达时间Tin服务时间Tr开始时间Ts结束时间Tc

8364522046ECDAB周转时间T平均带权周转时间W

SJF对短作业有利，并且整体性能也得到了提高；SJF的问题：

SJF需要事先知道或至少需要估计每个作业所需的处理机时间。只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”。

SJF偏向短作业，不利于分时系统（由于不可抢占性）。练习1.现有三个同时到达的作业J1,J2,J3,它们的执行时间分别为T1,T2,T3,且T1<T2<T3,系统按单道方式运行且采用短作业优先算法，则平均周转时间是（）。（A）T1+T2+T3（B）（T1+T2+T3）/3（C）(3T1+2T2+T3)/3（D）（T1+2T2+3T3）/3时间片轮转调度算法(RR)●算法思想●进程按FCFS在就绪队列排队，调度程序把CPU分配给队首进程，令其执行一个时间片，一个时间片执行完毕将进程排在队尾。

作业到达时间Tin服务时间Tr开始时间Ts结束时间Tc

周转时间T带权周转时间W8364522046ECDAB时间片轮转调度算法(RR)●时间片大小的确定 响应时间T=用户数目N*时间片q●响应时间T 当N一定，T与q成正比。T若要求快，则q也要小。●就绪队列的进程数N T一定，q与N成反比。N越多，q要小。●系统的处理能力 保证用户键入的常用命令能在一个时间片内处理完毕。时间片大小系统处理能力比较●算法思想从后备队列中选择若干优先权最高的作业，将它们调入内存。或从就绪队列中选择优先权最高的进程，将处理机分配给它。●优先权类型静态优先权确定因素：进程类型、进程对资源的需求、用户要求。动态优先权确定因素：等待时间、运行时间。●特点：综合考虑各种情况优先权调度算法高响应比优先调度算法

如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：

由上式可以看出：

(1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。

(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。

作业到达时间Tin服务时间Tr开始时间Ts结束时间Tc

8364522046ECDAB周转时间T平均带权周转时间W最短剩余时间（SRT）

SRT是针对SJF增加了强占机制的一种调度算法，它总是选择预期剩余时间最短的进程。只要新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程。

作业到达时间Tin服务时间Tr开始时间Ts结束时间Tc

82046ECDAB周转时间T带权周转时间W平均36452最短剩余时间（SRT）SRT不象FCFS偏向长进程，也不象轮转法（下个算法）产生额外的中断，从而减少了开销。必须记录过去的服务时间，从而增加了开销。从周转时间来看，SRT比SJF有更好的性能。高响应比优先调度算法

如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：

由上式可以看出：

(1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。

(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。

作业到达时间Tin服务时间Tr开始时间Ts结束时间Tc

8364522046ECDAB周转时间T平均带权周转时间W不同调度算法对同一个作业/进程的性能分析:作业到达时间Tin服务时间Tr从平均周转时间及其平均带权周转时间来看，SRT好于前面的任何一个算法。A03B26C44D65E82FCFS8.602.56SJF7.601.84HRP8.002.14SRT7.201.59RR10.802.71●算法思想●根据作业的性质和类型不同，将就绪队列再分为若干个子队列，每个进程分属于一个队列。●在多级队列的基础上，不但设多个队列，且为每个队列赋予不同的优先权，第一个队列的优先权最高，第二个队列次之，其余队列的优先权逐个降低。●各个队列中的进程执行时间片大小逐渐增大。●新进程投入第一个队列。●调度从第一个队列进行，仅当第一个队列为空时，才调度第二个队列中的进程。多级反馈队列调度算法多级反馈队列调度算法各种常用调度算法的比较43/19

算法比较项FCFSRRSJFSRTHRPMFQ调度方式非抢占式抢占式(按时间片)非抢占式抢占式(进程到达)非抢占式抢占式(按时间片)吞吐量不突出时间片太小,可能变低高高高不突出响应时间可能很高，对于短进程提供良好的响应时间对短作业/进程提供良好响应时间提供良好的响应时间提供良好的响应时间不突出开销最小低可能高可能高可能高可能高对进程的作用不利于短作业/进程和I/O忙型公平对待不利于长作业/进程不利于长进程良好的均衡（进程）可能偏向I/O繁忙的作业/进程饥饿问题无无可能可能无可能不适合作业调度练习1.以下（）是基于时间片的调度算法。（A）时间片轮转法（B）高响应比优先调用算法（C）抢占式调用算法（D）先来先服务算法练习2.时间片轮转算法经常用于（）。（A）单用户操作系统（B）实时系统（C）分时系统（D）批处理系统练习3.以下（）算法与作业的运行时间有关。（A）优先级调度（B）时间片轮转（C）短作业优先（D）先来先服务练习4.（）优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变。（A）先来先服务（B）静态（C）动态（D）短作业练习5.对于处理机调度中高响应比调度算法，通常影响响应比的主要因素可以是（）。（A）程序长度（B）静态优先数（C）运行时间（D）等待时间练习6.设有三个作业，其运行时间分别是2h,5h,3h,假定它们同时到达，并在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是（）AJ1,J2,J3BJ3,J2,J1CJ2,J1,J3DJ1,J3,J2练习7.下列算法中，（）调度算法是绝对可以抢占的。A先来先服务B时间片轮转C优先级D短进程优先练习8.关于优先权大小的论述中，正确的是（）Ａ计算型作业的优先权，应高于Ｉ/O型作业的优先权Ｂ用户进程的优先权，应高于系统进程的优先权Ｃ在动态优先权中，随着作业等待时间的增加，其优先权将随之下降Ｄ在动态优先权中，随着进程执行时间的增加，其优先权降低练习9.假设某操作系统采用时间片轮转调度策略,分配给A类进程的时间片为100ms,分配给B类进程的时间片为400ms,就绪进程队列的平均长度为5(包括正在运行的进程),其中A类进程有4个,B类进程有1个,所有进程的平均服务时间为2s,问A类进程和B类进程的平均周转时间各为少?(不考虑I/O情况)●4.3死锁的基本概念一组竞争系统资源或相互通信的进程相互的“永久”阻塞。若无外力作用，这组进程将永远不能继续执行。产生死锁的原因●资源数<要求该种资源的进程数●进程的推进顺序非法进程P……get(A);……get(B);……release(A);……release(B);……

进程Q……get(B);……get(A);……release(B);……release(A);……A、B分别代表某种资源进程的推进顺序不当死锁●(1)、(2)、(4)、(5)正常运行●(3)、(6)发生死锁进程的推进顺序合适不死锁进程P对资源的申请、释放次序改变后不死锁！交换P操作的位置voidproducer()//生产者进程{while(true){produceanitemindata_p;P(empty);P(mutex);buffer[i]=data_p;i=(i+1)%n;V(mutex);V(full);}}voidconsumer()//消费者进程{while(true){P(mutex); P(full); data_c=buffer[j];j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c;}}问题的提出：对于生产者-消费者问题，如果将P操作的位置交换，将产生什么样的后果？？消费者先行死锁！voidproducer()//生产者进程{while(true){produceanitemindata_p;P(mutex); P(empty); buffer[i]=data_p;i=(i+1)%n;V(mutex);V(full); }}voidconsumer()//消费者进程{while(true){P(full); P(mutex); data_c=buffer[j];j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c; }}？生产者运行N次后——死锁！交换P操作的位置产生死锁的四个必要条件不剥夺条件互斥条件请求保持条件环路条件(1)（资源独占）一个资源每次只能给一个进程使用(2)（部分分配，占有申请）一个进程在申请新的资源的同时保持对原有资源的占有(3)（不可强占）资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放练习1.当出现（）情况下，系统出现死锁。（A）计算机系统发生了重大故障（B）资源个数远远小于进程数（C）若干进程因竞争资源而无休止地相互等待他方释放已占有的资源（D）进程同时申请的资源数超过资源总数练习2.为多道程序提供的可共享资源不足时，可能出现死锁，但是，不适当的（）也可能产生死锁。（A）进程优先权（B）资源的线性分配（C）进程推进顺序（D）分配队列的优先权练习3.以下（）情况下，系统可能出现死锁。（A）进程释放资源（B）一个进程进入死循环（C）多个进程竞争资源出现了循环等待（D）多个进程竞争CPU练习4.一个进程在获得资源后，只能在使用完资源后由自己释放，这属于死锁必要条件的（）。（A）互斥条件（B）请求与释放条件（C）不剥夺条件（D）环路等待条件练习5.死锁产生的必要条件是互斥，（），不剥夺和环路等待。（A）请求与阻塞（B）请求与保持（C）请求与释放（D）释放与阻塞采用预先静态分配方法系统要求所有进程一次性地申请其所需的全部资源优点：方法简单缺点：进程延迟运行资源浪费用户有时提不出他要使用的全部资源去掉“请求保持条件”互斥条件不可禁止去掉“不剥夺条件”去掉“环路“条件方法占有某些资源的进程，当它有新的资源请求被拒绝时，该进程停止运行，并释放它所占有的资源。当它再次被执行时，重新申请资源。如果一个进程请求另一个进程占有的资源，操作系统可以剥夺后者占有的资源，要求它释放资源并将资源分配给前者使用

缺点该策略实现起来比较复杂，而且要付出很大代价。反复申请、释放，使进程执行无限延迟，不仅延迟了周转时间。还增加了系统开销，降低了系统吞吐量。采用资源的有序分配令所有资源排队，并赋予不同的序号。当进程请求资源时，必须严格按递增的次序提出，从而消除了环路。缺点：定好序号后，增加新设备类型受到限制。尽管定序号时考虑大多数作业使用资源的顺序。但会发生使用顺序与规定顺序不一致的情况，造成资源浪费。限制用户简单、自主地编程。死锁的预防措施低效！●死锁的预防4.4死锁的预防与避免练习1．发生死锁的必要条件有四个，要防止死锁产生，可以通过破坏这4个必要条件之一来实现，但破坏（）条件是不可行的。A互斥B不可剥夺C请求与保持D循环等待练习2．一次分配所有资源的方法可以预防死锁的发生，它破坏了死锁四个必要条件中的（）A互斥B请求并保持C非剥夺D循环等待练习3．死锁预防是保证系统不进入死锁状态的静态策略，其解决办法是破坏产生死锁的四个必要条件之一，下列方法中破坏了“循环等待”条件的是（）A银行家算法B一次性分配策略C剥夺资源法D资源有序分配策略●安全状态是指系统至少存在一个安全序列<P1,P2,…,Pn>，按照这个序列为进程分配资源，直到满足最大需求，每个进程都可顺序完成。●若系统不存在这样一个安全序列，则系统处于不安全状态。避免死锁是通过明智的选择，确保系统永远不会到达死锁点。即动态地决定是否分配资源给进程！安全状态—与—不安全状态死锁的避免系统有三个进程P1、P2、P3，共有12台磁带机，进程P1要求10台，P2要求4台，P3要求9台。在T0时刻，进程P1、P2、P3已获得5、2、2台，尚有3台未分配，问：系统是否处于安全状态？进程最大需求已分配可用P1 10 5 3P242P392存在安全序列<P2,P1,P3>！——实例安全状态银行家算法●进行资源预分配●实施安全检测

●安全：真正资源分配

●不安全：回到预分配前状态算法描述银行家算法1.银行家算法中的数据结构

（1）可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。如：

ABC523银行家算法1.银行家算法中的数据结构

（2）最大需求矩阵Max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。ABCP1562P2331P3425P4332银行家算法1.银行家算法中的数据结构

（3）分配矩阵Allocation。n*m矩阵，表示每个进程分配的资源数。ABCP1212P2121P3222P4132银行家算法1.银行家算法中的数据结构

（4）需求矩阵Need。n*m矩阵，表示每个进程还需要各类资源数。ABCP1352P2211P3223P42322．银行家算法Pi请求资源Request[i]Need[i]请求超量，错返Request[i]Available不满足，等待Available:=Available-Request[i]Allocation[i]:=Allocation[i]+Request[i]Need[i:=Need[i]-Request[i]安全确认，pi继续Available:=Available+Request[i]Allocation[i]:=Allocation[i]-Request[i]Need[i]:=Need[i]+Request[i]pi等待FTFTTF安全性检测算法FWork:=Available;Finish:=false;有满足条件的j:Finish[j]=falseNeed[j]WorkFinish[j]=true;Work:=Work+Allocation[j]Tj,finish[j]=trueTF安全不安全银行家算法设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图:资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431(1)T0时刻可以找到一个安全序列{p1,p3,p4,p2,p0},系统是安全的银行家算法(2)P1发出请求Request(1,0,2)，执行银行家算法:资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332230P13222003021220

20P2902302600P3222211011P4433002431可以找到一个安全序列{p1,p3,p4,p0,p2}，系统是安全的，可以将P1的请求分配给它。银行家算法(３)P4发出请求Request(3,3,0),执行银行家算法:资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743230P13223020

20P2902302600P3222211011P4433002431Available=（2,3,0），Request[i]≤Available

，所以P4等待。银行家算法(4)P0请求资源Request（0，2，0），执行银行家算法，试分配后:资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753030723210P13223020

20P2902302600P3222211011P4433002431Available＝(2,1,0)不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配练习1.某个时刻进程的资源使用情况如表所示，此时安全序列是（）.

AP1P2P3P4BP1P3P2P4CP1P4P3P2D不存在进程已分配资源尚需资源可用资源R1R2R3R1R2R3R1R2R3P1200001021P2120132P3011131P4001200练习设系统中有3种类型的资源（A，B，C）和5个进程P1，P2，P3，P4，P5，A资源数为17，B资源数为5，C资源数为20。假设系统在t0时刻如下表所示，系统采用银行家算法避免死锁。进程最大资源需求已分配资源可用资源ABCABCABCP1559212233P2536402P34011405P4425204P5424314

1）t0时刻是不否为安全状态？若是，请给出安全序列。2）若在t0时刻进程P2申请资源（0，3，4），是否能实施资源分配？3）在（2）基础上，若进程P4申请资源（2，0，1），是否能实施资源分配？4）在（3）基础上，若进程P1申请资源（0，2，0），是否能实施资源分配？●4.5死锁的检测与解除由二元组G=（V，E）

V：结点集，分为P(进程)，R(资源)两部分

P={p1,p2,…,pn},R={r1,r2,…,rm}

E：边的集合，其元素为有序二元组:

(pi,rj)或(rj,pi)

表示法资源类:用方框表示（资源的不同类型）资源实例:用方框中的黑圆点表示（存在于每个资源中）进程:用圆圈中加进程名表示分配边：资源实例进程的一条有向边申请边：进程资源类的一条有向边

●在图中找出一个既不阻塞又非独立的进程结点pi，消去pi所有的请求边和分配边，使之成为孤立结点。●在进行一系列简化后，能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可以完全简化的，否则若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。当且仅当S状态的资源分配图是不可完全简化的，S为死锁状态。资源分配图的简化2.死锁判定法则(1)如果资源分配图(SRAG)中没有环路，则系统内没有死锁。(2)如果SRAG中有环路，且每类资源只有一个，则有环是系统存在死锁的必要充分条件。(3)如果SRAG中有环路，但每类资源的个数不全为1，则可以利用对SRAG化简的方法，来检测系统是否存在死锁

资源分配图示例有环无死锁资源分配图示例

有环有死锁2.试化简下图的进程-资源图,并利用死锁定理给出相应原结论.P2P3P1R1R2R3R4死锁的解除●当发现死锁时，应立即把它们从死锁中解脱出来，常采用的两种方法是：●剥夺资源●从其它进程剥夺足够数量的资源给死锁进程。●撤消进程：撤消的原则是●为解除死锁状态所需撤消的进程数目最小。●撤消进程所付出的代价最小。按复杂度递增的顺序列出的方法:1.撤消所有的死锁进程2.死锁进程回滚到某些检查点3.连续撤消死锁进程直到不再存在死锁4.连续剥夺资源直到不再存在死锁对于3和4，选择代价最小的进程进行代价最小的进程考虑因素:目前为止消耗的处理器时间最少;目前为止产生的输出最