操作系统第3章练习题

1、第3章 处理机调度与死锁3.1 典型例题解析【例1】（1）3个进程共享4个同种类型的资源，每个进程最大需要2个资源，请问系统是否会因为竞争该资源而死锁？（2）n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n。说明该系统不会因竞争该类资源而阻塞。（3）在（2）中，如果没有“每个进程都需要用该类资源”的限制，情况又会如何？（西北工业大学2000年考题）答：（1）该系统不会因为竞争该类资源而死锁。因为，必有一个进程可获得2个资源，故能顺利完成，并释放出其所占用的2个资源给其他进程使用，使它们也顺利完成。（2）用Max(i)表示第i个进程的最大资源需

2、求量，need（i）表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：need（i）0(对所有的i)max(1)+max(i)+max(n) m+n如果在这个系统中发生了死锁，则意味着已有一个以上的进程因申请不到该类资源而无限阻塞，而m个资源应该全部分配出去，即alloc(1)+alloc(i)+alloc(n)=m 因此need(1)+need(i)+need(n)=max(1)+max(i)+max(n)-alloc(1)+alloc(i)+alloc(n)m+n-m即need(1)+need(i)+need(n)n这样，至少必须存在一个进程，

3、其need(i)0，这显然与题意不符，所以该系统不可能因竞争该类资源而进入死锁状态。（3）此时系统可能发生死锁，如n=4,m=3时，若P1的Max为0，而其余三个进程的Max都为2，则仍然满足最大需求量之和（即6）小于m+n（即7）的要求，但当除P1以外的其余三个进程各得到一个资源时，这三个进程将进入死锁状态。【例2】设系统中有3种类型的资源A、B、C和5个进程P0、P1、P2、P3、P4，A资源的数量为10，B资源的数量为5，C资源的数量为7。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。MaxAllocationNeedAvailableABCABCABCABCP0P1

4、P2P3P4753010743332322200122902302600222211011433002431（1）T0时刻是否为安全状态？若是，请给出安全序列。（2）在T0时刻若进程P1发出资源请求Request（1，0，2），是否能够实施资源分配？（3）在的基础上P4发出资源请求Request（3，3，0），是否能够实施资源分配？（4）在的基础上P0发出资源请求Request（0，2，0），是否能够实施资源分配?答：(1) 利用银行家算法对T0时刻的资源分配情况进行分析，可得此时刻的安全性分析情况:WorkNeedAllocationWork+AllocationFinishABCABCAB

5、CABCP1332122200532TrueP3532011211743TrueP4743431002745TrueP27456003021047TrueP010477430101057True可知，在T0时刻存在着一个安全序列P1、P3、P4、P2、P0，故系统是安全的。（2）P1请求资源Request（1，0，2），系统按银行家算法进行检查：Request（1，0，2）Need（1，2，2）Request（1，0，2）Available（3，3，2）系统试探分配，修改相应的向量，形成的资源变化情况如下表所示：MaxAllocationNeedAvailableABCABCABCABCP07

6、53010743230P1322302020P2902302600P3222211011P4433002431在利用安全性算法检查此时系统是否安全，如下表所示：WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532TrueP3532011211743TrueP4743431002745TrueP0745743010755TrueP27556003021057True由安全性算法检查可知，可以找到一个安全序列P1、P3、P4、P0、P2。因此，系统是安全的，可以立即把P1所申请的资源分配给它。（3）P4发出资源请求Req

7、uest（3，0，0），系统按照银行家算法进行检查：Request（3，3，0）Need（4，3，1）Request（3，3，0）Available（2，3，0），所以让P4等待。（4）P0发出资源请求Request（0，2，0），系统按照银行家算法进行检查：Request（0，2，0）Need（7，4，3）Request（0，2，0）Available（2，3，0）系统试探分配，修改相应的向量，形成的资源变化情况如下表所示：AllocationNeedAvailableABCABCABCP0030723210P1302020P2302600P3211011P4002431进行安全性检查，可用

