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