1.存储器概述

1.1.存储器分类

1.1.1.按在计算机中的作用（层次）分类

主存储器：简称主存，又称内存；用来存放计算机运行期间所需的大量程序和数据；CPU 可以直接对其进行访问，也可以和高速缓冲存储器（Cache）及辅助存储器交换数据；特点是容量较小，存储速度较快，造价高。
辅助存储器：简称辅存，又称外存；是主存储器的后援存储器，用来存放当前暂时不用的程序和数据，以及一些需要永久性保存的信息，它不能与 CPU 直接交换信息；特点是容量极大，存储速度较慢，造价低。
高速缓冲存储器：简称 Cache；它位于主存和 CPU 之间，用来存放正在执行的程序段和数据，以便 CPU 能够高速地使用它们；Cache 的读取速度可以和 CPU 相匹配，但存储容量小，价格高，目前会被集成在 CPU 当中。

1.1.2.按照存储介质分类

磁表面存储器：如磁盘、磁带等。
磁心存储器半导体存储器：如 MOS 型存储器、双极型存储器。
光存储器：如光盘。

1.1.3.按存储方式分类

随机存储器（RAM）：存储器的任何一个存储单元的内容都可以随机存取，而且存取时间与存储单元的物理位置无关；其优点是读写方便，使用灵活，主要用作主存或高速缓冲存储器；RAM 又分为静态 RAM（以触发器原理寄存信息）和动态 RAM（以电容充电原理寄存信息）。
只读存储器（ROM）：存储器的内容只能随机读出而不能写入；信息一旦写入存储器就固定不变，即使断电内容也不会丢失。因此通常用它存放固定不变的程序，常数和汉字字库，甚至用于操作系统的固化。它与随机存储器可以共同作为主存的一部分，统一构成主存的地址域。
串行访问存储器：对存储单元进行 I/O 操作时，需按其物理位置的先后顺序寻址，包括顺序存取存储器（如磁带）与直接存取存储器（如磁盘）。

注意：

顺序存储寄存器的内容只能按照某种顺序存取，存取时间的长短与信息在存储体的物理位置有关，其特点是存储速度慢，例如：磁带；
直接存取存储器既不像 RAM 那样随机访问任何一个存储单元，又不像顺序存取存储器那样完全按照顺序存取，而是介于两者之间，存取信息是通常先寻找整个存储器中的某个小区域，再在小区域内顺序查找，例如：机械硬盘。

1.2.4.按信息的可保存性分类

易失性存储器：断电后，存储的信息会消失，如 RAM；
非易失性存储器：断电后，存储的信息仍然会保持，如 ROM。

注意：

破坏性读出：某个存储单元所存储的信息被读出时，原存储信息被破坏；具有破坏性读出性能的存储器，每次读出操作后，必须紧接一个再生操作，以便恢复被破坏的信息，例如：DRAM（栅极电容）。
非破坏性读出某个存储单元所存储的信息被读出时，原存储信息不被破坏，例如：SRAM（双稳态触发器）。

1.2.多级存储系统

多级存储系统：为了缓解存储系统容量、速度和成本这三者之间的矛盾。在计算机系统中，存储器系统通常会采用多级结构，如下图所示，从上至下：

价格越来越低。
速度越来越慢。
容量越来越大。
CPU 访问的频度越来越低。

实际上，存储系统的层次结构主要体现在 “Cache - 主存” 和 “主存 - 辅存” 这两层：

“Cache - 主存”：主要解决 CPU 和主存速度不匹配的问题。
“主存 - 辅存”：主要解决存储系统的容量问题。

在多级存储系统中：

Cache、主存可以和 CPU 直接交换信息。
辅存则要通过主存和 CPU 交换信息。
主存与 CPU、Cache、辅存都能交换信息。

多级存储系统的核心思想是：让上一层的存储器作为下一层存储器的高速缓存。

“Cache - 主存” 层速度接近于 Cache，容量和价位却接近于主存。
“主存 - 辅存” 层速度接近于主存，容量和价位却接近于辅存。

另外注意：

主存和 Cache 之间的数据调动是由硬件自动完成的，对所有程序员透明。
主存和辅存之间的数据调动则是由硬件和操作系统共同完成的，对应用程序员是透明。

1.3.存储器性能指标

存储器有以下三个性能指标（相互制约），通过协调这三个指标，设计者尽可能地设计大容量、低成本和高速度的存储器系统。

存储容量。
单位成本。
存储速度。

1.3.1.存储容量

存储容量 = 存储字数 × 字长（如 1M×8 位）。

单位换算：1B(Byte，字节)=8b(bit，位)。
存储字数表示存储器的地址空间大小，字长表示一次存取操作的数据量。

1.3.2.单位成本

每位价格 = 总成本 ÷ 总容量。

1.3.3.存储速度

数据传输率 = 数据的宽度 ÷ 存储周期。

存取时间（ $T_{a} $）：是指从启动一次存储器操作到完成该操作所经历的时间，分为读出时间和写入时间。
存取周期 ( $ T_{m} $)：存取周期又称读写周期或访问周期。它是指存储器进行一次完整的读写操作所需的全部时间，即连续两次独立访问存储操作（读或写操作）之间所需的最小时间间隔。
主存带宽（ $ B_{M} $）: 主存宽度又称为数据传输率，表示每秒从主存进出信息的最大容量，单位为字 / 秒，字节 / 秒 (B/s) 或位 / 秒(b/s)。

2.主存储器

2.1.基本的半导体元件及原理

在 (计算机组成原理) 第一章计算机系统概述 - 计算机硬件组成 (存储器、运算器和控制器概述及计算机工作过程详解) 这篇文章中说到：一个存储器由存储体、MAR（地址寄存器）和 MDR（数据寄存器）构成，这三部分会在时序逻辑电路的控制下相互配合进行工作。

存储体是用来存放二进制数据的，它由多个存储单元构成，而存储单元又有存储元构成，下图就是一个存储元，由 MOS 管和电容实现。

MOS 管：可以理解为一种电控开关，输入电压达到 ** 某个阈值时，**MOS 管就可以接通。
电容：当产生电压差时就会充电，可以保存一定电荷。电容带电和不带电分别对应两种状态，也即二进制中的 0 和 1。

利用 MOS 管和电容可以进行如下操作：

读出二进制：假如电容有电，此时当 MOS 管接通时，电荷就可以顺着导线向 MOS 管右侧流动，当在该侧检测到电流时相当于输出了 1，反之则输出了 0 。
写入二进制：在 MOS 管右侧接入电压，然后导通 MOS 管，这样电流就会从右向左流动，此时电容一端接地，于是两块板子上有电压差，电荷就会被 “装载” 进去，接着再把 MOS 管断开，这样电荷就跑不出去了。

上述仅仅是一个存储元，如果把多个存储元按照一定方式连接，那么就能一次性读出或者写入多位数据，比如下图：

下图中红色导线连接了每个存储元的 MOS 管，因此如果给其加上电压，就意味着所有存储元的 MOS 管都可以被导通。
当 MOS 管导通后，电容里存储的电荷就可以顺着绿色的线导出 。

于是按照上述方式就可以读出一整行存储元所存储的数据信息，而这一行其实就是存储单元（也即一个存储字），多个存储单元组合便构成了存储体。

为什么存储器每次读写操作的单位是一个存储字：因为同属于一个存储字的存储元它们的 MOS 管一端接的都是同一根线。

2.2.存储器芯片的基本原理

读出和写入的功能有了，那么下一个问题就是如何决定我们要读或者写的具体是哪一个存储字呢，这就要涉及到译码器的概念了。

译码器：当给出 $n$ 位地址时，这 $n$ 位地址就会对应 $2^{n} $ 个存储单元（因为是地址是二进制），所以译码器会根据 MAR（它和 CPU 连接）里面给出的这几位地址，将其转化为某一条字选线的高电平信号。

例如：MAR 送过来的地址是000，对应十进制的 0，所以译码器会给第 0 根字选线一个高电平，此时第一个存储字对应的存储元件都会被选通。

如下，当第 0 根字选线被接通后，就可以通过数据线（也叫位线，绿色），把每一位的二进制信息传送到 MDR 当中，然后 CPU 会通过数据总线（宽度等于存储字长）从 MDR 当中取走这一存储字的数据。

为此，我们需要新增一个控制电路来控制 MAR、MDR 和译码器：

控制 MAR：当 CPU 通过地址总线把地址送入 MAR 时，由于使用的是电信号，而电信号容易紊乱，因此在 MAR 中电信号稳定之前，该地址不能被送入译码器当中。
控制 MDR：和 MAR 相同，稳定时才能输出。

另外，存储芯片还需要向外提供片选线，用 $ C $ $ S $（芯片选择信号）或 $ C $ $E $（芯片使能信号）表示（横线表示低电平有效）。

当然，控制电路还需要提供读控制线和写控制线：

$ W $$ E $：低电平时，表示正在进行写操作，也就是要把 MDR 里保存的数据把它输入到电容中。
$ O $$ E$：低电平时，进行读操作。
下图中读写控制线分为两根，也可以整合为一根， $ W $ $E $就表示低电平写，高电平读。

最后屏蔽内部实现细节后，存储器芯片会这样表示 ：

最后再次说明一下片选线的作用：下图是内存条，一个内存条由很多存储芯片组成（如果是 8G，那么每个存储芯片大概就是 1G），因此片选线就是为了操作指定的存储芯片。

同时上面原理图中讲到的每一根线其实就是对应了芯片的引脚。

$n$ 位地址就对应了 $2^{n} $ 个存储单元，因此总容量 = 存储单元个数 × 存储字长
有时我们会见到这样的描述，8×8 位的存储单元，比如 8K×8 位，就是 $2^{13}×8bit $

2.3.寻址

如下矩阵方格中每一个方格表示 8bit 的信息，每一行表示一个存储字，为 4B 大小，该矩阵共有 256 行，大小为 1KB

现代计算机通常是按照字节寻址的，因此 1 个小方格就对应 1 个地址，这里有 1K 个字节那么就有 1K 个地址。既然有 1K 个地址，那么根据之前叙述，应该就有 10 根地址线（ $2^{10} $）。

虽然是按照字节编址的，但还可以按照字、半字、双字等方式寻址：

按字节寻址：1K 个单元，每个单元 1B。
按字寻址：256 个单元，每个单元 4B。
按半字寻址：512 个单元，每个单元 2B。
按双字寻址：128 个单元，每个单元 8B。

