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
waitandpostaround 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
waitclaims a unit, sleeping if none is free, andpostreturns 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.