李忠武，李青，夏春梅

（保山學(xué)院，云南保山，678000）

Metronome回收器分析研究

李忠武，李青，夏春梅

（保山學(xué)院，云南保山，678000）

基于時(shí)間的調(diào)度策略首先在面向Java的Metronome實(shí)時(shí)垃圾回收器中得到應(yīng)用，它是一個(gè)增量式的標(biāo)記——清掃回收器，并會(huì)在必要時(shí)進(jìn)行局部整理以避免堆的碎片化。該回收器使用刪除寫屏障來維護(hù)弱三色不變式，即回收器將寫操作所覆蓋的指針域的目標(biāo)對(duì)象標(biāo)記為存活。標(biāo)記過程中新分配的對(duì)象標(biāo)記為黑色。與Blelloch和Cheng的副本復(fù)制回收器相比，該回收器寫操作的標(biāo)記開銷更低（同時(shí)也具有更高的可預(yù)測(cè)性）。筆者試從Metronome回收器的時(shí)間使用率、空間使用率、變更操作、敏感性和與基于工作的調(diào)度策略幾個(gè)方面對(duì)Metronome回收器分析研究，提出從賦值器使用率和內(nèi)存使用率角度出發(fā)來設(shè)計(jì)回收器的方法。

回收器；內(nèi)存；賦值器；垃圾

0 引言

Metronome回收器的最大貢獻(xiàn)之一在于其最早提出了內(nèi)存垃圾回收調(diào)試問題的形式模型，以及從賦值器使用率和內(nèi)存使用率角度出發(fā)來設(shè)計(jì)回收器的方法。該模型通過如下幾個(gè)參數(shù)實(shí)現(xiàn)參數(shù)化：賦值器瞬時(shí)分配率 A *τ、賦值器瞬時(shí)垃圾生成率G*（）τ 、垃圾回收處理率P（依照存活數(shù)據(jù)進(jìn)行測(cè)量）。所有這些參數(shù)均按照單位時(shí)間內(nèi)的單位數(shù)據(jù)量進(jìn)行定義。此處的時(shí)間 是指賦值器時(shí)間，并假定回收器可以運(yùn)行得無限快（也可更加實(shí)際地假定可用內(nèi)存足夠多，無需進(jìn)行垃圾回收）。

通過這些參數(shù)，我們便可簡(jiǎn)單地將時(shí)段（，） τ1τ2中的內(nèi)存分配量定義為：

類似地，該時(shí)段內(nèi)的垃圾生成量可以定義為：

?t 時(shí)段內(nèi)的最大內(nèi)存分配量為：

進(jìn)一步得出最大內(nèi)存分配率（此處需要注意區(qū)分α（*某一時(shí)段內(nèi)的最大內(nèi)存分配率）與α（*程序整個(gè)生命周期內(nèi)的最大內(nèi)存分配量））為：

在給定時(shí)間 ，程序的瞬間內(nèi)存需求量（包括垃圾、額外開銷、內(nèi)存碎片）為：

程序的真正執(zhí)行時(shí)間當(dāng)然還要包括回收器的執(zhí)行時(shí)間，因此我們引入函數(shù)t?τ→：來表示從真正時(shí)間t到賦值器執(zhí)行時(shí)間 的映射，此時(shí)必然有 。我們將以賦值器時(shí)間作為參數(shù)的函數(shù)記為*

f，而將以真正時(shí)間作為參數(shù)的函數(shù)記為 f。則在t時(shí)刻，程序的存活內(nèi)存總量為：

而程序執(zhí)行過程中的最大內(nèi)存需求量為：

1 時(shí)間使用率

除了上述各項(xiàng)參數(shù)外，基于時(shí)間的調(diào)度策略還包括兩個(gè)額外的參數(shù)：賦值器執(zhí)行時(shí)間單元TQ以及回收器執(zhí)行時(shí)間單元TC，它們分別表示賦值器和回收器在放棄執(zhí)行（yield）之前可以使用的時(shí)間量。據(jù)此，我們可以把最小賦值器使用率定義為：

隨著程序的執(zhí)行，最小賦值器使用率會(huì)逐漸趨近于賦值器占整體執(zhí)行時(shí)間的期望值，即：

下面以一個(gè)可以實(shí)現(xiàn)精確調(diào)度的系統(tǒng)為例，假定回收器執(zhí)行時(shí)間單元 CT=10，即賦值器可能經(jīng)歷的最大停頓時(shí)間為10μ s。圖1展示了在賦值器執(zhí)行時(shí)間單元分別為 QT=2.5、QT= 1 0、QT=40時(shí)的最小賦值器使用率曲線。從圖中可以注意到：當(dāng)?t足夠大時(shí)，u (? t)逐漸向收斂；回收器的執(zhí)行頻率越高T（即賦值器執(zhí)行的時(shí)間單元 QT越短），則曲線的收斂速度越快。除此之外，時(shí)間范圍越小，則參數(shù) 對(duì)實(shí)時(shí)系統(tǒng)的影響比重越大。當(dāng)然，實(shí)際應(yīng)用中的回收器通常只會(huì)斷續(xù)執(zhí)行，因而 uT(?t)只是賦值器使用率的下限。

