工作集是程序在指定时间段内使用的内存页或其他数据单元的集合。在经典定义中,工作集是描述进程近期内存访问情况的模型,操作系统利用它来估计哪些页面应当保留在物理内存中。从更广泛的意义上说,这个术语描述的是应用程序、计算任务或工作负载在存储层次结构的某一层中活跃使用的数据。因此,工作集随时间而变化:它不一定包含程序分配的全部内存,也不一定与当前驻留在 RAM 中的内存完全相同。
起源与目的
彼得·J. 丹宁在 20 世纪 60 年代提出了工作集模型,并于 1968 年发表了具有重要影响的论文《程序行为的工作集模型》(The Working Set Model for Program Behavior)。该模型旨在解决虚拟内存中的一个核心问题:如何判断正在执行的程序需要多少物理内存,才能有效推进执行。
采用分页机制时,程序的虚拟地址空间被划分为大小固定的页面,在任一时刻只需将其中一部分保留在物理内存中。当执行过程访问了一个未驻留的页面时,就会发生缺页异常。处理这一异常可能需要从存储设备中读取数据,不过有些缺页异常无需访问存储设备即可处理。
工作集方法将内存分配与观测到的程序行为联系起来。系统不必为每个进程分配固定不变的页框数量,而是可以尝试保留各进程正在活跃使用的页面。当这些进程的内存需求总量超过可用容量时,系统还可以限制同时处于活跃状态的进程数量。
形式化定义
在按访问次数定义的形式中,设 为某进程的虚拟页面访问序列。对于长度为正整数 的窗口,第 次访问后的工作集为
工作集大小是该集合中不同页面的数量:
重复访问同一页面不会增大集合的大小。例如,若最近六次访问为
则该窗口对应的工作集为 ,大小为四个页面。
另一种常见定义以进程执行时间来度量窗口,而不是采用固定的访问次数。这一区别很重要:按访问次数划定的窗口与按执行时间划定的窗口,未必包含相同的访问。进程执行时间也不同于实际经过的时间,后者在进程挂起期间仍会继续流逝。
如果每个页面的大小为 字节,那么该集合代表的内存量就是 字节。这是一种以页面为粒度的度量,并不意味着这些页面中的每个字节都被访问过。
窗口的选择
窗口决定了测量所采用的时间尺度。
- 短窗口能迅速响应变化,但可能遗漏那些以较长间隔规律使用的页面。
- 长窗口能涵盖更多程序的重复行为,但也可能保留属于先前执行阶段的页面。
- 在固定的观测时点,增大窗口不会使工作集变小,因为较大的窗口包含较小窗口中的全部访问。
不存在普遍适用的最佳窗口。窗口是否有用,取决于工作负载、所需数据不在内存中的代价,以及要作出的内存管理决策。
局部性与程序阶段
该模型以访问局部性为基础:程序通常会在一段时间内,将访问集中在有限的代码和数据区域中。
时间局部性是指近期访问过的内容很可能再次被访问。空间局部性是指相邻的地址往往会被接连访问。工作集直接反映近期的使用情况,而以页面或缓存行为粒度的数据调入,也会将邻近数据一并带入内存。
程序可能经历多个阶段,各阶段的工作集有所不同。例如,编译器可能先处理源代码文本,再遍历中间表示,最后生成机器码。每个阶段可能侧重于不同的数据结构。在阶段切换期间,一个窗口可能暂时同时包含新旧两个阶段的页面,从而形成较大的工作集。
近期使用情况只是对未来需求的估计,并非保证。顺序扫描可能访问大量页面,却不再访问它们;而未出现在近期窗口中的某个页面,也可能紧接着就变得重要。
内存分配与内存抖动
经典的工作集策略力求让每个活跃进程的工作集都驻留在内存中。在选定窗口内未被访问的页面,则成为可回收的候选页面。
如果分配给某个进程的页框数量远少于其当前计算所需的数量,该进程可能反复访问刚被换出的页面,导致缺页异常。当过度的页面调入调出使系统几乎没有时间执行有效工作时,系统便发生了内存抖动。
对于工作集分别为 的进程,可以用以下简化公式估计内存需求:
如果这一需求超过了可供这些进程使用的页框数量,操作系统可能需要减少活跃进程的数量,或从其他地方回收内存。这个总和只是近似值:估算物理存储需求时,共享页面不能重复计数,而且系统还需要为内核数据、缓冲区及其他用途保留内存。
因此,工作集管理同时涉及页面置换和负载控制。当物理内存不足时,仅仅改用另一种页面淘汰策略,并不能让任意多的活跃工作集同时容纳其中。
实现与近似方法
精确跟踪每一次内存访问的开销通常过高,不适合操作系统日常使用。实际实现往往通过硬件维护的页面访问信息、定期采样和软件记录,来估计近期的活动情况。
页面置换算法可以检查与页面映射关联的访问位。如果该位表明页面近期被使用过,系统就可以记录这一情况,并清除该位,以便在后续采样周期中继续观察。这类方法近似估计的是距页面最近一次访问所经过的时间,而不是重建精确的访问序列。
工作集思想与最近最少使用置换策略有关,但两者并不相同。最近最少使用置换策略按照页面最近被访问的先后顺序对其排序;工作集策略则识别指定窗口内使用过的页面,并可利用所得集合的大小来指导内存分配。
WSClock 将工作集的页面访问年龄信息与时钟式页框扫描结合起来。它在确定置换候选页面时,会考虑页面近期是否被使用,以及是否被修改。另一种相关方法是缺页频率控制,它根据观测到的缺页频率调整内存分配,而不显式构建工作集。
工作集与其他内存度量的区别
以下几种度量分别描述进程内存的不同方面:
| 度量 | 描述内容 |
|---|---|
| 虚拟地址空间大小 | 为进程映射或预留的虚拟地址范围 |
| 驻留集 | 当前位于物理内存中的页面 |
| 经典工作集 | 在指定的近期窗口内访问过的不同页面 |
| 私有内存 | 按照所采用的统计口径,不与其他进程共享的内存 |
驻留集可能包含不活跃的页面,而近期观测到的工作集中的某些页面,也可能已经被换出。
不同平台使用的术语也有所不同。在微软 Windows 中,进程的工作集是指其虚拟地址空间中当前驻留在物理内存里的可分页页面。这一操作性定义与丹宁基于时间窗口的定义并不相同。私有工作集的统计不包含共享页面。
在 Linux 上,驻留内存统计以及按比例分摊共享页面的统计方式,能够提供有用的内存度量,但不能直接将其视为经典工作集的测量结果。进行比较时,需要注意各个计数器包含哪些内容、采样间隔是多少,以及如何处理共享内存。
更广泛的应用与局限
工作集一词的应用并不限于虚拟内存页面。在 CPU 缓存层面,工作集可以指某项计算正在反复使用的缓存行。在数据库中,它可以指经常访问的表页面和索引页面。完整数据集可能远大于活跃工作集。
这一区别有助于解释:为什么不减少输入数据总量,仅通过重新组织计算方式,也能提高性能。例如,将数组分块处理,可以减少必须同时保留在高速缓存中的数据量。
工作集大小并不能单独决定性能。两个工作集大小相同的工作负载,可能具有截然不同的访问频率、写入行为和内存带宽需求。即使某个集合未超出缓存的标称容量,也可能因映射冲突或其他工作负载的干扰而发生缓存未命中。在非统一内存访问系统中,驻留页面所在的物理位置也会影响访问开销。
因此,只有明确测量范围,工作集测量才有意义:必须说明观测的是哪个执行实体、采用什么内存单位、使用多大的观测窗口,以及研究的是哪一层存储的行为。