n May 29, 11:09m, David Jobet < XXXX@XXXXX.COM > wrote:
The above algorithm will not work.
A reader can start reading while inServiceFlag is false, and then be
scheduled out. The writer can then update the structure, toggling the
flag to true, and then back to false. When the reader continues, it
reads the updated data, and sees a false flag. It will get a
combination of data from two (or more) updates. A similar problem
affects the counter version, but there the reader needs to miss so
many updates the counter wraps.
How about using the xchg() operation to publish the data? Note that
the xchg instruction will nicely include the memory barrier you need.
Since mfence + memory operation is suggested to be replaced by xchg as
an optimization, this algorithm should be quite a bit faster than the
two mfence version.
The shared state consists of a pointer-sized piece of memory. If the
lower bit is not set, then the memory is a pointer. If it is set,
then it corresponds in some way to a reader.
The writer can then allocate some memory, and store the publishable
information in that block of memory. When it is done, use the xchg
operation to swap the pointer to point at the new information to
publish it. If the writer gets a cleared lower bit from the xchg, it
can reuse a memory block.
A reader then uses xchg() to set the pointer-sized piece of memory to
some other value with a low bit set. If the reader gets something
without a low bits set, then it has a pointer to the latest bit of
published information. If it doesn't, it gets to know which other
reader has that information. (Or which reader knows which reader has
that information, or similar.) The readers can then use locks to
arbitrate amongst themselves without affecting the wait-free writer.
An example lock-based algorithm for the readers, with a writer-
preferring read-write lock per reader, might be:
Write-lock the rwlock corresponding to my thread.
Try to get data from writer via xchg.
If I succed, copy the data into my publication area.
Unlock the rwlock corresponding to my thread. Done.
If I fail, store the location of the reader who has the latest
information in my publication area.
Unlock my rwlock.
read-lock the lock in the reader thread indicated by the output from
If they don't have the data, read who they think has it. Unlock their
read lock, and try that new reader recursively until you find the
Copy the data from the reader, and then unlock their read lock.
Write-lock my rwlock.
Copy the data into my publication area.
Unlock my rwlock. Done.