# 📖 操作系统（Operating System）—— 408考研完全笔记

## 相关笔记

- [[DS]]：进程调度、死锁、页面置换、文件索引都依赖队列、图、树和查找结构。
- [[CO]]：中断、存储系统、虚拟地址转换和 CPU 执行机制是理解操作系统的硬件基础。
- [[CN]]：并发、缓冲、拥塞与可靠传输问题可以和操作系统资源管理模型对照学习。

> **编写说明**：本笔记严格依据全国硕士研究生招生考试计算机学科专业基础（科目代码：408/11408）考试大纲编写，融合汤子瀛《计算机操作系统》、Operating System Concepts（恐龙书）、CSAPP 与王道课程体系，力求概念严谨、表达通俗、解题实战。
>
> **考试概况**：408统考满分150分，考试时间180分钟（3小时）。其中数据结构约45分，计算机组成原理约45分，**操作系统约35分（约23%）**，计算机网络约25分。操作系统常见题型为：选择题约10道（20分）+综合应用题1~2道（约15分）。
>
> **高频核心章**：第2章进程与线程、第3章调度与死锁、第4章同步互斥、第5-6章存储管理与虚拟内存、第7章I/O系统、第8章文件管理。

---

# 第一章 操作系统引论

## 1.1 操作系统的目标和作用

### 操作系统的四个目标

| 目标 | 说明 |
|:---:|:---|
| **方便性** | 提供良好用户接口，使计算机更易使用 |
| **有效性** | 提高系统资源利用率和系统吞吐量 |
| **可扩充性** | 能方便地增加新功能模块，适应硬件和应用发展 |
| **开放性** | 遵循国际标准，通过兼容层实现软件互操作 |

### 操作系统的作用

1. **OS是用户与计算机硬件之间的接口**
2. **OS是计算机系统资源的管理者**（处理机、存储器、I/O设备、文件）
3. **OS实现了对计算机资源的抽象**（隐藏硬件细节，提供虚拟机）

### 推动OS发展的主要动力
- 不断提高计算机资源利用率
- 方便用户使用
- 器件的不断更新换代
- 计算机体系结构的不断发展和更新
- 不断提出新的应用需求

---

## 1.2 操作系统的发展过程

| 阶段 | 特点 | 优缺点 |
|:---|:---|:---|
| **人工操作** | 用户独占全机 | CPU利用率极低，人机矛盾 |
| **脱机I/O** | 引入磁带，外围机处理I/O | 减少CPU空闲时间 |
| **单道批处理** | 监督程序控制作业自动处理 | 自动性，顺序性，内存始终一道作业 |
| **多道批处理** | 内存中同时驻留多道程序 | **多道性、无序性、调度性**；缺乏交互能力 |
| **分时系统** | 多用户同时联机交互 | **多路性、独立性、及时性、交互性**；不能满足实时需求 |
| **实时系统** | 在规定时间内完成处理并给出响应 | **及时性、可靠性** |
| **微机操作系统** | 单用户单任务(MS-DOS)→单用户多任务(Windows)→多用户多任务(UNIX/Linux) | 广泛普及 |
| **嵌入式操作系统** | 微型化、可定制、实时性、可靠性 | 资源受限环境 |
| **网络操作系统** | 提供网络服务（文件/打印/通信） | C/S模式 |
| **分布式操作系统** | 多台计算机协同工作，统一管理 | 透明性、模块化 |

> **⚠️ 关键辨析**：
> - **多道批处理 vs 分时系统**：多道批处理追求**吞吐量**，分时系统追求**响应时间**
> - **硬实时 vs 软实时**：硬实时必须在截止时间内完成（如武器控制），否则灾难性后果；软实时偶尔超时可接受（如视频播放）

---

## 1.3 操作系统的基本特性（重点⭐）

### 四大基本特性

| 特性 | 定义 | 关键点 |
|:---|:---|:---|
| **并发** | 宏观上多个事件在同一时间段发生 | ≠并行（并行是同一时刻，需多CPU）；并发是OS最基本特征 |
| **共享** | 系统资源可供多个并发进程共同使用 | 互斥共享（临界资源一个时刻只一个进程用）/ 同时共享（宏观同时微观交替） |
| **虚拟** | 通过某种技术变一个物理设备为多个逻辑设备 | 时分复用（虚拟处理机/虚拟设备）/ 空分复用（虚拟存储器） |
| **异步** | 进程以不可预知的速度走走停停地推进 | 并发执行导致；OS须保证运行结果可再现 |

> **⚠️ 关系**：**并发和共享是OS两个最基本特征**，互为存在条件。虚拟以并发为前提，异步以并发为前提。没有并发和共享就谈不上虚拟和异步。

---

## 1.4 操作系统的运行环境

### 处理器的双重工作模式
- **用户态（目态）**：普通用户程序运行的状态，不能执行特权指令
- **核心态（管态/内核态）**：OS内核运行的状态，可执行全部指令

### 特权指令与非特权指令
- **特权指令**：仅在核心态可执行（如I/O指令、置中断指令、存取特殊寄存器指令等）
- **非特权指令**：在用户态和核心态均可执行

### 中断与异常
- **中断（外中断）**：由CPU外部I/O设备引起（如I/O完成中断、时钟中断）
- **异常（内中断/陷入/陷阱）**：由CPU内部事件引起（如除零、缺页、系统调用trap指令）

> **⚠️ 用户态→核心态**：**唯一途径是中断或异常**（也包括系统调用，实质是通过trap指令触发中断）
> **核心态→用户态**：通过设置程序状态字PSW即可

---

## 1.5 操作系统的主要功能

| 功能 | 子功能 | 说明 |
|:---|:---|:---|
| **处理机管理** | 进程控制、进程同步、进程通信、调度 | 最核心的管理功能 |
| **存储器管理** | 内存分配与回收、地址映射、内存保护、内存扩充 | 逻辑→物理地址变换 |
| **设备管理** | 缓冲管理、设备分配、设备处理 | 隐藏设备细节 |
| **文件管理** | 文件存储空间管理、目录管理、读写管理、保护 | 方便用户使用 |
| **接口管理** | 命令接口(CLI)、程序接口(系统调用)、图形接口(GUI) | 面向用户和程序 |

### 现代OS的新功能
- **安全保障**：认证技术、密码技术、访问控制技术、反病毒技术
- **联网和服务功能**
- **多媒体支持**

---

## 1.6 操作系统的结构（重点⭐）

| 结构 | 优点 | 缺点 | 典型代表 |
|:---|:---|:---|:---|
| **简单结构** | 简单,执行效率高 | 无模块划分,难维护 | MS-DOS |
| **模块化结构** | 模块-接口法,模块间以接口通信 | 模块划分标准不统一,接口不清晰 | — |
| **分层式结构** | 自底向上逐层构建,正确性易保证,维护性好 | 效率较低(每层都有额外开销) | THE系统 |
| **微内核结构** | 足够小的内核+客户-服务器模式,可扩展/可靠/可移植/支持分布式/面向对象 | 上下文切换开销大(原需4次切换,微内核需8次) | Mach, Windows NT |
| **外核结构** | 物理资源直接隔离与复用,减少映射层,库OS实现抽象 | 兼容性差 | Exokernel(MIT) |

### 微内核结构
- **微内核功能仅包含**：①进程（线程）管理 ②低级存储器管理 ③中断和陷入处理
- **基本概念**：足够小的内核 + 客户-服务器模式 + 策略与机制分离 + 面向对象
- **应用机制与策略分离**：内核中只有机制（如进程调度机制），策略在用户进程中

---

## 1.7 系统调用

**系统调用**：OS提供给应用程序使用OS服务的接口（唯一接口）。

### 系统调用与一般过程调用的4个主要区别

| 方面 | 系统调用 | 一般过程调用 |
|:---|:---|:---|
| 运行状态 | 用户态→核心态→用户态 | 保持在用户态 |
| 状态转换 | 通过中断机构进入核心态(INT 80H或trap) | 无状态转换 |
| 返回问题 | 可能不返回调用进程（如被更高优先级抢占） | 总是返回调用者 |
| 嵌套 | 嵌套深度有限 | 可任意嵌套/递归 |

### 系统调用的类型
1. **进程控制类**：创建/终止进程、加载/执行程序
2. **文件操纵类**：创建/删除/打开/关闭/读/写文件
3. **进程通信类**：发送/接收消息
4. **设备管理类**：请求/释放设备
5. **信息维护类**：获取/设置时间日期、系统数据

> **Linux系统调用补充**：早期x86可通过 `INT 0x80`，现代x86-64主要使用 `syscall` 指令进入内核。

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2012Q23、2015Q24、2019Q25、2023Q23/Q24/Q26、2024Q23、2025Q23/Q24
- **优质例题**：给定事件“除零、DMA完成、系统调用、缺页”，判断其属于中断/异常及是否会导致用户态→核心态。
- **最短解题模板**：
  1. 先判来源：外设=外中断；CPU内部=异常。
  2. 再判态切换：发生中断/异常→必入核心态处理。
  3. 最后排除干扰：普通算术/逻辑指令通常不触发态切换。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：外设中断、内部异常、trap入核。
- **口令**：用户态禁特权，系统调用走内核。
- **口令**：判题三步：来源→态切换→干扰项。

---

# 第二章 进程的描述与控制

## 2.1 前趋图和程序执行

### 前趋图（DAG）
- 有向无循环图（DAG），用于描述进程间的前后关系
- 节点表示语句/程序段/进程，有向边表示前趋关系

### 程序顺序执行的特征
1. **顺序性**：严格按顺序执行
2. **封闭性**：程序独占全部资源，结果不受外界影响
3. **可再现性**：输入相同→结果相同

### 程序并发执行的特征
1. **间断性**：执行—暂停—执行
2. **失去封闭性**：共享资源，执行环境被外界影响
3. **不可再现性**：结果可能因调度顺序不同而不同

---

## 2.2 进程的描述

### 进程的定义
- **进程是程序的一次执行过程**
- **进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位**（引入线程后，线程成为调度的基本单位）

### 进程的特征
| 特征 | 说明 |
|:---|:---|
| **动态性**（最基本） | 进程有创建、运行、消亡的生命周期 |
| **并发性** | 多个进程可同时存在于内存中并发执行 |
| **独立性** | 进程是独立运行和获得资源的基本单位 |
| **异步性** | 各进程按各自独立、不可预知的速度推进 |

### 进程的状态

**三态模型**：
```
        就绪 ——调度——→ 运行
         ↑               ↓
         ← —事件完成—— 阻塞
         ↑               ↓
         ←←←←←←←←←←←←←
                时间片完/被抢占
```

**五态模型**：就绪、运行、阻塞 + **创建、终止**

![进程五态转换图](图表/OS/01_进程五态转换图.png)

**七态模型**（含挂起）：
- 活动就绪 ↔ 静止就绪（挂起）
- 活动阻塞 ↔ 静止阻塞（挂起）

![七态模型状态转换图](图表/OS/11_七态模型状态转换图.png)

> **挂起(Suspend)**：进程从内存调至外存；**激活(Active)**：进程从外存调回内存

### 进程控制块 PCB

PCB是进程存在的**唯一标志**，包含4类信息：

| 类别 | 内容 |
|:---|:---|
| **进程标识符** | 内部标识符（PID数字标识）、外部标识符（用户使用的名称） |
| **处理机状态** | 通用寄存器、PC、PSW、用户栈指针 |
| **进程调度信息** | 进程状态、优先级、事件（阻塞原因）、调度其他信息 |
| **进程控制信息** | 程序和数据地址、同步和通信机制、资源清单、链接指针 |

**PCB的组织方式**：
1. **线性方式**：所有PCB放在一个线性表中
2. **链接方式**：按状态链成多个队列（就绪队列、阻塞队列等）
3. **索引方式**：建立索引表，表项指向PCB

---

## 2.3 进程控制

进程控制通过**原语**实现（原语在内核态执行，不可中断）。

| 原语 | 功能 |
|:---|:---|
| **创建原语** | 分配PID→分配资源→初始化PCB→插入就绪队列 |
| **终止原语** | 查找PCB→若进程正在运行则终止→终止其子孙进程→归还资源→删除PCB |
| **阻塞原语** | 将进程从运行态→阻塞态，保存现场，插入等待队列 |
| **唤醒原语** | 从等待队列移出→将进程从阻塞态→就绪态，插入就绪队列 |
| **挂起原语** | 活动就绪→静止就绪，或活动阻塞→静止阻塞 |
| **激活原语** | 静止就绪→活动就绪，或静止阻塞→活动阻塞 |

