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

[Ori Berger]

On 04/13/2011 09:41 AM, Omer Zak wrote:

> A full fledged queue would force the consuming process (process A) to
> read and process all data written by the producing process (process M)
> even when process A needs only the most recent value whenever it reads
> process M's data.

I forgot how this scheme is called, but assuming you have some shared 
memory between the processes, what you do is:

have value variable (e.g. "value") and counter variable ("counter")
also shadow_value and shadow_counter

initialize counter to 0 (any even number will do)

in process M:

atomic_increase counter; (or follow with memory_barrier())
write value;
atomic_increase counter; (or follow with memory_barrier())

in process A:

pre_counter = atomic_read counter; (or precede with memory_barrier())
new_value = read value;
post_counter = atomic_read counter; (or precede with memory_barrier())

if (pre_counter == post_counter) && (pre_counter%2 == 0), new_value has 
been safely read; write it to "shadow_value", use that as value, (and 
for good measure store pre_counter in "shadow_counter").

if pre_counter != post_counter, use "shadow_value" - and be aware that 
your value is actually up to date only for "shadow_counter".

This is lock free in the sense that no process blocks waiting for the 
other one. However, you may end up using an older value. You might put 
'A's reader in a loop, so that it retries until it manages to read an 
up-to-date value.

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.

Note that unlike CAS and friends, the "value" here can be any size 
whatsoever - only the counter needs to be read/written atomically (or 
otherwise synchronized through the memory barrier).