码距 (code distance)

第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## 码距 (code distance)

两个码字中具有不同代码的位数称为码字间的“距离”。在一种编码方式下所有可能出现的码字中，任意两两进行比较得到一组距离，其中的最小值称为这种编码方式的“码距”。例如，8421码的码距为1。

## 奇偶校验 (parity check)

奇偶校验通过在原二进制数据中增加一个奇校验位或偶校验位，用它使这组代码中“1”的个数为奇数或偶数，最后在该数据传输的结果中检查“1”的个数是否保持为奇数或偶数，如果是，则认为正确或有偶数个位置出错，否则，认为有奇数个位置出错。

## 海明码 (Hamming codes)

海明码主要用于存储器中的数据校验，将数据按某种规律分成若干组，对每组进行相应的奇偶检测。最终比较时，按位进行异或操作，根据异或操作结果，确定在哪一位发生了差错。

## 循环冗余校验 (Cyclic Redundancy Check, CRC)

循环冗余校验常用于外存储器或数据通信中的数据校验，检错纠错能力强。编码时通过某种数学运算根据原数据生成校验位，在检查时对含校验位的数据进行相应的数学运算，根据运算结果检错和纠错。

## 高速缓存 (cache)

高速缓存是在CPU和主存之间的一个高速小容量的存储器，在访问主存前先到该存储器访问。如果将当前正在访问的那个存储单元所在的主存块放到该存储器中，根据程序访问的局部化特性，这个主存块中的信息应该是最近经常要访问的，所以不必再到主存去访问，这样就可以很快得到所要的信息。

## 程序访问的局部化

对大量程序调查发现，程序在执行过程中产生的访存要求，其地址具有局部化特性。也就是说，在一个小的时间段内，存储器访问的地址大多在一个局部空间内。体现在时间和空间两个方面，可分为时间局部性和空间局部性两种。

## 时间局部性 (temporal locality)

时间局部性是指刚刚被访问的单元很可能在一个很短的时间内被再次访问。

## 空间局部性 (spatial locality)

空间局部性是指刚刚被访问的单元的临近单元很可能不久也会被访问。

## 命中率 (hit rate)

命中率指在快速的缓存中得到信息的概率。例如，在总共100次访问中，能在cache中访问到信息的次数为99次，则命中率为 99% 。

## 命中时间 (hit time)

命中时间是指在命中情况下的访问时间，包括判断是否命中的时间和在快速存储器中的访问时间两部分。

## 缺失率 (miss rate)

有些中文书将缺失率翻译成“失靶率”或“失效率”，是指没有命中的概率。例如，在总共100次访问中，能在cache中访问到信息的次数为99次，则缺失率为 1% 。


<!-- page: 198 -->

缺失损失(miss penalty)

缺失损失是指在缺失情况下，从主存取一个数据块到 cache 的时间。

主存块(block)

主存块是主存和 cache 之间进行信息交换的单位。把主存分成大小相等的块，主存块从 0 开始编号。访问某个主存单元时，就把这个单元所在的一个主存块调到 cache，根据程序访问的局部性特点，在随后的一段时间内，CPU 很可能要经常访问这个主存块，因为该主存块已调到 cache，所以就不需访问主存了。

cache 槽或 cache 行 (cache slot/cache line)

cache 由若干行组成，每一行中有一个用于存放主存块的槽，其大小与主存块一样，cache 行也从 0 开始编号，cache 行号就是槽号。

直接映射 cache(direct-mapped cache)

直接映射 cache 是指把主存的每一块映射到 cache 的一个固定行中。这样，主存块号和 cache 行号存在模映射关系，因此也称为模映射 (module mapping)。其映射关系为：cache 行(槽)号 = 主存块号 mod cache 行数。

全相联映射 cache (fully associative cache)

全相联映射 cache 是指每个主存块可装入到 cache 任一行的槽中。每个 cache 行的标记字段指出了该行的数据信息取自主存的哪个块。

组相联映射 cache(set-associative cache)

组相联映射 cache 结合直接映射和全相联映射的特点，将 cache 所有行分组，把一个主存块映射到特定 cache 组的任意一行中，即组间模映射、组内全映射。其映射关系为：cache 组号 = 主存块号 mod cache 组数。

