"Anthony Williams" <anthony_w.geo@yahoo.com> wrote in message news:wt6ok7ow.fsf@yahoo.com...
"Peter Dimov" <pdimov@mmltd.net> writes:
Peter Dimov wrote:
Chris Thomasson wrote:
"Peter Dimov" <pdimov@mmltd.net> wrote in message news:001801c6f7bd$c32f62a0$6607a8c0@pdimov2...
Chris Thomasson wrote:
[...]
Hi,
I have run a test against Peter's "naive" implementation, Peter's implementation of Chris's algorithm, my algorithm from the thread_rewrite branch (v1.1.2.8), my old condition-based algorithm from the thread_rewrite branch (v1.1.2.4), and a new variation of my latest offering that has a "waiting exclusive" bit, and blocks readers if that bit is set, in line with my last post on the subject. The test is essentially Peter's test, with a mod to count the max time any reader or any writer spends waiting, in order to check for starvation.
The tests were run on a Pentium D dual core machine. The output format is
num readers + num writers: : time-in-seconds max-reader-wait-in-milliseconds max-writer-wait-in-milliseconds
The total count N in Peter's algorithm was 65536, in order to get runtimes I could handle.
The first thing to note is that my current V1.1.2.8 deadlocks, so I got the algorithm wrong :-(
;^(...
The next thing to note is that the total runtimes of the remainder are all comparable. I would have to run longer tests to really tell them apart.
The next thing to note is that Peter's implementation of Chris's algorithm has some REALLY long wait times for readers --- 12 seconds! --- which follows from the "writer priority" nature of the algorithm.
12 Seconds? Something is off kilter wrt the writer frequency per-writer-thread and/or the critical-section the writes make use of... IMHO, this would prompt me to revise my applications synchronization scheme... Again, IMHO of course, anytime you are getting enough writes to tank a "rw-mutex w/ stick writer priority" , then you are probably better off using PDR instead of rw-mutexs. Okay, FWIW... Here some pseudo-code for an alter version of my algorithm that gives strict priority to the readers... This "newly augmented algorithm" should do better on Peters test... Hopefully!!! lol. ;^) // write lock rw_mutex_t cmp, xchg; for ( ;; ) { cmp = mtx; do { xchg = cmp; if ( ! cmp.reads && ! cmp.writes ) { ++xchg.writes; } else { ++xchg.w_waits; } } while ( dwcas( &mtx, &cmp, &xchg ) ); if ( ! cmp.reads && ! cmp.writes ) { break; } sem_wait( &w_wset ); } // read lock rw_mutex_t cmp, xchg; for ( ;; ) { cmp = mtx; do { xchg = cmp; if ( ! cmp.writes ) { ++xchg.reads; } else { ++xchg.r_waits; } } while ( dwcas( &mtx, &cmp, &xchg ) ); if ( ! cmp.writes ) { break; } sem_wait( &r_wset ); } // write unlock rw_mutex_t cmp, xchg; do { xchg = cmp; --xchg.writes; if ( cmp.w_waits && ! cmp.r_waits ) { --xchg.w_waits; } else if ( cmp.r_waits ) { xchg.r_waits = 0; } } while ( dwcas( &mtx, &cmp, &xchg ) ); if ( cmp.w_waits && ! cmp.r_waits ) { sem_post( &w_wset ); } else if ( cmp.r_waits ) { sem_post_multiple( &r_wset, cmp.r_waits ); } // read unlock rw_mutex_t cmp, xchg; do { xchg = cmp; --xchg.reads; if ( ! cmp.r_waits && cmp.w_waits ) { --xchg.w_waits; } else if ( cmp.r_waits ) { xchg.r_waits = 0; } } while ( dwcas( &mtx, &cmp, &xchg ) ); if ( ! cmp.r_waits && cmp.w_waits ) { sem_post( &w_wset ); } else if ( cmp.r_waits ) { sem_post_multiple( &r_wset, cmp.r_waits ); } Try that on for size everybody! However, beware, this algorithm can potentially starve writers!! Enjoy... ;^)