8、资源Available（2，1，0）已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。3.2 练习题一、 单项选择题1. 任何时刻总是让具有最高优先数的进程占用处理器，此时采用的进程调度算法是（）。A.非抢占式的优先数调度算法B.时间片轮转调度算法C.先来先服务调度算法D.抢占式的优先数调度算法2. 抢占式的优先数调度算法在（）中很有用。A.网络操作系统B.分布式系统C.批处理系统D.实时系统3. 下列算法中，（）只能采用非抢占调度方式，（）只能采用抢占调度方式，而其余的算法既可采用抢占方式，也可采用非抢占方式。A.高优先权优先法B.时间片轮转法C.FCFS调度算法D.短作业

9、优先算法4. 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。A.时间片轮转调度算法B.短进程优先调度算法 C.先来先服务调度算法D.高响应比优先调度算法 5. 进程调度的关键问题是（ ）A.时间片大小B.进程调度算法C.CPU速度D.内存空间利用率6. 下列选项中，降低进程优先权级的合理时机是（）。A.进程的时间片用完B.进程刚完成I/O，进入就绪队列C.进程长期处于就绪队列中D.进程从就绪状态转为运行态7. 采用时间片轮转调度算法是为了（）A.多个终端用户能得到系统的及时响应B.先来先服务C.CPU最短的进程先执行D.优先级高的进程能得到及时调度8. 下面关于优先权大小的叙述中

10、正确的是（）。A.用户进程的优先权，应高于系统进程的优先权B.在动态优先权中，随着作业的等待时间的增加，其优先权将随之增加C.资源要求多的作业，其优先权应高于资源要求少的作业D.长作业的优先权，应高于短作业的优先权9. 作业调度算法的选择常考虑的因素之一是使系统有最高的吞吐量，为此应（）。A.不让处理机空闲B.能够处理尽可能多的作业C.使用户们都满意D.不使磁头过于复杂10. 在各种作业调度算法中，若所有作业同时到达，则平均等待时间最短的算法是（）。A.先来先服务B.高优先权优先C.短作业优先D.高响应比优先11. 作业调度程序从（）队列中选取适当的作业投入运行。A.就绪 B.提交 C.运行

11、D.后备12. 在批处理系统中，用户的作业是由（）组成的。A.程序 B.程序+数据+作业说明书 C.程序+作业说明书D.程序+数据13. 假设下述四个作业同时到达，当使用最高优先数优先调度算法时，作业的平均周转时间为（）。作业所需运行时间优先数124259381438A. 4.5B. 10.5C. 4.75D. 10.2514. 一作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，其响应比是（）。A. 2B. 1C. 3D. 0.515. 下面哪个算法适用于分时系统中的进程调度（）。A.FCFSB.时间片轮转C.CPU为主的优先D.动态优先数法16. 在多道批处理系统中，

12、为充分利用各种资源，运行的程序应具备的条件是（）。A.适应于内存分配的B.计算量大的 C.I/O量大的D.计算型和I/O型均衡的17. 下面的叙述中正确的是（）。A.安全状态是没有死锁的状态，非安全状态是有死锁的状态。 B.安全状态是可能有死锁的状态，非安全状态也是可能有死锁的状态C.安全状态是可能没有死锁的状态，非安全状态是有死锁的状态D.安全状态是没有死锁的状态，非安全状态是可能有死锁的状态18. 除了进程竞争资源，因为资源不足可能出现死锁以外，不适当的（）也可能产生死锁。A.进程优先权B.资源的线性分配C.进程推进顺序D.分配队列优先权19. 发生死锁的必要条件有四个，要防止死锁的发生，

13、可以破坏这四个必要条件，但破坏（）条件是不太实际的。A.互斥B.请求和保持C.不剥夺D.环路等待20. 除了可以采用资源剥夺法解除死锁，还可以采用（）方法解除死锁。A.修改信号量 B.拒绝分配新的资源C.撤销进程 D.执行并行操作21. 资源的按序分配策略可以破坏（）条件。A.互斥 B.请求和保持C.不剥夺 D.环路等待22. 在（）的情况下，系统出现死锁。A.计算机系统发生了重大故障B.有多个阻塞的进程存在C.若干个进程因竞争资源而无休止地相互等待他方释放已占有的资源D.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数23. 某系统中有3个并发进程，都需要同类资源4个，试问该系统不