位（bite）: 音译为“比特”，表示二进制位。位是计算机内部数据储存的最小单位，11010100是一个8位二进制数。

字节（byte）：一个字节等于8位，即1Byte=8bit。

字：一串数码作为一个整体来处理运算，被称为一个字，字的位数称为字长，一个字通常有若干个字节，例如286微机的字由2个字节组成，它的字长为16；486微机的字由4个字节组成，它的字长为32位机。计算机的字长决定了其CPU一次操作处理实际位数的多少，由此可见计算机的字长越大，其性能越优越。

3.SRAM芯片和DRAM芯片

本节会在上节的基础上，介绍两种重要的存储器芯片：DRAM 和 SRAM。

DRAM(Dynamic-Random- Access -Memory)：动态 DRAM，主要用于主存。
SRAM(Static- Random -Access -Memory)：静态 RAM，主要用于 Cache。

注意：DRAM 芯片已经过时了，现在主存通常采用 SDRAM（如 DDR3 和 DDR4）。

3.1.存储器元件不同导致的特性差异

上一节介绍的芯片实则就是 DRAM 芯片，主要被用于制作主存。其实 DRAM 芯片和 SRAM 芯片的核心区别点就在于他们的存储元制作材料不一样。

DRAM：使用栅极电容。
SRAM：使用双稳态触发器 。

3.1.1.栅极电容

栅极电容：当给字选择线一高电平时，MOS 管会接通，然后给数据线一高电平，由于电容一端接地，因此电容板之间产生电压差，于是电荷被 “写入” 电容。

1：表示电容内存储了电荷。
0：表示电容内未存储电荷。

在读出时，如果电容里面有电荷，那么当 MOS 管接通后，一定会在数据线位置检测到电流信号，反之则不会，分别对应数据 1 和数据 0。

3.1.2.双稳态触发器

关于双稳态触发器具体原理请点击链接跳转：双稳态触发器。

双稳态触发器：是一种具有记忆功能的逻辑单元电路，它能储存一位二进制码。它有两个稳定的工作状态，在外加信号触发下电路可从一种稳定的工作状态转换到另一种稳定的工作状态。

相比栅极电容，双稳态触发器有两根数据线。当给字选择线一高电平信号后：

如果里面存储的是 1，那么将会在 BLX 这条线上输出低电平信号（左边没有）。
如果存储的是 0，那么将会在 BL 这条线上输出低电平信号（右边没有）。

同时在写入时：

如果要写入数据 0：那么只需要给 BL 一低电平信号，同时给 BLX 一高电平信号。
如果要写入数据 1，那么只需要给 BL 一高电平信号，同时给 BLX 一低电平信号。

3.1.3.SRAM 和 DRAM 对比

关于读写速度：

DRAM 使用栅极电容的充放电来完成读写操作：电容的物理特性就决定了其充放电是一种破坏性读出，读出后应该有重写操作，也就是需要重新充电，也称之为再生，读写速度较慢。
SRAM 使用双稳态触发器：在读写数据时，触发器的状态是保持稳定的，因此属于非破坏性读出，无需进行重写操作，读写速度也就更快。

2：关于成本和功耗

DRAM：单个存储元制造成本低，集成度高，功耗低。
SRAM：单个存储元制造成本更高，集成度低，功耗大。

3：其它区别

类型 / 特点	SRAM（静态 RAM）	DRAM（动态 RAM）
存储原理	触发器	电容
是否是破坏性读出	否	是
是否需要重写	否	是
运行速度	快	慢
集成度	低	高
发热量	大	小
成本	高	低
是否是易失性存储器	是	是
是否需要 “刷新”	否	是
送行列地址	同时送	分两次
用途	Cache	主存

刷新：电容里面的电荷不能永久存在，一般只能维持 2ms，因此即使不断电，2ms 后信息也会丢失，因此对于 DRAM 需要 “刷新”，也就是再充电；而 SRAM 只要不断电，触发器的状态就不会改变。

3.2.DRAM 的刷新

3.2.1.译码器需要使用行列地址

上一节说到了译码器的作用：把某一位的地址，转化为相应的选通线的高电平信号， $n$位地址就对应 $2^{n} $ 个选通线。

当地址数变多时，选通线数量级将会非常大，例如仅 20 个地址就需要 $ 2^{20}=1 048 576 $ 根选通线，这已接近百万了。

解决方法就是：将原来的单纯的一维的地址，改变为行列地址，也就是一个矩阵，分别交给行地址译码器和列地址译码器管理，这样的话每个译码器只需处理一半的地址信息，也就是 1024 根选通线。

例如地址0000 0000，如果采用之前的方案，那么经过译码器译码后，第 0 根选通线会被选中。

而如果采用行列译码器的方案，地址0000 0000的低四位将会交给列地址译码器，高四位将会交给行地址译码，每个存储单元只有列选通线和行选通线同时被选中时才能被选中，因此(1,1)位置的存储单元此时会被选中。

对于八位地址，原本需要使用 $2^{8}=256 $ 根选通线，而现在只需要$2^{4}+2^{4}=16+16=32$根选通线，所以使用行列地址的本质就是要减少选通线数量。

3.2.2.分散刷新、集中刷新和异步刷新

3.2.2.1.DRAM 刷新

关于 DRAM 的刷新，这里有 4 个问题需要回答：

多久刷新一次：一般为 2ms。
每次刷新多少存储单元：以行为单位，每次刷新一行存储单元。
如何刷新：有硬件支持，读出一行的信息后重新写入，占用 1 个读写周期。
什么时候刷新：分散刷新、集中刷新和异步刷新（接下来介绍）。

3.2.2.2.分散刷新、集中刷新和异步刷新特点

假设 DRAM 内部结构排列形式为 128×128，存储周期为 0.5 $us $，电容最多坚持 2ms，因此对应 2ms/0.5 $us $=4000 个周期，有 128 行，刷新每一行都需要 0.5 $us $，同时注意以下内容：

刷新对 CPU 是透明的，也即刷新不依赖于外部的访问。
DRAM 刷新单位是行，因此刷新操作时仅需要行地址。
刷新操作类似于读操作，但又有所不同：刷新操作仅给栅极电容补充电荷，不需要信息输出，另外刷新时不需要进行选片，即整个存储器中的所有芯片同时被刷新。

一共有分散刷新、集中刷新和异步刷新这三种方式：

分散刷新：把对每行的刷新分散到各个工作周期当中，这样，一个存储器的系统工作周期就分为了两个部分，前半部分用于正常读写或保持；后半部分用于刷新某一行。这种刷新方式增加了系统的存取周期，增加为 1 $us $。
集中刷新：是指利用一段固定的时间，依次对存储器的所有行进行逐一再生，存储周期不变，在刷新期间内会停止对存储器的访问，因此称之为 “死时间”，又称访存 “死区” 。
异步刷新：它是前两种刷新方式的结合。具体做法是用刷新周期除以行数，得到两次刷新操作之间的时间间隔 t（2ms/128=15.6 $us $），接着利用逻辑电路每隔该时间间隔 t(15.6 $us $) 产生一次刷新请求，因此每 15.6 $us $ 内会有 0.5 $us $ 的死时间。所以死时间会分散在整个过程中，而且可以在译码阶段刷新。

3.2.2.3.分散刷新、集中刷新和异步刷新优缺点

集中刷新：

优点：读写操作不受刷新工作的影响，因此系统的存取速度较高。
缺点：是在集中刷新期间（死区）不能访问存储器。

分散刷新：

优点：是没有死区。
缺点：是加长了系统的存取周期降低了整体速度。

异步刷新：综合最优。

可以避免使 CPU 连续等待过长的时间，而且减少了刷新次数，从根本上提高了整机的工作效率；
同时如果将刷新安排在不需要访问存储器的译码阶段，则既不会加长存取周期，又不会产生 “死时间”，这是分散刷新的方式的发展，也称之为 “透明刷新”。

3.3.DRAM 的地址线复用技术

前面说过 SRAM 需要同时送行列地址，也即行列地址信息会同时丢给行译码器和列译码器。

而 DRAM 由于用于主存，所以容量可能较大，因此地址线可能也会更多，所以为了使地址线电路变得更简单，会采用一种地址线的复用技术，也就是分两次送。

这种技术可以使行列地址分两次前后进行传送，传送时只需要一半地址，先传送至缓冲区，再传送给译码器即可，这样会使地址线更少。

4.只读存储器

4.1.只读存储器（ROM）特点

只读存储器（ROM）：前文说到的 SRAM 和 DRAM 都属于 RAM 芯片，RAM 芯片属于数据易失性芯片，断电后数据将会消失。但很多情况下需要对数据进行长期保存，所以就要使用到 ROM 芯片。它有两个显著的特点：

结构简单，所以位密度比可读存储器的高。
具有非易失性，可靠性高。

4.2.ROM 的类型

掩模式只读存储器（MROM）：MROM 的内容由半导体制造厂家按用户提出的要求在芯片的生产过程中直接写入，写入以后任何人无法改变其内容。优点是可靠性高、集成度高、价格便宜；缺点则是灵活性差。
一次可编程只读存储器（PROM）：PROM 是可以实现一次性编程的只读存储器，允许用户利用专门的设备写入自己的程序，一旦写入，内容无法改变。
可擦除可编程只读存储器（EPROM）：EPROM 可以让用户利用编程器写入信息，而且内容也可以进行多次改写。如果需要修改 EPROM 内容，则先将其全部内容擦除，然后再编程。EPROM 又可以分为紫外线擦除（UVEPROM）和电擦除（$E ^{2} PROM$）。EPROM 虽然既可以读又可以写，但是它不能取代 RAM，因为 EPROM 的编程次数有限，且写入时间过长。
闪存存储器（Flash Memory）：Flash Memory 是在 EPROM 与 $E ^{2} PROM$ 的基础上发展起来的，其主要特点是即可以在不加电的情况下长期保存信息，又能在线进行快速擦除和重写。需要注意的是闪存需要先擦除再写入，因此闪存的写速度要比读速度更慢。
固态硬盘（SSD）：基于闪存，由控制单元和存储单元组成。保留了闪存长期保存信息，快速擦除与重写的特性。对比传统的硬盘也具有读写速度快，功耗低，其缺点就是价格高。

4.3.计算机内的重要 BIOS

BIOS：是计算机主板一个非常重要的 ROM 芯片，它存储了 “自举装入程序”，负责引导装入操作系统，进行开机操作。

5.主存储器和CPU的连接

