日本語の資料がすくないGCアルゴリズムについて詳細に解説します

Lisp2 -Mark&Compact-

先頭にずらす

アルゴリズム

ヒープの先頭から詰めていく、もっとも素朴なアルゴリズム

1.マーク
rootを走査し、生きているオブジェクトに印を付ける。

2.移動先の計算
上図のようにliveポインタでオブジェクトを見つけ、オブジェクト内に持っているforwarding pointerに移動先を書き込んでおく。
その後、freeポインタはオブジェクトのサイズの分だけ移動する。
liveポインタがHeapの最後に到達したら終了。

3.ポインタ更新
オブジェクトを参照しているすべてのポインタをオブジェクト内にもっているforwarding pointerで書き換る。

4.移動
実際にforwarding pointerの通りに移動して、Compactionを終了とする。

なぜ後で移動するのか?最初に移動すればいいのにと考えたが、
オブジェクトを参照しているポインタとforward_pointerを結びつけるものが、
その実際のオブジェクトしかない為、移動する事ができない。

利点

  1. 色々なサイズのオブジェクトを利用できる
  2. オブジェクトの順序も保たれる

欠点

  1. forwarding pointerの余分な領域がオブジェクトに必要になる
  2. TwoFingerは「マーク、移動、ポインタ更新」の3パスだが、このアルゴリズムでは「マーク,移動先の計算、ポインタ更新、移動」の4パスが必要であり、遅い

実コードを見たい場合

 ・不明

このページへのコメント

筝荅宴障荐篋с 若若若若 http://www.fetang.com/

Posted by 若若若若 2013年08月01日(木) 06:54:07

コメントをかく


画像に記載されている文字を下のフォームに入力してください。

「http://」を含む投稿は禁止されています。

利用規約をご確認のうえご記入下さい

×

この広告は60日間更新がないwikiに表示されております。

Wiki内検索

Wiki内検索

フリーエリア

編集にはIDが必要です