Zhang XiJun

操作系统概论

操作系统的主要特征

并发性 (Concurrency)

🔍 核心定义

并发性是指两个或两个以上的事件或活动在同一时间间隔内发生。

• 关键点：“同一时间间隔” ≠ “同一时刻”。它强调的是“看起来同时”，而不是“真正同时”。

📌 操作系统中的体现

1. 多个 I/O 设备同时工作：
   • 你的键盘在输入，打印机在打印，网卡在收发数据。这些设备都在“同时”工作。
2. I/O 和 CPU 计算同时进行：
   • 当 CPU 在计算时，I/O 设备可能在后台传输数据。CPU 不需要等待 I/O 完成，可以去处理其他任务。
3. 内存中多个程序交替执行：
   • 这是最核心的体现。操作系统通过时间片轮转（Time-Slicing）等调度算法，让多个程序“轮流”使用 CPU，从而实现“宏观上的并发”。

🖼️ 并发 vs 并行

这是你 PPT 中提出的关键问题！

✅ 一句话总结：并行是并发的一种特例。并发是“逻辑上的同时”，并行是“物理上的同时”。

共享性 (Sharing)

🔍 核心定义

共享性指操作系统中的资源（包括硬件资源和软件资源）可被多个并发执行的进程共同使用，而不是被一个进程所独占。

• 关键点：共享不等于“无限制访问”，它必须在操作系统管理下进行，以保证安全和有序。

📌 资源共享的方式

1️⃣ 透明资源共享 / 同时共享方式

• 含义：允许多个进程在同一时间段内对资源进行访问，好像每个进程都独占资源一样。
• 特点：
  • 访问的次序对结果无影响。
  • 通常用于可重入或只读的资源。
• 例子：
  • CPU：通过时间片轮转，让多个进程“同时”使用 CPU。
  • 主存 (RAM)：多个进程的代码和数据可以同时存在于内存中。
  • 磁盘：多个进程可以同时读取磁盘上的不同文件。
  • 打印机：虽然物理上一次只能打印一个任务，但操作系统可以通过“打印队列”实现逻辑上的“同时共享”。

2️⃣ 独占资源共享 / 互斥共享方式

• 含义：在同一时间段内只允许一个进程访问资源。
• 特点：
  • 这类资源称为临界资源 (Critical Resource)。
  • 必须通过互斥机制（如锁、信号量）来保护。
• 例子：
  • 磁带机：一次只能由一个进程控制。
  • 扫描仪：一次只能扫描一份文档。
  • 数据库中的某一行记录：如果两个事务同时修改同一行，会导致数据不一致。

🛠️ 操作系统如何管理共享？

• 提供显式资源共享机制：如 fork(), semaphore, mutex, lock 等系统调用。
• 将互斥访问下放给用户决策：程序员需要自己负责加锁和解锁，操作系统提供工具。

异步性 (Asynchrony)

🔍 核心定义

异步性指在多道程序环境中，由于资源有限而进程众多，多数情况下，进程的执行不是一气呵成，而是“走走停停”。

• 关键点：进程的执行是不可预测的，它的推进速度取决于系统调度、I/O 等待、中断等多种因素。

📌 异步性的表现

1. 作业到达系统的时间和类型不确定：
   • 用户随时可能启动一个新程序。
2. 操作员发出命令或操作的时间和类型不确定：
   • 用户可能随时按下键盘或点击鼠标。
3. 程序运行发生错误或异常的类型和时刻不确定：
   • 程序可能因为除零、内存溢出等原因崩溃。
4. 中断事件发生的时刻不确定：
   • 时钟中断、I/O 中断、硬件故障中断等都是随机发生的。

1
2
3
4
5
6
7

graph TD
    A[并发性] --> B[多个任务同时执行]
    C[共享性] --> D[资源被多个任务共同使用]
    E[异步性] --> F[任务执行“走走停停”]

    B & D & F --> G[现代操作系统的核心特征]
    G --> H[实现多任务、多用户环境]

多道程序设计

核心思想

多道程序设计是指允许多个程序同时驻留在内存中，并由操作系统统一管理和调度，使它们交替（并发）地使用 CPU 和其他系统资源。

• 核心目的：掩盖 I/O 等待时间，提高 CPU 和系统资源的利用率。
• 终极目标：让昂贵的 CPU 永远不要闲着！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

gantt
    title 单道程序 vs 多道程序
    dateFormat  HH:mm:ss
    axisFormat  %Ss

    section 单道程序
    作业A-CPU     :crit, a1, 00:00:00, 2s
    作业A-I/O     :active, a2, after a1, 8s
    作业A-CPU     :crit, a3, after a2, 2s
    作业A-I/O     :active, a4, after a3, 8s

    section 多道程序
    作业A-CPU     :crit, b1, 00:00:00, 2s
    作业B-CPU     :crit, b2, after b1, 2s
    作业C-CPU     :crit, b3, after b2, 2s
    作业A-I/O     :active, b4, after b1, 8s
    作业B-I/O     :active, b5, after b2, 8s
    作业C-I/O     :active, b6, after b3, 8s

对比：在多道程序中，当作业 A 在等待 I/O 时，CPU 立刻去执行作业 B 和 C。CPU 几乎没有空闲时间，利用率接近 100%！

cpu利用率

CPU利用率 = 1 - p^n

🔍 假设条件

1. 系统中有 n 个程序 同时在内存中。
2. 每个程序平均有 p 的概率在等待 I/O 操作。
   • 例如，p = 0.8 表示一个程序有 80% 的时间在等磁盘读写、键盘输入等，只有 20% 的时间在真正使用 CPU。
3. 各个程序的等待操作是相互独立的。
   • 这是一个关键假设，意味着一个程序是否在等 I/O，不影响其他程序。

💡 公式推导

• CPU 空闲的概率：当且仅当所有 n 个程序都在等待 I/O 时，CPU 才会空闲。
• 因为每个程序等待 I/O 的概率是 p，且它们相互独立，所以所有 n 个程序都等待 I/O 的概率是 p^n。
• 因此，CPU 空闲的概率 = p^n。
• CPU 利用率 = 1 - CPU 空闲的概率 = 1 - p^n。

若进程平均花费 80% 的时间等待 I/O，则为了使得 CPU 利用率不低于 80%，应至少有多少道程序在主存中运行？

计算过程

根据公式：

CPU利用率 = 1 - p^n ≥ 0.8

移项得：

p^n ≤ 0.2

代入 p = 0.8：

0.8^n ≤ 0.2

两边取对数（以 10 为底或自然对数均可）：

n * log(0.8) ≤ log(0.2)

注意：log(0.8) 是负数，所以在除的时候要反转不等号方向：

n ≥ log(0.2) / log(0.8)

计算数值：

• log(0.2) ≈ -0.69897
• log(0.8) ≈ -0.09691
• n ≥ (-0.69897) / (-0.09691) ≈ 7.21

因为 n 必须是整数，且要满足 n ≥ 7.21，所以：

n = 8

✅ 最终答案

为了使得 CPU 利用率不低于 80%，应至少有 8 道程序在主存中运行。

是不是同时运行的程序越多越好？

不是！同时运行的程序（道数）并不是越多越好。存在一个最优的“道数”，超过这个值，系统的整体效率反而会下降。

当道数 n 超过某个临界值后，系统性能会急剧下降。主要原因有：

1️⃣ 上下文切换开销 (Context Switching Overhead)

什么是上下文切换？

• 当操作系统从一个进程切换到另一个进程时，它需要保存当前进程的状态（寄存器、内存映射、程序计数器等），并加载下一个进程的状态。

2️⃣ 内存压力 (Memory Pressure)

• 每个进程都需要内存：代码段、数据段、堆、栈、页表等。

3️⃣ 资源竞争加剧 (Resource Contention)

• 锁竞争：多个进程同时访问共享资源（如数据库连接池、文件锁），需要排队等待，增加了延迟。
• 缓存失效：多个进程的指令和数据交替进入 CPU 缓存，导致缓存命中率降低，CPU 需要更频繁地从内存读取数据。

处理器状态

为什么需要两种处理器状态？

现代计算机是一个多用户、多任务的环境。如果所有程序都能随意执行任何指令，那么一个不小心的 bug 或一个恶意程序就可能：

• 格式化硬盘。
• 修改系统时间。
• 访问其他用户的隐私数据。
• 导致系统崩溃。

为了避免这种情况，CPU 被设计成有两种工作模式：

1. 用户态 (User Mode)：普通程序运行的状态，只能执行“安全”的指令。
2. 核心态 (Kernel Mode / Supervisor Mode)：操作系统内核运行的状态，可以执行所有指令，包括“危险”的特权指令。

程序状态字 (PSW)

Program Status Word (PSW) 是一个非常重要的寄存器。

• 定义：PSW 是 CPU 内部的一个特殊寄存器，用于存储当前处理器的各种状态信息。
• 关键作用：PSW 中有一个标志位（通常是最高位或某一位），用来标识当前 CPU 处于用户态还是核心态。
  • PSW[bit] = 0 → 用户态
  • PSW[bit] = 1 → 核心态

✅ 这就是 CPU 判断当前是否可以执行特权指令的依据！

当 CPU 执行一条指令时，它会检查 PSW 中的这个标志位：

• 如果是用户态，并且指令是特权指令，则触发一个异常 (Exception)，操作系统会介入处理（通常是终止该程序）。
• 如果是核心态，则允许执行。

CPU 如何判断当前是否可以执行特权指令？

答案：CPU 通过检查 程序状态字 (PSW) 中的一个特定标志位来判断。

• 如果该标志位表示当前处于用户态，并且遇到的是特权指令，则 CPU 会触发一个异常（通常是“非法指令”或“特权指令违规”），并将控制权交给操作系统内核。
• 操作系统内核会根据情况决定是终止该程序，还是进行其他处理。

进程控制和管理

进程定义与属性

进程（Process）是程序在计算机上的一次执行实例，是操作系统进行资源分配、调度和保护的基本单位。

为什么要引入“进程”？

1️⃣ 刻画系统的动态性（Dynamic Nature）

• 问题：程序是静态的代码，无法描述“执行中”的状态。
• 解决方案：进程是一个动态实体，它有生命周期（创建 → 运行 → 阻塞 → 终止）。
• 意义：操作系统可以精确跟踪每个任务的当前状态，做出调度决策。

2️⃣ 发挥系统的并发性（Concurrency）

• 问题：CPU 和 I/O 设备速度不匹配。程序在等待 I/O（如读文件、网络请求）时，CPU 就空闲了。
• 解决方案：通过进程切换，让 CPU 在等待期间去执行其他任务。
• 意义：提高了 CPU 利用率和系统吞吐量。

3️⃣ 解决资源共享与隔离的矛盾

• 问题：多个程序可能需要共享资源（如文件、打印机），但又不能互相干扰。
• 解决方案：
  • 共享性：进程可以通过合法机制（如共享内存、消息队列）共享资源。
  • 独立性/保护性：每个进程拥有独立的地址空间，操作系统通过内存管理单元（MMU）确保 A 进程不能访问 B 进程的内存。
• 意义：既实现了协作，又保证了安全和稳定。

进程的五大核心属性

进程状态转换

五态模型

七态模型

七态模型在五态模型的基础上，显式增加了“挂起（Suspend）”的概念

挂起 = 进程被换出到外存（Swap）

• 目的：当系统内存紧张时，操作系统会将一些暂时不活跃的进程（比如长时间阻塞的进程）从内存移到硬盘上的“交换区（Swap Space）”，以腾出内存给更紧急的任务。

挂起就绪态 (Ready/Suspend)

定义：

进程具备运行条件（即它已经准备好执行），但目前在外存中。只有当它被换入内存后，才能被调度器选中运行。

挂起等待态 (Blocked/Suspend)

定义：

进程正在等待某一个事件发生（如 I/O 完成、用户输入、网络响应），并且目前在外存中。

进程描述和组成

进程映像

进程映像（Process Image）是指进程在内存中的完整内容，包括代码、数据、堆、栈以及内核数据结构（如 PCB）等所有组成部分的集合。

进程上下文

寄存器上下文 (Register Context)存储在 PCB 中 包含：通用寄存器、程序计数器、栈指针、程序状态字

这是进程“灵魂”的一部分——CPU 执行时最直接依赖的状态。

PCB（Process Control Block，进程控制块）

PCB 是操作系统为每个进程创建的一个数据结构，用来记录和刻画该进程的所有状态和相关信息。

1️⃣ 进程标识信息 (Identification Information)

🌰 你的例子：

1 2 3

import os print(f"当前进程 PID: {os.getpid()}") print(f"父进程 PID: {os.getppid()}")

这些值就是从 PCB 中读取的！

2️⃣ 处理器状态信息 (Processor State Information) —— 这就是“寄存器上下文”

这是 PCB 最关键的部分，用于上下文切换。

⚡ 关键点：每次进程切换时，操作系统都会将当前 CPU 寄存器的值“倾倒”进 PCB，再从新进程的 PCB “倒回”寄存器。这就是“上下文切换”的核心开销。

3️⃣ 进程调度信息 (Scheduling Information)

🌰 你的例子： 在 FastAPI 中，当一个请求在 await httpx.get(...) 时，其对应协程/线程的状态会被标记为“阻塞”，并被放入等待队列。这就是 PCB 中“进程状态”字段的作用。

4️⃣ 内存管理信息 (Memory Management Information)

💡 关键点：确保进程访问的是自己的内存空间，实现“内存保护”。

5️⃣ I/O 状态信息 (I/O Status Information)

🌰 你的例子： 当你在 Python 中 f = open("log.txt", "a") 时，操作系统会在 PCB 的“打开文件列表”中添加一条记录，记录这个文件句柄 f 对应的 fd。

6️⃣ 记账信息 (Accounting Information)

📊 用途：用于性能监控、计费、调试等。

进程队列

链接方式

索引方式

进程切换和处理器状态转换

模式切换 vs. 进程切换

1. 模式切换 (Mode Switch)

定义：CPU 在“用户态（User Mode）”和“核心态（Kernel Mode）”之间的切换。 触发方式：由中断（Interrupt）或系统调用（System Call） 引起。 目的：让操作系统获得控制权，执行特权指令（如访问硬件、修改内存映射）。

2. 进程切换 (Process Switch / Context Switch)

定义：操作系统暂停当前正在运行的进程，保存其状态，并加载另一个进程的状态，使其开始运行。 触发方式：通常发生在核心态下，由中断或系统调用引发。 目的：实现多任务并发，公平分配 CPU 时间。

当进程开始运行时，操作系统如何重新获得控制？

果进程一直在运行，操作系统就永远没机会调度其他进程了，系统就会卡死。

答案：中断 (Interrupt) 是关键！

• 什么是中断？ 中断就像一个“紧急电话”，它能打断 CPU 当前正在执行的程序，强制 CPU 去处理一个更高优先级的事情——通常是操作系统内核。
  • 硬件中断：由外部设备触发，比如键盘敲击、鼠标移动、网络数据包到达、定时器到期。
  • 软件中断/异常：由程序自身触发，比如除零错误、访问非法内存地址、或者程序主动发起的系统调用（如 open(), read()）。

进程需要保存哪些状态？

当操作系统获得控制权后，它必须把当前正在运行的进程（比如进程0）的“工作状态”完整地记录下来，以便将来能恢复执行。这个过程叫做“保存现场 (Save Context)”。

需要保存哪些状态？

这些状态主要存储在一个叫做 PCB (Process Control Block, 进程控制块) 的数据结构里。PCB 就像是进程的“身份证 + 工作日志 + 资源清单”。

如何选择下一个待执行的进程/线程？

当操作系统保存完当前进程的状态后，它需要决定“接下来该让谁干活”。这个决策过程叫做“进程调度 (Process Scheduling)”。

如何选择？

这取决于操作系统的调度算法 (Scheduling Algorithm)。

线程

为什么需要线程？—— 引入线程的动机

❓ 问题：进程模型有什么不足？

1. 切换开销大：进程切换需要保存/恢复整个内存空间（代码、数据、堆、栈）和 PCB，开销大。
2. 通信困难：进程间通信（IPC）需要管道、消息队列、共享内存等复杂机制，效率低。
3. 不适合细粒度并发：比如一个 Web 服务器，每个请求都创建一个进程，成本太高。

✅ 解决方案：引入线程！

线程是进程内的一个执行单元，是 CPU 调度和分派的基本单位。

• 同一个进程内的所有线程：
  • 共享：代码段、数据段、堆、打开的文件等进程资源。
  • 私有：各自的栈和寄存器上下文。

💡 核心价值：实现进程内部的并发，降低切换和通信开销。

什么是线程？—— 核心定义

线程（Thread）是进程中一个可并发执行的控制流，它拥有自己独立的栈和寄存器状态，但与其他线程共享进程的地址空间和资源。

线程如何工作？—— 线程的生命周期与切换

1. 线程的生命周期状态

和进程类似，线程也有状态：新建 → 就绪 → 运行 → 阻塞 → 终止。

2. 线程切换（Thread Switching）

• 开销远小于进程切换！因为不需要切换地址空间（页表），只需要保存/恢复寄存器上下文和栈指针。
• 切换由线程调度器（在 OS 内核或用户态库中）管理。

3. 线程的实现方式

💡 Python 的 threading 是内核级线程，但受 GIL 限制，无法真正并行执行 Python 字节码。

处理器调度

调度层次

1️⃣ 高级调度（High-Level Scheduling）—— 作业调度 / 长程调度

目标：决定哪些“作业”被允许进入系统参与 CPU 竞争。 对象：作业（Job）→ 通常是一个完整的程序或任务（如编译一个文件、运行一个脚本）。 发生频率：低（几分钟到几小时一次）。 执行者：操作系统内核。

🔍 核心功能：

• 选作业进内存：从后备队列中选择作业，将其加载到内存，创建进程。
• 控制多道程序的道数：决定同时在内存中运行多少个作业（即并发度）。太多会耗尽内存，太少会浪费 CPU。

2️⃣ 中级调度（Medium-Level Scheduling）—— 平衡调度 / 内存调度

目标：根据内存状态，决定哪些进程可以在内存中运行，哪些需要换出到外存。 对象：进程（Process）。 发生频率：中等（几秒到几分钟一次）。 执行者：操作系统内核。

🔍 核心功能：

• 选进程进出内存：当内存紧张时，将一些不活跃的进程（如长时间阻塞的进程）换出到 Swap 分区；当内存空闲时，再换回。
• 平衡系统负载：防止内存溢出，提高系统吞吐量。

3️⃣ 低级调度（Low-Level Scheduling）—— 进程调度 / CPU 调度

目标：决定哪个就绪队列中的进程/线程获得 CPU 执行权。 对象：进程或线程（内核级线程）。 发生频率：高（毫秒级，每几十到几百毫秒一次）。 执行者：操作系统内核 → 这是操作系统最核心的部分！

🔍 核心功能：

• 选进程分配 CPU：从就绪队列中选出下一个要运行的进程/线程。
• 执行上下文切换：保存当前进程上下文，恢复新进程上下文。
• 实现公平与效率：通过调度算法（如 RR、优先级、MLFQ）保证所有进程都能得到 CPU 时间。

1
2
3
4
5
6
7
8

graph LR
    A[高级调度] -->|选作业进内存| B[中级调度]
    B -->|选进程进出内存| C[低级调度]
    C -->|选进程分配 CPU| D[CPU 执行]

    style A fill:#f9d5e5,stroke:#333
    style B fill:#e3eaa7,stroke:#333
    style C fill:#b2d3c2,stroke:#333

调度算法评价指标

七种调度策略

先来先服务 (First Come First Serverd, FCFS)

短作业优先 (Shortest Job First, SJF)

最短剩余时间优先 (Shortest Remaining Time First, SRTF)

最高响应比优先 (Highest Response Ratio First, HRRF)

优先级调度 (Priority Scheduling)

轮转调度 (Round Robin Scheduling, RR)

多级反馈队列调度 (Multi-Level Feedback Queue, MLFQ)

并发：互斥与同步

进程交互

为什么需要“进程交互”？

在单进程时代，程序是“独占”的——它不需要考虑别人。但在现代操作系统中：

• 多个进程/线程同时运行。
• 它们可能共享资源（如内存、文件、数据库连接）。
• 它们可能需要协同完成一个复杂任务（如一个 Web 请求涉及多个微服务）。

这就产生了两个根本性问题：

1. 竞争（Competition）：多个进程争抢同一个资源，导致结果不可预测。
2. 协作（Cooperation）：多个进程需要按特定顺序执行，才能完成共同目标。

✅ 进程交互就是解决这两个问题的机制。

竞争关系（进程互斥）

✅ 核心定义：

进程互斥是指若干进程因相互争夺独占型资源而产生的竞争制约关系。

📌 关键词解析：

• “相互争夺”：多个进程都想使用同一个资源。
• “独占型资源”：一次只能被一个进程使用的资源，如打印机、临界区代码、全局变量、数据库连接等。
• “竞争制约关系”：一个进程的执行会制约另一个进程的执行。

🧱 两个核心控制问题：

1. 死锁问题（Deadlock）
   • 定义：多个进程互相等待对方释放资源，导致所有进程都无法继续执行。
   • 经典例子：“哲学家就餐问题”——五个哲学家围坐圆桌，每人左右各有一根筷子。他们必须拿到两根筷子才能吃饭。如果每个人都拿起左边的筷子，然后等待右边的筷子，就会陷入死锁。
   • 四个必要条件：
     • 互斥条件
     • 请求与保持条件
     • 不剥夺条件
     • 环路等待条件
2. 饥饿问题（Starvation）
   • 定义：某个进程因为优先级低或资源分配策略不当，长时间得不到所需资源，导致无法执行。
   • 例子：在一个高优先级任务永远不结束的系统中，低优先级任务可能永远得不到 CPU。

协作关系（进程同步）

✅ 核心定义：

