Home 计算机科学 计算机组成

# Ch3 存储系统

# 存储器概述

# 存储器的分类

  1. 按层次分
  • 主存（小、快、成本高）
  • 辅存（大、慢、成本低）
  • Cache
  1. 按存储介质分
  • 磁表面存储器（磁盘、磁带）
  • 磁芯存储器
  • 半导体存储器（MOS 型、双极型）
  • 光存储器（光盘）
  1. 按存储方式分
  • RAM （随机存储器）: 随机读取存储单元，存取时间与存储单元的物理位置无关。读写方便，主要用作主存和 cache，分静态 RAM 和动态 RAM。
  • ROM （只读存储器）：只能读不能写，非易失性，随机读取。广义的 ROM 也可以通过电擦除进行写入 (EEPROM)
  • SAM （顺序存储器）：按顺序存储，存取时间与存储单元的物理位置有关
  • DAM （直接存储器）：先选取信息所在区域，然后顺序存取。结合了 RAM 和 SAM 的特性（磁盘）
  • Associated memory: 不根据地址而是根据存储内容来进行存取的存储器，可以实现快速地查找快表。既可以按照地址寻址也可以按照内容寻址（通常是某些字段）
  • 串行访问存储器：SAM 和 DAM 都是，所以读写时间和物理位置有关
  1. 按信息的可保存性分类
  • 易失性存储器：断电后丢失数据，如 RAM
  • 非易失性存储器：断电后数据还在，如 ROM，磁盘光盘
  • 破坏性读出：读出数据后数据被破坏
  • 非破坏性读出：读出数据后数据不改变

# 存储器的性能指标

三个主要性能指标：存储容量、单位成本、存储速度

  1. 容量 = 存储字数 * 字长
  2. 单位成本 = 总成本 / 总容量
  3. 存储速度：
    存取时间TaT_a: 启动一次存储器操作到完成该操作所经历的时间，分为读出时间和写入事件
    存取周期TmT_m: 进行连续读 / 写操作所允许的最短时间间隔
    主存带宽BmB_m: b/s, B/s, word/s

存取时间仅为完成一次操作的时间，而存取周期不仅包含操作时间，还包括操作后线路的恢复时间

# 多级层次的存储系统


从上到下价格越来越低，速度越来越慢，容量越来越大，CPU 访问频度越来越低

存储时间与存储周期的关系

  • 透明（transparent）指的是某种机制或技术的存在对使用者来说是不可见或无感知的
    主存 - Cache 之间的数据调用由硬件自动完成，对所有程序员均是透明的
    主存 - 辅存的数据调用由硬件和操作系统共同完成，对应用程序员是透明的

# 主存储器

存储元件：MOS 管

# SRAM & DRAM

RAM: SRAM 静态随机存储器和 DRAM 动态随机存储器
主存主要是 DRAM，Cache 主要是 SRAM，都易失

DRAM 芯片：使用栅极电容存储信息，只要一个晶体管，读写更慢，是破坏性读出，需要重写，成本低，集成度高，功耗低

SRAM 芯片：使用双稳态触发器存储信息（六晶体管 MOS，RS, JK, D）。读写更快，是非破坏性读出，成本高，集成度低，功耗大

栅极电容需要一直刷新给电容充电，触发器不需要刷新，只要不断电状态不会改变

# DRAM 的刷新

  1. 多久需要刷新一次？ 刷新周期：一般为 2ms
  2. 每次刷新多少存储单元？以行为单位，每次刷新一行存储单元
    —— 为什么要用行列地址？减少选通线的数量
  3. 在什么时刻刷新？
    有硬件支持，读出一行的信息后重新写入，占用 1 个读 / 写周期
    假设 DRAM 内部结构排列成 128×128 的形式，读 / 写周期 0.5us
    2ms 共 2ms/0.5us = 4000 个周期
    三种刷新方式：

    刷新以行为单位，再生（重写）只需要恢复被读出来的存储单元
    刷新由存储器独立完成，不需要 CPU 控制
# DRAM 的地址引脚复用技术


