"Peter Dimov" <pdimov@mmltd.net> writes:
Anthony Williams wrote:
"Peter Dimov" <pdimov@mmltd.net> writes:
Peter Dimov wrote:
This is what CRITICAL_SECTIONs do, and I recall being told by Alexander Terekhov that it is suboptimal (threads take the slow path when they could take the fast path). My tests with a contended queue seemed to prove him right.
Unfortunately, I can no longer find his post where he explained that with Google.
Here it is:
Thanks. I'll have to look at Alexander's proposed swap-based implementation.
I've played with it a bit:
http://www.pdimov.com/cpp/mutex.cpp
but I suspect that there are a few errors in this old code... some of the reads are not atomic but need to be. Maybe we can give it a review and bring it up to Boost standards.
From the OS point-of-view, this is a producer-consumer scheme, with A being
The case given in Alexander's email above is: A: lock [lockcount == 0] B: lock [lockcount == 1, slow path] A: unlock [lockcount == 0, slow path/post sema] A: lock - [lockcount == 1, slow path] He claims that the second A: lock takes the slow path, when it could have taken the fast path because the lock is free. I disagree. The lock is NOT free, since B is waiting on it. If A can take the fast path here, that's opening the door for B to be starved. By A taking the slow path, both A and B will wait on the semaphore, and the OS can pick which wakes up. In your code, we have: A: lock [lock_==0, fast path, set lock_ to 1] B: lock [lock_==1, slow path] B: slow wait [lock_!=0, set lock_ to -1, wait on event] A: unlock [lock_<0, set lock_ to 0,post event] A: lock [lock_==0, fast path, set lock_ to 1] B: event posted, [lock_!=0, set lock_ to -1, wait on event] A: unlock [lock_<0, set lock_ to 0,post event] If A does unlock/lock without any intervening code, those last three lines can repeat forever: A: lock [lock_==0, fast path, set lock_ to 1] B: event posted, [lock_!=0, set lock_ to -1, wait on event] A: unlock [lock_<0, set lock_ to 0,post event] A: lock [lock_==0, fast path, set lock_ to 1] B: event posted, [lock_!=0, set lock_ to -1, wait on event] A: unlock [lock_<0, set lock_ to 0,post event] A: lock [lock_==0, fast path, set lock_ to 1] B: event posted, [lock_!=0, set lock_ to -1, wait on event] A: unlock [lock_<0, set lock_ to 0,post event] A: lock [lock_==0, fast path, set lock_ to 1] B: event posted, [lock_!=0, set lock_ to -1, wait on event] A: unlock [lock_<0, set lock_ to 0,post event] the producer and B the consumer. B is regularly woken, and does processing until it's next wait. Unfortunately, B never makes any progress. If A always takes the slow path when we have another waiter, then we give the OS more scope for ensuring that both A and B get a fair stab. Anthony -- Anthony Williams Software Developer Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk