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

[Ehud Karni]

On Wed, 13 Apr 2011 16:40:55, Ori Berger 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 scheme has some flows as Omer has noted.

Let me propose somewhat different scheme based on the same principle
that I think will work.

Use shared memory segment that include:
   an index (byte or word)
   First array of N (N >= 2) values to pass.
   Second array of N (N >= 2) values to pass.

Process A (the sending process) write the K (K=0...N-1) value to the
1st and 2nd array than it updates the index to K.

Process B does:
   Reads the index save it (I).
   Reads the value I from the 1st array and save it (V1).
   Reads the value I from the 2nd array and save it (V2).
   Reads the index again (I2).
   if V1 = V2 and I = I2, use the value, otherwise redo from the top.

This process ensures that B never gets a wrong value, but if A is too
fast, B will never get a value.

Ehud.


--
 Ehud Karni           Tel: +972-3-7966-561  /"\
 Mivtach - Simon      Fax: +972-3-7976-561  \ /  ASCII Ribbon Campaign
 Insurance agencies   (USA) voice mail and   X   Against   HTML   Mail
 http://www.mvs.co.il  FAX:  1-815-5509341  / \
 GnuPG: 98EA398D <http://www.keyserver.net/>    Better Safe Than Sorry