多级 cache(multilevel cache)

多级 cache 是指在计算机系统中，同时使用多个层次的 cache。例如，在 CPU 和主存之间设置两级 cache：L1 cache 和 L2 cache。一般 L1 cache 是数据 cache 和代码 cache 分离的。

数据 cache(data cache)

数据 cache 是专门用来存放数据信息的高速缓冲存储器。

代码 cache(code cache)

代码 cache 是专门用来存放指令代码的高速缓冲存储器，也称为指令 cache。

分离式 cache(split cache)

分离式 cache 是指数据和指令分开存放在各自的数据 cache 和指令 cache 中。

先进先出(First-In-First-Out, FIFO)

先进先出是一种替换算法，其基本思想是，总是把最先调入 cache 的一个主存块替换出去。

最近最少用(Least Recently Used, LRU)

最近最少用是一种替换算法，其基本思想是，总是把最近最少用的一个主存块从 cache 中替换出去。

直写(write through)

直写是指每次写 cache 的同时也写主存，主存与 cache 始终保持一致性。这种方式比较


<!-- page: 199 -->

简单，能保持主存与 cache 副本的一致性，但要插入慢速的访存操作，而且有些写入过程有可能是不必要的，例如中间结果的写入操作。这种方式的中文说法较多，有全写、直写、写直达、通过式写和透写等。

## 写缓冲（write buffer）

在使用直写方式处理写操作时，为了减少每次写主存的时间，在 cache 和主存之间加一个写缓冲。这样，不必每次都写主存，而只要写到一个快速的写缓冲就行了。当发生一次写操作时，CPU 同时写 cache 和写缓冲，然后由存储控制器将写缓冲内容写到主存。

## 回写（write back）

回写是指每次写操作时，先暂时只写 cache，并用标志（dirty bit）予以注明，直到该块内容需从 cache 中替换出去时，才一次写入主存。这种方式不在写 cache 中插入慢速的写主存操作，可以保持程序运行的快速性。但在写回主存前，主存与 cache 内容不一致，引起主存内容失效。这种方式的中文说法较多，有写回、回写、一次性写等。

## 3C 模型（three C's model）

存储器层次结构中信息访问时的缺失类型以及结构的改变对这些缺失类型的影响，可以用一个模型来进行分析。该模型给出的三个缺失类型：强制缺失（compulsory miss）、容量缺失（capacity miss）、冲突缺失（conflict miss），这三个类型名称的英文首字母正好都是 C，所以称为 3C 模型。

## 强制缺失（compulsory miss）

强制缺失是指调入 cache 前第一次被用到时一定会发生缺失，此时的缺失也称为冷启动缺失（cold-start miss）。

## 容量缺失（capacity miss）

容量缺失是指由于 cache 容量的限制，使得有些主存块无法继续保存在 cache 中而造成缺失。其直接原因就是刚被替换出去的块很快又需要取回来。

## 冲突缺失（conflict miss）

冲突缺失发生在组相联或直接映射 cache 中多个块同时竞争同一个位置时。冲突缺失率与关联度有关。

## 关联度（associativity）

关联度是指一个主存块映射到 cache 中时可能存放的位置个数。显然，直接映射的关联度为 1：全相联映射的关联度最高，为 cache 总行数；N 路组相联的关联度居中，为 $N$。

## 虚拟存储器（virtual memory）

虚拟存储器是一种存储管理机制，在采用虚拟存储器的系统中，每个作业运行时，可以只装入当前执行到的一部分到内存，而让暂时执行不到的另一部分放在外存，当需要用到时再从外存装入到主存，这样使得在很小的主存空间能运行一个比它大的作业，而且用户编写程序时用到的逻辑地址空间可以比主存地址空间大。对用户来说，好像计算机系统具有一个容量很大的主存储器，称为虚拟存储器。

## 物理存储器（physical memory）

通常把主存储器称为物理存储器。

## 虚拟地址（virtual address）

通常把用户编写程序时所用的地址称为虚拟地址，或称为逻辑地址。每个程序都有一


<!-- page: 200 -->

个统一的虚拟地址空间。虚拟地址的位数确定了虚拟地址空间的大小。例如，如果虚拟地址为32位，按字节编址，则虚拟地址空间大小为 $2^{32}\mathrm{B} = 4\mathrm{GB}$ 。

