处理机调度与死锁习题.ppt

《处理机调度与死锁习题.ppt》由会员分享，可在线阅读，更多相关《处理机调度与死锁习题.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、B响应时间响应时间C.等待时间等待时间D运行时间运行时间答案答案:A第三题第三题三三、作作业业从从进进入入后后备备队队列列到到被被调调度度程程序序选选中的时间间隔称为。中的时间间隔称为。p91A周转时间周转时间B响应时间响应时间C.等待时间等待时间D触发时间触发时间答案答案:C第四题第四题四四、假假设设下下述述四四个个作作业业同同时时到到达达，当当使使用用最最高高优优先先数数优优先先调调度度算算法法时时，作作业业的的平平均均周周转转时时间间为为小时。小时。P91 作业作业所需运行时间所需运行时间优先数优先数124259381438A4.5B10.5C4.75D10.25答案答案:D第五题第五题

4、五五、系系统统在在，发发生生从从目目态态到到管管态态的转换。的转换。P92A.发出发出P操作时操作时B.发出发出V操作时操作时C.执行系统调用时执行系统调用时D.执行置程序状态字时执行置程序状态字时答案答案:C第六题第六题六、操作系统为用户提供两个接口。一个六、操作系统为用户提供两个接口。一个是是，用户利用它来组织和控，用户利用它来组织和控制作业的执行或管理计算机系统。另一制作业的执行或管理计算机系统。另一个是个是，编程人员使用它们来，编程人员使用它们来请求操作系统提供服务。请求操作系统提供服务。答：答：命令接口命令接口程序接口程序接口第七题第七题七七、设设有有一一组组作作业业，它它们们的的提

5、提交交时时间间及及运运行行时时间间如下：如下：作业号作业号提交时间提交时间运行时间运行时间(分钟分钟)19:007029:403039:50104 10:105在单道方式下，采用短作业优先调度算法，作在单道方式下，采用短作业优先调度算法，作业的执行顺序是。业的执行顺序是。答：答：1 1、4 4、3 3、2 2 第八题第八题八、设有八、设有4道作业，它们的提交时间及执行时间如下：道作业，它们的提交时间及执行时间如下：作业号作业号提交时间提交时间执行时间执行时间110.02.0210.21.0310.40.5 410.50.3试试计计算算在在单单道道程程序序环环境境下下，采采用用先先来来先先服服务

6、务调调度度算算法法和和最最短短作作业业优优先先调调度度算算法法时时的的平平均均周周转转时时间间和和平平均均带带权权周周转转时时间间，并并指指出出它它们们的的调调度度顺顺序序。（时时间间单单位：小时，以十进制进行计算。位：小时，以十进制进行计算。）答案答案第九题第九题九九、下下表表给给出出作作业业1、2、3的的到到达达时时间间和和运运行行时时间间。采采用用短短作作业业优优先先调调度度算算法法和和先先来来先先服服务务调调度度算算法法，试试问问平平均均周周转转时时间间各各为为多多少少?是是否否还还有有更更好好的的调调度度策策略略存存在在?（时时间间单单位位：小小时时，以十进制进行计算。以十进制进行计

7、算。）作业号作业号到达时间到达时间运行时间运行时间10.08.020.44.031.0答案答案第十题第十题十十、假假设设有有四四个个作作业业，它它们们的的提提交交、运运行行时时间间如如下下表表所所示示。若若采采用用响响应应比比高高者者优优先先调调度度算算法法，试试问问平平均均周周转转时时间间和和平平均均带带权权周周转转时时间间为为多多少少?（时时间间单位：小时，以十进制进行计算。单位：小时，以十进制进行计算。）作业号作业号到达时间到达时间运行时间运行时间18.02.028.30.538.50.149.00.4答案答案十一题十一题十十一一、设设有有一一组组作作业业，它它们们的的提提交交时时间间及

8、及运运行行时时间如下所示。间如下所示。作业号作业号到达时间到达时间运行时间运行时间(分钟分钟)18:00 7028:403038:50 10 49:105试问在单道方式下，采用响应比高者优先调度试问在单道方式下，采用响应比高者优先调度算法，作业的执行顺序是什么算法，作业的执行顺序是什么?答案答案十二题：死锁十二题：死锁-选择题选择题某系统中有三个并发进程，都需要同类资某系统中有三个并发进程，都需要同类资源源4个，试问该系统不会发生死锁的最少个，试问该系统不会发生死锁的最少资源数是资源数是_答案：答案：B十三题：银行家算法十三题：银行家算法设系统中有设系统中有3种类型的资源（种类型的资源（A，B

9、，C）和）和5个进程，资源的个进程，资源的数量为（数量为（17，5，20）。在）。在T0时刻系统状态见表。系统采用银时刻系统状态见表。系统采用银行家算法实施死锁避免策略。行家算法实施死锁避免策略。T0时刻是否为安全状态？若是，请给出安全序列。时刻是否为安全状态？若是，请给出安全序列。在在T0时刻若进程时刻若进程P2请求资源（请求资源（0，3，4），是否能实施资），是否能实施资源分配？为什么？源分配？为什么？在在的基础上，若进程的基础上，若进程P4请求资源（请求资源（2，0，1），是否能），是否能实施资源分配？为什么？实施资源分配？为什么？在在的基础上，若进程的基础上，若进程P1请求资源（请求资

10、源（0，2，0），是否能），是否能实施资源分配？为什么？实施资源分配？为什么？T T0 0时刻系统状态时刻系统状态最大资源需求量最大资源需求量已分配资源数量已分配资源数量A B CA B CP1P2P3P4P55 5 95 3 64 0 114 2 54 2 42 1 24 0 24 0 52 0 43 1 4剩余资源数剩余资源数 A B C答案答案MaxAllocationNeedAvailableABCABCABCABCP1559212347233P2536402134P34011405006P4425204221P5424314110安全序列安全序列MaxAllocationNeedWo