现代计算机中，MAR 和 MDR 通常集成在 CPU 的内部，而存储芯片内的仅是一个普通的寄存器。主存储器与 CPU 的连接示意图如下：

主存储器通过数据总线、地址总线和控制总线与 CPU 连接。
数据总线的位数与工作频率的乘积正比于数据传输率。
地址总线的位数决定了可寻址的最大内存空间。
控制总线（读或写）指出总线周期的类型和本次输入输出操作完成的时刻。

5.1.单块存储芯片与 CPU 的连接

下图是前文中讲到过的一单个存储芯片的内部构造（2.1.基本的半导体元件及原理），它和 CPU 通过以下总线连接（具体过程会在 “二：多块存储芯片与 CPU 的连接 -（1）位扩展 -①：单个连接” 中进行描述）。

数据总线（绿色线）：用于传送数据。
地址总线（红色线）：用于传送地址。
控制总线（橙色线）：用于发出控制信号。

5.2.多块存储芯片与 CPU 的连接

上图展示的只是一个 8×8 位的存储芯片，仅能存储 8B 的数据，所以会存在以下问题：

问题一：存储字长为 8 位，也即 CPU 一次只能读或写 8 位，而现代计算机数据总线宽度至少是 64 位，严重不匹配。因此问题在于如何增加存储字长，使 CPU 一次能读或写多位数据 （对应位扩展）。
问题二：只有 8 个地址，地址数目太少。因此问题在于如何扩展地址空间，使地址数目变多（对应字扩展）。

这里，为了后续描述方便，为一块存储芯片的输入输出信号进行命名：

地址线：有可能输入多位的地址，因此地址用$A_{n} $表示， $n$从 0 开始，表示从地址低位到地址高位
数据线：用 $ D_{n} $表示， $n$从 0 开始，表示从数据低位到数据高位。
片选线：片选信号通常用 $CS $ 或 $ CE $ 表示，其中的横线表示低电平有效，高电平无效。
读写控制线：该信号用 $WE $ 或 $ WR $ 表示，其中的横线表示低电平写，高电平读。（注意有些地方也可能将读写分开，分别为 $OE $ 或 $ WE $，低电平表示有效，高电平无效）。

5.2.1.位扩展

5.2.1.1.单个连接

下图是买来的一块 8K×1 位的存储芯片。

该存储芯片有 8K 个存储单元，由于 $ 2^{13}=8192 $，这意味着至少需要 13 根地址线才能表示这么多地址，因此该存储芯片要向外暴露出 13 个地址引脚，然后 CPU 会把它想要访问的地址通过地址总线送过来。

左下角的 “ $W E $” 表示Write Enable，上方没有横线，那么就表示低电平读、高电平写。

上图显示 CPU 一次是可以读写 8 位数据的，但是由于存储芯片字长的限制，所以一次最多只能进行一位，这导致数据总线没有被充分利用。

还有一个片选线 $C S$ ，表示高电平有效，这里暂时先给一个高电平，具体作用后面会说。

至此，单个芯片的连接已经完成了。但是由于存储字长为 1，一次只能读写一位数据，所以数据总线利用率很差，因此在这种情况下可以进行位扩展。

5.2.1.2.多个连接

接着又买到了一个和上面相同规格的存储芯片。

对于地址线，我们从刚才连接的每一个地址线分别分流出一根线连接到该存储芯片的引脚上，这意味着一个地址可以同时选中两个存储单元。

对于读写控制线也是这样连接，这意味着它们是同时读或者同时写。

对于数据线，该存储芯片的引脚可以连接在 CPU 的$D_{1} $位置。

最后，也给片选$CS $ 线给一高电平。

至此，两块芯片连接完成。现在，从整体上看存储字长被扩展为了 2 位，也即可以同时读或写两位的信息了。

最后，再买来 6 块芯片，连接好即可。

每块芯片都有 8 个存储单元，CPU 发出的 $A_{0}$$A_{12} $的这 13 位的地址信息会同时送给 8 片存储芯片。

5.2.2.字扩展

5.2.2.1.线选法

如下是买来的一块 8K×8 位的存储芯片。

单个芯片的连接过程同 “5.2.1.1.单个连接”，可自行研究。

这个芯片明显不需要进行位扩展。但其问题在于：此 CPU 的寻址能力很大，可以达到$ 2^{16} $，但却只利用了其中一部分，有 3 位没有被利用，所以在这情况下就要采用字扩展的方式来解决问题。

再买来一块相同规格的存储芯片，先采用之前的位扩展的规则进行连接，如下图：

可以发现采用这种方式连接将会产生很大的问题：两块芯片会被同时选中，比如读数据时，两块存储芯片的 8 位数据会同时传给 CPU，因此存在数据冲突。

解决方法就在于片选信号$CS $。现在，将 $ A_{13}$连接到左边存储芯片的片选信号$CS $ 上，将 $ A_{14}$连接到右边存储芯片的片选信号$CS $ 上。由于是高电平有效，因此当地址位为 1 时表示该存储芯片工作。

$ A_{13}$和 $ A_{14}$只有两位，故取值只会有四种情况：01、10、11、00。

如果是 01（注意 $ A_{14}$是 0 $ A_{13}$是 1， $ A_{14}$是地址高位）：此时左边芯片工作，右边片不工作。因此现在 CPU 提供的这 13 位的地址只会读取左边存储芯片对应的 8 位的数据 。
如果是 10：此时右边芯片工作，左边芯片不工作；因此现在 CPU 提供的这 13 位的地址只会读取右边存储芯片对应的 8 位的数据 。
如果是 11 或 00：这种情况又会出现刚才的矛盾，因此不能出现 。

这样操作后，芯片所表示的地址范围会发生改变：

左边芯片：010 0000 0000 0000~011 1111 1111 1111。
右边芯片：100 0000 0000 0000~101 1111 1111 1111。

这种连接方法称之为 “线选法”，其缺点在于以 00 和 11 开头的地址是不能用的。

注意：不是仅有两个地址，是以 00 和 11 开头的所有地址均不可用，其数量是相当多的。

5.2.2.2.译码片选法

译码片选法会在线选法的基础上做一定改进，只需要加入一个非门。

以 $ A_{13}$为例，让它分别连接左边芯片和右边芯片的片选信号$CS $ 上，但是在第二个线路中加入一个非门，这样当 $ A_{13}$为 1 时，左边会被选中，右边由于非门的取反作用会变为不工作。

这样的话，左边芯片的地址范围就为：10 0000 0000 0000~11 1111 1111 1111；右边的则为：00 0000 0000 0000 ~01 1111 1111 1111，整个主存地址空间是连续的。

上面用到的非门叫做 “1-2 译码器”，这种方法叫做译码片选法，如果 CPU 有 n 条多余的片选线，那么他可以对应 $2^{n} $ 个片选信号。

译码器编号：1-2 译码器是输入 1 个对应 2 个，2-4 译码器是输入两个对应 4 个，以此类推。

讲完上面的操作，现在可以使用真正使用字扩展了。这里采用一个 2,4 译码器，也就是输入两个信号，输出 4 个信号，接着加入 4 个 8×8 位的存储芯片，每块存储芯片都会接受 CPU 发过来的低 13 位的地址信息。

注意上方图片中，每个存储芯片所有的地址信息都是直接来自于 CPU 的，不是从左边相邻的芯片传递过来的，这里是这样画只是为了整洁。
在电路图中，当需要表示低电平有效时，通常会在上面画一个 “小圆”。

当 $ A_{13}$， $ A_{14}$为均为 0 时，就表示第一根线为 1，剩余为 0，但是经过译码器后，由于是取反，所以第一根为 0，其余为 1，而正好 0 表示存储芯片工作，所以这种情况第一个存储芯片工作，其余不工作。

类似的，当 $ A_{13}$为 1， $ A_{14}$为 0 时，就表示第二根线为 1，剩余为 0，但是经过译码器后，由于是取反，所以第二根为 0，其余为 1，而正好 0 表示存储芯片工作，所以这种情况就表示第二个存储芯片工作，其余不工作。

因此：

要访问第一块存储芯片，就要保证 $ A_{13}$为 0， $ A_{14}$为 0，此时地址范围为：000 0000 0000 0000 到 001 1111 1111 1111
要访问第二块存储芯片，就要保证 $ A_{13}$为 1， $ A_{14}$为 0，此时地址范围为：010 0000 0000 0000 到 011 1111 1111 1111
要访问第三块存储芯片，就要保证 $ A_{13}$为 0， $ A_{14}$为 1，此时地址范围为：100 0000 0000 0000 到 101 1111 1111 1111
要访问第四块存储芯片，就要保证 $ A_{13}$为 1， $ A_{14}$为 1，此时地址范围为：110 0000 0000 0000 到 111 1111 1111 1111

所以这样的操作就能保证主存地址范围从全 0 到全 1，而且是连续的。

另外还需要注意的是，考试时可能不会是连续的 $ A_{13}$和 $ A_{14}$，有可能是 $ A_{13}$和 $ A_{15}$，但是无论怎么样，只要不选中，就不影响选片操作，是 0 是 1 不用管，只看选中的那几位 。

最后，这里的 $ A_{15}$没有被启用，如果要使用的话那么就需要一个 3-8 译码器，然后再增加 4 个相同规格的存储芯片即可。

5.2.2.3.字位同时扩展

位扩展可以使得存储芯片的字长变得更长，从而更好的发挥数据总线的传输能力；字扩展可以增加存储器的存储字数，从而更好利用 CPU 的寻址能力。既然二者都有的优点，那么就可以将它们综合起来，这种方法就是字位同时扩展。

如下图有 8 块芯片，共有 4 组，每组两块，每组芯片实现了位扩展。

前面的可以连接 $D_{0}-D_{3} $, 后面的可以连接前面的可以连接$D_{4}-D_{7}$。

这是一个 16K 的存储芯片，因此将 $A_{0}-A_{13} $作为片内地址， $ A_{14}-A_{15} $介入 2,4 译码器（因为有 4 组）。一个芯片是 16K×4 位，一组就是 16K×8 位，整体就是 64×8 位。

5.3.译码器(补充知识点)

1：需要注意的是片选信号和译码器要配合使用，一定要注意是高电平有效还是低电平有效。

2：译码器往往还有一个 (还有可能是多个) 和$CS $ 类似功能的控制端，叫做使能端，即$EN $。

下面两个必须是低电平，上面必须是高电平才能工作。如果是其他非法状态，译码器右侧输出将会是全 1。

