直接映射#

主存中的每个数据块只能映射到 Cache 中唯一一个固定的行。

• 映射关系：$\text{Cache 行号} = \text{主存块号} \bmod \text{Cache 总行数}$
• 优缺点：硬件设计最简单，地址变换速度快；但由于映射关系固定，极易产生块冲突，导致 Cache 命中率下降。

全相联映射#

主存中的任意数据块可以装入 Cache 中的任意一行。

• 映射关系：主存块可以放置在 Cache 的任何空闲行中。
• 优缺点：冲突概率低，Cache 空间利用率和命中率高；但由于需要同时比对 Cache 所有行的标记，硬件电路复杂，成本高。

组相联映射#

将 Cache 所有行分为若干个大小相同的“组”，主存块先通过模运算映射到唯一确定的组，但在该组内部的各行之间可以任意放置（即“组间直接映射，组内全相联映射”）。

• 映射关系：$\text{Cache 组号} = \text{主存块号} \bmod \text{Cache 总组数}$
• 优缺点：冲突概率低于直接映射，硬件实现难度与成本又低于全相联映射，是现代处理器中最常用的折中方案。

核心替换算法#

当 Cache 对应位置已满，而 CPU 又需要调入新数据块时，必须腾出某个已有的旧数据块，这由替换算法决定：

• 随机算法：随机选择一个 Cache 行进行替换。实现简单，但未考虑程序访问规律，命中率低。
• 先进先出算法：优先替换最先调入 Cache 的数据块。同样未考虑局部性规律，可能出现“贝拉迪异常”现象。
• LRU 算法：优先替换近期最长一段时间未被访问过的数据块。该算法高度契合时间局部性原理，是实际系统和考试题中很常见的近似最优替换策略，但不保证在所有访问序列下命中率最高。
• 最不经常使用算法：优先替换历史上累计访问次数最少的数据块。

LRU 模拟技巧

考试中若要求手动模拟 LRU 替换过程，只需为每个 Cache 行维护一个“新鲜度”计数器或直接记录访问顺序，每次替换时挑出距离当前时刻最久未被触及的行即可。

Cache 写操作策略#

当 CPU 执行写操作时，若 Cache 命中，为了保证 Cache 与主存中的数据一致性，通常采用以下写策略：

• 全写法：在写 Cache 的同时，将数据同步写入主存中。该方法能够始终保证主存与 Cache 数据绝对一致，控制简单；但会引起频繁的主存写操作，降低了系统的整体写入效率。
• 写回法：写操作时仅修改 Cache 对应的行，并为该行设置一个脏位标记为 1。只有当该 Cache 行在未来被替换出 Cache 时，硬件才根据脏位状态决定是否将修改过的数据写回主存。该方法显著减少了主存写次数，但控制逻辑复杂，且在写回前主存与 Cache 数据存在暂时不一致。

若写操作时 Cache 缺失，也有两种处理策略：

• 写分配法：先将主存中的目标块调入 Cache，然后修改 Cache。常与写回法配合使用。
• 非写分配法：直接在主存中修改数据，不将数据块调入 Cache。常与全写法配合使用。

Q1 (南阳理工学院 2024-2025 学年第 2 学期期末试卷（C 卷） 填空题)#

题干：若某存储器存储周期为 $250\text{ ns}$，每次读出 $16$ 位，该存储器的数据传输速率是________。

解析： 数据传输速率即为存储带宽。计算公式为： $\text{数据传输速率} = \frac{\text{每次读出位数}}{\text{存储周期}}$ 已知每次读出 16 位，即 $16\text{ bit} = 2\text{ B}$。存储周期为 $250\text{ ns} = 250 \times 10^{-9}\text{ s}$。 代入数据计算： $\text{数据传输速率} = \frac{2\text{ B}}{250 \times 10^{-9}\text{ s}} = \frac{2}{250} \times 10^9 \text{ B/s} = 0.008 \times 10^9 \text{ B/s} = 8 \times 10^6 \text{ B/s} = 8 \text{ MB/s}$ 若以位为单位，则是 $64\text{ Mbit/s}$。一般默认以字节每秒（B/s）为单位回答。

答案：$8\text{ MB/s}$（或 $8 \times 10^6\text{ B/s}$）。

Q2 (2022-2023-2考试 判断题)#

题干：半导体 RAM 信息可读可写，且断电后仍能保持记忆。（ ）

解析： 半导体随机存储器 RAM 是易失性存储器，断电后其内部存储的数据会全部丢失。断电不丢失数据的是非易失性存储器（如 ROM、Flash）。

答案：错。

Q3 (2022-2023-2考试 判断题)#

题干：双端口存储器可以同时访问同一区间、同一单元。（ ）

解析： 双端口存储器具有两套相互独立的读写控制线路，允许在同一时刻访问主存。只要两个端口不是同时对同一个单元进行写入操作，就允许同时访问。

答案：对。

Q4 (南阳理工学院 2024-2025 学年第 2 学期期末试卷（C 卷） 选择题)#

题干：以下哪种存储方式将数据的最高位有效字节（MSB）存储在最低地址内存单元？（ ）

A. 大端方式 B. 小端方式 C. 中端方式 D. 随机方式

答案：A

解析：

• A [正确]：大端方式将多字节数据的高位字节（最高有效字节）存放在低物理地址单元中，而将低位字节存放在高物理地址单元中。这与人类通常的阅读书写顺序（从左到右）是一致的。
• B [错误]：小端方式与大端方式相反，它将多字节数据的低位字节（最低有效字节）存放在低物理地址单元中，而将高位字节存放在高物理地址单元中。
• C [错误]：在计算机系统结构中没有所谓的“中端方式”。
• D [错误]：多字节数据的物理字节存放是有固定逻辑和物理规则的，不可能采用“随机方式”存储。

Q5 (计算机组成原理2020-2021第2学期A 选择题)#

题干：某计算机字长为 32 位，按字节编址，采用小端方式存放数据。假定有一个 double 型变量，其机器数表示为 1122 3344 5566 7788H，存放在 0000 8040H 开始的连续存储单元中，则存储单元 0000 8046H 中存放的是（ ）。

A. 22H B. 33H C. 77H D. 66H

答案：A

解析：

• A [正确]：double 型变量占 8 字节（64 位）。机器数表示为 1122 3344 5566 7788H，其字节从高到低依次为 11H最高有效字节至 88H最低有效字节。采用小端方式存储时，低物理地址存放低位字节，高物理地址存放高位字节。因此，从起始地址 0000 8040H 开始的连续 8 字节单元的存放数据为：

  • 0000 8040H：88H
  • 0000 8041H：77H
  • 0000 8042H：66H
  • 0000 8043H：55H
  • 0000 8044H：44H
  • 0000 8045H：33H
  • 0000 8046H：22H
  • 0000 8047H：11H

  由上可知，存储单元 0000 8046H 存放的是 22H。

