408 真题做题本·操作系统部分

第 3 章 内存管理

3.1 基本内存管理

1. 【2009】分区分配内存管理方式的主要保护措施是（ ）。

A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护

答案： A

解析： 分区分配方式为每个进程分配一段连续的内存区域。为了防止进程访问本分区以外的地址，通常设置基址寄存器和限长寄存器，或使用上、下界寄存器进行界地址检查。程序代码、数据和栈的保护属于更具体的访问权限保护，不是分区分配方式的主要保护措施。

2. 【2010】某基于动态分区存储管理的计算机，其主存容量为 55MB（初始为空闲），采用最佳适配（Best Fit）算法，分配和释放的顺序为：分配 15MB，分配 30MB，释放 15MB，分配 8MB，分配 6MB，此时主存中最大空闲分区的大小是（ ）。

A. 7MB
B. 9MB
C. 10MB
D. 15MB

答案： B

解析： 按顺序分析：

• 初始有一个 55MB 的空闲分区；
• 分配 15MB 后，剩余 40MB；
• 再分配 30MB 后，剩余 10MB；
• 释放先前的 15MB 后，空闲分区大小为 15MB 和 10MB；
• 按最佳适配算法分配 8MB，应从 10MB 分区中分配，留下 2MB；
• 再分配 6MB，应从 15MB 分区中分配，留下 9MB。

因此空闲分区为 2MB 和 9MB，最大空闲分区为 9MB。

3. 【2011】在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（ ）。

A. 编辑
B. 编译
C. 链接
D. 装载

答案： B

解析： 源程序经过编译后形成目标模块，编译器为程序中的指令和数据生成逻辑地址（相对地址）。链接阶段将多个目标模块及库函数组合成装入模块；装载阶段把装入模块装入内存；程序运行时，地址变换机构再把逻辑地址转换为物理地址。因此逻辑地址形成于编译阶段。

4. 【2017】某计算机按字节编址，其动态分区内存管理采用最佳适应算法，每次分配和回收内存后都对空闲分区链重新排序，当前空闲分区信息如下表所示：

分区起始地址	20K	500K	1000K	200K
分区大小	40KB	80KB	100KB	200KB

回收起始地址为 60K、大小为 140KB 的分区后，系统中空闲分区的数量、空闲分区链第一个分区的起始地址和大小分别是（ ）。

A. 3、20K、380KB
B. 3、500K、80KB
C. 4、20K、180KB
D. 4、500K、80KB

答案： B

解析： 待回收分区的地址范围为 $[60\text{K},200\text{K})$。

• 起始地址为 20K、大小为 40KB 的空闲分区范围为 $[20\text{K},60\text{K})$，与回收分区前邻接；
• 起始地址为 200K、大小为 200KB 的空闲分区范围为 $[200\text{K},400\text{K})$，与回收分区后邻接。

三者合并后得到起始地址为 20K、大小为

$$40+140+200=380\text{KB}$$

的空闲分区。系统此时共有 380KB、80KB、100KB 三个空闲分区。最佳适应算法按分区大小从小到大组织空闲分区链，因此链首是起始地址 500K、大小 80KB 的分区。

5. 【2019】在下列动态分区分配算法中，最容易产生内存碎片的是（ ）。

A. 首次适应算法
B. 最坏适应算法
C. 最佳适应算法
D. 循环首次适应算法

答案： C

解析： 最佳适应算法总是选择能满足请求的最小空闲分区。分配后往往留下大量很小、难以再次利用的空闲分区，因此最容易形成较多的外部碎片。

6. 【2009】一个分段存储管理系统中，地址长度为 32 位，其中段号占 8 位，则最大段长是（ ）。

A. $2^8$ 字节
B. $2^{16}$ 字节
C. $2^{24}$ 字节
D. $2^{32}$ 字节

答案： C

解析： 32 位逻辑地址中段号占 8 位，段内偏移量占

$$32-8=24$$

位。段内偏移量可表示 $0$ 到 $2^{24}-1$，所以单个段的最大长度为 $2^{24}$ 字节。

7. 【2010】某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为 $2^{10}$ 字节，页表项大小为 2 字节，逻辑地址空间大小为 $2^{16}$ 页。

页目录号	页号	页内偏移量

则表示逻辑地址空间的页目录表中表项的个数至少是（ ）。

A. 64
B. 128
C. 256
D. 512

答案： B

解析： 一个二级页表通常占一页。每页可容纳的页表项数为

$$\frac{2^{10}}{2}=2^9=512.$$

逻辑地址空间共有 $2^{16}$ 个页面，因此所需二级页表数，也就是页目录表至少需要的表项数为

$$\frac{2^{16}}{2^9}=2^7=128.$$

8. 【2014】下列选项中，属于多级页表优点的是（ ）。

A. 加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间

答案： D

解析： 多级页表把一个大页表拆成若干较小的页表，各级页表可分散存放，且未使用的虚拟地址范围可以不建立对应的下级页表，因此减少了页表对连续内存空间的要求。多级页表本身会增加地址转换时的访存次数，不能加快地址变换，也不会直接减少缺页次数或单个页表项的大小。

9. 【2016】某进程的段表内容如下表所示。当访问段号为 2、段内地址为 400 的逻辑地址时，地址转换的结果是（ ）。

段号	段长	内存起始地址	权限	状态
0	100	6000	只读	在内存
1	200	—	读写	不在内存
2	300	4000	读写	在内存

A. 段缺失异常
B. 得到内存地址 4400
C. 越权异常
D. 越界异常

答案： D

解析： 段号 2 对应的段长为 300，合法段内地址范围为 $0$ 到 $299$。题中段内地址为 400，超过段长，因此在进行地址相加之前就会发生越界异常。虽然该段已在内存且具有读写权限，但这些条件不能消除越界错误。

10. 【2019】在分段存储管理系统中，用共享段表描述所有被共享的段。若进程 P1 和 P2 共享段 S，下列叙述中，错误的是（ ）。

A. 在物理内存中仅保存一份段 S 的内容
B. 段 S 在 P1 和 P2 中应该具有相同的段号
C. P1 和 P2 共享段 S 在共享段表中的段表项
D. P1 和 P2 都不再使用段 S 时才回收段 S 所占的内存空间

答案： B

解析： 共享段在物理内存中只保存一份，多个进程的段表项可指向同一个共享段表项或同一物理段。由于每个进程具有独立的逻辑地址空间，同一共享段在不同进程中可以使用不同的段号，并不要求段号相同。只有所有共享该段的进程都不再使用它时，才可回收其物理内存。