3：在实际场景中，CPU 上还会有一个 MREQ（访问存储器的控制信号），CPU 会通过它来控制访问存储器。如下，只有当 MREQ 发出高电平时，经过非门，变为低电平后，译码器使能端变为低电平，此时译码器工作，地址才会被映射。

之所以 CPU 需要控制，是因为这些地址信息都是电信号，开始时电信号是不稳定的，因此需要等稳定后才能 “打开” 译码器。

4：注意 74ls138

6.双端口RAM和多模块存储器

之前在存储器分类、多级存储系统和存储器性能指标这篇文章中讲到了存取周期的概念：：存取周期又称读写周期或访问周期，它是指存储器进行一次完整的读写操作所需的全部时间，即连续两次独立访问存储操作（读或写操作）之间所需的最小时间间隔。对于 DRAM芯片，它的恢复时间是比较长的，有时有可能会到达存取周期的几倍，而现代计算机 CPU 通常都是多核的，那么这么多 CPU 核心究竟应该怎样访问主存才能解决恢复时间过长带来的问题呢？主要有两种思路：

双端口 RAM。
多模块存储器。

双端口 RAM：是指同一个存储器有左右两个独立的端口，分别具有两组相互独立的地址线、数据线和读写控制线，允许两个独立的控制器同时异步地访问存储单元。该项技术可以优化多核 CPU 访问一根内存条的速度。

两个端口对同一主存操作时无外乎有以下四种情况：

两个端口不同时对同一地址单元读出数据：没有错误。
两个端口同时对同一地址单元读出数据：没有错误。
两个端口同时对同一地址单元写入数据：发生写入错误。
两个端口同时对同一地址单元操作，一个写入，一个读出：发生读出错误。

其解决方法为：置 “忙” 信号 $ BUSY $为 0，由判断逻辑决定暂时关闭一个端口（延时）。未被关闭的端口正常访问，被关闭的延长一个很短的时间段后再访问。

多模块存储器：多体并行存储器由多体模块组成。每个模块都有相同的容量和存取速度，各模块都有独立的读写控制电路、地址寄存器和数据寄存器。它们既能并行工作，又能交叉工作。有两种编址方式：

高位交叉编址。
低位交叉编址。

6.1.高位交叉编址

高位交叉编址：高位地址表示体号，低位地址为体内地址。在这种编址方式下，总是把低的体内地址送到由高位体号所确定的模块内进行译码。访问一个连续的主存块时，总是先在一个模块内访问，等到该模块访问完才转到下一个模块访问，CPU 总是按顺序访问存储模块，存储模块不能并行访问，因此不能提高存储器的吞吐率。

如下图，存储器共有 4 个模块 $ M_{0}-M_{3} $（可以将其理解为 “4 根内存条”），按照这种方式编址后，地址前两位（高位）表示的是某根内存条，后面部分（低位）表示的是该内存条中的具体地址。

假设每个存储体的存取周期为 $T$，存取时间为 $r$，且 T=4r。如果多体存储器采用高位交叉编址，那么 CPU 真正花在读数据上的时间只有 $r$，但却要再花费 3r 的时间用来等待，效率不高。也就是说连续读取 $n$个存储字，就要耗时 $ nT $

6.2.低位交叉编址

低位交叉编址：低位地址表示体号，高位地址为体内地址。在这种编址方式下，总是把高位的体内地址送到由低位体号所确定的模块内进行译码。程序连续存放在相邻的模块中，将采用此编址方式的存储器称为交叉存储器。采用低位交叉编址后，可在不改变每个模块存取周期的前提下，采用流水线的方式并行存取，提高存储器带宽。

如下图，存储器共有 4 个模块$ M_{0}-M_{3}$（可以将其理解为 “4 根内存条”），每个模块的模块号 = 单元地址 %4 。

采用低位交叉编址的存储器连续读取 $n$个存储字，耗时为 $ T+(n-1)r $。CPU 每经过时间 $r$ 后会启动下一模块，**因此交叉存储器要求其模块数必须大于等于 $ $**，以保证某模块后经过$ T $ 时间后再次启动该模块时，其上次的存取周期已到（也就是已经恢复）。

7.磁盘存储器（磁盘的基本结构，磁盘阵列）

7.1.磁盘存储器

计算机的外存储器又称为辅助存储器，目前主要使用磁表面存储器。所谓 “磁表面存储”，是把某些磁性材料薄薄地涂在金属铝或塑料表面上作为载磁体来存储信息。

磁表面存储器有以下优点：

存储容量大，价位低。
记录介质可以重复使用。
记录信息可以长期保存而不丢失，甚至可以脱机存档。
非破坏读出，读出时不需要再生。

磁表面存储器有以下缺点：

存取速度慢。
机械结构复杂。
对环境要求较高。

7.1.1.磁盘设备组成

7.1.1.1.存储区域

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

磁头数：也即记录面数，表示硬盘总共有多个磁头，磁头分为读磁头和写磁头，每个磁头对应一个记录面。
柱面数：表示硬盘每一面盘片上有多少条磁道。在一个盘组中，不同记录面的相同编号（位置）的诸磁道构成一个圆柱面。
扇区数：表示每一条磁道上有多少个扇区。

7.1.1.2.硬盘存储器的构成

硬盘存储器的构成：由磁盘驱动器，磁盘控制器和盘片组成。

磁盘驱动器：核心部件是磁头组件和硬件组件，温彻斯特是一种可移动磁头固定盘片的硬盘存储器 。
磁盘控制器：硬盘存储器和主机的接口，主流的标准有 IDE,SCSI,SATA 等。

7.1.2.磁盘性能指标

①：磁盘容量：一个磁盘所能存储的字节总数。磁盘容量有格式化容量和非格式化容量之分。

非格式化容量：磁记录表面可以利用的磁化单元总数。
格式化容量：是指按照某种特定的记录格式所能存储信息的总量。

②：记录密度：是指盘片单位面积上记录的二进制的信息量，通常以道密度、位密度和面密度表示。

道密度：沿磁盘半径方向单位长度上的磁道数。
位密度：是磁道单位长度上所能记录的二进制代码的位数。
面密度：是道密度和位密度的乘积。

磁盘所有磁道记录的信息量一定是相等的，并不是说圆越大记录的信息就越多，因此越靠近里面的磁道位密度就越大。

7.1.3.平均存取时间

平均存取时间：一次磁盘读写花费的时间由以下三种时间决定：

①：寻道时间 $ T_{S} $：在读 / 写数据前，将磁头移动到指定磁道所花费时间。

启动磁头臂花费时间：$ s $（约为 2ms）。
移动磁头花费时间： 假设磁头匀速移动，每跨越一个磁道耗时为 $ m$（约为 0.2ms），总共需要跨越 $n$条磁道。
总花费时间： $ T_{S} $= $ s$+ $ m$× $ n$。

②：延迟时间 T R T_{R} TR：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。

磁盘转速为 $r$(单位为 “转 / 秒” 或“转 / 分”，典型转速为 5400r/min 或 7200r/min)。
转一圈所需要时间： $ $。
目标扇区平均需要转半圈： $ $。
总花费时间： $ T_{R} $= $ $× $ $= $r $。

③：传输时间 $T_{t} $：从磁盘读出或向磁盘写入数据所经历的时间。

每个磁道可以存储 $n$字节的数据，因此对于$ b $字节的数据需要的磁道数为： $ $。
读写一个磁道所需要的时间刚好又是转一圈所需要的时间： $ $。
总花费时间：$ T_{t} $= $ $× $ $= $ $。

因此：总的平均存储时间 $T_{a} $= 寻道时间 + 延迟时间 + 传输时间 = $ T_{s} $+ $ $+ $ $。

寻道时间为 6ms。
10000r/min，所以 166r/s，因此转一圈大约 6ms，所以半圈 3ms，所以延迟时间为 3ms。
传输时间为 4(KB)/20(MB)=0.2ms。
其他时间为 0.2ms。
所以平均时间为 9.4ms。

7.1.4.磁盘地址

主机会向磁盘发送地址信息，格式如下：

驱动器号	柱面（磁道）号	盘面号	扇区号
确定是哪一个硬盘	用于移动寻道	激活某个磁头	旋转扇区划过磁头

如果系统中有 4 个驱动器，每个驱动器带一个磁盘，每个磁盘 256 个磁道，16 个盘面，每个盘面划分为 16 个扇区，则每个扇区地址要 18 位二进制代码，分布如下：

7.1.5.磁盘工作过程

硬盘的主要操作是寻址、读盘、写盘。每个操作都对应一个控制字，硬盘工作时，第一步是取控制字，第二步是执行控制字。

需要注意的是硬盘属于机械式部件，其读写操作是并行的，不可能在同一时刻既读又写，也不可能在同一时刻读两组数据或写两组数据。所以是需要串 - 并变换电路的。

7.2.磁盘阵列

磁盘阵列：RAID（廉价冗余磁盘阵列）是指将多个独立的物理磁盘组成一个独立的逻辑盘，数据在多个物理盘上分割交叉存储，并行访问，具有更好的存储性能，可靠性和安全性。

RAID 的分级如下。在 RAID1~RAID5 几种方案中，无论何时有磁盘损坏，都可随时拔出受损的磁盘再插入好的磁盘，而数据不会损坏，提升了系统的可靠性。

RAID0：无冗余和无校验的磁盘阵列（逻辑上相邻的两个扇区在物理上存到两个磁盘）。
RAID1：镜像磁盘阵列（直接存两份数据）。
RAID2：逻辑上连续的几个 bit 物理上分散存储在各个盘中，4bit 信息为 + 3bit 海明校验位，可纠正一位错误。
RAID3：位交叉奇偶校验码的磁盘阵列。
RAID4：块交叉奇偶校验的磁盘阵列。
RAID5：无独立校验的奇偶校验磁盘阵列。

总之，RAID 通过同时使用多个磁盘，提高了传输率；通过在多个磁盘上并行存取来大幅提高存储系统的数据吞吐量了通过镜像功能，提高安全可靠性；通过数据校验，提高容错能力。

7.3.光存储器

光盘存储器是利用光学原理读 / 写信息的存储装置，它采用聚集激光束对盘式介质以非接触的方式记录信息 。

8.固态硬盘

在微小型高档笔记本电脑中，采用高性能 Flash Memory 作为硬盘记录数据——固态硬盘 。

8.1.固态硬盘（SSD）概述

