第03章计算机操作系统

1、第三章处理机调度与死锁 第三章处理机调度与死锁 3.1 处理机调度的层次处理机调度的层次3.2 调度队列模型和调度准则调度队列模型和调度准则3.3 调度算法调度算法3.4 实时调度实时调度 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.6 预防死锁的方法预防死锁的方法3.7 死锁的检测与解除死锁的检测与解除 第三章处理机调度与死锁 3.1处理机调度的层次处理机调度的层次 第三章处理机调度与死锁 3.1处理机调度的层次处理机调度的层次 第三章处理机调度与死锁 3.1处理机调度的层次处理机调度的层次 第三章处理机调度与死锁 (1) (1) 作业作业(Job)=(Job)=程序程序+

2、+数据数据+ +作业说明书作业说明书 系统根据说明书来对程序的运行进行控制。在批处理系系统根据说明书来对程序的运行进行控制。在批处理系统中，以作业为基本单位从外存调入内存的。统中，以作业为基本单位从外存调入内存的。 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 提交提交后备后备运行运行就绪就绪等待等待完成完成作业作业调度调度作业作业调度调度作业作业录入录入第三章处理机调度与死锁 3作业调度算法的选择作业调度算法的选择 第三章处理机调度与死锁 调度的对象是进程调度的对象是进程( (或内核级线程或内核级线程) )。进程调度是

3、最基本的。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的一种调度，在多道批处理、分时和实时三种类型的OSOS中，都必中，都必须配置这级调度。须配置这级调度。1 1低级调度的功能低级调度的功能低级调度用于决定就绪队列中的哪个进程低级调度用于决定就绪队列中的哪个进程( (或内核级线程或内核级线程) )应获得处理机，然后再由分派程序执行把处理机分配给该进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。的具体操作。第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 3 3进程调度方式（进程调度方式（两种）第三章处理机调度与

4、死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 3.2 调度队列模型和调度准则调度队列模型和调度准则 .1调度队列模型调度队列模型1 1仅有进程调度的调度队列模型（分时、实时仅有进程调度的调度队列模型（分时、实时OSOS）就 绪 队 列阻 塞 队 列进程调度CPU进程完成等待事件交互用户事件出现时间片完第三章处理机调度与死锁 2 2具有高级和低级调度的调度队列模型（批处理）具有高级和低级调度的调度队列模型（批处理）就 绪 队 列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现等待事件n事件n出现后 备 队 列第三章处理机调度与死锁 3 3同时

5、具有三级调度的调度队列模型同时具有三级调度的调度队列模型第三章处理机调度与死锁 图 3-3具有三级调度时的调度队列模型 就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现第三章处理机调度与死锁 niiTnT11第三章处理机调度与死锁 niiTTnW1s1第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 3.3调调 度度 算算 法法 第三章处理机调度与死锁 3.3调调 度度 算算 法法 1 1先来先服务调度算法先来先服务调度算法 第三

6、章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 图3-4FCFS和SJF调度算法的性能 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 作业作业提交时间提交时间执行时间执行时间开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转带权周转时间时间18.002.0028.500.5039.000.1049.500.20平均周转时间平均周转时间 t =平均带权周转时间平均带权周转时间 w = 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机

7、调度与死锁 第三章处理机调度与死锁 （HRN）HRN要求服务时间要求服务时间等待时间优先权第三章处理机调度与死锁 要求服务时间响应时间要求服务时间要求服务时间等待时间相应比PR第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 图3-5 q=1和q=4时的进程运行情况 ABCDEABCDEABCEACE(a) q1(b) q412345678910 11 12 13 14 15 16 17tA、B、C、D、E？A:4 B:3 C:4 D:2 E:4第三章处理机调度与死锁 图3-6 q=1和q=4时进程的周转时间 第三章处理机调

8、度与死锁 2 2多级反馈队列调度算法多级反馈队列调度算法第三章处理机调度与死锁 图 3-7多级反馈队列调度算法 就绪队列 1就绪队列 2就绪队列 3就绪队列 nS1S2S3至CPU至CPU至CPU至CPU(时间片： S1 S2 S3)第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 运行运行低优先就绪低优先就绪高优先就高优先就绪绪等待等待首先选择首先选择100ms其次选择其次选择500ms请求请求I/OI/O完成完成超时间片超时间片第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 运行运行低优先低优先就绪就绪高优高优先就先就绪绪因盘或带因盘或带I/O

9、而等而等待待进程调度进程调度500ms请求盘请求盘或带或带I/OI/O完成完成超时间片超时间片中优先中优先就绪就绪因终端因终端I/O而等而等待待因页面因页面I/O而等而等待待进程调度进程调度100ms进程调度进程调度100msI/O完成完成I/O完成完成请求终请求终端端I/O缺页中断缺页中断第三章处理机调度与死锁 思考思考n若在操作系统的就绪进程队列中等待运若在操作系统的就绪进程队列中等待运行的共有三个进程行的共有三个进程P1、P2、P3，已知它，已知它们各自的运行时间为们各自的运行时间为a、b、c，且满足关，且满足关系系a b c。请证明采用最短作业优先调。请证明采用最短作业优先调度算法能够

10、获得最小平均周转时间。度算法能够获得最小平均周转时间。第三章处理机调度与死锁 3.4实实 时时 调调 度度 1 1提供必要的信息提供必要的信息(1) (1) 就绪时间。就绪时间。(2) (2) 开始截止时间和完成截止时间。开始截止时间和完成截止时间。(3) (3) 处理时间。处理时间。(4) (4) 资源要求。资源要求。(5) (5) 优先级。优先级。2系统处理能力强系统处理能力强3采用抢占式调度机制采用抢占式调度机制 4具有快速切换机制具有快速切换机制第三章处理机调度与死锁 1 1非抢占式调度算法非抢占式调度算法1) 1) 非抢占式轮转调度算法非抢占式轮转调度算法数秒至数十秒的响应时间，可用

11、于要求不太严格的实时控制系统中。 2) 非抢占式优先调度算法非抢占式优先调度算法 获得仅为数秒至数百毫秒级的响应时间，因而可用于有一定要求的实时控制系统中。 第三章处理机调度与死锁 2 2抢占式调度算法抢占式调度算法在要求较严格的在要求较严格的( (响应时间为数响应时间为数十毫秒以下十毫秒以下) )的实时系统中，的实时系统中，应采用抢占式优先权调度算法。可根据抢占发生时间的不同而应采用抢占式优先权调度算法。可根据抢占发生时间的不同而进一步分成以下两种调度算法。进一步分成以下两种调度算法。1) 1) 基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法2) 2) 立即抢占立即抢占

12、(Immediate Preemption)(Immediate Preemption)的优先权调度算法的优先权调度算法第三章处理机调度与死锁 图3-8 实时进程调度 (a) 非抢占式轮转调度当前进程实时进程实时进程请求调度实时进程抢占当前进程并立即执行(d ) 立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b ) 非抢占式优先权调度当前进程实时进程实时进程请求调度 当前进程运行完成调度时间当前进程实时进程请求调度 时钟中断到来时调度时间(c) 基于时钟中断抢占的优先权抢占调度调度时间实时进程实时进程加入队尾等待下一个时间片实时进程加入队尾等待下

13、一个时间片实时进程加入队首实时进程加入队首阻塞第三章处理机调度与死锁 .3常用的几种实时调度算法常用的几种实时调度算法1 1最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法1) 非抢占式调度方式用于非周期实时任务图3-9示出了将该算法用于非抢占调度方式之例。该例中具有四个非周期任务，它们先后到达。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于

14、任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。 第三章处理机调度与死锁 图 3-9EDF算法用于非抢占调度的调度方式1342开始截止时间任务执行任务到达12 341342t到达到达到达到达到达到达第三章处理机调度与死锁 2) 抢占式调度方式用于周期实时任务图3-10示出了将最早截止时间优先算法用于抢占调度方式之例。在该例中有两个周期性任务，任务A的周期时间为20 ms，每个周期的处理时间为10 ms；任务B的周期时间为50 ms，每个周期的处理时间为25 ms。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。其中任务A的到达时间为0、20、40、；任务A

