博客

过独木桥问题

某条河只有一座独木桥（东西向），以便行人过河。现在河的两边都有人要过桥，按照下面规则过桥，为了保证过桥安全，请用P、V操作分别实现正确的管理。

规则：

1. 同一方向的可连续过桥，但可连续过桥人数最多为10人。
2. 某方向有人过桥时另一方向的人要等待

我对这个题目的理解：一个方向的人开始过桥时，桥上最多过10个，如果桥上的人满了，那么同方向的人再想要过桥就必须等待，直到这个方向的人全部过桥，对向的人才可以过桥。（

下面代码按此理解进行编码

）

第二种理解（有点矛盾）：东西方向交替过桥，一次最多连续过十个。我就在想，假设东方向有25个人要过桥，而西方向10人过桥的条件下，当东方向已经过了10个人（剩余15个），然后西方向10人过桥（剩余0个），然后东方向再过去10个（剩余5个），此时因为该西方向人过桥，但是西方向没人，如果西方向没人过桥，东方向必须要一直等吗？很矛盾。所以我就按第一种理解去设计了。（如果按此理解需要加一点前提条件：假设两边的人无限多）

Semaphore bridge = 10; //桥互斥信号量
Semaphore wait = 1;   //等待互斥, 当对面方向有人过桥就等待
Semaphore mutex1 = 1; //东方向互斥信号量
Semaphore mutex2 = 1; //西方向互斥信号量

int count1 = 0;		  //东方向要过桥人数, 要过桥+1, 已经过桥-1
int count2 = 0;       //西方向要过桥人数, 要过桥+1, 已经过桥-1

process_1{
	P(mutex1);
		if (count1 == 0) {
			P(wait);
		}
		count1++;
	V(mutex1);
	
	P(bridge);
		东方向人过桥();
	V(bridge);
	
	P(mutex1);
		count1--;
		if (count1 == 0) {
			V(wait);
		}
	V(mutex1);
}

process_2{
	P(mutex2);
		if (count2 == 0) {
			P(wait);
		}
		count2++;
	V(mutex2);
	
	P(bridge);
		西方向人过桥();
	V(bridge);
	
	P(mutex2);
		count2--;
		if (count2 == 0) {
			V(wait);
		}
	V(mutex2);
}