存储系统

存储器概论

存储器用来在计算机中存储程序和数据

为此，对存储介质有如下基本要求：

  • 能够有两个稳定状态
  • 两个状态容易识别
  • 两个状态转换方便

存储器按照访问方式分类：

  • 随机访问存储器（RAM）
    • 访问时间与位置无关，例如半导体存储器
  • 顺序访问存储器（SAM）
    • 按存储位置依次访问，例如磁带
  • 直接访问存储器（DAM）
    • 可以随机访问或顺序访问，例如磁盘
  • 关联访问存储器（CAM）
    • 根据内容访问，例如Cache和TLB

存储器的目标是大容量、高速度，但目前的现实是，速度越快容量越小

解决方案：层次存储器系统

层次存储器系统

  • 高速度
    • 使用速度高的静态存储器作为较小容量的高速缓存
  • 大容量
    • 使用价格、速度适中的动态存储器作为主存储器
  • 低成本
    • 使用价格最低的磁盘存储器作为辅助存储器和虚拟存储器的载体

程序运行的局部性原理：

  • 时间上：最近访问过的程序和数据很可能再次被访问
  • 空间上：被访问的程序和数据在空间上集中
  • 顺序上：顺序执行比转移执行可能性大

层次系统之间应满足的原则：

  • 一致性原则：不同层存储器中的同一信息应当保持相同的值
  • 包含性原则：内层的信息一定存在于外层存储器中

沿存储金字塔向下，速度变慢，每容量价格降低，CPU访问频率降低，可靠性降低，容量增大

  • 依次为：寄存器→缓存→主存→磁盘→磁带或光盘

动态存储器

工作原理

使用单个MOS管存储一个bit，MOS管源极的寄生电容CS中有电荷表示1，无电荷表示0

image-20241212110313606

写1操作：字线高，位线低，电容充电

写0操作：字线高，位线高，电容放电

读操作：字线高，位线高，相当于写0

于是，动态存储器的工作特点为：

  • 破坏性读出：读操作相当于写0，需要在读出后立刻写回——带来预充电延迟
  • 需定期刷新：不进行读写时，电容短路，但由于漏电的存在，需要及时刷新，刷新按行进行
    • 集中刷新：停止所有读写，逐行刷新
    • 分散刷新：每次读写后刷新一行，各行轮流进行
  • 支持快速分页组织：行、列地址要分两次给出，但是连续读写相同行的存储时可以先将行地址锁存，然后只需要送列地址

主存储器通过地址、数据、控制三类总线与其他部件连接：

  • 地址总线：选择主存储器的一个存储单元
    • 其位数决定了最大可寻址空间，注意区分按字节寻址和按字寻址
  • 数据总线：传送数据
    • 其最高数据吞吐是数据总线位数乘总线时钟频率

静态存储器

静态存储器原理：

image-20241212112110055

写操作：字线高，两条位线按待写入数据排布

读操作：字线高，两条位线均高，之后用放大器感知两条位线的变化

静态存储器的特征：

  • 速度块
  • 存储密度低
  • 数据出入共用管脚
  • 能耗、成本高

image-20241212112436614

高速缓冲存储器

位于主存与CPU之间，使用静态存储器实现

与CPU的运行速度基本匹配，且对程序员透明（注：这里的透明指的是程序员不关心高速缓存是否存在，高速缓存是否存在、如何存在不影响程序编写和运行）

缓存参数：

  • 块(Line)：数据交换的最小单位
  • 命中(Hit)：缓存中发现要访问的内容
    • 命中率(HR)、命中时间
  • 缺失(Miss)：需要到较低层次（如主存）中访问块
    • 缺失率(1-HR)、缺失损失
  • 命中时间<<缺失损失
  • 平均访问时间=HR*命中时间+(1-HR)*缺失损失

缓存映射策略

全相连映射

全相连方式中，每个缓存块对主存块的对应关系是任意的

例如，主存为4GB，缓存4KB，块大小4B，则缓存有1024个块，而主存有1G个块

每个缓存块单元中包含以下三项：

  • 有效位（1bit）
  • 标记（30bit），表示当前缓存内容在主存中的块地址
  • 数据（32bit）

判断缓存是否命中的方式为并行地将地址的高30位与缓存标记比较，然后通过1024-1数据选择器

