17.7 並行圧縮
圧縮とマークフェーズは切り離されている状況を考える
コピーGCに比べ、オブジェクトを再配置する順序に対する自由度が高まる
マーキングと圧縮のためのコピーを切り離し、圧縮をミューテータスレッドと並行実行
コンプレッサ法の動作
圧縮前に先頭オブジェクト表を計算
to 空間のページを、そのページに移動される最初の from 空間オブジェクトに対応付ける表
図3.3 を参照するとよい
https://gyazo.com/10ed4e99982a837365c1097d36e89a27
並列圧縮スレッドがまだ対応付けられていない to 空間仮想ページを取り合う
獲得したページを物理ページにマップ
from 空間ページからコピーしてくる
コピー内のポインタフィールドを to 空間を指すように書き換える
仮想記憶ページ保護プリミティブをリードバリアとして用いることで、並列圧縮を実現
圧縮とポインタ転送の両方で用いる
読み出し・書き出しの両方で保護（ここでは物理ページにマップしない）
先頭オブジェクト表の計算と to 空間の保護は、ミューテータの from 空間の操作と並行して発生
コンプレッサは全ミューテータを停止させて、ルートを to 空間アドレスを指すように反転し、再開させる
この段階ではオブジェクトは to 空間にコピーされていない
ミューテータが保護された to 空間のページにアクセスするとトラップ
ページをマップしてオブジェクトをコピーする
ミューテータがインクリメンタルな圧縮スレッドのように振る舞う
圧縮スレッドがページにアクセスする時、ダブルマッピングによりミューテータからページを保護
今回は以下の2つのページを用いる
自然な（保護したままの）to空間仮想ページ
ここでの保護は、ページを非アクセスにするという意味での保護
保護されていない、圧縮スレッド専用のプライベートなページ
ここでの圧縮スレッドはこのページにはじめて到達した元ミューテータ
圧縮が完了すれば保護が解除され、プライベートなマッピングも破棄
以下図はコンプレッサ法の圧縮作業を表したもの（上を見なくてもこれだけで十分かも）
濃い灰色：Live ページ。ほとんどが生きたオブジェクトで占められる。
薄い灰色：没収予定のページ。ほとんどが死んだオブジェクトであり、圧縮の有力候補。
破線：空きページ
破線（内側にさらに破線があるもの）：そのうち生きているオブジェクトがコピーされるページ。
斜線：マップされていないページ (Dead)。このページを指すオブジェクトがなくなれば回収される。
https://gyazo.com/5c1c14dbc9f65a8f4c4c0d99319d9196
コンプレッサ法の性能
仮想記憶のページマッピングプリミティブやページ保護プリミティブのコストに大きく依存
これらの処理はかなり手間がかかる
これらの操作を可能な限り一括してやるのが理想
コンプレッサは実際には to 空間全体に対し GC 開始時にページ保護とダブルマッピングを行う
コンプレッサはトラップのたびに8ページの仮想ページを移動する
コンプレッサ法の欠点
ミューテータがトラップを引き起こすと、オブジェクトのコピーやポインタの転送作業で停止時間が増大
後述する Pauseless コレクタはこれを緩和する
Pauseless
概要
移動前のオブジェクトが入っている from 空間のページを保護
移動後のオブジェクトや古くなったポインタの入っている to 空間ページは保護しない
コンプレッサと保護しているところが反対
コンプレッサ法にくらべ、必要最小限の保護で済む
ページを一括して保護せず、インクリメンタルに保護できる
リードバリアを用い、from 空間の古くなった参照をミューテータが使う前に横取りする
コンプレッサのようにミューテータがページ全体を修正するためにブロックするのを防ぐ
ハードウェアとオペレーティングシステムのサポート
Azul 社の独自ハードウェア
高速なユーザーモードトラップハンドラ
TLB（ハードウェアトランスレーションルックアサイドバッファ）
ユーザーモードとカーネルモードの他に GC モード特権レベルが追加されたもの
Pauseless の基本処理単位は TLB がサポートする大きな (1～2MB）のページ
高速で協調的な実行権切り替えメカニズム
GCセーフポイントに対応するもの
ハードウェアリードバリア
Pauseless のリードバリア
最初にロードを実行し、その後バリア処理を行う
バリア処理
ロードした値（アドレス）を TLB に通す
このアドレスが GC で保護されているなら、高速なユーザーモード GC トラップハンドラを起動
メモリアクセスが少ない
ロードした値をすぐ利用できる
Brooksではオブジェクトの取得のたびに間接参照1つ分のペナルティがある
オブジェクトヘッダ内の転送ワードが不要
キャッシュ容量の消費が低減
Pauseless は 64 ビットのアドレス空間から1ビットを盗んで用いる
このビットは Not-Marked-Through (NMT) ビットと呼ぶ
並行マーキングフェーズの間、この参照をコレクタがすでに操作したかどうかの判定に使用
マークビットと呼べばよくない？
ハードウェアはロードやストア時にこのビットを無視する
Azul ハードウェアは NMT ビットの望ましい値（正しい値）を保持している
参照内のビットの値が異なっていれば NMT トラップハンドラを起動する
code:python
# Algorithm 17-8: Pauseless のリードバリア
def Read(src, i):
if protected(ref):
return ref
def GCtrap(oldRef, addr):
newRef = forward(oldRef) # 必要に応じて転送/コピー
mark(newRef) # 必要ならマーク
# このマークはNMTビットを設定すること
while True: # CAS が理由なく失敗したときだけ繰り返す
# CAS はメモリモデルによっては理由なく失敗する可能性がある
if oldRef = CompareAndSwap(addr, oldRef, newRef):
return newRef # CAS に成功したら終了
if oldRef != *addr:
# srci == ? (他のミューテータが Write で書き込んだ値 or 他スレッドが Read で newRef にした) return newRef
def CompareAndSwap(x, old, new):
atomic
curr ← *x
if curr = old
*x ← new
return curr
標準的なハードウェアにおける Pauseless
リードバリアをエミュレートする必要がある（何らかの代償を伴う）
GC 保護チェックのエミュレート
通常のページ保護を使用
リードバリアのエミュレート
余分なロード命令を発行したり、
明示的にソフトウェアで補助テーブルをチェックしてトラップする必要があるか確認
多分 forward の部分 (Azul だとハードウェアレベルでいい感じにできるんだと思われる)
NMT チェックのエミュレート
ハードウェアレベルの NMT ビットが無いときの話
メモリを多重にマッピングし、NMT ビットの値を反映してページ保護を変更する
null 参照については明示的にフィルタリングが必要になる
NMT ビットは色々工夫すればソフトウェアレベルで取り去ることも可能らしい
コンパイラや OS の協力があれば
Pauseless GC のフェーズ
以下の3つのフェーズに分かれている。
それぞれのフェーズは完全に並列かつ並行動作が可能である。
この性質が各フェーズの動作を理解するのに大変役立つ
すごい
mark
relocate
remap
詳細は後述
markとremapは生きている全てのオブジェクトをなめるので、Pauselessではまとめられる。
前回のフェーズのremapと同時に次のmarkをすればよい。
Pauselessの利点
フェーズ終了時に慌てることがない。 ← ？
どのフェーズも並行動作ができるので、フェーズの終わりのようなものを考えて間にあわないなどが発生したりすることがないということか。
3つのフェーズでタイミングをあわせて何かするとかそういうことがないから、どこかが遅れてるとかが問題になりづらい？
relocateはずっと継続的に動作できて、ちょこちょこ解放してくれる。
ミューテータスレッドが多くておいつかなくなってきても、コレクタスレッドを増やせば対応可能。
マーキングが1パスで終わる。
ミューテータがマーク要求を割り込みで送ってくる みたいなことが発生せず、markは自分のタイミングで全生存オブジェクトを舐めるだけで済む。
再度触って色が戻る などが発生しない。
「自己治癒」作用
リードトラップが発生したら、その参照を引っ越し先へと更新するので、踏んだ人は以降発生しなくなる。
高々参照の数程度のトラップしか発生しない。
フェーズの移り変りの最初にたくさんのトラップが発生するが、それが過ぎればもうミューテータの停止は無い。
散発的にフェーズの最初に止めるだけである。
全スレッドを同時に止めるようなストップザワールドは無い。
mark
各オブジェクトのNMTビットの設定と寿命管理用のマークビットの設定を行う
NMTビットはマーカスレッドは用いず、ミューテータだけが用いる
NMT
期待されるNMTビットの値とオブジェクトのNMTビットが一致するとき、未だミューテータが到達していないことを表す
期待されるNMTビットの値はグローバルな状態で、各markフェーズごとに反転されることで、全オブジェクトのNMTビットのリセットを表現
NMTトラップハンドラ(GCtrap)によって、ミューテータはMarked-Throughなオブジェクトしか触ることができない
このトラップによって、ミューテータが触れたオブジェクトはすべてto空間へ転送済みであることが保証される
ミューテータの書き換えによってオブジェクトをダングリングさせることはできない
GCtrap中のforwardの必要に応じて転送/コピーというのは、
relocateによる引越しが行なわれていた場合には、引越し先のアドレスを得るだけ
そういうわけではない時(relocateが特に生きているとは見なしていなかったが生きている時)には、ここで実際にコピーまでしてからその引越し先のアドレスを返す。
寿命管理
2ビット使うことで世代別GCができるが、本質的には1ビットでも十分だと思う
無印Pauselessではなく世代別のC4のアルゴリズムになっている？
このビットはポインタへの埋め込みではなく、ヘッダやビットマップなどへ保存するのが自然そう
そうでないと、せっかくNMTビットにも関わらずポインタの等値比較できるようになっている意味がない
このビットが立っているからといって、既にミューテータがオブジェクトの参照をなくしていることもあるし、逆に立っていないがミューテータが参照を作った可能性もある。
参照がなくなっていた場合は、次のmarkのフェーズ後に本当になくなっていることが期待されているので、その後死ぬ。
できていた場合は、GCtrapの中のforwardで、転送する。
各ミューテータスレッドのルート集合はチェックポイントに達したタイミングでそれぞれマークしてもらう
ミューテータスレッドがチェックポイントで停止している間にマーカースレッドがマークする
マーカースレッドはミューテータとは並行に、このルート集合から辿っていき、到達可能なオブジェクトにマークビットを立てていく。
これを使ってreloacateが「疎なページ」を発見する。
終了判定
基本的にはシングルスレッドの場合と同様にreachableなオブジェクトを探し尽くすまで
未マークの参照をロードしたが、まだリードバリアの実行が終わっていないミューテータとの競合を考慮する必要がある
リードバリアがGCセーフポイントをまたぐことはないので、全ミューテータがセーフポイントをまたいでも新規の未マークの参照が報告されなければmarkフェーズを終了しても良い
relocate
マークビットの情報を用いて、疎なページを探し、再配置して圧縮し、物理メモリを解放する。
発見した疎なページへのアクセスにバリアを設けた後、新たなページへとオブジェクトをコピーして、補助領域に引越し先を記録する。
ミューテータスレッドが保護されたページを読んだ時、GCtrapにより、参照を引越し先を指すように更新する。
ページが空になった時、その瞬間にそのページに割り当てられた物理メモリを開放する。仮想メモリの解放は、remapがやる。
remap
ヒープ内に保持されている、生きているオブジェクトを指しているポインタを引っ越し先へと更新する。
ミューテータがトラップした時と同様の処理。
これによりrelocateフェーズによって保護されたページへのポインタが全部消えるはずなので、仮想メモリも解放できるようになるので、する。
markフェーズにマークだけでなくて引っ越しもさせて、最後に仮想メモリを解放すればremapをmarkに統合できる
が、並列にmarkとremapで2度走査することもでき、ここではそのつもりのアルゴリズムが書いてある
https://gyazo.com/d481b3ab1b3e5e58d09fc6d4c02b71e0
ファイナライゼーションと弱参照
Javaの弱参照(12.1参照)では、参照を無効化するコレクタと、参照を強くするミューテータの間での競合が発生しうる。 Pauselessではリードバリアがあるので、弱参照をnullにする処理をGCtrap内でCASでするようにすれば、一貫性を保ったどちらかの状態になるだけで壊れることはない。
オペレーティングシステムの拡張
Pauselessでは、仮想メモリのマッピングをアグレッシブかつ継続的にするので、OSの協調無しには性能が出ない。
各ページは一生のうちに、割り付けられてから1度リマップ(relocateフェーズ)され、そして1回アンマップ(remapフェーズ)される。
1度しかリマップしないということは、ページアウトのタイミングでスワップにコピーせずにそのまま内容を失うということ
このリマップの速度が支配的になる。
普通のOSでは以下のような悪い点がある。
リマップにTLBの無効化が生じるので、アクティブなスレッド数が多いとコストが高い。 TLBの無効化にはCPUの全コアに対しての割り込みが必要なので、このコストはコア数に応じて増加
通常4KBのページしかリマップできない(これは小さい)。
リマップ操作はシングルスレッド化される。
これどういうこと？ 複数の人が同時に別の場所をリマップしようとしても結局ロックの取り合いになるので並行化できないということか？
TLB無効化のコストを減らすために、TLBを無効化しないリマップと無効化するリマップを導入
おそらくTLBを無効化しないリマップは、対象のページをキューかなにかにためるだけで、実際のリマップはしない
無効化するリマップのタイミングでTLBを無効化しながらキューにたまったページをまとめてリマップする
更に追加のチューニング
大きな(2MB)ページマッピング
同一プロセス内での複数の(無効化しない)リマップの並行実行
TLBを無効化しないから並行実行できるのかも
これらを改善すると3桁程度高速化でき、スレッド数に対して線形程度のスケールができるようになった。
まとめ
Pauselessは大規模なマルチプロセッサ用の完全な並行並列コレクタとして設計された。
ストップザワールドが無く、死んだオブジェクトはいつでもrelocateが回収する。
ミューテータが割付けできるようにするために、コレクタが急いでしないといけないフェーズというものがない。
フェーズの変わり目にトラップの嵐でミューテータの動作率が下がることがあるが、自己治癒性によりすぐにおさまる。