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