处理机调度与死锁习题课

1、处理机调度与死锁习题课处理机调度与死锁习题课难点：调度算法的性能评估难点：调度算法的性能评估银行家算法避免死锁银行家算法避免死锁本章内容回顾本章内容回顾n处理机调度的层次（处理机调度的层次（3级）级）n周转时间和带权周转时间的计算周转时间和带权周转时间的计算n调度算法及其各自优缺点调度算法及其各自优缺点n调度算法性能评估（公平性，系统吞吐量，调度算法性能评估（公平性，系统吞吐量，响应时间，资源利用率）响应时间，资源利用率）(可靠性，简洁性可靠性，简洁性)n死锁产生的原因（死锁产生的原因（2个）和必要条件（个）和必要条件（4个）个）内容回顾内容回顾n处理死锁的基本方法处理死锁的基本方法n预防死锁

2、的方法预防死锁的方法n如何用银行家算法避免死锁如何用银行家算法避免死锁n如何求某时刻系统的安全性如何求某时刻系统的安全性n如何检测死锁（死锁定理）如何检测死锁（死锁定理）n如何解除死锁如何解除死锁第一题第一题一、既考虑作业等待时间，又考虑作业执一、既考虑作业等待时间，又考虑作业执行时间的调度算法是行时间的调度算法是 。 A. 响应比高者优先响应比高者优先 B短作业优先短作业优先 C优先级调度优先级调度 D先来先服务先来先服务 答案答案:A第二题第二题二、二、 是指从作业提交给系统是指从作业提交给系统到作业完成的时间间隔。到作业完成的时间间隔。 A周转时间周转时间 B响应时间响应时间 C. 等待

3、时间等待时间 D运行时间运行时间 答案答案:A第四题第四题四、假设下述四个作业同时到达，当使用最高优四、假设下述四个作业同时到达，当使用最高优先数优先调度算法时，作业的平均周转时间为先数优先调度算法时，作业的平均周转时间为小时。小时。 作业作业 所需运行时间所需运行时间 优先数优先数 1 2 4 2 5 9 3 8 1 4 3 8 A4.5 B10.5 C4.75 D10.25 答案答案:D第五题第五题五、系统在，发生从目态到管态五、系统在，发生从目态到管态的转换。的转换。 A. 发出发出P操作时操作时 B .发出发出V操作时操作时 C .执行系统调用时执行系统调用时 D. 执行置程序状态字时

4、执行置程序状态字时 答案答案:C第七题第七题七、设有一组作业，它们的提交时间及运行时间七、设有一组作业，它们的提交时间及运行时间如下：如下： 作业号作业号 提交时间提交时间 运行时间运行时间(分钟分钟) 1 9:00 70 2 9:40 30 3 9:50 10 4 10:10 5 在单道方式下，采用短作业优先调度算法，作在单道方式下，采用短作业优先调度算法，作业的执行顺序是。业的执行顺序是。 答：答：1 1、4 4、3 3、2 2 第八题第八题八、设有八、设有4道作业，它们的提交时间及执行时间如下：道作业，它们的提交时间及执行时间如下： 作业号作业号 提交时间提交时间 执行时间执行时间 1

5、10.0 2.0 2 10.2 1.0 3 10.4 0.5 4 10.5 0.3 试计算在单道程序环境下，采用先来先服务调度算法试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。带权周转时间，并指出它们的调度顺序。（时间单时间单位：小时，以十进制进行计算。位：小时，以十进制进行计算。）答案答案第九题第九题九、下表给出作业九、下表给出作业1、2、3的到达时间和运行时的到达时间和运行时间。采用短作业优先调度算法和先来先服务调间。采用短作业优先调度算法和先来先服务调度算法，试问平

6、均周转时间各为多少度算法，试问平均周转时间各为多少?是否还是否还有更好的调度策略存在有更好的调度策略存在?（时间单位：小时，时间单位：小时，以十进制进行计算。以十进制进行计算。） 作业号作业号 到达时间到达时间 运行时间运行时间 1 0.0 8.0 2 0.4 4.0 3 1.0 1.0 答案答案第十题第十题十、假设有四个作业，它们的提交、运行时间如下十、假设有四个作业，它们的提交、运行时间如下表所示。若采用响应比高者优先调度算法，试问表所示。若采用响应比高者优先调度算法，试问平均周转时间和平均带权周转时间为多少平均周转时间和平均带权周转时间为多少? （时时间单位：小时，以十进制进行计算。间单

