一、整体架构概览

CPU 和主存（DRAM）之间的数据传输，依靠一套叫做总线（Bus）的共享电气通道来完成。每次数据传输的完整过程叫做一次总线事务（Bus Transaction）。

系统组件连接图

+---------------------------+
|        CPU chip           |
|  +------------+   +-----+ |
|  |Register    |-->| ALU | |
|  |file (%rax) |<--+     | |
|  +-----+------+   +-----+ |
|        |                  |
|  +-----+--------+         |
|  | Bus interface|         |
+--+------+-------+---------+
          |
     System Bus（系统总线）
          |
     +----+-----+
     | I/O bridge|   <-- 信号翻译器，连接系统总线和内存总线
     +----+-----+
          |
     Memory Bus（内存总线）
          |
     +----+------+
     | Main      |
     | memory    |   <-- DRAM 主存，存放地址 A 处的数据 x
     +-----------+

两条总线的分工

---

总线名称	连接对象	职责
系统总线（System Bus）	CPU <-> I/O bridge	CPU 和桥接芯片之间传信号
内存总线（Memory Bus）	I/O bridge <-> 主存	桥接芯片和 DRAM 之间传信号

---

I/O bridge（I/O 桥）：相当于一个"翻译官"，把系统总线的电信号转换成内存总线的电信号，反之亦然。它内部包含内存控制器。

二、总线是什么？

总线是一组并行导线的集合，同时传输三类信号：

总线上的信号种类：
地址信号  ──────────────────────>  "我要访问哪个地址？"
数据信号  ──────────────────────>  "传输的数据内容是什么？"
控制信号  ──────────────────────>  "这次是读还是写？给谁的？"

• 地址和数据信号可以共用同一组线，也可以用不同的线（取决于设计）
• 同一条总线可以连接超过两个设备
• 控制信号负责同步和标识：当前传的是地址还是数据？是读操作还是写操作？是发给内存还是发给磁盘？

三、读事务（Read Transaction）— movq A, %rax

对应汇编指令：把内存地址 A 处的数据加载到寄存器 %rax。

movq A, %rax    // 从内存地址 A 读取 8 字节数据，存入寄存器 %rax

整个过程分三步：

第一步：CPU 把地址 A 放到总线上

CPU chip
  Bus interface
      |
      |-- [地址 A] --> System Bus --> I/O bridge --> Memory Bus --> 主存
                                         ^
                              (I/O bridge 把信号转发到内存总线)
主存看到地址 A，知道"有人要读我这个地址的数据"

ASCII 示意（图a）：
[Register file]  [ALU]
     |
[Bus interface] ---地址A---> [I/O bridge] ---地址A---> [Main memory]
                                                          |
                                                         [A] = x  <- 这里存着数据x

第二步：主存从总线读地址，取出数据 x，写回总线

主存收到地址 A
  -> 去 DRAM 里找地址 A 对应的数据 x
  -> 把 x 写到内存总线上
  -> I/O bridge 把内存总线信号翻译成系统总线信号，继续传给 CPU
ASCII 示意（图b）：
[Register file]  [ALU]
     |
[Bus interface] <---数据x--- [I/O bridge] <---数据x--- [Main memory]
                                                          |
                                                         [A] = x

第三步：CPU 从总线读数据 x，写入寄存器 %rax

CPU 的 Bus interface 从系统总线上感知到数据 x
  -> 把 x 复制到寄存器 %rax
ASCII 示意（图c）：
[Register file]  [ALU]
  %rax = x <--
     |
[Bus interface] <----------  [I/O bridge] <-----------  [Main memory]
                                                           [A] = x  (仍然保留)

读事务完整流程图

四、写事务（Write Transaction）— movq %rax, A

对应汇编指令：把寄存器 %rax 中的数据写入内存地址 A。

movq %rax, A    // 把寄存器 %rax 中的 8 字节数据，写入内存地址 A

同样分三步，方向和读事务相反：

第一步：CPU 把地址 A 放到总线上，主存等待数据

[Bus interface] ---地址A---> [I/O bridge] ---地址A---> [Main memory]
                                                          |
                                                        主存读到地址A，
                                                        等待数据到来...

第二步：CPU 把 %rax 中的数据复制到总线上

[Register file]
  %rax = x ──>
[Bus interface] ---数据x---> [I/O bridge] ---数据x---> [Main memory]

第三步：主存从总线读取数据 x，存入 DRAM 地址 A 处

[Main memory] 读取总线上的 x，把 x 写入地址 A 对应的 DRAM 单元
最终：内存地址 A 的内容 = x（与 %rax 相同）

写事务完整流程图

五、读 vs 写 对比总结

读事务（Load）：  内存 ──数据──> CPU
写事务（Store）： CPU  ──数据──> 内存
步骤对比：
读（movq A, %rax）          写（movq %rax, A）
─────────────────           ─────────────────
1. CPU 发地址 A             1. CPU 发地址 A
2. 内存取数据 x 发到总线    2. CPU 发数据 x 到总线
3. CPU 读 x 存入 %rax       3. 内存读 x 写入地址 A

六、类比理解

整个总线读写机制，就像一个图书馆借还书系统：

计算机概念	图书馆类比
CPU	读者
主存（DRAM）	书库
总线	图书馆传输通道（传送带）
I/O bridge	图书管理台（接收请求、翻译、转发）
地址 A	书的编号
数据 x	书的内容
读事务	读者借书：告诉管理员书号 -> 管理员取书 -> 读者拿到书
写事务	读者还书：告诉管理员书号 -> 读者把书递给管理员 -> 管理员放回书架

---

七、关于总线设计的补充说明

不同厂商的总线架构各有不同，例如：

厂商/平台	总线/互连技术
Intel 旧版（Pentium/Core 2）	前端总线（FSB）连接 CPU 和北桥（Northbridge）
AMD	HyperTransport 互连
Intel Core i7（较新）	QuickPath Interconnect（QPI）

---

这些细节虽然复杂，但核心思想不变：CPU 和内存之间总有一套总线机制负责搬运地址和数据，只是具体实现因平台而异。

内存写事务 与 磁盘存储 — 通俗理解笔记

一、写事务（Write Transaction）— movq %rax, A

这条汇编指令的含义：把寄存器 %rax 中的数据写入内存地址 A。

movq %rax, A    // 把 %rax 中的 8 字节数据 y，写入主存地址 A

写事务同样分三步，数据流向与读事务相反（从 CPU 流向内存）。

第一步（图a）：CPU 把地址 A 放到总线，主存读到后等待数据

寄存器状态：%rax = y（y 是要写入的数据）
[Register file]
  %rax = y
      |
[Bus interface] ---地址A---> [I/O bridge] ---地址A---> [Main memory]
                                                          |
                                                    主存读到地址A，
                                                    进入等待数据状态...
                                                    地址A处内容还是旧的

第二步（图b）：CPU 把数据 y 放到总线，向主存传送

[Register file]
  %rax = y
      |
      |（y 从寄存器流向 Bus interface）
      v
[Bus interface] ---数据y---> [I/O bridge] ---数据y---> [Main memory]
                                                          |
                                                    主存接收数据 y...

第三步（图c）：主存从总线读取数据 y，存入地址 A

[Register file]
  %rax = y  （寄存器内容不变）
      |
[Bus interface] <----------  [I/O bridge] <-----------  [Main memory]
                                                          |
                                                     地址A处 = y  (写入完成!)

写事务完整时序图

读 vs 写 完整对比

读事务 movq A, %rax          写事务 movq %rax, A
──────────────────────        ──────────────────────
数据流向： 内存 -> CPU         数据流向： CPU -> 内存
步骤1: CPU 发地址 A           步骤1: CPU 发地址 A
步骤2: 内存取数据x放总线      步骤2: CPU 把数据y放总线
步骤3: CPU 读x存入%rax        步骤3: 内存读y存入地址A

二、磁盘存储（Disk Storage）

磁盘和内存的最大区别：容量 vs 速度

---

存储器	典型容量	访问时间	相对速度
SRAM（寄存器旁缓存）	几 MB	~纳秒级	最快
DRAM（主内存）	几 GB ~ 几十 GB	~几十纳秒	较快
磁盘（HDD）	几百 GB ~ 几 TB	~几毫秒	极慢

---

速度量化对比：

• 磁盘读取比 DRAM 慢约 $10^5$ 倍（慢 10万倍）
• 磁盘读取比 SRAM 慢约 $10^6$ 倍（慢 100万倍）
  $$\text{磁盘访问时间}\approx 10^5\times \text{DRAM访问时间}\approx 10^6\times \text{SRAM访问时间}$$

容量量化对比：

• DRAM 主内存：数百 MB ~ 数千 MB（即几 GB）
• 磁盘：数百 GB ~ 数千 GB（即几 TB）
  $$\text{磁盘容量}\approx 10^3\times \text{DRAM容量}$$

类比理解

把数据访问比作去不同地方取文件：
SRAM（缓存）：  文件就在桌子上，伸手就拿   -> 1秒
DRAM（内存）：  文件在隔壁房间，走几步拿   -> 几十秒
磁盘（硬盘）：  文件在城市另一头，开车去拿 -> 几天
这就是为什么程序员要关心"局部性"和缓存——
尽量让数据待在"桌子上"，而不是频繁去"城市另一头"取。

存储层次结构预览

速度  容量
快    小
|  [CPU寄存器]      访问时间: ~0.3 ns
|  [L1 Cache]       访问时间: ~1 ns
|  [L2 Cache]       访问时间: ~4 ns
|  [L3 Cache]       访问时间: ~10 ns
|  [主存 DRAM]      访问时间: ~60 ns
|  [磁盘 HDD]       访问时间: ~5-10 ms  (比DRAM慢10万倍!)
|  [网络存储/磁带]  访问时间: 秒级~分钟级
慢    大

三、总结

写事务三步的关键点：

1. 先告诉内存地址，内存准备好接收
2. 再传数据，数据从 CPU 流向内存
3. 内存落盘（写入DRAM），事务完成
   磁盘存储的关键点：

• 磁盘容量是内存的 $10^3$ 倍，但速度慢 $10^5$ 倍
• 这种巨大的速度鸿沟是存储层次结构（Memory Hierarchy）存在的根本原因
• 后续章节将介绍如何用缓存机制弥补这个差距

磁盘几何结构（Disk Geometry）— 通俗理解笔记

一、磁盘的物理组成层次

磁盘的结构从外到内，像一套俄罗斯套娃：

二、各组成部分详解

1. 盘片（Platter）

• 圆形薄片，表面涂有磁性材料（用来记录 0 和 1）
• 每个盘片有上下两个面，都可以存数据
• 多个盘片叠在一起，共用中心的**主轴（Spindle）**旋转
• 转速通常在 $5400\sim 15000$ RPM（每分钟转数）之间

单个盘片截面示意：
        上表面（Surface 0）  <- 可读写
   ========================
        下表面（Surface 1）  <- 可读写

2. 磁道（Track）

• 每个盘面上有若干同心圆环，每个圆环叫一条磁道
• 类比：就像黑胶唱片上的一圈圈纹路

单面磁道示意（俯视）：
        ┌─────────────────────┐
      ╱   ╔═══════════════╗    ╲
     │    ║  ╔═════════╗  ║     │
     │    ║  ║  主轴   ║  ║     │  <- 每圈就是一条磁道 Track
     │    ║  ╚═════════╝  ║     │
      ╲   ╚═══════════════╝    ╱
        └─────────────────────┘
  外圈磁道 k-1, k-2 ...  内圈磁道 k

3. 扇区（Sector）

• 每条磁道被切成若干弧段，每段叫一个扇区
• 每个扇区存储相同数量的数据位，通常是 512 字节
• 扇区之间有间隙（Gap），间隙里存的是格式化标识位（帮助磁头定位扇区边界），不存用户数据

单条磁道展开示意（Track k）：
 ┌──────┬──────┬──────┬──────┬──────┬──────┐
 │ 间隙 │扇区1 │ 间隙 │扇区2 │ 间隙 │扇区3 │ ...
 └──────┴──────┴──────┴──────┴──────┴──────┘
          512B          512B          512B
  Gap=格式化标识  Sector=用户数据

4. 主轴（Spindle）

• 贯穿所有盘片中心的转轴
• 带动所有盘片同步旋转
• 转速决定了数据能多快转到磁头下方

三、多盘片视图与柱面（Cylinder）

多盘片结构

3 个盘片叠在一起，产生 6 个可用面：

               主轴
                |
    ────────────|────────────   Surface 0 (Platter 0 上面)
    ════════════|════════════   Platter 0
    ────────────|────────────   Surface 1 (Platter 0 下面)
                |
    ────────────|────────────   Surface 2 (Platter 1 上面)
    ════════════|════════════   Platter 1
    ────────────|────────────   Surface 3 (Platter 1 下面)
                |
    ────────────|────────────   Surface 4 (Platter 2 上面)
    ════════════|════════════   Platter 2
    ────────────|────────────   Surface 5 (Platter 2 下面)
                |
              (底部)

柱面（Cylinder）的概念

柱面 k = 所有盘面上编号为 k 的磁道的集合。
因为每个盘面上的磁道都按同样方式编号，所以从侧面看，这些等距磁道连起来恰好构成一个圆柱形，故称"柱面"。

柱面 k 侧视示意（3盘片，6面）：
主轴
 |
 |===[ Surface 0 的 Track k ]===
 |
 |===[ Surface 1 的 Track k ]===    <- 这6条Track k
 |                                      合在一起 = 柱面 k
 |===[ Surface 2 的 Track k ]===
 |
 |===[ Surface 3 的 Track k ]===
 |
 |===[ Surface 4 的 Track k ]===
 |
 |===[ Surface 5 的 Track k ]===
 |

柱面的实际意义：读写头移动到某个半径位置时，可以同时访问所有盘面上的同一圈磁道（即整个柱面），减少磁头移动次数，提升效率。

四、容量计算公式

磁盘总容量由以下参数决定：
$$\text{总容量}=\text{盘面数}\times \text{每面磁道数}\times \text{每道扇区数}\times \text{每扇区字节数}$$
例如，一块磁盘有以下参数：

参数	数值
盘片数	3（共 6 个面）
每面磁道数	10,000 条
每道扇区数	400 个
每扇区大小	512 字节

---

$$\text{总容量}=6\times 10000\times 400\times 512\text{ B}=12,288,000,000\text{ B}\approx 12\text{ GB}$$

五、类比总结

---

磁盘概念	生活类比
磁盘（Disk Drive）	整栋图书馆大楼
盘片（Platter）	每一层楼
表面（Surface）	每层楼的地板和天花板（两面都能放书）
磁道（Track）	每面上的一排排书架（同心圆）
扇区（Sector）	书架上的一格（存 512 字节）
间隙（Gap）	书架之间的通道（存标识，不放书）
柱面（Cylinder）	每层楼同一位置书架的垂直集合
主轴（Spindle）	大楼中央的电梯井（带动旋转）

---

磁盘操作、访问时间与逻辑块 — 通俗理解笔记

一、磁盘读写的物理过程

核心部件

         主轴（Spindle）
              |
    ──────────|──────────   <- 盘片（Platter）旋转
              |
         [磁头 Head] <── 悬浮在盘面上方约 0.1 微米
              |
         [机械臂 Arm] <── 沿径向来回摆动，定位磁道
              |
         [执行器 Actuator]

磁头的惊人参数

磁头在盘面上方"飞行"，而非直接接触：

• 飞行高度：约 $0.1$ 微米（$=0.0001$ 毫米）
• 飞行速度：约 $80$ km/h
  类比：相当于把一栋摩天大楼横放，以离地 $2.5$ cm 的高度绕地球飞行，绕一圈只需 $8$ 秒！在这个精度下，盘面上一粒灰尘就像一块巨石。

如果磁头撞上灰尘颗粒，就会发生磁头碰撞（Head Crash），直接撞毁盘面。这就是为什么磁盘必须密封在真空包装中。

多盘片时的磁头运动

二、磁盘访问时间的三个组成部分

读取一个扇区的总时间 = 寻道时间 + 旋转延迟 + 传输时间
$$T_{access}=T_{avg\_seek}+T_{avg\_rotation}+T_{avg\_transfer}$$

时间线示意：
磁头移动到目标磁道     等待目标扇区转过来      读取扇区数据
|←── 寻道时间 ──────→|←── 旋转延迟 ─────────→|←── 传输时间 →|
   (3~9 ms 平均)          (约 4 ms)              (约 0.02 ms)

1. 寻道时间（Seek Time）$T_{seek}$

• 机械臂把磁头径向移动到目标磁道所需的时间
• 取决于：磁头当前位置 + 机械臂移动速度
• 平均寻道时间 $T_{avg\_seek}$：约 $3\sim 9$ ms
• 最大寻道时间 $T_{max\_seek}$：可达 $20$ ms

2. 旋转延迟（Rotational Latency）$T_{rotation}$

磁头到位后，需要等待目标扇区旋转到磁头正下方。
最坏情况：磁头刚好错过目标扇区，需等待磁盘转完整整一圈：
$$T_{max\_rotation}=\frac{1}{\text{RPM}}\times \frac{60\text{ s}}{1\text{ min}}$$
平均旋转延迟（平均等半圈）：
$$T_{avg\_rotation}=\frac{1}{2}\times T_{max\_rotation}$$

3. 传输时间（Transfer Time）$T_{transfer}$

目标扇区的第一个位到达磁头后，开始实际读/写数据所需的时间。
$$T_{avg\_transfer}=\frac{1}{\text{RPM}}\times \frac{1}{\text{每道平均扇区数}}\times \frac{60\text{ s}}{1\text{ min}}$$

三、计算示例（教材原题）

磁盘参数：

参数	值
转速	7,200 RPM
平均寻道时间 $T_{avg\_seek}$	9 ms
每道平均扇区数	400

---

第一步：计算平均旋转延迟
$$T_{avg\_rotation}=\frac{1}{2}\times T_{max\_rotation}=\frac{1}{2}\times \frac{60}{7200}\times 1000\approx 4\text{ ms}$$
第二步：计算平均传输时间
$$T_{avg\_transfer}=\frac{60}{7200}\times \frac{1}{400}\times 1000\approx 0.02\text{ ms}$$
第三步：求总访问时间
$$T_{access}=T_{avg\_seek}+T_{avg\_rotation}+T_{avg\_transfer}$$
$$=9+4+0.02=13.02\text{ ms}$$

四、重要结论

结论1：寻道和旋转延迟主导访问时间

访问时间构成（饼图式示意）：
寻道时间   9.00 ms  ████████████████████████████████  69%
旋转延迟   4.00 ms  ██████████████                    31%
传输时间   0.02 ms  |                                  <1%
                    ↑
              传输时间几乎可忽略不计！

含义：读一个扇区的前512字节很贵（需等磁头就位），但一旦开始读，剩余字节几乎"免费"。所以磁盘操作应尽量顺序读写大块数据，避免随机小量访问。

结论2：粗略估算公式

由于寻道时间和旋转延迟数量级相近：
$$T_{access}\approx 2\times T_{avg\_seek}$$

结论3：磁盘 vs 内存的速度鸿沟

读一个 512 字节扇区大小的块：

存储器	读取时间	相对磁盘
SRAM	$\approx 256$ ns	约快 40,000 倍
DRAM	$\approx 4000$ ns	约快 2,500 倍
磁盘	$\approx 10$ ms	基准

---

$$T_{disk}\approx 40000\times T_{SRAM}\approx 2500\times T_{DRAM}$$

五、练习题 6.3 解答

参数：转速 12,000 RPM，$T_{avg\_seek}=5$ ms，每道 300 扇区
$$T_{avg\_rotation}=\frac{1}{2}\times \frac{60}{12000}\times 1000=2.5\text{ ms}$$
$$T_{avg\_transfer}=\frac{60}{12000}\times \frac{1}{300}\times 1000\approx 0.017\text{ ms}$$
$$T_{access}=5+2.5+0.017\approx 7.5\text{ ms}$$

六、逻辑磁盘块（Logical Disk Blocks）

为什么需要逻辑块？

真实磁盘结构极其复杂：多个盘面、不同记录区、物理扇区编址繁琐。操作系统不想关心这些细节。
解决方案：磁盘控制器（Disk Controller）把物理结构抽象成一个简单的线性序列：
$$\text{逻辑块}0,1,2,3,\dots ,B-1$$
每个逻辑块 = 一个扇区大小（通常 512 字节）。

逻辑块 -> 物理扇区的映射流程

磁盘控制器的作用总结

操作系统视角：  [逻辑块 0][逻辑块 1][逻辑块 2] ...  (简单线性数组)
                          |
                    [磁盘控制器] <- 负责翻译和调度
                          |
物理磁盘视角：  (盘面2, 磁道47, 扇区13) 等复杂物理地址

七、格式化容量（补充说明）

磁盘出厂前必须先格式化：

• 在扇区间隙写入标识信息
• 标记有缺陷的柱面，将其隔离
• 预留若干备用柱面（spare cylinders），以备某柱面损坏时替换
  因此：
  $$\text{实际可用容量}<\text{标称最大容量}$$
  厂商报的"格式化容量"已去掉了备用区，比物理极限容量要小一些。

八、练习题 6.4 解答思路