固态硬盘（SSD）：它是一种基于闪存技术的存储器，与 U 盘并无本质区别，属于电可擦除 ROM，也即 EEPROM。传统机械硬盘与固态硬盘内部构造如下图所示：

SSD 有以下特点：

SSD 读写速度较快，随机访问性能高，用电路控制访问位置（机械硬盘则是通过移动磁臂旋转磁盘控制访问位置）。
SSD 安静无噪音、耐摔抗震、能耗低、造价更高。
SSD 容易出现坏块（读写次数过多可能会导致）。

8.2.固态硬盘（SSD）组成

8.2.1.闪存翻译层

闪存翻译层：主要作用是负责翻译逻辑块号，找到对应页。具体来说，I/O 总线会给出系统所要读 / 写的逻辑块号，然后闪存翻译层会把逻辑块号映射为对应的物理地址。

8.2.2.存储介质

存储介质：上面 SSD 构造图中的黑色块状部分为闪存芯片，多个闪存芯片构成 SSD 的闪存芯片组。每个闪存芯片内由多个数据块组成（每个数据块大小为 16KB~512KB）、每个数据块又有多个页组成（每个页大小为 512B~4KB）。这里特别注意 “逻辑块” 在不同的存储器下有不同的含义：

如果是磁盘：逻辑块指的就是磁盘的块或扇区。
如果是 SSD：逻辑块指的就是 SSD 的页。
所以，SSD 的一个页相当于磁盘的一个扇区、SSD 的一个块相当于磁盘的一个磁道。

8.3.固态硬盘（SSD）的读写

固态硬盘（SSD）的读写：主要由以下特点：

以页为单位进行读写。
以块为单位进行擦除，擦干净的块，其中的每页都可以写一次，读无限次。
支持随机访问，也即系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址。
SSD 读速度要快于写速度，这是因为要写的页如果有数据则需要先将块内其他页全部复制到一个新的块中，再写入新的页。

8.4.磨损均衡技术

磨损均衡技术：由于反复写会导致闪存快磨损，所以引入磨损均衡技术，闪存翻译层有一个平均磨损逻辑试图通过将擦除平均分布在所有块上来最大化每个块的寿命。有如下两种方式：

动态磨损均衡：写入数据时，优先选择累计擦除次数少的新闪存块。
静态磨损均衡：SSD 监测并自动进行数据分配、迁移。让老旧的闪存块承担以读为主的储存任务，让较新的闪存块承担更多的写任务。

9.高速缓冲存储器Cache

由于程序的转移概率和数据分布的离散性很大，所以想要仅仅通过提高主存系统的并行性以此来提升存储器带宽的想法是不现实的。因此这就我们必须从系统结构上加以改进，也即采用1.1存储器分类中讲到的多级存储体系。

Cache - 主存层次。
主存 - 辅存层次。

9.1.Cache 基本原理

以微信为例，当你打开微信时，与微信有关的数据和代码将会被加载进主存，比如文字数据、支付数据、运动数据等等。这些数据很多，涉及各个功能，但有的人使用微信可能只偏好于某些方面（比如视频聊天）。所以在这样的情况下，CPU 在较长时间内使用到的只是微信的部分程序和数据。

所以可以把把这一部分的数据复制一份给 Cache，由于 Cache 的速度和 CPU 十分接近，这样的话 CPU 会直接和 Cache 交流，整机性能会有明显提升 。

9.2.程序访问的局部性原理

如下是一段简单的 C 语言程序：

