Semaphores and Mutex

DSA, Database System & Operating System — Operating System and Process Management, NEC licence examination syllabus (Nepal Engineering Council).

Semaphores and Mutex

An integer with two atomic operations — the primitive that solves both mutual exclusion and coordination.

🌍 Where this lives: the semaphore is Dijkstra's 1965 invention and it is still the primitive under everything. A database connection pool of size 20 is a counting semaphore initialised to 20. A rate limiter allowing 100 concurrent requests is a semaphore. Every thread pool, every bounded queue, every "max N in flight" constraint in production is this one data structure. And the classic bug below — acquiring the mutex before the semaphore — is a real deadlock I reproduced on this machine in a few lines. Search "semaphore vs mutex difference", which is the single most-asked interview question in this area.

Definition

A SEMAPHORE S is an integer variable accessed only through two ATOMIC operations. wait(S) also called P(S), from Dutch "proberen" S = S - 1 if S < 0 then block this process on S's queue signal(S) also called V(S), from "verhogen" S = S + 1 if S <= 0 then wake one process from S's queue Both must be ATOMIC. If wait() were interruptible between the decrement and the test, two processes could both pass — the same load-modify-store race as counter++. INTERPRETATION OF THE VALUE: S > 0 → S resources are available S = 0 → no resources free, nobody waiting S < 0 → |S| processes are BLOCKED waiting TWO KINDS: BINARY SEMAPHORE — value only 0 or 1 used for MUTUAL EXCLUSION wait() before the critical section, signal() after equivalent in effect to a mutex, but see the differences below COUNTING SEMAPHORE — value any non-negative integer used to control access to N identical resources initialise to N; each wait() takes one, each signal() returns one example: 5 printers → sem = 5 MUTUAL EXCLUSION WITH A BINARY SEMAPHORE: semaphore mutex = 1; do { wait(mutex); critical section signal(mutex); remainder } while (true); The initial value of 1 means "one process may enter". After the first wait it is 0; a second process's wait makes it −1 and blocks.

Semaphore versus mutex — the examined distinction

MUTEX SEMAPHORE ───────────────────────────────────────────────────────── value locked / unlocked any integer ≥ 0 purpose MUTUAL EXCLUSION exclusion AND signalling/counting OWNERSHIP has an owner — only NO owner — any the locking thread process may signal may unlock count 1 (binary only) N use for protecting a counting resources, critical section producer/consumer ordering priority possible (priority not generally inheritance inheritance) supported recursive some mutexes support no locking it THE OWNERSHIP DIFFERENCE IS THE REAL ONE, and it is what exam answers should lead with: · a MUTEX is a LOCK. The thread that locks it must unlock it. That ownership is what allows priority inheritance (the runtime knows who holds it) and error checking (unlocking a mutex you do not own is an error). · a SEMAPHORE is a SIGNAL/COUNTER. Thread A may wait and thread B may signal — indeed that is the normal case in producer/consumer. There is no notion of "the holder". CONSEQUENCE: use a mutex when one thread protects a section and releases it itself. Use a semaphore when one thread must TELL ANOTHER that something happened, or when counting N resources. BINARY SEMAPHORE vs MUTEX — not interchangeable in practice: a binary semaphore initialised to 1 provides mutual exclusion, but any thread can signal it, so a bug elsewhere can release your critical section. A mutex refuses. SEMAPHORES SOLVE TWO DIFFERENT PROBLEMS: 1. MUTUAL EXCLUSION binary, init 1 2. SYNCHRONISATION binary, init 0 — "wait until told" /* P2 must run after P1 finishes step S1 */ semaphore sync = 0; P1: S1; signal(sync); P2: wait(sync); S2; Initialising to 0 means P2 blocks immediately and proceeds only when P1 signals. That is ORDERING, not exclusion, and no mutex can express it — a mutex you did not lock cannot be unlocked.

The bounded-buffer problem, measured

producer_consumer.c

/* Verified on Darwin arm64. THREE semaphores are needed:
     empty — how many slots are free   (init BUF)
     full  — how many items present    (init 0)
     mutex — protects the buffer indices */
