Operating-System/Homework/04第四章 互斥同步与通讯（1）.md

第四章 互斥、同步与通讯（上）

一、知识讲解

本章是操作系统的核心章节之一，主要研究多进程（多线程）并发执行时如何协调彼此的活动。内容涵盖并发原理、进程互斥、进程同步、经典同步问题以及管程等高级同步机制。

---

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）：访问共享变量的程序段。
• 把临界区与其所对应的共享变量联系起来，称为关于某一种共享变量的临界区。

表示法：

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）：

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）：

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（先标志再检查）：

P0: do { flag[0]=true; while(flag[1]); CS; flag[0]=false; RS; } while(1);

缺点：不满足进展性——flag[0] = flag[1] = true 时双方都不能进入。

---

Dekker 算法（第一个解决互斥的软件算法，融合轮转与标志）：

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 算法（最经典、最常考的软件互斥算法）：

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)。

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 状态）：

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）——原子指令，不可中断

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;

满足互斥性、进展性，不满足有限等待性（忙等的进程可能饿死）。

改进——满足有限等待性：

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 指令——原子交换两个内存单元内容

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. 关中断/开中断指令

关中断;
临界区;
开中断;

Remarks：

• 开关中断只在单 CPU 系统中有效（多 CPU 各自开关，无法禁止其他 CPU）；
• 影响并发性（系统无法响应中断）；
• 关中断后代码必须很短，否则系统可能崩溃。

---

4.2.4 多处理机环境下的互斥

关键问题：

• 单 CPU：指令间交叉，TS/Swap 指令是原子的；
• 多 CPU：指令周期间交叉，TS/Swap 指令不是原子的（总线上的读-写-读-写可能交错）。

解决方案：

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 操作的定义

typedef struct semaphore {
    int value;
    PCB *queue;
} semaphore;
semaphore s;

• s.value 表示资源数（或可用资源数）；
• s.queue 是 FIFO 等待队列。

---

P 操作原语

void P(semaphore *s)
{
    s->value--;
    if (s->value < 0)
        asleep(s->queue);
}

asleep(s->queue):
1. 执行此操作进程的 PCB 入 s->queue 尾（状态改为等待）；
2. 转处理机调度程序。

P 是不可中断的原子原语（primitive）。

---

V 操作原语

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）

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 可用）

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 实现进程互斥（最基本题型）

Var mutex: semaphore;   //初值 = 1
shared x,y,z: integer;

进程 Pi:
Pi(mutex);
CS;                      //临界区
V(mutex);
RS;                      //剩余区

关键点：

• mutex 初值必须为 1；
• 临界区前后成对使用 P(mutex)、V(mutex)；
• 必须配对，遗漏 P 或 V 都会出错。

---

互斥例子：借书系统（改进版）

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

---

用信号量实现进程同步（典型题型）

一般形式：

VAR S: semaphore;   //初值 = 0

P1（先动作）:
    ...先动作...
    V(S);             //通知后动作

P2（后动作）:
    P(S);             //等待先动作完成
    ...后动作...

司机-售票员问题解法：

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。

完整解法（推荐背诵的标准答案）：

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 分别互斥：

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 不互斥，简单）：

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 计数）：

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（标准正确解法）：

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 把叉子，每两位之间一把；
• 哲学家思考-饿了-取左叉-取右叉-进食-放左叉-放右叉；
• 叉子为不同种组合资源。

朴素解法（会引起死锁）：

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 人就餐

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（用于阻塞自身）。

测试函数：

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;

哲学家活动：

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）解法：

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）：

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）：

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)。

工人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；
• 一组申请时：直接使用；
• 两组申请时：组间交替，组内依次；
• 三组申请时：组间轮流，组内依次。

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()。

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 只水桶共用。

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 操作低级，容易用错。

形式：

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 两个缓冲区。

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 管程形式

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;，可根据需要定义多个条件变量。

条件变量操作：

wait(c):
    如紧急队列非空，唤醒第一个等待者；否则释放管程互斥权；
    执行此操作的进程进入 c 链尾。

signal(c):
    如 c 链空，相当空操作；
    否则唤醒第一个等待者，执行此操作的进程进入紧急队列。

---

4.3.5.4 管程的使用——典型例子

例 1：生产者/消费者管程

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：读者/写者管程（写者优先）

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：哲学家就餐管程解法

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 算法）

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：嗜眠理发师问题

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：单一资源管理

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 操作：

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 实现生产者/消费者：

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 进程高级通讯（下一章）