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

Mostly Parallel GC


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

アルゴリズム

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

注意

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

利点

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

欠点

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

コメントをかく


ユーザーIDでかく場合はこちら

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

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

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

×

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

Wiki内検索

Wiki内検索

フリーエリア

編集にはIDが必要です