## 虚页号(Virtual Page Number, VPN)

为了实现虚拟存储器，通常把虚拟地址空间划分为若干等长的块，每块称为一页(page)。操作系统在加载和运行程序时，按页为单位进行内存分配。每页按顺序进行编号，从第0页开始。虚拟地址空间所包含的页数决定了虚页号的位数，虚拟地址的高位部分为虚页号。

## 页内偏移量(page offset)

页内偏移量是指需访问的逻辑地址位于当前页的哪个位置。页面大小决定了页内偏移量的位数，例如，如果一个虚拟页的大小为 $2\mathrm{KB}(2^{11}\mathrm{B})$ ，按字节编址，那么页内偏移量就是11位。页内偏移量为虚拟地址的低位部分。

## 物理地址(physical address)

主存储器地址称为物理地址，也称为主存地址或实地址。

## 页框(page frame)

有些书把页框(有时也译为页帧)称为物理页或实页。操作系统在管理内存时，按页为单位进行内存分配。其具体做法就是，把主存储器分成固定长且比较小的存储块，称为页框，每个进程也被划分成等长的程序块。这样，对进程进行存储分配时，将一个程序块(虚拟页)装到一个可用的存储块(页框)中。

## 物理页号(Physical Page Number, PPN)

把主存空间分成固定长的页框，从0开始按顺序编号，该编号就是物理页号，也称为页框号或实页号。物理地址的高位部分是物理页号。

## 地址变换(address translation)

把程序中的虚拟地址转换为物理地址的过程称为地址变换。

## 页表(page table)

每个进程有一个页表，记录该进程的每个页存放在主存的哪个页框中，或在外存哪个地方。页表中一般有装入位、修改位、替换控制位、访问控制位和实页号等。

## 页表基址寄存器(page table base register)

每个进程有一个页表，页表在主存中的首地址被记录在一个特殊的寄存器中，这个特殊寄存器称为页表基址寄存器，简称页表寄存器。

## 有效位(valid bit)

有效位用来表示对应页是否装入主存并有效，也称为装入位。若该位为“1”，表示该页在主存中并且没有被淘汰；若该位为“0”，则说明该页不在主存，发生了“缺页”异常。

## 修改位(modify bit)

修改位用来表示对应页在主存期间是否被修改过。若该位为“1”，则表明该页已被修改过，淘汰时必须将该页写回到外存；若该位为“0”，则表明该页未被修改过，淘汰时不需要将该页写回到外存。有些作者或系统把它称为“脏位”(dirty bit)。

## 使用位(reference bit)

使用位用来表示对应页的使用情况，据此可以了解该页是最近经常被访问还是很少被访问，因而决定是否马上被替换。所以，也称为替换控制位。


<!-- page: 201 -->

## 访问方式位 (access bit)

访问方式位用来表示该页的读写权限，也称为访问控制位或存取权限位。例如，代码段所在页的访问方式一般是“执行/只读”；共享数据段所在页一般是“只读”；私有数据段所在页一般是“可读可写”。

## 缺页 (page fault)

需要访问的页不在内存中时，则发生“缺页”异常。通过检查“有效位”就可以判断是否“缺页”。

## 交换 (swapping)/页面调度 (paging)

缺页时，需要把所缺页面从外存调入主存中，这个过程称为“页面换入”；当需要从主存淘汰一页到外存时，称为“页面换出”。页面换入/换出称为交换（swapping）或页面调度（paging）。

## 按需调页 (demand paging)

按需调页指只有发生“缺页”时才换入页面。大部分现代计算机系统都使用这种策略进行存储管理。

## LRU 页 (Least Recently Used page)

LRU 页是指最近最少使用的页。通过检查“使用位”可以找到 LRU 页。

## 快表 (Translation Lookaside Buffer, TLB)

用一个特殊的 cache 来跟踪记录最近用过的页表表项，因为页表表项主要用于地址转换，所以把这种特殊的 cache 也称为转换后援缓冲器（Translation-Lookaside Buffer，TLB）。因为在 TLB 中查找页表项速度很快，所以 TLB 也被称为快表。TLB 通常很小，在高端机器中也通常不超过 $128\sim 256$ 项，一般用全相联方式，中等性能机器多用小的组相联方式。