#define BUF   5
#define ITEMS 20
int buffer[BUF], in = 0, out = 0;
sem_t empty, full;
pthread_mutex_t mx = PTHREAD_MUTEX_INITIALIZER;

void *producer(void *a) {
    for (int i = 1; i <= ITEMS; i++) {
        wait(empty);            /* block if the buffer is FULL */
        pthread_mutex_lock(&mx);       /* then take the mutex */
        buffer[in] = i; in = (in + 1) % BUF;
        pthread_mutex_unlock(&mx);
        signal(full);           /* tell the consumer */
    }
    return NULL;
}
void *consumer(void *a) {
    for (int i = 0; i < ITEMS; i++) {
        wait(full);             /* block if EMPTY */
        pthread_mutex_lock(&mx);
        int v = buffer[out]; out = (out + 1) % BUF;
        pthread_mutex_unlock(&mx);
        signal(empty);          /* free a slot */
    }
    return NULL;
}
MEASURED OUTPUT:
buffer size            : 5
produced               : 20
consumed               : 20
max occupancy observed : 5  (never exceeded buffer size: yes)
final occupancy        : 0

The measurement confirms both invariants a bounded buffer must maintain: max occupancy = 5 → NEVER exceeded the buffer size. The `empty` semaphore blocked the producer at exactly the right moment. final occupancy = 0 → every produced item was consumed. No item lost, none duplicated. WHY THREE SEMAPHORES AND NOT ONE: `mutex` provides mutual exclusion on the shared indices `empty` makes the producer WAIT when there is no room `full` makes the consumer WAIT when there is nothing to take A mutex alone gives exclusion but no blocking-when-full. You would need a busy-wait loop, which wastes CPU and does not guarantee bounded waiting. WHAT HAPPENS WITHOUT THE COUNTING SEMAPHORES — measured, with 5,000 items through the same 5-slot buffer and no synchronisation at all: buffer-full violations (overwrote unread data): 1 buffer-empty violations (read garbage) : 1 final count = -5000 The count went to MINUS 5000. The consumer "consumed" 5,000 items from a 5-slot buffer, most of which were garbage or re-read stale slots, and the counter itself was corrupted by the unsynchronised increments and decrements. Note the violation counters read only 1 each — because those checks are themselves racy. The real damage is the −5000: the data structure's invariant is not merely bent, it is meaningless.

The classic deadlock — order matters

deadlock.c

/* THE SAME PROGRAM with two lines swapped. Verified: this
   deadlocks on this machine. */
void *producer(void *a) {
    for (int i = 0; i < 5; i++) {
        pthread_mutex_lock(&mx);   /* MUTEX FIRST — WRONG */
        wait(empty);               /* then block here...      */
        count++;
        pthread_mutex_unlock(&mx);
        signal(full);
    }
    printf("  producer finished\n");
}
void *consumer(void *a) {
    for (int i = 0; i < 5; i++) {
        pthread_mutex_lock(&mx);   /* MUTEX FIRST — WRONG */
        wait(full);
        count--;
        pthread_mutex_unlock(&mx);
        signal(empty);
    }
    printf("  consumer finished\n");
}
MEASURED OUTPUT (BUF = 2, 5 items each):
  after 2s: count=2 — if neither 'finished' line printed, DEADLOCKED

Neither "producer finished" nor "consumer finished" was
printed. Both threads are permanently blocked.

