# 第四章 互斥、同步与通讯（上） ## 一、知识讲解 本章是操作系统的核心章节之一，主要研究多进程（多线程）并发执行时如何协调彼此的活动。内容涵盖并发原理、进程互斥、进程同步、经典同步问题以及管程等高级同步机制。 --- ### 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 `(avalue--; 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 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