Lecture 06: The Memory Hierarchy

存储技术

随机访问存储器

**随机访问存储器（Random-Access Memory，RAM）**根据存储单元实现方式可以分为两类：静态的RAM（SRAM）和动态的RAM（DRAM）。

• SRAM

  由于具有双稳态，所以只要有电，就会永远保持它的值，即使有干扰，当干扰消除时就会恢复到稳态

• DRAM

  • 由于每个存储单元比较小，DRAM可以制造的十分密集，可以作为主存或图形系统的帧缓冲区。
  • 由于通过电容电压来保存位，当电容电压受到扰动时就无法恢复了。并且电容存在漏电现象，存储单元10~100毫秒会失去电荷，使得内存系统必须周期性通过读出重写来刷新内存的每一位。
  • 暴露在光线中会导致电容电压改变。

非易失性存储器

之前介绍的DRAM和SRAM在断电时都会丢失数据，所以是易失的（Volatile），而非易失性存储器（Nonvolatile Memory）即使断电后，也会保存信息，该类存储器称为只读存储器（Read-Only Memory，ROM），但是现在ROM中有的类型既可以读也可以写了，可以根据ROM能够重编程的次数以及对它们进行重编程所用的机制进行区分，包括：

• **可编程ROM（PROM）：**可以编程一次
• **可擦写PROM（EPROM）：**可以批量擦除
• **闪存（Flash Memory）：**具有部分（块级）擦除功能，大约擦除十万次后会耗尽

存储在ROM设备中的程序称为固件（Firmware），包括BIOS、磁盘控制器、网卡、图形加速器和安全子系统等。当计算机系统通电后，会运行存储在ROM中的固件。

磁盘存储

**磁盘（Disk）**是被用来保存大量数据的存储设备，但是读信息的速度比DRAM慢10万倍，比SRAM慢100万倍。

磁盘是由多个叠放在一起的盘片（Platter）构成，每个盘片有两个覆盖着磁性记录材料的表面（Surface）。每个表面由一组称为磁道（Track）的同心圆组成，每个磁道被划分为若干扇区（Sector），每个扇区包含相同数量的数据位（通常为512字节）作为读写数据的基本单位。扇区之间通过间隙（Gap）分隔开来，间隙不保存数据信息，只用来表示扇区的格式化位。通常会使用柱面（Cylinder）来描述不同表面上相同磁道的集合，比如柱面k就是6个表面上磁道k的集合。盘片中央会有一个可以旋转的主轴（Spindle），使得盘片以固定的旋转速率（Rotational Rate）旋转，单位通常为RPM（Revolution Per Minute）。

将磁盘能记录的最大位数称为最大容量（容量），主要由以下方面决定：

• **记录密度（Recording Density）：**一英寸的磁道中可以放入的位数
• **磁道密度（Track Density）：**从盘片中心出发，沿着半径方向一英寸，包含多少磁道
• **面密度（Areal Density）：**记录密度和磁道密度的乘积

在面密度较低时，每个磁道都被分成了相同的扇区，所以能够划分的扇区数由最内侧磁道能记录的扇区数决定，这就使得外侧的磁道具有很多间隙。现代大容量磁盘采用**多区记录（Multiple Zone Recording）**技术，将一组连续的柱面划分成一个区，在同一个区中，每个柱面的每条磁道都有相同数量的扇区，由该区中最内侧的磁道决定，由此使得外侧的区能划分成更多的扇区。

磁盘通过一个连接在**传动臂（Actuator Arm）上的读/写头（Read/Write Head）来进行读写，对于有多个盘面的磁盘，会用多个位于同一柱面上的垂直排列的读/写头。对于扇区的访问时间（Access Time）**由以下几部分构成：

• **寻道时间：**为了读取到目标扇区，会先控制传动臂将读/写头移动到该扇区对应的磁道上，该时间称为寻道时间。依赖于读/写头之前的位置，以及传动臂在盘面上移动的速度。

• **旋转时间：**当读/写头处于目标磁道时，需要等待目标扇区的第一个位旋转到读/写头下

• **传送时间：**当读/写头处于目标扇区的第一位时，就可以进行传送了

由于磁盘构造的复杂性，现代磁盘将其抽象为B个扇区大小的逻辑块序列，编号为0,1,...,B-1，通过磁盘中的磁盘控制器来维护逻辑块号和实际扇区之间的映射关系。为此需要通过磁盘控制器对磁盘进行格式化：

• 会用表示扇区的信息填写在扇区之间的间隙
• 表示出表面有故障的柱面，并且不进行使用
• 在每个区会预留一组柱面作为备用，没有映射为逻辑块。当损坏时，磁盘控制器会将数据复制到备用柱面，则磁盘就可以继续正常工作了。

当从磁盘读取数据到主存，需要以下步骤：

1. 操作系统发送一个命令到磁盘控制器，读取某个逻辑块号
2. 磁盘控制器上的固件执行快速表查找，得到该逻辑块号翻译成一个三元组（盘面，磁道，扇区）
3. 磁盘控制器解释三元组信息，将读/写头移动到对应的扇区
4. 将读取到的信息放到磁盘控制器的缓冲区中
5. 将缓冲区中的数据保存到主存中。

