"Peter Dimov" <pdimov@mmltd.net> writes:
Anthony Williams wrote:
"Peter Dimov" <pdimov@mmltd.net> writes:
Chris Thomasson wrote:
Here is the initial experimental pseudo-code that I am thinking about prototyping in IA-32 Assembly:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/5f...
Seems like it can work. Don't you only need one bit for writes though?
It's essentially the same algorithm I've used in my latest offering on the thread_rewrite branch.
Do you plan to document the algorithm?
Yes, later. Thanks for reviewing, Peter. The final boost code can only be better because of it. Thanks also to Chris for his pseudo-code.
I'm interested in the following scenario:
- K active readers are holding the lock - a writer is waiting for the above - L readers are wating for the writer
Since you seem to only store K+L (Chris's algorithm has separate counts), how do you know when to signal the writer?
Maybe it's not /quite/ the same algorithm, but it's certainly very similar. The answer to your question is "when all K+L readers have finished". i.e., my algorithm gives readers priority. Maybe this isn't such a good thing; in the "common" scenario of one writer thread and many readers, a waiting writer needs to block waiting readers, otherwise the writer might starve if the readers overlap each other. Chris's algorithm goes to the other extreme --- writers always take priority, and no readers will take the lock if there are any waiting writers. If there is more than one writer thread, then the readers might starve. The way I see it, the ideal is that a waiting writer will block any fresh readers until all the current readers have gone away, but once that happens, and the lock is released, the waiting writer and the waiting readers will compete equally. To do that, you should be able to get away with a single bit for waiting writers, too --- either there are waiting writers, or there aren't. Likewise for waiting readers. When the last reader, or the only writer unlocks, it clears both the waiting readers and waiting writers flags, and unblocks all waiting threads (signals an event). The waiting threads then compete. If a reader gets there first, then subsequent readers are allowed in until a writer thread wakes up. Once a writer either gets the lock, or flags that it's waiting, then the remaining readers are blocked until the next wakeup. Thoughts? Anthony -- Anthony Williams Software Developer Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk