存储器概述

存储器分类

按照在计算机中的层次分类

1. 主存储器，又称内存。
2. 辅助存储器，又称辅存、外存。
3. 高速缓冲器，建成 $Cache$，处于主存和 $CPU$ 之间，用于存放 $CPU$ 经常使用的指令和数据，其存取速度可与 $CPU$ 相匹配。

按照存储介质分类

可分为磁表面存储器（磁盘、磁带）、磁芯存储器、半导体存储器（$MOS$ 型存储器、双极型存储器）和光存储器（光盘）。

按照存取方式分类

1. 随机存储器（$RAM$），存储器中的任意位置都可随机存取，且存取时间与位置无关，主要用作主存或 $Cache$，可以分为静态 $RAM$ 和动态 $RAM$.
2. 只读存储器（$ROM$），存储器的内容只能随机读出而不能写入，信息一旦写入，即使断电内容也不会丢失，由 $ROM$ 派生出的存储器也可以反复重写。 $ROM$ 和 RAM 均为随机存取，广义上的只读存储器现在可以通过点擦除的方式写入，其 只读 的概念并没有保留，但是其写入速度会比读取速度满很多。
3. 穿行访问存储器，读写时按照其物理位置的先后顺序寻址，包括顺序存取存储器（如磁带）和直接存取存储器（如磁盘、光盘）。

按照信息的可保存性分类

断电后信息消失的存储器成为 易失性存储器，信息仍然保留的被称为 非易失型存储器。

若信息被读出时，原存储信息被破坏，则称为 破坏性读出，否则称为 非破坏性读出，具有破坏性读出的存储器每次读出后，必须紧跟一个 再生 操作。

存储的性能指标

主要有三个指标——存储容量、单位成本、存储速度。

存储容量 $=$ 存储字数 $\times$ 字长，单位成本 $=$ 总成本 $/$ 总容量，存储速度 $=$ 数据宽度 $/$ 存取周期。

存取时间不等于存取周期，一般存取周期大于存取时间，因为读写之后，需要有一段恢复内部状态的复原时间。对于破坏性存储器，存储周期甚至可以达到存取时间的两倍。

多级层次的存储系统

存储器层次结构的主要思想是上一层的存储器作为下层存储的高速缓存，其速度接近上层，而成本却接近于下层存储器，能一定程度上解决 速度、容量、成本 三者的矛盾。

caution

主存和 $Cache$ 之间的数据调用是由硬件完成，对所有程序员都是透明的。

在主存 - 辅存的不断发展中，逐渐形成了 虚拟存储系统，使得编程时可用的地址空间远大于主存空间。

note

主存 -$Cache$ 和主存 - 辅存中，上层内容都是下层的一部分内容的副本。

主存储器

主存储器主要由 $DRAM$ 实现，$Cache$ 则由 $SRAM$ 实现，都属于易失性存储器。

note

$DRAM$ 的单位价格低于 $SRAM$，速度也慢于 $SRAM$，因为 $SRAM$ 需要更多的硅。

info

通常把存放一个二进制位的物理器件成为 存储元 ，地址码相同的多个存储元构成一个 存储单元 ，若干存储单元构成 存储体 .

SRAM 芯片

静态随机存储器（$SRAM$）的存储元是利用双稳态触发器（六晶体管 $MOS$）来记忆信息，属于非破坏性存储器。

SRAM 存取速度快，但是集成度低，功耗较大，价格昂贵。

DRAM 芯片

动态随机存储器（$DRAM$）利用存储元电路中的栅极电容上的电荷存储信息，$DRAM$ 的基本存储元只使用一个晶体管，因此其密度比 $SRAM$ 高很多。

相对于 $SRAM$ 来说，$DRAM$ 更易集成、价格更低，容量更大，功耗更低。

$DRAM$ 电容上的电荷一般只能维持一到两毫秒，因此需要每隔一段时间刷新一次，刷新周期通常取 $2ms$. 常用刷新方式有 $3$ 种：

1. 集中刷新：在一个刷新周期内，利用一段固定时间，依次对存储器进行逐行再生，此期间 停止读写，成为 死时间 ，又称访存 死区 ；
2. 分散刷新：将每行刷新分散到各个周期中去，因此一个存储器的工作周期被分为两部分—— 前半部分用于正常读、写或保持，后半部分用于刷新。此方式虽然没有死区，但是延长了系统的存取周期，导致整机速度降低；
3. 异步刷新：前两种方法的结合，可以缩短死时间，并且充分利用最大刷新间隔 $2ms$ 的特点。其将刷新周期除以行数得到两次刷新操作之间的时间间隔 $t$，利用逻辑电路间隔产生刷新请求，从而避免使 $CPU$ 连续等待过长时间，并且减少了刷新次数，提高工作效率。

info

刷新操作对 $CPU$ 是透明的，且刷新单位是行，由芯片内部整成行地址。

刷新操作类似于读操作，但是有所不同。另外刷新不需要选片，整个存储器中的所有芯片同时被刷新。

SDRAM 芯片

tip

同步动态存储器，内部分为多个存储体，可以轮流交叉工作，因此该芯片有额外选择存储体的引脚；支持突发读写，行列地址送一次后，可以连续读取 $n$ 个连续数据，常用于高速缓存等。

更高级的还有 $DDR\ SDRAM$ 等。

DRAM 芯片的读写周期

读周期中，为了使芯片能正确接受行、列地址，行选通信号 $\overline{RAS}$ 和列选通信号 $\overline{CAS}$ 有效期会有一段时间间隔，先接受行地址，再接受列地址。读写控制信号 $\overline{WE}$ 为高电平，并在 $\overline{CAS}$ 有效前建立。

写周期中，行列选通的时序关系和读周期相同，$\overline{WE}$ 为低电平，并在 $\overline{CAS}$ 有效前建立。

读 （写）周期表示 $DRAM$ 芯片进行两次连续读（写）所必须间隔的时间。

info

DRAM 芯片容量大，为了减少地址引脚数量，因此将行列地址分开输入。

SRAM 和 DRAM 的比较

	SRAM	DRAM
存储信息	触发器	电容
破坏性读出	非	是
需要刷新	不要	需要
送行列地址	同时送	分两次
运行速度	快	慢
集成度	低	高
成本	高	低
主要用途	高速缓存	主机内存

存储器芯片内部结构

存储器芯片主要由以下部分组成：

1. 存储体（存储矩阵），由 行选择线（X） 和 列选择线（Y） 来选择目标单元。存储体的相同行、列上的位同时被读出或写入。
2. 地址译码器，将地址转换为移码输出线上的高电平，驱动相应读写电路。
3. I/O 控制电路，控制选中单元的读出或写入，具有 放大信息 的作用。
4. 片选控制信号，由于单个芯片容量太小，因此多个芯片扩展，访问某个字时，首先要片选对应的芯片，而其他芯片不被选中。
5. 读/写控制芯片，控制读/写行为。

指令执行过程

指令执行过程中需要访问主存时，$CPU$ 首先将被访问单元地址送到 $MAR$，通过 地址线

将其送到主存中的 地址寄存器。

同时 $CPU$ 将读写信号通过 控制线 送到主存的 读写控制电路

1. 若是写操作，将数据送到 MDR 中，在 读写控制电路 的控制下，经过 数据线 将信号写入选中单元；
2. 若是读操作，主存将数据送到 MDR 中。

info

数据线宽度和 $MDR$ 相同。

多模块存储器

多模块存储器是一种空间并行技术，利用多个结构完全相同的存储模块的并行工作来提高存储器的吞吐率，常用的有 单体多字存储器 和 多体低位交叉存储器。

caution

$CPU$ 的速度比存储器快得多，若同时从存储器中取出 $n$ 条指令，就可充分利用 CPU资源，提高运行速度，多体交叉存储器就是基于该思想提出。

单体多字存储器

特点是存储器中只有一个存储体，每个存储单元存储 $m$ 个字，总线宽度也为 $m$ 个字，一次并行读出 $m$ 个字，地址必须顺序排列并处于同一存储单元。一个存储周期内，从同一地址取出 $m$ 条指令，然后逐条送至 $CPU$.

缺点：指令和数据在主存内必须是连续存放的，一旦遇到转移指令或操作数不能连续存放的情况，该方法效果不明显

多体并行 （交叉）存储器

由多体模块组成，每个模块的容量速度相同，各模块有独立的读写控制电路、地址寄存器和数据寄存器，既能并行工作（即所有存储体同时工作），又能交叉工作。

