第三章 处理机调度与死锁New

1、 3.1 3.1 处理机调度的层次处理机调度的层次3.2 3.2 调度队列模型和调度准则调度队列模型和调度准则3.3 3.3 调度算法调度算法 3.4 3.4 实时调度实时调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 n理解处理机调度的概念和调度的层次理解处理机调度的概念和调度的层次n掌握各种作业、进程调度算法和实时调掌握各种作业、进程调度算法和实时调度算法度算法n理解死锁的基本概念理解死锁的基本概念n掌握死锁的处理方法掌握死锁的处理方法教学重点教学重点：各种作业、进程调度

2、算法和死锁：各种作业、进程调度算法和死锁 的处理方法等。的处理方法等。教学难点教学难点：作业、进程调度算法：作业、进程调度算法, 死锁死锁 对资源进行有效的调度是非常必要的，我对资源进行有效的调度是非常必要的，我们生活中也会经常遇到，如：调度银行出纳们生活中也会经常遇到，如：调度银行出纳员服务顾客请求问题等。员服务顾客请求问题等。 CPUCPU是计算机系统中的一个十分重要的资是计算机系统中的一个十分重要的资源，对它进行高效的调度是操作系统设计的源，对它进行高效的调度是操作系统设计的中心问题之一。中心问题之一。 （作业调度、长程调度、接纳调度）（作业调度、长程调度、接纳调度）1 1、作业和作业步

3、、作业和作业步n作业：包含程序、数据和作业说明书作业：包含程序、数据和作业说明书。n作业步：作业执行过程中的每一个加工步骤作业步：作业执行过程中的每一个加工步骤n作业流：作业进入系统，依次存于外存形成作业流作业流：作业进入系统，依次存于外存形成作业流2 2、作业控制块（、作业控制块（JCBJCB）n它是作业在系统中存在的标志，其中保存了系统它是作业在系统中存在的标志，其中保存了系统 对作业进行管理和调度所需的全部信息。对作业进行管理和调度所需的全部信息。n内容：内容：n作业标识，用户名，作业类型，作业状态，调度信息等作业标识，用户名，作业类型，作业状态，调度信息等n进入系统进入系统 建立建立J

4、CB-JCB-插入相应后备队列插入相应后备队列-作业调度作业调度- - 作业控制作业控制 作业结束作业结束 回收资源回收资源3 3、作业调度、作业调度n将外存作业调入内存，创建将外存作业调入内存，创建PCBPCB等，插入就绪队等，插入就绪队列。列。n一般用于批处理系统，分一般用于批处理系统，分/ /实时系统一般直接入实时系统一般直接入内存，无此环节。内存，无此环节。n调度特性调度特性n接纳作业数（内存驻留数，多道程序度）接纳作业数（内存驻留数，多道程序度）太多太多 周转时间周转时间T T长长太少太少 系统效率低系统效率低n接纳策略：即采用何种调度算法：接纳策略：即采用何种调度算法：FCFSFC

5、FS、短作业、短作业优先等优先等（进程调度，短程调度）（进程调度，短程调度）主要是决定就绪队列中的哪个进程应获得处理机，主要是决定就绪队列中的哪个进程应获得处理机，然后由分派程序（然后由分派程序（DispatcherDispatcher）分派处理机。）分派处理机。1.1.低级调度的功能：低级调度的功能：n保存处理机现场信息保存处理机现场信息n按某种算法选取进程按某种算法选取进程n把处理机分配给进程把处理机分配给进程2.2.进程调度的三个进步机制进程调度的三个进步机制n排队器排队器n分派器分派器n上下文切换机制：两对切换上下文切换机制：两对切换CPU Switch From Process to

6、 Process3.3.进程调度方式：进程调度方式：1)1)非抢占方式：非抢占方式：简单、系统开销小，实时性差简单、系统开销小，实时性差 ( (如如win31)win31)2)2)抢占方式抢占方式（1 1）优先权原则）优先权原则（2 2）短进程优先原则）短进程优先原则（3 3）时间片原则）时间片原则n引起进程调度的因素有哪些引起进程调度的因素有哪些？n进程正常终止或异常终止进程正常终止或异常终止n进程因某种原因阻塞：进程因某种原因阻塞：I/OI/O请求；请求；waitwait操作等操作等n时间片用完时间片用完n抢占方式下，就绪队列中某进程的优先权比当前执行抢占方式下，就绪队列中某进程的优先权比

