How are condition varaibles implemnted?

Question

This has baffled me for a long time.

Given basic atomic primitives like compare & swap, I can see how to implement a spin lock (from which I can build mutexes).

However, I don't see how to build condition variables out of this. How is this done?

Thanks!

Answer 1

It's not particularly simple. The following is a link to a paper by Douglas Schmidt (who is also largely responsible for the ACE libraries) that details several approaches for implementing condition variables on Windows using the synchronization primitives available in Win32 (pre-Vista). The approaches include using only the basic, generally available on any OS primitives, and discusses the various limitations of the approaches:

• http://www.cs.wustl.edu/~schmidt/win32-cv-1.html

The bottom line (concluding remarks):

This article illustrates why developing condition variables on Win32 platforms is tricky and error-prone. There are several subtle design forces that must be addressed by developers. In general, the different implementations we've examined vary according to their correctness, efficiency, fairness, and portability. No one solution provides all these qualities optimally.

The SignalObjectsAndWait solution in Section 3.4 is a good approach if fairness is paramount. However, this approach is not as efficient as other solutions, nor is it as portable. Therefore, if efficiency or portability are more important than fairness, the SetEvent approach described in Section 3.2 may be more suitable. Naturally, the easiest solution would be for Microsoft to simply provide condition variables in the Win32 API.

Note that starting in Vista, Windows supports condition variables using native APIs:

• http://msdn.microsoft.com/en-us/library/ms686903.aspx