11. 【2019】某计算机主存按字节编址，采用二级分页存储管理，虚拟地址结构如下图所示。

页目录号（10 位）	页号（10 位）	页内偏移量（12 位）

虚拟地址 20501225H 对应的页目录号、页号分别是（ ）。

A. 081H、101H
B. 081H、401H
C. 201H、101H
D. 201H、401H

答案： A

解析： 页内偏移量占低 12 位，页号占其上的 10 位，页目录号占最高 10 位。因此

$$\text{页目录号}=(\text{20501225H}\gg 22)\&\text{3FFH}=\text{081H},$$ $$\text{页号}=(\text{20501225H}\gg 12)\&\text{3FFH}=\text{101H}.$$

12. 【2020】下列因素中，影响请求分页系统有效（平均）访存时间的是（ ）。
    I. 缺页率　II. 磁盘读写时间　III. 内存访问时间　IV. 执行缺页处理程序的 CPU 时间

A. 仅 II、III
B. 仅 I、IV
C. 仅 I、III、IV
D. I、II、III 和 IV

答案： D

解析： 请求分页系统的有效访存时间由正常访存和缺页处理两部分共同决定，可概括为

$$EAT=(1-p)T_{\text{正常访存}}+p{T}_{\text{缺页处理}},$$

其中 $p$ 为缺页率。正常访存时间与内存访问时间有关；缺页处理包括执行缺页处理程序、必要的磁盘换入或换出等操作。因此四项都会影响平均访存时间。

13. 【2021】在采用二级页表的分页系统中，CPU 页表基址寄存器中的内容是（ ）。

A. 当前进程的一级页表的起始虚拟地址
B. 当前进程的一级页表的起始物理地址
C. 当前进程的二级页表的起始虚拟地址
D. 当前进程的二级页表的起始物理地址

答案： B

解析： 页表基址寄存器用于启动硬件地址转换，MMU 必须能够直接据此访问当前进程的最高级页表，因此其中保存的是当前进程一级页表（页目录）的起始物理地址。二级页表的起始物理地址由一级页表项给出。

14. 【2022】某进程访问的页 b 不在内存中，导致产生缺页异常，该缺页异常处理过程中不一定包含的操作是（ ）。

A. 淘汰内存中的页
B. 建立页号与页框号的对应关系
C. 将页 b 从外存读入内存
D. 修改页表中页 b 对应的存在位

答案： A

解析： 缺页处理必须为页 b 确定页框，将其从外存调入内存，并修改页表项中的页框号、存在位等信息。如果系统中存在空闲页框，就可直接使用，无须淘汰任何内存页；只有没有空闲页框时才需要执行页面置换。

15. 【2023】进程 R 和 S 共享数据 data，若 data 在 R 和 S 中所在页的页号分别为 p1 和 p2，两个页所对应的页框号分别为 f1 和 f2，则下列叙述中，正确的是（ ）。

A. p1 和 p2 一定相等，f1 和 f2 一定相等
B. p1 和 p2 一定相等，f1 和 f2 不一定相等
C. p1 和 p2 不一定相等，f1 和 f2 一定相等
D. p1 和 p2 不一定相等，f1 和 f2 不一定相等

答案： C

解析： 进程 R 和 S 各自拥有独立的虚拟地址空间，所以同一共享数据在两个进程中的虚页号可以不同，即 p1 和 p2 不一定相等。共享的本质是两个虚页映射到同一物理页框，因此 f1 和 f2 必须相等。

16. 【2024】下列算法中，每次回收分区时仅合并大小相等的空闲分区的是（ ）。

A. 伙伴算法
B. 最佳适应算法
C. 最坏适应算法
D. 首次适应算法

答案： A

解析： 伙伴算法把内存划分为大小为 $2^k$ 的分区。释放一个分区时，只有当它的“伙伴”分区同样空闲且大小相等时，二者才能合并成一个更大的分区。其余三种算法属于动态分区分配算法，并不限定只能合并大小相等的空闲分区。

17. 【2013】（8 分）某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答下列问题：

（1）若使用一级页表的分页存储管理方式，逻辑地址结构如下：

页号（20 位）	页内偏移量（12 位）

则页的大小是多少字节？页表最大占用多少字节？

（2）若使用二级页表的分页存储管理方式，逻辑地址结构如下：

页目录号（10 位）	页表索引（10 位）	页内偏移量（12 位）

设逻辑地址为 LA，请分别给出其对应的页目录号和页表索引的表达式。

（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为 00008000H，其长度为 8KB，被装载到从物理地址 00900000H 开始的连续主存空间中。页表从主存 00200000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。

请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号以及代码页面 2 的起始物理地址。

答案：

（1）页大小为 4096B，一级页表最大占用 4MB。

（2）页目录号和页表索引分别为

$$\text{页目录号}=(LA\gg 22)\&\text{3FFH},$$ $$\text{页表索引}=(LA\gg 12)\&\text{3FFH}.$$

（3）两个页表项的物理地址分别为 00200020H、00200024H；页框号分别为 00900H、00901H；代码页面 2 的起始物理地址为 00901000H。

解析：

（1）页内偏移量占 12 位，所以页大小为

$$2^{12}=4096\text{B}=4\text{KB}.$$

页号占 20 位，最多有 $2^{20}$ 个虚页，每个页表项占 4B，因此一级页表最大占用

$$2^{20}\times 4=2^{22}\text{B}=4\text{MB}.$$

（2）32 位逻辑地址的最高 10 位是页目录号，中间 10 位是页表索引，最低 12 位是页内偏移量，所以可用移位和掩码运算得到上述表达式。也可写成

$$\text{页目录号}=\lfloor \frac{LA}{2^{22}}\rfloor ,$$ $$\text{页表索引}=\lfloor \frac{LA}{2^{12}}\rfloor \mathrm{mod}{2}^{10}.$$

（3）代码段从逻辑地址 00008000H 开始，页大小为 1000H，因此它占用虚页 8 和虚页 9。页表起始物理地址为 00200000H，每个页表项占 4B，所以：

$$\text{虚页 8 的页表项地址}=\text{00200000H}+8\times 4=\text{00200020H},$$ $$\text{虚页 9 的页表项地址}=\text{00200000H}+9\times 4=\text{00200024H}.$$

代码段连续装入从 00900000H 开始的两个页框，故两个页框号为

$$\frac{\text{00900000H}}{\text{1000H}}=\text{00900H},$$ $$\frac{\text{00901000H}}{\text{1000H}}=\text{00901H}.$$

代码页面 2 是第二个代码页，其起始物理地址为 00901000H。

