跳转至

习题演练

【2010-17】下列命中组合情况中，一次访存过程中不可能发生的是（ ）。

A. TLB未命中，Cache未命中，Page未命中

B. TLB未命中，Cache命中，Page命中

C. TLB命中，Cache未命中，Page命中

D. TLB命中，Cache命中，Page未命中

解析

答案：D

TLB（快表）本质上是页表（Page Table）在CPU内部的一个高速缓存。如果 TLB命中，说明该虚拟页对应的页表项已经缓存在了TLB中，而只有当一个页面已经被装入主存（即 Page命中）时，它的物理映射信息才可能是有效的并被缓存到TLB中。因此，只要TLB命中，必定意味着Page也是命中的。所以“TLB命中，Page未命中”的情况在一次访存过程中是不可能发生的。

【2013-16】某计算机主存地址空间大小为256MB，按字节编址。虚拟地址空间大小为4GB，采用页式存储管理，页面大小为4KB，TLB（快表）采用全相联映射，有4个页表项，内容如下表所示。

\(\begin{array}{cccc}\text{有效位}&\text{标记}&\text{页框号}&\text{...}\\\hline 0&\text{FF180H}&\text{0002H}&\text{...}\\ 1&\text{3FFF1H}&\text{00352H}&\text{...}\\ 0&\text{02FF3H}&\text{0351H}&\text{...}\\ 1&\text{03FFFH}&\text{0153H}&\text{...}\\ \end{array}\)

则对虚拟地址03FFF180H进行虚实地址变换的结果是（ ）。

A. 0153180H

B. 0035180H

C. TLB缺失

D. 缺页

解析

答案：A

  1. 拆分虚拟地址： 按字节编址，页面大小为 4KB（即 公式），因此虚拟地址的低12位为页内偏移量。虚拟地址总长32位（4GB），高20位为虚拟页号（VPN）。
  2. 虚拟地址公式 ，查找TLB中03FFFH对应的页表项，有效位为1，页框号为0153H，物理地址为公式 。

【2015-16】假定编译器将赋值语句“x=x+3;”转换为指令“add xaddr, 3”，其中xaddr是x对应的存储单元地址。若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写 (Write Trough)方式，则完成该指令功能需要访问主存的次数至少是（ ）。

A. 0

B. 1

C. 2

D. 3

解析

答案：B

指令 add xaddr, 3 的完整执行周期（包括取指、取数、执行写回）访存情况如下：

  1. 取指令： 题目假设配有相应的TLB，若取指时TLB命中且Cache命中，则访问主存 0次。
  2. 取操作数： 题目求“至少”的情况，我们假设最乐观的状态，即访问 xaddr 时TLB命中且Cache也命中，从Cache中取数，访问主存 0次。
  3. 写回操作数： CPU将加3后的结果写回 xaddr。虽然此时Cache依然命中，但题目明确指出 Cache采用直写（Write Through）方式。直写策略要求在向Cache写入数据的同时，必须同步将数据写入主存。因此这一步不可避免地需要访问主存 1次。 综合以上步骤，完成该指令至少需要访问主存1次。

【2019-14】下列关于缺页处理的叙述中，错误的是（ ）。

A. 缺页是在地址转换时CPU检测到的一种异常

B. 缺页处理由操作系统提供的缺页处理程序来完成

C. 缺页处理程序根据页故障地址从外存读入所缺失的页

D. 缺页处理完成后回到发生缺页的指令的下一条指令执行

解析

答案：D

缺页异常属于内部异常中的故障（Fault）。当CPU在进行地址转换检测到缺页时，当前正在执行的指令会被迫中止。操作系统介入并从外存调入缺失的页后，CPU会返回到发生缺页异常的那条指令重新执行（因为该指令刚才并没有执行成功），而不是回到下一条指令执行。因此选项D的叙述是错误的。

【2020-15】下列关于TLB和Cache的叙述中，错误的是（ ）。

A. 命中率都与程序局部性有关

B. 缺失后都需要去访问主存

C. 缺失处理都可以由硬件实现

D. 都由DRAM存储器组成

解析

答案：D

A正确：Cache利用数据的空间/时间局部性，TLB利用页表访问的局部性。

B正确：Cache缺失需访问主存读取数据块，TLB缺失需访问主存读取多级页表。

C正确：Cache缺失全由硬件处理；TLB缺失既可以由硬件实现（如X86），也可以由软件处理（如MIPS），所以“可以由硬件实现”表述无误。

D错误：Cache和TLB为了追求与CPU匹配的极高访问速度，通常都由 SRAM（静态随机存取存储器）或 CAM（相联存储器）组成，只有主存才通常由 DRAM（动态随机存取存储器）组成。

【2022-15】某计算机主存地址为24位，采用分页虚拟存储管理方式，虚拟地址空间大小为4GB，页大小为4KB，按字节编址。某进程的页表部分内容如下表所示。当CPU访问虚拟地址00082840H，虚-实地址转换的结果是（ ）。

\(\begin{array} {|c|c|c|}\hline \text{虚页号}&\text{实页号（页框号）}&\text{存在位}\\\hline \text{82}&\text{024H}&0\\\hline \dots&\dots&\dots\\\hline \text{129}&\text{180H}&1\\\hline \text{130}&\text{018H}&1\\\hline \end{array}\)

A. 得到主存地址02 4840H

B. 得到主存地址18 0840H

C. 得到主存地址01 8840H

D. 检测到缺页异常

解析

答案：C

