[ntp:hackers] [Gpsd-dev] Single-writer/many-reader consistency: Test program written & verified

Terje Mathisen terje at tmsw.no
Mon Mar 28 12:21:30 UTC 2011

Terje Mathisen wrote:
> As I promised I've written a test program, with one writer and 3 readers
> (I have 4 cores so all run at all times, I force them to be on separate
> cores).
> With up to 1000 updates/second I'm totally unable to see any kind of
> inconsistency at any time, with 10K to 1M updates/second the FIFO needs
> to be significantly larger to avoid all problems.
> Anyway, for 1-100Hz the 4-way buffer is definitely working.
> I'll post the program and more details tomorrow.

Dave Hart & I have banged quite a bit against the (fixed) version of the 
test program, and the conclusion is quite nice:

With a 4-way timestamp buffer, and a simple _ReadWriteBarrier() between 
the store of the timestamp and the update of the counter (inside the 
writer process) it is simply impossible to get to an inconsistent state:

Here's the results from a 1-minute run:

counts[] = {0,1,2,3}
Writer affinity = 1, old = f
Reader 1 affinity = fffffffe, old = f
Reader 2 affinity = fffffffe, old = f
Reader 3 affinity = fffffffe, old = f

counts[] = {1020921970,1939160384,924938960,2002669713}

All threads done!
Thread 0 did 1020921970 iterations
Thread 1 did 1939160384 iterations
Thread 2 did 924938960 iterations
Thread 3 did 2002669713 iterations
counter_update = 1047208131, counter_retry = 365502934, 
timestamps_inconsistent = 0

I.e. 1e9 write operations, nearly 4e9 reads.

Of the reads 1e9, i.e. about 25% happened in the middle of an update and 
one third of these required a retry due to the counter variable getting 
close to wrapping around.

There were zero inconsistent timestamps, verified by having the same 
value in both copies, and the current counter value in ns/us field.

Dave has done similar tests for up to hour-long runs, on 3-4 different 
cpu models, with the same results.

As I posted last night, as soon as the update rate drops down to 1KHz or 
less, there are effectively zero retries so the readers never have to 
even spin around a single extra time.

I'll put a copy of the source code on my server later today, I'm 
currently traveling.


- <Terje at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

More information about the hackers mailing list