3.2 虚拟内存管理

1. 【2011】在缺页处理过程中，操作系统执行的操作可能是（ ）。
   I. 修改页表　II. 磁盘 I/O　III. 分配页框

A. 仅 I、II
B. 仅 II
C. 仅 III
D. I、II、III

答案： D

解析： 发生缺页时，操作系统需要为所缺页面分配一个空闲页框，或通过页面置换获得页框；随后通过磁盘 I/O 将页面调入内存；最后修改页表项中的页框号、存在位等信息。因此三项操作都可能发生。

2. 【2011】当系统发生抖动（thrashing）时，可采用的有效措施是（ ）。
   I. 撤销部分进程　II. 增加磁盘交换区的容量　III. 提高用户进程的优先级

A. 仅 I
B. 仅 II
C. 仅 III
D. 仅 I、II

答案： A

解析： 抖动的根本原因是系统中同时运行的进程过多，各进程获得的页框不足，导致频繁缺页。撤销或挂起部分进程可以降低多道程序度，使剩余进程获得更多页框，从而缓解抖动。增加交换区容量只能扩大外存交换空间，不能减少缺页；提高进程优先级也不能改善其驻留集不足的问题。

3. 【2012】下列关于虚拟存储的叙述中，正确的是（ ）。

A. 虚拟存储只能基于连续分配技术
B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制
D. 虚拟存储容量只受内存容量的限制

答案： B

解析： 虚拟存储器要求程序的一部分可以装入内存、其余部分暂留外存，因此必须基于分页、分段或段页式等非连续分配技术。虚拟地址空间的最大容量还受 CPU 地址位数限制，并非只由内存或外存容量决定。

4. 【2013】若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是（ ）。
   I. 处理越界错　II. 置换页　III. 分配内存

A. 仅 I、II
B. 仅 II、III
C. 仅 I、III
D. I、II、III

答案： B

解析： 缺页表示所访问的逻辑地址合法，但对应页面当前不在内存，因此不属于越界访问。缺页处理时，若有空闲页框则可直接分配内存；若无空闲页框则需要置换一个页面，所以 II、III 都可能发生。

5. 【2014】下列措施中，能加快虚实地址转换的是（ ）。
   I. 增大快表（TLB）容量　II. 让页表常驻内存　III. 增大交换区（swap）

A. 仅 I
B. 仅 II
C. 仅 I、II
D. 仅 II、III

答案： C

解析： 增大 TLB 容量通常可提高 TLB 命中率，减少查页表的次数；让页表常驻内存可避免访问页表时再次产生缺页，两者都能加快地址转换。增大交换区只增加外存交换空间，不会缩短虚实地址转换过程。

6. 【2014】在页式虚拟存储管理系统中，采用某些页面置换算法会出现 Belady 异常现象，即进程的缺页次数会随着分配给该进程的页框个数增加而增加。下列算法中，可能出现 Belady 异常现象的是（ ）。
   I. LRU 算法　II. FIFO 算法　III. OPT 算法

A. 仅 II
B. 仅 I、II
C. 仅 I、III
D. 仅 II、III

答案： A

解析： FIFO 算法不具有栈性质，可能发生 Belady 异常。LRU 和 OPT 都属于栈式页面置换算法，分配更多页框时，较小驻留集始终是较大驻留集的子集，因此缺页次数不会反而增加。

7. 【2015】请求分页系统中，分配策略与置换策略不能组合使用的是（ ）。

A. 可变分配、全局置换
B. 可变分配、局部置换
C. 固定分配、全局置换
D. 固定分配、局部置换

答案： C

解析： 全局置换允许一个进程从系统所有可置换页框中选择牺牲页，因此各进程实际占用的页框数会动态变化，与“固定分配”矛盾。可变分配可与全局或局部置换结合，固定分配则只能与局部置换结合。

8. 【2015】系统为某进程分配了 4 个页框，该进程已访问的页号序列为 2，0，2，9，3，4，2，8，2，4，8，4，5。若进程要访问的下一页的页号为 7，依据 LRU 算法，应淘汰页的页号是（ ）。

A. 2
B. 3
C. 4
D. 8

答案： A

解析： 按 LRU 算法处理已给访问序列后，驻留的 4 个页面为 $\{2,4,8,5\}$。它们最近一次被访问的位置分别是：页 2 在序列第 9 次访问，页 8 在第 11 次，页 4 在第 12 次，页 5 在第 13 次。因此页 2 最久未被使用，访问页 7 时应淘汰页 2。

9. 【2016】某系统采用改进型 CLOCK 置换算法，页表项中字段 A 为访问位，M 为修改位。A=0 表示页最近没有被访问，A=1 表示页最近被访问过；M=0 表示页没有被修改过，M=1 表示页被修改过。按 $(A,M)$ 所有可能的取值，将页分为四类：$(0,0)$、$(1,0)$、$(0,1)$ 和 $(1,1)$，则该算法淘汰页的次序为（ ）。

A. $(0,0),(0,1),(1,0),(1,1)$
B. $(0,0),(1,0),(0,1),(1,1)$
C. $(0,0),(0,1),(1,1),(1,0)$
D. $(0,0),(1,1),(0,1),(1,0)$

答案： A

解析： 改进型 CLOCK 算法优先淘汰“近期未访问且未修改”的页，其次是“近期未访问但已修改”的页，再考虑近期访问过的页。因此四类页面的优先级从高到低为

$$(0,0)\to (0,1)\to (1,0)\to (1,1).$$

其中修改过的页被淘汰时需要写回外存，代价更大。

10. 【2016】某进程访问页面的序列如下图所示：

Text

..., 1, 3, 4, 5, 6, 0, 3, 2, 3, 2, t, 0, 4, 0, 3, 2, 9, 2, 1, ...

若工作集的窗口大小为 6，则在 t 时刻的工作集为（ ）。

A. $\{6,0,3,2\}$
B. $\{2,3,0,4\}$
C. $\{0,4,3,2,9\}$
D. $\{4,5,6,0,3,2\}$

答案： A

解析： 窗口大小为 6，t 时刻向前考察最近 6 次页面访问，依次为

$$6,0,3,2,3,2.$$

去除重复页号后，工作集为 $\{6,0,3,2\}$。

11. 【2019】某系统采用 LRU 页置换算法和局部置换策略，若系统为进程 P 预分配了 4 个页框，进程 P 访问页号的序列为 0，1，2，7，0，5，3，5，0，2，7，6，则进程访问上述页的过程中，产生页置换的总次数是（ ）。

