GC/standard/Mark&Sweep
最終更新：
author_nari 2008年11月03日(月) 12:49:47履歴
Mark&Sweep 
和訳：印づけ、掃除
アルゴリズム
ルート(用語集)を全走査し、参照されているオブジェクトを見つけ出す。
見つけたオブジェクトに対して1bitマークをし、続けてオブジェクト内で参照しているオブジェクト(枝のオブジェクト)
に対して、印をつけていく。
ルートの走査が終わると、印があるもの（図：緑）とないもの（図：水色）に別れ、
印がないものはゴミ（参照なし）と判断され解放される。
この印付けをMark、ゴミの解放をSweepという。
保守的GCによく使われる。
オブジェクトの格納領域（ヒープ領域）を作成する際に、新規にallocateする処理の為に、
フリーリストで利用可能な領域を繋ぐ(空のオブジェクトを繋ぐと考えるといいかも)
そして、ユーザーがオブジェクトを作成する際にフリーリストから一つオブジェクトを貸し出す。
Sweepフェイズではヒープ領域を全走査し、Markされていないものを解放後、フリーリストにつなぎ直す。
見つけたオブジェクトに対して1bitマークをし、続けてオブジェクト内で参照しているオブジェクト(枝のオブジェクト)
に対して、印をつけていく。
ルートの走査が終わると、印があるもの（図：緑）とないもの（図：水色）に別れ、
印がないものはゴミ（参照なし）と判断され解放される。
この印付けをMark、ゴミの解放をSweepという。
保守的GCによく使われる。
オブジェクトの格納領域（ヒープ領域）を作成する際に、新規にallocateする処理の為に、
フリーリストで利用可能な領域を繋ぐ(空のオブジェクトを繋ぐと考えるといいかも)
そして、ユーザーがオブジェクトを作成する際にフリーリストから一つオブジェクトを貸し出す。
Sweepフェイズではヒープ領域を全走査し、Markされていないものを解放後、フリーリストにつなぎ直す。
利点
- GCの実装以外の場所ではGCのことを（あまり）考えなくていい
- サイクルも解放できる（サイクルについてはリファレンスカウントの項を参照）
欠点
- スイープのため最低一度はオブジェクトを全部なめる必要がある
- GCの負荷が一点に集中する(停止時間が長い)
実コードを見たい場合
・Ruby処理系
→読みやすいのでおすすめ
・BoehmGC
→読みやすいのでおすすめ
・BoehmGC
- カテゴリ：
- パソコン
- ガーベッジコレクタ（GC）
コメントをかく