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

Eric Raymond esr at thyrsus.com
Sat Mar 26 19:36:12 UTC 2011

Dave Hart <davehart at gmail.com>:
>          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.

It's the same painful tradeoff that tz and I and other discussants
have been grappling with for the last week in one way or another.  The
methods that provably prevent corrupt data have nasty blocking failure
modes; the methods that don't have scary worst-case behavior may
produce intermittent data corruption in the *normal* case if the underlying
hardware messes with operation order enough.

I am by no means sure I know where to land.  I have working seqlocks
now and am oscillating back and forth about whether to scrap that and go
with semaphores.  I was almost ready to do it until two things happened:

(a) tz pointed out correctly that in a semaphore-based approach, readers
have to assert as well as writers - otherwise writer can start an update while
reader is still reading.

(b) I then realized that under a correct semaphore implementation,
anybody dying while semaphore is asserted starves everybody else
(which we should have remembered from Operating Systems 101).  This is
a very practical problem because while we haven't had a crash bug in
gpsd since something like 2005, I can't say the same thing about all
the clients out there!

This is pushing me back towards sticking with the working seqlock.
But *that* means I have to either deal with the pile of nonportable
hair that is memory barriers or expensively checksum the data.

Yes, I've been listening to Terje too.  The problem is that his proposal
is complicated enough to make my head hurt - and I plain don't trust
complicated algorithms in cases like this, they tend to have holes 
where nobody is looking and be difficult to *maintain* correctness of
even if they started out correct.
		<a href="http://www.catb.org/~esr/">Eric S. Raymond</a>

More information about the hackers mailing list