A. 3
B. 4
C. 5
D. 6

答案： C

解析： 前四个不同页面 0、1、2、7 依次装入 4 个空闲页框，只产生缺页，不发生置换。此后：

• 访问 0：命中；
• 访问 5：淘汰最久未用的页 1，第 1 次置换；
• 访问 3：淘汰页 2，第 2 次置换；
• 访问 5、0：均命中；
• 访问 2：淘汰页 7，第 3 次置换；
• 访问 7：淘汰页 3，第 4 次置换；
• 访问 6：淘汰页 5，第 5 次置换。

因此共发生 5 次页面置换。

12. 【2020】下列因素中，影响请求分页系统有效（平均）访存时间的是（ ）。
    I. 缺页率　II. 磁盘读写时间　III. 内存访问时间　IV. 执行缺页处理程序的 CPU 时间

A. 仅 II、III
B. 仅 I、IV
C. 仅 I、III、IV
D. I、II、III 和 IV

答案： D

解析： 有效访存时间既与正常访问内存的时间有关，也与发生缺页的概率及一次缺页处理的总开销有关。缺页处理开销包括执行异常处理程序、磁盘读写、更新页表等，因此 I、II、III、IV 都会影响平均访存时间。

13. 【2021】某请求分页存储系统的页大小为 4KB，按字节编址。系统给进程 P 分配 2 个固定的页框，并采用改进型 CLOCK 置换算法，进程 P 页表的部分内容如下表所示。

页号	页框号	存在位（1：存在，0：不存在）	访问位（1：访问，0：未访问）	修改位（1：修改，0：未修改）
...	...	...	...	...
2	20H	0	0	0
3	60H	1	1	0
4	80H	1	1	1
...	...	...	...	...

若 P 访问虚拟地址为 02A01H 的存储单元，则经地址变换后得到的物理地址是（ ）。

A. 00A01H
B. 20A01H
C. 60A01H
D. 80A01H

答案： C

解析： 页大小为 4KB，即 1000H。虚拟地址 02A01H 可分解为：

$$\text{页号}=2,\text{页内偏移量}=\text{A01H}.$$

页 2 的存在位为 0，访问时发生缺页。当前两个驻留页的状态分别为页 3 的 $(A,M)=(1,0)$ 和页 4 的 $(1,1)$。改进型 CLOCK 算法扫描并清除访问位后，页 3 先成为优先级最高的 $(0,0)$ 类页面，因此淘汰页 3，把页 2 装入页框 60H。最终物理地址为

$$\text{60H}\times \text{1000H}+\text{A01H}=\text{60A01H}.$$

原页表中页 2 的页框号 20H 在存在位为 0 时无效，不能直接用于地址转换。

14. 【2022】下列选项中，不会影响系统缺页率的是（ ）。

A. 页置换算法
B. 工作集的大小
C. 进程的数量
D. 页缓冲队列的长度

答案： D

解析： 页置换算法会影响牺牲页的选择；工作集大小反映进程当前需要的页面集合；进程数量会影响每个进程可获得的页框数，这些都可能改变缺页率。页缓冲队列主要用于缩短缺页处理时的 I/O 等待时间，不改变进程访问页面时是否命中的判定，因此不会影响缺页率。

15. 【2023】对于采用虚拟内存管理方式的系统，下列关于进程虚拟地址空间的叙述中，错误的是（ ）。

A. 每个进程都有自己独立的虚拟地址空间
B. C 语言中 malloc（ ） 函数返回的是虚拟地址
C. 进程对数据段和代码段可以有不同的访问权限
D. 虚拟地址空间的大小由内存和硬盘的大小决定

答案： D

解析： 每个进程通常具有独立的虚拟地址空间，malloc() 返回的是进程虚拟地址空间中的地址，页表还可为代码页、数据页设置不同的读、写、执行权限。虚拟地址空间的理论大小主要由体系结构规定的虚拟地址位数决定，并非由当前内存和硬盘容量共同决定，因此 D 错误。

16. 【2009】请求分页管理系统中，假设某进程的页表内容如下表所示。页面大小为 4KB。

页号	页框（Page Frame）号	有效位（存在位）
0	101H	1
1	—	0
2	254H	1

一次内存的访问时间是 100ns，一次快表（TLB）的访问时间是 10ns，处理一次缺页的平均时间为 $10^8\text{ns}$（已含更新 TLB 和页表的时间）。进程的驻留集大小固定为 2，采用最近最久未使用置换算法（LRU）和局部淘汰策略。假设：

① TLB 初始为空；

② 地址转换时先访问 TLB，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间）；

③ 有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。

设有虚地址访问序列 2362H、1565H、25A5H，请回答：

（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。

（2）基于上述访问序列，虚地址 1565H 的物理地址是多少？请说明理由。

答案：

（1）依次为 $210\text{ns}$、$100000220\text{ns}$、$110\text{ns}$。

（2）物理地址为 101565H。

解析： 页面大小为 4KB，即

$$4\text{KB}=2^{12}\text{B}=1000\text{H}.$$

因此，虚拟地址的高位为页号，低 12 位为页内偏移量。

（1）访问 2362H：

$$2362\text{H}=2\times 1000\text{H}+362\text{H}.$$

页号为 2，页内偏移量为 362H。页 2 在内存中，但 TLB 初始为空，因此先发生 TLB 未命中，再访问页表，最后访问一次主存中的目标单元，所需时间为

$$10+100+100=210\text{ns}.$$

访问后，页 2 的页表项被调入 TLB，且页 2 成为最近使用的页面。

访问 1565H：

$$1565\text{H}=1\times 1000\text{H}+565\text{H}.$$

页号为 1，页内偏移量为 565H。TLB 中没有页 1 的表项，访问页表后发现页 1 的有效位为 0，因此发生缺页异常。第一次执行到发现缺页所需时间为

$$10+100=110\text{ns}.$$

缺页处理时间为 $10^8\text{ns}$。缺页处理结束后，产生缺页的指令重新执行。由于缺页处理时间已经包含更新页表和 TLB 的时间，重新执行时 TLB 命中，所需时间为

$$10+100=110\text{ns}.$$

故本次访问总时间为

$$110+10^8+110=100000220\text{ns}.$$

由于驻留集大小固定为 2，页 1 调入时必须淘汰一个已有页面。此前刚访问过页 2，所以按 LRU 算法应淘汰页 0，页 1 被装入页 0 原来占用的 101H 号页框。

访问 25A5H：

$$25A5\text{H}=2\times 1000\text{H}+5A5\text{H}.$$

页号为 2。页 2 仍在内存中，且其表项已在 TLB 中，因此 TLB 命中，只需访问 TLB 和主存各一次：

$$10+100=110\text{ns}.$$

（2）页 1 被装入 101H 号页框，故虚地址 1565H 对应的物理地址为

$$101\text{H}\times 1000\text{H}+565\text{H}=101565\text{H}.$$

17. 【2010】设某计算机的逻辑地址空间和物理地址空间均为 64KB，按字节编址。若某进程最多需要 6 页数据存储空间，页大小为 1KB，操作系统采用固定分配、局部置换策略为此进程分配 4 个页框。在时刻 260 前，该进程的访问情况如下表所示（访问位即使用位）。当该进程执行到时刻 260 时，要访问逻辑地址为 17CAH 的数据。请回答下列问题：

页号	页框号	装入时刻	访问位
0	7	130	1
1	4	230	1
2	2	200	1
3	9	160	1

（1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。

（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针沿顺时针方向移动，且当前指向 2 号页框，示意图见下图）。

答案：

（1）页号为 5。

（2）物理地址为 1FCAH。

（3）物理地址为 0BCAH。

解析： 页大小为 1KB，即

$$1\text{KB}=2^{10}\text{B}=400\text{H}.$$

逻辑地址 17CAH 可分解为

$$17CA\text{H}=5\times 400\text{H}+3CA\text{H}.$$

因此，页号为 5，页内偏移量为 3CAH。页 5 当前不在内存中，访问时发生缺页。

（2）FIFO 算法淘汰最早进入内存的页面。四个页面的装入时刻分别为 130、230、200、160，其中页 0 的装入时刻 130 最早，故淘汰页 0。页 5 被装入页 0 原占用的 7 号页框，所以物理地址为

$$7\times 400\text{H}+3CA\text{H}=1C00\text{H}+3CA\text{H}=1FCA\text{H}.$$

（3）CLOCK 指针当前指向 2 号页框，而四个驻留页的访问位均为 1。算法从当前指针位置开始顺时针扫描：第一次扫描到各页时，将访问位由 1 清为 0，并继续移动指针。扫描一周后再次回到 2 号页框，此时其访问位已经为 0，因此淘汰 2 号页框中的页 2，将页 5 装入 2 号页框。

物理地址为

$$2\times 400\text{H}+3CA\text{H}=800\text{H}+3CA\text{H}=0BCA\text{H}.$$

18. 【2011】（12 分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为 16MB，主存（物理）地址空间大小为 1MB，页面大小为 4KB；Cache 采用直接映射方式，共 8 行；主存与 Cache 之间交换的块大小为 32B。系统运行到某一时刻时，页表、Cache 和 TLB 的部分内容如下。

页表部分内容

虚页号	有效位	页框号	...
0	1	06	...
1	1	04	...
2	1	15	...
3	1	02	...
4	0	—	...
5	1	2B	...
6	0	—	...
7	1	32	...

Cache 部分内容

行号	有效位	标记	...
0	1	020	...
1	0	—	...
2	1	01D	...
3	1	105	...
4	1	064	...
5	1	14D	...
6	0	—	...
7	1	27A	...

TLB 当前内容

组号	路 1 有效位	路 1 标记	路 1 页框号	路 2 有效位	路 2 标记	路 2 页框号	路 3 有效位	路 3 标记	路 3 页框号	路 4 有效位	路 4 标记	路 4 页框号
0	0	—	—	1	001	15	0	—	—	1	012	1F
1	1	013	2D	0	—	—	1	008	7E	0	—	—

请回答下列问题：

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

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

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

（4）假定为该机配置一个四路组相联的 TLB，共可存放 8 个页表项，则此时虚拟地址 024BACH 所在的页面是否存在主存中？要求说明理由。

答案：

（1）虚拟地址为 24 位，其中第 23～12 位为虚页号；物理地址为 20 位，其中第 19～12 位为页框号。

（2）物理地址划分为：标记 12 位、Cache 行号 3 位、块内地址 5 位。

（3）该页面在主存中，物理地址为 04C60H；访问 Cache 不命中。

（4）该页面在主存中。

解析：

（1）虚拟地址空间大小为 16MB：

$$16\text{MB}=2^{24}\text{B},$$

故虚拟地址为 24 位。页面大小为 4KB：

$$4\text{KB}=2^{12}\text{B},$$

所以页内偏移量占低 12 位，即第 11～0 位；虚页号占高 12 位，即第 23～12 位。

主存空间大小为 1MB：

$$1\text{MB}=2^{20}\text{B},$$

故物理地址为 20 位。页内偏移量仍占低 12 位，页框号占高 8 位，即第 19～12 位。

（2）Cache 采用直接映射，共 8 行，因此 Cache 行号需要

$${\log }_{2}8=3$$

位。块大小为 32B，因此块内地址需要

$${\log }_{2}32=5$$

位。物理地址总长为 20 位，所以标记位数为

$$20-3-5=12.$$

因此，物理地址从高位到低位的划分为：

• 第 19～8 位：标记，12 位；
• 第 7～5 位：Cache 行号，3 位；
• 第 4～0 位：块内地址，5 位。

（3）虚拟地址 001C60H 的虚页号和页内偏移量分别为

$$\text{虚页号}=001\text{H},\text{页内偏移}=C60\text{H}.$$

由页表可知，虚页 1 的有效位为 1，页框号为 04H，因此页面在主存中，对应物理地址为

$$04\text{H}\times 1000\text{H}+C60\text{H}=04C60\text{H}.$$

对物理地址 04C60H 进行 Cache 地址划分：

$$\text{Cache 行号}=\left(04C60\text{H}÷20\text{H}\right)\mathrm{mod}8=3,$$

标记为

$$04C60\text{H}÷100\text{H}=04C\text{H}.$$

Cache 第 3 行的有效位为 1，但其标记为 105H，与 04CH 不同，因此 Cache 不命中。

（4）TLB 共 8 项、四路组相联，因此共有

$$\frac{8}{4}=2$$

组，组号占虚页号最低 1 位，其余高位作为 TLB 标记。

虚拟地址 024BACH 的虚页号为 024H。因为

$$024\text{H}\mathrm{mod}2=0,$$

所以应查找 TLB 第 0 组；其标记为

$$024\text{H}÷2=012\text{H}.$$

第 0 组中存在有效的标记 012H，对应页框号 1FH，故 TLB 命中，由此可知该页面当前在主存中。