行列地址分成两次送，节省了一半的地址线
行列数优化原则：尽量使行、列数相同，且行数较少（因为按行刷新）
目前常用 SDRAM（同步 DRAM），数据交换同步于 CPU 的时钟信号，使得 CPU 不需要等待

# ROM

结构简单、非易失性
类型：

  1. MROM 掩模式 ROM
    在芯片生产过程中写入，无法改变，可靠性高，急程度高，价格便宜，灵活性差
  2. PROM 一次可编程 ROM
    可以用专门的设备写入一次，一旦写入无法改变
  3. EPROM 可擦除可编程 ROM
    可以写入并多次改写，但是编程次数有限且时间长
  4. Flash
    兼有 RAM 和 ROM 的优点，可以不加电长期保存信息，又能在线快速擦除和重写，价格便宜，急程度高，电可擦除重写且速度快
    SSD 固态硬盘基于 Flash，由控制单元和 Flash 组成，长期保存、快速擦除和重写，对比传统硬盘读写速度快。低功耗。但是价格高

# 主存储器的基本组成

核心部件：一个个存储 0 或 1 的存储单元构成的存储矩阵
访问主存时，CPU 把地址送到 MAR，MAR 通过地址总线把地址送到主存中的地址寄存器，地址译码器进行译码，选中相应的内存单元，然后通过控制电路决定读 / 写操作：

  • 读操作：将选中的内存单元的内容通过数据总线送到 MDR 中
  • 写操作：将 MDR 中的内容通过数据总线送到选中的内存单元中
    MDR 的位数和数据总线位数相同，通常等于存储字长；MAR 的位数和地址总线位数相同

# 多模块存储器

DRAM 芯片的恢复时间比较长，有可能是存取时间的几倍（SRAM 的恢复时间较短）。CPU 的读写速度比主存快很多，主存恢复时间太长
—— 利用多个完全相同的存储模块并行工作来提高吞吐率：单体多字存储器，多体低位交叉存储器

  • 双端口 RAM（408 不考，了解即可）

  1. 单体多字存储器
    一般一个存储单元只存储一个 word，但是单体多字存储器一个存储单元存储多个 word，然后读的时候一次性读取这多个字。好处是快，缺点是只有指令和数据连续存放时才能提高存取速度，否则造成不必要的读取。

  2. 多体并行存储器（重点）
    分为高位交叉编址和低位交叉编址两种

    高位交叉编址每一块存储体的高位是一样的，实际上还是顺序存储。因此访问连续内存实际上访问的还是同一块存储体，并不能通过并行加快访问速度
    低位交叉编址的每一块存储体低位相同，因此可以在恢复时间并行存取下一块内存的数据
    存取周期为 T , 存取时间为 r , T = r + 恢复时间
    对于 n 个存储器并行访问的存储器：
    采用高位交叉编址的时间为 n*T
    低位交叉编址为 T + (n-1)*r

  • 轮流启动：每个 bank 的存储位数等于数据总线的位数，此时采用轮流启动
    • 对于低位交叉编址，要保证 m>=T/r ，以保证流水线不间断
    • 理想情况下，m 个 bank 的交叉存储器每隔 T/m 个周期可以读 / 写一个数据，若相邻 m 次访问的当存地址出现在同一个模块内，则会发生访存冲突，此时需要延迟发生冲突的访问请求。
  • 同时启动：如果 m 个 bank 的总位数加起来刚好等于数据总线的位数，则 m 个同时存 / 取

# 主存储器与 CPU 的连接

# 连接原理

通过总线连接（控制、地址、数据）
传输速率 = 总线宽度 / 传输时间
地址总线的位数决定了可寻址的最大内存空间
控制总线指出总线周期的类型和本次输入输出完成的时刻
将多个芯片集成在内存条上，由多个内存条和主板上的 ROM 芯片组成计算机所需的主存空间，通过总线与 CPU 连接

# 主存容量的扩展

