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?

Brevier

Answer 1

One way of implementing X given semaphores is to add a server process to the system, use semaphores to communicate with it, and have the process do all the hard work of implementing X. As an academic exercise, this might be cheating, but it does get the job done, and it can be more robust to misbehaviour by the client processes, or to their sudden death.

Invitation

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

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

Answer 2

I may be missing something here, but there seem to be a simpler way to implement a Condition from a Semaphore and Lock than the way described in the paper.

class Condition {
    sem_t m_sem;
    int   m_waiters;
    int   m_signals;
    pthread_mutex_t *m_mutex;
public:

    Condition(pthread_mutex_t *_mutex){
        sem_init(&this->m_sem,0,0);
        this->m_waiters = 0;
        this->m_signals = 0;
        this->m_mutex = _mutex;
    }
    ~Condition(){}
    void wait();
    void signal();
    void broadcast();
};

void Condition::wait() {
    this->m_waiters++;
    pthread_mutex_unlock(this->m_mutex);
    sem_wait(&this->m_sem);
    pthread_mutex_lock(this->m_mutex);
    this->m_waiters--;
    this->m_signals--;
}

void Condition::signal() {
    pthread_mutex_lock(this->m_mutex);
    if (this->m_waiters && (this->m_waiters > this->m_signals)) {
        sem_post(&this->m_sem);
        this->m_signals++;
    }
    pthread_mutex_unlock(this->m_mutex);
}

Oscar

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. – Amann

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