计算机操作系统(第三版)汤小丹第3章

1、注意：1)“本章要点”部分，用红字标注的不是期末考试出题范围。2)“习题部分”用蓝字标注的是重点习题，期末考试50%的题目是这些习题的原题。红字标注的习题期末考试不考，仅供考研的同学参考。3）大部分习题答案只给出要点，同学们可以自行适当补充，但一定要简明扼要。4）如“本章要点”部分用红字标注的非考试内容，在“习题”部分有相关的重点习题，则对该部分内容只需做该习题即可。-第三章 要点这一章和第2章是本课程最重要的两章。3.1小节概念上了解什么是高级调度、中级调度、低级调度。熟知P87介绍的抢占式和非抢占式调度。 3.2 小节 熟知P88图3.1调度队列模型。3.3 小节 熟悉本小节介绍的各种调度

2、算法及其优劣。3.4 小节 知道什么是实时调度，实现实时调度的基本条件。其它内容可以不看。 3.5 小节 了解死锁产生的原因（P103-105）。 特别熟悉产生死锁的四个必要条件（P105） 了解处理死锁的基本方法（P105-106）3.6 小节 了解预防死锁的几种办法（P106-107） 熟悉系统安全状态（107-108）、银行家算法（P109-111），知道怎样使用银行家算法的思路，手工找出是否存在安全序列。考研的同学最好能编程实现它。 3.7小节 了解P112资源分配图的约简、了解P113的死锁定理。本章习题1. 高级调度与低级调度的主要任务是什么?为什么要引入中级调度?a 作业调度又称

3、宏观调度或高级调度，其主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存，输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利.b. 进程调度（又称CPU调度、微观调度、低级调度），其主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它。C 为了提高内存利用率和系统吞吐量，引入了中级调度. 2 何为作业？作业步和作业流？答：P84-85。在个人电脑上很少用到“作业”这个概念，但Windows操作系统有一种批处理文件，其后缀为.bat，相当于教材提到的“作业说明书”， 批处理文件可以顺序的执行一系列程序。3 在什么情况下

4、需要用到作业控制块JCB？其中包含了那些内容？答：P85。4 在作业调度中如何决定接纳多少个作业和接纳哪些作业？ 答：P85。5 试说明低级调度的主要功能？答：P86。缩略成百字左右的答案即可。6 在抢占式调度中，抢占的主要原则是什么？答：P87的三条原则。7. 选择调度方式和调度算法时，应遵循的准则是什么?答：P90-91a 面向用户的准则：周转时间短，响应时间快，截止时间的保证，以及优先权准则.B 面向系统的准则：系统吞吐量高，处理机利用率好，各类资源的平衡利用. 8 在批处理系统、分时系统、实时系统中，各采用哪几种调度算法？答：批处理系统适合采用动态优先权的抢占式或非抢占式算法。分时系统

5、本身就是抢占式的（时间片一到即切换进程），结合动态优先权就更好了。这道题需要对3.3小节的各种算法有深入了解。比如：1) 什么是抢占式或非强占式？2) 什么是动态优先级和静态优先级？3) 短作业优先算法是否含有优先级？是否是抢占式的？4) 分时系统是否抢占式？5) 哪些算法会造成进程饥饿？为什么？6) 带优先级（静态或动态）的算法一定是抢占式的吗？本题对实时调度算法不做要求。9 何为静态和动态优先级？确定静态优先级的依据是什么？答：P93。“2优先权的类型”。10 试比较FCFS和SPF两种算法答：简单的说，FCFS公平，无进程饥饿，但调度性能不好。SPF正相反。11 时间片轮转法中，应如何确

6、定时间片的大小？答：P95。12 试举一个例子说明通常的优先级调度算法不适合于实时系统？答：优先级调度算法即可以是抢占式的，也可以是非抢占式的。实时系统的进程调度是很复杂的，比如进程A需要10ms内完成，当进行到5 ms，来了一个优先级更高的需要2 ms内完成的进程B，如B抢占A，则B完成后A无法按时完成；如B不抢占A，则A完成后B无法按时完成。13. 为什么说多级反馈队列能较好地满足各种用户的需要?答：P9714 为什么在实时系统中，要求系统（尤其是CPU）有较强的处理能力？答:P98“2系统处理能力强”。实际上有些实时系统CPU处理能力并不强，比如一些嵌入式实时系统，这就要求系统尽量少做一

7、些并发计算任务，留出足够冗余处理实时任务。15 按调度方式可将实时调度算法分为哪几种？答：P99-10016 什么是最早截止时间优先调度算法，请举例说明之17 什么是最低松弛度优先调度算法，请举例说明之答：P100-102。考研的同学概念上了解一下即可。 最早截止时间优先调度算法：任务要求的截止时间越早，其优先级就越高。最低松弛度优先调度算法：任务的紧急程度越高，其优先级就越高。18 何谓死锁?产生死锁的原因和必要条件是什么?答：死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进;产生死锁的原因有二，一是竞争资源，二是进程推进顺序非法；产生必要条件是: 互

8、斥条件，请求和保持条件，不剥夺条件和环路等待条件。这四个必要条件必须同时满足，才有死锁的可能。 19 在解决死锁问题的几个方法中，哪种方法最容易实现?哪种方法使资源的利用率最高?a 解决死锁可归纳为四种方法: 预防死锁，避免死锁，检测死锁和解除死锁；b 其中，预防死锁的“摈弃环路”是最容易实现的，系统开销也小；见P107。c 避免死锁（银行家算法）使资源的利用率最高（应该是系统开销最大）。 20 请详细说明可通过哪些途径预防死锁?答:P107a. 摈弃请求和保持条件,就是如果系统有足够的资源，便一次性地把进程所需的所有资源分配给它；b. 摈弃不剥夺条件，就是已经保持了资源的进程，当它提出新的资

