经典同步问题

1.生产者 - 消费者问题

生产者消费者问题是并发编程中的经典问题，涉及到两种线程 —— 生产者 和 消费者，它们共享一个固定大小的缓冲区或存储区。

• 生产者的任务是生成数据并将其 放入缓冲区。
• 消费者的任务是 从缓冲区中取出 并消费这些数据。

关键的挑战在于确保生产者不会在缓冲区满时添加数据，同时确保消费者不会在缓冲区空时尝试消费数据。

semaphore mutex = 1;    // 临界区互斥信号量
semaphore empty = n;    // 空闲缓冲区数量
semaphore full = 0;     // 忙缓冲区数量

producer() {
	while (1) {
		P(empty);    // 等待一个空位置
		P(mutex);    // 进入临界区前先获取mutex
		...          // 将数据项添加到缓冲区
		V(mutex);    // 离开临界区，释放mutex
		V(full);     // 增加一个数据项的计数
	}
}

consumer() {
	while (1) {
		P(full);    // 等待一个数据项
		P(mutex);   
		...         // 从缓冲区取出数据项并消费
		V(mutex);
		V(mepty);   // 增加一个空位置的计数
	}
}

---

2.读者 - 写者问题

读者写者问题 是另一个经典的并发编程问题，涉及到对 共享数据 或 资源 的访问，这些 资源 可以被 多个读者 同时读取，但只能被 一个写者 写入，而且当 写者 正在写入数据时，没有其他 读者 或 写者 可以访问该 资源。

这个问题的挑战在于两点：

• 允许多个读者同时读取资源。
• 确保当有一个写者访问资源时，没有其他读者或写者可以同时访问。

下面的代码是读者优先的写法：

int read_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;

reader() {
	while (1) {
		P(mutex);                         // 获取互斥访问权，以修改 read_count
		read_count += 1;
		if (read_count == 1) P(wrt);      // 如果这是第一个读者，需要锁定资源，防止写者写入
		V(mutex);                         // 释放互斥访问权
		...                               // 读取资源
		P(mutex);                         // 获取互斥访问权，以修改 read_count
		read_count -= 1;
		if (read_count == 0) V(wrt);     // 如果没有读者在读取，释放资源，允许写者写入
		V(mutex);                        // 释放互斥访问权
	}
}

writer() {
	while (1) {
		P(wrt);                          // 获取资源的互斥访问权
		...                              // 写入资源
		V(wrt);                          // 释放资源的互斥访问权
	}
}

---

3.哲学家就餐问题

假设有五位 哲学家 坐在一个 圆桌 周围，每两位哲学家之间有一把 叉子。哲学家的生活由 思考和吃饭 两种活动组成。为了吃饭，一个哲学家需要两把叉子——左边和右边的一把。问题在于，如何设计一个算法使得哲学家们可以正常就餐，而不会因为竞争叉子而导致死锁或饥饿。

哲学家就餐问题有多种解法，这里只提供一种 最直观的解法，对于包含 N 位哲学家的问题：

• 前 N-1 个哲学家先拿起 左边的叉子，再拿起 右边的叉子
• 最后一个 哲学家先拿起 右边的叉子，再拿起 左边的叉子

semaphore fork[5] = {1, 1, 1, 1, 1};     // 五个叉子，初始都是可用的

void philosopher() {
	if (i < 5) {
		// 对于前面的哲学家，先左后右
		first = i;
		second = (i + 1) % 5;
	} 
	else {
		//对于最后一个哲学家，先右后左
		first = (i + 1) % 5;
		seconde = i;	
	}

	while (1) {
		think();
		P(fork[first]);
		P(fork[second]);
		eat();
		V(fork[first]);
		V(fork[second]);
	}
}

---

4.题目实战

4.1.

semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

poter() {
	P(empty);
	P(mutex);
	将行李放入传送带;
	V(mutex);
	V(full);
}

passenger() {
	P(full);
	P(mutex);
	取走行李;
	V(mutex);
	V(empty);
}

4.2.

semaphore door = 1;
semaphore mutex1 = 1, mutex2 = 1;                 // studentCount、paperCount的互斥访问权
semaphore ready = 1, begin = 1, over = 1;         // 发卷、开始考试、所有学生交卷
int studentCount = 0, paperCount = 0;

Student() {
	P(door);
	进门;
	V(door);
	
	P(mutex1);
	studentCount += 1;
	if (studentCount == N) V(ready);
	P(mutex1);

	P(begin);
	答题、交卷;
	P(mutex2);
	paperCount += 1;
	if (paperCount == N) V(over);
	P(mutex2);
	
	P(door);
	出门;
	V(door);
}

Teacher() {
	P(door);
	进门;
	V(door);

	P(ready);
	发试卷;
	V(begin);
	等待监考结束;
	P(over);

	P(door);
	出门;
	V(door);
}

4.3. 2025 年 408 真题

