独木桥问题

前言

独木桥问题是操作系统中P、V操作部分的经典问题，有很多变种问题也是考试的重点，需要准确牢记！

独木桥问题1

问题描述

东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待一方的车全部过完后， 另一方的车才允许过桥。请用信号量和 P、V操作写出过独木桥问题的同步算法。

问题分析

首先对于东西两侧的车辆而言，桥是一个互斥资源，而对东西两侧各自而言，每辆车上桥是同步关系，东西两侧的车辆在抢到这互斥资源后只有最后一辆车通过了独木桥才释放，所以需要记录上桥车子的数量，这个问题和读者优先的读写问题很相似。

PV、操作

semaphore wait = 1；  // 互斥信号量，表示独木桥的数量
int count1 = 0;       // 东侧车辆在独木桥上的数量
semaphore mutex1 = 1; // 东侧车辆的互斥信号量，保证count1操作的完整执行
int count2 = 0;       // 西侧车辆在独木桥上的数量
semaphore mutex2 = 1; // 西侧车辆的互斥信号量，保证count2操作的完整执行

cobegin
process P东() {
	P(mutex1);
	count1++;
	if(count1 == 1)  // 东侧第一个准备上桥的车去抢夺独木桥
		P(wait);
	V(mutex1);
	{过独木桥};
	P(mutex1);
	count1--;
	if(count1 == 0)  // 东侧最后一个已经下桥的车去释放独木桥
		V(wait);
	V(mutex1);
}

process P西() {
	P(mutex2);
	count2++;
	if(count2 == 1)  // 西侧第一个准备上桥的车去抢夺独木桥
		P(wait);
	V(mutex2);
	{过独木桥};
	P(mutex2);
	count2--;
	if(count2 == 0)  // 西侧最后一个已经下桥的车去释放独木桥
		V(wait);
	V(mutex2);
}
coend

独木桥问题2

问题描述

在独木桥问题1中，限制桥面上最多可以有k辆汽车通过。试用信号量和P、V操作写出过独木桥问题的同步算法

问题分析

在独木桥问题1的基础上，增加对桥面上车辆的控制，东西侧抢夺到独木桥的一方，要竞争上桥的名额，所以要增加一个互斥信号量

P、V操作

semaphore wait = 1；  // 互斥信号量，表示独木桥的数量
int count1 = 0;       // 东侧车辆在独木桥上的数量
semaphore mutex1 = 1; // 东侧车辆的互斥信号量，保证count1操作的完整执行
int count2 = 0;       // 西侧车辆在独木桥上的数量
semaphore mutex2 = 1; // 西侧车辆的互斥信号量，保证count2操作的完整执行
semaphore bridge = k; // 限制获得独木桥使用权的一方在独木桥上的数量

cobegin
process P东() {
	P(mutex1);
	count1++;
	if(count1 == 1)  // 东侧第一个准备上桥的车去抢夺独木桥
		P(wait);
	V(mutex1);
	
	P(bridge);
	{过独木桥};
	V(bridge);
	
	P(mutex1);
	count1--;
	if(count1 == 0)  // 东侧最后一个已经下桥的车去释放独木桥
		V(wait);
	V(mutex1);
}

process P西() {
	P(mutex2);
	count2++;
	if(count2 == 1)  // 西侧第一个准备上桥的车去抢夺独木桥
		P(wait);
	V(mutex2);
	
	P(bridge);
	{过独木桥};
	V(bridge);
	
	P(mutex2);
	count2--;
	if(count2 == 0)  // 西侧最后一个已经下桥的车去释放独木桥
		V(wait);
	V(mutex2);
}
coend

独木桥问题3（最难理解）

问题描述

在独木桥问题1中，以三辆汽车为一组，要求保证东方和西方以组为单位交替通过汽车。试用信号量和P， V操作写出汽车过独木桥问题的同步算法

问题分析

要求东西方车辆交替通过，优点生产者消费者的同步问题的感觉，所以需要两个同步信号量维持东西方车辆交替进行，一方的三辆车通过后就去唤醒另一方通过，依次循环，直至全部通过。

P、V操作

semaphore wait = 1；  // 互斥信号量，表示独木桥的数量
int count1 = 0;       // 东侧车辆在独木桥上的数量
semaphore mutex1 = 1; // 东侧车辆的互斥信号量，保证count1操作的完整执行
int count2 = 0;       // 西侧车辆在独木桥上的数量
semaphore mutex2 = 1; // 西侧车辆的互斥信号量，保证count2操作的完整执行
semaphore S1 = 3;     // 东侧可以上桥的车子数量
semaphore S2 = 0;     // 西侧可以上桥的车子数量

cobegin
process P东() {
	P(S1);           // 东侧先申请使用独木桥
	P(mutex1);
	count1++;
	if(count1 == 1)  // 东侧第一个准备上桥的车去抢夺独木桥
		P(wait);
	V(mutex1);
	{过独木桥};
	V(S2);
	P(mutex1);
	count1--;
	if(count1 == 0)  // 东侧最后一个已经下桥的车去释放独木桥
		V(wait);
	V(mutex1);
}

process P西() {
	P(S2);           // S2初始值为0，所以刚开始只能等待
	P(mutex2);
	count2++;
	if(count2 == 1)  // 西侧第一个准备上桥的车去抢夺独木桥
		P(wait);
	V(mutex2);
	{过独木桥};
	V(S1);
	P(mutex2);
	count2--;
	if(count2 == 0)  // 西侧最后一个已经下桥的车去释放独木桥
		V(wait);
	V(mutex2);
}
coend

P、V操作错误分析