• B [错误]：33H 存放于地址 0000 8045H 中。

• C [错误]：77H 存放于地址 0000 8041H 中。

• D [错误]：66H 存放于地址 0000 8042H 中。

Q6 (计算机组成原理2020-2021第二学期B 简答题)#

题干：某存储容量为 256MB 的存储器由若干个 4M×8 的 DRAM 芯片构成，则 DRAM 芯片的地址引脚和数据引脚的数量是？（ ）

解析：

1. DRAM 芯片规格为 $4\text{M} \times 8\text{位}$。
2. 数据引脚数由芯片的位宽决定，位宽为 8 位，因此数据引脚数为 8 根。
3. 芯片字数为 $4\text{M} = 2^{22}$ 个存储单元。如果采用普通的寻址方式，地址线需要 22 根。但 DRAM 芯片为了减少引脚数，普遍采用地址引脚复用技术，行地址和列地址分时复用相同的引脚。因此实际的地址引脚数减半： $\text{DRAM 地址引脚数} = \frac{22}{2} = 11\text{ 根}$

答案：地址引脚 11 根，数据引脚 8 根。

Q7 (计算机组成原理2020-2021第二学期B 选择题)#

题干：某计算机主存容量为 64KB，其中 ROM 区为 4KB，其余为 RAM 区，按字节编址。现要用 2K×8 位的 ROM 芯片和 4K×4 位的 RAM 芯片来设计该存储器，需要上述规格的 ROM 芯片数和 RAM 芯片数分别是（ ）。

A. 1, 15 B. 2, 15 C. 1, 30 D. 2, 30

答案：D

解析：

• A [错误]：ROM 芯片数与 RAM 芯片数计算均错误。
• B [错误]：RAM 芯片数计算错误，仅计算了字扩展需求（15），忽略了位扩展需求（应乘以 2）。
• C [错误]：ROM 芯片数计算错误。ROM 区目标容量为 4KB，使用 $2\text{K} \times 8$ 位（即 2KB）芯片，若仅用 1 片，总容量只有 2KB，达不到 ROM 区容量需求。
• D [正确]：
  1. ROM 区芯片计算： ROM 区总容量为 $4\text{KB} = 4\text{K} \times 8$ 位。使用规格为 $2\text{K} \times 8$ 位的 ROM 芯片，只需进行字扩展。需要的 ROM 芯片数量为： $\text{ROM 芯片数} = \frac{4\text{KB}}{2\text{K} \times 8\text{位}} = \frac{4\text{K} \times 8\text{位}}{2\text{K} \times 8\text{位}} = 2\text{ 片}$
  2. RAM 区芯片计算： 主存总容量为 64KB，ROM 区占 4KB，则 RAM 区容量为 $64\text{KB} - 4\text{KB} = 60\text{KB} = 60\text{K} \times 8$ 位。 使用规格为 $4\text{K} \times 4$ 位的 RAM 芯片进行字位联合扩展。字扩展倍数为 $\frac{60\text{K}}{4\text{K}} = 15$ 倍，位扩展倍数为 $\frac{8\text{位}}{4\text{位}} = 2$ 倍。 因此所需的 RAM 芯片总数为： $\text{RAM 芯片数} = 15 \times 2 = 30\text{ 片}$ 综上，需要的 ROM 芯片为 2 片，RAM 芯片为 30 片。

Q8 (2022-2023-2考试 简答题)#

题干：用一个 512K×8 位的 Flash 存储芯片组成一个 4M×32 位的半导体只读存储器，存储器按字编址，试回答以下问题： (1) 共需要几片这样的存储芯片？ (2) 该存储器的数据线和地址线数分别是多少根？

解析：

1. 芯片数计算： $\text{芯片总片数} = \left(\frac{4\text{M}}{512\text{K}}\right) \times \left(\frac{32\text{位}}{8\text{位}}\right) = 8 \times 4 = 32\text{ 片}$
2. 数据线与地址线计算：
   • 数据总线宽度与存储器的数据位数一致，为 32 位，因此数据线数为 32 根。
   • 存储器按字编址，其字数为 $4\text{M} = 2^{22}$。因此，寻址这 $4\text{M}$ 个字需要 22 根地址线。

答案：(1) 需要 32 片。(2) 数据线为 32 根，地址线为 22 根。

Q9 (计算机组成原理2020-2021第二学期B 选择题)#

题干：计算机的存储器采用分级方式是为了（ ）。

A. 方便编程 B. 解决容量、速度、价格三者之间的矛盾 C. 保存大量数据方便 D. 操作方便

答案：B

解析：

• A [错误]：方便编程是采用虚拟存储器等软硬件协同管理后的效果之一，从根本上解决存储体系矛盾才是采用分级存储体系的核心出发点。
• B [正确]：单一存储介质无法同时实现超高速度、超大容量和极低成本。采用“寄存器 - Cache - 主存 - 外存”的多级层次结构，利用了程序的局部性原理，通过软硬件的协同，成功在整体上获得了接近最高速介质的速度、接近最廉价介质的容量以及极低的平均成本，解决了这三者的矛盾。
• C [错误]：保存大量数据可以直接使用低速、大容量的辅存，无需设计复杂的 Cache 等高速多级分级结构。
• D [错误]：操作方便主要依靠操作系统的接口实现，并不是物理层面上采用分级存储的主要物理动因。

Q10 (南阳理工学院 2024-2025 学年第 2 学期期末试卷（C 卷） 判断题)#

题干：单体多字存储器中，每个存储单元存储多个字。（ ）

解析： 单体多字存储器是一种并行主存系统。它的特点是只有一个存储体，但每个存储单元的字长是普通存储字长的数倍（例如包含 4 个字）。CPU 每次访问时，可以同时读出或写入多个字的数据，从而在空间上并行提高了存储带宽。

答案：对。

Q11 (计组2019秋18级测试 答案.md 综合分析题)#

题干：假设主存容量为 512MB，Cache 容量为 4KB，每个字块为 16 个字，每个字为 32 位。请回答以下问题： (1) Cache 可容纳多少块，其地址为多少位？ (2) 主存可容纳多少块，其地址为多少位？ (3) 在四路组相联（即 Cache 每组包含 4 个块）映射方式下，请画出主存地址各字段的位数。

解析： 首先明确基本物理单位：

• 每个字为 32 位 = 4 字节（B）。
• 每个字块包含 16 个字 = $16 \times 4\text{ B} = 64\text{ B}$。
• Cache 容量为 $4\text{KB} = 4096\text{ B}$。
• 主存容量为 $512\text{MB} = 512 \times 2^{20}\text{ B} = 2^{29}\text{ B}$。

