CSAPP笔记之存储器层次结构

笔记
CSAPP，笔记
Catalogue
  1. 1. 随机访问存储器
    1. 1.1. 传统机械硬盘
      1. 1.1.1. 1.磁盘容量
      2. 1.1.2. 2. 磁盘操作
  2. 2. 总线
  3. 3. 局部性原理
  4. 4. 存储器层次结构
    1. 4.1. 缓存命中
    2. 4.2. 缓存不命中
      1. 4.2.1. 缓存不命中的种类
    3. 4.3. 缓存利用局部性原理
    4. 4.4. 高速缓存
      1. 4.4.1. 1. 读取过程
      2. 4.4.2. 2. 缓存一致性问题（拓展）
  5. 5. 参考资料

下面内容是对《深入理解计算机系统》和内存与缓存文章的一个学习笔记

随机访问存储器

随机访问存储器(Random-Access Memory，RAM)分为两类：

  • 静态的：静态RAM(SRAM)
    • 静态RAM比动态RAM更快，同时也更贵，不需要定期刷新，SRAM用来作为高速缓存存储器
  • 动态的: 动态RAM(DRAM)
    • DRAM稍微慢一点(大概是SRAM速度的十分之一)，需要刷新，可以用来作为主存以及图形系统的帧缓冲区

无论是DRAM还是SRAM，一旦不通电，所有的信息都会丢失，如果想要让数据持久化，可以考虑ROM、PROM、EPROM、EEPROM等介质。固体硬件会存储在ROM中 (比如 BIOS，磁盘控制器，网卡、图形加速器、安全子系统等等)。

目前比较常见的就是SSD固态硬盘，它是一种基于闪存的磁盘驱动器，而闪存是一类非易失性存储器，基于EEPROM。SSD取消了机械结构，更稳定快速

传统机械硬盘

传统机械硬盘部件如下：

机械硬盘

机械硬盘有许多片磁盘组成，每一片磁盘有两面，每一面由一圈圈的磁道组成，每个磁道被划分为一组扇区，每个扇区包含相等数量的数据位（通常是512字节）

磁盘结构

1.磁盘容量

硬盘的容量指的是最大能存储的比特数，通常用 GB 来做单位。1 GB 相当于 10 的 9 次方个 Byte。磁盘容量是由以下技术因素决定的：

  • 记录密度 (位/英寸)：磁道一英寸的段中保存的位数
  • 磁道密度 (道/英寸)：1英寸直径能保存多少条磁道
  • 面密度 (位/平方英寸)：记录密度与磁道密度的乘积

容量 Capacity = 每个扇区的字节数(bytes/sector) x 磁道上的平均扇区数(avg sectors/track) x 磁盘一面的磁道数(tracks/surface) x 磁盘的面数(surfaces/platter) x 硬盘包含的磁盘数(platters/disk)

2. 磁盘操作

磁盘以扇区大小的块来读写数据，对扇区的访问时间(access time)有三个主要的部分：寻道时间(seek time)、旋转时间(rotational latency)和传送时间（transfer time):

  • 寻道时间： 为了读取某个目标扇区的内容，传动臂首先将读/写头定位到包含目标扇区的磁道上。移动传动臂所需的时间称为寻道时间。（现代驱动器寻道时间通常在3~9ms)

  • 旋转时间：一旦读/写头定位到了期望的磁道，驱动器等待目标扇区的第一个位旋转到读/写头下。该步骤取决于硬盘具体的转速，一般来说是7200 RPM

  • 传送时间：当目标扇区1的第一位位于读/写头下时，驱动器等待目标扇区的第一个位旋转到读/写头下。该步骤取决于需要读取的扇区数目

举个例子，假设转速是 7200 RPM，平均寻址时间 9ms，平均每个磁道的 sector 数目是 400，那么我们有：

  • Tavg rotation = 1/2 x (60 secs / 7200 RPM) x 1000 ms/sec = 4 ms
  • Tavg transfer = 60 / 7200 RPM x 1/400 secs/track x 1000 ms/sec = 0.02 ms
  • Taccess = 9 ms + 4 ms + 0.02 ms