7、当前执行的进程高的进程高运行频率运行频率n低低 中中 高高。1.1.仅有进程调度的队列模型仅有进程调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列交互用户交互用户时间片完时间片完进程调度进程调度进程完成进程完成等待事件等待事件事件出现事件出现2.2.具有高、低级调度的队列模型具有高、低级调度的队列模型就绪队列就绪队列CPU阻塞队列阻塞队列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现后备队列后备队列阻塞队列阻塞队列等待事件等待事件2事件事件2出现出现作业调度作业调度就绪队列就绪队列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进

8、程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻塞队列阻塞队列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业 1 1、面向用户的准则、面向用户的准则（1 1）周转时间短（常用于批处理系统）周转时间短（常用于批处理系统）概念：作业从提交概念：作业从提交 完成的时完成的时间间. .分为：分为：n驻外存等待调度时间驻外存等待调度时间n驻内存等待调度时间驻内存等待调度时间n执行时间执行时间n阻塞时间阻塞时间1 1、面向用户的准则、面向用户的准则n平均周转时间平均周转时间n平均带权平均带权 n可见带权可见带权w w越小越好越小越好,T

9、s,Ts为实际服务时间。为实际服务时间。 11niiTnT11niisiTWnT1 1、面向用户的准则、面向用户的准则（2 2）响应时间快：（对交互性作业）响应时间快：（对交互性作业）概念：键盘提交请求到首次响应时间概念：键盘提交请求到首次响应时间n输入传送时间输入传送时间n处理时间处理时间n响应传送时间响应传送时间（3 3）截止时间的保证（特别是实时系统）截止时间的保证（特别是实时系统）（4 4）优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度） 2 2、面向系统的准则、面向系统的准则（1 1）吞吐量高（特别是批处理）：单位时）吞吐量高（特别是批处理）：单位时间完成作业数间完成作业

10、数（2 2）处理机利用率好：（因）处理机利用率好：（因CPUCPU贵，特别贵，特别是大中型多用户系统）是大中型多用户系统）（3 3）各类资源的平衡利用。）各类资源的平衡利用。 3.3.13.3.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法1.1.先来先服务调度算法（先来先服务调度算法（FCFSFCFS）n特点：简单，有利于长作业（进程）特点：简单，有利于长作业（进程） 即即CPUCPU繁忙繁忙性作业性作业, ,不利于短作业（进程）不利于短作业（进程）2.2.短作业（进程）优先调度算法：短作业（进程）优先调度算法：SJ(P)FSJ(P)Fn提高了平均周转时间和平

11、均带权周转时间（从而提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）提高了系统吞吐量）n特点：对长作业不利，有可能得不到服务特点：对长作业不利，有可能得不到服务n估计时间不易确定估计时间不易确定 先来先服务算法实例先来先服务算法实例图图3-4 FCFS3-4 FCFS和和SJ(P)FSJ(P)F比较比较1.1.优先权调度算法类型优先权调度算法类型n非抢占式优先权算法非抢占式优先权算法n抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。2.2.优先权类型：优先权类型：1 1）静态优先权：）静态优先权：n进程优先权在整个运行期不变。进程优先权在整个运行期不变。n确定优先权依据

12、确定优先权依据n进程类型进程类型n进程对资源的需求；进程对资源的需求；n根据用户需求。根据用户需求。n特点：简单，但低优先权作业可能长期不被调特点：简单，但低优先权作业可能长期不被调度（饥饿）。度（饥饿）。 （例子（例子MIT IBM7049 MIT IBM7049 ）2 2）动态优先权：）动态优先权：n如：优先权随执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时间而升高。n优点：长短兼顾优点：长短兼顾 缺点：需经常计算各进程优先缺点：需经常计算各进程优先级级3.3.高响应比优先调度算法：高响应比优先调度算法：n响应比响应比RpRp= =（Tw+TsTw+Ts）/Ts/T

