操作系统-处理机调度与死锁习题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,处理机调度与死锁习题课,难点：调度算法的性能评估,银行家算法避免死锁,本章内容回顾,处理机调度的层次（3级）,作业调度和进程调度的功能,周转时间和带权周转时间的计算,调度算法及其各自优缺点,调度算法性能评估（公平性，系统吞吐量，响应时间，资源利用率）(可靠性，简洁性),死锁产生的原因（2个）和必要条件（4个）,内容回顾,处理死锁的基本方法,预防死锁的方法,如何用银行家算法避免死锁,如何求某时刻系统的安全性,如何检测死锁（死锁定理）,如何解除死锁,第一题,一、既考虑作业等待时间，又考虑作业执行时间的调度算法是,。,A.,响应比高者优先,B,短作业优先,C,优先级调度,D,先来先服务,答案:A,第二题,二、是指从作业提交给系统到作业完成的时间间隔。,p91,A,周转时间,B,响应时间,C.,等待时间,D,运行时间,答案:A,第三题,三、作业从进入后备队列到被调度程序选中的时间间隔称为。,p91,A,周转时间,B,响应时间,C.,等待时间,D,触发时间,答案:C,第四题,四、假设下述四个作业同时到达，当使用最高优先数优先调度算法时，作业的平均周转时间为小时。,P91,作业,所需运行时间,优先数,1 2 4,2 5 9,3 8 1,4 3 8,A,4.5 B,10.5 C,4.75 D,10.25,答案:D,第五题,五、系统在，发生从目态到管态的转换。,P92,A.,发出,P,操作时,B.,发出,V,操作时,C.,执行系统调用时,D.,执行置程序状态字时,答案:C,第六题,六、操作系统为用户提供两个接口。一个是，用户利用它来组织和控制作业的执行或管理计算机系统。另一个是，编程人员使用它们来请求操作系统提供服务。,答：命令接口,程序接口,第七题,七、设有一组作业，它们的提交时间及运行时间如下：,作业号,提交时间,运行时间,(,分钟,),1 9:00 70,2 9:40 30,3 9:50 10,4 10:10 5,在单道方式下，采用短作业优先调度算法，作业的执行顺序是。,答：,1,、,4,、,3,、,2,第八题,八、设有,4,道作业，它们的提交时间及执行时间如下：,作业号,提交时间,执行时间,1 10.0 2.0,2 10.2 1.0,3 10.4 0.5,4 10.5 0.3,试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。,（,时间单位：小时，以十进制进行计算。,）,答案,第九题,九、下表给出作业,1,、,2,、,3,的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各为多少,?,是否还有更好的调度策略存在,?（,时间单位：小时，以十进制进行计算。,）,作业号,到达时间,运行时间,1 0.0 8.0,2 0.4 4.0,3 1.0 1.0,答案,第十题,十、假设有四个作业，它们的提交、运行时间如下表所示。若采用响应比高者优先调度算法，试问平均周转时间和平均带权周转时间为多少,?（,时间单位：小时，以十进制进行计算。,）,作业号,到达时间,运行时间,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,试问在单道方式下，采用响应比高者优先调度算法，作业的执行顺序是什么,?,答案,十二题：死锁-选择题,某系统中有三个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是_,A.9 B.10 C.11 D.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），是否能实施资源分配？为什么？,T,0,时刻系统状态,最大资源需求量,已分配资源数量,A B C,A B C,P1,P2,P3,P4,P5,5 5 9,5 3 6,4 0 11,4 2 5,4 2 4,2 1 2,4 0 2,4 0 5,2 0 4,3 1 4,剩余资源数,A B C,答案,Max,Allocation,Need,Available,A B C,A B C,A B C,A B C,P1,5 5 9,2 1 2,3 4 7,2 3 3,P2,5 3 6,4 0 2,1 3 4,P3,4 0 11,4 0 5,0 0 6,P4,4 2 5,2 0 4,2 2 1,P5,4 2 4,3 1 4,1 1 0,安全序列,Max,Allocation,Need,Work,A B C,A B C,A B C,A B C,P4,4 2 5,2 0 4,2 2 1,2 3 3,P2,5 3 6,4 0 2,1 3 4,4 3 7,P3,4 0 11,4 0 5,0 0 6,8 3 9,P5,4 2 4,3 1 4,1 1 0,12 3 14,P1,5 5 9,2 1 2,3 4 7,15 4 18,Finish,False,False,False,False,False,1.考虑一组进程：,进程 执行时间 优先数P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2其中，,小的优先数表示高的优先级,。设这组进程在相对时刻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 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 P3 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,、,2,、,3,、,4,。,作业,提交,执行,开始,完成,周转,带权周转,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,3 10.4 0.5 13.0 13.5 3.1 6.2,4 10.5 0.3 13.5 13.8 3.3 11.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,。,作业,提交,执行,开始,完成,周转,带权周转,1 10.0 2.0 10.0 12.0 2.0 1.0,4 10.5 0.3 12.0 12.3 1.8 6.0,3 10.4 0.5 12.3 12.8 2.4 4.8,2 10.2 1.0 12.8 13.8 3.6 3.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,。,作业,到达,运行,开始,完成,周转时间,1 0.0 8.0 0.0 8.0 8.0,2 0.4 4.0 8.0 12.0 11.6,3 1.0 1.0 12.0 13.0 12.0,平均周转时间,T=(8+11.6+12),3=10.53,采用短作业优先调度策略，则调度顺序为,1,、,3,、,2,。,作业,到达时间,运行时间,开始时间,完成时间,周转时间,1 0.0 8.0 0.0 8.0 8.0,3 1.0 1.0 8.0 9.0 8.0,2 0.4 4.0 9.0 13.0 12.6,平均周转时间,T=(8+8+12.6),3=9.53,存在缩短平均周转时间的策略，如知道后面将来两个短作业，因此在作业,1,到达后暂不投入运行，等所有作业到齐后再按短作业优先调度算法调度，其调度顺序为,3,、,2,、,1,。,作业,到达时间,运行时间,开始时间,完成时间,周转时间,3 1.0 1.0 1.0 2.0 1.0,2 0.4 4.0 2.0 6.0 5.6,1 0.0 8.0 6.0 14.0 14.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.4,r3=l+(10.0-8.5),0.1=16,r4=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.6,r4=l+(10.1-9.0),0.4=3.75,从上述计算结果看，作业,2,的响应比高，所以让作业,2,先运行。因此四个作业的,执行次序为：作业,1,、作业,3,、作业,2,、作业,4.,解：四个作业的调度次序为：作业,1,、作业,3,、作业,2,、作业,4,。,作业,到达,运行,开始,完成,周转,带权周转,1 8.0 2.0 8.0 10.0 2.0 1.0,2 8.3 0.5 10.1 10.6 2.3 4.6,3 8.5 0.1 10.0 10.1 1.6 16.0,4 9.0 0.4 10.6 11.0 2.0 5.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:108:40),30=2,r3=1+(9:108:50),10=3,r4=1+(9:109:10),5=1,从计算结果看，作业,3,的响应比高，所以让作业,3,先运行。,10,分钟后,(,即,9:20),，作业,3,运行完毕,9:20,时，这时作业,3,运行完成，其他两个作业的响应比分别为：,r2=1+(9:208:40),30=2