数据总线宽度 > 存储字长 —— 位扩展
地址总线宽度 > 存储字数量所需的宽度

  1. 位扩展法：增加存储字长
    由于数据总线宽度大于存储字长，存在浪费情况，必须进行位扩展使数据位数与数据总线位数相等
    如图：

  2. 字扩展法
    地址总线存在浪费情况，对存储字的数量进行扩展
    用多出来的地址线提供 CS 片选信号，决定输出的是哪个芯片的数据

  • 线选法：n 条多余的地址线，对应 n 个选片信号，地址空间不连续造成地址空间浪费（只能有一个 1 有效），电路简单
  • 译码器选法：n 条多余的线对应2n2^n 个选片信号，地址空间可以连续
  1. 字、位同时扩展
    既增加存储字的数量，又增加存储字长

# 存储芯片的地址分配和片选

见上方线选法译码器选法

# 存储器与 CPU 的连接

…
片选信号还与 CPU 的方寸控制信号MREQ‾\overline{MREQ} 有关（低电平有效），若 CPU 访问 IO 则此信号为高电平
MAR 位数要看主存地址空间大小，而不能看实际上用了多少位

# 外部存储器

磁盘存储器是以磁盘为存储介质的存储器，优点：容量大，价格低；记录介质可重复使用；可以长期保存；非破坏性读出。缺点：存取速度慢；机械结构复杂；对工作环境要求高

# 磁盘存储器

  1. 磁盘存储器

  • 组成：磁盘驱动器，磁盘控制器，盘片

  • 存储区域：扇区（也称块）是磁盘读写的最小单位，按块存取

    • 磁头数 (Heads)：一个记录面对应一个磁头
    • 柱面数 (Cylinders)：表示每面盘片上的磁道数，不同记录面的相同位置的磁道构成一个柱面
    • 扇区数 (Sectors)：每条磁道上有多少扇区

  • Disk Cache

    • 在内存上的一片区域，用来缓冲被送到磁盘上的数据。优点：写磁盘时按簇进行，可以避免频繁地用小块数据写；中间结果数据写回之前可以被快速再次使用

  • 磁记录原理

    • 原理：当磁头和磁性记录介质有相对运动时，通过电磁转换完成读 / 写操作。
    • 编码方法：按某种方案（规律），把一连串的二进制信息变换成存储介质磁层中一个磁化翻转状态的序列，并使读 / 写控制电路容易、可靠地实现转换。
    • 磁记录方式：通常采用调频制（FM）和改进型调频制（MFM）的记录方式。

  • 性能指标

    • 磁盘的容量：一个磁盘所能存储的字节总数称为磁盘容量。磁盘容量有非格式化容量和格式化容量之分。
      非格式化容量是指磁记录表面可以利用的磁化单元总数，非格式化容量 = 记录面数 * 柱面数 * 每条磁道的磁化单元数
      格式化容量是指按照某种特定的记录格式所能存储信息的总量，格式化容量 = 记录面数 * 柱面数 * 每道扇区数 * 每个扇区的容量
      格式化容量 < 非格式化容量

    • 记录密度：记录密度是指盘片单位面积上记录的二进制的信息量，通常以 道密度 、 位密度 和 面密度 表示。道密度是沿磁盘半径方向单位长度上的磁道数；位密度是磁道单位长度上能记录的二进制代码位数；面密度是位密度和道密度的乘积。
      磁盘所有磁道记录的信息量一定是相等的，并不是圆越大信息越多，故每个磁道的位密度都不同，越靠近圆心位密度越大

    • 平均存取时间：
      平均存取时间 = 寻道时间（磁头移动到目的磁道）+ 旋转延迟时间（磁头定位到所在扇区）+ 传输时间（传输数据所花费的时间）
      寻道时间通常取从最外道到最内道时间的一半，旋转延迟时间通常取旋转半周的时间

    • 数据传输率：磁盘存储器在单位时间内向主机传送数据的字节数，称为数据传输率
      假设磁盘转速为 r（转 / 秒），每条磁道容量为 N 个字节，则数据传输率为Dr=rND_r=rN

  • 磁盘地址

  • 磁盘的工作原理
    硬盘的主要操作是寻址、读盘、写盘。每个操作都对应一个控制字，硬盘工作时，第一步是取控制字，第二步是执行控制字。
    硬盘属于机械式部件，其读写操作是串行的，不可能在同一时刻既读又写，也不可能在同一时刻读两组数据或写两组数据。

  1. RAID
    将多个独立的物理磁盘组成一个独立的逻辑磁盘，数据分割交叉存储，并行访问。
  • RAID0：无冗余和无校验的磁盘阵列。
  • RAID1：镜像磁盘阵列。每份数据存两遍，成本太高
  • RAID2：采用纠错的海明码的磁盘阵列。
    逻辑上连续的几个 bit 物理上分散存储在各个盘中 4bit 信息位 + 3bit 海明校验位 —— 可纠正 1bit 错误
    每个码字有 m 个信息位和 r 个冗余位，$ (m+r+1)≤2^r$
    参考 xyx 学长的计网笔记：
  • RAID3：位交叉奇偶校验的磁盘阵列。前三个盘的奇偶校验位写在第四个盘上
  • RAID4：块交叉奇偶校验的磁盘阵列。
  • RAID5：无独立校验的奇偶校验磁盘阵列。在所有磁盘之间分条，并且每个数据块的奇偶校验块 § 写入到同一条带上
    RAID1-RAID5 数据不会损坏

