Loading... ## 存储系统的基本概念 ### 存储器的层次化结构 ![image-20240814142210004.png][1] - 辅存中的数据需要调入主存后才能被 CPU 访问。 - 主存和辅存间存在虚拟存储系统，由操作系统实现，用以解决主存容量不够的问题。 - Cache 和主存之间的数据通路可以解决主存和 CPU 速度不匹配的问题。 ### 存储器的分类 #### 按层次结构 同上面的层次结构图。 #### 按存储介质 - 半导体存储器：内存等。 - 磁表面存储器：如磁盘，磁带。 - 光存储器：以光介质存储信息。 #### 按存取方式 - 随机存取存储器 (Random Access Memory, **RAM**) ：读写任何一个存储单元所需的时间都相同，与存储单元所在的物理位置无关，比如内存条。 - 顺序存取存储器 (Sequential Access Memory, **SAM**) ：读写一个存储单元所需的时间取决于存储单元所在的物理位置，比如磁带。 - 直接存取存储器 (Direct Access Memory, **DAM**) ：既有随机存取的特性，也有顺序存取的特性。先直接选取信息所在的区域，然后再按照顺序方式存取，比如机械硬盘。 - 相联存储器 (Associative Memory) ，即可以按照内容访问的存储器 (Content Addressed Memory, **CAM**) ：可以按照内容检索到存储位置进行读写。"快表" 就是一种相联存储器。 > SAM 和 DAM 都可以被称为串行访问存储器，其特点是读写某个存储单元所需的时间与存储单元的物理位置有关。 #### 按信息的可更改性 - 读写存储器 (Read/Write Memory) ：可读也可写的存储器，如磁盘，内存等。 - 只读存储器 (Read Only Memory) ：只能读，不能写的存储器，如蓝光光碟。 ROM 其实也可多次读写，但必须把里面的内容全部擦除再重新写入，较麻烦。 #### 按信息的可保存性 - 易失性存储器：断电后存储信息会消失的存储器，如内存，Cache等。 - 非易失性存储器：断电后存储信息依然可以保留的存储器，如磁盘。 - 破坏性读出：信息读出后，原存储信息会被破坏。如 DRAM 芯片，读出数据后要进行重写。 - 非破坏性读出：信息读出后，原存储信息不会被破坏。如 SRAM 芯片，光盘等。 ### 存储器的性能指标 1. 存储容量：存储字数 $\times$ 存储字长。 2. 单位成本：每位价格 = 总成本 $\times$ 总容量。 3. 存储速度：数据传输率 = 数据的宽度 $\times$ 存储周期。 (数据的宽度即存储字长) ![image-20240814144021451.png][2] - **存取时间 (Ta)** ：从启动一次存储器操作到完成该操作所经历的时间，分为读出时间和写入时间。 - **存取周期 (Tm)** ：存取周期又称读写周期或访问周期。它是存储器进行一次完整的读写操作所需要的全部时间，即连续两次独立地访问存储器操作之间所需的最小时间间隔。 **主存带宽 (Bm)** ：主存带宽又称**数据传输率**，表示每秒从主存进出信息的最大数量。单位为 字/秒，字节/秒 (B/s) ，或位/秒 (b/s) 。 ## 主存储器的基本组成 ### 存储单元 前面提到过主存储器逻辑上由**存储体，MAR，MDR**组成，它们在时序控制逻辑电路的控制下相互配合。 ![image-20240819121322214.png][3] 其中的存储体中存放着具体的二进制数据。每个存储体由许多存储单元组成，而每个存储单元由存储元组成： ![image-20240819122133445.png][4] - MOS 管：当输入的电压达到一定水平时，MOS 管可以导电，反之则表现为绝缘体。因为可以在导体和绝缘体之间转换，因此被称为半导体。 - 电容：可以保存一定的电荷，因此有两种状态，可以对应二进制的 0 和 1 。 将多个存储元连接在一起，就可以同时读出或写入多个二进制信息： ![image-20240819121549377.png][5] 如上图，给红线加上电压，就相当于给每个 MOS 管传输一个二进制 1 ，从而可以通过绿线读出每个存储元中的二进制数据。此时每行的存储元数量就是存储字长。 ### 译码器 CPU 会把想要获取的数据地址放入 MAR 中，然后由**译码器**将地址翻译，并给对应存储单元加上电压，从而将数据读入 MDR 中。 ![image-20240830210913511.png][6] - **每一个地址都对应一条译码器的输出线**。假设 MAR 有 $n$ 位，对应的存储单元就有 $2^n$ 个。译码器会根据 MAR 的这 $n$ 位地址转化成某一条字选线的高电平信号。 ### 控制电路 二进制数据是通过电信号来传输的，电信号在**最开始的时候可能会不稳定**，因此需要一个**控制电路**，在 MAR 中的电信号稳定后才开启译码器。数据输出也是同理，在电信号稳定后控制电路才会打开 MDR 接收数据。 控制电路还会对外提供几个引脚： - 片选线：传输芯片选择信号或者芯片使能信号，用来选择存储芯片。 - 读写控制线：可能有一条或者两条。 若有两条，$\overline{WE}$ 表示允许写，$\overline{OE}$ 表示允许读； 若只有一条，则 $\overline{WE}$ 表示低电平写，高电平读。 ### 整合 隐去内部细节，得到存储芯片的完整构造： ![image-20240830214644069.png][7] 一个内存条中可能包含多个存储芯片，因此需要片选线来确定需要选择哪一个芯片。 ### 容量表示方法 存储体的总容量可以用多少 bit 来表示，也可以使用 存储单元个数 $\times$ 存储字长 来表示。 比如一块存储芯片是 $8K \times 8$ 位，其中第一个 $8K$ 表示有 $2^{13}$ 个存储单元，每个存储单元中包含 8 位信息 (存储字长为 8 位) 。 ### 寻址 现代计算机通常是**按字节编址**的 (每个字节对应一个地址) ，但也支持按字寻址，按半字寻址，按双字寻址。 ![image-20240830223633814.png][8] ### 考点 - 根据存储芯片的一些参数信息，判断该存储芯片的引脚数量。 需要判断地址线和数据线有多少根，每根地址线或数据线都会对应一个金属引脚；片选线对应一个金属引脚；读写控制线需要根据参数来判断是一根还是两根；此外还有供电引脚，接地引脚等。 ## SRAM 和 DRAM - SRAM：Static Random Access Memory ，静态 RAM ，常用于 Cache ，使用**栅极电容**存储信息。 - DRAM：Dynamic Random Access Memory ，动态 RAM ，常用于主存，使用**双稳态触发器**存储信息。 > DRAM 属于已经过时的技术，目前主流的 DDR4 ，DDR5 主存都是采用 SDRAM 芯片。 ### 存储元件区别 ![image-20240831011715703.png][9] - 栅极电容制造成本低，集成度高，功耗低。 - 双稳态触发器制造成本高，集成度低，功耗大。 ### DRAM 的刷新 电容内的电荷只能维持 2ms 左右。这意味着即使不断电，2ms 后栅极电容内保存的信息也会消失。解决方法是定时对 DRAM 进行**刷新**操作。 > 刷新是由存储器独立完成的，不需要 CPU 的控制。 - 刷新周期：一般为 **2ms** 。 - 每次刷新的存储单元数量：以行为单位，每次刷新一行。 - 刷新操作：有对应的硬件支持，可以读出一行信息后重新写入，占用一个读写周期。 #### 二维存储矩阵 采用行列地址的原因：如果使用一维的方式来存储的话，每个存储单元都需要对应译码器的一根字选择线，因此 $n$ 位地址就需要在译码器上接 $2^n$ 根选通线，这在目前是难以实现的。 ![image-20240904215719014.png][10] 若使用二维的排列，则只需要 $2^{\frac{n}{2}}$ 根选通线，数量级大大减少。 ![image-20240904220142508.png][11] ##### 行列地址译码 以 8 位地址为例，前 4 位作为行地址，后 4 位作为列地址，分别传入行地址译码器和列地址译码器，得到最终要获取的存储元。存储元上有两条选通线，只有两条选通线都为高电平时才会输出数据。 ![image-20240904222806882.png][12] 由于 DRAM 容量较大，因此会采用**地址线复用技术**，也就是使用同一条地址线分批传送行地址和列地址，这样可以使需要的地址线和芯片引脚减少。SRAM 容量小，集成度低，因此可以不使用该技术。 #### 刷新方式 假设 DRAM 内部结构排列成 $128 \times 128$ 的形式，存取周期为 0.5us ，因此 2ms 内共有 4000 个周期。 - **分散刷新**：每次读写完都刷新一行。此时系统的存取周期变为 1us ，前 0.5us 用于正常读写，后 0.5us 用于刷新某行。 ![image-20240904224944410.png][13] - **集中刷新**：集中安排一段时间用于刷新，这段时间内无法访问存储区，称为 "访存死区" 。 ![image-20240904225025309.png][14] - **异步刷新**：2ms 内每行刷新一次即可，因此可以把刷新的操作分散到整个时间段内。 ![image-20240904225223933.png][15] ### 特点对比 | 类型特点 | SRAM | DRAM | | ----------------------- | ------ | ------------------- | | 存储信息 | 触发器 | 电容 | | 破坏性读出 | 否 | 是 | | 是否需要重写 | 否 | 是 | | 运行速度 | 快 | 慢 | | 集成度 | 低 | 高 | | 发热量 | 大 | 小 | | 存储成本 | 高 | 低 | | 易失性 (断电后信息消失) | 易失 | 易失 | | 是否需要刷新 | 不需要 | 需要 | | 送行列地址 | 同时送 | 分两次送 (地址复用) | ## 只读存储器 ROM - RAM 芯片：易失性，断电后数据消失。 - ROM 芯片：非易失性，断电后数据不会丢失。 ### 各种 ROM - MROM (Mask Read-Only Memory) ：掩模式只读存储器 厂家按照客户需求，在芯片生产过程中直接写入信息，之后**任何人不可重写** (只能读出) 。 可靠性高，灵活性差，生产周期长，只适合批量定制。 - PROM (Programmable Read-Only Memory) ：可编程只读存储器 用户可用专门的 PROM 写入器写入信息，**写一次后就不可更改**。 - EPROM (Erasable Programmable Read-Only Memory) ：可擦除可编程只读存储器 允许用户写入信息，之后用某种方法擦除数据，**可进行多次重写**。 - UVEPROM (ultraviolet rays) ：用紫外线照射特定区域 8 ~ 20 分钟，可**擦除所有数据**。 - EEPROM (Electrically EPROM ，又称为 E$^2$PROM) ： 可用 "电擦除" 的方法擦除**特定的字**。 - Flash Memory ：闪速存储器 (闪存) ，如 U 盘，SD 卡等。 在 EEPROM 的基础上发展而来，断电后也可保存信息，且**可进行多次快速的擦除重写**。由于闪存需要先擦除再写入，因此闪存的写速度要比读速度要慢。 > 每个存储元只需要单个 MOS 管，因此闪存位密度比 RAM 高。 - SSD (Solid State Drives) ：固态硬盘 由控制单元 + 存储单元 (Flash 芯片) 构成，与闪速存储器的核心区别在于控制单元不一样，但存储介质都类似，**可以进行多次快速擦除重写**。 SSD 速度快，功耗低，但价格高。目前个人电脑上常用 SSD 取代传统的机械硬盘。 > 手机辅存也使用 Flash 芯片，但相比 SSD 使用的芯片集成度高，功耗低，价格贵。 ### 计算机内的重要 ROM 主存是使用 RAM 芯片制造的，所以断电后主存内是没有数据的。因此电脑开机时需要从主板上的 BIOS 芯片 (ROM) 中读取数据，并通过 BIOS 里面的**自举装入程序**引导装入操作系统。 ![image-20240905005404903.png][16] > 一般认为内存条就是主存，但实际上，主板上的 ROM 芯片也是主存的一部分。 > > 统一编址：如 ROM 芯片占 1KB ，那么主存中 0~1023 这片地址就是分配给 ROM 的。 ## 多模块存储器 DRAM 是破坏性读出，这意味着读取数据之后要花费时间来恢复主存中的数据，恢复所需要的时间可能比主存存取数据的时间要长几倍。之前提到过 CPU 的速度是比主存快很多的，因此 CPU 想要连续读写主存的时候就会被恢复时间拖累。 ### 单体多字存储器 类似于之前存储系统中的位扩展，将多个存储体合并成一个进行读写： ![image-20240905222923188.png][17] - 灵活性差，每次只能同时读取 $m$ 个字，不能单独取其中某个字。 - 指令和数据在主存内必须是连续存放的，否则会读入冗余信息。 - 即使会读冗余数据，也可以很大提升主存的读取速度。 ### 多体并行存储器 将多个存储体进行编码，和存储体内的地址拼接在一起。这里有两种拼接方法： #### 高位交叉编址 ![image-20240906004317373.png][18] - 体号放在体内地址的前面，体内地址顺序存放，所以又称为顺序存储。 - 只要使不同请求源同时访问不同的体，就可实现并行访问。 - 通常内存访问都是顺序访问的，所以实际效果相当于**单纯的扩容**。 设每个存储体的存取周期为 $T$ ，存取时间为 $r$ ，$T = 4r$ ，那么连续取 $n$ 个存储字的耗时为 $nT$ 。 ![image-20240906004839889.png][19] #### 低位交叉编址 > 内存的 "双通道" 就是低位交叉编址。 ![image-20240906004354928.png][20] - 低地址表示体号，高地址表示体内地址，因此访问数据的时候是交替访问所有存储体的，因此顺序读取时可以充分利用恢复时间。 - 采用 "流水线" 的方式进行并行存取。 (宏观上并行，微观上串行) - 宏观上一个存储周期内，$m$ 体交叉存储器可以提供的数据量为单个模块的 $m$ 倍。 设每个存储体的存取周期为 $T$ ，存取时间为 $r$ ，$T = 4r$ ，那么连续取 $n$ 个存储字的耗时为 $T + (n - 1)r$ 。 > 宏观上 $(n \to +\infty)$ 读写一个字的时间接近 $r$ 。 ![image-20240906005312611.png][21] #### 特点 - 每个模块都具有相同的容量和存取速度。 - 各模块都有独立的读写控制电路，地址寄存器和数据寄存器。它们既能并行工作，也可以交叉工作。 #### 考点 1. 微观层面下，计算低位交叉编址的多体存储器连续读取 $n$ 个存储字的耗时。 $T + (n - 1)r$ ，其中 $T$ 为存取周期， $r$ 为存取时间。 2. 设每个存储体的存取周期为 $T$ ，**存取时间**为 $r$ ，为了使流水线不间断，应该保证模块数 (存储体数) $m \geq T / r$ 。 设每个存储体的存取周期为 $T$ ，**总线传输周期**为 $r$ ，为了使流水线不间断，应该保证模块数 (存储体数) $m \geq T / r$ 。(两种常见描述，表达的是同一个意思) ## 外存储器 计算机的外存储器又称为辅助存储器，目前主要使用磁表面存储器。 ### 磁表面存储器 把某些磁性材料薄薄地土菜金属铝或塑料表面上作为载磁体来存储信息。磁盘存储器，磁带存储器，磁鼓存储器均属于磁表面存储器。 **优点**： 1. 存储容量大，位价格低； 2. 记录介质可以重复使用； 3. 记录信息可以长期保存而不丢失，甚至可以脱机存档； 4. 非破坏性读出。 **缺点**： 1. 存取速度慢； 2. 机械结构复杂； 3. 对工作环境要求高。 > 外存储器既可以作为输入设备，也可以作为输出设备。(可读可写) ### 磁盘存储器 ![image-20240907020014050.png][22] #### 磁盘设备的组成 1. 存储区域 一块硬盘含有若干个**记录面**，每个记录面划分为若干条**磁道**，而每条磁道又划分为若干个**扇区 (又称块) **，扇区是**磁盘读写的最小单位**，也就是说磁盘**按块读取**。 ![image-20240907020936958.png][23] 2. 磁盘存储器 磁盘存储器由磁盘驱动器，磁盘控制器和盘片组成。 - 磁盘驱动器：核心部件是磁头和盘片，温切斯特盘是一种可移动头固定盘片的硬盘存储器。 - 磁盘控制器：是硬盘存储器和主机的接口，主流的标准有 IDE ，SCSI ，SATA 等。 #### 磁盘的性能指标 1. 磁盘的容量：一个磁盘所能存储的字节总数称为**磁盘容量**。磁盘容量由**非格式化容量**和**格式化容量**之分。 - 非格式化容量是指磁记录表面可以利用的磁化单元总数。 - 格式化容量指的是按照某种特定的记录格式所能存储信息的总量。 格式化后的容量一般会比较小，因为需要跳过坏道，以及留出一部分空间用作其他用途。 2. 记录密度：记录密度是指盘片单位面积上记录的二进制信息量，通常以**道密度**，**位密度**和**面密度**来表示。 - 道密度：沿磁盘半径方向单位长度上的磁道数； - 位密度：磁道单位长度上能记录的二进制代码位数； - 面密度：位密度和道密度的乘积。 > 磁盘所有磁道记录的信息量一定是相等的，并不是越外圈信息越多，因此每个磁道的位密度都不同。 3. **平均存取时间**：平均存取时间 = 寻道时间 (磁头移动到目标磁道) + 旋转延迟时间 (磁头定位到所在扇区) + 传输时间 (传输数据所花的时间) + 磁盘控制器时间 (某些题目会加上) 。 寻道时间一般会给一个平均时间；旋转延迟时间若没给，则可以取旋转半圈所需要的时间。 4. 数据传输率：磁盘存储器在单位时间内向主机传送数据的字节数。 假设磁盘转速为 $r$ 转 / 秒 ，每条磁道的容量为 $N$ 个字节，则数据传输率为 $D_r = rN$ 。 #### 磁盘地址 主机向磁盘控制器发送寻址信息，一般格式如下： | 驱动器号 | 柱面 (磁道) 号 | 盘面号 | 扇区号 | | -------------------- | ----------------- | ------------ | ------------------------------ | | 指明使用的是哪个磁盘 | 移动磁头臂 (寻道) | 激活某个磁头 | 通过旋转将特定扇区划过磁头下方 | **常见题型：** - 若系统中有 4 个驱动器，每个驱动器带一个磁盘，每个磁盘 256 个磁道，16 个盘面，每个盘面划分为 16 个扇区，则扇区地址最少需要多少位？ 每个扇区地址需要 18 位二进制代码： | 驱动器号 | 柱面 (磁道) 号 | 盘面号 | 扇区号 | | -------- | -------------- | ------ | ------ | | 2bit | 8bit | 4bit | 4bit | #### 硬盘的工作过程 硬盘的主要操作是**寻址，读盘，写盘**。每个操作都对应一个控制字，硬盘工作时，第一步是获取控制字，第二步是执行控制字。 硬盘属于机械式部件，器读写操作都是串行的。总线上的数据是并行传输的，这里就需要一个变换电路来实现。 ![image-20240907023703193.png][24] #### 磁盘阵列 RAID (Redundant Array of Independent Disks, 独立硬盘冗余阵列) 是将多个独立的物理磁盘组成一个独立的逻辑盘，数据在多个物理盘上分割交叉存储，并行访问。具有更好的存储性能，可靠性和安全性。 - RAID0：无冗余和校验的磁盘阵列。速度最快，容量最大，**没有容错能力**。 - RAID1：镜像磁盘阵列。逻辑上相邻的两个扇区在物理上存到两个磁盘中，类比之前的 "低位交叉编制的多体存储器" ；缺点是**容量减少一半**。 - RAID2：采用纠错的海明码 (Hamming Code) 的磁盘阵列。逻辑上连续的几个 bit 物理上分散存储在各个盘中，每组数据由 4bit 信息位 + 3bit 海明校验位，可以纠正一位错误。 - RAID3：位交叉奇偶校验的磁盘阵列。 - RAID4：块交叉奇偶校验的磁盘阵列。 - RAID5：无独立校验的奇偶校验磁盘阵列。 > 越往下磁盘可靠性越高。 RAID 通过同时使用多个磁盘，提高了传输率；通过在多个磁盘上并行存取来大幅提高存储系统的数据吞吐量；通过镜像功能，可以提高安全可靠性；通过数据校验，可以提供容错能力。 ### 固态硬盘 固态硬盘 (SSD) 基于闪存技术 Flash Memory ，属于电可擦除 ROM ，即 EEPROM 。 #### 结构 ![image-20240907130452651.png][25] - 内存翻译层：负责翻译逻辑块号，找到对应的页 (Page) 。 - 存储介质包含多个**闪存芯片** (Flash Chip) ，每个芯片包含多个**块** (block) ，每个块包含多个**页** (page) 。 #### 读写性能特性 - **以页为单位**进行读写，这里的 "页" 相当于磁盘的 "扇区" 。 - 以块为单位进行擦除操作。擦干净的块里面每个页都可以写一次，读无限次。 - 支持随机访问。系统给定一个逻辑地址，闪存翻译层可以通过电路迅速定位到对应的物理地址。 - 读取快写入慢。若要写的页中有数据，则不能写入。需要将块内其他页全部复制到一个新的块中，然后再写入新的页。 #### 对比机械硬盘 - SSD 读写速度快，随机访问性能高，用电路控制访问位置； 机械硬盘通过移动磁臂，旋转磁盘来控制访问为止，有寻道时间和旋转延迟。 - SSD 安静无噪音，耐摔抗震，能耗低，但造假更贵。 - $\star$ SSD 的一个块被擦除次数过多 (同一个块被重复写太多次) 可能会损坏； 机械硬盘的扇区不会因为读写次数过多而损坏。 #### 磨损均衡技术 思路：将擦除操作平均分布在各个块上，从而提升 SSD 的使用寿命。 - 动态磨损均衡：写入数据时，优先选择累计擦除次数少的闪存块进行写入。 - 静态磨损均衡：SSD 检测并自动进行数据分配，迁移，让老旧的闪存块承担以读为主的存储任务，较新的闪存块承担更多的写任务。 ## Cache 使用多模块存储器之类的技术可以提高主存的工作速度，但优化后的主存速度依旧比 CPU 处理速度慢很多。为了解决这个问题，结合程序的**局部性原理**，可以在存储系统中添加一个 Cache 层，用来缓和 CPU 和主存之间的速度矛盾。 ### 局部性原理 - 空间局部性：在最近的未来要用到的信息 (指令和数据) 很可能与现在正在使用的信息在存储空间上是邻近的。 比如访问数组元素，顺序执行的指令代码。 - 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息。 比如循环结构的指令代码。 基于局部性原理，不难想到可以把 CPU 目前访问的地址 "周围" 的部分数据放入 Cache 中，缓存命中的时候可以大大增加系统的运行速度。 > 如何界定这个 "周围" ？ 将主存的**存储空间分块**，如：每 1KB 分为一块。主存与 Cache 之间以 "块" 为单位进行数据交换。 ![image-20240907182613513.png][26] - 操作系统中通常将主存中的 "一个**块**" 也称为 "一个**页 / 页面 / 页框**" 。 - Cache 中的 "**块**" 也称为 "**行**" 。 ### 性能分析 设 $t_c$ 为访问一次 Cache 所需的时间，$t_m$ 为访问一次主存所需要的时间。 - 命中率 $H$ ：CPU 将要访问的信息已经在 Cache 中的比例； - 缺失 (未命中) 率： $M = 1 - H$ 。 - Cache - 主存 系统的平均访问时间： $t = Ht_c + (1 - H)(t_c + t_m)$ 。 先访问 Cache ，若没命中再访问主存。 - 或 $t = Ht_c + (1 - H)t_m$ 、 同时访问 Cache 和主存，若 Cache 命中则立即停止访问主存。 > 例题：假设 Cache 的速度是主存的 5 倍，且 Cache 的命中率为 95% ，则采用 Cache 后，存储器性能提高多少？ 设 Cache 的存取周期为 $t$ ， 则主存的存取周期为 $5t$ 。 - 若 Cache 和主存同时访问，命中时访问的时间为 $t$ ，未命中释放访问时间为 $5t$ 。则平均访问时间为 $0.95 \times t + 0.05 \times 5t = 1.2t$ ，故性能为原来的 $5t / 1.2t \approx 4.17$ 倍。 - 若先访问 Cache 再访问主存，则命中时访问的时间为 $t$ ，未命中释放访问时间为 $t + 5t$ 。则平均访问时间为 $T_a = 0.95 \times t + 0.05 \times 6t = 1.25t$ ，故性能为原来的 $5t / 1.25t = 4$ 倍。 ### Cache 和主存的映射关系 > 如何区分 Cache 与主存的数据块的对应关系？ 映射都是由硬件电路直接实现的，常见的有下面三种映射方式： - **全相联映射**：主存块可以放在 Cache 的任意位置。 - **直接映射方式**：每个主存块只能存放到一个特定的位置。 Cache 块号 = 主存块号 % Cache 总块数。 - **组相联映射**：Cache块分为若干组，每个主存块可以放到特定分组中的任意一个位置。 组号 = 主存块号 % 分组数。 > 每个块除了有一个标记之外，还有一个有效位，表示这个标记是否有效。 假设某个计算机的主存地址空间大小为 256MB ，按字节编址，其数据 Cache 有 8 个 Cache 行，行长为 64B 。 Cache 行即 Cache 块，与主存块的大小相同，因此块内地址应当有 $log_2 64 = 6$ 位；主存地址空间大小为 256MB ，因此主存的地址共 28 位，所以块号应该有 22 位。 #### 全相联映射 将需要缓存的块随便放在 Cache 中的一个空闲位置上即可： ![image-20240907235648693.png][27] **访存流程：** 1. 用需要访存地址的前 22 位对比 Cache 中所有块的标记； 2. 若标记匹配且有效位为 1 ，则 Cache 命中，访问 Cache 中的数据； 3. 若未命中或有效位为 0 ，则正常访问主存。 **优点：** Cache 存储空间利用充分，命中率高。 **缺点：** 查找标记最慢，有可能需要对比所有行的标记。 #### 直接映射 直接映射，主存块在 Cache 中的位置 = 主存块号 % Cache 总块数： ![image-20240908000111591.png][28] **优点：**对于任意一个地址，只需要对比一个标记，速度最快。 **缺点：**Cache 存储空间利用不充分，命中率低。每个块都在 Cache 中有自己固定的位置，当这个位置已经被写入时，即使 Cache 中还有空闲的块，也不能使用这些空闲的空间。 **标志优化**：若 Cache 总块数为 $2^n$ ，则主存块号末尾 $n$ 位可以直接反映它在 Cache 中的位置，因此将主存块号的其余位作为标记即可。 ![image-20240908001746966.png][29] **访存流程**： 1. 根据主存块号的**后三位**确定 Cache 行； 2. 若主存块号的前 19 位与 Cache 标记匹配且有效位为 1 ，则 Cache 命中； 3. 若未命中或有效位为 0 ，则正常访问主存。 #### 组相联映射 以 2 路组向量映射为例：2 路组相联即 2 块为一组，分四组。 ![image-20240908001855624.png][30] 所属分组 = 主存块号 % 分组数，因此相当于块号最后两位为组号。 ![image-20240908001711540.png][31] **优点：**另外两种方式的折中，综合效果最好。 **访存流程：** 1. 根据主存块号的后两位确定所属的分组号； 2. 若主存块号的前 20 为与分组内的某个标记匹配且有效位为 1 ，则 Cache 命中； 3. 若违命终或有效位为 0 ，则正常访问主存。 ### Cache 替换算法 > Cache 满了该如何解决？ - 全相联映射：Cache 完全满了才需要替换，需要在全局选择替换哪一块。 - 直接映射：如果对应位置非空，则直接替换。 - 组相联映射：分组内满了才需要替换，需要在分组内选择替换哪一块。 设总共有 4 个 Cache 块，初始整个 Cache 为空。采用全相联映射的方式，依次访问主存块 {1, 2, 3, 4, 1, 2, 5 , 1, 2, 3, 4, 5} ，有如下几种主流的方法： #### 随机算法 RAND 若 Cache 已满，则随机选择一块进行替换。 ![image-20240909194503398.png][32] - **优点：** 实现简单。 - **缺点：** 完全没考虑局部性原理，Cache 命中率低，实际效果很不稳定。 #### 先进先出算法 FIFO 若 Cache 已满，则替换最先被调入 Cache 的块。 ![image-20240909194806968.png][33] > 抖动现象：频繁的换入换出现象。(刚被替换的块很快又被调入) - **优点：** 实现简单，按顺序放入或替换 Cache 块。 - **缺点：** 依然没有考虑局部性原理，最先被调入 Cache 的块也可能时被频繁访问的。 #### 近期最少使用算法 LRU Least Recently Used ：为每一个 Cache 块设置一个**计数器**，用于记录每个 Cache 块已经多久没有被访问了。当需要替换的时候替换计数器最大的 Cache 块。 硬件操作流程如下： 1. 命中时，索命中的行的计数器清零，**值比其低的计数器加 1 ，其余不变。** 2. 未命中且还有空闲行时，心状如的行的计数器置为 0 ，其余非空闲行全加 1 。 3. 未命中且无空闲行时，计数器最大的行信息块被淘汰，新装的块的计数器置为 0 ，其余全加 1 。 > 为什么只让值更低的计数器加 1 ，因为这样的操作可以让计数器内的数不超过 Cache 块的总数，从而只需要 $\lceil log_2n \rceil$ (其中 $n$ 位Cache 块的总数) 位就可以记录所有的数。 > > 此外， Cache 装满后，所有计数器的值一定不重复。 - **优点：** 基于局部性原理，近期被访问过的主存块，在不久的将来也很有可能被再次访问，因此淘汰最久没被访问过的块是合理的。LRU 算法的实际运行效果优秀，Cache命中率高。 - **缺点：** 若被频繁访问的主存块数量大于 Cache 行数量，则可能发生**抖动**。 #### 最不经常使用算法 LFU Least Frequently Used， 为每个 Cache 块设置一个计数器，用于记录每个 Cache 块**被访问过几次**.当 Cache 满了之后替换计数器最小的块。 ![image-20240909201043289.png][34] - 曾经被经常访问的主存块在未来不一定会用得到，并没有很好的遵循局部性原理，因此实际运行效果不如 LRU 。 ### Cache 写策略 > CPU 修改了 Cache 中的数据副本，如何确保主存中数据母本的一致性？ #### 写回法 (write-back) 当 CPU 对 Cache **写命中**时，只修改 Cache 的内容，不立即写入主存，只有当此块被换出时才写回主存。 未被修改的块不必写回，因此需要增加一个**脏位**，用来记录 Cache 中的块是否被修改过。 ![image-20240909212123454.png][35] - 减少了访存次数，但存在数据不一致的隐患。 #### 全写法 write-through 又称**写直通法**。当 CPU 对 Cache **写命中**时，必须把数据同时写入 Cache 和主存，一般使用**写缓冲 (write buffer) ** 。 ![image-20240909212400134.png][36] - 使用写缓冲，CPU 写的速度很快，若写操作不频繁则效果很好。 - 若写操作很频繁，可能会因为写缓冲饱和而发生阻塞。 #### 写分配法 write-allocate 当 CPU 对 Cache **写不命中**时，把主存中的块调入 Cache ，在 Cache 中修改。通常**搭配写回法**使用。 ![image-20240909213124980.png][37] #### 非写分配法 not-write-allocate 当 CPU 对 Cache **写不命中**时，只写入主存，不调入 Cache 。通常**搭配全写法**使用。 ![image-20240909213233847.png][38] - 只有**读未命中**时才会将块调入 Cache 。 ### 多级 Cache 现代计算机通常采用多级 Cache ，离 CPU 越近的速度越快，容量越小；离 CPU 越远的速度越快，容量越大。 ![image-20240909213459959.png][39] [1]: https://blog.domineto.top/usr/uploads/2024/09/3926206113.png [2]: https://blog.domineto.top/usr/uploads/2024/09/2817053392.png [3]: https://blog.domineto.top/usr/uploads/2024/09/2884636561.png [4]: https://blog.domineto.top/usr/uploads/2024/09/3712050661.png [5]: https://blog.domineto.top/usr/uploads/2024/09/167395163.png [6]: https://blog.domineto.top/usr/uploads/2024/09/1717299362.png [7]: https://blog.domineto.top/usr/uploads/2024/09/918614580.png [8]: https://blog.domineto.top/usr/uploads/2024/09/1807330849.png [9]: https://blog.domineto.top/usr/uploads/2024/09/4273765630.png [10]: https://blog.domineto.top/usr/uploads/2024/09/1000700031.png [11]: https://blog.domineto.top/usr/uploads/2024/09/3661032860.png [12]: https://blog.domineto.top/usr/uploads/2024/09/2556596898.png [13]: https://blog.domineto.top/usr/uploads/2024/09/2130809519.png [14]: https://blog.domineto.top/usr/uploads/2024/09/3139555012.png [15]: https://blog.domineto.top/usr/uploads/2024/09/1831387157.png [16]: https://blog.domineto.top/usr/uploads/2024/09/3101616256.png [17]: https://blog.domineto.top/usr/uploads/2024/09/760413688.png [18]: https://blog.domineto.top/usr/uploads/2024/09/3115844578.png [19]: https://blog.domineto.top/usr/uploads/2024/09/921388313.png [20]: https://blog.domineto.top/usr/uploads/2024/09/4168940807.png [21]: https://blog.domineto.top/usr/uploads/2024/09/2073547369.png [22]: https://blog.domineto.top/usr/uploads/2024/09/1006102880.png [23]: https://blog.domineto.top/usr/uploads/2024/09/1898818650.png [24]: https://blog.domineto.top/usr/uploads/2024/09/912444607.png [25]: https://blog.domineto.top/usr/uploads/2024/09/2447213921.png [26]: https://blog.domineto.top/usr/uploads/2024/09/405506237.png [27]: https://blog.domineto.top/usr/uploads/2024/09/3146940194.png [28]: https://blog.domineto.top/usr/uploads/2024/09/1518227443.png [29]: https://blog.domineto.top/usr/uploads/2024/09/2422121379.png [30]: https://blog.domineto.top/usr/uploads/2024/09/3279920247.png [31]: https://blog.domineto.top/usr/uploads/2024/09/2327297265.png [32]: https://blog.domineto.top/usr/uploads/2024/09/827555990.png [33]: https://blog.domineto.top/usr/uploads/2024/09/100635975.png [34]: https://blog.domineto.top/usr/uploads/2024/09/2016171658.png [35]: https://blog.domineto.top/usr/uploads/2024/09/3739493660.png [36]: https://blog.domineto.top/usr/uploads/2024/09/4222667959.png [37]: https://blog.domineto.top/usr/uploads/2024/09/4082156651.png [38]: https://blog.domineto.top/usr/uploads/2024/09/1984760062.png [39]: https://blog.domineto.top/usr/uploads/2024/09/2916939406.png 最后修改：2024 年 11 月 21 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