组成原理-存储系统
基本术语
- 存储器：存放程序和数据的器件。
- 存储位：存放一个二进制数位的存储单元，是存储器最小的存储单位。
- 存储字：计算机可寻址（作为一个整体存入或取出）的最小信息单位。
- 存储单元：存放一个存储字的若干个记忆单元组成一个存储单元。
- 存储体：大量存储单元的集合组成存储体。
- 存储单元地址：存储单元的编号。
- 字编址：对存储单元按字编址。
- 字节编址：对存储单元按字节编址。
- 寻址：通过地址寻找数据，从对应地址的存储单元中访存数据。
存储系统分类
按存储介质分类
半导体存储器：用半导体器件组成的存储器。
磁表面存储器：用磁性材料做成的存储器。（磁盘、磁带）
激光存储器：信息以刻痕的形式保存在盘面上，用激光束照射盘面，靠盘面的不同反射率来读出信息。
按存取方式分类
RAM
随机存储器（RAM，Random Access Memory）：可随机访问任意存储单元，且存取时间与存储单元的物理位置无关。主要充当高速缓冲存储器和主存储器。
半导体随机存储器
动态随机存储器（DRAM）
只能将数据保持很短的时间。为了保持数据，DRAM 使用电容存储，所以必须隔一段时间刷新（Refresh）一次，如果存储单元没有被刷新，存储的信息就会丢失，关机就会丢失数据。常用于主存储器。DRAM 采用地址复用技术，地址线是原来的 1/2，且地址信号分行、列两次传送。相对于 SRAM 来说，DRAM 具有容易集成、价位低、容量大和功耗低等优点，但 DRAM 的存取速度比 SRAM 慢，一般用来组成大容量主存系统。
DRAM 保存的信息会自动消失（易失性存储器），为此，每隔一段时间必须刷新，通常取 2ms，这个时间称为刷新周期。常用的刷新方式有 3 种：集中刷新、分散刷新和异步刷新。
（1）集中刷新：指在一个刷新周期内，利用一段固定的时间，依次对存储器的所有行进行逐一再生，在此期间停止对存储器的读写操作，称为“死时间”，又称访存“死区”。集中刷新的优点是读写操作时不受刷新工作的影响，因此系统的存取速度较高；缺点是在集中刷新期间（死区）不能访问存储器。
补充一点：为什么刷新与存取不能并行？
因为内存就一套地址译码和片选装置，刷新与存取有相似的过程，它要选中一行——这期间片选线、地址线、地址译码器全被占用着。同理，刷新操作之间也不能并行——意味着一次只能刷一行。
（2）分散刷新：把对每行的刷新分散到各个工作周期中。这样，一个存储器的系统工作周期分为两部分：前半部分用于正常读、写或保持；后半部分用于刷新某一行。这种刷新方式增加了系统的存取周期，如存储芯片的存取周期为 0.5μs，则系统的存取周期为 1μs。分散刷新的优点是没有死区；缺点是加长了系统的存取周期，降低了整机的速度。
即在每个存取操作后绑定一个刷新操作。延长了存取周期，这样存取周期就成了0.5μs + 0.5μs =1μs。但是由于与存取操作绑定，就不需要专门给出一段时间来刷新了。这样，每有128个读取操作，就会把0-127行全部刷新一遍。故每隔128μs 就可将存储芯片全部刷新一遍，即刷新周期是1μs×128=128μs远短于2ms，而且不存在停止读/写的死时间，但是存取周期长了，整个系统速度降低了。（分散刷新的刷新周期128μs ，其实不需要这么频繁，会导致浪费）
（3）异步刷新：异步刷新是前两种方法的结合，它既可以缩短“死时间”，又能充分利用最大刷新间隔为 2ms 的特点。具体做法是将刷新周期除以行数，得到两次刷新操作的时间间隔 t，利用逻辑电路每隔时间 t 产生一次刷新请求。这样可以避免使 CPU 连续等待过长的时间，而且减少了刷新次数，从根本上提高了整机速度。
具体操作为：在2ms内对128行各刷新一遍
即每隔15.6μs刷新一行(2000μs/128≈15.6μs)，而每行刷新的时间仍为0.5μs。这样，刷新一行只能停止一个存取周期，但对每行来说，刷新间隔时间仍为2ms，而死时间为0.5μs。（相对每一段来说，是集中式刷新，相对整体来说，是分散式刷新）
如果将DRAM的刷新安排在CPU对指令的译码阶段，由于这个阶段CPU不访问存储器，所以这种方案既克服了分散刷新需独占0.5μs用于刷新，使存取周期加长且降低系统速度的缺点，又不会出现集中刷新的访存“死区”问题，从根本上上提高了整机的工作效率。
DRAM 的刷新需注意以下问题：（1）刷新对 CPU 是透明的，即刷新不依赖外部的访问；（2）动态 RAM 的刷新单位是行，故刷新操作时仅需要行地址；（3）刷新操作类似于读操作，但又有所不同。刷新操作仅给栅极电容补充电荷，不需要信息输出。另外，刷新时不需要选片，即整个存储器中的所有芯片同时被刷新。
SRAM 和 DRAM 都满足断电内容消失，但需要刷新的只有 DRAM，而 SRAM 不需要刷新。
静态随机存储器（SRAM）
所谓的 “静态”，指这种存储器只要保持通电，里面储存的数据就可以恒常保持。相对之下，DRAM 里面储存的数据需要周期性地 Refresh。然而，当电力供应停止（关机）时，储存的数据还是会消失，所以也称为 Volatile Memory（易失性存储器），这与在断电后仍能储存数据的 ROM 或闪存不同的。但是 SRAM 也有它的缺点，即它的集成度较低，功耗较 DRAM 大，相同容量的 DRAM 内存可以设计为较小的体积，但是 SRAM 却需要很大的体积。同样面积的硅片可以做出更大容量的 DRAM，因此 SRAM 显得更贵。常用于高速缓存。
| 特点 \ 类型 | SRAM | DRAM |
|---|---|---|
| 存储信息 | 触发器 | 电容 |
| 破坏性读出 | 非 | 是 |
| 需要刷新 | 不要 | 需要 |
| 送行列地址 | 同时送 | 分两次送 |
| 运行速度 | 快 | 慢 |
| 集成度 | 低 | 高 |
| 发热量（功耗） | 大 | 小 |
| 存储成本 | 高 | 低 |
| 主要用途 | 高速缓存 | 主机内存 |
静态存储器结构
译码部分：
找到静态存储器中对应的存储单元。
总体：
串行访问存储器（SAS）
对存储单元进行 读/写 操作时，需按其物理地址的先后顺序寻址，包括顺序存取存储器（如磁带，SAM）与直接存取存储器（如磁盘,DAM）。
顺序存取存储器（SAM）
是完全的串行访问，顺序存取存储器的内容只能按照某种顺序存取，存取时间的长短与信息在存储体上的物理位置有关，其特点是存取速度缓慢。如：磁带，读写时要待磁带移动到合适位置之后才能顺序读写。由于价格便宜，主要用于数据备份容灾系统。
直接存取存储器（DAM）
是部分的串行访问，如：HHD 机械硬盘，对信息的存取有两步操作。首先，磁头直接移动到目标区域（磁道），然后再从磁道的合适位置开始读写，它介于顺序存取和随机存取之间。主要用于辅助存储器。
只读存储器（ROM）
存储器的内容只能随机读出而不能写入。信息一旦写入存储器就固定不变，即使断电，内容也不会丢失。因此，通常用它存放固定不变的程序、常数和汉字字库，甚至用于操作系统的固化。它与随机存储器可共同作为主存的一部分，统一构成主存的地址域。
由 ROM 派生出的存储器也包含可反复重写的类型，ROM 与 RAM 的存取方式均为随机存取。广义上的只读存储器已可已可通过电擦除等方式进行写入，其“只读”的概念没有保留，但仍然保留了断电内容保留、随机读取特性，但其写入速度比读取速度慢得多。
掩膜式只读存储器（MROM）
MROM 写入后任何人无法改变其内容
一次可编程只读存储器（PROM）
PROM 允许用户利用专门的设备（编程器）写入自己的程序，一旦写入，内容就无法改变。
可擦除可编程只读存储器（EPROM）
EPROM不仅可以由用户利用编程器写入信息，而且可以对其内容进行多次改写。需要修改 EPROM 内容时，先将其全部内容擦除，然后编程。
闪速存储器（Flash Memory）
固态硬盘（Solid State Drives
按信息的可保存性分类
非永久记忆（易失性）的存储器：掉电后数据消失的存储器，如：半导体读/写存储器 RAM。
永久性记忆（非易失性）的存储器：掉电后仍能保存信息的存储器，如：磁性材料做成的存储器以及半导体 ROM。
若某个存储单元所存储的信息被读出时，原存储信息被破坏，则称为破坏性读出；若读出时，被读单元存储信息不被破坏，则称为非破坏性读出，具有破坏性读出的存储器，每次读出操作后，必须紧接一个再生的操作，以便恢复被破坏的信息。
三层存储结构
几个问题：
1、cpu速度慢：cpu访问的是主存，但是主存的速度慢于cpu的读取速度。导致cpu的速度慢。
2、主存容量不足
解决方法：
1、cache：解决cpu速度慢的问题（一般是集成在cpu上）
2、辅存解决主存容量小的问题
存储系统层次结构主要体现在 “Cache - 主存” 层次和 “主存 - 辅存” 层次。前者主要解决 CPU 和主存速度不匹配的问题，后者主要解决存储系统容量的问题
主存和 Cache 之间的数据调动是由硬件自动完成的，对所有程序员均是透明的；而主存和辅存之间的数据调动则是由硬件和操作系统共同完成的，对应用程序员是透明的。
主存储器：主存（又称内存）
用来存放计算机运行期间所需的大量程序和数据，CPU 可以直接随机地对其进行访问，也可以和告诉缓冲存储器（Cache）及辅助存储器交换数据，其特点是容量较小、存取速度较快、单位价格较高。
- 半导体存储器、DRAM、非永久记忆存储器
- 特性：“可随机访问任意存储单元” 和 “掉电即失去数据”，这些特性均服务于冯诺依曼体系 “存储程序” 的核心理想。
辅助存储器：辅存
又称外存储器（外存），是主存储器的后援存储器，用来存放当前暂时不用的程序和数据，以及一些需要永久性保存的信息，它不能与 CPU 直接交换信息。其特点是容量极大、存取速度较慢、单位成本低。
高速缓冲存储器：cache
位于主存和 CPU 之间，用来存放正在执行的程序段和数据，以便 CPU 能高速地使用它们。Cache 地存取速度可与 CPU 的速度匹配，但存储容量小、价格高。目前的高档计算机通常将它们制作在 CPU 中。
存储器的性能指标
存储器有 3 个主要性能指标，即存储容量、单位成本和存储速度。这 3 个指标相互制约，设计存储器系统所追求的目标就是大容量、低成本和高速度。
具体可见《王道》
主存中的数据组织
主存：随机访问存储器，包含读/写存储空间和只读存储空间
存储字长：主存的一个存储单元所包含的二进制位数。按照字节为单位。
数据存储与边界的关系
按边界对齐，方便访问和读取。但是会浪费空间。
大端和小端存储方式
大端：最高字节地址作为数据地址
小端：最低字节地址作为数据地址
大端模式更符合人的读写习惯，但是小端模式更符合计算机的处理。
CPU和主存储器连接
连接由总线来支持：包括数据总线、地址总线和控制总线。
CPU 通过 AR（地址寄存器）& AB（地址总线）、DR（数码寄存器）& DB（数据总线）和主存进行数据传输。
若 AR 为 K 位字长，表示 CPU 的寻址宽度，即允许主存包含有 2K 个可寻址存储单位；
若 DR 为 n 位字长，则表示在一个存储周期内，CPU 和主存之间通过总线进行 n 位数据传输。
控制总线包括控制数据传输的读（READ）、写（WRITE）和表示存储器功能完成的（READY）的三种控制线。
cpu向内存写数据的时，相当于将数据写入内存地址中。数据的地址经过地址总线送给译码器，译码器的有效输出送给锁存单元的使能端，而cpu中寄存器数据通过数据总线送给锁存单元的输入端，实现数据存入内存。
cpu读内存数据时，相当于将内存地址中的数据读入cpu。数据的地址经过地址总线送给译码器，译码器的有效输出送给锁存单元的使能端，此时锁存单元将输出端数据送入数据总线，再通过数据总线送入cpu。
cpu与内存通过数据总线交换数据，数据总线是双向的。
CPU读取主存数据
当 CPU 从存储器读取一个存储字时，CPU 必须指定该存储字的地址，将该地址送到 AR 再经 AB 送到存储器，同时，CPU 通过控制线发送 READ 信号到存储器。此后，CPU 等到存储器通过控制线发来一个 READY 信号，表示已经完成了数据的读，并将数据经 DB 放到 DR 上了，CPU 再从 DR 取出相应的数据。以此来完成了一个存储器字的读与取。
CPU存放数据到主存
CPU 为了存放一个字到存储器，首先将存储字在存储器中的存放地址通过 AR 经 AB 发送到存储器，并将存储字放到 DR，同时发出一个 WRITE 信号到存储器。此后，CPU 等到接收 READY 信号。存储器会根据 AB 收到的地址来存放 DB 接收到的存储字，然后通过 READY 控制线发送 READY 信号给 CPU 接收。以此完成了一个存储字的存放。
可见，主存和 CPU 之间采用的是异步工作方式，以 READY 信号表示以此访存操作的结束。
存储扩展
CPU 的数据线数与存储芯片数据位数不一定相等，通常进行位扩展，用多个存储芯片对字长进行扩充，使数据位数与 CPU 的数据线数相等。可用的技术方法有位扩展法、子扩展法和字位同时扩展法。
分为字扩展和位扩展以及字位扩展。
位扩展
地址线不变，但是数据线分成了四个部分。因为位表示的是字的深度，字的地址还是和没扩展前一样的。
仅采用位扩展时，各个芯片连接地址线的方式一样，而连接数据线的方式不一样，某一时刻选中所有芯片，所以片选信号线要连接到所有芯片。
字扩展
由于位数没有发生变化，所以数据线是没有发生变化的。但是由于字的数量（厚度）增加了，所以地址线要增加。
片选信号是选择字扩展中的字的厚度中的那一层。
字扩展将存储芯片的地址线、数据线、读写控制线相应并联，而由片选信号来区分芯片的地址范围
仅采用字扩展时，各个芯片连接地址线方式相同，连接数据线的方式也相同，但在某一时刻只需选中部分芯片，所以通过片选信号或采用译码器设计连接到相应的芯片。
字位扩展
字位同时扩展就是既增加存储字的数量，又增加存储字长。
采用字位同时扩展时，各个芯片连接地址线的方式相同，但连接数据线的方式不同，而且需要通过片选信号或采用译码器设计连接到相应的芯片。
双端口 RAM 和多模块存储器
双端口 RAM 是指同一个存储器有左、右两个独立的端口，分别具有两组相互独立的地址线、数据线和控制线，允许两个独立的控制器同时异步地访问存储单元。当两个端口的地址不相同时，在两个端口上进行读写操作一定不会发生冲突。
两个端口同时存取存储器地同一地址单元时，会因数据冲突造成数据存储或读取错误。两个端口对同一主存操作有以下4 种情况：
- 两个端口不同时对同一地址单元存取数据。
- 两个端口同时对同一地址单元读出数据。
- 两个端口同时对同一地址单元写入数据。
- 两个端口同时对同一地址单元操作，一个写入数据，另一个读出数据。
其中，第 1 种和第 2 种情况不会出现错误；第 3 种情况会出现写入错误；第 4 种情况会出现读出错误。
多体交叉存储器
由多个存储模块构成。基本思想是：在不提高存储器效率、不扩展数据通路位数的前提下，通过存储芯片的交叉组织，提高CPU单位时间内访问的数据量，从而缓解快速的CPU与慢速的主存之间的速度差异。
分为高位和低位两种多体交叉存储器。
高位多体交叉存储器
可以看到的是，用高位段地址经过译码后产生片选信号，选择存储体。低位段地址直接选择一个存储体内的不同存储单元。
特点
- 相邻的地址在同一个存储体中
- 不同存储体的地址不相邻
问题
因为连续的地址在同一个存储体中，无法实现存储体并行工作
低位多体交叉存储器
用低位段地址经过译码后产生片选信号，选择存储体。高位段地址直接选择一个存储体内的不同存储单元。
存储流水线访问
其中：存储周期T=0至W0 时间，表示的是存储体存入数据的时间。
连续并行读取时间是：0至W0 +W0至W1 （此时第一个存储体的数据读出） +W1至W2 （此时第二个存储体的数据读出） +W2至W3
Cache的基本原理
cache，中译名高速缓冲存储器，其作用是为了更好的利用局部性原理，减少CPU访问主存的次数。简单地说，CPU正在访问的指令和数据，其可能会被以后多次访问到，或者是该指令和数据附近的内存区域，也可能会被多次访问。因此，第一次访问这一块区域时，将其复制到cache中，以后访问该区域的指令或者数据时，就不用再从主存中取出。
程序访问的局部性原理包括时间局部性和空间局部性。
- 空间局部性：在最近的未来要用到的信息（指令和数据），很可能与现在正在使用的信息在存储空间上是邻近的
- 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息
主要分析的是CPU和主存之间的Cache
cache的工作过程
Cache和主存都被分成若干大小相等的块（Cache块又称为Cache行），每块由若干字节组成，块的长度称为块长（Cache行长）。所以Cache中的块数要远少于主存中的块数，它仅保存主存中最活跃的若干块的副本。
CPU与Cache之间的数据交换以字为单位，而Cache与主存之间的数据交换则以Cahce块为单位。
当CPU发出读请求时，若访存地址在Cache中命中，就将此地址转换成Cache地址，直接对Cahce进行读操作，与主存无关；若访存地址在Cache中未命中，则需访问主存，并把此字所在的块一次性地从主存调入Cache，若此时Cache已满，则需根据某种 替换算法，用这个块替换Cache中原来的某块信息。
Q：如何判断数据在Cache中？
A：使用相联存储器（注意，这里是在相联存储器中进行分析的，没有进入到cache块中）
Q：Cache中的数据是有效的吗？
A：使用cache块中的vaild
当CPU发出写请求时，若Cache命中，有可能会遇到Cache与主存中的内容不一致的问题，此时需要根据某种 写策略 解决这个问题。
在写穿式Cache中，数据更新时，在写入缓存之后，立即也将数据写入内存，如果此时请求指定的地址没有对应的缓存，那么直接写入内存。所以每次操作总会执行：
第一步，CPU将数据写入Cache；
第二步，将Cache数据传送到Memory中相应的位置；在写回式Cache中，数据更新时，在写入缓存之后，不会立即更新对应的内存，只有当该缓存被用于其他的内存数据（即数据被替换出缓存）时，被修改的缓存中的数据才会被覆盖式地写入到对应的内存中。
并不是每次执行步骤1后都执行步骤2操作。
Q：写回前，主存的数据是新的吗？（因为没有及时的写回主存中）
A：使用cache块中的dirty
cache的地址划分
因为cache是以块划分的，所以对主存地址，需要进行二次划分。
为了解决上述的三个问题，cache的结构需要进行相应的改变。
CPU将地址置入相联存储器中，如果数据在cache中，去cache中对应的地址查找，如果不再就直接对主存进行访问。
相联存储器
作用：判断CPU要访问的内容是否在Cache中，在的话，会给出相应内容在cache中的地址。
存放查找表 (独立硬件，不在缓存中)
存储容量 = 查找表容量 = cache块数 * 表项大小
cache中用于存放块表，虚拟存储器中存放段表、页表
（valid, Key， Value ）
( 有效位, 主存块地址 ， Cache块地址） 注：value不一定是必要的
CPU给出的块地址与查找表中某单元相同且有效位为1表示命中
步骤(对应的是系统的读过程)
CPU给出主存地址（块地址，块内地址）
主存块地址为关键字查找相联存储器中的查找表
如相符表示副本在cache中，命中，访问cache
否则数据缺失，访问主存
将数据所在块副本调入cache（块交换—局部性）
载入副本过程可能引起替换
更新查找表，记录当前数据块地址
cache缺失时系统等待数据调入
基本结构如下
检索寄存器从地址中剥离Key
当明确查找的在Cache中时，符合寄存器会记录要查找的地址的位置
此处的存储体就是cache中的标记存储体
由下图可以看到：key包含了tag和offset。
cache地址映射和变换方法
这里的地址映射是指：主存空间映射到cache的地址空间。
在使用相联存储器得知数据在cache中后，接下来需要得知主存数据如何放置到cache行中。此外，cache满后应该如何处理？如何实现保持cache和主存的一致性？
全相联映射
只有一个组，就是全相联。不用hash来确定组，直接挨个比对高位地址，来确定是否命中。可以想见这种方式不适合大的缓存。想想看，如果4M 的大缓存 linesize为32Byte，采用全相联的话，就意味着410241024/32 = 128K 个line挨个比较，来确定是否命中，这是多要命的事情。高速缓存立马成了低速缓存了。
映射算法：主存的数据块可映射到cache任意行同时将该数据块地址对应的标记存储体中保存。
主存地址=块地址（标记）+块内地址（字）
因为只有一组，cache中的所有行标记会全部送入相联存储器中进行比较。如果命中的话，从cache中剥离出具体要访问的那个字。反之，会根据cpu给出的原始地址再次访问主存。
直接映射
每个组只有一个line，选中组之后不需要和组中的每个line比对，因为只有一个line。这样导致了cache的利用率低，块内冲突率高，但是淘汰算法（后来的赶走之前的）简单，适合大容量cache。
映射算法：cache共n行，主存第j快映射到cache行号为i=jmod (n)即映射到特定行
主存调入cache中的位置由行地址决定。
先看索引，取出对应的标识放入相联存储器中比较。命中与否的结果与上述相同。可以很明显的看出比较的内容变少了。
组相联映射
cache分成多个组，每个组分成多个行。所谓8路组相连（ 8-way set associative）的含义是指，每个组里面有8个行。
cache分组（每组包含的行数相同），主存以cache分组标准将块分组（两者数量相同）
映射算法：cache共n组，主存第j块号映射到cache的组号是i=jmod（n）。即主存的数据块映射到cache特定组的任意行
我们知道，cache的容量要远远小于主存，主存和cache肯定不是一一对应的，那么主存中的地址和cache的映射关系是怎样的呢？
拿到一个地址，首先是映射到一个组里面去。如何映射？取内存地址的中间几位来映射。
举例来说，data cache: 32-KB, 8-way set associative, 64-byte line size
Cache总大小为32KB，8路组相连（每组有8个line），每个line的大小linesize为64Byte,OK，我们可以很轻易的算出一共有32K/8/64=64 个组。
对于32位的内存地址，每个line有2^6 = 64Byte，所以地址的【0，5】区分line中的那个字节。一共有64个组。我们取内存地址中间6为来hash查找地址属于那个组。即内存地址的【6，11】位来确定属于64组的哪一个组。组确定了之后，【12，31】的内存地址与组中8个line挨个比对，如果【12，31】为与某个line一致，并且这个line为有效，那么缓存命中。
先看索引，取出索引组的全部行对应的标识放入相联存储器中比较。命中与否的结果与上述相同。
替换算法
cache存储空间被占满后需要替换数据块。
直接映射是不需要替换算法的。全相联映射替换算法适用于全部行。组相联映射替换算法适用组内全部行
① 先进先出算法(FIFO)
基本思想：按照数据块进入Cache的先后决定替换的顺序，即在需要进行替换时，选择最先
被调入Cache中的块作为替换块。这种方法要求为每块记录它们进入Cache的先
后次序。
优点：FIFO算法系统开销较小。
缺点：是不考虑程序访问的局部性，可能会把一些需要经常使用的块（如循环程序块）也作
为最早进入Cache的块而替换掉，因此，可能导致Cache的命中率不高。
② 近期最少使用(LRU)算法
基本思想：将近期内长久未被访问过的行换出。为此，每行设置一个计数器，cache每命中一次，命中行计数器清零，其它各行计数器增1，因此它是未访问次数计数器。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。
优点：这种算法显然保护了刚调入Cache的新数据，符合cache工作原理，因而使cache有较高
的命中率。LRU算法硬件实现简单
③ 最不经常使用(LFU)算法
基本思想：将一段时间内被访次数最少的那行数据换出。为此，每行设置一个计数器，新新
调入行的数据从0开始计数，每访问一次被访行的计数器增1。当需要替换时，对
这些特定行的计数值进行比较，将计数值最小的行换出。
缺点：一段期间访问情况不能严格反映近期访问情况。例如特定行中的A、B两行，A行在期间的前期多次被访问而后期未被访问，但累积计数值很大，B行是前期不常用而后期却正被频繁访问，但可能由于累积计数小于A行而被LFU算法换出了。
④ 随机替换算法
基本思想：需要进行替换时，从特定的行位置中随机地选取一行进行替换。
优点：硬件实现最容易，而且速度也比前几种策略快。
缺点：随意换出的数据很可能马上又要用，从而降低命中率和cache工作效率。但这个负面效应随着cache容量增大会减少，模拟研究表明随机替换策略的功效只是稍逊于LFU和LRU。
随机替换法
替换算法的抖动
调出去的那块就是即将访问的那块数据。
要避免抖动，需要在程序行为上避免。
虚拟存储器
解决了程序大小大于内存的限制问题
虚拟存储器处于“主存-辅存”存储层次。
- 辅存—–逻辑地址
- 主存—–物理地址
页式虚拟存储器
采用页表判断cpu访问的内容是否在主存，如果在辅存，则调用其内容到主存中。
转换：
MMU用于指出页表在内存中的位置，通过与VPN结合就能访问到页表中与虚拟页号VPN相对应的物理页号PPN。实现虚拟地址到物理地址的转换。
页表常驻在内存中。保存有虚拟页号和物理页号的对应关系。
进程开始要访问一个地址，它可能会经历下面的过程
1、每次我要访问地址空间上的某一个地址，都需要把地址翻译为实际物理内存地址
2、所有进程共享这整一块物理内存，每个进程只把自己目前需要的虚拟地址空间映射到物理内存上
3、进程需要知道哪些地址空间上的数据在物理内存上，哪些不在（可能这部分存储在磁盘上），还有在物理内存上的哪里，这就需要通过页表来记录
4、页表的每一个表项分两部分，第一部分记录此页是否在物理内存上，第二部分记录物理内存页的地址（如果在的话）
5、当进程访问某个虚拟地址的时候，就会先去看页表，如果发现对应的数据不在物理内存上，就会发生缺页异常
6、缺页异常的处理过程，操作系统立即阻塞该进程，并将硬盘里对应的页换入内存，然后使该进程就绪，如果内存已经满了，没有空地方了，那就找一个页覆盖，至于具体覆盖的哪个页，就需要看操作系统的页面置换算法是怎么设计的了。当每个进程创建的时候，内核会为进程分配4G的虚拟内存，当进程还没有开始运行时，这只是一个内存布局。实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data段）拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射）。这个时候数据和代码还是在磁盘上的。当运行到对应的程序时，进程（拿着虚拟地址）去寻找页表，发现页表中地址没有存放在物理内存上，而是在磁盘上，于是发生缺页异常，于是将磁盘上的数据拷贝到物理内存中。
另外在进程运行过程中，要通过malloc来动态分配内存时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。
可以认为虚拟空间都被映射到了磁盘空间中（事实上也是按需要映射到磁盘空间上，通过mmap，mmap是用来建立虚拟空间和磁盘空间的映射关系的）
TLB
虚实地址转换过程中存在的问题：
两次访问主存：第一次拿页表项判断是否在主存中，第二次得到数据。
5，6步骤是为了替换主存中的对应物理地址的内容。
为了减少访问主存的次数。设置TLB，不去主存拿页表。故TLB能节省一次CPU访问主存的次数。
于是TLB设计成页表映像的一部分。
1、CPU拿着虚拟地址访问MMU（为了将虚拟地址中剥离出的虚页号与MMU中的页表基址寄存器结合得到物理内存地址）
2、MMU拿着虚页号VPN访问TLB
首先，先去TLB中根据标志Tag寻找，假如找到了并且有效位是1，说明TLB命中了，那么直接就可以从TLB中获取该虚拟页号对应的物理页号。假如有效位是0，说明该页不在内存中，这时候就发生缺页异常，CPU需要先去外存中将该页调入内存并将页表和TLB更新。
假如在TLB中没有找到，那么就去页表（Page Table）中寻找（以虚拟页号为索引），假如找到了并且有效位是1，那么就可以取出对应的物理页号。假如有效位是0，说明该页不在内存中，这时候就发生缺页异常，CPU需要先去外存中将该页调入内存并将页表和TLB更新。
假如在页表中没有找到，也是缺页。同意会执行上述的缺页处理。
（不管从哪获取到物理页号，都可以根据规则组拼成实际物理地址，然后就可以访存去数据啦）
此处TLB tag是因为TLB只是页表的一个子集，不能全部遍历页表中的每一项。所以要增加tag判断与虚页对应的物理页是否存在。（具体见上面的引用部分）
段式虚拟存储器
以段为单位。一般将主存空间按照实际运行程序中的段来划分。由此 段可大可小。
段的独立性—易于编译、管理、修改和维护，也便于多道程序共享
各段的长度不同，给主存的分配带来麻烦
段式管理容易产生碎块，浪费主存空间
段页式虚拟存储器
程序按模块分段
段再分成长度固定的页。
程序调入调出按页面来进行
程序共享保护按段进行
兼备段式，页式管理的优点
在地址映像中需要多次查表
RAID
核心技术：将数据条带化后的存放在不同磁盘上，通过多磁盘的并行操作提高磁盘系统的读写速率。使用基于异或运算为基础的校验技术恢复损坏的数据
最左边的盘就是冗余盘。是用于备份的。
RAID0
数据以条带方式均匀分散在各磁盘上。
没有冗余，没有校验技术，任一磁盘坏了就GG。
RAID1
数据采用镜像的冗余方式，同一个数据有多份拷贝
RAID3/4
专用校验盘。
RAID5
RAID10
RAID01
一些习题
-万继光 - 百度文库 - wenku.baidu.com.png)
-万继光 - 百度文库 - wenku.baidu.com-1595315230835.png)-万继光 - 百度文库 - wenku.baidu.com.png)