Semaphores for Ordering

This lesson discusses another use case of semaphores, as a way for ordering events in concurrent programs.

We'll cover the following

Semaphores are also useful to order events in a concurrent program. For example, a thread may wish to wait for a list to become non-empty, so it can delete an element from it. In this pattern of usage, we often find one thread waiting for something to happen, and another thread making that something happen and then signaling that it has happened, thus waking the waiting thread. We are thus using the semaphore as an ordering primitive (similar to our use of condition variables earlier).

A simple example is as follows. Imagine a thread creates another thread and then wants to wait for it to complete its execution.

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

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

sem_t s;

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

int main(int argc, char *argv[]) {
    sem_init(&s, 0, X); 
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    sem_wait(&s); // wait here for child
    printf("parent: end\n");
    return 0;
}
A Parent Waiting For Its Child

When this program runs, we would like to see the following:

parent: begin
child
parent: end

The question, then, is how to use a semaphore to achieve this effect; as it turns out, the answer is relatively easy to understand. As you can see in the code, the parent simply calls sem_wait() and the child sem_post() to wait for the condition of the child finishing its execution to become true. However, this raises the question: what should the initial value of this semaphore be i.e. value of X?

(Again, think about it here, instead of reading ahead)

The value of X

The answer, of course, is that the value of the semaphore should be set to 0. Replace X with 0 in the above code and run again. There are two cases to consider. First, let’s assume that the parent creates the child but the child has not run yet (i.e., it is sitting in a ready queue but not running). In this case, presented below, the parent will call sem_wait() before the child has called sem_post(); you’d like the parent to wait for the child to run. The only way this will happen is if the value of the semaphore is not greater than 0; hence, 0 is the initial value. The parent runs, decrements the semaphore (to -1), then waits (sleeping). When the child finally runs, it will call sem_post(), increment the value of the semaphore to 0, and wake the parent, which will then return from sem_wait() and finish the program.

The second case, as shown below, occurs when the child runs to completion before the parent gets a chance to call sem_wait(). In this case, the child will first call sem_post(), thus incrementing the value of the semaphore from 0 to 1. When the parent then gets a chance to run, it will call sem_wait() and find the value of the semaphore to be 1; the parent will thus decrement the value (to 0) and return from sem_wait() without waiting, also achieving the desired effect.

ASIDE: SETTING THE VALUE OF A SEMAPHORE

We’ve now seen two examples of initializing a semaphore. In the first case, we set the value to 1 to use the semaphore as a lock; in the second, to 0, to use the semaphore for ordering. So what’s the general rule for semaphore initialization?

One simple way to think about it, thanks to Perry Kivolowitz, is to consider the number of resources you are willing to give away immediately after initialization. With the lock, it was 1, because you are willing to have the lock locked (given away) immediately after initialization. With the ordering case, it was 0, because there is nothing to give away at the start; only when the child thread is done is the resource created, at which point, the value is incremented to 1. Try this line of thinking on future semaphore problems, and see if it helps.

Get hands-on with 1400+ tech skills courses.