[ntp:hackers] [Gpsd-dev] Single-writer/many-reader consistency

Dave Hart davehart at gmail.com
Sat Mar 26 16:09:53 UTC 2011

On Sat, Mar 26, 2011 at 05:34 UTC, Eric Raymond wrote:
> In previous mail Dave Hart wrote:
>> 8.  Come to agreement on the consistency protocol for one writer,
>> multiple readers, including use of memory barriers where available,
>> but do not require memory barrier support from the compiler, as (IIUC)
>> x86/x64 do not need them for volatile atomic accesses to be coherent
>> across processors, and the ovewhelming majority of current
>> refclock_shm users are on x86 or x64.
> I'm writing to point out that NTP and GPSD are facing near-identical
> problems here.  We too have a one-writer/many-readers shred-memory
> interface we're trying to design with good consistency guarantees.

Yes, I picked up on that and consider it fortuitous, and I'm
optimistic we might come up with similar-enough solutions to be able
to learn from each others' experiences in the wild going forward.
Thank you for pointing it out, though, as some of my NTP colleagues
were undoubtedly unaware.  I had joined gpsd-dev@ before
cross-posting, so I saw some traffic hackers at ntp didn't which made
that obvious.

> As noted in that other thread I started: If your premise is that you
> can't require on memory barriers, you may *have* to go with a
> semaphore, because in their absence instruction reordering and strange
> memory-controller strategies can cause serious problems for spinlocks.

I probably should not have mentioned without requiring memory barriers
as I was attempting to collect a list of suggested improvements, and
here, the suggested improvement boils down to "reduce or eliminate
readers using a mix of two updates" with the liveliest discussion all
about how to achieve that.

> I myself am seriously considering abandoning the spinlock variation I
> invented in favor of a semaphore.  I invented my mechanism because I
> wanted to avoid contention on a semaphore, but in thinking about it
> further I think I may have been more worried about that than I should
> have been.
> Only one process (the single writer) would ever change the semaphore
> state; the readers would just block or spin until it goes to zero.  In
> GPSD writes are infrequent, now normally 1 per second and highly
> unlikely to exceed 100 per second even with survey-grade GPSes we
> don't support yet.  Writes are also small, less than 8K.
> Given this timing pattern, I think readers blocking on the semaphore seem
> unlikely to take a performance hit that is much above the level of
> profiling noise, if that.
> If NTP thinks it's looking at a similar timing pattern, you might want
> to seriously look at using an explicit semaphore.

For refclock_shm.c the rate is one update per second and unlikely to
increase.  On one hand, using a semaphore is appealing because any
needed memory barrier is handled portably by the semaphore
implementation, giving us the same level of consistency guarantee on
all architectures.  I agree actual contention is not going to be much
of a factor, when everything is working smoothly.  I am concerned that
use of a semaphore or mutex could allow one participant process to
interfere with others in undesirable ways, like blocking for extended
periods or failing to receive subsequent updates, that lock-free
approaches would not suffer.

> (I'm having big fun with all this.  Eric gets to think like an OS implementor
> again, yay!  I've missed that, I have.)

Good to hear.  Having fun is important in keeping us fully engaged and creative.

Dave Hart

More information about the hackers mailing list