18.1 単純な参照カウント法の再考
不変条件:「あるオブジェクトの参照カウントはそのオブジェクトへの参照数に等しい」
マルチスレッド下でこの不変条件を守るのは難しい
o[i]の参照カウントが2回デクリメントされるかもしれないし、新しいターゲットの一方の参照カウントは増え過ぎることがある
増えすぎるのはどういうケース
code: too-many-incremnet.py
Write(o, i, x) | Write(o, i, x)
# この場合 addReference(x)が2回連続で呼ばれて参照カウントが増えすぎる
# Write は atomic ではないためにこういう問題が起きる
https://gyazo.com/70b0a62a92b3124a3dbe633ef9ac37b6
参照カウントをポインタのロード/ストアと同期させるのが難しい
簡単な解決策: 読み出しあるいは書き込みをしようとしているフィールドを含んだオブジェクト src をロックする
code: algrithm-18-1.py
def Read(src, i):
lock(src)
addReference(tgt)
unlock(src)
return tgt
def Write(src, i, ref):
addReference(ref)
lock(src)
deleteReference(old)
unlock(src)
一般的なプリミティブを用いた実装の試み
code:algorithm-18-2.py
# このコードは機能しない
# rc は Reference Count の略
def Write(src, i, ref):
if ref ≠ null
AtomicIncrement(&rc(ref)) # ref はフリーにならないことが保証される
loop
if CompareAndSet(&srci, old, ref) deleteReference(old)
return
def deleteReference(ref): # ref は null であるかフリーではないことが保証されている
if ref ≠ null
AtomicDecrement(&rc(ref))
if rc(ref) = 0
for each fld in Pointers(ref)
deleteReference(*fld)
free(ref)
# p = Read(src, i)
def Read(src, i):
# この瞬間に別スレッドが srci が指しているオブジェクトを削除する可能性がある AtomicIncrement(&rc(tgt)) # おっと!
return tgt
CompareAndSwap2を使う
これでも「あるオブジェクトの参照カウントはそのオブジェクトへの参照数に等しい」は保証できない
ただし以下のより弱い不変条件は保証できる
「オブジェクトへのポインタが存在する間、その参照カウントをゼロにすることがない」
「オブジェクトへのポインタが存在しなければ、その参照カウントはいつかはゼロになる」
code:algorithm-18-3.py
def Read(src, i, root):
loop
if tgt = null
return null
rc ← rc(tgt)
if CompareAndSet2(&srci, &rc(tgt), tgt, rc, tgt, rc+1) return tgt
def CompareAndSwap2(x0, x1, old0, old1, new0, new1):
atomic
curr0, curr1 ← *x0, *x1
if curr0 = old0 && curr1 = old1
*x0, *x1 ← new0, new1
return curr0, curr1