进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。

📌 关键词解析：

• “完成共同任务”：多个进程/线程需要合作才能达成目标。
• “协调活动”：它们需要按特定顺序执行。
• “排定执行先后次序”：比如 A 必须在 B 之前执行。
• “等待、传递信号或消息”：通过同步机制（如信号量、条件变量、管道）实现通信和协调。

🧱 核心思想：

• “生产者-消费者”模型：生产者生成数据，消费者消费数据，它们必须同步。
• “读者-写者”模型：读者可以同时读，但写者必须独占。
• “屏障（Barrier）”：所有进程到达某个点后才能继续执行。

临界区管理

什么是“临界区”？

✅ 核心定义：

并发进程中，与共享变量有关的程序段叫做“临界区”（Critical Section）。

📌 关键词解析：

• “并发进程”：多个进程/线程同时运行。
• “共享变量”：多个进程都能访问和修改的变量（如全局变量、数据库连接、文件句柄）。
• “程序段”：一段代码，比如 counter += 1 这样的操作。

💡 简单说：临界区 = 操作共享资源的那一小段代码。

🎯 为什么重要？

因为这段代码如果被多个进程同时执行，会导致竞态条件（Race Condition），产生不可预测的结果。

如何避免错误？—— 互斥访问临界区

如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。

这就是“进程互斥”的核心思想。

临界区调度的三个原则（经典！）

这是解决临界区问题的黄金法则，任何同步机制都必须满足这三个条件：

✅ 原则 1：一次至多一个进程能够进入临界区内执行

互斥性（Mutual Exclusion）

• 这是最基本的要求。任何时候，最多只能有一个进程在临界区内。
• 如果 A 在临界区，B 就不能进入，必须等待。

✅ 原则 2：如果已有进程在临界区，其他试图进入的进程应等待

忙则等待（Progress）

• 如果临界区空闲，想进入的进程可以立即进入。
• 如果临界区被占用，其他进程必须等待，不能“自旋”浪费 CPU（虽然有些实现会自旋，但理想情况下应该阻塞等待）。

✅ 原则 3：进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入

有限等待（Bounded Waiting）

• 防止“饥饿”。不能让某个进程永远等下去。
• 例如，使用队列来管理等待的进程，确保每个进程最终都能获得进入临界区的机会。

实现临界区管理的软件方法一Peterson方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int turn;           // turn 表示轮到谁进入
boolean flag[2];   // flag[i] 表示进程 i 想进入临界区

// 初始化
flag[0] = flag[1] = false;

Process P0() {
    flag[0] = true;
    turn = 1;       // 谦让给 P1
    while (flag[1] && turn == 1); // 等待 P1 退出或谦让
    /* critical section */
    flag[0] = false;
    /* remainder section */
}

Process P1() {
    flag[1] = true;
    turn = 0;       // 谦让给 P0
    while (flag[0] && turn == 0); // 等待 P0 退出或谦让
    /* critical section */
    flag[1] = false;
    /* remainder section */
}

✅ 1. 互斥性 (Mutual Exclusion)

定义：一次至多一个进程能进入临界区。

📌 证明思路：

• 假设 P0 和 P1 同时进入临界区。
• 那么 flag[0] = true 且 flag[1] = true。
• 根据算法，P0 在进入前设置了 turn = 1，P1 设置了 turn = 0。
• 由于 turn 只能取值 0 或 1，不可能同时为 0 和 1。
• 所以，当 P0 检查 while (flag[1] && turn == 1) 时，如果 turn == 0，它就会阻塞。
• 同理，P1 也会被阻塞。
• 结论：不可能同时进入。

✅ 2. 空闲让进 (Progress)

定义：如果临界区空闲，且有进程想进入，则该进程应该能进入。

📌 证明思路：

• 如果 P1 不想进入临界区，则 flag[1] = false。
• 此时，无论 turn 是多少，P0 的 while (flag[1] && turn == 1) 条件都会失败（因为 flag[1] 是 false），所以 P0 可以立即进入临界区。

✅ 3. 有限等待 (Bounded Waiting)

定义：一个进程最多等待另一个进程执行完临界区一次，就能获得进入的机会。

📌 证明思路：

• 假设 P0 被阻塞，说明 turn = 1 且 flag[1] = true，即 P1 在临界区。
• 当 P1 执行完临界区后，它会设置 flag[1] = false。
• 此时，如果 P0 还想进入，它的 while 条件会失败，从而进入临界区。
• 如果 P1 在 flag[1] = false 后又想进入，则它会设置 flag[1] = true 和 turn = 0。
• 此时，P0 会被阻塞，但 P1 执行完后，P0 就能进入。
• 结论：P0 最多等待 P1 执行一次临界区，就能进入。

信号量与PV操作

信号量（Semaphore）

✅ 核心定义：

信号量是一种软件资源，用于表示物理资源的实体，是一个与队列有关的整型变量。

📌 关键词解析：

• “表示物理资源”：比如打印机、数据库连接池、线程池中的可用线程数。
• “整型变量”：信号量的值代表当前可用资源的数量。
• “与队列有关”：当资源不足时，等待的进程会被放入一个等待队列。

P/V 操作：信号量的“原子操作”

✅ 定义：

P (Proberen, 尝试) 和 V (Verhogen, 增加) 是对信号量进行操作的原语。

• P 操作：尝试获取资源。如果资源可用（信号量 > 0），则减 1；否则，进程进入等待队列。
• V 操作：释放资源。增加信号量值，并唤醒一个等待的进程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// P 操作 (Wait)
void P(semaphore s) {
    s.value = s.value - 1;
    if (s.value < 0) {
        // 资源不足，将当前进程加入等待队列并阻塞
        block(current_process);
    }
}

// V 操作 (Signal)
void V(semaphore s) {
    s.value = s.value + 1;
    if (s.value <= 0) {
        // 有进程在等待，唤醒一个
        wakeup(one_waiting_process);
    }
}

⚠️ 关键点：P/V 操作必须是原子操作（Atomic Operation），即在执行过程中不能被中断。否则会导致竞态条件。

哲学家进餐问题

哲学家进餐问题：核心描述

✅ 问题设定：

• 有 5 位哲学家 围坐在一张圆桌旁。
• 每位哲学家面前有一盘意大利面。
• 桌子上有 5 把叉子，每两位哲学家之间放一把。
• 哲学家的生活只有两件事：
  • 思考（Think）：什么都不做。
  • 吃饭（Eat）：必须同时拿到左右两边的叉子才能吃。
• 吃完后，会放下叉子，继续思考。

💡 目标：设计一个算法，让所有哲学家都能吃饱，且不会发生死锁或饥饿。

为什么会出现死锁？

📌 死锁的四个必要条件：

1. 互斥条件：叉子一次只能被一个人使用。
2. 请求与保持条件：哲学家拿起一把叉子后，会继续等待另一把。
3. 不剥夺条件：不能强行从哲学家手中拿走叉子。
4. 环路等待条件：每位哲学家都在等右边的人放下叉子，形成一个循环等待链。

解决方案：打破死锁的四个条件之一

要避免死锁，只需破坏其中一个必要条件即可。以下是几种经典的解决方案：

✅ 解决方案 1：限制同时就餐的哲学家数量（破坏“环路等待”）

最多允许 4 位哲学家同时吃面。

📌 原理：

• 如果只有 4 个人尝试拿叉子，那么至少有一把叉子是空闲的。
• 这样，总会有一个人能拿到两把叉子并吃完，从而释放资源。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import threading
import time

# 5 把叉子（信号量）
forks = [threading.Semaphore(1) for _ in range(5)]
# 限制同时就餐人数为 4
dining_room = threading.Semaphore(4)

def philosopher(i):
    while True:
        think()
        dining_room.acquire()  # 进入餐厅（最多 4 人）
        
        forks[i].acquire()       # 拿起左边叉子
        forks[(i + 1) % 5].acquire()  # 拿起右边叉子
        
        eat(i)
        
        forks[i].release()       # 放下左边叉子
        forks[(i + 1) % 5].release()  # 放下右边叉子
        
        dining_room.release()    # 离开餐厅

def think():
    time.sleep(0.1)

def eat(i):
    print(f"Philosopher {i} is eating...")
    time.sleep(0.1)

# 创建 5 个哲学家线程
threads = []
for i in range(5):
    t = threading.Thread(target=philosopher, args=(i,))
    threads.append(t)
    t.start()

for t in threads:
    t.join()

✅ 解决方案 2：奇偶号哲学家取叉子顺序不同（破坏“环路等待”）

奇数号哲学家先取左边叉子，再取右边；偶数号哲学家先取右边叉子，再取左边。

📌 原理：

• 这样就不会形成环路等待。
• 例如，哲学家 0（偶数）先拿右边叉子（叉子 1），哲学家 1（奇数）先拿左边叉子（叉子 1）→ 他们争抢同一把叉子，但最终只会有一个成功，另一个等待，从而打破环路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def philosopher(i):
    while True:
        think()
        
        if i % 2 == 0:  # 偶数号哲学家
            forks[(i + 1) % 5].acquire()  # 先拿右边叉子
            forks[i].acquire()             # 再拿左边叉子
        else:  # 奇数号哲学家
            forks[i].acquire()             # 先拿左边叉子
            forks[(i + 1) % 5].acquire()  # 再拿右边叉子
        
        eat(i)
        
        forks[i].release()                 # 放下左边叉子
        forks[(i + 1) % 5].release()      # 放下右边叉子

✅ 解决方案 3：拿起两把叉子才开始吃（破坏“请求与保持”）

每位哲学家必须同时拿到两把叉子才能开始吃，否则一把也不拿。

1️⃣ 全局变量定义

1
2
3
4
5
6
7

#define THINKING 0
#define HUNGRY   1
#define EATING   2

semaphore s[5];     // 用于阻塞哲学家的信号量
semaphore mutex = 1; // 互斥锁，保护 state 和 s
int state[5];      // 哲学家的状态

• s[i] 初始值为 0，因为一开始没有人需要等待。
• state[i] 初始化为 THINKING。

2️⃣ take_fork(int i) 函数

1
2
3
4
5
6
7

void take_fork(int i) {
    P(mutex);           // 获取互斥锁
    state[i] = HUNGRY;  // 哲学家 i 变成饥饿状态
    test(i);            // 尝试让 i 吃饭
    V(mutex);           // 释放互斥锁
    P(s[i]);            // 如果 test(i) 没有让 i 吃上饭，这里会阻塞
}

📌 关键点：

• state[i] = HUNGRY: 告诉“管家”，我饿了。
• test(i): “管家”检查我是否能吃。
  • 如果能吃，test(i) 会执行 V(s[i])，唤醒我。
  • 如果不能吃，test(i) 不做任何事。
• P(s[i]): 如果我没被唤醒，我就在这里阻塞，等待邻居放叉子。

✅ 这个函数是“非阻塞”的：它只负责声明“我饿了”，然后立即返回。真正的等待发生在 P(s[i])。

3️⃣ put_fork(int i) 函数

1
2
3
4
5
6
7

void put_fork(int i) {
    P(mutex);           // 获取互斥锁
    state[i] = THINKING; // 哲学家 i 变成思考状态
    test((i + 1) % 5);  // 检查右边邻居
    test((i + 4) % 5);  // 检查左边邻居（(i+4)%5 == (i-1)%5）
    V(mutex);           // 释放互斥锁
}

📌 关键点：

• state[i] = THINKING: 我吃饱了，不再占用叉子。
• test((i+1)%5) 和 test((i+4)%5): 告诉“管家”，我的邻居们可能现在可以吃饭了。
  • 例如，哲学家 0 放下叉子后，哲学家 1 和 4 可能现在能拿到两把叉子了。
  • “管家”会检查他们是否处于 HUNGRY 状态，并且邻居都不在吃，如果是，就唤醒他们。

4️⃣ test(int i) 函数 —— 核心逻辑！

1
2
3
4
5
6
7
8

void test(int i) {
    if (state[i] == HUNGRY &&
        state[(i + 1) % 5] != EATING &&
        state[(i + 4) % 5] != EATING) {
        state[i] = EATING;  // 可以吃了！
        V(s[i]);            // 唤醒哲学家 i
    }
}

📌 关键点：

• 检查三个条件：
  1. state[i] == HUNGRY: 我确实想吃饭。
  2. state[(i+1)%5] != EATING: 我右边的邻居没在吃。
  3. state[(i+4)%5] != EATING: 我左边的邻居没在吃。
• 如果都满足：说明我现在可以拿到两把叉子！
  • 设置 state[i] = EATING。
  • 执行 V(s[i])，唤醒我自己（因为我在 take_fork 中 P(s[i]) 阻塞了）。

✅ 这个函数是“原子”的：因为它在 mutex 保护下执行，不会被其他哲学家打断。

生产者消费者问题

mutex 的作用就是：

保护对共享变量（或临界区）的访问， 只在真正操作这些共享资源的前后“加锁”和“解锁”。

（防死锁铁律）：

永远不要在持有互斥锁（mutex）的情况下，调用可能阻塞的操作（如 P(empty)、P(full)、sleep、wait 等）。

什么是生产者-消费者问题？

这是一个经典的多线程同步问题，用于模拟现实中的“生产”与“消费”场景：

• 生产者 (Producer)：负责制造数据或产品。
• 消费者 (Consumer)：负责处理或消费这些数据/产品。
• 缓冲区 (Buffer)：一个有限大小的共享空间，用来暂存生产者的产品，供消费者取用。

📌 核心挑战

1. 互斥 (Mutual Exclusion)：多个生产者/消费者不能同时操作缓冲区的同一个位置，否则数据会错乱。
2. 同步 (Synchronization)：
   • 生产者不能在缓冲区满时继续生产（要等待）。
   • 消费者不能在缓冲区空时继续消费（要等待）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

item B[n];
Semaphore empty;  /*可用的空缓冲区个数*/
Semaphore full;   /*可用的产品数*/
Semaphore mutex;  /*互斥信号量*/
empty = n; full = 0; mutex = 1;
int in = 0; out = 0;  /*in为放入缓冲区指针, out为取出缓冲区指针*/

Process producer_i( ) {
    while(true) {
        item product = produce();
        P(empty);
        P(mutex);
        B[in] = product;
        in = (in+1) % n;
        V(mutex);
        V(full);
    }
}

Process consumer_i( ) {
    while(true) {
        P(full);
        P(mutex);
        Item product = B[out];
        out = (out+1) % n;
        V(mutex);
        V(empty);
        consume(product);
    }
}

问题：如果将P操作的顺序交换，会出现什么情况？

生产者霸占着 mutex 锁，等待 empty，消费者等待 mutex 锁，导致死锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

sequenceDiagram
    participant Producer as 生产者 P1
    participant Consumer as 消费者 C1
    participant Mutex as 互斥锁 (mutex)
    participant Empty as 空闲缓冲区 (empty)

    Note over Producer,Consumer: 初始状态: empty=0 (缓冲区满), mutex=1

    Producer->>Mutex: P(mutex) // 成功获取锁，mutex=0
    Producer->>Empty: P(empty) // empty=0，阻塞！等待空位...
    Note over Producer: 生产者 P1 霸占 mutex 锁，等待 empty

    Consumer->>Full: P(full) // full=1，成功，full=0
    Consumer->>Mutex: P(mutex) // mutex=0，阻塞！等待锁...
    Note over Consumer: 消费者 C1 等待 mutex 锁

    Note over Producer,Consumer: 💥 死锁！
    Note right of Producer: 我要等 empty (需 C1 消费)
    Note left of Consumer: 我要等 mutex (需 P1 释放)

问题：当前生产者消费者共用一个互斥锁会造成竞争

1
2
3
4

Semaphore pmutex, cmutex; // 两个独立的互斥锁
...
P(pmutex); // 生产者只锁自己的写入区域
P(cmutex); // 消费者只锁自己的读取区域

优势：

• 生产者之间：仍然需要 pmutex 来互斥，因为多个生产者可能同时想写入 in 指针指向的位置。
• 消费者之间：仍然需要 cmutex 来互斥，因为多个消费者可能同时想读取 out 指针指向的位置。
• 生产者 vs 消费者：它们可以并行！ 只要生产者在写一个位置，消费者在读另一个位置，两者互不干扰，完全可以同时进行。

死锁

死锁产生

什么是死锁

在多进程/多线程系统中，死锁是指两个或多个进程因竞争资源而造成的一种互相等待的现象，若无外力作用，它们都将无法向前推进。

简单说：A 等 B，B 等 C，C 又等 A，大家谁也不让步，结果全都卡住。

死锁的4个必要条件

只要系统发生死锁，以下4个条件必然同时成立。缺一不可！

1️⃣ 互斥访问 (Mutual Exclusion)

• 定义：系统中存在临界资源，进程应互斥地使用这些资源。
• 通俗解释：资源一次只能被一个进程使用。比如，打印机、文件、数据库连接、内存中的某个变量等。
• 为什么是必要条件？如果资源可以被多个进程同时共享（如只读文件），那就不存在竞争，也就不会死锁。

2️⃣ 占有和等待 (Hold and Wait)

• 定义：进程在请求资源得不到满足而等待时，不释放已占有的资源。
• 通俗解释：一个进程已经拿着一些资源，但它还需要其他资源才能完成工作，于是它一边等着新资源，一边还紧紧攥着自己手里的旧资源，不肯放手。
• 为什么是必要条件？如果一个进程在等待新资源时能主动释放旧资源，那么它就不会阻塞别人，死锁也就不会形成。

3️⃣ 不剥夺 (No Preemption)

• 定义：已被占用的资源只能由属主进程自愿释放，而不允许被其他进程剥夺。
• 通俗解释：资源一旦被某个进程拿走，除非它自己愿意还回来，否则谁也不能强行抢走。这保证了进程的“自主性”，但也为死锁埋下了隐患。
• 为什么是必要条件？如果系统能强行剥夺资源（比如操作系统强制回收），那么就可以打破死锁链。

4️⃣ 循环等待 (Circular Wait)

• 定义：存在循环等待链，每个进程在链中等待下一个进程所持有的资源，造成这组进程处于永远等待状态。
• 通俗解释：这是一个闭环。A 等 B 的资源，B 等 C 的资源，C 又等 A 的资源，形成了一个“等待环”。
• 为什么是必要条件？如果没有循环，等待链最终会指向一个“不等待”的进程，这个进程完成后会释放资源，从而解开整个等待链。

死锁防止

死锁避免

银行家算法

死锁检测和解除

资源分配图

• 阻塞节点 (Blocked Node)：一个进程，它正在请求一个或多个资源，但这些资源当前都被其他进程占用，且没有空闲实例可用。它必须等待。
• 非阻塞节点 (Non-blocked Node)：一个进程，它要么没有请求任何资源，要么它请求的资源当前有空闲实例可以立即满足。它可以继续执行。

如何通过资源分配图判断死锁？

✅ 死锁的充分条件（当资源类型只有一个实例时）

如果资源分配图中存在一个环，则系统一定发生死锁。

• 原因：在一个环中，每个进程都在等待下一个进程所持有的资源，而下一个进程又在等待再下一个……形成一个无限等待的闭环。

⚠️ 当资源类型有多个实例时

环的存在是死锁的必要条件，但不是充分条件。

• 原因：即使图中有环，但如果环中的某个资源类型有多个实例，那么可能还有空闲实例可以满足某个进程的需求，从而打破死锁。

资源分配图的简化

死锁检测算法

与银行家算法的安全性检测类似

存储管理

内存是什么？

从物理上讲，内存通常指的是随机存取存储器（RAM - Random Access Memory）。

从操作系统的角度来看，内存是CPU（大脑）和硬盘（仓库）之间的“高速中转站”。它是计算机暂时存放数据的地方，用来存储当前正在运行的程序和正在处理的数据。

存储层次结构

计算机的存储设备像一个金字塔，越往上速度越快、价格越贵、容量越小：

1. 寄存器 (Registers): 在 CPU 内部，极快，容量极小（纳秒级）。
2. 高速缓存 (Cache): 在 CPU 旁边，非常快（L1/L2/L3）。
3. 内存 (Main Memory/RAM): 我们今天的主角，速度适中，容量适中。
4. 本地磁盘 (Local Disk): 机械硬盘或固态硬盘，慢，容量巨大（毫秒级）。

操作系统的任务： 主要是管理第3层（内存），并负责在内存和磁盘之间搬运数据。

逻辑地址和物理地址

逻辑地址 (Logical Address)

• 别名： 虚拟地址 (Virtual Address)。
• 谁生成的？ CPU（在执行程序时）。
• 是什么？ 这是程序“眼中”的地址。
  • 当程序员写代码或者编译器编译程序时，它们看到的都是逻辑地址。
  • 程序觉得：“我拥有从 0 到 Max 的一整块连续内存。”

物理地址 (Physical Address)

• 谁看到的？ 内存条（硬件）。
• 是什么？ 这是数据在内存条上真正的“门牌号”。
  • 它对应着内存芯片中某个具体的存储单元。
  • 只有操作系统和硬件知道数据真正藏在哪里。

内存复用方式

为了支持多道程序设计（让电脑同时跑微信、浏览器、游戏），内存必须被复用。复用只有两种基本手段：

1. 切大块（按照分区复用）：
   • 把内存切成几个大块（分区）。
   • 规矩： 一个程序必须完整地塞进一个分区里（连续存放）。
2. 切碎块（按照页框复用）：
   • 把内存切成无数个一样大的小格子（页框）。
   • 规矩： 一个程序可以被切碎，散落在多个页框里（离散存放）。

四大具体方法

这张图非常精彩，它展示了从“逻辑空间”（你以为的样子）到“物理空间”（实际的样子）的四种映射路径。请看着图中的 ①、②、③、④。

1. 路径 ①：单连续/分区存储管理 (The “Old School”)

