How to Implement Semaphores

Let's see how we can make a semaphore out of a lock and a condition variable.

We'll cover the following

Finally, let’s use our low-level synchronization primitives, locks, and condition variables, to build our own version of semaphores called … (drum roll here) … Zemaphores. This task is fairly straightforward, as you can see in the code snippet below.

Press + to interact
typedef struct __Zem_t {

    int value;

    pthread_cond_t cond;

    pthread_mutex_t lock;

} Zem_t;



// only one thread can call this

void Zem_init(Zem_t *s, int value) {

    s->value = value;

    Cond_init(&s->cond);

    Mutex_init(&s->lock);

}



void Zem_wait(Zem_t *s) {

    Mutex_lock(&s->lock);

    while (s->value <= 0)

        Cond_wait(&s->cond, &s->lock);

    s->value--;

    Mutex_unlock(&s->lock);

}



void Zem_post(Zem_t *s) {

    Mutex_lock(&s->lock);

    s->value++;

    Cond_signal(&s->cond);

    Mutex_unlock(&s->lock);

}

Explanation

In the code above, we use just one lock and one condition variable, plus a state variable to track the value of the semaphore. Study the code for yourself until you really understand it. Do it!

One subtle difference between our Zemaphore and pure semaphores as defined by Dijkstra is that we don’t maintain the invariant that the value of the semaphore, when negative, reflects the number of waiting threads; indeed, the value will never be lower than zero. This behavior is easier to implement and matches the current Linux implementation.

Curiously, building condition variables out of semaphores is a much trickier proposition. Some highly experienced concurrent programmers tried to do this in the Windows environment, and many different bugs ensued“Implementing Condition Variables with Semaphores” by Andrew Birrell. December 2004. An interesting read on how difficult implementing CVs on top of semaphores really is, and the mistakes the author and co-workers made along the way. Particularly relevant because the group had done a ton of concurrent programming; Birrell, for example, is known for (among other things) writing various thread-programming guides.. Try it yourself, and see if you can figure out why building condition variables out of semaphores is more challenging of a problem than it might appear.

You can try out the implementation of Zemaphore below:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#include "common.h"
#include "common_threads.h"
#include "zemaphore.h"

Zem_t s;

void *child(void *arg) {
    sleep(4);
    printf("child\n");
    Zem_post(&s); // signal here: child is done
    return NULL;
}

int main(int argc, char *argv[]) {
    Zem_init(&s, 0); 
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    Zem_wait(&s); // wait here for child
    printf("parent: end\n");
    return 0;
}

Get hands-on with 1400+ tech skills courses.