How can you implement a condition variable using semaphores?

algorithm mutex semaphore condition-variable
templatetypedef picture templatetypedef · Mar 19, 2011 · Viewed 10.8k times · Source

A while back I was thinking about how to implement various synchronization primitives in terms of one another. For example, in pthreads you get mutexes and condition variables, and from these can build semaphores.

In the Windows API (or at least, older versions of the Windows API) there are mutexes and semaphores, but no condition variables. I think that it should be possible to build condition variables out of mutexes and semaphores, but for the life of me I just can't think of a way to do so.

Does anyone know of a good construction for doing this?

Answer

Martin DeMello picture Martin DeMello · Mar 19, 2011

Here's a paper from Microsoft Research [pdf] which deals with exactly that.

Related questions

How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More
What does O(log n) mean exactly?

I am learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm proportionally...and the same goes for, …

Read More