• 逻辑上： 程序认为自己是一条连续的直路（单连续逻辑地址空间）。
• 物理上： 放入“分区”（Partition）。
• 解释：
  • 这是最原始的方法。程序多大，就在内存里找个多大的坑填进去。
  • 缺点： 必须连续。如果你有 100MB 内存，中间断断续续空了 50MB，但没有一块连续的 50MB，那 50MB 的程序就跑不起来。这叫“外部碎片”。

2. 路径 ②：页式存储管理 (Paging - 现代主流的基础)

• 逻辑上： 程序依然认为自己是一条连续的直路（单连续逻辑地址空间）。
• 物理上： 放入“页框”（Page Frames）。
• 变化：
  • 虽然程序觉得自己是连续的，但操作系统偷偷拿把剪刀，把程序切成标准大小的“页”，然后随便塞进内存里任意位置的“框”里。
  • 优点： 彻底解决了“必须连续”的问题。内存利用率极高。

3. 路径 ③：段式存储管理 (Segmentation - 符合人类直觉)

• 逻辑上： 程序认为自己是由不同的“功能块”组成的（多连续逻辑地址空间/段表）。
  • 比如：主程序段、数据段、栈段。
• 物理上： 放入“分区”。
• 解释：
  • 程序员喜欢这种方式。因为我们可以说：“把我的代码段设为只读，把数据段设为可写”。
  • 但是，每个段在物理内存里还是要占一块连续的地盘，所以依然会有碎片问题。

4. 路径 ④：段页式存储管理 (Segmented Paging - 集大成者)

• 逻辑上： 先分段（符合程序员视角，便于管理和保护）。
• 物理上： 再分页（符合硬件视角，便于内存利用）。
• 解释：
  • 这是最强形态。
  • 先把程序按逻辑分成“段”（比如代码段）。
  • 再把这个“段”切碎成“页”，丢进物理内存的“页框”里。
  • 结果： 既有了分段的逻辑优势（保护、共享），又有了分页的物理优势（没有碎片）。

存储管理的功能

地址转换 (Address Translation)

• 核心： 将逻辑地址映射为物理地址（又称重定位）。
• 方式： 分为静态重定位（装入时确定，不可动）和动态重定位（运行时确定，灵活）。

分配与去配 (Allocation & Deallocation)

• 核心： 掌管内存的“借”与“还”。
• 动作： 进程装入时分配空间并记录；进程撤离时回收空间并去配。

存储保护 (Storage Protection)

• 核心： 确保进程互不干扰，防止越界访问。
• 规则： 自己的随便用，共享的按权限用，别人的严禁用。

内存共享 (Sharing)

• 核心： 允许多个进程共同使用同一块内存区域（如公共代码库）。
• 目的： 提高内存利用率，支持进程协作。

内存扩充 (Expansion)

• 核心： 利用磁盘空间“欺骗”程序，实现虚拟内存。
• 技术： 对换（整进整出）与虚拟技术（部分装入，按需调页）。

一句话总结： 操作系统通过转换地址让程序能跑，通过分配回收管理空间，通过保护防止打架，通过共享节省资源，通过扩充让小内存跑大程序。

连续分配管理方式 (Continuous Allocation)

核心定义

所谓“连续”，就是一个程序在物理内存中必须占据一块连在一起的地盘。

• 就像一群人去电影院看电影，必须买连座票，中间不能断开。

连续分配主要经历了三个阶段的进化，我们重点掌握后两个：

第一阶段：单一连续分配 (Single Continuous Allocation)

• 这是什么： 整个内存只有你（操作系统）和我（用户程序）两个人。
• 情况： 内存分为系统区和用户区。用户区一次只能跑一个程序。
• 结局： 这种方式太浪费了（如果你只有 10MB 程序，却占用了 8GB 内存），现代通用操作系统已经不用了。我们直接跳过。

第二阶段：固定分区分配 (Fixed Partitioning)

为了能多道程序并行，我们开始切蛋糕。

• 做法： 系统启动时，就把内存切成若干个固定大小的区域（分区）。这些格子的大小一旦切好，就不能变了。
• 两种切法：
  1. 分区大小相等： 比如全是 10MB 的格子。
  2. 分区大小不等： 有小的（4MB）、中等的（8MB）、大的（16MB），这样更灵活。
• 问题（致命伤）：内部碎片 (Internal Fragmentation)
  • 假设有一个分区是 10MB。
  • 你的程序只有 6MB。
  • 虽然程序装进去了，但剩下的 4MB 被锁在这个分区里，别的程序进不来，你也用不了。这就叫内部碎片（在分区内部浪费的空间）。

第三阶段：动态分区分配 (Dynamic Partitioning)

为了解决“内部碎片”，操作系统决定：现吃现切。

• 做法： 初始时内存是一整块。当程序 A 来了，它需要 5MB，我就切 5MB 给它；程序 B 来了要 10MB，我紧接着切 10MB 给它。
• 优点： 没有内部碎片！因为我是按需分配的，你需要多少我给多少。
• 问题（致命伤）：外部碎片 (External Fragmentation)
  • 随着时间推移，有的程序运行完走了（释放内存），内存里会留下一个个“坑”。
  • 比如：程序 B 走了，留下了 10MB 的空坑。
  • 这时来了一个 12MB 的新程序，它塞不进这个 10MB 的坑里。虽然内存里可能总共有 100MB 的空闲空间，但因为它们不连续（都是些碎小的坑），导致大程序跑不起来。这就叫外部碎片（在分区外部浪费的空间）。

“紧凑”技术 (Compaction)

操作系统不能看着这 16M 内存白白浪费。为了让 P5 跑起来，操作系统必须进行“内存搬家”，专业术语叫紧凑或拼接。

• 做法： 操作系统让现有的进程（P2, P4, P3）全部往上挪动，挤在一起。
• 效果：
  • 所有的空闲小坑（6M, 6M, 4M）会被“挤”到内存的最底部，汇合成一个 16M 的大坑。
  • 这时候，10M 的 P5 就可以舒舒服服地住进去了！

代价： “搬家”是非常耗时的。CPU 要暂停所有工作，疯狂地搬运数据（复制内存），这会严重拖慢电脑速度。这也解释了为什么以前的 Windows 98/XP 用久了要进行“磁盘碎片整理”（虽然那是磁盘，但原理类似，都是为了合并碎片）。

可变分区内存管理-分配算法

为什么需要分配算法？

因为“紧凑”（内存搬家）的代价太高了，会让电脑变卡。所以我们尽量通过聪明的分配算法，减少碎片的产生，不到万不得已不搬家。

以下是四种算法的详细解析：

1. 最先适应算法 (First Fit)

这是最简单、最自然的策略。

• 核心思想： 不管别的，按地址从低到高挨个找，找到第一个能装下的坑，就立刻分给它。
• 数据结构： 空闲分区表是按地址递增排列的。
• 优点：
  • 保留了大空间： 因为它总是先填低地址的坑，所以高地址的大片连续空间通常会被保留下来，有利于以后装入大作业。
• 缺点：
  • 忙闲不均： 低地址部分会被切得稀碎，用得很频繁；而查找时每次都从头开始，导致查找开销大，且低地址端充满了小碎片。

2. 下次适应算法 (Next Fit)

这是对“最先适应算法”的改良。

• 核心思想： 既然每次从头找太累，那就从上次分配结束的位置开始往下找。找到队尾如果还没找到，就绕回队头接着找（循环扫描）。
• 优点：
  • 速度快： 缩短了平均查找时间。
  • 均衡： 内存里的每个坑被选中的概率差不多，空间利用更均衡。
• 缺点（致命）：
  • 因为它把内存里的“大坑”都截断用了，导致缺乏大的连续空间。如果有大作业来了，可能反而找不到足够大的地盘了。

3. 最优适应算法 (Best Fit)

听名字觉得是最好的，其实通常是最烂的。

• 核心思想： 扫描整个内存，找到能装下该进程、且大小最接近（最小）的那个坑。
  • 比如你要 5MB，有一个 6MB 的坑和一个 20MB 的坑，它会选 6MB 的那个。
• 数据结构： 为了找得快，通常把空闲分区按大小递增顺序排列。
• 优点：
  • 它确实不想浪费大空间，尽量保留了大分区给大作业用。
• 缺点：
  • 制造碎片： 每次切完后，剩下来的那点空间（比如 6MB 切走 5MB，剩 1MB）实在太小了，谁也用不了。日积月累，内存里全是这种微小的、无法利用的外部碎片。

4. 最坏适应算法 (Worst Fit)

这是“最优适应”的反面。

• 核心思想： 每次都挑最大的那个坑给进程。
  • 比如你要 5MB，它偏偏要把那个 100MB 的大坑切给你。
• 数据结构： 空闲分区按大小递减顺序排列，这样查表时只要看第一个满不满足就行了。
• 优点：
  • 减少碎片： 切完剩下的一般还比较大（100MB 切走 5MB，剩 95MB），还可以继续给别的程序用。所以它对中小型作业非常有利。
• 缺点：
  • 大作业哭了： 最大的坑很快就被消耗掉了，真来了个超级大的程序，往往就没地方放了。

分页存储管理 (Paging Storage Management)

为什么要引入分页？

• 分区的痛： 程序必须完整地塞进连续的内存里。如果有 3 个 2MB 的小坑，想装一个 5MB 的程序，装不进去。
• 分页的药： 允许程序“打散”。把 5MB 的程序切成很多小块，分别塞进那 3 个 2MB 的坑里（甚至更小的坑），只要总空间够，就能跑。

核心思想： 逻辑上连续（程序看来是完整的），物理上不连续（内存里是散落的）。

三大概念

A. 页框 (Page Frame) —— 物理内存的“格子”

• 定义： 操作系统把物理内存切成一个个大小完全固定的块。
• 大小： 通常较小且是 2 的幂，比如 4KB（4096字节）。
• 编号： 从 0 开始编号，叫页框号或物理块号。
• 类比： 就像是一个巨大的药柜，里面全是大小一样的标准小抽屉。

B. 页面 (Page) —— 程序的“切片”

• 定义： 把用户的程序（逻辑地址空间）*也切成和页框*一模一样大小的块。
• 编号： 从 0 开始编号，叫页号。
• 类比： 你把药材（程序）切成标准的小方块，每一块刚好能塞进一个抽屉。

C. 页表 (Page Table) —— 寻宝图

• 定义：既然程序被切碎散落在内存的各个角落，CPU 怎么知道程序的“第 1 页”在哪个“抽屉”里？
• 我们需要一张映射表，这就是页表。
• 内容： 记录了 逻辑页号 -> 物理页框号 的对应关系。

分页是如何解决碎片问题的？

没有“外部碎片”：

• 因为内存被切成了标准的 4KB 格子，程序也是 4KB 的块。只要内存里有空闲的格子，程序就能塞进去，完全不用担心“坑太小”的问题。

只有微小的“内部碎片”：

• 产生原因： 程序的最后一部分可能填不满一页。
• 例子： 页面大小是 4KB。你的程序是 4.1KB。
  • 第 1 页（4KB）填满。
  • 第 2 页（0.1KB）只占了一点点，剩下的 3.9KB 就是浪费的。
• 结论： 这种浪费主要发生在程序的最后一页，平均只有半页大小，相比于固定分区的浪费，这简直可以忽略不计。

分页存储管理的地址转换

TLB（快表）

1. 核心痛点：为什么要引入快表？

请看图，它指出了一个严重的问题：

• 页表放在哪里？ 放在内存中。
• 这就导致了一个尴尬的后果： 每次 CPU 想读取一个数据，必须访问两次内存。
  1. 第一次访问： 去查内存里的页表，把逻辑地址翻译成物理地址。
  2. 第二次访问： 根据物理地址，真正去取数据。

2. 解决方案：TLB (快表)

为了解决“慢”的问题，科学家发明了 TLB (Translation Look-aside Buffer)，中文叫快表或联想寄存器。

• 它是什么？ CPU 内部的一种极其快速、但容量很小的高速缓存。
• 它存什么？ 它存放当前最常访问的那一小部分页表项（Page # 到 Frame # 的映射）。
• 原理： 利用程序的“局部性原理”。如果你刚看了第 5 页，你很可能马上又要看第 5 页。

升级后的比喻：

• 你在手边放了一张小纸条（TLB）。
• 每次找书前，先看小纸条。如果纸条上有位置信息（TLB 命中），直接去拿书，不用跑去查目录了！

3. 加入 TLB 后的工作流程

请看图 的流程图，这是现在的标准动作：

1. CPU 发出请求： 逻辑地址（页号 p）。
2. 先查 TLB（快）：
   • 情况 A：命中 (Hit)
     • 直接拿到物理块号。
     • 耗时： 仅需 1 次内存访问（取数据）。
   • 情况 B：未命中 (Miss)
     • 没办法，只能老老实实去访问内存里的页表（慢）。
     • 拿到块号后，顺手把这一项存进 TLB（以备下次用）。
     • 耗时： 2 次内存访问。

分页存储空间的分配与去配

安全性问题： 怎么防止进程去访问不属于它的内存？

之前学的页表，只是告诉 CPU “第 X 页在第 Y 块”。但这里有个漏洞：如果一个程序只有 5 页，但恶意（或错误）代码试图去访问“第 6 页”，会发生什么？

为了防止这种越界访问，操作系统在页表的每一行后面加了一个小尾巴，叫 “有效-无效位” (Valid-invalid bit)。

1. 机制详解

• v (valid)：有效。表示这一页是合法的，确实在物理内存里，且属于当前进程。
• i (invalid)：无效。表示这一页不属于该进程（或者该页还在磁盘上没调入内存）。
• 后果： 如果 CPU 试图访问一个标记为 i 的页面，硬件会立即触发一个异常 (Exception/Trap)，操作系统会终止该进程或进行处理。

2. 图中的数学例子（非常重要）

让我们拆解一下图中的计算题，看看它是怎么判定“第 6 页”是非法的：

• 前提条件：
  • 页大小 = 2KB (2¹¹ = 2048 字节)。
  • 这意味着地址的低 11 位是偏移量。
• 进程需求：
  • 进程实际使用的地址范围是 0 ~ 10468。
• 计算需要多少页：
  • $$\frac{10468}{2048} \approx 5.11$$
  • 这意味着填满了第 0, 1, 2, 3, 4 页，并且第 5 页占用了一点点（0.11的部分）。
  • 所以，总共需要 0~5 号页（共 6 个页）。
• 查看页表状态：
  • 你看右边的页表，页号 0~5 的状态位都是 v（允许访问）。
  • 页号 6, 7 的状态位是 i（禁止访问）。
  • 如果程序试图访问地址 12287（属于第 6 页），MMU 检查到是 ‘i’，直接报错拦截。

管理问题： 操作系统怎么快速知道哪些物理格子是空的？

操作系统手里握着几千几万个物理页框，当新程序来的时候，怎么快速找到哪里有空位？位图 (Bitmap) 是最常用的方法。

1. 核心思想

• 用一串二进制位 (0和1) 来代表物理内存的格局。
• 每一位 (bit) 对应一个 物理页框。
• 映射规则：
  • 第 1 个 bit 对应 第 1 个页框。
  • 第 2 个 bit 对应 第 2 个页框…以此类推。

2. 状态表示

• 1： 表示该页框被占用。

• 0： 表示该页框空闲。

  (注：有些系统可能反过来，但根据这张PPT的文字“找出为 0 的那些位”，说明这里 0 代表空闲)

3. 分配算法流程

当一个程序需要申请 3 个页框时：

1. 扫描： 操作系统扫描这个位图，寻找哪里有 “0”。
2. 计算： 比如发现第 5、6、8 位是 0。
3. 计算页框号：
   • 发现第 i 位是 0，那么对应的物理页框号就是 i（或者基于基址计算）。
4. 修改状态： 把这几位从 0 变成 1（标记为占用）。
5. 分配： 把算出来的物理页框号填到进程的页表里。

多级页表 (Multi-level Page Table)

1. 为什么要引入多级页表？(The Problem)

让我们做一个简单的数学计算：

• 在 32 位系统下，页面大小 4KB。

• 这意味着总共有 2²⁰ (约 100 万) 个页面。

• 如果每个页表项占 4 字节，那么一张完整的页表需要：

  100万 × 4B = 4MB

痛点：

1. 必须连续： 在单级页表中，这 4MB 的空间必须在物理内存中连续存放。
2. 难找： 在内存紧张时，很难找到一块完整的、连续的 4MB 空间给页表住。
3. 浪费： 很多程序其实只用了一点点内存，但为了维持结构，你不得不把这 100 万个坑位都建好（哪怕大部分是空的）。

解决方案：

把这 4MB 的大页表，也切成小块（页），散落在内存里！既然切碎了，就需要再建立一张表来管理这些碎块——这就是二级页表（页表的页表）。

2. 逻辑地址的重新划分

请看图，为了支持二级页表，逻辑地址被切得更碎了：

• 旧模式（单级）： 20位页号 (p) + 12位偏移 (d)。
• 新模式（二级）：
  • p₁ (10位)：一级页号（外层页号）。用来找“目录的目录”。
  • p₂ (10位)：二级页号（内层页号）。用来找“具体的页表”。
  • d (12位)：页内偏移。保持不变。

为什么是 10 位？

2¹⁰ = 1024。每个页表项 4 字节。

1024 × 4B = 4KB。

妙处： 这样切割后，每一张二级页表的大小刚好是一个页面 (4KB)！这让页表本身也可以完美地塞进普通的内存页框里。

地址变换过程 (The Walk)

请看图，这是一个“三步跳”的过程：

1. 第一跳（查目录）：
   • CPU 拿着 p₁，去查一级页表。
   • 得到结果：知道“这一段地址对应的二级页表”在内存的什么位置。
