处理机调度与死锁N.ppt

第三章 处理机调度与死锁,3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,教学目的与要求,理解处理机调度的概念和调度的层次掌握各种作业、进程调度算法和实时调度算法理解死锁的基本概念掌握死锁的处理方法,教学重点：各种作业、进程调度算法和死锁 的处理方法等。教学难点：作业、进程调度算法,死锁,3.1 处理机调度的层次,对资源进行有效的调度是非常必要的，我们生活中也会经常遇到，如：调度银行出纳员服务顾客请求问题等。CPU是计算机系统中的一个十分重要的资源，对它进行高效的调度是操作系统设计的中心问题之一。,3.1 处理机调度的层次,高级调度（作业调度、长程调度、接纳调度）1、作业和作业步作业：包含程序、数据和作业说明书。作业步：作业执行过程中的每一个加工步骤作业流：作业进入系统，依次存于外存形成作业流2、作业控制块（JCB）它是作业在系统中存在的标志，其中保存了系统 对作业进行管理和调度所需的全部信息。内容：作业标识，用户名，作业类型，作业状态，调度信息等进入系统建立JCB-插入相应后备队列-作业调度-作业控制作业结束回收资源,3、作业调度将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。调度特性接纳作业数（内存驻留数，多道程序度）太多周转时间T长太少系统效率低接纳策略：即采用何种调度算法：FCFS、短作业优先等,3.1.2 低级调度（进程调度，短程调度）,主要是决定就绪队列中的哪个进程应获得处理机，然后由分派程序（Dispatcher）分派处理机。1.低级调度的功能：保存处理机现场信息按某种算法选取进程把处理机分配给进程2.进程调度的三个进步机制排队器分派器上下文切换机制：两对切换,CPU Switch From Process to Process,3.进程调度方式：,1)非抢占方式：简单、系统开销小，实时性差(如win31)2)抢占方式（1）优先权原则（2）短进程优先原则（3）时间片原则引起进程调度的因素有哪些？进程正常终止或异常终止进程因某种原因阻塞：I/O请求；wait操作等时间片用完抢占方式下，就绪队列中某进程的优先权比当前执行的进程高,为提高系统吞吐量和内存利用率而引入的一 内-外存对换功能（换出时，进程为挂起或就绪驻外存状态）三级调度的运行频率低中高。,3.1.3 中级调度（中程）,3.2调度的队列模型和调度准则,1.仅有进程调度的队列模型,就绪队列,CPU,阻塞队列,交互用户,时间片完,进程调度,进程完成,等待事件,事件出现,调度的队列模型,2.具有高、低级调度的队列模型,就绪队列,CPU,阻塞队列,时间片完,进程调度,进程完成,等待事件1,事件1出现,后备队列,阻塞队列,等待事件2,事件2出现,作业调度,3.具有三级调度的队列模型,就绪队列,CPU,就绪、挂起队列,时间片完,进程调度,进程完成,后备队列,阻塞、挂起队列,事件出现,作业调度,阻塞队列,等待事件,挂起,事件出现,中级调度,交互型作业,3.2.2 选择调度方式和调度算法的若干准则,1、面向用户的准则（1）周转时间短（常用于批处理系统）概念：作业从提交 完成的时间.分为：驻外存等待调度时间驻内存等待调度时间执行时间阻塞时间,1、面向用户的准则平均周转时间平均带权 可见带权w越小越好,Ts为实际服务时间。,选择调度方式和算法的若干准则,1、面向用户的准则（2）响应时间快：（对交互性作业）概念：键盘提交请求到首次响应时间输入传送时间处理时间响应传送时间（3）截止时间的保证（特别是实时系统）（4）优先权准则：（即需要抢占调度）,选择调度方式和算法的若干准则,2、面向系统的准则（1）吞吐量高（特别是批处理）：单位时间完成作业数（2）处理机利用率好：（因CPU贵，特别是大中型多用户系统）（3）各类资源的平衡利用。,选择调度方式和算法的若干准则,3.3调度算法是一个资源分配问题,先来先服务和短作业（进程）优先调度算法1.先来先服务调度算法（FCFS）特点：简单，有利于长作业（进程）即CPU繁忙性作业,不利于短作业（进程）2.短作业（进程）优先调度算法：SJ(P)F提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）特点：对长作业不利，有可能得不到服务估计时间不易确定,先来先服务算法实例,图3-4 FCFS和SJ(P)F比较,高优先权优先调度算法,1.优先权调度算法类型非抢占式优先权算法抢占式优先权算法，实时性更好。2.优先权类型：1）静态优先权：进程优先权在整个运行期不变。确定优先权依据进程类型进程对资源的需求；根据用户需求。特点：简单，但低优先权作业可能长期不被调度（饥饿）。（例子MIT IBM7049）,高优先权优先调度算法(2),2）动态优先权：如：优先权随执行时间而下降，随等待时间而升高。优点：长短兼顾 缺点：需经常计算各进程优先级3.高响应比优先调度算法：响应比Rp=（Tw+Ts）/Ts特点：（1）短作业RP大。（2）Ts（要求服务时间）相同的进程间相当于FCFS。（3）长作业等待一段时间仍能得到服务。,22,常见的批处理作业调度算法,先来先服务算法（FCFS：First Come First Serve）最短作业优先算法（SJF：Shortest Job First）最短剩余时间优先（SRTF:Shortest Remaining Time First）最高响应比优先算法（HRRF：Highest Response Ratio First）响应比 R=响应时间/要求服务时间=（等待时间+要求服务时间）/要求服务时间=1+（等待时间/要求服务时间）,23,基于优先数调度算法（HPF：Highest Priority First）（a）由用户规定优先数（外部优先数）用户提交作业时，根据急迫程度规定适当的优先数，作业调度程序根据JCB优先数决定进入内存的次序。（b）由系统计算优先数（内部优先数）例：可按如下公式计算作业的优先数：优先数=用户规定优先数作业处理时间+作业等待时间输出量,24,25,26,27,28,29,30,31,32,基于时间片的轮转调度算法,1.时间片轮转时间片大小的确定太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求；T=nq就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）,基于时间片的轮转调度算法（2）,2.多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间短作业一次完成；中型作业周转时间不长；大型作业不会长期不处理。,就绪队列1,至CPU,S1,就绪队列2,S2,至CPU,就绪队列3,S3,至CPU,就绪队列n,Sn,至CPU,时间片：S1S2S3,图35多级队列反馈调度算法,36,进程调度算法,对下表，分别采用先来先服务（FCFS）、非抢占最短进程优先（SPF）及抢占的最短剩余时间优先（SRT）、高响应比优先（HRRN）、时间片轮转（RR,时间片q=1）、多级反馈队列（FB，第i级队列的时间片=2i-1）调度算法进行CPU调度，求出各进程的执行情况以及平均周转时间和平均带权周转时间。,FCFS 的调度性能,同样，看到进程E的不利情况。,先来先服务（FCFS）,短作业/进程优先（SJ(P)F）,降低对长进程有利的一种方法就是短进程优先策略：,表 SPF 的调度性能,=1.84,0,3,11,15,9,3,9,15,20,11,TA=3,TB=7,TC=11,TD=14,TE=3,=7.60,8,3,6,4,5,2,2,0,4,6,A,B,C,D,E,WE=1.50,WA=1,WB=1.17,WC=2.75,WD=2.80,E,C,D,A,B,周转时间T=结束时间Tc-到达时间Tin=3-0=3,周转时间 T,带权周转时间W=周转时间T/服务时间Tr=3/3=1,带权周转时 间W,平均,SJF对短作业有利，明显的作业E提前接受了服务，并且整体性能也得到了提高；SJF的问题：,SJF需要事先知道或至少需要估计每个作业所需的处理机时间。,只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”。,SJF 偏向短作业，不利于分时系统（由于不可抢占性）。,短作业/进程优先（SJF）,表 HRRN的调度性能,=2.14,0,3,9,15,13,3,9,13,20,15,TA=3,TB=7,TC=9,TD=14,TE=7,=8.00,8,3,6,4,5,2,2,0,4,6,A,B,C,D,E,WE=3.50,WA=1,WB=1.17,WC=2.25,WD=2.80,E,C,D,A,B,周转时间T=结束时间Tc-到达时间Tin=3-0=3,周转时间 T,带权周转时间W=周转时间T/服务时间Tr=3/3=1,带权周转时 间W,平均,=(9-4)+4/4=2.25,=(9-6)+5/5=1.6,=(9-8)+2/2=1.5,RC,RD,RE,RD,=(13-6)+5/5=2.4,RE,=(13-8)+2/2=3.5,最高响应比（HRRN）,不同调度算法对的性能分析:,进程调度算法,最短剩余时间（SRT）,SRT是针对 SPF 增加了强占机制的一种调度算法，它总是选择预期剩余时间最短的进程。只要新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程。SRT不象FCFS偏向长进程，也不象轮转法（下个算法）产生额外的中断，从而减少了开销。必须记录过去的服务时间，从而增加了开销。从周转时间来看，SRT 比SPF 有更好的性能。,处理机调度,表 SRT 的调度性能,=1.59,0,3,4,15,8,3,15,8,20,10,TA=3,TB=13,TC=4,TD=14,TE=2,=7.20,8,3,6,4,5,2,2,0,4,6,A,B,C,B,E,WE=1.00,WA=1,WB=2.17,WC=1.00,WD=2.80,E,C,D,A,B,周转时间T=结束时间Tc-到达时间Tin=3-0=3,周转时间 T,带权周转时间W=周转时间T/服务时间Tr=3/3=1,带权周转时 间W,平均,D,B剩余时间=6-1=5；,C剩余时间=4-0=4；,0,5,0,0,最短剩余时间（SRT）,不同调度算法的性能对比分析:,表 RR 的调度性能,周转时间 T,带权周转时 间W,=2.71,0,2,5,7,10,4,18,17,20,15,TA=4,TB=16,TC=13,TD=14,TE=7,=10.80,8,3,6,4,5,2,2,0,4,6,WE=3.50,WA=1.33,WB=2.67,WC=3.25,WD=2.80,E,C,D,A,B,平均,轮转（RRRound Robin）,调度算法（对同样进程情况下，5个算法比较）,47,FCFS,SPF(非抢占),SRT(抢占),48,HRRF,RR(q=1),FB(q=2i-1),（不立即抢占）,FB(q=2i-1),（立即抢占）,49,50,各种常用调度算法的比较表,不适合作业调度,51,作业调度与进程调度,有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。如下表所示(作业的优先数即为进程的优先数，优先数越小越好)。（1）列出所有作业进入内存时刻及结束时刻？（2）计算平均周转时间？,52,解：,（1）作业A、B、C、D进入内存时刻分别为：10:00、10:20、11:10、10:50。它们的结束时刻为：11:10、10:50、12:00、12:20。（2）作业A、B、C、D的周转时间分别为70，30，90，90分钟，平均周转时间为70分钟。,A,B,C,D,3.4.1实现实时调度的基本条件1提供必要的调度信息（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；2系统处理能力强,3.4实时调度,Ci为处理时间，Pi为周期时间（基于周期性实时任务）,3.4.1实现实时调度的基本条件3.采用抢占调度方式剥夺方式：一般都采用此方式非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。4.具有快速切换机制具有快速响应外部中断能力。快速任务分派,3.3实时调度,实时调度算法的分类,1.非抢占式调度算法时间片轮转 秒级非抢占优先权 秒-毫秒级2.抢占式调度算法时钟中断抢占优先权 毫秒级基于抢占点抢占立即抢占immediate preemption 毫秒-微秒级只要不在临界区即抢占（中断引发）,进程1,进程2,进程n,实时进程,调度时间,实时进程请求调度,调度实时进程运行,a 非抢占式轮转调度,当前进程,实时进程,实时进程请求调度,当前进程运行完成,b 非抢占式优先权调度,调度时间,c 基于时钟中断抢占的优先权调度,当前进程,实时进程,实时进程请求调度,实时进程抢占当前进程，并立即执行,d 立即抢占的优先权调度,当前进程,实时进程,实时进程请求调度,时钟中断到来时,调度时间,调度时间,常用的几种实时调度算法,1.最早截止时间优先EDF（earliest deadline first)算法根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式,最早截止时间优先算法既可以用于抢占式也可用于非抢占式方式中。图3-9给出了该算法用于非抢占式调度方式示例。在该例子中具有四个非周期任务，它们先后到达。,任务1,任务执行任务到达,任务1,t,图3-9 EDF算法用于非抢占式点的调度方式,任务3,任务4,任务2,任务2,任务3,任务4,开始截止时间：,最早截止时间优先（EDF）,图310 最早截止时间优先算法用于抢占调度方式之例,2.最低松弛度优先LLF算法,松弛度：根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度越高，该任务的优先级就越高，使之优先执行。若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：2001001090主要用于可抢占的调度方式中在实现该算法时，要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的（数值小的）任务排在队列的前面。,假如一个实时系统中有两个周期性实时任务，A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间25ms。对于A，合适截止时间依次为20、40、60、80、100;对于B，合适截止时间依次为50、100、150;图3-11 给出了A和 B截止的时间点。,图3-11 A和B任务每次必须完成的时间,最低松弛度优先（LLF）,松弛度=必须完成的时间点-本身所需运行时间-当前时间:,A1(10),B1(20),0 10 20 30 40 50 60 70 80 90 100,t1 t2 t3 t4 t5 t6 t7 t8,t,图3.12 利用LLF算法对两个周期性实时任务进行调度,A2(10),A3(10),A4(10),B1(5),B2(15),B2(10),初始：t=0时刻，计算A，B松弛度：,A1=20 10 0=10,B1=50 25 0=25,t=10时刻，计算A，B松弛度：,A2=40 10 10=20,B1=50 25 10=15,t=30时刻，计算A，B松弛度：,A2=40 10 30=0,B1=50 5 30=15,t=40时刻，计算A，B松弛度：,A3=60 10 40=10,B1=50 5 40=5,t=45时刻，计算A，B松弛度：,A3=60 10 45=5,B2=100 25 45=30,t=55时刻，计算A，B松弛度：,A4=80 10 55=35,B2=100 25 55=20,t=70时刻，计算A，B松弛度：,A4=80 10 70=0,B2=100 10 70=20,t=80时刻，计算A，B松弛度：,A5=100 10 80=10,B2=100 10 80=10,最低松弛度优先（LLF）,64,65,3.5产生死锁的原因和必要条件,3.5.1产生死锁的原因。1、竞争资源引起死锁。1）可剥夺（CPU、内存）和非剥夺性（打印机，磁带机）资源2）竞争非剥夺性资源可造成死锁,p1,p2,R1,R2,图3-13I/O设备共享时的死锁情况,3.5产生死锁的原因和必要条件,3）竞争临时性资源临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。,图3-14进程之间通信时的死锁,2、进程推进顺序不当引起死锁。,2,1,3,D,P2Req(R2),P2Req(R1),P1Req(R1),P1Req(R2),P2Rel(R2),P2Rel(R1),P1Rel(R1),P1Rel(R2),4,图3-15进程推进顺序对死锁的影响,3.5.2 产生死锁的必要条件,1互斥条件（资源的临界性）2请求和保持条件3不剥夺条件4环路等待条件,处理死锁的基本方法,1预防死锁：破坏4个条件之一：有效，使资源利用率低。2避免死锁：防止进入不安全态。3检测死锁：检测到死锁再清除。4解除死锁：与“检测”配套。,3.6 死锁预防和避免,3.6.1 死锁预防 1、互斥条件是资源固有属性，不能避免。2、摒弃请求和保持条件全分配，全释放（AND同步p52）优点：简单且安全缺点：（1）资源严重浪费（2）延迟进程运行3、摒弃“不剥夺”条件增加系统开销，且进程前段工作可能失效。,3.6 死锁预防和避免,3.6.1 死锁预防 4、摒弃“环路等待”条件有序资源分配法：为资源编号，申请时需按编号进行。缺点：（1）新增资源不便，（原序号已排定）（2）资源与进程使用顺序不同造成浪费（3）用户不自由,3.6.2 系统的安全状态,在“避免死锁”方法中的判断条件 1.安全状态系统按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。,74,3.6.2 系统的安全状态（2）,2.安全状态例,安全序列：p2p1p3,3.6.2 系统的安全状态（3）,3安全不安全的转换 上例中，若P3再申请一台，则不安全,利用银行家算法避免死锁,1数据结构availablej=k:系统现有Rj类资源k个；maxi,j=k:进程i需要Rj的最大数k个；alloci,j=k:进程i已得到Rj类资源k个；needi,j=k:进程i需要Rj类资源k个有：needi,j=maxi,jalloci,jrequesti进程i请求资源数worki：进程i执行完后系统应有资源数（也即可用数）finishi：布尔量，表进程i能否顺序完成。,2银行家算法,reqi=needi,error,reqi=avail,block,avail=avail-reqialloci=alloci+reqineedi=needi-reqi,系统安全？,Y,N,Y,N,Y,N,正式将资源分配给进程Pi,撤销本次分配让进程Pi等待,3安全性算法,设置两个向量 工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目 Finish:它表示系统是否有足够的资源分配给进程，使之运行完成(2)从进程集合中找到一个能满足下述条件的进程：Finishi=false;Needi,jWorkj；若找到，执行步骤(3)，否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Workj+Allocationi,j;Finishi=true;go to step 2;(4)如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。,4实例,图 3-16 T0时刻的资源分配表,4实例,图 3-17 T0时刻的安全序列,4实例,图 3-18 P1申请资源时的安全性检查,图 3-19 为P0分配资源后的有关资源数据,3.7死锁的检测和解除,检测1.资源分配图,p1,p2,r1,r2,图3-20 每类资源有多个时的情况,3.7死锁的检测和解除,2.死锁定理简化资源分配图若能完全简化则消去所有的边。定理：死锁状态的充分条件，资源分配图不可完全简化,Work:=availableL:=Li|alloci=0reqi=0/*孤立进程点*/For all Li L do BeginFor all reqi=work doBeginWork:=work+allociL=LiLEnd EndDeadlock:=(L=p1 pn),3.检测死锁的算法：,剥夺资源。(2)撤消进程。,3.7.2 死锁的解除,检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不行，继续回退，,3.7.2 死锁的解除（2）,为把系统从死锁状态中解脱出来，所花费的代价可表示为：R(S)min=minCui+minCuj+minCuk+,图3-22 付出代价最小的死锁解除方法,89,例,设系统仅有一类数量为M的独占型资源，系统中N个进程竞争该类资源，其中各进程对该类资源的最大需求为W。当M，N，W分别取下列值时，试判断下列哪些情况会发生死锁？为什么？M=2;N=2，W=2；(2)M=3;N=2，W=2；(3)M=3;N=2，W=3；(4)M=5;N=3，W=2；(5)M=6;N=3，W=3；,90,解,判断是否发生死锁，可用以下经验公式：公式表明，若要系统不发生死锁，则进程的最大需求量W不得超过x；若超过则可能导致死锁。利用资源分配图举一个死锁例子便可。,91,将M、N代入公式，得到以下结果：(1)x=1,xW，不会死锁；(5)x=8/3;xW，可能会死锁；,92,例,一台计算机有10台磁带机被n个进程竞争，每个进程最多需要3台磁带机，那么n最多为_时，系统没有死锁的危险？解：n最大为4。假设有m个资源，每个进程最多可申请k个资源，则系统要想避免死锁的发生，允许的最多进程数n为1+（m-k）/（k-1）。当后面一项是小数时，总是取小整数。,习题,P115：18，20，21，22,