在将磁盘内容传送到主存的过程中，不需要经过CPU，因为磁盘读取速度比CPU执行速度慢很多，所以CPU会先去执行其他工作。当传送完成后，由磁盘发送一个中断信号到CPU。

固态存储

**固态硬盘（Solid State Disk，SSD）**是一种基于闪存的存储技术，插在I/O总线上标准硬盘插槽（通常为USB或SATA），处于磁盘和DRAM存储器的中间点。

它由闪存和**闪存翻译层（Flash Translation Layer）**组成

• 闪存翻译层是一个硬件/固件设备，用来将对逻辑块的请求翻译成对底层物理设备的访问。
• 闪存的基本属性决定了SSD随机读写的性能，通常由B个块的序列组成，每个块由P页组成，页作为数据的单位进行读写。通常页大小为512字节~4KB，块中包含32~128页，则块的大小有16KB~512KB。

当对页进行写操作时，首先需要先对该页所处的整个块进行擦除。

SSD的优缺点：

• **优点：**由于闪存是半导体存储器，没有移动的部件，所以速度比磁盘更快且磨损小，能耗低
• **缺点：**SSD每字节比磁盘贵大约30倍，所以常用的存储容量比磁盘小100倍左右。

局部性

具有良好**局部性（Locality）**的程序，会倾向于引用最近引用过的数据项本身，或者引用最近引用过的数据项周围的数据项。局部性主要具有两种形式：

• **时间局部性（Temporal Locality）：**引用过的数据项在不久会被多次引用。

• **空间局部性（Spatial Locality）：**引用过的数据项，在不久会引用附近的数据项。

从硬件到操作系统，再到应用程序，都利用了局部性

• **硬件：**在处理器和主存之间引入一个小而快速的高速缓存存储器，来保存最近引用的指令和数据，从而提高对主存的访问速度。
• **操作系统：**用主存来缓存虚拟空间中最近被引用的数据块。
• **应用程序：**比如Web浏览器会将最近引用的文档放入本地磁盘中，来缓存服务器的数据。

一个例子：数组的遍历

相比于采用列优先遍历，行优先遍历会更快。因为存储就是使用的行优先。跨列的访问会跨越更大的空间，影响读取速度。

存储器的层次结构

如上图所示是一种经典的存储器层次结构，会使用基于SRAM的高速缓存存储器来解决CPU和DRAM主存之间的鸿沟，**高速缓存（Cache）**是一个小而快速的存储设备，用来存放使用频率大的数据，来作为存储在更大更慢设备中的数据对象的缓冲区域。

存储器层次结构的中心思想是让层次结构中的每一层来缓存低一层的数据对象，将第k层的更快更小的存储设备作为第k+1层的更大更慢的存储设备的缓存。相比于第k+1层的数据，程序会倾向于访问存储在第k层的数据。如果我们访问第k+1层存储的数据，我们会将其拷贝到第k层，因为根据局部性原理我们很有可能将再次访问该数据，由此我们就能以第k层的访问速度来访问数据。而且因为我们不经常访问第k+1层的数据，我们就可以使用速度更慢且更便宜的存储设备。

上图展示的是存储器层次结构的基本缓存原理。每一层存储器都会被划分成连续的数据对象组块，称为块（Block），每个块都有一个唯一的地址或名字，并且通常块的大小都是固定的。第k层作为第k+1层的缓存，数据会以块大小作为**传送单元（Transfer Unit）**在第k层和第k+1层之间来回赋值，使得第k层保存第k+1层块的一个子集的副本。通常存储器层次结构中较低层的设备的访问时间较长，所以较低层中会使用较大的块。

缓存命中

• 缓存命中（cache hit）

  当程序需要第k+1层的某个数据对象d时，会现在第k层的块中搜索d，如果d刚好缓存在第k层中，则成为缓存命中（Cache Hit），则该程序会直接从第k层中读取d。根据存储器层次结构，可以知道第k层的读取速度更快，因此缓存命中会使得程序更快。

• 缓存不命中（cache miss）

  如果第k层没有缓存数据对象d，则称为缓存不命中（Cache Miss），则会从第k+1层中取出包含d的块，然后第k层的缓存会执行某个**放置策略（Placement Policy）**来决定该块要保存在第k层的什么位置

  • • **随机替换策略：**会随机选择一个牺牲块
    • **最近最少被使用（LRU）替换策略：**选择最后被访问的时间离现在最远的块

  随机放置块会使得定位起来代价很高。

  • 可以采用更严格的放置策略，将第k+1层的某个块限制放置在第k层块的一个小的子集中，比如第k+1层的第i个块保存在第k层的i mod 4中。但是该放置策略会引起冲突不命中（Conflict Miss），此时缓冲区足够大，但是由于需要的对象会反复映射到同一个缓存块，使得缓存一直不命中。此时就需要修改放置策略。

  比较特殊的情况是第k层的缓存为空，那么对于任意的数据对象的访问都会不命中。空的缓存称为冷缓存（Cold Cache），该不命中称为强制性不命中（Compulsory Miss）或冷不命中（Cold Miss）。

  程序通常会按照一系列阶段来运行，每个阶段会访问缓存块的某个相对稳定不变的集合，则该集合称为工作集（Working Set），如果工作集大小超过缓存大小，则缓存会出现容量不命中（Capacity Miss），这是由缓存太小导致的。