2. 第二跳（查页表）：
   • CPU 拿着 p₂，去刚才找到的那张二级页表里查。
   • 得到结果：终于拿到了真正的物理块号 (Frame #)。
3. 第三跳（取数据）：
   • 用物理块号 + 偏移量 d，去访问物理内存，拿到真正的数据。

优点：

• 离散存储页表： 页表不需要 4MB 连续空间了，可以打散放在各种角落。
• 节省空间： 如果一个程序只用了很小的内存，我们只需要建立“一级页表”和“少量二级页表”即可。其他的二级页表根本不用创建（或者可以留在磁盘上）。

缺点（如图片右上角文字所示）：

• 变慢了！
  • 单级页表：访存 2 次（查表+取数）。
  • 二级页表：访存 3 次（查一级+查二级+取数）。
  • 多级页表级数越多，访问越慢。

补救措施： 这就是为什么上一节讲的 TLB (快表) 极其重要！如果有 TLB，大部分时候我们直接能拿到结果，不需要走这漫长的三步跳。

分段存储管理

1. 为什么要分段？

请看图，这解释了分段的初衷：

• 程序员眼中的程序：
  • 程序员写代码时，不会认为程序是一堆 4KB 的碎片。
  • 我们认为程序是由不同的功能块组成的：比如 主程序 (main)、子程序 (subroutine)、栈 (stack)、变量数组 (array) 等。
• 分页的尴尬： 分页像碎纸机，可能把一个完整的函数切成两半，一半在第 1 页，一半在第 20 页。这让共享和保护变得很麻烦。
• 分段的解决： 保持逻辑完整。
  • 主程序 单独一段。
  • 栈 单独一段。
  • 数据表 单独一段。
  • 特点： 每个段的大小不固定（主程序可能 50KB，栈可能 1KB）。

黄金类比：

• 分页 像是把一本书的每一页撕下来，胡乱塞进一个个一样大的信封里。
• 分段 像是把书按“章”分开。第一章放一个文件夹，第二章放一个文件夹。有的章长，有的章短。

2. 逻辑地址的变化 (2D Address)

在分段管理中，地址不再是一维的线性的，而是二维的。

请看图 的底部：

• 逻辑地址 = 段号 (Segment Number) + 段内偏移 (Offset)
• 例子： “第 1 段 的 第 500 行”。

关键区别：

• 分页： 只要给出一个物理地址，机器自动切分。
• 分段： 用户（编译器）必须显式地指定“段号”和“段内偏移”。

3. 核心机制：段表 (Segment Table)

既然段的大小不固定，操作系统怎么管理呢？请看图。

我们需要一张段表，用来记录每个“章”在内存里的位置。因为每一章长度不一样，所以段表必须包含两列核心信息：

1. 段起始地址 (Base)： 这个段在物理内存是从哪里开始的？（比如从 6300 开始）。
2. 段长度 (Limit/Length)： 这个段到底有多大？（比如只有 400 大小）。
   • 注意：页表不需要记录“长度”，因为页表默认全是 4KB。但在分段中，这个长度至关重要！

4. 地址变换与保护 (The Translation & Safety)

这是分段管理最厉害的地方：越界保护。

我们模拟一次 CPU 访问（结合图 的数据）：

• 场景： CPU 要访问 段号 1，偏移量 500 的数据。

步骤：

1. 查表： 找到段表里的第 1 项。
2. 获取信息：
   • 基址 (Base) = 6300
   • 限长 (Length) = 400
3. 越界检查 (Critical Step)：
   • CPU 会拿你的偏移量 500 和 限长 400 比较。
   • 500 > 400，说明你试图访问这一段之外的地方！
   • 结果： 硬件直接拦截，抛出 “段错误” (Segmentation Fault)。这是编程时最常见的报错之一。
4. 正常情况： 如果偏移量是 100（小于 400），则物理地址 = 6300 + 100 = 6400。

虚拟内存 (Virtual Memory)

1. 痛点：实存管理的问题

请看图，传统的实存管理（Real Memory Management）有一个硬性规定：

• 必须全部装入： 作业（程序）如果要运行，必须把它的全部信息一次性装入内存。
• 后果：
  1. 大程序跑不了： 程序的体积受限于物理内存的大小。
  2. 浪费资源： 其实程序里很多代码是很少用到的（比如“异常处理代码”、“巨大的未填满的数组”）。把这些一辈子都不一定跑一次的代码一直放在昂贵的内存里，是极大的浪费。

2. 解决方案：虚拟内存

虚拟内存的核心思想就是“欺骗”。

• 核心动作：部分装入 (Partial Loading)。
  • 操作系统不再把整个程序塞进内存，而是只把当前立刻要用的那几页装进去，剩下的留在硬盘上。
  • 程序运行到哪里，就动态地把哪里的数据从硬盘“拉”进内存（请求调页）。
  • 如果内存满了，就把暂时不用的数据“踢”回硬盘（页面置换）。
• 效果：
  • 逻辑 > 物理： 给用户提供一个比物理主存大得多的“虚拟主存”。
  • 以小博大： 8GB 的物理内存，可以流畅运行 20GB 的游戏，甚至可以同时运行总共 100GB 的多个程序。

3. 理论基石：局部性原理

你可能会问：“这样频繁地在内存和硬盘之间倒腾数据，电脑不会卡死吗？” 答案是：通常不会。因为程序运行有一个神奇的规律，叫“局部性原理”。

请看图，它解释了为什么我们敢“只装入一部分”：

1. 时间局部性 (Temporal Locality)：
   • 现象： 如果一条指令被执行了，那么不久之后它很有可能再次被执行。
   • 原因： 程序里充满了大量的循环 (Loop)。一旦进入循环，CPU 就会盯着这几行代码反复跑，完全不需要访问其他页面的代码。
2. 空间局部性 (Spatial Locality)：
   • 现象： 如果一个存储单元被访问了，那么它附近的单元也很有可能马上被访问。
   • 原因： 指令通常是顺序执行的；数据通常是聚集成群的（比如数组、表）。

结论： 在一段较短的时间内，程序实际上只需要访问极小一部分内存就能正常工作。所以我们完全可以把剩下的 90% 扔在硬盘里睡觉，而不影响运行速度。

如何实现虚拟内存技术

要实现虚拟内存，不能使用我们最早学的“连续分配方式”（因为要频繁地把一大块程序搬进搬出，效率太低且不仅能保证连续空间）。

因此，虚拟内存必须建立在离散分配（非连续分配）的基础上。

根据课件，实现虚拟内存主要有以下三个流派和两个核心“新技能”：

1. 三种实现方式

其实就是把你之前学的“基本款”升级为“虚拟款”：

2. 两个新增的核心功能

这是“虚拟系统”和“普通系统”最本质的区别。为了实现“空手套白狼”，操作系统必须具备两项新能力：

A. 请求调页/调段功能 (Demand Paging/Segmentation)

• 动作： “缺了就拿”。
• 描述： 在程序执行过程中，当 CPU 发现要访问的数据不在内存时（缺页），操作系统负责把所需的信息从硬盘（外存）调入内存，然后让程序继续执行。

B. 页面置换/段置换功能 (Page/Segment Replacement)

• 动作： “满了就扔”。
• 描述： 当内存空间不够的时候，操作系统负责利用某种算法，把内存中暂时用不到的信息（页面或段）换出到硬盘上，腾出地方给新进来的页面用。

页式虚拟存储管理

1. 核心思想：按需调入 (Demand Paging)

• 启动时： 操作系统只把进程的第一页（或者极少量的几页）装入内存，然后就让 CPU 开始跑。
• 运行时：
  • CPU 执行着执行着，发现要访问的下一行代码在“第 5 页”。
  • 一查页表，发现第 5 页不在内存里。
  • 动作： 暂停程序，去硬盘把第 5 页抓进来，然后继续跑。
• 地位： 这是现代 OS 的主流存储管理技术。

2. 基础设施升级：扩充页表 (Expanded Page Table)

为了支持这种“有的在内存，有的在硬盘”的复杂情况，原来的页表（只记录页号->块号）已经不够用了。我们需要给页表加很多“状态栏”。

请看图，现在的页表项变得很宽，包含了以下关键信息：

1. 驻留标识 (Present/Resident bit)： 最重要的一位。
   • 1: 表示该页在内存中（可以直接访问）。
   • 0: 表示该页在磁盘上（需要触发中断去调入）。
2. 写回标志 (Dirty/Modify bit)：
   • 记录这一页在内存里有没有被修改过。
   • 作用： 当这一页要被踢出内存时，如果是“脏”的（被改过），必须写回硬盘保存；如果是“干净”的，直接扔掉就行（硬盘里有原版），省了一次磁盘 IO。
3. 引用标志 (Reference bit)：
   • 记录这一页最近有没有被访问过。
   • 作用： 给置换算法参考。最近刚被用过的，最好别踢它（LRU 算法的基础）。

3. 核心机制：缺页中断 (Page Fault)

当 CPU 想要访问一个“驻留标识为 0”（不在内存）的页面时，就会触发缺页中断。这是虚拟内存运转的“引擎”。

1. CPU 访问： 给出逻辑地址。
2. 硬件检查： 发现页表里这一项显示“不在内存”。
3. 产生中断： 硬件立刻产生缺页中断，CPU 暂停当前进程，把控制权交给操作系统。
4. OS 处理 (关键分支)：
   • 情况 A（内存有空位）：
     • 直接从磁盘找到该页，读入空闲的页框。
     • 修改页表（把驻留位置 1，填入块号）。
   • 情况 B（内存满了）：
     • 执行页面置换算法，挑一个倒霉蛋（淘汰页）踢出去。
     • 如果那个倒霉蛋被修改过，先把它写回磁盘。
     • 把腾出来的空位给新页面用。
5. 恢复执行： 操作系统更新完页表后，重新执行刚才那条导致中断的指令。这一次，CPU 就能顺利找到数据了。

虚存地址转换过程

第一阶段：启动与分流

1. 地址分解 (Step 1)

• 动作： CPU 发出指令，MMU（内存管理单元）截获逻辑地址，自动把它切成两半：页号 (p) 和 页内偏移 (d)。

2. 查快表 (Step 2)

• 动作： 以页号 p 为索引，先去查 CPU 内部的 快表 (TLB)。
• 耗时： t₁（非常短，纳秒级）。

第二阶段：三种可能的命运

命运一：快表命中 (TLB Hit) —— 极速模式

这是图中 (3) 的路径。

• 情况： 在 TLB 里直接找到了页号对应的物理块号。
• 结果：
  • 直接取出块号。
  • 拼接： 块号 + 偏移量 = 物理地址。
  • 访问数据： 去访问主存（耗时 t₂）。
• 总耗时： t₁(查TLB) + t₂(取数据)。

命运二：快表未命中，但页表命中 —— 普通模式

这是图中 (4) -> (5) 的路径。

• 情况： TLB 里没找到（Miss），但MMU 去查内存里的 页表 时，发现该页在内存中（驻留位为 1）。

• 动作：

  1. 从页表中读出物理块号。
  2. 关键动作：装入快表 (Load TLB)。为了下次能快点，把这一项复制到 TLB 里。
  3. 形成物理地址，访问数据。

• 总耗时： t₁(查TLB) + t₂(查页表) + t₂(取数据)。

  (比命运一多了一次访存的时间)

命运三：缺页中断 —— 龟速模式

这是图中 (6) -> (7) -> (8) 的路径（红色箭头）。

• 情况： TLB 没找到，查内存页表发现也不在内存中（驻留位为 0，失效）。
• 动作：
  1. Step (6) 缺页中断： MMU 发出信号，CPU 暂停，操作系统接管。
  2. Step (7) 调页： 操作系统去 辅助存储器 (磁盘) 里把这一页找出来，读入内存。
     • 注意：这一步耗时是 t₃，通常是毫秒级，比前两种慢几万倍。
  3. Step (8) 装入/改表： 数据读进内存后，操作系统更新 页表 和 快表，把状态改为“在内存”。
• 结局： 重启指令，这次就会走“命运一”或“命运二”了。

缺页中断率 (Page Fault Rate)

怎么衡量虚拟内存效率高不高？就看缺页中断率 (f)。

• 公式：

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

  • F: 缺页次数（去磁盘拿的次数）。
  • S: 成功在内存找到的次数。
  • 目标： 我们希望 f 无限接近于 0。

• 影响 f 的四大因素：

  1. 内存页框数： 给进程分的“房间”越多，缺页率越低。
  2. 页面大小： 页面越大，缺页率通常越低（因为一次拉进来更多数据），但浪费也可能变大。
  3. 页面替换算法： 算法越聪明（踢得越准），缺页率越低。
  4. 程序特性： 这不仅是 OS 的事，也是程序员的事！

页面调度算法

最佳页面调度算法(OPT, OPTimal replacement)

先进先出页面调度算法(FIFO, First-In First-Out replacement)

Belady异常

为什么会发生这种事？

Belady 异常的根本原因在于 FIFO 算法的“无脑”。

• FIFO 的逻辑： 只看进入内存的时间，谁来得早谁滚蛋。
• 问题所在： 它完全不考虑页面的使用频率或访问模式。
  • 在上面的 4 页框例子中，4 和 3 是经常要被访问的热门页面。
  • 但是因为它们进来得早，FIFO 总是优先把它们踢出去。
  • 当页框变多时，页面的驻留时间变长了，队列的结构变了，导致原本能“巧合”命中的页面（比如在3页框时，踢出的顺序刚好避开了马上要用的页），在4页框时反而被“精准”地踢出去了。

最近最少使用页面调度算法(LRU, Least Recently Used replacement)

最不常用页面调度算法(LFU, least frequently used)

时钟页面调度算法(Clock, Clock policy replacement)

1. 核心道具 (The Setup)

要玩转这个算法，需要三个关键道具：

1. 环形队列 (Circular Queue)：
   • 把内存里的所有页面首尾相连，排成一个圆圈，就像钟面一样。
2. 表针 (Pointer)：
   • 有一个指针，指向当前要检查的那个页面（下一号淘汰候选人）。
3. 引用标志位 (Reference/Use Bit)：
   • 每个页面都有一个标志位。
   • 1 = 最近被访问过（免死金牌）。
   • 0 = 最近没被访问（可以杀）。

2. 算法规则：给一次“改过自新”的机会

Clock 算法的核心逻辑就是“二次机会” (Second Chance)。

当内存满了，需要踢人时，指针开始顺时针扫描：

• 情况 A：遇到标志位是 1 的页面
  • 动作： 操作系统心软了。它把标志位改为 0（没收免死金牌），然后指针移向下一页。
  • 潜台词： “我看你最近刚被用过，这次先不杀你，但我把你的牌子没收了。如果下次我转回来你还没被访问，那你就在劫难逃了。”
• 情况 B：遇到标志位是 0 的页面
  • 动作： 操作系统不客气了。直接淘汰这个页面！
  • 后续： 把新页面装进这个坑位，把标志位置为 1，指针移向下一页。

段式虚拟存储管理

如果有需要再学

设备管理

设备控制方式

为什么要有设备控制方式

1. 巨大的速度鸿沟 (The Speed Gap)

这是最根本的原因。

• CPU：是电子设备，运算速度以纳秒 (ns) 计，一秒钟能执行几十亿次指令。
• I/O设备：大多包含机械部件（如硬盘磁头转动、打印机喷墨），速度以毫秒 (ms) 甚至秒计。

差距有多大？ 如果把 CPU 比作一列高铁（时速 300公里），那 I/O 设备就像是一只蜗牛。 如果没有优化的“控制方式”（比如让 CPU 傻等的轮询方式），就相当于让高铁停下来等蜗牛爬过铁轨。这简直是暴殄天物，极大地浪费了昂贵的 CPU 资源。

所以，设备控制方式的演进，本质上就是为了不让高铁等蜗牛。

2. 实现“并行操作” (Parallelism)

操作系统的核心目标之一是效率。我们希望计算机能同时做多件事。

• 没有好的控制方式时：CPU 必须亲自指挥设备每一个动作。CPU 在忙 I/O 的时候，就不能做计算；做计算的时候，就不能管 I/O。这是串行的。
• 有了好的控制方式（如 DMA、通道）：
  • CPU 说：“你去把电影拷贝一下。”（发指令）
  • CPU 转头去运行游戏逻辑。（做计算）
  • 设备控制器自己在旁边慢慢拷贝电影。（做 I/O）

这就是CPU 与设备的并行。只有通过先进的设备控制方式，才能把 CPU 从繁琐的搬运工作中解放出来，让它去处理更有价值的逻辑运算。

3. 屏蔽设备的复杂性 (Abstraction)

世界上的设备千奇百怪：鼠标、键盘、显卡、网卡、打印机、VR眼镜……

• 它们的物理原理完全不同。
• 它们的数据格式完全不同。

如果让 CPU 直接去控制每一个物理细节（比如控制硬盘电机转几圈、控制打印机喷头往哪喷），CPU 的指令集会变得无比复杂，且操作系统无法通用。

设备控制方式（配合硬件控制器）起到了一层“翻译”和“管家”的作用：

• CPU 只需要下达统一的命令（读、写）。
• 具体的脏活累活（如何控制电压、如何校验数据、如何按顺序传输）交给设备控制器和控制逻辑（如 DMA 控制器）去完成。

四者之间差异在于：CPU和设备并行工作的方式和程度不同。

轮询（Polling）

流程解析：

1. 发出命令：CPU 告诉设备（控制器）“我要读数据”。
2. 读状态：CPU 紧接着去读设备的状态寄存器。
3. 检查状态（关键点）：
   • 如果设备“未就绪”（还在忙着准备数据），CPU 顺着红色箭头跳回去，再次读取状态。
   • CPU 会一直在“读状态 -> 检查 -> 未就绪 -> 读状态”这个圈里打转。
4. 读写数据：只有当设备终于显示“就绪”了，CPU 才会跳出循环，亲自把数据读进来。

核心特点：CPU 全程陪跑 (CPU 全程参与)

忙等 (Busy Waiting)：

• 这就是上面说的那个“死循环”。在设备准备数据的这段时间（对于 CPU 来说极其漫长），CPU 没有去干别的更有意义的事，而是像个复读机一样一直问“好了没？”。
• 结果：CPU 的利用率被严重拉低。

串行工作：

• PPT 文字提到：“在设备接受 I/O 命令之前处理器不能执行其他操作”。
• 这意味着 计算任务 和 I/O 任务 是完全串行的（排队做）。CPU 不能在设备忙的时候去算别的题。

中断驱动方式 (Interrupt-Driven I/O)

当设备准备好了（状态变为“就绪”），控制器会向 CPU 发送一个电信号，这个信号就叫中断。

CPU 的反应：

1. 收到信号，暂停当前正在做的工作（保存现场）。
2. 跳到 “中断处理程序”（流程图中的黄色框）。
3. 传送数据：CPU 亲自把数据从设备搬运到内存。
4. 恢复：搬运完后，CPU 回到刚才暂停的地方继续工作。

直接存储器访问（DMA, Direct Memory Access）

图展示了 DMA 模块的内部结构，这解释了它是如何独立工作的：

• 地址寄存器：记住了数据要搬到内存的哪个位置。
• 数据计数：记住了还有多少数据要搬。
• 控制逻辑：负责指挥总线进行读写。
• 关键点：CPU 一旦把这些寄存器填好，DMA 就拥有了工作的全部信息，不再需要 CPU 指导。

CPU -> DMA（下达命令）：

• CPU 告诉 DMA：“把硬盘里这 1MB 数据搬到内存地址 X。”

继续执行后续指令（红色虚线）：

• 关键时刻：CPU 下完命令直接走人，去处理其他进程。
• 与此同时，DMA 控制器接管总线，一车一车地往内存搬数据。这是真正的并行！

中断（最后一步）：

• 只有当这 1MB 数据全部搬完了，DMA 才会发一个中断信号告诉 CPU：“老板，活干完了。”

什么是“周期窃取”？

“DMA 和 CPU 同时通过总线访问内存，CPU 会把总线的占有权让给 DMA 一个/几个主存周期”。

形象理解：

• 总线 (Bus) 就像是一条独木桥。内存是桥对面的仓库。
• CPU 是一个一直在过桥搬东西的人。
• DMA 是另一个也要过桥搬东西的人。
• “周期窃取”：当 DMA 需要搬运一个数据字时，它不会把 CPU 彻底赶走，而是趁着 CPU 正在思考（译码）或者还没上桥的间隙，“偷” 用一下这个桥（总线周期），快速搬运一个字，然后立马把桥还给 CPU。

图中的方框（取指令、译码、取操作数…）代表 CPU 执行一条指令的各个微步骤。

中断断点 (最右侧)：请看最右边的箭头。中断是非常“讲礼貌”的。它必须等到 CPU 把当前这条指令完全执行完（存结果之后），才会去响应中断。

DMA 断点 (中间的箭头)：请看指向“译码”和“取操作数”之间的那个箭头。DMA 是“急脾气”。它不需要等指令执行完。只要 CPU 当前这个微操作（比如译码）不占用总线，DMA 就可以见缝插针地插入进来，偷一个周期传数据。

结论：DMA 的响应速度比中断快得多，因为它不需要等指令结束。

为什么“窃取”不会严重拖慢 CPU？

Cache 的功劳：PPT 最后一行提到“CPU 大部分情况下与 Cache 进行数据交换”。CPU 也就是在这一瞬间不能访问主存（内存），但它依然可以访问Cache（高速缓存）。只要 Cache 里有数据，CPU 就算没了总线也能继续干活，完全感觉不到 DMA 在偷东西。

不连续性：DMA 只是偶尔偷一个周期，而不是长时间霸占，所以对 CPU 的宏观影响很小。

三种方式对比

• ① 轮询方式: CPU需要主动等待设备就绪，并且全程参与内存数据的交换。
• ② 中断方式: CPU无需主动等待设备就绪。当设备准备好后，会向CPU发送一个中断信号，CPU响应中断后再参与内存数据交换。
• ③ DMA方式: CPU只在I/O操作开始前和结束后参与（例如，初始化DMA控制器），在实际的数据传输过程中，由DMA控制器直接在内存和设备间搬运数据，CPU完全不参与主存数据交换。

从轮询到中断再到DMA，CPU的效率越来越高，它能更早地从I/O等待中解放出来去执行其他任务，从而提高了系统的并行处理能力。然而，这种并行仅限于物理层面的I/O操作，即CPU和I/O设备可以同时工作，而不是指CPU内部或软件层面的并行计算。

通道控制方式 (Channel Control)

1. 核心定义：什么是“通道”？

• 别名：它又被称为 I/O 处理器 (I/O Processor)。
• 地位：它不再是一个简单的硬件控制器，而是一个“弱智版 CPU”。
• 能力：它拥有执行逻辑独立 I/O 任务的能力。这意味着它不仅仅能“搬运”，还能做简单的“决策”（比如：先读这个，再写那个，如果错了重试）。

2. 核心机制：通道程序 & 四级连接

这里有两个关键概念需要理解：

A. 通道程序 (Channel Program)

PPT 提到，处理器不再执行具体的 I/O 指令，而是“在主存中组织通道程序”。

• DMA 方式：CPU 给的是参数（源地址、目的地址、数据量）。
• 通道方式：CPU 给的是一段代码（通道程序）。
  • 比喻：
    • DMA：老板说“把这堆砖搬到后院”。
    • 通道：老板写了一张任务清单：“1. 先把砖搬到后院；2. 然后去买水泥；3. 最后把墙砌好。” 通道拿着这张清单，自己去执行一系列复杂的动作，不需要老板再插手。

B. 四级连接 (Four-level Connection)

PPT 中提到了 “处理器、通道、控制器、设备” 的四级连接。

• 这是一个层级管理结构：
  • CPU 指挥 通道。
  • 通道 指挥 设备控制器。
  • 设备控制器 控制 设备。
• 目的：一个通道可以控制多台设备，大大节省了 CPU 的接口资源。

3. 工作流程：高度并行 (High Parallelism)

详细展示了工作步骤，这里有几个考试常考的缩写：

1. CPU 启动：
   • CPU 遇到 I/O 任务。
   • OS 组织好通道程序，把这个程序的地址放在 CAW (Channel Address Word，通道地址字) 中。
   • CPU 启动通道，然后立即走人（去干别的事）。
2. 通道执行：
   • 通道从 CAW 里拿到清单（通道程序），开始指挥设备干活。
   • 此时，CPU 和 通道 真正实现了“高度并行”。
3. 结束汇报：
   • 活干完了，通道发出中断。
   • CPU 响应中断，从 CSW (Channel Status Word，通道状态字) 中读取执行情况（比如是成功了还是出错了）。

总线与I/O

什么是总线

从慢吞吞的键盘到快如闪电的显卡，它们都需要和 CPU 或内存交换数据。总线就是它们共同行走的通道。

想象计算机的主板是一个繁忙的城市。

• CPU、内存、硬盘、网卡 就是城市里的建筑物。
• 总线 就是连接这些建筑物的主干道。
• 数据 就是路上跑的车辆。

总线的三大组成部分：

1. 数据总线 (Data Bus) —— 运货车
   • 作用：用来传输实际的数据（比如你的文档内容、游戏画面）。
   • 特点：是双向的（能发能收）。路越宽（比如 32位、64位），一次能拉的货就越多。
2. 地址总线 (Address Bus) —— 导航员
   • 作用：用来告诉大家“我要去哪里”。比如 CPU 要读内存，必须先通过地址总线广播：“我要找 0x0012 号房间的数据”。
   • 特点：通常是单向的（由 CPU 发出）。
3. 控制总线 (Control Bus) —— 红绿灯/交警
   • 作用：用来指挥交通。比如发送“读”、“写”、“中断”或“请求占用总线”的信号。
   • 关联：刚才我们学的 “DMA 周期窃取”，其实就是 DMA 通过控制总线向 CPU 申请：“把路权借我用一下”。

解决 I/O 速度不匹配问题

这里的“不匹配”体现在两个维度：

• I/O 和 CPU 的不匹配：CPU 是光速运行的，而 I/O 设备相对较慢。
• 各设备之间的不匹配：这是这张图的重点。键盘和显卡虽然都是 I/O 设备，但它们的速度简直是云泥之别。

总线概念结构

单总线结构模型 (Single Bus Structure Model)

• 一条总线：中间那根橙色的双向大箭头。
• 全员接入：CPU、主存（内存） 和所有的 I/O 模块 都直接挂在这同一根线上。

这意味着什么？ 这意味着 CPU 想和内存说话，要走这条路；硬盘想把数据传给内存，也要走这条路。大家共享这一条通信通道。

优点：简单粗暴

1. 结构简单：硬件设计非常容易，成本低。
2. 易于扩充：这是最大的好处。如果你想加一台打印机，只需要把它“挂”在总线上就行，不需要改动 CPU 或内存的架构。就像在路边盖新房子一样容易。

缺点：致命的“堵车”

这种设计在早期计算机中很流行，但随着设备越来越多，它的弊端完全暴露出来：

• 共用总线导致压力大：
  • 因为只有一条路，同一时刻只能有一组对话。如果硬盘正在传电影，CPU 就不能读内存，必须干等。这就构成了瓶颈。
• 传输时延长：
  • 设备多了，大家都要申请路权，排队时间自然变长。
• 最痛的点：慢速外设占用带宽多：
  • 这是单总线最大的硬伤。
  • 比喻：想象这是一条单车道高速公路。如果前面有一辆拖拉机（慢速 I/O 设备）在慢慢开，后面性能再好的法拉利（CPU/内存）也得跟在屁股后面慢慢爬。
  • 这就导致了高速设备的性能被低速设备严重拖累。

三级总线模型 (Three-level Bus Model)

第一级：局部总线 (Local Bus) —— “VIP 专用通道”

• 位置：最上方，连接 CPU 和 Cache (高速缓存)。
• 作用：这是系统中最快的一条路。
• 意义：CPU 和 Cache 之间的交互极其频繁且速度极快。把它们单独划在这个“小圈子”里，让 CPU 能全速运行，完全不受外界打扰。

第二级：主存总线 (System Bus) —— “城市主干道”

• 位置：中间层，连接 主存 (Main Memory)、Cache 和 局部 I/O 控制器。
• 作用：负责内存数据的吞吐。
• 意义：当 Cache 没命中时，需要从主存调数据，就走这条路。它比局部总线慢一点，但依然很快。

第三级：扩展总线 (Expansion Bus) —— “社区辅路”

• 位置：最下方，连接各种 I/O 设备（如 LAN网卡、SCSI设备、打印机等）。
• 作用：专门用来挂载各种速度参差不齐的外设。
• 关键组件：扩展总线接口 (Expansion Bus Interface)。它是连接“主干道”和“辅路”的立交桥/收费站。它不仅负责传递数据，还起到缓冲的作用，防止慢速设备的信号干扰高速总线。

优点：各行其道

分流 (Isolation)：

• “主存与 I/O 之间的数据传送” 和 “处理器的内存活动” 被分离开了。
• 简单说：硬盘往内存传数据（走扩展总线 -> 主存总线）的时候，CPU 依然可以在局部总线上和 Cache 玩得很开心，互不影响。

扩展性强：

• “支持更多的 I/O 设备”。因为有了扩展总线这一层，你可以挂很多慢速设备，而不会增加主存总线的负载（电容负载）。

缺点：木桶效应

PPT 也提到了一个缺点：“不适用于 I/O 设备数据速率相差太大的情形”。

• 解读：你看最下面的“扩展总线”，上面既挂了高速的 LAN (网卡)、SCSI (高速硬盘接口)，又可能挂慢速的 字符设备 (键盘/鼠标)。
• 如果所有外设都挤在这一根扩展总线上，高速设备（如千兆网卡）可能会觉得这条路太慢，或者被慢速设备抢占时隙，导致性能发挥不出来。
• 解决思路：这就是为什么现代电脑（如你现在的 PC）其实演进到了更高级的结构（如 桥接芯片组架构，分为北桥和南桥，或者现在的 PCH），把高速 I/O (PCIe) 和低速 I/O (USB) 进一步分开。

南北桥架构” (Northbridge and Southbridge Architecture)

核心理念：快慢彻底分家

PPT 顶部的文字点出了核心思路：“通过存储总线、PCI总线、E(ISA)总线分别连接主存、高速I/O设备和低速I/O设备”。

• 为什么要分南北？
  • 有些设备太快（内存、显卡），必须贴着 CPU 跑。
  • 有些设备太慢（鼠标、键盘），离 CPU 远点没关系。
  • 于是，主板芯片组被劈成了两半：北桥负责快，南桥负责慢

北桥 (Northbridge) —— 速度担当

地位：它是离 CPU 最近的芯片（通常在主板上方，故称北桥）。

• 别名：PPT 中标注为 “主存控制器” (Memory Controller)。
• 连接对象（贵族圈）：
  1. CPU：通过“处理器总线”直接连接，带宽最高。
  2. 主存 (RAM)：通过“存储总线”连接。这是北桥最重要的任务——管理内存读写。
  3. 高速 I/O 设备：PPT 中展示了 图形设备 (显卡)、SCSI (服务器硬盘)、LAN (网卡) 挂接在 PCI 总线 上。虽然 PCI 总线在物理上通常由南桥管理或作为南北桥的桥梁，但逻辑上它们属于高速区，需要通过北桥与 CPU 高速交换数据。

南桥 (Southbridge) —— 管家担当

地位：离 CPU 较远（通常在主板下方，故称南桥）。

• 别名：PPT 中标注为 “I/O 控制器”。
• 连接对象（平民圈）：
  1. 低速 I/O 设备：PPT 下方展示的 COM 口、鼠标、键盘。
  2. 慢速总线：这些设备挂在 E(ISA) 总线 上。这是一种非常古老且缓慢的总线标准。
• 职责：南桥负责处理这些琐碎、慢速的输入输出，整理好之后，再通过“桥间接口”统一汇报给北桥。

关键接口：桥间接口 (Hub Interface)

请看图中连接北桥和南桥的那根竖线——“桥间接口”。

• 这是连接“CBD”和“郊区”的高速公路。
• 所有的鼠标点击、键盘输入，都要先汇聚到南桥，通过这个接口传给北桥，最后才能到达 CPU。

北桥：负责 CPU总线、存储总线（内存）以及 PCI总线（高速 I/O，如显卡、网卡）。

南桥：负责 E(ISA)总线（慢速 I/O，如键盘、鼠标），并通过桥间接口与北桥通信。

优点：支持不同速率 (Heterogeneity)

PPT 明确指出了这种架构的优点：“可以支持不同数据速率的 I/O 设备”。

• 各司其职：
  • CPU 想读内存，直接找北桥，路径极短，速度极快。
  • CPU 想读鼠标，指令传给南桥，南桥慢慢去读，不会占用北桥的高速通道。
• 消除瓶颈：慢速的 ISA 设备再多，也不会拖慢 CPU 访问内存的速度，因为它们在物理上被隔绝在南桥下面了。

第一梯队（最快）：北桥负责

• 不仅仅是内存：你说得对，北桥不仅连接主存，还连接了 图形设备 (显卡)。显卡是 I/O 设备中对速度要求最高的（比如打游戏时的数据吞吐量极大），所以它被提拔到了“北桥”这个 VIP 区域，直接和 CPU、内存享受高速通道。

第二梯队（较快）：PCI 总线

• LAN (网卡) 和 SCSI (硬盘) 挂在 PCI 总线 上。这是一条高速公路，专门给这些吞吐量大的设备跑。

第三梯队（慢速）：南桥负责

• 鼠标、键盘 被赶到了最下面的 E(ISA) 总线，由 南桥 统一管理。
• 南桥像一个过滤器，把这些慢速设备的琐碎请求整理好，再通过中间的接口汇报上去。

I/O 软件的层次结构

第 1 层：用户空间的 I/O 软件 (User-Space I/O Software)

“我要打印一份文件”

• 位置：最顶层，直接和用户打交道。
• 是谁：你写的 C 语言代码（printf, scanf），或者具体的应用程序（Word, 浏览器）。
• 核心功能：
  • I/O 系统调用：发起请求。
  • SPOOLing：比如你点打印时，电脑没卡死，而是把任务放到了后台队列里，这就是 SPOOLing 技术（后面会细讲）。
  • I/O 格式化：比如把你的数字 100 转换成字符 '1', '0', '0' 显示在屏幕上。
• 特点：它根本不知道硬盘是圆的还是方的，它只知道“我要读/写数据”。

第 2 层：独立于设备的 I/O 软件 (Device-Independent I/O Software)

“好的，不管你是存到 U 盘还是硬盘，逻辑都一样”

• 位置：第二层，这是操作系统的核心通逻辑。
• 核心功能：
  • 设备的命名：把物理设备映射成逻辑名（比如 /dev/sda 或 C: 盘）。
  • 设备保护：检查你有没有权限读这个文件。
  • 缓冲 (Buffering)：非常关键！为了解决速度差异，数据会先暂存在这里。
  • 设备分配与释放：决定这个打印机现在归谁用。
• 特点：这一层抹平了硬件差异。对于它来说，所有设备都是“文件”。

第 3 层：I/O 设备驱动程序 (Device Drivers)

“收到，正在指挥西部数据硬盘的磁头移动”

• 位置：第三层，这是最懂硬件的软件。
• 核心功能：
  • 翻译：把上层的“读第 5 个块”这种抽象命令，翻译成具体的硬件指令（如“设置寄存器 X 为 1，向端口 Y 发送数据”）。
  • 检查状态：看设备是不是忙，是不是出错了。
• 特点：每一类设备都有专门的驱动。显卡有显卡驱动，网卡有网卡驱动。它是操作系统和硬件之间的“翻译官”。

第 4 层：I/O 中断处理程序 (Interrupt Handlers)

“老板，活干完了！(叫醒 CPU)”

• 位置：最底层软件，紧贴硬件。
• 核心功能：
  • 处理中断：当硬件干完活（比如 DMA 搬运完了），会发个电信号触发中断，这层软件负责响应。
  • 唤醒驱动：告诉上面的驱动程序“数据到了，你可以继续往下跑了”。
• 特点：它是在硬件事件发生后被动触发的“急救员”。

总结：数据流动的全过程

想象你在 Word 里点击“保存”（写硬盘）：

1. 用户层：Word 调用系统函数 write()。
2. 独立层：OS 检查权限，分配缓存，找到文件对应的逻辑地址。
3. 驱动层：驱动程序把逻辑地址算出具体的磁道和扇区，向硬盘控制器发指令。
4. 硬件层：硬盘疯狂转动，磁头写入数据。
5. 中断层：硬盘写完，发中断。中断程序告诉驱动“搞定”，驱动告诉上层“搞定”，最后 Word 提示你“保存成功”。

I/O 缓冲区

1. 核心定义：什么是 I/O 缓冲区？

给出了明确定义：“在内存中开辟的存储区，专门用于临时存放 I/O 操作的数据”。

• 通俗理解：
  • 没有缓冲：CPU 直接伸手向硬盘要数据，硬盘没给，CPU 就手悬在半空等着。
  • 有了缓冲：在内存里放一个“快递柜”。硬盘把数据慢慢填进柜子，填满了通知 CPU 来取。CPU 取数据的时候，硬盘可以继续往下一个柜子里填。

2. 为什么要引入缓冲？（五大目的）

PPT 左侧详细列出了目的，每一条都直击痛点：

1. 解决速度不匹配：这是最核心的。CPU 是跑车，I/O 是拖拉机。缓冲让跑车不用停车等拖拉机。
2. 协调记录大小不一致：
   • 逻辑记录：你的代码可能想读一行字（10个字节）。
   • 物理记录：硬盘一次只能读一个扇区（4KB）。
   • 缓冲的作用：把 4KB 读到缓冲区，然后把其中的 10个字节 拿给你的程序。
3. 提高并行性：CPU 算它的，设备传它的，互不干扰。
4. 减少中断次数：
   • 如果没有缓冲，每来一个字符就要中断 CPU 一次。
   • 有了缓冲，填满一整个缓冲区（比如 4KB）才中断一次。CPU 舒服多了。
5. 放宽响应时间要求：数据来了先进缓冲区待着，CPU 忙完手头的事再来取，不用秒回。

3. 缓冲技术的进化史（看右边的图）

PPT 右侧的四张小图展示了缓冲技术是如何一步步变强的。

(a) 无缓冲 (No Buffering)

• 状态：CPU 和设备直接对接。
• 后果：完全串行。设备忙，CPU 就要等；CPU 忙，设备就要停。效率最低。

1. 三个关键变量 (T, M, C)

首先，你要搞清楚这三个字母代表什么，它们是一个数据块处理流程的三个步骤：

• T (Time for Input)：输入时间。从磁盘把一块数据读到缓冲区。这是 I/O 设备的活。
• M (Time for Move)：传送时间。系统把数据从缓冲区“搬”到用户的内存区。这是内存复制的操作。
• C (Time for Computation)：计算时间。CPU 对这块数据进行处理。这是 CPU 的活。

核心逻辑：

• 没有缓冲时：这三步是串行的，总时间 = T + C。
• 有了单缓冲：T（I/O） 和 C（CPU计算） 可以并行了（同时进行）。

2. 两种场景分析

PPT 下方展示了两种可能的情况，取决于“谁更慢”。

情况一：T > C (I/O 慢，CPU 快)

这是左边的图。

• 场景：硬盘读得很慢 (T 长)，CPU 算得很快 (C 短)。
• 过程：
  • CPU 很快算完了上一块数据 (C)，但是下一块数据还没传完 (T)。
  • 结果：CPU 必须等待硬盘。
• 瓶颈：在于 T。
• 处理一块数据的总时间：T + M。
  • (注：虽然也有 C，但 C 包含在 T 的时间段里并行做完了，没有增加额外耗时，所以只算长的那段 T，加上必须要做的搬运 M。)

情况二：T < C (I/O 快，CPU 慢)

这是右边的图。

• 场景：硬盘读得飞快 (T 短)，但 CPU 计算很复杂，算得很慢 (C 长)。
• 过程：
  • 硬盘很快把缓冲区填满了 (T)，但是 CPU 还在算上一块 (C)，没空来取。
  • 结果：硬盘必须等待 CPU 腾出缓冲区。
• 瓶颈：在于 C。
• 处理一块数据的总时间：C + M。

(b) 单缓冲 (Single Buffer)

• 原理：操作系统在内存里建一个仓库。
  • 设备 -> 仓库：设备把数据搬进仓库（CPU 此时可以干别的）。
  • 仓库 -> 用户进程：仓库满了，CPU 把数据从仓库挪走。
• 局限：不能同时进出。当 CPU 正在从仓库取货时，设备不能往里面送货（因为只有一个门），设备必须暂停等待仓库腾空。

(c) 双缓冲 (Double Buffering) —— 也叫“乒乓缓冲”

• 原理：建两个仓库（1号和2号）。
• 玩法：
  • 设备往 1号 装货。
  • 与此同时，CPU 从 2号 取货。
  • 大家都不用停！等 1号满了、2号空了，交换一下。
• 优点：实现了极致的并行。除非 CPU 处理太慢或者设备太慢导致一方严重积压，否则数据流几乎是连续的。

答案是：Max(C + M, T)

这里的逻辑是：

• T (Input)：设备往“缓冲区1”里送货的时间。
• C + M (Compute + Move)：CPU 从“缓冲区2”取货 (M) 并处理 (C) 的时间。
• 因为有两个缓冲区，这两件事是完全并行的。谁慢（时间长），整体速度就取决于谁。

(d) 多缓冲/循环缓冲 (Circular Buffering)

• 原理：建很多个仓库，连成一个圈。
• 场景：适用于阵发性的大量数据传输（比如看高清视频，网速忽快忽慢）。
• 玩法：
  • 设备拼命往空仓库里填（生产者）。
  • CPU 拼命追着满仓库取（消费者）。
  • 只要圈里还有空位，设备就不用停；只要圈里还有满位，CPU 就不用停。这是弹性最大的方案。

独占型外围设备的分配

设备独立性 (Device Independence)

1. 核心痛点：如果把代码写死会怎样？

以前的做法 (物理设备绑定)：

• 你在写程序时，如果直接写死：“我要用编号为 001 的那台惠普打印机”。
• 后果：如果这台 001 号打印机坏了，或者被搬走了，你的程序就直接报错崩溃了，即使旁边还有一台一模一样的 002 号打印机空闲着，你也用不了。

总结：绑定具体物理设备虽然简单，但灵活性极差，一坏就瘫痪。

2. 解决方案：引入“逻辑设备”

为了解决这个问题，操作系统引入了设备独立性。

• 核心思想：
  • 用户（程序员）：只负责说“我要用一台打印机”（这就是逻辑设备）。
  • 操作系统：负责去仓库看哪台打印机是好的、空闲的（比如 003 号），然后把它分配给你（这就是物理设备）。
• PPT 定义：用户不指定物理设备，而是指定逻辑设备，使得用户作业和物理设备分离开来。

3. 实现机制：映射表 (The Mapping Table)

操作系统是怎么把你的“空头支票”（逻辑设备）兑现成“真金白银”（物理设备）的呢？

• PPT 中间红字提到：系统需要提供逻辑设备名到物理设备名的映射表。
• 类比：
  • 你打车时输入“我要去机场”（逻辑请求）。
  • 打车软件（操作系统）查一下数据库（映射表），指派了“京B·12345”这辆车（物理设备）给你。
  • 这一层映射关系，就是设备独立性的核心。

4. 三大优点 (考试必考)

代码不用改 (应用程序与具体物理设备无关)：

• 你换了个新鼠标，不需要去改你的游戏代码。因为游戏只调用“逻辑鼠标”，操作系统会自动把新鼠标映射上去。系统增减或变更设备时不需要修改源程序。

系统更可靠 (易于应对故障)：

• 如果打印机 A 坏了，操作系统自动把任务导向打印机 B。用户根本感觉不到故障的存在。

资源分配更灵活：

• 谁闲着就给谁用，实现了多道程序设计，不再出现“旱的旱死，涝的涝死”的情况。

设备分配的数据结构

共享型外围设备的驱动

1. 物理组件：搭建“多层蛋糕”

请看右上角的 3D 图：

• 盘片 (Platters)：磁盘里不只有一张盘，而是有多张盘片叠在一起，穿在中间的轴上高速旋转。
• 盘面 (Surfaces)：每个盘片就像硬币一样，有正反两面。通常每一面都可以存数据，所以 2 个盘片就有 4 个盘面。
• 磁头 (Heads)：看那个像梳子一样的移动臂，它的每一个齿尖上都有一个磁头。
  • 关键点：所有磁头是共进退的。移动臂一动，所有磁头一起动。

2. 数据划分：画圈圈

请看右下角的平面图：

• 磁道 (Track)：盘面被划分成无数个同心圆，每一个圈就是一个磁道。
  • 比喻： 就像操场上的跑道。
• 扇区 (Sector)：每个磁道又像切披萨一样，被切分成很多小块，每一块叫扇区。
  • 地位：扇区是磁盘读写的最小物理单位（通常是 512 字节或 4KB）。

3. 核心概念：柱面 (Cylinder) —— 考试必考

这是最抽象但最重要的概念。请看右上角图中标注红色的虚线圆柱体。

• 定义：所有盘面上，半径相同的那些磁道，在垂直方向上叠在一起，就构成了一个柱面。
• 为什么要有这个概念？
  • 因为所有磁头是固定在同一个移动臂上的。
  • 当你把磁头移动到最外圈（磁道 0）时，所有盘面的磁头都同时停在了磁道 0 上。
  • 性能秘诀：如果不移动机械臂，只通过电子切换磁头来读写不同盘面上的数据，速度是极快的。
  • 结论：柱面是操作系统优化读写速度的关键。把相关联的数据存在同一个柱面上，就能减少机械臂的移动。

4. 磁盘寻址：如何找到一个数据块？

PPT 左下角红字列出了物理块地址的编码方法，最经典的是 CHS 寻址法：

1. 柱面号 (Cylinder) —— 找圈

• 首先，操作系统指挥移动臂，把磁头移动到指定的半径位置（比如第 100 号柱面）。
• 动作：机械移动（最慢，叫“寻道时间”）。

2. 磁头号 (Head) —— 找面

• 磁头臂到了位置，但有 4 个盘面，我要读哪一个？通过激活具体的磁头来选择盘面。
• 动作：电子切换（极快）。

3. 扇区号 (Sector) —— 找块

• 盘面在疯狂旋转，磁头不动，等着指定的那个扇区（披萨块）转到磁头底下。
• 动作：机械旋转等待（较慢，叫“旋转延迟”）。

地址转换关系（扇区编号从0开始）

磁盘存取时间

$$T_a = T_s + \frac{1}{2r} + \frac{b}{rN}$$

公式左边的 T_a 代表 磁盘一次存取的总时间 (Total Access Time)。它由三部分组成：

第一部分：寻道时间 (T_s) —— “最耗时的赶路”

• 对应变量：T_s (Seek Time)。
• 含义：机械臂把磁头移动到指定柱面（磁道）所花的时间。
• 特点：
  • 这是物理机械运动。
  • 在计算题中，通常会直接给你一个平均值（比如 “平均寻道时间为 10ms”），或者让你根据移动了多少个磁道来算。
  • 它是性能杀手：通常占总时间的大头。

第二部分：旋转延迟 ($\frac{1}{2r}$) —— “平均运气”

• 对应变量：图中蓝色的 $\frac{1}{2r}$。
• 含义：平均旋转等待时间。
• 推导逻辑（非常重要）：
  • r：磁盘旋转速度（单位：转/秒）。比如 7200转/分 = 120转/秒。
  • 1/r：转一整圈需要的时间。
  • 为什么是 1/2？：因为当你磁头到了磁道时，目标扇区可能刚过去（要等一整圈），也可能正好就在下面（不用等）。平均来看，你需要等半圈。
  • 这就是 $\frac{1}{2} \times (\text{转一圈的时间})$ 的由来。

第三部分：传输时间 ($\frac{b}{rN}$) —— “真正的读写”

• 对应变量：图中橙色的 $\frac{b}{rN}$。
• 含义：平均传输时间。也就是磁头扫过数据块并读取内容的时间。
• 变量详解：
  • b：你要读写的字节数 (Bytes to transfer)。
  • N：一个磁道上总共有多少字节 (Bytes per track)。
  • r：转速。
• 推导逻辑：
  • r × N = 磁盘一秒钟能扫过多少数据（数据传输率）。
  • 时间 = 总量 / 速度 = b/(r × N)。
  • 或者另一种理解： $\frac{b}{N}$ 表示你要读的数据占了这一圈的百分之多少（比如占了 1/10 圈），然后乘以转一圈的时间 (1/r)。结果是一样的。

移臂调度及算法

先来先服务算法

最短查找时间优先算法

单向扫描算法

双向扫描算法

电梯调度算法

旋转调度

循环排序

优化分布（交替排序）

参考资料

操作系统原理 (2025 春季学期)

01 - AI 时代的操作系统课2025 南京大学操作系统原理]_哔哩哔哩_bilibili

第一章作业

1

假设同一套指令集用不同的方法设计了两种机器 M1 和 M2。机器 M1 的时钟周期为 0.8ns，机器 M2 的时钟周期为 1.2ns。某个程序 P 在机器 M1 上运行时的 CPI 为 4，在 M2 上的 CPI 为 2。对于程序 P 来说，哪台机器的执行速度更快？快多少？

2

假定编译器对某段高级语言程序编译生成两种不同的指令序列 S1 和 S2，在时钟频率为 500MHz 的机器 M 上运行，目标指令序列中用到的指令类型有 A、B、C 和 D 四类。每类指令在 M 上的 CPI 和两个指令序列所用的各类指令条数如下表所示。

3

假定机器 M 在运行程序 P 的过程中，共执行了 500×10⁶ 条浮点数指令、4000×10⁶ 条整数指令、3000×10⁶ 条访存指令、1000×10⁶ 条分支指令，这 4 种指令的 CPI 分别是 2、1、4、1。若要使程序 P 的执行时间减少一半，浮点指令的 CPI 应如何改进？若要使程序 P 的执行时间减少一半，访存指令和分支指令的 CPI 应如何改进？若浮点指令和整数指令的 CPI 减少 20%，访存指令和分支指令的 CPI 减少 40%，则程序 P 的执行时间会减少多少？