(1) Cache 参数：

• Cache 的块数 = $\frac{\text{Cache 容量}}{\text{块大小}} = \frac{4\text{KB}}{64\text{ B}} = 64\text{ 块}$。
• Cache 容量为 $4\text{KB}$，按字节寻址需要 12 位地址（因 $2^{12} = 4096$）。 (2) 主存参数：
• 主存的块数 = $\frac{\text{主存容量}}{\text{块大小}} = \frac{512\text{MB}}{64\text{ B}} = 8\text{M 块} = 2^{23}\text{ 块}$。
• 主存容量为 $512\text{MB}$，按字节寻址需要 29 位地址（因 $2^{29} = 512\text{M}$）。 (3) 四路组相联映射下的地址字段划分：
• Cache 总块数为 64 块。因为是四路组相联，每组有 4 块，则 Cache 的总组数 = $\frac{64}{4} = 16\text{ 组} = 2^4\text{ 组}$。
• 组地址（Index）需要 4 位。
• 块内偏移地址（Offset）由块大小决定，块大小为 64 B，按字节寻址需要 6 位（因 $2^6 = 64$）。
• 主存字块标记（Tag）的位数 = 主存地址总位数 - 组地址位数 - 块内偏移位数 = $29 - 4 - 6 = 19\text{ 位}$。

答案： (1) Cache 可容纳 64 块，地址为 12 位。 (2) 主存可容纳 $8\text{M}$（即 $2^{23}$）块，地址为 29 位。 (3) 主存地址各字段划分如下：

Q12 (2022-2023-2考试 计算题)#

题干：某计算机的 Cache 由 64 个存储块构成，采用四路组相联映射方式，主存包含 4096 个存储块，每块由 128 个字组成，访问地址为字地址。 (1) 主存地址和 Cache 地址各有多少位？ (2) 按照题干条件中的映射方式，列出主存地址的划分情况，并标出各部分的位数。

解析： 注意此题中访问地址为字地址，即寻址的基本单位是“字”，而不是“字节”。

• 块大小 = 128 个字。
• Cache 块数 = 64 块。
• Cache 容量（字） = $64 \times 128 = 8192\text{ 字} = 2^{13}\text{ 字}$，因此 Cache 地址为 13 位。
• 主存块数 = 4096 块 = $2^{12}\text{ 块}$。
• 主存容量（字） = $4096 \times 128 = 2^{12} \times 2^7 = 2^{19}\text{ 字}$，因此主存地址为 19 位。

(2) 地址字段划分：

• 块内地址（Offset）由块大小决定。块大小为 128 字，字地址寻址需要 7 位（因 $2^7 = 128$）。
• Cache 组数 = $\frac{64\text{ 块}}{4\text{ 块/组}} = 16\text{ 组} = 2^4\text{ 组}$，因此组地址（Index）为 4 位。
• 主存标记（Tag）的位数 = 主存地址位数 - 组地址位数 - 块内地址位数 = $19 - 4 - 7 = 8\text{ 位}$。

答案： (1) 主存地址为 19 位，Cache 地址为 13 位。 (2) 主存地址划分如下：

Q13 (计算机组成原理2020-2021第二学期B 选择题)#

题干：计算机存储系统中的高速缓存采用直接映射策略时，高速缓存控制器如何确定是否命中（ ）。

A. 高速缓存中行标志与 CPU 给出物理地址的高位一致 B. 高速缓存中与 CPU 给出的物理地址中组索引一致的行中存在行标志与物理地址高位一致的行，且该行有效 C. 高速缓存中与 CPU 给出的物理地址中行索引一致的行中的行标志与物理地址的高位一致，且该行有效 D. 高速缓存中存在行标志与 CPU 给出物理地址的高位一致的行，且该行有效

答案：C

解析：

• A [错误]：直接映射中主存块只能映射到唯一的 Cache 行中。仅仅行标记与高位一致是不够的，还必须要求该 Cache 行的有效位为 1。
• B [错误]：直接映射按行索引定位，不需要使用组索引。组索引是组相联映射方式所采用的字段。
• C [正确]：在直接映射策略中，主存中的每一块均映射到 Cache 的唯一固定行中。当 CPU 给出一个访存物理地址时，Cache 控制器首先根据地址中的行索引字段，直接定位到唯一的 Cache 行。接着，控制器需要检查两点：第一，该 Cache 行中的标记（行标志）是否与物理地址中的高位标记（Tag）字段完全一致；第二，检查该行的有效位（Valid Bit）是否为 1。只有当有效位为 1 且标记完全匹配时，才判定为 Cache 命中。
• D [错误]：此项属于全相联映射方式下的命中判断逻辑，在直接映射下，不需要检索所有的行，只需直接定位并比较那一行即可。

Q14 (南阳理工学院 2024-2025 学年第 2 学期期末试卷（C 卷） 计算题)#

题干：假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访问 $2000$ 次，其中访问 Cache 缺失（未命中）$50$ 次，则 Cache 的命中率是多少？

解析： Cache 命中率 $H$ 的计算公式为： $H = \frac{\text{命中次数}}{\text{总访问次数}} = \frac{\text{总访问次数} - \text{未命中次数}}{\text{总访问次数}}$ 代入数据计算： $H = \frac{2000 - 50}{2000} = \frac{1950}{2000} = 97.5\%$

答案：$97.5\%$。

Q15 (南阳理工学院 2024-2025 学年第 2 学期期末试卷（C 卷） 判断题)#

题干：虚拟存储器对应用程序员不透明，对系统程序员透明。（ ）

解析： 在计算机组成原理和操作系统中，“透明”是指“客观存在但无需关心、看不见”。

• 虚拟存储器由硬件与操作系统自动管理。应用程序员在编写程序时，可以直接使用大范围的虚拟地址，无需操心物理内存的调入调出细节，因此虚拟存储器对应用程序员是透明的。
• 系统程序员需要编写操作系统的页表管理、页面置换算法和中断处理程序，必须直接控制虚拟存储器的物理运作，因此对系统程序员是不透明的。

答案：错。

4.1 名词解释#

解释下列名词：

存取时间、存取周期、存储器带宽、存储单元、边界对齐的数据存放、大端存储、小端存储、静态存储器、动态存储器、刷新、刷新周期、字扩展、位扩展、多体交叉存储器、高速缓冲存储器、双端口存储器、相联存储器、时间局部性、地址映射、直接相联映射、全相联映射、组相联映射、命中率、虚拟存储器、页框号、页表（通常称慢表）、页表项、TLB（通常称快表）、LRU 算法、LFU 算法、Cache 一致性、写回法、写穿法。

4.2 选择题（考研真题）#

1
struct record {
2
    short x1;
3
    int x2;
4
} a;

