作业三 进程同步与互斥
这两个问题都是关于进程同步和互斥的经典问题，它们可以通过信号量机制来解决。信号量（semaphore）是一种用于控制多个进程对共享资源访问的同步机制。信号量可以是二进制的（只能取0或1），也可以是计数信号量（可以取非负整数值）。
题目一（2009真题）：
3 个进程 P1、P2、P3 互斥地使用一个包含 N（N ＞ 0）个单元的缓冲区。P1 每次用 produce() 生成一个正整数，并用 put() 将其送入缓冲区的某一空单元中 ；P2每次用 getodd() 从该缓冲区中取出一个奇数，并用 countodd() 统计奇数的个数 ；P3 每次用geteven() 从该缓冲区中取出一个偶数，并用 counteven() 统计偶数的个数。
请用信号量机制实现这 3 个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。
解答：
问题分析：
- 同步问题：n个缓冲区单元，缓冲区有空位置时才能写；有奇数才能读出奇数，有偶数才能读出偶数。用前V后P实现。
- 互斥问题：三个进程彼此互斥访问缓冲区。一般都是对于一个缓冲区或者本质上是缓冲区的变量进行访问，这时候就要用PV操作将对于这个信号量的访问夹在中间。
观察出这是一个生产者消费者问题，由于只有一个缓冲区，有多个商品（奇数和偶数），P1生产奇数和偶数，P2消费奇数，P3消费偶数，明显这是一个多生产者多消费者单缓冲区问题，对于这类问题，只需要将标准生产者消费者问题模型中的full信号量拆分成多个商品的信号量。
mutex：一个二进制信号量，用于控制对缓冲区的互斥访问。empty：一个计数信号量，表示缓冲区中空闲单元的数量。odd：一个计数信号量，表示缓冲区中奇数的数量。even：一个计数信号量，表示缓冲区中偶数的数量。
伪代码实现如下：
// 定义信号量
semaphore mutex = 1; // 缓冲区互斥信号量。互斥访问缓冲区
semaphore empty = N; // 缓冲区空闲位置数量。缓冲区中有n个单元
semaphore odd = 0; // 缓冲区奇数数量
semaphore even = 0; // 缓冲区偶数数量// P1进程
P1: while true dox = produce() // 生成一个数据P(empty) // 等待空闲单元。判断缓冲区是否有空单元P(mutex) // 进入缓冲区。缓冲区是否被占用，互斥访问缓冲区put(x) // 将x放入缓冲区if x % 2 == 1 thenV(odd) // 增加奇数计数elseV(even) // 增加偶数计数V(mutex) // 释放缓冲区V(empty) // 增加空闲单元计数。缓冲区空位数量加一
end while// P2进程
P2: while true doP(odd) // 等待奇数。有奇数才能取奇数出来P(mutex) // 进入临界区x = getodd() // 取出一个奇数V(mutex) // 离开临界区countodd() // 统计奇数个数
end while// P3进程
P3: while true doP(even) // 等待偶数P(mutex) // 进入临界区x = geteven() // 取出一个偶数V(mutex) // 离开临界区counteven() // 统计偶数个数
end while举一反三
设自行车生产线上有一个传送带，其中有 N (N≥3) 个位置，每个位置可存放一个车架或者一个车轮，设有3名工人，进程P1表示工人1每次加工一个车架并放入传送带，进程P2表示工人2每次加工一个车轮并放入传送带，进程P3表示工人3每次从传送带上取出一个车架和两个车轮并组装成一辆自行车。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义（要求用伪代码描述）。
参考答案：
semaphore mutex = 1; // 缓冲区互斥信号量
semaphore empty = N; // 缓冲区空闲位置数量
semaphore weel = 0; // 车轮数量
semaphore frame = 0; // 车架数量
semaphore weel_empty = N-1; // 剩余车轮空位数量名额
semaphore frame_empty = N-2; // 剩余车架空位数量名额cobegin
Process P1() {while(1) {加工一个车架;P(frame_empty); // 占用缓冲区可放置车架数量名额P(empty); // 占用一个缓冲区空位置P(mutex);车架放入缓冲区中;V(mutex);V(frame); // 车架数量+1}
}
Process P2() {while(1) {加工一个车轮；P(weel_empty); // 占用缓冲区可放置车轮数量名额P(empty); // 占用一个缓冲区空位置P(mutex);车轮放入缓冲区中；V(mutex);V(wheel); // 车轮数+1}
}
Process P3() {while(1) {P(frame); // 取出一个车架P(mutex);缓冲区中取一个车架;V(mutex);V(empty); // 空位+1；V(frame_empty); // 释放一个缓冲区可放置车架数量名额P(wheel);P(wheel);P(mutex);缓冲区中取两个车轮;V(mutex);V(empty);V(empty);V(weel_empty); // 释放一个缓冲区可放置车轮数量名额V(weel_empty); // 释放一个缓冲区可放置车轮数量名额组装为一辆车;}
}
coend考点：生产者消费者问题。
题目二：
如下图所示，get、copy和put三个进程共用两个缓冲区s和t (其大小每次存放一个记录) ，get 进程负责不断地把输入记录输入缓冲区s 中，copy 进程负责从缓冲区s 中取出记录复制到缓冲区t 中，而put 进程负责从缓冲区t 中取出记录打印。
试用PV操作实现这三个进程之间的同步，并写出伪代码描述。
解答：
问题分析：
-
缓冲区 s：用于暂存 get 进程获取的记录。
-
缓冲区 t：用于暂存 copy 进程从缓冲区 s 复制过来的记录，等待 put 进程打印。
-
互斥访问：由于缓冲区 s 和 t 的大小都为1，任何时候只能有一个进程访问任一缓冲区，以避免数据冲突。
-
同步操作：需要确保 get 进程在缓冲区 s 为空时等待，copy 进程在缓冲区 s 有数据时读取，在缓冲区 t 为空时等待，put 进程在缓冲区 t 有数据时读取。
-
P操作：等待（Proberen）操作，如果信号量的值大于0，则将其减1；如果为0，则阻塞进程。
-
V操作：信号（Verhogen）操作，将信号量的值加1，如果有进程因等待该信号量而被阻塞，则唤醒它们。
信号量定义：
-
s_empty：表示缓冲区 s 的空闲状态。初始值为1，因为一开始缓冲区 s 是空的。
-
t_full：表示缓冲区 t 的占用状态。初始值为0，因为一开始缓冲区 t 是空的。
-
mutex_s 和 mutex_t：用于确保对缓冲区 s 和 t 的互斥访问。初始值均为1。
伪代码实现如下：
// 信号量定义
Semaphore s_empty = 1; // 缓冲区s的空闲位置，初始为1
Semaphore t_full = 0; // 缓冲区t的满位置，初始为0
Semaphore mutex_s = 1; // 缓冲区s的互斥信号量，初始为1
Semaphore mutex_t = 1; // 缓冲区t的互斥信号量，初始为1// get 进程
GET: while true doP(s_empty) // 等待缓冲区 s 空闲P(mutex_s) // 进入缓冲区 s 的临界区record = read_input() // 读取输入记录V(mutex_s) // 离开缓冲区 s 的临界区put record into s // 将记录放入缓冲区 sV(t_full) // 通知缓冲区 s 已满
end while// copy 进程
COPY: while true doP(t_full) // 等待缓冲区 s 有数据P(mutex_s) // 进入缓冲区 s 的临界区record = get from s // 从缓冲区 s 取出记录V(mutex_s) // 离开缓冲区 s 的临界区P(mutex_t) // 进入缓冲区 t 的临界区put record into t // 将记录放入缓冲区 tV(mutex_t) // 离开缓冲区 t 的临界区V(s_empty) // 通知缓冲区 s 已空V(t_full) // 通知缓冲区 t 已满
end while// put 进程
PUT: while true doP(t_full) // 等待缓冲区 t 有数据P(mutex_t) // 进入缓冲区 t 的临界区record = get from t // 从缓冲区 t 取出记录V(mutex_t) // 离开缓冲区 t 的临界区print record // 打印记录V(s_empty) // 通知缓冲区 s 已空
end while
