李忠武，李青，夏春梅

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

Metronome回收器分析研究

李忠武，李青，夏春梅

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

1 時間使用率

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

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

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

2 空間使用率

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

我們進一步定義所需額外空間的最大值：

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

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

而整個程序的空間需求量為：

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

3 變更操作

由于寫屏障必須記錄賦值器所刪除和插入的每個引用，所以變更操作也存在額外的空間開銷。回收器必須確保寫屏障的開銷是一個常量。寫屏障不僅過濾掉null引用，而且要對目標對象進行標記以避免重復記錄，從而確保回收器的工作量存在上限（最差情況下，堆中所有對象都將被標記為存活）。因此在最差情況下，寫屏障日志中的條目數(shù)量會與堆中對象的數(shù)量相等。針對這一情況，日志條目的分配應當與一般對象的分配有所區(qū)分。

4 敏感性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

進一步得出一個完整的回收周期所需的額外空間問題為：

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

則總體空間需求量為：

6 結(jié)束語

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

[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].北京：機械工業(yè)出版社，2015.

[3]王志英，計算機體系結(jié)構(gòu)[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