7、位：小时，以十进制进行计算。） 作业号作业号 到达时间到达时间 运行时间运行时间 1 8.0 2.0 2 8.3 0.5 3 8.5 0.1 4 9.0 0.4 答案答案十一题十一题十一、设有一组作业，它们的提交时间及运行时十一、设有一组作业，它们的提交时间及运行时间如下所示。间如下所示。作业号作业号 到达时间到达时间 运行时间运行时间(分钟分钟) 1 8:00 70 2 8:40 30 3 8:50 10 4 9:10 5 试问在单道方式下，采用响应比高者优先调度试问在单道方式下，采用响应比高者优先调度算法，作业的执行顺序是什么算法，作业的执行顺序是什么? 答案答案十二题：死锁十二题：死锁-

8、选择题选择题某系统中有三个并发进程，都需要同类资某系统中有三个并发进程，都需要同类资源源4个，试问该系统不会发生死锁的最少个，试问该系统不会发生死锁的最少资源数是资源数是_A.9 B.10 C.11 D.12答案：答案：B十三题：银行家算法十三题：银行家算法设系统中有设系统中有3种类型的资源（种类型的资源（A，B，C）和）和5个进程，资源的个进程，资源的数量为（数量为（17，5，20）。在）。在T0时刻系统状态见表。系统采用银时刻系统状态见表。系统采用银行家算法实施死锁避免策略。行家算法实施死锁避免策略。 T0时刻是否为安全状态？若是，请给出安全序列。时刻是否为安全状态？若是，请给出安全序列。

9、 在在T0时刻若进程时刻若进程P2请求资源（请求资源（0，3，4），是否能实施），是否能实施资源分配？为什么？资源分配？为什么？ 在在的基础上，若进程的基础上，若进程P4请求资源（请求资源（2，0，1），是否能），是否能实施资源分配？为什么？实施资源分配？为什么？ 在在的基础上，若进程的基础上，若进程P1请求资源（请求资源（0，2，0），是否能），是否能实施资源分配？为什么？实施资源分配？为什么？ T T0 0时刻系统状态时刻系统状态最大资源需求量最大资源需求量已分配资源数量已分配资源数量A B CA B CP1P2P3P4P55 5 95 3 64 0 114 2 54 2 42 1 24

10、0 24 0 52 0 43 1 4剩余资源数剩余资源数 A B C答案答案MaxAllocationNeedAvailableA B CA B CA B CA B CP15 5 92 1 23 4 72 3 3P25 3 64 0 21 3 4P34 0 114 0 50 0 6P44 2 52 0 42 2 1P54 2 43 1 41 1 0安全序列安全序列MaxAllocationNeedWorkA B CA B CA B CA B CP44 2 52 0 42 2 12 3 3P25 3 64 0 21 3 44 3 7P34 0 114 0 50 0 68 3 9P54 2 43

11、1 41 1 012 3 14P15 5 92 1 23 4 715 4 18FinishFalseFalseFalseFalseFalse1.考虑一组进程：考虑一组进程：进程进程 执行时间执行时间 优先数优先数P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2其中，其中，小的优先数表示高的优先级小的优先数表示高的优先级。设这组进程在相对时刻。设这组进程在相对时刻0以以P1、P2、P3、P4、P5的次序进入就绪队列，进入时的次序进入就绪队列，进入时消耗的时间忽略不计。消耗的时间忽略不计。（1） 分别给出分别给出FCFS，HRN，RR（时间片（时间片S = 1）算法下，）算法下，这组

12、进程的执行顺序图示。这组进程的执行顺序图示。（2） 每个进程在上述何种算法下它的等待时间和周转时间每个进程在上述何种算法下它的等待时间和周转时间最短？最短？（3） 计算在每种算法下的平均等待时间和平均周转时间。计算在每种算法下的平均等待时间和平均周转时间。作业作业1：作业作业2：2.考考 虑虑 下下 面面 的的 系系 统统 “ 瞬瞬 态态 ” ： 五五 个个 进进 程程 P1,P2, P3, P4, P5 ， 四四 类类 资资 源源 A,B,C, D Allocation Max Available P1 0 0 1 2 0 0 1 2 0 0 1 2 P2 1 0 0 0 1 7 5 0 P

13、3 1 3 5 4 2 3 5 6 P4 0 6 3 2 0 6 5 2 P5 0 0 1 4 0 6 5 6使使 用用 银银 行行 家家 算算 法法 回回 答答 以以 下下 问问 题题 ：1) 给给 出出 Need 的的 内内 容容 2) 系系 统统 是是 安安 全全 状状 态态 吗吗 ？ (请请 写写 出出 过过 程程 )3) 如如 果果 进进 程程 P2要要 求求 0， 4， 2， 0， 此此 要要 求求 能能 满满 足足 吗？吗？ (请请 写写 出出 过过 程程 ) 第八题答案第八题答案解：若采用先来先服务调度算法，则其调度顺序为解：若采用先来先服务调度算法，则其调度顺序为1 1、2

