求经典同步互斥问题-"司机和售票员“问题

REPEATREPEAT

启动① 关门 ②

正常运行 售票 关门－启动－行驶－停－开门

到站停 ③ 开门 ④

UNTIL FALSE UNTIL FALSE

为了安全起见：

(1)关车门后才能启动车辆 －启动在关门之后

(2)到站停车后，才能开车门－开车门在到站停车之后

在计算机系统中可以将司机和售票员分别看作P1、P2两个进程，当它们并发地向前推进时，计算机系统所接受到的实际上是司机活动与售票员活动的许多交叉中的任意一个交叉，这些交叉有些满足上述要求，有些则不满足，而 *** 作系统必须保证不发生不满足上述要求的交叉，即：

如P2尚未推进到②处时，而P1已推进到①处，则P1应等待直到P2推进到②处为止；

如P1尚未推进到③时，P2已到④，则P2应等待直到P1推进到③处为止。

P1在①处发生了等待，则P2执行到②处时应将P1唤醒；

P2在④处发生了等待，P1到③处应将P2唤醒。

一组相互合作的并发进程，为了协调其推进速度，有时需要相互等待与相互唤醒，进程之间这种相互制约的关系称作进程同步，虽然进程同步仅发生在相互有逻辑关系的进程之间，这种相互制约的关系称作进程同步，进程同步现象仅发生在相互有逻辑关系的进程之间，这点与进程互斥不同，进程互斥现象发生在任意两个进程之间。

与进程同步相关的另一概念是进程合作，一组进程如果它们单独执行不能正常进行，但并发执行可以正常进行，这种现象称为进程合作，参与进程合作的进程称为合作进程，如司机与售票员的例子，二者单独执行都不能正常进行，但二者并发反可以正常进行，成为合作进程，这种进程合作的现象在 *** 作系统中经常发生。

解法一：

struct semaphore s1,s2=0,0

cobegin

void driver(void)

{

while(TRUE){

p(s2)

启动车辆

正常行车

到站停车

V(s1)}

}

void conductor(void)

{

while(TRUE){

上、下乘客；关车门；

V(s2)

售票；

P(s1)

开车门上、下乘客}

}

coend

解法二：

struct semaphore s1,s2=1,0

cobegin

void driver(void)

{

while(TRUE){

P(s2)

启动车辆

正常行车

到站停车

V(s1)}

}

void conductor(void)

{

while(TRUE){

P(s1)

开车门

上、下乘客

关车门

V(s2)售票；}

}

coend

第一步：确定进程间的关系.售票员关车门后,要向司机发开车信号,司机接到开车信号后才能启动车辆.在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开车门,让乘客上下车.因此司机启动车辆的动作必须与售票员的动作取得同步；售票员开车门的动作也必须同司机停车取得同步.

第二步：确定信号量及其值.由于司机与售票员之间要互通消息,司机进程设置一个私有信号量run,用于判断是否关车门,司机能否启动车辆,初值为1.售票员进程设置一个私有信号量stop,用于判断是否停车,售票员是否能够开车门,初值为0

第三步：确定P（wait）、V（signal） *** 作的位置

司机 *** 作中,是否关门?没关则等待,这是一个P *** 作,P(run)；

司机 *** 作中,设立停车标志,这是一个V *** 作,V(stop)；

售票员 *** 作中,是否停车?没停则等待,这是一个P *** 作,P(stop)；

售票员 *** 作中,设立关门标志,这是一个V *** 作,V(run)

lstop ,run:semaphore

run:=1//是否关车门

stop:=0//是否停车

Driver：begin cobegin

driver:begin

L1:P(run)

启动车辆；

正常行车；

到站停车；

V(stop)

goto L1

end

Conductor:begin

L2:上乘客；

关车门；

V(run)

售票；

P(stop)

开车门；

下乘客；

goto L2

end

coend

end