磁盘参数：13,000 RPM，$T_{avg\_seek}=6$ ms，每道 5,000 扇区，4 个盘面，扇区 512 字节。
文件大小：1 MB = $1\times 1024\times 1024/512=2048$ 个逻辑块。
$$T_{avg\_rotation}=\frac{1}{2}\times \frac{60}{13000}\times 1000\approx 2.31\text{ ms}$$
$$T_{avg\_transfer}=\frac{60}{13000}\times \frac{1}{5000}\times 1000\approx 0.00092\text{ ms}$$
A. 最优情况（顺序映射）：
第一个块：$T_{avg\_seek}+T_{avg\_rotation}+T_{avg\_transfer}=6+2.31+0.00092\approx 8.31$ ms
后续块连续排列在同一磁道，每块只需传输时间：
$$T_{best}=(T_{avg\_seek}+T_{avg\_rotation}+T_{avg\_transfer})+(2048-1)\times T_{avg\_transfer}$$
$$\approx 8.31+2047\times 0.00092\approx 8.31+1.88\approx 10.19\text{ ms}$$
B. 随机情况（随机映射）：
每块都需要重新寻道和等待旋转：
$$T_{random}=2048\times (T_{avg\_seek}+T_{avg\_rotation}+T_{avg\_transfer})$$
$$\approx 2048\times 8.31\approx 17,019\text{ ms}\approx 17\text{ s}$$
对比结论：顺序读取约 $10$ ms，随机读取约 $17$ 秒，相差约 1700 倍！这就是为什么程序的空间局部性对磁盘 I/O 性能至关重要。

I/O 设备连接与 I/O 总线 — 通俗理解笔记

一、三条总线的整体架构

计算机系统中存在三个层次的总线，速度依次降低，但连接的设备类型越来越多样：

+------------------CPU------------------+
|  [寄存器文件]  [ALU]                  |
|       |                               |
|  [Bus interface 总线接口]             |
+-----------+---------------------------+
            |
       系统总线（System Bus）  <- 最快，CPU专用
            |
       [I/O bridge  I/O桥]  <- 翻译器+路由器
            |          |
       内存总线      I/O总线（I/O Bus） <- 较慢，但设备无关
     （Memory Bus）      |
            |     ┌─────┼──────┬──────────┐
       [主存 DRAM] │     │      │          │
               [USB] [显卡] [主机总线   [扩展槽]
               控制器  适配器  适配器     网卡等
                          SCSI/SATA]
                              |
                         [磁盘控制器]
                              |
                          [硬盘]

三条总线对比

---

总线	速度	特点	连接对象
系统总线（System Bus）	最快	CPU专用，厂商定制	CPU <-> I/O bridge
内存总线（Memory Bus）	快	专用于内存访问	I/O bridge <-> 主存
I/O 总线（I/O Bus）	较慢	与CPU无关，通用标准	各类外设

---

关键点：I/O 总线的设计与底层 CPU 无关，所以同一块显卡、硬盘可以用在不同品牌的 CPU 平台上，这就是"通用性"的来源。

二、I/O 总线上挂载的三类设备

1. USB 控制器（USB Controller）

作用：作为所有 USB 设备的"集线枢纽"，一个控制器可以连接多个 USB 设备。
连接的典型设备：

• 键盘、鼠标
• 数码相机、游戏手柄、打印机
• 外置硬盘、固态硬盘（SSD）
• 调制解调器
  USB 带宽演进：

---

版本	最大带宽
USB 3.0	$625$ MB/s
USB 3.1	$1250$ MB/s

---

USB 控制器的角色：
I/O 总线
   |
[USB 控制器] ──── USB 总线 ────┬── 鼠标
                               ├── 固态硬盘
                               └── 键盘

2. 显卡（Graphics Adapter / Graphics Card）

作用：代替 CPU 完成屏幕像素的绘制工作，包含专用硬件和固件逻辑。

CPU 告诉显卡"画什么"
      |
  [显卡 GPU]  <- 负责把指令转化成每一个像素的颜色值
      |
  [显示器]    <- 把像素呈现给用户

显卡承担了大量图形计算，解放了 CPU，让 CPU 专注于逻辑运算。

3. 主机总线适配器（Host Bus Adapter，SCSI/SATA）

作用：把磁盘连接到 I/O 总线，相当于磁盘和总线之间的"接头翻译器"。
两种主流接口对比：

接口	发音	速度	价格	支持磁盘数
SCSI	“scuzzy”	较快	较贵	支持多块磁盘
SATA	“sat-uh”	较慢	较便宜	只支持一块磁盘

---

主机总线适配器的角色：
I/O 总线
   |
[主机总线适配器 SCSI/SATA]
   |
[磁盘控制器]  <- 内置在磁盘驱动器包装内
   |
[磁盘盘片]   <- 实际的物理存储介质

4. 扩展槽（Expansion Slots）

主板上预留的空槽，可以插入额外的适配器卡，直接连接到 I/O 总线：

• 网络适配器（网卡）
• 声卡
• 其他专用设备

三、完整层次结构图（Mermaid）

四、类比理解

把整个系统比作一个城市交通网络：

计算机部件	城市交通类比
CPU	市政府（决策中心）
系统总线	市政专用高速公路（仅政府车辆）
I/O bridge	高速公路收费站+换乘枢纽
内存总线	仓库专用通道（连接大型货仓）
I/O 总线	城市主干道（各类车辆都能走）
USB 控制器	小区门口的快递柜（汇聚多个快递）
显卡	广告部门（专门负责输出视觉内容）
SCSI/SATA 适配器	港口装卸码头（对接大型货船=磁盘）
扩展槽	预留的停车位（随时可加新设施）

---

五、为什么 I/O 总线比系统总线慢？

这是一种设计权衡：

系统总线：速度优先，为CPU量身定制，改一个CPU就得换总线设计
I/O 总线：兼容优先，统一标准让所有外设厂商都能接入，
          代价是速度相对较低
速度层次：
系统总线 > 内存总线 > I/O总线
  快                      慢
  窄（只连少数部件）       宽（连接各类设备）

这也是为什么显卡、网卡等高速设备现代都改用 PCIe（PCI Express）总线——它是一种高速版的 I/O 总线，专为需要大带宽的设备设计。

磁盘访问、DMA 与中断机制 — 通俗理解笔记

一、CPU 读取磁盘的完整过程（三步走）

CPU 读磁盘数据，不是直接搬运数据，而是"下命令，然后去忙别的，等通知"。整个过程分三个阶段：

二、阶段一：内存映射 I/O（Memory-Mapped I/O）

什么是内存映射 I/O？

CPU 和 I/O 设备通信，使用的技术叫内存映射 I/O：

• 系统地址空间中，划出一段地址专门给 I/O 设备使用
• 每个地址叫一个 I/O 端口（I/O Port）
• 设备挂载到总线时，就被分配到一个或多个端口
  类比：就像一栋大楼里，1-100 层住人（主存），101-110 层是邮件收发室（I/O 端口）。CPU 只需往对应楼层"投信"，设备就能收到命令。

以磁盘控制器为例（端口 0xa0）

CPU 发起一次磁盘读，需要向 0xa0 连续写入三条 store 指令：

地址 0xa0 的三次写入：
第1次写：命令字（"开始读！是否读完后中断CPU？"）
第2次写：逻辑块号（"读第几号逻辑块？"）
第3次写：目标内存地址（"读出来的数据放到主存的哪个位置？"）

对应的 C++ 概念演示（非真实系统代码，仅帮助理解）：

#include <cstdint>
#include <iostream>
// 模拟内存映射 I/O 的概念（真实系统需要特权指令，这里仅作示意）
// 假设磁盘控制器映射到地址 0xa0
// I/O 端口的"寄存器"结构
struct DiskControllerPort {
    uint32_t command;       // 命令寄存器：写入读/写命令
    uint32_t block_number;  // 逻辑块号寄存器
    uint64_t mem_addr;      // 目标主存地址寄存器
};
// 模拟 CPU 向磁盘控制器发起读请求
void cpu_issue_disk_read(
    DiskControllerPort* port,  // I/O 端口（映射到 0xa0）
    uint32_t logical_block,    // 要读的逻辑块号
    uint64_t dest_addr         // 数据写入主存的地址
) {
    // 第1条 store：写命令字
    // 命令 = 0x01 表示"读"，0x80 表示"完成后中断CPU"
    port->command = 0x01 | 0x80;
    // 第2条 store：写逻辑块号
    port->block_number = logical_block;
    // 第3条 store：写目标内存地址
    port->mem_addr = dest_addr;
    // CPU 发完命令就去做别的事情了，不在这里等待！
    std::cout << "命令已发送，CPU继续执行其他指令..." << std::endl;
}
int main() {
    // 模拟：请求读取逻辑块 42，数据存入主存地址 0x10000
    DiskControllerPort fake_port{};
    cpu_issue_disk_read(&fake_port, 42, 0x10000);
    // 实际系统中，CPU此后会去执行其他指令，等中断到来
    return 0;
}

https://godbolt.org/z/3s67oahaM

三、阶段二：DMA 直接内存访问（Direct Memory Access）

什么是 DMA？

DMA = Direct Memory Access（直接内存访问）
核心思想：磁盘控制器自己把数据直接搬进主存，不需要 CPU 参与搬运。

没有 DMA 的情况（低效）：
磁盘 -> 磁盘控制器 -> CPU 寄存器 -> 主存
                        ↑
                  CPU 要亲自搬每一个字节，浪费算力
有 DMA 的情况（高效）：
磁盘 -> 磁盘控制器 ----DMA----> 主存
                        ↑
                  CPU 完全不参与数据搬运！
                  CPU 可以同时做其他计算

CPU 有多宝贵？

一颗 $1$ GHz 的处理器，时钟周期为 $1$ ns，在磁盘读取的 $16$ ms 内，理论上可以执行：
$$\text{可执行指令数}=\frac{16\times 10^{-3}\text{ s}}{1\times 10^{-9}\text{ s/指令}}=16,000,000\text{ 条指令}$$
如果 CPU 傻等磁盘，就白白浪费了 1600 万条指令的执行机会！DMA 正是为了解决这个问题而生的。

四、阶段三：中断（Interrupt）

什么是中断？

DMA 传输完成后，磁盘控制器需要告知 CPU"数据已就绪"，用的机制叫中断（Interrupt）：

中断信号的传递路径：
[磁盘控制器] --中断信号--> [CPU芯片外部引脚] --> CPU暂停当前工作
                                                        |
                                                 跳转到OS中断处理程序
                                                        |
                                               记录"磁盘I/O完成"
                                                        |
                                               返回被打断的位置继续执行

中断 vs 轮询（Polling）

---

方式	做法	效率
轮询（Polling）	CPU 不断询问"好了吗？好了吗？"	极低，CPU 被占满
中断（Interrupt）	CPU 去忙别的，设备完成后主动通知	高效，CPU 不浪费

---

类比：等快递时——轮询是每隔 5 分钟下楼看一次；中断是快递到了主动打电话通知你。

五、完整流程 ASCII 示意