> **⚠️ 阻塞和唤醒必须成对出现**！阻塞由进程自己调用（主动），唤醒由其他相关进程调用（被动）。

---

## 2.4 进程通信

| 方式 | 说明 |
|:---|:---|
| **共享存储器** | 多个进程通过读/写共享内存区域通信；需同步互斥机制保护 |
| **管道(pipe)** | 半双工，固定大小缓冲区(通常4KB)，**FIFO字节流**；写满时写进程阻塞,读空时读进程阻塞；连接读写进程的共享文件 |
| **消息传递** | **直接通信**：点对点,send(P,msg)/receive(Q,msg)；**间接通信**：通过邮箱,send(A,msg)/receive(A,msg) |
| **客户机-服务器** | socket（套接字,可跨网络）/ RPC（远程过程调用） |

---

## 2.5 线程

### 线程的概念
- **线程是CPU调度的基本单位**
- **进程是资源分配的基本单位**
- 一个进程可包含多个线程，共享进程资源
- 线程比进程更轻量，切换开销更小

### 进程 vs 线程

| 比较项 | 进程 | 线程 |
|:---|:---|:---|
| 资源分配 | 资源分配的基本单位 | 不拥有系统资源(共享进程资源) |
| 调度 | (无线程时)调度的基本单位 | 调度的基本单位 |
| 并发性 | 进程间可并发 | 进程内的多线程也可并发 |
| 系统开销 | 进程创建/撤销/切换开销大(需切换页表导致TLB失效/Cache冷) | 线程切换开销小(不切换地址空间,TLB/Cache仍有效) |
| 独立性 | 进程间独立 | 同一进程内的线程共享地址空间 |

### 线程控制块 TCB
包含：线程标识符、寄存器状态（PC、PSW、通用寄存器）、线程运行状态、优先级、栈指针等。

### 线程的实现方式

| 方式 | 优点 | 缺点 |
|:---|:---|:---|
| **用户级线程ULT** | 不需内核支持,切换快,进程可专用调度算法,平台无关 | 一个线程阻塞→整个进程阻塞；不能利用多处理机 |
| **内核级线程KST** | 多处理机上可并行,一线程阻塞不影响其他,内核本身也可多线程 | 模式切换开销大(用户态→内核态) |
| **组合方式** | 结合两者优点 | 实现复杂 |

### 多线程模型

| 模型 | 说明 | 缺点 |
|:---|:---|:---|
| **多对一** | 多个ULT映射到一个KST | 一阻塞全阻塞，不能多处理机并行 |
| **一对一** | 每个ULT对应一个KST | 创建开销大（如Windows NT） |
| **多对多** | 多个ULT映射到≤ULT数的KST | 结合优点,最灵活 |

### 轻量级进程(LWP)
- 作为ULT与KST之间的中间层
- 每个LWP连接一个KST
- ULT通过LWP间接使用内核服务

---

## 2.6 程序运行环境与进程内存映像（2026趋势）

### 进程内存映像（Memory Image）

典型用户进程地址空间自低地址到高地址可概括为：

`text(代码段) → data(已初始化全局/静态区) → bss(未初始化全局/静态区) → heap(堆,向高地址增长) ... stack(栈,向低地址增长)`

- **text段**：机器指令与只读常量，通常只读且可共享
- **data段**：已初始化的全局变量和静态变量
- **bss段**：未初始化全局变量和静态变量（装入时清零）
- **heap堆**：由 `malloc/new` 等动态扩展和回收
- **stack栈**：函数调用现场、局部变量、返回地址

> **⚠️ 易考辨析**：进程共享“代码和只读数据”通常发生在同一程序多进程场景；线程共享进程地址空间，但各线程栈独立。

### fork 与 COW（写时复制）

- `fork()` 后父子进程最初共享物理页框（只读映射）
- 任一方尝试写入时触发保护异常，OS复制该页（Copy-On-Write）
- COW的目标：减少无效复制开销，提高创建子进程效率

---

## 2.7 信号（Signal）机制（2025新增）

### 信号的本质
- **信号是软件层面的异步事件通知机制**，用于告知进程“发生了某事件”
- 信号不是数据传输通道，主要表达“发生了什么”而非“传了什么”

### 信号处理方式
1. **默认处理**（终止/忽略/停止/继续/核心转储）
2. **显式忽略**（部分信号可忽略）
3. **自定义处理函数**（signal handler）

### 常见高频信号
- `SIGKILL(9)`：立即终止，**不可捕获、不可忽略**
- `SIGTERM(15)`：请求终止，可被捕获处理
- `SIGCHLD`：子进程状态变化通知父进程
- `SIGSEGV`：非法内存访问

### 生命周期与检查时机
- 流程：**产生（generate）→ 未决（pending）→ 递送（deliver）→ 处理（handle）**
- 内核通常在**从核心态返回用户态前**检查并递送可处理信号

### 信号 vs 信号量（常考）

| 对比项 | 信号（Signal） | 信号量（Semaphore） |
|:---|:---|:---|
| 作用 | 异步事件通知 | 同步与互斥 |
| 是否计数资源 | 否 | 是（value体现资源数/等待数） |
| 典型场景 | 进程终止、异常通知、子进程回收 | 生产者-消费者、互斥临界区 |

> **⚠️ 一句话区分**：Signal解决“事件到了吗”，Semaphore解决“资源够不够/次序对不对”。

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2011Q25、2014Q26、2017Q27、2019Q23/Q24、2024Q24/Q25/Q28、2025Q22/Q46
- **优质例题**：判断“创建子进程、I/O完成、时间片用完、请求I/O”引起的进程状态转换。
- **最短解题模板**：
  1. 建立五态图：就绪、执行、阻塞及方向箭头。
  2. 逐事件映射：时间片到期→执行→就绪；I/O请求→执行→阻塞；I/O完成→阻塞→就绪。
  3. 涉及线程时先判“共享什么”：地址空间共享，栈/寄存器私有。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：时间片到=就绪；等I/O=阻塞；I/O完=就绪。
- **口令**：进程管资源，线程管调度。
- **口令**：共享地址空间，私有栈与寄存器。

---

# 第三章 处理机调度与死锁

## 3.1 处理机调度的层次

| 层次 | 又称 | 频率 | 功能 |
|:---|:---|:---|:---|
| **高级调度（作业调度）** | 长程调度 | 最低 | 从外存后备队列中选择作业调入内存,创建进程 |
| **中级调度（内存调度）** | 中程调度/对换调度 | 中等 | 决定哪些进程可参与竞争CPU（挂起/激活） |
| **低级调度（进程调度）** | 短程调度 | **最高（最频繁）** | 从就绪队列中选一个进程分配CPU |

> **⚠️ 低级调度（进程调度）是最基本的调度**，任何OS都必须有。多道批处理系统需要高级调度+低级调度，分时系统通常不需要高级调度。

---

## 3.2 调度的目标和准则

### 调度的共同目标
- **资源利用率高**：CPU利用率 = CPU有效工作时间 / 总时间
- **公平性**
- **平衡性**
- **策略强制执行**

### 不同系统的目标

| 系统类型 | 主要目标 |
|:---|:---|
| 批处理 | 平均周转时间短、吞吐量高、处理机利用率高 |
| 分时 | 响应时间快、均衡性 |
| 实时 | 满足截止时间、可预测性 |

### 重要公式⭐

$$\bar{T} = \frac{1}{n}\sum_{i=1}^{n}T_i$$

其中 $T_i = $ 作业完成时间 $-$ 作业提交时间 = 周转时间

$$W_i = \frac{T_i}{T_{si}} \quad \text{（带权周转时间，}T_{si}\text{为实际服务时间）}$$

$$\bar{W} = \frac{1}{n}\sum_{i=1}^{n}W_i \quad \text{（平均带权周转时间）}$$

---

## 3.3 调度算法（核心考点⭐⭐⭐）

### 3.3.1 先来先服务 FCFS

- **按到达先后顺序**调度
- **非抢占式**
- 对**长作业有利，短作业不利**
- 常与其他算法结合使用
- 既可作业调度,也可进程调度

### 3.3.2 短作业/进程优先 SJF/SPF

- 选择**估计运行时间最短**的作业优先
- **非抢占式SJF / 抢占式SRTN（最短剩余时间优先）**
- 平均周转时间和平均带权周转时间最小
- **缺点**：①须预知运行时间 ②长作业可能饥饿 ③无法用于交互式系统 ④忽视紧迫性

### 3.3.3 优先级调度

- **非抢占式**：一旦某进程获得CPU，就一直运行到完成或阻塞
- **抢占式**：有更高优先级进程到达时立即抢占

**优先级的类型**：
- **静态优先级**：创建时确定，不再改变（依据：进程类型、资源需求、用户要求）
- **动态优先级**：随运行情况动态调整（如等待时间越长优先级越高）

### 3.3.4 高响应比优先 HRRN

$$R_P = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}$$

- **$R_P$ 最高的优先调度**
- 兼顾短作业和长作业（短作业天然响应比高,长作业等久了响应比也升高）
- **非抢占式**
- 缺点：每次调度前都要重新计算所有作业的响应比，增加开销

### 3.3.5 时间片轮转 RR

- 专门为**分时系统**设计
- 所有就绪进程排成FIFO队列，每次分配一个时间片q
- **q太小** → 上下文切换频繁，开销大
- **q太大** → 退化为FCFS
- q的经验值：略大于一次典型交互的时间

### 3.3.6 多级队列调度

- 设置多个就绪队列，不同队列可有不同调度算法和不同优先级
- 适合多处理机系统

### 3.3.7 多级反馈队列调度 MLFQ（⭐⭐⭐）

**公认的较好的调度算法**，兼顾多种类型作业。

**算法规则**：
1. 设置多个就绪队列，优先级**递减**，时间片**递增**
2. 新进程进入第1级队列末尾，按FCFS等待调度
3. 若在当前时间片内未完成，降至下一级队列末尾
4. **仅当第k级队列为空时，才调度第k+1级队列**
5. 若有新进程进入较高优先级队列，可抢占当前运行进程

**优点**：终端型用户（短作业快速响应）、短批处理作业用户（周转时间短）、长批处理作业用户（不会饥饿）都能满足。

### 3.3.8 公平调度

- **保证调度**：N个进程，每个保证获得1/N的处理机时间。实际/应得比率最小的优先
- **公平分享调度（FSS）**：按用户分配CPU时间，保证用户层面公平

---

## 3.4 实时调度

### 可调度条件

$$\sum_{i=1}^{m}\frac{C_i}{P_i} \leq 1 \quad \text{（单处理机）}$$

$$\sum_{i=1}^{m}\frac{C_i}{P_i} \leq N \quad \text{（N个处理机）}$$

其中 $C_i$ = 处理时间，$P_i$ = 周期

### 实时调度分类

| 类别 | 方式 | 响应时间 |
|:---|:---|:---|
| 非抢占轮转 | 轮转调度 | 数秒~数十秒 |
| 非抢占优先级 | 优先级+非抢占 | 数百ms~数秒 |
| 抢占-时钟中断 | 在时钟中断时抢占 | 几ms~几十ms |
| 抢占-立即抢占 | 事件发生立即抢占 | 几百μs~几ms |

### 最早截止时间优先 EDF

- **截止时间越早，优先级越高**
- 可用于抢占式/非抢占式
- 对**隐式截止期任务集**（$D_i=P_i$），单处理机下 $\sum C_i/P_i \le 1$ 是**充要条件**
- 若任务模型不满足 $D_i=P_i$，则需结合具体约束（如$D_i$与$P_i$关系、是否可抢占）进一步判定

### Rate Monotonic（RM）补充

- RM为固定优先级实时调度（周期越短优先级越高）
- RM充分条件（不是必要条件）：

$$U = \sum_{i=1}^{n}\frac{C_i}{P_i} \le n\left(2^{1/n}-1\right)$$

- 当 $n \to \infty$ 时，上界趋近于 $\ln 2 \approx 0.693$

### 最低松弛度优先 LLF

$$\text{松弛度} = \text{必须完成时间} - \text{剩余运行时间} - \text{当前时间}$$

