问答题 在两所学校之间有一条弯曲的小路,其中从S到T的一段路每次只允许一辆自行车通过,但中间有一个小的“安全岛”M(同时只允许两辆自行车停留),可供已从两端进入小路的两辆自行车错车使用,如图所示。试设计一个算法使来往的自行车均可顺利通过。
【正确答案】本题临界资源较多,需仔细考虑。首先中间的安全岛M仅允许两辆自行车通过,应作为临界资源设置信号量。但可以发现,在任何时刻进入小路的自行车最多不会超过两辆(两个方向各一辆),因此不需为安全岛M设置信号量。在路口S处,左侧出发的若干辆自行车应进行路口资源的争夺,以决定谁先进入小路SK段,为此设置信号量S,用以控制路口资源的争夺;同理,设置信号量T,控制右侧方向自行车对路口T的争夺。又因为小路SK段仅允许一辆车通过,所以还需要设置信号量SK初值为1,同理设置小路LT段信号量LT初值为1。程序实现如下: Semaphore S=1, T=1, SK=1, LT=1; Left() P(S); //检查路口S是否可以进入 P(SK); //检查小路SK是否可以使用,即检查是否有右边来的车 通过SK段; 进入安全岛M; V(SK); //释放小路SK的使用权 P(LT); //检查小路LT是否可以使用,即检查是否有右边来的车 通过LT; V(LT); //释放小路LT的使用权 V(S); //释放路口S的使用权 } Right() { P(T); //检查路口T是否可以进入 P(LT); //检查小路LT是否可以使用,即检查是否有左边来的车 通过LT; 进入安全岛M; V(LT); //释放小路SK的使用权 P(SK); //检查小路LT是否可以使用,即检查是否有左边来的车 通过SK; V(SK); //释放小路LT的使用权 V(T); //释放路口S的使用权 } ★注:Left进程进入安全岛M后,释放了路段SK,但没有释放路口S,原因在于它是向对面的Right进程释放路段资源SK,而在P进程离开小路LT后,才会将路口S释放给其他Left进程,如果不这样,就会死锁。请考虑如下情况:两个方向各有一辆车前进,若在Left进程到达安全岛M后,执行V(S)及V(SK)操作,则有可能使得同方向的其他Left进程得到路段SK的使用权,而进入小路SK;同理,Right进程到达安全岛后执行V(LT)及V(T)操作,有可能使得同方向的其他Right进程得到路段LT而进入小路。此时共有4辆车在整个路径中,出现死锁状态。
【答案解析】