CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 6 of 7 · 5 min read

The invariant

Building one and reasoning about it

In plain words: A semaphore can be built from a mutex, a condition variable and an integer, using exactly the patterns of pages 3 and 4. The count is the shared data, and the condition variable holds the sleepers:

typedef struct { int value; pthread_mutex_t mu; pthread_cond_t cv; } zsem;

void z_wait(zsem *s) {
    pthread_mutex_lock(&s->mu);
    while (s->value <= 0) pthread_cond_wait(&s->cv, &s->mu);   /* the loop of page 4 */
    s->value--;
    pthread_mutex_unlock(&s->mu);
}
void z_post(zsem *s) {
    pthread_mutex_lock(&s->mu);
    s->value++;
    pthread_cond_signal(&s->cv);
    pthread_mutex_unlock(&s->mu);
}

Four threads, each doing 500,000 wait-and-post pairs around an increment with this binary semaphore (value 1), reached exactly 2,000,000, in 0.38 s. The library sem_t uses a futex directly and is faster, but the construction shows that the semaphore needs nothing beyond the earlier tools. The reverse is also possible but awkward: a condition variable built from semaphores is hard to get right.

Reasoning about a semaphore uses an invariant, something that is true at every moment: the value equals the initial value, plus the number of completed posts, minus the number of completed waits, and it is never negative. From it follow the facts used so far. With an initial value of 1, the number of threads inside the critical section is at most 1: each one completed a wait without its matching post, and the difference cannot exceed 1. With an initial value of n, at most n threads are inside.

The POSIX calls:

Call Job
sem_init(&s, 0, n) Set up a semaphore for threads of one process, with value n
sem_wait(&s) Wait operation; may return -1 with EINTR if a signal arrives
sem_trywait(&s) Take a unit if one is free; otherwise return -1 with EAGAIN
sem_timedwait(&s, &abs_time) Wait, but give up at an absolute time with ETIMEDOUT
sem_post(&s) Post operation; safe to call from a signal handler
sem_destroy(&s) Free a semaphore no thread uses

sem_wait can be interrupted by a signal, so programs that use signals loop on EINTR. A named semaphore (sem_open) is shared between processes, for communication between unrelated programs.

Semaphore invariant

The semaphore invariant is the rule that, at every moment, a semaphore's value equals its initial value plus the number of completed posts minus the number of completed waits, and is never negative, which bounds the number of threads that can be past a wait without a matching post.

Example: a semaphore that starts at 3, with 5 completed waits and 2 completed posts, has the value 0: 3 + 2 − 5.

Common mistake

Using a semaphore with value 1 as a signal. A signal needs the initial value 0. A value of 1 lets the first wait pass at once, before the event has happened.

Interview angle

Answer in your head first, then open it.

What is a semaphore?

A non-negative counter with atomic wait (decrease, sleeping at zero) and post (increase, waking one).

What is the difference between a mutex and a binary semaphore?

A mutex has an owner and error checking. A semaphore has no owner and can signal between threads.

How would you limit a program to 10 concurrent database connections?

A counting semaphore initialised to 10.

What does a semaphore initialised to 0 do?

It orders events: the waiter sleeps until another thread posts.

Can you build a semaphore from a mutex and a condition variable?

Yes: a counter protected by the mutex, with a wait loop on the condition variable.

Check yourself: 1. What is the value after initial 4, 7 completed posts and 9 completed waits? 2. Why does sem_wait need a loop on EINTR? 3. Why can the invariant never allow a negative value?

Words you will meet

Word Meaning
Semaphore A non-negative counter with atomic wait and post
P and V Dijkstra's names for wait and post
Binary semaphore A semaphore used with 0 and 1, for exclusion
Counting semaphore A semaphore that counts available units
Rendezvous A point where all threads must arrive before any goes on
Invariant A fact that is true at every moment
Named semaphore A semaphore shared between processes by a name

Quick notes

  • A semaphore is a non-negative integer, changed only by the atomic operations wait (decrease the value, sleeping first if it is zero) and post (increase the value and wake a.
  • A binary semaphore is a semaphore used with the values 0 and 1 only, initialised to 1, so that wait and post around a critical section give mutual exclusion, but which, unlike a mutex, has no owner.
  • A counting semaphore is a semaphore whose initial value is the number of identical units of a resource that are available, so that wait claims a unit, sleeping if none is free, and post returns one.
  • A rendezvous is a synchronisation point at which two or more threads must all arrive before any of them continues, implemented for two threads with two semaphores initialised to 0.
  • The semaphore invariant is the rule that, at every moment, a semaphore's value equals its initial value plus the number of completed posts minus the number of completed waits, and.