有高位交叉编址 （顺序方式）和低位交叉编址（交叉方式）两种，高位交叉编址中高位地址表示体号，低位地址表示体内地址，低位地址译码之后才能访问对应模块。

访问连续主存块时，必须先在一个模块内访问完毕，才能访问下一个模块，不能并行访问，因此不能提高存储器吞吐。

低位交叉方式的低位地址为体号，高位地址为体内地址，每个模块按照 模m 交叉编址，模块号 $=$ 单元地址 $\% \ m$ ，数据或程序连续存储在相邻模块中。

地位交叉方式编址后，可在不改变每个模块的存取周期下，采用 流水线 的方式并行存储，提高存储器的带宽。

加速比：设读出的是转移指令且转移成功或数据不连续的概率为 $\lambda$，则并行存储器的加速比为

$$B= \frac{1-(1-\lambda)^m}{\lambda}$$

相联存储器

tip

相连存储器通常由 $SRAM$ 组成，是按照内容而不是地址访问的，但是其也可以按照地址访问；存储器内有大量的比较器并发比较，并将结果接入多路选择器，因此硬件复杂，成本高，其容量不可能太大，太大会导致查找速度变慢；一般用于 $Cache$ 的目录表，虚拟存储器的快表等。

主存储器与 CPU 的连接

连接原理

1. 主存储器通过数据总线、地址总线和控制总线与 $CPU$ 连接
2. 数据总线的位数和工作频率的乘积正比于数据传输率
3. 地址总线的位数决定了可寻址的最大内存空间

主存容量扩展

单个存储芯片容量有限，因此常用多个芯片扩展主存容量。

位扩展法

顾名思义，对位即字长进行扩展，使其数据位数和数据线位数 相同 .

位扩展法可以理解为并联，所有芯片的 地址端、片选端和读写控制端 就并联，即接受相同的信号，数据端全部接入数据线，充当其一部分，这样就能同时发出更多位的数据。

字扩展法

与位扩展法相反，字扩展法扩展主存所能存储的总字数，显然需要将一部分信号（高位）经过译码器（2/4, 3/8 等）充当 片选信号 ，同时所有芯片的数据端都与数据线相连，这样同一时间只会有一个芯片被激活，也只会有一个芯片的数据进行传送 .

字位同时扩展法

不再赘述。

芯片片选

片选除了选择译码器还可以直接片选，被称为线选法，要求片选信号中只能有一位有效，这会导致地址空间不连续。

只读存储器

特点

$ROM$ 中一旦有了信息，就不能轻易改变，即使掉电也不会丢失，其有两个显著优点：

1. 结构简单，位密度比高；
2. 非易失性，可靠性高。

类型

根据制造工艺不同，分为 掩模式只读存储器（MROM）、一次可编程只读存储器（PROM）、可擦除可编程只读存储器（EPROM）、$Flash$ 存储器和固态硬盘（$SSD$）。

1. $MROM$，其内容由半导体制造厂按照用户需求直接写入，不可更改；
2. $PROM$，只可以利用专门设备实现一次性编程；
3. $EPROM$，可以利用专门设备实现多次改写，但是写入时间长，次数有限；
4. $Flash$ 存储器，能快速擦除重写，价格便宜集成度高；
5. 固态硬盘，用固态电子存储芯片阵列制成的硬盘，由控制单元和存储单元（$Flash$ 芯片）组成，对比传统硬盘读写快，功耗低，但是价格高。

外部存储器

磁盘

优点

1. 容量大，单价低；
2. 可重复写入；
3. 信息可长期保存，甚至脱机存档；
4. 非破坏性读出，无需再生。

缺点：速度慢、机械结构复杂、对工作环境要求高。

磁盘存储器

组成：

1. 磁盘驱动器，核心部件是 磁头组件 和 盘片组件；
2. 磁盘控制器，是磁盘和主机的接口，主流标准有 $IDE$、$SCSI$、$SATA$；
3. 盘片。

存储区域：一块硬盘有若干 记录面，每个面划分为若干 磁道，每条磁道又划分为若干 扇区（又称，块），其是硬盘读写的最小单位。

磁头数：就是记录面的数量，表示硬盘有多少个磁头，一一对应。

柱面数：表示每面盘片上有多少磁道，不同记录面相同位置的磁道就形成了柱面。

扇区数：每个磁道的扇区数。

info

