第三章 处理机调度和死锁

第三章处理机调度和死锁第一页，共六十八页，编辑于2023年，星期四处理机调度进程数目>处理机数目动态分配由处理机调度程序完成作业提交处理机调度获得处理机,执行第二页，共六十八页，编辑于2023年，星期四3.1处理机调度的层次

3.1.1高级调度（作业调度、长程调度、接纳调度）

--把外存上处于后备队列中的作业调入内存。1．作业和作业步

(1)作业(Job)。程序和数据+作业说明书。

在批处理系统中，是以作业为基本单位从外存调入内存的。

(2)作业步(JobStep)。顺序加工步骤。相对独立，相互关联。例如：“编译”作业步，“连结装配”

“运行”作业步(3)作业流。输入的作业流；处理作业流。

第三页，共六十八页，编辑于2023年，星期四2．作业控制块JCB(JobControlBlock)每个作业设置一个作业控制块，是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。作业创建JCB后备队列作业调度进入内存结束回收资源撤销JCB就绪队列3.1.1高级调度第四页，共六十八页，编辑于2023年，星期四3．作业调度

作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。调度特性1.接纳作业数（内存驻留数）太多―――> 周转时间T长太少―――> 系统效率低2.接纳策略：即采用何种调度算法：FCFS、短作业优先等3.1.1高级调度第五页，共六十八页，编辑于2023年，星期四3.1.2低级调度（进程调度或短程调度）1．低级调度的功能低级调度用于决定就绪队列中的哪个进程(或内核级线程，为叙述方便，以后只写进程)应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。(1)保存处理机的现场信息。(2)按某种算法选取进程。(3)把处理器分配给进程。2．进程调度中的三个基本机制为了实现进程调度，应具有如下三个基本机制：(1)排队器。(2)分派器(分派程序)。(3)上下文切换机制。第六页，共六十八页，编辑于2023年，星期四3．进程调度方式

1)非抢占方式(NonpreemptiveMode)不允许抢占正在运行进程的处理机。实现简单，系统开销小难以满足紧急任务的要求，不适合实时系统

2)抢占方式(PreemptiveMode)允许根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。优先权原则。短作业(进程)优先原则。时间片原则。3.1.2低级调度第七页，共六十八页，编辑于2023年，星期四3.1.3中级调度（中程调度）使那些暂时不能运行的进程不再占用宝贵的内存资源，将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上就是存储器管理中的对换功能第八页，共六十八页，编辑于2023年，星期四3.2.1调度队列模型一、仅有进程调度的调度队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度等待事件事件出现进程完成3.2调度队列模型和调度准则

第九页，共六十八页，编辑于2023年，星期四二、具有高/低级调度的调度队列模型就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现阻塞队列等待事件2事件2出现作业调度后备队列N3.2.1调度队列模型第十页，共六十八页，编辑于2023年，星期四三、具有三级调度的调度队列模型就绪队列CPU就绪、挂起队列时间片完进程调度进程完成后备队列阻塞、挂起队列事件出现作业调度阻塞队列等待事件挂起事件出现中级调度交互型作业3.2.1调度队列模型第十一页，共六十八页，编辑于2023年，星期四3.2.2选择调度方式和算法的若干准则

一、面向用户的准则1．周转时间短（常用于批处理系统）概念：作业从提交――>完成的时间.分为：（1）驻外等待调度时间（2）驻内等待调度时间（3）执行时间（4）阻塞时间第十二页，共六十八页，编辑于2023年，星期四一、面向用户的准则平均周转时间

平均带权周转时间

可见带权W越小越好,Ts为实际服务时间。3.2.2选择调度方式和算法的若干准则

第十三页，共六十八页，编辑于2023年，星期四一、面向用户的准则2．响应时间快：（对交互性作业）概念：键盘提交请求到首次响应的时间（1）输入传送时间（2）处理时间（3）响应传送时间3．截止时间的保证（特别于实时系统）4．优先权准则：（即需要抢占调度）3.2.2选择调度方式和算法的若干准则

第十四页，共六十八页，编辑于2023年，星期四二、面向系统的准则1．吞吐量高（特别于批处理）：单位时间完成作业数2．处理机利用率好：（因CPU贵，特别于大中型多用户系统）3．各类资源的平衡利用。3.2.2选择调度方式和算法的若干准则

第十五页，共六十八页，编辑于2023年，星期四

3.3调度算法

——是一个资源分配问题

3.3.1先来先服务和短作业（进程）优先调度算法