从这里可以看出，主要决定访问时间的是寻址时间和旋转延迟

总线

总线是用来传输地址、数据和控制信号的一组平行的电线，通常来说由多个设备共享。

CPU通过总线和对应的接口从不同的设备中获取所需要的数据，然后放入寄存器中等待运算

总线结构

上图展示了一个计算机系统的大致配置，主要部件是CPU芯片，I/O桥，组成主存的DRAM存储器模块以及I/O设备。这些部件由总线连接起来，系统总线连接CPU和I/O桥1，内存总线连接I/O桥和主存，I/O总线连接I/O设备与I/O桥

下面来看一下CPU从磁盘中读数据时发生的过程是怎样的。

CPU使用一种称为存储器映射I/O的技术来向I/O设备发出命令，在使用存储器映射I/O的系统中，地址空间有一块地址是为与I/O设备通信保留的，每个这样的地址称为一个I/O端口，当一个设备连接到总线时，它与一个或多个端口相关联。

  1. CPU通过将命令、逻辑块号和目的存储器地址写到与磁盘相关联的存储器映射地址，发起一个磁盘读，如下图

CPU1

  1. 磁盘控制器读扇区，并执行到主存的DMA传送

CPU2

  1. 当DMA传送完成后，磁盘控制器用中断的方式通知CPU

CPU3

  1. CPU然后从主存读取数据

在磁盘控制器收到来自CPU的读命令之后，它将逻辑块号翻译成一个扇区地址，读该扇区的内容，然后将这些内容直接传送到主存，不需要CPU的干涉，设备可以自己执行读或写总线事务，而不需要CPU干涉的过程，这个过程称为直接存储器访问（DMA)，这种传送称为DMA传送。

在DMA传送完成后，磁盘扇区的内容被安全地存储在主存中以后，磁盘控制器通过给CPU发送一个中断信号来通知CPU，基本思想就是中断会发信号到CPU芯片的一个外部引脚上，这会导致CPU暂停它当前正在做的工作，跳转到一个操作系统例程，这个程序会记录下I/O已经完成，然后将控制返回到CPU被中断的地方。

局部性原理

局部性通常有两种不同的形式：

  • 时间局部性
    • 在一个具有良好时间局部性的程序中，被引用过一次的存储器位置很可能在不远的将来再被多次引用。程序循环、堆栈等是产生时间局部性的原因
  • 空间局部性
    • 在一个具有良好空间局部性的程序中，如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置

举个例子：

1
2
3
4
5
sum = 0;
for (i = 0; i < n; i++){
    sum += a[i];
}
return sum;

这里每次循环都会访问sum是满足时间局部性的；数组的访问时连续的，属于空间局部性的。

存储器层次结构

下图展示了存储器层次结构体系：

存储器层次结构

这里涉及到缓存的技术，缓存可以看做是把大且缓慢的设备中的数据的一部分拿出来存储到其中的更快的存储设备，在金字塔式存储体系中，每一层都可以看做是下一层的缓存，利用局部性原理，程序会更倾向于访问第k层的数据，而非第k+1层，这样就减少了访问时间

缓存命中

当程序需要访问第k+1层的某个数据对象d时，它首先在当前存储在第k层的一个块中查找d，如果d刚好缓存在第k层中，那么就是我们所说的缓存命中（cache hit)

缓存不命中

如果第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中(cache miss)，当发生缓存不命中时，第k层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了的话，可能就会覆盖现存的一个块。

缓存不命中的种类

缓存不命中有三种：

  • 强制性不命中
    • CPU 第一次访问相应缓存块，缓存中肯定没有对应数据，这是不可避免的
  • 冲突b不命中(Confilict Miss):
    • 在直接相联或组相联的缓存中，不同的缓存块由于索引相同相互替换，引起的失效叫做冲突失效
  • 容量不命中(Capacity Miss):
    • 有限的缓存容量导致缓存放不下而被替换，被替换出去的缓存块再被访问，引起的失效叫做容量失效

