Semaphores

Counter Model and Two Operations

A semaphore stores an integer. Wait subtracts one; if the result becomes negative the caller is placed on a sleep queue. Post adds one and, if the queue is nonempty, wakes one sleeper. The absolute value of a negative count equals the number of sleeping threads. All updates must occur inside an atomic critical section, so a real implementation typically also needs a low-level lock.

Using a Semaphore as a Lock

Setting the counter to 1 yields mutual exclusion. The first wait succeeds and changes the count to 0; later waits block. The matching post restores the count to 1 and may wake a contender. Because only the two states “held/not held” are visible, this usage is often called a binary semaphore. Keep the critical section short to preserve concurrency.

Enforcing Order with Semaphores

Setting the counter to 0 lets one thread wait for a completion signal from another. The child posts after finishing its work; the parent blocks on wait until that signal arrives. The pattern avoids busy-waiting and is lighter than a condvar because no extra predicate check is required. Wake-up order among multiple waiters is implementation-defined, commonly FIFO.

Pitfalls

• Using a semaphore without calling sem_init is undefined behaviour.
• Initialising a lock semaphore to 0 makes the first thread block forever.

Minimum C11 · complete program · Download .c

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

#define N 1000

sem_t lock;
int shared = 0;

void *inc(void *arg) { (void)arg;
    for (int i = 0; i < N; i++) {
        sem_wait(&lock);
        shared++;
        sem_post(&lock);
    }
    return NULL;
}

int main(void) {
    pthread_t t[2];
    sem_init(&lock, 0, 1);
    for (int i = 0; i < 2; i++) {
        pthread_create(&t[i], NULL, inc, NULL);
    }
    for (int i = 0; i < 2; i++) {
        pthread_join(t[i], NULL);
    }
    printf("%d\n", shared);
    sem_destroy(&lock);
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror -pthread ostep-31-semaphores.c -o example && ./example

Expected result

2000

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

What initial value must a semaphore have to protect a critical section? What happens if it is wrongly set to 0?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.