三个人一起植树，甲挖坑，乙放树苗入坑并填土，丙负责为新种树苗浇水。步骤依次为：挖树坑，放树苗，填土和浇水。现在有铁锹和水桶各一个，铁锹用于挖树坑，填土。水桶用于浇水。当树坑数量小于 3 时，甲才可以挖树坑。设初始坑 = 0，铁锹水桶均可用，定义尽可能少的信号量，用 wait() 和 signal() 操作描述植树过程中三人的同步互斥关系，并说明所用信号量的作用及其初值。

这题是一个近似于流水线的结构，
其过程为：挖树坑（甲）→ 放树苗、填土（乙）→ 浇水（丙）。
不过甲最多可以同时挖三个树苗，也就是说不允许同时存在 4 个未被乙使用的树坑，这是比较复杂的一点。
实现甲和乙之间的同步需要使用到 pits 和 empty 这两个信号量，同时还需要一个 water 信号量来实现乙和丙的同步，代码实现如下：

semaphore mutex = 1;    // 对铁锹的使用需要互斥
semaphore pits = 3;     // 甲还能挖洞的数量
semaphore empty = 0;    // 可以使用的树坑的数量
semaphore water = 0;    // 需要浇水的树苗数量

甲() {
	wait(pits);          // 最多只能挖三个未被乙使用的坑
	wait(mutex);         // 占用铁锹
	挖树坑;
	signal(mutex);       // 释放铁锹
	signal(empty);       // 通知乙可以放树苗和填土了
}

乙() {
	wait(empty);         // 等待到有树坑为止
	wait(mutex);         
	放树苗、填土;
	signal(mutex);
	signal(pits);       // 通知甲可以继续挖坑了
	signal(water);      // 通知丙可以浇水了
}

丙() {
	wait(water);
	浇水;
}

4.4. 2014 年 408 真题

系统中有多个生产者进程和多个消费者进程，共享一个能存放 1000 件产品的环形缓冲区（初始为空）。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出 10 件产品后，其他消费者进程才可以取产品。请使用信号量 P、V（wait()，signal()）操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。

这是典型的生产者和消费者问题，只对典型问题加了一个条件，只需在标准模型上新加一 个信号量，即可完成指定要求。
设置四个变量 consumer_mutex、buffer_mutex、empty 和 full,

• consumer_mutex 用于一个控制一个消费者进程一个 周期（10 次）内对于缓冲区的控制，初值为 1；
• buffer_mutex 用于进程单次互斥的访问缓冲区，初值 为 1；
• empty 代表缓冲区的空位数，初值为 0；
• full 代表缓冲区的产品数，初值为 1000，具体进 程的描述如下：

semaphore consumer_mutex = 1, buffer_mutex = 1;
semaphore empty = 1000;
semaphore full = 0;

Consumer() {
	P(consumer_mutex);
	for (int i = 0; i < 10; i++) {
		P(full);
		P(buffer_mutex);
		从缓冲区取走产品;
		V(buffer_mutex);
		V(empty);
		消费产品;
	}
	V(consumer_mutex);
}

Producer() {
	P(empty);
	生产产品;
	P(buffer_mutex);
	将产品放入缓冲区;
	V(buffer_mutex);
	V(full);
}

4.5. 2009 年 408 真题

三个进程 P₁ 、P₂ 、P₃ 互斥使用一个包含 N(N>0) 个单元的缓冲区。 P₁ 每次用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元中； P₂ 每次用 getodd() 从该缓冲区中取出一个奇数并用 countodd() 统计奇数个数； P₃ 每次用 geteven() 从该缓冲区中取出一个偶数并用 counteven() 统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

互斥资源：缓冲区只能互斥访问，因此设置互斥信号量 mutex。
同步问题：

• P₁ 、P₂ 因为奇数的放置与取用而同步，设同步信号量 odd；
• P₁ 、P₃ 因为偶数的放置与取用而同步，设置同步信号量 even；
• P₁ 、P₂ 、P₃ 因为共享缓冲区，设同步信号量 empty, 初值为 N。程序如下：

semaphore mutex = 1;
semaphore odd = 0, even = 0;
semaphore empty = N;

P1() {
	x = produce();        // 生成一个数
	P(empty);             // 判断缓冲区是否有空单元
	P(mutex);             // 缓冲区是否被占用
	put();
	P(mutex);             // 释放缓冲区
	if (x % 2 == 1) V(odd);  // 如果是偶数，向 P3 发出信号
	else V(even);            // 如果是奇数，向 P2 发出信号
}

P2() {
	P(odd);               // 收到 P1 发来的信号，已产生一个奇数
	P(mutex);             // 缓冲区是否被占用
	getodd();
	V(mutex);             // 释放缓冲区
	V(empty);             // 向 P1 发信号，多出一个空单元
	countodd();
}

P3() {
	P(even);              // 收到 P1 发来的信号，已产生一个偶数
	P(mutex);
	geteven();
	V(mutex);
	V(empty);
	counteven();
}

---