4.5 Semaphores: Counting Semaphores, Binary Semaphores & Mutexes

Back to Operating Systems Notes

📚Module 04: Process Synchronization & ConcurrencyTopic 4.5⏱️15 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Technical Interviews

💡 Core Intuition

🍳 The Everyday Analogy: The Marina Slipmaster and Fleet Tokens

Imagine a busy coastal marina with a finite dock capacity guarded by a harbor Slipmaster (the Operating System):

Architecture Flow

The Marina Slipmaster Pass Analogy

Mapping marina slip tokens to Dijkstra's atomic semaphore operations

💡 Hover or click any card for deep-dive operational details

⛵Arrival

Boat Arrives at Dock

Invoke wait(S)

A boat requests permission to enter and anchor in an open slip.

→

Inspect Box

⚓Depletion

All Slips Occupied

Token Count S <= 0

When the token box reaches zero, incoming boats cannot dock.

→

Sleep or Wake

🌊Departure

Boat Exits Harbor

Invoke signal(S)

Departing boats return their token to the dock box.

• Binary Token ($S = 1$): When only one single boat can access the fueling dock at any instant. This enforces strict mutual exclusion.
• Counting Tokens ($S = k$): When the marina has $k$ identical docking slips. Up to $k$ boats enter simultaneously; the $(k+1)^{\text{th}}$ boat must wait until a slip is vacated.

---

💻 Bridging to Computer Science

In 1965, Dutch computer scientist Edsger W. Dijkstra introduced the Semaphore—a synchronization tool that eliminated the two-process limitation of Peterson's algorithm and provided an elegant, hardware-assisted foundation for solving the $n$-process critical section problem without wasting CPU clock cycles.

---

📑Table of Contents

• 💡 Core Intuition
• 📚 Core Deep-Dive & Concepts
  • 1. Semaphore Definition & Fundamental Primitives
  • 2. Solving the n-Process Critical Section Problem
  • 3. Types of Semaphores: Binary vs. Counting
  • 4. Eliminating Busy Waiting: Block & Wakeup Semaphores
  • 5. Enforcing Process Execution Ordering Using Semaphores
  • 6. Deadlock Hazard & The Semaphore Ordering Invariant
• 🏭 In The Real World: Production Case Study
  • PostgreSQL Connection Pooling with Counting Semaphores
• 🎯 Exam & Interview Pitfall Check

---

📚 Core Deep-Dive & Concepts

1. Semaphore Definition & Fundamental Primitives

Definition: A Semaphore $S$ is an integer variable that, apart from initialization, can be accessed only through two standard atomic operations: wait(S) and signal(S).

Historically, Dijkstra utilized Dutch terminology for these operations:

• wait(S) is termed $P(S)$ (from Dutch proberen, meaning "to test" or "to attempt").
• signal(S) is termed $V(S)$ (from Dutch verhogen, meaning "to increment").

/* Classical Busy-Waiting Semaphore Primitives */

void wait(Semaphore S) {
    while (S <= 0); // Busy wait (spin until S > 0)
    S--;
}

void signal(Semaphore S) {
    S++;
}

Atomicity Guarantee

The operations inside wait(S) and signal(S) are executed atomically without preemption:

1. The testing of the integer condition (S <= 0) and the subsequent decrement (S--) must execute as a single, indivisible hardware operation.
2. No two processes can execute wait(S) or signal(S) on the same semaphore concurrently.

---

2. Solving the $n$-Process Critical Section Problem

While Peterson's algorithm is mathematically limited to strictly $2$ processes, a semaphore provides a universal, scalable solution for an arbitrary number of $n$ concurrent processes ($P_0, P_1, \dots, P_{n-1}$).

To solve the critical section problem among $n$ processes, the semaphore is initialized to $1$: $\text{Semaphore } S = 1;$

/* Canonical n-Process Critical Section Solution */

void Pi() {
    while (true) {
        /* Initial Section */

        /* Entry Section */
        wait(S);

        /* === CRITICAL SECTION === */
        // At most one process executes here at any instant

        /* Exit Section */
        signal(S);

        /* Remainder Section */
    }
}

Synchronization Criteria Verification

