《操作系统-处理机调度与死锁习题.ppt》由会员分享，可在线阅读，更多相关《操作系统-处理机调度与死锁习题.ppt（32页珍藏版）》请在三一办公上搜索。
1、处理机调度与死锁习题课,难点：调度算法的性能评估银行家算法避免死锁,本章内容回顾,处理机调度的层次（3级）作业调度和进程调度的功能周转时间和带权周转时间的计算调度算法及其各自优缺点调度算法性能评估（公平性，系统吞吐量，响应时间，资源利用率）(可靠性，简洁性)死锁产生的原因（2个）和必要条件（4个）,内容回顾,处理死锁的基本方法预防死锁的方法如何用银行家算法避免死锁如何求某时刻系统的安全性如何检测死锁（死锁定理）如何解除死锁,第一题,一、既考虑作业等待时间，又考虑作业执行时间的调度算法是。A.响应比高者优先 B短作业优先 C优先级调度 D先来先服务,答案:A,第二题,二、是指从作业提交给系统到作
2、业完成的时间间隔。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 A4.5 B10.5 C4.75 D10.25,答案:D,第五题,五、系统在，发生从目态到管态的转换。P92 A.发出P操作时 B.发出V操作时 C.执行系统调用时 D.执行置程序状态字时,答案:C,第六
3、题,六、操作系统为用户提供两个接口。一个是，用户利用它来组织和控制作业的执行或管理计算机系统。另一个是，编程人员使用它们来请求操作系统提供服务。,答：命令接口 程序接口,第七题,七、设有一组作业，它们的提交时间及运行时间如下：作业号 提交时间 运行时间(分钟)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 试计算在单
4、道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（时间单位：小时，以十进制进行计算。）,答案,第九题,九、下表给出作业1、2、3的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各为多少?是否还有更好的调度策略存在?（时间单位：小时，以十进制进行计算。）作业号 到达时间 运行时间 1 0.0 8.0 2 0.4 4.0 3 1.0 1.0,答案,第十题,十、假设有四个作业，它们的提交、运行时间如下表所示。若采用响应比高者优先调度算法，试问平均周转时间和平均带权周转时间为多少?（时间单位：小时，以
5、十进制进行计算。）作业号 到达时间 运行时间 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个进
6、程，资源的数量为（17，5，20）。在T0时刻系统状态见表。系统采用银行家算法实施死锁避免策略。T0时刻是否为安全状态？若是，请给出安全序列。在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？在的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？在的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？,T0时刻系统状态,答案,安全序列,1.考虑一组进程：进程 执行时间 优先数P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2其中，小的优先数表示高的优先级。设这组进程在相对时刻0以P1、P2、P3、P4、P5的次序进入就绪队
7、列，进入时消耗的时间忽略不计。（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
8、 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
9、.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=
10、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.
11、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,返回,第十题分析,所谓响应比高者优先调度算法，就是在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后选响应比最高者投入运行。响应比定义如下：响应比=作业响应时间运行时间的估计值 其中响
12、应时间为作业进入系统后的等待时间加上估计的运行时间。于是 响应比=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和作
13、业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+
14、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.3 r4=1+(9:209:10)5=3 从计算结果看，作业4的响应比高，所以让作业4先运行。5分钟后(即9:25)，作业4运行完毕这时只剩下作业2，调度作业2运行。解：从上面的分析可知，作业的执行顺序为1、3、4、2。,返回,
