存储器山
首先上 CSAPP 的存储器山镇文￣□￣。虽然说 Java 程序员不像 C 程序员需要特别关心内存分配等操作，但是学习下计算机的存储结构，明确各个层次的存储器特性，对写高性能的代码还是很有帮助的。所以基于“深入理解计算机系统”，一起学习下存储器相关的一些知识。
存储器分类
存储器系统是一个不同容量、成本和访问时间的存储设备的层次结构。越靠近 CPU 的存储器越快也越贵、越小，从磁盘上读取信息比从 DRAM 中读取慢了 10 万倍，比 SRAM 慢了 100 万倍。计算机巧妙的运用了各种存储器的特性，构建了一个既运行高效又支持大容量存储的系统。
SRAM
SRAM 全称“Static Random Access Memory”，之所以被称为“静态”存储器，是因为只要有电，它就会永远保持它的值。即使有干扰来扰乱电压，当干扰消除时，依然会恢复到稳定值。而一旦断电，里面的数据就会丢失了。SRAM 对诸如光和电噪声这样干扰不敏感，是因为 SRAM 比 DRAM 使用了更多的晶体管，因而密集度较低，也就更贵，功耗更大。
由于 SRAM 速度快、容量小、价格贵，所以多用来制造高速缓存，如现在计算机中基本都有的 L1，L2，L3 缓存。
DRAM
DRAM 全称“Dynamic Random Access Memory”，相比 SRAM，DRAM 需要定时刷新，所以也被称为“动态”存储器。DRAM 每个单元由一个电容和一个晶体管组成，由于组成简单，所以 DRAM 可以制造的非常密集，因而容量可以做的较大。但DRAM 对干扰非常敏感。因为数据存储在电容里面，而电容会不断漏电，所以要定时刷新，才能保证数据不会丢失。
DRAM 由于容量大、价格便宜，多用来制作计算机主存，或者各种显卡的显存等。
| 每位晶体管数 | 相对访问时间 | 持续的? | 敏感的? | 相对花费 | 应用 | |
|---|---|---|---|---|---|---|
| SRAM | 6 | 1X | 是 | 否 | 1000X | 高速缓存存储器 |
| DRAM | 1 | 10X | 否 | 是 | 1X | 主存，帧缓冲区 |
ROM
ROM 全程“Read Only Memory”，由于历史原因，虽然 ROM 中有的类型即可以读也可以写，但是他们整体上被称为只读存储器。相比于 SRAM，DRAM 最大的不同就是断电后不会丢失信息，因为是非易失性存储器。
存储在 ROM 中的程序通常被称为“固件”，当计算机通电后就会运行存储在 ROM 中的固件，例如我们所熟知的 BIOS 程序，就存储在 ROM 中，每次计算机开机会引导操作系统启动。复杂的设备，如显卡和磁盘驱动控制器，也依赖固件翻译来自 CPU 的 I/O 请求。
磁盘
磁盘是由“盘片”构成，每个盘片有两面或者一面称为“表面”，表面覆盖着磁性记录材料。盘片中央有一个旋转主轴，使得盘片以固定的旋转速率旋转，通常 5400 ~ 15000 转/分钟。磁盘通常包含一个或多个盘片，并封闭在一个容器中。
磁盘的表面由一组组称为“磁道”的同心圆组成，每个磁道被划分为一组“扇区”，每个扇区包含相同数量的数据位（通常 512 byte)。扇区之间由一些间隙分隔开，间隙不存储数据位，只用来标识扇区的格式化位。
盘片
|
磁盘
|
|---|
磁盘容量
一个磁盘可以记录的最大位数称为他的容量。磁盘容量由以下技术因素决定：
- 记录密度：磁道一英寸的段中可以放入的位数。
- 磁道密度：从盘片中心向外半径一英寸可以有的磁道数。
磁盘的容量 = 字节数/扇区 * 平均扇区数/磁道 * 磁道数/表面 * 表面数/盘片 * 盘片数/磁盘
磁盘操作
磁盘用“读/写头”来读写存储在磁性表面的位，读写头连接到一个传动臂。通过沿着半径轴前后移动传动臂，可以将读/写头定位到期望磁道，这个过程称为“寻道”。有多个盘面的磁盘针对每个盘面都有一个独立的读/写头，读/写头垂直排列，一致行动，在任何时刻，所有读/写头都位于同一柱面上。
读写
|
统一移动
|
|---|
磁盘以扇区大小的块来读写数据，对扇区的访问时间主要由下面几个部分决定。
- 寻道时间：移动传动臂到指定磁道上的时间。现在驱动器中平均寻到时间通常是 3~9 ms，并且受限于物理性能局限，很难再缩小。
- 旋转时间：读/写头到指定磁道后，需要等待磁盘旋转到目标扇区，目标扇区第一个位旋转到读/写头下的时间为旋转时间。以 7200 转磁盘为例，平均旋转时间约为 4ms。
- 传送时间：从读取扇区第一个位到扇区读取完毕的时间为传送时间，主要取决于磁盘的旋转速度及磁道的扇区数目。相比于寻道时间及旋转时间，传送时间很小基本可以忽略不计。
由于寻道时间和旋转时间大致相等，所以经常用寻道时间*2 来估算磁盘访问时间。
逻辑磁盘块
为了对操作系统隐藏磁盘构造的复杂性，现代磁盘将其构造呈现为一个简单的视图：一个 B 个扇区大小的逻辑块序列，编号为0，1，...，B-1。磁盘中有一个小的硬件称为磁盘控制器，维护着逻辑块号与实际磁盘扇区的映射关系。
当操作系统想要读写一个磁盘的扇区数据时候，将会发送一个命令到磁盘控制器，让他读取某个逻辑块号。磁盘控制器将逻辑块号翻译成一个（盘面，磁道，扇区）的三元组，唯一的标识了对应的物理扇区。然后将读/写头移动到相应的物理扇区，进行读写操作。
磁盘读取
固态硬盘
固态硬盘（SSD）是一种基于闪存的存储技术，有一个或多个闪存芯片和闪存翻译层组成。闪存芯片替代传统磁盘中的机械驱动器，闪存翻译层则是类似于磁盘控制器的存在。
固态硬盘
相比传统磁盘，SSD 有很多优点。由于由半导体存储器构成，因而随机访问时间比旋转磁盘要快很多，功耗更低，也更结实。同样也有一些缺点，闪存块会磨损，因而 SSD 寿命较普通磁盘短。SSD 较传统磁盘价格更贵，因而常用的存储容量也比传统磁盘较小。
硬件技术趋势
硬件技术趋势
上图是各种硬件按年统计的运行速度，可以看出，虽然 SRMA 的性能滞后于 CPU 的性能，但是在持续保持增长，追赶 CPU 的增长曲线。而 DRAM 和磁盘的性能增长缓慢，严重滞后于 CPU 的性能，与 CPU 性能之间的差距在不断扩大。
CPU 在 2003 年开始出现变化，是由于当时无法再通过增加 CPU 的频率来提升性能，因为这样芯片的功耗会太大。解决办法就是用多个小处理器取代单个大处理器，从而提升性能。CPU 频率在 2003 年达到了最低点，上升后又开始以比以前慢一些的速率下降。不过，CPU 的有效周期时间还是以接近以前的速率持续下降。
局部性
从上面我们可以看到不同硬件的运行效率差距简直天壤之别，那么计算机是如何将这些运行效率差异如此之大的硬件组合在一起，并能保证高效运行呢？这里就要了解一个很重要的概念--局部性原理。
一个编写良好的计算机程序常常有良好的“局部性”。也就是，它们倾向于引用的数据项多临近与其他最近引用过的数据项，或者是最近引用过的数据项本身。这种倾向性，被称为“局部性原理”。这是一个很重要的概念，对硬件和软件系统的设计和性能都有着极大的影响。
局部性有两种不同的形式：
- 时间局部性：被引用过的内存位置很可能在不远的将来再被多次引用。
- 空间局部性：如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用其附近的一个位置。
/**
* 局部性验证小程序
* @author 鱼蛮 on 2021/11/1
**/
public class Locality extends AbstractBenchMark {
/**
* 缓存组是8路的，所以需要大于8才会比较明显的缓存冲突情况
*/
final static int ROW = 16;
/**
* Core i7，L1 d-cache是32KB，L2 cache 是256K，这个值可以根据 cache 情况调整
* 一个Integer值16byte，32KB/16byte=2048，数组的一行正好可以填充满L1缓存
*/
final static int COLUMN = 2048;
static Integer[][] arr;
@Benchmark
public void locality() {
int tmp = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COLUMN; j++) {
tmp += arr[i][j];
}
}
}
@Benchmark
public void noneLocality() {
int tmp = 0;
for (int j = 0; j < COLUMN; j++) {
for (int i = 0; i < ROW; i++) {
tmp += arr[i][j];
}
}
}
static {
int counter = 0;
arr = new Integer[ROW][COLUMN];
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COLUMN; j++) {
// 主要Integer的常量池影响
arr[i][j] = new Integer(counter++);
}
}
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(Locality.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
/// 用来打印数据内存地址，来实际验证
printAddress(arr[0][0]);
printAddress(arr[0][1]);
printAddress(arr[1][0]);
}
public static void printAddress(Object o) {
System.out.println("number:" + o + ",address:"+ Long.toHexString(VM.current().addressOf(o)) + "##" + Long.toBinaryString(VM.current().addressOf(o)));
}
}
可以用上面的小程序来验证局部性的重要性，两种方式的运行效率差距还是比较大的。
Benchmark Mode Cnt Score Error Units
Locality.locality avgt 5 18587.618 ± 1567.916 ns/op
Locality.noneLocality avgt 5 37490.564 ± 5833.672 ns/op
存储器层次结构
基于各种存储技术特性及局部性原理，硬件和软件可以很好的互相补充。它们这种互相补充的性质使人们想到一种组织存储系统的方法，称为“存储器层次结构”，所有的现代计算机系统都使用了这种方法。下图展示了一个典型的存储器层次结构。一般，从高处往底层走，存储设备变的更慢、更大、更便宜。
存储器层次
缓存
一般而言，缓存是一个相对小而快速的设备，他作为储存在更大、更慢的设备中的数据对象的缓冲区域。在存储器层次结构中，任何一层都可以看做是其下一层的缓存。在计算机系统中，缓存主要是为了加速 CPU 的访问，毕竟 CPU 跟底层的存储系统运行效率差距巨大。
在 CSAPP 里面老师描述缓存举得例子特别形象：对一个学生来说，家就好比主存，里面有各种各样的东西。而背包就好比高速缓存，只装了你最需要的东西。当你从书包拿出课本的时候可以很快，否则你就需要跑回家拿。
现代操作系统可以说是各种缓存的集合，如下表所见，从 CPU 都浏览器，到时都运用了缓存技术。
| 类型 | 缓存什么 | 被缓存在何处 | 延迟(周期数) | 由谁管理 |
|---|---|---|---|---|
| CPU寄存器 | 4字节或8字节字 | 芯片上的CPU寄存器 | 0 | 编译器 |
| TLB | 地址翻译 | 芯片上的TLB | 0 | 硬件MMU |
| L1高速缓存 | 64字节块 | 芯片上的L1高速缓存 | 4 | 硬件 |
| L2高速缓存 | 64字节块 | 芯片上的L2高速缓存 | 10 | 硬件 |
| L3高速缓存 | 64字节块 | 芯片上的L3高速缓存 | 50 | 硬件 |
| 虚拟内存 | 4KB页 | 主存 | 200 | 硬件+OS |
| 缓冲区缓存 | 部分文件 | 主存 | 200 | OS |
| 磁盘缓存 | 磁盘扇区 | 磁盘控制器 | 100 000 | 控制器硬件 |
| 网络缓存 | 部分文件 | 本地磁盘 | 10 000 000 | NFS客户 |
| 浏览器缓存 | Web页 | 本地磁盘 | 10 000 000 | Web浏览器 |
| Web缓存 | Web页 | 远程服务器磁盘 | 1 000 000 000 | Web代理服务器 |
缓存数据总是以块大小为传送单元，在第 k 层跟 k+1 层之间来回拷贝。相邻层次之间块大小是固定的，但其他层次对之间可以有不同的块大小。L1 和 L0 之间传送通常使用 1 个字的块，L2 和 L1、L3 和 L2、L4 和 L3 之间传递通常使用几十个字节的块。而 L5 跟 L4 之间传递通常用几百或者几千字节的块。一般而言离CPU越远的设备访问时间越长，为了补偿这些时间，倾向于使用较大的块。
缓存不命中
缓存不命中主要分为三类：
- 冷不命中：一个空的缓存被称为冷缓存，此类不命中称为冷不命中。应对这种情况就是在使用前需要暖身（warm up），也就是常说的预热。
- 冲突不命中：由于缓存的容量限制，读取不同的内容命中同一缓存块称为冲突不命中。比如一个容量为 4 的缓存（采用取余的放置策略），程序来回请求块 0 和块 8，就会导致每次请求都无法命中缓存。
- 容量不命中：当缓存太小无法缓存工作集的时候称为容量不命中。
只要发生了缓存不命中，就需要执行严格的缓存“放置策略”，来决定将 k+1 层的块放置何处，而不是放置在任意地方，否则定位起来代价很高。
高速缓存
早起计算机系统的存储器只有三层：CPU 寄存器、DRAM 主存和磁盘。不过，由于 CPU 和主存（DRAM）之间的差距逐渐增大，于是在 CPU 寄存器和主存之间插入了小的 SRAM 高速缓存，称为 L1 高速缓存，访问速度大约 4 个时钟周期。如下图所示。
高速缓存
随着 CPU 和主存的性能差距不断变大，于是又在 L1 和主存之间增加了 L2 高速缓存，L2 高速缓存访问速度大约 10 个时钟周期。现代计算机在 L2 和主存之间又插入了一个 L3 缓存，访问速度大约 50 个时钟周期。
高速缓存组织结构
高速缓存通常按组形式来组织，如下图所示，高速缓存被组织成 S 个高速缓存组。每个缓存组有 E 个高速缓存行，每行包含 B 字节的数据块及 1 个有效位和 t 位的标记位（用来标识缓存组中惟一的缓存行）。所以高速缓存的容量计算也非常容易计算：SEB。
高速缓存组织
内存地址根据高速缓存的组织形式，被划分为了三部分，用于快速定位到缓存：
- 块偏移：简称（CO），用于在缓存块中快速定位数据，位数等于
- 组索引：简称（CI），用于查找缓存所在的缓存组，位数等于
- 标记：简称（CT），查找到的缓存组如果有多行时，需要依次比较缓存标记是否相同，来确定缓存是否存在，位数等于：内存地址位数-CO位数-CI位数。
直接映射高速缓存
每个缓存组只有一行（E=1）的高速缓存被称为直接映射高速缓存。
让我们一起看一个高速缓存的查找实例，假设内存地址为 4 位。高速缓存有 4 组，每组 1 行，每个缓冲块 2 字节。那么根据之前的知识我们可以知道，4 位地址被划分成了如下图所示的 3 部分。
直接映射高速缓存
假设 CPU 每次读取 1 字节的数据，我们按照下表来依次读取，则会有相应的缓存命中情况。
| 内存地址 | 组 | 标记 | 有效位 | 块偏移 | 是否命中 |
|---|---|---|---|---|---|
| 0(0 00 0) | 0(00) | 0 | 0 | 0 | miss |
| 1(0 00 1) | 0(00) | 0 | 1 | 1 | hit |
| 7(0 11 1) | 3(11) | 0 | 0 | 1 | miss |
| 8(1 00 0) | 0(00) | 1 | 0 | 0 | miss |
| 0(0 00 0) | 0(00) | 0 | 0 | 0 | miss |
当程序访问地址大小为 2 的幂的数组时，直接映射高速缓存中通常会发生冲突不命中。这是因为这些块被映射到了同一个高速缓存组，例如上表中的内存地址 0 跟内存地址 8 就映射到了一个缓存组，从而产生冲突。即使程序有良好的空间局部性，而且我们的高速缓存有足够的空间来存放数据（组 1 跟 组 2 还未被使用），也无法有效利用缓存来提升性能。
组相连高速缓存
直接映射高速缓存中冲突不命中造成的原因源于每组只有一行，而组相连高速缓存就是组数大于 1 组，并且小于缓存大小/块大小的情况，所以每组都存在多个缓存行。我们让上面中的缓存每组有 2 行，则缓存组变成 2，再看下缓存命中情况。
| 内存地址 | 组 | 标记 | 有效位 | 块偏移 | 是否命中 |
|---|---|---|---|---|---|
| 0(00 0 0) | 0(0) | 00 | 0 | 0 | miss |
| 1(00 0 1) | 0(0) | 00 | 1 | 1 | hit |
| 7(01 1 1) | 1(1) | 01 | 0 | 1 | miss |
| 8(10 0 0) | 0(0) | 10 | 0 | 0 | miss |
| 0(00 0 0) | 0(0) | 00 | 1 | 0 | hit |
我们会发现，相比直接映射高速缓存产生了更少的缓存未命中。缓存组内较多的缓存行降低了缓存冲突的可能性，但是也需要更多的标记位，也会增加命中时间，因为最坏情况下需要遍历组内所有的标记位，才能找到对应的缓存行。
当 CPU 请求的数据不在缓存中，而查找到的缓存组已满时候，高速缓存必须替换缓存组中的某一个行，这其中就需要用到高速缓存替换策略，常见的有 LFU（最不常使用），LRU（最近最少使用）等。
全相连高速缓存
全相连高速缓存即只有一个组，包含所有缓存行。全相连高速缓存因为只有一个组，所以组选择非常简单。全相连高速缓存拥有最大的缓存空间利用率，但是必须搜索许多标记，构造一个又大又快的全相连高速缓存很困难，也很昂贵，因此全相连高速缓存只适合做小的高速缓存。有些虚拟系统中使用的小容量的 TLB 采用这种形式。
实际高速缓存示例
高速缓存示例
在高缓存中其实不止保存程序数据，也可以保存指令。只保存指令的高速缓存称为 i-cache，只保存数据的高速缓存称为 d-cache。
上图给出的是 Intel Core i7（Haswell）处理器的高速缓存层次结构。每个 CPU 芯片有四个核。每个核有自己私有的 L1 i-cache，L1 d-cache 及 L2 统一高速缓存。所有的核共享 L3 统一高速缓存。所有的 SRAM 高速缓存都在 CPU 芯片上。下表是 Core i7 处理器高速缓存的基本特性。
| 高速缓存类型 | 访问时间(周期) | 高速缓存大小(C) | 相连度(E) | 块大小(B) | 组数(S) |
|---|---|---|---|---|---|
| L1 i-cache | 4 | 32KB | 8 | 64B | 64 |
| L1 d-cache | 4 | 32KB | 8 | 64B | 64 |
| L2统一高速缓存 | 10 | 256KB | 8 | 64B | 512 |
| L3统一高速缓存 | 40~75 | 8M | 16 | 64B | 8192 |
存储器山
一个程序从存储系统中读取数据速率称为吞吐量，或者称为读带宽。通常以 MB/s 为单位。
存储器山
这张图是开头的那张图，描绘的是 Intel Core i7 系统的存储器山。展示了一个丰富的地势结构，垂直于大小轴的是四条山脊，对应 L1 高速缓存、L2 高速缓存、L3 高速缓存和主存的时间局部性区域。L1 山脊的最高点（读速率为 14GB/s）与主存山脊的最低点（读取速率为 900MB/s）之间的差别有一个数量级。
在 L2、L3、主存山脊上，随着步长的增加，有一个空间局部性的斜坡，空间局部性下降。即使工作集太大，不能全部装入任何一个高速缓存是，主存山脊的最高点仍然比它的最低点高 8 倍。因此，即使当程序的时间局部性很差时，空间局部性仍能补救，并且是非常重要的。
有一条特别的平坦的山脊线，对于步长 1 垂直于步长轴，此时吞吐量相对保持不变，为 12GB/s，即使工作集超过 L2、L3 的大小。这是由于 Core i7 存储器系统中的硬件预期机制，它会自动的识别顺序的、步长为 1 的引用模式，试图在一些块被访问之前，将他们取到高速缓存中。从存储器山可以明显看出算法对小步长效果最好--这也是代码中要使用步长为 1 的顺序访问的另一个理由。
存储器系统的性能不是一个数字就能描述的，而是一座时间和空间局部性的山。我们应该构造运行在山峰而不是山谷的程序。主要就是利用时间局部性，使得频繁使用的字从 L1 中取出，还要利用空间局部性，使得尽可能多的字从一个 L1 高速缓存行中访问到。
深入理解计算机系统
网友评论