1. Mutual Exclusion: Satisfied. Because $S$ is initialized to $1$, the first process calling wait(S) finds $S = 1$, decrements it to $0$, and enters the Critical Section. Any subsequent process calling wait(S) encounters $S = 0$, becomes trapped in the while (S <= 0) check, and cannot enter until the active process executes signal(S).
2. Progress: Satisfied. If no process is inside the Critical Section and multiple processes request entry, only processes competing in their Entry Section participate in the decision. A process executing in its Remainder Section has already executed signal(S) and cannot block other processes. The selection cannot be postponed indefinitely.
3. Bounded Waiting: Not Guaranteed in Basic Implementation. In a standard un-ordered spinlock semaphore, when signal(S) increments $S$ from $0$ to $1$, all spinning processes race to acquire it. The underlying CPU arbiter or scheduler may starve an unlucky process indefinitely.

---

3. Types of Semaphores: Binary vs. Counting

Semaphores are divided into two distinct functional categories based on their permissible value domain:

Binary Semaphore vs Counting Semaphore

Contrasting mutual exclusion locks against multi-unit resource allocation pools

Binary

Binary Semaphore (Mutex)

🔒

Dominant Architecture / DomainCritical Section Isolation (0 or 1)

• •Integer value is strictly restricted between 0 and 1.
• •Initialized to 1 to guarantee mutual exclusion across n processes.
• •Provides lock-like semantics: wait() locks, signal() unlocks.
• •Guarantees that at most one process executes inside the Critical Section.

"Ensures pure single-occupancy serialization over shared critical code."

Counting

Counting Semaphore

🔢

Dominant Architecture / DomainMulti-Instance Resource Pools (-∞ to +∞)

• •Integer value ranges over an unrestricted domain (-∞ to +∞).
• •Initialized to N, where N is the total available instances of a resource.
• •Each wait() allocates an instance; each signal() releases an instance.
• •Negative values indicate the exact number of blocked waiting processes.

"Throttles concurrent access across pools of finite physical hardware or buffers."

State Invariants for Counting Semaphores

When using counting semaphores with a waiting list:

• If $S > 0$: The value represents the exact number of free, available resource units.
• If $S = 0$: Exactly zero resource units are free, and no processes are waiting.
• If $S < 0$: Exactly zero resource units are free, and $|S|$ processes are currently blocked and waiting in the queue.

---

4. Eliminating Busy Waiting: Block & Wakeup Semaphores

The simple definition of wait(S) uses a busy-waiting while (S <= 0); loop. This wastes CPU cycles that other active processes could use for productive execution.

To overcome this, operating system kernels implement non-busy waiting (sleeping) semaphores using process state transitions (block() and wakeup()):

typedef struct {
    int value;
    struct process *list; // Queue of Process Control Blocks (PCBs)
} Semaphore;

void wait(Semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // No resources available: suspend the calling process
        add_this_process_to(S->list);
        block(); // Transition from RUNNING to WAITING state
    }
}

void signal(Semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // Processes are waiting in the queue: awaken one
        struct process *P = remove_process_from(S->list);
        wakeup(P); // Transition from WAITING to READY state
    }
}

Busy Waiting (Spinlock) vs Block-and-Wakeup Semaphore

Performance tradeoffs between CPU polling and kernel context-switch overhead

Spinlock

Busy Waiting Semaphore

🔄

Dominant Architecture / DomainLow-Latency & Multiprocessor Kernels

• •Continuously loops on the CPU core checking S <= 0.
• •Burns CPU cycles during the entire waiting interval.
• •Zero context-switch overhead; ideal when lock hold time is < 2 context switches.
• •Commonly used in kernel interrupt handlers where threads cannot sleep.

"Blazing fast for ultra-short critical sections on multicore machines."

Sleep Queue

Block & Wakeup Semaphore

💤

Dominant Architecture / DomainGeneral-Purpose User Space & I/O

• •Invokes block() system call to yield the CPU core immediately.
• •Process moves to WAITING queue; CPU is dispatched to productive jobs.
• •Incurs two context switches (one to sleep, one to resume).
• •Essential when critical sections involve disk, network, or long computations.

"Maximizes CPU utilization by putting blocked processes to sleep."

Numerical Trace of Block-and-Wakeup Mechanics

Consider a counting semaphore initialized to $S = 2$:

