Mutexes, Condition Variables, and Semaphores are Equivalent

Introduction

If you have actual experience in multithreading, you are probably aware of mutexes, condition variables, or semaphores. These are the so-called synchronization primitives.

You may not be familiar with all of them, but most multithreading environments provide at least one of them. The pthread API includes the mutex and the condition variable; the semaphore is present in both System V and POSIX. The 3 synchronization primitives are not the only possible synchronization primitives, for example, there are also channels in Golang, and event objects in Win32.

There are many materials explaining how to use a particular primitive and the difference between different primitives. However, for beginners, it is important to know, that all the primitives are equivalent in power — in other words, what can be done in with a particular primitive can also be done with another one.

If this idea is new to you, the rest of the post will further your understanding by implementing one synchronization primitive with another one, using pseudo code.

The Semaphore and the Mutex

A semaphore is an integer, there are two operations on a semaphore:

1. Increasing its value via sem_post.
2. Decreasing its value via sem_wait.

The value never goes below zero, the sem_wait blocks the calling thread when the value is zero until the value is later increased by a sem_post.

The semaphore can be trivially used as a mutex:

struct mutex_t {
    semaphore_t sem;
};

void mutex_init(mutex_t &mu) {
    // the initial value of 1.
    sem_init(mu.sem, 1);
}
void mutex_lock(mutex_t &mu) {
    sem_wait(mu.sem);
    // success, the value is now 0.
}
void mutex_unlock(mutex_t &mu) {
    sem_post(mu.sem);
    // restored the value from 0 to 1, and possibly woke up a sleeping thread.
}

The Condition Variable and the Semaphore

The two operations of a condition variable:

1. Put the calling thread to sleep via cond_wait.
2. Wake up a sleeper via cond_signal if there are any.

The condition variable is always used with a mutex — the mutex protects the “condition”! But the mutex must be released when the cond_wait put a thread to sleep so the condition can be changed later; thus, the cond_wait takes a mutex as an argument.

Implementing the semaphore with a condition variable is still obvious:

struct semaphore_t {
    mutex_t mu;
    cond_t cond;
    uint64_t value;
};

void sem_init(semaphore_t &sem, uint64_t value) {
    mutex_init(sem.mu);
    cond_init(sem.cond);
    sem.value = value;
}

void sem_post(semaphore_t &sem) {
    mutex_lock(sem.mu);
    sem.value += 1;
    if (sem.value == 1) {
        // from 0 to 1, there might be sleeping threads,
        // try to wake up one.
        cond_signal(sem.cond);
    }
    mutex_unlock(sem.mu);
}

void sem_wait(semaphore_t &sem) {
    mutex_lock(sem.mu);
    while (sem.value == 0) {
        // the cond_wait releases the sem.mu and
        // put the thread to sleep in a single operation.
        cond_wait(sem.cond, sem.mu);
        // the sem.mu is acquired again after the cond_wait.
    }
    sem.value -= 1;
    mutex_unlock(sem.mu);
}

Note that the cond_wait is always used inside a loop checking for the condition, because, by the time a thread wakes up, the condition could be already changed (by another thread) before it acquires the mutex again.

The Condition Variable Implemented With Only Mutexes

This is tricky and slightly more complicated than the previous sections. Think of solutions before revealing the answer!

struct sleeper_t {
    // part of a list
    sleeper_t *next;
    // for waking up myself
    mutex_t alarm;
};

struct cond_t {
    // for the protection of the cond_t itself
    mutex_t self;
    // a list of sleepers
    sleeper_t *next;
};

void cond_init(cond_t &cond) {
    mutex_init(cond.self);
    cond.next = NULL;
}

void cond_signal(cond_t &cond) {
    mutex_lock(cond.self);
    if (cond.next) {
        // remove a sleeper from the waiting list.
        sleeper_t *s = cond.next;
        cond.next = cond.next.next;
        // and wake it up.
        mutex_unlock(s->alarm);
    }
    mutex_unlock(cond.self);
}

void cond_wait(cond_t &cond, mutex_t &mu) {
    // the alarm mutex is set to the locked state initially.
    sleeper_t s;
    mutex_init(s.alarm);
    mutex_lock(s.alarm);

    // put myself into the waiting list.
    mutex_lock(cond.self);
    s.next = cond.next;
    cond.next = &s;
    mutex_unlock(cond.self);

    // about to enter sleep, release the mu.
    mutex_unlock(mu);
    // sleeping by locking the locked alarm mutex again.
    mutex_lock(s.alarm);
    // waked up, acquire the mu again.
    mutex_lock(mu);

    // clean up
    mutex_unlock(s.alarm);
}

Conclusions

For a selected set of 3 synchronization primitives, we have implemented each primitive using the other primitives. This shows that their powers are at the same level, what can be done in with a particular primitive can also be done with another one.

If you understand some synchronization primitives, it is easy to understand other primitives as well.

Readers can try more exercises like this, for example:

1. Implement the Golang channel.
2. Condition variables or semaphores from Golang channels.
3. Read the documentation of the Event Objects from Win32, and think about how to use them instead of condition variables or semaphores.

While synchronization primitives are equivalent in power, there are still preferences when it comes to real projects. Many people prefer condition variables over semaphores because semaphores are not always obvious to use and can be pretty tricky sometimes, whereas condition variables are much more straightforward: just list the condition and wait for it.

Further Reading

If the idea of this post is new to you, you just discovered a hole in your understanding. And getting a random piece of knowledge from a random blog post doesn’t fill that hole.

There are many resources that can help you learn the basics of multithreading. Any decent operating system textbook will teach you this. Here is a good one you can read online. Once you learned the basics, the pthread manpages should be enough to put you into practice.

This post is inspired by an exercise from the “Build Your Own Redis” book.