时间轴（向右为时间流逝）
CPU:   [发命令]──[做其他工作 A]──[做其他工作 B]──[收中断，处理完成]──[继续...
磁盘:            [寻道]──[旋转等待]──[读扇区]──[DMA传输到主存]──[发中断]
主存:                                                 [接收DMA数据写入]

六、PCI vs PCIe 总线演进

---

总线	类型	最大吞吐量	特点
PCI（旧）	共享总线，所有设备共用	$533$ MB/s	一次只能一个设备使用总线
PCIe（新）	点对点串行链路+交换机	$16$ GB/s	快约 $30$ 倍，类似交换式以太网

---

$$\frac{16\text{ GB/s}}{533\text{ MB/s}}\approx 30\text{ 倍}$$
PCIe 的结构更像网络交换机，每个设备有独立通道，互不干扰，带宽大幅提升。

七、真实商业磁盘参数（Seagate Barracuda 7400）

---

参数	值
盘面直径	3.5 英寸
格式化容量	3 TB
盘片数	3
表面数	6
逻辑块总数	5,860,533,168
逻辑块大小	512 字节
转速	7,200 RPM
平均旋转延迟	4.16 ms
平均寻道时间	8.5 ms
磁道间寻道时间	1.0 ms
平均传输速率	156 MB/s
最大持续传输速率	210 MB/s

---

验证平均旋转延迟：
$$T_{avg\_rotation}=\frac{1}{2}\times \frac{60}{7200}\times 1000=\frac{1}{2}\times 8.33=4.17\text{ ms}$$
与手册标注的 $4.16$ ms 完全吻合。
估算平均访问时间：
$$T_{access}\approx T_{avg\_seek}+T_{avg\_rotation}=8.5+4.16\approx 12.7\text{ ms}$$
（传输时间相对极小，可忽略不计）

八、知识点总结

三个核心概念：

• 内存映射 I/O：用普通的内存地址（I/O 端口）和设备通信，简洁统一
• DMA：设备自主搬运数据，CPU 解放出来做有用的计算
• 中断：设备完成后主动通知 CPU，避免 CPU 空转等待

固态硬盘（SSD）原理与寿命计算 — 通俗理解笔记

一、SSD 是什么？

SSD（Solid State Disk，固态硬盘）是基于**闪存（Flash Memory）**的存储设备。
它插入标准磁盘插槽（USB 或 SATA），对外表现得和普通机械硬盘完全一样——CPU 发来"读/写第 N 号逻辑块"的请求，SSD 乖乖处理，操作系统根本感知不到差别。

SSD 内部结构

I/O 总线
    |
    v
+----------------------------------SSD 封装----------------------------------+
|                                                                            |
|              [Flash Translation Layer  闪存翻译层]                        |
|               相当于机械硬盘里的"磁盘控制器"                              |
|               负责：逻辑块号 -> 物理页地址 的映射                         |
|                          |                                                 |
|   +--------------------闪存芯片---------------------------------+          |
|   |                                                             |          |
|   |  Block 0              Block 1    ...    Block B-1           |          |
|   | [P0|P1|...|P(P-1)]  [P0|P1|...|P(P-1)] [P0|P1|...|P(P-1)] |          |
|   |                                                             |          |
|   +-------------------------------------------------------------+          |
+----------------------------------------------------------------------------+

层次结构

典型参数：

• 页大小：$512$ 字节 ~ $4$ KB
• 每块页数：$32$ ~ $128$ 页
• 块大小：$16$ KB ~ $512$ KB

二、SSD 读写规则（关键！）

这是理解 SSD 一切特性的基础：

读：以"页"为单位读取，直接读，快
写：以"页"为单位写入，但有限制：
    ┌─────────────────────────────────────────────────┐
    │ 规则1：写一页之前，它所在的整个"块"必须先被擦除 │
    │ 规则2：一个块擦除后，其中每一页只能写一次       │
    │ 规则3：一个块大约经过 100,000 次写后就会磨损报废 │
    └─────────────────────────────────────────────────┘

类比理解

把 SSD 想象成一本铅笔写的草稿本：

• 读：随便翻到哪一页看，很快
• 写：必须先用橡皮把整页擦干净（实际是整个"块"），再写
• 磨损：橡皮擦了 10 万次之后，纸就破了，这一块报废

三、随机写为什么慢？两个原因

原因 1：擦除一个块很慢

$$T_{擦除块}\approx 1\text{ ms}$$
而访问一页只需约 $50\sim 60$ μs，擦除比访问慢超过一个数量级：
$$\frac{1\text{ ms}}{60\text{ μs}}\approx 16\text{ 倍}$$

原因 2：写有数据的页需要"搬家"

如果要写的目标页 $p$ 中已经有数据，不能直接覆盖，必须：

步骤示意：
旧块（含有效数据）：[P0: 旧数据A | P1: 旧数据B | P2: 目标页p | P3: 旧数据C]
                                                      ↑
                                               想写新数据到这里
必须先：
1. 找一个已擦除的空块（新块）
2. 把旧块中所有"有用的页"复制到新块：[P0:A | P1:B | P3:C]
3. 擦除旧块
4. 把新数据写入目标页 p
最终新块：[P0:A | P1:B | P2:新数据 | P3:C]

这个"搬家"过程叫做写放大（Write Amplification），大量随机写会频繁触发此过程。

四、SSD 性能参数（Intel SSD 730）

---

操作类型	指标	值
顺序读	吞吐量	$550$ MB/s
随机读	IOPS	$89,000$ 次/秒
随机读	吞吐量	$365$ MB/s
平均顺序读访问时间	—	$50$ μs
顺序写	吞吐量	$470$ MB/s
随机写	IOPS	$74,000$ 次/秒
随机写	吞吐量	$303$ MB/s
平均顺序写访问时间	—	$60$ μs

---

读比写快，随机写尤其慢于随机读，原因正是上节的擦除机制。

五、SSD vs 机械硬盘（HDD）对比

速度对比：
$$T_{SSD随机访问}\approx 50\text{ μs}\ll T_{HDD随机访问}\approx 10\text{ ms}$$
$$\frac{10\text{ ms}}{50\text{ μs}}=200\text{ 倍}$$
SSD 随机访问比机械硬盘快约 200 倍。

六、磨损均衡（Wear Leveling）

闪存翻译层中有磨损均衡逻辑：

• 不让某几个块频繁被擦写而提前报废
• 把擦写操作均匀分散到所有块上
• 使整块 SSD 的寿命最大化

没有磨损均衡：
Block 0: 擦写10万次 -> 报废  (其他块还几乎没用)
Block 1: 擦写10万次 -> 报废
整盘提前失效
有磨损均衡：
Block 0: 擦写~N次
Block 1: 擦写~N次
...
Block B-1: 擦写~N次          -> 所有块同时接近寿命极限，整盘寿命最大化

七、练习题 6.5：SSD 寿命计算

Intel 保证该 SSD 在报废前的总写入量为：
$$W_{total}=128\text{ PB}=128\times 10^{15}\text{ 字节}$$
换算公式：
$$\text{寿命（年）}=\frac{W_{total}}{\text{写入速率}\times \text{每年秒数}}$$
其中每年秒数：
$$1\text{ 年}=365\times 24\times 3600=31,536,000\text{ 秒}\approx 3.15\times 10^7\text{ 秒}$$

A. 最坏情况：顺序写，速率 $470$ MB/s

$$\text{寿命}=\frac{128\times 10^{15}\text{ B}}{470\times 10^6\text{ B/s}\times 3.15\times 10^7\text{ s/年}}$$
$$=\frac{1.28\times 10^{17}}{1.48\times 10^{16}}\approx 8.6\text{ 年}$$

B. 最坏情况：随机写，速率 $303$ MB/s

$$\text{寿命}=\frac{128\times 10^{15}\text{ B}}{303\times 10^6\text{ B/s}\times 3.15\times 10^7\text{ s/年}}$$
$$=\frac{1.28\times 10^{17}}{9.54\times 10^{15}}\approx 13.4\text{ 年}$$

随机写速率更慢，反而寿命更长（因为写入总字节数相同，速率慢则消耗时间更长）

C. 平均情况：每天写入 $20$ GB

每年写入量：
$$W_{year}=20\text{ GB/天}\times 365\text{ 天}=7300\text{ GB}=7.3\text{ TB}$$
$$\text{寿命}=\frac{128\times 10^{15}\text{ B}}{7.3\times 10^{12}\text{ B/年}}\approx 17,534\text{ 年}$$
实际使用中，SSD 的寿命极长，日常用户完全不需要担心写寿命问题。

寿命汇总对比

---

使用场景	写入速率	估算寿命
顺序写（最坏）	$470$ MB/s 持续	$\approx 8.6$ 年
随机写（次坏）	$303$ MB/s 持续	$\approx 13.4$ 年
日常使用（均值）	$20$ GB/天	$\approx 17,534$ 年

---

八、总结

SSD 核心要点：
结构：  I/O总线 -> 闪存翻译层 -> 闪存芯片（块->页）
读写规则：
  读：以页为单位，直接读，快（~50 μs）
  写：必须先擦整块，再写页；写有数据的页还需搬家
速度：  读 > 写；顺序 > 随机
寿命：  每块约10万次擦写；靠磨损均衡分摊到全盘
        日常使用寿命极长（万年量级）
vs HDD：随机访问快200倍；但贵30倍/字节，容量较小

存储技术趋势（Storage Technology Trends）— 通俗理解笔记

一、核心结论先读

提高密度（降低成本）容易，提高速度（降低访问时间）难。
这是整节最重要的一句话。30 年来，存储器的价格暴跌，但速度进步缓慢——而 CPU 的速度飞速提升，导致 CPU 和存储器之间的速度鸿沟越来越大。

二、各类存储技术 30 年趋势数据

(a) SRAM 趋势

---

指标	1985	1990	1995	2000	2005	2010	2015	变化倍数
价格（$/MB）	2,900	320	256	100	75	60	25	降低 116 倍
访问时间（ns）	150	35	15	3	2	1.5	1.3	降低 115 倍

---

特点：价格和速度同步改善，均提升约 $100$ 倍，步调一致。

(b) DRAM 趋势

---

指标	1985	1990	1995	2000	2005	2010	2015	变化倍数
价格（$/MB）	880	100	30	1	0.1	0.06	0.02	降低 44,000 倍
访问时间（ns）	200	100	70	60	50	40	20	降低 10 倍
典型容量（MB）	0.256	4	16	64	2,000	8,000	16,000	增大 62,500 倍

---

极度不对称：
$$\text{价格降低倍数}=44,000\gg \text{速度提升倍数}=10$$
价格降了 4 个数量级，速度只提升了 1 个数量级。

© 机械硬盘（HDD）趋势

---

指标	1985	1990	1995	2000	2005	2010	2015	变化倍数
价格（$/GB）	100,000	8,000	300	10	5	0.3	0.03	降低 3,333,333 倍
最小寻道时间（ms）	75	28	10	8	5	3	3	降低 25 倍
典型容量（GB）	0.01	0.16	1	20	160	1,500	3,000	增大 300,000 倍

---

更加极端：
$$\text{价格降低倍数}=3,333,333\gg \text{速度提升倍数}=25$$
价格降了 6 个数量级（百万倍），速度只提升了 25 倍！

(d) CPU 趋势

---

指标	1985	1990	1995	2000	2003	2005	2010	2015	变化倍数
Intel CPU	80286	80386	Pent.	P-III	Pent.4	Core 2	Core i7(n)	Core i7(h)	—
时钟频率（MHz）	6	20	150	600	3,300	2,000	2,500	3,000	500 倍
时钟周期（ns）	166	50	6	1.6	0.3	0.5	0.4	0.33	500 倍
核心数	1	1	1	1	1	2	4	4	—
等效周期（ns）	166	50	6	1.6	0.30	0.25	0.10	0.08	2,075 倍

---

等效周期 = 单核时钟周期 ÷ 核心数，反映整体吞吐能力：
$$\text{等效周期改善倍数}=\frac{166\text{ ns}}{0.08\text{ ns}}\approx 2,075\text{ 倍}$$

三、速度鸿沟的直观对比

1985 年：各部件速度差距
CPU周期:   166 ns
SRAM:      150 ns  <- 几乎追平CPU
DRAM:      200 ns  <- 略慢
磁盘:      75 ms   <- 已经差很多
2015 年：速度鸿沟急剧扩大
CPU等效周期:  0.08 ns
SRAM:         1.3 ns   <- 慢 ~16 倍，还能跟上
DRAM:         20 ns    <- 慢 ~250 倍，差距在拉大
磁盘寻道:     3 ms     <- 慢 ~37,500,000 倍，已经天壤之别

速度鸿沟量化（2015 年）：
$$\frac{T_{DRAM}}{T_{CPU}}=\frac{20\text{ ns}}{0.08\text{ ns}}=250\text{ 倍}$$
$$\frac{T_{磁盘}}{T_{CPU}}=\frac{3\times 10^6\text{ ns}}{0.08\text{ ns}}\approx 37,500,000\text{ 倍}$$

四、趋势图（ASCII 半对数示意）

访问时间（对数轴，越下越快）
1985    1990    1995    2000    2005    2010    2015
  |       |       |       |       |       |       |
  |   磁盘寻道时间（ms级）
  |-----------------------------------------------→ 缓慢下降（只快了25倍）
  |
  |   DRAM访问时间（ns~μs级）
  |   ·····································→ 缓慢下降（只快了10倍）
  |
  |   SRAM访问时间（ns级）
  |     ···························→ 中速下降（快了115倍）
  |
  |   CPU时钟周期（ns级）
  |         ·················→ 快速下降（快了500倍）
  |
  |   CPU等效周期（考虑多核）
  |           ·············→ 极速下降（快了2075倍）
  ↓（更快）

结论：SRAM 勉强跟上 CPU，DRAM 和磁盘的速度差距越来越大。

五、为什么 2003 年是拐点？

2003 年前后，多核处理器登场：

2003年前：CPU速度提升靠提高单核频率
          性能瓶颈 = 延迟（单核访存时间）
2003年后：CPU靠增加核心数提升吞吐
          性能瓶颈 = 吞吐量（多核同时发请求，内存/磁盘带宽跟不上）

Pentium 4（2003）主频达 $3.3$ GHz 后，单核频率几乎到了物理极限（发热、功耗），于是转向多核。Core 2 开始出现 2 核，Core i7 达到 4 核，使得等效周期进一步缩短，但 DRAM/磁盘带宽成为新瓶颈。

六、解决方案：SRAM 缓存

面对 CPU 和内存之间的速度鸿沟，现代计算机的应对策略是：

这种方案有效的前提是程序具有局部性（Locality）——即程序倾向于反复访问最近使用过的数据和附近的数据。

七、练习题 6.6：何时能用 $200 买到 1 PB 硬盘？

数据提取

从 2005 到 2015 的磁盘价格数据：

年份	价格（$/GB）
2005	5
2010	0.3
2015	0.03

---

计算价格下降速率

2005 → 2015（10年）：
$$\text{降低倍数}=\frac{5}{0.03}\approx 166.7\text{ 倍}$$
等效为每年降低的比例（按等比数列）：
$$r={\left(\frac{0.03}{5}\right)}^{1/10}=(0.006{)}^{0.1}\approx 0.631$$
即每年价格变为上一年的约 $63.1\%$，每年降约 $36.9\%$。

目标：1 PB 花费 $200

$$1\text{ PB}=10^{15}\text{ B}=10^6\text{ GB}$$
目标价格：
$$\frac{\$200}{10^6\text{ GB}}=2\times 10^{-4}\text{ \$/GB}$$
以 2015 年（$0.03$ $/GB）为基准，设经过 $n$ 年后达到目标：
$$0.03\times (0.631{)}^n=2\times 10^{-4}$$
$$(0.631{)}^n=\frac{2\times 10^{-4}}{0.03}=6.67\times 10^{-3}$$
两边取对数：
$$n\times \ln (0.631)=\ln (6.67\times 10^{-3})$$
$$n=\frac{\ln (6.67\times 10^{-3})}{\ln (0.631)}=\frac{-5.01}{-0.461}\approx 10.9\text{ 年}$$
$$\text{目标年份}\approx 2015+11=2026\text{ 年}$$

按照 2005-2015 的价格下降趋势外推，大约在 2026 年前后，$200 可以买到 1 PB 的机械硬盘存储。

八、总结：一张图看清所有趋势

指标          1985→2015 改善倍数    性质
SRAM 价格      116 倍降低           价格和速度同步
SRAM 速度      115 倍提升
DRAM 价格    44,000 倍降低          价格远超速度
DRAM 速度       10 倍提升
磁盘 价格  3,333,333 倍降低         价格远超速度（更极端）
磁盘 速度       25 倍提升
CPU 速度        500 倍提升          单核
CPU 等效      2,075 倍提升          多核总吞吐

核心规律：

• 提高密度（塞更多位）很容易 → 价格暴跌
• 提高速度（更快响应）很难 → 访问时间改善缓慢
• CPU 越来越快，DRAM/磁盘越来越跟不上 → 缓存层次结构的价值日益重要

局部性原理（Locality）— 通俗理解笔记

一、什么是局部性？

局部性原理：写得好的程序倾向于反复访问最近用过的或附近的数据，而不是随机跳跃访问内存。
局部性分两种：

生活类比

---

局部性类型	类比
时间局部性	你今天查了某本字典，明天可能还会查同一本字典
空间局部性	你查了字典第 100 页，接下来可能查第 101、102 页

---

二、为什么局部性很重要？

局部性是整个**存储层次结构（缓存机制）**能够工作的根本原因：

如果程序访问完全随机：
  每次访问都需要从慢速内存/磁盘取数据
  缓存没有意义，速度极慢
如果程序有好的局部性：
  最近用过的数据大概率还在快速缓存里
  下次访问直接命中缓存，极快

局部性在各个系统层级都被利用：

层级	如何利用局部性
硬件（CPU）	Cache 缓存最近用过的指令和数据
操作系统	用主存缓存最近访问的虚拟地址页和磁盘块
应用程序	浏览器缓存最近浏览的网页到本地磁盘
Web 服务器	前端磁盘缓存热门文档，无需每次访问后端

---

三、多核处理器的"功耗墙"（补充背景）

CPU 功耗公式：
$$P=f\cdot C\cdot V^2$$
其中 $f$ 是时钟频率，$C$ 是电容（正比于芯片面积），$V$ 是电压。
2003 年前后，提高 $f$ 导致 $P$ 超出散热极限（功耗墙），于是厂商转向多核：

• 把一个大核变成多个小核，总面积不变（$C$ 不变）
• 每个核频率降低，但多核并行，等效性能继续提升
• 2004 年双核，2007 年四核，此后核心数持续增加
  $$\text{等效性能}\propto \text{核心数}\times \text{单核频率}$$

四、示例代码分析（sumvec 函数）

原始代码（C 风格）

#include <iostream>
// N 个元素的向量求和函数
// 这是局部性的教科书级别好例子
int sumvec(int v[], int N)
{
    int i, sum = 0;           // sum：时间局部性极好（每次循环都访问）
    for (i = 0; i < N; i++)   // i：时间局部性极好（每次循环都访问）
        sum += v[i];           // v[i]：空间局部性极好（顺序访问相邻地址）
    return sum;
}
int main()
{
    const int N = 8;
    int v[N] = {10, 20, 30, 40, 50, 60, 70, 80};
    int result = sumvec(v, N);
    std::cout << "sum = " << result << std::endl;  // 输出：sum = 360
    return 0;
}

局部性分析

变量 sum 的时间局部性：

循环第1次：读sum(=0),  写sum(=v[0])
循环第2次：读sum,      写sum(=sum+v[1])
循环第3次：读sum,      写sum(=sum+v[2])
...
sum 每次都被访问 -> 时间局部性极好 -> 会常驻寄存器，速度极快

变量 i 的时间局部性：

每次循环都读写 i -> 时间局部性极好 -> 常驻寄存器

数组 v[] 的空间局部性：

内存布局（每个 int 占 4 字节）：
地址:    0    4    8   12   16   20   24   28
内容:   v[0] v[1] v[2] v[3] v[4] v[5] v[6] v[7]
访问顺序: 1    2    3    4    5    6    7    8
-> 按地址顺序，从低到高，步长=4字节
-> 空间局部性极好（步长 = 1个元素大小，称为"步长-1访问模式"）

步长-1（stride-1）访问模式是空间局部性最好的情况：
$$\text{步长}=\frac{\text{相邻两次访问的地址差}}{\text{元素大小}}=\frac{4\text{ 字节}}{4\text{ 字节}}=1$$
步长越小，空间局部性越好；步长越大，缓存命中率越低。

五、好局部性 vs 差局部性的完整对比代码

#include <iostream>
// =============================================
// 示例1：好的空间局部性（行优先访问二维数组）
// =============================================
// C/C++ 中，二维数组按"行优先"存储：
// a[0][0], a[0][1], a[0][2], a[1][0], a[1][1], ...
// 行优先访问 = 顺序访问内存 = 步长-1 = 空间局部性好
int sumarray_row_major(int a[][3], int rows)
{
    int i, j, sum = 0;
    for (i = 0; i < rows; i++)       // 外层循环：行
        for (j = 0; j < 3; j++)      // 内层循环：列（顺序访问同一行）
            sum += a[i][j];           // 访问顺序：a[0][0]->a[0][1]->a[0][2]->a[1][0]...
                                      // 每次跨越 4 字节，步长=1，缓存友好
    return sum;
}
// =============================================
// 示例2：差的空间局部性（列优先访问二维数组）
// =============================================
// 列优先访问 = 每次跳过一整行 = 步长大 = 空间局部性差
int sumarray_col_major(int a[][3], int rows)
{
    int i, j, sum = 0;
    for (j = 0; j < 3; j++)          // 外层循环：列
        for (i = 0; i < rows; i++)   // 内层循环：行（每次跳一整行）
            sum += a[i][j];           // 访问顺序：a[0][0]->a[1][0]->a[2][0]->a[0][1]...
                                      // 每次跨越 3*4=12 字节，步长=3，缓存不友好
    return sum;
}
int main()
{
    // 3x3 矩阵，按行优先存储在内存中：
    // 地址低 -> 高：[1,2,3,4,5,6,7,8,9]
    int a[3][3] = {{1, 2, 3},
                   {4, 5, 6},
                   {7, 8, 9}};
    // 两种方式结果相同，但性能差异巨大（矩阵越大越明显）
    std::cout << "行优先（好局部性）sum = " << sumarray_row_major(a, 3) << std::endl;
    std::cout << "列优先（差局部性）sum = " << sumarray_col_major(a, 3) << std::endl;
    return 0;
}

内存访问顺序对比（ASCII）

内存中 a[3][3] 的存储布局（行优先）：
地址:  0    4    8   12   16   20   24   28   32
内容: a00  a01  a02  a10  a11  a12  a20  a21  a22
行优先访问顺序（好）：
  1→2→3→4→5→6→7→8→9
  每步 +4 字节，完全顺序
列优先访问顺序（差）：
  a00→a10→a20→a01→a11→a21→a02→a12→a22
  地址跳跃：0→12→24→4→16→28→8→20→32
  每步 +12 字节，跨行跳跃，缓存频繁失效

六、局部性总结

判断局部性好坏的快速规则：
时间局部性：
  变量被循环反复访问？  -> 好
  变量只用一次？        -> 无时间局部性
空间局部性：
  按顺序访问数组？      -> 好（步长-1）
  跳跃访问数组？        -> 差（步长大）
  访问结构体各字段？    -> 好（字段相邻存储）
  随机访问指针链表？    -> 差（节点分散在堆上）

编程建议：

• 优先使用顺序遍历，避免大步长跳跃
• 嵌套循环访问二维数组时，内层循环遍历列（C/C++ 行优先）
• 把循环中频繁使用的变量保存在局部变量（促进编译器放入寄存器）

内存局部性详解：空间局部性与步长访问模式

一、核心概念回顾

什么是局部性（Locality）？

程序在访问内存时，往往存在"局部性"现象：

• 时间局部性（Temporal Locality）：一个数据被访问过之后，很快还会被再次访问。
  • 例：循环中的累加变量 sum，每次循环都要读写它。
• 空间局部性（Spatial Locality）：一个数据被访问后，它附近的数据也很快会被访问。
  • 例：按顺序读数组元素，读了 a[0] 后紧接着读 a[1]。
    局部性好的程序，缓存命中率高，运行速度更快。

二、二维数组在内存中的存储方式

C 语言的二维数组按**行主序（Row-Major Order）**存储。
以 int a[2][3]（M=2行，N=3列）为例，内存布局如下：

地址:   0      4      8      12     16     20
内容:  a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2]
简写:   a00    a01    a02    a10    a11    a12

