操作系统第3章练习题

第3章 处理机调度与死锁

3.1 典型例题解析

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

（2）用Max(i)表示第i个进程的最大资源需求量，need（i）表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知： need（i）>0(对所有的i)

max(1)+?max(i)+?+max(n)

need(1)+?need(i)+?+need(n)=max(1)+?max(i)+?+max(n)-alloc(1)+?alloc(i)+?+alloc(n)

need(1)+?need(i)+?+need(n)

这样，至少必须存在一个进程，其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时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。 P0 P1 P2 P3 P4 A 7 3 9 2 4 Max B 5 2 0 2 3 C 3 2 2 2 3 Allocation A B C 0 2 3 2 0 1 0 0 1 0 0 0 2 1 2 A 7 1 6 0 4 Need B 4 2 0 1 3 C 3 2 0 1 1 Available A B C 3 3 2 （1）T0时刻是否为安全状态？若是，请给出安全序列。

（2）在T0时刻若进程P1发出资源请求Request（1，0，2），是否能够实施资源分配？ （3）在②的基础上P4发出资源请求Request（3，3，0），是否能够实施资源分配？ （4）在③的基础上P0发出资源请求Request（0，2，0），是否能够实施资源分配?

答：(1) 利用银行家算法对T0时刻的资源分配情况进行分析，可得此时刻的安全性分析情

况: P1 P3 P4 P2 P0 Work A 3 5 7 7 10 B 3 3 4 4 4 C 2 2 3 5 7 A 1 0 4 6 7 Need B 2 1 3 0 4 C 2 1 1 0 3 Allocation A 2 2 0 3 0 B 0 1 0 0 1 C 0 1 2 2 0 Work+Allocation A 5 7 7 10 10 B 3 4 4 4 5 C 2 3 5 7 7 Finish True True True True True

可知，在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）

系统试探分配，修改相应的向量，形成的资源变化情况如下表所示：

P0 P1 P2 P3 P4 Max A 7 3 9 2 4 B 5 2 0 2 3 C 3 2 2 2 3 A 0 3 3 2 0 Allocation B 1 0 0 1 0 C 0 2 2 1 2 A 7 0 6 0 4 Need B 4 2 0 1 3 C 3 0 0 1 1 A 2 Available B 3 C 0

在利用安全性算法检查此时系统是否安全，如下表所示： P1 P3 P4 P0 P2 Work A 2 5 7 7 7 B 3 3 4 4 5 C 0 2 3 5 5 A 0 0 4 7 6 Need B 2 1 3 4 0 C 0 1 1 3 0 Allocation A 3 2 0 0 3 B 0 1 0 1 0 C 2 1 2 0 2 Work+Allocation A 5 7 7 7 10 B 3 4 4 5 5 C 2 3 5 5 7 Finish True True True True True

由安全性算法检查可知，可以找到一个安全序列{P1、P3、P4、P0、P2}。因此，系统是安全的，可以立即把P1所申请的资源分配给它。

（3）P4发出资源请求Request（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）

系统试探分配，修改相应的向量，形成的资源变化情况如下表所示：

P0 P1 P2 P3 P4 Allocation A 0 3 3 2 0 B 3 0 0 1 0 C 0 2 2 1 2 A 7 0 6 0 4 Need B 2 2 0 1 3 C 3 0 0 1 1 A 2 Available B 1 C 0

进行安全性检查，可用资源Available（2，1，0）已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

3.2 练习题

一、单项选择题

1. 任何时刻总是让具有最高优先数的进程占用处理器，此时采用的进程调度算法是（）。 A.非抢占式的优先数调度算法 B.时间片轮转调度算法 C.先来先服务调度算法 D.抢占式的优先数调度算法 2. 抢占式的优先数调度算法在（）中很有用。 A.网络操作系统 B.分布式系统 C.批处理系统 D.实时系统 3. 下列算法中，（）只能采用非抢占调度方式，（）只能采用抢占调度方式，而其余的算法既可采用抢占方式，也可采用非抢占方式。 A.高优先权优先法 B.时间片轮转法 C.FCFS调度算法 D.短作业优先算法

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. 下面关于优先权大小的叙述中正确的是（）。 A.用户进程的优先权，应高于系统进程的优先权

B.在动态优先权中，随着作业的等待时间的增加，其优先权将随之增加 C.资源要求多的作业，其优先权应高于资源要求少的作业 D.长作业的优先权，应高于短作业的优先权

