ガーベジコレクション入門 その1
- 1. ガーベジコレクション?? (1) Sakai Lab B4 / Rei Shimizu(@_iy4)
- 2. ガーベジコレクションの?的 ? ヒープ領域に配置されたオブジェクトの管理 1. 参照されていないオブジェクトを開放する 2. ポインタの貼り替えを?う 3. ヒープ領域の拡張 ヘッダフィールド 参照されていないオブジェクト
- 3. ルートオブジェクト ? 全てのオブジェクトの起点となるオブジェクト ? 静的領域 / スタック領域 に存在 ヘッダフィールド ヒープ領域
- 4. マークアンドスイープGC ? ?きているオブジェクトを回収するマークフェーズ 1. ルートオブジェクトから再帰的にポインタを辿る → 辿れるということは?存している 2. ?存しているオブジェクトにはマークビットを?てる ? ヒープ領域の再配置を?うスイープフェーズ 1. ヒープ領域を?査する。ここでマークビットが?っているオブジェクトは次のGCに備えてマークビット を外す 2. ?っていないオブジェクトは「フリーリスト」に繋ぐ。アロケーション時にフリーリストを辿ることで チャンクを再利?
- 8. アロケーション / チャンクの結合 ? アロケーション ? フリーリストをたどり、要求されているオブジェクトサイズより?きいサイズのチャンクを返す ? 返されたチャンクを分割し、要求されるオブジェクトサイズのみ割当を?い、残りはフリーリストに戻す ? チャンクの結合 ? スイープ時に死滅オブジェクトが連続していた場合、それらを繋げてフリーリストにつなげる
- 9. マークアンドスイープGCのデメリット ? フラグメンテーション問題 ? アロケーション時にチャンクはどんどん細分化される ? ?さすぎるチャンクは割り当てられない → フラグメンテーションの発? ? 同様の問題はファイルシステムでも?られる ? 遅い ? 参照関係にあるオブジェクトが遠くに配置される → 参照局所性の低下 ? フリーリストを線形探索するためアロケーションが遅い ? Copy On Writeとの相性が悪い ? Linuxカーネルにおいては、?プロセスに書き込みが発?するまで親プロセスとメモリを共有 ? マークビットの存在により、マーク時にかならずメモリのコピーが発?する
- 10. 複数フリーリストの利? ? 通常のフリーリストには任意のサイズのチャンクが接続されている ? サイズ毎に複数のフリーリストを容易することでチャンクの探索時間を削減 ? サイズをキーとしたハッシュマップのような感じ ? ある?きさ以上のフリーリストはまとめて扱う → メモリ空間の節約 ? ?きなサイズのアロケーションはほとんど発?しないため、これで問題ない
- 11. BiBOP法 ? ヒープ領域をサイズに従ってブロック化 ? ?つのブロックには同?のサイズのオブジェ クトしか存在しない ? サイズに従ってフリーリストを?意 → 複数フ リーリストとの組み合わせ フリーリスト (ワード?1) フリーリスト (ワード?2)
- 12. ビットマップマーキング ? ヒープ領域内のオブジェクトヘッダを書き換えるとコピーが発?する → ヒープ領 域外でマーク情報を管理 ? 外部のビットマップテーブルでマーキング情報を管理 ? オブジェクトが参照されている場合はフラグビットを?てる 10 0 001???ビットマップテーブル ヒープ領域 obj_num = 何番?のオブジェクトか? Index = obj_num / WORD_SIZE offset = obj_num / WORD_SIZE 実際は?次元配列のようになっており、indexとoffsetでアクセス
- 14. 参照カウント式GC ? 各オブジェクトは参照カウンターを持つ ? 参照カウンターは「そのオブジェクトを指し?すポインタの数」を?している ? 参照カウンターが0になった瞬間、死んだオブジェクトとしてフリーリスト?り ? 死んだオブジェクトの?オブジェクトも全て死んだオブジェクトとなる
- 15. ヒープ領域 1 1 1 1 1
- 16. ヒープ領域 0 1 1 1 1 1
- 17. ヒープ領域 0 1 1 1 1 1
- 18. ヒープ領域 0 1 1 1 1 1 フリーリスト
- 19. 参照カウント式GCのデメリット ? ポインタの更新頻度が増えるとカウンタの増減処理も増える → 無視できないオー バーヘッド、特にルートのポインタは頻繁に更新される ? 最悪ケースでは、ヒープ上の全てのオブジェクトから参照される → カウンター ビットを多めに確保する必要がある ? 循環参照が回収出来ない 1 1 N 循環参照
- 20. 遅延参照カウント法 ? ルートからの参照オブジェクトが変化しても、カウンターを即座にインクリメン トしない ? デクリメント時に、参照カウンターが0になったオブジェクトをゼロカウントテー ブルに繋ぐ ? オブジェクトの追加時に、フリーリストからチャンクが取得出来なかった場合は ゼロカウントテーブルをスキャンしてフリーリストを拡張 → ここが遅延要素 ? スキャン時にルートから参照されているオブジェクトのインクリメントを?う
- 21. ヒープ領域 1 1 1 1 1
- 26. Sticky 参照カウント法 ? カウンタービットを多めに確保する必要がある問題を解決する ? ビット数を制限、オーバーフローしても無視 ? 多くのオブジェクトは?成された直後に死ぬと?われるので、オーバーフローす るほど参照されるオブジェクトが?まれることは稀 ? 少量の死滅オブジェクトの残留は許容 ? マークアンドスイープGCとのあわせ技
- 27. 参考?献 ? 中村成洋, 相川光, ガーベジコレクションのアルゴリズムと実装, 秀和システム, p12-54