全相连方式使用灵活，但成本高

直接映射

直接映射方式中，将主存块地址分为Tag和Index，同一Index的地址映射到同一缓存单元

例如，主存4GB，缓存4KB，块大小4B，则缓存有1024个块，即Index一共有1024种

主存1G个块，主存块地址位数为30位，取前20位为tag，后10位为index

每个缓存单元包含：

  • 有效位（1bit）
  • 标记（20bit）
  • 数据（32bit）

直接映射缓存中，缓存缺失可能有两种原因：

  • 对应index处的有效位为0（启动失效）
  • 对应index处缓存有效，但tag不匹配（冲突失效）

特点：利用率低，命中率低，效率低，成本低

多路组相连

直接映射和全相连的折中方案，组内为全相连，组间为直接映射

缓存一致性保证策略

缓存内存储的数据必须与主存中的对应数据完全一致，这是缓存成立的前提

因此，需要在发生数据写入时需要考虑将数据写回缓存还是写回主存

写直达 (Write through)

是效率低的强一致性保证手段

  • 缓存命中的写
    • 同时写缓存和主存
  • 缓存缺失的写

拖后写 (Write back)

是效率高的弱一致性保证手段

缓存命中时先只写缓存，不写主存，选择合适的时间写主存

写分配和非写分配

写分配和非写分配是当写入缓存缺失的块时的策略：

  • 写分配：寻找一个块将被写的块放入，再按照缓存命中的写处理
  • 非写分配：直接写主存

MESI态

  • 修改态（M）：此缓存中的数据已被修改且和主存中不同（“脏数据”），只能从此缓存中获取
  • 独占态（E）：此缓存中数据与主存相同，但其他缓存中没有副本
  • 共享态（S）：此缓存中数据与主存相同，且其他缓存中可能有副本
  • 无效态（I）：尚未装入数据

状态转移图（其中远程读写表示读写了其他缓存中的相同数据）

image-20241212115957662

缓存命中率分析

四类缓存缺失：

  • 必然缺失
    • 开机或进程切换
    • 首次访问某数据块
    • 对策：预取
  • 容量缺失
    • 活动数据超过了缓存大小
    • 对策：增大缓存容量
  • 冲突缺失
    • 多个内存块映射到同一缓存块
    • 对策：增加缓存容量、增加相连的路数
  • 无效缺失
    • 其他进程修改了主存数据，使缓存数据无效

影响缓存命中率的因素：

  • 缓存容量
  • 缓存块大小
  • 地址映射方式（多少路？）
  • 替换算法（同一标签的组满了之后，替换哪一行出去）
  • 多级缓存

缓存替换策略：

  • 最近最少使用（LRU）
    • 满足程序局部性要求，有较高命中率，但硬件实现复杂
  • 先入先出（FIFO）
    • 满足时间局部性，实现简单
  • 随机替换（RAND）
    • 实现简单，命中率也不太低

缓存接入系统的体系结构

  1. 侧接法

    • 和CPU、主存在总线上并列
    • 结构简单，成本低，但总线会高占用

  2. 隔断法

    • 缓存将CPU与主存在总线上隔断
    • 支持总线并发，但结构复杂，成本较高

虚拟内存

虚拟内存的意义

  1. 独立的逻辑地址空间：每个进程在自身视角认为独占虚拟内存
  2. 实现内存共享：不同进程的不同虚拟页可能映射到相同物理页
  3. 实现内存保护：页表中存放访问权限

段式存储管理

段式内存管理使用段表，包含如下内容：

  • 段表基地址
  • 段表项
    • 段起始地址
    • 段长
    • 装入位
    • 保护、共享等标志

段的分界和程序或数据的自然分界相对应，段长动态可变，段起点、终点不变，空间分配困难，容易产生碎片

页式存储管理

使用页表，与段式不同，页的大小固定，页起终点总是按页大小对齐

页表大小可能很大，因此需要采用层次页表或反转页表

转换旁路缓冲 (TLB)

TLB通常容量较小，最多128-256个表项，可以使用全相连，但一般使用N路组相连

页替换算法

  • 最近最少使用（LRU）
    • 将页按照最近一段时间的访问频率排序，当访问一个页时，将其移到表头，替换时替换表尾页
    • 被替换页最好是“干净”（即未被修改过）的