1
for (i = 0; i <= 9; i++) {
2
    temp = 1;
3
    for (j = 0; j <= i; j++)
4
        temp *= a[j];
5
    sum += temp;
6
}

4.3 简答题#

(1) 计算机系统中采用层次化存储体系结构的目的是什么？
(2) 为什么在存储器芯片中设置片选输入端？
(3) 动态 MOS 存储器为什么要刷新？如何刷新？
(4) 试述多体交叉存储器的设计思想和实现方法。
(5) 为什么说 Cache 对程序员是透明的？
(6) 直接相联映射方式下为什么不需要使用替换算法？
(7) 为什么要考虑 Cache 的一致性？
(8) 替换算法有哪几种？它们各有何优缺点？

4.4#

对于 32KB 容量的存储器，若按 16 位字编址，其地址寄存器应是多少位？数据寄存器是多少位？

4.5#

用 4 个 $32\text{K}\times 8$ 位 SRAM 存储芯片可设计出哪几种不同容量和字长的存储器？画出相应设计图并完成与 CPU 的连接。

4.6#

用 $32\text{K}\times 8$ 位 RAM 芯片和 $64\text{K}\times 4$ 位 ROM 芯片设计 $256\text{K}\times 8$ 位存储器。其中，从 30000H 到 3FFFFH 的地址空间为只读存储区，其他为可读、可写存储区。完成存储器与 CPU 的连接。

4.7#

某计算机字长为 16 位，主存容量为 $128\text{K}\times 16$ 位，请用 $16\text{K}\times 8$ 位的静态 RAM 芯片和 $32\text{K}\times 16$ 位的 ROM 芯片为该机设计一个主存储器。要求 18000H ~ 1FFFFH 为 ROM 区，其余为 RAM 区。画出该存储器结构及其与 CPU 连接的框图。

4.8#

设有某动态 RAM 芯片，容量为 $64\text{K}\times 1$ 位，除电源线、接地线和写使能控制线外，该芯片的最小引脚数量是多少？

4.9#

用 $64\text{K}\times 1$ 位的 DRAM 芯片构成 $1\text{M}\times 8$ 位的存储器，若采用异步刷新，每次刷新间隔不超过 2ms，则产生刷新信号的间隔时间是多少？假设读写周期为 $0.5\mu\text{s}$，若采用集中刷新方式，则存储器刷新一遍最少要用多少个读写周期？CPU 的死时间为多少？

4.10#

用 $16\text{K}\times 1$ 位的 DRAM 芯片构成 $64\text{K}\times 8$ 位的存储器，设存储器的读写周期为 $0.5\mu\text{s}$，要使 CPU 在 $1\mu\text{s}$ 内至少访问存储器一次，采用哪种刷新方式比较合适？若每次刷新间隔不超过 2ms，该方式下刷新信号的产生周期是多少？

4.11#

设 Cache 的容量为 $2^{14}$ 块，每块 4 个字节，主存按字节编址，其中有下表所示的数据（地址和数据均采用十六进制表示）。

将主存中这些数据装入 Cache 后，Cache 各块中的数据内容及相应的标志是什么？
(1) 全相联映射；
(2) 直接相联映射；
(3) 四路组相联映射。

4.12#

某计算机的 Cache 由 64 个存储块构成，采用四路组相联映射方式，主存包含 4096 个存储块，每块由 128 个字组成，访问地址为字地址。
(1) 主存地址和 Cache 地址各有多少位？
(2) 按照题干条件中的映射方式，列出主存地址的划分情况，并标出各部分的位数。

4.13#

某计算机的主存容量为 4MB，Cache 容量为 16KB，每块包含 8 个字，每字为 32 位，映射方式采用四路组相联。设 Cache 的初始状态为空，CPU 依次从主存第 0, 1, 2, …, 99 号单元读出 100 个字（每次读一个字），并重复此操作 10 次，替换算法采用 LRU 算法。
(1) 求 Cache 的命中率。
(2) 若 Cache 比主存快 10 倍，分析采用 Cache 后存储访问速度提高了多少。

4.14#

假定某数组元素按行优先顺序存放在主存中，则在以下两段伪代码 A 和 B 中，分析下列问题。
(1) 两段代码中对数组访问的时间局部性和空间局部性。
(2) 变量 sum 的时间局部性和空间局部性。
(3) for 循环体对指令访问的时间局部性和空间局部性。

代码 A：

1
int sum_array_A(int a[M][N]) {
2
    int i, j, sum = 0;
3
    for (i = 0; i < M; i++)
4
        for (j = 0; j < N; j++)
5
            sum += a[i][j];
6
    return sum;
7
}

代码 B：

1
int sum_array_B(int a[M][N]) {
2
    int i, j, sum = 0;
3
    for (i = 0; i < N; i++)
4
        for (j = 0; j < M; j++)
5
            sum += a[j][i];
6
    return sum;
7
}

4.15#

假定主存地址为 32 位，按字节编址，指令 Cache 和数据 Cache 与主存之间均采用 8 路组相联映射、写穿策略和 LRU 替换算法，主存块大小为 64B，数据区容量各为 32KB。开始时 Cache 均为空。请回答下列问题。
(1) Cache 每一行中标记、LRU 位各占几位？是否有修改位？
(2) 有如下 C 语言程序段：

1
for (k = 0; k < 1024; k++)
2
    s[k] = 2 * s[k];

若数组 s 及其变量 k 均为 int 型，int 型数据占 4B，变量 k 分配在寄存器中，数组 s 在主存中的起始地址为 0080 00C0H，则该程序段执行过程中，访问数组 s 的数据 Cache 缺失次数为多少？
(3) 若 CPU 最开始的访问操作是读取主存单元 0001 0003H 中的指令，简要说明从 Cache 中访问该指令的过程，包括 Cache 缺失处理过程。

4.16#

已知计算机 M 字长为 32 位，按字节编址，采用请求调页策略的虚拟存储管理方式，虚拟地址 32 位，页面大小为 4KB；数据 Cache 采用 4 路组相联映射方式，数据区大小为 8KB，主存块大小为 32B。现有 C 语言程序段如下：

1
int a[24][64];
2
for (i = 0; i < 24; i++)
3
    for (j = 0; j < 64; j++)
4
        a[i][j] = 10;

已知二维数组 a 按行优先存放，在虚拟地址空间中分配的起始地址为 0042 2000H，sizeof(int)=4。假定在 M 上执行上述程序段之前数组 a 不在主存，且在该程序执行过程中不会发生页面置换。请回答下列问题：
(1) 数组分布在几个页面中？对于数组 a 的访问，会发生几次缺页异常？页故障地址各是什么？
(2) 不考虑变量 i 和 j，该程序段的数据访问是否具有时间局部性？为什么？
(3) 计算机 M 的虚拟地址 ($A_{31} \sim A_0$) 中哪几位用作块内地址？哪几位用作 Cache 组号？a[1][0] 的虚拟地址是多少？其所在主存块对应的 Cache 组号是多少？
(4) 数组 a 占用多少主存块？假设上述程序段执行过程中数组 a 的访问不会和其他数据发生 Cache 访问冲突，则数组 a 的 Cache 命中率是多少？若将循环中 i 和 j 的次序按如下方式调换：