一个磁盘由不同的盘片组成，每个盘片的上下面都可以读写。

磁道的形状是圆环，越靠近里面磁道号越小，中央的地区被称为启停区，不存储数据。

扇区包含了 一个磁道 的一部分。

柱面由不同及记录面上相同磁道号的磁道所形成。

磁记录原理

原理：磁头和磁性介质相对运动时，通过电磁转换完成读写。

编码方式：按照某种方案（规律），把一连串的二进制信息变换为存储介质中的一个磁化翻转状态序列，并使读写电路容易、可靠的转换。

磁记录方式 ：调频制（$FM$）和改进型调频制（$MFM$），归零制 ($RZ$)、不归零制 ($NRZ$)、调相制 ($PM$) 等多种类型。

归零制的特点：不论某存储单元的代码是 0 或是 1，在记录下一个信息之前记录电流要恢复到零电流。在给磁头线圈送入的脉冲电流中，正脉冲表示 1，负脉冲表示 0.

不归零制的特点：磁头线圈上始终有电流，不是正向电流就是反向电流，正向电流代表 1，反向电流代表 0，可以减少反转次数。

调相制记录方式的特点：在—个磁化元的中间位置，利用电流相位的变化实现写“1”或者写“0”，所以通过磁头中的电流方向一定要改变一次，即在一个周期内改变，若表示 1 则从高电平到低电平。

调频制的特点：记录 1 时在一个周期中和结束翻转一次，记录 0 则只在周期结束时翻转；

改进型调频制：记录 1 和调频制一致，只有记录连续 0 时才在周期结束时翻转。

性能指标

记录密度：单位面积的盘片能记录的二进制信息量。

格式化磁盘容量：按照某种特定的记录格式所能存储的信息总量，一般比非格式化磁盘容量小。

非格式化磁盘容量：磁记录表面可以利用的磁化单元总数。

平均存取时间：由 寻道时间（磁头移动到目标磁道）、旋转延迟时间（磁头定位到扇区） 和 传输时间（传输数据） 构成。

数据传输率：单位时间内向主机传送的字节数。

磁盘地址

主机向磁盘控制器发送寻址信息，磁盘的地址由 驱动器号、柱面（磁道）号、盘面号、扇区号构成。

工作过程

寻址 、读盘 、写盘，每个操作对应了一个控制字，工作时先取控制字，再执行控制字。

RAID （独立冗余磁盘阵列）

将多个独立的物理磁盘组成一个独立的逻辑盘，数据在物理盘上分割交叉存储，并行访问，存储性能更好。

RAID 0：无冗余和校验，将连续的多个数据块交替存放在不同物理磁盘中，空间大速度快，但无容错

RAID 1：镜像，即在不同的物理磁盘中存相同的数据，提高容错能力

RAID 2：纠错海明码，将数据以 $bit$ 为单位进行分割，每次读写需要全组磁盘联动，不能实现并发 $I/O$；校验盘的数量太多

RAID 3：位交叉奇偶校验，只需要一块检验盘，主轴同步才能发挥最大性能，不能实现并发

RAID 4：块交叉奇偶校验，需要额外的一个组，有校验盘争用的问题

RAID 5：无独立校验的奇偶校验，至少需要三个硬盘，将校验盘分布在每组中的不同位置中，是目前采用最多最流行的方式，可以实现并发

RAID 6：双冗余度，在 $RAID\ 5$ 的基础上多加了一块校验盘，使用一个方程式来计算新的校验数据，能够保证在同时损坏两块盘的情况下，恢复丢失的数据，同时速度不必 $RAID\ 5$ 慢很多。

固态硬盘（SSD）

基于闪存技术的存储器，与 $U$ 盘没有本质上差别，只是容量大性能好。

一个 $SSD$ 由多个 闪存芯片 和 闪存翻译层 组成，闪存翻译层代替传统磁盘中的机械驱动器，负责将来自 $CPU$ 的读写请求翻译为底层物理设备的读写控制信号。

通常一个闪存由一些块组成，每个块由一些页组成，一个页一般是 $512B -4KB$，每块一般由 $32-128$ 个块，这样块大小为 $16KB-512KB$.

数据 以页为读写单位，只有在页所属的块整个被擦除之后才能写这一页，块的寿命大概是 $10$ 万次。

