On Tuesday, 22 January 2013 at 14:10:14 UTC, qznc wrote:
On Tuesday, 22 January 2013 at 10:27:58 UTC, bearophile wrote:
The Go language has four different solutions, one of them is:
http://rosettacode.org/wiki/Atomic_updates#Lock-free
From the site:
This version uses no locking for the phase where the
two clients are updating the buckets. Instead it
watches for collisions and retries as needed.
func (bl *lfList) transfer(b1, b2, a int, ux int) {
if b1 == b2 {
return
}
bl.RLock()
for {
t := int32(a)
v1 := atomic.LoadInt32(&bl.b[b1])
if t > v1 {
t = v1
}
if atomic.CompareAndSwapInt32(&bl.b[b1], v1, v1-t) {
atomic.AddInt32(&bl.b[b2], t)
break
}
// else retry
}
bl.tc[ux]++
bl.RUnlock()
runtime.Gosched()
}
Is that solution actually correct?
If I am not mistaken, the buckets are in an inconsistent state
between CompareAndSwapInt32 and AddInt32.
So?
buckets[from] -= realAmount; //Inconsistent state here
buckets[to ] += realAmount;
The bottom line is that there *has* to be a point in time where
the state is inconsistent. Your job is to make sure this
inconsistency does not overlap and corrupt the overall state.