每个 int 占 4 字节，所以相邻元素地址差 4。
用 ASCII 图示意：

内存地址:  [0]    [4]    [8]    [12]   [16]   [20]
           +------+------+------+------+------+------+
           | a00  | a01  | a02  | a10  | a11  | a12  |
           +------+------+------+------+------+------+
            第0行 <----------->  第1行 <----------->

三、图6.18：按行访问——空间局部性好

代码

// 按"行优先"顺序累加二维数组所有元素
// 外层循环遍历行，内层循环遍历列
// 访问顺序：a[0][0] -> a[0][1] -> a[0][2] -> a[1][0] -> a[1][1] -> a[1][2]
int sumarrayrows(int a[M][N])
{
    int i, j, sum = 0;   // sum：时间局部性好（每次循环都用到）
    for (i = 0; i < M; i++)          // 外层：遍历每一行
        for (j = 0; j < N; j++)      // 内层：遍历当前行的每一列
            sum += a[i][j];          // 按行顺序读取，步长为1
    return sum;
}

访问顺序表（M=2, N=3）

---

地址	0	4	8	12	16	20
内容	a00	a01	a02	a10	a11	a12
访问顺序	1	2	3	4	5	6

---

访问过程可视化（Mermaid）

为什么局部性好？

访问步长 = 1个元素 = 4字节，称为步长-1访问模式（Stride-1）。
内存中元素是连续存放的，访问顺序也是连续的，CPU 每次从缓存里加载一块连续内存（缓存行），后续元素已经在缓存里了，缓存命中率极高。