Step	Process Action	$S\to\text{value}$	Action Taken	Blocked Queue (S->list)
0	Initial State	$2$	Semaphore initialized with 2 resource tokens	Empty []
1	$P_1$ calls wait(S)	$1$	$S\to\text{value} \ge 0 \implies$ Granted access	Empty []
2	$P_2$ calls wait(S)	$0$	$S\to\text{value} \ge 0 \implies$ Granted access	Empty []
3	$P_3$ calls wait(S)	$-1$	$S\to\text{value} < 0 \implies$ $P_3$ blocked	[P3]
4	$P_4$ calls wait(S)	$-2$	$S\to\text{value} < 0 \implies$ $P_4$ blocked	[P3, P4]
5	$P_1$ calls signal(S)	$-1$	$S\to\text{value} \le 0 \implies$ Awaken $P_3$	[P4] ($P_3$ moved to Ready)
6	$P_2$ calls signal(S)	$0$	$S\to\text{value} \le 0 \implies$ Awaken $P_4$	Empty [] ($P_4$ moved to Ready)
7	$P_3$ calls signal(S)	$1$	$S\to\text{value} > 0 \implies$ No processes waiting	Empty []

---

5. Enforcing Process Execution Ordering Using Semaphores

Semaphores are not merely locking primitives; they are general-purpose coordination primitives capable of enforcing arbitrary execution orders among asynchronous processes.

Problem Specification

Suppose three concurrent processes $P_1, P_2, P_3$ execute concurrently. Enforce the strict execution sequence: $P_2 \longrightarrow P_3 \longrightarrow P_1$

Mathematical Construction

To force a process to pause until an asynchronous prerequisite completes, we initialize signaling semaphores to $0$: $\text{Semaphore } S_1 = 0, \quad S_2 = 0;$

/* Process Coordination Blueprint */

void P1() {
    wait(S2);        // Blocked until P3 signals S2
    execute_code_1();
}

void P2() {
    execute_code_2(); // Executes immediately (first)
    signal(S1);      // Unblocks P3
}

void P3() {
    wait(S1);        // Blocked until P2 signals S1
    execute_code_3();
    signal(S2);      // Unblocks P1
}

Process Execution Order: P2 -> P3 -> P1

Tracing how zero-initialized semaphores establish deterministic ordering

Process P2

Semaphore S1 (init: 0)

Process P3

Semaphore S2 (init: 0)

Process P1

1

Process P1→Semaphore S2 (init: 0)

P1 invokes wait(S2)

2

Process P3→Semaphore S1 (init: 0)

P3 invokes wait(S1)

3

Process P2→Process P2

P2 executes execute_code_2()

4

Process P2→Semaphore S1 (init: 0)

P2 invokes signal(S1)

5

Process P3→Process P3

P3 executes execute_code_3()

6

Process P3→Semaphore S2 (init: 0)

P3 invokes signal(S2)

7

Process P1→Process P1

P1 executes execute_code_1()

---

6. Deadlock Hazard & The Semaphore Ordering Invariant

When processes must acquire multiple semaphores simultaneously, subtle bugs in the invocation order create catastrophic system deadlocks.

Suppose two processes $P$ and $Q$ require access to two shared resources protected by semaphores $S_1 = 1$ and $S_2 = 1$.

Crossed Semaphore Wait Order vs Identical Global Order

The fundamental rule for preventing deadlock when acquiring multiple semaphores

Fatal Flaw

Crossed Acquisition (Deadlock)

💀

Dominant Architecture / DomainCircular Wait Vulnerability

• •Process P calls wait(S1) then wait(S2).
• •Process Q calls wait(S2) then wait(S1).
• •If P acquires S1 and is preempted, Q acquires S2.
• •P blocks waiting for S2; Q blocks waiting for S1.
• •Both processes sleep permanently: Deadlock!

"Crossing semaphore acquisition orders produces an unavoidable circular dependency."

Correct Architecture

Identical Global Order (Deadlock-Free)

🛡️

Dominant Architecture / DomainHierarchical Resource Allocation

• •Process P calls wait(S1) then wait(S2).
• •Process Q calls wait(S1) then wait(S2).
• •If P acquires S1, Q blocks immediately on wait(S1).
• •P successfully acquires S2, enters CS, and exits.
• •Q unblocks and completes normally without deadlock.

