Loading article…
チェイニーのアルゴリズムは、1970年にCJチェイニーがACMの論文で初めて発表したもので、コンピュータソフトウェアシステムのガベージコレクションを追跡するためのストップアンドコピー方式です。この方式では、ヒープは2つの等しい半分に分割され、一度に1つだけが使用されます。ガベージコレクションは、一方の半空間（from-space）からもう一方の半空間（to-space）へ生存オブジェクトをコピーすることで実行され、コピーされた半空間が新しいヒープとなります。その後、古いヒープ全体が一括して破棄されます。これは、従来のストップアンドコピー方式を改良したものです。
チェイニーのアルゴリズムは、以下のようにアイテムを回収します。
すべてのto-space参照が検査され、更新されると、ガベージコレクションが完了します。
このアルゴリズムはスタックを必要とせず、from-spaceとto-spaceの外側に2つのポインタのみを必要とします。1つはto-space内の空きスペースの先頭へのポインタ、もう1つはto-space内で検査する必要のある次のワードへのポインタです。2つのポインタ間のデータは、アルゴリズムがまだ実行すべき作業を表します（これらのオブジェクトは、後述する3色表記では灰色で表されます）。
転送ポインタ（「壊れたハート」と呼ばれることもあります）は、ガベージコレクション処理中にのみ使用されます。既にto-space（つまりfrom-spaceに転送ポインタを持つ）にあるオブジェクトへの参照が見つかった場合、そのポインタを転送ポインタと一致するように更新するだけで、参照を迅速に更新できます。
この戦略は、すべての有効な参照を使い果たし、次に参照されているオブジェクト内のすべての参照を使い果たすことであるため、幅優先リストコピーガベージコレクション方式として知られています。
チェイニーは、その研究を、1年前にRRフェニケルとJCヨケルソンによって発表された半空間ゴミ収集装置に基づいて行った。
チェイニーのアルゴリズムは、 3色マーキング方式のガベージコレクタの一例です。グレーセットの最初の要素はスタックそのものです。スタック上で参照されるオブジェクトは、黒色セットとグレーセットの要素を含むto-spaceにコピーされます。
このアルゴリズムは、白いオブジェクト（転送ポインタのないfrom-space内のオブジェクトに相当）をto-spaceにコピーすることで、それらをグレーセットに移動します。to-space領域上のスキャンポインタとフリースペースポインタの間にあるオブジェクトは、まだスキャンされていないグレーセットのメンバーです。スキャンポインタの下にあるオブジェクトは、ブラックセットに属します。オブジェクトは、スキャンポインタをその上に移動するだけでブラックセットに移動されます。
走査ポインタが空き領域ポインタに到達すると、グレーセットは空になり、アルゴリズムは終了します。