步长公式：步长 = 相邻两次访问的地址差 / 元素大小
步长-1示意：
访问: a00 -> a01 -> a02 -> a10 -> a11 -> a12
地址:  0  ->  4  ->  8  -> 12  -> 16  -> 20
跳跃:     +4     +4     +4     +4     +4
步长 = 4字节 / 4字节 = 1（步长-1）

四、图6.19：按列访问——空间局部性差

代码

// 按"列优先"顺序累加二维数组所有元素
// 外层循环遍历列，内层循环遍历行
// 访问顺序：a[0][0] -> a[1][0] -> a[0][1] -> a[1][1] -> a[0][2] -> a[1][2]
int sumarraycols(int a[M][N])
{
    int i, j, sum = 0;   // sum：时间局部性好
    for (j = 0; j < N; j++)          // 外层：遍历每一列
        for (i = 0; i < M; i++)      // 内层：遍历当前列的每一行
            sum += a[i][j];          // 按列顺序读取，步长为N（跨行跳跃！）
    return sum;
}

访问顺序表（M=2, N=3）

---

地址	0	4	8	12	16	20
内容	a00	a01	a02	a10	a11	a12
访问顺序	1	3	5	2	4	6

---

访问过程可视化（Mermaid）

为什么局部性差？

访问步长 = N个元素 = N×4字节，称为步长-N访问模式（Stride-N）。
每次访问都要跨越 N 个元素跳跃，内存不连续。CPU 加载的缓存行里存的是同一行的其他元素，但我们下一步要访问的是下一行的同列元素，缓存里没有，必须重新从内存加载（缓存缺失）。

步长-N示意（N=3）：
访问: a00 -> a10 -> a01 -> a11 -> a02 -> a12
地址:  0  -> 12  ->  4  -> 16  ->  8  -> 20
跳跃:     +12    -8     +12    -8     +12
步长 = 12字节 / 4字节 = 3 = N（步长-N）

五、两种访问模式对比

---

比较项	sumarrayrows（按行）	sumarraycols（按列）
循环结构	外层 i（行），内层 j（列）	外层 j（列），内层 i（行）
访问步长	步长-1（连续）	步长-N（跳跃）
空间局部性	好	差
缓存命中率	高	低
性能	快	慢（N越大越慢）

---

步长与局部性的关系

$$\text{步长}=\frac{\text{相邻两次访问的地址差（字节）}}{\text{单个元素大小（字节）}}$$
一般规律：步长越小，空间局部性越好，性能越高。

六、完整可运行 C++ 演示代码

下面的代码演示了两种访问模式的性能差异，并输出访问顺序。

#include <iostream>
#include <chrono>
#include <iomanip>
// 矩阵维度
const int M = 2;  // 行数（用于演示访问顺序）
const int N = 3;  // 列数
// ------- 演示部分：打印访问顺序（小矩阵 M=2, N=3） -------
// 按行访问：步长-1，空间局部性好
int sumarrayrows(int a[M][N])
{
    int i, j, sum = 0;
    int order = 1;  // 记录访问顺序
    int access_order[M][N];  // 存储每个元素的访问顺序编号
    for (i = 0; i < M; i++)          // 外层遍历行
        for (j = 0; j < N; j++) {    // 内层遍历列（连续地址）
            sum += a[i][j];
            access_order[i][j] = order++;
        }
    // 打印访问顺序
    std::cout << "\n[sumarrayrows] 按行访问顺序：\n";
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++)
            std::cout << std::setw(4) << access_order[i][j];
        std::cout << "\n";
    }
    return sum;
}
// 按列访问：步长-N，空间局部性差
int sumarraycols(int a[M][N])
{
    int i, j, sum = 0;
    int order = 1;
    int access_order[M][N];
    for (j = 0; j < N; j++)          // 外层遍历列
        for (i = 0; i < M; i++) {    // 内层遍历行（跳跃地址）
            sum += a[i][j];
            access_order[i][j] = order++;
        }
    // 打印访问顺序
    std::cout << "\n[sumarraycols] 按列访问顺序：\n";
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++)
            std::cout << std::setw(4) << access_order[i][j];
        std::cout << "\n";
    }
    return sum;
}
// ------- 性能测试部分：大矩阵（体现缓存效果） -------
const int BIG = 1024;  // 大矩阵维度，缓存效果更明显
long long sumrows_big(int a[][BIG])
{
    long long sum = 0;
    for (int i = 0; i < BIG; i++)
        for (int j = 0; j < BIG; j++)
            sum += a[i][j];  // 步长-1：连续访问
    return sum;
}
long long sumcols_big(int a[][BIG])
{
    long long sum = 0;
    for (int j = 0; j < BIG; j++)
        for (int i = 0; i < BIG; i++)
            sum += a[i][j];  // 步长-N：跳跃访问
    return sum;
}
// 静态分配大数组（避免栈溢出）
static int big_array[BIG][BIG];
int main()
{
    // ---------- 1. 演示访问顺序 ----------
    std::cout << "===== 访问顺序演示（M=2, N=3）=====\n";
    std::cout << "内存布局（行主序）：\n";
    std::cout << "  地址: 0     4     8     12    16    20\n";
    std::cout << "  内容: a00   a01   a02   a10   a11   a12\n";
    int a[M][N] = {{1, 2, 3}, {4, 5, 6}};
    int sum1 = sumarrayrows(a);
    std::cout << "  sum = " << sum1 << "\n";
    int sum2 = sumarraycols(a);
    std::cout << "  sum = " << sum2 << "\n";
    // ---------- 2. 性能对比 ----------
    std::cout << "\n===== 性能对比（" << BIG << "x" << BIG << " 矩阵）=====\n";
    // 初始化大矩阵
    for (int i = 0; i < BIG; i++)
        for (int j = 0; j < BIG; j++)
            big_array[i][j] = i * BIG + j;
    // 测试按行访问
    auto t1 = std::chrono::high_resolution_clock::now();
    long long r1 = sumrows_big(big_array);
    auto t2 = std::chrono::high_resolution_clock::now();
    double time_rows = std::chrono::duration<double, std::milli>(t2 - t1).count();
    // 测试按列访问
    auto t3 = std::chrono::high_resolution_clock::now();
    long long r2 = sumcols_big(big_array);
    auto t4 = std::chrono::high_resolution_clock::now();
    double time_cols = std::chrono::duration<double, std::milli>(t4 - t3).count();
    std::cout << "按行访问（步长-1，局部性好）: "
              << std::fixed << std::setprecision(2) << time_rows << " ms\n";
    std::cout << "按列访问（步长-N，局部性差）: "
              << std::fixed << std::setprecision(2) << time_cols << " ms\n";
    std::cout << "性能比（列/行）: "
              << std::fixed << std::setprecision(2) << time_cols / time_rows << "x 慢\n";
    // 验证结果一致
    std::cout << "\n两种方式结果相同: " << (r1 == r2 ? "是" : "否") << "\n";
    return 0;
}

