VERYGOOD操作系统硕士研究生入学考试模拟试题参考答案（电子）

(1) 临界区管理的原则是什么?

(2) 分析该题中的互斥现象和同步现象。 (3) 说明信号量的声明和初值设定的理由。

(4) 给出上述问题的解决算法，结合该算法，简述PV操作解决该问题的基本思路。 解：

（1），临界区管理原则有：a)一次只能一个进程进入临界区；b)等待进入临界区的时间必须是有限的；c)临界区空闲时，访问临界区的请求应立即响应；d)进程在临界区中的驻留时间必须有限。

（2）该题中的互斥现象有两点：第一，因为简易桥是单向通过，因此东西方向过桥的车辆对桥的使用是互斥的，第二，同方向上可能会同时有多辆车辆过桥，为了正确释放桥的使用，必须设置桥上车辆的计数器，对计数器的使用也是需要互斥的。该题中的同步现象有：当桥上已有4辆车辆时，同方向上的第5辆之间存在同步现象。

（3）据上分析，信号量应该有4个：S，初值为1，代表桥的互斥使用的信号量；Scounteast, 初值为1，代表由东向西方向行驶的桥上的车辆计数器的互斥使用；Scountwest,初值为1，代表由西向东方向行驶的桥上的车辆计数器的互斥使用；Scount4，初值为4，代表桥上车辆的计数信号量，用于同步管理。 （4）算法如下：

var S, Scounteast, Scountwest, Scount4;:semaphore; S:=1;Scounteast:=1;Scountwest:=1;Scount4:=4; Counteast, Countwest:integer; Counteast:=0;Countwest:=0; Cobegin

process east(i) begin

P(Scounteast);

if Counteast=0 then P(S); Counteast:=Counteast+1; V(Scounteast); P(Scount4);

上桥；过桥；下桥； V（Scount4）; P(Scounteast);

Counteast:=Counteast-1; if Counteast=0 then V(S); V(Scounteast); end;

process west(i) begin

33

P(Scountwest);

if Countwest=0 then P(S); Countwest:=Countwest+1; V(Scountwest); P(Scount4);

上桥；过桥；下桥； V(Scount4); P(Scountwest);

Countwest:=Countwest-1; if Countwest=0 then V(S); V(Scountwest); end; coend.

解题的基本思路如下：

●关于桥的互斥使用：互斥管理只发生在：同方向上的第一辆车在上桥前需要查看桥的状态是否为“可用”，此时，可以使用P(S) 操作；类似，同方向上的最后一辆车下桥时，必须释放桥的使用，此时，可以使用V(S)操作。

●为判断桥上车辆数目，必须设置计数器Counteast和Countwest.，而上述两变量则是为新引入的共享变量，必须互斥使用，因此，设置两个信号量Scounteast和Scountwest，使用PV操作进行管理。

●桥的最大负荷为4辆，实际上类似于“读者—写者问题”中共享有四个缓冲区的缓冲池，这是一种同步管理。根据题意，同步管理应该设置在“上桥”和“下桥”时，否则会出现等待车辆可能没有及时过桥的错误。

5. 有一共享文件F和两组并发进程（A组和B组），该两组进程在共享文件F时只进行读且受到如下限制：(南京大学1996)

·同一组的进程可同时读文件F；

·当某组有进程在读文件F时，不允许另一组中的任何进程读文件F； ·当无进程在读文件F时则允许任何一组中的进程去读文件F。 请用管理（monitor）来实现对共享文件F的管理。 答：

type sharefile = MONITOR

var Acount, Bconut : integer; A, B : condition;

Define Astart_read, Aend_read, Bstart_read, Bend_read; use wait, signal, check, release; procedure Astart-read; begin

check(IM);

if Bcount>0 then wait(A,IM);

34

Acount := Acount + 1; signal(A, IM); release(IM); end;

procedure Aend-read; begin

check(IM);

Acount := Acount - 1;

if Acount=0 then signal(B,IM); release(IM); end;

procedure Bstart-read; begin

check(IM);

if Acount>0 then wait(B,IM); Bcount := Bcount + 1; signal(B, IM); release(IM); end;

procedure Bend-read; begin

check(IM);

Bcount := Bcount - 1;

if Bcount=0 then signal(A,IM); release(IM); end;

begin

Acount := 0; Bcount := 0; A := 0; B := 0; end.

任何一个进程读文件前，首先调用start-read，执行完读操作后，调用end-read。即：

cobegin

process A-group-reader begin ……

call sharefile.Astart-read; ……

read the F; ……

call sharefile.Aend-read; …… end;

process B-group-reader begin ……

call sharefile.Bstart-write; ……

35

read the F; ……

call sharefile.Bend-write; …… end; coend.

6.进程P使用缓冲区B向进程Q1,Q2,?,Qm发送消息，要求每当P向B中发消息，只有当所有的进程Q1,Q2,?,Qm都读取这条消息后，P才可向B发新消息。利用P,V原语写进它们的动作序列。(大连理工1999)

解：在本题中，进程间发/收消息如图进行。 Q1

P ? B

Qm

可以把缓冲区B分作有m个空槽，每个可存一个消息，发消息时P共发m个，取消息时Qi仅取自已的一个消息，这样可满足题意。于是，应设置一个信号量mutex实现诸进程对缓冲区B的互斥访问；一个信号量empty和信号量数组full[m]描述缓冲区的消息收发情况，应符合发一次、Qi各收1次而共为m次。mutex的初始值为1；empty初值为m；full[m]初值为0。其同步关系描述如下： var mutex,empty,full[m]：semaphore; B:array [0..m-1] of message; int i;mutex=1; empty=m;

for(i=0;i<=m-1;i++) {

full[i]=0; }

cobegin

process P begin

while (1) {

send( );

} end;

process Qi (i=1,2,?,m)

begin while (1) {

receive(i);

}

36

end;

coend

send ( ) /*P发送消息的动作*/ { int i;

for (i=0;i<=m-1;i++) P(empty); p(mutex);

for(i=0;i<=m-1;i++) {

B[i]:=new message; }

V(mutex）;

for(i=0;i<=m-1;i++) V(full[i]); }

receive(i) /*进程Qi接收消息动作*/ {

P(full[i]); P(mutex);

take the message from B[i]; V(mutex); V(emtpy); }

37