页面大小 4KB（公式 B），页内偏移量占12位。对虚拟地址 0008 2840H 进行拆分，低12位 840H 是页内偏移，高20位 00082H 是虚拟页号，00082H=8×16+2=130，查该进程页表得，虚页号130对应的存在位为1，实页号为018H，主存地址为24位，实页号占高24-12=12位，查表得到的实页号正好12位，高位不需要去0或者补0，拼接得到主存地址公式 。

【2024-16】对于页式虚拟存储管理系统，下列关于存储器层次结构的叙述中，错误的是

A. Cache-主存层次的交换单位为主存块，主存-外存层次交换单位为页

B. Cache-主存层次替换算法由硬件实现，主存-外存层次替换算法由软件实现

C. Cache-主存层次可采用回写法写策略，主存-外存层次通常采用回写法写策略

D. Cache-主存层次可采用直接映射方式，主存-外存层次通常采用直接映射方式

解析

答案：D

  • D 选项错误。 Cache-主存层次确实可以采用直接映射方式（也可以是全相联或组相联），但是主存-外存层次（虚拟存储系统）通常采用的是全相联映射方式，而不是直接映射方式。因为外存（磁盘）的读取速度极慢，发生缺页的代价极其惨重，为了尽最大可能消除“冲突缺失”、提高命中率，系统允许将外存中的任何一页调入主存中的任何一个空闲页框内（即全相联）。

其他选项分析（均为正确叙述）：

  • A 选项正确： Cache 与主存之间的数据交换是以“块（Block）”为单位的（通常几十字节）；而主存与外存之间的数据交换是以“页（Page）”为单位的（通常几KB到几十KB）。
  • B 选项正确： Cache 为了追求极致的速度，其映射、替换等所有操作均由硬件逻辑直接实现；而主存-外存层次的缺页处理、页面替换等操作，是由操作系统的存储管理模块（软件）结合页表来实现的。
  • C 选项正确： Cache-主存层次的写策略可以是直写（Write-through）或回写（Write-back）；但在主存-外存层次，由于每次访问磁盘的开销巨大，系统绝不可能在每次修改主存时都同步去写磁盘（直写），因此必然采用回写策略，即只在页面被替换出主存时才将其写回磁盘。

【2024-17】某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址为32位，主存地址为30位，页大小为1 KB。若TLB共有32个表项，采用4路组相联映射方式，则 TLB 表项在标记字段的位数至少是

A. 17

B. 18

C. 19

D. 20

解析

答案：C

  1. 求虚拟页号（VPN）位数： 页大小为 1KB（公式 B），因此虚拟地址（32位）的低10位为页内偏移。高位即为虚拟页号，位数为 32 - 10 = 22 位。
  2. 划分TLB结构： TLB通过虚拟页号进行查找，VPN在TLB中被划分为 [TLB标记 (Tag)] 和 [TLB组索引 (Index)] 两部分。
  3. 求组索引位数： TLB共有32个表项，采用4路组相联映射，因此总组数为 公式= 8 组。要对8个组进行寻址，组索引需要 公式 = 3 位。
  4. 求标记字段位数： TLB标记的位数 = 虚拟页号总位数 - 组索引位数 = 22 - 3 = 19 位。因此TLB表项在标记字段至少需要19位。

【2024-18】下列事件，不是在 MMU 地址转换过程中检测的是

A. 访问越权

B. Cache 缺失

C. 页面缺失

D. TLB缺失

解析

答案：B

MMU 负责将虚拟地址转化为物理地址，所以会检测以下事件：访问越权、页面缺失、TLB 缺失。Cache 缺失不是在 MMU 地址转换过程中检测的，而是在 CPU 访问主存数据检测的，访问主存的前提是有物理地址，所以该过程是在 MMU 完成地址翻译之后。

为什么主存-辅存必须用“全相联”？ 为什么 Cache 不全用全相联？

1. 什么是主存-辅存的“全相联映射”？

在虚拟存储器中，逻辑空间被划分为大小相等的“页”，物理主存被划分为同样大小的“页框”。全相联映射即 辅存（硬盘）中的任何一个页，都可以被灵活地装入到主存中的任何一个空闲的页框里。它们之间没有任何位置上的“强制绑定”关系。

可以用“停车场”来形象地理解：

  • 直接映射（Cache常用）： 你的车牌号尾数是5，你就只能停在5号车位。如果5号车位有人了，即使整个停车场其他几百个车位全空着，你也得把5号车位那辆车赶走才能停进去。（这叫冲突缺失，命中率低）。
  • 全相联映射（主存-辅存采用）： 你可以把车停在停车场的任何一个空闲车位。只有当整个停车场彻底爆满时，你才需要考虑赶走一辆车（替换）。

2. 为什么主存-辅存必须用“全相”？

核心原因有以下三点：

① 硬盘太慢了，缺页代价极其惨重，这是最根本的原因。

  • CPU 访问主存的速度是纳秒级 (ns)。
  • CPU 访问硬盘（辅存）的速度是毫秒级 (ms)。
    两者相差了数十万甚至上百万倍。如果在主存中找不到需要的数据（发生“缺页”），系统就不得不去读硬盘，这会导致 CPU 被迫停顿漫长的时间。因此，主存-辅存层次设计的最高优先级目标就是：不择手段地提高命中率，尽一切可能避免去读硬盘。

② 全相联能提供最高的命中率

正如上面停车场的例子，如果在这个层次使用“直接映射”或“组相联映射”，就会发生“冲突缺失”——主存明明还有大量空闲空间，却因为位置限制不得不把有用的数据踢回硬盘。采用全相联映射，只要主存没被完全塞满，就绝对不会发生替换操作。这就彻底消除了“冲突缺失”，从而最大化了主存的命中率。

③ 靠操作系统（软件）实现，有条件做全相联

