GC/extend/Partial Mark and Sweep
最終更新：
author_nari 2010年10月25日(月) 12:57:24履歴
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にすることが出来る。
以下擬似コード
4.scan
control_set内でカウントが0のもののみwhite、その他はblackに塗り分け、
カウントを減らしていたgrayオブジェクトに+1をし、カウントを元に戻す。
また、control_setからみえるObjectが1以上であった場合、そのObjectと子供については
whiteにする事はしない。
（まだ参照されている為）
5.collect_white
whiteのObjectを回収して、循環参照が解消される。
その後、control_setからpopされる。
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される。
利点
- 循環参照が解決される
- MarkandSweepを部分的に行え、時間の短縮になる。
欠点
- 不明
実コードを見たい場合
- PHP5.3以降
- Python
- Firefox3
- カテゴリ：
- パソコン
- ガーベッジコレクタ（GC）
コメントをかく