工作集窗口与驻留需求

一个进程申请过100页，并不意味着下一小段计算要同时用到100页。页与页表映射把访问地址归到虚拟页；工作集模型再从最近访问过哪些页，估计当前阶段需要保留多少信息。

形式陈述

令进程P的页引用序列为 $x_1,x_2,\ldots$ 。在完成第 $t$ 次引用后，最近 $\Delta$ 次引用的工作集定义为

W_P(t,\Delta)=\{x_i:\max(1,t-\Delta+1)\le i\le t\},\qquad w_P(t,\Delta)=|W_P(t,\Delta)|.

这里 $t\ge0$ ， $\Delta\ge1$ 均为整数； $t=0$ 时集合为空。集合记录不同页，重复访问同一页不会重复占一个元素。本页用“每进程引用次数窗口”方便手算。Denning原始模型用进程执行时间窗口；两者都排除进程暂停的墙钟间隔，但单位不同，不能把4次引用直接换成4毫秒。

工作集是历史记录，驻留集 $R_P$ 是当前已有物理帧支撑的页集合。可以有 $W_P\not\subseteq R_P$ ：刚访问过的页随后被挤出；也可以有 $R_P\not\subseteq W_P$ ：某页仍驻留，只是最近没碰。操作系统可以尝试保留工作集，但定义本身不承诺已替它取得内存。

直觉

把最近 $\Delta$ 个页号存进队列，再为每个页号保留窗口内出现次数。新引用入队并加计数；若队列超长，弹出最老引用并减计数。只有某页计数降到0时，才把该页移出集合。这可用长度至多 $\Delta$ 的队列和计数表实现。

例如窗口内容为 b d d d，工作集是 $\{b,d\}$ 。接着访问 e，弹出b，得到 d d d e，工作集变成 $\{d,e\}$ 。若弹出的是一个d，仍有其他d留在窗口，就不能把d整页删除。按“每次弹出都删除集合元素”实现，会在重复访问很多时低估需求。

同一进程若被暂停一分钟，它没有产生新引用， $t$ 不变，窗口也不变。另一个进程继续执行，并不使P的页在P自己的参考历史里变旧。若要按全局墙钟时间主动回收休眠进程的页，可以另设策略，但那是在历史窗口之外作资源决定。

例子与边界

令 $\Delta=4$ ，P依次访问 a b a c b d d d e。每行在本次访问完成后记录。

$t$	最近至多4次引用	大小
1	a	1
2	a b	2
3	a b a	2
4	a b a c	3
5	b a c b	3
6	a c b d	4
7	c b d d	3
8	b d d d	2
9	d d d e	2

到6时，窗口里四次访问恰好都不同，需求估计为4；到9时，程序集中使用d与e，窗口仍长4，但不同页数降到2。窗口长度是观察范围，不是强制保留的页数。

若把窗口改成3， $t=6$ 时只看 c b d，大小3；改成6则看 a b a c b d，大小4。对固定时刻，较短窗口包含于较长窗口，因此大小随 $\Delta$ 非递减。这不意味着大小随 $t$ 非递减；上表已经从4降到了2。

不同进程里同一个虚拟页号a，不一定指同一内容。估计全机页框需求时，先把各页映射为待驻留的底层页身份：私有页带进程身份，共享页则用共同对象与偏移身份。只有确实能由同一物理内容支撑的页才能去重。

假设P工作集为 $\{P_a,P_b,S\}$ ，Q为 $\{Q_c,Q_d,S\}$ ，S是相同共享只读页。两者大小都是3，但联合需求为

|\{P_a,P_b,S\}\cup\{Q_c,Q_d,S\}|=5,

不是6。若一方写入触发写时复制，S可能变成两个不同底层页，之后就要重新计数。这个联合集扩展用于本页实验；原始论文推导某些整体性质时明确假设工作集不重叠，不能直接把那些加法式用于共享场景。

在 $t=9$ 之后，程序可能继续交替d、e，也可能立即顺序扫描100个新页。这两种未来拥有完全相同的历史工作集。由过去的2页就断言“给2帧后不会缺页”，没有逻辑依据；预测需要访问局部性持续的假设，并要随着新观测更新。

相反，大窗口可能留下上一阶段已经不用的页。程序从a、b阶段转到d、e阶段后，旧页会在窗口里保留一段时间。加大窗口能减少过早遗忘，却也可能抬高无用保留量；没有仅凭窗口定义就能算出的普适最佳 $\Delta$ 。

推论与应用

设当前允许活跃的进程集合为A，按底层页身份去重后的联合工作集大小为 $D_A$ ，可供它们使用的页框预算为 $M$ 。当 $D_A>M$ 时，这些被估计为活跃的内容不可能全部同时驻留。可以减少活跃集合、调整窗口估计或接受更多换入换出，但不能靠更聪明的计数绕过容量不等式。

$D_A\le M$ 也只是通过一次容量筛选。内核自身开销、锁定页、区域限制、连续性和访问阶段变化，都可能使实际分配或后续访问出问题。抖动与负载控制会把这个信号连到“哪些进程继续参与运行”的决定，而不是把工作集公式直接当调度器。

严格记录每次内存引用通常成本很高。实际系统可以采样访问位、按时间桶近似最近使用情况；Clock替换就利用访问位决定候选页，但一个引用位并不等于本页精确的四次引用窗口。比较测量结果时，要同时写清采样频率和丢失了哪些时间细节。

复算时请先列窗口，再去重，最后讨论它与驻留预算是否匹配。这个顺序能避免把“最近四次访问”“四个不同页”和“已经分到四帧”当作同一件事。

参考资料

Peter J. Denning，“The Working Set Model for Program Behavior”，Communications of the ACM 11(5)，1968，pp.323–333；pp.324、326定义进程时间与工作集，pp.326–328讨论预测、参数和采样。本页离散引用窗口、九步轨迹与共享身份去重为明确的教学变体。