缓存利用局部性原理

概括来说，基于缓存的存储器层次结构行之有效，是因为较慢的存储设备比较快的存储设备更便宜，还因为程序往往展示局部性：

  • 利用时间局部性：由于时间局部性，同一数据对象可能会被多次使用，一旦一个数据对象在第一次不命中时被拷贝到缓存中，我们就会期望后面对该目标有一系列的访问命中，因为缓存比低一层的存储设备更快，对后面的命中的服务会比最开始的不命中快很多

  • 利用空间局部性：块通常包含有多个数据对象，由于空间局部性，我们会期望后面对该块中的其他对象的访问能够补偿不命中后拷贝该块的花费

高速缓存

高速缓存存储器是由硬件自动管理的SRAM主存，CPU会首先从这里找数据，其所处的位置如下：

高速缓存

每个高速缓存器地址有m位，形成M=2^m个不同的地址，其关键组成部分为：

  • 一个高速缓存有S=2^s个高速缓存组（cache set)的数组
  • 每个组包含E个高速缓存行(cache line)
  • 每个行是由一个B=2^b字节的数据库（block)组成

高速缓存结构

再次总结一下就是，高速缓存是一个高速缓存组的数组，每个组包含一个或多个行（cache line)，每个行包含了一个有效位，一些标记位，以及一个数据块。

当处理器需要访问一个地址时，会先在高速缓存中进行查找，如果高速缓存中有，那么将数据返回给CPU，如果没有，才接着向主存发起访问。那么高速缓存中查找过程怎样的呢？

首先在查找过程中我们从概念的层面将地址划分为三个部分，如下图：

高速缓存

1. 读取过程

首先通过set index确定要从哪个set中寻找，确定后利用tag和同一个set中的每个cache line进行比对，找到tag相同的那个line，最后再根据block offset确定要从line的哪个位置读起。

当 E=1 时，也就是每个 set 只有 1 个 line 的时候，称之为直接映射缓存(Direct Mapped Cache)，如下图所示

高速缓存2

2. 缓存一致性问题（拓展）

高速缓存实际上既可以保存数据，也可以保存指令，只保存指令的高速缓存称为i-cache，只保存程序数据的高速缓存称为d-cache，既保存指令又包括数据的高速缓存称为统一的高速缓存，现代处理器包括独立的i-cache和d-cache。下面展示一个Intel Core i7的高速缓存层次结构

多核处理器的组织结构

高速缓存虽好，但是它却带来了一个问题就是：缓存一致性问题。在如上图所示的多处理器系统中，每个CPU都有自己的高速缓存，而它们又共享同一主存，当多个处理器都有自己的运算任务都涉及同一块主内存区域时，将可能导致各自的缓存数据不一致的问题。

为了解决缓存一致性问题，需要各个处理器访问缓存时遵循缓存一致性协议（最常见的MESI协议)，在读写时要根据协议来进行操作。

在MESI协议中，每个Cache line有4种状态，分别是：

  • M（Modified) ：这行数据有效，但是被修改了，和内存中的数据不一致，数据只存在于本Cache中
  • E (Exclusive): 这行数据有效，和内存中的数据一致，数据只存在于本Cache中
  • S (Shared): 这行数据有效，和内存中的数据一致，数据分布在很多 Cache中
  • I （Invalid): 这行数据无效

每个Core的Cache控制器不仅知道自己的读写操作，也监听其他Cache的读写操作，假如有4个Core:

  • Core1从内存中加载了变量X，值为10，这时Core1中缓存变量X的cache line的状态是E；
  • Core2也从内存中加载了变量X，这时Core1和Core2缓存变量X的cache line状态转化成S；
  • Core3也从内存中加载了变量X，然后把X设置成了20，这时Core3中缓存变量X的cache line状态转化成M，其它Core对应的cache line变成I（无效）

参考资料

Bagikan Komentar