存储器系统

背景

面临问题

• 单级存储系统中，主存的存储速度与 CPU 的速度不匹配，造成 CPU 资源的浪费
• 程序运行时访问主存存在明显的局部性特征

局部性原理

无论是存取指令或存取数据，所访问的存储单元都趋于聚集在一个较小的连续存储区域中。

时间上，刚被访问过的存储单元可能不久又将被访问；空间上，刚被访问过的存储单元的临近单位可能不久被访问。

原理

存储器系统通过使用存储器层次结构，将快速、小容量的廉价存储器和慢速、大容量的廉价存储器组合起来，接近理想的快速、大容量存储器。以便快速访问最常用数据，同时又有容量存储其他大量数据。

层次结构

• Cache，通常放在与处理器同一芯片的 SRAM 中。
• Main Memory（主存），也叫物理存储器，包含了虚拟存储器的一部分，可以看作硬盘中常用数据的高速缓存。
• Hard Drive（硬盘），存储不在主存的数据，提供了比主存实际容量更大的存储器空间，通过虚拟内存机制扩展可用内存，称为虚拟存储器。

性能分析

• 缺失率与命中率
  • $MR=\text{Miss Rate}=\frac{\text{Miss Counts}}{\text{Total Access Counts}}$
  • $HR=\text{Hit Rate}=\frac{\text{Hit Counts}}{\text{Total Access Counts}}$
  • $MR=1-HR$
• 平均存储器访问时间：处理器必须等待存储器的每条装入和存储指令平均时间
  • $ATAM=t_{cache}+M{R}_{cache}(t_{MM}+M{R}_{MM}{t}_{VM})$

Cache

Cache，高速缓冲存储器。

在CPU和主存间设置一容量较小的高速缓存，其中总是存放最活跃（被频繁访问）的程序块和数据，大多数情况下，CPU能直接从这个高速缓存中取得指令和数据，而不必访问主存。

这就是Cache。

解决的问题

1. Cache 里要存放哪些数据？
2. 如何判断数据是否在 Cache 中，以及如何在 Cache 里寻找数据？
3. Cache 满后，如何用新数据替换旧数据？

基本概念

• 容量（Capacity，C）
• 数据块（Block）
  • 块大小（b）：一个高速缓存块中的字数，也表明主存与Cache之间局部总线的宽度。为了利用空间局部性，一般一个块都大于 1 个字。
  • 块数（B）： $B=C/b$
• 标记（Tag）：每一 Cache 数据块有一个标记字段，用来保存该 Cache 数据块对应的主存数据块的地址信息，用以唯一区分用于区分映射到同一 Cache 行的不同主存块。
• 有效位（Valid Bit）：Cache 中每一 Block 有一个有效位，用于指示相应数据块中是否包含有效数据。
• 行（Line)：Cache 中一个 Block 及其 Tag、Valid Bit 构成 1 行。
• 组（Set）：一个高速缓存可被组织为 S 组，每一组有一个或多个数据块。
• 路（Way）、相联度（Degree of Associative）：Cache 相关联的等级，每一路具有独立的地址比较机构，各路地址比较能同时进行（一般与组结合），路数即指一组内的块数。

因此 Cache 为一个二维阵列，行为组，列为路；每一个项包括一个块、一个 Tag 和一个有效位（合称为一行，注意与前面的行区分）。

基本结构

• 存储机构：一般采用 SRAM 构成。以数据块 Block （若干字）为单位，Cache 块大小与主存块大小相同。
• 地址机构：地址比较、转换机制，地址标记（Tag），一个 Block 具有一个 Tag。
• 替换机构：记录 Block 的使用情况，替换策略，有效位（v）记录对应数据块中的数据是否有效。

映射

主存中数据的地址和 Cache 中数据的位置之间的关系称为映射。

• 把主存划分成大小相等的主存块（Block）
• Cache 中存放一个主存块的对应单位称为 Cache 块（Block）
• Cache 块大小与主存块大小相等

映射关系

主存地址划分：

块大小为一个字时
块大小大于一个字时

位数分别为：

• Offset: $\log b$
  • Byte Offset：$\log \text{WordSize(byte)}$
  • Block Offset：块内偏移字数： $\log \frac{b}{WordSize(byte)}=\log WordCounts$
• Set：$\log S$
• Tag: 剩余位数

访问逻辑：

1. 用 Set 找 Cache 行
2. 用 Tag 判断是不是要的主存块
3. 用 Valid Bit 判断是否有效
4. 用 Offset 找块内字、字节

映射方式

Note

以下以每块 1 字为例讲解。

直接映射

每一组只包含一块，$S=B$，因此每一个主存地址都映射到 Cache 的同一组：$K=Addr\mathrm{mod}B$，K 为地址为 Addr 的内存块映射的 Cache 组序号。

