教程笔记 · Part 2

范围：PDF 页 121-240（教材印刷页约 110-229）。 涵盖：第 3 章存储管理收尾（段页式 / 段页式虚存）、第 4 章设备管理、第 5 章文件管理、第 6 章并发程序设计前半。 来源：index.md 同目录扫描图（已采样精读 ~35 张关键页）。

一、章节地图（中 1/3）

二、第 3 章存储管理收尾（p121-128）

3.4.3 段页式存储管理

1) 基本思想

• 段页式 = 段式管理 + 页式管理。每一段不必占据连续的存储空间，而是存放在不连续的主存页框中。
• 同样可以扩充成虚拟存储管理：只要装入进程的部分段、或这些段中的部分页面，进程就可以运行。

2) 地址结构与转换

逻辑地址：[段号 s | 页号 p | 页内地址 d]

地址转换流程（图 3-18）：

1. 先查快表（联想存储器），命中则形成 (页框号, 单元号) → 物理地址
2. 不命中则查段表（段内含「标志 / 页表限长 / 页表基址」）
3. 由段表找到该段页表，再查页表得页框号
4. 物理地址 = 页框号 × 页大小 + 单元号
5. 同时把 (段号, 页号, 页框号) 登记入快表

3) 段页式虚拟存储（图 3-19 流程）

按逻辑地址查快表 → 否，查段表 → 段表是否在主存？否 → 缺段中断；是 → 该页超出页表长？是 → 越界中断；否 → 该页在主存？否 → 缺页中断；是 → 形成物理地址。

共四种中断：缺段、越界、缺页、保护。

对应学校 ch3（存储管理）末尾

第三章本章小结要点（p123-124）

• 存储管理基本功能：存储分配 / 地址转换 / 存储保护 / 存储共享 / 存储扩充
• 地址转换：通过静态或动态地址重定位将逻辑地址映射到物理地址
• 五种主要管理方式：单连续 / 固定分区 / 可变分区 / 页式 / 段式 / 段页式
• 虚拟存储管理：让进程的”部分”装入主存即可运行，扩充逻辑可用空间
• 关键问题：缺页中断、抖动（thrashing）、页面置换（OPT/FIFO/LRU/LFU/Clock）、Belady 异常

习题三关键题（p124-128 摘录）

这些题型在校考中高频出现，建议重点记。

应用题 (1) — 缓存/内存/外存平均访问时间

设缓存命中率 (n-1)/n，内存命中率 (m-1)/m，缓存访问 A ns，内存装入缓存 B ns，外存装入内存 C ns。 平均访问时间 T = A + (1/n)(B + (1/m)·C)

(2) — 局部性举例：双重 for 循环对 a[i] = a[i] * j 的空间/时间局部性分析

(19) FIFO/OPT/LRU/LFU/Clock 缺页比较 - 给定页面走向 1-2-3-1-4-5-1-2-1-4-5-3-4-5，全部从空开始，3 个页框 - 计算缺页中断次数与缺页率

(20) 页框数变化对 FIFO/OPT/LRU 的影响：3、4、5、6 个页框；走向 1-2-3-4-2-1-5-6-2-1-2-3-7-6-3-2-1-2-3-6

(21) 给逻辑地址序列计算页面调度：地址流 10、11、104、170、73、305、180、…，页面大小 100B；FIFO/LRU；3 个页框

(22) 综合性能题（缺页率上限）：访问周期 1µs，未修改页缺页 2ms，已修改页缺页加写盘 8ms，70% 被替换的页修改过；要求平均存取时间 ≤ 2µs，求最大允许缺页率

(23) 给定 R/D 位、装入时间、最后访问时间，FIFO/LRU 选哪页换出

(24) 数组遍历顺序对缺页的影响：int A[100][100] 按行存储，3 页内存，每页 200 整数；按行遍历 vs 按列遍历

三、第 4 章 设备管理（p129-162）

4.1 设备管理基础

4.1.1 设备管理概述（p129-131）

• I/O 设备 = 外围设备 = 外部设备 = 外设
• I/O 系统 = I/O 设备 + 接口电路 + 控制部件 + 通道 + 管理软件
• 设备分类视角：
• 速度（低/中/高）
• 信息组织（字符/块）
• 共享属性（独占型/共享型/虚拟型）
• 用途（输入/输出/存储）

