1、操作系统复习资料习题 5 第3章 调度与死锁一、单项选择题1. 在为多道程序所提供的可共享的系统资源不足时，可能出现死锁。但是，不适当的_也可能产生死锁。A. 进程优先权 B. 资源的线性分配C. 进程推进顺序 D. 分配队列优先权2. 采用资源剥夺法可解除死锁，还可以采用_方法解除死锁。A. 执行并行操作 B. 撤消进程 C. 拒绝分配新资源 D. 修改信号量3. 产生死锁的四个必要条件是：互斥、_、循环等待和不剥夺。A. 请求与阻塞 B. 请求与保持 C. 请求与释放 D. 释放与阻塞4. 发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏_条件是不太实际的。A.
2、互斥 B. 不可抢占C. 部分分配 D. 循环等待5. 在分时操作系统中，进程调度经常采用_算法。A. 先来先服务 B. 最高优先权C. 时间片轮转 D. 随机6. 资源的按序分配策略可以破坏_条件。A. 互斥使用资源 B. 占有且等待资源 C. 非抢夺资源 D. 循环等待资源7. 银行家算法是一种_算法。A. 死锁解除 B. 死锁避免C. 死锁预防 D. 死锁检测8. _优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。A. 先来先服务 B. 静态C. 动态 D. 短作业9. 某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是_。A. 9 B. 1
3、0 C. 11 D. 1210. 以优先级为基础的进程调度算法可以保证在任何时候正在运行的进程总是非等待状态下诸进程中优先级最高的进程。上述描述是_。（可抢占的情况下）A. 正确的 B. 错误的11. 当检测出发生死锁时，可以通过撤消一个进程解除死锁。上述描述是_。A. 正确的 B. 错误的12. 在下列解决死锁的方法中，属于死锁预防策略的是_。A. 银行家算法 B. 资源有序分配法 C. 死锁检测法 D. 资源分配图化简法13. _是作业存在的惟一标志。A. 作业名 B. 进程控制块 C. 作业控制块 D. 程序名14. 用户使用操作系统通常有三种手段，它们是终端命令、系统调用命令和_。A.
4、 计算机高级指令 B. 宏命令 C. 作业控制语言 D. 汇编语言 15. 在分时操作系统环境下运行的作业通常称为_。A. 后台作业 B. 长作业 C. 终端型作业 D. 批量型作业16. 在各种作业调度算法中，若所有作业同时到达，则平均等待时间最短的算法是_。A. 先来先服务 B. 优先数 C. 最高响应比优先 D. 短作业优先17. 既考虑作业等待时间，又考虑作业执行时间的调度算法是_。A. 响应比高者优先 B. 短作业优先C. 优先级调度 D. 先来先服务18. _是指从作业提交给系统到作业完成的时间间隔。A. 周转时间 B. 响应时间C. 等待时间 D. 运行时间19. 下述作业调度算
5、法中，_调度算法与作业的估计运行时间有关。A. 先来先服务 B. 短作业优先C. 均衡 D. 时间片轮转二、填空题1. 作业调度又称 长程调度 。其主要功能是 调度作业进入内存运行 ，并为作业做好运行前的准备工作和作业完成后的善后处理工作。2. 操作系统为用户提供两个接口。一个是 命令接口 ，用户利用它来组织和控制作业的执行或管理计算机系统。另一个是 程序接口 ，编程人员使用它们来请求操作系统提供服务。3. 按命令接口对作业控制方式的不同可将命令接口分为 脱机 和 联机 。4. 设有一组作业，它们的提交时间及运行时间如下：作业号提交时间运行时间（分钟）19:007029:403039:5010
6、410:105在单道方式下，采用短作业优先调度算法，作业的执行顺序是_1、4、3、2_。5. 进程的调度方式有两种，一种是 抢占 ，另一种是 非抢占 。6. 死锁是指在系统中的多个_进程_无限期地等待永远不会发生的条件。7. 一种最常用的进程调度算法是把处理机分配给具有最高优先权的进程。而确定优先权的方法概括起来不外乎是基于 类型 特性和 进程推进（进程等待时间和占用CPU的时间） 特性两种方法。前者所得到的是 静态 优先权，后者所得到的是 动态 优先权。8. 在_FIFO_调度算法中，按照进程进入就绪队列的先后次序来分配处理机。9. 银行家算法中，当一个进程提出的资源请求将导致系统从 安全状
7、态 进入 不安全状态 时，系统就拒绝它的资源请求。10. 如果要求所有进程一次性申请它所需要的全部资源。若系统有足够的资源分配给进程，便一次把所有的资源分配给该进程。但在分配时只要有一种资源要求不能满足，则资源全不分配，进程等待。这种死锁预防方法破坏了死锁产生必要条件中的_请求且保持_条件。11. 对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于 避免 ，破坏环路等待条件是属于 预防 ，而剥夺资源是 解除 的基本方法。解 析 题 31. 为什么说采用有序资源分配法不会产生死锁？解：为了便于说明，不妨设系统中有m类资源，n个进程，分别用R1，R2，Rm（1，2，m
8、可看作资源编号）和P1，P2， Pn表示。根据有序资源分配法可知，进程申请资源时必须按照资源编号的升序进行，即任何进程在占有了Ri类资源后，再申请的资源Rj的编号j一定大于i。因此在任一时刻，系统中至少存在一个进程Pk，它占有了较高编号的资源Rh，且它继续请求的资源必然是空闲的，因而Pk可以一直向前推进直至完成，当Pk运行完成后即会释放它占有的所有资源；在Pk完成之后，剩下的进程集合中同样会存在一个进程，它占有了较高编号的资源，且它继续请求的资源必然是空闲的，因而它可以一直向前推进直至完成；以此类推，所有进程均可运行完成，故不会发生死锁。2. n个进程共享某种资源R，该资源共有m个可分配单位，
9、每个进程一次一个地申请或释放资源单位。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于mn，试证明在这个系统中不可能发生死锁。解：设max（i）表示第i个进程的最大资源需求量，need（i）表示第i个进程还需要的资源量，alloc（i）表示第i个进程已分配的资源量。由题中所给条件可知：max（1）max（n）=（need（1）need（n）（alloc（1）+alloc（n）mn如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，即alloc（1）alloc（n）= m另一方面所有进程将陷入无限等待状态。由上述两式可得：need（1）need（n）n上式表示死锁
10、发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i，need（i）=0，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。3. 有相同类型的5个资源被4个进程所共享，且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是否会由于对这种资源的竞争而产生死锁。解：该系统不会由于对这种资源的竞争而产生死锁。因为在最坏情况下，每个进程都需要2个这样的资源，且每个进程都已申请到了1个资源，那么系统中还剩下1个可用资源。无论系统为了满足哪个进程的资源申请而将资源分配给
11、该进程，都会因为该进程已获得了它所需要的全部资源而确保它运行完毕，从而可将它占有的2个资源归还给系统，这就保证了其余三个进程能顺利运行。由此可知，该系统不会由于对这种资源的竞争而产生死锁。4.（北京大学1991年试题）考虑下列资源分配策略：对资源的申请和释放可以在任何时候进行。如果一个进程提出资源请求时得不到满足，若此时无由于等待资源而被阻塞的进程，则自己就被阻塞；若此时已有等待资源而被阻塞的进程，则检查所有由于等待资源而被阻塞的进程。如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。例如，考虑一个有3类资源的系统，系统所有可用资源为（4，2，2），进程A申请（2，2，1），可满
12、足；进程B申请（1，0，1），可满足；若A再申请（0，0，1），则被阻塞。此时，若C请求（2，0，0），它可以分到剩余资源（1，0，0），并从A已分到的资源中获得一个资源，于是进程A的分配向量变成（1，2，1）而需求向量变成（1，0，1）。 这种分配策略会导致死锁吗？如果会，请举一个例子；如果不会，请说明产生死锁的哪一个必要条件不成立？ 这种分配方式会导致某些进程的无限等待吗？为什么？解：本题所给的资源分配策略不会产生死锁。因为本题给出的分配策略规定若一进程的资源得不到满足，则检查所有由于等待资源而被阻塞的进程，如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。从而破坏了产生死锁
13、必要条件中的不剥夺条件，这样系统就不会产生死锁。这种方法会导致某些进程无限期的等待。因为被阻塞进程的资源可以被剥夺，所以被阻塞进程所拥有的资源数量在其被唤醒之前只可能减少。若系统中不断出现其他进程申请资源，这些进程申请的资源与被阻塞进程申请或拥有的资源类型相同且不被阻塞，则系统无法保证被阻塞进程一定能获得所需要的全部资源。例如，本题中的进程A申请（2，2，1）后再申请（0，0，1）被阻塞。此后，进程C又剥夺了进程A的一个资源，使得进程A拥有的资源变为（1，2，1），其需求向量为（1，0，1）。之后，若再创建的进程总是只申请第1和第3类资源，总是占有系统所剩下的第1和第3类资源的全部且不阻塞，那
14、么进程A将会无限期地等待。5.（上海交通大学1999年试题）一台计算机有8台磁带机。它们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没有死锁危险，并说明原因。解：当N为1，2，3时，系统没有产生死锁的危险。因为，当系统中只有1个进程时，它最多需要3台磁带机，而系统有8台磁带机，其资源数目已足够系统内的1个进程使用，因此绝不可能发生死锁；当系统中有2个进程时，最多需要6台磁带机，而系统有8台磁带机，其资源数目也足够系统内的2个进程使用，因此也不可能发生死锁；当系统中有3个进程时，在最坏情况下，每个进程都需要3个这样的资源，且假定每个进程都已申请到了2个资源，那么系统中还剩
15、下2个可用资源，无论系统为了满足哪个进程的资源申请而将资源分配给该进程，都会因为该进程已获得了它所需要的全部资源而确保它运行完毕，从而可将它占有的3个资源归还给系统，这就保证了其余进程能顺利运行完毕。由此可知，当N为1，2，3时，该系统不会由于对这种资源的竞争而产生死锁。6.（北京大学1997年试题）设系统中有3种类型的资源（A，B，C）和5个进程P1、P2、P3、P4、P5，A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态见下表所示。系统采用银行家算法实施死锁避免策略。T0时刻系统状态最大资源需求量已分配资源数量ABCABCP1559212P2536402P340
16、11405P4425204P5424314剩余资源ABC233 T0时刻是否为安全状态？若是，请给出安全序列。 在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？ 在的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？ 在的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？解：由题目所给出的最大资源需求量和已分配资源数量，可以计算出T0时刻各进程的资源需求量Need，Need最大资源需求量分配资源数量：资源需求量ABCP1347P2134P3006P4221P5110 利用银行家算法对此时刻的资源分配情况进行分析，可得此时刻的安全性
17、分析情况：WorkNeedAllocationWork+AllocationFinishP52 3 31 1 03 1 45 4 7trueP45 4 72 2 12 0 47 4 11trueP37 4 110 0 64 0 511 4 16trueP211 4 161 3 44 0 215 4 18trueP115 4 183 4 72 1 217 5 20true从上述情况分析中可以看出，此时存在一个安全序列P5，P4，P3，P2，P1，故该状态是安全的。 在T0时刻若进程P2请求资源（0，3，4），因请求资源数（0，3，4）剩余资源数（2，2，3），所以不能分配。 在的基础上，若进程P
18、4请求资源（2，0，1），按银行家算法进行检查： P4请求资源（2，0，1） P4资源需求量（2，2，1） P4请求资源（2，0，1） 剩余资源数（2，3，3） 试分配并修改相应数据结构，资源分配情况如下：AllocationNeedAvailableP12 1 23 4 70 3 2P24 0 21 3 4P34 0 50 0 6P44 0 50 2 0 P53 1 41 1 0 再利用安全性算法检查系统是否安全，可得此时刻的安全性分析情况：WorkNeedAllocationWork+AlloFinishP40 3 20 2 04 0 54 3 7trueP54 3 71 1 03 1 4
19、7 4 11trueP37 4 110 0 64 0 511 4 16trueP211 4 161 3 44 0 215 4 18trueP115 4 183 4 72 1 217 5 20true从上述情况分析中可以看出，此时存在一个安全序列P4，P5，P3，P2，P1，故该状态是安全的，可以立即将P4所申请的资源分配给它。 在的基础上，若进程P1请求资源（0，2，0），按银行家算法进行检查： P1请求资源（0，2，0） P1资源需求量（3，4，7） P1请求资源（0，2，0） 剩余资源数（0，3，2） 试分配并修改相应数据结构，资源分配情况如下：AllocationNeedAvailabl
20、eP12 3 23 2 70 1 2P24 0 21 3 4P34 0 50 0 6P44 0 50 2 0 P53 1 41 1 0 再利用安全性算法检查系统是否安全，可用资源Available（0，1，2）已不能满足任何进程的资源需求，故系统进入不安全状态，此时系统不能将资源分配给P1。7. 若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为a、b、c，且满足关系abc，试证明采用短作业优先调度算法能获得最小平均周转时间。解：由于短作业优先调度算法总是在后备作业队列中选择运行时间最短的作业作为调度对象，因此对短作业优先调度算法而言，这三个作业的总周转时间为T1=
21、a(ab)(abc)=3a2bc 若不按短作业优先调度算法来调度这三个作业，不失一般性，假定调度顺序为2、1、3，则其总周转时间为T2=b(ba)(bac)=3b2ac 式得：T2T1=ba0由此可见，短作业优先调度算法能获得最小平均周转时间。8. 设有4道作业，它们的提交时间及执行时间如下：作业号提交时间执行时间110.02.0210.21.0310.40.5410.50.3试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（时间单位：小时，以十进制进行计算。）解：若采用先来先服务调度算法，则其调度顺序为1、2、3、
22、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.02.83.13.3)/4=2.8平均带权周转时间 W=(12.86.211)/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.01.82.43.6)/4=2.45平均带权周转时间 W=(164.83.6)/4=3.85