- 松弛度越小，越紧迫，优先级越高
- 松弛度=0时必须立即执行
- 主要用于**抢占式**调度

### 优先级倒置问题⭐

**问题**：高优先级进程被低优先级进程间接阻塞。

**典型场景**：P1(高)→P2(中)→P3(低)。P3进入临界区持有共享资源；P1需要该资源被阻塞；P2就绪抢占P3运行→P3无法释放资源→P1一直被阻塞。

**解决方案**：
1. **简单方法**：进程进入临界区后，不允许被抢占（缺点：临界区长则影响系统）
2. **动态优先级继承**：P3继承P1的高优先级→P2无法抢占P3→P3尽快完成释放资源→P1得以运行

---

## 3.5 Linux CFS调度器

- **调度器类**优先级：Stop > Real_Time > Fair > Idle
- **友好值nice**：-20~+19，默认0
- **虚拟运行时间vruntime**：nice值越大，vruntime增长越快；调度时选vruntime最小的
- 实时调度：SCHED_FIFO / SCHED_RR，静态优先级0-99
- 普通调度：优先级100-139（对应nice -20~+19）

---

## 3.6 死锁（核心考点⭐⭐⭐）

### 死锁的定义
多个进程因竞争资源而造成的一种**互相等待**的僵局。

### 死锁的四个必要条件

| 条件 | 说明 |
|:---|:---|
| **互斥条件** | 资源一次只供一个进程使用 |
| **请求和保持条件** | 进程持有至少一个资源,又请求新资源,但新资源被占用而阻塞,此时不释放已持有的 |
| **不可抢占条件** | 已获得的资源未使用完之前不能被强行夺走 |
| **循环等待条件** | 存在进程-资源的环形等待链 |

> **⚠️ 四个条件缺一不可**。循环等待是死锁的**必要不充分条件**（有循环等待不一定死锁,但死锁必有循环等待）

### 死锁的处理策略

| 策略 | 方法 |
|:---|:---|
| **预防** | 破坏四个必要条件之一(除互斥外) |
| **避免** | 银行家算法（动态检测安全性） |
| **检测和解除** | 资源分配图,死锁定理 |
| **忽略（鸵鸟策略）** | 不处理,如UNIX/Linux一般采用 |

### 死锁预防

| 破坏条件 | 方法 | 缺点 |
|:---|:---|:---|
| 请求和保持 | 一次性申请全部资源 | 资源浪费严重,可能饥饿 |
| 不可抢占 | 请求新资源不满足时释放已有的 | 实现复杂,可能导致已有工作丢失 |
| 循环等待 | 资源编号,按序申请 | 资源编号不灵活,可能浪费 |

### 银行家算法（⭐⭐⭐核心）

**数据结构**：
- $Available[m]$：当前各类资源的可用数量
- $Max[n][m]$：每个进程对各类资源的最大需求
- $Allocation[n][m]$：已分配给每个进程的各类资源数量
- $Need[n][m]$：每个进程还需要的各类资源数量

$$Need[i][j] = Max[i][j] - Allocation[i][j]$$

![银行家算法流程图](图表/OS/07_银行家算法流程图.png)

![调度算法对比图](图表/OS/12_调度算法对比图.png)

**安全性算法**：
1. 初始化：$Work = Available$，$Finish[i] = false$
2. 找满足条件的进程$P_i$：$Finish[i]=false$ 且 $Need[i] \leq Work$
3. 若找到：$Work = Work + Allocation[i]$，$Finish[i] = true$，转第2步
4. 若不能找到：检查所有$Finish[i]$，若全为true→**安全**（输出安全序列）；否则→**不安全**

#### 银行家算法完整数值示例（⭐⭐⭐ 高频大题）

> **题目**：系统有 A、B、C 三类资源，初始可用量为 $(3,3,2)$。5个进程当前状态如下：
>
> | 进程 | Max (A,B,C) | Allocation (A,B,C) | Need (A,B,C) |
> |:--:|:--:|:--:|:--:|
> | $P_0$ | (7,5,3) | (0,1,0) | (7,4,3) |
> | $P_1$ | (3,2,2) | (2,0,0) | (1,2,2) |
> | $P_2$ | (9,0,2) | (3,0,2) | (6,0,0) |
> | $P_3$ | (2,2,2) | (2,1,1) | (0,1,1) |
> | $P_4$ | (4,3,3) | (0,0,2) | (4,3,1) |
>
> **$Available = (10,5,7) - (7,2,5) = (3,3,2)$**
>
> **求安全序列**：
>
> | 步骤 | 选进程 | Work (A,B,C) | Need≤Work? | 执行后 Work+=Alloc |
> |:--:|:--:|:--:|:--:|:--:|
> | 1 | $P_1$ | (3,3,2) | (1,2,2)≤(3,3,2) ✓ | (3,3,2)+(2,0,0)=**(5,3,2)** |
> | 2 | $P_3$ | (5,3,2) | (0,1,1)≤(5,3,2) ✓ | (5,3,2)+(2,1,1)=**(7,4,3)** |
> | 3 | $P_4$ | (7,4,3) | (4,3,1)≤(7,4,3) ✓ | (7,4,3)+(0,0,2)=**(7,4,5)** |
> | 4 | $P_2$ | (7,4,5) | (6,0,0)≤(7,4,5) ✓ | (7,4,5)+(3,0,2)=**(10,4,7)** |
> | 5 | $P_0$ | (10,4,7) | (7,4,3)≤(10,4,7) ✓ | (10,4,7)+(0,1,0)=**(10,5,7)** |
>
> ✅ 所有进程均可完成 → 安全序列 $\langle P_1, P_3, P_4, P_2, P_0\rangle$
>
> **追问**：若 $P_1$ 此时请求 $(1,0,2)$，能否分配？
> - 试分配：$Available=(3,3,2)-(1,0,2)=(2,3,0)$，$Alloc_1=(3,0,2)$，$Need_1=(0,2,0)$
> - 再跑安全性算法：$P_1→P_3→P_4→P_2→P_0$，仍安全 → **可以分配**

> ⚠️ **银行家算法是死锁避免策略**，不是死锁预防。它不破坏任何必要条件，而是在每次资源分配前检测安全性。

### 死锁检测

**资源分配图的简化**：
1. 找到既不阻塞又不孤立的进程节点$P_i$（其请求可被满足）
2. 消去$P_i$的所有边（相当于$P_i$执行完归还资源）
3. 重复直到无法再简化

**死锁定理**：当且仅当资源分配图**不可完全简化时**，系统处于死锁状态。

![死锁资源分配图](图表/OS/18_死锁资源分配图.png)

### 死锁解除
1. **终止进程**：终止所有死锁进程 / 逐个终止直到解除死锁
2. **资源剥夺**：从死锁进程中抢占资源分配给其他进程
3. 选择终止/剥夺的依据：优先级、已执行时间、已使用资源量、进程性质（交互/批处理）

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2009Q24/Q25、2010Q26、2011Q23、2014Q23/Q24、2016Q24/Q25、2018Q24/Q26、2019Q27/Q30、2021Q23、2025Q26
- **优质例题**：给出进程到达时间+服务时间，分别按FCFS/SJF/RR计算平均周转时间，并判断是否存在饥饿。
- **最短解题模板**：
  1. 先画甘特图（含抢占时刻）。
  2. 算每进程完成时刻→周转时间→带权周转时间。
  3. 死锁题先写“四必要条件”，再用安全序列/资源分配图做判定。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：调度先画图，不画必错时刻。
- **口令**：周转=完成-到达，带权=周转/服务。
- **口令**：死锁先四条件，再判安全序列。

---

# 第四章 进程同步（核心考点⭐⭐⭐）

## 4.1 基本概念

### 两种制约关系
- **间接制约（互斥）**：多个进程因共享临界资源而互斥使用
- **直接制约（同步）**：多个进程因合作而需要协调推进顺序

### 临界资源
一次仅允许一个进程使用的资源。硬件如打印机、软件如共享变量。

### 临界区
进程中访问临界资源的那段代码。

### 同步机制应遵循的四个准则

| 准则 | 说明 |
|:---|:---|
| **空闲让进** | 临界区空闲时，允许请求进入 |
| **忙则等待** | 临界区被占用时，其他请求必须等待 |
| **有限等待** | 保证进程在有限时间内能进入临界区（不饥饿） |
| **让权等待** | 不能进入临界区的进程应释放CPU（原则上应遵循但非必须） |

---

## 4.2 软件同步方法

### Peterson算法（两进程互斥⭐）

```c
// 进程Pi
flag[i] = true;     // 表示Pi想进入
turn = j;           // 谦让：设置对方优先
while(flag[j] && turn == j);  // 等待
    // 临界区
flag[i] = false;
```

- 满足**空闲让进、忙则等待、有限等待**（前3条准则）
- **不满足让权等待**（忙等）
- 仅适用于两个进程

---

## 4.3 硬件同步机制

| 方法 | 原理 | 缺点 |
|:---|:---|:---|
| **关中断** | 进入临界区前关中断，退出后开中断 | 滥用风险、影响效率、不适用多CPU |
| **TS指令(Test-and-Set)** | 原子操作：读取lock旧值并置lock=true | 忙等,不满足让权等待 |
| **Swap/XCHG指令** | 原子交换两个变量 | 忙等,不满足让权等待 |

```c
// TS指令
boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}
// 使用：while(TestAndSet(&lock)); 临界区; lock=false;
```

---

## 4.4 信号量机制（⭐⭐⭐最核心）

### 整型信号量
```c
wait(S) { while(S <= 0); S--; }   // 忙等
signal(S) { S++; }
```
缺点：忙等（不满足让权等待）

### 记录型信号量（⭐⭐⭐）

```c
typedef struct {
    int value;
    struct process_control_block *list;  // 等待队列
} semaphore;

void wait(semaphore *S) {     // P操作
    S->value--;
    if (S->value < 0)
        block(S->list);       // 阻塞自己,插入等待队列
}

void signal(semaphore *S) {   // V操作
    S->value++;
    if (S->value <= 0)
        wakeup(S->list);      // 唤醒等待队列中的一个进程
}
```

> **⭐ 关键理解**：
> - $value > 0$：有$value$个资源可用
> - $value = 0$：无资源可用，无进程等待
> - $value < 0$：$|value|$ = 等待队列中的进程数
> - **满足让权等待**（阻塞自己而非忙等）

### AND型信号量
- `Swait(S1, S2, ..., Sn)`：**同时申请**所有资源，全部≥1才分配
- `Ssignal(S1, S2, ..., Sn)`：同时释放所有资源
- 避免死锁（一次获取所有需要的资源）

### 信号量集
- `Swait(S1,t1,d1; S2,t2,d2; ...; Sn,tn,dn)`
  - $t_i$：测试值（$S_i \geq t_i$ 才分配）
  - $d_i$：需求值（每次分配$d_i$个）
- 特殊情况：
  - $(S,d,d)$：每次申请$d$个
  - $(S,1,1)$：等价于记录型信号量
  - $(S,1,0)$：**开关型**（$S \geq 1$时允许，$S=0$时阻塞，但不消耗资源）

---

## 4.5 信号量的应用（⭐⭐⭐）

### 实现互斥

```c
semaphore mutex = 1;  // 互斥信号量,初值为1

// 进程Pi
wait(mutex);          // P(mutex)
    // 临界区
signal(mutex);        // V(mutex)
```

> $mutex$ 取值范围：$-1, 0, 1$
> - $1$：资源空闲
> - $0$：一个进程在临界区，无等待
> - $-1$：一个在临界区，一个在等待

### 实现同步

```c
semaphore S = 0;  // 同步信号量,初值为0

// 进程P1                          // 进程P2
C1;  // 语句C1                     wait(S);  // P(S) 等在前面
signal(S); // V(S) 执行完C1后通知   C2;       // C2必须在C1之后执行
```

> **口诀：前V后P**（在"前面的"操作后面做V，在"后面的"操作前面做P）

---

## 4.6 管程（⭐⭐）

### 管程的定义
管程由以下四部分组成：
1. **管程名称**
2. **共享数据结构**
3. **对该数据结构操作的一组过程（函数）**
4. **对共享数据设置初始值的语句**

### 管程的特性
- **封装**：数据结构只能被管程内部的过程访问
- **互斥**：每次**只允许一个进程**进入管程执行
- **信息隐蔽**：外部不可见内部数据

