Coend; End;
6．售票厅问题解答如下：
(1) 定义一信号量S，初始值为20。
S>0 S的值表示可继续进入售票厅的人数 S=0 表示售票厅中已有20名顾客
S<0 |S|的值为等待进入售票厅中的人数 (2) 上框为P(S)
下框为V(S) (3) S的最大值为20
S的最小值为20-N，N为某一时刻需要进入售票厅的最大人数。
7．进程间存在着2种相互制约的关系：直接制约关系（即同步问题）和间接制约关系（即互斥问题）。同步问题是存在逻辑关系的进程之间相互等待所产生的制约关系，互斥问题是相互无逻辑关系的进程间竞争使用相同资源所发生的制约关系。
(1) 属于互斥关系，因为书的个数是有限的，一本书只能借给一个同学； (2) 属于互斥关系，篮球只有一个，两队都要争夺；
(3) 属于同步关系，各道工序的开始都依赖前道工序的完成；
(4) 属于同步关系，商品没生产出来，消费无法进行，商品未消费完，生产也无须进行。 8．因为P1和P2是两个并发进程，所以进程调度程序调度P1和P2的顺序是不确定的。 这里不妨假设P1先执行。进程P1执行到语句P(S2)时，S2＝-1，进程P1阻塞。此时，y=3，z=4。当进程调度程序调度到进程P2时，由于进程P1已执行了V(S1)，进程P2在执行P(S1)时并未阻塞而继续执行，当执行到V(S2)时，将P1唤醒，然后执行最后一个语句z:=x+z，此时x=5，z=9。当进程P1再次被调度时，继续执行P1的最后一个语句，此时y=12,最终结果是：x=5，y=12，z=9。
如果当P2进程执行到V(S2)时，将P1唤醒，然后P2进程被中断，此时x=5，y=3, z=4。P1进程开始执行然后执行最后一个语句y:=z+y，此时x=5，y=3,z=7。然后P2进程被调度，执行z:= x+z，此时x=5，y=3，z=12。
如果P2先执行，则执行结果与上面相同。 9．缓冲池各问题解答如下：. (1) 互斥信号量和初值
m(1)=1,m(2)=1,m(3)=1,m(4)=1 (2) 同步信号量
full(i) 表示buffer(i)是否有数据；
初值为 full(1)=0, full (2)=1, full (3)=0, full (4)=2；
empty(i)表示buffer(i)是否有空间；
初值为empty(1)=3, empty (2)=1, empty (3)=3, empty (4)=0 （3）进程程序 process Proc(i) { p(empty(i))；
p(full((i-1)mod4)+1))； p(m(i))；
p(m(full((i-1)mod4)+1))； move； v(m(i))；
v(m(full((i-1)mod4)+1)); v(full(i));
v(empty((i-1)mod4)+1));
}
- 21 -
第四章 调度与死锁
4.3 习题
4.3.1 选择最合适的答案
1．某系统采用了银行家算法，则下列叙述正确的是（ ）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁
2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（ ）。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（ ）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法
4．在下列选项中，属于预防死锁的方法是（ ）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法
5．在下列选项中，属于检测死锁的方法是（ ）。 A.银行家算法 B.消进程法
C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（ ）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（ ）。
A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法
8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（ ）相同。
A.先来先服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.长作业优先调度算法 9．作业从后备作业到被调度程序选中的时间称为（ ）。 A.周转时间 B.响应时间 C.等待调度时间 D.运行时间
10．资源静态分配法可以预防死锁的发生，它们使死锁四个条件中的（ ）不成立。 A.互斥条件 B.请求和保持条件 C.不可剥夺条件 D.环路等待条件
4.3.2 选择所有正确答案
1．下列选项中，（ ）可能是非抢占方式进程调度中引起调度的原因。 A.当前的运行进程调用阻塞原语而进入阻塞状态 B.当前的运行进程提出申请I/O而阻塞
C.有更高优先级的进程到达而从执行状态变为就绪状态 D.正在执行的进程执行了P原语操作，由于资源不足而阻塞
2．选择排队作业中等待时间最长的作业被优先调度，该调度算法不可能是（ ）。
- 22 -
A.先来先服务调度算法 B.高响应比优先调度算法 C.优先权调度算法 D.短作业优先调度算法
3．作业控制块JCB连成一串而形成的一个排队队列，该队列称为（ ）。 A挂起队列 B.阻塞队列 C.就绪队列 D.后备队列
4．下列哪个选项描述的时间属于响应时间的一部分（ ）。 A.处理机对请求信息进行处理的时间
B.从键盘输入的请求信息传送到处理机的时间 C.所形成的响应回送到终端显示器的时间 D.用户查看响应回送到的信息
5．下列四个选项描述的时间组成了周转时间，其中可能发生多次的是（ ）。 A.等待I/O操作完成的时间
B.作业在外存后备队列上等待作业调度的时间 C.进程在CPU上的执行时间
D.进程在就绪队列上等待进程调度的时间
6．下面列出的是选择调度方式和算法的4个面向用户的准则。其中，不完全适用于实时系统的准则是（ ）。
A.优先权准则 B.响应时间快 C.截止时间的保证 D.周转时间短
7．下面列出了选择调度方式和算法的4个准则。其中，对批处理、分时、实时系统都
可以采用的是（ ）。
A.周转时间短 B.响应时间快 C.截止时间的保证 D.优先权准则 8．下列选项中，（ ）是分时系统中确定时间片大小需要考虑的因素。 A.各类资源的平衡利用 B.就绪队列中进程的数目 C.系统的处理能力 D.系统对响应时间的要求 9．下面列出的选项中，属于可剥夺性资源的有（ ）。 A.CPU B.内存 C.磁盘 D.磁带机
10．在多级队列调度和多级反馈队列调度的叙述中，正确的是（ ）。
A.多级反馈队列调度中就绪队列的设置不是象多级队列调度一样按作业性质划分，而是按时间片的大小划分
B.多级队列调度用到优先权，而多级反馈队列调度中没有用到优先权
C.多级队列调度中的进程固定在某一个队列中，而多级反馈队列调度中的进程不固定
D.多级队列调度中每个队列按作业性质不同而采用不同的调度算法，而多级反馈队列调度中除了个别队列外，均采用相同的调度算法
4.3.3 判断正误，简要说明理由
1．作业调度能够使作业获得CPU。
2．在多道程序系统中，系统的现有空闲可用资源能否满足一个后备作业J的资源要求，是选择作业J进入内存的必要条件。
3．短作业（进程）优先调度算法具有最短的平均周转时间，因此这种算法是最好的算法。
4．在优先权调度算法中确定静态优先权时，一般说，计算进程的优先权要高于磁盘I/O进程的优先权。
5．摒弃不可剥夺条件的方法可用于预防多个打印进程死锁的发生。
6．操作系统处理死锁，只要采用预防、解除、检测、避免之中的一种就足够了。 7．如果系统在所有进程运行前，一次性地将其在整个运行过程所需的全部资源分配给进程，即所谓“静态分配”法，是可以预防死锁发生的。
8．多个进程竞争比进程数目少的资源时就可能产生死锁，而当资源数目大于进程数目
- 23 -
时就一定不会发生死锁。
9．在银行家算法中，对某时刻的资源分配情况进行安全分析，如果该时刻状态是安全的，则存在一个安全序列，且这个安全序列是唯一的。
10．进程调度算法各种各样，但是如果选择不当，就会造成死锁。
4.3.4 简答题
1．高级调度和低级调度的主要任务是什么？为什么要引入中级调度？ 2．在作业调度中需作出哪些决定？ 3．在剥夺调度中，有哪些剥夺原则？
4．在OS中引起进程调度的主要因素有哪些？
5．在选择调度方式和调度算法时，应遵循的原则是什么？
6．在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？ 7．为什么说多级反馈队列能较好地满足各种用户的需要？
8．在多用户分时系统中，时间片轮转调度的算法在确定时间片的大小时，应考虑哪些因素？
9．为实现实时调度，对实时系统提出了哪些要求？
10．目前常用的调度方式和算法，能否应用到实时系统中？
11．在多处理机系统中，比较有代表性的线程调度方式有哪几种？ 12．试比较自调度和成组调度？
13．在OS/2中采用哪种调度方式和调度算法？
14．何为死锁？产生死锁的原因和必要条件是什么？ 15．在解决死锁问题的几个方法中，哪种方法最容易实现？哪种方法使资源的利用率最高？
16．请详细说明可通过哪些途径预防死锁？
17．在银行家算法的例子中，如果P0发出的请求向量由Request0(0,2,0)改为Request0(0,1,0)，问系统可否将资源分配给它？
4.4 习题解答要点
4.4.1 选择最合适的答案
1.B 2.B 3.B 4.D 5.D 6.A
7.D 8.A
9.C 10.B
4.4.2 选择所有正确答案
1.ABD 2.BCD 3.D 4.ABC 5.ACD 6.AD 7.D 8.BCD 9.ABC 10.ACD
4.4.4 简答题
1． 错误
作业调度是高级调度。它只能使某作业获得使用CPU的资格。而只有进程调度或线程调度才能使作业真正获得CPU。
2． 错误
多道系统中的资源分配有两种方法：
(1) 静态分配：作业调度的功能之一是审查系统能否满足用户作业的资源要求；之二是按照一定的算法选取作业。
(2) 动态分配：进程所需的资源是在运行中分配的，作业调度并不考虑当前空闲的资源量，只是按照一定的算法选取作业。
3． 错误
前半句话讲的正确，但由此说短作业（进程）优先调度算法是最好的，就不正确了。因为一个算法的好坏要看其是否适于系统的需要而判定。
4． 错误
因为磁盘I/O进程属于系统进程。而系统在确定进程的静态优先权时遵循的原则是：系
- 24 -
统进程的优先权高于一般用户进程的优先权（除非用户的进程特别紧迫或重要）
5． 错误
因为摒弃不剥夺条件的方法可预防死锁的发生。 6． 错误
因为，操作系统要兼顾资源的使用效率和安全性两个方面，常见的是，将预防、解除、检测、避免四种处理混合起来使用。举例来说，只有检测死锁而无解除死锁，检测出死锁又有什么用呢？
7． 正确
因为资源的“静态分配”方法，可以摒弃“请求和保持”条件，是可以预防死锁的。 8． 错误
进程是否发生死锁，需要考虑每个进程申请资源的数目、所申请资源的种类、进程推进情况等因素。不能简单地比较进程数目和资源数目就来确定是否死锁。
9． 错误
系统在调用银行家算法进行安全检查时，只要找到一个安全序列就可断定系统是安全的。但安全序列可能不止一个，有的情况下可能是只有一个，有的情况下可能有2个或者更多。
10． 错误
如果进程调度算法选择不当，会造成某些进程的长期等待。我们将这种进程称为“饥饿”进程（长期“饥饿”的极端情况是“饿死”）。“饿死”和“死锁”具有完全不同的含义。
4.3.4 简答题
1．高级调度和低级调度的主要任务以及引入中级调度原因如下：
(1) 高级调度又称为作业调度。它是批处理系统中使用的一种调度。其主要任务是，按照某种算法从外存的后备队列上选择一个或多个作业调入内存，并为它们创建进程、分配必要的资源，然后再将创建的进程控制块挂入就绪队列上。
(2) 低级调度又称进程调度。它是距离硬件最近的一级调度。其主要任务是，按照某种算法从就绪队列上选择一个（或多个）进程，使其获得CPU。
(3) 引入中级调度的目的是为了提高内存利用率和系统吞吐量。其功能是，让那些暂时不能运行的进程不再占用宝贵的内存资源，而是调出到外存上等待。此时的进程状态为挂起状态。当这些进程重新具备运行条件且内存空闲时，由中级调度选择一部分挂起状态的进程调入内存，将其状态变为内存就绪状态。
2．在作业调度中需作出的决定如下：
(1) 作业调度需要按照多道程序度（即，最大道数）决定一次接纳多少作业进入内存。如果太少将导致系统资源利用率低，且系统吞吐量低；太多将导致内存空间紧张，系统服务质量下降，使作业运行周期过长。
(2) 作业调度需要决定接纳哪些作业进入内存。常用的算法是，先来先服务，短作业优先，最高优先级调度、响应比高者优先等。
3．在剥夺进程调度中，剥夺原则如下：
(1) 时间片原则。在轮转算法中，CPU轮流为诸多进程服务，每个进程运行完自己的时间片后，系统就将它的CPU剥夺过来，交给下一个进程使用。
(2) 优先级原则。为紧迫的作业赋予较高的优先级，这种作业到达系统，或者由阻塞状态被唤醒后，若其优先级高于当前运行的进程的优先级，可以剥夺其CPU。
(3) 短作业（进程）优先原则。若一个作业（进程）到达系统，其运行长度比当前运行的进程长度明显的短，则剥夺它的CPU。
4．引起进程调度的主要因素主要有： (1) 一个进程运行完毕；
(2) 一个正在运行的进程被阻塞；
(3) 在抢占式调度中，一个高优先级的进程被创建；
(4) 在抢占式调度中，一个高优先级进程由阻塞被唤醒； (5) 在轮转式调度中，正在运行的进程运行完一个时间片。 5．在选择调度方式和调度算法时，应遵循的原则如下：
- 25 -