13、sn特点：特点：n（1 1）短作业）短作业R RP P大。大。n（2 2）TsTs（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于FCFSFCFS。n（3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。22l 先来先服务算法（先来先服务算法（FCFSFCFS：First Come First ServeFirst Come First Serve）l 最短作业优先算法（最短作业优先算法（SJFSJF：Shortest Job FirstShortest Job First）l 最短剩余时间优先（最短剩余时间优先（SRTF: Shortest Rema

14、ining SRTF: Shortest Remaining Time FirstTime First）l 最高响应比优先算法（最高响应比优先算法（HRRFHRRF：Highest Response Highest Response Ratio FirstRatio First）响应比响应比 R R = 响应时间/要求服务时间 =（等待时间+要求服务时间）/要求服务时间 = 1 +（等待时间/要求服务时间）23l基于优先数调度算法基于优先数调度算法（HPF：Highest Priority First）（a）由用户规定优先数（外部优先数）用户提交作业时，根据急迫程度规定适当的优先数，作业调度程

15、序根据JCB优先数决定进入内存的次序。（b）由系统计算优先数（内部优先数）例：可按如下公式计算作业的优先数：优先数= 用户规定优先数作业处理时间+ 作业等待时间输出量2425262728293031321.1.时间片轮转时间片轮转n时间片大小的确定时间片大小的确定n太大：退化为太大：退化为FCFSFCFS；n太小：系统开销过大太小：系统开销过大n系统对响应时间的要求；系统对响应时间的要求；T=nqT=nqn就绪队列中进程的数目；就绪队列中进程的数目；n系统的处理能力：（应保证一个时间片处系统的处理能力：（应保证一个时间片处理完常用命令）理完常用命令）2.2.多级反馈队列调度多级反馈队列调度n特

16、点：长、短作业兼顾，有较好的响应时特点：长、短作业兼顾，有较好的响应时间间n短作业一次完成；短作业一次完成；n中型作业周转时间不长；中型作业周转时间不长；n大型作业不会长期不处理。大型作业不会长期不处理。就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2S3图图35多级队列反馈调度算法多级队列反馈调度算法36进程调度算法进程调度算法对下表，分别采用先来先服务（对下表，分别采用先来先服务（FCFS）、非抢占最）、非抢占最短进程优先（短进程优先（SPF）及抢占的最短剩余时间优先）及

17、抢占的最短剩余时间优先（SRT）、高响应比优先（）、高响应比优先（HRRN）、时间片轮转）、时间片轮转（RR,时间片时间片q=1）、多级反馈队列（）、多级反馈队列（FB，第，第i级队级队列的时间片列的时间片=2i-1）调度算法进行）调度算法进行CPU调度，求出各调度，求出各进程的执行情况以及平均周转时间和平均带权周转进程的执行情况以及平均周转时间和平均带权周转时间。时间。进程到达时间服务时间A03B26C44D65E82 FCFS 的调度性能 TW进程到达时间Tin服务时间Tr开始时间Ts 结束时间Tc周转时间T带权周转时间WA0303TA=3WA=1B2639TB=7WB=1.17C4491

18、3TC=9WC=2.25D651318TD=12WD=2.40.E821820TE=12WE=6平均 =8.60 = 2.56同样，看到进程同样，看到进程E的不利情况。的不利情况。 先来先服务（先来先服务（FCFS） 短作业短作业/进程优先（进程优先（SJ(P)F） 降低对长进程有利的一种方法就是短进程优先策略： 表 SPF 的调度性能 WT进程到达时间Tin服务时间Tr开始时间Ts 结束时间Tc = =1.841.840 03 3111115159 93 39 9151520201111T TA A=3=3T TB B=7=7T TC C=11=11T TD D=14=14T TE E=3=