你可能会问：既然全相联这么好，为什么 Cache 不全用全相联？

  • Cache 的无奈： Cache 是为了匹配 CPU 的极速，它的地址转换必须在 1~2 个时钟周期内靠纯硬件电路完成。如果 Cache 做成全相联，意味着硬件要在瞬间同时把目标地址和 Cache 中所有行的地址进行比对，这种极其复杂的比较器电路成本太高，且延迟很大，所以 Cache 只能妥协，多用组相联。
  • 主存-辅存的优势： 主存-辅存的映射和缺页处理是由操作系统（软件）结合数据结构（页表 Page Table）来实现的。软件查表是非常灵活的，记录“任意页对应任意页框”的映射关系轻而易举。虽然软件查表、更新页表比起纯硬件耗时更长，但是与读取硬盘那漫长的毫秒级时间相比，这点软件处理的开销简直微不足道。

总结

主存-辅存层次采用全相联映射，是典型的“用空间和软件管理的复杂度，去换取宝贵的磁盘 I/O 时间”的权衡结果。因为在这里，哪怕能减少 1% 的缺页率，带来的性能提升都是巨大的。

（原创题）关于 Cache-主存层次与主存-辅存（外存）层次的异同，下列叙述中错误的是（ ）

A. 引入 Cache-主存层次的主要目的是为了加快 CPU 访问信息的速度，而主存-辅存层次则是为了解决主存容量不足的问题。

B. CPU 可以直接访问 Cache 和主存中的数据，但不能直接访问辅存，辅存的数据必须先调入主存才能被 CPU 处理。

C. Cache-主存层次的地址映射关系完全由硬件实现并使用标志（Tag）描述，主存-辅存层次的映射关系则由操作系统通过页表来实现。

D. Cache-主存层次和主存-辅存层次的数据调度与交换过程，对所有的程序员（包括应用程序员和系统程序员）都是完全透明的。

解析

正确答案：D

  • D 选项错误： 两个层次在“透明性”上是不同的。Cache-主存层次的数据交换完全由硬件自动完成，对所有程序员（无论是应用程序员还是系统程序员）都是透明的；而主存-辅存层次（虚拟存储器）的数据交换由硬件和操作系统共同完成，它只对应用程序员透明，但对系统程序员是不透明的（因为系统程序员需要编写操作系统中的缺页中断处理、页面替换等底层硬件调度代码）。
  • A 选项正确： 准确描述了两者的引入目的。Cache 用于提速（填补 CPU 和主存间的速度鸿沟），虚拟存储器（主存-辅存）用于扩容。
  • B 选项正确： 准确描述了 CPU 的访问权限。Cache 和主存属于内部存储器，CPU 可直接寻址访问；辅存属于外部存储器，必须经过主存作为中转。
  • C 选项正确： 准确描述了映射关系的实现介质。Cache 为了极致的速度，映射和查找全靠纯硬件电路（比对 Tag）；而主存-辅存层次的缺页代价大，由软件（操作系统）维护的页表（Page Table）来实现虚拟地址到物理地址的映射。

真题大题

【2011-44】

（12分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB，主存（物理）地址空间大小为1MB，页面大小为4KB：Cache采用直接映射方式，共8行：主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题 44-a 图、题 44-b 图所示，图中页框号及标记字段的内容为十六进制形式。

1778145699084-4a1becef-49d3-4d8a-8935-183a4e8b96a4.png

1778145714364-78433fdb-bbba-4580-bb60-c5d34949e31e.png

请回答下列问题∶

(1) 虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？

(2) 使用物理地址访问Cache时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。

(3) 虚拟地址001C60H所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache命中？要求说明理由。

(4) 假定为该机配置一个4路组相连的TLB，该TLB共可存放8个页表项，若其当前内容（十六进制）如题 44-c 图所示，则此时虚拟地址024BACH所在的页面是否在主存中？要求说明理由。

1778146005619-498e1e88-4104-45cf-be59-8a0b6404a63a.png

计算 结果
虚拟地址位数 16MB = 2²⁴ 24位
物理地址位数 1MB = 2²⁰ 20位
页内偏移 4KB = 2¹² 12位
虚页号位数 24 - 12 12位（bits 23~12）
物理页框号位数 20 - 12 8位（bits 19~12）
Cache块内偏移 32B = 2⁵ 5位（bits 4~0）
Cache行索引 8行 = 2³ 3位（bits 7~5）
Cache标记 20 - 5 - 3 12位（bits 19~8）

(1) 虚拟地址共24位（16MB = 2²⁴）

- 第23位~第12位（共12位）表示<strong>虚页号</strong>
- 第11位~第0位（共12位）表示页内偏移

物理地址共20位（1MB = 2²⁰）

- 第19位~第12位（共8位）表示<strong>页框号（物理页号）</strong>
- 第11位~第0位（共12位）表示页内偏移

(2)物理地址（20位）按以下方式划分：\(\begin{array}{|c|c|c|}\hline主存字块标记Tag& 行号& 块内地址\\\hline\end{array}\)

  • 块内地址（5位，第4~0位）：块大小32B = 2⁵，定位块内具体字节
  • 行号（3位，第7~5位）：直接映射共8行 = 2³，确定映射到哪一Cache行
  • 标记位（12位，第19~8位）：用于判断Cache行中的数据是否为所需数据

(3) 虚拟地址001C60H所在的页面是否在主存中？若在，对应物理地址是什么？是否Cache命中？

第一步：拆分虚拟地址 001C60H

001C60H = 0000 0000 0001 1100 0110 0000B（24位）
虚页号（bits 23~12）= 0x001 = 001H
页内偏移（bits 11~0）= 0xC60 = C60H

