CRuby's Parallel Marking (Draft)

gistfile1.txt

CRuby's Parallel Marking (Draft)(Ja)

ソースコード: https://github.com/authorNari/ruby
※まだ実装中

1 Abstract
並列スレッドの仕事分配には「Arora's Task Stealing Deque」のアルゴリズムを利用する。
http://doi.acm.org/10.1145/277651.277678
また、並列マークの実装の大部分はOpenJDK7のコードを参考に独自改良したものである。

2 Task Stealing
Aroraらのアルゴリズムでは「リセットが起きないとdeque最大数まで使用できない」という問題がある。
そのため、deque.datesはリングバッファで実装した。

2.1 Ring buffer

リングバッファであるため bottom は一周して、topよりも下になるかもしれない。
そのため、リングバッファのサイズを取得する関数のsize_deque()を工夫してある。
size_deque() は bottom と top の状態に応じて以下のように値を返す。
GC_DEQUE_SIZE = 32, GC_DEQUE_SIZE_MASK = 31 と仮定する。

  a. bottom = 5, top = 5, bottom == top の場合は 0
  b. bottom = 7, top = 5, bottom < top の場合は 2
  c. bottom = 2, top = 5, bottom > top の場合は 29
  d. bottom = 4, top = 5, bottom == (top - 1) の場合は 0

2.2 Why size_deque(bottom = 4, top = 5) is 0 ?

2.1.a.のケースについて説明する。
実はdequeの最大の要素数は GC_DEQUE_SIZE - 2 まである。
わざとリングバッファの最後の1要素分空けている。
そのため、 GC_DEQUE_SIZE - 1 まで要素が入ることはない。
つまり、通常は「bottom = 4, top = 5」の状態にはならない。
2.1.d.は、並列性の複雑さによって発生する。
例えば、オーナースレッドでは bottom = 2, top = 3 （残り1要素）の状態で
pop_bottom() を呼び出す。他スレッドは同時に pop_top() を呼び出す。

  bottom = 3, top = 3 # pop_bottom() の increment
  bottom = 3, top = 2 # pop_top() の decrement, pop_top()のCASが成功
  ... # *ここの間は size_deque() が GC_DEQUE_SIZE - 1 になる * (A)
  bottom = 3, top = 3 # pop_bottom() の deque->age = new_age, CASに失敗

(A)の間に pop_top() が起こっても不具合がないようするため、2.1.d.のケースが存在する。

2.3 Logical reset
Aroraらのアルゴリズムと異なるのは、pop_bottom()で空のdequeになった際に
bottom を 0 にリセットしないことある。
これはリングバッファで実装されているため、論理的にリセットされた状態に
なると考えることができる。
また、2.2の(A)の状態で push() が発生すると bottom をインクリメントするため、整合性が
とれなくなる恐れがある。そのため、bottom = 0 でリセットしない。

2.4 Tag increment timing
tagをインクリメントするタイミングは次の2つ。

 1. reset at pop_bottom()
 2. top == 0 at pop_top()

1. はAroraらのアルゴリズムと同じ。
2. はリングバッファゆえにやらなければならない。
例えば、pop_top()で top == 1, tag == 0 でサスペンドしているスレッドAがあるとする。
スレッドBはpop_top()を繰り返し、topが一周回ると、また top == 1, tag == 0 の状態になるかもしれない。
その場合はどちらのpop_top()のCASも成功する可能性がある。
そのため、topが一周した段階でtagをインクリメントする必要がある。

2.5. Deque overflow & getback
dequeがオーバフローしたときは、push()がFALSEを返す。
その際にdeque内の全要素をpop_botom()を使って取り出し、マークスタックに移動する。

また、空になったときは pop_local() がFALSEを返す。
マークスタックにバッファがあれば、deque内にpush()を使って詰め直す。


3. Mark phase
マークフェーズは次の4ステップから構成される。

 1. Root object's scan
 2. Parallel gray object's scan
 3. Parallel deque object's scan
 4. Parallel stole object's scan

1. はルートから直接参照されるオブジェクトをマークする。
2. は全ヒープを並列に走査して、マークされたオブジェクトの子オブジェクトをスキャンする。
3. は 2. によって追加された自スレッドの deque 内のオブジェクトをすべてスキャンする。
4. では、自スレッドのすべての仕事が完了しているため、steal()を使って他スレッドからオブジェクトを盗み、これをスキャンする。
盗むオブジェクトがなくなれば並列マークの終了である。

3.1 Parallel gray object's scan
まず、ヒープには root object's scan によってマークがすでに付いている。
マークが付いているが、その子オブジェクトがまだマークされていないオブジェクトを gray object と呼ぶ。
root object's scan によってマークされたオブジェクトは gray object である。

並列マークスレッドはマーク時に、アドレス順に並んでいるヒープスロットから順番に1つだけを確保する。
確保が完了すれば、ヒープスロット内のマークが付いているオブジェクト（gray object）をスキャンする。
ヒープスロット内のgray objectをすべてスキャンすると、また次のヒープスロットの確保を行う。

3.2 Passed gray object
3.1 でも述べた通り、並列マーキングは先頭のヒープスロットから順番に灰色オブジェクトをスキャンしていく。
ここで問題となるのが、すでにgray object's scanを通り過ぎた位置に灰色オブジェクトの子オブジェクトがある場合だ。
これはgray object's scanが通らないため、あとで特別にケアする必要がある。
これをpassed gray objectと呼ぶ。
結論から言うと passed gray object は deque に追加して、あとで特別にケアする。

passed gray objectを検出するために global slot finger を使用する。
global slot finger は並列マークスレッドがヒープスロットを確保した際に、CASを利用してアトミックにヒープスロットのアドレスを設定する。
これによって並列マークスレッドが確保した中で一番下位アドレスにあるヒープスロットが global slot finger に格納される。

passed gray object はこれらの global slot finger を使って次のように検出される。

 「子オブジェクトは global slot finger のヒープスロット内の最後より上位にあるか？」

並列マークではこの処理が大きな意味を持つ。
子オブジェクトが、他のスレッドがマーク中のヒープスロット内のオブジェクトだった場合は、それがすでにpassed gray objectになってしまう可能性があるからだ。
検出した passed gray object は漏れなく push_bottom() される。

3.3 Obejct marking
それぞれのdequeには同じオブジェクトが入る可能性がある。
オブジェクトは複数の親オブジェクトを持つかもしれないからだ。
そのため、markは競合する可能性がある。

しかし、Markをアトミック操作にする必要はない。
なぜなら、マークビットの操作はすべて1にする方向であり、mark bit以外のビットは変更がないからである。

そのため、マーク済みのオブジェクトがdequeに入る可能性がある。
その場合、マーク済みのオブジェクトはスキャンせずに、無視するだけだ。



--- English ---
TODO: 
---------------