# 固态硬盘 (SSD)

  1. 特性
    属于 Flash memory, EEPROM
    组成：闪存翻译层，存储介质

    数据以页为单位读写，以块为单位擦除只有整个块被擦除之后才能写这一页，若视图修改包含已有数据的页PiP_i，则这个快中所有含有有用数据的页必须被复制到新的空白的块中，才能对PiP_i 进行写操作
    SSD 的优点：随机写很慢，随机读比机械磁盘块，没噪声，能耗低，抗震性好，安全性高
  2. Wear Leveling 磨损均衡
    重复擦写块就会磨损坏，一般是几百次到几千次
    (1) 动态磨损均衡：写入时优先选择擦除次数少的新闪存块，只在写入时触发，仅考虑可用空间（对于冷数据不包括在空间池中，减少了可以用的 block 数量）
    (2) 静态磨损均衡：就算没有写入，SSD 也会监测并自动进行数据分配，让老的闪存快以读为主，让新的块腾出空间，以写为主：将数据从写入 / 擦除次数较低的 block 移动到其他 block 中，这样可以将低擦写次数的 block 释放出来，添加到可用可用空间池中，以便后续使用。仅覆盖单个闪存芯片单元

# Cache

解决 CPU 和主存速度不一致问题，由 SRAM 组成，通常集成在 CPU 中

# 程序访问的局部性原理

  • 时间局部性：比如循环、数组（每次循环访问一次数组能体现时间局部性）
  • 空间局部性：最近的未来用到的信息很可能和正在使用的信息在存储空间上是临近的（顺序访问数组能体现空间局部性）
    Cache 利用局部性原理，将最近或频繁访问的数据复制到更快但容量较小的存储中，以便提高访问速度和系统性能。

hit/miss 计算
设tct_c 为访问一次 Cache 所需时间，tmt_m 为访问一次内存所需时间，则 Cache 和主存同时被访问总时间为t=Htc+(1−H)tmt = Ht_c + (1 - H)t_m
若先访问 Cache 再访问主存则时间为：t=tc+(1−H)tmt = t_c + (1 - H)t_m

# Cache 工作原理

主存和 Cache 之间以 == 块 (Block)== 为单位进行数据交换

# 映射方式

  1. 直接映射 Directed mapped


    cache 行号 = 主存块号 mod cache 行数
    物理地址结构：
    | tag | index（行号） | byte offset |

index的位数=log2(cache的block数)index的位数 = log_2(cache的block数)

byte offset的位数=log2(cache的block的字节数)byte\ offset的位数 = log_2(cache的block的字节数)

tag的位数=32−index的位数−byte offset的位数tag的位数 = 32 - index的位数 - byte\ offset的位数

