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

スナップショット型GC(snapshot-at-the-beginning:SATB)


開始時の写真を元にゴミ掃除

アルゴリズム

このアルゴリズムはMark&Sweepを基本に考えられる。
GC開始時にルートから参照できるセルに印をつける。
実はここまではIncrementalGCの主な実装と同じで、
ミュテータのセル操作によるものは一律印付けしてしまう。(上図参照)
想定されるは以下の2ケース
  1. マーク中に新規割り当てされたセル
  2. マーク中に書き換えられた黒→白のセル
2に関しては書き換えられたセルの枝にあるセルも全て印付けを行う。
1に関しては新規割り当てのセルの為、枝のセルは存在し得ない。

この単純な操作により、GC開始時にゴミであったセルが削除される。
GCの開始時の写真を撮って、その時のゴミを回収する事から
「スナップショット型」「スナップショット方式」と呼ばれる。

このアルゴリズムはGCのIncrementalGC、PararellGC、ConcurrentGCを行う為のものであり、
現在のGCの並列化、並行化において一番性能のいいアルゴリズムと思われる。

発案者はCommonLisp入門などの著者 湯淺太一教授

利点

  1. 単純なアルゴリズムの為、実装が簡単。
  2. 漸次化、並列化、並行化を可能にする。

欠点

  1. GC開始時のゴミしか回収しない為、ゴミの取りこぼしが多くなり、飢餓状態に陥りやすい。
  2. ルートマークだけは処理分割(並列化など)できない。
2はスタックを処理分割する「リターンバリア」という手法が検討されている。

実コードを見たい場合

 ・もしかしたらJVM

コメントをかく


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

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

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

×

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

Wiki内検索

Wiki内検索

フリーエリア

編集にはIDが必要です