14、2、3 3、4 4。 作业作业 提交提交 执行执行 开始开始 完成完成 周转周转 带权周转带权周转 1 10.0 2.0 10.0 12.0 2.0 1.0 1 10.0 2.0 10.0 12.0 2.0 1.0 2 10.2 1.0 12.0 13.0 2.8 2.8 2 10.2 1.0 12.0 13.0 2.8 2.8 3 10.4 0.5 13.0 13.5 3.1 6.2 3 10.4 0.5 13.0 13.5 3.1 6.2 4 10.5 0.3 13.5 13.8 3.3 4 10.5 0.3 13.5 13.8 3.3 11.0 11.0 平均周转时间平均周转时间 T=(

15、2.0+2.8+3.1+3.3)T=(2.0+2.8+3.1+3.3)4=2.8 4=2.8 平均带权周转时间平均带权周转时间 W=(1+2.8+6.2+11)4=5.25 解：若采用先来先服务调度算法，则其调度顺序为解：若采用先来先服务调度算法，则其调度顺序为1 1、4 4、3 3、2 2。 作业作业 提交提交 执行执行 开始开始 完成完成 周转周转 带权周转带权周转 1 10.0 2.0 10.0 12.0 2.0 1 10.0 2.0 10.0 12.0 2.0 1.0 1.0 4 10.5 0.3 12.0 12.3 1.8 4 10.5 0.3 12.0 12.3 1.8 6.0 6

16、.0 3 10.4 0.5 12.3 12.8 2.4 3 10.4 0.5 12.3 12.8 2.4 4.8 4.8 2 10.2 1.0 12.8 13.8 3.6 2 10.2 1.0 12.8 13.8 3.6 3.6 3.6 平均周转时间平均周转时间 T=(2.0+1.8+2.4+3.6)T=(2.0+1.8+2.4+3.6)4=2.45 4=2.45 平均带权周转时间平均带权周转时间 W=(1+6+4.8+3.6)W=(1+6+4.8+3.6)4=3.85 4=3.85 返回返回第九题答案第九题答案解：采用先来先服务调度策略，则调度顺序为解：采用先来先服务调度策略，则调度顺序为1

17、 1、2 2、3 3。 作业作业 到达到达 运行运行 开始开始 完成完成 周转时间周转时间 1 0.0 1 0.0 8.0 0.0 8.0 8.0 8.0 0.0 8.0 8.0 2 0.4 2 0.4 4.0 8.0 12.0 11.6 4.0 8.0 12.0 11.6 3 1.0 3 1.0 1.0 12.0 13.0 12.0 1.0 12.0 13.0 12.0 平均周转时间平均周转时间T=(8+11.6+12)3=10.53 采用短作业优先调度策略，则调度顺序为采用短作业优先调度策略，则调度顺序为1 1、3 3、2 2。 作业作业 到达时间到达时间 运行时间运行时间 开始时间开始时

18、间 完成时间完成时间 周转时间周转时间 1 0.0 1 0.0 8.0 0.0 8.0 8.0 0.0 8.0 8.0 8.0 3 1.0 3 1.0 1.0 8.0 9.0 1.0 8.0 9.0 8.0 8.0 2 0.4 2 0.4 4.0 9.0 13.0 4.0 9.0 13.0 12.6 12.6 平均周转时间平均周转时间T=(8+8+12.6)3=9.53 存在缩短平均周转时间的策略，如知道后面将来两个短作业，因存在缩短平均周转时间的策略，如知道后面将来两个短作业，因此在作业此在作业1 1到达后暂不投入运行，等所有作业到齐后再按短作业到达后暂不投入运行，等所有作业到齐后再按短作业

19、优先调度算法调度，其调度顺序为优先调度算法调度，其调度顺序为3 3、2 2、1 1。 作业作业 到达时间到达时间 运行时间运行时间 开始时间开始时间 完成时间完成时间 周转时间周转时间 3 1.0 3 1.0 1.0 1.0 1.0 2.0 1.0 2.0 1.0 1.0 2 0.4 2 0.4 4.0 4.0 2.0 6.0 2.0 6.0 5.6 5.6 1 0.0 1 0.0 8.0 8.0 6.0 14.0 6.0 14.0 14.0 14.0 平均周转时间平均周转时间T=(1+5.6+14)3=6.87 返回返回第十题分析第十题分析所谓响应比高者优先调度算法，就是在每次调度作所谓响应

