A Non-Fragmenting Non-Moving Garbage Collector Gustavo

A Non-Fragmenting Non-Moving
Garbage Collector
Gustavo Rodriguez-Rivera,Michael Spertus,Charles Fiterman
Geodesic Systems
について
発表者 : 小林義徳
[email protected]
ISMM 98 Pages 79-85
http://www.acm.org/pubs/contents/proceedings/plan/286860/
内容
Introduction
Boehm
GC について
Fragmentation
を防ぐ二つの手法
Medium size objects in BiBoP like allocators
Footprint reduction
仮想メモリを利用した方法
実験および実験結果
Introduction(1)
Non-moving Garbage Collector の弱点
オブジェクトを動かせない
fragmentation の問題に弱い。
cf. moving collectors
オブジェクトを動かすことで、
fragmentation を解消できる
移動には、ポインタの書き換えを伴うため、
Conservative GC では使えない。
Introduction(2)
Great Circle
Geodesic Systems 社の、商用GC ライブラリ
後述する二つの手法により、fragmentation を低減
Boehm GC の改造という形で実装
Geodesic Systems,Inc.
http://www.geodesic.com/products/products.html
Boehm GC について
Allocation 戦略～ BiBoP(Big-Bag-of-Pages)
 Boehm GC でのオブジェクトのサイズによる分類
 Black-Listing について

BiBoP(Big-Bag-of-Pages)
1 つのページ内のオブジェクトは、全て同じサイズ。
 異なるサイズのオブジェクトは、異なるページから割り
当てる。


あるポインタに対し、
オブジェクトの開始アドレス
オブジェクトのサイズ
を知ることができる。

ページ内のオブジェクトサイズの違いによる
内部断片化が起こらない。
Boehm GC でのオブジェクトの
サイズによる分類

Small objects
1 つのページを分割することで allocate される
object
 Large objects(page サイズ)
1 つ以上の連続したページを確保
 ページサイズの半分 + ε
またはページサイズ + ε
の要求が来た時、深刻な内部断片化が。
内部断片化がおこる例
ページサイズ : 4096 bytes
Allocate 要求 : 2050 bytes
Boehm GC では、4096 bytes を確保
残りの2046 bytes は無駄に。
ページサイズ : 4096 bytes
無駄
2050 bytes
Black-Listing
Pointer に指されているページを
あらかじめ Black List に登録
 Black List に載っているページからの
オブジェクトの Allocate は避ける
 False
生きたオブジェクトを指す False Pointer を
減らすことができる
Fragmentation を防ぐ二つの手法
 Medium size objects in BiBoP like allocators
内部断片化を減らす
 Footprint reduction
外部断片化を減らす
仮想メモリを利用した方法
Medium Objects(1)
 Small
objects
1 つのページを分割することで allocate
 Large objects
1 つ以上の連続したページを確保
 Medium objects
複数ページをいくつかに分割
Medium Objects(2)
ページサイズ : 4096 bytes
Allocate 要求 : 2050 bytes
 Medium objects をサポートしたGC では、
2 つのページを 3 つに分割
8192 = 2730 * 3 + 2
 Boehm GC
4096 – 2050 = 2046 bytes wasted
 This GC
2730 – 2050 = 680 bytes wasted
Medium Objects(3)
Fragmentation
= (realSize – requestedSize) / realSize
Objects がない場合(Figure 1)
 Medium Objects がある場合(Figure 2)
 Medium
要求サイズが 2049 バイト付近の場合、Medium Object なしの方は
Fragmentation が 50 % 近いのに対し、Medium Object ありの方は
Fragmentation が 20% ぐらいにまで抑えられている。
Footprint reduction
ページに対する、commit / uncommit operation
 uncommit 操作で、仮想メモリのページに
対応する実メモリのみ OS に返される。
 アドレス空間を再利用できる。
cf. map/unmap operation
 unmap 操作で、アドレス空間と実メモリの
両方がOS に返される。
Footprint reductionの例
(Figure 3)
4 つの Live Objects
 3 つの Free pages
 3 つの uncommitted pages
 しかし、図の左側で、3 つの free pages は連
続ではない。
 Footprint reduction により、Free と
Uncommitted を入れ替え、連続なアドレスが
得られる。

Footprint reduction (Figure 3)
Footprint reduction
Great Circle では・・・
あらかじめ決められた回数だけ Garbage Collection
が呼ばれたときに、Footprint Reduction が実行される。
 あらかじめ決められた回数の GC にわたって使われ
てないページは、uncommit され、OS に返される。


Blacklist に載っているページに対しては、
実メモリが uncommitted であるという効果もある。
Footprint reduction の実装(1)
 Page-flags
Committed-bit
Free-bit
Recently used-bit
初期化時に、大きなページ列をアドレス空間のみ取得
(arena)。また、page-flags がクリアされる
Footprint reduction の実装(2)
Large Object の要求がきて、free list の中からでは要
求に応えられない場合の動作




Arena の中から、十分な大きさの uncommitted pages を見
つける。
1.のページを commit し、free list に追加する。また、
committed-bits と free-bits を更新。
要求が満たされる。
Arena 中の、連続な uncommitted pages が十分な大きさ
でない場合、新しく uncommitted pages を OS からとってき
て、arena に追加する。
Footprint reductionの実装(3)
 ページが
free-list に返された場合、
recently used-bits と free-bits がセットされる。
中に、
recently used-bit が立っていないページは
OS に返され、ヒープが縮小される。
 Footprint reduction
実験


Netscape について、メモリ使用量を測定
Sparc Station 10
 Solaris Operating System
 Injection technique を用いて、Netscape と
X-Server の両方にGreat Circle を実行時
にリンク。
 メモリは、明示的に確保・開放している。
実験
Figure 4
 Without
footprint reduction
 Netscape を 5 分間走らせたときのHeap Size
 約 40 のドキュメントをロード
実験
Figure 5

With footprint reduction
 その他は、Figure 4 のときと同じ
Footprint reduction は、毎回連続な 100 kB を free-list
に返す
 100 kB という数字は、実行時に tune することもできる。

結論(1)
Footprint Reduction
は long-lived application
に対し、非常に有効である。
 とくに、Netscape のような、負荷の変化が激し
いアプリケーションではとりわけ有効である。
 Footprint reduction
結論(2)
Medium Objects
objects による advantage は、
この実験ではよくわからない。
 Medium objects が有効であることを示すに
は、さらなる実験が必要であろう。
 Medium
References

Boehm GC について
“Space Efficient Conservative Garbage Collection”
Hans-Juergen Boehm

Injection Technique について
“Non-intrusive cloning garbage collection with stock
operating system support.”
Gustavo Rodriguez-Rivera,Vincent Russo.
Marking with blacklisting
mark(p){
if p is not a valid object address{
if p is in the vicinity of the heap{ add p to blacklist }
return
}
if p is marked { return }
set mark bit for p
foreach field q in the object referenced by p { mark(q) }
}

Download Report