17.4 レプリケーションコピー法
Brooks の間接バリアは時間的および空間的ペナルティを伴う
復習: Brooks の間接バリアとは
すべてのオブジェクトに転送先を表すポインタを持たせる
From空間もしくはTo空間のどちらかを指すようにする
オブジェクトへのアクセス時には転送先ポインタを通じて行う
Brooks の間接バリアの欠点
ヒープアクセスのたびにオーバーヘッドがある
オブジェクトのヘッダに1ワードのポインタが付け加わる
Brooks の間接バリアの利点
Bakerのto空間不変条件が保たれる
復習: Bakerのto空間不変条件とは「黒いミューテータは定義よりto 空間へのポインタしか保持しない」
復習: 黒いミューテータとは「コレクタが走査済みで、ルートを追跡済みであり、再走査を必要としないもの」
コレクタが操作したときにリードバリアがオブジェクトをto空間に転送する
これによりto空間不変条件が保たれる
to空間にコピーが存在するときは常にそちらがアクセスされる
ヒープの更新が決して失われない
レプリケーションコピーGC
レプリケーションコピーGCはこの要件を緩和して、コレクタがfrom空間からto空間にオブジェクトをコピーしている間にも、ミューテータがfrom空間のオブジェクトに書き込めるようにした
この要件: バリアによる排他制御
ライトバリアがfrom 空間オブジェクトへのすべての更新をログに残し、to 空間の複製に適用しなければいけない差分を記録する
レプリケーションコピーGCの終了条件
ミューテーションログが空で、ミューテータのルートがすべて走査済みで、to空間のすべてのオブジェクトが走査済みであること
これが満たされるとfrom空間とto空間を反転する
並行レプリケーションコピーGC
並行レプリケーションコピーGCでは、ミューテータとコレクタの間でミューテーションログを介する同期と、ミューテータのルートを更新する際の同期が必要となる
ミューテーションログを介する同期
おそらくログはキューとして実装される
キューが空のときは同期する必要がある
Q: この２つの同期だけだとGCが永遠に終了しないことがありそう
永遠にミューテーションログが空にならないケースがあるのではないか?
17.5でロックフリーでないと指摘されている
13.4: 並行アルゴリズムがロックフリー（lock-free）であるとは、いずれかのスレッドが有限のステップ数で処理を終了し、その処理を無限回繰り返せること
並行レプリケーションコピー方式の利点
停止時間が短い
flipとルートの書き換え
並行レプリケーションコピー方式の欠点
全書き込みをログする必要がある
Next: 17.5 マルチバージョンコピー法