第二步：查页表

查页号001H对应的表项，有效位 = 1（在主存中），页框号 = 04H。

第三步：构造物理地址

页框号为04H，与页内地址拼接成物理地址为\(\rm \underbrace{04}_{\text{页框号}}\,\underbrace{C60}_{\text{页内地址}} H\) 。

第四步：判断Cache 是否命中。

\(\rm 04C60 H = \underbrace{0000 0100 1100}_{\text{主存字块标记}}\, \underbrace{011}_{\text{行号}}\, \underbrace{0 0000}_{\text{块内地址}}B\)，映射到Cache的第011B=3行

查看44-b的表格，有效位为1，标记为105H不等于需要访问标记04CH，所以不命中。

(4) TLB（4路组相联，8项）中，虚拟地址024BACH所在的页面是否在主存中？

第一步：拆分虚拟地址 024BACH。

024BACH（24位）= 0000 0010 0100 1011 1010 1100B
虚页号（bits 23~12）= 0x024 = 024H = 0000 0010 0100B
页内偏移（bits 11~0）= BACH

第二步：TLB分组。

TLB共8个表项，4路组相联：

  • 组数 = 8 ÷ 4 = 2组（组0和组1）
  • 组索引位数 = log₂2 = 1位（取虚页号最低1位）

虚页号 024H = ...0010 0100B，最低位 = 0 → 映射到组0

TLB标记 = 虚页号高11位 = 0000 0010 010B = 0x012 = 012H

第三步：查TLB组0（题44-c图）。

在TLB组0的4个表项中查找标记 = 012H 的表项，发现组0中存在有效位为1、标记为012H的项，因此访问TLB命中，即虚拟地址024BACH所在的页面在主存中。

【2016-45】

（14分）某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为32位，物理地址为24位，页大小为8KB；TLB采用全相联映射；Cache数据区大小为64KB，按2路组相联方式组织，主存块大小为64B。存储访问过程的示意图如下。

1775220975050-796e8d7e-415f-4bc2-a3bd-72ab19e570a3.png

请回答下列问题。

(1) 图中字段A～G的位数各是多少？TLB标记字段B中存放的是什么信息？

(2) 将块号为4099的主存块装入到Cache中时，所映射的Cache组号是多少？对应的H字段内容是什么？

(3) Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？

(4) 为什么Cache可以采用直写 (Write Through) 策略，而修改页面内容时总是采用回写 (Write Back) 策略？

【预备计算】

参数 计算 结果
页内偏移 8KB = 2¹³ 13位
虚页号位数（A） 32 - 13 19位
物理页框号位数（C） 24 - 13 11位
Cache块内偏移（G） 64B = 2⁶ 6位
Cache组数 64KB ÷ (2 × 64B) = 512 512组
Cache组索引（F） log₂512 9位
Cache标记（E） 24 - 6 - 9 9位

(1) 图中字段A～G的位数各是多少？TLB标记字段B中存放的是什么信息？

解：地址变换流程各字段：

虚拟地址（32位）：
┌────────────────────┬───────────────────────┐
│ 虚页号 A = 19位 │ 页内偏移 D = 13位 |
└────────────────────┴───────────────────────┘
↓ TLB查找（全相联）
┌────────────────────┬───────────┐
│ TLB标记 B = 19位 │ │
└────────────────────┴───────────┘
↓ 命中则得到
┌─────────────────────┬──────────────────────┐
│ 物理页框号 C = 11位 │ 页内偏移 D = 13位 |
└─────────────────────┴──────────────────────┘
↓ 物理地址（24位）送Cache
┌──────────────┬─────────────┬───────────────┐
│ Cache标记 │ Cache组索引 │块内偏移 │
│ E = 9位 │ F = 9位 │ G = 6位 │
└──────────────┴─────────────┴───────────────┘

TLB标记字段B中存放的是虚页号（19位）。 因为TLB采用全相联映射，没有组索引，TLB的整个标记字段就是完整的虚页号，用于与CPU给出的虚页号比较判断是否命中。

(2) 将块号为4099的主存块装入Cache时，所映射的Cache组号是多少？对应的H字段（Cache标记）内容是什么？

法一： Cache共512组，2路组相联，块大小64B：

Cache组号 = 主存块号 mod Cache组数

组号 = 4099 mod 512
     = 4099 - 8 × 512
     = 4099 - 4096
     = 3

Cache标记H = 主存块号 ÷ Cache组数 = floor(4099 / 512)

H = ⌊4099 / 512⌋ = ⌊8.005...⌋ = 8

H字段内容 = 8（十进制），即 000001000B（9位二进制）。

法二：对于任意Cache格式，主存地址均可划分为\(\begin{array}{|c|c|}\hline\text{块号}&\text{块内地址}\\\hline\end{array}\) ，本题Cache采用组相联格式， 地址可划分为\(\begin{array}{|c|c|}\hline\text{块号}&\text{块内地址}\\\hline\end{array} =\begin{array}{|c|c|c|}\hline\text{主存字块标记}&\text{组号}&\text{块内地址}\\\hline\end{array}\) ，所以 \(\begin{array}{|c|}\hline\text{块号}\\\hline\end{array} =\begin{array}{|c|c|}\hline\text{tag}&\text{组号}\\\hline\end{array}\) 。块号4099=4096+3=\(\underbrace{00 0001 000}_{\text{tag}}\underbrace{0 0000 0011}_{\text{组号}}\) B，因此，所映射的Cache组号为0 0000 0011B=3。标记H为主存字块标记，块号4099对应的H字段内容为0 0000 1000B。

(3) Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？

缺页处理的时间开销远大于Cache缺失处理的时间开销。