9. 作业调度算法的选择常考虑的因素之一是使系统有最高的吞吐量，为此应（）。 A.不让处理机空闲 B.能够处理尽可能多的作业

C.使用户们都满意 D.不使磁头过于复杂

10. 在各种作业调度算法中，若所有作业同时到达，则平均等待时间最短的算法是（）。 A.先来先服务 B.高优先权优先 C.短作业优先 D.高响应比优先 11. 作业调度程序从（）队列中选取适当的作业投入运行。 A.就绪 B.提交 C.运行 D.后备 12. 在批处理系统中，用户的作业是由（）组成的。

A.程序 B.程序+数据+作业说明书 C.程序+作业说明书 D.程序+数据

13. 假设下述四个作业同时到达，当使用最高优先数优先调度算法时，作业的平均周转时间为（）。

作业 1 2 3 4 所需运行时间 2 5 8 3 优先数 4 9 1 8 A. 4.5 B. 10.5 C. 4.75 D. 10.25 14. 一作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，其响应比是（）。 A. 2 B. 1 C. 3 D. 0.5 15. 下面哪个算法适用于分时系统中的进程调度（）。 A.FCFS B.时间片轮转 C.CPU为主的优先 D.动态优先数法 16. 在多道批处理系统中，为充分利用各种资源，运行的程序应具备的条件是（）。 A.适应于内存分配的 B.计算量大的 C.I/O量大的 D.计算型和I/O型均衡的 17. 下面的叙述中正确的是（）。

A.安全状态是没有死锁的状态，非安全状态是有死锁的状态。

B.安全状态是可能有死锁的状态，非安全状态也是可能有死锁的状态 C.安全状态是可能没有死锁的状态，非安全状态是有死锁的状态 D.安全状态是没有死锁的状态，非安全状态是可能有死锁的状态

18. 除了进程竞争资源，因为资源不足可能出现死锁以外，不适当的（）也可能产生死锁。 A.进程优先权 B.资源的线性分配 C.进程推进顺序 D.分配队列优先权

19. 发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏（）条件是不太实际的。 A.互斥 B.请求和保持 C.不剥夺 D.环路等待 20. 除了可以采用资源剥夺法解除死锁，还可以采用（）方法解除死锁。 A.修改信号量 B.拒绝分配新的资源 C.撤销进程 D.执行并行操作 21. 资源的按序分配策略可以破坏（）条件。 A.互斥 B.请求和保持 C.不剥夺 D.环路等待 22. 在（）的情况下，系统出现死锁。 A.计算机系统发生了重大故障 B.有多个阻塞的进程存在

C.若干个进程因竞争资源而无休止地相互等待他方释放已占有的资源 D.资源数大大小于进程数或进程同时申请的资源数大大超过资源总数

23. 某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是（）。 A. 9 B. 10 C. 11 D. 12

24. 某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（）。 A. 2 B. 3 C. 4 D. 5

解析：3k<8+k => k<4（n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n。则该系统不会因竞争该类资源而阻塞。） 25. 银行家算法是一种（）算法。 A.解除死锁 B.避免死锁 C.预防死锁 D.检测死锁

二、填空题

1．进程调度程序按____________从____________中选择一个进程; 从而使之占用处理器运行。

2．进程调度算法常用的有____________、____________ 、____________ 、高优先权优先等几种。

3．进程的调度方式有两种，一种是____________，另一种是____________。

4．在____________调度算法中，按照进程进入就绪队列的先后顺序来分配处理机。 5．死锁是指在系统中的多个___________无限期等待永远也不会发生的条件。

6．死锁产生的四个必要条件是____________、____________、____________和____________ 。

7．银行家算法中，当一个进程提出的资源请求将导致系统从____________ 状态进入____________状态时，系统就拒绝它的资源请求。

8．对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于____________，破坏环路等待条件是属于____________，而剥夺资源是____________的基本方法。

三、计算题

1、有4个进程P1，P2，P3，P4，它们进入就绪队列的先后次序为P1、P2、P3、P4，它们的优先数和需要的处理器时间如下表所示。假定这四个进程执行过程中不会发生等待事件，忽略进行调度等所花费的时间，从某个时刻开始进程调度，请回答下列问题：

①写出分别采用“先来先服务”调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及的平均等待时间；

②写出分别采用“非抢占式的优先数”（固定优先数）调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间；

③写出分别采用“时间片轮转”（时间片大小为5）调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间。

进 程 P1 P2 P3 P4 处理器时间 8 6 22 4 优先数 3 1 5 4

本文来源：https://www.bwwdw.com/article/gcrd.html