有座东西方向架设、可双向通行的单车道简易桥,最大载重负荷为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辆车,实际上类似于“读者一写者问题”中共享有四个缓冲区的缓冲池,这是一种同步管理。根据题意,同步管理应该设置在“上桥”和“下桥”时,否则会出现等待车辆可能没有及时过桥的错误。