On 04/13/2011 05:04 PM, Omer Zak wrote:
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).
While that is true, I was wrong in asserting that "atomic" is enough. It
needs to be ordered with respect to the value updates. the
"memory_barrier()" is enough. On x86 with cache coherent everything and
using a "lock xadd", it should work as is.
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.
True. You need a no-realistic-possibility-of-overflow counter there. 8
bits if process A reads sufficiently quickly compared to M updates. 64
bits would be sufficient for anything on any processor. 32 bits might be
enough for you.
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.
But you also wrote:
> 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.
This suffers from the same problem. Either you do locks (which risk
blocking), or you risk using an older value (potentially, very old). Or
you do a "wait free" algorithm (contrast with "lock free", which is what
I described; no locks but has a "wait" - either a busy wait in reading
an up-to-date value, or a delay in using an up-to-date value), which is
beyond the scope of this email, and probably your implementation.
_______________________________________________
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