### 条件变量

```
x.wait()   // 阻塞调用进程,释放管程,将进程加入x的等待队列
x.signal() // 唤醒x等待队列中的一个进程;若无等待进程,则无操作
```

> **⚠️ 条件变量的signal与信号量的signal不同**：
> - 信号量的signal：$S$值加1，即使无等待进程也有效果
> - 条件变量的signal：若无等待进程则无动作（不会"记忆"）

### 管程 vs 进程

| 方面 | 管程 | 进程 |
|:---|:---|:---|
| 目的 | 管理共享资源 | 实现系统并发 |
| 数据结构 | 共享数据结构 | PCB |
| 操作 | 同步操作 | 程序执行 |
| 工作方式 | 被动调用 | 主动运行 |
| 并发 | 不可并发(互斥进入) | 可并发 |
| 动态性 | 管程是OS的一个资源管理模块（静态） | 进程有生命周期（动态） |

---

## 4.7 经典同步问题（⭐⭐⭐必考）

![PV前驱图与生产者消费者模型](图表/OS/02_PV前驱图与生产者消费者.png)

![PV操作信号量机制](图表/OS/17_PV操作信号量机制.png)

### 生产者-消费者问题

```c
semaphore mutex = 1;   // 互斥访问缓冲区
semaphore empty = n;   // 空缓冲槽数量,初始n
semaphore full = 0;    // 满缓冲槽数量,初始0

// 生产者                              // 消费者
while(1) {                             while(1) {
    生产一个产品;                          wait(full);     // 有产品才取
    wait(empty);    // 有空槽才放          wait(mutex);
    wait(mutex);                           从缓冲区取产品;
    放入缓冲区;                            signal(mutex);
    signal(mutex);                         signal(empty);  // 增加一个空槽
    signal(full);   // 增加一个产品         消费产品;
}                                      }
```

> **⚠️ 必须先P资源信号量,再P互斥信号量！反过来必死锁！**
> - 错误示例：`wait(mutex); wait(empty);` → 若缓冲区满,生产者持有mutex等empty,消费者想进入要等mutex → **死锁**

### 哲学家进餐问题

5个哲学家围坐，5根筷子。每人需左右两根筷子才能吃饭。

```c
semaphore chopstick[5] = {1, 1, 1, 1, 1};

// 哲学家i
while(1) {
    思考;
    wait(chopstick[i]);         // 拿左
    wait(chopstick[(i+1)%5]);   // 拿右
    进餐;
    signal(chopstick[i]);       // 放左
    signal(chopstick[(i+1)%5]); // 放右
}
```

**可能死锁！**（5人同时拿左筷子）

**死锁解决方案**（任选一）：
1. **最多4人同时进餐**（限制同时拿筷子的人数）
2. **同时拿起两根筷子**（AND信号量）
3. **奇偶号策略**：奇号哲学家先拿左再拿右，偶号先拿右再拿左

### 读者-写者问题

```c
// 读者优先解法
semaphore rmutex = 1;    // 保护readcount
semaphore wmutex = 1;    // 互斥写
int readcount = 0;

// 读者                                // 写者
wait(rmutex);                          wait(wmutex);
    readcount++;                           写操作;
    if(readcount == 1)                 signal(wmutex);
        wait(wmutex);  // 第一个读者锁住写
signal(rmutex);
    读操作;
wait(rmutex);
    readcount--;
    if(readcount == 0)
        signal(wmutex); // 最后一个读者解锁写
signal(rmutex);
```

> **第一问题（读者优先）**：读者可能导致写者饥饿
> **第二问题（写者优先）**：需增加额外信号量，写者到达后新读者不能读

### 写者优先思路（补充）

```c
// 写者优先常见信号量
semaphore rmutex = 1;    // 保护readcount
semaphore wmutex = 1;    // 写互斥
semaphore readTry = 1;   // 是否允许新读者进入
semaphore wcMutex = 1;   // 保护writecount
int readcount = 0, writecount = 0;

// 写者
wait(wcMutex); writecount++;
if (writecount == 1) wait(readTry);  // 第一位写者到达，阻止新读者
signal(wcMutex);

wait(wmutex); 写操作; signal(wmutex);

wait(wcMutex); writecount--;
if (writecount == 0) signal(readTry); // 最后一位写者离开，放行读者
signal(wcMutex);
```

> **要点**：`readTry` 是“闸门”，只要有写者等待，就不再放新读者进入，从而避免写者饥饿。

---

## 4.8 Linux同步机制

- **并发来源**：中断、内核态抢占、多处理机
- **原子操作**：lock前缀指令、atomic_t
- **自旋锁**：多处理机忙等,适用短临界区; spin_lock/spin_unlock; 变种rwlock/seqlock
- **信号量**：适用长临界区,可睡眠

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2009Q45、2010Q27、2011Q45、2014Q47、2015Q45、2017Q46、2018Q32、2019Q43、2020Q45、2021Q45/Q46、2022Q45、2024Q46、2025Q45
- **优质例题**：三线程A/B/C有前驱约束 A→C、B→C、C→D，写出最少信号量与P/V序列。
- **最短解题模板**：
  1. 先画前驱图，给每条“前驱边”分配一个同步信号量。
  2. 每个活动：前驱边对应 `P` 在前，后继边对应 `V` 在后。
  3. 共享缓冲区再补 `mutex`（互斥）+ `empty/full`（同步）。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：先前驱后PV，不画图不下笔。
- **口令**：互斥用mutex，同步用前驱信号量。
- **口令**：缓冲区三件套：`mutex`、`empty`、`full`。

---

# 第五章 存储器管理

## 5.1 程序的装入和链接

### 装入方式

| 方式 | 特点 | 适用 |
|:---|:---|:---|
| **绝对装入** | 编译时产生绝对地址 | 单道程序 |
| **可重定位装入（静态重定位）** | 装入时一次性修改全部地址 | 装入后不能移动 |
| **动态运行时装入（动态重定位）** | 运行时借助重定位寄存器转换地址 | 地址可延迟到执行时变换，支持紧凑 |

### 链接方式

| 方式 | 说明 |
|:---|:---|
| **静态链接** | 装入前将所有模块链接成完整可执行文件 |
| **装入时动态链接** | 装入内存时边装入边链接 |
| **运行时动态链接** | 运行到某模块时才链接（最灵活,节省内存） |

---

## 5.2 连续分配方式

| 方式 | 说明 | 碎片 |
|:---|:---|:---|
| **单一连续分配** | 内存分为系统区+用户区,一次只一个程序 | 有内碎片 |
| **固定分区分配** | 预先分为若干固定大小分区 | **内碎片**（分区内浪费） |
| **动态分区分配** | 按需分配大小 | **外碎片**（分区间浪费），可通过**紧凑**解决 |

### 动态分区分配算法⭐

| 算法 | 策略 | 空闲分区排列 | 优缺点 |
|:---|:---|:---|:---|
| **首次适应FF** | 从头找第一个够大的 | 地址递增 | 保留大分区,但低址碎片多 |
| **循环首次适应NF** | 从上次找到的位置继续 | 循环 | 分布均匀,但大分区缺乏 |
| **最佳适应BF** | 找最小的够用分区 | 容量递增 | 碎片最小但太小无法用 |
| **最坏适应WF** | 找最大的分区 | 容量递减 | 碎片概率小,但大分区缺乏 |

### 动态分区分配的改进算法
- **快速适应**：按常用空间大小分类，设索引表管理
- **伙伴系统**：分区大小为$2^k$，分割/合并都是二分
- **哈希算法**：以空闲分区大小为关键字建哈希表

---

## 5.3 分页存储管理方式（⭐⭐⭐）

### 基本概念
- **页面（页）**：进程地址空间分成的固定大小区域（如4KB）
- **物理块（页框/帧）**：内存空间分成的同大小区域
- **页内碎片（内碎片）**：最后一页装不满一块

### 地址计算公式⭐

$$P = INT\left[\frac{A}{L}\right] \quad d = A \mod L$$

其中 $A$ = 逻辑地址，$L$ = 页面大小，$P$ = 页号，$d$ = 页内偏移

### 页表
- 每个进程一张页表
- 作用：**页号 → 物理块号** 的映射
- 页表寄存器PTR：存放页表起始地址和页表长度

### 地址变换过程（基本分页）

![存储管理方式对比](图表/OS/13_存储管理方式对比.png)

![分页地址变换图](图表/OS/03_分页地址变换图.png)

1. 从逻辑地址取出页号P和页内偏移d
2. 页号P与页表长度比较 → 若P ≥ 页表长度则**越界中断**
3. 页表起始地址 + P × 页表项长度 → 找到页表项 → 取物理块号b
4. 物理地址 = b × L + d（即块号拼接页内偏移）

> **基本分页：访问一个数据需要2次访存**（1次查页表+1次读数据）

### 快表TLB⭐

![TLB命中路径图](图表/OS/04_TLB命中路径图.png)

![虚拟地址翻译流程](图表/OS/14_虚拟地址翻译流程.png)

引入TLB后：先查TLB(命中则1次访存)，未命中则查页表(2次访存)并更新TLB。

$$EAT = h\,(t_{TLB}+t_m) + (1-h)\,(t_{TLB}+2t_m)$$

其中 $h$ = TLB命中率，$t_{TLB}$ = TLB访问时间，$t_m$ = 内存访问时间。

> 等价写法：$EAT = 2t_m + t_{TLB} - h\,t_m$。

### 两级页表

- 32位地址空间，4KB页面 → 页表项1M个 → 页表占4MB → 不现实
- **解决**：对页表也分页！
- 逻辑地址：`|外层页号P1(10位)|外层页内地址P2(10位)|页内偏移d(12位)|`
- **需要3次访存**（访问外层页表→访问页表→访问数据）

### 多级页表
- 64位系统需要更多级（如x86-64用4级页表）
- 每增加一级多一次访存

### 反置页表
- 按**物理块号**而非页号组织：每个物理块对应一个表项
- 表项内容：页号 + 进程标识符PID
- 减少页表内存占用
- 可用哈希加速检索

---

## 5.4 分段存储管理方式

### 分段的引入目的
1. 方便编程（逻辑分段）
2. 信息共享（以段为单位共享）
3. 信息保护
4. 动态链接
5. 动态增长

### 分段的基本原理
- 作业地址空间分为若干段，每段有段名和段长
- 逻辑地址：`|段号S|段内地址d|`（**二维地址**）
- 段表项：段号 + **段长** + **基址（起始地址）**

### 段的地址变换
1. 段号S与段表长度比较 → 若S ≥ TL则**越界中断**
2. 由段表找到段表项 → 取段长和起始地址
3. 段内地址d与段长比较 → 若d ≥ SL则**越界中断**（⭐**两次越界检查**！）
4. 物理地址 = 起始地址 + d

### 分页 vs 分段（⭐⭐⭐必考）

![分段与段页式对比图](图表/OS/08_分段与段页式对比图.png)

| 比较项 | 分页 | 分段 |
|:---|:---|:---|
| 目的 | 系统管理的需要,提高内存利用率 | 用户的需要,满足编程和使用 |
| 单位性质 | 页是信息的**物理单位** | 段是信息的**逻辑单位** |
| 大小 | **固定**,由系统/硬件决定 | **不固定**,由用户程序决定 |
| 地址维度 | **一维**（页号+偏移自动划分,用户不可见） | **二维**（需给出段名和段内地址） |
| 碎片 | 内碎片 | 外碎片 |

### 可重入代码（纯代码）
- 允许多个进程同时访问的代码
- **不允许任何修改**
- 可修改的部分放在各进程的**局部数据区**

---

## 5.5 段页式存储管理方式

- **先分段,每段再分页**
- 逻辑地址：`|段号S|段内页号P|页内偏移d|`
- 段表项：页表起始地址 + 页表长度
- **需要3次访存**（段表→页表→数据）
- 实际中加TLB减少访存次数

---

## 5.6 IA-32/x86-64内存管理

### IA-32
- 分段+分页：CPU生成逻辑地址→分段单元→线性地址→分页单元→物理地址
- Linux在IA-32上仅最低限度使用段
- 4KB页使用二级页表（10+10+12）
- PAE扩展为三级页表,支持36位物理地址(64GB)