9、源请求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请；c. 摈弃环路等待条件，就是将所有资源按类型排序标号，所有进程对资源的请求必须严格按序号递增的次序提出. 21在教材银行家算法的例子中，如果P0发出的请求向量由Request0(0,2,0)改为Request0(0,1,0),问系统可否将资源分配给它?答：可以。可以找到一个安全序列P1,P4,P3,P2,P0,或P1,P4,P3,P0,P2 。22 在银行家算法中，若出现下列的资源分配情况：试问：AllocationNeedAvailableP00 0 3 20 0 1 21 6 2 2P11 0 0 01 7

10、5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6(1)该状态是否安全?(2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？【注】期末考试不会出这道题的原题，但很可能出一比这道题简单的相同类型题目答：这是5个进程，对4种资源的分配。Allocation是各进程已获得的资源，Need是尚缺的资源，Available是系统剩余的资源。银行家算法分为两部分：第一部分是资源预分配算法（P109“2银行家算法”），即对某进程的一个资源请求，先进行模拟分配，然后运行银行家算法的第二部分，找出是否存在安全序列。第二部分是安全

11、性算法（P109“3安全性算法”）,找出当前系统状态是否有安全序列。(1)该状态是否安全? 只需运行银行家算法的第二部分即可。我的解法看上去与教材不一样，实际是一样的。Available（1622）P0 Need(0012)，分配/去配后：AllocationNeedAvailableP01 6 5 4P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6Available（1 6 5 4）=P3 Need(0652)，分配/去配后：AllocationNeedAvailableP01 9 8 6P11 0 0 01 7

12、 5 0P21 3 5 42 3 5 6P3P40 0 1 40 6 5 6Available（1 9 8 6）P1 Need(1750)，分配/去配后：AllocationNeedAvailableP02 9 8 6P1P21 3 5 42 3 5 6P3P40 0 1 40 6 5 6Available（2 9 8 6）P2 Need(2356)，分配/去配后：AllocationNeedAvailableP03 12 13 10P1P2P3P40 0 1 40 6 5 6Available（3 12 13 10）P4 Need(0656)，分配/去配后：AllocationNeedAva

13、ilableP03 12 14 14P1P2P3P4 最后得出安全序列为P0,P3,P1,P2,P4(应该还有其他安全序列)(2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？AllocationNeedAvailableP00 0 3 20 0 1 21 6 2 2P11 0 0 01 7 5 0P21 3 5 4 2 3 5 6 P30 3 3 20 6 5 2P40 0 1 40 6 5 6首先要运行银行家算法的第一部分，进行预分配（模拟分配）。预分配后系统状态如下：AllocationNeedAvailableP00 0 3 20 0 1 20 4 0

14、0P11 0 0 01 7 5 0P23 5 7 6 1 1 3 4 P30 3 3 20 6 5 2P40 0 1 40 6 5 6然后运行银行家算法的第二部分，找安全序列。很显然，Available（0400）不能满足任何一个进程的Need，不存在安全状态。所以，P2提出的请求Request(1,2,2,2)现在不能分配，要等待一段时间后，系统状态发生变化后，再提请求，再进行银行家算法的预分配和查找安全序列。补充习题1 （该题对考研的同学很重要，要求你能画出与题目答案相似的图表）某就绪队列中已有以下进程等待调度：Process CPU阵发期 优先级（数越小优先级越高）P1 24 3 P2

15、3 2 P3 3 1（1）在不考虑这些进程到达就绪队列时间先后的前提下（假定它们同时到达），分别画出及计算： 短作业优先算法、循环轮转算法（时间片为4）、静态优先数算法的甘特图及平均等待时间。注：周转时间=进程在就绪队列中的时间+CPU阵发期 CPU阵发期=进程占用CPU的时间等待时间=周转时间-CPU阵发期甘特图是一种常用图表，横轴是时间，纵轴是任务（2）上述三种算法，哪种算法实用性最差？简单说明理由。（3）上述三种算法，哪些算法肯定是抢占式的？哪些算法既可以是抢占式的也可以是非抢占式的？答：（1）短作业优先算法P2P3P10 3 6 30 Waiting time for P1 = 6;

16、P2 = 0; P3 = 3Average waiting time: (6 + 0 + 3)/3 = 3循环轮转算法（时间片为4）P1P2P3P1P1P1P1P10 4 7 10 14 18 22 26 30 The waiting time is : P1=30-24=6; P2=7-3=4; P3=10-3=7The average waiting time is (6+4+7)/3=5.66静态优先数算法P3P2P1 0 3 6 Waiting time for P1 = 6; P2 = 3; P3 =0Average waiting time: (6 + 3 + 0)/3 = 3（2）短作业优先算法实用性最差，因为实际中很难知道进程的CPU阵发时间。（3）循环轮转算法肯定是抢占式的，其它两种算法既可以是抢占式的也可以是非抢占式的。补充习题2. 何谓银行家算法的保守性? 举例说明之。答：银行家算法的保守性是指银行家算法基于死锁的必要条件而非充分条件，如不存在安全序列也不一定死锁。它只给出了进程需要资源的最大量，而所需资源的