因此会有很多主存块被映射至同一个 Cache 块（同一个 Set）。

优缺点

• 优点：实现简单，只需利用主存地址中的区地址，与块地址对应的Cache块中Tag 进行1次比较，即可确定是否命中。
• 缺点：映射关系不灵活。
  • 因每个主存块只能固定地对应某个确定的Cache块，会出现Cache有很多空闲，但新块不能直接写入而需要替换的现象，Cache空间的利用不充分。
  • 由于一组里只有一个缓存块，因此两个映射到同一组的地址常常会冲突，损失率高。

多路组相联

N 路组相联 Cache，通过为一组提供 N 块缓存块的方式减少冲突。每个内存地址仍然映射到唯一的一组，但是可以映射到一组 N 块中的任意一块。

全相联

全相联 Cache 只有一组，其中包含 B 路，即 $S=1$。存储器地址可以映射到任何一块。因此全相联 Cache 可以成为 B 路组相联 Cache。

在相同容量下，全相联 Cache 有最小的冲突损失，但是要更多的硬件比较 Tag。

总结

缺失处理

CPU访问Cache缺失时，CPU必须等待数据装入Cache后才能访问Cache，这期间的时间损失称为缺失损失。块的增大会导致缺失损失的增大。

其中，取出块的时间为第一个字的延迟时间（存储器访问）+ 块的剩余部分的传送时间。

存储组织

Cache的存储组织对缺失损失具有很大的影响

• 单字宽内存组织：CPU 一次请求 1 个字，Cache 一次也只和内存交换 1 个字，内存本身也是 单字宽。
• 多字宽内存组织：CPU 仍然是逐字访问，内存是多字宽的，一次可以返回 多个字。Cache miss 代价减小。
• 单体多字交叉内存组织：内存被分成 多个内存体（bank），不同地址映射到不同 bank，可以并行访问多个 bank。内存吞吐提升。

缺失处理方式

• 块装入后访问：缺失数据块中各字按顺序全部装入Cache后，再从Cache中访问所请求的字（也即引起缺失的字）
• 尽早重启（early restart）：缺失数据块中各字按顺序装入 Cache，一旦所请求的字装入Cache，CPU立即访问该字，控制机构再继续传送剩余数据到cache
• 请求字优先（requested word first）：所请求的字先装入 Cache，CPU立即访问该字，控制机构再按照先从所请求字的下一个地址、再到块的起始地址的顺序继续传送剩余数据到 cache

数据替换

替换策略

• 最近最少使用法（IRU）
  • 被调入或被替换的块，其计数器清0，而其它的计数器则加1
  • 访问命中时，所有块的计数值与命中块的计数值进行比较
    • 如果计数值小于命中块的计数值，则该块的计数值加1
    • 如果块的计数值大于命中块的计数值，则数值不变
    • 最后将命中块的计数器清为0
  • 需要替换时，则选择计数值最大的块来替换
• 先进先出法（FIFO）
  • 当某块被装入或被替换时，该块的计数器清为0，而同组的其它各块的计数器均加1
  • 当需要替换时就选择计数值最大的块被替换掉
• 最小使用频率法（IFU）
• 随机法（RAND）

数据一致性

数据一致性的问题主要由写操作产生，有两种策略：

• 写直达（Write Through）：写 Cache 的同时写主存，效率较低
• 写回（Write Back）：写操作只更新 Cache 中的数据，直到 Block 替换时才将整个 Block 写回主存，一般使用“脏位”（Dirty Bit）来表示 Block 在替换回主存之前是否被修改过

虚拟存储系统

背景

面临问题

• 同时运行的程序对内存的需求之和可能超过计算机实际内存容量
• 单个程序对内存的需求也有可能超过机器实际内容容量
• 存储器保护：
  • 编写编译程序时，不知道程序运行时将和哪些其他程序共享内存
  • 编程者实际上希望把每个程序编译在他自己的地址空间中

解决方法

程序运行时，内存管理采用交换机制（硬件和操作系统实现），进程保存在外存中，进程执行时，只将其活跃部分调入内存（局部性原理）。此时内存可以视为辅存的“高速缓存” 。

这样一种把内存当做辅助存储器的高速缓存的技术，称为虚拟存储器技术。

外存

虚拟存储器的硬件基础。

容量大且价格便宜、非易失，但访问速度显著慢于主存，因此用以提供虚拟化存储系统使用的容量。

不与 CPU 直接交换信息，通过需通过 I/O 机制将数据调入物理存储器，即主存，来访问（主存内保存其中一部分内容，类似于 Cache 之于主存）。

典型代表：

• 磁表面存储器：HDD、软盘
• 光介质存储器：光盘
• 半导体存储器：SSD、U 盘

