19.3 仕事ベースのリアルタイムGC
Bakerのインクリメンタル二分空間コピーGC
リアルタイムGCをめざした最も初期の試みのうちの1つ。
割り付けるオブジェクトは全てLispのconsセルであることから大きさが同じであるという仮定を用いて、行なうべき仕事が各サイクルで時間的/空間的に有界であることを示した。
Belloch and Cheng
Bakerの解析をマルチプロセッサGCに対して拡張して、上界を示した。
最小ミューテータ利用率を用いて定式化した最初の研究である。
が、仕事ベースであるため、停止時間にばらつきがあったり、ミューテータのリアルタイム保証を得ることが難しかったりする。
結局このアルゴリズムじゃダメだが、停止時間/空間の制約に関する知見を与えるので設計を見ていくことにするらしい。
ダメなアルゴリズムなのでさらっと行きたい。
マシンモデル
理想化されたマシンについて2人は解析を与えたので、現実に実装する時には理想と現実のズレで苦しむことになるらしい。
「典型的な共有メモリ型対称マルチプロセッサ」
TestAndSetとFetchAndAddを持つことを仮定されている。
FetchAndAddを公平な形で実装することが、全プロセッサの処理を進行させる上では重要である。 ← ？？？
逐次的コンシステンシを持つことも仮定されている。
これはそこそこ強力な仮定。
現実に実装する時に困難となりうる。
メモリはポインタ1つを格納できるサイズの連続の領域であり、アドレスとして[0...M+1]のレンジを持つ。
Mはメモリのサイズ。
アドレス0と1を、ここでは特別な意味を持たせて使う(したがって、値 0 および 1 のポインタは特別な意味を持つ って表記ムズすぎる)。
0はnullポインタ、1はmakeGreyのTestAndSetにおける競合チェックのために予約されている
アプリケーションモデル
以下の操作がある。
Read
Write
New(n) n個のフィールドに新たなオブジェクトを割り付けて、最初のフィールドを返す。
InitSlot(v)オブジェクトの初期化
制約
New(n)を実行するとInitSlot(v)を前から順にn回実行していく。
「新しいオブジェクトを使用したり」(←これなに？ 全部InitSlotされる前にさわっちゃダメということ？)、もう一度Newを実行したりする前に、n回のInitSlotの全てが完了していないといけない。
ReadとWriteは挟まっててもいい。
Write操作が不可分
isPointer(p, i) オブジェクトpのi番目のフィールドがポインタかどうか決定する(これはオブジェクトのクラスとかから静的に決定できるかもしれない)。
アルゴリズム
オブジェクト表現
各オブジェクトにはヘッダ領域がついていて、ここに転送先のアドレスや複製待ちのフィールド数を保存する
from空間のオブジェクトのヘッダには転送先のアドレスを格納し、forwardingAddress(p)でアクセスする
to空間のオブジェクトのヘッダには未複製のフィールド数を格納し、copyCount(r)でアクセスする
from空間のオブジェクトpのcopyCountはr = forwardingAddress(p)をした上で(r != nullなら)copyCount(r)することで得ることができる
forwardingAddressとcopyCountを同じオブジェクトに同時に格納することはないので、ヘッダ領域は1ワードのみでよく、そのためこの2つの関数の実装は同じでよい
これはto空間とfrom空間を反転したときに自動的に黒→白に変更する上でも役立っている
オブジェクトの色
白のとき forwardingAddress(p)=null
灰のとき forwardingAddress(p)!=null && copyCount(r)=n (n>0)
黒のとき forwardingAddress(p)!=null && copyCount(r)=0
to空間とfrom空間が反転した際に、to空間の黒であったオブジェクトが、copyCountとforwardingAddressの領域が同じであることにより、copyCount(r)=0 の意味が forwardingAddress(p)=nullになるので、特別な処理をしなくても、白色と判定されるようになる。
copyOneSlot(p):
copyCount(r)はpのサイズnに対して、一般に0からnまでの値を取りうるが、負の値のときにはロック状態を表現する
i番目のフィールドの複製中のとき、copyCount(r) == -(i+1)とする
WriteバリアにおいてcopyCount(r)の値をチェックすることで、copyOneSlotが転送中のフィールドに対して競合する書き込みが発生しないようにしている
複製オブジェクトのフィールドに書き込まれるポインタ値は、複製先のオブジェクトのアドレス(forwardingAddress(v))である
code: .py
if isPointer(p, i):
v = makeGrey(v)
makeGray(p):
makeGrayを呼ぶ時点では、呼び出し側はpは白(つまりforwardingAddress(p)=null)だと思っている。が、複数箇所から同時に呼ばれることがある。
TestAndSet(&forwardingAddress(p))で、TestAndSetが0を返した時は、勝ったということなので、「指名コピー者」となれる。
TestAndSet(addr): *addrが0なら1にする。元々の*addrを返す。
TestAndSetによってforwardingAddress(p)の値はまず1になり、その後r = allocate(count)の値で上書きされる
競争に負けたとき、forwardingAddress(p) == 1だったなら、勝者が値を更新してくれるまで少し待てばよい
allocate(n):
code:allocate.py
def allocate(n):
ref ← FetchAndAdd(&free, n)
if ref + n > sharedStack: # to 空間を使い果たした
if gcOn:
error "Out of memory"
# ここではgcOn == false
interrupt(collectorOn) # ミューテータに割り込みをかけて次の GC を開始
ref ← allocate(n) # やり直す (ここでrefに代入していないのはおそらくバグ)
return ref
New(n):
forwardingAddress(p) = rは一見無駄に見えるが、割り付け直後のオブジェクトを黒色にするためには仕方がない
3色抽象化の表現方法を変更すれば最適化の余地がある
ミューテータはNew(n)のあとにInitSlot(v)をn回呼び出してフィールドを初期化する必要がある
この初期化は次のNewまでに終わらせる必要があるが、途中でRead, Writeすることは認められている
この初期化が完了していない状態でGCが走っても大丈夫なように設計されている
Write(p, i, v):
pが白ならば、単にp[i] = vするだけ
pが転送先rをもつならば、rのロックがかかっていないことを確認してからp[i] = vする
書き込みが終わったら、一定数$ k個の仕事を回収する
interruptを呼び出すと、中で最終的にsynchまで到達して他スレッドと同期する
interrupt(collectorOn) でなくても collectorOn() でも良さそうに見える、理由は謎
下の実装だったらsynchが分散しなくてよくなって、interruptの気持ちがはっきりするのに
code: interrupt.py
def interrupt(callback):
synch()
callback()
synch()
謎の解説スライド
enterRoom, transitionRooms, exitRoom
部屋は共有スタックの実装において同期を減らすために用いられる
ある時点でpushのみ/popのみを行うのであればFetchAndAddなどのprimitive命令で実装できる
synch (synchronize)
全プロセッサで同期を取るための関数
code:algorithm_19-4.py
shared round ← 0 # 現在の同期ラウンド
shared count ← 0 # synch 済みのプロセッサ数
synch():
curRound ← round
self ← FetchAndAdd(&cnt, 1) + 1
if self = numProc # ラウンド終了。次のラウンド用にリセット
cnt ← 0
round++
while round = curRound:
pass
# 何もしない: 最後のプロセッサがラウンドを変えるまで待つ
collectorOn
全プロセッサでto空間とfrom空間を反転する
toBot, fromBot, fromTop, toTopはプロセッサ固有の変数
gcOn, free , sharedStack は全プロセッサで共有の変数
反転した後で最後に割り付けたオブジェクトの複製を割り付け、そのマーク作業をローカルスタックにpush
このような複雑な構成になっているのはGCに関する関数一回分のコストを定数に抑え、解析をしやすくするため?
もし、最後に割り付けたオブジェクトを全て転送してからでないと空間の反転ができないとすると、反転する関数のコストが定数でなくなる?
具体的には、オブジェクトのフィールド数に比例したコストがかかる?
r ← allocate(lastL)のあたりの挙動の説明
p, r: 空間A(当時のto空間)にallocate(3)によって作られる
forward(p) == r
lastA == p
lastL == 3
lastC == 0
InitSlot(v)を2回
p[0], p[1], r[0], r[1]: 初期化済み
lastC == 2
collectorOn
flipにより空間Aがfrom空間、空間Bがto空間になる
r2: 空間Bにallocate(3)によって作られる
forward(p) == r2
lastC > 0なのでlocalPush(p) (p == lastA)
lastC == 0 なら、のちのInitSlot(v)でr2 の全てのフィールドが初期化される
InitSlot(v)を残り1回
p[2], r2[2]: 初期化済み
r2[0], r2[1]: 未初期化
lastC == 3
pはスタックに入っているので、いずれcollect経由のcopyOneSlotによって、現在のforward(p) == r2の初期化がいずれ行われる
最後に割り付けオブジェクトの処理が終わったらルートをマークする
ルートってレジスタだけでしたっけ? スタック上のオブジェクトは?
スタックは存在しないというマシンモデル(p456)
スタックもルートに含めると仕事が定数でなくなる気がするな
code:algorithm_19-4.py
shared gcOn
shared sharedStack # toTopは誤植か
shared free
collectorOn():
synch()
gcOn ← true
toBot, fromBot ← fromBot, toBot # 反転
toTop, fromTop ← fromTop, toTop
free, sharedStack ← toBot, toTop # 全プロセッサでtoBot, toTopは同じ
stackLimit ← sharedStack
synch()
r ← allocate(lastL) # 最後に割り付けたオブジェクトの複製を割り付ける
forwardingAddress(lastA) ← r # 最後に割り付けたオブジェクトを転送
copyCount(r) ← lastC # コピーするスロット数をセット
if lastC > 0:
localPush(lastA) # ローカルスタックに作業をプッシュ
for i ← 0 to length(REG): # ルートを灰色にする
if isPointer(REG, i):
sharedPush() /* 共有スタックに作業を移す */
synch()
collectorOff
collect中でexitRoom() == trueつまり共有スタックが空(sharedStack == toTop)のときにcollectorOffが呼び出される
ルートは最後にまとめて転送する
ルートを灰色にする で makeGray してないけど?
code:algorithm_19-4.py
collectorOff():
synch()
for i ← 0 to length(REG): # ルートを灰色にする
if isPointer(REG, i):
REGi ← forwardingAddress(REGi) # ルートを転送する lastA ← forwardingAddress(lastA)
gcOn ← false
synch()
============== ここまでやった(2021/10/16) ==========
その他実用上の改良点 (後半3つは説明が少ない)
各プロセッサが固有の割り付け領域を持つことで
FetchAndAddをなくす
オブジェクトをプロセッサ自身のプライベートな空間のどこに置くか知ることができるので、TestAndSet でなく CompareAndSwap を使うことができる
投機的にallocするということ?
いいえ、各プロセッサの持つプライベートな空間のfreeがalllocされるアドレスなので、allocする必要がない
New や InitSlot?InitLoc 中のコレクタの作業を、ローカルな割り付け領域が（小さな）オブジェクトでいっぱいになるまで延期したり
延期して後でまとめてやると停止時間が保証できなくなるのでは?
実用上の工夫なので理論的な保証は捨てる
New における（オリジナルと複製の）二重割り付けのコストを回避したり
どうやって?
「部屋」による同期を用いて Write を不可分にする
アルゴリズム19-2 - 23行目, 26行目のwhile loopがなくなる
アルゴリズム19-2 - 18行目のatomicは削除するべき
時間的・空間的上界
最悪空間計算量の上界がある
たかだか$ 2(R(1+2/k)+N+5PD)メモリワードを要する
ミューテータスレッドの停止時間の上界がある
この上界は大きなオブジェクトや配列でも保証される
これはmakeGrayが1フィールドずつ進めるから
パフォーマンス
シングルプロセッサでストップザワールドGCに対して50%のオーバーヘッドがあった
これは並列並行にしたコスト
コレクタはプロセッサに対してよくスケールしたが、ミューテータはしなかった
ストップザワールドGCは10msの粒度で最小ミューテータ利用率がゼロあるいはほとんどゼロだった
10msずつに時間を区切ったときに全プロセッサのうちミューテータが使っているプロセッサの割合が0になっているところがあった?
最小ミューテータ使用率(MMU)
https://gyazo.com/ec8320bcef784a062f049017c6bc4529
並行コレクタでは10msのMMUがk=2で10%, k=1.2で15%だった
kはcollectのパラメータ
停止時間を短くすることに成功している
不均一な作業量と仕事ベーススケジューリングに与えるインパクト
実行時間解析において最悪ケースが通常ケースとかけ離れている
最悪実行時間解析ではミューテータの最悪な振る舞いを仮定して、コレクタの実行時間を見積もらなくてはいけない
Baker［1978］コレクタでは、ポインタスロットを読み出す操作がターゲットのコピーを引き起こす可能性がある
配列のような可変長オブジェクトでは定数時間にならない
ルートの反転操作はスタックの長さに比例する
最悪ケースの時間を短くするための工夫
スタックをスタックレットに分割し、反転時には一番上のスタックのみを走査する
スタックがスタックレットを超えて巻き戻るときはミューテータが走査する
オブジェクトをオブレットに、配列をアレイレットに分割する
アクセス時に特殊なラッパーを介する必要がありオーバーヘッドがある
ミューテータに対する非対称(非均一)なオーバーヘッド
反転操作の直前ではほとんど全てのオブジェクトが転送済みなのでWriteにオーバーヘッドはほぼ無い
アルゴリズム 19-2 22行目の forwardingAdress(p) != 0 がfalse
逆に反転操作の直後ではWrite のたびに転送が発生する
ミューテータが実行できる時間の割合が短くなりすぎる問題
https://gyazo.com/d488dc59569082248dcbb7445c0912e6
これは最悪の場合、ミューテータが単位時間に作り出すコレクタの仕事量が10単位時間かかるってこと?
非移動型並行コレクタ
ヒープ領域にアクセスする際のオーバーヘッドは均一
割り付けのタイミングが均一にならないので、仕事ベースではGCオーバーヘッドの変動が大きい
この割り付け時の問題は非移動型でも解消できない
より高度なスケジューリング
ミューテータの各操作に対してコレクタに発生する負荷を計算し、それをもとにコレクタをスケジュールするのは、ばらつきが大きすぎて無理
ガベージコレクションをミューテータから切り離す
どうやって?
こうすると最悪実行時間解析が平均的なミューテータの実行時間と近くなる