14、会发生死锁的最少资源数是（）。A. 9 B. 10C. 11 D. 1224. 某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（）。A. 2 B. 3 C. 4 D. 5 解析：3k k4（n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n。则该系统不会因竞争该类资源而阻塞。）25. 银行家算法是一种（）算法。A.解除死锁 B.避免死锁C.预防死锁 D.检测死锁二、填空题1进程调度程序按_从_中选择一个进程; 从而使之占用处理器运行。2进程调度算法常用的有_、_ 、_ 、高优先权优

15、先等几种。3进程的调度方式有两种，一种是_，另一种是_。4在_调度算法中，按照进程进入就绪队列的先后顺序来分配处理机。5死锁是指在系统中的多个_无限期等待永远也不会发生的条件。6死锁产生的四个必要条件是_、_、_和_ 。7银行家算法中，当一个进程提出的资源请求将导致系统从_ 状态进入_状态时，系统就拒绝它的资源请求。8对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于_，破坏环路等待条件是属于_，而剥夺资源是_的基本方法。三、计算题1、有4个进程P1，P2，P3，P4，它们进入就绪队列的先后次序为P1、P2、P3、P4，它们的优先数和需要的处理器时间如下表所示。假

16、定这四个进程执行过程中不会发生等待事件，忽略进行调度等所花费的时间，从某个时刻开始进程调度，请回答下列问题：写出分别采用“先来先服务”调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及的平均等待时间；写出分别采用“非抢占式的优先数”（固定优先数）调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间；写出分别采用“时间片轮转”（时间片大小为5）调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间。进 程处理器时间优先数P183P261P3225P4442、在一个批处理单道系统中，采用响应比高者优先的作业调度算法。当一个作业进入系

17、统后就可以开始调度，假定作业都是仅计算，忽略调度花费的时间。现有三个作业，进入系统的时间和需要计算的时间如表所示：作业进入系统时间需要计算时间开始时间完成时间周转时间19:0060分钟29:1045分钟39:2525分钟（1）求出每个作业的开始时间、完成时间及周转时间并填入表中。（2）计算三个作业的平均周转时间应为多少？3、一系统具有150个存储单元，在T0时刻系统按下表所示分配给3个进程。T0时刻系统资源分配状态表进程Maximum demandCurrent allocationP17025P26040P36045对下列请求应用银行家算法分别分析判定是否安全？（1）第4个进程P4到达，最大

18、需求60个存储单元，当前请求分配25个单元。（2）第4个进程P4到达，最大需求50个存储单元，当前请求分配35个单元。如果是安全的，请给出一个可能的进程安全执行序列；如果是不是安全的，请说明原因。四、问答题1、何谓死锁？产生死锁的原因和必要条件是什么？2、下列程序执行结果中a=？为什么？a=55;pid=fork();if (pid= =0)a=99;exit(0);elsewait(NULL);printf(“a=%dn”,a);参考答案一、 单项选择题1-5: DD CB DB6-10: AABBC11-15: DBDCB16-20: DDCAC21-25: DCBCB二、填空题 1某种调度算法 就绪队列2先来先服务 短进程优先 时间片轮转调度算法3剥夺式 非剥夺式4先来先服务5进程6互斥 请求和保持 不剥夺 环路等待7安全状态 不安全状态8避免死锁 预防死锁 解除死锁三、计算题1、答：先来先服务算法选择进程的顺序依次为P1、P2、P3、P4。进程P1等待时间为0；进程P2等待时间为8；进程P3等待时间为8+6=14；进程P4等待时间为8+6+22=36。平均等待时间为（0+8+14+36）/4=14.5非抢占式的优先数算法选择进程的顺序依次为P3、P4、P1、P2。进程P1等待时间为4+22=26；进程P2等待时间为22