Cache缺失时，直接从主存调块到Cache，全程硬件完成，速度快；缺页时必须从外存（磁盘）读取，磁盘I/O是机械运动或闪存擦写，延迟高出主存访问数个数量级。

(4) 为什么Cache可以采用直写策略，而修改页面内容时总是采用回写策略？

策略 Cache（Cache-主存） 虚拟内存（主存-外存）
写策略 直写（Write Through）可行 必须采用回写（Write Back）
原因 主存访问延迟约百纳秒，直写的性能损失可接受；且直写使Cache与主存保持一致，简化一致性管理 磁盘I/O延迟达毫秒级，若每次写页面都立即写磁盘，性能损失灾难性（写操作变慢10⁵倍）；采用回写仅在页面被置换时才写磁盘，大幅减少磁盘I/O次数

本质区别：下层存储器的访问延迟差异决定了写策略的选择。主存速度相对较快，直写可接受；磁盘速度极慢，必须回写以避免频繁磁盘I/O造成的性能崩溃。

【2018-44】

（15分）某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如题44图所示。

1778146319121-14f6b756-32ed-444b-9c4b-239b317d687e.png

根据题44图回答下列问题。

(1) 主存物理地址占多少位？

(2) TLB采用什么映射方式？TLB用SRAM还是DRAM实现？

(3) Cache采用什么映射方式？若Cache采用LRU替换算法和回写（Write Back）策略，则Cache每行中除数据（Data）、Tag和有效位外，还应有哪些附加位？Cache总容量是多少？Cache中有效位的作用是什么？

(4) 若CPU给出的虚拟地址为0008C040H，则对应的物理地址是多少？是否在Cache中命中？说明理由。若CPU给出的虚拟地址为0007C260H，则该地址所在主存块映射到的Cache组号是多少？

解析

(1) 主存物理地址占多少位？

物理地址映射到Cache后的地址位数不变，观察映射到Cache后的地址结构，可得物理地址占20+3+5=28位。

(2) TLB采用什么映射方式？TLB用SRAM还是DRAM实现？

  1. TLB采用全相联映射，可以把页表内容调入任一块空TLB项中，TLB中每项都有一个比较器，没有映射规则，只要空闲就行。
  2. TLB需要极高的访问速度（与CPU流水线匹配，通常1个时钟周期），必须使用SRAM实现。DRAM速度不够快，无法满足TLB的性能要求。

(3) Cache采用什么映射方式？附加位有哪些？Cache总容量是多少？有效位的作用？

  1. 根据题44图，Cache中每组有两行，采用2路组相联映射方式。
  2. 若Cache采用LRU替换算法和回写（Write Back）策略，则Cache每行中除数据（Data）、Tag和有效位外，还应有替换算法控制位和一致性维护位（脏位）。LRU需要的替换算法控制位数为公式 ，本题为2路组相连，所以每行需要公式 位替换算法控制位。每行有1位脏位，根据脏位判断数据是否被更新，如果脏位为1则需要写回内存。
  3. Cache组相联映射的地址结构中，主存字块标记占20位，组号占3位，Cache中有 公式组，每组有两行，Cache中有8×2=16行，块内地址占5位，计算机按字节编址，Cache块大小为公式 ×1B=32B。

Cache每行标记位数=主存字块标记位数+有效位位数+替换算法控制位位数+脏位位数=(20+1+1+1)bit=23bit。

Cache每行数据位数=32B=32×8bit=256bit。

Cache总容量=(Cache每行标记位数+Cache每行数据位数)×Cache行数=(23bit+256bit)×16=558B。

  1. 有效位的作用： 标记该Cache行是否包含有效数据。
  • 系统初始化或Cache被清空时，所有有效位清0，表示所有Cache行均无有效内容。
  • 当一个主存块调入Cache时，对应行的有效位置1。
  • CPU访问Cache时，必须同时满足"有效位=1"且"Tag匹配"，才算Cache命中。仅Tag匹配但有效位=0，仍视为Cache未命中（Miss）。

(4) 虚拟地址0008C040H和0007C260H的地址转换与Cache命中情况

① 虚拟地址 0008C040H

  • 虚拟地址 公式，查找TLB表中Tag为0008CH的项，有效位为1，实页号为0040H，得到0008C040H所在的物理地址为 公式 。
  • Cache组相联映射的地址格式为 公式 ，物理地址高20位对应主存字块标记，所以物理地址 公式 的主存字块标记为00400H，查Cache表表中Tag为00400H的项，左边一个存在Tag为00400H的项，但有效位为0，右边一个不存在Tag为00400H的项，所以访问Cache不命中。

② 虚拟地址 0007C260H（确定其主存块映射的Cache组号）

因为物理地址的低12位与虚拟地址低12位相同，对于虚拟地址为0007C260H，低12位为260H=0010 0110 0000B 。根据物理地址的结构，物理地址的后八位01100000B的前三位011B是组号，因此该地址所在的主存映射到Cache组号为011B=3。

【2019-46】

若计算机M的主存地址为32位，釆用分页存储管理方式，页大小为4KB，则第1行的push指令和第30行的ret指令是否在同一页中（说明理由）？若指令Cache有64行，采用4路组相联映射方式，主存块大小为64B，则32位主存地址中，哪几位表示块内地址？哪几位表示Cache组号？哪几位表示标记（tag）信息？读取第16行的call指令时，只可能在指令Cache的哪一组中命中（说明理由）？

int f1(int n){
1   00401000  55              push ebp
    ...       ...             ...
if(n>1)
11  00401018  83 7D 08 01     cmp dword ptr [ebp+8],1
12  0040101C  7E 17           jle f1+35h (00401035)
return n*f1(n-1);
13  0040101E  8B 45 08        mov eax, dword ptr [ebp+8]
14  00401021  83 E8 01        sub eax, 1
15  00401024  50              push eax
16  00401025  E8 D6 FF FF FF  call f1 (00401000)
    ...       ...             ...
19  00401030  0F AF C1        imul eax, ecx
20  00401033  EB 05           jmp f1+3Ah (0040103a)
else return 1;
21  00401035  B8 01 00 00 00  mov eax, 1
}
    ...       ...             ...
26  00401040  3B EC           cmp ebp, esp
    ...       ...             ...
30  0040104A  C3              ret
解析

页大小4KB，因此页内偏移12位。

push地址 00401000H：虚页号 = 0x00401000 >> 12 = 0x00401
ret地址 0040104AH：虚页号 = 0x0040104A >> 12 = 0x00401

两条指令的虚页号相同，均为0x401页，因此在同一页中。

指令Cache字段划分（64行，4路组相联，块大小64B，32位地址）：

Cache组数 = 64行 ÷ 4路 = 16组
块内偏移 = log₂(64B) = 6位（bits 5~0）
组索引 = log₂(16) = 4位（bits 9~6）
标记(Tag) = 32 - 6 - 4 = 22位（bits 31~10）

call指令（地址00401025H）所在的Cache组：

00401025H = 0000 0000 0100 0000 0001 0000 0010 0101B

块内偏移（bits 5~0） = 10 0101B = 0x25 = 37（在64B块内的第37字节）
块号 = 0x00401025 >> 6 = 0x10040（计算：0x401025 / 64 = 0x10040余0x25）
组号 = 0x10040 mod 16 = 0（因为0x10040 = 0x1004 × 16 + 0）

call指令只可能在指令Cache的第0组中命中。

理由：call指令的物理地址确定后，其所在主存块的块号为0x10040，0x10040 mod 16 = 0，固定映射到Cache第0组，无论该块是否在Cache中（命中或缺失），它都只可能在第0组。

【2021-44】

（8分）假设计算机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表项的位数增加几位？

(1) 虚拟地址中哪几位表示虚页号？哪几位表示页内地址？

虚拟地址格式为 \(\begin{array}{|c|c|}\hline \text{虚页号}&\text{页内地址}\\\hline \end{array}\)

  • 按字节编址，且页大小 4KB = 2¹² → 页内地址：bits 11~0（低12位）
  • 虚页号：bits 29~12（高18位）

(2) TLB中哪几位是标记？哪几位是组号？

TLB共8组 → 组号 = log₂8 = 3位

约定：虚页号高位作标记，低位作组号：\(\begin{array}{|c|}\hline \text{虚页号}\\\hline \end{array}=\begin{array}{|c|c|}\hline \text{标记}&\text{TLB组号}\\\hline \end{array}\)

  • TLB组号：bits 14~12（虚页号的低3位，共3位）
  • TLB标记：bits 29~15（虚页号的高15位，共15位）

(3) 访问序列：VPN = 10, 12, 16, 7, 26, 4, 12, 20。哪个VPN对应的TLB表项被替换？

首先计算每个VPN映射到的TLB组（组号 = VPN mod 8，即VPN低3位）：因此，虚页号10、12、16、7、26、4、12、20映射到的 TLB 组号依次为 2、4、0、7、2、4、4、4。

只有第4组发生了3次以上访问（VPN 12、4、12、20），可能发生替换。追踪第4组状态：

初始状态：TLB第4组为空（2路）
访问VPN=12（第2次，组4）：Miss → 装入，组4 = [12]，LRU顺序：12最新
访问VPN=4（第6次，组4）：Miss → 装入，组4 = [12, 4]，LRU顺序：4最新，12最旧
访问VPN=12（第7次，组4）：Hit → 更新LRU，组4 = [12, 4]，LRU顺序：12最新，4最旧
访问VPN=20（第8次，组4）：Miss，组4已满（2路），按LRU淘汰最旧的4 → 替换VPN=4
组4 = [12, 20]

被替换的TLB表项对应 VPN = 4。

理由：访问VPN=20时，第4组已存放VPN 12和VPN 4，组满需替换。按LRU策略，VPN 4是最近最少使用的（最后一次使用是第6次，而VPN 12在第7次被重新使用），故淘汰VPN 4。

(4) 若虚拟地址位数增加到32位，则TLB表项的位数增加几位？

参数 原（30位虚拟地址） 新（32位虚拟地址）
虚页号位数 30 - 12 = 18位 32 - 12 = 20位
TLB组号位数 log₂8 = 3位（不变） 3位（不变）
TLB标记位数 18 - 3 = 15位 20 - 3 = 17位
增加位数 — 17 - 15 = 2位

TLB表项的标记字段增加 2位。（物理地址24位不变，物理页框号 = 24 - 12 = 12位不变，因此TLB表项中的页框号字段不增加位数。）

【2023-43】

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

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

已知二维数组a按行优先存放，在虚拟地址空间中分配的起始地址为0042 2000H，sizeof(int)=4，假定在M上执行上述程序段之前数组a不在主存，且在该程序段执行过程中不会发生页面置换。请回答下列问题。

(1) 数组a分为几个页面存储？对于数组a的访问，会发生几次缺页异常？页故障地址各是什么？

(2) 不考虑变量i和j，该程序段的数据访问是否具有时间局部性？为什么？

(3) 计算机M的虚拟地址（A31~A0）中哪几位用作块内地址？哪几位用作Cache组号？a[1][0]的虚拟地址是多少？其所在主存块对应的Cache组号是多少？