19. 【2012】某请求分页系统的局部页面置换策略如下：系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计）。本轮没有被访问过的页框将被系统回收，并放入空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中的页框号依次为 32、15、21、41。进程 P 依次访问的 $⟨\text{虚拟页号},\text{访问时刻}⟩$ 为：$⟨1,1⟩$、$⟨3,2⟩$、$⟨0,4⟩$、$⟨0,6⟩$、$⟨1,11⟩$、$⟨0,13⟩$、$⟨2,14⟩$。请回答下列问题：

（1）访问 $⟨0,4⟩$ 时，对应的页框号是什么？

（2）访问 $⟨1,11⟩$ 时，对应的页框号是什么？说明理由。

（3）访问 $⟨2,14⟩$ 时，对应的页框号是什么？说明理由。

（4）该策略是否适合于时间局部性好的程序？说明理由。

答案：

（1）21 号页框。

（2）32 号页框。

（3）41 号页框。

（4）适合。

解析： 初始空闲页框链为

$$32\to 15\to 21\to 41.$$

时刻 1 访问页 1，页 1 尚未使用过，因此从空闲链表头取出 32 号页框；时刻 2 访问页 3，取出 15 号页框；时刻 4 访问页 0，取出 21 号页框。因此：

（1）访问 $⟨0,4⟩$ 时对应 21 号页框。

时刻 5 进行第一轮扫描。页 1、页 3、页 0 在时刻 0～5 内都被访问过，所以均保留在驻留集中，同时为下一轮扫描重新记录访问情况。

时刻 6 再次访问页 0。在时刻 5～10 这一轮中，页 0 被访问，页 1 和页 3 没有被访问。因此时刻 10 扫描时，页 1 所在的 32 号页框和页 3 所在的 15 号页框被回收到空闲链表尾部，但页框中的内容暂不清除。

时刻 11 再次访问页 1。由于页 1 的内容仍保存在空闲链表中的 32 号页框内，系统直接将该页框重新放回驻留集，无需从外存重新调入页面。因此：

（2）对应 32 号页框。

时刻 14 访问页 2。页 2 以前没有被使用过，因而不可能在空闲页框链中保留其副本，只能从空闲页框链表头取页框。此时链首仍为初始未分配的 41 号页框，因此：

（3）对应 41 号页框。

（4）该策略适合时间局部性好的程序。时间局部性好的程序往往会在较短时间内重复访问最近使用过的页面。该策略保留近期访问过的页面；即使某页被暂时回收到空闲链表，只要页框尚未再次分配，其内容仍然保留，页面再次访问时可以快速恢复到驻留集，从而减少磁盘读入次数和缺页处理开销。

20. 【2015】某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：

页目录号（10 位）	页号（10 位）	页内偏移量（12 位）

请回答下列问题：

（1）页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？

（2）假定页目录项和页表项均占 4 个字节，则进程的页目录和页表共占多少页？要求写出计算过程。

（3）若某指令周期内访问的虚拟地址为 01000000H 和 01112048H，则进行地址转换时共访问多少个二级页表？要求说明理由。

答案：

（1）页和页框大小均为 4096B，虚拟地址空间共有 $2^{20}$ 页。

（2）页目录和所有二级页表共占 1025 页。

（3）共涉及 1 个二级页表。

解析：

（1）页内偏移量占 12 位，因此页和页框大小均为

$$2^{12}=4096\text{B}=4\text{KB}.$$

虚页号由页目录号和页号共同组成，共 20 位，因此虚拟地址空间包含

$$2^{10+10}=2^{20}$$

个虚页。

（2）页目录共有 $2^{10}=1024$ 个目录项，每项 4B，故页目录大小为

$$2^{10}\times 4=4096\text{B},$$

恰占 1 页。

每个二级页表也有 $2^{10}=1024$ 个页表项，每项 4B，因此每个二级页表也恰占 1 页。若要覆盖整个虚拟地址空间，则页目录中的 1024 个目录项分别对应 1024 个二级页表，故全部二级页表共占 1024 页。

因此页目录和页表总计占

$$1+1024=1025$$

页。

（3）二级页表由虚拟地址的页目录号确定。两个地址的页目录号分别为

$$01000000\text{H}\gg 22=4,$$ $$01112048\text{H}\gg 22=4.$$

二者的页目录号相同，均通过页目录中的第 4 项访问同一个二级页表。因此，本指令周期内虽然进行了两次地址转换，但只涉及 1 个不同的二级页表。

21. 【2016】某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为 32 位，物理地址为 24 位，页大小为 8KB；TLB 采用全相联映射；Cache 数据区大小为 64KB，按 2 路组相联方式组织，主存块大小为 64B。存储访问过程如下图所示。请回答下列问题：

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

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

（3）Cache 缺失处理的时间开销大，还是缺页处理的时间开销大？为什么？

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

答案：

（1）$A=19$ 位，$B=19$ 位，$C=11$ 位，$D=13$ 位，$E=9$ 位，$F=9$ 位，$G=6$ 位。B 中存放虚页号。

（2）映射到 Cache 第 3 组，H 字段为 8，即二进制 000001000。

（3）缺页处理的时间开销更大。

（4）Cache 与主存之间的写入代价相对较小，而内存页面写回外存的代价极大，因此前者可以直写，后者应采用回写。

解析：

（1）页大小为 8KB：

$$8\text{KB}=2^{13}\text{B}.$$

因此，32 位虚拟地址中页内偏移量占 13 位，虚页号占

$$32-13=19$$

位，所以 A 为 19 位。TLB 采用全相联映射，不需要组号字段，所有虚页号位均用于比较，因此 B 也为 19 位，存放完整的虚页号。

物理地址为 24 位，页内偏移量仍为 13 位，故页框号占

$$24-13=11$$

位。因此 C 为 11 位，D 为 13 位。

Cache 数据区大小为 64KB，块大小为 64B，所以 Cache 中共有

$$\frac{64\text{KB}}{64\text{B}}=1024$$

个 Cache 行。采用 2 路组相联，因此组数为

$$\frac{1024}{2}=512=2^9.$$

故组号字段 F 占 9 位。块大小为 64B，所以块内偏移字段 G 占

$${\log }_{2}64=6$$

位。Cache 标记字段 E 占

$$24-9-6=9$$

位。

（2）主存块号 4099 映射到的 Cache 组号为

$$4099\mathrm{mod}512=3.$$

Cache 标记为主存块号除以组数所得的商：

$$\lfloor \frac{4099}{512}\rfloor =8.$$

因此 H 字段应为 8。H 占 9 位时，其二进制表示为

$$000001000.$$

