627 lines
26 KiB
Markdown
627 lines
26 KiB
Markdown
# 第四章 互斥、同步与通讯（下）
|
||
|
||
## 一、知识讲解
|
||
|
||
本章承接第四章（上）的内容，重点介绍**进程高级同步机制（会合）**与**进程高级通讯机制**。低级同步（信号灯、管程）基于共享存储区，难以适应分布式环境；高级机制则更适合分布/异构系统。
|
||
|
||
---
|
||
|
||
### 4.3.6 会合（Rendezvous）
|
||
|
||
#### 1. 会合的引入背景
|
||
|
||
**Ada 语言**（80年代由美国国防部 DOD 发起，Ada 95 引入面向对象特性）首先提出"会合"作为分布式系统中的同步通讯机制。
|
||
|
||
- **共享变量方式**：PV 操作（信号灯）依赖于访问进程与共享变量在**同一存储区**。当进程分布在不同站点（站点1、站点2）时，共享内存不可用，无法用 PV 实现互斥。
|
||
- **管程方式**：管程是被动的同步原语，但管程本身与调用进程在同一存储区，**不适合分布环境**。
|
||
|
||
因此，Ada 提出了**会合**机制：两个并发执行流汇集到一处——调用方发起调用，被调用方接受，**握手、同步发生**，且能传递参数。
|
||
|
||
#### 2. 会合图示
|
||
|
||
- 任务（被调用者）有多个 entry（入口），每个入口有一个 **FIFO 队列**保存等待的调用者。
|
||
- 调用者发起 `调用语句`，被调用任务在 `accept` 处等待。
|
||
- 双方在某入口汇合后，由**被调用者代替调用者执行调用代码**（即执行 accept 后面的语句序列）。
|
||
- 会合结束后双方各自继续。
|
||
|
||
#### 3. Ada 同步语句
|
||
|
||
**（1）调用语句**
|
||
```
|
||
<任务名称>.<入口名称>[<实参表>]
|
||
```
|
||
如：`single_resource.acquire;`
|
||
|
||
**（2）接受语句**
|
||
```
|
||
accept <入口名称>[<形参表>]
|
||
[do <语句序列> end <入口名称>]
|
||
```
|
||
accept 后面跟的 `do...end` 块即为会合期内被调用方执行的代码。
|
||
|
||
**（3）选择语句 select**
|
||
```
|
||
select
|
||
[when <布尔表达式> =>]
|
||
<接受语句>
|
||
[<语句序列>]
|
||
{ or [when <布尔表达式> =>]
|
||
<接受语句>
|
||
[<语句序列>] }
|
||
[ else <语句序列>]
|
||
end select
|
||
```
|
||
|
||
#### 4. accept 语句的执行流程
|
||
|
||
```
|
||
有调用者？
|
||
├─ 等待 ─→ 选取第一个
|
||
└─ 有 ─→ 会合开始
|
||
├─ 调用者等待
|
||
├─ 有 in 参数 ─→ 取 in 参数
|
||
├─ 有语句序列 ─→ 执行之
|
||
├─ 有 out 参数 ─→ 送 out 参数
|
||
└─ 会合结束 ─→ 调用者继续
|
||
```
|
||
|
||
只有当**调用者与被调用者双方都到达会合点**时，会合才开始；任一方先到则等待对方。
|
||
|
||
#### 5. select 语句语义（要点）
|
||
|
||
1. 计算所有 `when` 后的布尔表达式，**为真者对应入口标记为"开放"**。
|
||
2. **若没有开放的 accept**：
|
||
- 若有 `else` 部分，执行 else；否则抛异常（程序退出 select）。
|
||
3. **若没有"开放且被调用的" accept**：
|
||
- 若有 `else`，执行 else；否则**等待**直到有调用者出现。
|
||
4. **任取一开放且被调用的 accept**，进入会合期，执行参数传递与会合代码。
|
||
5. 会合结束后，若 select 后有语句序列，则继续执行。
|
||
|
||
#### 6. 典型例子——单一资源管理
|
||
|
||
```ada
|
||
task single_resource is
|
||
entry acquire;
|
||
entry return;
|
||
end single_resource;
|
||
|
||
task body single_resource is
|
||
begin
|
||
loop
|
||
accept acquire;
|
||
accept return;
|
||
end loop
|
||
end single_resource;
|
||
|
||
-- 使用方
|
||
single_resource.acquire;
|
||
-- 使用资源
|
||
single_resource.return;
|
||
```
|
||
|
||
**说明**：因为 `accept` 之间是顺序的，所以 acquire 与 return 必须交替执行，天然保证了互斥。
|
||
|
||
#### 7. 客栈问题（Ada Lodge Problem）——会合综合应用
|
||
|
||
场景：猎人(hunter)送来一份猎物，面包师(bakery)送来一份面包，主人(master)把面包+猎物做成三明治，探险家(explorer)进店取走一份三明治吃。**一份猎物 + 一份面包 = 一份三明治**。
|
||
|
||
关键设计：
|
||
- master 任务有三个 entry：`deliverbread`、`delivermeat`、`lodge`。
|
||
- select 中：
|
||
- `when bread=0` 接受面包；
|
||
- `when meat=0` 接受猎物；
|
||
- `when (sandwich<>0) or (bread<>0 and meat<>0)` 接受探险家入店请求；
|
||
- else 分支：当"有面包且有猎物且没三明治"时调用 `makesandwich`（栈主人主动做三明治）。
|
||
|
||
要点：**会合期外仍可执行语句**（如 `sandwich:=0`、`makesandwich`），select 的 else 分支就属于"会合期外"。
|
||
|
||
#### 8. 有界缓冲问题（Bounded Buffer）
|
||
|
||
```ada
|
||
task boundedbuffer is
|
||
entry putin;
|
||
entry getout;
|
||
end boundedbuffer;
|
||
|
||
task body boundedbuffer is
|
||
b: array(0..k-1) of integer;
|
||
ip, op: 0..k-1;
|
||
count: integer;
|
||
begin
|
||
ip:=0; op:=0; count:=0;
|
||
loop
|
||
select
|
||
when (count<k) =>
|
||
accept putin(item:in integer) do
|
||
b(ip):=item
|
||
end putin;
|
||
ip:=(ip+1) mod k;
|
||
count:=count+1;
|
||
or when (count>0) =>
|
||
accept getout(item:out integer) do
|
||
item:=b(op)
|
||
end getout;
|
||
op:=(op+1) mod k;
|
||
count:=count-1;
|
||
end select
|
||
end loop
|
||
end boundedbuffer;
|
||
```
|
||
|
||
通过 `when` 守卫保证缓冲区满时拒绝 putin、空时拒绝 getout。
|
||
|
||
#### 9. 读者-写者问题（写者优先，作业#4）
|
||
|
||
```ada
|
||
task readers_writers is
|
||
entry start_read, finish_read;
|
||
entry start_write, finish_write;
|
||
end readers_writers;
|
||
|
||
task body readers_writers is
|
||
read_count, write_count: integer;
|
||
begin
|
||
read_count:=0; write_count:=0;
|
||
loop
|
||
select
|
||
when write_count=0 =>
|
||
accept start_read do
|
||
read_count:=read_count+1;
|
||
end start_read
|
||
or
|
||
when read_count>0 =>
|
||
accept finish_read do
|
||
read_count:=read_count-1;
|
||
end finish_read
|
||
or
|
||
when write_count=0 =>
|
||
accept start_write do
|
||
while read_count>0 do
|
||
accept finish_read do
|
||
read_count:=read_count-1;
|
||
end finish_read
|
||
end while
|
||
end start_write;
|
||
write_count:=write_count+1
|
||
or
|
||
when write_count>0 =>
|
||
accept finish_write do
|
||
write_count:=write_count-1;
|
||
end finish_write
|
||
end select
|
||
end loop
|
||
end readers_writers;
|
||
```
|
||
|
||
**写者优先的关键**：在 `accept start_write` 内**嵌套 accept finish_read**，把当前所有读者"消化"完后再把 `write_count` 加1，从而阻止后续新读者进入。
|
||
|
||
---
|
||
|
||
### 4.4 进程高级通讯
|
||
|
||
#### 1. 进程通讯的层次
|
||
|
||
| 层次 | 通讯内容 | 机制 |
|
||
|------|----------|------|
|
||
| **低级通讯** | 简单信号（少量控制信息） | 进程互斥、进程同步（如 PV） |
|
||
| **高级通讯** | 大宗信息（数据/消息） | 共享内存、消息传递 |
|
||
|
||
#### 2. 高级通讯的分类（重要考点）
|
||
|
||
| 维度 | 类别 1 | 类别 2 |
|
||
|------|--------|--------|
|
||
| **通讯机制** | 共享内存（memory sharing） | 消息传递（message passing） |
|
||
| **寻址方式** | 直接（进程-进程） | 间接（进程-信箱-进程） |
|
||
| **命名对称性** | 对称（sender 和 receiver 互相指名） | 非对称（仅 sender 指名 receiver） |
|
||
| **缓冲方式** | 有缓冲 | 无缓冲 |
|
||
|
||
---
|
||
|
||
### 4.4.2 进程通讯模式
|
||
|
||
#### 1. 共享内存模式（Shared Memory）
|
||
|
||
- OS 提供**一段公共内存区 M**。
|
||
- 进程 P1、P2 通过 `P/V` 等互斥同步机制保证对 M 的安全访问。
|
||
- 适用于单机多进程，效率高；但**不能跨越机器**。
|
||
|
||
#### 2. 消息传递模式（Message Passing）
|
||
|
||
- 进程间通过 `send / receive` 原语交换消息。
|
||
- 可分布式、跨网络；是分布式 OS 的主要通讯手段。
|
||
|
||
---
|
||
|
||
### 4.4.3 直接方式
|
||
|
||
#### 1. 对称形式（Symmetric）
|
||
|
||
```
|
||
send(R, message)
|
||
receive(S, message)
|
||
```
|
||
发送方和接收方**互相指名**对方。优点是清晰；缺点是进程名变化时双方都要改。
|
||
|
||
#### 2. 非对称形式（Asymmetric，仅 sender 指名）
|
||
|
||
```
|
||
send(R, message)
|
||
receive(pid, message)
|
||
```
|
||
只有发送者指名接收者，接收者由 `pid`（任一发送者）反向得到。常见于 **C/S 模型**：多个 client（sender）向 server（receiver）发请求。
|
||
|
||
---
|
||
|
||
### 4.4.3.1 有缓冲途径（直接方式、非对称、有缓冲）
|
||
|
||
#### 1. 消息结构
|
||
|
||
```
|
||
size | text | sender | link
|
||
```
|
||
|
||
#### 2. 进程消息队列管理（每接收者一个队列）
|
||
|
||
```
|
||
Var Sm: semaphore; -- 初值 0（队列中消息计数）
|
||
Var m_mutex: semaphore; -- 初值 1（队列互斥）
|
||
```
|
||
|
||
- 接收方 `receive` 前：`P(Sm)`。
|
||
- 发送方 `send` 后：`V(Sm)`。
|
||
- 入列/出列动作夹在 `P/V(m_mutex)` 之间。
|
||
|
||
#### 3. 缓冲池管理
|
||
|
||
```
|
||
Var Sb: semaphore; -- 初值 k（空缓冲数量）
|
||
Var b_mutex: semaphore; -- 初值 1（缓冲池互斥）
|
||
Head：缓冲链头
|
||
```
|
||
|
||
申请空缓冲：`P(Sb); P(b_mutex); 头缓冲出链; V(b_mutex);`
|
||
释放空缓冲：`P(b_mutex); 缓冲入链头; V(b_mutex); V(Sb);`
|
||
|
||
#### 4. send / receive 原语伪码
|
||
|
||
```
|
||
Send(R, M):
|
||
根据R找接收者
|
||
P(Sb); P(b_mutex); 取一空buf; V(b_mutex);
|
||
buf <- (size, text, sender)
|
||
P(m_mutex); 消息入链尾; V(m_mutex);
|
||
V(Sm);
|
||
|
||
Receive(pid, N):
|
||
P(Sm); P(m_mutex); 头消息出链; V(m_mutex);
|
||
(size, text) -> N; sender -> pid
|
||
P(b_mutex); 空buf入链; V(b_mutex);
|
||
V(Sb);
|
||
```
|
||
|
||
**重要说明**：send/receive 本身是高级通讯原语，但**它们可以用低级原语（PV）来实现**；而且 send/receive 并不是"真正不可中断"的原语，OS 在执行它们的过程中仍可能被中断。
|
||
|
||
---
|
||
|
||
### 4.4.3.2 无缓冲途径（直接方式、非对称、无缓冲）
|
||
|
||
#### 1. 实现机制
|
||
|
||
- 收发双方 PCB 各有两个信号灯 `S_m`、`S_w`，初值都为 0。
|
||
- **不设缓冲**，消息由发送者进程空间直接**复制**到接收者进程空间。
|
||
- 必须收发双方**同时到达会合点**（会合性/rendezvous 语义）。
|
||
|
||
#### 2. send 过程
|
||
|
||
```
|
||
Send(R, M):
|
||
根据R找到消息接收者
|
||
发送消息进程计数+1
|
||
若接收进程在等待则将其唤醒 → V(S_m)
|
||
等待消息传送完毕 → P(S_w)
|
||
```
|
||
|
||
#### 3. receive 过程
|
||
|
||
```
|
||
Receive(pid, N):
|
||
等待消息到达 → P(S_m)
|
||
消息由发送进程空间复制到接收进程空间
|
||
唤醒发送消息进程 → V(S_w)
|
||
```
|
||
|
||
#### 4. 优缺点对比
|
||
|
||
| 优点 | 缺点 |
|
||
|------|------|
|
||
| 节省空间（不需要 buffer） | 并发性差：发送方必须等接收方 receive 完成复制后才能继续 |
|
||
|
||
---
|
||
|
||
### 4.4.4 间接方式（Mailbox / 信箱）
|
||
|
||
#### 1. 概念
|
||
|
||
进程间通讯通过一个**共享信箱 mb** 进行：
|
||
```
|
||
Send_mb(mb, m)
|
||
Receive_mb(mb, n)
|
||
```
|
||
|
||
拓扑灵活：
|
||
- 多对一（多 sender — 一 receiver，如服务器场景）
|
||
- 多对多（多 sender — 多 receiver）
|
||
|
||
#### 2. 信箱数据结构（属于 OS 空间）
|
||
|
||
```
|
||
type mailbox = record
|
||
in, out: 0..k; -- 环形队列指针
|
||
s1, s2: semaphore; -- s1 初值 k（空位数），s2 初值 0（消息数）
|
||
mutex: semaphore; -- 初值 1
|
||
letter: array[0..k-1] of message;
|
||
end;
|
||
var mb: mailbox;
|
||
```
|
||
|
||
系统调用 `create_mb(mb)`、`delete_mb(mb)` 创建/销毁信箱。
|
||
|
||
#### 3. send_mb / receive_mb 实现
|
||
|
||
```
|
||
Procedure send_mb(var mb: mailbox; m: message):
|
||
P(s1); -- 申请空位
|
||
P(mutex);
|
||
letter[in] := m;
|
||
in := (in+1) mod k;
|
||
V(mutex);
|
||
V(s2); -- 消息数 +1
|
||
|
||
Procedure receive_mb(var mb: mailbox; var n: message):
|
||
P(s2); -- 申请消息
|
||
P(mutex);
|
||
n := letter[out];
|
||
out := (out+1) mod k;
|
||
V(mutex);
|
||
V(s1); -- 空位数 +1
|
||
```
|
||
|
||
**关键点**：
|
||
- `s1`、`s2` 一对信号灯实现了**生产者-消费者**约束（空位 vs 消息）。
|
||
- `mutex` 实现对信箱内部数据结构的互斥访问。
|
||
- 信箱属于 OS 空间，由 OS 统一管理生命周期。
|
||
|
||
#### 4. 信箱空间归属小结
|
||
|
||
| 归属 | 说明 | 生命周期 |
|
||
|------|------|----------|
|
||
| **OS 空间**（如上） | 由 OS 创建/销毁 | 进程结束信箱仍可保留 |
|
||
| 进程空间 | 由某进程创建，进程退出即失效 | 与进程同生共死 |
|
||
|
||
---
|
||
|
||
### UNIX 进程高级通讯机制
|
||
|
||
#### 1. 管道（Pipe）
|
||
|
||
- 基于**文件系统**实现，与普通文件使用统一的界面（open/read/write/close）。
|
||
- **两次 IO**：读、写各一次。
|
||
- **速度优化**：
|
||
- **延迟写（delayed write）**：先写到内存缓冲区，内存资源不紧张且缓冲区不被占用时不会刷到外存。
|
||
- 读时优先从内存缓冲区得到数据。
|
||
- **大小限制**：通常 ~2KB；超出后循环使用，避免缓冲资源紧张。
|
||
- 适用：父子/兄弟进程等**有亲缘关系**的进程（无名管道）。
|
||
|
||
#### 2. UNIX 信号（Signal）
|
||
|
||
- 每个进程 PCB 中有 `p_sig` 字段记录接收到的信号。
|
||
- user 结构中有 `u_signal[NSIG]` 数组保存信号处理程序入口。
|
||
- 系统调用 `signal(sig, func)` 预置处理程序：
|
||
- `func = 0`：收到信号时进程**终止自己**。
|
||
- `func = 奇数`：**忽略**该信号。
|
||
- `func = 偶数`：作为**处理程序入口地址**。
|
||
- 子进程**继承**父进程的信号处理程序。
|
||
- 信号**任何时候都可接收**，仅记录在 `p_sig` 中。
|
||
- 信号**处理时机**：进程被调度选中、即将由**核心态转为目态（用户态）**时。
|
||
- 信号对用户而言是一种"软中断"。
|
||
|
||
---
|
||
|
||
### Windows 10 的管道
|
||
|
||
| 类型 | 命名 | 标识 | 关键 API |
|
||
|------|------|------|----------|
|
||
| **无名管道**（Anonymous） | 无 | 句柄 `hReadPipe`、`hWritePipe` | `CreatePipe` |
|
||
| **命名管道**（Named） | `\\.\pipe\PipeName`（服务端）/ `\\serverName\pipe\PipeName`（客户端） | 文件系统路径 | `CreateNamedPipe`、`ConnectNamedPipe`、`CallNamedPipe`、`ReadFile`/`WriteFile` |
|
||
|
||
- **CreateNamedPipe**：服务器端建立管道。
|
||
- **ConnectNamedPipe**：服务器端等待客户连接请求。
|
||
- **CallNamedPipe**：客户端建立到服务器管道的连接并通讯。
|
||
- **ReadFile / WriteFile**：管道读写（与文件 I/O 同一套接口）。
|
||
|
||
---
|
||
|
||
### Windows 10 的 Mailslot（邮件槽）
|
||
|
||
- **服务端路径**：`\\.\mailslot\[path]name`（本地）
|
||
- **客户端路径**：`\\range\mailslot\[path]name`（range 是域名，表示发往哪台主机）
|
||
- 关键 API：
|
||
- `CreateMailslot`：服务端创建邮件槽。
|
||
- `GetMailslotInfo`：服务端查询邮件槽状态（消息数、最大长度等）。
|
||
- `ReadFile`：服务端读取消息。
|
||
- `WriteFile`：客户端发送消息。
|
||
|
||
**特点**：基于广播/域内投递，适合**一对多**的轻量级消息通讯。
|
||
|
||
---
|
||
|
||
### 概念对比小结（考试最爱）
|
||
|
||
| 机制 | 拓扑 | 缓冲 | 同步性 | 适合场景 |
|
||
|------|------|------|--------|----------|
|
||
| **共享内存** | 1 对 1 或多对多 | 用户自管 | 用户自管 | 单机高速数据交换 |
|
||
| **直接消息 有缓冲** | 1 对 1 或多对 1 | OS 维护消息队列 | 异步（发送后即可返回） | C/S、Producer-Consumer |
|
||
| **直接消息 无缓冲** | 1 对 1 | 无 | **会合（同步）** | 强同步握手 |
|
||
| **间接消息（信箱）** | 多对 1 / 多对多 | OS 信箱 | 异步 | 多发送者场景、解耦 |
|
||
| **管道** | 通常 1 对 1（亲缘） | 内核缓冲 | 字节流 | shell 流水线 |
|
||
| **命名管道** | C/S | 内核缓冲 | 同步/异步 | 跨进程、跨网络（Windows） |
|
||
| **邮件槽 mailslot** | 多对多（域） | 内核 | 不可靠/单向 | Windows 局域网广播 |
|
||
|
||
---
|
||
|
||
## 二、考点总结
|
||
|
||
### 考点1：会合（Rendezvous）的概念与适用场景
|
||
|
||
- **内容**：会合是 Ada 语言提出的、用于**分布式系统**的同步通讯机制。两个并发执行流在"调用语句"与"accept 语句"处汇合，握手、同步发生，由被调用方代替调用方执行会合代码。引入背景是共享变量/管程无法在分布式站点间使用。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. （填空）会合机制是为解决 __________ 环境下共享变量与管程不可用的问题而提出的。
|
||
- 答案：**分布式（多站点）**
|
||
2. （简答）为什么共享变量方式（PV）不适合分布式系统？
|
||
- 答案：PV 操作的共享变量必须与访问进程位于**同一存储区**；分布式系统中各进程分布在不同站点，没有共享内存，因此无法用 PV 实现互斥/同步。
|
||
|
||
### 考点2：Ada 的三类同步语句
|
||
|
||
- **内容**：调用语句 `<任务>.<入口>[<实参>]`；接受语句 `accept <入口>[<形参>] [do <语句序列> end <入口>]`；选择语句 `select ... or ... [else ...] end select`。
|
||
- **考查方式**：填空、简答、代码阅读。
|
||
- **可能的题目**：
|
||
1. （填空）Ada 中被调用任务用以接受调用请求的语句是 __________。
|
||
- 答案：**accept 语句**
|
||
2. （代码）写出单一资源管理器的 Ada task 框架。
|
||
- 答案：见上文"单一资源管理"示例，含 `accept acquire; accept return;` 顺序循环。
|
||
|
||
### 考点3：accept 的会合期执行流程
|
||
|
||
- **内容**：调用者发起调用→任务在 accept 等待→双方到齐会合开始→若有 in 参数则取 in 参数→若有语句序列则执行→若有 out 参数则送 out 参数→会合结束，调用者继续。
|
||
- **考查方式**：选择、流程图题。
|
||
- **可能的题目**：
|
||
1. （选择）关于 accept 语句，下列说法正确的是：__
|
||
- A) 仅调用者到达会合点即可开始会合
|
||
- B) 仅被调用者到达会合点即可开始会合
|
||
- C) **双方都到达会合点时才会合才开始**（正确答案）
|
||
- D) 会合由调用方执行会合代码
|
||
|
||
### 考点4：select 语句的语义（when / else / 等待）
|
||
|
||
- **内容**：先算所有 `when` 布尔式，为真者对应入口开放；若没有开放 accept 且无 else 则异常；若没有"开放且被调用的" accept 则等待（或执行 else）；任选一开放且被调用的 accept 执行会合。
|
||
- **考查方式**：选择、读程序、写程序。
|
||
- **可能的题目**：
|
||
1. （选择）select 语句中若所有 when 条件都为假、且没有 else 部分，则行为是：__
|
||
- 答案：**抛异常（异常退出 select）**
|
||
2. （选择）若所有开放入口都无调用者、且没有 else，则行为是：__
|
||
- 答案：**等待**直到有调用者出现
|
||
|
||
### 考点5：会合的典型应用——客栈问题
|
||
|
||
- **内容**：master 任务的三个 entry（deliverbread、delivermeat、lodge）通过 select 的 when 守卫实现"一份面包 + 一份猎物 = 一份三明治"的同步约束，else 分支在会合期外主动 `makesandwich`。
|
||
- **考查方式**：代码补全、简答。
|
||
- **可能的题目**：
|
||
1. （简答）客栈问题中 master 如何保证每次只做一份三明治？
|
||
- 答案：通过 `sandwich`、`bread`、`meat` 三个状态变量 + select 的 when 守卫实现：lodge 入口需 `sandwich≠0 或 (bread≠0 且 meat≠0)`；else 分支在原料齐备时主动制作。做完/取走后立即清零。
|
||
|
||
### 考点6：会合的典型应用——有界缓冲问题
|
||
|
||
- **内容**：用 count 与模 k 的环形缓冲，通过 select 的 `when count<k` 与 `when count>0` 实现生产者-消费者约束。
|
||
- **考查方式**：选择、改写。
|
||
- **可能的题目**：
|
||
1. （选择）Bounded buffer 的 putin 入口的守卫条件是 ________。
|
||
- 答案：`count < k`（缓冲区未满）
|
||
|
||
### 考点7：会合实现读者-写者问题（写者优先）
|
||
|
||
- **内容**：用 `read_count`、`write_count` 计数；在 `accept start_write` 内**嵌套 accept finish_read**，把所有活跃读者消化完后再使 write_count 加 1，从而阻止后续新读者。
|
||
- **考查方式**：代码阅读、简答。
|
||
- **可能的题目**：
|
||
1. （简答）为什么把 `accept finish_read` 嵌套在 `accept start_write` 内部即可实现"写者优先"？
|
||
- 答案：嵌套的 accept 在会合期内会持续接收并处理读者退出请求，直到 `read_count=0`，然后会合结束、写者才能进入并把 `write_count` 增 1。这样在已有写者等待时，新读者被 `when write_count=0` 守卫阻挡，无法进入，从而保证写者优先。
|
||
|
||
### 考点8：进程高级通讯的分类
|
||
|
||
- **内容**：高级通讯按四种维度分类：共享内存 vs 消息传递；直接 vs 间接；对称 vs 非对称；有缓冲 vs 无缓冲。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. （填空）高级通讯的两大机制是 __________ 和 __________。
|
||
- 答案：**共享内存（memory sharing）**、**消息传递（message passing）**
|
||
2. （选择）C/S 模型中常见的是哪种命名方式？
|
||
- A) 对称形式 B) **非对称形式（仅 sender 指名 receiver）**（正确答案）
|
||
|
||
### 考点9：直接消息——有缓冲途径的 PV 实现
|
||
|
||
- **内容**：每接收者维护消息队列，需要三组信号灯：`Sm`（消息计数，初值0）、`m_mutex`（队列互斥，初值1）、`Sb`（空缓冲数，初值k）、`b_mutex`（缓冲池互斥，初值1）。send 时申请空 buf、填入消息、入队、`V(Sm)`；receive 时 `P(Sm)`、出队、归还 buf、`V(Sb)`。
|
||
- **考查方式**：代码补全、PV 计算、应用题。
|
||
- **可能的题目**：
|
||
1. （填空）有缓冲消息队列中，`Sm` 的初值是 ________，`m_mutex` 的初值是 ________。
|
||
- 答案：`Sm=0`，`m_mutex=1`
|
||
2. （应用）画出 `send(R,M)` 完整 PV 序列。
|
||
- 答案：`P(Sb); P(b_mutex); 取空buf; V(b_mutex); 填 buf; P(m_mutex); 入队; V(m_mutex); V(Sm);`
|
||
|
||
### 考点10：直接消息——无缓冲途径（会合语义）
|
||
|
||
- **内容**：收发双方各设 `S_m`、`S_w`（初值0）。发送方 `V(S_m)` 后 `P(S_w)` 等待；接收方 `P(S_m)` 后复制消息，再 `V(S_w)`。**消息直接从发送进程空间复制到接收进程空间**，无需缓冲。
|
||
- **考查方式**：PV 顺序题、简答。
|
||
- **可能的题目**：
|
||
1. （填空）无缓冲途径下，发送方发送消息后必须执行 __________ 才能继续。
|
||
- 答案：`P(S_w)`（等待接收方复制完消息）
|
||
2. （简答）无缓冲途径相对有缓冲途径的优缺点。
|
||
- 答案：优点——节省空间（不需要缓冲）；缺点——并发性差，发送方必须等接收方执行 receive 把消息复制到接收进程空间后才能继续。
|
||
|
||
### 考点11：间接方式——信箱通讯
|
||
|
||
- **内容**：信箱属于 OS 空间，含环形队列 `letter[in..out]`、信号灯 `s1`（空位=k）、`s2`（消息=0）、`mutex`（互斥=1）。send_mb：`P(s1); P(mutex); letter[in]:=m; in++; V(mutex); V(s2);`。receive_mb：反向。
|
||
- **考查方式**：PV 顺序、代码补全。
|
||
- **可能的题目**：
|
||
1. （填空）信箱通讯中 `s1` 表示 ________、`s2` 表示 ________。
|
||
- 答案：`s1` 表示**空位数**（初值k），`s2` 表示**消息数**（初值0）
|
||
2. （选择）信箱机制最适合的场景是：
|
||
- A) 1对1 同步握手 B) **多对一 或 多对多，解耦发送者和接收者**（正确答案）
|
||
|
||
### 考点12：UNIX 管道（Pipe）
|
||
|
||
- **内容**：基于文件系统、与文件统一界面；速度优化包括**延迟写**（写到内存缓冲，不立刻刷盘）和**大小限制**（如2KB，循环使用）；通常用于亲缘进程（无名管道）。
|
||
- **考查方式**：选择、填空、简答。
|
||
- **可能的题目**：
|
||
1. （填空）UNIX pipe 的速度优化措施有 ________ 和 ________。
|
||
- 答案：**延迟写（delayed write）**、**缓冲大小限制（循环使用）**
|
||
2. （简答）为什么 pipe 虽然是"文件"但一般不会真的执行磁盘 I/O？
|
||
- 答案：pipe 采用延迟写策略，数据先写入内存缓冲区，内存资源不紧张时不会刷盘；读时直接读内存缓冲，因此基本不发生磁盘 I/O。
|
||
|
||
### 考点13：UNIX 信号（Signal）
|
||
|
||
- **内容**：`p_sig` 字段记录收到的信号；`u_signal[NSIG]` 数组保存处理入口；`signal(sig,func)` 中 func=0 终止、奇数忽略、偶数为处理入口；子进程继承父进程信号表；信号处理时机是**由核心态转目态前**。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. （填空）UNIX 中，进程被调度选中即将由核心态转为目态时，会检查并处理 PCB 中的 ________ 字段。
|
||
- 答案：`p_sig`（信号字段）
|
||
2. （选择）`signal(sig, func)` 中 `func` 为奇数表示：__
|
||
- A) 终止进程 B) **忽略该信号**（正确答案） C) 作为处理入口 D) 出错
|
||
|
||
### 考点14：Windows 命名管道 vs 无名管道
|
||
|
||
- **内容**：无名管道通过 `CreatePipe` 创建，仅本机有亲缘关系的进程可用；命名管道使用路径名 `\\.\pipe\PipeName` 或 `\\serverName\pipe\PipeName`，可跨网络，支持 C/S，关键 API 有 `CreateNamedPipe`、`ConnectNamedPipe`、`CallNamedPipe`、`ReadFile/WriteFile`。
|
||
- **考查方式**：选择、填空、应用。
|
||
- **可能的题目**：
|
||
1. （填空）Windows 中，命名管道服务端路径格式为 ________，客户端为 ________。
|
||
- 答案：`\\.\pipe\PipeName`、`\\serverName\pipe\PipeName`
|
||
2. （选择）下列哪个 API 是客户端用来连接命名管道的？
|
||
- 答案：`CallNamedPipe`
|
||
|
||
### 考点15：Windows Mailslot（邮件槽）
|
||
|
||
- **内容**：服务端 `\\.\mailslot\[path]name`，客户端 `\\range\mailslot\[path]name`；支持一对多的轻量级不可靠消息通讯；API：`CreateMailslot`、`GetMailslotInfo`、`ReadFile`、`WriteFile`。
|
||
- **考查方式**：选择、填空。
|
||
- **可能的题目**：
|
||
1. （填空）邮件槽主要适用于 ________ 的消息通讯场景。
|
||
- 答案：**一对多（域内广播）/ 轻量级消息**
|
||
2. （选择）服务端查询邮件槽状态应调用：__
|
||
- 答案：`GetMailslotInfo`
|
||
|
||
### 考点16：综合——各通讯机制对比
|
||
|
||
- **内容**：共享内存 vs 消息传递、直接 vs 间接、有缓冲 vs 无缓冲、管道 vs 命名管道 vs mailslot 在拓扑、同步性、缓冲、典型场景上的差异。
|
||
- **考查方式**：表格题、简答。
|
||
- **可能的题目**：
|
||
1. （简答）比较"直接消息 无缓冲"与"直接消息 有缓冲"在同步性、空间开销、并发性上的差异。
|
||
- 答案：① **同步性**：无缓冲是会合式（同步，必须同时到达）；有缓冲是异步（send 后即可返回）。② **空间**：无缓冲不需要缓冲，节省空间；有缓冲需要缓冲池（开销=k 个缓冲 + 队列）。③ **并发性**：无缓冲并发性差（发送方必须等待接收方 receive 复制完成）；有缓冲并发性好（消息进入队列即返回）。
|
||
2. （简答）比较消息传递与共享内存的优缺点。
|
||
- 答案：消息传递——易于分布式、跨网络，编程简单，但有数据拷贝开销；共享内存——效率高（无拷贝）、适合大数据量，但必须自行解决互斥同步，且**不适合分布式**。 |