15、的最后期限为20、40、60、；任务B的到达时间为0、50、100、；任务B的最后期限为50、100、150、(注：单位皆为ms)。 第三章处理机调度与死锁 图3-10 最早截止时间优先算法用于抢占调度方式之例最早截止时间优先算法用于抢占调度方式之例 A1 B1A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1A2B1A3 B2 A4B2A5 B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到达时间、执行时间和最后期限A1固定优先级调度固定优先级调度A2B1A3A4A5，B2A5，B2A4A1(错过)A2B1A3(错

16、过)A1A2B1(错过)A3A4A5，B201020304050 60708090100 时间t/ms使用完成最后期限最早和最后期限调度(A有较高优先级)(B有较高优先级)最早截至时间优先调度最早截至时间优先调度最后期限最后期限A到达就执行到达就执行B到达就执行到达就执行第三章处理机调度与死锁 第四行是采用最早截止时间优先算法的时间图。在t = 0时，A1和B1同时到达，由于A1的截止时间比B1早，故调度A1执行；在t = 10时，A1完成，又调度B1执行；在t = 20时，由于A2的截止时间比B2早，B1被中断而调度A2执行；在t = 30时，A2完成，又重新调度B1执行；在t = 40时，

17、A3又到达，但B1的截止时间要比A3早，仍应让B1继续执行直到完成(t = 45)，然后再调度A3执行；在t = 55时，A3完成，又调度B2执行。在该例中利用最早截止时间优先算法可以满足系统的要求。 第三章处理机调度与死锁 2 2最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。例如，一个任务在200 ms时必须完成，而它本身所需的运行时间就有100 ms，因此，调度程序必须在100 ms

18、之前调度执行，该任务的紧急程度(松弛程度)为100 ms。又如，另一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。 第三章处理机调度与死锁 该算法主要用于可抢占调度方式中。假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。由此可得知任务A和B每次必须完成的时间分别为：A1、A2、A3、和B1、B2、B3

19、、，见图3-11。为保证不遗漏任何一次截止时间，应采用最低松弛度优先的抢占调度策略。 第三章处理机调度与死锁 图 3-11A和B任务每次必须完成的时间 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0第三章处理机调度与死锁 在刚开始时(t1=0)，A1必须在20 ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10 ms；B1必须在50 ms时完成，而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出： 第三章处理机调度与死锁 类似地，可算出B1的松弛度为15

20、 ms，故调度程序应选择B2运行。在t3=30 ms时，A2的松弛度已减为0(即40-10-30)，而B1的松弛度为15 ms(即50-5-30)，于是调度程序应抢占B1的处理机而调度A2运行。在t4=40 ms时，A3的松弛度为10 ms(即60-10-40)，而B1的松弛度仅为5 ms(即50-5-40)，故又应重新调度B1执行。在t5=45 ms时，B1执行完成，而此时A3的松弛度已减为5 ms(即60-10-45)，而B2的松弛度为30 ms(即100-25-45)，于是又应调度A3执行。在t6=55 ms时，任务A尚未进入第4周期，而任务B已进入第2周期，故再调度B2执行。在t7=7

21、0 ms时，A4的松弛度已减至0 ms(即80-10-70)，而B2的松弛度为20 ms(即100-10-70)，故此时调度又应抢占B2的处理机而调度A4执行。图3-12示出了具有两个周期性实时任务的调度情况。 第三章处理机调度与死锁 图 3-12利用LLF算法进行调度的情况 t1A1(10)10203040506080t0t10B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)第三章处理机调度与死锁 小结第三章处理机调度与死锁 第三章处理机调度与死锁 Deadlock possible 3.5产生死锁的原因和必要条件产生死锁的原

22、因和必要条件 第三章处理机调度与死锁 Deadlock第三章处理机调度与死锁 第三章处理机调度与死锁 死锁死锁：第三章处理机调度与死锁 n 最易理解的死锁：线程最易理解的死锁：线程A、B死锁！死锁！n 两兄弟相依为命，靠打猎为生，家里面有两把枪，金两兄弟相依为命，靠打猎为生，家里面有两把枪，金枪和银枪。一般的时候他们每人拿一把枪就好了，但是枪和银枪。一般的时候他们每人拿一把枪就好了，但是有特殊问题发生了！某天，由于猎物太强悍，他们只有有特殊问题发生了！某天，由于猎物太强悍，他们只有一人手上两把枪才搞得定！现在老大拿到了金枪，老二一人手上两把枪才搞得定！现在老大拿到了金枪，老二拿到了银枪，老大还

