933 KiB
存储系统
存储器被划分为若干个存储单元，每个存储单元都从$0$开始顺序编号。比如一个存储器有$128$个存储单元，则它的编号范围是$0\sim127$。
存储器概念
存储器的分类
作用
- 主存储器：主存或内存。
- 存放计算机运行间的程序和数据。
- $CPU$、$Cache$，能直接访问。
- 容量小、速度快、价格高。
- 辅助存储器：辅存或外存。
- 存放暂时不用的或永久的数据。
- 不能与$CPU$直接交换信息。
- 容量大、速度慢、成本低。
- 高速缓冲存储器$Cache$。
- 存放正在执行的程序和数据。
- 在$CPU$中。
- 容量小、速度快、价格高。
存储介质
- 磁表面存储器：
- 磁盘。
- 磁带。
- 磁芯存储器。
- $MOS$型存储器。
- 双极型存储器。
- 光存储器：光盘。
- 半导体存储器。
存取方式
- 随机存取：
- $RAM$：随机存取存储器：
- $DRAM$：动态。
- $SRAM$：静态。
- $ROM$：只读存储器。
- $RAM$：随机存取存储器：
- 串行访问：
- 直接存取：磁盘。
- 顺序存取：磁带。
信息可保存性
- 断电后信息是否消失：
- 易失性：$RAM$。
- 非易失性：磁带、$ROM$。
- 破坏性，存取是否影响存储内存：
- 破坏性读出：$DRAM$。
- 非破坏性读出。
存储器性能指标
- 存储容量：存储字数×字长（如$1M\times8$位）。
- 单位成本：每位价格=总成本÷总容量。
- 存储速度：数据传输率=数据的宽度÷存储周期：
- 存储周期=存取时间+恢复时间。
- 存取时间（$T_a$）：存取时间是指从启动一次存储器操作到完成该操作所经历平均的时间，分为读出时间和写入时间。
- 存取周期（$T_m$）：存取周期又称为读写周期或访问周期。它是指存储器进行一次完整的读写操作所需的金部时间，即连续两次独立地访问存储器操作（读或写操作）之间所需的最小时间间隔。
- 主存带宽（$B_m$）：主存带宽又称数据传输率，表示每秒从主存进出信息的最大数量，单位为字/秒、字节/秒（$B/s$）或位/秒（$b/s$）。
存储器层次化结构
- $CPU$。
- $Cache$：为了解决$CPU$的高速与主存之间的低速速度不匹配的问题，由硬件自动完成。
- 主存。
- 辅存：为了解决主存容量不足的问题，由硬件和操作系统共同完成。
- 虚拟存储系统。
存储部件概念
存储主体
- 存储元：由电路控制的单个存储部件。
- 存储单元：由同一个电路控制的一组同时读写的存储部件集合，一般为一行存储元，一行存储元的个数就代表一次存储的字长。
- 存储体：由多个存储单元构成的，多个电路控制的存储集合。
- 存储字：存储单元通电后由电信号表示可以读写的一个存储单元信息集合。存储字的位数就是存储字长，单位是$bit$。
存储控制
存储控制即通过电路选择读写的存储单元。一般通过译码器来控制哪个存储单元用来读写。
- 高电平有效：接收到高电平时代表该电路是工作的，接收到低电平时代表该电路是关闭的。
- 低电平有效：接收到低电平时代表该电路是工作的，接收到高电平时代表该电路是关闭的。若代表线路或开关的字母上有横杠代表低电平有效。否则一般都是高电平有效。
译码器是将电路信号进行翻译，转换为片选信号的部件。由于同时对多个存储单元进行读写操作时，数据可能发生混乱。所以就需要用对应数据的所在地址来区分不同的数据，译码器将输入的二进制代码翻译为高低电平信号。
- 假如使用$n$位地址码，有一种方法是用$1$代表当前读取的逻辑地址，即$00\cdots01$就代表$1$，$00\cdots10$就代表$2$，这时候每一位就对应一位，就只能表示$n$个存储单元。这是基本电平信号控制。
- 为了提升效率表示更多地址，所以需要译码器将电平信号转换为逻辑信号，将普通的$01$信号变为逻辑的二进制信号，从而能表示的地址就变成了$2^n$个。
输入口为$2$个电路，输出口为$2^2=4$的译码器就是$24$译码器，输入口为$3$输出口为$2^3=8$的译码器就是$38$译码器。所以总容量=存储单元个数×存储字长。
通过译码器图可以表示对应线路以及输入口和输出口，用来说明整个$CPU$情况。
- 假如译码器的输入口为$A$、$B$……$N$等$n$个。默认是高电平有效。
- 若高电平有效，则输入口字母为$A$、$B$……$N$，输出口字母为$\overline{Y_i}$，其中$i=2^n-1$。
- 若是低电平有效，则输入口字母为$\overline{A}$、$\overline{B}$……$\overline{N}$，输出口字母为$\overline{Y_i}$，其中$i=2^n-1$。并在字母的线路直线的靠近译码器方框的末端加上空心圈。
译码器应该能被控制进行打开和关闭，所以译码器除了输入口和输出口还有使能端。
- 用于控制译码器的启动和关闭，若图上没有圈或字母上没有横杠则代表高电平有效，使能端输入$1$译码器就能开始工作。实际上会有多个使能端，只有高电平有效的使能端输入$1$，同时低电平有效的使能端输入$0$才能启动，只要输入有一个异常都不会工作，类似输入密码。
主存结构
主存读写
$CPU$要想实现数据的读写操作，就必须与外部器件（芯片）进行以下三类信息的交互：
- 地址信息，即存储单元的地址。
- 控制信息，即对存储器的存储器件（芯片）的选择——读或写。
- 数据信息，即将要用于读或写的数据。
所以在主存结构中必须包含传输这三种信息的线路：地址总线、控制总线、数据总线。
- 首先$CPU$通过地址总线把地址信息传递至存储器，对应地找到目标存储单元。
- $CPU$又通过控制总线把控制信息（读操作或写操作）传递至存储器，找到对应读或写的芯片器件。
- $CPU$最后通过数据总线把将要被读或被写的数据信息传递至目标存储单元，执行数据的读或写。
主存构成
- 存储矩阵：由大量相同位存储单元阵列。
- 译码驱动：将来自地址总线的地址信号翻译成对应存储单元的选通信号，该信号在读写电路的配合下未完成对被选中的单元的读写操作。
- 译码器：将$MAR$输入的地址进行译码，选择选中的存储单元地址。
- 驱动器：根据译码器提供的地址，通过驱动器获取对应存储单元。
- 读写电路：包括读出放大器和写入电路，用来完成读写操作。根据控制电路的读或写操作要求，将$MDR$传入的数据写入存储体中，或将存储体中的数据读出到$MDR$中。
- $MAR$：地址寄存器，保存从地址总线输入的地址。
- $MDR$：数据寄存器，保存读出或写入的数据。
- 地址线$A_i$：用来输入$CPU$要访问的主存地址，是单向的，位数与$CPU$芯片容量相关，一般与$MAR$位数相等。直接连接$MAR$。多少个存储单元就多少根地址线。地址线的多少决定CPU寻址能力。
- 数据线$D_i$：用来输入输出数据，是双向的，位数与读入写入数据位数相关。直接连接$MDR$。存储字长多少位就多少根数据线。数据线的多少决定CPU数据吞吐能力。
- 地址线和数据线位数同时决定的内存大小，假如地址线有$N$根，数据线有$M$根，则芯片容量为$2^N\times MB$。地址线位数代表存储体的行，数据线代表存储体的列。
- 片选线：是整个存储芯片的开关，用来确定哪一个存储芯片被选中，可用于容量扩充。
- $\overline{CS}$：芯片选择信号，选择指定芯片，低电平有效。
- $\overline{CE}$：芯片使能信号，打开指定芯片进行存储，低电平有效。
- 读写控制线：决定芯片进行何种操作。控制线的多少决定$CPU$可以控制的外部部件的数量。
- 如果是一根就用$\overline{WE}$表示，低电平写，高电平读。如果是$WE$则反之。
- 如果是两根，则$\overline{OE}$低电平表示允许读，$\overline{WE}$低电平表示允许写。如果是$OE$和$WE$则反之。
主存分配
- 指按照不同的长度切分存储单元。
- 若字长为$4B$，总容量为$1KB$，则按字节寻址是$1K$个单元，每个单元$1B$；按字寻址是$256$个单元，每个单元$4B$；按半字寻址是$512$个单元，每个单元$2B$；按双字寻址是$128$个单元，每个单元$8B$。
半导体随机存储器
主存由$DRAM$实现，$Cache$由$SRAM$实现。
SRAM和DRAM
随机存取存储器$RAM$分为$SRAM$和$DRAM$，即静态与动态。
SRAM和DRAM的区别
| 类型 | SRAM | DRAM |
|---|---|---|
| 存储信息 | 双稳态触发器，分为0态和1态 | 电容，充电是1，否则为0 |
| 破坏性读出 | 非；读只用查看触发器状态；写只用改变触发器状态 | 是；读需要连接电容，检测电流变化，电流随着电路连通而溜走；写需要给电容充放电 |
| 需要刷新 | 不要，能保持两种稳定的状态 | 需要，因为电容上的电荷只能维持2ms |
| 送行列地址 | 同时送，因为地址分为行地址和列地址一同发送，需要一根片选线 | 分两次送，行地址和列地址分开，所以地址线可以复用，线路减少一半，需要一根行通选线和一根列通选线 |
| 运行速度 | 快 | 慢 |
| 集成度 | 低，6个逻辑元件构成 | 高，1个或3个逻辑元件构成 |
| 发热量 | 大 | 小 |
| 存储成本 | 高，常用于Cache |
低，常用于主存 |
注意：$SRAM$不地址复用，而$DRAM$地址复用。（地址线只有原来的一半）
存储器芯片结构
- 存储体：由行选择线$X$和列选择线$Y$选择访问单元。
- 地址译码器：将地址转换为译码输出线上的高电平，以便驱动对应读写电路。
- $I/O$控制电路：控制选中单元读出写入，并放大信息。
- 片选控制信号：产生片选控制。
- 读/写控制信号：输入读或写命令。
DRAM的刷新
- 刷新周期：一般为$2ms$。
- 刷新单元数：以行为单元，每次刷新一行存储单元。
- 如果译码器有$n$位，则可以寻址$2^n$个，也就需要$2^n$与存储单元连接的线路，很难实现。
- 将地址拆分为行列地址（$DRAM$行、列地址等长）。
- $SRAM$需要$2^n$条线路，而$DRAM$需要$2^{\frac{n}{2}+1}$根线。
- 刷新方式：硬件支持，读出一行的信息后重新写入整个行，占用一个读写周期。
- 刷新时刻：假设$DRAM$内部结构排列为$128\times128$的形式，读写周期为$0.5\mu s$，所以$2ms$一共$4000$个周期（注意针对刷新问题，读写时间不是重点，即无论是否读写或者读写多少行，都要在固定时间进行刷新所有行）：
- 分散刷新：
- 每读取完一行数据就刷新一次。
- 如在每存取周期$1\mu s$中前$0.5$用于读写，后$0.5$用于刷新该行。
- 没有死区，但是加长了系统存取周期，降低整机速度。
- 集中刷新：
- 有一段时间专门刷新，但是这时候就无法访问存储器，称为访存死区。该段时间为死时间。
- 因为有$128$行，刷新需要$128$个周期的时间。所以一共需要专门刷新$128\times0.5=64\mu s$，则前面正常读写时间为$2000-64=1936\mu s$，读写需要$3872$个周期。
- 读写时间不受刷新工作的影响，但是存在死区。
- 异步刷新：
- 隔一段时间刷新一次，一次要刷新所有的行，而如果将刷新设置在不需要访存的译码时间可以加大利用效率。
- 将刷新周期除以行数，得到两次刷新操作之间的时间间隔$t$，利用逻辑电路每$t$时间产生一次刷新请求。
- 因为每隔$2ms$要刷新$128$行即$128$次，所以平均每个时间周期为$2ms\div128=15.6\mu s$，$15.6\mu s$中要读写数据并刷新一次即一行，所以每$15.6\mu s$中有$0.5\mu s$的死时间，其中前$15.6-0.5=15.1\mu s$用来读写。
- 分散刷新：
RAM的读写周期
- 读周期：
- 从给出有效地址开始，到读出所选中单元的内容并在外部数据总线上稳定地出现所需的时间，称为读出时间（$t_A$）。从数据稳定到数据有效之间存在一个时间缝隙，因为数据线上的信号速度是不一样的，所以需要这个缓冲。
- 地址片选信号$\overline{CS}$必须保持到数据开始稳定输出，$t_{CO}$为片选的保持时间，即发出片选信号的从地址有效到地址失效的时间，在读周期中$\overline{WE}$为高电平。
- 读周期与读出时间是两个不同的概念，读周期时间（$t_{RC}$）表示存储芯片进行两次连续读操做时必须间隔的时间，因为里面存在要等待数据稳定才能开始读的等待时间等其他时间，所以必然大于等于读出时间。
- 写周期：
- 要实现写操作，要求片选信号$\overline{CS}$和写命令信号$\overline{WE}$必须都为低电平。
- 为使数据总线上的信息能够可靠地写入存储器，要求$\overline{CS}$信号与$\overline{WE}$信号相“与”的宽度至少为$t_{WC}$。
- 为了保证在地址变化期间不会发生错误写入而破坏存储器的内容，$\overline{WE}$信号在地址变化期间必须为高电平。
- 为了保证有效数据的可靠写入，地址有效的时间至少应为$t_{WC}=t_{AW}+t_W+t_{WR}$。其中$t_{AW}$和$t_{WR}$为写入前和写入后必须的间隔时间，$t_W$为写入的时间。
- 为了保证在$\overline{WE}$和$\overline{CS}$变为无效前能把数据可靠地写入，要求写入的数据必须在$t_{DW}$以前在数据总线上已经稳定。
ROM
只读存储器$ROM$即使断电也能保存数据，主存不能直接与$CPU$相连，所以一定会出现$ROM$来完成这个工作。
$ROM$写入速度不如$RAM$，所以一般还是用来保存信息而不用于大量的写。
ROM的分类
- 掩膜式只读存储器（$MROM$）：存储内容由半导体制造厂按用户提出的要求在芯片的生产过程中直接写入，无法修改。
- 一次可编程只读存储器（$PROM$）：存储内容由用户用专门的设备（编程器）一次性写入，之后无法修改。
- 可擦除可编程只读存储器（$EPROM$）：先全部擦除数据然后编程。修改次数有限，写入时间长：
- 紫外线擦除（$UVEPROM$）。
- 电擦除（$EEPROM$）。
- 闪速存储器（$Flash,Memory$）：如$U$盘，写入速度快。
- 固态硬盘（$Solid,State,Drives$）：控制单元+$FLASH$芯片。
主存与CPU连接
对$CPU$来讲，系统中所有物理存储器中的存储单元都处在一个统一的逻辑存储器中，这个逻辑存储器的容量大小受到$CPU$寻址能力的限制。如果一个$CPU$的地址总线宽度为$10$，则该$CPU$可以寻址的存储单元为$2^{10}=1024$个，这$1024$个可寻到的存储单元就构成了这个$CPU$的内存地址空间，也叫做逻辑存储器。
所以对于$CPU$而言，它有一个固定的内存地址大小，对应的地址就是个逻辑地址，所以$CPU$读入的数据有限，一次性处理的能力有限；而内存（如内存条）可以扩充，其实际地址就是物理地址，由操作系统给$CPU$的逻辑地址映射物理地址，还包括替换算法等一系列处理方案。
连接原理
$CPU$与内存通过总线连接。
- $MDR$和$MAR$虽然为寄存器，但是现在一般集成在$CPU$上。
- 数据总线直接连接在$MDR$上，可以写入也可以读出，是一个双向的。
- 地址总线直接连接在$MAR$上，将$CPU$的地址要求交给主存，是一个单向的。其位数决定可寻址最大内存空间。
- 控制总线向主存发送控制类型，如读写要求，是一个单向的。
主存容量扩展
为了获取更多的容量，所以需要对主存容量进行扩展。
位扩展法
- $CPU$的数据线数与存储芯片位数不一定相等，用多个存储器件对数据位数进行扩展（一次性输入输出数据数量）。
- 地址总线和片选线都是并联的，数据总线连接在每一块芯片上。
- 因为需要拓展位，所以一次性需要处理所有芯片的数据，从而需要对芯片同时进行片选线同步信号，所以所有芯片的$\overline{CS}$都可以连接在一起。
- 每个芯片各输入输出一部分数据。
字扩展法
- 增加存储器中字的数量（数据的地址大小即能保存的数据的数量），而位数不变，字扩展将芯片的地址线、数据线、读写控制线相应并联，与位扩展法连接方式一样。
- 但是如果每个芯片同时输入输出输数据则$CPU$无法区分到底是哪个芯片存储的数据，所以不能再将片选线连在一起同时控制。
- 需要用片选信号区分个芯片地址范围，即将每个芯片的片选线依次连接在$CPU$的地址线接口上，因为不能同时工作，所以片选线信号$CS$或$\overline{CS}$不会同时为$1$或$0$，而片选线的信号连接在$CPU$的地址线接口上就相当于将片选线的信号也作为芯片存储地址。
- 如一个$CPU$一共有$16$个地址线接口$A_0$到$A_{15}$与$8$个数据接口$D_0$到$D_7$以及一个读写控制线$\overline{WE}$，现在有两个$8K\times8$位的存储芯片，首先按位扩展时将两个芯片的地址线$A_0$到$A_{12}$全部串联接到$CPU$的$A_0$到$A_{12}$接口上，芯片读写线$WE$串联接到$CPU$的$WE$接口上，数据线$D_0$到$D_7$借到$CPU$数据接口$D_0$到$D_7$上。如果这时$CPU$发出地址信号$0,0000,0000,0000$，就无法识别这个地址是第一块还是第二位芯片的第一位。此时$CPU$的$A_{13}$到$A_{15}$三个接口还是空的，将芯片1的选片线$CS$接到$CPU$的$A_{13}$上，芯片2的选片线$CS$接到$CPU$的$A_{14}$上，此时$CPU$的地址信号会变成15位。因为$CS$指高电平$1$有效，$A_{13}$为$1$代表选择芯片1，$A_{14}$为$1$代表选择芯片$2$，所以$010,0000,0000,0000$代表选择芯片$1$，$100,0000,0000,0000$带包选择芯片$2$。若高位为$110$或$000$则冲突而浪费位数。
- 每个芯片各存储一部分数据。
字位同时扩展法
即增加存储字的数量又增加存储字长。各芯片连接地址线的方式相同，但是连接数据线的方式不同，需要通过片选信号$\overline{CS}$或采用译码器设计连接到对应芯片。
存储芯片片选
- 线选法：
- 当某地址线信息为“$0$”时，就选中与之对应的存储芯片，只能一位有效。
- 优点：不需要地址译码器，线路简单。
- 缺点：地址空间不连续，选片的地址线必须分时为低电平（否则不能工作)，不能充分利用系统的存储器空间，造成地址资源浪费。
- 译码片选法：
- 由于译码器可以将$n$位映射到$2^n$位，所以通过地址译码芯片产生片选信号。如线选法如果三位编码只能选择三个芯片，而译码片选法三位编码可以选择八个芯片，即三位二进制编码。
- 优点：地址空间可连续，可以增加逻辑设计。
- 缺点：电路逻辑复杂。
双端口RAM和多模块存储器
由于$CPU$与主存相连，而$CPU$速度增长是指数级别的，而主存容量增长是线性的，所以双方速度不匹配，所以需要更快的访问速度。一方面可以更高性能存储器，一方面使用高速缓冲存储器。
存取周期由存取时间和恢复时间构成，所以缩短存取周期的方法一种是空间上并行（双端口存储器技术），一种是时间上并行（多模块存储器技术）。
双端口RAM
左右有两个独立的端口，所以有两对独立的数据线、地址线、控制线可以同时对主存进行操作，如果不是一个位置不会发生异常。
两个端口对同一主存操作有以下$4$种情况：
- 两个端口不同时对同一地址单元存取数据。
- 两个端口同时对同一地址单元读出数据。
- 两个端口同时对同一地址单元写入数据。会产生写入错误
- 两个端口同时对同一地址单元，一个写入数据，另一个读出数据。会产生读出错误。
所以只用设置一个“忙”的标志位，若$CPU$发现该端口为忙，则等待一段时间再进行访问。
多模块存储器
单体多字存储器
由于$CPU$的速度远快于主存，所以同时从主存中拿出多个指令就能让$CPU$等待$I/O$时间变短，从而提高效率，单体多字存储器以此而实现。
普通存储器是每行为一个存储单元，而对于单体多字存储器来说，每个存储单元存储$m$个字，若总线宽度也为$m$个字，则一次并行就能读出$m$个字。但是只有数据和指令是连续存放在内存的才能这样操作，转移指令无效。
多体并行存储器
每个模块都有相同的容量和存取速度，以及独立的读写控制电路、地址寄存器和数据寄存器。地址分为体号和体内地址两个部分。
对读取数据进行优化。（不是对传输数据）
- 高位交叉编址的多体存储器：
- 高位是体号，低位是体内地址。
- 按列，模块里先编址，一个个模块进行分配。只是相当于扩容而已，对于速度没有改变。
- 若连续取$n$个存储字，每次访问需要$T$的时间，则耗时$nT$。
- 低位交叉编址的多体存储器：
- 低位是体号，高位是体内地址。
- 按行，每一个单元先编址，一行行进行分配。
- 由于每个存储体都是独立的，所以可以间隔一小段时间就能进行另一个的存储单元的访存而不用等待上一个单元的阶数。这就要求其模块数必须到达一个值，从而保证能流水线运行而不会卡住。
- 设模块字长等于数据总线宽度，模块存取一个字的存取周期为$T$，总线传送周期为$r$，所以存储器交叉模块数应该大于等于$m=T/r$。这个值被称为交叉存取度。
- 从而启动该模块后能保证经过$m\times r$的时间后再次使用该模块时上次存取操作已经完成。
- 若连续取$n$个存储字，每次访问需要$T$的时间，启动间隔为$\tau$，则耗时$T+(n-1)\tau$。
如高位交叉编址，体号+体内地址：
| M0 | M1 | M2 | M3 |
|---|---|---|---|
| 0000 | 0100 | 1000 | 1100 |
| 0001 | 0101 | 1001 | 1101 |
| 0010 | 0110 | 1010 | 1110 |
| 0011 | 0111 | 1011 | 1111 |
这时按顺序访问就是竖着的。
低位交叉编址，体内地址+体号：
| M0 | M1 | M2 | M3 |
|---|---|---|---|
| 0000 | 0001 | 0010 | 0011 |
| 0100 | 0101 | 0110 | 0111 |
| 1000 | 1001 | 1010 | 1011 |
| 1100 | 1101 | 1110 | 1111 |
此时顺序访问就是横着的，多个存储体可以共同输入输出数据，可以流水线操作。
对于交叉存储器的存取速度：
- 模块数为$m$，存储周期为$T$，字长为$W$，数据总线宽度为$W$，总线传输周期为$r$，连续存取$n$个字，求交叉存储器的带宽。（有$m$个存储体，存储周期为$T$，字长为$W$，每隔$r$时间启动下一个存储体，连续存取$n$个字，求交叉存储器的存取速率。）
- 连续存取$n$个字耗时为$T+(n-1)r$，但是需要$m\geqslant\dfrac{T}{r}$。因为如果模块数过少，则轮流到某一个存储体时这个存储体上一次的处理还没有完成就无法继续工作了。
- 所以带宽是$\dfrac{n\times W}{T+(n-1)r}$。
- 当$n$无限大时，带宽趋近于$\dfrac{W}{r}$，而单个存储体的带宽为$\dfrac{W}{T}$。
多端口存储器是对同一个存储体使用多套读写电路实现的，扩大存储容量的难度显然比多体结构的存储器要大，而且不能对多端口存储器的同一个存储单元同时执行多个写入操作，而多体结构的存储器则允许在同一个存储周期对几个存储体执行写入操作。
高速缓冲存储器
在操作系统中也谈论过$Cache$。
并注意访存指的是访问主存而不包括$Cache$。
高速缓冲存储器基本概念
局部性原理
- 时间局部性：程序所访问的数据在相邻时间也可能访问到。
- 空间局部性：程序所访问的数据的周围数据也可能访问到。
高速缓冲存储器地址
- 主存储器的地址包括主存块号和块内地址，而$Cache$的地址包含缓冲块号和块内地址，两个块内地址都是一样长的且完全相同的。
- $Cache$块又称为$Cache$行。长度为块长或$Cache$行长。
- $Cache$还有一个标记，用来说明$Cache$块与主存块的关系，等于此块在主存中的块号。
工作流程
- $CPU$发出访问地址，从地址总线传输到$Cache$。
- 通过$Cache$主存地址映射变换结构，将主存地址转换为$Cache$地址，在$Cache$中寻址对应数据。
- 如果命中就访问$Cache$并取出指令通过数据总线返回$CPU$。
- 如果不命中，就直接访问主存，取出信息通过数据总线返回$CPU$，并把这个信息存储在$Cache$中。
- 需要检测$Cache$是否已满，如果不满就直接将新的主存块调入$Cache$进行存储。
- 若已经满了则通过$Cache$替换结构，执行替换算法腾出空位再调入。
其中$CPU$和$Cache$之间数据交换以字为单位，而$Cache$和内存之间数据交换以块为单位。
命中与未命中
- 命中：主存块调入缓存，主存块与缓存块建立了对应关系，用标记记录与某缓存块建立了对应关系的主存块号。
- 未命中：主存块未调入缓存，主存块与缓存块未建立对应关系。
- 命中率：$CPU$欲访问的信息在$Cache$中的比率，设一个程序执行期间，$Cache$的总命中次数为$N_c$，访问主存的总次数为$N_m$，则命中率$H=\dfrac{N_c}{N_c+N_m}$。
- 命中率与$Cache$的容量与块长有关。一般每块可取$4$到$8$个字，块长取一个存取周期内从主存调出的信息长度。
- 访问效率=$Cache$访存时间÷平均访存时间。
- 相联存储器：并行比较标记，若有标记与当前将要访问的地址的标记相同，且有效位为1（表示当前存储单元存储数据），则命中；若标记不同，则直接替换。
高速缓冲存储器的效率
- 效率$e$与命中率有关，$e=$访问$Cache$的时间/平均访问时间$\times100%$。
- 假如$Cache$和主存是同时被访问的，设$Cache$命中率为$h$，访问$Cache$的时间为$t_c$，访问主存的时间为$t_m$，则$e=\dfrac{t_c}{h\times t_c+(1-h)\times t_m}\times100%$。当$h=0$时最小为$\dfrac{t_c}{t_m}$，当$h=1$时最大为$1$。
地址映射
即将主存块调入$Cache$时应该将其放在哪里。
地址以字节为单位。
默认都需要一位有效位。
注意：$Cache$字块标记是指$Cache$有多少行，而不是有多少容量。
直接映射
存储方式：
- 对号入座，每一个主存块只能存放在唯一一个地方。
- 将主存储体按$Cache$存储体的长度划分为多个区，主存的每个区只能放在$Cache$的指定区域中。类似于模运算，将主存长度对$Cache$长度取模，地址相同余数的内存块放在同一个$Cache$块中。
地址组成：
- 地址=主存字块标记+$Cache$字块标记+字块内地址。
- $Cache$地址=$Cache$字块标记+字块内地址。
- 主存字块标记为主存容量除以$Cache$容量，表示要用多少位来区分主存地址。
- $Cache$字块标记，即$Cache$行号的位数为$Cache$的块数的二对数。
- 字块内地址就是块内地址，位数为每块容量的二对数。
附加位：
- 这种映射方式需要一位有效位标识是否有数据存储。
- 若发生冲突，不需要替换算法直接替换出去。所以不需要替换位。
- 但是与全相连映射不同的是，因为直接映射是根据模运算来存储的，所以行与行之间是顺序的关系，所以主存块号不需要全部存入标记项，把能区分相同模结果的地址前一部分位的数据存入即可。
特点：
- 优点：节省掉$Cache$字块标记，有效位存储的地址减少，实现难度降低。
- 缺点：空间利用率降低。
如$Cache$一共八行，则主存按八为一个周期存储，则如$Cache$的$0$号地址中一定存入主存块地址模八后余$0$的主存块，即地址都为为$xx\cdots000$，同理$1$号地址存的都是$xx\cdots001$，所以可以保存主存地址减三的前面位数就足够了。这里的$000$和$001$等类似于$Cache$的组号。若$Cache$的行数为$2^n$，主存块号地址为$c$位，则标记项只用保存$c-n$位就可以了。
全相联映射
存储方式：
- 空位随意放。
- 但是这时候还是不知$Cache$里的每一个存储单元存的是主存的哪一块数据，所以还需要将主存的主存块号保存到标记项中。
- 因为是乱序存放，所以一定要把整个主存块号都放入标记项中。
地址组成：
- 地址=主存字块标记+字块内地址。
附加位：
- 因为无法查看$Cache$里面每个存储块是否有数据，所以还需要一个有效位来表示里面是否有数据，将有效位放入标记项中。
特点：
- 优点：冲突概率低；空间利用率高，命中率高。
- 缺点：标记比较速度慢，实现成本高（相联存储器）。
组相联映射
存储方式：
- 按号分组，组内随意放，结合了上面二者的优点。
- 标记项也需要存入能区分数据块的部分地址。
- 将$Cache$的块分为几个组，主存不再按照$Cache$的行数进行模运算分组存入，而用$Cache$组的个数进行模运算，虽然这样能节省的位数变少，但是这样主存的某一块就可以在每一组内随机选一个存储，而不用只能存储在一个块内浪费其他块的空间。
- 每组有$r$个行，则称为$r$路组相联。
地址组成：
- 地址=主存字块标记+$Cache$组号+字块内地址（$Cache$每行长度）。
- 一般物理地址的中间部分直接映射为组号。
- 当$Cache$组地址位数长度变为表示$Cache$行数的二进制位，那么组号和行号一样就变成了直接映射，若组地址位数为$1$全部为一个组，则$Cache$不分组都随机存储即变成了全相连映射。
附加位：
- 需要有效位。
标记整列
称为地址映射表，即标记项总体长度，即总$Cache$行数$\times$标记项的长度。
标记项的长度=标记位长度+其他位长度（如有效位、替换控制位、一致控制位即脏位）。
- 有效位默认是一位。
- 替换控制位主要用于组相联映射方式，其他两种方式基本上没有这个。多少路组相联的二对数对应多少位替换控制位。如两路组相联对应标记项的一位替换控制位，物理地址的$Cache$组标记为三位对应八组，则一共有十六行$Cache$行。
- 脏位默认是一位。如果是写回法和写分配法则需要，全写法和非写分配法则不需要。
标记位长度=主存地址长度（即主存总容量位数而不是$Cache$容量长度）-其他地址长度（块内地址，即$Cache$行的数量的对数；组地址，即多少个组的对数）。
标记的主要计算在于主存块标记长度，即标记位长度，为什么是这个长度？为什么要如此计算？
我们要将主存的内容放到高速缓冲存储器中，所以我们要根据主存的地址找到$Cache$的地址，并能通过$Cache$的地址找到主存的地址。由于$Cache$的数量远小于主存的数量，所以我们使用不同的方式将主存映射到$Cache$中。我们通过替换映射算法能得到一部分主存和$Cache$的映射规则，但是这种规则只能得到不完整的地址信息，那么其他相关地址信息就是通过标记项来给出，通过标记项和$Cache$位置信息就能完整映射$Cache$到每一个主存地址。
因为是主存地址映射，所以我们自然要映射到每一个主存地址，所以主存地址长度是我们的目标，通过地址信息加和得到所有主存地址。由于主存与$Cache$之间的数据交换单位为块，所以只要给定一个$Cache$块在主存中的首地址，那么一个块内的其他数据的地址也是可以推算的，所以这部分的信息可以在地址总线传输过来的块内偏移量中得到，标记位中就可以不要这个信息，所以主存地址长度减去块内地址长度。通过映射方式不同，我们可以得到每一块或每一组$Cache$与主存之间的映射关系，确定映射关系后，地址总线传输块号或者组号，所以这部分内容也是可以减去的，即主存地址长度再减去块号长度或块组号长度。最后的位数就是标记长度，通过标记位能与块号/组号+偏移地址得到主存地址。
如某计算机的主存地址大小为$256MB$，按字节编址，有$8$个$Cache$行，行长$64B$，使用直接映射方式，求标记项长度。首先主存地址大小为$256MB=2^{28}B$，则主存地址总长度为$28$位；然后行长$64B=2^6B$，则块内偏移地址长度为$6$位，所以$28-6=22$，使用直接映射方式，一共$8$行，所以行号位长度为$3$位，所以$22-3=19$，标记位一共$19$位。
替换算法
即$Cache$中存储满了如何处理。对于直接映射法来说，固定替换出前一个数据存入此时的数据，所以替换算法只针对全相联映射和组相联映射。
随机算法
即$RAND$算法：随机地确定替换的$Cache$块。它的实现比较简单，但没有依据程序访问的局部性原理，故可能命中率较低。但是这种方式基本上不会使用。
先进先出算法
即$FIFO$算法：选择最早调入的行进行替换。它比较容易实现，可以使用堆栈，但也没有依据程序访问的局部性原理，可能会把一些需要经常使用的程序块（如循环程序）也作为最早进入$Cache$的块替换掉。
近期最少使用算法
即$LRU$算法：依据程序访问的局部性原理选择近期内长久未访问过的存储行作为替换的行，平均命中率要比$FIFO$要高，是堆栈类算法。是一种局部性策略。
$LRU$算法对每行设置一个计数器，$Cache$每命中一次，命中行计数器清$0$，而其他各行计数器均加$1$，需要替换时比较各特定行的计数值，将计数值最大的行换出。
最不经常使用算法
即$LFU$算法：将一段时间内被访问次数最少的存储行换出。每行也设置一个计数器，新行建立后从$0$开始计数，每访问一次，被访问的行计数器加$1$，需要替换时比较各特定行的计数值，将计数值最小的行换出。是一种全局性策略。
但是这种策略是无法实现的，因为计算机不可能全局考虑后面会出现什么，而只会考虑局部。
写策略
即$Cache$中内容修改后如何让主存于$Cache$修改的保持一致。分为当前命中和当前不命中的情况：
- 命中：全写法、写回法。
- 不命中：写分配法、非写分配法。
标记项结构：有效位+脏位+替换控制位+标记位。
全写法
也称为写直通法或$write-through$：当$CPU$对$Cache$写命中时，必须把数据同时写入$Cache$和主存。
由于写$Cache$要远快于写主存，所以一般使用写缓冲（$write buffer$）暂存写入的数据，但是如果写的速度过快可能会出现溢出。
写回法
也称为$write-back$：当$CPU$对$Cache$写命中时，只修改$Cache$的内容，而不立即写入主存，只有当此块被换出时才写回主存（全部改完了再写回主存）。
需要在信息位中使用一个类似于有效位的$1/0$表示位，名为脏位，$0$代表未修改，$1$代表修改。
写分配法
也称为$write-allocate$：把主存中的块调入$Cache$，在$Cache$中修改。一般搭配写回法使用，即写完$Cache$之后再把$Cache$的值覆盖在主存的数据上，所以也需要设置一个脏位。
非写分配法
也称为$not-write-allocate$：只写入主存，不调入$Cache$。一般搭配全写法使用。
多级Cache
使用两级$Cache$，在与$CPU$直接连接的第一层$Cache$使用全写法，在与主存直接连接的第二层$Cache$使用写回法。
虚拟存储器
$Cache$为了解决主存和$CPU$之间的问题，而虚拟存储器为了解决主存和辅存之间的问题。虚拟存储器包括主存和辅存，将主存和辅存联合在一起统一编址。
- 是一个逻辑模型。
- 用户给出一个地址，叫做虚地址或逻辑地址，虚拟存储器要给出该地址对应的数据。
- 有辅助硬件将虚地址映射到主存中某个单元，主存单元地址称为实地址或物理地址。虚地址远大于实地址。
- 基于局部性原理：在程序执行过程中，程序对主存的访问是不均匀的。
- 由操作系统和一部分硬件完成地址映射。
具体内存参考操作系统，主要考页式存储，段式非常少。
对于虚拟存储器的三个地址空间：
- 实地址=主存页号+页内字地址。
- 虚地址=虚存页号+页内字地址。
- 辅存地址=磁盘号+盘面号+磁道号+扇区号。
注意：虚拟系统中，找到的地址后，进行地址映射是靠操作系统完成，在操作系统的书中会更详细讲到。
页式虚拟寄存器
- 虚拟空间与主存空间都被划分成同样大小的页，主存的页称为实页，虚存的页称为虚页。
- 虚页地址分为虚页号和页内地址，实页地址分为实页号和页内地址，在虚页转换为实页时，页内地址是相同的，唯一要考虑的是虚页号如何转换为实页号。
- 做法就是将这种映射关系存在一张表中，这张表就是页表。页表存储的是实页号和装入位，用来标识虚拟地址是否装入主存地址。页表长期存储在主存中。
- 首先页内基表寄存器保存着页表起始地址，和虚页号进行计算就得到了页表项的地址，就可以找到页表项，把页表项中的实页地址取出并进行拼接就得到了页内地址。
- 若在$Cache$中存有则访问$Cache$，若没有再访问主存。
- 页表包括有效位（装入位）、脏位、引用位、物理页或磁盘地址。
- 优点：长度固定，页表简单，调入方便。
- 缺点：程序不可能总是页面的整数倍，所以最后一页的部分空间会浪费；页不是逻辑独立的实体，所以保护、处理、共享不便。
对于页表的大小选择需要适度。页面若很小，虚拟存储器中包含的页面数就会过多，使得页表的体积过大，导致页表本身占据的存储空间过大，同一个程序需要调用更多页表，使操作速度变慢；当页面很大时，虚拟存储器中的页面数会变少，由于主存的容量比虚拟存储器的容量小，主存中的页面数会更少，每次页面装入的时间会变长，每当需要装入新的页面时，速度会变慢。
段式虚拟寄存器
- 段式虚拟存储器中的段是按程序的逻辑结构划分的，各个段的长度因程序而异。
- 虚拟地址分为两部分：段号和段内地址。
- 段表：每一行记录了与某个段对应的段号、装入位、段起点和段长等信息。
- 由于段的长度可变，所以段表中要给出各段的起始地址与段的长度。
- 段表的段首址加上虚拟地址的段内地址就得到了物理地址。
- 优点：按逻辑划分，所以利于编译、管理、修改、保护、共享。
- 缺点：段长度可变，所以分配空间不便，容易造成碎片问题。
段页式寄存器
- 把程序按逻辑结构分段，每段再划分为固定大小的页，主存空间也划分为大小相等的页。
- 程序对主存的调入、调出仍以页为基本传送单位。每个程序对应一个段表，每段对应一个页表。
- 所以段长必须是页长的整数倍，段首址必须是某页的页首址。
- 虚拟地址：段号+段内页号+页内地址。
- $CPU$根据虚地址访存时，首先根据段号得到段表地址；然后从段表中取出该段的页表起始地址，与虚地址段内页号合成，得到页表地址；最后从页表中取出实页地址，与页内地址拼接形成主存实地址。
快表
快表原理
- 页表、段表存放在主存中，收到虚拟地址后要先访问主存，查询页表、段表，进行虚实地址转换。放在主存中的页表称为慢表（$Page$）。
- 提高变换速度→用高速缓冲存储器$Cache$存放常用的页表项→快表（$TLB$）。
- $TLB$是$Page$的副本（快表是慢表的副本），而$Cache$为主存的副本。
- 慢表在主存中。快表是一个特殊的单独的$Cache$。
- 使用相联存储器，所以查找速度更快。也可以使用$SRAM$。（$DRAM$必须不断刷新不适合$TLB$和$Cache$）
- 快表地址计算与之前的地址计算类似，使用全相联或组相联的模式，若使用组相联也需要留出组号。
快表映射
快表映射一般次啊用全相联或组相联映射。映射方式与$Cache$映射类似。
- 每个$TLB$项由页表表项内容加上一个$TLB$标记字段组成，$TLB$标记用来表示该表项取自页表中哪个虚页号对应的页表项。
- $TLB$标记的内容在全相联方式下就是该页表项对应的虚页号。
- $TLB$标记的内容在组相联方式下则是对应虚页号的高位部分，而虚页号的低位部分用于选择$TLB$组的组索引（组号）。
快表与Cache
先虚拟存储再高速缓存，先主存再$Cache$。
| 序号 | TLB | Page | Cache | 访存次数 | 访磁次数 | 说明 |
|---|---|---|---|---|---|---|
| 1 | 命中 | 命中 | 命中 | 0 | 0 | TLB命中则Page一定命中，Cache未知 |
| 2 | 命中 | 命中 | 缺失 | 1 | 0 | TLB命中则Page一定命中，Cache未知 |
| 3 | 缺失 | 命中 | 命中 | 1 | 0 | TLB缺失而Page可能命中，Cache未知 |
| 4 | 缺失 | 命中 | 缺失 | 2 | 0 | TLB缺失而Page可能命中，Cache未知 |
| 5 | 缺失 | 缺失 | 缺失 | 2+ | 1+ | TLB缺失而Page也缺失，则Cache一定缺失 |
- $Cache$缺失：硬件完成。
- $TLB$缺失：硬件或软件。
- $Page$缺失：软件完成（操作系统的缺页异常处理程序）。
虚拟存储器与Cache
- $Cache$主要解决系统速度，而虚拟存储器却是为了解决主存容量。
- $Cache$全由硬件实现，是硬件存储器，对所有程序员透明；而虚拟存储器由$OS$和硬件共同实现，是逻辑上的存储器，对系统程序员不透明，但对应用程序员透明。
- 对于不命中性能影响，因为$CPU$的速度约为$Cache$的$10$倍，主存的速度为硬盘的$100$倍以上，因此虚拟存储器系统不命中时对系统性能影响更大。
- $CPU$与$Cache$和主存都建立了直接访问的通路，而辅存与$CPU$没有直接通路。也就是说在$Cache$不命中时主存能和$CPU$直接通信，同时将数据调入$Cache$；而虚拟存储器系统不命中时，只能先由硬盘调入主存，而不能直接和$CPU$通信。
所以高速缓冲存储器连接主存实地址与$Cache$地址，虚拟存储连接主存实地址和虚拟存储逻辑地址，快表连接虚拟存储逻辑地址与快表地址。