4.1.2 I/O 控制方式（p132-134）

四种控制方式按 CPU 参与程度递减排列：

通道工作流程（p134）： 1. CPU 遇 I/O 任务 → OS 组织通道程序 → 首地址存入通道地址字（CAW） 2. 启动通道 → 通道从 CAW 取通道程序 → 控制 I/O 设备 3. I/O 完成 → 通道发出中断 → CPU 处理中断 4. 通道状态字（CSW） 寄存器保存通道 I/O 进展状况

通道分类：字节多路通道 / 选择通道 / 数组多路通道

4.1.3 总线与 I/O（p135-138）

• 单总线 → 三级总线 → 含南北桥的多级总线 → 含 I/O 通道的多级总线
• 总线层级和 Cache 层级共同决定计算机性能差距

4.2 设备管理软件

4.2.1 I/O 软件实现层次（p139-140）

I/O 软件设计四大目标/原则： 1. 设备无关性（编程时不关心物理设备） 2. 出错处理（尽量在低层处理，离硬件近） 3. 同步/异步传输（同步=阻塞；异步=CPU 继续干别的） 4. 缓冲技术（建立缓冲区匹配速度差）

四层结构（自底向上）：

用户空间 I/O 软件（库函数 fwrite/fprintf；SPOOLing 软件；POSIX 库）
─────────────────────────
独立于设备的 I/O 软件（缓冲管理；命名；权限；分配/释放）
─────────────────────────
设备驱动程序（针对具体设备的代码；接收上层请求；操作设备寄存器）
─────────────────────────
中断处理程序（最底层；唤醒等待设备的进程）

4.2.2 设备驱动程序（p141-142）

驱动程序三大功能： 1. 设备初始化（系统启动或传输前预置状态） 2. 执行设备驱动例程（启动设备、传输数据；通道系统还要生成通道指令） 3. 调用与执行中断处理程序（处理设备/控制器/通道的中断）

4.2.3 I/O 缓冲区（p143-145）

为何要缓冲？ - CPU 与设备速度不匹配 - 逻辑记录 ≠ 物理记录 - 减少 I/O 中断次数 / 放宽 CPU 中断响应时间

种类： - 单缓冲（CPU 处理 + 设备 I/O 串行交替） - 双缓冲（一边读一边处理，提高并行度） - 循环缓冲（多个缓冲块循环使用） - 缓冲池（系统级，按需分配）

缓冲管理三件事： 1. 文件打开时分配缓冲区 2. 文件关闭时按 LRU 等策略释放/重用 3. 提供高速缓存操作（写缓存、延迟写、读缓存、预读）

4.3 独占型外围设备的分配（p139-141）

4.3.1 设备独立性

• 设备独立性：用户应用与具体物理设备无关；增减设备无需改源码
• 实现：用户用逻辑设备名，OS 维护”逻辑名 ↔ 物理名” 对照表
• 优点：① 可移植 ② 容错（一台坏自动换） ③ 资源利用率高

4.3.2 分配方式

• 静态分配：作业执行前分配，结束后回收。简单、防死锁，但利用率低（如打印机被占着不打）
• 动态分配：用时分配，用完即收。利用率高，但有死锁风险

例：系统只有 1 台打印机 + 1 台磁带机，进程 P 占打印机想要磁带机，进程 Q 占磁带机想要打印机 → 死锁。需要预先检查避免循环等待。

数据结构：设备类表 + 设备表

4.4 共享型外围设备的驱动（p143-148）

4.4.1 磁盘驱动（p143-144）

磁盘读写周期组成（图 4-12）：

等待设备 + 等待通道 + 寻道 + 旋转延迟 + 数据传输

磁盘存取时间计算公式（核心考点）：

Ta = Ts + 1/(2r) + b/(rN)

• Ts：寻道时间（移臂）
• r：旋转角速度（每秒转数）
• 1/(2r)：平均旋转等待时间（半周）
• b：要读写的数据字节数
• N：每磁道字节数
• b/(rN)：传输时间

