19.7 断片化の制御
リアルタイムコレクタは断片化を管理して制限するよう設計する必要がある
断片化が進行すると空間使用量の上限を超えてしまう可能性がある
断片化を考慮するにはアプリケーション毎の振る舞いの特徴が必要
ポインタの密度
オブジェクトの大きさの平均・分散
アプリケーションによらない断片化の管理方法
圧縮
オブジェクト分割
oblet / arraylet
外部断片化を内部断片化で置き換える
並行圧縮は難しい
コレクタがオブジェクトをミューテータと並行して動かす
同時にミューテータのアクセスが時間制約を満たすことを保証しなければならない
アプローチ
すべてのオブジェクトについて2つのコピーを保持する
例：レプリケーションコレクタ・Blelloch and Cheng
17.4 レプリケーションコピー法
19.3 仕事ベースのリアルタイムGC
2つのコピーの一貫性を維持するには何らかのロックが必要
近代的マルチプロセッサには厳密なコヒーレンシがない
レプリケーションコレクタはミューテータのルート転送を確認するための同期的終結フェーズが必要
オブジェクト毎のロックではスケールしない
ページ保護によるページ単位の同期
コンプレッサ法・Pauseless
17.7 並行圧縮
最小ミューテータ利用率が低下することがある
トラップコストが大きい
フェーズの変わり目にトラップが集中しうる
ロックフリーでないと難しい
13.4 進行性の保証
ミューテータの進行性保証
時間制約保証
並行圧縮しながらミューテータアクセスをウェイトフリーやロックフリーにするアプローチをみていく
Metronomeのインクリメンタル圧縮
ほとんどコピーしないコレクタとしての設計
外部断片化が起こることは稀であるという仮定
大きな配列をarrayletによりチャンク分割する
このチャンクが最大の割り付け単位
コピーが必要なオブジェクトの数を減らす
すべてのミューテータスレッドが止まっている間に断片化除去を行う
インクリメンタルコレクタなので
ミューテータのアクセスはBrooksの間接バリアを使って最新のコピーへ転送する
ミューテータがコピー途中のオブジェクトを見ないように
間接参照のコストの代わりに時間制約を守ることができる
Tax-and-Spendで拡張したMetronomeは圧縮しない並行コレクタ
各GCサイクルにおいて必要なページ断片化除去処理量を求める解析的フレームワーク
ミューテータがメモリ割り付け要求で待たされないために
断片化除去の仕事をアロケータのサイズクラスごとに均等に分配
各サイズクラスはページの連結リストからなる
あるサイズクラスの断片化除去アルゴリズム
1. ページの密度を、ページ中のオブジェクトの数から算出する
2. 最低密度のページ中のオブジェクトを、空きのあるページの中で最高密度のページへ移動させる
3. 空きページ数の目標を達成するまでこれを繰り返す
移動元と移動先のページが同じになれば終了する
最少数のオブジェクト移動で最多数のページを完全に埋めるアルゴリズム
最低密度のページにあったオブジェクトが高密度なページへ分散するのでキャッシュ局所性は悪くなる
高密度なページを選ぶ際に、最高密度ではなくある程度の余裕があるページを選ぶことで対処可能
オブジェクトの参照を移動先へ更新するのは次のマークフェーズでたどるまで遅らせる
次のマークフェーズの後で移動前のオブジェクトを解放する
移動先へのアクセスはBrooksの転送バリアが提供する
遅延させる利点：
反転フェーズが不要
というより、反転フェーズがマークフェーズと融合する
その間に死んだオブジェクトの更新の手間が省ける
追跡と同時の更新は局所性がよい
ユニプロセッサ上でのインクリメンタルレプリケーションGC
多くのリアルタイムアプリケーションは組み込みシステム上
組み込みシステムの多くはユニプロセッサ
ユニプロセッサにおいてミューテータ操作を不可分にするのは簡単
スケジューラの割り込みを無効化する、または
GCセーフポイント以外でのスレッド切り替えを禁止する
ただし、ミューテータのバリアがGCセーフポイントを含まない限り
このとき、次の条件を満たせばコレクタはオブジェクトを自由にコピーできる
ミューテータがコピー以降はコピーにしかアクセスしない、または
Brooksの転送バリアがto空間不変条件を守る
常にコピー元とコピー先の両方を更新する
レプリケーションコレクタで他のミューテータがまだ古いバージョンを読んでいる場合に備える
KaliberaはレプリケーションGCとBrooksバリアを使ったコピーGCを、ユニプロセッサ上で動作するJavaのリアルタイムシステムとして評価
Kaliberaでは複製の転送ポインタは複製元のオブジェクトを指す
オリジナルのBrooksでは複製自身を指す
バリアが単純で予測可能
Readは指しているオブジェクトをそのまま読む
複製かどうかを区別しない
読み出しにかかる転送を省略できる利点がある
Writeは両方のバージョンに書き込む
複製前なら転送アドレスは自分自身なので2回目の書き込みは不要
ほとんどの時間は複製前
code: アルゴリズム19-7.py
# ユニプロセッサでのレプリケーションGC
atomic Read(p, i):
return pi
atomic Write(p, i, value): # pはプライマリオブジェクトでも複製でもよい
# ここにスナップショットGCのための削除バリアのコードが入る
pi = value
r = forwardingAddress(p)
ri = value
# ここにインクリメンタルアップデートGCのための挿入バリアのコードが入る
マルチプロセッサ上の並行圧縮ではミューテータ・ミューテータ間やコレクタ・ミューテータ間の細粒度の同期が必要
ReadやWriteが不可分であるという仮定が成り立たない
19.7 Stoplessから