From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-09-19 10:38:35
"Peter Dimov" <pdimov_at_[hidden]> writes:
> Inventing mutex and condition variable algorithms is a slight cause of
> concern, I have to admit. The easiest way to get a free review of the
> algorithms is to post the code on comp.programming.threads and hope that
> someone of the experts there has enough time to look at them. CVs in
> particular have proven to be quite hard to implement correctly, and
> Alexander Terekhov's "8a" algorithm has emerged as a de-facto standard.
The mutex is simple, and you can see the code in
boost/thread/win32/basic_mutex.hpp on the thread_rewrite branch.
The algorithm is:
atomic increment active_count
if new active_count ==1, that's us, so we've got the lock
get semaphore, and wait
now we've got the lock
atomic decrement active_count
if new active_count >0, then other threads are waiting,
so release semaphore.
if there's already a semaphore associated with this mutex, return that
create new semaphore.
use atomic compare-and-swap to make this the associated semaphore if
if another thread beat us to it, and already set a semaphore, destroy
new one, and return already-set one
else return the new semaphore
The condition variable algorithm is actually a variant of Alexander Terekhov's
algorithm, and uses the same "gate" idea. However, my implementation uses
QueueUserAPC to wake up the waiting threads, rather than have them wait on an
event. This gets round what I think is a deficiency in Alexander's algorithm,
which is that once a notify operation is underway, no new threads can wait on
the condition until all notified threads have actually woken up, and the last
one has "opened the gate". By using QueueUserAPC, we can notify the threads to
wake up, and open the gate, without having to wait for all the notified
threads to resume. The flipside is that the first thread to wait is the first
to be notified. Whether this is a good or bad thing is open to debate.
The code is in boost/thread/win32/condition.hpp on the thread_rewrite branch.
The algorithm is as follows:
waiting_list_node* next, prev
waiting_list: doubly-linked list of waiting_list_node
create a new waiting_list_node
new_node.thread_handle=thread handle for this thread
// Any APC will break the sleep, so keep sleeping until we've been
// notified, or we've timed out
&& SleepEx(milliseconds_until(timeout), true)==WAIT_IO_COMPLETION);
return new_node.notified // did we timeout, or were we notified?
// unlink the node from the list
// wake the node's thread by queueing an APC
// the APC func doesn't have to do anything to wake the thread
if(waiting_list.prev==&waiting_list) do nothing
create a waiting_list_node for new_list
// transfer the existing list over to new_list
// the waiting_list is now empty
unlock(gate) // noone has to wait for us any more
while(new_list.prev!=&new_list) // loop until the captured list is empty
I'll post the algorithms over at comp.programming.threads for comment.
-- Anthony Williams Software Developer Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk