题目

某请求分页系统的局部页面置换策略如下：

• 系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计）
• 本轮没有被访问过的页框将被系统回收，放入空闲页框链尾，其中内容在下一次被分配之前不被清空
• 当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框

假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。系统空闲页框链表中页框号依次为 32、15、21、41。

进程 P 依次访问的 ⟨虚拟页号, 访问时刻⟩ 是：

⟨1, 1⟩、⟨3, 2⟩、⟨0, 4⟩、⟨0, 6⟩、⟨1, 11⟩、⟨0, 13⟩、⟨2, 14⟩

请回答下列问题：

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

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

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

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

解析

完整时间线推演

按时间顺序逐事件追踪驻留集和空闲链：

时刻	事件	驻留集（页号 → 页框号）	空闲链（链头 → 链尾）
0	初始	∅	[32, 15, 21, 41]
1	访问页 1 → 缺页，取链头 32		[15, 21, 41]
2	访问页 3 → 缺页，取链头 15		[21, 41]
4	访问页 0 → 缺页，取链头 21	{1→32, 3→15, 0→21}	[41]
5	第一轮扫描：本轮（0~5）访问过的页 = {1, 3, 0}——全部驻留集都被访问 → 不回收任何页框		[41]
6	访问页 0 → 命中 框 21		[41]
10	第二轮扫描：本轮（5~10）只访问过 {0} → 回收页 1（框 32）和页 3（框 15）		[41, 32, 15]（按扫描顺序入链尾）
11	访问页 1 → 缺页，但页 1 还在空闲链（框 32），直接放回驻留集	{0→21, 1→32}	[41, 15]
13	访问页 0 → 命中 框 21		[41, 15]
14	访问页 2 → 缺页，页 2 从未访问过，取链头 41	{0→21, 1→32, 2→41}	[15]
15	（第三轮扫描，本题不再问）

（1）访问 ⟨0, 4⟩ 的页框号

页 0 第一次被访问，缺页。空闲链此时还是 [21, 41]（前两次访问已用掉 32、15）→ 取链头 21。

答：页框号 21。

（2）访问 ⟨1, 11⟩ 的页框号

t=11 落在 t=10 第二轮扫描之后。第二轮扫描发生时（5~10 期间只访问了页 0），页 1 因"本轮未被访问"被回收到空闲链尾——但它的内容（页 1 的数据）并未被清空，框 32 在链中还存着页 1 的副本。

t=11 缺页时按规则查："页 1 曾被使用过、且现在还在空闲链中" → 直接把框 32 放回驻留集，无需重新读盘。

答：页框号 32。

编者注（核心机制）：这正是该策略的精妙之处——回收页框不立即清空内容给"重新放回"留了余地。如果回收时立即清零，再次访问页 1 就只能从链头取一个新框、还要从磁盘读 4 KB 数据，开销大得多。

（3）访问 ⟨2, 14⟩ 的页框号

页 2 在前面从未出现过——既不在驻留集，也不在空闲链中（链中残留的是页 1 的内容、页 3 的内容）。所以走"普通缺页"分支，取链头 41。

答：页框号 41。

编者注（易错点）：注意 t=14 时空闲链是 [15]（41 已在 t=14 被取走前还在头部）。初学者容易把"链中残留的页 3 的内容"也算成"页 3 还在驻留集"——错。驻留集和空闲链是两个独立的集合：内容残留不等于"页还在使用"，必须满足"页号被某个驻留集表项指向"才算在驻留集中。

（4）是否适合时间局部性好的程序？

适合。

为什么？ 时间局部性好 = 最近访问过的页很可能很快又被访问。这套策略的优势恰好建立在这个假设上：

• 扫描周期内被回收的页框只是"暂时离队"——内容还在
• 一旦该页在不远的将来被访问 → 走 "重放" 分支（如本题的 ⟨1, 11⟩）→ 零磁盘 I/O

如果程序时间局部性差（每次访问都是不同的、新出现的页），重放命中率几乎为零，回收的页框只是占着空闲链不让其他用、还得不时地从链尾被冲走、最终触发真正的磁盘读——优势完全发挥不出。

编者注（与经典 LRU 对比）：这种"回收 + 内容保留 + 可重放"的设计，本质上是在驻留集和工作集之间做出弹性扩张：

• 严格的 LRU：驻留集 = 工作集，每次缺页必须读盘
• 本题策略：驻留集 ≤ 工作集 + 空闲链中的"软驻留"页 → 命中率更高，但需要额外管理空闲链

这是 OS 内存章中"动态调整驻留集"的实际样例，2009-46（请求分页 + LRU）和本题对比着复习能加深对"驻留集 vs 工作集"的理解。