2 空間使用率

前邊提到，空間利用率會(huì)根據(jù)賦值器分配率的變化而有所不同。假定回收率固定為P，則在t時(shí)刻，回收器將花費(fèi) ()/m t p時(shí)間來處理 ()m t的存活數(shù)據(jù)（工作量正比于標(biāo)記存活對(duì)象所需的追蹤工作）?；厥掌髅繄?zhí)行一個(gè)TC 的時(shí)間單元，賦值器都會(huì)執(zhí)行一個(gè)TQ 的時(shí)間單元。因此在時(shí)刻t執(zhí)行增量回收所必需的額外空間為：

我們進(jìn)一步定義所需額外空間的最大值：

Metronome回收器釋放一個(gè)垃圾對(duì)象可能需要長(zhǎng)達(dá)三個(gè)回收周期：第一個(gè)回收周期將判斷對(duì)象是否為垃圾；如果其在當(dāng)前回收周期的快照獲取完畢之后立即成為垃圾，則其只能在下一個(gè)回收周期中得到回收。而在第二個(gè)回收周期中，如果該對(duì)象在得到釋放之前又需要進(jìn)行遷移，則其只能在第三個(gè)回收周期中得到回收。

因此，系統(tǒng)在時(shí)刻 所需的空間為（內(nèi)部忽略碎片）：

而整個(gè)程序的空間需求量為：

這一數(shù)值即為系統(tǒng)在最差情況下的空間需求量，此時(shí)所有垃圾對(duì)象都將被保留到下一個(gè)回收周期，而它們?cè)谙乱粋€(gè)回收周期中又都需要移動(dòng)。空間需求量的期望值是

3 變更操作

由于寫屏障必須記錄賦值器所刪除和插入的每個(gè)引用，所以變更操作也存在額外的空間開銷?；厥掌鞅仨毚_保寫屏障的開銷是一個(gè)常量。寫屏障不僅過濾掉null引用，而且要對(duì)目標(biāo)對(duì)象進(jìn)行標(biāo)記以避免重復(fù)記錄，從而確?；厥掌鞯墓ぷ髁看嬖谏舷蓿ㄗ畈钋闆r下，堆中所有對(duì)象都將被標(biāo)記為存活）。因此在最差情況下，寫屏障日志中的條目數(shù)量會(huì)與堆中對(duì)象的數(shù)量相等。針對(duì)這一情況，日志條目的分配應(yīng)當(dāng)與一般對(duì)象的分配有所區(qū)分。

4 敏感性

只有當(dāng)開發(fā)者所提供的參數(shù)能夠精確反映應(yīng)用程序與回收器的特征時(shí)，Metronome回收器的運(yùn)行時(shí)行為才能達(dá)到預(yù)期目標(biāo)，這些參數(shù)包括：應(yīng)用程序的分配率*()A t、垃圾生成率*()G t、回收器處理率P、賦值器和回收器各自的執(zhí)行時(shí)間單元TQ 和TC 。賦值器使用率Tu公取決于TQ和TC，因而其值可以保持穩(wěn)定（除此這外，僅可能受到操作系統(tǒng)傳遞時(shí)間單元相關(guān)信號(hào)的波動(dòng)以及最小時(shí)間單元的影響）。

整個(gè)程序的空間需求量 ST會(huì)受到垃圾回收所必需的額外空間的影響，而后者又取決于程序的最大內(nèi)存使用量m以及賦值器在一個(gè)執(zhí)行時(shí)間單元里的內(nèi)存分配量。如果開發(fā)者低估了總空間需求量m或者最大分配 率α*，則總內(nèi)存需求量ST可能會(huì)出現(xiàn)不可控制的增長(zhǎng)。如果在賦值器某一時(shí)刻的分配率過高，則基于時(shí)間的回收器很容易出現(xiàn)內(nèi)存需求量暴增的情況。類似地，開發(fā)者也必須對(duì)回收器處理率P進(jìn)行較為保守的估計(jì)（即小于真正的回收處理率）。

幸運(yùn)的是，相對(duì)于賦值器執(zhí)行時(shí)間單元而言，一個(gè)回收周期的持續(xù)時(shí)間相對(duì)較長(zhǎng)：

因此，回收周期內(nèi)的分配率將接近于平均分配率，因而只要最大內(nèi)存需求量 得到準(zhǔn)確評(píng)估，系統(tǒng)的空間消耗量將幾乎保持不變。

5 與基于工作的調(diào)度策略的比較