https://godbolt.org/z/nj4M3M16h

编译与运行

# 编译（开启优化可进一步体现差距）
g++ -O0 -o locality_demo locality_demo.cpp
# 运行
./locality_demo

预期输出示意

===== 访问顺序演示（M=2, N=3）=====
内存布局（行主序）：
  地址: 0     4     8     12    16    20
  内容: a00   a01   a02   a10   a11   a12
[sumarrayrows] 按行访问顺序：
   1   2   3
   4   5   6
  sum = 21
[sumarraycols] 按列访问顺序：
   1   3   5
   2   4   6
  sum = 21
===== 性能对比（1024x1024 矩阵）=====
按行访问（步长-1，局部性好）:  X.XX ms
按列访问（步长-N，局部性差）: XX.XX ms
性能比（列/行）: X.XX 慢

七、缓存工作原理（理解为什么步长重要）

CPU 读取 a[0][0] 时，缓存会自动加载一整块相邻内存（缓存行，通常64字节）：
缓存行内容: [a00, a01, a02, a10, a11, a12, ...]
                ^
                当前访问
按行访问：下一次访问 a01，已经在缓存里 -> 命中
按列访问：下一次访问 a10（地址+12），如果超出缓存行 -> 缺失，需重新加载

缓存命中与缺失示意（Mermaid）

步长-1（按行）：大量命中，极少缺失
步长-N（按列）：大量缺失，性能大幅下降

八、总结

---

概念	说明
行主序存储	C 语言二维数组按行连续存放
步长-1（Stride-1）	相邻访问地址差1个元素，空间局部性最好
步长-N（Stride-N）	相邻访问地址差N个元素，空间局部性差
按行访问	与存储顺序一致，步长-1，缓存效率高
按列访问	与存储顺序垂直，步长-N，缓存频繁缺失

---

关键结论：仅仅交换两个循环的顺序，就能让程序快几倍到几十倍。这就是为什么在写矩阵运算时，始终要优先选择按行访问的写法。

6.2.2 指令读取的局部性 & 6.2.3 局部性总结 & 习题详解

一、指令读取的局部性（Locality of Instruction Fetches）

什么是指令读取？

程序的代码（指令）本身也存储在内存里，CPU 执行程序时需要从内存中取指令（Fetch），就像读取数据一样。因此，指令的访问也存在局部性问题。

循环代码的局部性分析

以一个简单的 for 循环为例：

for (i = 0; i < N; i++)
    sum += v[i];

循环体指令在内存中的位置（连续存储）：
地址:  100    104    108    112
指令:  [load] [add]  [inc]  [cmp/jmp]
        取v[i]  累加   i++   判断跳转

• 空间局部性：循环体内的指令在内存中顺序排列，CPU 取完一条指令后，下一条紧挨着，是完美的步长-1访问，空间局部性极好。
• 时间局部性：循环体会被反复执行 N 次，同样的指令一遍遍地被取用，时间局部性也极好。

代码与数据的重要区别

---

对比项	程序数据	程序指令（代码）
运行时是否被修改	经常被读写	几乎从不被修改
访问特点	读写都有	只读（CPU 只取指令，极少改写）
局部性来源	数据访问顺序	指令执行顺序（顺序 + 循环）

---

代码在运行期间基本不变，这使得指令缓存（I-Cache）可以长时间保持有效，缓存效率非常高。

二、局部性总结（Summary of Locality）

三条核心规则

规则一：时间局部性——重复引用同一变量

程序中反复使用同一个变量，就有好的时间局部性。
典型例子：循环变量 i、累加器 sum，每次循环迭代都用到它们。
规则二：空间局部性——步长越小越好
对于步长-k 的访问模式，k 越小，空间局部性越好。
$$\text{步长}k=\frac{\text{相邻两次访问地址差（字节）}}{\text{单个元素大小（字节）}}$$

---

步长 k	举例	空间局部性
$k=1$	顺序访问数组 a[0], a[1], a[2]...	最好
$k=N$	按列访问二维数组	差
$k$ 很大	随机跳跃访问	很差

---

规则三：循环的指令局部性

循环体越小、迭代次数越多，指令的时间局部性和空间局部性越好。

迭代次数多 -> 同一批指令反复使用 -> 时间局部性好
循环体小   -> 指令集中在一小段内存 -> 空间局部性好

三、习题 6.7：重排循环使三维数组以步长-1访问

原始代码（问题所在）

// 原始版本：访问 a[j][k][i]，最内层循环改变 k，但下标中变化最快的却是 i
// 这导致内存访问不连续
int productarray3d(int a[N][N][N])
{
    int i, j, k, product = 1;
    for (i = N-1; i >= 0; i--) {
        for (j = N-1; j >= 0; j--) {
            for (k = N-1; k >= 0; k--) {
                product *= a[j][k][i];  // 注意：下标是 [j][k][i]，不是 [i][j][k]
            }
        }
    }
    return product;
}

分析：三维数组的内存布局

C 语言三维数组 a[N][N][N] 按行主序存储，最右边的下标变化最快：
$$\text{元素地址}=\text{基址}+(d_0\times N\times N+d_1\times N+d_2)\times \text{sizeof(int)}$$
其中 $d_0,d_1,d_2$ 分别是三个维度的下标。

内存顺序（N=2 为例）：
a[0][0][0], a[0][0][1],
a[0][1][0], a[0][1][1],
a[1][0][0], a[1][0][1],
a[1][1][0], a[1][1][1]
              ^^^^^^^
              最右下标变化最快 -> 相邻元素

要实现步长-1访问，最内层循环必须遍历最右边的下标。

原始代码的访问模式分析

访问的是 a[j][k][i]，三个下标对应循环变量：

循环层	变量	对应下标位置
最外层	i	第3个下标（最右，变化应最快）
中间层	j	第1个下标
最内层	k	第2个下标

---

最内层循环改变 k（第2个下标），但 i（第3个下标）是常量，没有利用连续性，步长 = N，局部性差。

解决方案：重排循环

让最内层循环控制最右边的下标（第3个位置，即 i）：

a[j][k][i] 中，i 是第3个下标
-> i 应该在最内层循环
-> j 和 k 的顺序可以任意（只要 i 在最内层）

正确答案

// 修正版本：重排循环，让 i（最右下标）在最内层
// 这样最内层循环每次 i++，访问地址连续，实现步长-1
int productarray3d_fixed(int a[N][N][N])
{
    int i, j, k, product = 1;
    // j 在最外层，k 在中间层，i 在最内层
    // 访问 a[j][k][i]，最内层 i 变化 -> 最右下标变化 -> 连续内存访问
    for (j = N-1; j >= 0; j--) {
        for (k = N-1; k >= 0; k--) {
            for (i = N-1; i >= 0; i--) {   // i 在最内层，控制最右下标
                product *= a[j][k][i];
            }
        }
    }
    return product;
}

访问顺序对比（N=2）

原始版本（步长-N）：
  固定 j=1,k=1: 访问 a[1][1][1], a[1][1][0]  <- 只有这两个连续
  固定 j=1,k=0: 访问 a[1][0][1], a[1][0][0]  <- 跳跃了！
修正版本（步长-1）：
  固定 j=1,k=1: 访问 a[1][1][1], a[1][1][0]  (i: 1->0)
  固定 j=1,k=0: 访问 a[1][0][1], a[1][0][0]  (i: 1->0)
  固定 j=0,k=1: 访问 a[0][1][1], a[0][1][0]  (i: 1->0)
  固定 j=0,k=0: 访问 a[0][0][1], a[0][0][0]  (i: 1->0)
  每个内层组内部都是连续内存 ✓

四、习题 6.8：结构体数组的空间局部性排名

数据结构定义

#define N 1000
// 定义一个"点"的结构体，包含速度和加速度各3个分量
typedef struct {
    int vel[3];   // 速度：vel[0], vel[1], vel[2]（3个int，共12字节）
    int acc[3];   // 加速度：acc[0], acc[1], acc[2]（3个int，共12字节）
} point;
point p[N];   // N个点组成的数组

结构体在内存中的布局

每个 point 结构体大小 = 6个int = 24字节，结构体内部字段连续存储：

单个 point p[i] 的内存布局（24字节）：
偏移:  0    4    8    12   16   20
字段: vel0 vel1 vel2 acc0 acc1 acc2
整个数组 p[N] 的内存布局：
[p[0].vel0][p[0].vel1][p[0].vel2][p[0].acc0][p[0].acc1][p[0].acc2]
[p[1].vel0][p[1].vel1][p[1].vel2][p[1].acc0][p[1].acc1][p[1].acc2]
...

三个函数的代码与分析

clear1 函数

void clear1(point *p, int n)
{
    int i, j;
    for (i = 0; i < n; i++) {           // 外层：遍历每个点 p[i]
        for (j = 0; j < 3; j++)
            p[i].vel[j] = 0;            // 内层1：先清零 vel[0], vel[1], vel[2]
        for (j = 0; j < 3; j++)
            p[i].acc[j] = 0;            // 内层2：再清零 acc[0], acc[1], acc[2]
    }
    // 访问顺序：vel0,vel1,vel2,acc0,acc1,acc2（一个点的所有字段连续清零）
    // 然后跳到下一个点，继续连续清零
}

访问顺序（以 i=0 为例）：

p[0].vel[0] -> p[0].vel[1] -> p[0].vel[2] -> p[0].acc[0] -> p[0].acc[1] -> p[0].acc[2]
地址: 0           4              8              12             16             20

• 每次 j 循环都是连续内存，步长-1
• 两个内层循环之间有一次小跳跃（从 vel[2] 到 acc[0]，但它们本就相邻）
• 整体几乎全是步长-1访问，空间局部性好

clear2 函数

