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

Partial Mark and Sweep -Cycle Collection-

部分的なMarkandSweep

アルゴリズム

まず、CycleCollectionとは
Reference Counting GC(RC)で発生する循環参照を改善する為のGCである。
つまりRCの改良版。

1.インクリメント
インクリメントでは+1すると共にObjectのColorをblackにする

2.デクリメント
図のようにデクリメントでは-1すると共に、control_setにポインタをプッシュする。
その際、ObjectColorをpurpleにし、すでにpurpleであるものはcontrol_setには追加しない。

3.Mark Gray
control_setがいっぱいになったタイミングで起動し、図の様にcontrol_setにあるObjectとその子供をGrayにする。
それに伴って子供Objectのみ-1を行い、循環参照だった場合は全て0にすることが出来る。
以下擬似コード
MarkGray(S)
  if (color(S) != gray)
    color(S) = gray
    for C in S.child
      count(C) = count(C) - 1
      MarkGray(C)

4.scan
control_set内でカウントが0のもののみwhite、その他はblackに塗り分け、
カウントを減らしていたgrayオブジェクトに+1をし、カウントを元に戻す。
また、control_setからみえるObjectが1以上であった場合、そのObjectと子供については
whiteにする事はしない。
(まだ参照されている為)

5.collect_white
whiteのObjectを回収して、循環参照が解消される。
その後、control_setからpopされる。

利点

  1. 循環参照が解決される
  2. MarkandSweepを部分的に行え、時間の短縮になる。

欠点

  1. 不明

実コードを見たい場合

  • PHP5.3以降
  • Python
  • Firefox3

コメントをかく


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

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

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

×

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

Wiki内検索

Wiki内検索

フリーエリア

編集にはIDが必要です