23、要拿到银枪才出发，老二一样，要拿到了银枪，老大还要拿到银枪才出发，老二一样，要拿到金枪才出发（至于这两兄问什么这样？我们假设就拿到金枪才出发（至于这两兄问什么这样？我们假设就是这样了。）这时候，很显然两兄弟都出发不了。老大是这样了。）这时候，很显然两兄弟都出发不了。老大始终拿不到银枪，老二页始终拿不到金枪，因为他们都始终拿不到银枪，老二页始终拿不到金枪，因为他们都想得到两把枪，所以不想放出手上的那把枪！现在这个想得到两把枪，所以不想放出手上的那把枪！现在这个猎就打不成了，两兄弟死锁了。（这是获取资源的死猎就打不成了，两兄弟死锁了。（这是获取资源的死锁。）锁。）女朋友生气了，心想：男朋友要是给我

24、打了电话，我就女朋友生气了，心想：男朋友要是给我打了电话，我就给他回一个。男朋友也是这样想的，女朋友给我打了我给他回一个。男朋友也是这样想的，女朋友给我打了我才给他打！女朋友越来越生气，她一直没等到电话，因才给他打！女朋友越来越生气，她一直没等到电话，因为男朋友一直没打给她，为什么不打！因为男朋友没有为男朋友一直没打给她，为什么不打！因为男朋友没有接到女朋友的电话！为什么女朋友不打？他一直没有接接到女朋友的电话！为什么女朋友不打？他一直没有接到男朋友的电话啊，两人死锁到男朋友的电话啊，两人死锁了。了。（这是事件通知的死锁）（这是事件通知的死锁） 第三章处理机调度与死锁 第三章处理机调度与死锁

25、图图3-13I/O设备共享时的死锁情况设备共享时的死锁情况 r1 r2P1P2第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 图3-14进程之间通信时的死锁 S2P1S3P3S1P2第三章处理机调度与死锁 1) 进程推进顺序合法进程推进顺序合法在进程P1和P2并发执行时，如果按下述两种顺序推进： A1: P1 request (r1) A2: P2 request (r2) B1: P1 request (r2) B2: P2 request (r1) C1: P1 release (r1) C2: P2 release (r2) D1: P1 release (r2)

26、 D2: P2 release (r1)则两个进程可顺利完成，若A1、A2或者A2、A1则可能发生死锁马儿光吃草,不快跑第三章处理机调度与死锁 危险区危险区N A1 B1 C1 D1 P1进展进展 P2进进展展D2C2B2A2 A1: P1 request (r1) A2: P2 request (r2) B1: P1 request (r2) B2: P2 request (r1) C1: P1 release (r1) C2: P2 release (r2) D1: P1 release (r2) D2: P2 release (r1)第三章处理机调度与死锁 第三章处理机调度与死锁 。第三

27、章处理机调度与死锁 不考虑此问题：不考虑此问题：（鸵鸟政策）（鸵鸟政策）让死锁发生：让死锁发生：允许死锁发生，但能检测出死锁允许死锁发生，但能检测出死锁并实现修复。并实现修复。不让死锁发生：不让死锁发生：为了不发生死锁，必须设法破为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一坏产生死锁的四个必要条件之一第三章处理机调度与死锁 (1) 预防死锁预防死锁。这是一种较简单和直观的事先预防的方法。该方法是通过设置某些，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但由于所施加的限制条件往往，因而可能会导致系统资源利用率和系统吞吐量降

28、低。 第三章处理机调度与死锁 第三章处理机调度与死锁 。 第三章处理机调度与死锁 3.6预防、避免死锁的方法预防、避免死锁的方法 1 1破坏破坏“互斥互斥”条件，很难，条件，很难，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备。2 2摒弃摒弃“请求和保持请求和保持”条件条件规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。可以第三章处理机调度与死锁 优点优点：简单：简单、易于实现且很安全易于实现且很安全。缺点缺点(1)(1)资源被严重浪费资源被严重浪费，因为一个进程是一次性地获得其整个运行过程所需的全部资源的，且独占资源，其中可能有些资源