## 分页式虚拟存储器 (paging VM)

分页式虚拟存储器的主要思想是，把主存储器分成固定长且较小的存储块（称为页框），虚拟地址空间也被划分成等长的程序块（称为页）。操作系统把当前用到的页装入到空闲的主存存储块中。所以，分页方式是按固定长的页进行分配和调度的。逻辑地址由页号和页内偏移量组成。

## 分段式虚拟存储器 (segmentation VM)

分段式虚拟存储器与分页式不同。分页式使用固定大小的块进行管理，而分段方式采用变长块的机制管理存储器。“段”是按照程序的逻辑结构划分而成的多个相对独立的部分，例如过程、子程序、数据表、阵列等。操作系统在进行虚拟空间和主存空间对应时，按程序中实际的段来分配主存空间，每个段在主存中的起始位置记录在段表中，并附以“段长”项。段表本身也是主存中的一个可再定位段。一个大程序由多个代码段和多个数据段构成。逻辑地址由段号和段内地址组成。

## 段页式虚拟存储器 (paged segmentation VM)

段页式虚拟存储器是分段和分页相结合的方式。程序按独立模块分段，段内再分成固定大小的页，主存分配时仍以页为基本单位。用段表和页表（每段一个）进行两级定位管理。逻辑地址由段地址、页地址和偏移量三个字段构成。根据段地址到段表中查阅与该段相应的页表指针，转向页表，然后根据页地址从页表中查到该页在主存中的实页号，与偏移量相加得到物理地址。


<!-- page: 202 -->

进程（process）

进程是程序在系统中的某个数据集合上的一次动态运行。当运行一个程序时，就启动了一个进程，同一个程序在不同的数据集上运行构成不同的进程。进程是操作系统进行资源分配的单位。当某一个进程占用 CPU 执行，则该进程是活动进程（active process）；否则是非活动进程（inactive process）。

管理模式（supervisor mode）

管理模式也称为系统模式、内核模式、超级用户模式、管态、内核态或核心态。在管理模式下，处理器运行内核代码，允许使用特权指令，例如停机指令、开/关中断指令、cache 冲刷指令等。

用户模式（user mode）

用户模式也称为目态、用户态。在用户模式下，处理器运行用户进程，此时不允许使用特权指令。

系统调用（system call）

系统调用用来使 CPU 从用户态转换到内核态。系统调用是一条专门的特殊指令，执行这种指令后，CPU 就调出特定的操作系统内核模块进行执行，进入内核态。在内核态下，操作系统可以执行专门的管态指令（或称特权指令，用户程序不能使用这些指令）来对一些用户进程不能访问的 CPU 状态进行读写。

异常返回（return from exception）

异常返回指令用于从操作系统内核进程返回到用户进程。通过系统调用进入操作系统内核时，需保留系统调用指令后面一条指令的地址作为返回地址，所以用异常返回指令返回用户进程时，可以根据该地址进行返回。

存储保护（protection）

虚拟存储器可以实现多道程序运行，即在一个主存物理空间中同时有多个进程共存。为避免主存中多道程序相互干扰，防止某进程出错而破坏其他进程的正确性，或某进程不合法地访问其他进程的存储区，应对每个进程进行存储保护。存储保护包含两方面：①地址越界，即访问了不该访问的区域；②访问越权，即进行了不该进行的存取操作。

7.4 常见问题解答

1. ROM 和 RAM 一样，都是随机存取存储器吗？

答：是的。虽然经常把只读存储器（ROM）和随机访问存储器（RAM）放在一起进行分类，但 ROM 的存取方式和 RAM 是一样的，都是通过对地址进行译码，选择某个单元进行读写，所以两者采用的都是随机存取方式。不过，在程序执行过程中，ROM 存储区只能读出信息，不能修改；而 RAM 区既可以读出，也可以修改信息。

2. 寄存器和主存储器都是用来存放信息的，它们有什么不同？

答：寄存器在 CPU 中，用触发器来实现，速度极快，价格高，容量只有几十个，多的机器也只有几百个，主要用来暂存指令运行时的操作数和结果。