随机写很慢，一是因为擦除块很慢，属于毫秒级别，二是如果写操作试图修改一个包含已有数据的页，那么该块中的所有数据都必须被移动到另一个新块中，才能完成修改。

$SSD$ 由半导体存储器构成，没有移动的部件，因此随机访问块，没有机械噪声和震动，能耗低，抗震性好，安全性高。但是反复写后闪存块会磨损，闪存翻译层中存在平均磨损的逻辑将擦属平均分布在所有块上来最大化每个块的寿命。

高速缓冲存储器

程序访问的局部性原理

时间局部性：未来要用到的信息很可能是现在正在使用的信息。

空间局部性：未来要用到的信息很可能与现在正在使用的信息在存储空间上是邻近的。

基本原理

为了便于与主存交换信息，$Cache$ 和主存都被划分为相等大小的块；因此有 $Cache$ 的主存系统都采用多体交叉存储器，其同时于 $CPU$ 和 $Cache$ 相连。

info

$Cache$ 块又称为 $Cache$ 行。

$CPU$ 发出读请求时，若地址在 $Cache$ 中，称为 Cache 命中 就将此地址转换为 $Cache$ 地址，直接对 $Cache$ 进行读。

info

某些计算机中也采用同时访问 $Cache$ 和主存，若 $Cache$ 命中，则主存访问中止，否则访问主存替换 $Cache$.

$Cache$ 不命中时，则仍需访问主存，同时把该字所在的块调入 $Cache$. 若 $Cache$ 已满，则需要某些替换规则来决定将什么块替换出去。

caution

$CPU$ 与 $Cache$ 间交换单位为字，$Cache$ 与主存间交换单位为块。

若 $Cache$ 命中后发现 $Cache$ 中和主存中的内容存在不一致，则需要一定的写策略处理。

映射方式

地址映射 是将主存地址空间映射到 $Cache$ 地址空间，$Cache$ 中需要为每块添加一个有效位，指明内容是否有效，同时也要将标记存下，来确定该块来自与主存的哪个位置，而全相联映射的标记则是唯一的。

caution

标记记录了主存当中的哪个块在 $Cache$ 中，其不一定是唯一的，如直接映射中不同的块可能拥有相同的标记，但是相同标记下的块与 $Cache$ 块一一对应；只有全相联映射的标记唯一。

实际上 $Cache$ 块号/组号就相当于一种标记，而全相联没有，就导致其知道内容存在，但是无法定位，因此需要使用 按内容寻址 的相联存储器，或是单独用表存储标记和地址的映射。

全相联映射

任意映射，除了块内地址全是标记位。

全相联映射的地址组成如下

[    主存块号    ][   块内地址   ]

目录表中额外存储了对应主存块号所对应的 $Cache$ 块号，因此其 $Cache$ 地址是

[  Cache块号  ][   块内地址   ]

优点：冲突概率低、命中率高、空间利用率高。

缺点：标记位太长，比较速度慢，实现成本高通常需要昂贵的 按内容寻址 的相联存储器进行地址映射，$Cache$ 太大会导致查表速度满。

直接映射

取模法，Cache 行号 $=$ 主存块号 $\%$ Cache 总行数，这样主存中每一块和 Cache 中存在 唯一对应，因此也 无需使用页面替换算法。

直接映射的目录表存储的是对应 $Cache$ 行对应的主存区号（主存块号除以行数向下取整），查找时先通过块号定位到目录表的位置，再判断目录表中的所存储的主存区号和当前要查找的主存区号是否相同，以及有效位是否为 $1$，若相同可以直接从 $Cache$ 的对应块号（行号）取出数据。

直接映射的地址组成如下

[区号][  块号 ][   块内地址   ]

$Cache$ 地址实际上就是

[  块号 ][   块内地址   ]

优点：硬件简单，访问速度快，因为无需地址变换。

缺点：冲突概率高，$Cache$ 空间利用率低。

组相联映射

将 $Cache$ 行分为几个 大小相同 的组，每个主存块可以装入固定的组中的任意一行，即组间采用直接映射、组内采用全相联映射。

warning

也有的教材是组间全相联、组内直接映射。

$Cache$ 组号 $=$ 主存块号 $\%$ $Cache$ 组数。

路数越大，即每一组内的 $Cache$ 行数量越多（越接近全相联），发成冲突的概率就越低，但是相联比较电路也越复杂。