### x86-64
- 四级页表,48位虚地址,支持52位物理地址
- 页面大小可为4KB/2MB/1GB

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2009Q26/Q27、2010Q28/Q29、2016Q28、2019Q31、2024Q25/Q27、2025Q22
- **优质例题**：已知逻辑地址长度、页大小、页表项大小，求页号位数/页内偏移位数/页表占用空间。
- **最短解题模板**：
  1. 先拆位：偏移位数 = $\log_2(页大小)$。
  2. 页号位数 = 逻辑地址位数 - 偏移位数。
  3. 页表空间 = 页数 × 页表项大小，注意单位统一（B/KB）。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：先偏移后页号，最后算页表。
- **口令**：页号=高位，页内偏移=低位。
- **口令**：所有计算先统一单位。

---

# 第六章 虚拟存储器

## 6.1 虚拟存储器概述

### 局部性原理⭐
- **时间局部性**：刚访问的单元不久会被再访问（循环）
- **空间局部性**：刚访问的单元附近的单元不久会被访问（顺序执行）

### 传统存储管理特征 vs 虚拟存储器

| 特征 | 传统 | 虚拟 |
|:---|:---|:---|
| 一次性 | 必须一次性全部装入 | 多次性：允许分多次调入 |
| 驻留性 | 一直驻留到结束 | 对换性：允许换入换出 |
| — | — | 虚拟性：逻辑扩大内存 |

> **虚拟存储器三大特征：多次性（最重要）、对换性、虚拟性**
> **虚拟性以多次性和对换性为基础，多次性和对换性建立在离散分配方式上**

### 虚拟存储器的实现方式
1. **请求分页存储管理**（最常用）：以页为单位换入/换出
2. **请求分段存储管理**：以段为单位换入/换出

---

## 6.2 请求分页存储管理方式

### 请求页表项

| 页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址 |
|:---|:---|:---|:---|:---|:---|

- **P（存在位）**：该页是否在内存中（1在/0不在）
- **A（访问字段）**：记录访问次数或多久未访问,供置换算法参考
- **M（修改位/脏位）**：该页是否被修改过,供换出时决定是否写回
- **外存地址**：该页在外存的位置

### 缺页中断⭐
- **发生在指令执行期间**（不同于一般中断在指令执行后检查）
- **一条指令可能产生多次缺页中断**（极端情况下可达6次：指令本身跨页最多2次 + 源操作数跨页最多2次 + 目的操作数跨页最多2次）

### 内存分配策略

| 策略 | 分配 | 置换 | 适用/特点 |
|:---|:---|:---|:---|
| **固定分配局部置换** | 固定物理块数 | 从本进程页面中选换出 | 物理块数难确定 |
| **可变分配全局置换** | 可变 | 从所有进程中选换出 | 最易实现,但可能影响其他进程 |
| **可变分配局部置换** | 可变 | 从本进程中选换出,可动态增减 | 兼顾灵活和隔离 |

### 页框分配与回收（新增强化）

#### 常见页框分配算法
- **等额分配**：每个进程平均分配相同数量页框
- **比例分配**：按进程大小（页数）比例分配页框
- **优先级分配**：高优先级进程获得更多页框（缺页时可从低优先级进程回收）

#### 回收策略要点
- **局部回收**：仅在本进程驻留集中置换，隔离性好
- **全局回收**：可跨进程选牺牲页，系统吞吐量高但会互相干扰
- **后台回收**：系统在空闲或阈值触发时批量回收脏页并维护空闲页框池

> **考试常用结论**：页框过少会触发抖动；页框分配和页面置换需配合工作集思想联合判断。

### 缺页率

$$f = \frac{F}{A} = \frac{F}{S+F}$$

影响因素：页面大小、分配的物理块数、页面置换算法、程序局部性

---

## 6.3 页面置换算法（⭐⭐⭐必考）

![页面置换算法对比](图表/OS/05_页面置换算法对比.png)

### OPT（最佳页面置换算法）
- 淘汰**未来最长时间不会被访问**的页
- **最低缺页率，但不可实现**（需预知未来）
- 用作评价其他算法的标准

### FIFO（先进先出）
- 淘汰**最早进入内存**的页
- 实现简单（FIFO队列）
- **Belady异常**：增加物理块数反而缺页率上升！⭐
- 实际应用极少

### LRU（最近最久未使用）⭐
- 淘汰**最近最久未使用**的页
- 向前看（基于历史）对比OPT向后看（基于未来）
- 性能接近OPT
- **需要硬件支持**：移位寄存器 或 栈

> **⚠️ LRU不会出现Belady异常**（属于"栈算法"类）

### LFU（最少使用）
- 淘汰**一段时间内使用次数最少**的页
- 用移位寄存器记录访问频率

### Clock（时钟/NRU）⭐
- 简单Clock：循环队列,每页一个访问位A
  - 若A=0 → 换出
  - 若A=1 → 置A=0,给第二次机会,检查下一页
- 又称**二次机会算法/NRU（最近未用）**

### 改进型Clock⭐
- 同时考虑**访问位A**和**修改位M**
- 四类页面优先级：

| 类别 | A | M | 含义 | 淘汰优先级 |
|:---|:---|:---|:---|:---|
| 第1类 | 0 | 0 | 未访问,未修改 | **最优先淘汰** |
| 第2类 | 0 | 1 | 未访问,已修改 | 次优先 |
| 第3类 | 1 | 0 | 已访问,未修改 | 可能再被访问 |
| 第4类 | 1 | 1 | 已访问,已修改 | 最不应淘汰 |

扫描过程：
1. 第1轮找(0,0)不改A
2. 找不到则第2轮找(0,1)同时把扫过的A置0
3. 还找不到则重复1-2（此时A都已为0,必能找到）

### 页面缓冲算法 PBA
- 设空闲页面链表+修改页面链表

### 页面置换手工模拟示例（⭐⭐⭐ 必练）

> **题目**：3个物理块，访问串 $7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1$，分别用 FIFO 和 LRU 计算缺页次数。
>
> **FIFO**（淘汰最早进入的页）：
>
> | 访问 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
> |:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
> | 块1 | **7** | 7 | 7 | **2** | 2 | 2 | 2 | **4** | 4 | 4 | **0** | 0 | 0 | 0 | 0 | 0 | 0 | **7** | 7 | 7 |
> | 块2 | | **0** | 0 | 0 | 0 | **3** | 3 | 3 | **2** | 2 | 2 | 2 | 2 | **1** | 1 | 1 | 1 | 1 | **0** | 0 |
> | 块3 | | | **1** | 1 | 1 | 1 | **0** | 0 | 0 | **3** | 3 | 3 | 3 | 3 | **2** | 2 | 2 | 2 | 2 | **1** |
> | 缺页 | ✗ | ✗ | ✗ | ✗ | | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | | | ✗ | ✗ | | | ✗ | ✗ | ✗ |
>
> FIFO 缺页 **15** 次，缺页率 = 15/20 = 75%
>
> **LRU**（淘汰最近最久未使用的页）：
>
> | 访问 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
> |:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
> | 块1 | **7** | 7 | 7 | **2** | 2 | 2 | 2 | **4** | 4 | 4 | **0** | 0 | 0 | **1** | 1 | 1 | 1 | 1 | 1 | 1 |
> | 块2 | | **0** | 0 | 0 | 0 | **3** | 3 | 3 | 3 | **3** | 3 | 3 | 3 | 3 | **2** | 2 | 2 | **7** | 7 | 7 |
> | 块3 | | | **1** | 1 | 1 | 1 | **0** | 0 | **2** | 2 | 2 | 2 | **2** | 2 | 2 | **0** | 0 | 0 | **0** | 0 |
> | 缺页 | ✗ | ✗ | ✗ | ✗ | | ✗ | ✗ | ✗ | ✗ | | ✗ | | | ✗ | ✗ | ✗ | | ✗ | | |
>
> LRU 缺页 **12** 次，缺页率 = 12/20 = 60%
>
> **结论**：LRU(12次) < FIFO(15次)，LRU性能更优且无Belady异常。
>
> 📝 **答题提醒**：画表时每一步标清"淘汰了谁"和"新换入谁"，缺页打 ✗ ，命中留空。
- 换出时不立即写盘,而是挂在链表上
- 后续需要该页时可直接从链表取回（避免磁盘I/O）
- 修改页面积累到一定数量后批量写盘

---

## 6.4 "抖动"与工作集

### 抖动（颠簸）
- **定义**：进程大部分时间用于页面置换而非有效计算
- **原因**：分配给进程的物理块太少
- 多道程序度过高→物理块不足→频繁缺页→I/O繁忙→CPU利用率下降

### 工作集 w(t, Δ)
- **定义**：进程在时间间隔$(t-\Delta, t)$中实际访问的页面集合
- $\Delta$为窗口尺寸
- 工作集大小是$\Delta$的非降函数

### 抖动预防方法
1. **局部置换策略**：限制影响范围
2. **工作集算法融入调度**：确保驻留集足够才调入新作业
3. **L=S准则**：L(缺页间平均时间)≈S(平均缺页服务时间)时最优
4. **挂起进程**：减少多道程序度

---

## 6.5 请求分段存储管理

### 请求段表项
在普通段表项基础上增加：存取方式、访问字段A、修改位M、存在位P、**增补位**、外存地址

### 增补位
- 请求分段特有字段
- 表示该段在运行过程中是否做过**动态增长**

### 共享段表
- **count（共享计数）**：记录共享该段的进程数，count为0时才回收
- **存取控制**：不同进程可有不同的读写权限
- **段号**：不同进程中可有不同的段号

### 分段保护
1. **越界检查**：段号 vs 段表长度；段内地址 vs 段长
2. **存取控制检查**：只读/只执行/读写
3. **环保护机构**：低编号环=高特权，程序可调用内环服务，可访问外环数据

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2009Q46、2010Q46、2011Q28/Q29、2014Q30、2015Q27/Q30、2016Q26/Q29、2018Q45、2019Q29、2024Q45、2025Q25/Q28/Q29
- **优质例题**：4页框下访问串 `1,2,3,4,1,2,5,1,2,3,4,5`，比较FIFO与LRU缺页次数并判断Belady异常。
- **最短解题模板**：
  1. 画页框时间表（每一步记录页框内容）。
  2. 命中不替换，缺页按算法选牺牲页。
  3. 汇总缺页次数并比较：FIFO可能Belady，LRU通常不出现。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：置换必画表，口算易翻车。
- **口令**：命中不动，缺页才换。
- **口令**：FIFO有Belady，LRU更稳。

---

# 第七章 输入/输出系统

## 7.1 I/O设备分类

| 分类方式 | 类型 | 示例 |
|:---|:---|:---|
| 按**使用特性** | 存储设备 / 输入设备 / 输出设备 / 交互式设备 | 磁盘 / 键盘 / 打印机 / 显示器 |
| 按**传输速率** | 低速 / 中速 / 高速 | 键盘 / 打印机 / 磁盘 |
| 按**共享属性** | 独占设备 / 共享设备 / 虚拟设备 | 打印机 / 磁盘 / SPOOLing |
| 按**传输单位** | 块设备 / 字符设备 | 磁盘 / 键盘 |

---

## 7.2 设备控制器

### 设备控制器的组成
1. **设备控制器与CPU的接口**：数据线+地址线+控制线，含数据寄存器、控制/状态寄存器
2. **设备控制器与设备的接口**：数据/控制/状态信号
3. **I/O逻辑**：对命令译码，选择设备

### CPU与控制器通信方式
- **特定I/O指令形式**：专门的I/O指令（如`io-store`）
- **内存映像I/O**：把设备寄存器地址映射到内存地址空间，用普通存取指令访问

---

## 7.3 I/O通道

| 通道类型 | 工作方式 | 适用设备 | 特点 |
|:---|:---|:---|:---|
| **字节多路通道** | 按字节交叉 | 低速设备 | 含多个非分配型子通道,轮流使用 |
| **数组选择通道** | 按数据块,独占 | 高速设备 | 一次只服务一个设备,利用率低 |
| **数组多路通道** | 按数据块,多路 | 高/中速设备 | 既高速又高利用率 |

**瓶颈问题**解决：增加通路（一个设备连多个控制器，一个控制器连多个通道）

---

## 7.4 I/O控制方式（⭐⭐⭐）