仔细地观察上述P、V操作，会发现它描述的情况和题目的要求不完全一致。因为情况较多，在这就举一个反例。

反例：因为我们给S1设置初值为3，所以东侧在争夺独木桥方面是具有优势的。刚开始，肯定是东侧的一辆车A先上桥，A过了独木桥以后会使S2+1，这个时候西侧的车B就有希望继续执行，由于这个时候独木桥的使用权在东侧，所以车B执行到P(wait)，然后等待。假设这个时候东侧只有车A上桥，车A继续执行到count1--，问题就出在这里，因为此时只有车A上桥，所以count的值为1，执行完count--以后，count==0正好满足释放独木桥的条件，西侧的车B等待这一刻很久了，它如果瞅准时机，申请到了独木桥的使用权，此时就会呈现东西侧以一辆车为一组交替执行，不满足题目要求。

由分析我们可以看出，上述P、V操作其实包含着很多种可能，有可能是一辆车为一组，也有可能是两辆车为一组，也有可能是三辆车为一组，设置会出现东西侧车辆以不同的数量为一组交替通过独木桥。

我们要求解的答案是上述可能性的子集！

正解

**分析：**仔细研究上述错误的P、V操作会发现，原因出在释放资源的判断上，上述写法，无法保证一组有三辆车子下桥，所以我们引入新的变量来表示下桥的车子数量

semaphore wait = 1;    // 互斥信号量，表示独木桥的数量
int countu1 = 0;        // 东侧在桥上的车子数量
int countd1 = 0;       // 东侧下桥的车子数量
semaphore mutex1 = 1;  // 东侧车辆的互斥信号量，保证count1和countu1操作的完整执行
int countu2 = 0;        // 西侧在桥上的车子数量
int countd2 = 0;       // 西侧下桥的车子数量
semaphore mutex2 = 1;  // 西侧车辆的互斥信号量，保证count2和countu2操作的完整执行
semaphore S1 = 3;      // 东侧可以上桥的车子数量
semaphore S2 = 0;      // 西侧可以上桥的车子数量

cobegin
process P东() {
    P(S1);             // S1初始值为3，所以可以先申请使用独木桥
    P(mutex1);         // 为保证countu1++完整执行而进入临界区
    countu1++;         // 东侧上桥车子数量+1
    if(countu1 == 1)   // 如果是第一个上桥的车子，则去占用独木桥
    	P(wait);
    V(mutex1);         // countu1++操作完成，故退出临界区
    {过独木桥};
    V(S2);             // 唤醒西侧车子
    
    P(mutex1);         // 为保证countu1--和countd1++完整执行而进入临界区
    countu1--;         // 东侧车子开始下桥
    countd1++;         // 记录东侧下桥的车子数量
    if((countu1 == 0) && countd1 == 3) {
    	countd1 = 0;
     	V(wait);   
    }
    V(mutex1);
}

process P西() {
    P(S2);             // S2初始值为0，所以刚开始西侧只能等待
    P(mutex2);         // 为保证countu2++的完整执行而进入临界区
    countu2++;         // 西侧上桥车子数量+1
    if(countu2 == 1)   // 如果是第一个上桥的车子，则去占用独木桥
    	P(wait);
    V(mutex2);         // countu2++操作完成，故退出临界区
    {过独木桥};
    V(S1);             // 唤醒东侧车子
    
    P(mutex2);         // 为保证countu2--和countd2++完整执行而进入临界区
    countu2--;         // 西侧车子开始下桥
    countd2++;         // 记录西侧下桥的车子数量
    if((countu2 == 0) && (countd2 == 3)) {
    	countd2 = 0;
    	V(wait);
    }
    V(mutex2);
}
coend

独木桥问题4

问题描述

在独木桥问题1中，要求各方向的汽车串行过桥，但当另一方提出过桥时，应能阻止对方未上桥的后继车辆，待桥面上的汽车过完桥后，另一方的汽车开始过桥。试用信号量和P，V 操作写出过独木桥问题的同步算法

问题分析

根据问题描述，在独木桥问题1中，东西侧车辆也是互斥通过独木桥的，问题4只是在此基础上增加了一方对另一方排他性的控制这样的要求，应该使用互斥信号量来完成。

P、V操作

semaphore wait = 1；  // 互斥信号量，表示独木桥的数量
int count1 = 0;       // 东侧车辆在独木桥上的数量
semaphore mutex1 = 1; // 东侧车辆的互斥信号量，保证count1操作的完整执行
int count2 = 0;       // 西侧车辆在独木桥上的数量
semaphore mutex2 = 1; // 西侧车辆的互斥信号量，保证count2操作的完整执行
semaphore stop = 1;   // 上桥许可证，表示同一时刻桥上只有来自同一方向的车

cobegin
process P东() {
	P(stop);
		P(mutex1);
		count1++;
		if(count1 == 1)  // 东侧第一个准备上桥的车去抢夺独木桥
			P(wait);
		V(mutex1);
	V(stop);
	{过独木桥};
	P(mutex1);
	count1--;
	if(count1 == 0)      // 东侧最后一个已经下桥的车去释放独木桥
		V(wait);
	V(mutex1);
}

process P西() {
	P(stop);
		P(mutex2);
		count2++;
		if(count2 == 1)  // 西侧第一个准备上桥的车去抢夺独木桥
			P(wait);
		V(mutex2);
	V(stop);
	{过独木桥};
	P(mutex2);
	count2--;
	if(count2 == 0)  // 西侧最后一个已经下桥的车去释放独木桥
		V(wait);
	V(mutex2);
}
coend