🏷️ 知识点：页面置换算法
某虚拟存储系统采用页式存储管理，只有 a、b 和 c 三个页框，页面访问的顺序为： 0, 1, 2, 4, 2, 3, 0, 2, 1, 3, 2, 3, 0, 1, 4 若采用 FIFO 替换算法，则命中率为（ ）。
A. 20% B. 26.7% C. 15% D. 50%
[tag_link]
正确答案：B
本题考查 FIFO 算法。 FIFO 算法指淘汰**先进入**的，易知替换顺序为：
| 走向 | 0 | 1 | 2 | 4 | 2 | 3 | 0 | 2 | 1 | 3 | 2 | 3 | 0 | 1 | 4 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| c | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | ||
| b | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 4 | |
| a | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 |
| 命中否 | √ | √ | √ | √ |
表中除了标注为命中的，其余均未命中，所以命中率为 。 >
某系统采用改进型 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)
[tag_link]
正确答案：A
改进型 Clock 也称为 “二次机会（Second-Chance）算法的增强版”，依据页的访问位 A 和修改位 M 将页分成四类：
(0, 0)：最近未被访问，未被修改 —— 优先淘汰(0, 1)：最近未被访问，但被修改 —— 淘汰代价较大（需写回磁盘），次优先(1, 0)：最近被访问，未被修改 —— 说明该页仍有用，再次保留(1, 1)：最近被访问，已被修改 —— 最不愿意淘汰因此，淘汰顺序是按照代价和“是否有用”排序的：👉 (0, 0) < (0, 1) < (1, 0) < (1, 1)✅ [tag_link]正确答案是：A. (0, 0), (0, 1), (1, 0), (1, 1)
现有一 LRU 算法，采用固定分配局部置换的页面置换策略，已为进程分配 3 个页框，页面访问序列为 {0,1,2,0,5,1,4,3,0,2,3,2,0 }，其中 0,1,2 已调入内存。则缺页次数是（ ）。
A. 5 B. 6 C. 7 D. 8
[tag_link]
正确答案：B
在 LRU 算法中，每当需要访问一个不在当前内存中的页面时，就需要进行置换操作，并选择当前内存中最久未使用的页面进行替换。我们按照给定的页面访问序列进行模拟：初始状态：内存中页面为 {0, 1, 2}，访问序列：
| 访问页面 | 是否命中/缺页 | 之后的内存页面 |
|---|---|---|
| 0 | 命中 | {1, 2, 0} |
| 1 | 命中 | {2, 0, 1} |
| 2 | 命中 | {0, 1, 2} |
| 0 | 命中 | {1, 2, 0} |
| 5 | 缺页，替换页面 1 | {2, 0, 5} |
| 1 | 缺页，替换页面 2 | {0, 5, 1} |
| 4 | 缺页，替换页面 0 | {5, 1, 4} |
| 3 | 缺页，替换页面 5 | {1, 4, 3} |
| 0 | 缺页，替换页面 1 | {4, 3, 0} |
| 2 | 缺页，替换页面 4 | {3, 0, 2} |
| 3 | 命中 | {0, 2, 3} |
| 2 | 命中 | {0, 3, 2} |
| 0 | 命中 | {3, 2, 0} |
| 总计缺页次数为 6 次。 |
系统为某进程分配了 4 个页框，该进程已访问的页号序列为 2, 0, 2, 9, 3, 4, 2, 8, 2, 4, 8, 4, 5。若进程要访问的下一页的页号为 7，依据 LRU 算法，应淘汰页的页号是（ ）。
A. 2 B. 3 C. 4 D. 8
[tag_link] 正确答案：A参考 LRU ，对页号序列从后往前计数，直到数到 4（页框数）个不同的数字为止，这个停止的数字就是要淘汰的页号（最近最久未使用的页），题中为页号 2。
下列说法中，正确的是（ ）。 Ⅰ. 先进先出（FIFO）页面置换算法可能会产生 Belady 现象。 Ⅱ. 最近最少使用（LRU）页面置换算法可能会产生 Belady 现象。 Ⅲ. 在进程运行时，如果它的工作集页面都在虚拟存储器内，能够使该进程有效地运行，否则会出现频繁的页面调入/调出现象。 Ⅳ. 在进程运行时，如果它的工作集页面都在主存储器内，能够使该进程有效地运行，否则会出现频繁的页面调入/调出现象。
A. Ⅰ和Ⅲ B. Ⅰ和Ⅳ C. Ⅱ和Ⅲ D. Ⅱ和Ⅳ
[tag_link]
正确答案：B
说法Ⅰ正确：先进先出（FIFO）页面置换算法在增加内存页面帧数时，可能导致缺页次数反而增加，这种现象称为 Belady 异常，因此 FIFO 确实可能产生 Belady 现象。
说法Ⅱ错误：最近最少使用（LRU）页面置换算法属于栈算法，对于任何页面访问序列，增加页面帧数不会增加缺页次数，因此 LRU 不会产生 Belady 现象。
说法Ⅲ错误：工作集是指进程在最近一段时间内访问的页面集合。 若工作集页面仅位于虚拟存储器（如磁盘交换区），进程访问时需频繁调入主存，会导致缺页中断和页面调入/调出，无法有效运行； 有效运行需要工作集页面位于主存储器中。
说法Ⅳ正确：当进程的工作集页面都在主存储器内时，进程可快速访问所需页面，减少缺页中断，从而有效运行； 否则，会因页面缺失而出现频繁的页面调入/调出现象。
综上，正确说法为Ⅰ和Ⅳ，对应选项 B。
某请求分页存储系统的页大小为 4KB，按字节编址。系统给进程 P 分配 2 个固定的页框并采用改进型 Clock 置换算法，进程 P 页表的部分内容如下表所示：
若 P 访问虚拟地址为 02A01H 的存储单元，则经地址变换后得到的物理地址是（）。
A. 00A01H B. 20A01H C. 60A01H D. 80A01H
[tag_link]
正确答案：C
页面大小为 4KB，低 12 位是页内偏移。虚拟地址为 02A01H，页号为 02H，02H 页对应的页表项中存在位为 0，进程 P 分配的页框固定为 2，且内存中已有两个页面存在。根据 CLOCK 算法，选择将 3 号页换出，将 2 号页放入 60H 页框，经过地址变换后得到的物理地址是 60A01H。
如下程序在页式虚存系统中执行，程序代码位于虚拟空间 0 页，A 为 128×128 的数组，在虚空间以行为主序存放，每页存放 128 个数组元素。工作集大小为 2 个页框（开始时程序代码已在内存，占 1 个页框），用 LRU 算法，下面两种对 A 初始化的程序引起的页故障数分别为（ ）。
A. 128×128, 128 B. 128, 128×128 C. 64, 64×64 D. 64×64, 64
[tag_link]
正确答案：A
在页式虚存系统中，数组 A 为 128×128，以行为主序存放，每页存放 128 个元素，因此每行对应一个虚拟页，共占用 128 页（假设从第 1 页开始）。 工作集大小为 2 个页框，开始时程序代码（位于第 0 页）已占 1 个页框，故仅剩 1 个页框用于数据页。 采用 LRU 替换��法，数据页框只能容纳一页数据。
对于程序 1（列优先初始化）：外层循环遍历列 j，内层循环遍历行 i。 访问顺序为 A[1][1], A[2][1], …, A[128][1], A[1][2], A[2][2], …, A[128][2], …, A[1][128], A[2][128], …, A[128][128]。 每次访问的元素属于不同行（即不同页），由于只有 1 个数据页框，每次访问新页时都会发生页故障并替换当前页。 即使同一页后续会被再次访问，但两次访问之间间隔了其他 127 页的访问，该页已被替换出内存，因此每次访问都会引发页故障。 总访问次数为 128×128，故页故障数为 128×128。
对于程序 2（行优先初始化）：外层循环遍历行 i，内层循环遍历列 j。 访问顺序为 A[1][1], A[1][2], …, A[1][128], A[2][1], A[2][2], …, A[2][128], …, A[128][1], A[128][2], …, A[128][128]。 每行元素位于同一页，访问某行时，第一次访问该页发生页故障，随后访问该行其他元素时页已在内存，无故障。 处理下一行时，新页替换旧页，再次发生页故障。 因此，每行仅一次页故障，共 128 行，故页故障数为 128。
综上，程序 1 页故障数为 128×128，程序 2 页故障数为 128，对应选项 A。
下列选项中，不会影响系统缺页率的是()。
A. 页面置换算法
B. 工作集的大小
C. 进程的数量
D. 页缓冲队列的长度
[tag_link]
正确答案：D
页置换算法会影响缺页率，例如，LRU 算法的缺页率通常要比 FIFO 算法的缺页 率低，排除 A。工作集的大小决定了分配给进程的物理块数，分配给进程的物理块数越多， 缺页率就越低，排除 B。进程的数量越多，对内存资源的竞争越激烈，每个进程被分配的物 理块数越少，缺页率也就越高，排除 C。页缓冲队列是将被淘汰的页面缓存下来，暂时不写 回磁盘，队列长度会影响页面置换的速度，但不会影响缺页率，答案选 D。