4.4.2 磁盘驱动调度

移臂调度算法（5 种）

旋转调度（p145-147）

为减小旋转延迟： 1. 先来先服务 2. 循环排序：按多个柱面访问请求排序 3. 旋转位置测定：硬件需测出磁头当前位置；否则平均要等半周

经典例题（p147）：10 条逻辑记录 A~J 存放在某旋转设备上，旋转一周 20ms，处理每块 4ms。 - 按 A-B-C-D-E-F-G-H-I-J 顺序存：处理总时间 = 10 + 2 + 4 + 9×(16+2+4) = 214 ms - 按 A-H-E-B-I-F-C-J-G-D 优化分布：= 10 + 10×(2+4) = 70 ms（约前者 1/3）

这种排列方式称为”优化分布“。

集簇读写：一次读多个扇区；一组逻辑数据放在同一柱面。

4.5 虚拟设备 SPOOLing（p148-152）

1) 概念

• SPOOL = Simultaneous Peripheral Operations On-Line
• 又称”假脱机”操作：用磁盘 + 缓冲区模拟独占型物理设备
• 把独占设备改造成共享设备，提高利用率
• 是一种”速度匹配技术“

2) 系统组成（图 4-14）

          ┌─────────────┐
输入设备 →│预输入程序   │→ 磁盘输入井（输入缓冲区）
          └─────────────┘
                          ↓
                    [井管理程序]
                          ↓
          ┌─────────────┐
磁盘输出井←│缓输出程序   │→ 输出设备
          └─────────────┘

需要的数据结构： - 作业表：登记进入系统的作业信息（作业名、状态、预输入表位置、缓输出表位置） - 预输入表：登记每个作业的输入文件（设备类、文件名、长度、存放位置） - 缓输出表：登记每个作业的输出文件

典型应用：打印机改造成”虚拟打印机”，多作业可同时”打印”，实际是写入磁盘缓输出井，由系统按序送往真实打印机。

第 4 章本章小结（p152-153）

• 设备管理是 OS 中最庞杂、琐碎的部分
• I/O 设备 = 机械部件 + 电子部件（设备控制器）
• I/O 控制 4 种方式：轮询 / 中断 / DMA / 通道
• 总线由单总线演进至含通道的多级总线
• I/O 软件 4 层 + 缓冲技术（单/双/循环）
• 磁盘 = 直接存取存储设备；驱动调度 = 移臂 + 旋转
• 虚拟设备技术：SPOOLing 为代表

习题四关键应用题（p154-156）

重点记 (1)(3)(11)(12)(14)(15) — 校考核心题型。

(1) CPU 利用率：中断方式 1ms 处理 + 100Hz 中断频率 → 利用率 = 1 - 100×1ms/1s = 90%

(3) 磁盘块号转换公式（必背）

x = k×m×a + k×B + c       —— 逻辑块号 x 由柱面 a、磁头 B、磁道内块号 c 求出
a = (x-1) / (k×m)           —— 反向：由 x 求柱面号
b = ((x-1) % (k×m)) / k     —— 由 x 求磁头号
c = ((x-1) % (k×m)) % k + 1 —— 由 x 求块号

参数：n 柱面、m 磁头、k 物理块/磁道。

例：n=200, m=20, k=10。 - ① 柱面号 185、磁头号 12、块号 5 → x = 10×20×185 + 10×12 + 5 = 37125 - ② 逻辑块 1200 → a, b, c = ? - ③ 磁道内编号从 0 起的转换公式（自推）

(8) 最短查找时间优先：请求队列 8、18、27、129、110、186、78、147、41、10、64、12；磁头当前 100，求总移动柱面数

(10) 旋转圈数最少：5 个请求 (柱面/磁头/扇区) 表，磁头位 1 号柱面，求最优调度

(11) 含 40 磁道的盘面：编号 0-39，磁头位 11；请求依次 1, 36, 16, 34, 9, 12，分别用 FCFS / SSTF / 双向扫描算总移动磁道数

(12) 200 柱面磁盘：磁头 143、刚完成 125；请求顺序 86, 147, 91, 177, 94, 150, 102, 175, 130；分别用 FCFS / SSTF / 双向 / 电梯，求总移动 + 移动顺序