查找时通过组号确定所属目录表的哪个组，再确定有效位和主存区号和组内快号是否在其中，得到对应的 $Cache$ 组内块号。

地址构成为

[区号][组号][组内块号][块内地址]

$Cache$ 地址为

[组号][Cache 组内块号][块内地址]

替换算法

caution

全相联或组相联映射才需要使用替换算法。

随机算法：随机替换一个，但根据程序访问的局部性原理，命中率可能比较低

先进先出（FIFO）：按照时间顺序，最早调入的最早调出，命中率同样可能低，没有考虑局部性原理

近期最少使用（LRU）：选择近期内最久没有访问的 $Cache$ 行，需要对每一个 $Cache$ 行设置一个计数器，计数位数和 $Cache$ 组的大小（取 $log$）有关，某些时候会出现 抖动 的情况，如计数位 $4$ 位，访问 $1,2,3,4,5,1,2,3,4,5\cdots$ 这样会导致命中率为 $0$.

最不经常使用（LFU）：每隔一段时间将被访问次数最少的行换出，与 $LRU$ 类型，但是在时间维度上的比较。

最佳替换算法（OPT）：先模拟一次执行，确定好最佳的替换算法。

Cache 写策略

tip

以下是 $Cache$ 写命中。

全写法（写直通法、write through）

1. $Cache$ 命中时，同时把数据写入 $Cache$ 和主存；
2. 替换时，不比写回主存，直接覆盖 $Cache$ 行即可。

方法简单有效，能随时保证主存数据的正确，但是增加了访存次数。

info

为了减少写回造成的时间损耗，在 Cache 和主存之间添加了一个 写缓冲，其是一个 $FIFO$ 队列，但若出现频繁写时，会是写缓冲饱和溢出。

多级 $Cache$ 可以避免这个问题。

回写法（write-back）

1. 命中时只将数据写入 $Cache$；
2. 替换时，将块写回主存。

减少了访存次数，但存在不一致的隐患。 每个 $Cache$ 行需要设置一个 修改位（脏位），表示是否被修改过，若为 $0$, 表示未修改过，则无需写回。

tip

以下是 $Cache$ 写不命中。

写分配 （write-allocate）

1. 加载主存中的块到 $Cache$ 中；
2. 更新该 $Cache$ 块。

非写分配（non-write-allocate）

1. 只写入主存而不写入 $Cache$.

info

非写分配通常和全写法合用，写分配通常和回写法合用。

随着技术的发展（指令预取等），需要将指令 $Cache$ 和数据 $Cache$ 分开设计，因此有了分离 $Cache$. 现代计算机还设立多级 $Cache$，指令数据分离 $Cache$ 一般在 $L1$ 级，通常为写分配和回写法合用。

Cache 一致性协议 MESI

tip

在多核计算机中，需要一定的协议保持 $Cache$ 的一致性，因此不同 $CPU$ 的 $Cache$ 之间有一条单独的总线用于传递协议。

$MESI$ 是以下四种情况的缩写：

状态	描述	行为
$Modified$	该 Cache line 有效，且数据被修改和主存中的不同	监听所有对相应内存的操作，其他缓存只有在本 Cache line 写回后才能修改对应的内存
$Exclusive$	有效，数据与主存中一致，且只存在与当前缓存行中，	监听所有对相应内存的操作，一旦有修改，则更改状态为 $S$
$Shared$	有效一致，但是同时存在与其他缓存行中	监听所有对相应内存的操作，一旦有修改，更改状态为 $I$
$Invalid$	数据无效

针对不同的情况，$Cache$ 使用不同的写策略。

实际上类似一种对 $Cache$ 行进行加锁。

虚拟存储器

参考

主存和辅存共同构成了虚拟存储器，在硬件和软件系统的管理下工作，并且对程序员是 透明的，其拥有主存的速度和辅存的容量；一般由软件实现（操作系统）。

基本概念

虚拟存储器将主存和辅存统一编址，用户可以自由编程而不必关心主存实际容量和存放地址。

用户编程所能涉及的地址称为 虚地址 或者 逻辑地址 ，虚地址对应的存储空间称为虚拟空间或程序空间，而实际主存地址称为 实地址 或 物理地址。

$CPU$ 使用虚地址时，通过辅助硬件找出虚地址和实地址间的 映射关系 ，并判断对应内容是否已装入主存：