第二章作业

1

假定某计算机的总线采用奇校验，每8位数据有一位校验位，若在32位数据线上传输的信息是 8F 3C AB 96H，则对应的4个校验位应为什么？ 若接收方收到的数据信息和校验位分别为87 3C AB 96H 和 0101B，则说明发生了什么情况，并给出验证过程。.0

第一部分：计算原始数据 8F 3C AB 96H 对应的 4 个校验位

前提条件： - 使用奇校验：每个字节（8位）中，1的个数必须是奇数。 - 每8位数据配1位校验位，所以32位数据分成4个字节，对应4个校验位。 - 数据是十六进制：8F 3C AB 96H

我们需要对每一个字节单独计算其奇校验位。

第一步：把每个十六进制字节转换成二进制

• 8F H = 1000 1111
• 3C H = 0011 1100
• AB H = 1010 1011
• 96 H = 1001 0110

第二步：数每个字节中“1”的个数，然后确定校验位

奇校验规则： 如果当前字节中“1”的个数是偶数，则校验位设为 1，使总数变为奇数；如果是奇数，则校验位设为 0，保持奇数。

我们逐个来看：

1. 字节 8F = 1000 1111
   • 数“1”：位置0, 4,5,6,7 → 共 5个1 → 是奇数
   • 所以校验位 = 0
2. 字节 3C = 0011 1100
   • 数“1”：位置2,3,4,5 → 共 4个1 → 是偶数
   • 所以校验位 = 1
3. 字节 AB = 1010 1011
   • 数“1”：位置0,2,4,6,7 → 共 5个1 → 是奇数
   • 所以校验位 = 0
4. 字节 96 = 1001 0110
   • 数“1”：位置0,3,5,6 → 共 4个1 → 是偶数
   • 所以校验位 = 1

✅ 所以，对应的4个校验位是：0 1 0 1，即 0101B

第二部分：接收方收到的数据是 87 3C AB 96H 和校验位 0101B，发生了什么？验证过程

现在接收方收到： - 数据：87 3C AB 96H - 校验位：0101B

我们怀疑有错误，因为原始发送的是 8F，但收到的是 87 —— 很可能第一个字节出错了！

我们来逐字节验证奇校验是否成立。

第一步：将接收到的数据转为二进制

• 87 H = 1000 0111
• 3C H = 0011 1100 （没变）
• AB H = 1010 1011 （没变）
• 96 H = 1001 0110 （没变）

校验位：0101B → 对应四个字节的校验位分别是：第1字节 0，第2字节 1，第3字节 0，第4字节 1

第二步：验证每个字节 + 校验位 是否满足奇校验

注意：我们验证的是“数据位 + 校验位”一共9位中，1的个数是否为奇数。

1. 第一字节 87 + 校验位 0
   • 数据位：1000 0111 → “1”的个数：位置0, 5,6,7 → 4个1
   • 加上校验位 0 → 总共还是 4个1 → 是偶数 ❌
   • 不满足奇校验！→ 出错！
2. 第二字节 3C + 校验位 1
   • 数据位：0011 1100 → “1”的个数：4个（偶数）
   • 加上校验位 1 → 总共 4+1=5 → 奇数 ✅
   • 正确
3. 第三字节 AB + 校验位 0
   • 数据位：1010 1011 → “1”的个数：5个（奇数）
   • 加上校验位 0 → 总共 5 → 奇数 ✅
   • 正确
4. 第四字节 96 + 校验位 1
   • 数据位：1001 0110 → “1”的个数：4个（偶数）
   • 加上校验位 1 → 总共 5 → 奇数 ✅
   • 正确

✅ 结论：只有第一个字节校验失败！说明在传输过程中，第一个字节发生了错误。

进一步分析：哪里出错了？

原始发送的是 8F H = 1000 1111

接收的是 87 H = 1000 0111

对比：

1
2
3
4

原始: 1 0 0 0  1 1 1 1
接收: 1 0 0 0  0 1 1 1
             ↑
            第5位（从左数第5位，或从右数第4位）由1变成了0

所以，第5位发生了翻转错误（bit flip）。

🧠 总结

1. 原始数据 8F 3C AB 96H 的校验位是 0101B。
2. 接收方收到 87 3C AB 96H 和 0101B 后，发现第一个字节校验失败，说明该字节在传输中发生了错误（具体是第5位由1变0）。
3. 奇校验能检测单个比特错误，但不能纠正它，也不能检测偶数个比特错误。

第三章作业

已知 x = 10, y = -6，采用 6位机器数表示。请按如下要求计算并把结果还原成真值。

（1）求 [x + y]补，[x - y]补 （2）用原码一位乘法计算 [x × y]原 （3）用布斯算法计算 [x × y]补 （4）用加减交替法计算 [x / y]原 的商和余数

第七章作业

1

DRAM 的全称是 Dynamic Random Access Memory，中文叫 动态随机存取存储器。

它是计算机中最常用的主存储器（Main Memory / RAM），也就是我们平时常说的“内存条”上的核心芯片。

为什么 DRAM 单元要刷新？（物理原理）

核心原因：漏电。

你可以把 DRAM 的存储单元想象成一个底部有个小针眼的“水桶”（电容），而数据就是“水”（电荷）。

• 存入数据 “1”： 你给桶里倒满水。
• 存入数据 “0”： 你把桶倒空。
• 问题来了： 因为那个小针眼（晶体管的漏电流），满桶的水会慢慢往下漏。
  • 如果你不管它，过一会儿（比如 2ms 后），桶里的水漏干了，原本的 “1” 就变成了 “0”，数据就丢了。

这里最容易混淆的是两个时间概念，必须分清楚：

1. 最大刷新时间（题目中的 2ms）：
   • 这是死线 (Deadline)。
   • 意思是：对于每一个水桶，管理员最迟必须每隔 2ms 回来检查一次。如果超过 2ms 没管它，水就漏光了。
2. 产生刷新信号的间隔（题目要求的答案）：
   • 这是管理员处理下一行水桶的频率。
   • 关键点： 管理员不能一次性同时刷新几百万个水桶（那样电路会过载，电流太大）。他必须一批一批地（一行一行地）轮流刷新。

2

ROM 的全称是 Read-Only Memory，中文叫 只读存储器。

核心特点：

• 字面意思： “Read-Only” 意味着只能读，不能写（或者说在正常工作状态下不能随意写入）。
• 实际特性（最重要）：非易失性 (Non-Volatile)。
  • RAM (DRAM/SRAM)： 一断电，数据立马消失。
  • ROM： 断电后，数据依然保存。哪怕你把电脑关机放一年，ROM 里的数据也不会丢。

为什么 ROM 总是放在内存地址的最前面（从 0 开始）？

1. 开机第一件事： 当你按下电脑电源键时，RAM（内存条）里是空的（全是乱码或 0），CPU 无法从 RAM 里读取指令。
2. 启动引导： CPU 设计为通电后自动去地址 0000H（或其他固定地址）找第一条指令。
3. 固化程序： 我们必须在这个位置放一个断电也不丢数据的存储器（ROM），里面存着电脑的启动程序（BIOS/UEFI）。
   • 它负责检测硬件、初始化系统，然后把操作系统（Windows/Linux）从硬盘搬到 RAM 里。

当 $\overline{\text{MREQ}} = 0$（即处于低电平/有效状态）时，它的主要作用是通知系统，CPU 当前正打算对内存（RAM 或 ROM）进行访问。

$R/\overline{W}$ (Read / Write Control)

• 角色：这是 CPU 发出的控制信号（总线信号）。
• 含义：它告诉整个系统，CPU 当前想要控制数据流向的方向。
• 状态逻辑：
  • 高电平 (1) = Read (读)：CPU 准备从总线上接收数据（数据流向：内存 → CPU）。
  • 低电平 (0) = Write (写)：CPU 准备向总线上发送数据（数据流向：CPU → 内存）。

通俗理解：这是 CPU 在喊话：“大家都听好了，我现在是要‘收东西’（Read）还是要‘发东西’（Write）。”

$\overline{WE}$ (Write Enable)

• 角色：这是 RAM 芯片上的输入引脚（控制端）。
• 含义：允许写入信号。它决定了内存芯片是否允许将数据总线上的电平记录到存储单元中。
• 符号含义：顶部的横线表示低电平有效 (Active Low)。
• 状态逻辑：
  • 低电平 (0) = 允许写入：内存芯片打开“大门”，将数据总线上的数据存入当前地址指向的单元。
  • 高电平 (1) = 禁止写入：内存芯片处于读取模式（配合其他信号）或待机模式，不会修改内部存储的数据。

通俗理解：这是内存芯片身上的一个开关。只有把这个开关拉下来（变低），内存才会乖乖地把数据“记下来”。

3

4

5

6

第四章作业

1

哪些寻址方式下的操作数在寄存器中？哪些在存储器中？

• 操作数（Operand）：指令执行时要处理的数据。
• 寻址方式（Addressing Mode）：指明操作数在哪里（寄存器？内存？立即数？）以及如何找到它。
• 寄存器（Register）：CPU内部的高速存储单元。
• 存储器（Memory）：主存（RAM），速度比寄存器慢，但容量大。

⚠️ 注意：立即数（Immediate） 不是寄存器也不是存储器，它直接嵌入在指令中。

2

什么是 RISC？

RISC = Reduced Instruction Set Computer（精简指令集计算机）

与之相对的是 CISC（Complex Instruction Set Computer，复杂指令集计算机），比如 Intel x86。

1️⃣ 指令集精简（Reduced Instruction Set）

• 指令数量少（通常几十到几百条），每条指令功能单一。
• 指令长度固定（如 32 位），便于流水线处理。

💡 类比：就像厨房里只有几把多功能刀具，每把刀只做一件事，但做得又快又好。

例子：

• RISC：ADD R1, R2, R3 → 把 R2 和 R3 相加，结果存入 R1
• CISC：MOV [BX+SI+10], AX → 一条指令完成地址计算+内存写入

2️⃣ 指令执行周期短（Single-Cycle Execution）

• 大多数指令在一个时钟周期内完成。
• 通过简化指令和硬件设计实现。

3️⃣ 大量通用寄存器（Large Register File）

• 寄存器数量多（如 ARM 有 16 个通用寄存器，RISC-V 有 32 个）。
• 减少对内存的访问，提高速度。

4️⃣ 采用流水线技术（Pipelining）

• 指令执行分为多个阶段（取指、译码、执行、访存、写回），并行处理。
• RISC 指令简单统一，非常适合流水线。

5️⃣ 加载/存储架构（Load/Store Architecture）

• 只有 LOAD 和 STORE 指令可以访问内存。
• 其他运算指令只能在寄存器之间进行。

3

假定某计算机中有一条转移指令，采用相对寻址方式，共占两字节，第一字节是操作码，第二字节是 相对位移量(用补码表示),CPU每次从内存只能取一字节。假设执行到某转移指令时 PC的内容为200, 执行该转移指令后要求转移到100开始的一段程序执行，则该转移指令第二字节的内容应该是多少?

4

4.假设地址为1200H的内存单元中的内容为12FCH,地址为12FCH的内存单元的内容为38B8H,而 38B8H单元的内容为88F9H。说明以下各情况下操作数的有效地址是多少? (1)操作数采用变址寻址，变址寄存器的内容为252,指令中给出的形式地址为1200H。 (2)操作数采用一次间接寻址，指令中给出的地址码为1200H。 (3)操作数采用寄存器间接寻址，指令中给出的寄存器编号为8,8号寄存器的内容为1200H。

5

6.某计算机指令系统采用定长指令字格式，指令字长16位，每个操作数的地址码长6位。指令分二 地址、单地址和零地址3类。若二地址指令有k2条，零地址指令有k0条，则单地址指令最多有多少条?

第五章作业

1.

CPU的基本组成和基本功能各是什么?

1. CPU 的基本组成 (Basic Composition)

CPU 在硬件上主要由 数据通路 (Datapath) 和 控制器 (Control Unit) 两大部分组成。

• 数据通路 (Datapath)：
  • 定义：它是 CPU 中负责数据处理和信号传递的路径，“干活的肌肉”。
  • 包含的核心部件：
    • 运算部件 (ALU)：负责算术运算（加减）和逻辑运算（与或）。
    • 寄存器堆 (Register File)：CPU 内部的高速存储单元，用于暂存操作数和运算结果（如 rs, rt, rd）。
    • 程序计数器 (PC)：存着当前或下一条指令的地址，是指令流动的“指针”。
    • 其他连接部件：包括多路选择器 (MUX)、加法器 (Adder)、符号扩展单元 (SignExt) 等，用于连通电路和辅助计算。
• 控制器 (Control Unit)：
  • 定义：它是 CPU 的“大脑”，指挥数据通路工作。
  • 功能：根据指令的操作码 (Opcode) 和功能码 (Func)，生成各种控制信号（如 RegDst, ALUSrc, MemWr 等），控制 MUX 的选通和寄存器的读写。

2. CPU 的基本功能 (Basic Functions)

CPU 的功能就是执行指令，这一过程通常被称为 “指令周期”。结合 PPT 中的流程，基本功能可以概括为以下四点：

1. 指令控制 (Instruction Control)：
   • 取指令：控制程序按照顺序执行 (PC + 4) 或进行跳转 (beq/j)。确保 CPU 能自动地、连续地从存储器中取出指令。
2. 操作控制 (Operation Control)：
   • 译码与指挥：对取出的指令进行译码（分析 Opcode），产生相应的控制信号，指挥各个部件按规定的动作工作（例如：看到 lw 就打开内存读开关，看到 add 就指挥 ALU 做加法）。
3. 时间控制 (Time Control)：
   • 时序同步：对各种操作实施时间上的定时。通过 时钟信号 (Clk) 来同步所有部件的动作（例如：规定在时钟上升沿更新 PC，在下降沿写入寄存器），保证计算机有条不紊地工作。
4. 数据加工 (Data Processing)：
   • 运算：利用 ALU 对数据进行算术运算（如 add）和逻辑运算（如 ori），这是 CPU 最根本的功能。

2. 取指令部件的功能是什么？

根据 PPT image_373184.png，取指令部件 (Instruction Fetch Unit) 主要有两个核心功能：

1. 取指令：根据程序计数器 (PC) 中的地址，从指令存储器 (Instruction Memory) 中读取出当前的指令字 (M[PC])。
2. 更新 PC：计算下一条指令的地址。通常情况下是顺序执行 (PC <- PC + 4)；如果是跳转或分支指令，则更新为目标跳转地址。

3. 控制器的功能是什么？

根据 PPT image_2f0f80.png 和 image_2f0cd7.png 中展示的真值表逻辑：

控制器的功能是“翻译”和“指挥”。它接收指令中的 操作码 (op) 和 功能码 (func)，通过译码逻辑，产生一系列的 控制信号 (如 RegDst, ALUSrc, RegWr, MemtoReg 等)。这些信号控制着数据通路中各个多路选择器 (MUX)、ALU 和寄存器的动作，确保指令按预定逻辑执行。

4. 单周期处理器相关问题

• 单周期处理器的 CPI 是多少？
  • CPI = 1。
  • 原因：顾名思义，单周期处理器每条指令都在一个时钟周期内完成。
• 时钟周期如何确定？
  • 时钟周期取决于 最复杂指令（通常是 lw）的执行时间，也就是数据通路中的 关键路径 (Critical Path)。
  • 计算公式：T_cycle≥ 取指时间 + 译码/读寄存器时间 + ALU运算时间 + 读数据存储器时间 + 写回时间。必须保证最慢的指令也能在一个周期内跑完。
• 为什么单周期处理器的性能差？
  • 因为 时钟周期被“最慢的指令”拖累了。
  • 解释：虽然像 add 或 beq 这样的简单指令本来可以跑得很快（比如只要 400ps），但因为时钟周期必须迁就最慢的 lw 指令（比如 600ps），所以简单指令执行完后必须 空转等待，直到周期结束。这就造成了巨大的时间浪费，导致整体效率低下。

5. 单周期方式下，在一个指令周期内某个部件能否被重复使用多次？为什么？

• 回答：不能。
• 为什么：
  • 在单周期设计中，指令的执行像水流一样流过数据通路，每个部件在每个周期内只能处理这一个指令流过的数据。
  • 如果需要重复使用某个功能（例如需要做两次加法：一次算 PC+4，一次算 ALU 运算），硬件上必须 设置多份独立的部件（例如设置专门的加法器用于 PC 更新，见 image_2dc282.png 中的 Adder），而不能复用同一个 ALU。
  • 原因总结：如果复用，会产生 资源冲突 (Structural Hazard)，因为在一个时钟周期内，一个部件无法同时处理两个不同的任务。

6

1. RegWr (寄存器写使能)

• 正常功能：
  • 1：允许将数据写入寄存器堆（用于 R-type, ori, lw）。
  • 0：禁止写入（用于 sw, beq, j）。
• 若恒为 0：寄存器堆的大门永远关上了，任何数据都写不进去。
• 受影响指令：所有需要写回结果的指令，包括 R型指令 (add, sub 等)、ori 和 lw。它们虽然能算出结果，但存不下来，相当于白忙活。

2. RegDst (写入目标寄存器选择)

• 正常功能：
  • 1：写入目标是 rd (指令 11-15 位)，用于 R型指令。
  • 0：写入目标是 rt (指令 16-20 位)，用于 lw, ori。
• 若恒为 0：写入数据的目的地永远被锁定在 rt。
• 受影响指令：R型指令 (add, sub 等)。这些指令本该把结果存入 rd，现在却错误地覆盖了 rt 寄存器里的内容。
  • 注：lw 和 ori 本来就要选 0，所以它们不受影响。

3. ALUSrc (ALU 源操作数选择)

• 正常功能：
  • 1：ALU 的第二个输入选 立即数 (用于 lw, sw, ori)。
  • 0：ALU 的第二个输入选 寄存器 B (用于 R-type, beq)。
• 若恒为 0：ALU 永远看不见立即数，只能看见寄存器 B。
• 受影响指令：lw, sw, ori。这些指令需要用到立即数（算地址或做逻辑运算），信号错误会导致 ALU 使用错误的操作数进行计算。

4. Branch (分支信号)

• 正常功能：
  • 1：表示当前是分支指令，如果 Zero=1 则更新 PC 为跳转目标。
  • 0：表示顺序执行 PC+4。
• 若恒为 0：与门永远输出 0，PC 永远无法加载分支目标地址。
• 受影响指令：beq。即使比较结果相等（应跳转），CPU 也会无视，继续执行下一条指令，导致分支失效。

5. MemWr (存储器写使能)

• 正常功能：
  • 1：允许向数据存储器写入数据 (用于 sw)。
  • 0：只读不写。
• 若恒为 0：数据存储器变成了“只读”模式。
• 受影响指令：sw。该指令的功能就是存数，写不进去就完全失效了。

6. ExtOp (扩展模式选择)

• 正常功能：
  • 1：进行 符号扩展 (Sign Extension)，用于 lw, sw (处理负偏移量)。
  • 0：进行 零扩展 (Zero Extension)，用于 ori。
• 若恒为 0：所有立即数都按“零扩展”处理。
• 受影响指令：lw 和 sw。
  • 如果偏移量是正数，运气好还能对；但如果偏移量是 负数，零扩展会把它变成一个巨大的正数，导致计算出的内存地址完全错误。