void clear2(point *p, int n)
{
    int i, j;
    for (i = 0; i < n; i++) {           // 外层：遍历每个点
        for (j = 0; j < 3; j++) {       // 内层：同时清零 vel[j] 和 acc[j]
            p[i].vel[j] = 0;            // 先清零第j个vel
            p[i].acc[j] = 0;            // 再清零第j个acc（和vel相距12字节）
        }
    }
    // 访问顺序：vel0, acc0, vel1, acc1, vel2, acc2（交替访问）
}

访问顺序（以 i=0 为例）：

p[0].vel[0] -> p[0].acc[0] -> p[0].vel[1] -> p[0].acc[1] -> p[0].vel[2] -> p[0].acc[2]
地址: 0           12              4              16              8              20
跳跃:      +12          -8            +12          -8            +12

• 每次在 vel[j] 和 acc[j] 之间跳跃 12字节（3个int）
• 步长 = 3（因为跳过了3个int）
• 空间局部性中等（比clear1差，比clear3好）

clear3 函数

void clear3(point *p, int n)
{
    int i, j;
    for (j = 0; j < 3; j++) {           // 外层：遍历分量索引 j
        for (i = 0; i < n; i++)
            p[i].vel[j] = 0;            // 内层1：对所有点清零 vel[j]（每次跳一个结构体）
        for (i = 0; i < n; i++)
            p[i].acc[j] = 0;            // 内层2：对所有点清零 acc[j]（每次跳一个结构体）
    }
    // 访问顺序（j=0时）：p[0].vel[0], p[1].vel[0], p[2].vel[0]...
    // 相邻访问地址差 = sizeof(point) = 24字节 = 6个int -> 步长-6
}

访问顺序（j=0 的内层循环）：

p[0].vel[0] -> p[1].vel[0] -> p[2].vel[0] -> ...
地址: 0            24             48
跳跃:      +24          +24
步长 = 24字节 / 4字节 = 6（步长-6）

• 每次访问都跨越整个结构体（24字节），步长-6
• 空间局部性最差

三个函数的访问模式对比（Mermaid）

ASCII 内存访问图示

内存地址 (每格=4字节):
[0 ][4 ][8 ][12][16][20][24][28][32][36][40][44]...
 v0  v1  v2  a0  a1  a2  v0  v1  v2  a0  a1  a2
 ←── p[0] ──────────────→ ←── p[1] ──────────────→
clear1 访问顺序（步长-1）:
 1   2   3   4   5   6   7   8   9  10  11  12  <- 连续！
clear2 访问顺序（步长-3）:
 1   3   5   2   4   6   7   9  11   8  10  12  <- 小跳跃
clear3 访问顺序（步长-6）:
 1   4   7   2   5   8   3   6   9  ...         <- 大跳跃

空间局部性排名

$$\text{clear1（步长-1）}>\text{clear2（步长-3）}>\text{clear3（步长-6）}$$

排名	函数	步长	访问模式	空间局部性
第1（最好）	clear1	1	按结构体顺序连续清零	好
第2	clear2	3	交替访问 vel 和 acc	中等
第3（最差）	clear3	6	跨结构体按分量访问	差

---

五、完整可运行 C++ 演示代码

#include <iostream>
#include <chrono>
#include <iomanip>
#include <cstring>
// -------- 数据结构定义 --------
#define N 1000
#define BIG 100000   // 性能测试用的大数组
typedef struct {
    int vel[3];   // 速度向量：vel[0], vel[1], vel[2]
    int acc[3];   // 加速度向量：acc[0], acc[1], acc[2]
} point;
// -------- 三种清零函数 --------
// clear1：外层遍历点，内层顺序清零 vel 再清零 acc
// 访问步长-1，空间局部性最好
void clear1(point *p, int n)
{
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++)
            p[i].vel[j] = 0;   // 连续访问同一点的 vel 字段
        for (j = 0; j < 3; j++)
            p[i].acc[j] = 0;   // 连续访问同一点的 acc 字段
    }
}
// clear2：外层遍历点，内层同时清零 vel[j] 和 acc[j]
// 访问步长-3（vel 和 acc 之间差3个int），空间局部性中等
void clear2(point *p, int n)
{
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++) {
            p[i].vel[j] = 0;   // 访问 vel[j]
            p[i].acc[j] = 0;   // 跳12字节访问 acc[j]
        }
    }
}
// clear3：外层遍历分量索引，内层跨结构体访问
// 访问步长-6（每次跳一整个结构体24字节），空间局部性最差
void clear3(point *p, int n)
{
    int i, j;
    for (j = 0; j < 3; j++) {
        for (i = 0; i < n; i++)
            p[i].vel[j] = 0;   // 每次跳跃24字节（一个point的大小）
        for (i = 0; i < n; i++)
            p[i].acc[j] = 0;   // 同上
    }
}
// -------- 演示访问顺序（小数组 n=2）--------
void demo_access_order()
{
    std::cout << "===== 访问顺序演示（n=2个点）=====\n\n";
    std::cout << "内存布局（每格=4字节，共2个point，每个24字节）：\n";
    std::cout << "地址: [ 0][ 4][ 8][12][16][20][24][28][32][36][40][44]\n";
    std::cout << "字段: [v0][v1][v2][a0][a1][a2][v0][v1][v2][a0][a1][a2]\n";
    std::cout << "      <-------- p[0] ---------> <-------- p[1] --------->\n\n";
    // --- clear1 ---
    std::cout << "clear1 访问顺序（步长-1）：\n";
    int order1[2][6];  // [点][字段] -> 访问顺序号
    int cnt = 1;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 3; j++) order1[i][j]   = cnt++;
        for (int j = 0; j < 3; j++) order1[i][j+3] = cnt++;
    }
    for (int i = 0; i < 2; i++) {
        std::cout << "  p[" << i << "]: ";
        for (int f = 0; f < 6; f++)
            std::cout << std::setw(3) << order1[i][f];
        std::cout << "\n";
    }
    // --- clear2 ---
    std::cout << "\nclear2 访问顺序（步长-3）：\n";
    int order2[2][6];
    cnt = 1;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 3; j++) {
            order2[i][j]   = cnt++;   // vel[j]
            order2[i][j+3] = cnt++;   // acc[j]
        }
    for (int i = 0; i < 2; i++) {
        std::cout << "  p[" << i << "]: ";
        for (int f = 0; f < 6; f++)
            std::cout << std::setw(3) << order2[i][f];
        std::cout << "\n";
    }
    // --- clear3 ---
    std::cout << "\nclear3 访问顺序（步长-6）：\n";
    int order3[2][6];
    cnt = 1;
    for (int j = 0; j < 3; j++) {
        for (int i = 0; i < 2; i++) order3[i][j]   = cnt++;
        for (int i = 0; i < 2; i++) order3[i][j+3] = cnt++;
    }
    for (int i = 0; i < 2; i++) {
        std::cout << "  p[" << i << "]: ";
        for (int f = 0; f < 6; f++)
            std::cout << std::setw(3) << order3[i][f];
        std::cout << "\n";
    }
}
// -------- 性能测试（大数组）--------
static point big_p[BIG];
void perf_test()
{
    std::cout << "\n===== 性能测试（n=" << BIG << "个点）=====\n";
    auto bench = [](void (*fn)(point*, int), point* p, int n, const char* name) {
        // 预热
        fn(p, n);
        auto t1 = std::chrono::high_resolution_clock::now();
        for (int r = 0; r < 10; r++) fn(p, n);
        auto t2 = std::chrono::high_resolution_clock::now();
        double ms = std::chrono::duration<double, std::milli>(t2 - t1).count() / 10.0;
        std::cout << name << ": " << std::fixed << std::setprecision(3) << ms << " ms\n";
        return ms;
    };
    double t1 = bench(clear1, big_p, BIG, "clear1（步长-1，最好）");
    double t2 = bench(clear2, big_p, BIG, "clear2（步长-3，中等）");
    double t3 = bench(clear3, big_p, BIG, "clear3（步长-6，最差）");
    std::cout << "\n相对于 clear1：\n";
    std::cout << "  clear2 慢 " << std::fixed << std::setprecision(2) << t2/t1 << " 倍\n";
    std::cout << "  clear3 慢 " << std::fixed << std::setprecision(2) << t3/t1 << " 倍\n";
}
// -------- 习题6.7：三维数组步长修正 --------
#define DIM 64   // 三维数组维度
static int arr3d[DIM][DIM][DIM];
// 原始版本：a[j][k][i]，最内层循环改变k（第2维），步长-DIM
long long productarray3d_bad(int a[][DIM][DIM])
{
    long long product = 1;
    for (int i = DIM-1; i >= 0; i--)
        for (int j = DIM-1; j >= 0; j--)
            for (int k = DIM-1; k >= 0; k--)
                product *= (a[j][k][i] % 7 + 1);  // 防止溢出
    return product;
}
// 修正版本：a[j][k][i]，最内层循环改变i（第3维），步长-1
long long productarray3d_good(int a[][DIM][DIM])
{
    long long product = 1;
    for (int j = DIM-1; j >= 0; j--)
        for (int k = DIM-1; k >= 0; k--)
            for (int i = DIM-1; i >= 0; i--)  // i 在最内层，控制最右下标
                product *= (a[j][k][i] % 7 + 1);
    return product;
}
void test_3d()
{
    std::cout << "\n===== 习题6.7：三维数组循环重排 =====\n";
    for (int i = 0; i < DIM; i++)
        for (int j = 0; j < DIM; j++)
            for (int k = 0; k < DIM; k++)
                arr3d[i][j][k] = (i+j+k) % 5 + 1;
    auto t1 = std::chrono::high_resolution_clock::now();
    long long r1 = productarray3d_bad(arr3d);
    auto t2 = std::chrono::high_resolution_clock::now();
    long long r2 = productarray3d_good(arr3d);
    auto t3 = std::chrono::high_resolution_clock::now();
    double bad_ms  = std::chrono::duration<double, std::milli>(t2 - t1).count();
    double good_ms = std::chrono::duration<double, std::milli>(t3 - t2).count();
    std::cout << "原始（步长-N，差）: " << std::fixed << std::setprecision(3) << bad_ms  << " ms\n";
    std::cout << "修正（步长-1，好）: " << std::fixed << std::setprecision(3) << good_ms << " ms\n";
    std::cout << "结果相同: " << (r1 == r2 ? "是" : "否") << "\n";
}
int main()
{
    demo_access_order();
    perf_test();
    test_3d();
    return 0;
}

https://godbolt.org/z/z8fnW473Y

编译与运行

g++ -O0 -o locality2 locality2.cpp
./locality2

六、总结对比

局部性评估方法总结

关键结论

---

场景	好的做法	坏的做法
二维数组	外层行，内层列（步长-1）	外层列，内层行（步长-N）
三维数组	最内层循环控制最右下标	最内层循环控制非最右下标
结构体数组	先处理完一个元素的所有字段	外层按字段，内层遍历元素
通用原则	让内层循环访问连续内存	让内层循环跨越大块内存

---