29、很少使用，甚至在整个运行期间都未使用，这就严重地恶化了系统资源的利用率；，仅当进程在获得了其所需的全部资源后，才能开始运行，但可能因有些资源已长期被其它进程占用而致使等待该资源的进程迟迟不能运行。 第三章处理机调度与死锁 3 3摒弃摒弃“不剥夺不剥夺”条件条件在采用这种方法时系统规定，。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，也可认为是被剥夺了，从而摒弃了“不剥夺”条件。 这种预防死锁的方法实现起来第三章处理机调度与死锁 4 4摒弃摒弃“环路等待

30、环路等待”条件条件。 例如，令输入机的序号为1，打印机的序号为2，磁带机为3，磁盘为4。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待”条件。事实上，在采用这种策略时，总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。 第三章处理机调度与死锁 这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的。但也存在下述严重问题：。为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，第三章处理机调度与死锁 .2系统安

31、全状态系统安全状态（1 1安全状态安全状态在的方法中，允许进程地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。 第三章处理机调度与死锁 第三章处理机调度与死锁 进 程 最大需求 已 分 配 可 用 P1 10 5 3 P2 4 2 P3 9 2 第三章处理机调度与死锁 存在安全状态，不代表不可能发生死锁，存在安全状态，不代表不可能发生死锁，表示的是有解决死锁的方法存在。表示的是有解决死锁的方法存在。第三章处理机调度与死锁 3.6.3利用银行家算法避免死锁利用银行家算法避免死锁n银行家算法：银行家算法

32、：Dijkstra E.W Dijkstra E.W 于于19681968年提出。年提出。银行家算法银行家算法银行家拥有一笔周转资金银行家拥有一笔周转资金客户要求分期贷款，如果客户能够得到各期贷客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归款，就一定能够归还贷款，否则就一定不能归还贷款还贷款银行家应谨慎的贷款，防止出现坏帐银行家应谨慎的贷款，防止出现坏帐n 用银行家算法避免死锁用银行家算法避免死锁操作系统（银行家）操作系统（银行家）操作系统管理的资源操作系统管理的资源( (周转资金周转资金) )进程（要求贷款的客户）进程（要求贷款的客户）第三章处理机调度与死锁

33、 n 银行家银行家算法思想：算法思想： 该算法需要检查申请者对资源的最大需求量，该算法需要检查申请者对资源的最大需求量，如果系统如果系统现存的各类资源现存的各类资源可以满足申请者的请可以满足申请者的请求，就满足申请者的请求。求，就满足申请者的请求。这样申请者就可很这样申请者就可很快完成其计算，然后释放它占用的资源，从而快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避保证了系统中的所有进程都能完成，所以可避免死锁的发生。免死锁的发生。第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 银行家算法避免死锁银行家算法避免死锁算法：开始申请量=尚需

34、量ynny申请量=系统剩余安全性控制 分配进入下一步骤预分配作废阻塞安全首先为申请预分配资源错误预测ny第三章处理机调度与死锁 例. 多项资源的安全序列（a）初始状态）初始状态Max Matrix第三章处理机调度与死锁 Max Matrix（a）P2运行完成运行完成第三章处理机调度与死锁 Max MatrixMax Matrix第三章处理机调度与死锁 例. 进入不安全状态（a）初始状态）初始状态Max Matrix第三章处理机调度与死锁 例. 进入不安全状态Max Matrix（b）P1申请申请1个个R1、1个个R3第三章处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 第三章

35、处理机调度与死锁 第三章处理机调度与死锁 第三章处理机调度与死锁 图3-16 T0时刻的资源分配表 第三章处理机调度与死锁 (1) T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(见图 3-17所示)可知，在T0时刻存在着一个安全序列P1，P3，P4，P2，P0，故系统是安全的。 图3-17T0时刻的安全序列 P1P1，P3P3，P4P4，P2P2，P0P0是安全序列吗？是安全序列吗？第三章处理机调度与死锁 (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1，0，2)Need1(1，2，2) Request1

36、(1，0，2)Available1(3，3，2) 系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，由此形成的资源变化情况如图3-16中的圆括号所示。 第三章处理机调度与死锁 再利用安全性算法检查此时系统是否安全。如图3-18所示。 图3-18P1申请资源时的安全性检查 第三章处理机调度与死锁 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3，3，0)Need4(4，3，1)； Request4(3，3，0)Available(2，3，0)，让P4等待。(4) P0请求资源：P0发

