BackgroundIn most languages and environments that support concurrent programming, the primary synchronization primitive is the monitor idiom, or condition variable idiom, as it is also sometimes referred to. Examples are Java, pthreads, and C#.
with Windows Vista and Windows Server 2008, Win32 joins the club and provides a native condition variable (monitor) implementation.
Before that, Win32 was the oddball with respect to thread synchronization: it did not provide the monitor
idiom at all. Instead, there was (and still is) a motley collection of synchronization primitives such as
mutexes, events, semaphores, etc., together with a set of functions such as
One could ask why it is that David Cutler originally snubbed the monitor idiom, and whether that was good or bad. Be that as it may, a natural question was—and still is until there are no more pre-Vista operating systems in use anymore—if and how the monitor idiom can be implemented in Win32. The answer to that question is long and painful. The purpose of this short article is not to provide a comprehensive treatment of the subject. However, I will point out one thing which is so important that everybody who is interested in a condition variable (monitor) implementation for Windows should know it:
A number of people have suggested implementations that use the Win32 function
"A thread waiting on a synchronization object can be momentarily removed from the wait
state by a kernel-mode APC, and then returned to the wait state after the APC is complete. If the call to
In view of this, it is clear that any implementation of monitors and condition variables in Win32 that uses the
The Fair MonitorThe primary purpose of my fair monitor for Win32 is not to address the general problem of implementing monitors (condition variables) in Win32. What I address is the fact that any wait on a Win32 synchronization primitive, that is, any call to
"A thread waiting on a synchronization object can be momentarily removed from the wait state by a kernel-mode APC, and then returned to the wait state after the APC is complete."
When the object on which the threads are waiting is signaled while a thread is hijacked by an APC in this manner, then the hijacked thread cannot get its fair FIFO treatment, because it's not in the queue at all. Moreover, people have observed (although I couldn't find a place where Microsoft officially admits it) that when a hijacked thread is returned to the queue, it actually goes to the end of the queue, which means that in all likelihood, the queue has now been reordered, and there goes FIFO.
More recently, there is in fact a second reason why Win32 wait operations do not offer a fairness guarantee. Beginning with Windows Vista and Windows Server SP1, Microsoft has made a subtle change to the behavior of all locks (mutexes, critical sections, and kernel locks). The intent of the change is to avoid lock convoys. A side effect of the change is that wait operations on locks are no longer guaranteed to be fair even in the absence of kernel mode APCs. For more details, see e.g. John Duffy's blog entry on the subject.
Personally, I have yet to see a situation where there is a need for a FIFO guarantee on a system wait operation. It seems to me that in a preemptive multithreading environment, such a guarantee is pretty much pointless because there is hardly a way of knowing which thread has entered the wait state first. However, I have witnessed passionate discussions about the issue during which people have complained bitterly about Win32's missing FIFO guarantee. Therefore, and because it seemed like a fun excercise to me, I have written something that addresses the problem.
Since any synchronization problem can be solved with a monitor, one only needs to implement a fair monitor for Win32. Any synchronization problem where fairness is required can then be solved with that monitor. Unless I am missing something, the only way to ensure fairness is to essentially re-implement the queuing in user mode. This will of course incur a considerable performance cost. But if fairness is, for some reason, an overriding concern, then I don't believe there is another choice. Also, if the performance overhead is not a problem for you (and in many situations, it shouldn't be), then my fair monitor provides you with a simple and reliable monitor implementation for Win32.
So here is, for your convenience, my horrendously inefficient but one hundred percent fair monitor for Win32. The header file with its comments serves as the documentation.
|Download the fair monitor for Win32|
Original version created.