(14) 100 柱面磁头正向减小方向：请求 190, 10, 160, 80, 90, 125, 30, 20, 29, 140, 25；用 SSTF / 电梯计算

(6)(7) 单缓冲 vs 双缓冲传输总时间：T1=磁盘→缓冲，T2=缓冲→用户区（T2 << T1），T3=CPU 处理；计算总时间。 - 单缓冲：(T1 + T2 + T3) × n 或 max(T1+T2, T3) × n + … - 双缓冲：max(T1, T2+T3) × n + 首块开销

四、第 5 章 文件管理（p163-196）

5.1 文件系统概述（p163-167）

文件四大概念

关系：1 卷含多块；1 文件由多记录组成；1 块可存放多记录（成组）或 1 记录跨多块（跨块）。

文件命名

• 文件名 + 扩展名（用圆点分隔）
• MS-DOS：8.3 格式（8 字符名 + 3 字符扩展）
• 早期 UNIX：14 字符
• Windows：最长 255 字符
• 扩展名习惯：.com .exe .lib .bat .obj .txt .asm .c

文件分类

按用途：系统/库/用户文件 按保护：只读/读写/不保护 按数据类型：源程序文件/可执行文件 按设备：磁盘/磁带/光盘/软盘 按结构：逻辑结构 vs 物理结构

引入文件的优点

1. 用户使用方便（按名存取）
2. 文件安全可靠（系统提供保护）
3. 系统管理统一（所有外存设备的信息抽象成文件）

文件系统的组成（图 5-1）

文件系统
├── 文件的组织
│   ├── 组织方法：流式 / 记录式
│   └── 物理结构：顺序 / 连接 / 直接 / 索引
├── 文件的存取
│   └── 顺序 / 直接 / 索引
├── 文件的控制
│   └── 逻辑控制子系统 / 物理控制子系统
└── 文件的使用（系统调用）
    └── 创建 / 撤销 / 打开 / 关闭 / 读写 / 定位

5.2 文件的组织（p167-172）

5.2.1 文件的存储

• 存储介质：磁带、光盘、磁盘
• 卷 = 物理单位；块 = 存储介质上由连续信息组成的区域

5.2.2 文件的逻辑结构

• 流式文件（无结构，UNIX/Linux）：字节流，无逻辑记录
• 记录式文件（有结构）：由若干逻辑记录组成

记录的成组（block factor）

• 一个逻辑记录小于一个物理块时，把若干逻辑记录拼成一组写入一块
• 块因子 = 一个物理块中的逻辑记录数
• 成组（写）+ 分解（读）需要 OS 提供 I/O 缓冲区

5.2.3 文件的物理结构

DOS 的 FAT 文件系统 是连接文件改良：把每块的连接字抽出来集中放在文件分配表中。

散列法冲突处理

• 一种散列算法的好坏 = 不同关键字映射到相同地址的概率
• 常见解决：开放地址 / 链地址 / 再散列

5.3 文件目录（p172-178）

1) 文件控制块 FCB

• 每个文件对应一个 FCB（保存文件属性）
• 内容：文件名、类型、长度、物理位置、存取权限、时间戳…

2) 文件目录

• 文件目录 = FCB 的集合
• 目录文件 = 把目录信息也存为文件
• 一级目录、二级目录、树形（多级）目录

3) 树形层次目录（图 5-8，UNIX 示例）

            /
   ┌───┬───┴───┬───┬───┐
  bin unix   user etc tmp dev
       │      │    │
      lib    user  bin
            ┌─┴─┐
           liu sun fei

• 根目录（/）→ 子目录 → 文件
• 路径名：根目录到文件的所有目录用 /（UNIX）或 \（Windows）分隔
• 绝对路径名：从根目录开始
• 相对路径名：从当前目录开始

4) 嫁接（mount）

• UNIX：通过 mount 把子树挂载到现有树的某个节点；最终形成一棵大树
• Windows：每个分区独立有自己的盘符 → “森林”结构

5.4 文件的共享、保护和保密（p176-179）

5.4.1 文件共享

1) 静态共享

• 多用户共享同一文件 → 文件的多个目录项指向同一 FCB

2) 动态共享

• 进程 A 与 B 通过不同系统打开文件表指向同一主存活动文件表
• 各自维护独立读写指针，互不干扰

3) 符号链接共享（UNIX）

• 硬链接（hard link）：把文件名直接链接到索引结点（i-node）。
• 缺点：不能跨文件系统；不能链接目录
• 软链接 / 符号链接（symbolic link）：只含目标路径名，不指向 i-node。
• 优点：跨文件系统、可链目录、可跨网络
• 缺点：搜索路径开销大

5.4.2 文件保护

• 控制存取权限：读 / 写 / 执行
• UNIX 模型：拥有者 / 组 / 其他用户 × rwx

5.4.3 文件保密

• 加密文件系统

5.5 文件的使用（p180-184）

5.5.1 文件的存取方法

连接文件只能顺序存取（因为没有索引和连续地址）。

5.5.2 文件的使用（系统调用）

5.6 文件系统的实现（p185-190）

5.6.1 文件存储空间管理

文件分配方式

空闲块管理

1) 位示图法（p187-188）

• 用一张二进制位图，每位对应一物理块；1=占用，0=空闲
• 优点：开销极小（每块仅 1 位）；可全装入内存；配合位操作指令快速分配
• 例：1KB/块，位示图开销仅占 0.012%

2) 空闲块成组连接法（p188-189）

• 把空闲块分成多组，每组用一个专用块登记下一组的空闲块号
• 例（Linux）：338 个空闲块分 4 组（编号 12-349），前 39 块在专用块，每 100 块一组，每组首块登下一组
• 分配算法：

IF 空闲块数 == 1 THEN
    IF 第 1 个单元 == 0 THEN 等待
    ELSE 复制第 1 个单元对应块到专用块并分配
ELSE 分配第（空闲块数）个单元对应块；空闲块数减 1

• 归还算法：

IF 空闲块数 < 100 THEN
    专用块的（空闲块数）个单元置归还号
    （空闲块数）++
ELSE
    复制专用块的空闲块数到归还块第 1 单元
    空闲块数置 1
    第 1 单元置归还号

5.6.2 文件系统的实现层次（图 5-14）

用户接口  → 接收系统调用，进行语法检查
逻辑文件控制子系统  → 路径名搜索目录、建活动文件表、转逻辑记录到物理块号
文件保护子系统  → 验证存取权限
物理文件控制子系统  → 缓冲区管理、相对块号转实际块号、调用 I/O
I/O 控制子系统  → 执行物理 I/O

第五章本章小结要点

• 文件 = 一组相关信息按某种结构组织
• 4 个核心概念：卷 / 块 / 记录 / 文件
• 物理结构：顺序、连接、直接、索引
• 目录结构：一级、二级、树形
• 共享：硬链接、软链接、动态共享活动文件表
• 实现：FCB、空闲管理（位示图/成组连接）、5 层结构

习题五关键题（p191-194）

思考题精选： - (1) 给卷/块/记录/文件定义并说明关系 - (4) 文件的物理结构有哪几种组织方式？ - (5) 记录成组分解操作的优点 - (6) 不同访问/更新模式选何种文件组织 - (8) 直接文件解决冲突的方法 - (16) 文件系统的副本技术（备份）

应用题（必练）： - (1) 成组方式存放定长记录：给定文件块数和块因子，求总记录数 - (17) 磁盘块号转换：参数 n=200, m=20, k=10；① 第 56 柱面第 6 磁道第 3 扇区是第几字第几位 ② 回收某物理块时位示图修改 - (18) 层次文件系统的目录共享：给目录树（如题图 5-2），分析能否建/重命名/共享/限制访问 - (19) 多级索引计算最大文件页数 + 读某页最少启动磁盘次数：每磁盘块 512B，地址 4B；前 10 个直接、后 3 个分别一级/二级/三级索引

五、第 6 章 并发程序设计（p197-240，前半）

6.1 顺序与并发程序设计（p197-200）

顺序程序设计的特性

1. 顺序性：严格按序执行
2. 封闭性：独占资源，状态只由自身决定
3. 确定性：结果与执行速度/时段无关，仅与初始输入有关
4. 可再现性：同样输入必产生同样过程和结果

优点：编程调试方便；缺点：系统效率低。

多道程序设计

例（图 6-1）：while(true) {input; process; output;} 顺序结构 → 处理器利用率仅 35%。

把程序拆为三部分：

while(true) { input; send; }
while(true) { receive; process; send; }
while(true) { receive; output; }

→ I/O 设备和 CPU 并行 → 系统效率大幅提升。

并发程序的特征（与顺序对应）

1. 失去封闭性：进程间资源共享 → 互相影响
2. 失去可再现性：执行结果可能与速度有关 → “与时间相关的错误“
3. 失去确定性：可能出现竞态条件

6.2 临界区管理（p201-205）

6.2.1 与时间相关的错误

例 1：飞机票售票问题

T1: X1 = A[j];              /* X1 = m, m>0 */
T2: X2 = A[j];              /* X2 = m */
T2: X2--; A[j] = X2; 输出一张票;   /* A[j] = m-1 */
T1: X1--; A[j] = X1; 输出一张票;   /* A[j] = m-1，错误！应为 m-2 */

两个进程同时给同一座位的两位旅客售票 → 出现同张票卖给两人。

例 2：永远等待问题（借还主存）

int X = memory;
void borrow(int B) {
    while(B > X) {进程进入等待主存资源队列;}
    X = X - B;
    修改主存分配表; 进程获得主存资源;
}
void return(int B) {
    X = X + B;
    修改主存分配表;
    释放等待主存资源进程;
}

错误情景：进程 P 比较 B>X 后被抢占；进程 Q 调用 return() 把 X 增大；但 P 还没进等待队列，Q 的”释放等待进程”等于空操作；之后 P 才进队列，从此永远等待。

6.2.2 临界区与互斥

• 临界资源：必须互斥访问的共享资源
• 临界区：访问临界资源的代码段
• 临界区设计原则： 1. 互斥进入：同一时刻只允许一个进程 2. 空闲让进：无进程在临界区时，请求者立即进入 3. 有限等待：等待时间有上限 4. 让权等待：等待时不应占用 CPU

6.2.3 临界区管理的硬件实现（p205）

1) 关中断

• 进入临界区前关中断，退出后开中断
• 因为单 CPU 进程切换由中断驱动，关中断 = 不被切换
• 缺点：① 临界区代码不能太长 ② 不适用多 CPU ③ 给用户用太危险

2) 测试并设置指令 TS

bool TS(bool x) {
    if(x == false) {
        x = true;
        return true;
    } else {
        return false;
    }
}

• 是原子指令
• 互斥模板：while(!TS(lock)); 进临界区；lock = false; 出
• 缺点：忙等

3) 对换指令 Swap

类似 TS，原子地交换两个变量。

6.3 PV 操作（p206-218）

6.3.1 信号量与 PV 原语（p206-208）

• 信号量 s：含 value 整数 + 等待队列 list
• 信号量分类：整型 / 记录型 / AND型 / 信号量集

procedure P(semaphore s) {
    s.value = s.value - 1;
    if(s.value < 0) W(s.list);   /* 阻塞调用者 */
}

procedure V(semaphore s) {
    s.value = s.value + 1;
    if(s.value <= 0) R(s.list);  /* 唤醒队列首进程 */
}

• PV 操作必须是不可中断的原语
• 等待队列采用 FIFO 策略

推论

1. 若 s.value > 0：等于实际可用资源数
2. 若 s.value < 0：其绝对值等于等待队列中进程数
3. P 操作通常意味”申请资源”；V 操作意味”释放资源”

6.3.2 PV 解决进程互斥（p209）

semaphore mutex;
mutex = 1;
cobegin
    process Pi() {  /* i = 1, ..., n */
        ...
        P(mutex);
        { 临界区 }
        V(mutex);
        ...
    }
coend

• n 个进程互斥时，mutex 取值范围 [-(n-1), 1]
• 当 mutex = -(n-1)：1 个在临界区内，n-1 个在等待队列

应用：飞机票售票（修正版）