我們可以對(duì)基于工作的調(diào)度策略進(jìn)行簡(jiǎn)單的分析，然后再將其與基于時(shí)間的調(diào)度策略進(jìn)行比較。但是，賦值器的操作卻會(huì)影響其能占用的執(zhí)行時(shí)間，從而對(duì)分析結(jié)果造成影響。更加正式地講，對(duì)于基于時(shí)間的調(diào)度策略，從真正時(shí)間 到賦值器時(shí)間 的映射函數(shù)?是線性且固定的，而對(duì)于基于工作的調(diào)度策略，這一映射則是變化的、非線性的，具體取決于應(yīng)用程序。

在基于工作的調(diào)度策略中，當(dāng)賦值器達(dá)到一定的內(nèi)存分配量時(shí)，調(diào)度器便會(huì)喚起回收器并執(zhí)行一定的回收工作，這一工作模式可以從回收器的兩個(gè)輸入?yún)?shù)中得到體現(xiàn)：賦值器工作單元QW和回收器工作單元 CW分別表示調(diào)度器允許賦值器/回收器在讓出CPU之前執(zhí)行多少（相對(duì)）內(nèi)存分配/回收工作。

對(duì)基于工作的調(diào)度策略，由于其時(shí)間映射函數(shù)?是變化的、非線性的，所以無法得出最小賦值器使用率的封閉解。在每個(gè)回收增量中，回收器會(huì)以速率P處理總量為 CW的內(nèi)存，因而回收停頓時(shí)間固定為 d = CW/P。每個(gè)賦值器執(zhí)行單元會(huì)分配總量為的QW內(nèi)存，因此第i個(gè)賦值器執(zhí)行單元的最小執(zhí)行時(shí)間?τi為滿足如下等式的解：

增大時(shí)間間隔并不會(huì)降低賦值器在該時(shí)間段內(nèi)的最大內(nèi)存分配量，因而 α*(? τi)會(huì)呈現(xiàn)單調(diào)遞增的趨勢(shì)。因此 ?τi＞ ?τi? 1 ，則等式（15）可以通過迭代的方式求解。假定k為最大的整數(shù)，則有：

因此，在時(shí)段?t內(nèi)最小賦值器使用率為：

其中，?τk為時(shí)段?t內(nèi)k個(gè)賦值器執(zhí)行單元的總時(shí)長(zhǎng)，y為其余賦值器執(zhí)行單元，其定義如下：

需要注意的是，當(dāng)?t＜d時(shí)，最小賦值器使用率uW(?t)將低至零。除此之外，一旦賦值器分配了大小為 n QW的對(duì)象，回收器便必須執(zhí)行n個(gè)回收工作單元，從而產(chǎn)生至少nd的回收停頓時(shí)間，在此期間賦值器使用率也將降低至零。這一分析結(jié)果表明，開發(fā)者必須避免在基于工作的垃圾回收環(huán)境下分配過大的對(duì)象，同時(shí)必須確保分配操作分布均勻，只有這樣才能確保應(yīng)用程序滿足實(shí)時(shí)要求。

最小賦值器使用率取決于賦值器的分配率α（*?t)（其中，?t ≤ ?τ ）以及回收器處理率P。假定需要滿足實(shí)時(shí)性能要求的時(shí)段?t較小（例如20ms），則該時(shí)段內(nèi)的峰值分配率可能會(huì)高。因此，從實(shí)時(shí)尺度來看，基于工作的調(diào)度策略的最小賦值器使用率 uW(? t)將會(huì)與賦值器分配率存在很大差異。而對(duì)于基于時(shí)間的調(diào)度策略，回收器受分配率影響的時(shí)間?τ則是一個(gè)更大的范圍，即回收器完成一個(gè)垃圾回收周期所需的時(shí)間。

在空間方面，回收器在時(shí)刻 所需的額外空間量為：

進(jìn)一步得出一個(gè)完整的回收周期所需的額外空間問題為：

只要開發(fā)者對(duì)總存活內(nèi)存量 預(yù)估準(zhǔn)確，則該值也必然是準(zhǔn)確的。另外需要注意的是，如果 QW＜CW，則一個(gè)完整回收周期所需的額外空間總量 eW將超過賦值器所需的空間總量m。因此在時(shí)刻 ，應(yīng)用程序的總內(nèi)存需求量為：

則總體空間需求量為：

6 結(jié)束語

綜上所述，對(duì)于基于工作的回收調(diào)度策略，只要存活內(nèi)存總量 預(yù)估準(zhǔn)確，則應(yīng)用程序必然可以滿足空間界限要求，但其最小賦值器使用率則嚴(yán)重依賴于賦值器執(zhí)行實(shí)時(shí)任務(wù)時(shí)的分配率。與此相比，盡管基于時(shí)間的回收器很容易滿足最小賦值器使用率的要求，但其空間需求總量卻可能產(chǎn)生波動(dòng)。

[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.）.人工智能計(jì)算Agent基礎(chǔ)[M].北京：機(jī)械工業(yè)出版社，2015.

[3]王志英，計(jì)算機(jī)體系結(jié)構(gòu)[M]，清華大學(xué)出版社，2014.

李忠武，副教授，主要從事計(jì)算機(jī)科學(xué)研究。

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