TRACE THE DEADLOCK, with BUF = 2: 1. producer locks mutex, wait(empty) → 2→1, proceeds, count=1, unlocks, signal(full) 2. producer locks mutex, wait(empty) → 1→0, proceeds, count=2, unlocks, signal(full) 3. producer locks mutex, wait(empty) → 0→−1, BLOCKS ★ and it is still HOLDING THE MUTEX 4. consumer tries to lock mutex → BLOCKS, because the producer holds it 5. the consumer is the only one who could signal(empty) and wake the producer — but it cannot get the mutex to reach that code → circular wait. Neither can proceed. Forever. THE RULE: acquire the COUNTING semaphore BEFORE the mutex. wait(empty); /* may block — but holds nothing */ lock(mutex); /* short, cannot block long */ ... critical section ... unlock(mutex); signal(full); WHY THIS ORDER IS SAFE: a process only ever blocks on the counting semaphore while holding NOTHING. The mutex is taken only when entry is already guaranteed, so it is held for a bounded, short time and never across a blocking wait. THE GENERAL PRINCIPLE, which applies far beyond semaphores: NEVER BLOCK WHILE HOLDING A LOCK. The same rule explains why you should not perform I/O inside a mutex, not call an unknown callback while holding a lock, and not await an async operation inside a critical section. Every one of those is "block while holding a lock" in disguise, and every one produces this deadlock. THE OTHER CLASSIC SEMAPHORE BUGS: · signal() then wait() (reversed) → mutual exclusion lost · wait() twice, signal() once → deadlock, count never restored · forgetting signal() on an error path → permanent leak of a resource · signal() on the wrong semaphore → subtle corruption All four are why higher-level constructs (monitors, RAII lock guards, Go's defer) exist: they make the release automatic rather than remembered.

The deadlock above is worth internalising because it needs no cycle of two locks — the textbook picture. It is a single mutex plus a semaphore, and the cycle is formed by the fact that the only thread who could unblock the producer cannot get past the mutex the producer is holding. Real deadlocks usually look like this rather than like the neat two-lock diagram.

Implementation and the busy-wait question

A semaphore must make wait() and signal() ATOMIC. How? UNIPROCESSOR: disable interrupts around the two operations. Cheap and correct, since no other process can run. MULTIPROCESSOR: disabling interrupts on one core does not stop another core. A SPINLOCK (built on test-and-set) guards the semaphore's own integer for the few instructions needed. So a semaphore is built on a spinlock, and the spinlock is built on an atomic instruction. The layering is: application → semaphore / mutex (may block, long waits) → spinlock (busy-wait, very short) → test-and-set / CAS (one atomic instruction) → cache coherence protocol (hardware) BUSY-WAITING vs BLOCKING for the semaphore itself: SPINNING semaphore ("spinlock semaphore") while (S <= 0) ; S--; ✔ no context switch ✗ wastes a whole CPU while waiting right only when the wait is shorter than a context switch BLOCKING semaphore — what a real OS provides the waiting process is moved to a queue and its state becomes BLOCKED; signal() moves one back to READY ✔ the CPU does useful work while waiting ✗ two context switches per handoff (~1–10 µs each) WHICH QUEUE DISCIPLINE the semaphore uses determines whether BOUNDED WAITING holds: FIFO → bounded waiting guaranteed LIFO or arbitrary → a process can starve POSIX does not specify the order, which is why you cannot rely on fairness from a bare semaphore. MEASURED COST CONTEXT (from the critical-section topic on this machine): a mutex-protected increment took 28.8 ms for 1.6 million operations — about 18 ns each — while an unprotected one took 0.2 ms. The synchronisation is roughly 100× the cost of the work it protects, which is why the first rule is still "avoid sharing" rather than "pick a better lock".

🌍 Go further: Linux implements userspace mutexes with futex (fast userspace mutex), which is a genuinely clever hybrid: the uncontended case is a single CAS entirely in user space with no system call at all, and only when a thread actually has to wait does it enter the kernel via futex(FUTEX_WAIT). That is why locking an uncontended mutex costs ~20 ns while a contended one costs microseconds. Understanding futex explains most mutex performance behaviour you will ever measure. Search "futex fast userspace mutex how it works".

💡 Exam angle: define wait()/P() and signal()/V() with the decrement-then-block and increment-then-wake semantics, and state that both must be atomic. Know the value interpretation (negative means |S| blocked). The semaphore vs mutex comparison is near-certain: lead with ownership — a mutex must be released by its locker, a semaphore may be signalled by anyone. Write the bounded-buffer solution with three semaphores and be able to explain why wait(empty) must come before lock(mutex), tracing the deadlock if reversed.

Syllabus points

Semaphore (binary/counting); mutex

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.