操作系统第6章36 本单元作业二参考答案.docx

操作系统第6章36 本单元作业二参考答案.docx

《操作系统第6章36 本单元作业二参考答案.docx》由会员分享，可在线阅读，更多相关《操作系统第6章36 本单元作业二参考答案.docx（16页珍藏版）》请在冰点文库上搜索。

操作系统第6章36本单元作业二参考答案

单元六课后作业答案

一、填空

1．信号量的物理意义是当信号量值大于零时表示可分配资源的个数；当信号量值小于零时，其绝对值为等待使用该资源的进程的个数。

2．所谓临界区是指进程程序中需要互斥执行的程序段。

3．用P、V操作管理临界区时，一个进程在进入临界区前应对信号量执行P操作，退出临界区时应对信号量执行V操作。

4．有m个进程共享一个临界资源。

若使用信号量机制实现对临界资源的互斥访问，则该信号量取值最大为1，最小为−（m−1）。

注意，无论有多少个进程，只要它们需要互斥访问同一个临界资源，那么管理该临界资源的信号量初值就是1。

当有一个进程进入临界区时，信号量的值就变为0。

随后再想进入的进程只能等待。

最多的情况是让一个进程进入后，其余（m−1）个进程都在等待进入。

于是这时信号量取到最小值：

−（m−1）。

5．对信号量S的P操作原语中，使进程进入相应信号量队列等待的条件是Vs<0。

6．死锁是指系统中多个进程无休止地等待永远不会发生的事件出现。

7．产生死锁的4个必要条件是互斥、非剥夺、部分分配和循环等待。

8．在银行家算法中，如果一个进程对资源提出的请求将会导致系统从安全的状态进入到不安全的状态时，就暂时拒绝这一请求。

9．信箱在逻辑上被分为信箱头和信箱体两部分。

10．在操作系统中进程间的通信可以分为低级通信与高级通信两种。

二、选择

1．P、V操作是A。

A．两条低级进程通信原语B．两条高级进程通信原语

C．两条系统调用命令D．两条特权指令

2．进程的并发执行是指若干个进程B。

A．共享系统资源B．在执行的时间上是重叠的

C．顺序执行D．相互制约

3．若信号量S初值为2，当前值为−1，则表示有B个进程在与S相关的队列上等待。

A．0B．1C．2D．3

4．用P、V操作管理相关进程的临界区时，信号量的初值应定义为C。

A．−1B．0C．1D．随意

5．用V操作唤醒一个等待进程时，被唤醒进程的状态变为B。

A．等待B．就绪C．运行D．完成

6．若两个并发进程相关临界区的互斥信号量MUTEX现在取值为0，则正确的描述应该是B。

A．没有进程进入临界区

B．有一个进程进入临界区

C．有一个进程进入临界区，另一个在等待进入临界区

D．不定

7．在系统中采用按序分配资源的策略，将破坏产生死锁的D条件。

A．互斥B．占有并等待C．不可抢夺D．循环等待

8．某系统中有3个并发进程，都需要4个同类资源。

试问该系统不会产生死锁的最少资源总数应该是B。

A．9B．10C．11D．12

9．银行家算法是一种A算法。

A．死锁避免B．死锁防止C．死锁检测D．死锁解除

10．信箱通信是进程间的一种B通信方式。

A．直接B．间接C．低级D．信号量

三、问答

1．试说出图6-13（即教材中第2章的图2-2）所给出的监视程序A和计数程序B之间体现出一种什么关系，是“互斥”还是“同步”？

为什么？

图6-13对两个程序的描述

答：

图6-13（即教材中第2章的图2-2）所给出的监视程序A和计数程序B之间体现出的是一种互斥关系，因为在监视程序A里，要对共享变量COUNT进行操作：

COUNT=COUNT+1;

在计数程序B里要对共享变量COUNT进行操作：

打印COUNT的值;

COUNT=0;

这两段程序是不能交叉进行的，不然就会出现与时间有关的错误。

2．模仿教材中的图6-4，画出COPY和PUT之间的直接依赖关系。

然后把两个图汇集在一起，体会它们三者之间正确的同步关系。

再模仿教材中的图6-8，能用信号量及P、V操作来正确处理GET、COPY和PUT三者之间的协同工作关系吗？