(4) 数组a占用多少主存块？假设上述程序段执行过程中数组a的访问不会和其他数据发生Cache访问冲突，则数组a的Cache命中率是多少？若将循环中i和j的次序按如下方式调换：

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

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

解析

(1) 数组a分为几个页面？会发生几次缺页异常？页故障地址各是什么？

数组a的大小：

元素个数 = 24 × 64 = 1536个
字节数   = 1536 × 4 = 6144字节 = 6KB

页面占用分析：起始地址 0x00422000 恰好是页边界（页内偏移 = 0x000）：

页0x422：0x422000 ~ 0x422FFF（4KB，存放a[0][0] ~ a[15][63]）
页0x423：0x423000 ~ 0x4237FF（2KB，存放a[16][0] ~ a[23][63]）
  a[16][0]的偏移 = 16×64×4 = 4096字节 → 地址0x423000（新页起始）
  a[23][63]的偏移 = (23×64+63)×4 = (1472+63)×4 = 1535×4 = 6140
  结束地址 = 0x422000 + 6140 = 0x4237FC

数组a共分为 2 个页面。

缺页次数：

执行中不发生页面置换，每个页面首次访问时产生1次缺页：

  • 第1次缺页：访问 a[0][0]（i=0, j=0），地址 0x00422000（页0x422首次访问）
  • 第2次缺页：访问 a[16][0]（i=16, j=0），地址 0x00423000（页0x423首次访问）

共发生 2次缺页异常，页故障地址分别为 0x0042 2000 和 0x0042 3000。

(2) 该程序段的数据访问是否具有时间局部性？为什么？

不具有时间局部性。

原因：程序段对数组a的每个元素执行"写操作"（a[i][j] = 10），每个元素在整个程序段执行过程中只被访问一次，写完之后不再被读取或写入。时间局部性要求同一数据在短时间内被多次访问，而这里每个数组元素仅访问一次，没有重复访问，因此不具备时间局部性。

注：空间局部性存在（按行顺序访问相邻元素），但时间局部性不存在。

(3) 虚拟地址各字段划分；a[1][0]的虚拟地址及对应Cache组号

虚拟地址格式为 公式 ，物理地址格式为 公式 ，页大小和页框号大小相同，页面大小为4KB= 公式 B，按字节编址，页内地址占低12位。也就是虚拟地址和物理地址的低12位相同。

Cache结构参数：

块大小    = 32B = 2⁵  → 块内偏移：5位（A4~A0）
数据区    = 8KB
4路组相联 → 组数 = 8KB ÷ (4 × 32B) = 8192 ÷ 128 = 64组 = 2⁶
           → 组索引：6位（A10~A5）

物理地址组相联映射格式为 公式，5+6=11<12，虚拟地址和物理地址的低11位一定相同。物理地址中低5位用作块内地址，低11位中高6位用作Cache组号。对应虚拟地址中低5位（A4~A0）用作块内地址，低11位中高6位（A10~A5）用作Cache组号。

a[1][0]的虚拟地址0042 2100H。因为a的起始地址为0042 2000H，一行有64个元素，一个元素占4个地址单元，所以a[1][0]的虚拟地址是0042 2000H+(64×1+0)×4H=0042 2100H。

a[1][0]所在主存块对应的Cache组号是8。因为a[1][0]的虚拟地址0042 2100H =公式 ，组号001 000B=8。

(4) 数组a占多少主存块？两种循环顺序下的Cache命中率各是多少？

数组a占用的主存块数：

主存块数 = 6144B ÷ 32B = 192块

分析Cache是否会发生冲突：

数组a的192个块分布在Cache的64组中，每组恰好 192÷64 = 3块。4路组相联每组可容纳4块，因此192块全部装入Cache不会发生组内冲突替换。

行优先循环（i外j内）的Cache命中率：

访问顺序：a[0][0], a[0][1], ..., a[0][63], a[1][0], ..., a[23][63]

每个主存块包含 32B/4B = 8个int元素：

  • 访问块内第1个元素：缺失（Miss），块调入Cache
  • 访问块内第2~8个元素：命中（Hit）
总访问次数 = 1536次
Miss次数   = 192次（每块首次访问）
Hit次数    = 1344次

Cache命中率 = 1344 / 1536 = 7/8 = 87.5%

列优先循环（j外i内）的Cache命中率：

访问顺序：a[0][0], a[1][0], ..., a[23][0], a[0][1], ..., a[23][63]

分析：

  • 访问a[0][0]时，块（含a[0][0]~a[0][7]）装入Cache（set 0）
  • 访问a[1][0]时，其块装入不同的Cache组（set 8），不冲突
  • ...访问完a[23][0]后，共加载24块，分布于8个不同的Cache组（每组3块，4路容纳）
  • 访问a[0][1]：与a[0][0]在同一块（偏移差4B，同在32B块内）→ Hit
  • 访问a[1][1]：与a[1][0]在同一块 → Hit
  • ...

规律：每8列（j=0～7, j=8～15, ...）中，第1列（首次访问每行）产生24次Miss，其余7列产生Hit。

Miss轮次 = 64列 ÷ 8 = 8轮
每轮Miss = 24次（24行首次访问新块）
总Miss   = 8 × 24 = 192次
总Hit    = 1536 - 192 = 1344次

列优先Cache命中率 = 1344 / 1536 = 7/8 = 87.5%

结论： 本例中由于数组a（6KB）小于Cache数据区（8KB），且192块恰好分配在64组中每组3块（4路可全部容纳），无论行优先还是列优先，Cache命中率均为 7/8（87.5%）。