在 32 位系统中，一个 word 是 4B；64 位系统中，一个 word 是 8B
Cache 的一行构成：
| valid bit | dirty bit | tag | data |

example






  1. 全相连 Full Associative
    block can go anywhere in cache
    主存地址：
    | tag | byte offset |
    好处是能降低冲突率，每次需要和所有 block 比较是否 hit 开销大，不适合大容量 Cache

  2. 组相连 Set Associative

    物理地址构成：
    | tag | set index | 块内偏移 |
    set index 的位数表示有多少组，

setNum=Cache大小blockSize∗路数setNum = \frac{Cache大小}{blockSize * 路数}

一个四路相联 cache，CPU 字长为 4 字节，内存和 cache 都是以字节编址，cache 和内存交换单位为块，每个块大小为 512 字节，cache 能够容纳 1024 个块。如果物理内存为 32 位地址:
set 数 = 1024/4 = 256
index 位数 = log2 (256) = 8
blockOffset 位数 = log2 (512) = 9
tag 位数 = 32 - 8 - 9 = 17

  • 物理地址构成：| tag 17 位 | set index 8 位 | block offset 9 位 |
  • 计算内存地址 FAB12389（16 进制）在 cache 中可能的位置块号:
    1111 1010 1011 0001 0010 0011 1000 1001
    set index 是 10010001 也就是 145，所以可能的 block 号是 145*4 = 580, 581, 582, 583


n 路组相连需要 n 个比较器，位数 = tag 位数

# 替换算法

  1. Random Replacement
    随机找一块替换，实现简单，命中率低

  2. FIFO
    选择最早进入的 Cache 行的进行替换

  3. LRU
    选择近期用得最少的 Cache 行进行替换，对每个 Cache 行维护一个计数器表示访问的次数，每次替换掉数值最小的。
    2-way Cache 要用 1 bit 来记录，4-way Cache 要用 2 bit 来记录

4-way Cache，有五个块映射到 Cache 同一组，访问顺序是 {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}

# Cache 一致性问题

当 write hit 时：

  1. Write through 直写 / 全写法
    Cache hit 的时候，CPU 不仅写入 Cache，而且写入主存
    为了减少写入主存的时间小号，增加一个 write buffer，CPU 同时写入 Cache 和 write buffer，write buffer 采用 FIFO，当 write buffer 满时，将 write buffer 中的数据写入主存
  2. Write back 写回法
    write hit 时，只把数据写入 Cache，只有此块被 replace 的时候才写入主存。减少了方寸次数，所以给 cache 行设置一个 dirty bit，CPU 写数据时将 dirty bit 置为 1 表示此块被修改过，repalce 时需要写入主存

write miss 时：

  1. Write Allocate 写分配法
    如果发生 write miss，会从内存中加载对应的数据块到 cache 中，然后进行写操作。和 write-back 搭配使用，把后续对该块的修改都缓存在 cache 中
  2. Not-Write-Allocate 非写分配法
    只更新主存不把主存写入 Cache，适用于 write-through，因为即使写入 cache，也会马上写回内存，没必要占用 cache 空间。

write through 通常和 not-write-allocate 一起用，write back 通常和 write allocate 一起用

# 使用分离的指令 Cache 和数据 Cache


# 虚拟存储器

# 基本概念

主存和辅存共同构成了虚拟存储器，对于应用程序员而言，虚拟存储器是透明的。（对 OS 开系统程序员不透明，他们必须管理 TLB）
虚拟存储器具有主存的速度和辅存的容量

  • 允许多个程序之间高效、安全地共享内存
  • 允许单个程序使用超过内存容量的内存

实地址 = 主存页号 + 页内字地址
虚地址 = 虚存页号 + 页内字地址
辅存地址 = 磁盘号 + 盘面号 + 磁道号 + 扇区号