int sumarrayrows(int a[M][N])
{
	int i,j,sum=0;
	for(i = 0 ;i < M ;i++)
		for(j = 0;j < N;j++
			sum+=a[i][j];
	return sum;
}

该程序在运行后会被加载进内存，程序的本质就是指令和数据，所以这段程序在主存中分布情况可能是下面这样：

假定 M、N 为 2048，按字节编址，int 占用 4 个字节。
这个二维数组看似是二维的，实则在主存中是一维的，相当于把第二行接到了第一行的尾巴后面。

程序访问的局部性原理包括空间局部性和时间局部性：

空间局部性：是指最近未来要用到的信息，很可能与现在使用的信息在存储空间上是邻近的。例如上例中形参是一个数组，在一个元素访问完毕之后，下一个元素的物理位置和它其实是相邻的。

时间局部性：是指最近未来要用到的信息，很可能就是现在正在使用的信息。比如上例中 for 循环内的sum+=a[i][j]，这一条语句明显会被重复使用多次。

Cache + 局部性原理：可以把 CPU 目前正在访问的元素的邻近数据放到 Cache 中，之后 CPU 的访存操作大多数就会针对 Cache 进行，程序的执行速度的也会得到提升。

下面是一个空间局部性很差的程序，它只是在上面程序的基础上把 “一行一行的访问” 变为了 “一列一列的访问”。之前，访问完a[0][0]，下一个访问的就是a[0][1]，而现在下一个却变成了a[1][0]了。因为每次访问都要跳过 2048 个数组元素，也就是 8192 字节，假如主存与 Cache 的交换单位较小，那么每访问一个数组元素都需要装入一个主存块到 Cache 中。

int sumarrayrows(int a[M][N])
{
	int i,j,sum=0;
	for(i = 0 ;i < N ;i++)
		for(j = 0;j < M;j++
			sum+=a[i][j];
	return sum;
}

9.3.主存块

主存块：这是主存与 Cache 之间交换数据的最小单位。也即将主存的存储空间分块，比如每 1KB 为一块，主存与 Cache 之间就会以块为单位进行数据交换。

例如下图数组，对于a[0][0]我们先判断它属于哪一块，确定好之后再将它所在的块复制到 Cache 中去。

假设主存大小为 4M，每 1KB 为一块，由于 4M=4096KB，因此会被分为 4096 块，然后对其编号（0-4095）。

由于 $2^{22}=4 194 $，所以这些地址至少需要 22 位才能全部表示，我们将 22 位地址拆分为两个部分，前 12 位表示块号（ $ 2^{12}=4096 $），后 10 位表示块内地址（ $ 2^{10}=1024 $)。

9.4.命中率和缺失率

命中率 $H$： CPU 欲访问的信息已经在 Cache 中的比率。

缺失率： CPU 欲访问的信息未经在 Cache 中的比率，为 $1-H$。

假设某程序执行期间，Cache 的的总命中次数为 $ N_{c} $，访问主存的总次数为 $ N_{M} $，那么 $H$= $ $。
命中率 $H$ 越接近 1 越好。
设 $ t_{c} $为命中时的 Cache 访问时间， $ t_{m} $为未命中时的访问时间, 则 Cache - 主存系统的平均访问时间 $ T_{a}=Ht_{c}+(1-H)t_{m} $。

10.Cache和主存的映射方式

前面说过，Cache 中保存的实际是主存中的数据副本，所以这里就会涉及一个很重要的问题：主存内容和 Cache 中的内容是如何对应，也即是如何映射的？ 地址映射的方法有以下三种：

全相联映射：主存块可以放在 Cache 的任何位置。
直接映射：每个主存块只能放到一个特定的位置，由主存块号 %Cache 总块数来确定。
组相联映射：将 Cache 块分为若干组，每个主存块可以放到特定分组中的任意一个位置，其中组号 = 主存块号 % 分组数。

把主存块放到 Cache 中后：

要给每个 Cache 块增加一个 “标记位”，记录对应的主存块号。
再给每个 Cache 块增加一个 “有效位”，用于控制其是否生效，以免产生冲突。

分块后需要对主存进行编号，假设某个计算机的主存地址空间大小为 256MB，按字节编址，Cache 有 8 个 Cache 行（也即 Cache 块），行长（也即块大小）为 64B。

主存块号编号：块大小为 $64B=2^6B$、主存大小为 $256MB=2^28B$，那么就有 $2^{28}/2^6$ 个主存块，所以主存编号为从 0 到 $2^{22}-1$。
块内地址：这 22 位是用于区分主存块的，所以剩下的 28-22=6 位则为每个主存块的地址范围（或空间）。也即先利用高 22 位确定是哪一块，然后在该块中用低 6 位确定地址。

10.1.全相联映射

10.1.1.如何映射

全相联映射：主存块可以放在 Cache 的任何位置。

例如下图中的 0 号主存块，它就可以放置到 Cache 的 3 号位置，每行的标记号用于指出该行取自主存的哪一块，同时将对应的有效位置为 1。

10.1.2.如何访存

以上图紫色主存块为例，其地址为 1…1101001110，在全相联映射下，CPU 访存时首先会取该地址的前 22 位，也即主存块号，来和 Cache 中每一行的标记进行对比。

若标记号 = 块号且有效位为 1：说明 Cache 命中，也就是说此时访问的数据在 Cache 中是有副本的，接着只需在 Cache 中访问后 6 位地址所定位的单元即可。
若标记号不匹配或匹配但有效位为 0：此时说明 Cache 未命中，则正常访问主存，也即要从主存中取数据。

10.2.直接映射

10.2.1.如何映射

直接映射：每个主存块只能放到一个特定的位置，由主存块号 %Cache 总块数来确定。

例如下图中的 0 号主存块，由于 0%8=0，因此它只能放到 Cache 的 0 号位置；对于 8 号主存块，由于 8%8=0，所以它也要放到 0 号位置，而且需要把之前的 0 号主存块给腾空，相应的标记位也要修改。

“%” 运算具有一些特性，这里 Cache 块数 = 8=$2^3$，其指数部分为 3，这意味着主存块号中的后 3 位直接反映了该主存块在 Cache 中的位置。例如上图中的 0 号和 8 号，其主存块号的后三位均为 000，这正好对应了它们在 Cache 的第 0 行。

因此标记可以直接取主存块号的前 19 位，相应地址形式会变化为下面这样 。

10.2.2.如何访存

以上图橙色主存块为例，其地址为 0…01000001110。在直接映射下，CPU 访存时首先会根据主存块号的后三位确定 Cache 行（而不用挨个比较），接着会判断前 19 位和标记号是否匹配并同时判断有效位是否为 1。

10.3.组相联映射

10.3.1.如何映射

组相联映射：将 Cache 块分为若干组，每个主存块可以放到特定分组中的任意一个位置，其中组号 = 主存块号 % 分组数。

以 2 路组相联为例（2 块为一组，分为四组）。对于下图中 1 号主存块，由于 1%4=1，因此它会被放入第一组的任意位置；对于 222-3 号主存块也会放入第一组，它会放到该组另一个空闲位置。

和直接映射一样，由于 “%” 的运算特性，这里分组数 = 4=22，这意味着主存块号中的后 2 位反映了该主存块在哪一个组。所以标记号只需取前 20 位，相应地址形式会变化为下面这样。

10.3.2.如何访存

以上图橙色主存块为例，其地址为 1…0100001110。在组相联映射下，CPU 访存时首先会根据主存块号的后两位确定所属分组号，接着会判断主存块号的前 20 位与分组内的某个标记号是否匹配同时判断有效位是否为 1。

10.4.三种方式各自优缺点

全相联映射：

优点：Cache 存储空间利用充分，命中率高。
缺点：查找慢，有时可能要比对所有行的标记。

直接映射：

优点：对于任意一个位置，只需对比一个标记，速度最快。
缺点：缺点就是 Cache 存储空间利用不充分，命中率低。

组相联映射：综合效果较好。

11.Cache替换算法

在10.Cache和主存的映射方式中我们讲到了 Cache 和主存之间的映射关系，细致分析了三种映射方式各自的特点。那么下一个亟待解决的问题就是：Cache 是很小的，主存却很大，如果 Cache 满了应该怎么办？ 这就是本节的主题——Cache 的替换算法。当然，不同的映射方式其替换机制也会有所不同。

全相联映射：Cache 完全满了才需要替换，需要在全局中选择替换哪一块。
直接映射：如果对应位置为空则直接替换，无需考虑替换算法。
组相联映射：分组内满了才需要替换，需要在分组内选择替换哪一块。

本节以全相联映射为例，介绍以下四种替换算法：

随机算法（RAND）。
先进先出算法（FIFO）。
近期最少使用算法（LRU）。
最不频繁使用算法（LFU）。

在讲解之前大家一定明白一点，CPU 每访问一个内存块，都会立即把该内存块调入 Cache 中。

11.1.随机算法（RAND）

随机算法（RAND）：若 Cache 已满，则随机选择一块进行替换。

通过以下叙述可知：随机算法十分简单，但是它完全没有考虑到局部性原理，命中率很低，实际效果很不稳定。

如下有 4 个 Cache 块，初始状态下 4 个 Cache 块均为空，采用全相连映射，CPU 访问主存块的顺序为：{1,2,3,4,1,2,5,1,2,3,4,5}，CPU 每访问一个内存块，都会立即把该内存块调入 Cache 中，前四次调入时由于都有空闲 Cahce 块，所以不会发生替换。

访问主存块	1	2	3	4
Cache #0	1	1	1	1
Cache #1		2	2	2
Cache #2			3	3
Cache #3				4
是否命中？	否	否	否	否
是否替换？	否	否	否	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。由于 1,2 主存块已经被调入了 Cache，所以直接命中。

访问主存块	1	2	3	4	1	2
Cache #0	1	1	1	1	1	1
Cache #1		2	2	2	2	2
Cache #2			3	3	3	3
Cache #3				4	4	4
是否命中？	否	否	否	否	是	是
是否替换？	否	否	否	否	否	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。对于 5 号主存块，它并没有调入 Cache 中，因此需要立即被调入，但此时已经没有空闲 Cache 块了，所以需要使用替换算法选择一块换出，然后再把 5 号主存块调入。这里采用的是随机算法，所以我们可以任意挑选一块调入，比如把 3 号主存块给替换出去。

访问主存块	1	2	3	4	1	2	5
Cache #0	1	1	1	1	1	1	1
Cache #1		2	2	2	2	2	2
Cache #2			3	3	3	3	5
Cache #3				4	4	4	4
是否命中？	否	否	否	否	是	是	否
是否替换？	否	否	否	否	否	否	是

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。直接命中。

访问主存块	1	2	3	4	1	2	5	1	2
Cache #0	1	1	1	1	1	1	1	1	1
Cache #1		2	2	2	2	2	2	2	2
Cache #2			3	3	3	3	5	5	5
Cache #3				4	4	4	4	4	4
是否命中？	否	否	否	否	是	是	否	是	是
是否替换？	否	否	否	否	否	否	是	否	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。和上面一样，随机挑选一块换出。

访问主存块	1	2	3	4	1	2	5	1	2	3
Cache #0	1	1	1	1	1	1	1	1	1	1
Cache #1		2	2	2	2	2	2	2	2	2
Cache #2			3	3	3	3	5	5	5	5
Cache #3				4	4	4	4	4	4	3
是否命中？	否	否	否	否	是	是	否	是	是	否
是否替换？	否	否	否	否	否	否	是	否	否	是

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。和上面一样，随机挑选一块换出。

访问主存块	1	2	3	4	1	2	5	1	2	3	4
Cache #0	1	1	1	1	1	1	1	1	1	1	4
Cache #1		2	2	2	2	2	2	2	2	2	2
Cache #2			3	3	3	3	5	5	5	5	5
Cache #3				4	4	4	4	4	4	3	3
是否命中？	否	否	否	否	是	是	否	是	是	否	否
是否替换？	否	否	否	否	否	否	是	否	否	是	是

访存结束，{1,2,3,4,1,2,5,1,2,3,4,5}。直接命中。

访问主存块	1	2	3	4	1	2	5	1	2	3	4	5
Cache #0	1	1	1	1	1	1	1	1	1	1	4	4
Cache #1		2	2	2	2	2	2	2	2	2	2	2
Cache #2			3	3	3	3	5	5	5	5	5	5
Cache #3				4	4	4	4	4	4	3	3	3
是否命中？	否	否	否	否	是	是	否	是	是	否	否	是
是否替换？	否	否	否	否	否	否	是	否	否	是	是	否

11.2.先进先出算法（FIFO）

先进先出算法（FIFO）：若 Cache 已满，则替换最先被调入 Cache 的块。

通过以下叙述可知：先进先出算法实现也很简单，但该算法依然没有考虑到局部性原理，因为最先被调入的 Cache 块也有可能是会频繁访问到的。而且此算法容易产生抖动现象（—刚换上去的块又立马被换下）。

仍然采用之前的例子，直接进行到这一步。

访问主存块	1	2	3	4	1	2
Cache #0	1	1	1	1	1	1
Cache #1		2	2	2	2	2
Cache #2			3	3	3	3
Cache #3				4	4	4
是否命中？	否	否	否	否	是	是
是否替换？	否	否	否	否	否	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。对于 5 号主存块，它并没有调入 Cache 中，因此需要立即被调入，但此时已经没有空闲 Cache 块了，所以需要使用替换算法选择一块换出，然后再把 5 号主存块调入。这里采用的是 FIFO 算法，根据先进先出原则，最先被调入 Cache 的最先被替换，因此 1 号被替换。

访问主存块	1	2	3	4	1	2	5
Cache #0	1	1	1	1	1	1	5
Cache #1		2	2	2	2	2	2
Cache #2			3	3	3	3	3
Cache #3				4	4	4	4
是否命中？	否	否	否	否	是	是	否
是否替换？	否	否	否	否	否	否	是

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。此时应该替换 2 号。

访问主存块	1	2	3	4	1	2	5	1
Cache #0	1	1	1	1	1	1	5	5
Cache #1		2	2	2	2	2	2	1
Cache #2			3	3	3	3	3	3
Cache #3				4	4	4	4	4
是否命中？	否	否	否	否	是	是	否	否
是否替换？	否	否	否	否	否	否	是	是

后续步骤不再详细演示，最终结束状态如下：

访问主存块	1	2	3	4	1	2	5	1	2	3	4	5
Cache #0	1	1	1	1	1	1	5	5	5	5	4	4
Cache #1		2	2	2	2	2	2	1	1	1	1	5
Cache #2			3	3	3	3	3	3	2	2	2	2
Cache #3				4	4	4	4	4	4	3	3	3
是否命中？	否	否	否	否	是	是	否	否	否	否	否	否
是否替换？	否	否	否	否	否	否	是	是	是	是	是	是

11.3.近期最少使用算法（LRU）——效率最高

近期最少使用算法（LRU）：该算法会为每一个 Cache 块设置一个计数器，用于记录每个 Cache 块究竟有多长时间没有被访问了。在替换时直接选取计数器最大的替换即可。

通过以下叙述可知：LRU 算法是基于局部性原理的，近期访问过的主存块，在不久的将来很有可能会被再次访问到，因此这种淘汰机制是合理的。LRU 算法的实际运行效果也很优秀，Cache 命中率也高。

计数器的变化规则如下：

命中时：所命中的块的计数器清零，计数器比其低的块的计数器 + 1，其余不变。
未命中且还有空闲块时：新装入的块的计数器置为 0，其余非空闲块的计数器全 + 1。
未命中且没有空闲块时：计数器最大的块被淘汰，新装入块的计数器置为 0，其余块的计数器 + 1。

如下表格表示初始状态：

计时器	访问主存块	1	2	3	4	1	2	5	1	2	3	4	5
0	Cache #0
0	Cache #1
0	Cache #2
0	Cache #3
	是否命中？
	是否替换？

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。由于 1 装入了第一个 Cache 块，属于未命中且还有空闲块，因此该块计数器置为 0，其余非空闲块计数器全 + 1。

计时器	访问主存块	1
0	Cache #0	1
0	Cache #1
0	Cache #2
0	Cache #3
	是否命中？	否
	是否替换？	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。情况同上。

计时器	访问主存块	1	2
1	Cache #0	1	1
0	Cache #1		2
0	Cache #2
0	Cache #3
	是否命中？	否	否
	是否替换？	否	否

第三、四个主存块亦是如此。

计时器	访问主存块	1	2	3	4
3	Cache #0	1	1	1	1
2	Cache #1		2	2	2
1	Cache #2			3	3
0	Cache #3				4
	是否命中？	否	否	否	否
	是否替换？	否	否	否	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。此时 Cache 命中，因此需要将所命中块的计数器清零，比其低的块的计数器 + 1，其余不变。

这一点其实就体现了 LRU 算法的核心，它能保证最近访问的块的计数器一定很低。

计时器	访问主存块	1	2	3	4	1
0	Cache #0	1	1	1	1	1
3	Cache #1		2	2	2	2
2	Cache #2			3	3	3
1	Cache #3				4	4
	是否命中？	否	否	否	否	是
	是否替换？	否	否	否	否	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}，情况同上。