主存储器在 CPU 之外，用 MOS 管电路实现，速度没有寄存器快，价格也比寄存器便宜，容量可以达到 GB 数量级，用来存放被启动程序的代码和数据。


<!-- page: 203 -->

3. 存取时间 $T_{\mathrm{A}}$ 就是存储周期 $T_{\mathrm{M}}$ 吗？

答：不是。存取时间 $T_{\mathrm{A}}$ 是执行一次读操作或写操作的时间，分为读出时间和写入时间。读出时间为从主存接收地址开始到数据取出为止的最短时间；写入时间是从主存接收地址开始到数据写入被写单元为止的最短时间。存储周期 $T_{\mathrm{M}}$ 是指存储器进行连续两次独立的读或写操作所需的最小时间间隔。所以存取时间 $T_{\mathrm{A}}$ 不等于存储周期 $T_{\mathrm{M}}$。通常存储周期 $T_{\mathrm{M}}$ 大于存取时间 $T_{\mathrm{A}}$。

4. 刷新和再生是一回事吗？

答：不是一回事。对某个单元的刷新和再生的操作过程是一样的，即读后恢复。但再生操作是随机的，只对所读单元进行；而刷新操作则是按顺序定时按行进行的。

5. 刷新是一个个芯片按顺序完成的吗？

答：不是。刷新按行进行，所有存储阵列的同一行中的记忆单元同时被刷新，因此仅需要行地址，不需要列地址。刷新行号由 DRAM 芯片的刷新控制电路中的刷新计数器产生。整个存储器中的所有芯片的相同行同时进行刷新。例如，若有 8 个 $1024 \times 1024 \times 4$ 的 DRAM 芯片构成一个存储器，则只需要 1024 次刷新操作就可以把整个存储器刷新一遍。

6. 主存都是由 RAM 组成的吗？

答：不是。主存是由 RAM 和 ROM 两部分组成的，它们统一编址，分别占用不同的地址空间。

7. 目前流行的内存条技术是什么？

答：目前主存常用的是基于 SDRAM（Synchronous DRAM）芯片技术的内存条，包括 DDR SDRAM、DDR2 SDRAM、DDR3 SDRAM 和 DDR4 SDRAM 等。SDRAM 是一种与当年 Intel 公司推出的芯片组中北桥芯片的前端总线同步运行的 DRAM 芯片，因此，称为同步 DRAM。

8. SDRAM 芯片中的操作由什么信号进行同步？

答：SDRAM 芯片的每一步操作都在外部系统时钟 CLK 的控制下进行，即芯片内部工作频率与外部系统时钟频率同步。

9. 连接 SDRAM 芯片的存储器总线是否支持突发传输方式？

答：是。支持突发（burst）传输方式。只要在第一次存取时给出首地址，以后按地址顺序读写即可，不再需要地址建立时间和行、列预充电时间，就能连续快速地从行缓冲中输出一连串数据。

10. SDRAM 芯片技术中的 DDR、DDR2、DDR3 等各是什么含义？

答：DDR 是 Double Data Rate 的缩写，含义是双倍数据传输率。通过芯片内部 I/O 缓冲中数据的两位预取功能，并利用存储器总线上时钟信号 CLK 的上升沿与下降沿进行两次传送，使总线上每秒传送数据的次数达到芯片内部工作频率的两倍，也是存储器总线时钟频率的两倍。

DDR2 采用 4 位预取方式，外部总线时钟频率是芯片内部工作频率的两倍，因而，总线上每秒传送数据的次数达到芯片内部工作频率的 4 倍。存储器总线上时钟信号 CLK 的上升沿与下降沿进行两次传送，因而总线上每秒传送数据的次数是总线时钟频率的两倍。

DDR3 采用 8 位预取方式，外部总线时钟频率是芯片内部工作频率的 4 倍，因而，总线上每秒传送数据的次数达到芯片内部工作频率的 8 倍。存储器总线上时钟信号 CLK 的上


<!-- page: 204 -->

升沿与下降沿进行两次传送，因而总线上每秒传送数据的次数是总线时钟频率的两倍。

11. 磁盘上信息是如何组织的？磁盘的最小编址单位是什么？

