51. A
2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 51. A
在任意时刻 $t$，都存在一个集合，它包含所有最近 $k$ 次（该题窗口大小为6）内存访问所访问过的页面。这个集合 $w(k, t)$ 就是工作集。题中最近6次访问的页面分别为6, 0, 3, 2, 3, 2，去除重复的页面，形成的工作集为{6, 0, 3, 2}。
## 52. C
最近最久未使用（LRU）算法每次执行页面置换时会换出最近最久未使用过的页面。第一次访问5页面时，会把最久未被使用的1页面换出，第一次访问3页面时，会把最久未访问的2页面换出。具体的页面置换情况如下图所示。
[tbl-117.md](tbl-117.md)
需要注意的是，题中问的是页置换次数，而不是缺页次数，所以前4次缺页未换页的情况不考虑在内，答案为5次，因此选择选项C。
## 53. D
选项I影响缺页中断的频率，缺页率越高，平均访存时间越长；选项II和IV影响缺页中断的处理时间，中断处理时间越长，平均访存时间越长；选项III影响访问页表和访问目标物理地址的时间，所以选项I、II、III和IV均正确。
## 54. C
页面大小为4KB，低12位是页内偏移。虚拟地址为02A01H，页号为02H，02H页对应的页表项中存在位为0，进程P分配的页框固定为2，且内存中已有两个页面存在。根据Clock算法，选择将3号页换出，将2号页放入60H页框，经过地址变换后得到的物理地址是60A01H。
## 55. A
缺页异常需要从磁盘调页到内存中，将新调入的页与页框建立对应关系，并修改该页的存在位，选项B、C、D正确；若内存中有空闲页框，则不需要淘汰其他页，选项A错误。
## 56. D
页置换算法会影响缺页率，例如，LRU算法的缺页率通常要比FIFO算法的缺页率低，排除选项A。工作集的大小决定了分配给进程的物理块数，分配给进程的物理块数越多，缺页率就越低，排除选项B。进程的数量越多，对内存资源的竞争越激烈，每个进程被分配的物理块数越少，缺页率也就越高，排除选项C。页缓冲队列是将被淘汰的页面缓存下来，暂时不写回磁盘，队列长度会影响页面置换的速度，但不会影响缺页率。
## 57. D
虚拟地址空间的大小由底层的虚拟内存管理机制和操作系统决定，通常在不同的操作系统中
<!-- page: 255 -->
有所不同，与内存和硬盘的大小没有关系，内存和硬盘的大小仅决定虚拟存储器实际可用容量的最大值，选项D错误。选项A、C显然正确。在进程的虚拟地址空间中，有专门用来存放动态分配的变量的堆区，通过调用malloc()函数动态地分配该空间，选项B正确。
## 二、综合应用题
### 01.【解答】
一页的大小为32B，逻辑地址结构为：低5位为页内位移，其余高位为页号。
101（八进制） = 001000001（二进制），则页号为2，在相联存储器中，对应的页帧号为f3，即物理地址为(f3.1)。
204（八进制） = 010000100（二进制），则页号为4，不在相联存储器中，查内存的页表得页帧号为f5，即物理地址为(f5.4)，并用其更新相联存储器中的一项。
576（八进制） = 101111110（二进制），则页号为11，已超出页表范围，即产生越界中断。
### 02.【解答】
1）80%的访问的页表项在关联寄存器中，访问耗时 1μs。
2）18%的访问的页表项不在关联寄存器中，但在内存中，耗时(1 + 1)μs。
3）2%的访问产生缺页中断，访问耗时(1μs + 1μs + 20ms)。
从而有效访问时间为 80% × 1 + 18% × 2 + 2% × (1 × 2 + 20 × 1000) = 401.2μs。
## 注意
针对3）中的耗时情况，有些读者可能对缺页中断的页面调度过程有些模糊，导致此情况下的访问耗时计算出现偏差。题目中已经明确说明“页表保存在主存”，意味着物理页号一定可以通过查找内存获得并计算出相应的物理地址。即若关联寄存器命中（可以取得页框号，再结合逻辑地址中的偏移量，便可算得对应的物理地址。至此，已经获得物理地址），则仅访问一次内存（根据物理地址取得相应的页面，耗时 1μs）即可；若未命中，则还要从主存中［注意，若地址变换是通过查找内存中的页表完成的，则还应将这次所查到的页表项存入关联寄存器中］。取出相应的页表项（耗时 1μs），再根据得到的物理地址访问内存取得对应的页面（耗时 1μs）。但是，无论关联寄存器是否命中，欲访问的页面［非页表（Page）］不一定在主存中，即若页面不在内存中，则产生缺页中断，操作系统需要启动磁盘将缺页调入内存。题目中明确说明“剩下的 20% 中，10% 的访问（总数的 2%）会产生缺页”，其中“剩下的 20%”意味着是通过查找内存（关联寄存器未命中）得到物理地址的（耗时 1μs），缺页中断（耗时 20ms）后，将缺页调入主存，此时“系统恢复缺页中断发生前的状态，将程序指令器重新指向引起缺页中断的指令，重新执行该指令”，这时页表项已在关联寄存器中（对此不解的读者请回看上文的“*注”处），则根据取得的物理地址仅访存一次即可取得对应的页面（耗时 1μs）。
## 注意
建议读者结合《计算机组成原理考研复习指导》中的“虚拟存储器”小节进行复习。希望读者在完成本题的基础上总结出求解该类题型的方法，以便在以后遇到类似的题目时得心应手。读者应做到基础扎实，注意细节，触类旁通。
### 03.【解答】
发生页故障的原因是，当前访问的页不在主存，需要将该页调入主存。此时不管主存中是否已满（已满则先调出一页），都要发生一次页故障，即无论怎样安排，n个不同的页号在首次进入主存时必须要发生一次页故障，总共发生n次，这是页故障数的下限。虽然不同的页号数为n小于或等于总长度p（访问串可能有一些页重复出现），但驻留集 m < n，所以可能有某些页进入主
<!-- page: 256 -->
存后又被调出主存，当再次访问时又发生一次页故障的现象，即有些页可能出现多次页故障。最差的情况是每访问一个页号时，该页都不在主存中，这样共发生 $p$ 次故障。
因此，对于FIFO、LRU置换算法，页故障数的上限均为 $p$，下限均为 $n$。例如，当 $m = 3, p = 12, n = 4$ 时，有访问串111223334444，则页故障数为4，这是下限 $n$ 的情况。又如，有访问串123412341234，则页故障数为12，这是上限 $p$ 的情况。
## 04.【解答】
1）根据页面走向，使用最佳置换算法时，页面置换情况见下表。
物理块数为3时：
[tbl-118.md](tbl-118.md)
缺页率为 7/12。
物理块数为4时：
[tbl-119.md](tbl-119.md)
缺页率为 6/12。
由上述结果可以看出，增加分配作业的内存块数可以降低缺页率。
2）根据页面走向，使用先进先出页面淘汰算法时，页面置换情况见下表。
物理块数为3时：
[tbl-120.md](tbl-120.md)
缺页率为 9/12。
物理块数为4时：
[tbl-121.md](tbl-121.md)
缺页率为 10/12。
由上述结果可以看出，对先进先出算法而言，增加分配作业的内存块数反而使缺页率上升，即出现Belady现象。
3）根据页面走向，使用最近最久未使用页面淘汰算法时，页面置换情况见下表。
物理块数为3时：
<!-- page: 257 -->
[tbl-122.md](tbl-122.md)
缺页率为 10/12。
物理块数为 4 时：
[tbl-123.md](tbl-123.md)
关注公众号[考研小舟]
免费考研资料&无水印PDF
缺页率为 8/12。
由上述结果可以看出，增加分配作业的内存块数可以降低缺页率。
05. 【解答】 公众号：小兔网盘免费分享无水印PDF
1）系统出现“抖动”现象。这时若再增加并发进程数，反而会恶化系统性能。页式虚拟存储系统因“抖动”现象而未能充分发挥功用。
2）系统正常。不需要采取什么措施。
3）CPU 没有充分利用。应该增加并发进程数。
06. 【解答】
在缺页中断处理完成，调入请求页面后，还需 1μs 的存取访问，即
1）当未缺页时，直接访问内存，用时 1μs。
2）当缺页时，若未修改，则用时 8μs + 1μs。
3）当缺页时，而且修改了，则用时 20μs + 1μs。
设最大缺页中断率为 p，有 (1 - p) × 1μs + (1 - 70%) × p × (1μs + 8μs) + 70% × p × (1μs + 20μs) = 2μs，即 1μs + (1 - 70%) × p × 8μs + 70% × p × 20μs = 2μs，解得 p ≈ 0.061 = 6.1%。
07. 【解答】
1）页面大小为 4KB，因此页内偏移为 12 位。系统采用 48 位虚拟地址，因此虚页号为 48 - 12 = 36 位。采用多级页表时，最高级页表项不能超出一页大小；每页能容纳的页表项数为 4KB / 8B = 512 = 2⁹，36 / 9 = 4，因此应采用 4 级页表，最高级页表项正好占据一页空间。
2）系统进行页面访问操作时，首先读取页面对应的页表项，有 98% 的概率可以在 TLB 中直接读取到，然后进行地址转换，访问内存读取页面；若 TLB 未命中，则要通过一次内存访问来读取页表项。页面平均访问时间为
$$
98\% \times (10 + 100) + (1 - 98\%) \times (10 + 100 + 100) = 112 \text{ns}
$$
3）二级页表的平均访问时间计算同理：
$$
98\% \times (10 + 100) + (1 - 98\%) \times (10 + 100 + 100 + 100) = 114 \text{ns}
$$
4）设快表命中率为 p，则应满足
$$
p \times (10 + 100) + (1 - p) \times (10 + 100 + 100 + 100) \leqslant 120 \text{ns}
$$
解得 p ≥ 95%。
5）系统采用 48 位虚拟地址，每段最大为 4GB，因此段内地址为 32 位，段号为 48 - 32 = 16 位。每个用户最多可以有 2¹⁶ 段。段内采用页式地址，与 1）中计算同理，(32 - 12)/9，取上整为 3，因此段内应采用 3 级页表。
<!-- page: 258 -->
# 注意
在采用多级页表的页式存储管理中，若快表命中，则只需要一次访问内存操作即可存取指令或数据，这一点需要注意和理解。以本题1）中假设的条件为例，不考虑分段时，需要4级页表。若快表未命中，则需要从虚拟地址的高位起，每9位连级访问各级页表，第5次才能访问到指令或数据所在的内存页面。
若快表命中，则首先考虑快表中的实际内容；快表存放经常被访问的页面对应的页表项，页表项中是完整的 48–12 = 36 位页面号，所以根据快表可以直接对虚拟地址进行转换。因此多级页表中，快表命中时同样只需要一次访问内存操作。根本原因在于，快表提供了进行地址转换的完整的页面号，而不是某一级的页面号。
## 08.【解答】
1）物理块数为3时，缺页情况见下表：
[tbl-124.md](tbl-124.md)
缺页次数为6，缺页率为 6/12 = 50%。
2）物理块数为4时，缺页情况见下表：
[tbl-125.md](tbl-125.md)
缺页次数为4，缺页率为 4/12 = 33%。
# 注意
当分配给作业的物理块数为4时，注意到作业请求页面序列中只有4个页面，可以直接得出缺页次数为4，而不需要按表列出缺页情况。
## 09.【解答】
1）FIFO算法：最先进入的页帧号应最先替换，因此访问虚页4发生缺页时，应置换3号页帧中的3号虚页，因为它是最先进入存储器的。
LRU算法：应置换1号页帧中的1号虚页，因为它是最大未被访问和修改过的，又是最先进入存储器的。
改进型CLOCK算法：第一轮扫描淘汰访问位和修改位都为0的页面，因此淘汰1号页面。
2）采用LRU算法时缺页情况如下表，缺页次数为3次。
[tbl-126.md](tbl-126.md)
<!-- page: 259 -->
## 10. 【解答】
由于驻留集大小任意，现要求两种算法的替换页面和缺页情况完全一样，就意味着要求 FIFO 与 LRU 的置换选择一致。FIFO 替换最早进入主存的页面，LRU 替换上次访问以来最久未被访问的页面，这两个页面一致。就是说，最先进入主存的页面在此次缺页之前不能再被访问，这样该页面也就同时是最久未被访问的页面。
例如，合法驻留集大小为 4 时，对访问串 1,2,3,4,1,2,5，当 5 号页面调入主存时，应在 1,2,3,4 页中选择一个替换，FIFO 选择 1，LRU 选择 3。原因在于 1 号页面虽然最先进入主存，但因为其进入主存后又被再次访问，所以它不是最久未被访问的页面。若去掉对 1 号页面的第二次访问，则 FIFO 与 LRU 的替换选择就会相同。同理，当 5 号页面调入主存后，若再访问新的 6 号页面，则 2 号页面会遇到同样的问题。因此，以此类推，访问串中的所有页面号都应不同，但要注意到，连续访问相同页面时不影响后面的替换选择，所以对访问串的要求是：不连续的页面号均不相同。
## 11. 【解答】
1）FIFO 置换算法选择最先进入内存的页面进行替换。由表中装入时间可知，第 2 页最先进入内存，因此 FIFO 置换算法将选择第 2 页替换。
2）LRU 置换算法选择最近最长时间未使用的页面进行替换。由表中的上次引用时间可知，第 1 页是最长时间未使用的页面，因此 LRU 置换算法将选择第 1 页替换。
3）简单 CLOCK 置换算法从上一次位置开始扫描，选择第一个访问位为 0 的页面进行替换。由表中的 $R$ （读）标志位可知，依次扫描 2,0（按装入顺序），页面 0 未被访问，扫描结束，因此简单 CLOCK 置换算法将选择第 0 页替换。
4）改进型 CLOCK 置换算法从上一次的位置开始扫描，首先寻找未被访问和修改的页面。由表中的 $R$ （读）标志位和 $M$ （修改）标志位可知，只有页面 0 满足 $R = 0$ 和 $M = 0$，因此改进型 CLOCK 置换算法将选择第 0 页替换。
## 12. 【解答】
程序 1 按行优先的顺序访问数组元素，与数组在内存中存放的顺序一致，每个内存页面可存放 200 个数组元素。这样，程序 1 每访问两行数组元素就产生一次缺页中断，所以程序 1 的执行过程会发生 50 次缺页。
程序 2 按列优先的顺序访问数组元素，每个内存页面存放两行数组元素，因此程序 2 每访问两个数组元素就产生一次缺页中断，整个执行过程会发生 5000 次缺页。
若每页只能存放 100 个整数，则每页仅能存放一行数组元素，同理可以计算出：程序 1 的执行过程产生 100 次缺页；程序 2 的执行过程产生 10000 次缺页。
以上说明缺页的次数与内存中数据存放的方式及程序执行的顺序有很大关系；同时说明，当缺页中断次数不多时，减小页面大小影响并不大，但缺页中断次数很多时，减小页面大小会带来很严重的影响。
## 13. 【解答】
1）页面大小为 4KB，每个页表项大小为 4B，因此在每个页表当中，共有 1024 个页表项，对每个层次的页表来说，都满足这一点，这样每级页表的索引均为 10 位，因为页面大小为 4KB，所以页内偏移地址为 12 位。逻辑地址被划分为 5 个部分：
[tbl-127.md](tbl-127.md)
空闲 一级索引 二级索引 三级索引 页内偏移
可访问的虚拟地址空间大小为 $2^{42}\mathrm{B} = 4\mathrm{TB}$。
<!-- page: 260 -->
2）假定一个页面的大小为 $2^{Y}$，即页内偏移地址为 $Y$ 位，每个页面可以包含 $2^{Y} / 8 = 2^{(Y-3)}$ 个页表项，因此每级页表的索引位为 $Y - 3$ 位，共有 4 级页表，所以 $4(Y - 3) + Y \leqslant 64$，$Y \leqslant 15.2$，因此 $Y = 15$。所以最大的页面大小为 $2^{15}\mathrm{B} = 32\mathrm{KB}$。
总结：求解这类题目的关键是清楚地划分逻辑地址，清楚地划分了逻辑地址的每个部分，这类题目就很容易求解。
## 14. 【解答】
1）页面大小为4KB，所以页内偏移量占12位，物理页框号占 $24 - 12 = 12$ 位，页表项大小为4B，所以每个页面能存放 $4\mathrm{KB} / 4\mathrm{B} = 1\mathrm{K}$ 个页表项，因此二级页号和一级页号各占10位。页表基址寄存器中存放的是当前进程的一级页表的起始物理地址，一级页表页表项中的内容是此页表项对应的二级页表所在的物理页框号。
2）TLB的命中率为 $98\%$，若TLB命中，则地址转换时间为10ns。
若TLB未命中，则还要分别查找一级页表和二级页表，且均未缺页，所以地址转换时间为210ns。地址转换的平均时间为 $10 \times 98\% + 210 \times 2\% = 14\mathrm{ns}$。
3）若TLB未命中且一级页表命中，但二级页表缺失，则处理缺页中断后再访问TLB，所以地址转换时间为 $220\mathrm{ns} + 10\mathrm{ms}$。地址转换的平均时间为 $10\mathrm{ns} \times 98\% + 210\mathrm{ns} \times 2\% \times 90\% + (220\mathrm{ns} + 10\mathrm{ms}) \times 2\% \times 10\% \approx 20014\mathrm{ns}$。
## 14. 【解答】
1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即 $2^{12}$，得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成二进制的4位数字，因此十六进制的低三位正好为页内位移，最高位为页号）：
2362H: $P = 2$，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计 $10\mathrm{ns} + 100\mathrm{ns} + 100\mathrm{ns} = 210\mathrm{ns}$。
1565H: $P = 1$，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理 $10^{8}\mathrm{ns}$，访问快表10ns，合成物理地址后访问主存100ns，共计 $10\mathrm{ns} + 100\mathrm{ns} + 10^{8}\mathrm{ns} + 10\mathrm{ns} + 100\mathrm{ns} = 100000220\mathrm{ns}$。
25A5H: $P = 2$，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns + 100ns = 110ns。
2）当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。
## 15. 【解答】
1）因为该计算机的逻辑地址空间和物理地址空间均为 $64\mathrm{KB} = 2^{16}\mathrm{B}$，按字节编址，且页的大小为 $1\mathrm{K} = 2^{10}$，所以逻辑地址和物理地址的地址格式均为
[tbl-128.md](tbl-128.md)
17CAH = 0001 0111 1100 1010B，可知该逻辑地址的页号为000101B = 5。
2）采用FIFO置换算法，与最早调入的页面即0号页面置换，其所在的页框号为7，于是对应的物理地址为0001 1111 1100 1010B = 1FCAH。
3）采用CLOCK置换算法，首先从当前位置（2号页框）开始顺时针寻找访问位为0的页面，当指针指向的页面的访问位为1时，就将该访问位清零，指针遍历一周后，回到2号页框，此时2号页框的访问位为0，置换该页框的页面，于是对应的物理地址为0000 1011
<!-- page: 261 -->
1100 1010B = 0BCAH。
## 16. 【解答】
1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框（21），其对应的页框号为21。
2）页框号为32。理由：因 $11 > 10$，因此发生第三轮扫描，页号为1的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为32。
3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
4）合适。理由：程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。