Semaphores

01 Introduction

Lesson 6.3 presented the lock: a synchronization primitive with two operations, acquire and release, whose only purpose is to guarantee mutual exclusion. A lock is the right tool when the problem is to protect a critical section, but it is not general enough for every synchronization need. Consider two problems that a lock cannot solve cleanly.

• Signalling. A thread must wait until another thread has completed some action — for example, a consumer must wait until a producer has placed an item in a buffer. A lock can express the mutual exclusion on the buffer, but it cannot express the condition "wait until the buffer is non-empty". A busy-wait loop under a lock would deadlock, because the consumer would hold the lock while waiting for the producer, and the producer would be unable to acquire the lock to make the buffer non-empty.
• Counting. A pool of resources has a fixed number of units available — say, ten database connections. A thread must wait if no unit is free and proceed when one is. A lock can express "at most one thread at a time", but not "at most ten threads at a time".

Both problems are solved by the semaphore, introduced by Edsger Dijkstra in 1965. A semaphore is an integer variable with two atomic operations — traditionally called P and V, from the Dutch words proberen (to test) and verhogen (to increment). The value of the semaphore can be any non-negative integer, and it typically represents the number of available units of a resource, or the number of threads waiting for a condition to become true.

This lesson presents the semaphore in its full generality. It defines the two operations and their semantics, shows how a binary semaphore (one restricted to the values 0 and 1) is equivalent to a lock, and then shows how a counting semaphore solves problems that a lock cannot. The central example is the bounded-buffer producer–consumer problem, which uses three semaphores to coordinate an arbitrary number of producers and consumers through a fixed-size buffer. The lesson also covers the reader–writer problem, the POSIX semaphore interface, and the classic pitfalls — forgetting to signal, signalling too many times, and the deadlocks that arise from acquiring semaphores in the wrong order.

02 Learning objectives

This lesson contributes to U6.3 and U6.4, and to course learning outcomes CLO2, CLO3, and CLO8.

03 Required reading

• Operating System Concepts — Chapter 6, Sections 6.6–6.8, Semaphores, Classic Problems of Synchronization, and Monitors (the first part). The standard treatment of the semaphore, the producer–consumer problem, and the reader–writer problem.
• OSTEP — Chapter 31, Semaphores. The clearest available treatment of the semaphore as a general synchronization primitive. OSTEP's use of the semaphore to solve the producer–consumer and reader–writer problems is the basis for the worked example in this lesson.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.3.4, Semaphores, and Section 2.3.5, Mutexes. A complementary treatment that places semaphores in the historical context of the 1960s.
• Dijkstra, E. W. — Cooperating Sequential Processes. In Programming Languages, ed. F. Genuys, Academic Press, 1968. The original paper introducing the semaphore and the P and V operations.
• Linux man pages: man 7 sem_overview, man 3 sem_init, man 3 sem_wait, man 3 sem_post, man 3 sem_destroy, man 3 sem_open, man 3 sem_close, man 3 sem_unlink, man 3 sem_getvalue.

04 Core content

4.1 The semaphore abstraction

A semaphore is an integer variable that, apart from initialization, can be accessed only through two atomic operations:

P(s) — also called wait(s), down(s), or acquire(s)

If s > 0, decrement s and return immediately. If s == 0, block the calling thread until s becomes positive, then decrement s and return. The operation is atomic: no other thread can observe an intermediate state or interleave its own P or V with this one.

V(s) — also called signal(s), up(s), or release(s)

Increment s by 1. If one or more threads are blocked in P on s, wake one of them. The operation is atomic.

The value of a semaphore has a natural interpretation that depends on how it is used. In a counting semaphore, the value is the number of units of a resource currently available: a thread calls P to take a unit (blocking if none is available) and V to return a unit. The value ranges from 0 to some initial maximum, and it never goes negative. In a binary semaphore, the value is restricted to 0 or 1, and the semaphore acts as a lock: P is acquire and V is release.

4.2 Busy-waiting and blocking implementations

The P and V operations can be implemented in two ways. The busy-waiting implementation uses the spinlock machinery from Lesson 6.3:

void P(sem_t *s) {
    while (s->value <= 0)
        ;                       /* spin */
    s->value--;
}

void V(sem_t *s) {
    s->value++;
}