11、rkABCABCABCABCP4425204221233P2536402134437P34011405006839P542431411012314P155921234715418FinishFalseFalseFalseFalseFalse1.考虑一组进程：考虑一组进程：进程进程执行时间执行时间优先数优先数P1103P211P323P414P552其中，其中，小的优先数表示高的优先级小的优先数表示高的优先级。设这组进程在相对时刻。设这组进程在相对时刻0以以P1、P2、P3、P4、P5的次序进入就绪队列，进入时消的次序进入就绪队列，进入时消耗的时间忽略不计。耗的时间忽略不计。（1）分别给出分别给

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

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

14、.0 2 10.2 1.0 12.0 13.0 2.8 2 10.2 1.0 12.0 13.0 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=(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解：若采用先来先服务调度算法，则其调度顺序为解：若采用先

15、来先服务调度算法，则其调度顺序为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.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 平均周转时

16、间平均周转时间 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 1、2 2、3 3。作业作业 到达到达 运行运行 开始开始 完成完成 周转时间周转时间 1 0.0 1 0.0 8.0 0.0 8.0 8.0 0.0 8.0 2 0.4 2 0.4 4.0 8.0 12.0 11.6 4.0 8.0 12.0

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

18、转时间平均周转时间T=(8+8+12.6)存存在在缩缩短短平平均均周周转转时时间间的的策策略略，如如知知道道后后面面将将来来两两个个短短作作业业，因因此此在在作作业业1 1到到达达后后暂暂不不投投入入运运行行，等等所所有有作作业业到到齐齐后后再再按按短短作作业业优先调度算法调度，其调度顺序为优先调度算法调度，其调度顺序为3 3、2 2、1 1。作业作业 到达时间到达时间 运行时间运行时间 开始时间开始时间 完成时间完成时间 周转时间周转时间 3 1.0 3 1.0 2.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

19、 1 0.0 8.0 8.0 6.0 14.0 6.0 14.0 平均周转时间平均周转时间T=(1+5.6+14)返回返回第十题分析第十题分析所所谓谓响响应应比比高高者者优优先先调调度度算算法法，就就是是在在每每次次调调度度作作业业运运行行时时，先先计计算算后后备备作作业业队队列列中中每每个个作作业业的的响响应比，然后选响应比最高者投入运行。应比，然后选响应比最高者投入运行。响应比定义如下：响应比定义如下：响应比响应比=作业响应时间运行时间的估计值作业响应时间运行时间的估计值 其其中中响响应应时时间间为为作作业业进进入入系系统统后后的的等等待待时时间间加加上上估估计的运行时间。于是计的运行时间

20、。于是 响应比响应比=1+作业等待时间运行时间的估计值作业等待时间运行时间的估计值第十题答案第十题答案在在8 8：0000时时，因因为为只只有有作作业业1 1到到达达，系系统统将将作作业业1 1投投入入运运行行。作作业业1 1运行运行2 2小时小时(即即 1010：0000时时)完完成成。由由于于该该算算法法采采用用响响应应比比高高者者优优先先调调度度算算法法，这样在作业这样在作业1 1执行执行 完完后后，要要计计算算剩剩下下三三个个作作业业的的响响应应比比，然然后后选选响响应应比比高高者者去运行。剩下三个作业去运行。剩下三个作业 的响应比为：的响应比为：r2=l+(10.0-8.3)r2=l

21、+(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+(10.0-9.0)r4=l+(10.0-9.0)0.4=3.5 0.4=3.5 从计算结果看，作业从计算结果看，作业3的响应比高，所以让作业的响应比高，所以让作业3先运行。先运行。作作业业3 3运运行行小小时时完完成成(即即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

22、+(10.1-9.0)0.4=3.75 0.4=3.75 从从上上述述计计算算结结果果看看，作作业业2 2的的响响应应比比高高，所所以以让让作作业业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

23、 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 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 返回返回第

24、十一题答案第十一题答案8:008:00时时，因因为为这这时时只只有有作作业业1 1到到达达，因因此此调调度度作作业业1 1运行。运行。7070分钟后分钟后(即即9:10)9:10)，作业，作业1 1运行完毕。运行完毕。9:109:10时时，这这时时作作业业1 1运运行行完完成成，其其他他三三个个作作业业均均已已到到达。它们的响应比分别为：达。它们的响应比分别为：r2=1+(9:108:40)r2=1+(9:108:40)30=2 30=2 r3=1+(9:108:50)r3=1+(9:108:50)10=3 10=3 r4=1+(9:109:10)r4=1+(9:109:10)5=1 5=1

25、从从计计算算结结果果看看，作作业业3 3的的响响应应比比高高，所所以以让让作作业业3 3先运行。先运行。1010分钟后分钟后(即即9:20)9:20)，作业，作业3运行完毕运行完毕9:209:20时时，这这时时作作业业3 3运运行行完完成成，其其他他两两个个作作业业的的响应比分别为：响应比分别为：r2=1+(9:208:40)r2=1+(9:208:40)30=2.3 30=2.3 r4=1+(9:209:10)r4=1+(9:209:10)5=3 5=3 从从计计算算结结果果看看，作作业业4 4的的响响应应比比高高，所所以以让让作作业业4 4先运行。先运行。5 5分钟后分钟后(即即9:25)9:25)，作作业业4 4运运行行完完毕毕这这时时只只剩剩下下作作业业2 2，调调度度作作业业2 2运行。运行。解：从上面的分析可知，作业的执行顺序为解：从上面的分析可知，作业的执行顺序为1、3、4、2。返回返回