问题 问答题

有座东西方向架设、可双向通行的单车道简易桥,最大载重负荷为4辆汽车。请定义合适的信号量,正确使用P、V操作,给出任一车辆通过该简易桥的管理算法,解答中请回答下列问题:

给出上述问题的解决算法,结合该算法,简述P、V操作解决该问题的基本思路。

答案

参考答案:

算法如下:

semaphore S,Scounteast, Scountwest, ScountD;

S:=A;

Scounteast:=A;

scountwest:=A;

ScountD:=D;

Integer Counteast, Countwest;

Counteast:=0;

Countwest:=0;

Cobegin

Program east(i)

Begin

p(Scounteast);

if Counteast=0 then p(S);

Counteast:=Counteast+A;

V(Scounteast);

p(ScountD);

上桥;过桥;下桥;

V(ScountD);

P(Scounteast);

Countest:=Counteast-A;

if Counteast=0 then V(S);

V(Scounteast);

End

Program west(i)

Begin

P(Scountwest);

if Countwest=0 then P(S);

Countwest:=Countwest+A;

V(Scountwest);

p(ScountD);

上桥;过桥;下桥;

V(ScountD);

p(Scountwest);

Countwest=Countwest-A;

if Countwest=0 then V(S);

V(Scountwest);

End

coend

解题的基本思路如下。

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

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

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

单项选择题
单项选择题