This implementation is simple but has the same drawbacks as the spinlock: it wastes CPU cycles, and the P operation must be atomic (typically implemented with a lock inside the semaphore), which means it is not as simple as it appears. In practice, this implementation is used only in kernel code where spinning is appropriate.

The blocking implementation is what the POSIX semaphore provides. The semaphore has a value and a queue of blocked threads. P decrements the value if it is positive; otherwise, it adds the caller to the queue and blocks. V increments the value and, if the queue is non-empty, removes one thread from it and makes it ready. The waiting thread consumes no CPU while it is blocked.

A well-implemented blocking semaphore uses a hybrid design similar to the futex: the uncontended fast path is handled in user space, and the kernel is involved only when the semaphore must block a thread or wake one. This is the design of the POSIX semaphore in glibc.

4.3 Binary semaphores and mutual exclusion

A binary semaphore is a semaphore whose value is restricted to 0 or 1. It is initialized to 1, and it is used to enforce mutual exclusion:

sem_t mutex;
sem_init(&mutex, 0, 1);     /* initial value 1 */

/* Critical section */
sem_wait(&mutex);          /* P: take the lock */
counter++;
sem_post(&mutex);          /* V: release the lock */

The first thread to call sem_wait finds the value 1, decrements it to 0, and enters the critical section. A second thread calling sem_wait finds the value 0 and blocks. When the first thread calls sem_post, the value becomes 1 and the second thread is woken. This is exactly the behaviour of a lock; a binary semaphore and a mutex are functionally equivalent for mutual exclusion.

There is one difference worth noting. A lock is owned by the thread that holds it: only the holding thread can release a mutex. A binary semaphore has no ownership: any thread can call V on it, regardless of which thread called P. This makes semaphores more flexible — they can be used for signalling, as we will see — but it also makes them more error-prone: a thread that accidentally signals a semaphore it did not wait on can corrupt the protocol.

4.4 Using a semaphore for signalling

The second use of the semaphore is signalling: one thread waits for another to complete an action. A semaphore is initialized to 0 and used as a one-shot signal:

sem_t done;
sem_init(&done, 0, 0);

/* Thread A — the worker */
do_work();
sem_post(&done);           /* signal completion */

/* Thread B — the waiter */
sem_wait(&done);           /* wait for the signal */
use_result();

If thread B reaches sem_wait before thread A reaches sem_post, B blocks. When A posts, B is woken. If B reaches sem_wait after A has already posted, the semaphore's value is 1, so B does not block; it decrements the value to 0 and proceeds. The order of the two operations does not matter: the signal is remembered.

This is the key property that a lock cannot provide. With a lock, the waiter must acquire before the releaser releases, or the release has no effect. With a semaphore used for signalling, the post is remembered as an increment to the value, and the wait consumes it. This is the basis of the producer–consumer and reader–writer solutions.

4.5 The bounded-buffer producer–consumer problem

The producer–consumer problem (also called the bounded-buffer problem) is the canonical synchronization problem. One or more producers generate items and place them in a shared buffer of fixed size; one or more consumers remove items from the buffer and process them. The buffer is a circular array of N slots with two indices, in and out.

Three synchronization problems must be solved:

• A producer must not insert into a full buffer. It must wait until a slot is free.
• A consumer must not remove from an empty buffer. It must wait until an item is available.
• The buffer's indices and contents must be accessed mutually exclusively. Two producers must not both write to the same slot, and a consumer must not read a slot while a producer is writing it.

The classical solution uses three semaphores:

sem_t empty;    /* counts empty slots, initialized to N */
sem_t full;     /* counts filled slots, initialized to 0 */
sem_t mutex;    /* protects the buffer structure, initialized to 1 */

The producer's loop is:

do {
    item = produce();
    sem_wait(&empty);      /* wait for a free slot */
    sem_wait(&mutex);      /* enter the critical section */
    buffer[in] = item;
    in = (in + 1) % N;
    sem_post(&mutex);      /* leave the critical section */
    sem_post(&full);       /* announce a new item */
} while (1);

The consumer's loop is the mirror image:

do {
    sem_wait(&full);       /* wait for an item */
    sem_wait(&mutex);      /* enter the critical section */
    item = buffer[out];
    out = (out + 1) % N;
    sem_post(&mutex);      /* leave the critical section */
    sem_post(&empty);      /* announce a free slot */
    consume(item);
} while (1);

