18.1 単純な参照カウント法の再考

不変条件:「あるオブジェクトの参照カウントはそのオブジェクトへの参照数に等しい」

マルチスレッド下でこの不変条件を守るのは難しい

増えすぎるのはどういうケース

code: too-many-incremnet.py

Write(o, i, x) | Write(o, i, x)

# この場合 addReference(x)が2回連続で呼ばれて参照カウントが増えすぎる

# Write は atomic ではないためにこういう問題が起きる

https://gyazo.com/70b0a62a92b3124a3dbe633ef9ac37b6

参照カウントをポインタのロード/ストアと同期させるのが難しい

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

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):

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)

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