Semaphores: A Definition

This lesson covers the basics of semaphores and its two main routines.

We'll cover the following

A semaphore is an object with an integer value that we can manipulate with two routines; in the POSIX standard, these routines are sem_wait() and sem_post()Historically, sem_wait() was called P() by Dijkstra and sem_post() called V(). These shortened forms come from Dutch words; interestingly, which Dutch words they supposedly derive from has changed over time. Originally, P() came from “passering” (to pass) and V() from “vrijgave” (release); later, Dijkstra wrote P() was from “prolaag”, a contraction of “probeer” (Dutch for “try”) and “verlaag” (“decrease”), and V() from “verhoog” which means “increase”. Sometimes, people call them down and up. Use the Dutch versions to impress your friends, or confuse them, or both. See https://news.ycombinator.com/ item?id=8761539) for details.. Because the initial value of the semaphore determines its behavior, before calling any other routine to interact with the semaphore, we must first initialize it to some value, as the code below does.

Press + to interact
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

In the code, we declare a semaphore s and initialize it to the value 1 by passing 1 in as the third argument. The second argument to sem_init() will be set to 0 in all of the examples we’ll see; this indicates that the semaphore is shared between threads in the same process. See the man page for details on other usages of semaphores (namely, how they can be used to synchronize access across different processes), which require a different value for that second argument.

Semaphore routines

After a semaphore is initialized, we can call one of two functions to interact with it, sem_wait() or sem_post(). The behavior of these two functions is seen in the code excerpt below.

Press + to interact
int sem_wait(sem_t *s) {
    decrement the value of semaphore s by one
    wait if value of semaphore s is negative
}
int sem_post(sem_t *s) {
    increment the value of semaphore s by one
    if there are one or more threads waiting, wake one
}

For now, we are not concerned with the implementation of these routines, which clearly requires some care; with multiple threads calling into sem_wait() and sem_post(), there is the obvious need for managing these critical sections. We will now focus on how to use these primitives; later we may discuss how they are built.

We should discuss a few salient aspects of the interfaces here. First, we can see that sem_wait() will either return right away (because the value of the semaphore was one or higher when we called sem_wait()), or it will cause the caller to suspend execution waiting for a subsequent post. Of course, multiple calling threads may call into sem_wait(), and thus all be queued waiting to be woken.

Second, we can see that sem_post() does not wait for some particular condition to hold like sem_wait() does. Rather, it simply increments the value of the semaphore, and then, if there is a thread waiting to be woken, wakes one of them up.

Third, the value of the semaphore, when negative, is equal to the number of waiting threads“The Structure of the THE Multiprogramming System” by E.W. Dijkstra. CACM, volume 11(5), 1968. One of the earliest papers to point out that systems work in computer science is an engaging intellectual endeavor. Also argues strongly for modularity in the form of layered systems.. Though the value generally isn’t seen by users of the semaphores, this invariant is worth knowing and perhaps can help you remember how a semaphore functions.

Don’t worry (yet) about the seeming race conditions possible within the semaphore; assume that the actions they make are performed atomically. We will soon use locks and condition variables to do just this.

Get hands-on with 1400+ tech skills courses.