Loading article…
チェイニーのアルゴリズムは、1970 年のACM論文で CJ チェイニーによって初めて説明された、コンピュータ ソフトウェア システムにおけるガベージ コレクションを追跡する停止およびコピー方式です。この方式では、ヒープは2 つの均等な半分に分割され、一度に 1 つだけが使用されます。ガベージ コレクションは、ライブ オブジェクトを一方の半空間 (from 空間) からもう一方の半空間 (to 空間) にコピーすることによって実行され、これが新しいヒープになります。その後、古いヒープ全体が 1 つにまとめて破棄されます。これは、以前の停止およびコピー手法の改良版です。[引用が必要]
Cheney のアルゴリズムは、次のようにアイテムを回収します。
- スタック上のオブジェクト参照。スタック上のオブジェクト参照がチェックされます。from-space 内のオブジェクトを指す各オブジェクト参照に対して、次の 2 つのアクションのいずれかが実行されます。
- オブジェクトがまだ to スペースに移動されていない場合は、to スペースに同一のコピーを作成し、from スペースのバージョンを to スペースのコピーへの転送ポインターに置き換えることによってこれが実行されます。次に、to スペースの新しいバージョンを参照するようにオブジェクト参照を更新します。
- オブジェクトがすでに to スペースに移動されている場合は、from スペースの転送ポインターからの参照を更新するだけです。
- to スペース内のオブジェクト。ガベージ コレクターは、to スペースに移行されたオブジェクト内のすべてのオブジェクト参照を調べ、参照されたオブジェクトに対して上記の 2 つのアクションのいずれかを実行します。
すべての to-space 参照が検査され更新されると、ガベージ コレクションが完了します。
このアルゴリズムではスタックは不要で、from-space と to-space の外側には 2 つのポインターのみが必要です。to-space の空き領域の先頭へのポインターと、to-space で調べる必要がある次のワードへのポインターです。2 つのポインター間のデータは、アルゴリズムに残っている作業を表します (これらのオブジェクトは、3 色用語では 灰色で表示されます。後述します)。
転送ポインタ (「ブロークン ハート」と呼ばれることもあります) は、ガベージ コレクション プロセス中にのみ使用されます。to スペースにすでに存在するオブジェクト (つまり、from スペースに転送ポインタがあるオブジェクト) への参照が見つかった場合、そのポインタを転送ポインタと一致するように更新するだけで、参照をすばやく更新できます。
この戦略は、すべてのライブ参照を使い果たし、次に参照オブジェクト内のすべての参照を使い果たすというものであるため、これは幅優先リストコピー ガベージ コレクション スキームとして知られています。
サンプルアルゴリズム
初期化() =
トスペース = N/2
スペースから = 0
allocPtr = スペースから
scanPtr = 何でも -- 収集時にのみ使用される
割り当てる(n) =
allocPtr + n > fromspace + N/2の場合
集める（）
終了
allocPtr + n > fromspace + N/2の場合
失敗「メモリ不足」
終了
o = アロケートポインタ
アロケートPtr = アロケートPtr + n
戻る
収集() =
swap(fromspace, tospace)
allocPtr = スペースから
scanPtr = スペースから
-- 持っているすべてのルートをスキャンします
スタック内の各ルート、または他の場所
ルート = コピー(ルート)
終了
-- to スペース内のオブジェクトをスキャンします (このループによって追加されたオブジェクトを含む)
scanPtr < allocPtrの場合
ForEach は o から r を参照します (scanPtr によってポイントされます)
r = コピー(r)
終了
scanPtr = scanPtr + o.size() -- to スペース内の次のオブジェクト（存在する場合）を指します。
終了中
コピー(o) =
oに転送先アドレスがない場合
o' = アロケートポインタ
allocPtr = allocPtr + サイズ(o)
oの内容をo'にコピーする
転送アドレス(o) = o'
終了
転送先アドレスを返す(o)
セミスペース
チェイニー氏は、1年前にRRフェニチェル氏とJCヨチェルソン氏によって公開された 半空間ガベージコレクターに基づいて研究を進めました。
三色抽象化と同等
Cheney のアルゴリズムは、 3 色マーキングガベージ コレクターの例です。グレー セットの最初のメンバーはスタック自体です。スタック上で参照されるオブジェクトは、ブラック セットとグレー セットのメンバーを含む to スペースにコピーされます。
アルゴリズムは、白いオブジェクト (転送ポインタのない from スペース内のオブジェクトに相当) を to スペースにコピーしてグレー セットに移動します。to スペース領域上のスキャン ポインタとフリー スペース ポインタの間にあるオブジェクトは、まだスキャンされていないグレー セットのメンバーです。スキャン ポインタの下にあるオブジェクトは、黒のセットに属します。オブジェクトは、スキャン ポインタをその上に移動するだけで黒のセットに移動されます。
スキャン ポインターが空き領域ポインターに到達すると、グレー セットは空になり、アルゴリズムは終了します。
参考文献
- Cheney, CJ (1970 年 11 月)。「非再帰リスト圧縮アルゴリズム」。Communications of the ACM。13 ( 11 ): 677–678。doi : 10.1145/362790.362798。S2CID 36538112 。
- Fenichel, RR; Yochelson, Jerome C. (1969). 「仮想メモリ コンピュータ システム用の LISP ガベージ コレクター」Communications of the ACM . 12 (11): 611–612. doi : 10.1145/363269.363280 . S2CID 36616954.
- Byers, Rick (2007). 「ガベージコレクションアルゴリズム」(PDF) .ガベージコレクションアルゴリズム. 12 (11): 3–4.
外部リンク
- YouTubeの「Android ランタイムの理解 (Google I/O'19)」- Android は、セミスペース ガベージ コレクターのバリアントを使用します。