|
|
Threads-Devel : |
From: Anthony Williams (anthony_at_[hidden])
Date: 2007-08-09 13:21:08
Hi Allen,
I've snipped your comprehensive state list to the "interesting" states.
"Allen Pulsifer" <pulsifer3_at_[hidden]> writes:
> State RF3. All running readers have just finished, and there are both
> readers and writers waiting. We either (a) choose one or more of the
> readers to run and go to either State R1 or R2; or (b) chose one of the
> writers to run, and go to State W.
> State WF3. A writer has just finished, and there both readers and writers
> waiting. We either (a) choose one or more of the readers to run and go to
> either State R1 or R2; or (b) chose one of the writers to run, and go to
> State W.
>
> In summary, the decisions that have to be made are:
>
> - at RF2 and WF2: which writer runs?
Leave that to the OS.
> - at RF3 and WF3: do one or more readers run, or does one of the writers
> run? If one or more readers, how many readers and which readers? If a
> writer, which writer?
>
> The solution that apparently has been proposed and implemented for all of
> the decisions above is that we simple wake all threads and allow the OS to
> make these decisions as a side-effect of its scheduling algorithms and
> whoever gets back to the mutex in whatever order.
Yes. The writer condition is notified first, but the mutex is still locked.
> For State RF3, I think that is the wrong approach, for the reasons I
> mentioned in my last email--as long as you are using State R2, where new
> readers are forced to wait in an effort to clear the resource for exclusive
> access, then you should follow this by going to exclusive access. In State
> RF3, the library should only wake the writer threads and allow one of them
> to run.
I'm beginning to find your argument quite compelling.
> For State WF3, I think it would also be a mistake to simply wake all threads
> and make it a free-for-all. The reason again is that you might end up with
> only one of the readers having access while 20 other readers wait, when it
> would be better to have two or more readers running with shared access.
> Therefore, in State WF3, I think the library should do one of the following:
Firstly, this shouldn't happen very often. If there are writers waiting a high
percentage of the time when a writer unlocks, then you probably want a
different synchronization scheme.
I think there are three reasonable options here:
(a) do what the code does now --- wake all threads, and allow them to compete.
> (B) Wake only the readers, and allow N readers to get shared access to the
> lock, where N is from 1 to the # of readers then waiting. Note that this
> could be implemented by temporarily going into State R1. Also note N could
> be dynamically set by the application at any time, to allow the behavior to
> be adapted to the workload.
>
> (C) Wake all of the threads. If a writer gets the lock first, go to State
> W. If a reader gets the lock first, then allow N readers to get shared
> access to the lock before going to State R2.
I think "N=all currently waiting" is the only sensible choice in cases B and
C.
I'm inclined to go for C. I'll have a go at implementing it, and timing it
against what we've currently got when I get a chance. The win32 code was
subject to intense scrutiny and lots of benchmarking of various options, but
the pthreads code has not been subject to the same level of scrutiny --- it is
just a simple reimplementation of almost the same logic as the win32 version
using condition variables rather than native win32 sync primitives.
Anthony
-- Anthony Williams Just Software Solutions Ltd - http://www.justsoftwaresolutions.co.uk Registered in England, Company Number 5478976. Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL From: Anthony Williams <anthony_at_[hidden]> Date: Thu, 09 Aug 2007 18:21:08 +0100 In-Reply-To: <001201c7d6a3$56765f40$670aa8c0_at_apt23> (Allen Pulsifer's message of "Sat, 4 Aug 2007 10:25:32 -0400") Message-ID: <r6mclj3v.fsf_at_[hidden]> User-Agent: Gnus/5.1008 (Gnus v5.10.8) XEmacs/21.4.19 (windows-nt)