How can you implement a condition variable using semaphores?

Question

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?

Solution

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

Comments

[Theo]

Umm, unless "semaphore" means something completely different in the Windows APIs they are not something you communicate with.

[mcdowella]

One process can set a semaphore and another process can test it to see if it has been set or not. Two machines can communicate arbitrary messages by testing and setting the voltages down a couple of wires. Two processes can communicate arbitrary messages by testing and setting the state of semaphores. In practice you would probably use the semaphores only to regulate access to shared memory, but I regard both cases as communication - even if in the second case all you are communicating is "OK - you can read shared memory now".

[PSkocik]

I think that should mostly work but theoretically, your last waiter could get preempted between sem_wait an pthread_mutex_lock by a thread calling signal -- and that would mess up your semaphore value. It's tricky to get these things right for all possible interleavings of threads.

[KoLiBer]

Condition::wait() method has a critical section at this->m_waiter++; and cannot work correctly