1
for (j = 0; j < 64; j++)
2
    for (i = 0; i < 24; i++)
3
        a[i][j] = 10;

则数组 a 的 Cache 命中率又是多少？

4.17#

主存容量为 8MB，虚存容量为 2GB，分页管理时若页面大小为 4KB，求出对应的 VPN、VPO、PPN、PPO 的位数。

4.18#

某页式虚拟存储器共 8 页，每页为 1KB，主存容量为 4KB，页表如下表所示。

(1) 失效的页有哪几页？
(2) 虚地址 0、3028、1023、2048、4096、8000 的实地址分别是多少？

4.19#

某计算机系统中的一个 TLB 和 L1 级数据 Cache，存储系统按字节编址，虚拟存储容量为 2GB，主存容量为 4MB，页大小为 128KB，TLB 采用四路组相联方式，共有 16 个页表项。Cache 容量为 16KB，每块包含 8 个字，每字为 32 位，映射方式采用四路组相联，回答下列问题。
(1) 虚拟地址中哪几位表示虚拟页号？哪几位表示页内地址？虚拟页号中哪几位表示 TLB 标记？哪几位表示 TLB 索引？
(2) 物理地址中哪几位表示物理页号？哪几位表示偏移地址？
(3) 为实现主存与数据 Cache 之间的组相联映射，对该地址应进行怎样的划分？

4.20#

假设计算机 M 的主存地址为 24 位，按字节编址；采用分页存储管理方式，虚拟地址为 30 位，页大小为 4KB；TLB 采用 2 路组相联方式和 LRU 替换策略，共 8 组。请回答下列问题。
(1) 虚拟地址中哪几位表示虚页号？哪几位表示页内地址？
(2) 已知访问 TLB 时虚页号高位部分用作 TLB 标记，低位部分用作 TLB 组号，M 的虚拟地址中哪几位是 TLB 标记？哪几位是 TLB 组号？
(3) 假设 TLB 初始时为空，访问的虚页号依次为 10、12、16、7、26、4、12、20，在此过程中，哪一个虚页号对应的 TLB 表项被替换？说明理由。
(4) 若将 M 中的虚拟地址位数增加到 32 位，则 TLB 表项的位数增加几位？

4.21#

某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为 32 位，物理地址为 24 位，页大小为 8KB；TLB 采用全相联映射；Cache 数据区大小为 64KB，按 2 路组相联方式组织，主存块大小为 64B。

(1) 物理地址各个字段的位数各是多少？TLB 标记中存放的是什么信息？
(2) 将块号为 4099 的主存块装入 Cache 中时，映射的 Cache 组号是多少？对应标记的内容是什么？
(3) Cache 缺失处理的时间开销大还是缺页处理的时间开销大？为什么？
(4) 为什么 Cache 可以采用写穿策略，而修改页面内容时总是采用写回策略？

4.22#

某计算机采用页式虚拟存储管理方式，按字节编址。CPU 进行页式虚拟存储器访问。回答下列问题。
(1) 主存的物理地址占多少位？
(2) TLB 采用什么映射方式？TLB 是用 SRAM 还是用 DRAM 实现？
(3) Cache 采用什么映射方式？若 Cache 采用 LRU 替换算法和写回策略，则 Cache 每行中除数据、tag 和有效位外，还应有哪些附加位？Cache 总容量是多少？Cache 中有效位的作用是什么？
(4) 若 CPU 给出的虚拟地址为 0008 C040H，则对应的物理地址是多少？是否在 Cache 中命中？说明理由。若 CPU 给出的虚拟地址为 0007 C260H，则该地址所在主存块映射到的 Cache 组号是多少？

4.4#

答：

1. 存储器容量为 32KB = $32 \times 1024 \times 8$ 位。
2. 若按 16 位字编址，则存储器的字容量为：
   $\text{字数} = 32\text{KB} \div 2\text{B} = 16\text{K} = 16384$ 个字。
3. 地址寄存器（MAR）的位数取决于字数。因为 $16\text{K} = 2^{14}$，所以地址寄存器应是 14 位。
4. 数据寄存器（MDR）的位数取决于字长，字长为 16 位，因此数据寄存器是 16 位。

4.5#

答：
使用 4 个 $32\text{K}\times 8$ 位的 SRAM 芯片，可以通过不同的排列组合进行字扩展或位扩展，设计出以下三种不同容量和字长的存储器：

1. 设计方案一：容量 $32\text{K}\times 32$ 位（容量 128KB，字长 32 位）
   • 实现方法：进行位扩展。将 4 个芯片并联，其地址线 $A_{14}\sim A_0$ 均连接到 CPU 的地址线；4 个芯片的片选信号线 $\overline{\text{CS}}$ 并联后接 CPU 的访存控制线；数据线分别连接到 CPU 32位数据总线的不同字节段 $D_0\sim D_7$、$D_8\sim D_{15}$、$D_{16}\sim D_{23}$、$D_{24}\sim D_{31}$。
2. 设计方案二：容量 $128\text{K}\times 8$ 位（容量 128KB，字长 8 位）
   • 实现方法：进行字扩展。将 4 个芯片的地址线 $A_{14}\sim A_0$ 和数据线 $D_7\sim D_0$ 分别并联。使用 CPU 的高位地址线 $A_{16}, A_{15}$ 通过一个 $2\:4$ 译码器，产生四个独立的片选信号分别连接到 4 个芯片的片选端 $\overline{\text{CS}}$。
3. 设计方案三：容量 $64\text{K}\times 16$ 位（容量 128KB，字长 16 位）
   • 实现方法：字位同时扩展。将 2 个芯片作为一组进行位扩展组成 $32\text{K}\times 16$ 位的单元（共 2 组）。再利用高位地址线 $A_{15}$ 经过一个非门译码，分别控制两组芯片的片选端。

4.6#

答：

1. 分析地址空间与容量需求：
   • 只读存储区（ROM）：地址范围 30000H ~ 3FFFFH。其大小为 3FFFFH - 30000H + 1 = 10000H 字节 = 64KB。
   • 可读写存储区（RAM）：目标总容量为 $256\text{K}\times 8$ 位 = 256KB。由于 ROM 占用了 64KB，其余的 256KB - 64KB = 192KB 空间为 RAM 区。
