Metronome回收器分析研究

李忠武，李青，夏春梅

（保山学院，云南保山，678000）

Metronome回收器分析研究

李忠武，李青，夏春梅

（保山学院，云南保山，678000）

基于时间的调度策略首先在面向Java的Metronome实时垃圾回收器中得到应用，它是一个增量式的标记——清扫回收器，并会在必要时进行局部整理以避免堆的碎片化。该回收器使用删除写屏障来维护弱三色不变式，即回收器将写操作所覆盖的指针域的目标对象标记为存活。标记过程中新分配的对象标记为黑色。与Blelloch和Cheng的副本复制回收器相比，该回收器写操作的标记开销更低（同时也具有更高的可预测性）。笔者试从Metronome回收器的时间使用率、空间使用率、变更操作、敏感性和与基于工作的调度策略几个方面对Metronome回收器分析研究，提出从赋值器使用率和内存使用率角度出发来设计回收器的方法。

回收器；内存；赋值器；垃圾

0 引言

Metronome回收器的最大贡献之一在于其最早提出了内存垃圾回收调试问题的形式模型，以及从赋值器使用率和内存使用率角度出发来设计回收器的方法。该模型通过如下几个参数实现参数化：赋值器瞬时分配率 A *τ、赋值器瞬时垃圾生成率G*（）τ 、垃圾回收处理率P（依照存活数据进行测量）。所有这些参数均按照单位时间内的单位数据量进行定义。此处的时间 是指赋值器时间，并假定回收器可以运行得无限快（也可更加实际地假定可用内存足够多，无需进行垃圾回收）。

通过这些参数，我们便可简单地将时段（，） τ1τ2中的内存分配量定义为：

类似地，该时段内的垃圾生成量可以定义为：

∆t 时段内的最大内存分配量为：

进一步得出最大内存分配率（此处需要注意区分α（*某一时段内的最大内存分配率）与α（*程序整个生命周期内的最大内存分配量））为：

在给定时间 ，程序的瞬间内存需求量（包括垃圾、额外开销、内存碎片）为：

程序的真正执行时间当然还要包括回收器的执行时间，因此我们引入函数tϕτ→：来表示从真正时间t到赋值器执行时间 的映射，此时必然有 。我们将以赋值器时间作为参数的函数记为*

f，而将以真正时间作为参数的函数记为 f。则在t时刻，程序的存活内存总量为：

而程序执行过程中的最大内存需求量为：

1 时间使用率

除了上述各项参数外，基于时间的调度策略还包括两个额外的参数：赋值器执行时间单元TQ以及回收器执行时间单元TC，它们分别表示赋值器和回收器在放弃执行（yield）之前可以使用的时间量。据此，我们可以把最小赋值器使用率定义为：

随着程序的执行，最小赋值器使用率会逐渐趋近于赋值器占整体执行时间的期望值，即：

下面以一个可以实现精确调度的系统为例，假定回收器执行时间单元 CT=10，即赋值器可能经历的最大停顿时间为10µ s。图1展示了在赋值器执行时间单元分别为 QT=2.5、QT= 1 0、QT=40时的最小赋值器使用率曲线。从图中可以注意到：当∆t足够大时，u (∆ t)逐渐向收敛；回收器的执行频率越高T（即赋值器执行的时间单元 QT越短），则曲线的收敛速度越快。除此之外，时间范围越小，则参数 对实时系统的影响比重越大。当然，实际应用中的回收器通常只会断续执行，因而 uT(∆t)只是赋值器使用率的下限。

2 空间使用率

前边提到，空间利用率会根据赋值器分配率的变化而有所不同。假定回收率固定为P，则在t时刻，回收器将花费 ()/m t p时间来处理 ()m t的存活数据（工作量正比于标记存活对象所需的追踪工作）。回收器每执行一个TC 的时间单元，赋值器都会执行一个TQ 的时间单元。因此在时刻t执行增量回收所必需的额外空间为：

我们进一步定义所需额外空间的最大值：

Metronome回收器释放一个垃圾对象可能需要长达三个回收周期：第一个回收周期将判断对象是否为垃圾；如果其在当前回收周期的快照获取完毕之后立即成为垃圾，则其只能在下一个回收周期中得到回收。而在第二个回收周期中，如果该对象在得到释放之前又需要进行迁移，则其只能在第三个回收周期中得到回收。

因此，系统在时刻 所需的空间为（内部忽略碎片）：

而整个程序的空间需求量为：

这一数值即为系统在最差情况下的空间需求量，此时所有垃圾对象都将被保留到下一个回收周期，而它们在下一个回收周期中又都需要移动。空间需求量的期望值是

3 变更操作

由于写屏障必须记录赋值器所删除和插入的每个引用，所以变更操作也存在额外的空间开销。回收器必须确保写屏障的开销是一个常量。写屏障不仅过滤掉null引用，而且要对目标对象进行标记以避免重复记录，从而确保回收器的工作量存在上限（最差情况下，堆中所有对象都将被标记为存活）。因此在最差情况下，写屏障日志中的条目数量会与堆中对象的数量相等。针对这一情况，日志条目的分配应当与一般对象的分配有所区分。

4 敏感性

只有当开发者所提供的参数能够精确反映应用程序与回收器的特征时，Metronome回收器的运行时行为才能达到预期目标，这些参数包括：应用程序的分配率*()A t、垃圾生成率*()G t、回收器处理率P、赋值器和回收器各自的执行时间单元TQ 和TC 。赋值器使用率Tu公取决于TQ和TC，因而其值可以保持稳定（除此这外，仅可能受到操作系统传递时间单元相关信号的波动以及最小时间单元的影响）。