磁硬盘基本结构

1. 数据组织形式：

   • 盘面
   • 磁道
   • 扇区

   每个磁道包含的扇区数相同；
   最小访问单位是扇区。

2. 性能指标：

   • 记录密度
     • 道密度：磁盘沿半径方向单位长度的磁道数
     • 位密度：单位长度磁道记录二进制的位数
   • 存储容量：盘面数(磁头数) * 每盘面的磁道数 * 每磁道的扇区数 * 扇区容量
   • 访问时间（也称寻址时间）: $T_A=T_S+T_W$
     • 寻道时间 $T_S$ ：磁头从当前位置定位到目标磁道所需时间（平均值）
     • 寻区时间 $T_W$ : 磁头定位到目标磁道后，等待目标扇区旋转到磁头下所需的时间（平均值）, 一般是转半圈的用时。
   • 数据传输率 $D_r$ ：单位时间内传输的数据位数（bit/s）
     • $R=(\text{转速每秒圈数})\times (\text{每磁道扇区数})\times (\text{每扇区字节数})\times 8$

基本概念

• 空间：
  • 用户编程空间：程序可以访问虚拟存储器中任意地方，其地址称为虚地址，对应虚存空间。
  • 物理内存空间：主存的空间，计算机物理内存的访问地址称为实地址，其对应的存储空间称为物理空间或主存空间。

flowchart TD
    A[程序访问虚拟地址空间] -->|虚拟地址| B[MMU + OS 映射]
    B --> C[物理内存（DRAM）]
    B --> D[外存（Swap / 扩展存储）]

    style A fill:#f9f,stroke:#333,stroke-width:1px
    style B fill:#ff9,stroke:#333,stroke-width:1px
    style C fill:#9f9,stroke:#333,stroke-width:1px
    style D fill:#9cf,stroke:#333,stroke-width:1px

• 页：虚拟存储器分为虚页，物理存储器分为物理页。虚页可以映射到任意实页，类似于全相联 Cache。
• 地址格式：
  • 虚地址：虚页号 + 页内地址
  • 实地址：实页号 + 页内地址
• 页表：记录虚页与实页的映射关系，实现虚实地址的转换。页表建立在内存中，操作系统为每道程序建立一个页表。页表用虚页号作为索引，页表项包括虚页对应的实页号和有效位。因此页表有虚页个数行，每行为实页号位数 + 1 有效位。
• 页表寄存器：保存页表在内存中的首地址

这些概念与 Cache 有相似之处：

工作原理

1. 虚拟地址空间
   • 程序看到的连续地址空间，即虚拟存储器（虚存）。
   • 不关心数据到底在主存还是外存。
2. 外存映射
   • 操作系统把外存（swap / 扩展存储）划分成页（page），每页大小通常和虚拟页大小一致。
   • 虚拟页可以映射到外存中的任意页，形成一个逻辑连续的虚拟空间。
   • 虚地址通过页表映射到实地址，因此每次访存，需要访问两次物理存储器：一次访问页表，一次访问数据。
3. 主存缓存
   • 为了加速访问，OS 会把活跃的虚拟页加载到主存（DRAM）中。
   • 主存中的页面就是 物理页，对应 CPU 可以直接访问的物理地址。

地址转换

• 页地址格式：页号 + 页偏移量
  • $PageOffset=\log PageSize(Byte)$，说明页内字节位置。
  • $PageNumber=AddrSize-PageOffset$，同时也是总页数。

通过页表建立虚地址的页号和实地址的页号之间的映射关系。

因此虚地址和实地址的最低的 Page Offset 位是一样的，从虚地址到实地址只需要转化页号。

页表

如前所述：

记录虚页与实页的映射关系，实现虚实地址的转换。页表建立在内存中，操作系统为每道程序建立一个页表。页表用虚页号作为索引，页表项包括虚页对应的实页号和有效位。因此页表有虚页个数行，每行为实页号位数 + 1 有效位。

因此页表为一个连续数组，以虚地址为索引，每一项记录了虚拟页是否在内存、在内存的实地址。

页表在内存的位置是任意的，由 OS 决定，使用页表寄存器保存页表在内存中的基地址。

转换后备缓冲器（TLB）

如果每一次访存都需要页表，那么虚拟存储器性能会受到严重影响。因此考虑到页表访问的局部性，如果处理器可以记住最后读出的页表表项，很可能可以重用映射而不需要重复访问页表。

因此处理器可以把最近使用的页表表项保存在名为 转换后备缓冲器（快表，TLB） 的小型高速缓存中。

处理器在访问页表前，先在 TLB 查找表项。如果命中则返回相应实页页号，否则从页表中获取映射关系。

TLB 一般使用全相联模式，每一项保存虚页页号、对应的实页页号、有效位、修改位