"Imposing a total global order on wait() calls guarantees deadlock-free execution."

The Global Semaphore Order Invariant

The Semaphore Ordering Rule: To guarantee deadlock-free execution when multiple semaphores are involved, the order of executing wait operations across all concurrent processes must be strictly identical.

---

🏭 In The Real World: Production Case Study

PostgreSQL Connection Pooling with Counting Semaphores

In high-throughput relational databases like PostgreSQL, each client connection forks a dedicated backend operating system process. If 10,000 incoming HTTP requests spawn 10,000 backend processes, the server exhausts physical RAM and collapses under context-switching thrashing.

Architecture Flow

Database Connection Throttling via Counting Semaphores

Bounding concurrent worker processes to protect host memory and prevent scheduler thrashing

🌐Traffic Ingress

10,000 Web Requests

Concurrent client API requests arriving at application gateway.

→

Acquire Connection Permit

🛡️Admission Gate

PgBouncer Semaphore (S = 50)

Counting semaphore initialized to max server capacity of 50 active backend connections.

→

Permits 1..50 Granted

⚡Active Workers

PostgreSQL Database

Exactly 50 active processes executing queries at wire speed with zero context thrashing.

→

⏳Waiting Queue

Idle Wait Queue (9,950)

Remaining 9,950 connections sleep efficiently in kernel epoll waiting for released permits.

1. The Counting Semaphore Barrier: Production proxies (such as PgBouncer or HikariCP) wrap the database with a counting semaphore initialized to the database pool limit (e.g., $S = 50$).
2. Backpressure:
   • The first 50 incoming queries execute wait(pool_size), decrementing the semaphore to $0$, and execute queries at maximum NVMe disk throughput.
   • The $51^{\text{st}}$ through $10,000^{\text{th}}$ connections invoke wait(pool_size), driving $S$ to negative values ($-1, -2, \dots, -9950$).
   • Rather than spinning CPU cores, the OS puts these sockets to sleep in Linux epoll wait queues.
3. Releasing Tokens: As queries complete, database workers invoke signal(pool_size), waking up the queued queries sequentially.
4. Result: Zero database crashes, zero memory exhaustion, and sustained maximum query throughput.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: A counting semaphore $S$ is initialized to $7$. Subsequently, $20$ wait(S) operations and $15$ signal(S) operations are executed on $S$. What is the final value of $S$, and how many processes are blocked in the waiting queue? Answer:

1. Mathematical Invariant: $\text{Final Value} = S_{\text{init}} + N_{\text{signal}} - N_{\text{wait}}$ $\text{Final Value} = 7 + 15 - 20 = 22 - 20 = +2$
2. Blocked Queue Analysis:
   • Because the final value is $+2$ ($S > 0$), there are $0$ blocked processes.
   • Exactly $2$ resource units remain available for future requests.

Question 2: A counting semaphore $S$ is initialized to $10$. An arbitrary sequence of operations leaves the semaphore with a value of $-6$. How many processes are currently blocked waiting on this semaphore? Answer: When a block-and-wakeup counting semaphore has a negative value ($S < 0$), the absolute magnitude $|S|$ represents the exact number of processes blocked in the semaphore queue S->list. $\text{Blocked Processes} = |-6| = 6\text{ processes}$

Common Interview Traps

• The "Semaphore Value Cannot Be Negative" Trap: In classical busy-waiting semaphores (Dijkstra's original definition), $S$ never drops below zero because while (S <= 0); blocks before decrementing. However, in modern operating system block-and-wakeup implementations, $S$ decrements before checking: S->value--; if (S->value < 0) block();. Therefore, $S$ can be negative, and its absolute value denotes the count of sleeping processes.
• Confusing Binary Semaphores with Mutexes: While a binary semaphore can function as a mutex, a true Mutex enforces ownership: only the specific thread that acquired the mutex can release it. A binary semaphore has no ownership: Process $A$ can execute wait(S) and Process $B$ can execute signal(S) (as required in process ordering patterns).
• The Inverted Wait Order Deadlock: Never allow two processes to acquire two semaphores in opposite order (wait(A); wait(B); vs wait(B); wait(A);). This is the classic deadlock pattern tested in interviews.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic4.4 Hardware Synchronization: TSL & SwapNext Topic →4.6 Classical Synchronization: Producer-Consumer