The empty and full semaphores perform the signalling: a producer waits on empty until a slot is free, and posts to full when it has produced an item; a consumer does the opposite. The mutex semaphore performs the mutual exclusion on the buffer structure.

4.6 Why the order of the waits matters

The producer–consumer solution is a standard example in every operating-systems textbook, and the most common mistake is to reverse the order of the two waits in the producer:

/* WRONG */
sem_wait(&mutex);      /* enter critical section first */
sem_wait(&empty);      /* then wait for a free slot */
...

This version deadlocks. Suppose the buffer is full and a producer reaches sem_wait(&mutex). It acquires the mutex and then calls sem_wait(&empty), which blocks because there are no free slots. The producer now holds the mutex while it is blocked. A consumer arrives, calls sem_wait(&full) — which succeeds, because there are filled slots — and then calls sem_wait(&mutex), which blocks because the producer holds it. The consumer cannot remove an item, so the producer cannot proceed. Both are blocked, and the system makes no progress.

The correct order — wait on the counting semaphore first, then on the mutex — avoids the deadlock because the producer does not hold the mutex while it is waiting for a slot. The general rule is: acquire semaphores in order of decreasing scope. The counting semaphores are the outermost resource; the mutex is the innermost. Wait for the outermost first.

4.7 The reader–writer problem

The reader–writer problem is a second classic synchronization problem. A shared data structure is accessed by two kinds of threads: readers, which only read it, and writers, which modify it. Multiple readers can access the structure simultaneously, because reading does not modify it; a writer must have exclusive access, because it changes the structure while others may be reading it.

The synchronization requirements are:

• Any number of readers may read simultaneously.
• At most one writer may write at a time.
• A writer must not write while any reader is reading.
• A reader must not read while a writer is writing.

A semaphore solution uses a binary semaphore wrt (for "write") that is held by a writer and by the readers collectively, and a counting semaphore mutex that protects a reader count:

sem_t wrt;      /* initialized to 1 */
sem_t mutex;    /* initialized to 1, protects read_count */
int read_count = 0;

/* Writer */
sem_wait(&wrt);
/* write the data structure */
sem_post(&wrt);

/* Reader */
sem_wait(&mutex);
read_count++;
if (read_count == 1)
    sem_wait(&wrt);       /* first reader locks out writers */
sem_post(&mutex);

/* read the data structure */

sem_wait(&mutex);
read_count--;
if (read_count == 0)
    sem_post(&wrt);       /* last reader lets writers in */
sem_post(&mutex);

The first reader acquires wrt, which blocks any writer. Subsequent readers increment the count and proceed without touching wrt. The last reader releases wrt, allowing a writer to proceed. The mutex semaphore protects the count so that the increments and decrements are atomic.

This solution is reader-preferring: a writer that arrives while readers are active must wait until all current readers have finished. If new readers keep arriving, the writer can wait indefinitely — a starvation problem. A writer-preferring variant gives writers priority: once a writer is waiting, new readers must wait until the writer has completed. A third variant gives neither side priority and relies on the scheduler for fairness.

4.8 POSIX semaphores

POSIX defines two kinds of semaphore: unnamed semaphores, which live in memory and are shared between threads of the same process (or between processes via a shared memory region), and named semaphores, which are identified by a name in the file system and can be shared between unrelated processes.

The unnamed interface is:

#include <semaphore.h>

sem_t s;

sem_init(&s, pshared, value);
    /* pshared = 0: shared between threads of one process */
    /* pshared = 1: shared between processes (via shared memory) */
    /* value: the initial value of the semaphore */

sem_wait(&s);      /* P */
sem_post(&s);      /* V */

sem_getvalue(&s, &val);   /* read the current value (best-effort) */

sem_destroy(&s);   /* release the semaphore */

The named interface uses the file system:

sem_t *s = sem_open("/my_sem", O_CREAT, 0644, 1);
sem_wait(s);
sem_post(s);
sem_close(s);
sem_unlink("/my_sem");     /* remove the name */

Named semaphores are useful for synchronizing unrelated processes, for example a client and a server, or two command-line tools that share a resource. Unnamed semaphores are the right choice for threads within a single process, and they are slightly faster because they do not involve the file system.

The POSIX implementation in glibc uses a futex-like design: the value of the semaphore is stored in user space, and the kernel is involved only when a thread must block or be woken. An uncontended sem_wait or sem_post is a small number of atomic instructions; a contended one enters the kernel.