计时器	访问主存块	1	2	3	4	1	2
1	Cache #0	1	1	1	1	1	1
0	Cache #1		2	2	2	2	2
3	Cache #2			3	3	3	3
2	Cache #3				4	4	4
	是否命中？	否	否	否	否	是	是
	是否替换？	否	否	否	否	否	否

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。此时属于 “未命中且没有空闲行”，所以计数器最大的块会被淘汰（淘汰 3 号主存块），新装入块的计数器置为 0，其余块计数器全 + 1。

计时器	访问主存块	1	2	3	4	1	2	5
2	Cache #0	1	1	1	1	1	1	1
1	Cache #1		2	2	2	2	2	2
0	Cache #2			3	3	3	3	5
3	Cache #3				4	4	4	4
	是否命中？	否	否	否	否	是	是	否
	是否替换？	否	否	否	否	否	否	是

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。直接命中。

注意：只需要将 “比该块计数器值小的块的计数器 + 1” 即可，大的不变，因此上面表格中的 3 号 Cache 的计时器就不用动了，这里很容易犯错。

计时器	访问主存块	1	2	3	4	1	2	5	1
0	Cache #0	1	1	1	1	1	1	1	1
2	Cache #1		2	2	2	2	2	2	2
1	Cache #2			3	3	3	3	5	5
4	Cache #3				4	4	4	4	4
	是否命中？	否	否	否	否	是	是	否	是
	是否替换？	否	否	否	否	否	否	是	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。直接命中。

计时器	访问主存块	1	2	3	4	1	2	5	1	2
1	Cache #0	1	1	1	1	1	1	1	1	1
0	Cache #1		2	2	2	2	2	2	2	2
2	Cache #2			3	3	3	3	5	5	5
5	Cache #3				4	4	4	4	4	4
	是否命中？	否	否	否	否	是	是	否	是	是
	是否替换？	否	否	否	否	否	否	是	否	否

继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。未命中，且没有空行。

计时器	访问主存块	1	2	3	4	1	2	5	1	2	3
2	Cache #0	1	1	1	1	1	1	1	1	1	1
1	Cache #1		2	2	2	2	2	2	2	2	2
3	Cache #2			3	3	3	3	5	5	5	5
0	Cache #3				4	4	4	4	4	4	3
	是否命中？	否	否	否	否	是	是	否	是	是	否
	是否替换？	否	否	否	否	否	否	是	否	否	是

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。未命中，且没有空行。

计时器	访问主存块	1	2	3	4	1	2	5	1	2	3	4
3	Cache #0	1	1	1	1	1	1	1	1	1	1	1
2	Cache #1		2	2	2	2	2	2	2	2	2	2
0	Cache #2			3	3	3	3	5	5	5	5	4
1	Cache #3				4	4	4	4	4	4	3	3
	是否命中？	否	否	否	否	是	是	否	是	是	否	否
	是否替换？	否	否	否	否	否	否	是	否	否	是	是

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。未命中，且没有空行。

计时器	访问主存块	1	2	3	4	1	2	5	1	2	3	4	5
0	Cache #0	1	1	1	1	1	1	1	1	1	1	1	5
3	Cache #1		2	2	2	2	2	2	2	2	2	2	2
1	Cache #2			3	3	3	3	5	5	5	5	4	4
2	Cache #3				4	4	4	4	4	4	3	3	3
	是否命中？	否	否	否	否	是	是	否	是	是	否	否	否
	是否替换？	否	否	否	否	否	否	是	否	否	是	是	是

11.4.最不经常使用算法（LFU）

最不经常使用算法（LFU）：该算法会为每一个 Cache 块设置一个计数器，用于记录每个 Cache 块被访问过几次。在替换时直接选取计数器最小的替换即可。

通过以下叙述可知：LFU 算法并没有很好地遵循局部性原理，比如微信聊天相关的块，在某个时间段内使用率会很高，但是一段时间后使用率会很低，并不科学。

计数器的变化规则为：

新调入的块计数器为 0，之后每访问一次计数器就 + 1。需要替换时，选择计数器最小的一行替换。
若有多个计数器最小的行，可以按照行号递增或 FIFO 策略进行选择。

计时器	访问主存块	1	2	3	4	1	2	5	1	2	3	4	5
0	Cache #0
0	Cache #1
0	Cache #2
0	Cache #3
	是否命中？
	是否替换？

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。

计时器	访问主存块	1	2	3	4
0	Cache #0	1	1	1	1
0	Cache #1		2	2	2
0	Cache #2			3	3
0	Cache #3				4
	是否命中？	否	否	否	否
	是否替换？	否	否	否	否

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。发生命中，计数器 + 1。

计时器	访问主存块	1	2	3	4	1	2
1	Cache #0	1	1	1	1	1	1
1	Cache #1		2	2	2	2	2
0	Cache #2			3	3	3	3
0	Cache #3				4	4	4
	是否命中？	否	否	否	否	是	是
	是否替换？	否	否	否	否	否	否

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。选择计数器最小的那一行，但是这里有两行相同（都是 0），所以再按照 FIFO 策略选择 3 号主存块淘汰。

计时器	访问主存块	1	2	3	4	1	2	5
1	Cache #0	1	1	1	1	1	1	1
1	Cache #1		2	2	2	2	2	2
0	Cache #2			3	3	3	3	5
0	Cache #3				4	4	4	4
	是否命中？	否	否	否	否	是	是	否
	是否替换？	否	否	否	否	否	否	是

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。1,2 命中，计数器 + 1。

计时器	访问主存块	1	2	3	4	1	2	5	1	2
2	Cache #0	1	1	1	1	1	1	1	1	1
2	Cache #1		2	2	2	2	2	2	2	2
0	Cache #2			3	3	3	3	5	5	5
0	Cache #3				4	4	4	4	4	4
	是否命中？	否	否	否	否	是	是	否	是	是
	是否替换？	否	否	否	否	否	否	是	否	否

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。需要进行替换，这里我们再采用行号递增的规则淘汰 5 号主存块。

计时器	访问主存块	1	2	3	4	1	2	5	1	2	3
2	Cache #0	1	1	1	1	1	1	1	1	1	1
2	Cache #1		2	2	2	2	2	2	2	2	2
0	Cache #2			3	3	3	3	5	5	5	3
0	Cache #3				4	4	4	4	4	4	4
	是否命中？	否	否	否	否	是	是	否	是	是	否
	是否替换？	否	否	否	否	否	否	是	否	否	是

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。命中，计时器 + 1。

计时器	访问主存块	1	2	3	4	1	2	5	1	2	3	4
2	Cache #0	1	1	1	1	1	1	1	1	1	1	1
2	Cache #1		2	2	2	2	2	2	2	2	2	2
0	Cache #2			3	3	3	3	5	5	5	3	3
1	Cache #3				4	4	4	4	4	4	4	4
	是否命中？	否	否	否	否	是	是	否	是	是	否	是
	是否替换？	否	否	否	否	否	否	是	否	否	是	否

继续访存，也即 {1,2,3,4,1,2,5,1,2,3,4,5}。需要替换，只剩一个最小的了，替换 3 号主存块即可。

计时器	访问主存块	1	2	3	4	1	2	5	1	2	3	4	5
2	Cache #0	1	1	1	1	1	1	1	1	1	1	1	1
2	Cache #1		2	2	2	2	2	2	2	2	2	2	2
0	Cache #2			3	3	3	3	5	5	5	3	3	5
1	Cache #3				4	4	4	4	4	4	4	4	4
	是否命中？	否	否	否	否	是	是	否	是	是	否	是	否
	是否替换？	否	否	否	否	否	否	是	否	否	是	否	是

12.Cache的写策略

在 10.Cache和主存的映射方式和 11.Cache替换算法这两篇文章中分别探讨了主存、Cache 之间的映射关系以及 Cache 的替换算法。关于 Cache，最后需要解决的一个问题就是：如何保持 Cache 与数据母体的一致性？因为我们知道，Cache 中保存的只是主存数据的副本，一旦对 Cache 进行写操作就一定会导致两部分数据出现不一致，而对于读操作则不关心。这就是 Cache 写策略所要探讨的问题。

Cache 写策略分写命中和写不命中两种情况：

写命中：有全写法和写回法。
写不命中：有写分配法和非写分配法两种。

12.1.写命中

写命中：写命中时主存块被调入 Cache 中，也即要被修改的单元在 Cache 中。此时有两种方法：

写回法。
全写法。

12.1.1.写回法 (write-back)

写回法 (write-back)：是指当 CPU 写命中时，只修改 Cache 中的内容，而不立即写入主存，只有当此块被换出时才写回主存。如下图，绿色主存块写命中，修改时只在 Cache 上修改，而不立即写入主存，只有当绿色块被替换时才会写回主存。

优点：减少了访存次数。
缺点：存在数据不一致的隐患。

这种方法需要判断 Cache 是否被修改过，因此在对应 Cache 块还会增加一个 “脏位”，用于标识是否修改过，如果对应位为 1 表示修改过，那么在被替换时该 Cache 块中的内容会被写回至标记位所定位的主存块上。

12.1.2.全写法 (write-through)

全写法 (write-through)：是指当 CPU 写命中时，必须把数据同时写入 Cache 和主存。当某一块需要替换时，不必把这一块写回主存，新调入的块直接覆盖即可。

优点：实现简单，更能保持数据的一致性。
缺点：增加了访存次数，降低了 Cache 的效率。

为了减少全写法直接写入主存时所产生时间损耗，通常会在 Cache 和主存之间加入写缓冲（Write Buffer）。CPU 同时写数据到 Cache 和写缓冲中，写缓冲再控制将内容写入主存，写缓冲是一个 FIFO 队列，可以解决速度不匹配的问题。

注意频繁写会导致缓冲区溢出。

12.2.写不命中

写不命中：写不命中时被修改的单元不在 Cache 中。此时有两种方法：

写分配法。
非写分配法。

12.2.1.写分配法 (write-allocate)

写分配法：是指当写不命中时，会把主存的块加载到 Cache 中，然后更新此 Cache 块，通常会结合写回法使用。

12.2.2.非写分配法（not-write-allocate）

非写分配法：是指当写不命中时，CPU 直接对主存的块进行修改，而不调入 Cache 中（注意只有读操作才将主存块调入 Cache 中），通常会结合全写法使用。

13.多级 Cache

现代计算机的 Cache 一般是多级的（通常三级）。对于三级 Cache，按离 CPU 的远近可命名为 L1 Cache、 L2 Cache、 L3Cache，离 CPU 越远，访问速度就越慢，容量也越大，反之相反。 其中指令 Cache 与数据 Cache 分离一般在 L1 级，此时通常为写分配法和写回法合用。

