The riddle of atomic data transfer from process A to process B

[Ori Berger]

On 04/13/2011 05:04 PM, Omer Zak wrote:

> If the counter is one byte wide, then any updates to it would be atomic
> by definition (of course, the context is that only process M ever
> modifies it).

While that is true, I was wrong in asserting that "atomic" is enough. It 
needs to be ordered with respect to the value updates. the 
"memory_barrier()" is enough. On x86 with cache coherent everything and 
using a "lock xadd", it should work as is.

> I wondered whether it is enough to realize the counter using two bits.
> However such a design won't protect process A from reading inconsistent
> data if process M was updating data twice while process A was reading
> the same data.

True. You need a no-realistic-possibility-of-overflow counter there. 8 
bits if process A reads sufficiently quickly compared to M updates. 64 
bits would be sufficient for anything on any processor. 32 bits might be 
enough for you.

>> Also, in a fully deterministic system, you might get to a situation
>> where A and B interlace in such a way that you *always* read the value
>> while it is being modified, so the shadow value never gets updated. In a
>> random system, the probability of being more than 'n' updates behind the
>> producer drops exponentially with n.
>
> The ideal solution needs a mechanism to prevent this theoretical
> possibility.

But you also wrote:

 > Even a bigger counter won't provide full protection as long as the
 > counter can overflow.  We need a way for process A to signal back to
 > process M that A is in middle of reading data, so process M should not
 > update it this time.

This suffers from the same problem. Either you do locks (which risk 
blocking), or you risk using an older value (potentially, very old). Or 
you do a "wait free" algorithm (contrast with "lock free", which is what 
I described; no locks but has a "wait" - either a busy wait in reading 
an up-to-date value, or a delay in using an up-to-date value), which is 
beyond the scope of this email, and probably your implementation.