答：

图6-14给出了GET、COPY和PUT三者间正确的同步关系：

GET在向COPY发“可以拷贝”的消息后，要等待COPY发来“拷贝结束”的消息。

因为这个消息意味着输入缓冲区R已经被COPY腾空，GET可以再次向里面存放从文件F里取出的记录了；COPY在等到GET发来的“可以拷贝”的消息后，才能够把输入缓冲区R里的记录拷贝到输出缓冲区T中。

完成这个动作后，表示输入缓冲区R已经被COPY腾空，因此应该立即向GET发消息，告诉它输入缓冲区R又可以使用了。

随后，向PUT发送“可以打印”的消息，等待PUT发来“打印结束”的消息；PUT在等到COPY发来“可以打印”的消息后，才能够从输出缓冲区T里取出记录打印。

打印完毕后，向COPY发送“打印完毕”的消息。

这个消息意味着输出缓冲区T已经被PUT腾空，COPY又可以再次去等待GET发送的“可以拷贝”的消息，从输入缓冲区R里取出记录存入输出缓冲区T了。

图6-14GET、COPY和PUT三者间的工作关系

于是，GET、COPY和PUT三者间有4个同步问题：

在GET的标号为3的地方是一个同步点；在COPY的标号为1和5的地方是两个同步点；在PUT的标号为1的地方是一个同步点。

因此，共要设置4个同步信号量：

S1——控制COPY与GET取得同步，初值=0；

S2——控制GET与COPY取得同步，初值=0；

S3——控制PUT与COPY取得同步，初值=0；

S4——控制COPY与PUT取得同步，初值=0。

图6-15表述了用信号量及P、V操作来正确处理GET、COPY和PUT三者之间的协同工作关系。

图6-15用P、V操作保证GET、COPY和PUT三者的正确协作

3．在图6-16（a）（即教材中图6-8）GET里，是先安放V（S1），再安放P（S2）的。

能把它们两个的安放顺序颠倒过来变成图6-16（b）吗？

为什么？

图6-16安放V（S1）和P（S2）的两种方法

答：

图6-16（b）里是先安放P（S2）,再安放V（S1）。

这种安放顺序是不行的。

因为安放P（S2），表示要在此等待COPY发来的消息（即希望COPY执行V（S2）操作），在接到了COPY的消息后，才执行V（S1）（即向COPY发消息）。

但是，根据COPY的安排，不接到GET发来的消息（即执行P（S1）操作），是不会向COPY发消息的（即执行V（S2）操作）。

于是，GET和COPY就陷入了循环等待：

GET等待COPY发消息，COPY等待GET发消息。

产生两个死锁了。

4．进程A和B共享一个变量，因此在各自的程序里都有自己的临界区。

现在进程A在临界区里。

试问进程A的执行能够被别的进程打断吗？

能够被进程B打断吗（这里，“打断”的含义是调度新进程运行，使进程A暂停执行）？

答：

当进程A在自己的临界区里执行时，能够被别的进程打断，没有任何的限制。

当进程A在自己的临界区里执行时，也能够被进程B打断，不过这种打断是有限制的。

即当进程B执行到要求进入自己的临界区时，就会被阻塞。

这是因为在它打断进程A时，A正在临界区里还没有出来，既然A在临界区，B当然就无法进入自己的临界区。

5．信号量上的P、V操作只是对信号量的值进行加1或减1操作吗？

在信号量上还能够执行除P、V操作外的其他操作吗？

答：

根据信号量的定义可知，P、V操作并非只是对信号量进行减1或加1操作，更重要的是在减1或加1后，还要判断运算的结果。

对于P操作，判定后调用进程自己有可能继续运行，也可能阻塞等待。

对于V操作，判定后调用进程自己最后总是继续运行，但之前可能会唤醒在信号量队列上等待的进程。

在信号量上除了能执行P、V操作外，不能执行其他任何操作。

6．系统有输入机和打印机各一台，均采用P-V操作来实现分配和释放。

现在有两个进程都要使用它们。

这会发生死锁吗？

试说明理由。

答：

采用信号量上的P、V操作，只能正确地完成对设备的申请与释放，但不能控制进程对设备的申请、释放顺序。

因此，当进程申请和释放设备的顺序不当时，仍会发生死锁。

例如，进程A使用输入机和打印机的顺序是：

请求打印机（Ar1）→请求输入机（Ar2）→释放打印机（Ar3）→释放输入机（Ar4）

进程B使用输入机和打印机的顺序是：

请求输入机（Br1）→请求打印机（Br2）→释放输入机（Br3）→释放打印机（Br4）

其中圆括号里标注的字母，表示某进程对设备的某种使用。

例如，Ar1表示进程A请求打印机。

由于A和B都是进程，它们的执行可以交叉进行。

执行顺序：

Ar1→Ar2→Ar3→Ar4→Br1→Br2→Br3→Br4

或

Ar1→Ar2→Br1→Ar3→Ar4→Br2→Br3→Br4

都是合理的交叉。

但是，以Ar1→Br1开始的执行就无法再往下进行了。

因为进程A执行了Ar1，表明它占用了打印机。

接着进程B执行了Br1，表明它占用了输入机。

这样一来，不管后面是执行Ar2（进程A申请输入机）还是执行Br2（进程B申请打印机），都不可能得到满足，两个进程先后被阻塞：

进程A占据着打印机而等待输入机，进程B占据着输入机而等待打印机。

这就产生了死锁。

7．现有4个进程A、B、C、D，共享10个单位的某种资源。

基本数据如图6-17（即教材中的图6-28）所示。

试问如果进程D再多请求一个资源单位，所导致的是安全状态还是不安全状态？

如果是进程C提出同样的请求，情况又会是怎样呢？

答：

若进程D多请求一个资源，资源的使用情况如图6-18（a）所示。

这时，系统剩余1个资源，4个进程各自还需要的资源数是5、4、2、2，资源剩余数无法保证任何一个进程运行结束。

所以D多请求一个资源单位，会导致不安全状态。

若是进程C提出同样的请求，那么系统资源的使用情况如图6-18（b）所示。

这时，整个系统虽然也只剩余1个资源，但却能够保证4个进程都完成。

所以，C再多请求一个资源单位，系统将处于安全状态。

图6-17第7题的基本数据

图6-18不安全与安全状态示意图

8．假定图6-19（即教材中的图6-21）里的进程A申请最后一台磁带机，会引起死锁吗？

图6-19多种资源的银行家算法

答：

进程A申请了最后一台磁带机后，系统资源的使用情况由图6-19变为图6-20。

按照多种资源的银行家算法，这时系统资源的剩余数可以满足进程D的要求，于是系统资源剩余数矩阵A变为A[1121]；这样的剩余数，可以满足进程A的要求，于是系统资源剩余数矩阵A变为A[5132]；这样的剩余数，可以满足进程B、C、E三个进程中任何一个的需要，例如给E。

在E完成后，系统资源剩余数矩阵A仍为A[5132]；再给C，C完成后系统资源剩余数矩阵A变为A[6242]；再给B，B完成后系统资源剩余数矩阵A变为A[6342]，系统收回了所有资源。

由此可知，进程A申请最后一台磁带机，不会引起死锁。

9．一个计算机有6台磁带机，有n个进程竞争使用，每个进程最多需要两台。

那么n为多少时，系统才不存在死锁的危险？

答：

由于每个进程最多需要两台磁带机，考虑极端情况：

每个进程已经都申请了一台。

那么只要还有一台空闲，就可以保证所有进程都可以完成。

也就是说当有条件：

n+1=6（即n=5）时，系统就不存在死锁的危险。

图6-20进程A申请了最后一台磁带机后

10．考虑教材中的图6-16（d）。

如果进程C需要的是资源S，而不是资源R，这会引起死锁吗？

如果是既要求资源R又要求资源S，情况会怎样？

答：

这时的资源使用序列为：

（1）A申请R，C申请T，A申请S，C申请S，A释放R，A释放S；

（2）A申请R，C申请T，A申请S，C申请S，C申请R，A释放R，A释放S。

分别画出它们的资源分配图，可知，它们都不会引起死锁。

四、计算

1．在公共汽车上，司机和售票员的工作流程如图6-21（即教材上的图6-29）所示。

为了确保行车安全，试用信号量及其P、V操作来协调司机和售票员的工作。

图6-21司机与售票员

解：

从日常生活知识知道，司机和售票员之间的工作有如下的制约关系存在。

（1）司机必须在得到售票员的“关门完毕”的信号后，才能启动汽车。

这是一个司机要与售票员取得同步的问题。

（2）售票员必须在得到司机的“已经停车”的信号后，才能打开车门。

这是一个售票员要与司机取得同步的问题。

因此，为了确保行车安全，需要设置两个同步信号量：

S1——初值为0，控制司机与售票员取得同步；

S2——初值为0，控制售票员与司机取得同步。

于是，在加入了信号量上的P、V操作后，图6-21应该变为图6-22。

2．有一个阅览室共100个座位。

用一张表来管理它，每个表目记录座号以及读者姓名。

读者进入时要先在表上登记，退出时要注销登记。

试用信号量及其P、V操作来描述各个读者“进入”和“注销”工作之间的同步关系。

解：

分析题意，知道在管理读者“进入”和“注销”阅览室的工作中，存在这样一些制约关系：

（1）100个座位是读者共同使用的资源，因此要用一个资源分配信号量来管理它；

（2）读者“进入”阅览室时，要申请座位。

只有申请到座位才能进入，否则应该等待到座位的释放；

（3）没有读者时，不能做“注销”工作，必须等到有了读者才能做。

因此，可以设置两个信号量：

S1——初值为100，管理座位的分配；

S2——初值为0，控制“注销”与“进入”间取得同步。

图6-22加入P、V操作后的司机与售票员

“进入”与“注销”两个进程的流程如图6-23所示。

图6-23“进入”与“注销”两个进程

在读者进入时，调用“进入”进程，通过P（S1）来申请座位。

如果申请到，就可以办理阅览手续。

如果100个座位都申请完毕，那么第101个读者就只有在关于S1的队列上等待，等到有人调用“注销”进程执行V（S1）。

在有读者离去时，就调用“注销”进程。

3．今有3个并发进程R、S、T，它们共享一个缓冲区B。

进程R负责从输入设备读入信息，每读出一个记录后就把它存入缓冲区B中；进程S利用缓冲区B加工进程R存入的记录；进程T把加工完毕的记录打印输出。

缓冲区B一次只能存放一个记录。

只有在进程T把缓冲区里的记录输出后，才能再往里存放新的记录。

试用信号量及其P、V操作控制这3个进程间的的正确工作关系。

解：

3个并发进程R、S、T之间有如下的制约关系：

（1）R必须先做，在往缓冲区B里面存入数据后，应该向S发消息，然后等待T打印输出后释放缓冲区B；

（2）S应该与R取得同步，在等到R发来的消息（表明B里面有数据）后，取出加工、回存，然后向T发消息；

（3）T应该与S取得同步，在等到S发来的消息（表明B里的数据已经加工完毕）后，才取出打印，然后向R发消息，表示缓冲区B又可以使用了。

从这些关系可以看出，这里是3个同步问题：

R要与T取得同步；S要与R取得同步；T要与S取得同步。

所以，设置3个同步信号量：

S1——控制S要与R取得同步；

S2——控制T要与S取得同步；

S3——控制R要与T取得同步。

图6-24给出了它们的工作流程示意。

图6-24R、S、T之间的相互制约关系

4．假定有3个进程R、W1、W2共享一个缓冲区B，B中每次只能存放一个数。

进程R从输入设备读入一个数，把它存放到缓冲区B里。

如果存入的是奇数，则由进程W1取出打印；如果存入的是偶数，则由进程W2取出打印。

规定进程R只有在缓冲区B为空或内容已经被打印后才能进行存放；进程W1和W2不能从空缓冲区里取数，也不能重复打印。

试用信号量及其P、V操作管理这3个进程，让它们能够协调地正确工作。

图6-25奇数、偶数问题

解：

这实际上也是最简单“生产者—消费者”问题的变种：

进程R是产生者，进程W1、W2是两个消费者。

只是W1只消费奇数，W2只消费偶数。

图6-25所示的是3个进程的工作示意。

分析一下题目，知道3个进程间有如下的制约关系存在：

（1）进程R申请使用缓冲区B，释放缓冲区B的权利是由进程W1或W2掌握的；