答：磁盘表面被分为许多同心圆，每个同心圆称为一个磁道。信息存储在磁道上。每个磁道被划分为若干段，又称为扇区。每个扇区存放一个记录块，每个记录块有相应的地址标识字段、数据字段和校验字段等。到磁盘上寻找数据时，只要定位到数据在哪个磁头的哪个磁道的哪个扇区。所以，扇区是磁盘的最小编址单位。

12. 一个磁盘扇区的大小总是 512B 吗？

答：不是。以前一个磁盘扇区的大小是 512B。但目前已经从传统的 512B 扇区迁移到更大、更高效的 4096B 扇区，通常称为 4K 扇区。

13. 盘面号和磁头号是一回事吗？

答：是的。硬磁盘是一个盘组，有多个盘片组成，每个盘片有两个面。每个盘面上有一个磁头，用于对该盘面上的信息进行读写。所以，磁头号就是盘面号。

14. 柱面号和磁道号是一回事吗？

答：是的。硬磁盘是一个盘组，有多个盘面组成，所有盘面上相同编号的磁道构成了一个圆柱面（但物理上这个圆柱面是不存在的），有多少磁道就形成多少圆柱面，磁道号就是圆柱面号。

15. 当一个磁道存满后，信息是在同一个盘面的下一个磁道存放，还是在同一个柱面的下一个盘面存放？

答：当一个磁道存满后，如果信息是在同一个盘面的下一个磁道存放，则需要移动磁头，因为移动磁头是机械运动，花费时间较长，且有机械磨损；如果信息在同一个柱面的下一个盘面存放，则不需移动磁头，即磁道号不变，只要给出一个相邻盘面号，通过译码电路选取该盘面的磁头就可以读写了，几乎没有延迟，也没有机械运动。因此，磁盘地址形式为磁道号（柱面号）、磁头号（盘面号）、扇区号。

16. 高速缓存 (cache) 对程序员来说是透明的吗？

答：cache 的访问过程对程序员来说是透明的。执行一条指令时，CPU 需要到主存取指令，有些指令还要访问主存来取操作数或将运算结果保存到主存。采用 cache 的计算机系统中，总是先到 cache 去访问指令或数据，当 cache 缺失时才到主存去访问。这个过程是 CPU 在执行指令过程中自动完成的。程序员不需要知道要找的指令和数据在不在 cache 中、在 cache 的哪一行中，也不需要知道 cache 的访问过程，只要在指令中给定存储单元地址（即变量的指针或指令的标号）就行了。事实上，现代计算机都采用虚拟存储器机制，所以，在编译链接生成的目标代码中，指令给出的地址还不是真正的主存单元地址，而是一个虚拟地址（逻辑地址），操作系统需要为程序分配主存空间，以页或段为单位把程序装载到主存中，并由 CPU 把逻辑地址转换为真正的主存地址（物理地址）。

17. 主存和 cache 之间按主存块为单位传送数据时，是否主存块越大越好？

答：不是。主存块大可以充分利用程序访问的空间局部性特点，使得一个比较大的主存局部空间被一起调入 cache 中，因而可以增加命中机会。但是，主存块不能太大，主要原因有两个：①主存块变大，使得缺失损失也变大，因为需要花费更多时间从主存读一个较大的块；②主存块变大，则 cache 行数变少，因而需要替换的可能性增加，从而导致命中的可能性变小。


<!-- page: 205 -->

18. 指令和数据都是放在同一个 cache 中的吗？

答：现代计算机系统中，一般采用多级 cache 系统。CPU 执行指令时，先到速度最快的一级 cache（L1 cache）中寻找指令或数据，找不到时再到速度次快的二级 cache（L2 cache）中找……最后到主存中找。对于一级 cache，指令和数据一般分开存放，分别称为 L1 Data Cache 和 L1 Code Cache，而对于二级以上的 cache，其指令和数据是放在一起的。

19. cache 可以做在 CPU 芯片里面吗？

答：可以。早期的计算机，其 cache 是做在 CPU 芯片外的。但随着 CPU 芯片技术的提高，cache 可以做在 CPU 芯片里面了。从逻辑上来说，cache 是位于 CPU 和主存之间的部件，但在物理上，cache 被封装在 CPU 芯片内。目前，一级 cache、二级 cache 甚至三级 cache 都可以封装在 CPU 芯片中。