1.先来先服务调度算法FCFS特点：简单，有利于长作业即CPU繁忙性作业进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99第十六页，共六十八页，编辑于2023年，星期四3.3.1先来先服务和短作业（进程）优先调度算法2.短作业进程优先调度算法：SJ(P)F选出估计运行时间最短的作业（进程）提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）对长作业不利，有可能得不到服务（饥饿）未考虑作业的紧迫性估计时间不易确定第十七页，共六十八页，编辑于2023年，星期四图3.4FCFS和SJF比较进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.10417231241418ABCDEFCFS041923184613ABCDESJF第十八页，共六十八页，编辑于2023年，星期四3.3.2高优先权优先调度算法1.优先权调度算法类型非抢占式优先权算法抢占式优先权算法，实时性更好。2.优先权类型：1．静态优先权：进程优先权在整个运行期不变。确定优先权依据（1）进程类型（2）进程对资源的需求；（3）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。第十九页，共六十八页，编辑于2023年，星期四3.3.2高优先权优先调度算法(2)2．动态优先权：如：优先权随执行时间而下降，随等待时间而升高。响应比Rp=（等待时间＋服务时间）/服务时间作为优先权优点：长短兼顾缺点：需计算Rp3.高响应比优先算法：特点：响应比Rp=（tw+ts）/ts（1）短作业RP大。（2）ts（要求服务时间）相同的进程间相当于FCFS。（3）长作业等待一段时间仍能得到服务。第二十页，共六十八页，编辑于2023年，星期四3.3.3基于时间片的轮转调度算法1.时间片轮转时间片大小的确定太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求；T=nq就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）第二十一页，共六十八页，编辑于2023年，星期四2.多级反馈队列调度

多个就绪队列，不同优先级新进程首先进入第一队列尾，FCFS；时间片结束后未完成的进入第二队列尾…第一队列空闲时才调度第二队列，抢占式3.3.3基于时间片的轮转调度算法（2）特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。第二十二页，共六十八页，编辑于2023年，星期四就绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至CPU就绪队列nSn至CPU时间片：S1<S2<S3图3－7多级队列反馈调度算法第二十三页，共六十八页，编辑于2023年，星期四3.4.1实现实时调度的基本条件1．提供必要的调度信息（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；2．系统处理能力强，满足：3.4实时调度Ci为处理时间，Pi为周期时间（基于周期性实时任务）第二十四页，共六十八页，编辑于2023年，星期四3.采用抢占调度方式剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。4.具有快速切换机制具有快速响应外部中断能力。快速任务分派能力3.4.1实现实时调度的基本条件第二十五页，共六十八页，编辑于2023年，星期四3.4.2实时调度算法的分类1非抢占式调度算法时间片轮转 秒级非抢占优先权（协同） 秒~毫秒级2抢占式调度算法时钟中断抢占优先权 毫秒级基于抢占点抢占立即抢占抢占优先权毫秒~微秒级只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进程运行a非抢占轮转调度当前进程实时进程实时进程要求调度当前进程运行完成b非抢占优先权调度调度时间当前进程实时进程实时进程要求调度抢占时刻（其它中断）d立即抢占优先权调度调度时间c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度时钟中断到达时调度时间第二十六页，共六十八页，编辑于2023年，星期四3.4.3常用的几种实时调度算法1.最早截止时间优先EDF（earliestdeadlinefirst)算法根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高就绪队列中按个任务截止时间的早晚排序可以是抢占式或非抢占式第二十七页，共六十八页，编辑于2023年，星期四2最早截止时间优先EDF例1341234t开始截止时间任务到达任务执行EDF算法用于非抢占调度方式34213.4.3常用的几种实时调度算法第二十八页，共六十八页，编辑于2023年，星期四2.最低松弛度优先LLF算法松弛度：根据任务的紧急（松弛）程度确定优先级，越紧急优先级越高松弛度=必须完成时间-本身运行时间-当前时间若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90按松弛度排序的实时任务就绪队列主要用于可抢占的调度方式中3.4.3常用的几种实时调度算法第二十九页，共六十八页，编辑于2023年，星期四最低松弛度优先LLF算法(2)A1A2A3A4t01020304050607080B1B1B2B2t1t2t3t4t5t6t7t8A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t每20ms执行一次，执行时间10ms每50ms执行一次，执行时间25mst2--A2:20,B1:15t1--A1:10,B1:25t3--A2:0,B1:15t4--A3:10,B1:5t5—A3:5,B2:30t7—A4:0,B2:20第三十页，共六十八页，编辑于2023年，星期四进程到达时间/s服务时间/s103226344465582请比较采用以下调度策略各进程的平均周转时间和平均带权周转时间。1、先来先服务FCFS2、时间片轮转RR（q=1和q=4）3、最短进程优先SPN4、最高响应比优先HRRN5、多级反馈队列q=2n第三十一页，共六十八页，编辑于2023年，星期四3.5产生死锁的原因和必要条件所谓死锁(deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处在这种僵持状态时，若无外力作用，它们都将无法再向前推进。第三十二页，共六十八页，编辑于2023年，星期四3.5.1产生死锁的原因一、竞争资源引起死锁。1．可剥夺（CPU、内存）和非剥夺性（打印机，磁带机）资源2．竞争非剥夺性资源——可造成死锁3．竞争临时性资源——也可能引起死锁p1p2R1R2p1p3S3S1p2S2第三十三页，共六十八页，编辑于2023年，星期四二、进程推进顺序不当引起死锁进程推进顺序合法进程推进顺序非法3.5.1产生死锁的原因第三十四页，共六十八页，编辑于2023年，星期四213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)43.5.1产生死锁的原因第三十五页，共六十八页，编辑于2023年，星期四3.5.2产生死锁的必要条件1．互斥条件（资源的临界性）2．请求和保持条件3．不剥夺条件4．环路等待第三十六页，共六十八页，编辑于2023年，星期四资源分配图进程