磁盘

之前提到的SRAM、DRAM都属于易失性存储，掉电后信息会丢失，访问粒度小（字节或缓存块），但访问速度快

磁盘属于非易失性存储器，访问很慢，但掉电后信息不丢失，访问的粒度很大（数据块）

磁盘使用磁颗粒的不同偏转方向来区分不同的状态

磁盘需要串行访问而非随机访问，访问时间与存储位的物理位置有关

磁盘的主要技术指标：

  • 存储密度：单位大小磁层表面存储的二进制信息量
  • 存储容量：总信息量
  • 寻址时间
  • 数据传输率
  • 误码率
  • 价格

磁头使用软磁材料，磁记录材料使用硬磁材料

磁记录方式

指使用磁层介质中的磁化翻转序列（表现为磁头读取时线圈中电流的变化）编码二进制信息的方法

评价标准有编码效率、自同步能力、读写可靠性等

常见的磁记录方式：

  • 归零制（RZ）：线圈中正脉冲为1，负脉冲为0，两个信息位之间线圈中电流为零
  • 不归零制（NRZ）：线圈中一直有正或负脉冲
  • 见1翻转的不归零制（NRZ1）：只有见到1才改变电流的方向
  • 调相制（PM）：使用边沿表示0和1
  • 调频制（FM）：周期中心和边缘都翻转为1，只有边缘翻转为0
  • 改进的调频制（MFM）：只有连续两个或以上的0时才在位周期开始位置翻转

image-20241212155817012

上图中每两条竖直线之间为一个位周期

磁盘访问过程

寻道：将磁头移动到正确的磁道上（圆形磁盘自内向外布有若干圈磁道）

寻找扇区：等待磁盘旋转到需要访问的扇区

数据传输：读写数据

因此，硬盘具有每面磁道数、每个磁道扇区数等参数，扇区是磁盘访问的最小单位

外磁道比内磁道的扇区数多一些，可以更好利用面积

RAID盘

**RAID盘 (Redundant Array of Inexpensive/Independent Disks)**是一种通过并行I/O来提高磁盘性能的技术

RAID的目标：

  • N个磁盘的容量
  • 1/N的访问时间
  • 更高的性价比
  • 采用冗余技术来提高存储信息的可用性（能正常工作的占比）

下面介绍RAID技术发展的若干个阶段

RAID0

RAID0将多个廉价磁盘模拟的单个虚拟磁盘划分成带(Strip)，每带k个扇区

设RAID阵列有N个磁盘，则将所有扇区按照编号模N的余数装载在对应的磁盘上，即分带

这样如果需要读取N个连续的带，则可以并行进行，且此操作对软件透明

但这样的做法没有冗余，不算真正的RAID

RAID1

将之前的N块磁盘再复制一份备份，写入磁盘时同时对两份磁盘写入，而读磁盘的时候可以负载均衡地读取任意一个磁盘

写操作效率不变但读操作变快

RAID2

将单个虚拟磁盘上的字节分解成4位的半字节，每个半字节配备3位海明码，形成7位字，7位字的每一位分别存储在7个磁盘上

要求驱动器同步转动

RAID3

与RAID2类似，但采用奇偶校验

RAID4

和RAID0类似，在额外的驱动器上写校验码，主磁盘崩溃时可以通过校验盘恢复

校验盘负担较重

RAID5

为了解决校验盘负载重的问题，将校验位循环分配在每块盘上

RAID6

使用二维校验码

固态硬盘

固态盘不使用机械盘中的旋转装置和磁头，没有移动的机械结构

由控制单元和存储单元组成

固态盘存储单元经过多次擦除后会不可靠

SSD的层次结构：

  1. package，一个存储芯片
  2. die
  3. plane，不同plane可以并行操作
  4. block，最小的擦除单位（MB粒度）
  5. page，最小的读写单位（KB粒度）

SSD的写入不会写入到之前的页，可以写入到距离非常遥远的新页，使用FTL层来维护逻辑地址和物理地址的映射关系

FTL：Flash Translation Layer，进行地址翻译的同时完成磨损均衡（FTL会选择目前擦写次数较少的页面进行写入）

SSD的垃圾回收：将回收块中有效页移动到其他块后擦除该块