（2）进程W1要等待R往缓冲区B里放入奇数后，才能工作（要与R取得同步），然后释放缓冲区；

（3）进程W2要等待R往缓冲区B里放入偶数后，才能工作（要与R取得同步），然后释放缓冲区。

因此，应该设置3个信号量：

S——初值为1，控制缓冲区B的分配；

SO——初值为0，控制W1与R取得同步；

SE——初值为0，控制W2与R取得同步。

3个进程的工作流程如图6-26所示。

图6-26W、R1、R2的相互制约关系

这里有3个问题需要解释。

（1）在进程R中，把数存入B之后，应该根据数的奇、偶性，来决定是向进程W1发消息，还是向进程W2发消息。

这样，才能给予W1或W2从B里取数的机会。

（2）由于在进程R里已经对数的奇、偶性做了判断，所以进程W1或W2到缓冲区B里取数时，不必对它再行判断，取出的内容肯定是所需要的，不会弄错。

（3）假定在进程R没有执行之前，进程W1和W2都先于它执行了。

那么这时由于信号量SO和SE的值都是0，所以它们都无法执行下去，分别在SO和SE的有关队列上等待。

当进程R被调度到、判定放入B的数是奇数还是偶数，并向W1或W2发消息后，它们两个中的一个才会被唤醒，才会到B里去取数。

还可以从别的角度出发，去理解本题目中R、W1、W2之间的制约关系，从而得到它的另一种解决办法。

图6-27给出了流程图，只需设置两个信号量：

S——初值为1；

G——初值为0。

这里有3个问题需要解释。

（1）信号量S用于资源分配。

进程R通过P（S）申请使用缓冲区B。

申请到后，才向里面存放数，然后就在信号量G上执行一个V操作，笼统地告诉进程W1或W2：

缓冲区B里有数可取了。

由于并不知道这个数的奇、偶性，所以，它们两个谁去取都是可以的。

（2）这时判断缓冲区B里数的奇、偶性，是在进程W1或W2里进行的。

运行W1时，如果判定B里的是奇数，那么进程W1就可以将其取出，然后释放缓冲区B（通过V（S）实现）。

如果判定B里的是偶数，那么进程W2就可以将其取出，然后释放缓冲区B（通过V（S）实现）。

图6-27W、R1、R2的另一种相互制约关系

图6-28第j售票处的售票程序

（3）要注意的是，如果在进程W1里判定B中的数不是奇数，那么它就不应该取出此数。

同样地，如果在进程W2里判定B中的数不是偶数，那么它就不应该取出此数。

既然它没有取，表明数还在缓冲区B里。

所以要通过V（G），使信号量G恢复原来的取值（含义是告诉要去取数的进程：

B里有数要取），以便给另一个进程去取的机会。

如果不做这一步，那么信号量G的当前值是0，无论进程W1还是W2在它的上面再执行P（G）时，就都无法通过，两个进程就会全被阻塞，进入死锁。

所以，进程W1和W2里的V（G）是非常重要的。

5．在飞机订票系统中，假定公共数据区的单元Ai（i=1，2，3…）里存放着某月某日第i次航班现有票数。

在第j个售票处，利用变量Rj暂存Ai里的内容。

现在为第j个售票处编写代码如图6-28（即教材中的图6-30）所示。

试问它的安排对吗？

如果正确，试说明理由；如果不对，指出错误，并做出修改。

解：

从图6-28可以知道，公共数据区的单元Ai（i=1，2，3…）里存放的某月某日第i次航班的现有票数，是j（j=1，2，3…）个售票处共享的数据。

因此，这些售票处对公共数据区的单元Ai（i=1，2，3…）的操作不能同时进行。

正因为如此，图中把对Ai的这些操作，用名为S的信号量上的P、V操作，保证它们互斥进行。

这样处理都是正确的。

关键是当判定没有第i次航班的机票时，图6-28里仅安排了打印“票已售完！

”的动作。

这样，第j售票处只有进入临界区的P（S），而没有执行退出临界区的V（S）。

它没有退出临界区，别的售票窗口也就无法再进入这个临界区。

所以，这种安排是不对的。

应该把图6-28改成为图6-29，这样就完全正确了。

图6-29正确的第j售票处的售票程序