2. 芯片数量计算：
   • ROM 区：需要 64KB。用 $64\text{K}\times 4$ 位的 ROM 芯片，需要进行位扩展。芯片数 = $64\text{KB} \div (64\text{K}\times 4\text{位}) = 2$ 片。
   • RAM 区：需要 192KB。用 $32\text{K}\times 8$ 位的 RAM 芯片，需要进行字扩展。芯片数 = $192\text{KB} \div 32\text{KB} = 6$ 片。
3. 地址分配与片选译码设计：
   • 地址线共 18 位（$A_{17}\sim A_0$），因为 $256\text{KB} = 2^{18}$。
   • 地址高两位 $A_{17}, A_{16}$ 决定地址区间：
     • ROM区地址：30000H ~ 3FFFFH。当 $A_{17}A_{16} = 11$ 时选通 ROM，此时片选信号 $\overline{\text{CS}}_{\text{ROM}} = \overline{A_{17} \cdot A_{16}}$。
     • RAM区地址：分为 6 组 32KB（地址线需 15 位 $A_{14}\sim A_0$）。可以用高位地址线 $A_{17}, A_{16}, A_{15}$ 经由译码器输出分别选通 6 组 RAM。

4.7#

答：

1. 容量与芯片分析：
   • 主存总容量为 $128\text{K}\times 16$ 位。按字节编址，总容量为 256KB。
   • ROM 区地址范围：18000H ~ 1FFFFH。其大小为 1FFFFH - 18000H + 1 = 8000H 字节 = 32KB。由于字长 16 位，对应的只读区域为 $16\text{K}\times 16$ 位。
   • 芯片选型：ROM 芯片规格为 $32\text{K}\times 16$ 位，使用其一半的容量。
   • RAM 区：其余空间为 RAM 区。RAM 总大小 = 256KB - 32KB = 224KB，对应 $112\text{K}\times 16$ 位。使用 $16\text{K}\times 8$ 位的 SRAM 芯片，每 2 片进行位扩展组成 $16\text{K}\times 16$ 位的一组。共需要 112K / 16K = 7 组，芯片总数 = 7 × 2 = 14 片。
2. 连接设计要点：
   • 地址线 17 位（$A_{16}\sim A_0$）。
   • 译码电路：使用 $3\:8$ 译码器对高位地址进行译码，输出的 8 个片选信号分别对应 1 组 ROM 和 7 组 RAM。

4.8#

答：

1. 容量为 64K × 1 位，则存储元个数为 64K = $2^{16}$，正常的地址线需要 16 根。
2. 该芯片为动态 RAM（DRAM），采用地址复用技术，行地址与列地址分时复用，因此所需的地址引脚数减半，为 16 / 2 = 8 根。
3. 芯片必须的引脚包括：地址线 8 根，数据线 1 根，行选通信号 $\overline{\text{RAS}}$ 1 根，列选通信号 $\overline{\text{CAS}}$ 1 根。
4. 除电源、地线及写使能外的最小引脚数 = 地址线(8) + 数据线(1) + $\overline{\text{RAS}}$(1) + $\overline{\text{CAS}}$(1) = 11 根。

4.9#

答：

1. 控制参数：$1\text{M}\times 8$ 位由 $64\text{K}\times 1$ 位芯片构成，每个芯片有 256 行。
2. 异步刷新计算：
   • 异步刷新是在 2ms 内将所有 256 行轮流刷新一遍。
   • 产生刷新信号的间隔时间 = 2ms ÷ 256 行 = $7.81\mu\text{s}$（或约 $7.8\mu\text{s}$）。
3. 集中刷新计算：
   • 读写周期为 $0.5\mu\text{s}$。刷新一行需要一个读写周期。
   • 存储器刷新一遍最少需要的读写周期数 = 芯片的行数 = 256 个周期。
   • CPU 的死时间 = 256 × $0.5\mu\text{s}$ = $128\mu\text{s}$。

4.10#

答：

1. 刷新方式选择：
   • 存储器读写周期为 $0.5\mu\text{s}$，CPU 要求在 $1\mu\text{s}$ 内至少能访问存储器一次。
   • 如果采用集中刷新方式，刷新期间会产生 $128\mu\text{s}$ 的死时间，无法满足 CPU 在 $1\mu\text{s}$ 内必须访问的要求。
   • 如果采用分散刷新方式，每个工作周期分为读写和刷新两部分，存取周期拉长为 $0.5\mu\text{s} \times 2 = 1\mu\text{s}$，CPU 刚好可以在 $1\mu\text{s}$ 内访问一次，且没有死时间。但分散刷新过于频繁，降低了系统性能。
   • 如果采用异步刷新方式，每隔 $7.81\mu\text{s}$ 才刷新一行（耗时 $0.5\mu\text{s}$），只要避开 CPU 访问时刻，CPU 的访问不会被长时间阻塞，最合适。
   • 结论：采用异步刷新或分散刷新均可，其中以异步刷新在维持系统整体性能上最为合适。
2. 刷新信号的产生周期：
   • $16\text{K}\times 1$ 位芯片有 128 行。
   • 刷新间隔为 2ms，所以产生刷新信号的周期 = 2ms ÷ 128 行 = $15.625\mu\text{s}$。

4.11#

答：
Cache 容量为 $2^{14}$ 块（16384 块），每块 4B。主存按字节编址。
块内偏移（Offset）占 2 位（$2^2 = 4\text{B}$）。Cache 索引（Index）占 14 位。

1. 全相联映射：
   • 映射规则：主存块可以放入 Cache 的任意空闲行。Cache 标记项保存物理块号（即主存地址的高 30 位）。
   • 标记内容：地址去掉低 2 位后的值。例如地址 000008H，其标记为 000002H。
2. 直接相联映射：
   • 映射规则：Cache 行号 = 物理块号 mod $2^{14}$。
   • 地址划分：高位为 Tag，中间 14 位为 Index，低 2 位为 Offset。
     • 地址 000000H：Index = 0，Tag = 0。装入 Cache 的第 0 块。
     • 地址 000008H：Index = 2，Tag = 0。装入 Cache 的第 2 块。
3. 四路组相联映射：
   • 组数 = $2^{14} \div 4 = 2^{12}$ 组。组索引（Index）占 12 位。高位为 Tag，低 2 位为 Offset。

4.12#

答：
(1) 主存地址和 Cache 地址位数：

• 主存包含 4096 个存储块，每块 128 个字。主存总字数 = $4096 \times 128 = 2^{19}$ 个字。因为访问地址为字地址，所以主存地址有 19 位。
• Cache 由 64 个存储块构成，每块 128 字。Cache总字数 = $64 \times 128 = 2^{13}$ 字。所以 Cache 地址有 13 位。
  (2) 主存地址划分（四路组相联）：