19、3= =7.607.608 83 36 64 45 52 22 20 04 46 6ABCDEW WE E=1.50=1.50W WA A=1=1W WB B=1.17=1.17W WC C=2.75=2.75W WD D=2.80=2.80E EC CD DA AB B周转时间周转时间T=T=结束时间结束时间T Tc c- -到达时间到达时间T Tinin=3-0=3=3-0=3周转时间周转时间 T T带权周转时间带权周转时间W W= =周转周转时间时间T/T/服务时间服务时间T Tr r=3/3=1=3/3=1带权周转时带权周转时 间间W W平均平均结束结束下下一一步步下下一一步步下下一一

20、步步下下一一步步下下一一步步下下一一步步下下一一步步 SJF对短作业有利，明显的作业E提前接受了服务，并且整体性能也得到了提高；SJF的问题： n SJF需要事先知道或至少需要估计每个作业所需估计每个作业所需的处理机时间的处理机时间。n 只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”。 n SJF 偏向短作业，不利于分时系统（由于不可抢占性）。 短作业短作业/进程优先（进程优先（SJF） 表 HRRN的调度性能 WT进程到达时间Tin服务时间Tr开始时间Ts 结束时间Tc =2=2.14.140 03 39 9151513133 39 9131320201515T TA

21、A=3=3T TB B=7=7T TC C=9=9T TD D=14=14T TE E=7=7= =8.008.008 83 36 64 45 52 22 20 04 46 6ABCDE W WE E=3.50=3.50W WA A=1=1W WB B=1.17=1.17W WC C=2.25=2.25W WD D=2.80=2.80E EC CD DA AB B周转时间周转时间T=T=结束时间结束时间T Tc c- -到达时间到达时间T Tinin=3-0=3=3-0=3周转时间周转时间 T T带权周转时间带权周转时间W W= =周转周转时间时间T/T/服务时间服务时间T Tr r=3/3=

22、1=3/3=1带权周转时带权周转时 间间W W平均平均=(9-4)+4/4=2.25=(9-6)+5/5=1.6=(9-8)+2/2=1.5RCRDRERD=(13-6)+5/5=2.4RE=(13-8)+2/2=3.5结束结束下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步 最高响应比（最高响应比（HRRNHRRN）不同调度算法对的性能分析不同调度算法对的性能分析:W进程到达时间Tin服务时间Tr从平均周转时间及其平从平均周转时间及其平均带权周转时间来看，均带权周转时间来看，HRRN 刚好介于刚好介于FCFS与与SPF之间，即好于之间，即好于FCFS，次于，次于SPF。 A A0

23、 03B B2 26C C4 44D D6 65E E8 82FCFS8.602.56SPF7.601.84HRRN8.002.14T进程进程调度算法调度算法 最短剩余时间（最短剩余时间（SRT） SRT是针对 SPF 增加了强占机制强占机制的一种调度算法，它总是选择预期剩余时间最短的进程选择预期剩余时间最短的进程。只要新进程就绪新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程。 SRT不象FCFS偏向长进程，也不象轮转法（下个算法）产生额外的中断，从而减少了开销减少了开销。 必须记录过去的服务时间，从而增加了开销增加了开销。 从周转时间来看，SRT 比SPF 有更好的性能

24、。处理机调度处理机调度 表 SRT 的调度性能 WT进程到达时间Tin服务时间Tr开始时间Ts 结束时间Tc =1=1.59.590 03 34 415158 83 315158 820201010T TA A=3=3T TB B=13=13T TC C=4=4T TD D=14=14T TE E=2=2=7=7.20.208 83 36 64 45 52 22 20 04 46 6ABCBE W WE E=1.00=1.00W WA A=1=1W WB B=2.17=2.17W WC C=1.00=1.00W WD D=2.80=2.80E EC CD DA AB B周转时间周转时间T=T=

25、结束时间结束时间T Tc c- -到达时间到达时间T Tinin=3-0=3=3-0=3周转时间周转时间 T T带权周转时间带权周转时间W W= =周转周转时间时间T/T/服务时间服务时间T Tr r=3/3=1=3/3=1带权周转时带权周转时 间间W W平均平均01234567891011121314151617181920DB剩余时间=6-1=5；C剩余时间=4-0=4；0500结束结束下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步 最短剩余时间（最短剩余时间（SRT） 不同调度算法的性能对比分析不同调度算法的性能对比分析:W进程到达时间Tin服务时间Tr从平均周