| 方式 | 数据传送单位 | CPU干预程度 | 特点 |
|:---|:---|:---|:---|
| **程序直接控制（轮询）** | 字节 | 极高(忙等) | CPU与设备串行,CPU利用率极低 |
| **中断驱动** | 字节 | 每字节中断一次 | CPU与设备可并行,但高速设备中断太频繁 |
| **DMA** | **数据块** | 每块中断一次 | 4个寄存器:CR/MAR/DR/DC；数据直接内存↔设备 |
| **通道** | **一组数据块** | 仅启动和完成时干预 | 执行通道程序,CPU/通道/设备三者并行 |

### DMA控制器4个寄存器
- **CR（命令寄存器）**：存放CPU命令
- **MAR（内存地址寄存器）**：数据在内存的起始地址
- **DR（数据寄存器）**：暂存传送数据
- **DC（数据计数器）**：本次传送的字节数

---

![I/O软件层次图](图表/OS/09_IO软件层次图.png)

## 7.5 I/O软件层次

从低到高：
1. **中断处理程序**：最底层，直接与硬件交互
2. **设备驱动程序**：抽象I/O请求→具体设备命令
3. **与设备无关的I/O软件**：设备命名、保护、分配、缓冲
4. **用户层I/O软件**：库函数、SPOOLing

---

## 7.6 设备分配

### 设备分配相关数据结构
- **DCT（设备控制表）**：每个设备一张
- **COCT（控制器控制表）**：每个控制器一张
- **CHCT（通道控制表）**：每个通道一张
- **SDT（系统设备表）**：全系统一张，记录所有设备

### SPOOLing（假脱机技术）⭐
- 将**物理上的独占设备**改造为**逻辑上的共享设备**
- **组成**：输入井+输出井（在磁盘上）+ 输入缓冲区+输出缓冲区（在内存中）+ 输入/输出进程
- **典型应用**：共享打印机（多个进程的打印请求放入磁盘输出井排队，由守护进程依次打印）

---

## 7.7 缓冲区管理⭐

### 缓冲引入原因
- 缓和CPU与I/O设备间的速度不匹配
- 减少I/O中断次数
- 解决基本数据单元大小不匹配

### 传输时间计算⭐

设 $T$ = 设备传送一块数据时间，$M$ = 将缓冲区数据传入用户区时间，$C$ = CPU处理一块数据时间

| 缓冲类型 | 每块平均处理时间 |
|:---|:---|
| **单缓冲** | $\max(C, T) + M$ |
| **双缓冲** | $\max(C+M, T)$ |

### 缓冲池
- **4种缓冲区**：收容输入(hin)、提取输入(sin)、收容输出(hout)、提取输出(sout)

---

## 7.8 磁盘

### 磁盘访问时间⭐

$$T_a = T_s + T_r + T_t$$

- $T_s$（寻道时间）：磁头移到目标磁道
- $T_r$（旋转延迟）：等转到目标扇区。平均 $T_r = \frac{1}{2r}$（$r$为转速）
- $T_t$（传输时间）：$T_t = \frac{b}{rN}$（$b$为字节数，$N$为每磁道字节数）

### 磁盘调度算法⭐⭐⭐

![磁盘结构示意图](图表/OS/16_磁盘结构示意图.png)

![磁盘调度轨迹对比](图表/OS/06_磁盘调度轨迹对比.png)

| 算法 | 策略 | 优缺点 |
|:---|:---|:---|
| **FCFS** | 先来先服务 | 公平但效率低 |
| **SSTF** | 最短寻道时间优先 | 性能好但可能饥饿 |
| **SCAN（电梯）** | 单方向扫到头再折返 | 消除饥饿,对中间磁道有利 |
| **LOOK** | 单方向扫描到该方向**最远请求**即折返 | 避免无效扫到端点,平均寻道更优 |
| **C-SCAN（循环扫描）** | 单方向扫到头,快速返回起点重新扫 | 更均匀的等待时间 |
| **C-LOOK** | 单方向扫描到最远请求后,快速回到最小请求再扫 | 比C-SCAN更少无效移动 |
| **N-Step-SCAN** | 将请求队列分段,段内SCAN | 避免磁臂粘着 |
| **FSCAN** | 两个子队列,一个当前服务,新请求入另一个 | 避免磁臂粘着 |

#### 磁盘调度手工计算示例（⭐⭐ 高频选择/大题）

> **题目**：磁盘请求队列为 $\{98, 183, 37, 122, 14, 124, 65, 67\}$，当前磁头在 **53** 号磁道，磁头正向磁道号增大方向移动。分别用 FCFS、SSTF、SCAN 计算总移动磁道数。
>
> **FCFS**（按请求到达顺序）：
> $53→98→183→37→122→14→124→65→67$
> 移动量 = $|53-98|+|98-183|+|183-37|+|37-122|+|122-14|+|14-124|+|124-65|+|65-67|$
> $= 45+85+146+85+108+110+59+2 = \mathbf{640}$
>
> **SSTF**（每次选最近磁道）：
> $53→65→67→37→14→98→122→124→183$
> 移动量 = $12+2+30+23+84+24+2+59 = \mathbf{236}$
>
> **SCAN**（电梯算法，先向大方向扫到最远请求再折返）：
> $53→65→67→98→122→124→183→37→14$
> 移动量 = $12+2+31+24+2+59+146+23 = \mathbf{299}$
>
> ⚠️ **LOOK vs SCAN**：LOOK 扫到该方向最远**请求**（183）即折返；SCAN 扫到磁盘**端点**（如199）才折返。题目需看清"SCAN"还是"LOOK"。

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2009Q32、2010Q32、2011Q26/Q32、2012Q24/Q26、2017Q32、2022Q30、2025Q23
- **优质例题**：比较程序直接控制/中断/DMA三种方式下CPU参与程度，并计算DMA每秒CPU占用比。
- **最短解题模板**：
  1. 先判传输粒度：程序/中断=字节，DMA=块。
  2. CPU开销 = 次数 × 每次处理时间。
  3. CPU占比 = CPU开销 / 总时间。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：轮询最忙，中断次之，DMA最省CPU。
- **口令**：DMA传块，CPU只管前后处理。
- **口令**：占比=总CPU开销/总时长。

---

# 第八章 文件管理

## 8.1 文件的逻辑结构

| 类型 | 说明 |
|:---|:---|
| **有结构文件（记录式）** | 顺序文件、索引文件、索引顺序文件、直接/哈希文件 |
| **无结构文件（流式）** | 字节序列,无明确结构 |

### 索引顺序文件（ISAM）补充
- 按关键字顺序组织主文件，并建立分层索引加速检索
- 插入新记录常先进入**溢出区**，再定期重组主文件
- 兼顾顺序访问与按键检索，适合“读多改少”的场景

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2009Q30/Q31、2014Q29/Q46、2015Q29、2017Q26/Q30/Q31、2018Q46、2020Q23/Q24/Q31、2022Q46、2024Q26/Q29、2025Q27/Q30/Q31
- **优质例题**：i-node含“12直接+1一级+1二级+1三级间接”，给块大小与指针大小，求最大文件长度。
- **最短解题模板**：
  1. 每级可索引块数 = 块大小 / 指针大小。
  2. 总容量 = 直接块 + 一级 + 二级 + 三级，对应逐级乘方。
  3. 最终统一换算为KB/MB/GB并标明单位。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：先算每级扇出，再逐级乘方。
- **口令**：直接+一级+二级+三级，缺一项都丢分。
- **口令**：硬链接同iNode，软链接存路径。

---

## 8.2 文件目录

### FCB（文件控制块）
包含：文件名、类型、大小、物理地址（起始块号）、创建/修改时间、存取控制信息等

### 索引节点（i-node）⭐
- 将FCB中除文件名外的信息提取出来形成索引节点
- 目录项仅含**文件名+索引节点号**
- 显著**减小目录项大小**→提高目录检索效率
- **磁盘索引节点**：存放在磁盘上
- **内存索引节点**：打开文件时调入内存，增加引用计数等字段

### 目录结构

| 结构 | 说明 |
|:---|:---|
| **单级目录** | 唯一目录,不允许重名 |
| **两级目录** | MFD（主文件目录）+ UFD（用户文件目录） |
| **树形目录** | 多级层次,用绝对路径/相对路径定位 |
| **无环图目录（DAG）** | 支持共享子目录/文件 |

### 目录检索
- **线性检索法**：顺序查找
- **Hash方法**：用文件名哈希直接定位（需解决冲突）

---

## 8.3 文件共享

| 方式 | 原理 | 优缺点 |
|:---|:---|:---|
| **硬链接** | 不同目录项指向**同一索引节点**，count引用计数 | 删除只count-1,count=0才真正删除；**目录通常禁建硬链接**防环 |
| **软链接（符号链接）** | 创建一个LINK类型文件,存放被链接文件的路径名 | 额外I/O开销（需解析路径）,被删除后变悬空链接 |

---

## 8.4 文件保护

### 访问矩阵
- 行=域(用户),列=对象(文件),元素=权限集合
- 太大难以存储→实际实现：

| 方式 | 原理 | 特点 |
|:---|:---|:---|
| **ACL（访问控制列表）** | 按列存储,每个文件记录哪些用户有何权限 | 精简为owner/group/other三类 |
| **能力表** | 按行存储,每个用户记录可访问哪些文件 | 用户持有能力列表 |

### 特殊权限
- **复制权R'**：能将权限复制给同一列其他域
- **所有权O**：能授予/取消同一列其他域的权限
- **控制权**：能修改同一行其他对象的权限

---

## 8.5 Linux文件系统

### VFS四个对象
1. **superblock（超级块）**：整个文件系统的信息
2. **dentry（目录项）**：路径中的一个分量
3. **iNode（索引节点）**：文件的元信息
4. **file（文件对象）**：进程已打开的文件

### ext2文件系统
- **块组**结构：超级块 + 组描述符 + 块位图 + iNode位图 + iNode表 + 数据块
- **iNode 128B**,含15个块指针i_block：
  - `i_block[0-11]`：**12个直接块**
  - `i_block[12]`：一次间接块
  - `i_block[13]`：二次间接块
  - `i_block[14]`：三次间接块

![文件系统层次结构](图表/OS/15_文件系统层次结构.png)

![iNode索引结构](图表/OS/10_iNode索引结构.png)

> **⚠️ 口径提示**：此处是 **ext2** 的“12直接 + 1一级 + 1二级 + 1三级”；而经典UNIX教材常写“10直接 + 3级间接”，两者来源不同，不矛盾。

---

## 8.6 文件操作与打开文件表（高频补强）

### 两级打开文件表

1. **系统打开文件表（全局）**
   - 记录：文件元信息引用（如iNode指针）、打开方式、当前偏移量、引用计数等
2. **进程打开文件表（每进程）**
   - 记录：该进程持有的文件描述符 `fd` 与系统打开文件表项的对应关系

> **关键关系**：`fd` 本质是“进程打开文件表的索引”，再间接指向系统打开文件表。

### `open()` 典型路径

1. 按路径检索目录项，定位目标文件iNode
2. 做权限检查与打开方式检查
3. 在系统打开文件表建立/复用表项（引用计数+1）
4. 在进程打开文件表分配一个空闲 `fd` 并返回

### `close()` 典型路径

1. 根据 `fd` 找到进程打开文件表项并清除
2. 对应系统打开文件表项引用计数减1
3. 若引用计数为0，按需回写并释放相关内核对象

### 常考辨析

- **多个 `fd` 可指向同一系统打开文件表项**（如 `dup`、`fork` 后继承）
- 若共享同一系统表项，文件偏移量通常联动变化；若分别 `open`，偏移量通常独立

---

# 第九章 磁盘存储器管理

## 9.1 外存组织方式

### 连续分配
- 目录项：文件名 + 起始盘块号 + 长度
- 优点：顺序访问快/支持随机访问
- 缺点：外碎片/需预知文件大小

### 链接分配
- **隐式链接**：每个盘块含指向下一盘块的指针
  - 仅支持顺序访问
- **显式链接（FAT）**：文件分配表放在内存中
  - FAT12（簇）/ FAT16（≤2048MB）/ FAT32（簇4KB,≤1TB,单文件≤4GB）/ NTFS
  - 支持随机访问

### 索引分配
- **单级索引**：一个索引块记录所有盘块号
- **多级索引**：索引块不够时,索引块指向索引块
- **增量式混合索引（UNIX）⭐**：