• 块内字地址（Offset）：7 位（因为每块有 $128 = 2^7$ 个字）。
• Cache 共有 64 块，四路组相联表示每组有 4 块。组数 = 64 / 4 = 16 组。组号（Index）占 4 位（因为 $16 = 2^4$）。
• 标记（Tag）：19 - 4 - 7 = 8 位。
• 划分结构：[ Tag (8位) ] + [ 组号 (4位) ] + [ 块内字地址 (7位) ]。

4.13#

答：
(1) Cache 命中率计算：

• Cache 容量为 16KB，每字 32 位（4 字节），包含的字数 = 16KB ÷ 4B = 4K 字。
• 块大小为 8 个字 = 32B。Cache 的总行数 = 16KB ÷ 32B = 512 行。采用四路组相联，组数 = 512 ÷ 4 = 128 组。
• CPU 依次从主存第 0 到 99 号字单元读出 100 个字。因为 100 个字运小于 Cache 的总容量（4K 字），这 100 个字可以完全被装入 Cache 中，且不会发生替换。
• 第一次循环时，Cache 为空。读取第 0 单元缺失，调入 0~7 单元。因此 100 个字在第 1 遍中发生的缺失次数 = $\lceil 100 / 8 \rceil = 13$ 次。
• 在随后的 9 次循环中，所需数据已全部在 Cache 中，命中率为 100%。
• 总访问次数 = 100 × 10 = 1000 次。总缺失次数 = 13 次。
• Cache 命中率 $H = (1000 - 13) \div 1000 = 98.7\%$。
  (2) 访问速度提高倍数：
• 设 Cache 访问周期为 $t$，则主存访问周期为 $10t$。
• 平均访问时间 $T_a = H \cdot t + (1 - H) \cdot 10t = 0.987t + 0.013 \times 10t = 0.987t + 0.13t = 1.117t$。
• 速度提高倍数 = 原始主存时间 ÷ 平均时间 = $10t \div 1.117t \approx 8.95$ 倍。

4.14#

答：
(1) 数组访问的局部性：

• 二维数组 $a[M][N]$ 在内存中是按行优先顺序连续存放的。
• 代码 A：内层循环变量为 $j$，访问序列为 $a[i][0], a[i][1], \ldots$。这是严格按照内存物理顺序顺序读取，具有极佳的空间局部性；因为每个数组元素只被访问了一次，所以无时间局部性。
• 代码 B：内层循环变量为 $j$，访问序列为 $a[0][i], a[1][i], a[2][i], \ldots$。在内存中每次访问都跳过了 $N$ 个元素。若 $N$ 较大，每次读取都会发生 Cache 缺失，空间局部性极差；无时间局部性。
  (2) 变量 sum 的局部性：
• 变量 sum 在循环体内部被反复进行读出和累加改写。因此，sum 具有极强的时间局部性；因为它是单量，无空间局部性。
  (3) 循环体指令访问的局部性：
• 循环体内的指令代码在循环期间被 CPU 反复、顺序地取出并执行。因此，指令访问既具有极强的时间局部性，又具有极强的空间局部性。

4.15#

答：
(1) Cache 附加位计算：

• 数据区容量为 32KB，主存块大小 64B，行数 = 32KB ÷ 64B = 512 行。采用 8 路组相联，组数 = 512 ÷ 8 = 64 组。
• 块内地址占 6 位，组号占 6 位。Tag 位数 = 32 - 6 - 6 = 20 位。
• 8 路组相联采用 LRU，状态数 8 个，LRU 位占 $\log_2 8 = 3$ 位。
• 采用写穿策略，数据修改同步写入主存，因此不需要修改位（脏位）。
• 结论：标记占 20 位，LRU 占 3 位，没有修改位。
  (2) 数据 Cache 缺失次数：
• 起始地址 0080 00C0H （十进制 192）能被 64 整除，数组首元素刚好与 Cache 的一个块的边界对齐。
• 数组 s 共有 1024 个元素，占用的内存字节数 = 1024 × 4B = 4096B。主存块大小为 64B，因此数组共占用 4096 ÷ 64 = 64 个主存块。
• 循环执行 s[k] = 2 * s[k]，对每个元素进行一次读取和一次写入。每个块有 16 个整型元素。第一次读取首元素会发生缺失，启动主存块调入，随后的 15 次读取和 16 次写入均命中。
• 数组占用 64 个块，总缺失次数 = 64 × 1 = 64 次。
  (3) 指令访问及缺失处理过程：
• CPU 给出的虚拟地址为 0001 0003H。
• 1. CPU 首先在 TLB 中进行地址映射获取物理地址。
• 2. 得到物理地址后，利用中间 6 位定位到指令 Cache 的对应组，并行读取该组 8 行中的 Tag 字段进行比较。
• 3. 若相等且有效位为 1，则命中，根据低 6 位偏移行内字节数据送入 CPU IR。
• 4. 若不匹配，则发生缺失。Cache 控制器向主存发起读请求，将该物理块（64B）整体调入 Cache 组内（若该组已满，根据 LRU 算法替换出最久未使用的块），更新该行的 Tag 并将有效位置 1，最后将所需指令送入 CPU。

4.16#

答：
(1) 页面分布及缺页异常次数：

• 数组 a[24][64] 共有 1536 个 int 元素，容量 = 1536 × 4B = 6144B。页面大小为 4KB = 4096B。起始地址 0042 2000H 对齐。
• 页面 1：存放数组的前 4096B，即前 1024 个元素（对应行 0 至行 15）。
• 页面 2：存放数组剩余的 2048B，即后 512 个元素（行 16 至行 23）。
• 分布结论：分布在 2 个页面中。
• 缺页异常：数组按行优先顺序读取，第一次访问 a[0][0] 时，页面 1 发生缺页；访问到 a[16][0] 时，页面 2 发生缺页。共发生 2 次缺页异常。
• 页故障地址：分别为 0042 2000H 和 0042 3000H。
  (2) 时间局部性：不具有时间局部性。因为每一个元素都仅仅被执行了一次写入操作，之后不再被重复访问。
  (3) 地址字段划分与组号计算：
• 块内偏移占 5 位（$2^5 = 32\text{B}$）。组号（Index）占 6 位（$2^6 = 64$ 组）。数据 Cache 组号占 6 位，块内地址占 5 位。
• a[1][0] 的虚拟地址 = 0042 2000H + (1 × 64 + 0) × 4 = 0042 2100H。
• 其页内偏移与物理地址低位一致为 100H（二进制：0001 0000 0000）。按划分规则：低 5 位 00000 为块内偏移，中间 6 位 001000（十进制为 8）为组号。所以对应的 Cache 组号是 8。
  (4) Cache 命中率计算：