26、转时间及其平从平均周转时间及其平均带权周转时间来看，均带权周转时间来看，SRT 好于前面的任何好于前面的任何一个算法。一个算法。 A A0 03B B2 26C C4 44D D6 65E E8 82FCFS8.602.56SPF7.601.84HRRN8.002.14SRT7.201.59T 表 RR 的调度性能 进程到达时间Tin服务时间Tr开始时间Ts 结束时间Tc 周转时间周转时间 T T带权周转时带权周转时 间间W WWT= =2.712.710 02 25 57 710104 41818171720201515T TA A=4=4T TB B=16=16T TC C=13=13T

27、TD D=14=14T TE E=7=7= =10.8010.808 83 36 64 45 52 22 20 04 46 6W WE E=3.50=3.50W WA A=1.33=1.33W WB B=2.67=2.67W WC C=3.25=3.25W WD D=2.80=2.80E EC CD DA AB B平均平均 轮转（轮转（RRRound Robin） 调度算法（调度算法（对同样进程情况下，5个算法比较）FCFS A B C D ESPF A B C D EHRRN A B C D ESRT A B C D ERR Aq=1 B C D E 0 5 10 15 20各种调度算法的比

28、较47FCFSSPF(非抢占)SRT(抢占)48HRRFRR(q=1)FB(q=2i-1)（不立即抢占）FB(q=2i-1)（立即抢占）49进程ABCDE平均FCFS完成时间周转时间带权周转时间331.0971.171392.2518122.420126.08.62.56SPF（非抢占）完成时间周转时间带权周转时间331.0971.1715112.7520142.81131.57.61.84SPF（抢占）完成时间周转时间带权周转时间331.015132.16841.020142.81021.07.21.59HRRN完成时间周转时间带权周转时间331.0971.171392.2520142.81

29、573.582.14RR（q=1 ）完成时间周转时间带权周转时间441.3318162.6717133.2520142.81573.510.82.71FB( q=2i-1)（不立即抢占）完成时间周转时间带权周转时间33117152.518143.520142.81463.010.42.56FB( q=2i-1)（立即抢占）完成时间周转时间带权周转时间341.3317162.6718112.7520142.81484.010.62.7150 算法比较项FCFSRRSJFSRTHRPMFQ调度方式非抢占式抢占式(按时间片)非抢占式抢占式(进程到达)非抢占式抢占式(按时间片)吞吐量不突出时间片太小,

30、可能变低高高高不突出响应时间可能很高，对于短进程提供良好的响应时间对短作业/进程提供良好响应时间提供良好的响应时间提供良好的响应时间不突出开销最小低可能高可能高可能高可能高对进程的作用不利于短作业/进程和I/O忙型公平对待不利于长作业/进程不利于长进程良好的均衡（进程）可能偏向I/O繁忙的作业/进程饥饿问题无无可能可能无可能各种常用调度算法的比较表不适合作业调度不适合作业调度51作业调度与进程调度作业调度与进程调度有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。如下表所示(作业的优先数即为进程的优先数，优先数越小越好)。（1）列出所

31、有作业进入内存时刻及结束时刻？（2）计算平均周转时间？作业名作业名 到达时间到达时间 估计运行时间估计运行时间优先数优先数A10:00405B10:20303C10:30504D10:5020652解：（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分钟。ABCD3 3.4.1.4.1实现实时调度的基本条件实现实时调度的基本条件1 1提供必要的调度信息提供必要的调度信息（1 1）就绪时间；）就绪时间

32、；（2 2）开始）开始/ /完成截止时间；完成截止时间；（3 3）处理时间；）处理时间；（4 4）资源要求；）资源要求；（5 5）优先级；）优先级；2 2系统处理能力强系统处理能力强NPCPCmiiimiii111Ci为处理时间，为处理时间，Pi为周期时间（基于周期性实时任务）为周期时间（基于周期性实时任务）3 3.4.1.4.1实现实时调度的基本条件实现实时调度的基本条件3.3.采用抢占调度方式采用抢占调度方式n剥夺方式：一般都采用此方式剥夺方式：一般都采用此方式n非剥夺方式（实现简单）：一般应使实时任务非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃较小，以及时放弃CPUCPU。4