37、出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0，2，0)Need0(7，4，3)； Request0(0，2，0)Available(2，3，0)； 系统暂时先假定可为P0分配资源，并修改有关数据，如图3-19所示。 第三章处理机调度与死锁 图3-19为P0分配资源后的有关资源数据 第三章处理机调度与死锁 (5) (5) 进行安全性检查：可用资源进行安全性检查：可用资源Available(2Available(2，1 1，0)0)已已不能满足任何进程的需要，故系统进入不安全状态，此时系不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。统

38、不分配资源。如果在银行家算法中，把如果在银行家算法中，把P0发出的请求向量改为发出的请求向量改为Request0(0，1，0)，系统是否能将资源分配给它？，系统是否能将资源分配给它？第三章处理机调度与死锁 已分配的资源最大需求量 ABCABCP1010753P2200322P3302902P4211222P5002433剩余资源ABC 33 2在此基础上P2 申请（1，0，2）能否分配？为什么？P5 申请（3，3，0）能否分配？为什么？P1 申请（0，2，0）能否分配？为什么？第三章处理机调度与死锁 银行家算法优缺点银行家算法优缺点即考虑最坏情况每个进即考虑最坏情况每个进程可能请求最大需求量（

39、类似银行提款）并在程可能请求最大需求量（类似银行提款）并在运行期中随时提出来运行期中随时提出来 第三章处理机调度与死锁 3.7死锁的检测与解除死锁的检测与解除 .1死锁的检测死锁的检测当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须做到：(1) 保存有关资源的请求和分配信息；(2) 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。 第三章处理机调度与死锁 1资源分配图资源分配图(Resource Allocation Graph)系统死锁可利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一个对偶G=(N1E)

40、，它具有下述形式的定义和限制：(1) 把N分为两个互斥的子集，即一组进程结点P=p1，p2，pn和一组资源结点R=r1，r2，rn，N=PR。在图3-20所示的例子中，P=p1，p2，R=r1，r2，N=r1，r2p1，p2。 第三章处理机调度与死锁 (2) 凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi，rj是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e=rj，pi是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配给进程pi。图3-13中示出了两个请求边和两个分配边，即E=(p1，r2)，(r2，p2)，(p2，r1

41、)，(r1，p1)。我们用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的rj，而分配边则应始于方框中的一个点。图3-20示出了一个资源分配图。图中，p1进程已经分得了两个r1资源，并又请求一个r2资源；p2进程分得了一个r1和一个r2资源，并又请求r1资源。 第三章处理机调度与死锁 图3-20每类资源有多个时的情况 P1P2r1r2第三章处理机调度与死锁 第三章处理机调度与死锁 图3-21资源分配图的简化 (a)(b)P1(c)P1P2P1P2P2第三章处理机调度与死锁 第三章处理机调度与死锁

42、第三章处理机调度与死锁 (4) 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。Work:=Available；L:=Li |Allocation i=0Request i=0for all Li L dobeginfor all Request iWork dobeginWork:=Work + Allocation i；LiL；endenddeadlock:=(L=p1，p2，pn)； 第三章处理机调度与死锁 .2死锁的解除死锁的解除常采用解除死锁的两种方法是：(1) 。从其它进程剥夺足够数量的资源给死锁进程，以解除

43、死锁状态。(2) 撤消进程撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。第三章处理机调度与死锁 本章重点n三级调度；n单CPU的调度算法；n实时调度；n死锁 1. 定义 举例 2. 引起死锁的原因 3. 产生死锁的必要条件 4. 死锁预防n银行家算法；第三章处理机调度与死锁 练习：练习：P P个进程共享个进程共享m m个同类资源，每一个资源在任一时个同类资源，每一个资源在任一时刻只能供一个进程使用，每一进程对任一资源都只能刻只能供一个进程使用，每一进程对任一资源都只能使用一有限时间，使用完便立

44、即释放。并且每个进程使用一有限时间，使用完便立即释放。并且每个进程对该类资源的最大需求量小于该类资源的数目。设所对该类资源的最大需求量小于该类资源的数目。设所有进程对资源的最大需求数目之和小于有进程对资源的最大需求数目之和小于p+mp+m。试证：该。试证：该系统中不会发生死锁。系统中不会发生死锁。解：设进程解：设进程i i所需资源数为所需资源数为riri，根据题意：，根据题意： r1+ r2+ rpp+m r1+ r2+ rpp+m 即即 (r1-1)+ ( r2 -1) + ( rp -1) m(r1-1)+ ( r2 -1) + ( rp -1) m 因此，在最坏的情况下也至少有一个进程能