int A[m];
semaphore s;
s = 1;
cobegin
    process Pi() {
        int Xi;
        ...
        P(s);
        Xi = A[j];
        if(Xi >= 1) {
            Xi--;
            A[j] = Xi;
            输出一张票;
        }
        V(s);
        ...
    }
coend

6.3.3 PV 解决进程同步（生产者-消费者）

单缓冲区（一生产者一消费者）

• 设两同步信号量 sget（缓冲区有产品数）、sput（缓冲区空位数）
• 生产者：P(sput); 放产品; V(sget);
• 消费者：P(sget); 取产品; V(sput);

多缓冲区（k 个，循环队列）（p214）

int B[k];
semaphore sput, sget;
sput = k;     /* 空位数 */
sget = 0;     /* 产品数 */
int putptr = 0, getptr = 0;

cobegin
    process producer_i() {
        L1: produce a product;
        P(sput);
        B[putptr] = product;
        putptr = (putptr + 1) mod k;
        V(sget);
        goto L1;
    }
    process consumer_j() {
        L2: P(sget);
        product = B[getptr];
        getptr = (getptr + 1) mod k;
        V(sput);
        consume a product;
        goto L2;
    }
coend

注意：putptr 仅生产者用；getptr 仅消费者用；它们不是共享变量，只有 B[k] 是共享变量。

多生产者多消费者

还要加一个 mutex 信号量保护 B、putptr、getptr。

6.3.4 经典同步问题（p215-218）

• 哲学家进餐：5 哲学家 5 筷子；防死锁策略：① 至多 4 人同时拿 ② 编号奇偶不同顺序 ③ 同时拿两根筷子（AND 信号量）
• 读者-写者：多读者可并发；写者独占
• 读者优先 / 写者优先 / 公平
• 理发师问题：n 把椅子；同步 customers、barbers、mutex

6.4 管程（p219-225）

1) 管程的提出动机

• PV 操作分散在程序各处 → 易错（顺序错、漏 V、漏 P）
• 管程把”共享变量 + 操作过程”封装起来，编译器保证互斥

2) 管程的组成

type 管程 = monitor {
    共享变量;
    条件变量;
    访问过程 1();
    访问过程 2();
    ...
    initialize_code;
}

• 互斥：编译器自动保证一次只能一个进程在管程内
• 条件变量操作：wait(c)、signal(c)

3) 霍尔（Hoare）管程

• 实现需 mutex（互斥进入，初值 1）+ next（被释放进程阻塞自己，初值 0）+ next_count
• signal 唤醒等待进程后，调用 signal 的进程要阻塞在 next 上
• 优点：被唤醒进程能立即拿到 mutex 执行

typedef struct interf {
    semaphore mutex;
    semaphore next;
    int next_count;
}

4) 汉森（Hansen）管程

• signal 必须是过程体的最后一个操作 → 简化但限制大

5) 管程实现读者-写者

procedure end_read() {
    rc = rc - 1;
    if(rc == 0) signal(W, Wc, IM);
}

procedure end_write() {
    wc = wc + 1;
    if(rc > 0 || wc > 1) wait(W, Wc, IM);
}

6.5 进程通信（p226-235，前段）

6.5.1 通信级别

• 低级通信：信号量 + PV，只能传少量信息
• 高级通信：进程间通信机制（IPC）传递大量数据

6.5.2 进程直接通信

• 必须显式指定发/收方
• 原语：send(目标, 消息) / receive(源, 消息)

6.5.3 进程间接通信（信箱）

• 通过中间实体——信箱
• 进程发消息到信箱；进程从信箱取消息
• 解耦发送方/接收方

6.5.4 共享存储系统

• 多个进程映射同一物理页面到各自虚地址空间
• 通信效率最高，但需 PV 同步保护

6.5.5 基于流的通信（管道、套接字）

发送进程 1 ─write(字节流)→ 管道/多路转接器/套接字 ─read(字节流)→ 接收进程 1
发送进程 M ─write(字节流)→                                  ─read(字节流)→ 接收进程 N

• 字节流；按 FIFO；自带缓冲；自动同步（满阻塞写，空阻塞读）

6.5.6 RPC（远程过程调用）

