操作系统分章习题(5)

第二章进程管理

begin

MPC.get(2); 吃梨子; end parend

7. 设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，

他们的活动是重复劳动，分别为：工人1 加工一个车架放入货架A中；工人2、3分别加工车轮放入货架B中（每人每次放入1个车轮）；工人4从货架A中取一个车架，再从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作。

【分析】信号量Aempty表示货架A的空位数，其初值为8；信号量Afull表示货架A上存放的车架数，其初

值为0；信号量Bempty表示货架B的空位数，其初值为20；信号量Bfull表示货架B上存放的车轮数，其初值为0；信号量mutex用于互斥（初值为1）。

解：BEGIN

semaphore Aempty，Bempty，Afull，Bfull，mutex；

Aempty ：= 8；Bempty：= 20；Afull：= 0；Bfull：= 0；mutex ：=1； PARBEGIN

Worker1：BEGIN

L1：生产1个车架；

P（Aempty）； //测试货架A是否有空位置 P（mutex）； //互斥使用货架A 车架放到货架A； V（Afull）； //货架A上的车架数增1，必要时唤醒等待的进程 V（mutex）； goto L1； END

Worker2、3：BEGIN

L2：生产1个车轮；

P（Bempty）； //测试货架B是否有空位置 P（mutex）； //互斥使用货架B 车轮放到货架B； V（Bfull）； //货架B上的车轮数增1，必要时唤醒等待的进程 V（mutex）； goto L2； END

Worker4：BEGIN

L3：P（Afull）； //测试货架A上是否有车架

P（Bfull）；P（Bfull）； //测试货架B上是否有2个车轮 P（mutex）；

取1个车架；取2个车轮； V（Aempty）； //货架A空位置增1 V（Bempty）；V（Bempty）；//货架B空位置增2 V（mutex）；

组装成一辆自行车； goto L3； END

20

第二章进程管理

PAREND

END

8. 假定有一个成品仓库，总共能存放8台成品，生产者进程把生产成品放入仓库，消费者进程从仓库中

取出成品消费。为了防止积压，仓库满时就停止生产。由于仓库搬运设备只有一套，故成品的存入和取出只能分别进行，试用P、V操作来实现该方案。 解：semaphore mutex, empty, full ;

mutex=1; //互斥信号量 empty=8; //生产者进程的同步信号量 full=0; //消费者进程的同步信号量 parbegin

process Pi //生产者进程 {

while (1) {

生产一个成品x; P(empty) //看看仓库是否还有空间可放成品 P(mutex); //互斥使用搬运设备 用搬运设备将成品放入仓库; V(full); //仓库中成品数增1(可能唤醒一个消费者) V(mutex); } }

process Cj //消费者进程 {

while (1) {

P(full) //看看仓库是否有成品 P(mutex); //互斥使用搬运设备 用搬运设备将成品从仓库取出;

V(emtpy); //仓库中可放成品数增1(可能唤醒一个生产者) V(mutex); } } parend 9. 有三个进程R、W1、W2共享一个缓冲器Ｂ，而B中每次只能存放一个数。当B中无数时，进程R

可将从输入设备上读入的数存放到缓冲器B中；若存放到B中的是奇数，则允许进程W1将其取出打印；若存放到B中的是偶数，则允许进程Ｗ2将其取出打印；同时规定：进程R必须等缓冲器中的数被取出后才能再存放下一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；Ｗ1和Ｗ2都不能从空的缓冲器中取数。用P、V操作作为同步机制写出三个并发进程的同步算法。(动作部分可用文字描述) 解：semaphore S,S1,S2;

S=1; S1=S2=0; parbegin Process R {

while (1) {

从输入设备上读入的数x;

21

第二章进程管理

P(S); B=x;

if (x%2==1) V(S1); //若是奇数，则通知W1 else V(S2); //若是偶数，则通知W2 }

}

Process W1 {

while (1) {

P(S1); y=B; V(S); Print(y); } }

Process W2 {

while (1) {

P(S2); y=B; V(S); Print(y); } }

parend

//看看缓冲器B中是否有奇数 //从缓冲器B中取奇数存于y

//通知R，缓冲器已空，可以在往里存数了 //打印

//看看缓冲器B中是否有偶数 //从缓冲器B中取偶数存于y

//通知R，缓冲器已空，可以在往里存数了

10. 进程P1使用缓冲区buffer向进程P2，P3，P4发送消息（如图2-1所示），要求每当Pl向buffer中

发消息时，只有当P2，P3，P4进程都读取这条消息后P1才可向buffer中发送新的消息。试用信号量机制描述如下图所示进程的动作过程。（本题是下题的特例）

P2 P1 buffer P3 P4 图2-1

解：设P1、P2、P3、P4的资源信号量分别为S1、S2、S3、S4

semaphore S1,S2,S3,S4;

S1.value=3;S2.vale=S3.vale=S4.value=0; （3分） parbegin process P1 {

while (condition) {

P1生成一个消息；

22

第二章进程管理

P（S1）；P（S1）；P（S1）； P1将消息存入缓冲区buffer； V（S2）；V（S3）；V（S4）； }

}

process Pi(i=2,3,4) {

while （condition） {

P（Si）；

Pi从buffer中取出消息； V（S1）；

Pi消费（使用）该消息； } }

parend

另一解法如下（此法更一般化，可用来解下题）：

semphore S1[3], S[3]; for (i=0;i<3;i++) { S1[i]=1; S[i]=0; }

parbegin process P1 {

while (1) {

P1生成一个消息；

for (i=0;i<3;i++) P(S1[i]); //看看P2～P4是否将消息取走 P1将消息存入缓冲区buffer；

for (i=0;i<3;i++) V(S[i]); //通知P2～P4缓冲区buffer中已有消息 } }

Process P2 {

while(1) { P(S[0]); //看看buffer中是否已有消息 从buffer中取出消息;

V(S1[0]); //通知P1,P2已从缓冲区buffer中取走消息 消费（使用）该消息; } }

Process P3 {

while(1) { P(S[1]); //看看buffer中是否已有消息

23

第二章进程管理

从buffer中取出消息;

V(S1[1]); //通知P1,P3已从缓冲区buffer中取走消息 消费（使用）该消息; }

}

Process P4 {

while(1) { P(S[2]); //看看buffer中是否已有消息 从buffer中取出消息;

V(S1[2]); //通知P1,P4已从缓冲区buffer中取走消息 消费（使用）该消息; } }

parend

11. (北大1994年试题)进程A1，A2，...，An1通过m个缓冲区向进程B1，B2，...，Bn2不断地发送

消息。发送和接收工作遵循如下规则： ① 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样； ② 对每个消息，B1，B2，...，Bn2都需各接收一次，读入各自的数据区内； ③ m个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。 试用P、V操作组织正确的发送和接收操作。（上题是本题的特例） 【分析】这是P-C问题变形。把这一组缓冲区看成n2组缓冲区。

解：设置一个信号量mutex实现诸进程对缓冲区的互斥访问；两个信号量数组empty[n2]和full[n2]描述n2组缓冲区的使用情况。mutex初值为1，数组empty的元素初值为m，数组full的元素初值为0。

var mutex: semaphore :=1;

empty,full: array[0..n2-1] of semaphore; i: integer;

for (i=0;i

empty[i]=m;full[i]=0; }

Aj ( ) //j=1,2,...,n1 {

while (1) { ......

for (int i=0;i

for (i=0;i

24

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库操作系统分章习题(5)在线全文阅读。