处理机调度与死锁习题课

处理机调度与死锁习题课难点：调度算法的性能评估银行家算法避免死锁本章内容回顾处理机调度的层次（4级）作业调度和进程调度的功能周转时间和带权周转时间的计算调度算法及其各自优缺点调度算法性能评估（公平性，系统吞吐量，响应时间，资源利用率）(可靠性，简洁性)死锁产生的原因（2个）和必要条件（4个）内容回顾处理死锁的基本方法预防死锁的方法如何用银行家算法避免死锁如何求某时刻系统的安全性如何检测死锁（死锁定理）如何解除死锁第一题一、既考虑作业等待时间，又考虑作业执行时间的调度算法是＿＿＿＿＿。A.响应比高者优先B．短作业优先C．优先级调度D．先来先服务答案:A第二题二、＿＿＿＿＿＿是指从作业提交给系统到作业完成的时间间隔。p91A．周转时间B．响应时间C.等待时间D．运行时间答案:A第三题三、作业从进入后备队列到被调度程序选中的时间间隔称为＿＿＿＿＿。p91A．周转时间B．响应时间C.等待时间D．触发时间答案:C第四题四、假设下述四个作业同时到达，当使用最高优先数优先调度算法时，作业的平均周转时间为＿＿＿＿＿小时。P91作业所需运行时间优先数124259381438A．4.5B．10.5C．4.75D．10.25答案:D第五题五、系统在＿＿＿＿＿＿，发生从目态到管态的转换。P92A.发出P操作时B.发出V操作时C.执行系统调用时D.执行置程序状态字时答案:C第六题六、操作系统为用户提供两个接口。一个是＿＿①＿＿，用户利用它来组织和控制作业的执行或管理计算机系统。另一个是＿＿②＿＿，编程人员使用它们来请求操作系统提供服务。答：①命令接口②程序接口第七题七、设有一组作业，它们的提交时间及运行时间如下：作业号提交时间运行时间(分钟)19:007029:403039:5010410:105在单道方式下，采用短作业优先调度算法，作业的执行顺序是＿＿＿。答：1、4、3、2第八题八、设有4道作业，它们的提交时间及执行时间如下：作业号提交时间执行时间110.02.0210.21.0310.40.5410.50.3试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（时间单位：小时，以十进制进行计算。）答案第九题九、下表给出作业1、2、3的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各为多少?是否还有更好的调度策略存在?（时间单位：小时，以十进制进行计算。）作业号到达时间运行时间10.08.020.44.031.01.0答案第十题十、假设有四个作业，它们的提交、运行时间如下表所示。若采用响应比高者优先调度算法，试问平均周转时间和平均带权周转时间为多少?（时间单位：小时，以十进制进行计算。）作业号到达时间运行时间18.02.028.30.538.50.149.00.4答案十一题十一、设有一组作业，它们的提交时间及运行时间如下所示。作业号到达时间运行时间(分钟)18:007028:403038:501049:105试问在单道方式下，采用响应比高者优先调度算法，作业的执行顺序是什么?答案十二题：死锁-选择题某系统中有三个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是______A.9B.10C.11D.12答案：B十三题：银行家算法设系统中有3种类型的资源（A，B，C）和5个进程，资源的数量为（17，5，20）。在T0时刻系统状态见表。系统采用银行家算法实施死锁避免策略。①T0时刻是否为安全状态？若是，请给出安全序列。②在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？③在②的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？④在③的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？T0时刻系统状态最大资源需求量已分配资源数量ABCABCP1P2P3P4P55595364011425424212402405204314剩余资源数ABC答案MaxAllocationNeedAvailableABCABCABCABCP1559212347233P2536402134P34011405006P4425204221P5424314110安全序列MaxAllocationNeedWorkABCABCABCABCP4425204221233P2536402134437P34011405006839P542431411012314P155921234715418FinishFalseFalseFalseFalseFalse1.考虑一组进程：进程执行时间优先数P1103P211P323P414P552其中，小的优先数表示高的优先级。设这组进程在相对时刻0以P1、P2、P3、P4、P5的次序进入就绪队列，进入时消耗的时间忽略不计。（1）分别给出FCFS，HRN，RR（时间片S=1）算法下，这组进程的执行顺序图示。（2）每个进程在上述何种算法下它的等待时间和周转时间最短？（3）计算在每种算法下的平均等待时间和平均周转时间。作业1：作业2：2.考虑下面的系统“瞬态”：五个进程{P1,P2,P3,P4,P5}，四类资源{A,B,C,D}AllocationMaxAvailableP1001200120012P210001750P313542356P406320652P500140656使用银行家算法回答以下问题：1)给出Need的内容2)系统是安全状态吗？(请写出过程)3)如果进程P2要求{0，4，2，0}，此要求能满足吗？(请写出过程)第八题答案解：若采用先来先服务调度算法，则其调度顺序为1、2、3、4。作业提交执行开始完成周转带权周转110.02.010.012.02.01.0210.21.012.013.02.82.8310.40.513.013.53.16.2410.50.313.513.83.311.0平均周转时间T=(2.0+2.8+3.1+3.3)／4=2.8平均带权周转时间W=(1+2.8+6.2+11)／4=5.25解：若采用先来先服务调度算法，则其调度顺序为1、4、3、2。作业提交执行开始完成周转带权周转110.02.010.012.02.01.0410.50.312.012.31.86.0310.40.512.312.82.44.8210.21.012.813.83.63.6平均周转时间T=(2.0+1.8+2.4+3.6)／4=2.45平均带权周转时间W=(1+6+4.8+3.6)／4=3.85返回第九题答案解：采用先来先服务调度策略，则调度顺序为1、2、3。作业到达运行开始完成周转时间10.08.00.08.08.020.44.08.012.011.631.01.012.013.012.0平均周转时间T=(8+11.6+12)／3=10.53采用短作业优先调度策略，则调度顺序为1、3、2。作业到达时间运行时间开始时间完成时间周转时间10.08.00.08.08.031.01.08.09.08.020.44.09.013.012.6平均周转时间T=(8+8+12.6)／3=9.53存在缩短平均周转时间的策略，如知道后面将来两个短作业，因此在作业1到达后暂不投入运行，等所有作业到齐后再按短作业优先调度算法调度，其调度顺序为3、2、1。作业到达时间运行时间开始时间完成时间周转时间31.01.01.02.01.020.44.02.06.05.610.08.06.014.014.0平均周转时间T=(1+5.6+14)／3=6.87返回第十题分析所谓响应比高者优先调度算法，就是在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后选响应比最高者投入运行。响应比定义如下：响应比=作业响应时间／运行时间的估计值其中响应时间为作业进入系统后的等待时间加上估计的运行时间。于是响应比=1+作业等待时间／运行时间的估计值第十题答案在8：00时，因为只有作业1到达，系统将作业1投入运行。作业1运行2小时(即10：00时)完成。由于该算法采用响应比高者优先调度算法，这样在作业1执行完后，要计算剩下三个作业的响应比，然后选响应比高者去运行。剩下三个作业的响应比为：r2=l+(10.0-8.3)／0.5=4.4r3=l+(10.0-8.5)／0.1=16r4=l+(10.0-9.0)／0.4=3.5从计算结果看，作业3的响应比高，所以让作业3先运行。作业3运行0.1小时完成(即10：10时)，此时，作业2和作业4的响应比为：r2=l+(10.1-8.3)／0.5=4.6r4=l+(10.1-9.0)／0.4=3.75从上述计算结果看，作业2的响应比高，所以让作业2先运行。因此四个作业的执行次序为：作业1、作业3、作业2、作业4.解：四个作业的调度次序为：作业1、作业3、作业2、作业4。作业到达运行开始完成周转带权周转18.02.08.010.02.01.028.30.510.110.62.34.638.50.110.010.11.616.049.00.410.611.02.05.0平均周转时间T=(2.0+2.3+1.6+2.0)／4=1.975平均带权周转时间W=(1+4.6+16+5)／4=6.65返回第十一题答案8:00时，因为这时只有作业1到达，因此调度作业1运行。70分钟后(即9:10)，作业1运行完毕。9:10时，这时作业1运行完成，其他三个作业均已到达。它们的响应比分别为：r2=1+(9:10—8:40)／30=2r3=1+(9:10—8:50)／10=3r4=1+(9:10—9:10)／5=1从计算结果看，作业3的响应比高，所以让作业3先运行。10分钟后(即9:20)，作业3运行完毕．9:20时，这时作业3运行完成，其他两个作业的响应比分别为：r2=1+(9:20—8:40)／30=2.3r4=1+(9:20—9:10)／5=3从计算结果看，作业4的响应比高，所以让作业4先运行。5分钟后(即9:25)，作业4运行完毕．这时只剩下作业2，调度作业2运行。解：从上面的分析可知，作业的执行顺序为1、3、4、2。返回