有4个实例的某类资源Pi

申请的一个实例RjPi持有Rj的一个实例

PiRjPiRj3.5.2产生死锁的必要条件第三十七页，共六十八页，编辑于2023年，星期四Example第三十八页，共六十八页，编辑于2023年，星期四死锁！第三十九页，共六十八页，编辑于2023年，星期四死锁？第四十页，共六十八页，编辑于2023年，星期四BasicFacts图中没有环没有死锁.

图中有环每个资源类型只有一个实例,那么一定死锁.每个资源类型只有多个实例,那么可能死锁.第四十一页，共六十八页，编辑于2023年，星期四3.5.3处理死锁的基本方法

1．预防；破坏4个条件之一：有效，使资源利用率低。2．避免：防止进入不安全态。3．检测：检测到死锁再清除。4．解除：与“检”配套。第四十二页，共六十八页，编辑于2023年，星期四3.6死锁预防和避免

3.6.1死锁预防

一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件全分配，全释放（AND）缺点：（1）延迟进程运行 （2）资源严重浪费三、摒弃“不剥夺”条件 增加系统开销，且进程前段工作可能失效。第四十三页，共六十八页，编辑于2023年，星期四 四、摒弃“环路”条件有序资源分配法：为资源编号，申请时需按编号次序进行。缺点：（1）新增资源不便（原序号已排定）（2）用户不自由（3）资源与进程使用顺序不同造成浪费3.6.1死锁预防第四十四页，共六十八页，编辑于2023年，星期四3.6.2系统的安全状态在“避免死锁”方法中的判断条件1.安全状态按某种顺序并发进程都能达到获得最大资源的可顺序完成的序列为安全序列。能找到安全序列的状态为安全状态，否则为不安全状态。避免死锁：资源分配时，使系统不进入不安全状态第四十五页，共六十八页，编辑于2023年，星期四2.安全状态例进程最大需求已分配可用P11053P242P392安全序列：p2p1p33.6.2系统的安全状态第四十六页，共六十八页，编辑于2023年，星期四3.安全不安全的转换不按照安全序列分配资源，可能转入不安全状态上例中，若P3再申请一台，则不安全进程最大需求已分配可用P11052P242P3933.6.2系统的安全状态第四十七页，共六十八页，编辑于2023年，星期四安全/不安全&死锁3.6.2系统的安全状态第四十八页，共六十八页，编辑于2023年，星期四系统在安全状态不会死锁.

系统在不安全状态可能死锁.

避免保证系统不会进入不安全状态.

3.6.2系统的安全状态第四十九页，共六十八页，编辑于2023年，星期四3.6.3利用银行家算法避免死锁

1．数据结构Available[j]=k:系统现有Rj类资源k个；Max[i,j]=k:进程i需要Rj的最大数k个；Allocation[i,j]=k:进程i已得到Rj类资源k个；

Need[i,j]=k: 进程i需要Rj类资源k个有：Need[i,j]=Max[i,j]－Allocation[i,j]Requesti[j]=k

进程i请求k个Rj类资源Work[j]=k:系统可提供进程继续运行所需要的资源数目finish[i]：布尔量，表进程i能否顺序完成。

第五十页，共六十八页，编辑于2023年，星期四银行家算法之例五个进程{P0,P1,P2,P3,P4},三种资源{A，B，C}，数量分别为10、5、7，在T0时刻的资源分配情况:MaxABCAllocABCNeedABCAvailABCP0753010743332P1332200122P2902302600P3222211011P44330024313.6.3利用银行家算法避免死锁

