18.2 バッファ型参照カウント方式

即時参照カウント法はロックかCompareAndSwap2などの特殊なプリミティブが必要

延期型参照カウント法は18.1で見た問題をある程度解決する

18章冒頭で見た参照カウントの操作コストが重いという話?

バッファ式参照カウント

ミューテータのライトバリアにおいて単純なロードとストアしか用いないにもかかわらずマルチスレッドアプリケーションをサポートする

DeTreville［1990］

ミューテータが各ポインタ更新での新旧の参照先をコレクタ内のバッファにログとして記録

独立した 1 つの参照カウントスレッドが、そのログを処理してオブジェクトの参照カウントを補正し、それによって変更が自明に不可分であることを保証

しかし更新をバッファリングしても、参照カウントの操作とポインタの書き込みを同調させる問題の解決にはならない

ログの正しさが保証できないから?

図18-1のようなケースでログの更新とポインタ更新が一致しないケースでだめ

解決策

Write 操作全体をロックで保護する

各ミューテータスレッドにバッファを持たせてそれを定期的に参照カウントスレッドに渡す

ポインタの書き込みが不可分に行われることを保証するようにプログラマが注意する必要がある

Bacon and Rajan［2001］

DeTreville［1990］と同様に各スレッドに局所バッファを持たせた

Readバリアはない

Writeバリアで書き込みをmyUpdatesに記録する

myUpdatesはプロセッサごとにある

eもプロセッサごと

collectはプロセッサ1からMAX_PROCESSORSまでに順番にスケージュールされ実行される

プロセッサ1番からプロセッサMAX_PROCESSORS-1番まではmyUpdateをグローバルなupdatesBufferに転送するだけ

MAX_PROCESSORS番のプロセッサでcollectが実行されるときに参照カウントを更新する

TODO: eって必要? → 必要

epochに触るのはcollectだけで、collectは一度に一つのプロセッサでしか実行されないのでepochに関して競合が起きる可能性はないように見える

eとepochの差は一定ではない

collectがプロセッサiで走る前 → e == epoch

collectがプロセッサiで走ったあと → e == epoch + 1

Writeはcollectする前と後でupdateBufferの別の場所にアクセスしなくてはならない

collectが走ったかどうかを判定するフラグを持っても良い

ミューテータが一斉に休止する必要がない

コレクタがオンザフライに動作する

code:algorithm-18-4.py

shared epoch

shared updatesBuffer[] # 時代あたり 1 つのバッファ

def Write(src, i, ref):

if src = Roots:

else:

log(old, ref)

def log(old, new):

def collect():

# 各プロセッサはグローバルな updatesBuffer 上に自身のバッファを渡す

myStackBuffer ← []

for each local ref in myStacks: # 延期型参照カウント法

# Q: なんでこの<ref, ref>が必要なの?

# A: この<ref, ref>が無いと Write の中で src = Roots の場合もAtomicExchangeを行う必要がある

# AtomicExchangeは重いのでできればさけたい

# <ref, ref> を追加している部分（ちょうど1回）にすべて押し付けてコストを削減している

atomic

atomic

myUpdates ← []

e ← e + 1

me ← myProcessorId

if me < MAX_PROCESSORS:

schedule(collect, me+1) # 次のプロセッサ上で collect() をスケジュールする

else:

# 最後のプロセッサが参照カウントを更新する

addReference(new)

deleteReference(old)

# Q: 上の4行の代わりにこれではだめか

# A: だめ。以下が反例。

# thread1 | thread2

# Write(obj2, j, Read(obj1, i)) | Write(obj1, i, ref)

# 1. Read(obj1, i) ※リードバリアが無いことに注意

# 2. Write(obj1, i, ref)

# 3. collectで

# addReference(ref)

# addReference(new)

# deleteReference(old)

epoch ← epoch + 1