20. 直接映射方式下是否需要考虑替换方式？为什么？

答：无需考虑。因为在直接映射方式下，一个给定的主存块只能映射到一个固定的 cache 槽中，所以，在对应 cache 槽已有一个主存块的情况下，新的主存块毫无选择地把原先已有的那个主存块替换掉，因而无需考虑替换算法。

21. 在 CPU 和主存间加入了多个 cache，计算机总存储量就增加了，对吗？

答：不对。虽然 cache 是存储器，具有几百 KB 甚至几 MB 的容量，但因为它存放的是主存信息的副本，所以并不能增加系统的存储容量。

22. 怎样保证 CPU 要找的指令和数据大都能在 cache 中访问到呢？

答：根据程序访问的局部性特点可知，不管是访问指令还是数据，CPU 在执行程序的过程中，若某个地址在 $T$ 时刻被访问，则该地址及其邻近地址在 $T + \Delta t$ 时间段内很可能也被访问。因而，在访问到某个内存地址时，把该地址及其邻近的内存单元内容（就是一个主存块，block）一起复制到 cache 中。这样，在接下来的一段时间内，CPU 所要访问的指令或数据基本上能在 cache 中找到了。

23. CPU 要找的指令和数据都能在 cache 中访问到吗？为什么？

答：不能。指令/数据在第一次被访问时，肯定不在 cache 中，因而在 cache 中访问不到。此时，就会把所访问的指令/数据所在的主存块从主存取到 cache 中，这样只要这个主存块不被其他主存块替换出来，以后再访问这个数据/指令或者同一块中其他数据/指令时，就能在 cache 中命中了。但是，随着程序的执行，CPU 所访问的地址区域会移到另外的主存块，由于 cache 容量的限制，当新的主存块调入 cache 时，原来在 cache 中的主存块很可能被新的主存块替换出来。如果替换出来后，CPU 又要对其进行访问，那么，CPU 在 cache 中肯定找不到。所以，CPU 要找的指令和数据不可能总在 cache 中访问到。

24. 发生取指令缺失时的处理过程是什么？这由硬件完成还是软件完成的？

答：每条指令执行的第一步是取指令。若在 cache 中取当前指令时发生缺失，则处理器必须按如下步骤完成：①把程序计数器的值恢复到当前指令的地址，然后通过总线中的地址线送到存储器中的地址缓冲器中，以便存储器对地址译码。②控制存储器执行一次读操作（若一个主存块只有一条指令，则一次读操作读一条指令即可；若一个主存块占用多条指令，则控制一次读出多条指令或读若干次），对主存的访问要通过总线完成，一次总线事务完成一次读操作。③读出的指令写到 cache 中，并把主存地址的高位写入标记字段，最后设置有效位。④重新执行当前指令的第一步操作，即取指令，这次在 cache 中取指令时便能


<!-- page: 206 -->

命中。

显然，cache 缺失不是内部异常，更不是外部中断，不会引起对当前正在执行程序的“中断”，因而不会调出操作系统内核程序来处理 cache 缺失，即上述处理过程不是由软件完成的，而是由 CPU 这个硬件完成的。

25. 引入 cache 后，CPU 的数据通路和控制部件要增加哪些功能和相关的电路？

答：在指令执行过程中，CPU 必须从存储器取指令，有些指令还要从存储器取操作数，或把结果写到存储器中。CPU 总是先到 L1 cache 中寻找，找不到再从 L2 以上的 cache 或主存中找。所以，在指令执行过程中，控制部件必须能够检测访问有没有命中。实现这个功能只要用若干比较器和一些门电路即可。若命中，则直接在 cache 中访问即可；若缺失，则处理器需要进行一系列的处理，包括：使当前指令暂时停止执行，并冻结所有寄存器，然后用一个专门的控制器控制从 L2 以上的 cache 或主存中取出当前访问地址所在的一个主存块送到 cache 中，并设置有效位和标记 (tag) 信息，最后重新从暂停执行的时钟周期开始执行指令。

26. 写操作处理和读操作处理有什么不同？