（3）缺页处理的时间开销远大于 Cache 缺失处理。Cache 缺失时，通常只需在主存与 Cache 之间传送一个主存块；缺页时则需要在外存与主存之间传送一个页面，可能还要选择并写回被淘汰的脏页。外存访问速度远低于主存，因此缺页处理代价更大。

（4）Cache 直写时，每次写 Cache 的同时写主存。由于主存相对于外存速度较快，并且可通过写缓冲减轻等待，因此直写策略可以接受。

若页面采用直写，则每次修改内存中的页面都要同步写外存，磁盘 I/O 次数会非常多，开销难以承受。因此页面通常采用回写策略：修改时只设置修改位，直到页面被淘汰时才将整个脏页写回外存。

22. 【2017】按字节编址的计算机 M 采用二级分页虚拟存储管理方式，虚拟地址格式如下所示：

页目录号（10 位）	页表索引（10 位）	页内偏移量（12 位）

C

// 函数 f1
int f1(unsigned n)
{
    int sum = 1, power = 1;
    for (unsigned i = 0; i <= n - 1; i++) {
        power *= 2;
        sum += power;
    }
    return sum;
}

函数 f1 的部分机器指令代码如下：

asm

int f1(unsigned n)
1   00401020   55            push ebp
...
    for (unsigned i = 0; i <= n - 1; i++)
