Atomic updates

[monarch_dodra]

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.