Background

Beginning 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 WaitForSingleObject, ReleaseMutex, and the like.

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 PulseEvent. These implementations will not work. This is due to the fact that the the Win32 function PulseEvent does not work and has never worked, a fact that Microsoft has finally admitted by officially deprecating PulseEvent. I quote from the Win32 documentation:

"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 PulseEvent occurs during the time when the thread has been removed from the wait state, the thread will not be released because PulseEvent releases only those threads that are waiting at the moment it is called. Therefore, PulseEvent is unreliable and should not be used by new applications."

In view of this, it is clear that any implementation of monitors and condition variables in Win32 that uses the function PulseEvent will suffer from inexplicably missed signals.

The Fair Monitor

"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.

Revision History

May 2013
Added some sample regression test code. Fixed a bug with timeout.

Oct 2006
The Wait() and EndSynchronized() methods now check if the calling thread holds the lock, that is, has called BeginSynchronized() at least once. This error check could not be made in the original version because the Win32 function ::TryEnterCriticalSection() did not exist at the time.