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).
_______________________________________________
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