45、得因此，在最坏的情况下也至少有一个进程能得到它所需的所有资源，从而可以运行完毕，之后就到它所需的所有资源，从而可以运行完毕，之后就可以释放它所占有的资源，近而使所有进程运行完可以释放它所占有的资源，近而使所有进程运行完毕。毕。第三章处理机调度与死锁 AB运河运河弯道弯道河道河道公路公路100m7/sfzx/xxxy/other/kj_623/3/02/cpu/PCP_JC_8.SWF第三章处理机调度与死锁 Main() Pship( ) Pcar( )Main() Pship( ) Pcar( ) int Sa=Sb=1; p(Sa); p(Sn); in

46、t Sa=Sb=1; p(Sa); p(Sn); int Sn=n; int Sn=n; 船头过船头过A A桥；桥； p(Sb);p(Sb);cobegin p(Sb); cobegin p(Sb); 过过B B桥；桥；Pship( ); Pship( ); 船头过船头过B B桥；桥； v(Sb);v(Sb);Pcar( ); Pcar( ); 船尾过船尾过A A桥；桥； 过弯道；过弯道；coend v(Sa); p(Sa);coend v(Sa); p(Sa); 船尾过船尾过B B桥；桥； v(Sn);v(Sn); v(Sb); v(Sb); 过过A A桥；桥； v(Sa); v(Sa);

47、第三章处理机调度与死锁 本章作业nP1158、18、22实验：第三章处理机调度与死锁 死锁部分例题死锁部分例题(1) (1) 在某一时刻，系统中既无执行态进程又无就绪态在某一时刻，系统中既无执行态进程又无就绪态进程，是否可能？若可能，在什么情况下会发生？进程，是否可能？若可能，在什么情况下会发生？ 解答解答: : 可能。在系统死锁状态下，进程处于占有等可能。在系统死锁状态下，进程处于占有等待资源的状态，应当既不属于执行态也不属于就待资源的状态，应当既不属于执行态也不属于就绪态。绪态。 第三章处理机调度与死锁 死锁部分例题死锁部分例题(2) (2) 一台计算机有八台磁带机。它们由一台计算机有八台

48、磁带机。它们由N N个进程竞争个进程竞争使用，每个进程可能需要使用，每个进程可能需要3 3台磁带机。请问台磁带机。请问N N为多为多少时，系统没有死锁危险，并说明其原因。少时，系统没有死锁危险，并说明其原因。 第三章处理机调度与死锁 死锁部分例题死锁部分例题(2) (2) 一台计算机有八台磁带机。它们由一台计算机有八台磁带机。它们由N N个进程竞争个进程竞争使用，每个进程可能需要使用，每个进程可能需要3 3台磁带机。请问台磁带机。请问N N为多为多少时，系统没有死锁危险，并说明其原因。少时，系统没有死锁危险，并说明其原因。 解答解答: :判断原则一：资源总数是否足够判断原则一：资源总数是否足够

49、判断原则二：资源是否可以顺利被释放判断原则二：资源是否可以顺利被释放当当N N2 2的时候的时候 永远不会发生死锁永远不会发生死锁 第三章处理机调度与死锁 当当N N3 3，3 3个进程竞争个进程竞争8 8台设备台设备, ,也不会死锁也不会死锁当当N=4 P1 P2 P3 P4 8N=4 P1 P2 P3 P4 8台台 Max 3 3 3 3Max 3 3 3 3 Allocation 1 1 1 1 Allocation 1 1 1 1 剩剩4 4台台 存在安全序列存在安全序列,按照安全序列按照安全序列推进时不会死锁推进时不会死锁, ,否则存在死锁危险否则存在死锁危险. .当当N=5 P1 P2 P3 P4 P5 8N=5 P1 P2 P3 P4 P5 8台台 Max 3 3 3 3 3Max 3 3 3 3 3 Allocation 1 1 1 1 1 Allocation 1 1 1 1 1 剩剩3 3台台第三章处理机调度与死锁 存在安全序列存在安全序列,按照安按照安全序列推进时不