GCアルゴリズム詳細解説

Hans J. Boehmらによって考案された、Mark&Sweepを基本とするアルゴリズムである。
ヒープ領域をページ単位で管理し、ハードウェアのメモリ管理機能を利用する。

1. GC開始時にルートから直接参照できるセルに印をつける。
2. 1が終わると、ヒープ全体を書込み禁止にしておく。
3. マーク操作をミューテータの実行と交互に少しずつ進めていく。ミューテータにより、セルへの書き込みが行われた場合にはページ保護違反が起きる。これをキャッチし、書き込みが起こったページを記録しておく。また、そのページには書き込みができるようにしておく。
4. マーク操作が終わると、書き込みがあったページのみをスキャンし、再度マーク操作を行う(これは、ミューテータの操作とは並行できない)。
5. スイープ操作を行う。ミューテータの操作と交互に行うため、一度にn(定数)ページずつスイープする。

オブジェクトの内部にマークビットを持たせると、GCのマーク操作により、ページ保護違反が起きる。
そのため、ヒープ領域の外にマーク用のビットマップを作るのがよい。

1. 一度書き込みのあったページは次回以降バリアなしで書き込みができる(書き込みの局所性を利用)。

1. ページを保護する操作は、ハードウェアに依存する。
2. ミューテータの実行と平行できない部分がある。つまり、完全なリアルタイム性は保証されない。