整个程序的空间需求量 ST会受到垃圾回收所必需的额外空间的影响，而后者又取决于程序的最大内存使用量m以及赋值器在一个执行时间单元里的内存分配量。如果开发者低估了总空间需求量m或者最大分配 率α*，则总内存需求量ST可能会出现不可控制的增长。如果在赋值器某一时刻的分配率过高，则基于时间的回收器很容易出现内存需求量暴增的情况。类似地，开发者也必须对回收器处理率P进行较为保守的估计（即小于真正的回收处理率）。

幸运的是，相对于赋值器执行时间单元而言，一个回收周期的持续时间相对较长：

因此，回收周期内的分配率将接近于平均分配率，因而只要最大内存需求量 得到准确评估，系统的空间消耗量将几乎保持不变。

5 与基于工作的调度策略的比较

我们可以对基于工作的调度策略进行简单的分析，然后再将其与基于时间的调度策略进行比较。但是，赋值器的操作却会影响其能占用的执行时间，从而对分析结果造成影响。更加正式地讲，对于基于时间的调度策略，从真正时间 到赋值器时间 的映射函数ϕ是线性且固定的，而对于基于工作的调度策略，这一映射则是变化的、非线性的，具体取决于应用程序。

在基于工作的调度策略中，当赋值器达到一定的内存分配量时，调度器便会唤起回收器并执行一定的回收工作，这一工作模式可以从回收器的两个输入参数中得到体现：赋值器工作单元QW和回收器工作单元 CW分别表示调度器允许赋值器/回收器在让出CPU之前执行多少（相对）内存分配/回收工作。

对基于工作的调度策略，由于其时间映射函数ϕ是变化的、非线性的，所以无法得出最小赋值器使用率的封闭解。在每个回收增量中，回收器会以速率P处理总量为 CW的内存，因而回收停顿时间固定为 d = CW/P。每个赋值器执行单元会分配总量为的QW内存，因此第i个赋值器执行单元的最小执行时间∆τi为满足如下等式的解：

增大时间间隔并不会降低赋值器在该时间段内的最大内存分配量，因而 α*(∆ τi)会呈现单调递增的趋势。因此 ∆τi＞ ∆τi− 1 ，则等式（15）可以通过迭代的方式求解。假定k为最大的整数，则有：

因此，在时段∆t内最小赋值器使用率为：

其中，∆τk为时段∆t内k个赋值器执行单元的总时长，y为其余赋值器执行单元，其定义如下：

需要注意的是，当∆t＜d时，最小赋值器使用率uW(∆t)将低至零。除此之外，一旦赋值器分配了大小为 n QW的对象，回收器便必须执行n个回收工作单元，从而产生至少nd的回收停顿时间，在此期间赋值器使用率也将降低至零。这一分析结果表明，开发者必须避免在基于工作的垃圾回收环境下分配过大的对象，同时必须确保分配操作分布均匀，只有这样才能确保应用程序满足实时要求。

最小赋值器使用率取决于赋值器的分配率α（*∆t)（其中，∆t ≤ ∆τ ）以及回收器处理率P。假定需要满足实时性能要求的时段∆t较小（例如20ms），则该时段内的峰值分配率可能会高。因此，从实时尺度来看，基于工作的调度策略的最小赋值器使用率 uW(∆ t)将会与赋值器分配率存在很大差异。而对于基于时间的调度策略，回收器受分配率影响的时间∆τ则是一个更大的范围，即回收器完成一个垃圾回收周期所需的时间。

在空间方面，回收器在时刻 所需的额外空间量为：

进一步得出一个完整的回收周期所需的额外空间问题为：

只要开发者对总存活内存量 预估准确，则该值也必然是准确的。另外需要注意的是，如果 QW＜CW，则一个完整回收周期所需的额外空间总量 eW将超过赋值器所需的空间总量m。因此在时刻 ，应用程序的总内存需求量为：

则总体空间需求量为：

6 结束语

综上所述，对于基于工作的回收调度策略，只要存活内存总量 预估准确，则应用程序必然可以满足空间界限要求，但其最小赋值器使用率则严重依赖于赋值器执行实时任务时的分配率。与此相比，尽管基于时间的回收器很容易满足最小赋值器使用率的要求，但其空间需求总量却可能产生波动。

[1]R Jones，A Hosking，E Moss.The Garbage Collection Handbook: The Art of Automatic Memory Management.Chapman & Hall/CRC.2011.

[2（]加）普尔（Poole,D.L.），（加）麦克沃思（Mackworth,A.K.）.人工智能计算Agent基础[M].北京：机械工业出版社，2015.

[3]王志英，计算机体系结构[M]，清华大学出版社，2014.

李忠武，副教授，主要从事计算机科学研究。

Analysis of Metronome recovery device

Li Zhongwu, Li Qing,Xia Chunmei
（Baoshan University,Baoshan Yunnan,678000）

the first time scheduling strategy based on Metronome in real-time garbage collector for Java application, it is the mark of a recovery -- sweeping incremental, and will carry out the local finishing when necessary to avoid heap fragmentation. The collector used to remove write barriers to maintain weak color invariant, the target object is labeled pointer domain recovery device covered by the write operation will be the survival. Mark the newly assigned object to black. Compared with the Blelloch and Cheng replica replica collector, the collector has lower overhead and higher predictability for the write operation. I try from the Metronome recovery time utilization, space utilization, change operation, sensitivity and scheduling strategy several aspects of work based on Metronome recovery analysis, put forward from the mutator utilization and memory usage perspective method to design recovery device.

Recycle Bin; memory; distributor; garbage