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

[Omer Zak]

On Wed, 2011-04-13 at 16:40 -0400, Ori Berger wrote:
> 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

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

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

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.
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.

> 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".

In this case, process A would simply yield control (equivalent to
putting process A in a loop, except that other processes would be
allowed to proceed meanwhile), as it hasn't read a new value this time.

> 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.

The ideal solution needs a mechanism to prevent this theoretical
possibility.

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

--- Omer


-- 
Shakespeare Monkeys: cat /dev/urandom | strings -n 16
My own blog is at http://www.zak.co.il/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.html