7. R-type (R型指令标识)

• 正常功能：这通常是一个译码信号。当它为 1 时，ALU 控制器会去查看 func 字段来决定具体做什么运算（加、减、与、或等）。当它为 0 时，ALU 控制器通常执行默认操作（如加法，服务于 lw/sw）。
• 若恒为 0：ALU 控制器认为当前“不是 R型指令”，因此忽略 func 字段，直接执行默认操作（通常是 ADD）。
• 受影响指令：除了 add 以外的所有 R型指令 (sub, and, or, slt 等)。它们会被错误地执行成加法。

8. MemtoReg (写回数据来源选择)

• 正常功能：
  • 1：写回寄存器的数据来自 存储器 (用于 lw)。
  • 0：写回寄存器的数据来自 ALU (用于 R-type, ori)。
• 若恒为 0：写回通路永远连着 ALU，断开了存储器。
• 受影响指令：lw。该指令本想把从内存读出的数据存进寄存器，结果却错误地把内存地址（ALU 计算结果）存进去了。

第六章作业

2（1）

1. 为什么“一条指令”的执行时间没有缩短？

流水线技术并不是让“单条指令跑得更快”，而是将一条指令拆分成多个步骤（如 IF, ID, EX, MEM, WB）。

• 寄存器延迟（Overhead）：在流水线的每个阶段之间，都需要加入流水线寄存器来保存中间结果。这些寄存器本身有读写延迟（建立时间、保持时间）。
• 木桶效应：流水线的时钟周期取决于最慢的那一个阶段。
  • 假设非流水线执行一条指令需要 800ps。
  • 将其切分为 5 段流水线，每段 160ps。但因为要加上寄存器延迟（假设 10ps），周期可能变成了 170ps。
  • 那么一条指令走完 5 个阶段总共需要 170 × 5 = 850ps。
• 结论：单条指令从进入流水线到流出，所花费的总时间（潜伏期，Latency）反而因为寄存器的开销而略微增加了。

2. 为什么“程序”的执行时间缩短了？

流水线的核心优势在于并行（Parallelism）*和*吞吐率（Throughput）。

• 并行处理：虽然一条指令要 5 个周期才做完，但当第一条指令在做“第二步”时，第二条指令已经开始做“第一步”了。

• 吞吐率提升：

  • 非流水线：每 800ps 才能完成一条指令。
  • 流水线：一旦流水线填满，每 170ps 就能有一条指令完成（理想情况下）。

• 数据证明：

  参考你之前的 PPT image_edf843.png：

  • 单周期方式执行 N 条指令：时间 = 600N ps。
  • 流水线方式执行 N 条指令：时间 = 234N ps。
  • 结论：234N < 600N，程序的总执行时间被显著缩短了。

2（5）

(1) 为什么要各流水段之间加寄存器？

简单来说，流水线寄存器（Pipeline Registers）是实现“流水线”功能的物理基础。

• 保存中间结果（记忆功能）：每个时钟周期结束时，当前阶段完成的工作（比如计算出的地址、读出的寄存器值）必须被保存下来，才能在下一个时钟周期传给下一阶段使用。如果没有寄存器，信号会瞬间流过整个电路，变成单周期处理器，无法并行。
• 隔离各个阶段（解耦）：寄存器像一堵墙，把复杂的组合逻辑电路切成了 5 小段。这样，第 1 段在取指时，第 2 段可以同时在译码，互不干扰。
• 同步时钟：所有的流水线寄存器由同一个时钟信号控制，确保所有指令像排队一样，整齐划一地每过一个周期向前挪一步。

(2) 各流水段寄存器的宽度是否都一样？

不一样。

(3) 为什么？

因为每个阶段需要传递给后续阶段的信息量是不同的。

流水线寄存器的宽度取决于后面所有的阶段需要用到哪些信息。所有的信息（包括数据信号和控制信号）都必须像接力棒一样，一层一层往下传。

我们可以具体拆解一下（以标准的 MIPS 32位 5级流水线为例）：

1. IF/ID 寄存器（通常最窄）：
   • 只需要保存：指令本身（32位） + 下一条指令地址 PC+4（32位）。
   • 总宽约 64位。
2. ID/EX 寄存器（通常最宽）：
   • 这一步刚把指令翻译完，需要把所有原材料都带上：读出的两个寄存器数据（32+32位）、扩展后的立即数（32位）、PC+4（32位）、写回的目标寄存器号（5位），再加上一大堆控制信号（WB, MEM, EX 段的信号）。
   • 总宽往往超过 100位。
3. EX/MEM 寄存器：
   • ALU用完的数据不需要传了，但算出的结果要传：ALU计算结果（32位）、准备写入内存的数据（32位）、写回目标寄存器号（5位）以及剩下的控制信号。
   • 宽度变小。
4. MEM/WB 寄存器：
   • 内存操作完，只需要传：读取的内存数据（32位）、ALU结果（32位）、写回目标寄存器号（5位）以及最后的 WB 控制信号。
   • 宽度进一步变化。

3

首先，我们根据题目给出的数据，列出当前各个阶段的耗时：

• IF (取指)：使用存储单元 → 200ps
• ID (译码)：寄存器堆读 → 50ps
• EX (执行)：ALU 和加法器 → 150ps
• MEM (访存)：使用存储单元 → 200ps
• WB (写回)：寄存器堆写 → 50ps

当前基准时钟周期：

T_clk = max (200, 50, 150, 200, 50) = 200ps。

目前的瓶颈是 IF 和 MEM 阶段。

(1) 若 EX 阶段的 ALU 时间缩短 20%

• 计算：新的 ALU 时间 = 150ps × (1 − 20%) = 120ps。
• 分析：此时流水线各段最长时间依然是 IF 和 MEM 的 200ps。EX 阶段本来就不是瓶颈（150ps < 200ps），缩短它只会让它等待的时间更长（气泡更多）。
• 结论：不能加快流水线执行速度。时钟周期仍然维持在 200ps。

(2) 若 ALU 操作时间增加 20%

• 计算：新的 ALU 时间 = 150ps × (1 + 20%) = 180ps。
• 分析：虽然 ALU 变慢了，但 180ps 仍然小于最慢的存储器访问时间（200ps）。流水线的“短板”依然是存储器。
• 结论：对流水线性能没有影响。时钟周期仍然维持在 200ps。

(3) 若 ALU 操作时间增加 40%

• 计算：新的 ALU 时间 = 150ps × (1 + 40%) = 210ps。
• 分析：此时 EX 阶段的时间（210ps）超过了原本的瓶颈（200ps）。
  • 旧瓶颈：200ps
  • 新瓶颈：210ps
  • 根据木桶效应，时钟周期必须迁就最慢的阶段。
• 结论：流水线性能会下降。时钟周期必须调整为 210ps，导致整体运行速度变慢。

4

(1) 在非流水线处理器上执行该程序需要花多长时间？

非流水线处理器采用串行执行方式，上一条指令完全做完，下一条才开始。

• 计算公式：总时间 = 指令条数 × 单条指令执行时间

• 计算过程：

  T_non-pipe = 10⁶ × 100ps = 10⁸ps

• 单位换算：

  10⁸ps = 100, 000ns = 100μs

答案： 需要花 100μs（或者写 10⁸ps）。

(2) 若新 CPU 采用 20 级流水线，理想情况下，它比非流水线处理器快多少？

这道题可以从两个角度回答，一个是计算加速比，一个是计算具体时间。题目问的是“快多少”（倍数），通常指加速比。

• 理想流水线假设：

  1. 流水线各段 perfectly balanced（完全平衡），每段耗时相等。
  2. 没有流水线填充时间的损耗（当 N 很大时，k − 1 个填充周期可忽略）。

• 流水线时钟周期：

  $$T_{\text{clk}} = \frac{\text{非流水线指令时间}}{\text{流水线级数}} = \frac{100\text{ps}}{20} = 5\text{ps}$$

• 流水线总执行时间：

  T_pipe ≈ N × T_clk = 10⁶ × 5ps = 5 × 10⁶ps

  (注：精确公式为 (N + k − 1) × T_clk，但 10⁶ ≫ 19，故忽略不计)

• 计算加速比 (Speedup)：

  $$\text{Speedup} = \frac{T_{\text{non-pipe}}}{T_{\text{pipe}}} = \frac{100 \times 10^6\text{ps}}{5 \times 10^6\text{ps}} = 20$$

答案： 理想情况下，它比非流水线处理器快 20 倍。

(一句话结论：理想情况下，多少级流水线，就获得多少倍的加速比)

(3) 实际流水线并是不是理想的，流水段之间的数据传送会有额外开销。这些开销是否会影响指令执行时间和指令吞吐率？

这是一个考察对流水线“潜伏期（Latency）”和“吞吐率（Throughput）”概念理解的问题。

回答：是的，会有影响。 具体分析如下：

1. 对“指令执行时间”（Latency）的影响： 会变长。
   • 定义：指一条指令从进入流水线第一段到最后一段完成所需要的总时间。
   • 分析：在非流水线中，时间纯粹是逻辑电路的操作时间（100ps）。在流水线中，为了保存中间结果，每一级之间都要加入流水线寄存器。这些寄存器有建立时间、保持时间等物理延迟（Overhead）。
   • 结果：一条指令在流水线中走完 20 级，总耗时 = 20 × (理想每级时间 + 寄存器延迟)。这个总和一定大于原来的 100ps。
2. 对“指令吞吐率”（Throughput）的影响： 会降低（相比理想流水线）。
   • 定义：指单位时间内完成的指令数量（$\text{TP} = \frac{1}{T_{\text{clk}}}$）。
   • 分析：流水线的时钟周期 T_clk 必须足够长，以容纳最慢的一段逻辑操作加上寄存器的延迟开销。
   • 结果：实际时钟周期 T_actual = 5ps + Overhead。因为分母变大了，所以吞吐率 $\frac{1}{T_{\text{actual}}}$ 会比理想吞吐率 $\frac{1}{5\text{ps}}$ 要低。

总结答案：

会影响。

• 指令执行时间（单条延迟）：会增加（因为加入了流水线寄存器的延迟开销）。
• 指令吞吐率：会降低（相比于没有开销的理想流水线，因为时钟周期被迫变长了）。

6

1. 哪些指令对之间发生数据相关（Data Dependency）？

我们要找出“写后读”（RAW, Read After Write）的依赖关系。

• 第一组相关：$s3
  • 产生者：第 1 条指令 addu $s3, $s1, $s0 （写入 $s3）
  • 消费者：第 2 条指令 addu $t2, $s3, $s3 （读取 $s3）
  • 描述：第 2 条指令依赖第 1 条指令的结果。
• 第二组相关：$t2
  • 产生者：第 2 条指令 addu $t2, $s3, $s3 （写入 $t2）
  • 消费者：第 3 条指令 lw $t1, 0($t2) （读取 $t2 作为基地址）
  • 以及：第 4 条指令 add $t3, $t1, $t2 （读取 $t2）
  • 描述：第 3 条和第 4 条指令都依赖第 2 条指令的结果。
• 第三组相关：$t1
  • 产生者：第 3 条指令 lw $t1, 0($t2) （写入 $t1）
  • 消费者：第 4 条指令 add $t3, $t1, $t2 （读取 $t1）
  • 描述：第 4 条指令依赖第 3 条指令的结果。

2. 如果不用“转发”技术，需要加几条 NOP？

规则分析： 在没有转发机制的标准 5 段流水线中，数据必须在 WB（写回） 阶段写入寄存器堆后，才能在 ID（译码） 阶段被后续指令读取。

• 写操作发生在第 5 个时钟周期（WB）。
• 读操作发生在第 2 个时钟周期（ID）。
• 这意味着，产生数据的指令必须先完成 WB 阶段，使用数据的指令才能进入 ID 阶段。对于相邻的两条相关指令，中间通常需要间隔 2 个时钟周期（即插入 2 条 NOP）。

具体插入情况：

1. 在第 1 条和第 2 条之间（解决 $s3 相关）： 需要插入 2 条 NOP。

   Plaintext

   1 2 3 4

   addu $s3, $s1, $s0 nop nop addu $t2, $s3, $s3

2. 在第 2 条和第 3 条之间（解决 $t2 相关）： 需要插入 2 条 NOP。

   Plaintext

   1 2 3 4

   addu $t2, $s3, $s3 nop nop lw $t1, 0($t2)

3. 在第 3 条和第 4 条之间（解决 $t1 相关）： 需要插入 2 条 NOP。

   Plaintext

   1 2 3 4

   lw $t1, 0($t2) nop nop add $t3, $t1, $t2

   (注：虽然第 4 条也依赖第 2 条的 $t2，但因为中间已经隔了第 3 条指令和它的 NOP，所以 $t2 的数据早就准备好了，不需要额外处理)

结论（无转发）： 需要在每组发生数据相关的相邻指令前加入 2 条 NOP 指令。

3. 如果采用“转发”，是否可以完全解决数据冒险？

回答：不可以。

原因分析（Load-Use 冒险）：

• ALU 到 ALU 的冒险（如第 1、2 条之间，第 2、3 条之间）可以通过转发完全解决。数据在 EX 阶段算出后，可以直接从流水线寄存器转发给下一条指令的 EX 阶段输入。
• Load 到 ALU 的冒险（即第 3 条 lw 和第 4 条 add 之间）无法完全解决。
  • lw 指令的数据是在 MEM（访存） 阶段结束时才从内存读出的（时钟周期 4）。
  • add 指令需要在 EX（执行） 阶段开始时使用数据进行计算（时钟周期 3）。
  • 时间悖论：数据在未来（第 4 周期）才产生，但现在（第 3 周期）就要用。这是物理上做不到的，这被称为 Load-Use Hazard。

4. 如果不行，需要加入几条 NOP？

针对上述的 Load-Use 冒险，必须让流水线暂停一个周期，等待数据从内存读出。

• 位置：在第 3 条 lw 和第 4 条 add 之间。
• 数量：1 条 NOP。
  • 加了 1 条 NOP 后，add 指令晚一个周期进入 EX 阶段，此时 lw 刚好走完 MEM 阶段，数据可以通过 MEM/WB 寄存器转发给 add。

最终代码序列（采用转发）：

MIPS Assembler

1
2
3
4
5

addu $s3, $s1, $s0
addu $t2, $s3, $s3   # 转发解决，无 NOP
lw   $t1, 0($t2)     # 转发解决，无 NOP
nop                  # 【必须加 1 条 NOP 解决 Load-Use 冒险】
add  $t3, $t1, $t2

结论（有转发）： 需要在发生数据相关的第 4 条指令（add）之前加入 1 条 NOP 指令。

真值 (X) 与 补码 ([X]_补) 之间的三大转换规则

1. 真值 → 补码 (X → [X]_补)

这是最基础的编码过程。

• 正数： 符号位设为 0，数值部分完全照抄，不变。
• 负数： 符号位设为 1，数值部分执行 “各位取反，末位加 1”。

2. 补码 → 真值 ([X]_补 → X)

这是解码过程。PPT 强调了正负数的处理逻辑是对称的：

• 符号位为 0（正数）： 数值部分直接就是真值。
• 符号位为 1（负数）： 数值部分再次执行 “各位取反，末位加 1”。
  • 点评：这验证了你之前的发现——求负数补码的原码，操作逻辑和求补码是一模一样的！

3. 求相反数的补码 ([X]_补 → [−X]_补)

这是数学上的变号操作（例如从 5 的补码求 −5 的补码）。

• 规则： 对 [X]_补 的所有位（注意 PPT 写的：符号位参与运算）执行 “各位取反，末位加 1”。
  • 注意： 这里就是我们刚才说的“整体取反法”。

💡 核心规律总结 (PPT 右下角方框的含义)

PPT 右下角的方框其实在告诉你，以下三个操作用的是同一个核心算法（取反加一）：

1. X → [−X]_补：把一个正数真值变成负数补码。
2. [X]_补 → X：把一个负数补码还原成真值（数值部分）。
3. [X]_补 → [−X]_补：已知一个数的补码，求它相反数的补码。

一句话总结这张 PPT：

在补码系统中，只要涉及“负数”或者“变号”，核心法宝就是 “各位取反，末位加 1”。

奇偶校验法

为了让你彻底明白，我们用一个最简单的ASCII 字符传输作为例子。

假设我们要传输字母 “A”。

字母 “A” 的二进制 ASCII 码是：1000001（共 7 位）。

现在，我们要给它加上第 8 位——校验位。

1. 原始数据分析

• 数据： 1 0 0 0 0 0 1
• 数一数“1”的个数： 这里有 2 个 1。
• 判断： 2 是偶数。

2. 奇校验 (Odd Parity) 的例子

目标： 加上校验位后，整个串里“1”的总数必须是 奇数。

• 现状： 现在有 2 个 1（偶数）。

• 操作： 既然还差一个 1 才能变成奇数，所以校验位必须填 1。

• 最终发送的数据：

  1000001 + 1 (校验位) → 10000011

• 验证： 总共有 3 个 1 → 奇数 → ✅ 合格。

3. 偶校验 (Even Parity) 的例子

目标： 加上校验位后，整个串里“1”的总数必须是 偶数。

• 现状： 现在有 2 个 1（已经由偶数了）。

• 操作： 不需要再加 1 了（否则就变成奇数了），所以校验位填 0。

• 最终发送的数据：

  1000001 + 0 (校验位) → 10000010

• 验证： 总共有 2 个 1 → 偶数 → ✅ 合格。

4. 它是怎么发现错误的？（以奇校验为例）

假设我们使用 奇校验，发送了 10000011（3个1，正常）。

场景一：传输正常

• 接收方收到： 10000011
• 检查： 数一下有 3 个 1（奇数）。
• 结论： 校验通过，数据应该是对的。

场景二：发生 1 位错误（比如第1位传丢了，1变成了0）

• 接收方收到： 00000011 （原本的第一个1变成了0）
• 检查： 数一下，现在只有 2 个 1（偶数）。
• 结论： 不对！ 我们约定好是奇校验的，怎么变成偶数了？报错！

场景三：发生 2 位错误（这是奇偶校验的死穴）

• 假设第1位和最后一位都翻转了。
• 接收方收到： 00000010
• 检查： 数一下，有 1 个 1（奇数）。
• 结论： 接收方会以为数据是对的（因为1的个数还是奇数），但实际上数据已经错得离谱了。

总结表格

海明校验码（略有涉及）

基于我们刚才的深度探讨，我为你整理了一份“海明校验码核心总结”。这份总结略过了死板的教科书定义，专门针对你刚才产生的核心顿悟（关于位置、倒序、多位错误等）进行梳理。

你可以把它当作一份复习备忘录：

1. 核心本质：它是一个“坐标定位系统”

海明码不只是简单的加减法，而是利用二进制权重（1, 2, 4, 8…）构建了一套坐标系。

• 目的： 不仅告诉你“错了”，还能精准地告诉你“第几位错了”。

2. 生成阶段：如何布阵？

• 确定人数： 使用公式 2^r ≥ k + r + 1。
  • 你的理解： 必须有足够的校验位（状态数），才能覆盖所有可能出错的位置 + 1种全对的情况。
• 站位： 校验位必须站在 2ⁿ (1, 2, 4, 8…) 的位置上。
  • 原因： 它们是二进制的“基石”，负责构建坐标轴。
• 计算： 每一个校验位负责监管“二进制位索引中包含自己权重”的那些数据位（利用偶校验原则填充 0 或 1）。

3. 校验阶段：如何抓内鬼？

这是你刚才理解最深刻的部分。

• 操作逻辑： 不区分数据位和校验位，将收到的所有位作为一个整体进行计算。
• 计算校正子（故障码）：
  • 重新计算 P1, P2, P4… 各自辖区内 1 的个数。
  • 偶数 → 记 0。
  • 奇数 → 记 1。
• 关键步骤： 倒序排列（S₄S₂S₁）。
  • 原因： 二进制习惯高位在左。

4. 判决阶段：结果意味着什么？

根据算出的“故障码”（二进制数转十进制）：

• 结果 = 0：
  • 结论： 传输成功（或者发生了极小概率的偶数位相互抵消）。
• 结果 = X (非0)：
  • 结论： 第 X 位出错了。
  • 动作： 无论第 X 位是数据还是校验码，直接将其取反（0变1，1变0），数据即修复。

5. 致命盲区：如果错了 2 位怎么办？

这是我们最后讨论的重点。

• 普通海明码： 会“撒谎”。两个错误叠加会算出一个错误的坐标，导致系统去修改一个无辜的正确位（越改越错）。
• 解决方案（SECDED）： 增加第 8 个“全校验位”。
  • 如果海明码说有错（故障码非0），但全校验位说没错（整体偶校验正常）。
  • 结论： 发生了双比特错误。系统会报警拒绝处理，而不是乱修。

一句话心法：

海明码就是把校验位安插在二进制权重点上，接收时重算一遍奇偶性，算出来的二进制数就是出错位置的坐标。

现在的你已经完全具备了手算海明码甚至去写代码实现它的逻辑基础了！需要我给你出一道终极测试题练练手吗？

原码一位乘法

它的核心思想只有一句话：“符号单独算，数值当无符号数算”。

1. 核心步骤

原码一位乘法把整个过程拆成了两个独立的任务：

任务一：处理符号位 (简单)

• 规则： 同号得正，异号得负。

• 运算： 用异或门 (XOR) 完成。

  P_s = X_s ⊕ Y_s

  (例如：0 ⊕ 1 = 1，结果为负)

任务二：处理数值位 (核心)

• 规则： 既然符号已经拿走了，剩下的绝对值 |X| 和 |Y| 其实就是两个正整数（或者说无符号数）。
• 算法： 直接套用你最开始学的“无符号乘法”（列竖式法）。
  • 看 Y 的最后一位。
  • 是 1 → 加 |X|。
  • 是 0 → 加 0。
  • 逻辑右移（前面补0，因为是绝对值运算，不涉及负数符号维持）。