答：因为读操作不改变 cache 中数据的值，所以读操作时的缺失处理比较简单。只要把主存块从内存装入 cache 中即可。而写操作时会改变 cache 中数据的值，造成 cache 数据和主存数据的不一致。因此，要有相应的写策略来解决这种不一致性。

27. cache 访问缺失对指令的执行有影响吗？有怎样的影响？

答：cache 访问缺失对指令的执行有很大影响，会大大延长指令的执行时间。延长多少由缺失损失确定，若从 L2 cache 取，则一般需要 $5\sim 10$ 个时钟周期；若从主存取，则需要 $25\sim 100$ 个周期。执行一条指令时的缺失情况有以下几种可能：①取指令时缺失。此时从 L2 以上 cache 或主存取出指令或者取出指令所在主存块，并存入 L1 code cache，然后再开始重新执行指令。②读数据时缺失。此时，从 L2 以上 cache 或主存取出数据或者数据所在主存块，并存入 L1 data cache，然后从取数那个时钟周期开始执行指令。③写数据时缺失。此时需要根据相应的写策略来决定是当时就更新主存的数据 (write through) 还是在主存块被替换时更新主存的数据 (write back)。存数操作结束后，指令也就执行结束了。

如果一条指令执行过程中，既发生取指令缺失又发生取数或存数缺失，那么这条指令的执行将要延长多个缺失损失的时间。也就是说，可能会延长几十到几百个时钟周期。在流水线方式下，会大大阻塞流水线的执行。

28. 虚拟存储器的大小是否等于磁盘的容量加上内存的容量？

答：不是。虚拟存储器本身只是一个概念，是一种存储管理机制，使用这种机制使得程序员编写程序时，好像计算机内部有一个极大的存储器，程序在这个极大的存储器中运行，而不受内存大小的限制。实际上这个存储器在物理上是不存在的，因此称为虚拟存储器。虚拟存储器的大小就是虚拟地址（或称逻辑地址）空间的大小，它由虚拟（逻辑）地址的位数决定，与系统中所安装的磁盘容量和内存容量没有直接的关系。

29. 在存储器层次结构中，cache-主存和主存-辅存这两个层次有何异同点？

答：这两个层次在以下几个方面有相同的地方：①都是基于程序访问的局部性特点，把一块相邻的局部信息从慢速存储器复制到快速存储器；②都必须考虑慢速存储器和快速存储器之间的映射问题；③当需要在快速存储器中装入新的块面对应位置已满时，都需要


<!-- page: 207 -->

考虑把哪一块从快速存储器中替换出来；④当在快速存储器中找不到信息时，都要从慢速存储器装入该信息所在块到快速存储器中。

因为这两个层次所处的位置和引入的目的不同，所以它们之间也存在许多不同之处：①位置不同。cache最靠近CPU，辅存最远离CPU，CPU可以直接访问cache和主存，但不能直接访问辅存，辅存和主存直接交换数据。②目的不同。在CPU和主存之间加入cache，目的是为了加快CPU访问信息的速度；而在主存-辅存层次采用虚拟存储器机制是为了使程序员写程序时不受内存容量的限制，即扩大系统的存储容量。③交换的信息块大小不同。在cache-主存层次，交换的信息块称为主存块(block)，一般大小为 $8\mathrm{B}\sim 128\mathrm{B}$；而主存-辅存层次，交换的信息块称为页(page)，一般大小为 $4\mathrm{KB}\sim 64\mathrm{KB}$。随着技术的发展，块大小也可能会变化，但它们之间在数量级上差别很大。因为虚拟页的缺失损失比cache缺失损失大得多，所以页太小会影响命中率从而极大降低系统效率。④缺失处理不同。在cache-主存层次，缺失处理由处理器(硬件)实现；而在主存-辅存层次，则由操作系统(软件)实现。⑤映射方式不同。在cache-主存层次，可根据不同的情况选择使用直接、全相联或组相联方式，映射关系完全由硬件实现，使用cache行中的标记(tag)字段来描述；而在主存-辅存层次，则都采用全相联方式，映射关系由操作系统实现，使用页表来描述映射关系。⑥写策略不同。在cache-主存层次，可以采用直写和回写两种策略：但在主存-辅存层次，则都采用回写策略。因为，如果采用直写，每次写操作都要访问磁盘，这样的开销是不能容忍的。