下图是一个含有两级的 Cache 系统，L1 对 L2 使用全写法，L2 对主存使用写回法，由于 L2 的存在，其访问速度远大于主存，因此避免了因频繁写时导致的缓冲区溢出。

如下图是资源管理器中显示的 Cache 信息。

14.虚拟存储器

14.1.页式存储器

前面说过主存和 Cache 之间是以块作为数据的传输单位的。

我们知道，应用程序运行时需要加载进主存。比如说微信，假如它有 1GB 大小，那么想要在主存中找到连续的 1GB 空间是很困难的，并且就算加载进去了，也会极大的破坏主存的利用率，产生很多碎片。

因此为了提高主存利用率，可以将程序（所谓程序就是数据、指令的集合体）分为一个个大小相同的 “页”，每个页面的大小和“物理块” 的大小是相同的。给每个页面编号后，就可以分散在主存中。

所以页式存储系统是这样的：一个程序（操作系统中称为进程)在逻辑上被分为若干大小相同的 “页面”，“页面” 大小与 “块” 大小相同，每个页面可以离散地放入不同的主存块。

页面的划分属于逻辑角度，主存和 Cache 块的划分属于物理角度。

14.2.逻辑地址和物理地址

逻辑地址：程序员视角中看到的地址。
物理地址：数据在主存中真实的地址。

我们编写程序时，所操作的数据其显示的地址均为虚拟地址，真实的地址需要操作系统进行映射。那么为什么需要虚拟地址呢？

早期的计算机启动进程时，会将进程或程序所包含的东西全部加载进内存，而且访问的就是真实的物理内存。

但是这种粗暴的操作有很大弊端，比如说经典的野指针问题在这种情况下就很容易产生，而且进程在运行中会产生大量数据，这些数据一旦不能连续存放，就会另外开辟空间，这无疑增加了异常访问的情况。

所以计算机设计者意识到了这种模式缺陷，想到了一种方法：增加一个中间层，利用中间层映射物理内存。程序访问内存时不直接访问物理内存，先访问中间层，如果中间层访问没有问题，那么操作系统就会将中间层映射到物理层，完成正常执行。

一个进程创建之后，操作系统会为这个进程分配一个专属于它的大小为 4GB 的虚拟进程地址空间（4GB 是因为 32 位系统中，指针是 4 个字节），与它相对的是一片真实的物理地址空间，操作系统在映射虚拟内存时只会映射到那一片物理空间，而且需要特别注意这个虚拟空间并不是真的有 4GB，它只是虚拟的。由于每一个进程都有自己的虚拟的进程地址空间，所以它只能访问自己的进程的数据，这样做实现了隔离，也就是进程之间的相互独立。并且把虚拟地址空间划分为这样、那样的区，也能实现数据的连续存放。

操作系统负责分页操作，该过程对程序员是不可见的。

站在程序员的视角上，对于一个打包好的 4KB 程序，我们肯定是知道它的大小的，由于 4KB=$ 2^{12}B $，因此可以编址，其范围为：000000000000~111111111111 。 假设该程序中有一个变量 $x$ 的逻辑地址为：001000000011，另外一个变量 y 的逻辑地址为：110000001010 。

在学习第一章时，我们知道取变量 $x$ 到 $ ACC $ 寄存器的操作对应的机器指令是：000001 001000000011，分别对应操作码和地址码（逻辑地址)，我们指明的仅仅是一个相对的地址，并不是说 $x$ 的地址真的就在那里。

每个页的大小是 1KB。也就是 $2 ^{10} $B，因此可以将变量 $x$ 的逻辑地址分为两个部分：一个表示页号，一个表示页内地址，其中页内地址的大小取决于每个页面的大小，如果是 1KB，那么就需要 10 个比特位。

因此 $x$ 的逻辑地址：001000000011 就表示它在第 0 页，而 $x$ 的真实的物理地址可以用该页所在的主存的块号（12 位）+ 页内地址表示 。

此例中，第 0 页放在了主存的第 2 块，因此 $x$ 的真实地址为：0000000000101000000011。

14.3.页表和地址变换过程

14.3.1.页表

所以我们见到的地址均为虚拟的地址，给出逻辑地址后，操作系统必须将其转化为真实的物理地址再进行访存，其中最基本的一个操作就是把页号映射为块号，所以为了记录这样的映射关系，操作系统会建立一张页表。

值得注意的是，页表中存放的数据是保存在主存中的，因此进行地址转换时还要要进行访存操作。

地址的变化过程大致如下：

拆分逻辑地址为页号和页内地址。
CPU 中的页表基址寄存器指明了页表在主存中的存放位置（以地址为 1058 为例，就表示当前运行的程序其所对应的页表是从 1058 后的存储单元开始存储的，由于每个页表项的大小相同，所以只需顺次读取即可）。
查询页表找到逻辑页面对应的主存块。
块号 + 页内地址 = 物理地址。
进行访存操作（Cache 未命中时进入主存）。

14.3.2.快表

依据程序执行的局部性原理，在一段时间内总是经常访问某些页时，若把这些页对应的页表项放在一个高速缓冲器中，称之为页表（TLB）中，则明显可以提高效率，相应地把放在主存中的页表称为慢表（Page）。

相应地在进行地址转换时，首先查快表，若命中，则无需访问主存中的页表；否则查询主存中完整的页表，查询之后为了以后便于访问将其加入到快表中。

结合之前的 Cache，整个访存操作可以是如下流程。

14.4.页式虚拟存储器

我们知道，运行一个程序时，需要将该程序调入主存，然后根据局部性原理，主存中的部分相关数据会调入 Cache 以提高性能。那么现在的问题是，一个程序调入主存时需要全部调入吗，还是只需要调入一部分就可以了呢？答案是部分即可。这一点大家可以联系我们日常使用的手机就能明白，手机内存有限，但是可以同时运行多个大体积程序。这就是虚拟存储系统：实际物理内存很有限，但是运行时似乎很大很大。

Tips：游戏开局（比如英雄联盟）前面，会有一段加载资源的过程，也就是 “loading”，其实其中绝大部分的工作就是将相关数据从辅存调入主存。

这一点其实与前面讲过的主存和 Cache 之间的关系比较相似，操作系统仍然会将程序分页，程序加载进主存时，会加载一部分，也就是说有的页已经加载进了主存，有的页还留在辅存中 。

有分页自然也有负责映射的页表，只不过这里的页表和前面所讲的页表稍有不同，除了完成最基本的映射工作外，这里的页表还会增加以下选项：

有效位：该有效位如果为 1 表示该页已经被加载进了主存，如果为 0 表示仍然留在辅存中。
外存块号：为了方便以后快速找到需要加载的页的位置，所以也会将辅存进行分块，并且记录其块号。这样以后程序在运行时，如果需要该数据就会能快速找到并加载进主存。
访问位：前面说过 Cache 被填满后就要执行 Cache 替换算法。而访问位涉及到的就是页面置换算法，主存相较于辅存很小，注定只能保存一部分辅存的副本，所以主存很容易会被填满，当其填满时就要进行替换。访问位可以记录最近一段时间内，该页被访问了多少次，因此淘汰页面时可以优先淘汰次数最少的页面。
脏位：如果脏位为 1 表示进行了更改，如果淘汰页面时则需要写回主存。

置于主存和辅存更详细的过程就需要在操作系统这么课中深究了。

14.5.段式虚拟存储器

段式虚拟存储器中的段是按程序的逻辑结构划分的，各个段的长度因程序而异。把虚拟地址分为两个部分：段号和段内地址。虚拟地址到实地址之间的变换是由段表实现的。段表是程序的逻辑段和在主存中存放位置的对照表。段表的每行记录与某个段对应的段号、装入位、段起点和段长等信息。由于段的长度可变所以段表中要给出各段的起始地址和段的长度。

CPU 根据虚拟地址访存时，首先根据段号与该段基地址拼接成对应的段表行，然后根据该段表行的装入位判断该段是否已调入主存。已调入主存时，从段表读出该段在主存中的起始地址与段内地址（偏移量）相加，得到对应的主存实地址。

段式虚拟存储器的优点是：段的分界与程序的自然分界对应，因为具有逻辑独立性，使得它易于编译、管理、修改和保护，也便于多道程序的共享。缺点则是因为段长度可变，分配空间不便，容易在段间留下碎片，不好利用，造成浪费。

14.6.段页式虚拟存储器

把程序按逻辑结构分段，每段再划分为固定大小的页，主存空间也划分为大小相等的页，程序对主存的调入、调出仍以页为基本传送单位，这样的虚拟存储器称为段页式虚拟存储器。在段页式虚拟存储器中，每个程序对应一个段表，每段对应一个页表，段的长度必须是页长的整数倍，段的起点必须是某一页的起点。

虚地址分为段号、段内页号、页内地址三部分。CPU 根据虚地址访存时，首先根据段号得到段表地址; 然后从段表中取出该段的页表起始地址，与虚地址段内页号合成，得到页表地址; 最后从页表中取出实页号，与页内地址拼接形成主存实地址。

段页式虚拟存储器的优点是，兼具页式和段式虚拟存储器的优点，可以按段实现共享和保护。缺点是在地址变换过程中需要两次查表，系统开销较大。

14.7.虚拟存储器与 Cache 比较

14.7.1.相同

最终目的都是为了提高系统性能，两者都有容量、速度和价格的梯度。
都把数据分为小的信息块，并作为基本的传递单位，虚拟存储器系统的信息块更大。
都有地址的映射、替换算法和更新策略等问题。
依据程序的局部性原理应用 “快速缓存的思想”，将活跃的数据放在相对高速的部件中。

14.7.2.不同

Cache 主要为了解决系统的速度，而虚拟存储器则为了解决主存容量。
Cache 全由硬件实现，是硬件存储器，对程序员透明；而虚拟存储器由 OS 和硬件共同实现，是逻辑上的存储器，对系统程序员不透明，但对应用程序员透明。
由于 CPU 的速度约为 Cache 的 10 倍，主存的速度约为硬盘的 100 倍以上，因此虚拟存储器系统不命中时对系统的性能影响很大。
CPU 与 Cache 和主存都建立了直接访问的通路，而辅存与 CPU 没有直接通路。也就是说在 Cache 不命中时主存能和 CPU 直接通信，同时将数据调入 Cache；而虚拟存储器系统不命中时，只能先由硬盘调入内存，而不能直接和 CPU 通信。