2. 举例演示

假设我们要计算 X × Y：

• X = −0.1101 (原码 1.1101)
• Y = +0.1011 (原码 0.1011)

第一步：定符号

1(X符号) ⊕ 0(Y符号) = 1(负)

把这个 1 存起来，最后贴到结果上。

第二步：算数值 (1101 × 1011)

这部分完全就是无符号乘法。

• 被乘数 |X| = 1101
• 乘数 |Y| = 1011
• 部分积 P 初始化为 0000

注意：这里的右移全部是逻辑右移（左边补0），因为我们在算绝对值，绝对值永远是正的。

第三步：拼接结果

• 数值部分： P 和 Y 拼起来 → 1000 1111
• 加上小数点： 0.10001111
• 加上符号（第一步算的）： 1.10001111

布斯算法

布斯乘法算法（Booth’s Multiplication Algorithm）是一种用于计算带符号二进制数（通常使用补码表示）的乘法算法。

相较于你之前了解的“原码一位乘法”（主要处理无符号数或需要单独处理符号位），布斯乘法可以直接对补码进行操作，不需要将符号位和数值位分开计算，这使得硬件电路设计更加统一和高效。

1. 核心原理

布斯乘法通过检查乘数的最后一位（Q₀）和辅助位（Q₋₁，初始为0）的状态变化来决定操作。它利用了“连续的1序列可以转换为一次减法和一次加法”的数学性质（例如 99 = 100 − 1），从而减少运算次数。

2. 运算规则表

每次检查乘数的最后两位（Q₀, Q₋₁），执行以下操作，然后进行算术右移：

注意：这里的“- 被乘数”通常通过“+ [-M]补”来实现。

3. 计算步骤演示

假设我们用 4位补码计算：2 × (−3) = −6

• 被乘数 (M) = 2 → 0010
  • (−M)补 = 1110 (用于减法操作)
• 乘数 (Q) = −3 → 1101
• 累加器 (A) = 0000 (初始化为0)
• 辅助位 (Q₋₁) = 0
• 计数器 = 4 (因为是4位)

演算过程：

最终结果：

将 A 和 Q 拼接起来（不看 Q₋₁）：1111 1010。

这是补码形式，转换为十进制：

• 符号位是1，取反加1得到原码：-(0000 0101 + 1) = - (0000 0110) = -6。
• 结果正确。

恢复余数法

加减交替法

原码除法 恢复余数法和不恢复余数法(加减交替法) 计组_哔哩哔哩_bilibili

整数除法处理过程_哔哩哔哩_bilibili

整数不恢复余数除法中，被除数通常要进行位扩展

在不恢复余数除法（加减交替法）*中，**整数除法**和*小数除法的核心算法是一样的，都是根据余数的正负决定商位和下一步操作。但它们在初始设置、精度控制、终止条件、结果处理等方面有明显区别。

定点整数的除法 - 知乎

空间局部性和时间局部性

这两个概念是计算机系统（特别是缓存 Cache）能够高效工作的基石。如果程序员写的代码符合这两个特性，程序的运行速度可能会快几十倍甚至上百倍。

简单来说，CPU 跑得飞快，内存（RAM）跑得比较慢。为了不让 CPU 傻等，我们需要猜测 CPU 接下来要用什么数据，并提前把它搬到离 CPU 最近的缓存里。

局部性原理（Principle of Locality） 就是我们用来猜测的“依据”。

1. 时间局部性 (Temporal Locality)

一句话解释： “如果一个数据现在被访问了，那么它在不久的将来很可能再次被访问。”

• 关键词： 重复利用 (Reuse)。

• 生活类比：

  你正在写作业（CPU工作），桌子上放着一本参考书。如果你刚查阅了某一页，你通常不会马上把它放回书架（内存），而是留就在手边（缓存）。因为你下一分钟大概率还会再看它一眼。

代码实例

看看下面这个简单的循环：

C

1
2
3
4

int sum = 0;
for (int i = 0; i < 1000; i++) {
    sum += i;
}

• 变量 sum 和 i： 在每一次循环中，这两个变量都被反复读取和修改。
• 指令本身： 循环体内的机器指令（代码本身）也是被一遍又一遍地执行。

硬件是怎么做的？

因为有时间局部性，CPU 会把 sum 和 i 以及循环内的指令死死地抓在 L1 Cache（一级缓存） 或者 寄存器 里，绝对不会每次都去慢吞吞的内存条里找。

2. 空间局部性 (Spatial Locality)

一句话解释： “如果一个数据被访问了，那么它附近的数据在不久的将来很可能也会被访问。”

• 关键词： 邻居 (Nearby)。

• 生活类比：

  你去图书馆（内存）借一本《哈利波特第1部》。虽然你现在只要第1部，但管理员（缓存控制器）通常会顺手把第2、3、4部也一起拿给你。因为按常理，看完第1部的人，大概率会接着看第2部，而不是突然跳去看旁边书架的《母猪的产后护理》。

代码实例

这是最典型的数组遍历：

C

1
2
3
4
5
6
7

int arr[1000];
// ... 假设数组里有数据 ...

for (int i = 0; i < 1000; i++) {
    // 按顺序访问：arr[0], arr[1], arr[2]...
    printf("%d", arr[i]);
}

• 数组 arr： 在内存中，数组的元素是连续存放的。arr[0] 的隔壁就是 arr[1]。
• 访问模式： 当程序请求 arr[0] 时，CPU 知道你有“空间局部性”的倾向。

硬件是怎么做的？

当 CPU 去内存取 arr[0] 时，内存条并不是只给一个数字，而是直接给一个 “缓存行” (Cache Line)（通常是 64 字节）。

这意味着，虽然你只喊了 arr[0]，但 arr[1] 到 arr[15] 可能已经被顺手打包带进了 CPU 的缓存。当你下一秒要用 arr[1] 时，它已经在缓存里等着你了，速度极快。

3. 一个经典的“反面教材”

为了让你感受到空间局部性的威力，我们看一个经典的二维数组遍历的例子。

假设有一个巨大的二维数组 matrix[10000][10000]。在 C/C++ 语言中，数组是按行存储的（Row-major），也就是说，第一行的数据在内存里是连在一起的，接着是第二行。

写法 A（利用空间局部性 - 快）：

1
2
3
4
5
6

// 按行遍历：外层是行(i)，内层是列(j)
for (int i = 0; i < 10000; i++) {
    for (int j = 0; j < 10000; j++) {
        sum += matrix[i][j]; 
    }
}

• 分析： 访问顺序是 [0][0], [0][1], [0][2]...。这在内存里是连续的。缓存一次加载一行，命中率极高。

写法 B（破坏空间局部性 - 慢）：

1
2
3
4
5
6

// 按列遍历：外层是列(j)，内层是行(i)
for (int j = 0; j < 10000; j++) {
    for (int i = 0; i < 10000; i++) {
        sum += matrix[i][j];
    }
}

• 分析： 访问顺序是 [0][0], [1][0], [2][0]...。
• 问题： [0][0] 和 [1][0] 在内存中相隔了整整一行（10000个元素）！
• 后果： 每次访问都像是“大跳跃”。CPU 加载了 [0][0] 及其附近的缓存行，结果你下一步要的是十万八千里外的 [1][0]。缓存全部失效（Cache Miss）。这会导致程序运行极其缓慢，甚至慢上几十倍。

cache行和主存块之间的映射方式

1. 直接映射 (Direct Mapping)

口诀： “死板、对号入座”

这是最简单的规则。我们规定：根据车牌号的末尾数字，只能停在固定的车位。

规则公式

Cache行号 = 主存块号 mod  Cache行数

举个例子

假设 Cache 只有 4 个车位（0, 1, 2, 3）。

主存有很多块（0, 1, 2, 3, 4, 5…）。

• 第 0 号主存块： 0 mod  4 = 0 → 只能停 0号 车位。
• 第 1 号主存块： 1 mod  4 = 1 → 只能停 1号 车位。
• …
• 第 4 号主存块： 4 mod  4 = 0 → 也要停 0号 车位！
• 第 8 号主存块： 8 mod  4 = 0 → 还要停 0号 车位！

优缺点

• 优点： 简单！你想找第4号块，只用去0号车位看一眼，不在就是不在，不用找别处。电路实现最便宜。

• 缺点（致命）： 冲突太容易发生了。

  如果你写了一段程序，反复需要访问“第0块”和“第4块”。

  • CPU要用第0块 → 把0停进0号位。
  • CPU要用第4块 → 把0踢走，把4停进0号位。
  • CPU又要用第0块 → 把4踢走，把0停进0号位。
  • 这就是“抖动”（Thrashing），明明旁边 1, 2, 3 号车位空着，但它们死活不能停。

2. 全相联映射 (Fully Associative Mapping)

口诀： “自由、随便停”

这是最灵活的规则。我们规定：只要有空位，想停哪儿停哪儿。

规则

没有公式。主存块可以放在 Cache 的任意一个行中。

举个例子

还是 4 个车位。

• 第 0 号块来了 → 停在 0 号位。
• 第 4 号块来了 → 0号位有人了？没关系，停在 1 号位。
• 第 8 号块来了 → 停在 2 号位。

优缺点

• 优点： 空间利用率极高，只要Cache没满，就不会发生冲突踢人的情况。

• 缺点： 找车太慢（太贵）。

  当你（CPU）想找“第4号块”时，你不知道它在哪里。你必须同时检查所有的车位（0,1,2,3…）。

  这需要非常复杂的硬件电路（并行比较器），如果 Cache 很大，这种电路极其昂贵且耗电。

3. 组相联映射 (Set Associative Mapping)

口诀： “中庸之道、分组管理”

这是现代 CPU（如 Intel Core, AMD Ryzen）普遍采用的方式。它折中了前两者的方案。

它把 Cache 分成了若干个“组” (Set)，每个组里包含几个车位（比如 2 个或 4 个）。

规则

1. 先定位组（像直接映射）： 你必须去指定的组。

   组号 = 主存块号 mod  组数

2. 再定位置（像全相联）： 到了那个组之后，组内的车位随便停。

这被称为 N-路 组相联 (N-way Set Associative)，这里的 N 就是一个组里有几个车位。

举个例子（2路组相联）

假设 Cache 还是 4 个车位，但我们将它们分为 2 个组（Set 0 和 Set 1）。

• Set 0 包含：车位0、车位1
• Set 1 包含：车位2、车位3

现在我们要停 第 4 号主存块：

1. 算组号： 4 mod  2(组数) = 0。所以必须去 Set 0。
2. 找位子： 到了 Set 0，发现里面有“车位0”和“车位1”。只要这两个有一个是空的，第4号块就能停进去。

优缺点

• 优点：
  • 比直接映射灵活：就算 Set 0 里已经停了“第0号块”，我“第4号块”来了还能停在 Set 0 的另一个空位，不会打架。
  • 比全相联便宜：查找时，只需要在特定的组内（比如搜4个位置）找，不需要全场搜。
• 地位： 这是工业界的标准答案。

直接映射中，主存地址的结构

1. 地址结构的宏观样子

假设 CPU 发出的地址是 N 位二进制数（比如 32位）。在直接映射模式下，它被切分为：

$$\text{主存地址} = \underbrace{\text{标记 (Tag)}}_{\text{高位}} \quad | \quad \underbrace{\text{行索引 (Index)}}_{\text{中间}} \quad | \quad \underbrace{\text{块内偏移 (Offset)}}_{\text{低位}}$$

每一段都有其特定的使命。

2. 深度拆解：每一段是干嘛的？

为了方便理解，我们设定一个具体的场景：

• 地址总长度： 32位
• Cache 大小： 4 KB (2¹² 字节)
• 块大小 (Block Size)： 64 Byte (2⁶ 字节)

根据这个配置，我们来计算每一段的长度和作用。

第一部分：块内偏移 (Block Offset) —— “具体的字节在哪？”

• 位置： 地址的最低位。

• 作用： Cache 和主存交换数据是以“块”为单位的（一拿就是 64B）。但 CPU 通常只需要其中的某 1 个字节。偏移量就是告诉 CPU，你要的数据在这个“块”里的第几个位置。

• 怎么算位数？

  看块大小。

  这里块大小是 64 Byte = 2⁶ Byte。

  所以，需要 6 位 来表示 0~63 的位置。

  • Offset = 6 bits

第二部分：行索引 (Cache Line Index) —— “停在哪个车位？”

• 位置： 地址的中间部分。

• 作用： 这是直接映射的核心。它决定了这块数据必须存放在 Cache 的第几行（第几个车位）。

• 怎么算位数？

  看 Cache 一共有多少行。

  $$\text{Cache行数} = \frac{\text{Cache总容量}}{\text{块大小}}$$

  在本例中：4KB/64B = 4096/64 = 64 行。

  64 行 = 2⁶。

  所以，需要 6 位 来定位这 64 个行（000000 到 111111）。

  • Index = 6 bits

第三部分：标记 (Tag) —— “你是谁？”

• 位置： 地址的最高位。

• 作用： 因为有很多个主存块都会映射到同一个 Cache 行（冲突）。当 CPU 拿着地址去查看那个 Cache 行时，发现里面已经存了数据，它怎么知道里面的数据是不是它想要的那个？

  靠比对 Tag！ Tag 就像身份证，证明身份。

• 怎么算位数？

  剩下的位数都是 Tag。

  Tag位数 = 总位数 − 索引位 − 偏移位

  在本例中：32 − 6 − 6 = 20 位。

  • Tag = 20 bits

直写和回写

1. 直写 (Write-Through)

口诀： “老实人、立刻同步”

原理

每当 CPU 要往 Cache 里写数据时，它会同时把数据写回主存。 即：写 Cache + 写主存 同时进行。

• 生活比喻： 你每花一笔钱，不仅记在草稿本上，还立刻跑去老板办公室，把正式账本也更新了。

优缺点

• 优点（简单可靠）：
  • 一致性极好： 主存里的数据永远是最新的。
  • 实现简单： 既然主存总是新的，当 Cache 里的这块数据需要被踢走（替换）时，直接丢弃就行，不需要做任何操作。
• 缺点（慢）：
  • 速度受拖累： CPU 跑得快，但主存太慢了。每次写操作 CPU 都要等主存写完，大大降低了速度。
  • 总线太忙： 哪怕只改了一个字节，都要往主存发一次信号，总线带宽被占满了。

补救措施：写缓冲 (Write Buffer)

为了不让 CPU 傻等主存，通常会在 CPU 和主存之间加一个“写缓冲队列”。 CPU 把数据扔进缓冲队列就立刻溜走去干别的，由硬件慢慢把队列里的数据写进主存。

2. 回写 (Write-Back)

口诀： “懒人智慧、秋后算账”

原理

当 CPU 要写数据时，只修改 Cache 里的内容，不立刻去改主存。 只有当这块数据在 Cache 里待不住了，要被踢走（替换/Evict）的时候，才把它写回主存。

• 关键角色：脏位 (Dirty Bit) Cache 行中需要增加一个标记位，叫“脏位”。
  • Dirty = 1： 说明这行数据被修改过，和主存不一样（脏了）。
  • Dirty = 0： 说明这行数据没被改过，和主存一样（干净）。
• 生活比喻： 你花钱时，只在手里的草稿本上改。老板那边的正式账本先不管。 等到你的草稿本写满了，必须换新本子时（发生替换），你才看一眼旧本子：
  • 如果本子上全是乱涂乱画（脏位=1），你就把最终结果一次性汇报给老板。
  • 如果本子上很干净没动过（脏位=0），直接把本子扔了就行，不用找老板。

优缺点

• 优点（极快）：

  • 速度快： 写操作都在高速 Cache 里完成，CPU 爽飞了。
  • 带宽省： 如果你对同一个变量 i 做了 100 次 i++，直写要访问主存 100 次；而回写只需要在最后踢出时访问 1 次主存。

• 缺点（复杂、有风险）：

  • 硬件复杂： 需要维护“脏位”。

  • 短暂的不一致： 在被写回之前，主存里的数据是旧的。

  • I/O 风险： 如果此时磁盘（DMA）直接去读主存，可能会读到旧数据（需要额外的同步机制来解决）。

  • 1. 直写 (Write-Through)

    口诀： “老实人、立刻同步”

    原理

    每当 CPU 要往 Cache 里写数据时，它会同时把数据写回主存。 即：写 Cache + 写主存 同时进行。

    • 生活比喻： 你每花一笔钱，不仅记在草稿本上，还立刻跑去老板办公室，把正式账本也更新了。

    优缺点

    • 优点（简单可靠）：
      • 一致性极好： 主存里的数据永远是最新的。
      • 实现简单： 既然主存总是新的，当 Cache 里的这块数据需要被踢走（替换）时，直接丢弃就行，不需要做任何操作。
    • 缺点（慢）：
      • 速度受拖累： CPU 跑得快，但主存太慢了。每次写操作 CPU 都要等主存写完，大大降低了速度。
      • 总线太忙： 哪怕只改了一个字节，都要往主存发一次信号，总线带宽被占满了。

    补救措施：写缓冲 (Write Buffer)

    为了不让 CPU 傻等主存，通常会在 CPU 和主存之间加一个“写缓冲队列”。 CPU 把数据扔进缓冲队列就立刻溜走去干别的，由硬件慢慢把队列里的数据写进主存。

    ---

    2. 回写 (Write-Back)

    口诀： “懒人智慧、秋后算账”

    原理

    当 CPU 要写数据时，只修改 Cache 里的内容，不立刻去改主存。 只有当这块数据在 Cache 里待不住了，要被踢走（替换/Evict）的时候，才把它写回主存。

    • 关键角色：脏位 (Dirty Bit) Cache 行中需要增加一个标记位，叫“脏位”。
      • Dirty = 1： 说明这行数据被修改过，和主存不一样（脏了）。
      • Dirty = 0： 说明这行数据没被改过，和主存一样（干净）。
    • 生活比喻： 你花钱时，只在手里的草稿本上改。老板那边的正式账本先不管。 等到你的草稿本写满了，必须换新本子时（发生替换），你才看一眼旧本子：
      • 如果本子上全是乱涂乱画（脏位=1），你就把最终结果一次性汇报给老板。
      • 如果本子上很干净没动过（脏位=0），直接把本子扔了就行，不用找老板。

    优缺点

    • 优点（极快）：
      • 速度快： 写操作都在高速 Cache 里完成，CPU 爽飞了。
      • 带宽省： 如果你对同一个变量 i 做了 100 次 i++，直写要访问主存 100 次；而回写只需要在最后踢出时访问 1 次主存。
    • 缺点（复杂、有风险）：
      • 硬件复杂： 需要维护“脏位”。
      • 短暂的不一致： 在被写回之前，主存里的数据是旧的。
      • I/O 风险： 如果此时磁盘（DMA）直接去读主存，可能会读到旧数据（需要额外的同步机制来解决）。

7 种基本的寻址方式

1. 立即寻址 (Immediate Addressing)

• 算法： 操作数 = A
• 通俗解释： “现钞交易”。数据不存放在内存或寄存器里，而是直接包含在指令代码中。
• 优点： 速度最快（因为取指令的时候顺便就把数据取到了，不用再去查内存）。
• 缺点： 数值的大小受限（因为指令字长是有限的，放不下太大的数）。

2. 直接寻址 (Direct Addressing)

• 算法： EA = A （有效地址 = 指令中给出的地址 A）
• 通俗解释： “拿钥匙开柜子”。指令直接告诉你数据在内存的哪个房间号（地址）。
• 优点： 计算简单，不用复杂的变换。
• 缺点： 地址范围有限（指令里的位数有限，可能访问不了太大的内存空间）。

3. 间接寻址 (Indirect Addressing)

• 算法： EA = (A) （指令给出的地址 A 里存的不是数据，而是数据的真实地址）
• 通俗解释： “寻宝图的寻宝图”。你去地址 A，发现里面是一张纸条，纸条上写的才是数据真正的藏身之处。
• 优点： 有效地址范围大（哪怕指令短，也能访问大内存）。
• 缺点： 慢！因为要访问两次存储器（第一次取地址，第二次取数据）。

4. 寄存器寻址 (Register Addressing)

• 算法： 操作数 = (R) （数据在寄存器 R 中）
• 通俗解释： “翻口袋”。数据就在 CPU 自己的口袋（寄存器）里，伸手就来。
• 优点： 执行极快（不需要访问慢速的内存），指令也很短（寄存器编号很短）。
• 缺点： 寄存器数量很少，也就是口袋太少，装不下多少东西。

5. 寄存器间接寻址 (Register Indirect Addressing)

• 算法： EA = (R) （寄存器 R 里存的是数据的内存地址）
• 通俗解释： “口袋里的钥匙”。CPU 口袋（寄存器）里没数据，但有一把通往内存的钥匙（地址）。
• 优点： 扩大了寻址范围（比直接寻址强）。
• 缺点： 比纯寄存器寻址慢，因为还是要访问一次存储器。

6. 偏移寻址 (Displacement Addressing)

这是现代计算机最常用的方式，包含相对寻址、基址寻址、变址寻址三种。

• 算法： EA = A + (R) （地址 = 形式地址 + 寄存器内容）
• 通俗解释： “基准点 + 偏移量”。比如“从学校大门（基准）往东走 100 米（偏移）”。它结合了直接寻址和寄存器间接寻址的特点。
• 优点： 非常灵活（方便做数组访问、程序浮动等）。
• 缺点： 计算稍微复杂一点。

7. 堆栈寻址 (Stack Addressing)

• 算法： EA = 栈顶
• 通俗解释： “拿最上面的盘子”。不需要给地址，默认就是操作堆栈最顶端的数据。
• 优点： 指令极短（甚至不需要地址码）。
• 缺点： 不灵活，只能按先进后出 (LIFO) 的顺序拿数据。