...
20  0040105E   39 4D F4      cmp dword ptr [ebp-0Ch], ecx
...
    { power *= 2;
23  00401066   D1 E2         shl edx, 1
...
      return sum;
...
35  0040107F   C3            ret

请回答下列问题：

（1）函数 f1 的机器指令代码占多少页？

（2）取第 1 条指令（push ebp）时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项（编号从 0 开始）？

（3）M 的 I/O 采用中断控制方式。若进程 P 在调用 f1 之前通过 scanf（ ） 获取 n 的值，则在执行 scanf（ ） 的过程中，进程 P 的状态会如何变化？CPU 是否会进入内核态？

答案：

（1）占 1 页。

（2）访问页目录的第 1 个表项和相应二级页表的第 1 个表项。

（3）进程状态通常经历“运行态→阻塞态→就绪态→运行态”；CPU 会进入内核态。

解析：

（1）页面大小为

$$2^{12}=4096\text{B}=1000\text{H}.$$

函数 f1 的机器指令地址范围为 00401020H～0040107FH。起始地址和结束地址的虚页号分别为

$$00401020\text{H}\gg 12=00401\text{H},$$ $$0040107F\text{H}\gg 12=00401\text{H}.$$

两者位于同一页，因此函数 f1 的机器指令代码占 1 页。

（2）对虚拟地址 00401020H 分解：

$$\text{页目录号}=00401020\text{H}\gg 22=1,$$ $$\text{页表索引}=(00401020\text{H}\gg 12)\&3FF\text{H}=1.$$

因此，需要访问页目录中的第 1 个表项，再访问对应二级页表中的第 1 个表项。

（3）scanf() 获取键盘输入时，进程 P 先在用户态运行。调用输入服务会通过系统调用进入内核态；若输入数据尚未到达，进程 P 因等待 I/O 而由运行态转为阻塞态，CPU 调度其他就绪进程运行。

输入完成后，I/O 设备发出中断，CPU 响应中断并进入内核态执行中断处理程序，将进程 P 唤醒，使其由阻塞态转为就绪态。此后 P 被调度时，再由就绪态转为运行态。因此典型状态变化为

$$\text{运行态}\to \text{阻塞态}\to \text{就绪态}\to \text{运行态}.$$

CPU 在执行系统调用和处理中断时都会进入内核态。

23. 【2020】某 32 位系统采用基于二级页表的请求分页存储管理方式，按字节编址，页目录项和页表项长度均为 4 字节，虚拟地址结构如下所示：

页目录号（10 位）	页号（10 位）	页内偏移量（12 位）

某 C 程序中数组 a[1024][1024] 的起始虚拟地址为 10800000H，数组元素占 4 字节。该程序运行时，其进程的页目录起始物理地址为 00201000H。请回答下列问题：

（1）数组元素 a[1][2] 的虚拟地址是什么？对应的页目录号和页号分别是什么？对应的页目录项的物理地址是什么？若该目录项中存放的页框号为 00301H，则 a[1][2] 所在页对应的页表项的物理地址是什么？

（2）数组 a 在虚拟地址空间中所占的区域是否必须连续？在物理地址空间中所占区域是否必须连续？

（3）已知数组 a 按行优先方式存放，若对数组 a 分别按行遍历和按列遍历，则哪种遍历方式的局部性更好？

答案：

（1）虚拟地址为 10801008H；页目录号为 042H，页号为 001H；页目录项物理地址为 00201108H；页表项物理地址为 00301004H。

（2）在虚拟地址空间中必须连续，在物理地址空间中不必连续。

（3）按行遍历的局部性更好。

解析：

（1）C 语言二维数组按行优先存储。a[1][2] 前面共有

$$1\times 1024+2=1026$$

个元素，每个元素占 4B，因此相对于数组首地址的偏移量为

$$1026\times 4=4104=1008\text{H}.$$

故其虚拟地址为

$$10800000\text{H}+1008\text{H}=10801008\text{H}.$$

页目录号为虚拟地址的高 10 位：

$$10801008\text{H}\gg 22=42\text{H}.$$

页号为中间 10 位：

$$(10801008\text{H}\gg 12)\&3FF\text{H}=1\text{H}.$$

页目录起始物理地址为 00201000H，每个目录项占 4B，因此对应页目录项的物理地址为

$$00201000\text{H}+42\text{H}\times 4=00201108\text{H}.$$

该页目录项中的页框号为 00301H，所以相应二级页表的起始物理地址为

$$00301\text{H}\times 1000\text{H}=00301000\text{H}.$$

页号为 001H，每个页表项占 4B，因此目标页表项的物理地址为

$$00301000\text{H}+1\times 4=00301004\text{H}.$$

（2）数组元素在 C 语言的逻辑结构中必须占据连续的虚拟地址，因此数组 a 在虚拟地址空间中的区域必须连续。分页存储管理可以把相邻虚页映射到不同的物理页框，所以数组在物理地址空间中不必连续。

（3）数组按行优先存放，同一行中的相邻元素在地址上连续。按行遍历时，访问地址连续，能够充分利用 Cache 块和页面中的空间局部性；按列遍历时，相邻两次访问相隔一整行，即

$$1024\times 4=4096\text{B},$$

恰好为一页，容易引起更多 Cache 缺失和缺页。因此按行遍历局部性更好。

24. 【2018】请根据下图给出的虚拟存储管理方式回答问题。计算机采用页式虚拟存储管理方式，按字节编址。

（1）某虚拟地址对应的页目录号为 6，在相应的页表中对应的页号为 6，页内偏移量为 8，该虚拟地址的十六进制表示是什么？

（2）寄存器 PDBR 用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR 的内容是否会变化？说明理由。同一进程的线程切换时，PDBR 的内容是否会变化？说明理由。

（3）为了支持改进型 CLOCK 置换方法，需要在页表项中设置哪些字段？

答案：

（1）01806008H。

（2）PDBR 中保存物理地址；进程切换时通常变化，同一进程的线程切换时通常不变化。

（3）访问位和修改位。

解析：

（1）由图可知，32 位虚拟地址由 10 位页目录号、10 位页表索引和 12 位页内偏移量构成。因此

$$\text{虚拟地址}=(6\ll 22)+(6\ll 12)+8.$$

计算得

$$(6\ll 22)=01800000\text{H},$$ $$(6\ll 12)=00006000\text{H}.$$

故虚拟地址为

$$01800000\text{H}+00006000\text{H}+00000008\text{H}=01806008\text{H}.$$

（2）PDBR 用于让 MMU 直接访问当前进程的页目录，因此其中必须保存页目录的物理起始地址。若保存虚拟地址，则转换该地址本身又需要先查页表，会形成循环依赖。

不同进程通常拥有彼此独立的虚拟地址空间和页目录，因此发生进程切换时，操作系统需要把 PDBR 改为新进程页目录的物理起始地址。

同一进程内的各线程共享进程的虚拟地址空间和页表，因此同一进程的线程切换时，PDBR 的内容通常不需要改变。

（3）改进型 CLOCK 算法根据页面的访问情况和修改情况将页面分为

$$(0,0),(0,1),(1,0),(1,1)$$

四类，因此页表项中至少需要设置访问位（使用位）和修改位（脏位）。

25. 【2021】假设计算机 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）第 29～12 位为虚页号，第 11～0 位为页内地址。

（2）第 29～15 位为 TLB 标记，第 14～12 位为 TLB 组号。

（3）虚页号 4 对应的 TLB 表项被替换。

（4）每个 TLB 表项增加 2 位。

解析：

（1）页大小为 4KB：

$$4\text{KB}=2^{12}\text{B}.$$

因此页内地址占低 12 位，即第 11～0 位。虚拟地址共 30 位，所以虚页号占

$$30-12=18$$

位，即第 29～12 位。

（2）TLB 共 8 组，因此 TLB 组号需要

$${\log }_{2}8=3$$

位。题目规定虚页号低位作组号，所以虚页号最低 3 位，即整个虚拟地址的第 14～12 位为 TLB 组号。

虚页号剩余的高

$$18-3=15$$

位作 TLB 标记，即第 29～15 位。

（3）各虚页号映射的 TLB 组号为其对 8 取模的结果：

访问虚页号	TLB 组号
10	2
12	4
16	0
7	7
26	2
4	4
12	4
20	4

TLB 为 2 路组相联。访问完 12 和 4 后，第 4 组中恰有这两个表项；随后再次访问 12，使 12 成为最近使用项，4 成为最近最久未使用项。最后访问虚页 20 时，20 也映射到第 4 组，需要在 12 和 4 中按 LRU 淘汰一个，因此淘汰虚页号 4 对应的表项。

（4）虚拟地址从 30 位增加到 32 位，页大小不变，页内地址仍占 12 位，故虚页号增加 2 位。TLB 组数不变，组号仍占 3 位，因此增加的 2 位全部进入 TLB 标记字段。页框号和其他控制位均不因此改变，所以每个 TLB 表项增加 2 位。

26. 【2024】（7 分）某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址和物理地址的长度均为 32 位，页表项大小为 4 字节，页大小为 4MB。虚拟地址结构如下：

页号（10 位）	页内偏移量（22 位）

进程 P 的页表起始虚拟地址为 B8C00000H，被装载到从物理地址 65400000H 开始的连续主存空间中。请回答下列问题，要求答案用十六进制表示。

（1）若 CPU 在执行进程 P 的过程中，访问虚拟地址 12345678H 时发生了缺页异常，经过缺页异常处理和 MMU 地址转换后得到的物理地址是 BAB45678H。在此次缺页异常处理过程中，需要为所缺页分配页框并更新相应的页表项，则该页表项的虚拟地址和物理地址分别是什么？该页表项中的页框号更新后的值是什么？

（2）进程 P 的页表所在页的页号是什么？该页对应的页表项的虚拟地址是什么？该页表项中的页框号是什么？

答案：

（1）页表项虚拟地址为 B8C00120H，物理地址为 65400120H，更新后的页框号为 2EAH。

（2）页表所在页的页号为 2E3H；该页对应的页表项虚拟地址为 B8C00B8CH；该页表项中的页框号为 195H。

解析： 页大小为 4MB，即

$$4\text{MB}=2^{22}\text{B}=400000\text{H}.$$

每个页表项占 4B。

（1）虚拟地址 12345678H 的页号为

$$12345678\text{H}\gg 22=48\text{H}.$$

该页对应页表项相对于页表起始地址的偏移量为

$$48\text{H}\times 4=120\text{H}.$$

所以该页表项的虚拟地址为

$$B8C00000\text{H}+120\text{H}=B8C00120\text{H}.$$

页表被连续装载到从物理地址 65400000H 开始的主存空间，因此相同偏移处的页表项物理地址为

$$65400000\text{H}+120\text{H}=65400120\text{H}.$$

物理地址 BAB45678H 的页内偏移量为

$$BAB45678\text{H}\&3FFFFF\text{H}=345678\text{H},$$

与原虚拟地址的页内偏移量一致。物理页框号为

$$BAB45678\text{H}\gg 22=2EA\text{H}.$$

因此页表项中的页框号应更新为 2EAH。

（2）页表起始虚拟地址为 B8C00000H，其所在虚页的页号为

$$B8C00000\text{H}\gg 22=2E3\text{H}.$$

虚页 2E3H 对应的页表项相对于页表起始地址的偏移量为

$$2E3\text{H}\times 4=B8C\text{H}.$$

故该页表项的虚拟地址为

$$B8C00000\text{H}+B8C\text{H}=B8C00B8C\text{H}.$$

页表所在页被装入从物理地址 65400000H 开始的页框。其页框号为

$$65400000\text{H}\gg 22=195\text{H}.$$

因此，该页对应页表项中的页框号为 195H。