第五十一页，共六十八页，编辑于2023年，星期四2．银行家算法（1）如果Requesti≤Need,则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requesti≤Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，Pi必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：Available[j]:=Availablei[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

3.6.3利用银行家算法避免死锁

第五十二页，共六十八页，编辑于2023年，星期四3、安全性算法（1）设置两个向量①工作向量Work。②Finish。（2）从进程集合中找到一个能满足下述条件的进程：①Finish[i]:=false②Need[i,j]≤Work[j]如找到，执行步骤（3）；否则，执行步骤（4）。（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]:=Work[i]+Allocation[i,j];Finish[i]：=true;Gotostep2;（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。3.6.3利用银行家算法避免死锁

第五十三页，共六十八页，编辑于2023年，星期四银行家算法之例五个进程{P0,P1,P2,P3,P4},三种资源{A，B，C}，数量分别为10、5、7，在T0时刻的资源分配情况:MaxABCAllocABCNeedABCAvailABCP0753010743332P1332200122P2902302600P3222211011P4433002431Work[j]:=Work[i]+Alloc[i,j]Finish[i]：=true;532743745104710573.6.3利用银行家算法避免死锁

从进程集合中找到一个能满足下述条件的进程：①Finish[i]:=false②Need[i,j]≤Work[j]第五十四页，共六十八页，编辑于2023年，星期四（1）T0时刻的安全性利用安全性算法对T0时刻的资源分配情况进行分析，可得下表所示的T0时刻的安全性分析，从中得知，T0时刻存在着一个安全序列{P1，P3，P4，P2，P0}，故系统是安全的:WorkABCNeedABCAllocABCWork+AvailABCFinishP1332122200532trueP3532011211743trueP4743432002745trueP27456003021047trueP010477430101057true3.6.3利用银行家算法避免死锁

第五十五页，共六十八页，编辑于2023年，星期四（2）P1请求资源P1发出请求向量Request(1,0,2),系统按银行家算法进行检查：(1)Request1(1,0,2)≤Need(1,2,2)(2)Request1(1,0,2)≤Available(3,3,2)(3)系统先假定可为P1分配资源，并修改Available，Allocation和Need向量，由此形成的资源变化情况如图MaxABCAllocABCNeedABCAvailABCP0753010743230P1332200122P2902302600P3222211011P44330024310203023.6.3利用银行家算法避免死锁

第五十六页，共六十八页，编辑于2023年，星期四（4）我们再利用安全性检查此时系统是否安全。由所进行的安全性检查得知，可以找到一个安全序列{P1，P3，P4，P2，P0}。因此，系统是安全的，可以立即将P1所申请的资源分配给它。WorkABCNeedABCAllocABCWork+AvailABCFinishP1230020302532trueP3532011211743trueP4743432002745trueP0745743010755trueP210476003021057true3.6.3利用银行家算法避免死锁

第五十七页，共六十八页，编辑于2023年，星期四（3）P4请求资源P4发出请求向量Request(3,3,0),系统按银行家算法进行检查：(1)Request4(3,3,0)≤Need4(4,3,1)。(2)Request4(3,3,0)>Available(2,3,0)，让P4等待。（4）P0请求资源P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查：(1)Request0(0,2,0)≤Need0(7,4,3));(2)Request0(0,2,0)≤Available(2,3,0)，(3)进行安全性检查可用资源Available{2,1,0}已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

3.6.3利用银行家算法避免死锁

第五十八页，共六十八页，编辑于2023年，星期四3.7

死锁的检测和解除3.7.1、死锁的检测系统必须须提供检测和解除死锁的手段：（1）保存有关资源的请求和分配信息；（2）提供算法以利用这些信息来检测系统是否进入死锁。1、资源分配图（ResourceAilocationGraph）系统死锁可利用资源分配图来描述。G=（N，E）：（1）N分为两个互斥的子集，进程结点P=（P1，P2,…,Pn）,资源结点R={r1,r2,…,rn},N=P∪R。（2）E中的边e∈E,都连接着P中的一个结点和R中的一个结点，e={pi,rj}是资源请求边，由进程pi指向资源rj,它表示进程pi请求一个单位的rj资源。第五十九页，共六十八页，编辑于2023年，星期四p1p2R2R1分配请求3.7.1

死锁的检测第六十页，共六十八页，编辑于2023年，星期四2、死锁定理简化资源分配图来检测系统处于S状态时，是否为死锁状态。简化方法如下：（1）在资源分配图中，找出一个既不阻塞又非独立的进程结点pi。在顺利情况下，pi可获得所需资源而继续执行，直至运行完毕，再释放其所占有的全部资源。这相当于消去pi所有的请求边和分配边，使之成为孤立的结点。p1p2R2R1p1p2R2R13.7.1

死锁的检测第六十一页，共六十八页，编辑