20、比高者优先调度算法，就是在每次调度作业运行时，先计算后备作业队列中每个作业的响业运行时，先计算后备作业队列中每个作业的响应比，然后选响应比最高者投入运行。应比，然后选响应比最高者投入运行。 响应比定义如下：响应比定义如下： 响应比响应比= =作业响应时间运行时间的估计值作业响应时间运行时间的估计值 其中响应时间为作业进入系统后的等待时间加上估其中响应时间为作业进入系统后的等待时间加上估计的运行时间。于是计的运行时间。于是 响应比响应比=1+作业等待时间运行时间的估计值作业等待时间运行时间的估计值 第十题答案第十题答案在在8 8：0000时，因为只有作业时，因为只有作业1 1到达，系统将作业到达

21、，系统将作业1 1投入运行。作投入运行。作业业1 1运行运行2 2小时小时( (即即 1010：0000时时) )完成。由于该算法采用响应比高者优先调度算完成。由于该算法采用响应比高者优先调度算法，这样在作业法，这样在作业1 1执行执行 完后，要计算剩下三个作业的响应比，然后选响应比高者完后，要计算剩下三个作业的响应比，然后选响应比高者去运行。剩下三个作业去运行。剩下三个作业 的响应比为：的响应比为： r2=l+(10.0-8.3)r2=l+(10.0-8.3)0.5=4.4 0.5=4.4 r3=l+(10.0-8.5) r3=l+(10.0-8.5)0.1=16 0.1=16 r4=l+(

22、10.0-9.0) r4=l+(10.0-9.0)0.4=3.5 0.4=3.5 从计算结果看，作业从计算结果看，作业3的响应比高，所以让作业的响应比高，所以让作业3先运行。先运行。 作业作业3 3运行运行0.10.1小时完成小时完成( (即即1010：1010时时) )，此时，作，此时，作业业2 2和作业和作业4 4的响应比为：的响应比为： r2=l+(10.1-8.3)r2=l+(10.1-8.3)0.5=4.6 0.5=4.6 r4=l+(10.1-9.0) r4=l+(10.1-9.0)0.4=3.75 0.4=3.75 从上述计算结果看，作业从上述计算结果看，作业2 2的响应比高，所

23、以的响应比高，所以让作业让作业2 2先运行。因此四个作业的先运行。因此四个作业的 执行次序为：执行次序为：作业作业1 1、作业、作业3 3、作业、作业2 2、作业、作业4. 4. 解：四个作业的调度次序为：作业解：四个作业的调度次序为：作业1 1、作业、作业3 3、作业、作业2 2、作业、作业4 4。 作业作业 到达到达 运行运行 开始开始 完成完成 周转周转 带权周转带权周转 1 8.0 2.0 8.0 1 8.0 2.0 8.0 10.0 2.0 10.0 2.0 1.0 1.0 2 8.3 0.5 10.1 2 8.3 0.5 10.1 10.6 2.3 10.6 2.3 4.6 4.6

24、 3 8.5 0.1 10.0 3 8.5 0.1 10.0 10.1 1.6 10.1 1.6 16.0 16.0 4 9.0 0.4 10.6 4 9.0 0.4 10.6 11.0 2.0 11.0 2.0 5.0 5.0 平均周转时间平均周转时间 T=(2.0+2.3+1.6+2.0)T=(2.0+2.3+1.6+2.0)4=1.975 4=1.975 平均带权周转时间平均带权周转时间 W=(1+4.6+16+5)W=(1+4.6+16+5)4=6.65 4=6.65 返回返回第十一题答案第十一题答案8:008:00时，因为这时只有作业时，因为这时只有作业1 1到达，因此调度作业到达，

25、因此调度作业1 1运行。运行。7070分钟后分钟后( (即即9:10)9:10)，作业，作业1 1运行完毕。运行完毕。 9:109:10时，这时作业时，这时作业1 1运行完成，其他三个作业均已到运行完成，其他三个作业均已到达。它们的响应比分别为：达。它们的响应比分别为： r2=1+(9:10r2=1+(9:108:40)8:40)30=2 30=2 r3=1+(9:10 r3=1+(9:108:50)8:50)10=3 10=3 r4=1+(9:10 r4=1+(9:109:10)9:10)5=1 5=1 从计算结果看，作业从计算结果看，作业3 3的响应比高，所以让作业的响应比高，所以让作业3 3先运行。先运行。1010分钟后分钟后( (即即9:20)9:20)，作业，作业3运行完毕运行完毕 9:209:20时，这时作业时，这时作业3 3运行完成，其他两个作业的运行完成，其他两个作业的响应比分别为：响应比分别为： r2=1+(9:20r2=1+(9:208:40)8:40)30=2.3 30=2.3 r4=1+(9:20