若Cache容量不足以容纳整个数组（如直接映射或容量更小），则列优先会因频繁冲突导致命中率大幅下降，甚至趋近于0。本题特殊之处在于4路组相联缓解了冲突。

【2024-44】

（本题10 分）对于题 43 中的计算机 M，C 语言程序 P 包含的语句 “sum += a[i];” 在 M 中对应的指令序列 S 如下。

slli r4, r2, 2  // R[r4]←R[r2]<<2
add r4, r3, r4  // R[r4]←R[r3]+R[r4]
lw r5, 0(r4)    // R[r5]←M[R[r4]+0]
add r1, r1, r5  // R[r1]←R[r1]+R[r5]

已知变量 i、sum 和数组 a 都为 int 型，通用寄存器 r1~r5 的编号为 01 H ~ 05 H。

请回答下列问题。

(1) 根据指令序列 S 中每条指令的功能，写出存放数组 a 的首地址、变量 i、变量 sum 的通用寄存器编号。（3 分）

(2) 已知 M 为小端方式计算机，采用页式存储管理方式，页大小为 4 KB。若执行到指令序列 S 中第一条指令时，i=5，且 r1 和 r3 的内容分别为 0000 1332 H 和 0013 DFF0 H，从地址 0013 DFF0 H 开始的存储单元内容如题 44 图所示，则执行 “sum+=a[i];” 语句后，a[i] 的地址、a[i] 和 sum 的机器数分别是什么（用十六进制表示）？a[i] 所在页的页号是多少？此次执行中，数组 a 至少存放在几页中？（5 分）

1778315186111-ed22979a-b006-43f8-a5bc-cd6c01435c03.png

(3) 指令 “slli r4, r2, 2” 的机器码是什么（用十六进制表示）？若数组 a 改为 short 类型，则指令序列 S 中 slli 指令的汇编形式应是什么？（2 分）

解析

(1) 写出存放数组a首地址、变量i、变量sum的通用寄存器编号。

add r4,r3,r4：这条指令将寄存器 r3 和 r4 的值相加，结果存储在寄存器 r4 中。这对应于计算数组元素的内存地址（即&a[i]）。因此，我们可以推断出寄存器 r3 存储的是数组 a 的首地址，即 a 的寄存器编号为 03H。

slli r4,r2,2：这条指令将寄存器 r2 的值左移 2 位，2 结果存储在寄存器 r4 中。在 C 语言中，这对应于数组索引的计算（即 i*4，因为每个 int 类型占 4 字节）。因此，我们可以推断出寄存器 r2 存储的是变量 i 的值，即的寄存器编号位 02H。

add r1,rl,r5：这条指令将寄存器 r1 和 r5 的值相加，结果存储在寄存器 r1 中。这对应于累加操作（即 sum+=a[i])。因此，我们可以推断出寄存器 r1 存储的是变量 sum 的值，即 sum 的寄存器编号为 01H。

所以，数组 a 的首地址、变量 i 和 sum 的通用寄存器编号分别为 03H、02H 和 01H。

(2) 执行"sum+=a[i]"后，a[i]的地址、a[i]和sum的机器数；a[i]所在页的页号；数组a至少存放在几页中。

  • a[i] 的地址：已知 i = 5，int 类型占 4 字节。偏移量为公式 = 20 字节，即十六进制的 14 H。数组首地址为 0013 DFF0 H，因此 a[5] 的地址 = 0013 DFF0 H + 0014 H = 0013 E004 H。
  • a[i] 的机器数：查表可知，地址 0013 E004 H 开始的连续 4 个字节内容分别为：DC、EC、FF、FF。由于该计算机采用小端方式（低字节存放在低地址），因此拼接后的机器数为：FFFF ECDC H。
  • sum 的机器数：执行加法：sum = sum + a[i]即 0000 1332 H + FFFF ECDC H。按十六进制相加，忽略 32 位溢出产生的最高位进位，结果为：0000 000E H。
  • a[i] 所在页的页号：页大小为 4KB（即 公式 B），说明物理地址的低 12 位为页内偏移，高 20 位为页号。a[i] 的地址 0013 E004 H，截取高 20 位，其所在页的页号为：0013E H（或写为 13E H）。
  • 数组 a 至少存放在几页中：数组首地址在 0013 DFF0 H，它所在的页面（页号 0013D H）结束地址为 0013D FFF H。该页剩余可用空间为 1000 H - FF0 H = 10 H 字节（即 16 字节），刚好能存放 4 个 int 型元素（a[0]、a[1]、a[2]、a[3]）。而本题中访问到了 a[5]，说明 a[4] 和 a[5] 被存放在了下一个相邻的页面（页号 0013E H）中。因此，数组 a 至少跨越了 2 页。

(3) "slli r4, r2, 2"的机器码；若数组a改为short类型，slli指令应如何修改？

指令的机器码： 根据图 43(a) 给出的 slli 指令格式： 000 0000(7位) | shamt(5位) | rs1(5位) | 010(3位) | rd(5位) | 001 0011(7位)

对于 slli r4, r2, 2：

  • rd = r4 = 04 H = 00100
  • rs1 = r2 = 02 H = 00010
  • shamt = 2 = 00010

拼接二进制：0000 000 | 0 0010 | 00010 | 010 | 00100 | 0010011 按 4 位一组转换为十六进制：0000_0000_0010_0001_0010_0010_0001_0011 机器码为：0021 2213 H。

改为 short 类型后的汇编形式： 若数组 a 为 short 类型，则每个元素占 2 个字节。计算偏移量时，应该将下标 i 乘以 2（即左移 1 位），而不是乘以 4。 因此，slli 指令的汇编形式应改为：slli r4, r2, 1。