33、.4.具有快速切换机制具有快速切换机制n具有快速响应外部中断能力。具有快速响应外部中断能力。n快速任务分派快速任务分派1.1.非抢占式调度算法非抢占式调度算法n时间片轮转时间片轮转 秒级秒级n非抢占优先权非抢占优先权 秒秒- -毫秒级毫秒级2.2.抢占式调度算法抢占式调度算法n时钟中断抢占优先权时钟中断抢占优先权 毫秒级毫秒级n基于抢占点抢占基于抢占点抢占n立即抢占立即抢占immediate preemption immediate preemption 毫秒毫秒- -微秒级微秒级n只要不在临界区即抢占（中断引发）只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间调度时间实时进

34、程请求调度实时进程请求调度调度实时进程运行调度实时进程运行a 非抢占式轮转调度非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程请求调度当前进程运行完成当前进程运行完成b 非抢占式优先权调度非抢占式优先权调度调度时间调度时间c 基于时钟中断抢占的优先权调度基于时钟中断抢占的优先权调度当前进程实时进程实时进程请求调度实时进程请求调度实时进程抢占当前实时进程抢占当前进程，并立即执行进程，并立即执行d 立即抢占的优先权调度立即抢占的优先权调度当前进程实时进程实时进程请求调度实时进程请求调度时钟中断到来时时钟中断到来时调度时间调度时间调度时间调度时间1.1.最早截止时间优先最早截止时间优先EDF

35、EDF（earliest deadline earliest deadline first)first)算法算法n根据任务的截止时间来确定任务的优先级根据任务的截止时间来确定任务的优先级n截止时间越早，优先级越高截止时间越早，优先级越高n可以是抢占式或非抢占式可以是抢占式或非抢占式最早截止时间优先算法既可以用于抢占式也可用于非抢占式方式中。图3-9给出了该算法用于非抢占式调度方式示例。在该例子中具有四个非周期任务，它们先后到达。 任务1任务执行任务到达任务任务1 1t图3-9 EDF算法用于非抢占式点的调度方式任务3任务4任务2任务任务2任务任务3任务任务4开始截止时间开始截止时间： 任务1的

36、任务3的 任务4的任务2的结束结束下下一一步步下下一一步步 最早截止时间优先（最早截止时间优先（EDF） 图310 最早截止时间优先算法用于抢占调度方式之例2 2. . 最低松弛度优先最低松弛度优先LLFLLF算法算法n松弛度：松弛度：n根据任务紧急（或松弛）的程度，来确定任务的优先级。根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度越高，该任务的优先级就越高，使之优任务的紧急程度越高，该任务的优先级就越高，使之优先执行。先执行。n若若A A进程进程需在需在200ms200ms时完成，其本身运行需要时完成，其本身运行需要100ms100ms，当，当前时刻是前时刻是10ms10m

37、s，则，则A A的松弛度为：的松弛度为：20020010010010109090n主要用于可抢占的调度方式中主要用于可抢占的调度方式中n在实现该算法时，要求系统中有一个在实现该算法时，要求系统中有一个按松弛度排序的实按松弛度排序的实时任务就绪队列，松弛度最低的（数值小的）任务排在时任务就绪队列，松弛度最低的（数值小的）任务排在队列的前面。队列的前面。假如一个实时系统中有两个周期性实时任务周期性实时任务，A和和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间25ms。对于A，合适截止时间依次为20、40、60、80、100 ; 对于B，合适截止时间依