| 地址项 | 类型 | 4KB块时可寻址容量 |
|:---|:---|:---|
| i.addr(0)~i.addr(9)（经典UNIX） | **直接地址** | 10×4KB = 40KB |
| i.addr(10) | 一次间接 | 1K×4KB = 4MB |
| i.addr(11) | 二次间接 | 1K×1K×4KB = 4GB |
| i.addr(12) | 三次间接 | 1K×1K×1K×4KB = 4TB |

> **⚠️ 口径提示**：本表采用经典UNIX教材口径；与上章ext2的12个直接块写法属于不同文件系统实现。

---

## 9.2 空闲空间管理

| 方法 | 原理 | 特点 |
|:---|:---|:---|
| **空闲区表法** | 表项（起始块号+空闲块数），FF/BF分配 | 连续分配适用 |
| **空闲链表法** | 盘块链（效率低）/ 盘区链（FF,效率高） | 链接分配适用 |
| **位示图法⭐** | 每个盘块1bit，0空闲/1占用 | 简单高效 |
| **成组链接法（UNIX）** | 空闲盘块号栈（100个），栈底指向下一组 | 大型文件系统 |

### 位示图计算公式⭐

盘块号 $b$ → 位示图位置 $(i, j)$：

$$i = (b-1) \div n + 1, \quad j = (b-1) \mod n + 1$$

位示图 $(i, j)$ → 盘块号 $b$：

$$b = n \times (i-1) + j$$

其中 $n$ 为位示图每行的位数。

> **⚠️ 编号约定**：上述公式按“盘块号与位示图行列均从1开始编号”给出；若题目采用0起编号，需整体平移后再代入。

### 成组链接法（UNIX）
- 空闲盘块号栈：存放100个空闲盘块号
- 栈底（第一个单元）存放下一组100个空闲盘块号所在的盘块号
- **分配**：从栈顶取一块；栈空则将栈底指示的下一组读入
- **回收**：盘块号压入栈顶；栈满则将当前100个写入回收块,该块号成为新栈底

---

## 9.3 磁盘容错与RAID

### RAID级别
- RAID 0：条带化,无冗余
- RAID 1：镜像,100%冗余
- RAID 5：分布式奇偶校验
- RAID 6：双校验

### 软件容错技术（SFT）
- SFT-I：双份目录、双份FAT、热修复重定向、写后读校验
- SFT-II：磁盘镜像/磁盘双工
- 基于集群的容错：服务器镜像

---

## 9.4 存储新技术

| 技术 | 连接方式 | 访问级别 | 特点 |
|:---|:---|:---|:---|
| **DAS** | 直连主机 | 块级 | 简单/成本低/容量有限 |
| **NAS** | 网络附加(NFS/SMB) | **文件级** | 共享方便 |
| **SAN** | 存储区域网(光纤) | **块级** | 高性能/高可靠 |

---

## 9.5 数据一致性

### 事务
- 原子性：要么全做要么全不做
- 日志记录：(事务名, 数据项名, 旧值, 新值)
- **undo**（事务未完成时恢复旧值）/ **redo**（事务已完成时重做新值）

### 检查点
- 定期在日志中记录检查点
- 恢复时只处理检查点之后的事务

### 并发控制
- 互斥锁 / 共享锁（类似读者-写者问题）

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2009Q29、2010Q45、2012Q32、2015Q31/Q32、2019Q44、2021Q28、2024Q32、2025Q32
- **优质例题**：给定初始磁头位置与请求序列，分别按FCFS、SSTF、SCAN计算总移动磁道数。
- **最短解题模板**：
  1. 先按算法确定访问顺序。
  2. 总移动量 = 相邻访问磁道差绝对值求和。
  3. 需要时间时再乘“每磁道移动时间”并加旋转/传输延迟。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：先排顺序，再算移动量。
- **口令**：时间=寻道+旋转+传输。
- **口令**：SSTF快但可能饿死远端请求。

---

# 第十章 多处理机操作系统

## 10.1 多处理机系统类型

| 类型 | 耦合度 | 通信延迟 | 特点 |
|:---|:---|:---|:---|
| **紧密耦合** | 共享存储器 | 10~50ns | SMP/ASMP |
| **松散耦合** | 各自OS，通过通信链路连接 | 10~50ms | 分布式 |

### UMA结构（4种）

| 结构 | CPU数 | 特点 |
|:---|:---|:---|
| 单总线 | 4~20 | 可加高速缓存 |
| 多总线 | 16~32 | 私有存储器 |
| 单级交叉开关 | 8~16 | N²交叉点 |
| 多级交换网络 | <100 | 分散流量 |

### NUMA
- 多节点,3层存储：本地→群内共享→全局共享
- **CC-NUMA**：高速缓存+目录表保证一致性
- 主要问题：远程访问时延

---

## 10.2 多处理机OS类型

| 类型 | 特点 | 优缺点 |
|:---|:---|:---|
| **主从式** | 一个主处理机负责管理 | 简单但资源利用率低/主机瓶颈 |
| **独立监督式** | 每个处理机有自己的OS | 自主可靠但复杂/负载不均 |
| **浮动监督式** | 管理功能可在处理机间浮动 | 最灵活/最可靠/负载均衡,实现复杂 |

---

## 10.3 多处理机调度（2025新增重点⭐）

### 多处理机调度策略（2025新增）⭐

| 策略 | 描述 | 优点 | 缺点 |
|:---|:---|:---|:---|
| **全局队列调度** | OS维护一个公共就绪队列 | **负载均衡**最好 | 随着CPU增多,临界区**锁竞争**加剧 |
| **私有队列调度** | 每个CPU维护私有就绪队列 | **亲和性(Affinity)** 好,Cache命中率高 | 可能导致**负载不均**,需迁移机制 |

### 调度对应关系
- **单处理机调度**：解决“何时执行”
- **多处理机调度**：解决“何时执行” + **“在哪执行”**

### 调度策略算法
1. **负载分配（Load Sharing）**：通过推/拉机制在私有队列间平衡负载。
2. **群组调度（Gang Scheduling）**：将一个进程的所有相关线程**同时**调度到一组CPU上并行运行。
    - **目的**：减少同步阻塞（避免“互相等的线程没在运行”）。
3. **专用处理器分配**：某个应用长期独占一组CPU（适用于科学计算）。

---

## 10.4 多处理机上的进程同步

### 自旋锁⭐
- **适用于多处理机**的互斥机制
- 循环测试锁变量（忙等），不阻塞不切换
- **vs 信号量**：自旋锁避免了阻塞和进程切换开销,适用于**短临界区**
- 实现：总线设锁变量，循环Test-and-Set

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：近年独立命题少；与新增考纲“多处理机调度”强相关（2025起新增）
- **优质例题**：对比SMP中“公共就绪队列”与“私有就绪队列”的优缺点，判断何时需要负载均衡迁移。
- **最短解题模板**：
  1. 先判系统模型：ASMP 还是 SMP。
  2. 再判调度策略：亲和性优先还是吞吐优先。
  3. 结论用三词：可扩展性、均衡性、迁移开销。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：SMP看均衡，ASMP看主控。
- **口令**：自旋锁短临界区，信号量长临界区。
- **口令**：亲和性提局部性，迁移有代价。

---

# 第十一章 虚拟化和云计算

## 11.1 虚拟化

### VMM类型

| 类型 | 位置 | 示例 |
|:---|:---|:---|
| **Type1（裸金属型）** | 直接运行在硬件上 | Xen, ESXi, KVM |
| **Type2（寄居型）** | 运行在宿主OS之上 | VMware Workstation, VirtualBox |

### 虚拟化前提
- **敏感指令 ⊆ 特权指令**（Popek-Goldberg准则）
- 80x86不满足此条件 → Intel VT / AMD-V硬件辅助

### 虚拟化实现方式

| 方式 | 是否需修改Guest OS | 技术 |
|:---|:---|:---|
| **全虚拟化** | 否 | 二进制翻译 |
| **半虚拟化** | 是（使用hypercalls） | Xen的para-virtualization |
| **硬件辅助虚拟化** | 否 | VT-x,根模式/非根模式 |

### CPU虚拟化
- vCPU：虚拟CPU
- 指令执行：解释/扫描修补/二进制翻译/硬件辅助
- 上下文切换：VMCS（虚拟机控制结构）

### 内存虚拟化
- 两级映射：GVA→GPA→HPA
- 实现：**影子页表**（软件维护,开销大）或 **EPT/NPT**（硬件辅助二维页表,效率高）

### I/O虚拟化
- 全设备模拟 / 半虚拟化（前后端驱动）/ 直接I/O（VT-d）

---

## 11.2 云计算

### NIST定义的5个特征
- 按需自助服务
- 广泛的网络接入
- 资源池化
- 快速弹性伸缩
- 可计量服务

### 服务模型
- **SaaS**（软件即服务）：如Gmail
- **PaaS**（平台即服务）：如Google App Engine
- **IaaS**（基础设施即服务）：如AWS EC2

### VM迁移
- **静态迁移**：关机→复制→启动
- **动态（在线）迁移4阶段**：①开始 ②迭代传输（脏页） ③挂起+复制剩余脏页 ④提交+激活

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：2025Q24（虚拟化），其余年份多与系统结构综合考查
- **优质例题**：判断Type1/Type2 VMM部署位置，并比较全虚拟化与半虚拟化是否需要修改Guest OS。
- **最短解题模板**：
  1. 先看VMM位置：在硬件上=Type1；在宿主OS上=Type2。
  2. 再看Guest改动：要改Guest多为半虚拟化。
  3. 最后补一句：硬件辅助虚拟化依赖VT-x/AMD-V。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：Type1贴硬件，Type2压宿主。
- **口令**：改Guest多半虚拟，不改多全虚拟。
- **口令**：硬件辅助记VT-x/AMD-V。

---

# 第十二章 保护和安全

## 12.1 安全目标 CIA

| 目标 | 含义 |
|:---|:---|
| **机密性(Confidentiality)** | 防止未授权访问 |
| **完整性(Integrity)** | 防止未授权修改 |
| **可用性(Availability)** | 合法用户能及时获得服务 |

## 12.2 安全等级（TCSEC）

D → C1 → C2 → B1 → B2 → B3 → A（安全性递增）

| 等级 | 名称 | 特点 |
|:---|:---|:---|
| D | 最小保护 | 无安全特性,如MS-DOS |
| C1 | 自主安全保护 | 用户登录,访问控制 |
| C2 | 受控制的访问保护 | 审计功能,如Windows NT |
| B1 | 标记安全保护 | 强制访问控制 |
| B2 | 结构保护 | 形式化安全模型 |
| B3 | 安全域 | 可信恢复 |
| A | 验证设计 | 形式化验证 |

## 12.3 加密

| 方法 | 说明 |
|:---|:---|
| **易位法** | 改变明文字符排列顺序 |
| **置换法（替换密码）** | 用其他字符替换明文字符 |
| **对称加密（DES等）** | 加密和解密用同一密钥(64位) |
| **非对称加密（公钥密码）** | 公钥$K_e$加密,私钥$K_d$解密 |

### 数字签名
- **简单签名**：用发方私钥$K_{dA}$加密
- **保密签名**：先用发方私钥加密(签名),再用收方公钥加密(保密)

### 数字证书
- CA（证书授权机构）签发
- 包含：公钥+持有者信息+CA签名

## 12.4 用户验证

| 方式 | 示例 |
|:---|:---|
| 口令 | 密码 |
| 一次性口令 | 动态验证码 |
| 物理标志 | IC卡/U盾 |
| 生物识别 | 指纹/虹膜/面部 |

## 12.5 安全威胁

### 内部攻击
- **特洛伊木马**：隐藏在正常程序中的恶意代码
- **登录欺骗**：伪造登录界面窃取密码
- **逻辑炸弹**：在特定条件下触发的恶意代码
- **陷阱门（后门）**：绕过安全检查的秘密入口
- **缓冲区溢出**：最常见的攻击手段之一

### 外部攻击
- **病毒**：寄生于宿主程序，可自我复制
- **蠕虫**：独立运行，通过网络自我传播
- **移动代码**：通过网络传播的代码（如Java Applet）

### 🎯 本章真题锚点与最短模板