• 把单机过程调用拓展到分布式环境
• 客户机存根 client stub + 服务器存根 server stub
• 流程：客户调用 → client stub 打包参数 → send → 服务器 stub 收 → 解包调真过程 → 结果回包 → 返回

6.6 死锁（开端，p236-240 早段）

此处只覆盖到死锁概念与必要条件、银行家算法开篇；详见后段笔记。

死锁定义

一组进程中每个进程都在等待只能由该组其他进程才能引发的事件，这种永久等待状态称为死锁。

死锁四必要条件

1. 互斥使用
2. 占有并等待（hold and wait）
3. 不可剥夺（no preemption）
4. 循环等待（circular wait）

四条件同时满足才会死锁。打破任一条件即可避免死锁。

六、跨章对比与关键思维

1) 三大基础抽象的统一

2) “缓冲匹配速度差”的反复出现

• I/O 缓冲区（4.2.3）：CPU - 设备
• 文件系统缓冲（5.6）：内存 - 磁盘
• SPOOLing 输入井 / 输出井（4.5）：作业 - 独占设备

3) 互斥实现路径

关中断（最原始） → TS 指令 / Swap（硬件原子） → PV 操作（OS 原语） → 管程（语言级）

每往上一层抽象都更易用、更安全，但需要更多基础支撑。

4) 必背计算公式

磁盘存取时间        Ta = Ts + 1/(2r) + b/(rN)
块号正向转换        x = k×m×a + k×B + c
块号反向转换        a = (x-1)/(km), b = ((x-1) mod km)/k, c = ((x-1) mod km) mod k + 1
平均访存时间        T = A + (1/n)×(B + (1/m)×C)   （3 级存储）
互斥信号量取值范围  mutex ∈ [-(n-1), 1]
缺页率上限          T_avg ≤ 给定上限 → 反推 p

七、对应关系总览

标注本笔记各节对应学校 OS 课程的章节。

八、疑点与待补

1. 银行家算法的完整步骤在本段末仅起头，详细推导需在后段笔记补全
2. p138 (img-138) 第 4 章封面页未读，但章节起首在 p129 已展开
3. 文件系统的 iNode 详细结构 教材未必详细给出，可能在课后教辅
4. 习题部分的题目较多但没有提供答案；考试前需另找参考解答
5. TS 指令实现的 lock = false 解锁与 PV 区别：TS 是忙等；PV 是阻塞，区别要在校考中强调

采样统计：精读了约 35 张关键页： p121-123, 125, 128, 130, 133, 136, 139, 140, 143, 146, 150, 152, 155, 156, 158, 163, 165, 166, 170, 172, 176, 180, 185, 190, 194, 195, 198, 202, 205, 208, 212, 216, 219, 225, 232, 237。

跳过策略：纯过渡页、纯习题应用题（已采样章末习题首页）、重复内容页、二维码页（微视频页）。

九、图清理报告（p121-240）

• 范围：PDF 页 121-240（120 张候选），文件名格式 img-{N}-{P}.jpg（N=P+1）。
• 删除：79 张（纯文字段落、习题题面、过渡页、微视频二维码）— notes-part2 已用文字完整覆盖，无图片嵌入引用。
• 保留：41 张作为档案
• 35 张精读关键页：p121-123, 125, 128, 130, 133, 136, 139, 140, 143, 146, 150, 152, 155, 156, 158, 163, 165, 166, 170, 172, 176, 180, 185, 190, 194, 195, 198, 202, 205, 208, 212, 216, 219, 225, 232, 237
• 章首/小结：p138（ch4 封面）、p153（ch4 小结首页）、p197（ch6 封面）
• 范围相邻：p119, p120（与上段衔接）
• 抽样验证：p125（习题三题面 / 纯文字）、p145（4.2.3 缓冲区段首带二维码）、p160（SPOOLing 系统结构图，但 p150 已保留同主题）、p175（文件组织段落文字）、p190（第 5 章本章小结纯文字）、p220（PV 售票代码，但 p219 已保留管程同区段）— 全部确认可删。
• 体积：128.2MB → 99.8MB，节省 28.3MB（删除幅度 22%；本批 121-240 范围内 79/120 = 66% 删除率）。