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

TreadmillGC(Barker 1992)

Copyingに似たnon-movingなインクリメンタルGC

アルゴリズム

このアルゴリズムは双方向リンクを利用し,Copyingと似た動きをする.
つまりMark&Sweepは行わない.
Copyingのようにルートからたどったオブジェクトを移動させるアルゴリズムである.

移動の際,単純なChenyCopyingGCだとオブジェクトを物理的に移動するが,このアルゴリズムの場合,双方向リンクを付け替える事で移動とする.

このアルゴリズムではGCの際に4つのセグメントに分かれる.
  • Free 解放済み,もしくは未使用のオブジェクトが所属する空間
  • New スキャン中に割り当てたオブジェクトが所属する空間
  • To Fromから生きているオブジェクトの移動する先の空間
  • From スキャン対象のオブジェクトが所属する空間

またその区別の為,4つのポインタをもつ.
  • top To空間との境目に位置
  • bottom Free空間との境目に位置
  • scan スキャン対象のオブジェクトを指す
  • free 次のオブジェクト割り当て対象を指す

初期状態は以下の様な位置関係にある.
  • scanとfreeは隣同士に位置
  • topとbottomとscanは隣同士に位置

freeからオブジェクトを割り当てると,topとbottomの間に位置づける.
そうすると自然とFrom空間は肥大化し,Freeは少なくなる.

Freeが残り半分程になるとGCを開始する.手順は以下である.
  1. ルートを探索し,見つかったオブジェクトをscanとtopの間に移動する.ここにTo空間が生まれる.
  2. ルートを探索し終えると,scanポインタをtop方向にずらし,オブジェクトをスキャンする.
  3. 見つかったオブジェクトは同様にscanの右に移動する.
  4. 一つの木を探索し終えると,いったんGCを中断する.
  5. オブジェクトの割り当て要求がある場合,freeをbottom方向にずらす.この際free-scan間はNew空間になる.
  6. またGCを再開.
  7. これを繰り返しscanがtopに到達すると,bottomをtop方向にオブジェクトを解放しながら動かす.
  8. bottomがtopに到達すると,From空間がまるまるFree空間に変わる.
  9. その後,scanをfreeの横に,topをscanの横に移動する事でTo空間がFrom空間に変わる.
  10. GC終了.

私的にはしくみを知ったときに一番感銘を受けたアルゴリズム.
美しいですよね.

利点

  1. インクリメンタル
  2. non-movingなCopyingGCのようなものを作成できる

欠点

  1. CopyingGCとは違いコンパクションされない。フラグメンテーションが発生する。

実コードを見たい場合


  1. Io(id:keisukefukudaさんより)

このページへのコメント

欠点といいますか、
Copying GC と大きく異なるのは compaction が無い点ですよね。

Posted by 通りすがりのものです 2009年06月03日(水) 15:06:33

プログラミング言語Ioが、Generational Treadmill GCを採用しているようです。

Posted by id:keisukefukuda 2009年03月03日(火) 18:31:54

コメントをかく


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

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

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

×

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

Wiki内検索

Wiki内検索

フリーエリア

編集にはIDが必要です