虚拟存储器缺页访问辅存的代价很大，当程序访问某个 virtual page 时，如果该页当前不在主存中，就会发生 page fault，操作系统需要从辅存加载该页到主存，访问很慢所以访问代价大。因此采用 full associative 允许 virtual page 可以加载到主存的任何一个空闲物理页框中，提高命中率。
写操作中处理一致性问题时采用 write back 。主存中的页面状态维护一个 dirty 标志位。当操作系统需要将该页替换出主存时，会检查该页的脏页标志：如果 dirty，说明主存页面数据修改过，必须写回辅存；如果 dirty 为 0，说明主存数据和辅存一致，直接丢弃主存页面，无需写回

# 页式虚拟存储器

  • 基本单位：页
    主存和虚拟地址空间被划分为相同大小的页，主存中的成为物理页（实页、页框、frame），虚拟地址空间中的页称为虚拟页（虚页）
    页表 (page table) 记录了程序的虚页调入贮存时被安排在主存中的位置
    一般的 page 大小从 4KiB ~ 64KiB 不等
  1. 页表 (page table)
    页表放在主存中。

    有效位（Valid Bit）：用于指示一个页面是否已经被加载到主存中。如果有效位被设置为 1，这意味着对应的页面已经在物理内存中，可以立即被访问。如果有效位为 0，则表示该页面当前不在内存中，可能需要从磁盘或其他存储设备中调入。当一个程序尝试访问一个页面时，操作系统会检查页表中的有效位，如果发现页面不在内存中，就会触发一个 page fault，然后将页面从磁盘加载到内存中。
    引用位（Reference Bit）：引用位主要用于页面置换算法中，它记录了页面最近是否被访问过。每当一个页面被访问时，操作系统会将该页面的引用位置为 1。随着时间的推移，如果一个页面长时间没有被访问，它的引用位可能会被清零。当操作系统需要选择一个页面进行置换时，它可能会优先选择那些引用位为 0 的页面。

转换过程：当一个程序尝试访问内存时，它会生成一个虚拟地址。虚拟地址包含两部分信息：页号（Page Number）和页内偏移（Offset）。用 VPN 作为索引查询 page table，检查 valid bit 是否为 1，从页表条目中获取 PPN，PPN 和 page offset 组合成物理地址。

页式虚拟存储器的优点：页面长度固定，页表简单，调入方便
缺点：产生内碎片

  1. 地址转换

    每个进程都有一个页表基址寄存器，存放该进程的页表首地址。然后通过 VPN 作为索引在页表中查找对应的页表项。物理地址 = 物理页号 + 页内地址。

  2. TLB（快表）
    为了减少访问主存的此书，TLB 相当于 page table 的 cache。
    TLB 用 SRAM 实现，不在主存中，工作原理类似于 Cache，通常采用 full associative 或者 set associative。

    通过 VPN 查找 TLB 和 Cache 的查找一样，如果是全相连则直接比较 tag，如果是组相连则通过低位查找 set，然后用高位和 tag 比较。

  3. 具有 TLB 和 Cache 的多级存储系统

    查找时，TLB 和 page table 可以同步进行，如果在 TLB 中找到了，page table 的查找就作废。

# 段式虚拟存储器


按程序的逻辑结构划分，段的长度因程序而异。虚拟地址分为段号和段内地址。虚地址和实地址的转换依靠段表。
段表每行记录某个段的段号、有效位、段长度、段起始地址。
段表本身也是段，一般驻留在主存中
分页对程序员是透明的，分段对程序员是不透明的

段式虚拟存储器的优点：具有逻辑独立性，易于编译、管理、修改和保护，便于多道程序的共享
缺点：产生外碎片

# 段页式虚拟存储器

把程序按逻辑结构分段，再在每段划分固定大小的页。因此段的长度必须是页长度的整数倍，段的起点必须是某一页的起点。
虚地址分为段号，段内页号，页内地址

  • 访问流程：从段表基址寄存器（STBR） 中读取段表的起始地址，用段号（s）作为索引，在段表中查找第 s 个表项，从该表项中取出该段对应的页表起始地址（即页表基址），与段内页号合成得到页表地址（页表项地址 = PTBR + p × 页表项大小），读取第 p 个页表项得到物理页号（PPN），和页内地址合成得到物理地址