38、次为50、100、150 ; 图3-11 给出了A和 B截止的时间点。 图3-11 A和B任务每次必须完成的时间0 20 40 60 80 100 120 140 160 180 200A A A A A A A A A A t B B B 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(

39、10) A3(10)A4(10)B1(5)B2(15)B2(10)初始：t=0时刻，计算A，B松弛度：A1= 20 10 0 = 10B1= 50 25 0 = 25t=10时刻，计算A，B松弛度：A2= 40 10 10 = 20B1= 50 25 10 = 15t=30时刻，计算A，B松弛度：A2= 40 10 30 = 0B1= 50 5 30 = 15t=40时刻，计算A，B松弛度：A3= 60 10 40 = 10B1= 50 5 40 = 5t=45时刻，计算A，B松弛度：A3= 60 10 45 = 5B2= 100 25 45 = 30t=55时刻，计算A，B松弛度：A4= 8

40、0 10 55 = 35B2= 100 25 55 = 20t=70时刻，计算A，B松弛度：A4= 80 10 70 = 0B2= 100 10 70 = 20t=80时刻，计算A，B松弛度：A5= 100 10 80 = 10B2= 100 10 80 = 10结束结束下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步 最低松弛度优先（最低松弛度优先（LLF） 64653 3.5.5.1.1产生死锁的原因。产生死锁的原因。1 1、竞争资源引起死锁。、竞争资源引起死锁。1 1）可剥夺（）可剥夺（CPUCPU、内存）和非剥夺性（打印机，、内存）和非剥

41、夺性（打印机，磁带机）资源磁带机）资源2 2）竞争非剥夺性资源）竞争非剥夺性资源可造成死锁可造成死锁 p1p2R1R2图3-13I/O设备共享时的死锁情况3 3）竞争临时性资源）竞争临时性资源n临时性资源是指由一个进程产生，被另一个进临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。程使用一段时间后便无用的资源。P1P3S3S1P2S2图3-14进程之间通信时的死锁2 2、进程推进顺序不当引起死锁。、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(

42、R2)4图3-15进程推进顺序对死锁的影响1 1互斥条件（资源的临界性）互斥条件（资源的临界性）2 2请求和保持条件请求和保持条件3 3不剥夺条件不剥夺条件4 4环路等待条件环路等待条件 1 1预防死锁：预防死锁： 破坏破坏4 4个条件之一：有效，使资源利用率低。个条件之一：有效，使资源利用率低。2 2避免死锁：防止进入不安全态。避免死锁：防止进入不安全态。3 3检测死锁：检测到死锁再清除。检测死锁：检测到死锁再清除。4 4解除死锁：与解除死锁：与“检测检测”配套。配套。 3.6.1 3.6.1 死锁预防死锁预防 1 1、互斥条件是资源固有属性，不能避免。、互斥条件是资源固有属性，不能避免。2

43、 2、摒弃请求和保持条件、摒弃请求和保持条件全分配，全释放（全分配，全释放（ANDAND同步同步p52p52）优点：简单且安全优点：简单且安全缺点：（缺点：（1 1）资源严重浪费）资源严重浪费（2 2）延迟进程运行）延迟进程运行3 3、摒弃、摒弃“不剥夺不剥夺”条件条件增加系统开销，且进程前段工作可能失效。增加系统开销，且进程前段工作可能失效。 3.6.1 3.6.1 死锁预防死锁预防 4 4、摒弃、摒弃“环路等待环路等待”条件条件有序资源分配法：为资源编号，申请时需按编号进行。有序资源分配法：为资源编号，申请时需按编号进行。缺点：缺点：（1 1）新增资源不便，（原序号已排定）新增资源不便，（

44、原序号已排定）（2 2）资源与进程使用顺序不同造成浪费）资源与进程使用顺序不同造成浪费（3 3）用户不自由）用户不自由在在“避免死锁避免死锁”方法中的判断条件方法中的判断条件 1. 1. 安全状态安全状态n系统按某种顺序并发进程都能达到获得最大系统按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。资源而顺序完成的序列为安全序列。n能找到安全序列的状态为安全状态。能找到安全序列的状态为安全状态。742.2.安全状态例安全状态例进程进程最大需求最大需求已分配已分配可用可用P11053P242P392安全序列：安全序列：p2p2p1p1p3 p3 3 3安全安全不安全的转换不安全的转换 n上例中，若上例中，若P3P3再申请一台，则不安全再申请一台，则不安全 进程进程最大需求最