🏷️ 知识点：驻留集
某进程访问页面的序列如下所示。
若工作集的窗口大小为 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}
[tag_link]
正确答案：A
在任一时刻 t，都存在一个 集合 ，它包含所有最近 k 次（该题窗口大小为 6）内存访问所访问过的页面。这个集合 w(k, t) 就是工作集。该题中最近 6 次访问的页面分别为 6, 0, 3, 2, 3, 2, 再去除重复的页面，形成的工作集为 {6, 0, 3, 2}。
某请求分页系统的局部页面置换策略如下：系统从 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) 该策略是否适合于时间局部性好的程序？说明理由。
[tag_link]
1）页框号为 21。理由：因为起始 [驻留集]为空，因此 0 页对应的页框为空闲链表中的第三个空闲页框 21，其对应的页框号为 21。
2）页框号为 32。理由：因 11>10 故发生第三轮扫描，页号为 1 的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为 32。
3）页框号为 41。理由：因为第 2 页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框 41，页框号为 41。
4）合适。理由：如果程序的时间局部性越好，那么从空闲页框链表中重新取回的机会越大，该策略的优势越明显。