1. 若在主存中则 变换地址 使 $CPU$ 直接进行访问；
2. 若不在主存中，则把包含该字的 页面 或 段 装入主存再由 $CPU$ 访问；
3. 装入过程中若主存已满，则需使用 替换算法 置换主存中的页面。

tip

其实就是类似于 $Cache$，用不到的页面暂时存入辅存中，而主存和辅存之间的访问代价很大，需要保证命中率，因此采用 全相联映射 和 回写法。

页式虚拟存储器

tip

与 $Cache$ 类似，页式虚拟存储器以 页为基本单位，主存和虚存以同样大小的页面进行划分。 主存的页被称为 实页、页框，虚存的页被称为 虚页。

页表

页表是存放在主存中对应虚页号和实页号的表。

页表中每一项由 有效位（装入位，为 1 表示已从外存调入主存）、脏位（修改位）、 引用位（使用位，用于配合替换策略使用） 和 物理页地址 .

物理地址：通过虚页号找到对应页表项，将物理页号和虚拟地址地位拼接得到完成物理地址。

优点： 页面长度固定、页表简单、调入方便。

缺点：由于程序不能刚好利用完所占页面，最后一页总是有浪费，并且页不是逻辑上独立的实体，所以处理保护和共享都不及段式虚拟存储器方便。

多级页表

单级分页的缺陷

页面的大小的往往很小，只有 $4K$，要映射满整个虚拟内存需要大量的页表项，并且每个进程都会维护一个很大的页表，一方面导致其占用大量空间，导致了查询效率降低。

在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万 （2^20） 个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。

这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。

那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。

多级页表将页号进行拆分，一级页表存储一级页号及其对应二级页表地址，依次类推直到最后一级页表才存储物理页号，现代 Linux 中通常使用四级页表；其利用了页表号的共同前缀来减少总页表的数据大小，另外单级页表中可能存在很多空的页表项，而在多级页表中可以将数据大小减小很多。

快表（TLB）

tip

多级页表虽然解决了存储数据的问题，但是其增加了查表次数，降低了虚拟地址到物理地址的转换速度，因此根据程序的局部性原理，可以使用快表，快表是 $CPU$ 和页表之间的 $Cache$，因此页表也被成为慢表。

类似地，也可以同时访问快表和页表，快表命中则停止访问页表，否则从页表中查找。

快表通常采用全相联或者组相联的方式，每个 $TLB$ 项由页表项加上一个 $TLB$ 标记字段组成，该标记指明页表项取对应哪个虚页号，

段式虚拟存储器

段表项由段号、装入位、段起点和段长等信息组成；每个程序段都是从 $0$ 开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。

地址构成为

[用户号（程序号）][段号][段内偏移]

通过用户哈在 CPU 中的 段表基址寄存器 中查找其在主存中的地址。

优点：段具有逻辑独立性，易于编译、管理、修改和保护，也便于多段程序共享；程序动态连接和调度容易；

缺点：段长度可变，分配空间不方便，容易在段间留下碎片，造成浪费；地址变换花费时间长，需要两次加法，段表太大；对辅存管理困难。

段页式虚拟存储器

将程序按照逻辑结构分段，每段在划分为固定大小的页，主存空间同样，页仍然作为基本单位，每个程序对应一个段表，每段对应一个页表，段长必须是页长的整数倍，段起点必须是某页的起点。

虚地址分为段号、段内页号和页内地址。

优点：兼具页式和段式虚拟存储器的优点，可以按段实现共享和保护，提高了内存的利用率。

缺点：需要查表两次，开销大。

虚拟存储器和 Cache 的比较

相同

1. 最终目标都是提高系统性能；
2. 都将数据划分为小数据块，并作为基本单位，虚存系统的块更大；
3. 都有地址映射、替换算法、更新策略等问题；
4. 依靠程序的局部性原理。 不同
5. $Cache$ 主要解决系统速度，虚拟存储器解决主存容量；
6. $Cache$ 全由硬件实现，对所有程序员透明，而虚拟存储器由 $OS$ 和硬件共同实现，是逻辑上的存储器，对系统程序员不透明；
7. $CPU$ 速度约为 $Cache$ 的 10 倍，而主存速度为硬盘的 $100$ 倍，虚拟存储器不命中的影响大；
8. $Cache$ 可以直接和 $CPU$ 通信。