- **高频题号（2009-2025）**：近年在408中独立命题较少，常以内核态/特权指令/系统调用安全边界形式融合出题（如2012Q23、2015Q24）
- **优质例题**：给定攻击场景（木马/蠕虫/缓冲区溢出），判断攻击类别并匹配防护手段（认证/访问控制/加密）。
- **最短解题模板**：
  1. 先判攻击载体：宿主依赖=病毒；独立传播=蠕虫。
  2. 再判防线层次：身份认证→授权控制→数据加密。
  3. 最后对照CIA三目标：机密性、完整性、可用性。

### ⚡ 秒杀版口令卡（10秒回忆）

- **口令**：CIA三目标：机密、完整、可用。
- **口令**：病毒要宿主，蠕虫可独立。
- **口令**：安全三层：认证→授权→加密。

---

# 附录：408操作系统冲刺总览

## 一、408考纲变化与命题趋势（2021-2026）

| 年份 | 变化内容 | 命题影响 |
|:---:|:---|:---|
| 2021-2024 | 操作系统核心框架稳定（进程/内存/文件/I/O） | 题型相对稳定：选择+PV大题 |
| **2025** | 明确新增：**信号（Signal）**、**多处理机调度**；“页框分配”表述扩展为“页框分配与回收” | 2026起高概率考查新增概念辨析题 |
| 2026备考 | 继续强调“程序运行环境、内存映像、虚拟化、VFS” | 跨章节综合题概率上升 |

## 二、应试技巧（高分版）

1. **选择题策略（20分）**
  - 先做“概念判断题”（状态转换/中断异常/文件链接），再做“计算题”（调度/分页/置换/磁盘调度）。
  - 对计算题统一采用“先列公式→再代数值→最后写单位”的三步法，避免低级算错。
  - 新增考点优先锁定：**Signal与Semaphore辨析**、**页框分配与回收策略**、**COW触发条件**。

2. **大题策略（15分）**
  - **PV题**：先画前驱关系，再定义信号量含义，最后写P/V序列。
  - **内存题**：先拆地址位段（页号/页内偏移），再判TLB/页表命中路径，最后给物理地址。
  - **虚存题**：先判“页框分配策略（固定/可变）+置换范围（局部/全局）”，再分析是否抖动。
  - **文件题**：先确认分配方式（连续/链接/索引），再算访盘次数和最大文件长度。

3. **零基础30天冲刺法（OS专用）**
  - 第1阶段（1-10天）：进程状态、调度算法、PV基础、分页地址变换。
  - 第2阶段（11-20天）：页面置换、银行家算法、磁盘调度、文件索引计算。
  - 第3阶段（21-30天）：17年真题限时套练，按“概念错/计算错/审题错”分类复盘。

## 三、408跨学科联动速查表（OS视角）

| OS知识点 | 数据结构 | 计组 | 计网 |
|:---|:---|:---|:---|
| 进程调度队列 | 队列/优先队列（堆） | CPI与中断开销 | 服务器并发请求调度 |
| 银行家算法 | 矩阵运算/图判定 | 资源竞争与总线仲裁 | 并发连接资源控制 |
| 分页与TLB | 哈希（反置页表）/位图 | Cache-TLB-主存层次 | 无 |
| 页面置换（LRU/Clock） | 栈/链表/循环队列 | 局部性原理 | 路由缓存思想类比 |
| 文件索引结构 | 多叉树/B+树思想 | 磁盘与总线DMA | 文件传输协议语义 |
| I/O中断与DMA | 生产者-消费者模型 | 中断机制/DMA/总线 | 网卡中断与驱动模型 |

## 四、408操作系统高频失分陷阱速查表（⭐ 考前必看）

| # | 陷阱描述 | 正确结论 | 章节 |
|:---:|:---|:---|:---:|
| 1 | 并发=并行 | 并发是“同一时间段交替推进”，并行是“同一时刻同时执行” | Ch1 |
| 2 | 用户态可以执行I/O指令 | I/O、关中断、设置时钟等均为特权指令，必须核心态执行 | Ch1 |
| 3 | 系统调用是普通函数调用 | 系统调用会触发用户态→核心态切换 | Ch1 |
| 4 | 进程是调度基本单位 | 引入线程后：进程是资源分配单位，线程是调度单位 | Ch2 |
| 5 | 时间片用完进程进入阻塞态 | 时间片用完：执行态→就绪态，不是阻塞态 | Ch3 |
| 6 | SJF不会饥饿 | 长作业可能长期得不到调度，存在饥饿风险 | Ch3 |
| 7 | 死锁=饥饿 | 死锁是互相等待；饥饿是长期得不到资源 | Ch3 |
| 8 | 银行家算法用于死锁检测 | 银行家算法属于“死锁避免”，核心是安全序列判断 | Ch3 |
| 9 | Peterson算法可用于多进程通用互斥 | Peterson原型只直接适用于两进程 | Ch4 |
| 10 | P/V操作一定忙等 | 记录型信号量可阻塞等待，不必忙等 | Ch4 |
| 11 | 分页没有碎片 | 分页有“页内碎片”，只是没有外碎片 | Ch5 |
| 12 | 段号必须在所有进程中一致 | 共享段可映射到不同进程的不同段号 | Ch5 |
| 13 | FIFO一定优于LRU | FIFO可能出现Belady异常，LRU通常更稳 | Ch6 |
| 14 | 缺页中断是外中断 | 缺页属于内中断（异常） | Ch6 |
| 15 | DMA不需要CPU参与 | DMA仅数据传输阶段不占CPU，前后处理仍需CPU | Ch7 |
| 16 | 软链接和硬链接都共享iNode | 只有硬链接共享iNode；软链接是保存路径名的特殊文件 | Ch8 |
| 17 | FAT和iNode可以等价替换 | FAT是分配表机制，iNode是元数据索引机制，定位路径不同 | Ch8/9 |
| 18 | RAID 0也有容错 | RAID 0只有条带化无冗余，坏一盘可能全盘数据不可用 | Ch9 |
| 19 | Signal就是信号量 | Signal是异步事件通知；信号量用于同步互斥与资源计数 | Ch2/4 |
| 20 | `fork`一定立即复制全部内存 | 现代系统多用COW：写入时才复制页框 | Ch2/5 |
| 21 | 页框分配和页面置换可分开判断 | 二者耦合：分配过少会抖动，需结合工作集评估 | Ch6 |
| 22 | LOOK与SCAN等价 | LOOK到最远请求即折返；SCAN会扫到端点再折返 | Ch7/9 |

## 五、必记公式与易混淆概念速查

### 必记公式

| 公式 | 适用场景 |
|:---|:---|
| $\bar{T}=\frac{1}{n}\sum T_i$ | 平均周转时间 |
| $W_i=T_i/T_{si},\ \bar{W}=\frac{1}{n}\sum W_i$ | 带权周转时间 |
| $R_P = 1 + \frac{\text{等待时间}}{\text{服务时间}}$ | HRRN响应比 |
| $P = \left\lfloor\frac{A}{L}\right\rfloor,\ d = A \bmod L$ | 分页地址计算 |
| $EAT = h(t_{TLB}+t_m)+(1-h)(t_{TLB}+2t_m)$ | 含TLB有效访存时间 |
| $EAT = (1-p)\,t_m + p\,t_{pf}$ | 含缺页有效访存时间 |
| 单缓冲: $\max(C,T)+M$ | 缓冲区传输时间 |
| 双缓冲: $\max(C+M,T)$ | 缓冲区传输时间 |
| $T_a = T_s + \frac{1}{2r} + \frac{b}{rN}$ | 磁盘访问时间 |
| $\text{松弛度}=\text{截止时间}-\text{剩余时间}-\text{当前时间}$ | LLF实时调度 |
| $\sum C_i/P_i \leq 1$ | EDF判据（隐式截止期 $D_i=P_i$ 时为充要条件） |
| $U=\sum_{i=1}^{n}\frac{C_i}{P_i}\le n(2^{1/n}-1)$ | RM充分可调度条件 |
| $b=n(i-1)+j,\ i=\left\lfloor\frac{b-1}{n}\right\rfloor+1,\ j=(b-1)\bmod n+1$ | 位示图计算（默认1起编号） |
| $Need = Max - Allocation$ | 银行家算法 |

### 易混淆概念对比

| 概念A | 概念B | 关键区别 |
|:---|:---|:---|
| 并发 | 并行 | 并发=宏观同时微观交替（单CPU）；并行=真正同时（多CPU） |
| 进程 | 线程 | 进程=资源分配单位；线程=调度单位 |
| 死锁 | 饥饿 | 死锁=互相等待（都阻塞）；饥饿=长期等不到资源（可处就绪态） |
| 内碎片 | 外碎片 | 内碎片=分区内浪费（固定分区/页式）；外碎片=分区间浪费（动态分区/段式） |
| 分页 | 分段 | 页=物理单位（系统行为）；段=逻辑单位（用户行为） |
| 中断 | 异常 | 中断=外部（I/O/时钟）；异常=内部（除零/缺页/trap） |
| 信号量P | 管程wait | P使value-1，可能阻塞；wait一定阻塞并释放管程 |
| 信号量V | 管程signal | V使value+1（无等待也+1）；signal无等待则空操作 |
| Signal | Semaphore | Signal=事件通知；Semaphore=同步互斥/资源计数 |
| 硬链接 | 软链接 | 硬链接=共享iNode（count）；软链接=存路径的特殊文件 |
| 抢占式 | 非抢占式 | 抢占=可中途剥夺CPU；非抢占=运行到完成/阻塞才让出 |
| LRU | LFU | LRU=最久未使用；LFU=访问频率最低 |
| FIFO Belady | LRU无Belady | FIFO增页框可能增缺页（Belady异常）；LRU不会 |
| LOOK | SCAN | LOOK到最远请求即返；SCAN到磁道端点再返 |

## 六、秒杀版口令卡总汇（全12章）

### Ch1 操作系统引论
- 外设中断、内部异常、trap入核。
- 用户态禁特权，系统调用走内核。
- 判题三步：来源→态切换→干扰项。

### Ch2 进程的描述与控制
- 时间片到=就绪；等I/O=阻塞；I/O完=就绪。
- 进程管资源，线程管调度。
- 共享地址空间，私有栈与寄存器。
- Signal看事件通知，Semaphore看同步互斥。

### Ch3 处理机调度与死锁
- 调度先画图，不画必错时刻。
- 周转=完成-到达，带权=周转/服务。
- 死锁先四条件，再判安全序列。

### Ch4 进程同步
- 先前驱后PV，不画图不下笔。
- 互斥用mutex，同步用前驱信号量。
- 缓冲区三件套：`mutex`、`empty`、`full`。

### Ch5 存储器管理
- 先偏移后页号，最后算页表。
- 页号=高位，页内偏移=低位。
- 所有计算先统一单位。

### Ch6 虚拟存储器
- 置换必画表，口算易翻车。
- 命中不动，缺页才换。
- FIFO有Belady，LRU更稳。
- 先判页框分配，再判局部/全局置换。

### Ch7 输入/输出系统
- 轮询最忙，中断次之，DMA最省CPU。
- DMA传块，CPU只管前后处理。
- 占比=总CPU开销/总时长。

### Ch8 文件管理
- 先算每级扇出，再逐级乘方。
- 直接+一级+二级+三级，缺一项都丢分。
- 硬链接同iNode，软链接存路径。

### Ch9 磁盘存储器管理
- 先排顺序，再算移动量。
- 时间=寻道+旋转+传输。
- SSTF快但可能饿死远端请求。
- LOOK到最远请求即返，SCAN到端点再返。

### Ch10 多处理机操作系统
- SMP看均衡，ASMP看主控。
- 自旋锁短临界区，信号量长临界区。
- 亲和性提局部性，迁移有代价。

### Ch11 虚拟化和云计算
- Type1贴硬件，Type2压宿主。
- 改Guest多半虚拟，不改多全虚拟。
- 硬件辅助记VT-x/AMD-V。

### Ch12 保护和安全
- CIA三目标：机密、完整、可用。
- 病毒要宿主，蠕虫可独立。
- 安全三层：认证→授权→加密。

> 📝 **后记**：操作系统高分的关键不是“背定义”，而是把状态转换、地址变换、P/V建模、访盘次数这四类题训练到“看题即建模、落笔即得分”。
>
> **加油，未来的北大学子！💪**