1889 lines
56 KiB
Markdown
1889 lines
56 KiB
Markdown
# 第四章 互斥、同步与通讯（上）
|
||
|
||
## 一、知识讲解
|
||
|
||
本章是操作系统的核心章节之一，主要研究多进程（多线程）并发执行时如何协调彼此的活动。内容涵盖并发原理、进程互斥、进程同步、经典同步问题以及管程等高级同步机制。
|
||
|
||
---
|
||
|
||
### 4.1 并发进程
|
||
|
||
#### 4.1.1 前趋图（Precedence Graph）
|
||
|
||
**定义**：前趋图是一个**有向无环图（DAG）**，用于描述进程（或语句、计算步骤）之间的执行顺序关系。
|
||
|
||
- **结点**：表示一个语句、一个计算步骤或一个进程。
|
||
- **有向边（→）**：表示偏序或前趋关系。
|
||
- 形式化：→ = {(Pi, Pj) | Pj 启动之前 Pi 必须已经完成}
|
||
- 记号：Pi → Pj 表示 Pi 是 Pj 的前趋，Pj 是 Pi 的后继。
|
||
- **初始结点**：没有前趋的结点。
|
||
- **终止结点**：没有后继的结点。
|
||
- **权重（weight）**：每个结点可附带权重，表示该结点所包含的程序量或计算时间。
|
||
|
||
**举例**：P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P5, P4→P6, P5→P7, P6→P7。
|
||
|
||
**考点提示**：前趋图常用于表示任务调度、编译流水线的依赖关系；它是理解进程同步关系的图形化工具。
|
||
|
||
---
|
||
|
||
#### 4.1.2 顺序程序及其特性
|
||
|
||
**程序的顺序执行**包括两层含义：
|
||
|
||
1. **内部顺序性**：对于一个进程，它的所有指令是按序执行的。
|
||
- 例：S1: a:=x+y → S2: b:=a-z → S3: c:=a+b → S4: d:=c+5
|
||
|
||
2. **外部顺序性**：对于多个进程，所有进程的活动是依次执行的（一个执行完再执行下一个）。
|
||
- 例：输入(I)、计算(C)、打印(P)三个进程：Ii → Ci → Pi。
|
||
|
||
**顺序程序的三大特性**：
|
||
| 特性 | 含义 |
|
||
|---|---|
|
||
| **连续性** | 指令逐条执行 |
|
||
| **封闭性** | 不受其它程序及外界因素影响 |
|
||
| **可再现性** | 结果与推进速度无关 |
|
||
|
||
---
|
||
|
||
#### 4.1.3 并发程序及其特性
|
||
|
||
**程序的并发执行**：
|
||
- **内部并发性**：同一程序内部多条语句之间的并发（如 S1、S2 无依赖可并行）。
|
||
- **外部并发性**：多个程序之间的并发。
|
||
|
||
**并发程序的三大特性**：
|
||
| 特性 | 含义 |
|
||
|---|---|
|
||
| **间断性（失去连续性）** | 程序交叉执行 |
|
||
| **非封闭性** | 一个进程的运行环境可能被其它进程所改变 |
|
||
| **不可再现性** | 由于交叉的随机性，多次执行可能对应不同的交叉，结果不同 |
|
||
|
||
**不可再现性经典例子**：
|
||
|
||
```
|
||
进程 P: 进程 Q:
|
||
A1: N:=0; B1: PRINT(N);
|
||
A2: N:=N+1; B2: N:=0;
|
||
A3: GOTO A2; B3: GOTO B1;
|
||
```
|
||
|
||
- 若 P 循环 5 次后 Q 循环 1 次，再 P 循环 3 次 Q 循环 1 次，输出 5, 3；
|
||
- 若 P 循环 2 次后 Q 循环 1 次，再 P 循环 6 次 Q 循环 1 次，输出 2, 6。
|
||
|
||
**易考点**：Q 执行完 B1 后被中断，P 加 1，Q 再执行 B2，则 P 的累计数被丢失——经典的**读丢失**问题。
|
||
|
||
---
|
||
|
||
#### 4.1.4 程序并发执行的条件：Bernstein 条件
|
||
|
||
**目的**：在失去封闭性的条件下，**保持可再现性**。
|
||
|
||
- **读集 R(pi)**：程序 pi 执行期间所需读取的所有变量的集合。
|
||
- **写集 W(pi)**：程序 pi 执行期间所需改变的所有变量的集合。
|
||
|
||
**Bernstein 条件**：若两个程序 p1, p2 满足
|
||
$$R(p_1) \cap W(p_2) \cup R(p_2) \cap W(p_1) \cup W(p_1) \cap W(p_2) = \Phi$$
|
||
则能够保持可再现性，可以并发执行。该条件由 **Bernstein 在 1966 年**首先提出。
|
||
|
||
**举例**：
|
||
```
|
||
S1: a:=x+y R(S1)={x,y}, W(S1)={a}
|
||
S2: b:=z+1 R(S2)={z}, W(S2)={b}
|
||
S3: c:=a-b R(S3)={a,b}, W(S3)={c}
|
||
S4: w:=c+1 R(S4)={c}, W(S4)={w}
|
||
```
|
||
- S1 与 S2 可并发（交集为空）；
|
||
- S1 与 S3 不可并发（W(S1) ∩ R(S3) = {a}）；
|
||
- S3 与 S4 不可并发（W(S3) ∩ R(S4) = {c}）。
|
||
|
||
---
|
||
|
||
#### 4.1.5 并发程序的表示
|
||
|
||
- **cobegin ... coend**：表示并发开始与结束。
|
||
- **parbegin ... parend**：同上（不同教材使用）。
|
||
|
||
操作系统遇到这些语句时，同时创建 n 个进程或线程分别执行 Si；当它们都结束时，并发语句结束。
|
||
|
||
---
|
||
|
||
#### 4.1.6 与时间有关的错误
|
||
|
||
**错误原因**：
|
||
1. **进程执行不正确的交叉（interleave）**；
|
||
2. **同时对一个公共变量操作**，其中一个进程的操作未结束，另一个进程也对公共变量进行操作，使公共变量处于不确定状态（**失去数据完整性**）。
|
||
|
||
**关键点**：
|
||
- 错误**不一定发生**，而**与进程的推进速度有关**（速度是时间的函数），所以叫"与时间有关的错误"。
|
||
- 必须**去掉导致不正确结果的交叉**。
|
||
|
||
**典型例 1：图书借阅系统（x：某种书册数，初始 x=1）**
|
||
|
||
```
|
||
终端 1 / 终端 2 都执行：IF x>=1 Then x:=x-1; 借书
|
||
```
|
||
两个终端同时判断 x>=1 都成功，都借书，x 变成 -1，违反数据完整性。
|
||
|
||
**典型例 2：就绪队列整队问题**
|
||
进程 A（优先级 2）、B（10）、C（30）、D（35）。插入 E（25）时执行：
|
||
```
|
||
R:=C; B:=E; E:=R
|
||
```
|
||
若插入过程中被 F（15）的唤醒中断，可能丢失一个就绪进程。
|
||
|
||
**典型例 3：两进程申请两个独占性资源**
|
||
```
|
||
P1: 申请打印机 → 申请输入机
|
||
P2: 申请输入机 → 申请打印机
|
||
```
|
||
若 P1 推进到申请打印机、P2 推进到申请输入机，两者均等待对方释放资源，形成**永久等待（死锁）**。
|
||
|
||
---
|
||
|
||
### 4.2 进程互斥（Mutual Exclusion）
|
||
|
||
#### 4.2.1 共享变量与临界区
|
||
|
||
- **共享变量（shared variable）**：多个进程都需要访问的变量。
|
||
- **临界区域（critical region）**：访问共享变量的程序段。
|
||
- 把临界区与其所对应的共享变量联系起来，称为**关于某一种共享变量的临界区**。
|
||
|
||
**表示法**：
|
||
```pascal
|
||
shared <一组变量>; {声明共享变量}
|
||
region <一组变量> do <语句>; {临界区}
|
||
```
|
||
|
||
**嵌套临界区**（被广泛考察的概念）：一个临界区内可以嵌套另一个临界区，内层临界区退出后，外层临界区继续执行。
|
||
|
||
---
|
||
|
||
#### 4.2.2 临界区域与进程互斥
|
||
|
||
**定义**：多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为**进程互斥**。
|
||
|
||
**两层含义**：
|
||
1. 任何时刻最多只能有一个进程处于**同一组共享变量的相同**临界区域；
|
||
2. 任何时刻最多只能有一个进程处于**同一组共享变量的不同**临界区域。
|
||
|
||
> 注意：互斥是**相对于公共变量**而言的。
|
||
|
||
---
|
||
|
||
#### 4.2.3 进程互斥的实现
|
||
|
||
**进程结构框架**：
|
||
```
|
||
Repeat
|
||
entry section {进入区}
|
||
critical section {临界区}
|
||
exit section {退出区}
|
||
remainder section {剩余区}
|
||
Until false
|
||
```
|
||
|
||
**临界区管理的三大原则（核心考点）**：
|
||
|
||
| 原则 | 英文 | 含义 |
|
||
|---|---|---|
|
||
| **互斥性** | Mutual Exclusion | 一次只允许一个进程进入关于同一组公共变量的临界区 |
|
||
| **进展性** | Progress | 临界区空闲时，放行一个进入者 |
|
||
| **有限等待** | Bounded Waiting | 一个想要进入临界区的进程，在等待有限个进程进入并离开临界区后获得进入临界区的机会 |
|
||
|
||
**易错点**：进展性 ≠ 有限等待。进展性保证不会无限制推卸决策；有限等待保证每个等待者最终都能进入。
|
||
|
||
---
|
||
|
||
##### 4.2.3.1 进程互斥的软件实现
|
||
|
||
完全用程序实现，不需特殊硬件指令支持；可用于单 CPU 和多 CPU 环境；存在**忙式等待（Busy Waiting）**问题。
|
||
|
||
**尝试 1（轮转法 turn）**：
|
||
```c
|
||
int turn; //初值 0
|
||
P0: do { while(turn==1); CS; turn=1; RS; } while(1);
|
||
P1: do { while(turn==0); CS; turn=0; RS; } while(1);
|
||
```
|
||
**缺点**：不满足进展性——P0、P1 必须交替进入临界区，若 P0 想进入两次而 P1 不想进入，则 P0 第二次进不去。
|
||
|
||
**尝试 2（标志法 flag）**：
|
||
```c
|
||
boolean flag[2]; //初值 false
|
||
P0: do { while(flag[1]); flag[0]=true; CS; flag[0]=false; RS; } while(1);
|
||
```
|
||
**缺点**：不满足互斥性——flag[0] = flag[1] = false 时两个进程可同时进入。
|
||
|
||
**尝试 3（先标志再检查）**：
|
||
```c
|
||
P0: do { flag[0]=true; while(flag[1]); CS; flag[0]=false; RS; } while(1);
|
||
```
|
||
**缺点**：不满足进展性——flag[0] = flag[1] = true 时双方都不能进入。
|
||
|
||
---
|
||
|
||
**Dekker 算法**（第一个解决互斥的软件算法，融合轮转与标志）：
|
||
|
||
```c
|
||
int flag[2]; //初值 0
|
||
int turn; //0 或 1
|
||
P0:
|
||
do {
|
||
flag[0]=1;
|
||
while(flag[1])
|
||
if(turn==1){
|
||
flag[0]=0;
|
||
while(turn==1) skip;
|
||
flag[0]=1;
|
||
}
|
||
CS;
|
||
turn=1;
|
||
flag[0]=0;
|
||
RS;
|
||
} while(1);
|
||
```
|
||
|
||
---
|
||
|
||
**Peterson 算法**（最经典、最常考的软件互斥算法）：
|
||
|
||
```c
|
||
boolean flag[2];
|
||
int turn;
|
||
P0:
|
||
do {
|
||
flag[0]=true; turn=1;
|
||
while(flag[1] && turn==1) skip;
|
||
CS;
|
||
flag[0]=false;
|
||
RS;
|
||
} while(1);
|
||
|
||
P1:
|
||
do {
|
||
flag[1]=true; turn=0;
|
||
while(flag[0] && turn==0) skip;
|
||
CS;
|
||
flag[1]=false;
|
||
RS;
|
||
} while(1);
|
||
```
|
||
|
||
**满足互斥性、进展性、有限等待性**。
|
||
**关键思想**：
|
||
- `flag[i]=true`：进程 i 想要进入；
|
||
- `turn`：当双方都想进入时，礼让给对方（最后写 turn 者将让权）。
|
||
- `flag[1] && turn==1`：对方想进入且对方礼让给我——则我进入；否则等待。
|
||
|
||
---
|
||
|
||
**Lamport 面包店算法**（Bakery Algorithm，多进程版本）：
|
||
|
||
**算法思想**：模拟面包店叫号——进程抓号，按号码顺序依次进入。
|
||
- 设发号者，按 0,1,2,... 发号。
|
||
- 问题：两个进程可能抓到相同的号 → 需要进程编号 tiebreaker。
|
||
- 排序：`(a,b) < (c,d)` iff `(a<c) or (a==c and b<d)`。
|
||
|
||
```c
|
||
boolean choosing[0..n-1]; //初值 false
|
||
int number[0..n-1]; //初值 0
|
||
|
||
Pi 进入：
|
||
1. choosing[i]=true;
|
||
2. number[i]=max{number[0],...,number[n-1]}+1;
|
||
3. choosing[i]=false;
|
||
4. for(j=0;j<n;j++){
|
||
5. while(choosing[j]) skip;
|
||
6. while(number[j]!=0 && (number[j],j)<(number[i],i)) skip;
|
||
7. }
|
||
|
||
Pi 离开：
|
||
number[i]=0;
|
||
```
|
||
|
||
**变量 choosing 的作用**：防止 P1 抓到 1 还未赋值时，P2 抓到 1 进入临界区，P1 再赋值 1 也进入——会破坏互斥。choosing[i]=true 期间表示 Pi 正在抓号。
|
||
|
||
**满足互斥性、进展性、有限等待性**——最坏情况下 Pi 将等待 n-1 个进程进入并离开。
|
||
|
||
---
|
||
|
||
**Eisenberg/McGuire 算法**（多进程、3 状态）：
|
||
|
||
```c
|
||
enum flag[0..n-1] = {idle, want_in, in_cs};
|
||
int turn; //0..n-1
|
||
|
||
Pi 进入:
|
||
do {
|
||
flag[i]=want_in;
|
||
j=turn;
|
||
while(j!=i)
|
||
if(flag[j]!=idle) j=turn;
|
||
else j=(j+1)%n;
|
||
flag[i]=in_cs;
|
||
j=0;
|
||
while(j<n && (j==i || flag[j]!=in_cs)) j++;
|
||
} while(j!=n);
|
||
turn=i;
|
||
|
||
Pi 离开:
|
||
j=(turn+1)%n;
|
||
while(flag[j]==idle) j=(j+1)%n;
|
||
turn=j;
|
||
flag[i]=idle;
|
||
```
|
||
|
||
**满足三原则**，最坏等待 n-1 个进程。
|
||
|
||
---
|
||
|
||
##### 4.2.3.2 进程互斥的硬件实现
|
||
|
||
**1. Test-and-Set 指令（TSL）**——原子指令，不可中断
|
||
|
||
```c
|
||
int test_and_set(int &target){
|
||
int temp;
|
||
temp = target;
|
||
*target = 1; {或 true}
|
||
return temp;
|
||
}
|
||
|
||
int lock = 0;
|
||
Pi 进入: while(test_and_set(&lock)) ; {忙等}
|
||
Pi 离开: lock=0;
|
||
```
|
||
|
||
**满足互斥性、进展性，不满足有限等待性**（忙等的进程可能饿死）。
|
||
|
||
**改进——满足有限等待性**：
|
||
```c
|
||
int waiting[n]; //初值 0
|
||
int lock; //初值 0
|
||
|
||
Pi 进入:
|
||
waiting[i]=1; key=1;
|
||
while(waiting[i] && key)
|
||
key=test_and_set(&lock);
|
||
waiting[i]=0;
|
||
CS;
|
||
j=(i+1)%n;
|
||
while(j!=i && !waiting[j]) j=(j+1)%n;
|
||
if(j==i) lock=0;
|
||
else waiting[j]=0;
|
||
RS;
|
||
```
|
||
|
||
---
|
||
|
||
**2. Swap 指令**——原子交换两个内存单元内容
|
||
|
||
```c
|
||
void swap(int &a, int &b){
|
||
int temp;
|
||
temp=*a; *a=*b; *b=temp;
|
||
}
|
||
|
||
int lock=0; int key;
|
||
Pi 进入: key=1;
|
||
do swap(&lock, &key) while(key==1);
|
||
Pi 离开: lock=0;
|
||
```
|
||
|
||
---
|
||
|
||
**3. 关中断/开中断指令**
|
||
|
||
```c
|
||
关中断;
|
||
临界区;
|
||
开中断;
|
||
```
|
||
|
||
**Remarks**：
|
||
- 开关中断**只在单 CPU 系统中有效**（多 CPU 各自开关，无法禁止其他 CPU）；
|
||
- 影响并发性（系统无法响应中断）；
|
||
- 关中断后代码必须很短，否则系统可能崩溃。
|
||
|
||
---
|
||
|
||
##### 4.2.4 多处理机环境下的互斥
|
||
|
||
**关键问题**：
|
||
- 单 CPU：指令间交叉，TS/Swap 指令是原子的；
|
||
- 多 CPU：**指令周期间交叉**，TS/Swap 指令**不是原子的**（总线上的读-写-读-写可能交错）。
|
||
|
||
**解决方案**：
|
||
```c
|
||
b=1;
|
||
while(b){
|
||
lock(bus);
|
||
b = test_and_set(&lock);
|
||
unlock(bus);
|
||
}
|
||
lock=0;
|
||
CS;
|
||
```
|
||
- 通过 **Bus 总线锁**（bus lock）实现真正的原子性。
|
||
- 现代总线（如 PCI）有 bus request protocol 支持锁总线；早期总线没有。
|
||
|
||
---
|
||
|
||
**经典 UNIX 互斥机制**：
|
||
- 关中断互斥（提高处理机优先级）；
|
||
- 简单、开销小、影响并发性；
|
||
- 关中断代码必须很短；
|
||
- SMP（对称多处理机）系统中改用**自旋锁（spin lock）**——TSL 指令 + 忙等。
|
||
|
||
---
|
||
|
||
### 4.3 进程同步
|
||
|
||
#### 4.3.1 进程同步的概念
|
||
|
||
**经典例子：司机-售票员问题**
|
||
```
|
||
司机： 售票员：
|
||
启动车辆 关车门
|
||
正常行驶 售 票
|
||
到站停车 开车门
|
||
```
|
||
- 司机须等售票员关车门后才能启动；
|
||
- 售票员须等司机到站停车后才能开车门。
|
||
|
||
**定义**：一组进程为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种**相互制约的关系**称为**进程同步**。
|
||
|
||
---
|
||
|
||
#### 4.3.2 进程同步机制
|
||
|
||
**定义**：用于实现进程同步的工具称为**同步机制（synchronization mechanism）**。
|
||
|
||
- **进程合作**：一组进程单独不能正常进行，但并发可以正常进行。
|
||
- **合作进程**：参与合作的进程。
|
||
|
||
**同步机制的要求**：
|
||
1. 描述能力够用；
|
||
2. 可实现；
|
||
3. 高效；
|
||
4. 使用方便。
|
||
|
||
**典型同步机制**：
|
||
| 机制 | 提出者/年代 |
|
||
|---|---|
|
||
| **信号量与 PV 操作** | Dijkstra, 1965 |
|
||
| **管程（Monitor）** | Dijkstra / Hoare / Hansen, 1970s |
|
||
| **会合（Rendezvous）** | Ada 语言 |
|
||
| **条件临界区（CCR）** | Hoare |
|
||
| **路径表达式** | Campbell / Habermann |
|
||
| **事件** | 传统 UNIX |
|
||
|
||
---
|
||
|
||
#### 4.3.3 信号量与 PV 操作
|
||
|
||
由 **E.W. Dijkstra** 于 **1965 年**提出（P、V 分别为荷兰语 Proberen=try、Verhogen=increment）。
|
||
|
||
##### 4.3.3.1 信号量与 PV 操作的定义
|
||
|
||
```c
|
||
typedef struct semaphore {
|
||
int value;
|
||
PCB *queue;
|
||
} semaphore;
|
||
semaphore s;
|
||
```
|
||
|
||
- `s.value` 表示资源数（或可用资源数）；
|
||
- `s.queue` 是 FIFO 等待队列。
|
||
|
||
---
|
||
|
||
##### P 操作原语
|
||
|
||
```c
|
||
void P(semaphore *s)
|
||
{
|
||
s->value--;
|
||
if (s->value < 0)
|
||
asleep(s->queue);
|
||
}
|
||
|
||
asleep(s->queue):
|
||
1. 执行此操作进程的 PCB 入 s->queue 尾（状态改为等待）；
|
||
2. 转处理机调度程序。
|
||
```
|
||
|
||
**P 是不可中断的原子原语（primitive）**。
|
||
|
||
---
|
||
|
||
##### V 操作原语
|
||
|
||
```c
|
||
void V(semaphore *s)
|
||
{
|
||
s->value++;
|
||
if (s->value <= 0)
|
||
wakeup(s->queue);
|
||
}
|
||
|
||
wakeup(s->queue):
|
||
1. s->queue 链头 PCB 出等待队列，进入就绪队列（状态改为就绪）。
|
||
```
|
||
|
||
---
|
||
|
||
##### 信号量规定与结论（高频考点）
|
||
|
||
**规定**：
|
||
- 必须置**一次初值**，只能置一次，初值 ≥ 0；
|
||
- **只能**执行 P 操作和 V 操作，其它操作非法。
|
||
|
||
**有用结论**：
|
||
| s->value 状态 | 含义 |
|
||
|---|---|
|
||
| s->value ≥ 0 | s->queue 为空，s->value = 实际剩余资源数 |
|
||
| s->value < 0 | \|s->value\| = 队列 s->queue 的长度（等待进程数） |
|
||
| 初值 = 1 | 可实现**进程互斥** |
|
||
| 初值 = 0 | 可实现**进程间简单同步** |
|
||
| 初值 > 1 的正整数 | 可管理**同种组合资源**（申请 P、归还 V） |
|
||
|
||
---
|
||
|
||
##### P、V 操作的实现方法
|
||
|
||
**方法 1：用开关中断实现（单 CPU）**
|
||
|
||
```c
|
||
void P(semaphore *s){
|
||
disable interrupt;
|
||
s->value--;
|
||
if (s->value < 0){
|
||
asleep(s->queue);
|
||
enable interrupt;
|
||
goto CPU dispatcher; //让出 CPU
|
||
} else
|
||
enable interrupt;
|
||
}
|
||
|
||
void V(semaphore *s){
|
||
disable interrupt;
|
||
s->value++;
|
||
if (s->value <= 0){
|
||
wakeup(s->queue);
|
||
enable interrupt;
|
||
} else
|
||
enable interrupt;
|
||
}
|
||
```
|
||
|
||
**方法 2：用 TS、Swap 指令实现（多 CPU 可用）**
|
||
|
||
```c
|
||
void P(semaphore *s){
|
||
while(TS(s->flag)) ; //忙等抢锁
|
||
s->value--;
|
||
if (s->value < 0){
|
||
asleep(s->queue);
|
||
s->flag=0;
|
||
goto CPU dispatcher;
|
||
} else
|
||
s->flag=0;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
##### 用信号量和 PV 实现进程互斥（最基本题型）
|
||
|
||
```c
|
||
Var mutex: semaphore; //初值 = 1
|
||
shared x,y,z: integer;
|
||
|
||
进程 Pi:
|
||
Pi(mutex);
|
||
CS; //临界区
|
||
V(mutex);
|
||
RS; //剩余区
|
||
```
|
||
|
||
**关键点**：
|
||
- mutex 初值必须为 1；
|
||
- 临界区前后成对使用 P(mutex)、V(mutex)；
|
||
- 必须配对，遗漏 P 或 V 都会出错。
|
||
|
||
---
|
||
|
||
##### 互斥例子：借书系统（改进版）
|
||
|
||
```c
|
||
Var mutex: semaphore; //初值 = 1
|
||
|
||
终端 1 / 终端 2 都执行:
|
||
CYCLE
|
||
等待借书者;
|
||
P(mutex);
|
||
IF x >= 1 Then
|
||
Begin
|
||
x := x - 1;
|
||
V(mutex);
|
||
借书
|
||
End
|
||
Else
|
||
Begin
|
||
V(mutex);
|
||
无书
|
||
End
|
||
End
|
||
```
|
||
|
||
---
|
||
|
||
##### 用信号量实现进程同步（典型题型）
|
||
|
||
**一般形式**：
|
||
```c
|
||
VAR S: semaphore; //初值 = 0
|
||
|
||
P1（先动作）:
|
||
...先动作...
|
||
V(S); //通知后动作
|
||
|
||
P2（后动作）:
|
||
P(S); //等待先动作完成
|
||
...后动作...
|
||
```
|
||
|
||
**司机-售票员问题解法**：
|
||
|
||
```c
|
||
VAR s1, s2: semaphore; //初值均为 0
|
||
|
||
司机: 售票员:
|
||
do { do {
|
||
P(s1); //等售票员关车门 关车门
|
||
启动车辆; V(s1); //通知司机
|
||
正常行驶; 售 票;
|
||
到站停车; P(s2); //等司机停车
|
||
V(s2); //通知售票员 开车门;
|
||
} while(1); } while(1);
|
||
```
|
||
|
||
**易错点**：
|
||
- s1、s2 都初始化为 0；
|
||
- "先"者执行 V，"后"者执行 P；
|
||
- 每个同步关系需要一个独立的信号量。
|
||
|
||
---
|
||
|
||
#### 经典同步问题
|
||
|
||
##### 例 1：生产者/消费者问题（最重要、最高频）
|
||
|
||
**预备知识**：
|
||
- **组合资源**：若干相对独立资源构成的资源集合，每个相对独立的资源称为**子资源**。
|
||
- **同种组合资源**：相同类型子资源构成的组合资源。
|
||
- 管理：Var S: semaphore;（初值 = 子资源个数）。
|
||
- 例：2 台打印机 → S.value = 2。
|
||
|
||
**自动机描述**：
|
||
- S.value 初值 = 空闲资源数；
|
||
- 每 P(S) 一次：分配一台，value 减 1；
|
||
- S.value = 0 后再 P(S)：等待进程数加 1（即 |S.value| = 等待进程数）；
|
||
- V(S)：归还资源，唤醒一个等待者，等待数减 1；否则空闲资源数加 1。
|
||
|
||
---
|
||
|
||
**问题描述**：
|
||
- 容量 k 的环形缓冲区 B[0..k-1]；
|
||
- 生产者放入 B，消费者从 B 取走；
|
||
- 多个生产者、多个消费者并发。
|
||
|
||
```
|
||
B[0..k-1] 容量 k（环形）
|
||
in: 生产者写指针
|
||
out: 消费者读指针
|
||
(in+1) mod k, (out+1) mod k
|
||
```
|
||
|
||
**资源信号量**：
|
||
- S1（empty）：箱子空闲位置，初值 = k；
|
||
- S2（full）：箱子中产品数，初值 = 0。
|
||
|
||
**互斥信号量**：
|
||
- mutex：对 B 和 in、out 操作的互斥，初值 = 1。
|
||
|
||
**完整解法（推荐背诵的标准答案）**：
|
||
|
||
```c
|
||
Program producers_consumers;
|
||
Var B: Array[0..k-1] of item;
|
||
S1, S2, mutex: semaphore;
|
||
in, out: 0..k-1;
|
||
|
||
Procedure producer;
|
||
begin
|
||
cycle
|
||
produce a product;
|
||
P(S1); //申请空位
|
||
P(mutex); //进入临界区
|
||
B[in] := product;
|
||
in := (in + 1) mod k;
|
||
V(mutex); //退出临界区
|
||
V(S2); //增加一个产品
|
||
end;
|
||
end;
|
||
|
||
Procedure consumer;
|
||
begin
|
||
cycle
|
||
P(S2); //申请产品
|
||
P(mutex); //进入临界区
|
||
x := B[out];
|
||
out := (out + 1) mod k;
|
||
V(mutex); //退出临界区
|
||
V(S1); //增加一个空位
|
||
consume x;
|
||
end;
|
||
end;
|
||
|
||
Begin
|
||
S1.value := k; S2.value := 0;
|
||
mutex.value := 1;
|
||
in := 0; out := 0;
|
||
Cobegin
|
||
P1: producer; ... Pm: producer;
|
||
C1: consumer; ... Cn: consumer;
|
||
Coend;
|
||
End.
|
||
```
|
||
|
||
**关键细节**：
|
||
- P(S1)、P(mutex) 顺序：**先资源后互斥**，可避免死锁；
|
||
- 若先 P(mutex) 再 P(S1)，当缓冲区满时生产者拿不到空位、又持有 mutex，可能死锁。
|
||
- V 操作的顺序无关紧要。
|
||
|
||
---
|
||
|
||
**并发性提高策略**：
|
||
- 生产者共享：B[in], in；
|
||
- 消费者共享：B[out], out；
|
||
- in = out 时满或空；
|
||
- 用 mutex1、mutex2 分别互斥：
|
||
```c
|
||
Producer: P(S1); P(mutex1); B[in]:=item; V(mutex1); V(S2);
|
||
Consumer: P(S2); P(mutex2); x:=B[out]; V(mutex2); V(S1);
|
||
```
|
||
|
||
---
|
||
|
||
##### 例 2：读者/写者问题（P. T. Courtois, 1971）
|
||
|
||
**问题陈述**：
|
||
- 一组公共数据 DB；
|
||
- 多个读者 R1..Rm、多个写者 W1..Wn；
|
||
- 要求：(1) R-R 可以同时；(2) R-W 不可同时；(3) W-W 不可同时。
|
||
|
||
---
|
||
|
||
**解法 1（不考虑 R-R 不互斥，简单）**：
|
||
|
||
```c
|
||
Var r_w_w: semaphore; //初值 = 1
|
||
Reader: P(r_w_w); {读} V(r_w_w);
|
||
Writer: P(r_w_w); {写} V(r_w_w);
|
||
```
|
||
缺点：R-R 不能同时（不必要的互斥）。
|
||
|
||
---
|
||
|
||
**解法 2（用 read_count 计数）**：
|
||
|
||
```c
|
||
Var read_count: integer; //初值 = 0
|
||
r_w_w: semaphore; //初值 = 1
|
||
Reader:
|
||
read_count := read_count + 1;
|
||
if read_count = 1 then P(r_w_w); //第一个读者
|
||
{读}
|
||
read_count := read_count - 1;
|
||
if read_count = 0 then V(r_w_w); //最后一个读者
|
||
```
|
||
**问题**：对 read_count 操作未互斥，多个读者同时 ++read_count 会出错。
|
||
|
||
---
|
||
|
||
**解法 3（标准正确解法）**：
|
||
|
||
```c
|
||
Var mutex: semaphore; //初值 = 1
|
||
r_w_w: semaphore; //初值 = 1
|
||
read_count: integer; //初值 = 0
|
||
|
||
Reader:
|
||
P(mutex);
|
||
read_count := read_count + 1;
|
||
if read_count = 1 then P(r_w_w); //首个读者锁
|
||
V(mutex);
|
||
{读}
|
||
P(mutex);
|
||
read_count := read_count - 1;
|
||
if read_count = 0 then V(r_w_w); //末个读者解锁
|
||
V(mutex);
|
||
|
||
Writer:
|
||
P(r_w_w);
|
||
{写}
|
||
V(r_w_w);
|
||
```
|
||
|
||
**易错点（高频考点）**：
|
||
- **读者等在何处？** 读者被阻塞在 `if read_count=1 then P(r_w_w)` 这一句；
|
||
- **写者等在何处？** 写者被阻塞在 `P(r_w_w)` 这一句；
|
||
- 读者在 `V(r_w_w)` 之后唤醒写者；
|
||
- **写者饿死问题**：若读者源源不断，read_count 始终 ≥ 1，写者永远拿不到 r_w_w → **写者饿死**。
|
||
|
||
**写者优先改进**（PPT 提到）：
|
||
- 一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入；
|
||
- 改进留给学生练习。
|
||
|
||
---
|
||
|
||
##### 例 3：哲学家就餐问题（Dining Philosophers, Dijkstra 1965）
|
||
|
||
**问题描述**：
|
||
- 5 位哲学家围坐圆桌；
|
||
- 5 把叉子，每两位之间一把；
|
||
- 哲学家思考-饿了-取左叉-取右叉-进食-放左叉-放右叉；
|
||
- 叉子为不同种组合资源。
|
||
|
||
**朴素解法（会引起死锁）**：
|
||
|
||
```c
|
||
var fork: array[0..4] of semaphore;
|
||
fork[0..4] := 1;
|
||
|
||
process PH(i):
|
||
repeat
|
||
think;
|
||
P(fork[i]); //取左叉
|
||
P(fork[(i+1) mod 5]); //取右叉
|
||
eat;
|
||
V(fork[i]);
|
||
V(fork[(i+1) mod 5]);
|
||
until false;
|
||
```
|
||
|
||
**死锁场景**：5 位哲学家同时拿起左叉，等待右叉——循环等待。
|
||
|
||
---
|
||
|
||
**死锁预防策略 1：限制最多 4 人就餐**
|
||
|
||
```c
|
||
var fork[0..4]: semaphore := 1;
|
||
count: semaphore := 4;
|
||
|
||
process PH(i):
|
||
repeat
|
||
think;
|
||
P(count);
|
||
P(fork[i]);
|
||
P(fork[(i+1) mod 5]);
|
||
eat;
|
||
V(fork[i]);
|
||
V(fork[(i+1) mod 5]);
|
||
V(count);
|
||
until false;
|
||
```
|
||
最多 4 个哲学家竞争 5 把叉子，必有一人能拿到两把。
|
||
|
||
---
|
||
|
||
**死锁预防策略 2：AND 型信号量（同时申请两把叉）**
|
||
|
||
详见下节 SP/SV 操作。
|
||
|
||
---
|
||
|
||
**死锁预防策略 3：管程解法——状态机法**
|
||
|
||
**数据结构**：
|
||
- `state[I]`：哲学家的状态（thinking / hungry / eating）；
|
||
- `self[I]`：每个哲学家一个信号量，初值 = 0（用于阻塞自身）。
|
||
|
||
**测试函数**：
|
||
```c
|
||
Procedure test(I: 0..4);
|
||
begin
|
||
if (state[I]=hungry) and
|
||
(state[(I-1) mod 5] <> eating) and
|
||
(state[(I+1) mod 5] <> eating) then
|
||
begin
|
||
state[I] := eating;
|
||
V(self[I]); //唤醒自己
|
||
end;
|
||
end;
|
||
```
|
||
|
||
**哲学家活动**：
|
||
```c
|
||
Process philosopher(I);
|
||
begin
|
||
repeat
|
||
think;
|
||
P(mutex);
|
||
state[I] := hungry;
|
||
test(I);
|
||
V(mutex);
|
||
P(self[I]); //等待获准
|
||
pick_up_fork(I);
|
||
pick_up_fork((I+1) mod 5);
|
||
eat;
|
||
put_down_fork(I);
|
||
put_down_fork((I+1) mod 5);
|
||
P(mutex);
|
||
state[I] := thinking;
|
||
test((I-1) mod 5);
|
||
test((I+1) mod 5);
|
||
V(mutex);
|
||
until false;
|
||
end;
|
||
```
|
||
|
||
**易错点**：临界区域是 `state[I]:=hungry; test(I);` 和 `state[I]:=thinking; test(left); test(right);`——必须用 mutex 保护。
|
||
|
||
**仍可能饿死**：某哲学家左右邻居轮流处于 eating 状态，自己永远 hungry——**仍可能饥饿，但不会死锁**。
|
||
|
||
---
|
||
|
||
##### 例 4：吸烟者问题（Cigarette Smokers' Problem, Patil 1977）
|
||
|
||
**问题陈述**：
|
||
- 3 个供应者 X、Y、Z：
|
||
- X：供应 tobacco 和 match；
|
||
- Y：供应 match 和 wrapper；
|
||
- Z：供应 wrapper 和 tobacco。
|
||
- 3 个吸烟者 A、B、C：
|
||
- A：拥有 tobacco；
|
||
- B：拥有 match；
|
||
- C：拥有 wrapper。
|
||
- 规则：(1) 三个供应者之一每次供应一组原料；(2) 上一组被消费完，下一组才能供应。
|
||
|
||
**AND 型信号量（SP/SV）解法**：
|
||
|
||
```c
|
||
shared t, w, m: semaphore; //tobacco, wrapper, match
|
||
s: semaphore; //初值 = 1（互斥供应者）
|
||
|
||
Process X (供应 tobacco & match):
|
||
loop
|
||
P(s);
|
||
SV(t,1; m,1);
|
||
endloop
|
||
|
||
Process Y (供应 match & wrapper):
|
||
loop
|
||
P(s);
|
||
SV(m,1; w,1);
|
||
endloop
|
||
|
||
Process Z (供应 wrapper & tobacco):
|
||
loop
|
||
P(s);
|
||
SV(w,1; t,1);
|
||
endloop
|
||
|
||
Process A (拥有 tobacco):
|
||
loop
|
||
SP(m,1,1; w,1,1); //同时申请 match 和 wrapper
|
||
smoke;
|
||
V(s);
|
||
endloop
|
||
|
||
Process B (拥有 match):
|
||
loop
|
||
SP(w,1,1; t,1,1); //同时申请 wrapper 和 tobacco
|
||
smoke;
|
||
V(s);
|
||
endloop
|
||
|
||
Process C (拥有 wrapper):
|
||
loop
|
||
SP(t,1,1; m,1,1); //同时申请 tobacco 和 match
|
||
smoke;
|
||
V(s);
|
||
endloop
|
||
```
|
||
|
||
---
|
||
|
||
##### AND 型信号量与 SP/SV 操作（重要扩展）
|
||
|
||
**SP（Simultaneous P）**：
|
||
```c
|
||
SP(S1,t1,d1; ... ; Sn,tn,dn);
|
||
if S1>=t1 and ... and Sn>=tn then
|
||
for I:=1 to n do Si := Si - di endfor;
|
||
else
|
||
1. 将执行进程放入第一个 Si<ti 的等待队列；
|
||
2. 程序计数器置回 SP 开始处，再次检测。
|
||
```
|
||
|
||
**SV（Simultaneous V）**：
|
||
```c
|
||
SV(S1,d1; ... ; Sn,dn);
|
||
for I:=1 to n do Si := Si + di endfor;
|
||
将所有相关等待队列的进程唤醒到就绪队列。
|
||
```
|
||
|
||
当 ti、di 都为 1 时，称为 **AND 型信号量**（最常用）。可解决哲学家问题中"同时取两把叉"的死锁。
|
||
|
||
---
|
||
|
||
##### 例 5：生产线问题（组合资源同步）
|
||
|
||
- 工人 1 加工车架，工人 2 加工车轮，工人 3 组装（一车架 + 两车轮）；
|
||
- 容量 k 的箱子。
|
||
|
||
**信号量**：
|
||
- empty：初值 = k（空位）；
|
||
- frame：初值 = 0（车架数）；
|
||
- wheel：初值 = 0（车轮数）；
|
||
- S1（车架数限制）：初值 = k-2；
|
||
- S2（车轮数限制）：初值 = 2(k-1)。
|
||
|
||
```c
|
||
工人1: 工人2:
|
||
加工一个车架; 加工一个车轮;
|
||
P(S1); P(S2);
|
||
P(empty); P(empty);
|
||
车架放入箱中; 车轮放入箱中;
|
||
V(frame); V(wheel);
|
||
while(1); while(1);
|
||
|
||
工人3:
|
||
P(frame);
|
||
箱中取一车架;
|
||
V(empty); V(S1);
|
||
P(wheel); P(wheel);
|
||
箱中取二车轮;
|
||
V(empty); V(empty); V(S2); V(S2);
|
||
组装;
|
||
while(1);
|
||
```
|
||
|
||
**死锁分析**：
|
||
- 若不限制，可能 K 个车轮和 K 个车架都堆积，工人 3 等不到组合 → 死锁；
|
||
- 防止：车架不超过 k-2（s1），车轮不超过 2(k-1)（s2）。
|
||
|
||
---
|
||
|
||
##### 例 6：资源调度问题（三组进程互斥使用资源 R）
|
||
|
||
- A、B、C 三组进程互斥使用资源 R；
|
||
- 一组申请时：直接使用；
|
||
- 两组申请时：组间交替，组内依次；
|
||
- 三组申请时：组间轮流，组内依次。
|
||
|
||
```c
|
||
int free = 1; //资源空闲标志
|
||
semaphore mutex = 1;
|
||
semaphore qa, qb, qc = 0, 0, 0;
|
||
int counta, countb, countc = 0;
|
||
|
||
A 申请:
|
||
P(mutex);
|
||
if (free == 1) { free = 0; V(mutex); }
|
||
else { counta++; V(mutex); P(qa); }
|
||
|
||
A 释放:
|
||
P(mutex);
|
||
if (countb > 0) { countb--; V(qb); }
|
||
else if (countc > 0) { countc--; V(qc); }
|
||
else if (counta > 0) { counta--; V(qa); }
|
||
else free = 1;
|
||
V(mutex);
|
||
```
|
||
|
||
---
|
||
|
||
##### 例 7：系统与网络打印机（2009 考研真题类似题）
|
||
|
||
- 网络打印机：网络用户专用；
|
||
- 系统打印机：系统用户专用，空闲时可被网络用户使用；
|
||
- 网络打印机释放后，优先唤醒系统等待者。
|
||
|
||
---
|
||
|
||
##### 例 8：2009 考研真题——奇偶消费者问题
|
||
|
||
**题目**：三个进程 P1、P2、P3 互斥使用一个 N 单元的缓冲区。P1 用 produce() 产生一个正数并用 put() 放入缓冲区；P2 用 getodd() 取奇数并 countodd()；P3 用 geteven() 取偶数并 counteven()。
|
||
|
||
```c
|
||
semaphore empty = N; //空位
|
||
semaphore odd = 0; //奇数个数
|
||
semaphore even = 0; //偶数个数
|
||
semaphore mutex = 1; //互斥
|
||
|
||
P1: P2: P3:
|
||
n = produce(); P(odd); P(even);
|
||
P(empty); P(mutex); P(mutex);
|
||
P(mutex); getodd(); geteven();
|
||
put(); V(mutex); V(mutex);
|
||
V(mutex); V(empty); V(empty);
|
||
if (n % 2 == 0) V(even); countodd(); counteven();
|
||
else V(odd); while(true); while(true);
|
||
while(true);
|
||
```
|
||
|
||
**信号量含义**：
|
||
- empty：缓冲区空位数；
|
||
- odd：缓冲区中奇数个数；
|
||
- even：缓冲区中偶数个数；
|
||
- mutex：对缓冲区操作的互斥。
|
||
|
||
---
|
||
|
||
##### 例 9：寺庙问题（小和尚打水，老和尚喝水）
|
||
|
||
- 缸容量 30 桶，入水取水每次 1 桶，不可同时；
|
||
- 井口每次 1 个桶取水；
|
||
- 5 只水桶共用。
|
||
|
||
```c
|
||
semaphore empty = 30; //缸容量
|
||
semaphore full = 0; //缸中水量
|
||
semaphore bucket = 5; //水桶数
|
||
semaphore mutex_bigjar = 1; //缸互斥
|
||
semaphore mutex_well = 1; //井互斥
|
||
|
||
小和尚 young_monk():
|
||
P(empty); //申请空位
|
||
P(bucket); //申请水桶
|
||
走到井边;
|
||
P(mutex_well);
|
||
井中取水;
|
||
V(mutex_well);
|
||
走到寺庙;
|
||
P(mutex_bigjar);
|
||
水入缸中;
|
||
V(mutex_bigjar);
|
||
V(bucket);
|
||
V(full);
|
||
|
||
老和尚 old_monk():
|
||
P(full);
|
||
P(bucket);
|
||
P(mutex_bigjar);
|
||
缸中取水;
|
||
V(mutex_bigjar);
|
||
喝水;
|
||
V(bucket);
|
||
V(empty);
|
||
```
|
||
|
||
**死锁分析**：P 操作顺序不当会引起死锁。
|
||
- 上述解法是**无死锁解法**；
|
||
- 若先 P(bucket) 再 P(empty)，多进程并发时可能死锁（所有人都拿着桶，缸满了也进不去）。
|
||
|
||
---
|
||
|
||
#### 4.3.4 条件临界区（Conditional Critical Region, CCR）
|
||
|
||
**背景**：PV 操作低级，容易用错。
|
||
|
||
**形式**：
|
||
```pascal
|
||
region V when B do S
|
||
```
|
||
- 执行 S 的条件：没有其它进程处于与 V 相关的条件临界区中（即互斥），且进入时 B 为 true。
|
||
|
||
**等价性**：
|
||
- CCR 与 PV 操作等价（证明从略）；
|
||
- 用 CCR 可实现 PV；
|
||
- 用 PV 也可实现 CCR；
|
||
- 由 **P. B. Hansen** 设计的 Edison 语言首先提供 CCR 同步机制。
|
||
|
||
**实现效率问题**：
|
||
- 条件表达式 B 包含进程局部信息，每个进入 CCR 的进程必须自己计算 B；
|
||
- 在入口形成等待队列；
|
||
- 离开时全局变量变化可能使某些 B 变 true，需唤醒等待进程重算 B；
|
||
- 重算结果可能仍为 false，进程将重新回到等待状态——本质上也是**忙式等待**。
|
||
|
||
**简单批处理例子**：
|
||
- reader / executer / printer 三进程，inbuff、outbuff 两个缓冲区。
|
||
|
||
```pascal
|
||
PROCESS reader;
|
||
LOOP
|
||
Read card;
|
||
REGION ib WHEN inbuff.size < n DO
|
||
inbuff.slots[inbuff.tail] := card;
|
||
inbuff.size := inbuff.size + 1;
|
||
inbuff.tail := (inbuff.tail + 1) MOD n;
|
||
END
|
||
ENDLOOP;
|
||
```
|
||
|
||
---
|
||
|
||
#### 4.3.5 管程（Monitor）
|
||
|
||
**PV 操作的局限**：
|
||
- **分散式同步机制**：共享变量操作、PV 操作分散在整个系统或各个进程中。
|
||
- 缺点：可读性差、正确性不易保证、不易修改；
|
||
- 优点：高效、灵活。
|
||
|
||
**管程的优势**：
|
||
- **集中式同步工具**：共享变量及其所有相关操作集中在一个模块中。
|
||
- 优点：可读性好、正确性易于保证、易于修改；
|
||
- 缺点：不甚灵活、效率略低。
|
||
|
||
**历史**：70 年代初由 E.W. Dijkstra、C.A.R. Hoare、P.B. Hansen 提出。
|
||
|
||
**基于管程的语言**：Concurrent Pascal（Hansen）、Modula、Mod*、Mesa、Concurrent Euclid、XCY、Java（synchronized method）。
|
||
|
||
---
|
||
|
||
##### 4.3.5.2 管程形式
|
||
|
||
```pascal
|
||
Type monitor_name = MONITOR(形参表)
|
||
共享变量说明;
|
||
define 本管程内定义、本管程外使用的子程序名表;
|
||
use 本管程外定义、本管程内使用的子程序名表;
|
||
|
||
Procedure 过程名(形参表);
|
||
局部变量说明;
|
||
Begin 语句序列 End;
|
||
|
||
Function 函数名(形参表): 返回值类型;
|
||
局部变量说明;
|
||
Begin 语句序列 End;
|
||
|
||
Begin 共享变量初始化语句序列 End;
|
||
```
|
||
|
||
**语言特点**：
|
||
1. 模块化（modularized）；
|
||
2. 抽象数据类型（abstract data type）；
|
||
3. 信息隐藏（information hiding）。
|
||
|
||
---
|
||
|
||
##### 4.3.5.3 管程语义
|
||
|
||
1. 管程的共享变量在管程外部不可见，外部只能通过调用管程中的外部子程序访问共享变量；
|
||
2. **为保证对共享变量操作的数据完整性，规定管程互斥进入**；
|
||
3. 管程中有等待/唤醒机制。
|
||
|
||
**三种唤醒语义（高频考点）**：
|
||
|
||
| 语义 | 名称 | 行为 |
|
||
|---|---|---|
|
||
| **Hoare 语义** | Signal and urgent wait | P 紧急等待，Q 继续，直到 Q 退出或等待 |
|
||
| **Java 语义** | Signal and continue | Q 等待，P 继续，直到 P 退出或等待 |
|
||
| **Hansen 语义** | Signal and leave | 唤醒是管程中可执行的最后一个操作 |
|
||
|
||
**Hoare 管程设施**：
|
||
- **入口等待队列**：每个管程一个，用于排队进入；
|
||
- **紧急等待队列**：每个管程一个，用于唤醒等待；
|
||
- **内部等待队列**：`var c: condition;`，可根据需要定义多个条件变量。
|
||
|
||
**条件变量操作**：
|
||
|
||
```c
|
||
wait(c):
|
||
如紧急队列非空，唤醒第一个等待者；否则释放管程互斥权；
|
||
执行此操作的进程进入 c 链尾。
|
||
|
||
signal(c):
|
||
如 c 链空，相当空操作；
|
||
否则唤醒第一个等待者，执行此操作的进程进入紧急队列。
|
||
```
|
||
|
||
---
|
||
|
||
##### 4.3.5.4 管程的使用——典型例子
|
||
|
||
**例 1：生产者/消费者管程**
|
||
|
||
```pascal
|
||
Type producer_consumer = MONITOR;
|
||
Var B: Array[0..n-1] of integer;
|
||
count, in, out: integer;
|
||
pq, cq: condition;
|
||
define put_in, get_out;
|
||
|
||
Procedure put_in(item: integer);
|
||
Begin
|
||
if (count == n) then wait(pq); //满则等
|
||
B[in] := item;
|
||
in := (in + 1) mod n;
|
||
count := count + 1;
|
||
signal(cq); //唤醒消费者
|
||
End;
|
||
|
||
Procedure get_out(var item: integer);
|
||
Begin
|
||
if (count == 0) then wait(cq); //空则等
|
||
item := B[out];
|
||
out := (out + 1) mod n;
|
||
count := count - 1;
|
||
signal(pq); //唤醒生产者
|
||
End;
|
||
|
||
Begin
|
||
in := 0; out := 0; count := 0;
|
||
End;
|
||
```
|
||
|
||
**例 2：读者/写者管程（写者优先）**
|
||
|
||
```pascal
|
||
Type readers_writers = MONITOR;
|
||
Var rq, wq: condition;
|
||
reading_count, write_count: integer;
|
||
|
||
Procedure start_read;
|
||
Begin
|
||
if (write_count > 0) then wait(rq);
|
||
reading_count := reading_count + 1;
|
||
signal(rq);
|
||
End;
|
||
|
||
Procedure finish_read;
|
||
Begin
|
||
reading_count := reading_count - 1;
|
||
if (reading_count = 0) then signal(wq);
|
||
End;
|
||
|
||
Procedure start_write;
|
||
Begin
|
||
write_count := write_count + 1;
|
||
if (write_count > 1) or (reading_count > 0)
|
||
then wait(wq);
|
||
End;
|
||
|
||
Procedure finish_write;
|
||
Begin
|
||
write_count := write_count - 1;
|
||
if (write_count > 0) then signal(wq)
|
||
else signal(rq);
|
||
End;
|
||
```
|
||
|
||
**例 3：哲学家就餐管程解法**
|
||
|
||
```pascal
|
||
Type dining_philosophers = MONITOR;
|
||
Var fork: array[0..4] of (free, used);
|
||
q: array[0..4] of condition;
|
||
|
||
Procedure pick_up(I: 0..4);
|
||
Begin
|
||
if fork[I] = used then wait(q[I]);
|
||
fork[I] := used;
|
||
End;
|
||
|
||
Function try_pick_up(I: 0..4): boolean;
|
||
Begin
|
||
if fork[I] = used then try_pick_up := false
|
||
else Begin fork[I] := used; try_pick_up := true End;
|
||
End;
|
||
|
||
Procedure put_down(I: 0..4);
|
||
Begin
|
||
fork[I] := free;
|
||
signal(q[I]);
|
||
End;
|
||
|
||
Procedure init;
|
||
Begin
|
||
for I := 0 to 4 do fork[I] := free;
|
||
End;
|
||
|
||
I 号哲学家活动:
|
||
repeat
|
||
{thinking}
|
||
with_two_forks := false;
|
||
repeat
|
||
forks.pick_up(I);
|
||
if forks.try_pick_up((I+1) mod 5) then
|
||
with_two_forks := true
|
||
else forks.put_down(I);
|
||
until with_two_forks;
|
||
{eating}
|
||
forks.put_down(I);
|
||
forks.put_down((I+1) mod 5);
|
||
until false;
|
||
```
|
||
|
||
**例 4：磁盘引臂调度（SCAN 算法）**
|
||
|
||
```pascal
|
||
Type diskhead = MONITOR;
|
||
Var busy: boolean;
|
||
headpos: 0..199;
|
||
direction: (up, down);
|
||
cylinder: array[0..199] of condition;
|
||
count: array[0..199] of integer;
|
||
|
||
Procedure require(dest: 0..199);
|
||
Begin
|
||
if busy then Begin
|
||
count[dest] := count[dest] + 1;
|
||
wait(cylinder[dest]);
|
||
End;
|
||
busy := true;
|
||
if dest < headpos then direction := down
|
||
else if dest > headpos then direction := up;
|
||
headpos := dest;
|
||
End;
|
||
|
||
Procedure release;
|
||
Begin
|
||
busy := false;
|
||
if direction = up then Begin upscan; downscan End
|
||
else Begin downscan; upscan End;
|
||
End;
|
||
```
|
||
|
||
**例 5：嗜眠理发师问题**
|
||
|
||
```pascal
|
||
Type sleepybarber = MONITOR;
|
||
Var chair: condition;
|
||
stool: condition;
|
||
count: 0..n+1;
|
||
|
||
Procedure sleep;
|
||
Begin
|
||
if count = 0 then wait(chair);
|
||
End;
|
||
|
||
Procedure enter(var full: boolean);
|
||
Begin
|
||
if count = n+1 then full := true
|
||
else Begin
|
||
full := false;
|
||
count := count + 1;
|
||
if count = 1 then signal(chair) //叫醒理发师
|
||
else wait(stool);
|
||
End;
|
||
End;
|
||
|
||
Procedure leave;
|
||
Begin
|
||
count := count - 1;
|
||
if count <> 0 then signal(stool);
|
||
End;
|
||
|
||
理发师:
|
||
repeat
|
||
sleepybarber.sleep;
|
||
cuthair;
|
||
until false;
|
||
|
||
顾客:
|
||
repeat
|
||
sleepybarber.enter(full);
|
||
until not full;
|
||
cuthair;
|
||
sleepybarber.leave;
|
||
```
|
||
|
||
**例 6：单一资源管理**
|
||
|
||
```pascal
|
||
Type single_resource = MONITOR;
|
||
Var busy: boolean; q: condition;
|
||
Procedure require;
|
||
Begin if busy then wait(q); busy := true End;
|
||
Procedure release;
|
||
Begin busy := false; signal(q); End;
|
||
Begin busy := false End;
|
||
```
|
||
|
||
---
|
||
|
||
##### 4.3.5.5 管程与 PV 操作的等价性
|
||
|
||
**用管程构造 PV 操作**：
|
||
|
||
```pascal
|
||
Type semaphore = MONITOR(init_value);
|
||
Var c: condition;
|
||
count: integer;
|
||
define P, V;
|
||
|
||
Procedure P;
|
||
Begin
|
||
count := count - 1;
|
||
if count < 0 then wait(c);
|
||
End;
|
||
|
||
Procedure V;
|
||
Begin
|
||
count := count + 1;
|
||
if count <= 0 then signal(c);
|
||
End;
|
||
|
||
Begin
|
||
count := init_value;
|
||
End;
|
||
```
|
||
|
||
**用 PV 操作构造管程**：
|
||
|
||
| 管程成分 | 信号灯实现 |
|
||
|---|---|
|
||
| 入口等待 | mutex: semaphore(1) |
|
||
| 紧急等待 | urgent: semaphore(0); urgent_count: integer(0) |
|
||
| 条件变量 c | s: semaphore(0); count: integer(0) |
|
||
| wait(c) | count++; if urgent_count>0 then urgent_count--; V(urgent) else V(mutex); P(s); |
|
||
| signal(c) | if count>0 then count--; urgent_count++; V(s); P(urgent); |
|
||
| 进入管程 | P(mutex) |
|
||
| 离开管程 | if urgent_count>0 then urgent_count--; V(urgent) else V(mutex); |
|
||
|
||
---
|
||
|
||
##### 4.3.5.6 管程的嵌套调用问题
|
||
|
||
**问题**：1. 是否允许嵌套；2. 若允许，如何处理互斥权。
|
||
|
||
**方法**：
|
||
1. **禁止嵌套**（Modula）；
|
||
2. **允许嵌套，等待时释放当前管程互斥权**（CPASCAL）；
|
||
3. **允许嵌套，等待时释放所有管程互斥权**；
|
||
4. **允许嵌套，调用时释放路径上管程互斥权**。
|
||
|
||
---
|
||
|
||
##### Java 语言中的"管程"
|
||
|
||
- Java 的 `synchronized method` 启用了对象的互斥锁（lock）；
|
||
- 每个对象内部有一个**等待队列（wait set）**；
|
||
- `wait()`：释放 lock，状态改为 blocked，进入 wait set；
|
||
- `notify()`：从 wait set 中选一个移到 entry set，状态改为 runnable（Signal and continue 语义）；
|
||
- `notifyAll()`：wait set 全部移到 entry set。
|
||
|
||
**Entry set 与 Wait set 的关系**：
|
||
- 锁的持有者执行 wait：状态 blocked、释放锁、入 wait set；若 entry set 非空，选其一进入同步方法；
|
||
- 锁的持有者执行 notify：任选 wait set 一线程入 entry set，状态 runnable；
|
||
- 锁的持有者执行 notifyAll：wait set 所有线程入 entry set，状态 runnable。
|
||
|
||
**Java 实现生产者/消费者**：
|
||
|
||
```java
|
||
public synchronized void enter(Object item) {
|
||
while (count == BUFFER_SIZE) {
|
||
try { wait(); } catch (InterruptedException e) { }
|
||
}
|
||
++count;
|
||
buffer[in] = item;
|
||
in = (in + 1) % BUFFER_SIZE;
|
||
notify();
|
||
}
|
||
|
||
public synchronized Object remove() {
|
||
while (count == 0) {
|
||
try { wait(); } catch (InterruptedException e) { }
|
||
}
|
||
--count;
|
||
item = buffer[out];
|
||
out = (out + 1) % BUFFER_SIZE;
|
||
notify();
|
||
return item;
|
||
}
|
||
```
|
||
|
||
**Java 同步规则**：
|
||
1. 拥有对象锁的线程可进入同一对象的另一个 synchronized 方法；
|
||
2. 方法可嵌套不同对象的 synchronized 方法调用；
|
||
3. 非 synchronized 方法任何时候都可被调用；
|
||
4. wait set 为空时 notify() / notifyAll() 无效。
|
||
|
||
---
|
||
|
||
### Windows 10 互斥同步机制（扩展知识）
|
||
|
||
| 机制 | 主要 API |
|
||
|---|---|
|
||
| **Mutex** | CreateMutex, OpenMutex, ReleaseMutex |
|
||
| **Semaphore** | CreateSemaphore, OpenSemaphore, ReleaseSemaphore |
|
||
| **Event** | CreateEvent, OpenEvent, SetEvent, ResetEvent, PulseEvent |
|
||
| **CRITICAL_SECTION** | InitializeCriticalSection, EnterCriticalSection, TryEnterCriticalSection, LeaveCriticalSection, DeleteCriticalSection |
|
||
|
||
- CRITICAL_SECTION 是用户态互斥，不进入内核，速度快；
|
||
- TryEnterCriticalSection 非阻塞，失败返回 0；
|
||
- Mutex 是内核对象，跨进程可用。
|
||
|
||
---
|
||
|
||
## 二、考点总结
|
||
|
||
### 考点 1：前趋图（Precedence Graph）
|
||
- **内容**：有向无环图表示语句/进程间偏序关系 → = {(Pi, Pj) | Pj 启动前 Pi 已完成}。
|
||
- **考查方式**：选择、填空、应用（画前趋图）。
|
||
- **可能的题目**：
|
||
1. 前趋图能描述进程间的什么关系？**答：偏序（前趋）关系，反映进程的执行顺序约束**。
|
||
|
||
---
|
||
|
||
### 考点 2：顺序程序 vs 并发程序的特性对比
|
||
- **内容**：
|
||
- 顺序程序：连续性、封闭性、可再现性。
|
||
- 并发程序：间断性、非封闭性、不可再现性。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. 并发程序失去了顺序程序的哪些特性？**答：失去封闭性和可再现性（连续性变为间断性）**。
|
||
|
||
---
|
||
|
||
### 考点 3：Bernstein 条件
|
||
- **内容**：R(p1)∩W(p2) ∪ R(p2)∩W(p1) ∪ W(p1)∩W(p2) = Φ 是可并发执行并保持可再现性的充分条件。
|
||
- **考查方式**：填空、应用（判断两条语句能否并发）。
|
||
- **可能的题目**：
|
||
1. S1: a:=x+y，R(S1)={x,y} W(S1)={a}；S2: b:=z+1，R(S2)={z} W(S2)={b}。判断能否并发。**答：可以，因为 R(S1)∩W(S2)=R(S2)∩W(S1)=W(S1)∩W(S2)=Φ**。
|
||
|
||
---
|
||
|
||
### 考点 4：与时间有关的错误
|
||
- **内容**：错误与进程推进速度有关，速度是时间的函数；典型错误包括丢失更新（read-modify-write）、死锁（永久等待）、数据完整性丧失。
|
||
- **考查方式**：选择、简答。
|
||
- **可能的题目**：
|
||
1. 试举两个与时间有关的错误的例子。**答：(1) 借书系统中两个终端同时借书使 x 变成负数；(2) 两进程交叉申请打印机和输入机形成永久等待**。
|
||
|
||
---
|
||
|
||
### 考点 5：临界区管理三原则（最核心）
|
||
- **内容**：互斥性（mutual exclusion）、进展性（progress）、有限等待（bounded waiting）。
|
||
- **考查方式**：选择、填空、判断（分析某算法是否满足三原则）。
|
||
- **可能的题目**：
|
||
1. 判断尝试 1（turn 轮转）是否满足三原则。**答：满足互斥性，但不满足进展性（P0 想连续进两次而 P1 不想进时，P0 第二次进不去）**。
|
||
2. 判断 Peterson 算法是否满足三原则。**答：满足互斥性、进展性、有限等待性**。
|
||
|
||
---
|
||
|
||
### 考点 6：Peterson 算法
|
||
- **内容**：用 flag[2] + turn 实现的经典两进程互斥算法。关键技巧是"先举手后让权"——`flag[i]=true; turn=j;`，然后等"对方没举手 或 对方没让给我"。
|
||
- **考查方式**：选择、应用（填空实现）、画图。
|
||
- **可能的题目**：
|
||
1. Peterson 算法中 `flag[0]=true; turn=1;` 后 `while(flag[1] && turn==1)` 含义是什么？**答：表示对方 P1 想要进入且对方礼让给我（P1 把 turn 写为 1），则我等待；否则我进入临界区**。
|
||
|
||
---
|
||
|
||
### 考点 7：Lamport 面包店算法
|
||
- **内容**：抓号 + 进程编号 tiebreaker；choosing 防止抓号冲突；满足三原则。
|
||
- **考查方式**：简答、应用（多进程互斥）。
|
||
- **可能的题目**：
|
||
1. Lamport 面包店算法中变量 choosing 的作用是什么？**答：标记 Pi 正在抓号过程中，防止其他进程在 number[i] 未赋值前读到旧值而出现重复抓号，进而破坏互斥性**。
|
||
|
||
---
|
||
|
||
### 考点 8：硬件互斥指令（TSL、Swap）
|
||
- **内容**：test_and_set 和 swap 都是原子指令；TS 满足互斥和进展，但简单版本不满足有限等待；改进版加 waiting 数组后满足三原则；多 CPU 下必须锁总线。
|
||
- **考查方式**：选择、填空、判断。
|
||
- **可能的题目**：
|
||
1. 简述关中断实现互斥的局限性。**答：(1) 仅适用于单 CPU；(2) 关中断期间系统不响应中断，影响并发性；(3) 关中断代码必须极短**。
|
||
2. 多 CPU 环境下 test_and_set 指令为什么不是原子的？**答：因为读-写内存操作分两个总线周期完成，多 CPU 之间可能交叉，两 CPU 同时读到 0 后都置 1，破坏互斥**。
|
||
|
||
---
|
||
|
||
### 考点 9：信号量初值与语义
|
||
- **内容**：
|
||
- s.value ≥ 0：s.queue 空，s.value 等于剩余资源数；
|
||
- s.value < 0：|s.value| 等于等待进程数；
|
||
- 初值 = 1：互斥；
|
||
- 初值 = 0：简单同步；
|
||
- 初值 > 1：管理同种组合资源。
|
||
- **考查方式**：填空、简答。
|
||
- **可能的题目**：
|
||
1. 信号量初值为 0 时的作用。**答：用于实现进程间的简单同步（先做者 V、后做者 P）**。
|
||
2. 信号量初值 = 1 时 s.value = -3 的含义。**答：有 3 个进程在该信号量队列上等待**。
|
||
|
||
---
|
||
|
||
### 考点 10：P/V 操作实现互斥与同步（必考大题）
|
||
- **内容**：
|
||
- 互斥模板：mutex 初值 = 1，CS 前 P(mutex) 后 V(mutex)；
|
||
- 同步模板：S 初值 = 0，先做者 V(S)，后做者 P(S)。
|
||
- **考查方式**：应用题（必考）。
|
||
- **可能的题目**：
|
||
1. 用 P/V 操作解决司机-售票员同步问题。**答：见 4.3.1 节完整解法（s1、s2 初值均为 0）**。
|
||
|
||
---
|
||
|
||
### 考点 11：生产者/消费者问题（最高频大题）
|
||
- **内容**：3 个信号量（S1=empty, S2=full, mutex），环形缓冲区 in/out 指针；先 P(资源) 再 P(mutex)。
|
||
- **考查方式**：应用题（必考，必须能默写）。
|
||
- **可能的题目**：
|
||
1. 用 P/V 操作解决容量为 k 的生产者-消费者问题（多个生产者、多个消费者）。**答：见 4.3 节完整解法；关键：P(S1)→P(mutex)→操作→V(mutex)→V(S2)**。
|
||
2. 如果把 P(mutex) 和 P(S1) 顺序颠倒会怎样？**答：当缓冲区满时，所有生产者持有 mutex 但申请不到空位 S1，消费者永远进不去释放 mutex → 死锁**。
|
||
|
||
---
|
||
|
||
### 考点 12：读者/写者问题（高频大题）
|
||
- **内容**：mutex 保护 read_count；第一个读者 P(r_w_w)，最后一个读者 V(r_w_w)；写者优先改进可避免写者饿死。
|
||
- **考查方式**：应用题（高频）。
|
||
- **可能的题目**：
|
||
1. 解法 3 中，读者阻塞在 `P(r_w_w)` 这一句；写者阻塞在 `P(r_w_w)` 这一句；若读者源源不断会出现什么问题？**答：写者饿死（starvation）**。
|
||
2. 如何改进为写者优先？**答：一旦有写者等待，新到达的读者等待；让正在读的读者都结束后写者进入**。
|
||
|
||
---
|
||
|
||
### 考点 13：哲学家就餐问题（高频大题）
|
||
- **内容**：朴素解法死锁；三种改进方案：限制最多 4 人、AND 信号量、状态机管程。
|
||
- **考查方式**：应用题、分析题。
|
||
- **可能的题目**：
|
||
1. 哲学家朴素解法为何死锁？**答：所有哲学家同时拿起左叉，等待右叉，形成循环等待**。
|
||
2. 用 AND 型信号量解哲学家问题。**答：每步 P(fork[i], 1; fork[(i+1) mod 5], 1) 同时申请两把叉**。
|
||
|
||
---
|
||
|
||
### 考点 14：AND 型信号量与 SP/SV 操作
|
||
- **内容**：SP 一次性申请多种资源，任一不足则等待；SV 一次性释放多种资源；AND 型是 ti=di=1 的特例。
|
||
- **考查方式**：填空、应用。
|
||
- **可能的题目**：
|
||
1. SP(S1,t1,d1; S2,t2,d2) 中，若 S1<t1 而 S2≥t2 会怎样？**答：将执行进程放入 S1 的等待队列尾，PC 置回 SP 开始处**。
|
||
|
||
---
|
||
|
||
### 考点 15：吸烟者问题
|
||
- **内容**：3 个供应者、3 个吸烟者；AND 型信号量 + s 互斥供应者。
|
||
- **考查方式**：应用题（扩展）。
|
||
- **可能的题目**：
|
||
1. 用 AND 型信号量解决吸烟者问题。**答：见 4.3 节完整解法**。
|
||
|
||
---
|
||
|
||
### 考点 16：条件临界区（CCR）
|
||
- **内容**：`region V when B do S`；CCR 与 PV 等价；CCR 实现效率较低（每个进程自己计算 B）。
|
||
- **考查方式**：填空、选择。
|
||
- **可能的题目**：
|
||
1. CCR 的实现效率低的主要原因。**答：每个欲进入条件临界区的进程必须自己计算条件 B；唤醒后条件可能仍为假，需重新等待——本质是忙式等待**。
|
||
|
||
---
|
||
|
||
### 考点 17：管程的三大唤醒语义
|
||
- **内容**：
|
||
- **Hoare**：P 紧急等待，Q 继续（Signal and urgent wait）；
|
||
- **Hansen**：signal 是管程中最后一个操作（Signal and leave）；
|
||
- **Java**：signal 后 P 继续，被唤醒者下次重新计算（Signal and continue）。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. Java 的 synchronized 采用哪种唤醒语义？**答：Signal and continue**。
|
||
2. Hoare 管程的 signal(c) 执行后，控制权转移给谁？**答：被唤醒者 Q 立即执行，执行者 P 进入紧急队列等待**。
|
||
|
||
---
|
||
|
||
### 考点 18：管程 vs 信号量
|
||
- **内容**：
|
||
- **信号量**：分散式，高效灵活，但易出错；
|
||
- **管程**：集中式，易读易维护，但效率略低、不甚灵活。
|
||
- **考查方式**：选择、简答。
|
||
- **可能的题目**：
|
||
1. 比较管程和信号量在同步机制中的优缺点。**答：信号量高效灵活但易出错；管程封装好、可读性高但效率略低**。
|
||
|
||
---
|
||
|
||
### 考点 19：管程与 PV 的等价性
|
||
- **内容**：用管程可实现 PV，用 PV 可实现管程（构造映射表）。
|
||
- **考查方式**：填空、简答。
|
||
- **可能的题目**：
|
||
1. 用 PV 操作模拟 Hoare 管程中 wait(c) 和 signal(c)。**答：见 4.3.5.5 节映射表**。
|
||
|
||
---
|
||
|
||
### 考点 20：管程的嵌套调用问题
|
||
- **内容**：4 种处理方法——禁止嵌套；允许嵌套但只释放当前管程互斥权；释放所有管程互斥权；释放路径上管程互斥权。
|
||
- **考查方式**：选择、简答。
|
||
- **可能的题目**：
|
||
1. Modula 语言对管程嵌套的处理。**答：禁止嵌套**。
|
||
|
||
---
|
||
|
||
### 考点 21：Java 中的管程实现
|
||
- **内容**：synchronized 启用 lock；wait() / notify() / notifyAll()；wait set 与 entry set；Java 采用 Signal and continue 语义。
|
||
- **考查方式**：选择、应用（填空 Java 代码）。
|
||
- **可能的题目**：
|
||
1. Java 的 wait() 和 notify() 必须在 synchronized 方法中调用的原因。**答：wait() 释放对象锁，notify() 也需持有对象锁才能操作 wait set，所以必须在 synchronized 方法或块中**。
|
||
|
||
---
|
||
|
||
### 考点 22：临界区调度原则
|
||
- **内容**：当关于某一组共享变量的所有临界区均为空闲时，要求进入的进程应立即进入；当一个临界区被占用时，要求进入的进程应等待；当一个进程离开临界区时，应容许一个等待者进入。
|
||
- **考查方式**：简答。
|
||
- **可能的题目**：
|
||
1. 简述临界区调度原则。**答：空闲让进、忙则等待、让权等待、择一唤醒**。
|
||
|
||
---
|
||
|
||
### 考点 23：并发进程应用题综合（必考）
|
||
- **内容**：综合运用信号量解决实际同步/互斥问题（流水线、读者写者变种、奇偶消费者、生产线、寺庙打水等）。
|
||
- **考查方式**：应用大题。
|
||
- **可能的题目**：
|
||
1. **2009 考研真题**：三个进程 P1、P2、P3 共享 N 单元缓冲区。P1 用 produce() 产生正数 put() 放入；P2 用 getodd() 取奇数；P3 用 geteven() 取偶数。用 P/V 实现同步互斥。**答：见 4.3 节例 9 完整解法（empty=N, odd=0, even=0, mutex=1）**。
|
||
|
||
---
|
||
|
||
### 考点 24：信号量机制中的死锁分析
|
||
- **内容**：P 操作顺序不当引起死锁（极限状态分析）；如寺庙问题中先 P(bucket) 再 P(empty)。
|
||
- **考查方式**：分析题。
|
||
- **可能的题目**：
|
||
1. 分析某 P/V 解法是否会产生死锁。**答：考察所有进程在极端状态下的 P 操作序列是否能形成循环等待**。
|
||
|
||
---
|
||
|
||
### 考点 25：硬件同步机制的局限
|
||
- **内容**：开关中断只对单 CPU 有效；TS/Swap 在多 CPU 下非原子，需锁总线；影响并发性。
|
||
- **考查方式**：选择、简答。
|
||
- **可能的题目**：
|
||
1. 为什么单 CPU 用开关中断实现互斥，多 CPU 不行？**答：开关中断只禁止当前 CPU 响应中断，其它 CPU 仍可执行并访问共享变量，无法实现互斥**。
|
||
|
||
---
|
||
|
||
## 三、本章知识结构图（辅助记忆）
|
||
|
||
```
|
||
第四章 互斥同步与通讯
|
||
├── 4.1 并发进程
|
||
│ ├── 前趋图（DAG）
|
||
│ ├── 顺序 vs 并发特性
|
||
│ ├── Bernstein 条件
|
||
│ └── 与时间有关的错误
|
||
├── 4.2 进程互斥
|
||
│ ├── 临界区与共享变量
|
||
│ ├── 三原则：互斥、进展、有限等待
|
||
│ ├── 软件实现
|
||
│ │ ├── 尝试 1/2/3（依次不满足）
|
||
│ │ ├── Dekker
|
||
│ │ ├── Peterson（最经典）
|
||
│ │ ├── Lamport 面包店
|
||
│ │ └── Eisenberg/McGuire
|
||
│ └── 硬件实现
|
||
│ ├── TS / Swap 指令
|
||
│ ├── 关中断/开中断（仅单 CPU）
|
||
│ └── 多 CPU 需锁总线
|
||
├── 4.3 进程同步
|
||
│ ├── 司机-售票员（典型同步）
|
||
│ ├── 信号量与 PV（Dijkstra 1965）
|
||
│ ├── 经典同步问题
|
||
│ │ ├── 生产者-消费者（必考）
|
||
│ │ ├── 读者-写者（高频）
|
||
│ │ ├── 哲学家就餐（高频）
|
||
│ │ ├── 吸烟者（AND 信号量）
|
||
│ │ └── 奇偶消费者（09 考研真题）
|
||
│ ├── 条件临界区（CCR）
|
||
│ ├── 管程
|
||
│ │ ├── Hoare / Hansen / Java 语义
|
||
│ │ ├── 条件变量 wait/signal
|
||
│ │ ├── 管程与 PV 等价
|
||
│ │ └── 嵌套调用问题
|
||
│ └── Windows 10 同步机制（Mutex/Semaphore/Event/CRITICAL_SECTION）
|
||
└── 4.4 进程高级通讯（下一章）
|
||
```
|
||
|