• 行优先顺序访问：每个主存块包含的 8 个元素被连续访问。仅在访问块中第 1 个元素时缺失，后 7 个均命中。命中率 = 7 / 8 = 87.5%。
• 列优先顺序访问：每次访问在内存中跳跃了一整行。在访问完一列前，主存块的内容早已被全部替换出 Cache（因为 Cache 总组数仅 64 组，无法同时驻留这么多跳跃地址的块）。所以每次访问都会发生 Cache 缺失，命中率为 0%。

4.17#

答：

1. 虚存容量为 2GB = $2^{31}$ 字节，页面大小为 4KB = $2^{12}$ 字节。页内偏移地址 VPO = 12 位，虚拟页号 VPN = 31 - 12 = 19 位。
2. 主存容量为 8MB = $2^{23}$ 字节，物理地址为 23 位。页内物理偏移地址 PPO = 12 位，物理页框号 PPN = 23 - 12 = 11 位。

4.18#

答：
(1) 缺页失效的虚页号有：2、3、5、7。
(2) 页大小为 1KB = 1024B。

• 虚地址 0：$\text{VPN} = 0 \div 1024 = 0$。对应实页号为 3，装入位 1。实地址 = $3 \times 1024 + 0 = 3072$。
• 虚地址 3028：$\text{VPN} = 3028 \div 1024 = 2$。装入位为 0，引发缺页失效，无实地址。
• 虚地址 1023：$\text{VPN} = 1023 \div 1024 = 0$。对应实页号为 3。实地址 = $3 \times 1024 + 1023 = 4095$。
• 虚地址 2048：$\text{VPN} = 2048 \div 1024 = 2$。装入位为 0，引发缺页失效，无实地址。
• 虚地址 4096：$\text{VPN} = 4096 \div 1024 = 4$。页表对应实页号为 3，装入位 1。实地址 = $3 \times 1024 + 0 = 3072$。
• 虚地址 8000：$\text{VPN} = 8000 \div 1024 = 7$。装入位为 0，缺页失效，无实地址。

4.19#

答：
(1) 虚拟地址划分：

• 虚拟容量为 2GB = $2^{31}$B，地址为 31 位。页大小为 128KB = $2^{17}$B。页内地址占低 17 位，虚拟页号（VPN）占高 14 位。
• TLB 组数 = 16 ÷ 4 = 4 组。TLB 索引占 2 位。
• 高位中的低 2 位（$V_{18}, V_{17}$）为 TLB 索引，高 12 位（$V_{30}\sim V_{19}$）为 TLB 标记。
  (2) 物理地址划分：
• 主存容量 4MB = $2^{22}$B，物理地址共 22 位。页大小为 128KB，偏移地址占低 17 位，物理页框号占高 5 位。
  (3) Cache 地址映射划分：
• Cache 共有 512 行。采用四路组相联，组数 = 512 ÷ 4 = 128 组。
• 块内偏移占 5 位（$2^5 = 32\text{B}$）。组号（Index）占 7 位（$2^7 = 128$ 组）。Tag 位数 = 22 - 7 - 5 = 10 位。
• 划分结构：[ Tag (10位) ] + [ 组号 (7位) ] + [ 块内偏移 (5位) ]。

4.20#

答：
(1) 虚拟地址 30 位，页大小 4KB（$2^{12}$B）。虚页号占高 18 位，页内地址占低 12 位。
(2) TLB 共 8 组（$2^3 = 8$），故 TLB 组号占 3 位，低 3 位用作组号，高 15 位用作标记。虚拟地址中，$V_{14}\sim V_{12}$ 为 TLB 组号，$V_{29}\sim V_{15}$ 为 TLB 标记。
(3) TLB 替换模拟过程：
将访问的虚页号转换为二进制以计算组号（低 3 位）：

• 10 (二进制 001010) → 组号 = 2 (低三位 010)。组 2 状态：[10]。
• 12 (二进制 001100) → 组号 = 4 (低三位 100)。组 4 状态：[12]。
• 16 (二进制 010000) → 组号 = 0 (低三位 000)。组 0 状态：[16]。
• 7 (二进制 000111) → 组号 = 7 (低三位 111)。组 7 状态：[7]。
• 26 (二进制 011010) → 组号 = 2。并入后变为 [26, 10]。
• 4 (二进制 000100) → 组号 = 4。并入后变为 [4, 12]。
• 12 (二进制 001100) → 组号 = 4。命中，更新状态为 [12, 4]（12 最新）。
• 20 (二进制 010100) → 组号 = 4。组 4 满，4 最久未用，故淘汰 4。
• 结论：虚页号 4 对应的表项被替换。
  (4) 每个 TLB 表项中的标记增加 2 位，整个表项位数增加 2 位。

4.21#

答：
(1) 物理地址字段划分：

• 物理地址为 24 位。页大小为 8KB = $2^{13}$B。物理页号 = 24 - 13 = 11 位，页内偏移地址 = 13 位。
• Cache 组数 = 512 组。块内偏移占 6 位。组索引占 9 位。Tag 位数 = 24 - 9 - 6 = 9 位。
• 划分：[ Tag (9位) ] + [ 组号 (9位) ] + [ 块内偏移 (6位) ]。
• TLB 采用全相联映射，TLB 标记中存放的是完整的虚拟页号（VPN = 19位）以及属性位。
  (2) 主存块装入映射计算：
• 块号为 4099。映射的 Cache 组号 = 块号 mod 512 = 4099 mod 512 = 3。
• 对应 Tag 的内容：物理块号高位部分，物理 Tag = 000001000_2（十六进制：008H）。
  (3) 时间开销对比：缺页处理的开销远大于 Cache 缺失的开销。因为 Cache 缺失只需从主存读取数据块，耗时几十到上百纳秒；而页缺失需要访问磁盘，需要几毫秒甚至十几毫秒。时间相差达 5 个数量级。
  (4) 写策略原因：Cache 采用写穿策略时，写主存延迟在几十纳秒内，性能影响小。而主存修改如果采用写穿到磁盘，将面临高达毫秒级的磁盘写入延迟，导致系统效率极低。因此采用写回法。

4.22#

答：
(1) 主存为 $1\text{MB}$，物理地址占 20 位。
(2) TLB 采用全相联映射或组相联映射，采用 SRAM 芯片实现。
(3) Cache 采用组相联映射。Cache 行中除数据外，还应有 LRU位和修改位（脏位）。有效位作用是指示当前 Cache 行中的数据是否有效。
(4) 虚拟地址 0008 C040H。物理地址为物理页框号加低 12 位 040H。是否命中取决于该物理地址对应的 Tag 是否与 Cache 对应行中的 Tag 一致。若虚拟地址为 0007 C260H：其物理偏移为 260H。利用物理地址的组索引字段定位到对应的 Cache 组。