4.9 Common pitfalls

Semaphores are flexible but unforgiving. Because they have no ownership semantics and no type checking, mistakes produce subtle bugs that are hard to diagnose. The following are the most common.

4.10 Semaphores versus locks and condition variables

It is worth placing the semaphore in the context of the other primitives in this unit.

The semaphore is the most general of these primitives. It can do everything a mutex can (a binary semaphore used for mutual exclusion), and it can do things a mutex cannot (signalling, counting). Its flexibility is also its weakness: the same flexibility that allows a semaphore to solve many problems makes it easy to misuse. A mutex or a condition variable is more constrained, which makes the correct usage easier to see.

The general guidance in modern concurrent programming is: use a mutex for mutual exclusion, a condition variable for waiting on a condition, and a semaphore for the specific problems it solves best — signalling a one-shot event, counting the units of a resource, and the classic producer–consumer and reader–writer problems. Do not use a semaphore for mutual exclusion when a mutex is available: the ownership semantics of the mutex catch errors that a semaphore will silently allow.

4.11 Common misconceptions

05 Worked example

The following example traces the bounded-buffer producer–consumer solution through a sequence of operations, showing the values of all three semaphores and the state of the buffer at each step.

06 Interactive activity

07 Knowledge check

sem_wait(&empty);
sem_wait(&mutex);
buffer[in] = item;
in = (in + 1) % N;
sem_post(&mutex);
sem_post(&full);

sem_wait(&full);
sem_wait(&mutex);
item = buffer[out];
out = (out + 1) % N;
sem_post(&mutex);
sem_post(&empty);

08 Unit discussion

09 Practice exercise

10 Summary

• A semaphore is an integer variable with two atomic operations: P (wait) decrements the value or blocks, and V (signal) increments the value and wakes a blocked thread if any.
• A binary semaphore (values 0 and 1) is equivalent to a lock for mutual exclusion. A counting semaphore (any non-negative value) counts the available units of a resource.
• A semaphore has no ownership: any thread may signal. This is what makes it useful for signalling between threads, and it is what makes it easy to misuse.
• The signalling use of a semaphore is what distinguishes it from a lock: a signal posted before a wait is remembered in the value, so the wait does not block. A lock has no such memory.
• The bounded-buffer producer–consumer problem is solved with three semaphores: empty (free slots), full (filled slots), and mutex (buffer protection). The order of the waits is critical — the counting semaphore must be waited on before the mutex.
• Reversing the order of the waits in the producer or consumer causes a deadlock: the producer holds the mutex while blocked on empty, and the consumer cannot acquire the mutex to free a slot.
• The reader–writer problem is solved with a binary semaphore wrt and a counting semaphore mutex protecting a read_count. The first reader acquires wrt, the last releases it, and multiple readers proceed in between.
• The reader-preferring variant can starve writers; a writer-preferring variant uses an additional turnstile semaphore to give writers priority, at the cost of potentially starving readers.
• POSIX defines both unnamed semaphores (for threads within a process, or processes sharing memory) and named semaphores (for unrelated processes). The implementation is a hybrid similar to the futex: fast in user space, kernel-involved only under contention.
• Semaphores are more general than mutexes but also more error-prone. The classic pitfalls are forgetting to signal, signalling too many times, and reversing the order of the waits. Use a mutex when mutual exclusion is all you need.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 6, Sections 6.6–6.8.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 31. Available online at ostep.org.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Sections 2.3.4–2.3.5.
• Dijkstra, E. W. Cooperating Sequential Processes. In Programming Languages, ed. F. Genuys, Academic Press, 1968. The original paper introducing the semaphore.
• Courtois, P. J., Heymans, F., & Parnas, D. L. Concurrent Control with Readers and Writers. Communications of the ACM, 1971. The original reader–writer paper, including the writer-preferring variant.
• Love, R. Linux Kernel Development, 3rd ed., Chapter 9, Kernel Synchronization Methods. The Linux kernel's completion variables and reader-writer semaphores.
• Linux man-pages: man 7 sem_overview, man 3 sem_init, man 3 sem_wait, man 3 sem_post, man 3 sem_destroy, man 3 sem_open, man 3 sem_close, man 3 sem_unlink, man 3 sem_getvalue.