{"title":"Semaphores","description":"","content":"Imagine you're managing a parking lot with 50 spaces. Cars can enter freely as long as spaces are available. \n\nAs the lot fills up, the sign at the entrance updates: “45 spaces available”, “12 spaces available”, and eventually “LOT FULL.” Once it is full, new cars cannot enter. They wait at the gate until a car leaves and a space opens up.\n\nThis is exactly how a **semaphore** works.\n\nA semaphore maintains a counter of available **permits**. Each thread must acquire a permit before it can proceed. When the thread finishes, it releases the permit back to the semaphore. If the counter reaches zero, any new thread that asks for a permit must wait until another thread releases one.\n\n\n\n\n\nThis is the key difference from a mutex:\n\n- A **mutex** is binary: locked or unlocked, so only one thread can enter at a time.\n- A **semaphore** generalizes the idea: it allows up to **N** threads to enter concurrently.\n\nThis makes semaphores the right tool when you need to limit concurrent access to a pool of resources, like database connections, API rate limits, or bounded buffers.\n\nIn this chapter, we'll explore how semaphores work internally, understand the difference between binary and counting semaphores, and see practical implementations.\n\n---\n\n# What is a Semaphore?\n\nA semaphore is a synchronization primitive built around a simple idea: maintain an integer count representing available \"permits,\" and provide atomic operations to acquire and release those permits.\n\n\n> **Real-World Analogy**\n>\n> The best way to understand this is through a concrete analogy. \n>\n> Picture a nightclub with a strict capacity limit of 100 people. A bouncer stands at the door with a clicker counter. Every time someone enters, the bouncer clicks \"in\" (decrementing the count). Every time someone leaves, the bouncer clicks \"out\" (incrementing the count). \n>\n> When the count hits zero, new guests must wait in line outside until someone leaves and frees up a spot.\n\n\nThe diagram below shows this in action. Three threads have successfully acquired permits from a semaphore initialized with 3 permits. Thread 4 arrives and wants to acquire, but no permits remain, so it must wait until one of the other threads releases.\n\n\n```mermaid\nflowchart LR\n subgraph Semaphore[\"Semaphore (permits=3)\"]\n P[Permit Pool
Available: 0]:::pool\n end\n\n T1[Thread 1
holding permit]:::t1 --> |acquired| P\n T2[Thread 2
holding permit]:::t2 --> |acquired| P\n T3[Thread 3
holding permit]:::t3 --> |acquired| P\n T4[Thread 4]:::waiting --> |waiting...| P\n\n P --> |release| OUT[Return permit
to pool]:::teal\n\n classDef t1 fill:#00ceff,stroke:#000,color:#000\n classDef t2 fill:#9775fa,stroke:#000,color:#000\n classDef t3 fill:#69db7c,stroke:#000,color:#000\n classDef waiting fill:#ffa94d,stroke:#000,color:#000\n classDef pool fill:#ffd43b,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nWhen Thread 1, 2, or 3 finishes its work and calls `release()`, the permit returns to the pool. At that point, Thread 4 wakes up, acquires the newly available permit, and proceeds.\n\n### The Two Core Operations\n\nFormally, a semaphore supports two atomic operations:\n\n- **acquire() / wait() / P():** Attempt to decrement the counter. If the counter is greater than zero, decrement it and return immediately. If the counter is zero, block the calling thread until another thread releases a permit.\n- **release() / signal() / V():** Increment the counter. If any threads are blocked waiting for permits, wake one of them up.\n\nThe letters P and V come from Dutch: \"proberen\" (to try/test) and \"verhogen\" (to increment). These names come from Edsger Dijkstra's original 1965 paper that introduced semaphores as a synchronization primitive. You'll see all three naming conventions (acquire/release, wait/signal, P/V) used in different languages and textbooks, but they all mean the same thing.\n\nThe key insight is that both operations are atomic. Between checking the counter and modifying it, no other thread can intervene. This atomicity is what makes semaphores safe for coordination.\n\n---\n\n# Binary vs Counting Semaphores\n\nSemaphores come in two flavors, distinguished by how many permits they manage.\n\n### Binary Semaphore (permits = 1)\n\nA binary semaphore has only two states: available (1) or taken (0). When a thread acquires the single permit, the semaphore transitions to the \"taken\" state. When that thread (or any thread) releases, it transitions back to \"available.\"\n\nThe state diagram below illustrates these two states and the transitions between them:\n\n\n```mermaid\nstateDiagram-v2\n [*] --> Available: initialized with permits=1\n\n Available --> Taken: acquire()\n Taken --> Available: release()\n\n classDef available fill:#69db7c,stroke:#000,color:#000\n classDef taken fill:#ff8787,stroke:#000,color:#000\n\n class Available available\n class Taken taken\n```\n\n\nStarting in the \"Available\" state, a thread calling `acquire()` moves the semaphore to \"Taken.\" While taken, any other thread calling `acquire()` will block. When any thread calls `release()`, the semaphore returns to \"Available\" and a waiting thread (if any) can proceed.\n\nBinary semaphores can be used for mutual exclusion (only one thread at a time), but as we'll see later, they differ from mutexes in important ways.\n\n### Counting Semaphore (permits = N)\n\nA counting semaphore allows up to N threads to hold permits simultaneously. As threads acquire permits, the count decreases. When the count reaches zero, additional threads must wait.\n\nThe state diagram below shows a counting semaphore initialized with 3 permits:\n\n\n```mermaid\nstateDiagram-v2\n [*] --> Three: initialized with permits=3\n\n Three --> Two: acquire()\n Two --> One: acquire()\n One --> Zero: acquire()\n Zero --> Waiting: acquire() blocks\n\n Zero --> One: release()\n One --> Two: release()\n Two --> Three: release()\n\n Waiting --> Zero: release() wakes waiter\n\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n\n class Three green\n class Two yellow\n class One orange\n class Zero,Waiting red\n```\n\n\nFollowing the diagram from left to right: the semaphore starts with 3 permits (green). Each `acquire()` decrements the count. After three acquires, we reach zero (red). A fourth `acquire()` enters the \"Waiting\" state, blocked until a `release()` occurs. When a thread releases, the count increments. If threads are waiting, one is woken to acquire the newly available permit.\n\n### When to Use Each\n\nThe choice between binary and counting semaphores depends on what you're trying to accomplish:\n\n\n| Type | Permits | Best For |\n|------|---------|----------|\n| Binary | 1 | Signaling between threads, simple synchronization gates |\n| Counting | N | Connection pools, rate limiting, bounded buffers, limiting concurrent operations |\n\n\nBinary semaphores shine when you need one thread to signal another that something has happened, like \"data is ready\" or \"initialization complete.\" Counting semaphores shine when you have a pool of interchangeable resources and want to limit how many threads can use them simultaneously.\n\n---\n\n# Use-Cases of Semaphores\n\nSemaphores are worth learning for three practical reasons. They solve real engineering problems, they unlock common coordination patterns, and they show up frequently in technical interviews.\n\nAt a high level, a semaphore is a tool for **controlling how many things can happen at the same time**. That makes it useful in two broad categories: **resource limiting** and **producer-consumer coordination**.\n\n### Resource Pool Management\n\nThe most common use of counting semaphores is limiting access to a pool of limited resources. Consider these scenarios:\n\n**Database connections:** Your application can hold at most 20 database connections. If 50 threads each try to open a connection simultaneously, you'll exhaust the pool and crash. A semaphore with 20 permits ensures only 20 threads can hold connections at once. The other 30 wait their turn.\n\n**Thread pool sizing:** When processing tasks in parallel, you often want to limit concurrency to match your CPU cores. A semaphore with 8 permits ensures at most 8 tasks run simultaneously, preventing CPU thrashing from excessive context switching.\n\n**API rate limiting:** External APIs often limit you to N requests per second. A semaphore helps enforce this limit locally before requests even leave your system, preventing expensive API errors.\n\n**File handles:** Operating systems limit how many files a process can open simultaneously. A semaphore protects against hitting this limit when processing many files concurrently.\n\nWithout semaphores in these scenarios, you risk resource exhaustion, cascading failures, and degraded performance under load.\n\n### Producer-Consumer Coordination\n\nSemaphores excel at coordinating producers and consumers with a bounded buffer between them. This is one of the classic problems in concurrent programming:\n\n- Producers create items and add them to a buffer\n- Consumers remove items from the buffer and process them\n- The buffer has a fixed capacity (can't hold unlimited items)\n- Producers must wait when the buffer is full\n- Consumers must wait when the buffer is empty\n\nTwo semaphores solve this elegantly: one tracks empty slots (so producers know when they can add), and one tracks filled slots (so consumers know when they can take). We'll implement this pattern in detail later in the chapter.\n\n---\n\n# How Semaphores Work\n\nNow that you understand what semaphores are for, let's look at how they actually work under the hood.\n\n### The Core Mechanism\n\nWhen a thread calls `acquire()` or `release()`, the semaphore performs a specific sequence of steps. Understanding this sequence helps you reason about semaphore behavior and avoid mistakes.\n\n#### **The acquire() operation:**\n\n\n```mermaid\nflowchart TD\n subgraph Acquire[\"acquire()\"]\n A1[Check permit count]:::primary --> A2{permits > 0?}:::decision\n A2 --> |Yes| A3[Decrement permits
Return immediately]:::green\n A2 --> |No| A4[Add thread to wait queue
Put thread to sleep]:::orange\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n\tclassDef decision fill:#ffd43b,stroke:#000,color:#000\n```\n\n\n1. Atomically check if permits > 0\n2. If yes: decrement the permit count and return immediately (the thread now \"holds\" a permit)\n3. If no: add the calling thread to a wait queue and put it to sleep (the thread blocks)\n\n#### **The release() operation:**\n\n\n```mermaid\nflowchart TD\n subgraph Release[\"release()\"]\n R1[Increment permit count]:::primary --> R2{Any threads
waiting?}:::decision\n R2 --> |Yes| R3[Wake one waiting thread
It will retry acquire]:::purple\n R2 --> |No| R4[Done - permit available
for future acquirers]:::secondary\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n\tclassDef decision fill:#ffd43b,stroke:#000,color:#000\n```\n\n\n1. Atomically increment the permit count\n2. Check if any threads are waiting in the queue\n3. If yes: wake one of them up (it will retry acquiring)\n4. If no: simply return (the permit is now available for future acquirers)\n\nNotice that `release()` never blocks. It always completes immediately. Only `acquire()` can block, and only when no permits are available.\n\n### Available Operations\n\nBeyond the basic acquire and release, most semaphore implementations provide additional operations for flexibility:\n\n\n| Operation | What It Does | Blocks? |\n|-----------|--------------|---------|\n| `acquire()` / `wait()` / `P()` | Acquire one permit, blocking if none available | Yes |\n| `release()` / `signal()` / `V()` | Release one permit, waking a waiter if any | No |\n| `tryAcquire()` | Try to acquire immediately; return true/false | No |\n| `tryAcquire(timeout)` | Try to acquire, waiting up to timeout | Up to timeout |\n| `availablePermits()` | Get current count (may be stale immediately) | No |\n\n\nThe `tryAcquire()` variants are useful when you want to fall back to alternative behavior if permits aren't available, rather than blocking indefinitely.\n\n### Sequence Example: Three Threads, Two Permits\n\nLet's trace through a concrete scenario to see how acquire and release interact. We have a semaphore with 2 permits and three threads that want to use it. Follow along with the sequence diagram below:\n\n\n```mermaid\nsequenceDiagram\n participant T1 as Thread 1\n participant S as Semaphore
(permits=2)\n participant T2 as Thread 2\n participant T3 as Thread 3\n\n Note over S: Initial state: permits=2\n\n T1->>S: acquire()\n Note over S: permits: 2→1\n S-->>T1: granted immediately\n\n T2->>S: acquire()\n Note over S: permits: 1→0\n S-->>T2: granted immediately\n\n T3->>S: acquire()\n Note over T3: blocked!
(permits=0, no permits available)\n\n Note over T1,T3: Thread 3 is now sleeping in wait queue\n\n T1->>S: release()\n Note over S: permits: 0→1, waiter exists\n S-->>T3: wake up!\n Note over S: T3 acquires: permits: 1→0\n S-->>T3: granted\n\n T2->>S: release()\n Note over S: permits: 0→1\n\n T3->>S: release()\n Note over S: permits: 1→2\n Note over S: Final state: permits=2\n```\n\n\nWalking through this step by step:\n\n1. **Thread 1 acquires:** The semaphore has 2 permits. Thread 1 calls `acquire()`, the count drops to 1, and Thread 1 proceeds immediately.\n2. **Thread 2 acquires:** Thread 2 calls `acquire()`, the count drops to 0, and Thread 2 proceeds immediately.\n3. **Thread 3 tries to acquire:** Thread 3 calls `acquire()`, but the count is 0. Thread 3 cannot proceed; it gets added to the wait queue and goes to sleep.\n4. **Thread 1 releases:** Thread 1 finishes its work and calls `release()`. The count would increment to 1, but there's a waiter (Thread 3). The semaphore wakes Thread 3, which immediately acquires the permit, bringing the count back to 0. Thread 3 now proceeds with its work.\n5. **Thread 2 releases:** Thread 2 calls `release()`. No waiters exist, so the count simply increments to 1.\n6. **Thread 3 releases:** Thread 3 calls `release()`. The count increments to 2, returning to the initial state.\n\nThis sequence demonstrates the key behaviors: immediate acquisition when permits are available, blocking when they're not, and automatic waking of waiters when permits are released.\n\n---\n\n# Implementing Semaphores\n\nLet's see how to use semaphores in real code. We'll cover basic usage patterns, then build a complete connection pool example.\n\n### Basic Usage\n\n\n#### Java\n\nJava provides `java.util.concurrent.Semaphore` with a clean, well-designed API:\n\n\n```java\nimport java.util.concurrent.Semaphore;\n\npublic class SemaphoreBasics {\n // Create a semaphore with 3 permits\n // Up to 3 threads can hold permits simultaneously\n private final Semaphore semaphore = new Semaphore(3);\n\n // Optional: fair=true ensures FIFO ordering\n // Threads acquire permits in the order they requested\n private final Semaphore fairSemaphore = new Semaphore(3, true);\n\n public void accessResource() throws InterruptedException {\n // acquire() blocks until a permit is available\n semaphore.acquire();\n try {\n // Critical section - only 3 threads can be here at once\n doWork();\n } finally {\n // ALWAYS release in a finally block!\n // This ensures the permit is returned even if doWork() throws\n semaphore.release();\n }\n }\n\n // Non-blocking variant: returns immediately with success/failure\n public boolean tryAccessResource() {\n // tryAcquire() returns false immediately if no permit available\n // Use this when you have a fallback option\n if (semaphore.tryAcquire()) {\n try {\n doWork();\n return true;\n } finally {\n semaphore.release();\n }\n }\n return false; // No permit available, caller can try alternative\n }\n\n private void doWork() {\n System.out.println(Thread.currentThread().getName() + \" working...\");\n }\n}\n```\n\n\nThe key pattern here is `acquire()` followed by a `try-finally` block that guarantees `release()`. This pattern prevents permit leaks even when exceptions occur.\n\n\n---\n\n# Example: Connection Pool\n\nA database connection pool is the classic semaphore use case. You have a fixed number of expensive connections, and many threads want to use them. The semaphore ensures no more threads use connections than exist in the pool.\n\nThe design works like this: we pre-create N connections and store them in a queue. A semaphore with N permits guards access. To get a connection, a thread acquires a permit (blocking if all connections are in use), then takes a connection from the queue. To return a connection, it puts the connection back in the queue and releases the permit.\n\n\n```java\nimport java.util.concurrent.*;\nimport java.util.Queue;\nimport java.util.LinkedList;\n\nclass ConnectionPool {\n private final Semaphore semaphore;\n private final Queue pool;\n\n public ConnectionPool(int poolSize) {\n // Fair ordering ensures threads get connections in request order\n // This prevents starvation under high load\n this.semaphore = new Semaphore(poolSize, true);\n this.pool = new LinkedList<>();\n\n // Pre-create all connections at startup\n // This makes acquisition fast (just grab from queue)\n for (int i = 0; i < poolSize; i++) {\n pool.add(new Connection(i));\n }\n }\n\n public Connection acquire() throws InterruptedException {\n // First, acquire a permit (blocks if all connections in use)\n semaphore.acquire();\n // Then grab a connection from the pool\n // We must synchronize pool access since multiple threads touch it\n synchronized (pool) {\n return pool.poll();\n }\n }\n\n public Connection tryAcquire(long timeout, TimeUnit unit)\n throws InterruptedException {\n // Try to get a permit within the timeout\n if (semaphore.tryAcquire(timeout, unit)) {\n synchronized (pool) {\n return pool.poll();\n }\n }\n return null; // Timed out waiting for a connection\n }\n\n public void release(Connection conn) {\n // Return connection to the pool first\n synchronized (pool) {\n pool.offer(conn);\n }\n // Then release the permit, allowing another thread to proceed\n semaphore.release();\n }\n\n public int availableConnections() {\n return semaphore.availablePermits();\n }\n}\n\nclass Connection {\n private final int id;\n\n public Connection(int id) {\n this.id = id;\n }\n\n public void execute(String query) {\n System.out.println(\"Connection \" + id + \" executing: \" + query);\n }\n}\n\npublic class ConnectionPoolDemo {\n public static void main(String[] args) throws InterruptedException {\n // Create a pool with only 3 connections\n ConnectionPool pool = new ConnectionPool(3);\n\n // But we'll have 10 threads trying to use it simultaneously\n ExecutorService executor = Executors.newFixedThreadPool(10);\n\n for (int i = 0; i < 10; i++) {\n final int taskId = i;\n executor.submit(() -> {\n try {\n // This will block for tasks 4-10 until earlier tasks release\n Connection conn = pool.acquire();\n try {\n conn.execute(\"SELECT * FROM users WHERE id = \" + taskId);\n Thread.sleep(100); // Simulate query execution time\n } finally {\n pool.release(conn); // Always release!\n }\n } catch (InterruptedException e) {\n Thread.currentThread().interrupt();\n }\n });\n }\n\n executor.shutdown();\n executor.awaitTermination(10, TimeUnit.SECONDS);\n }\n}\n```\n\n```python\nimport threading\nimport time\nfrom queue import Queue\n\nclass ConnectionPool:\n def __init__(self, pool_size):\n self.semaphore = threading.Semaphore(pool_size)\n self.pool = Queue()\n\n # Pre-create all connections\n for i in range(pool_size):\n self.pool.put(Connection(i))\n\n def acquire(self):\n # Block until permit available, then grab connection\n self.semaphore.acquire()\n return self.pool.get()\n\n def try_acquire(self, timeout):\n # Try to get permit within timeout\n if self.semaphore.acquire(timeout=timeout):\n return self.pool.get()\n return None\n\n def release(self, conn):\n # Return connection to pool, then release permit\n self.pool.put(conn)\n self.semaphore.release()\n\nclass Connection:\n def __init__(self, conn_id):\n self.id = conn_id\n\n def execute(self, query):\n print(f\"Connection {self.id} executing: {query}\")\n\ndef worker(pool, task_id):\n conn = pool.acquire()\n try:\n conn.execute(f\"SELECT * FROM users WHERE id = {task_id}\")\n time.sleep(0.1) # Simulate work\n finally:\n pool.release(conn)\n\ndef main():\n pool = ConnectionPool(3) # Only 3 connections\n threads = []\n\n # 10 threads competing for 3 connections\n for i in range(10):\n t = threading.Thread(target=worker, args=(pool, i))\n threads.append(t)\n t.start()\n\n for t in threads:\n t.join()\n\nif __name__ == \"__main__\":\n main()\n```\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n#include \n#include \n\n// Simple semaphore for pre-C++20 (or use std::counting_semaphore in C++20)\nclass Semaphore {\n std::mutex mtx_;\n std::condition_variable cv_;\n int permits_;\npublic:\n explicit Semaphore(int permits) : permits_(permits) {}\n\n void acquire() {\n std::unique_lock lock(mtx_);\n cv_.wait(lock, [this] { return permits_ > 0; });\n --permits_;\n }\n\n void release() {\n std::lock_guard lock(mtx_);\n ++permits_;\n cv_.notify_one();\n }\n};\n\nclass Connection {\n int id_;\npublic:\n explicit Connection(int id) : id_(id) {}\n void execute(const std::string& query) {\n std::cout << \"Connection \" << id_ << \" executing: \" << query << std::endl;\n }\n int id() const { return id_; }\n};\n\nclass ConnectionPool {\n Semaphore semaphore_;\n std::queue> pool_;\n std::mutex poolMtx_;\n\npublic:\n explicit ConnectionPool(int poolSize) : semaphore_(poolSize) {\n for (int i = 0; i < poolSize; ++i) {\n pool_.push(std::make_unique(i));\n }\n }\n\n Connection* acquire() {\n semaphore_.acquire();\n std::lock_guard lock(poolMtx_);\n auto conn = pool_.front().release();\n pool_.pop();\n return conn;\n }\n\n void release(Connection* conn) {\n {\n std::lock_guard lock(poolMtx_);\n pool_.push(std::unique_ptr(conn));\n }\n semaphore_.release();\n }\n};\n\nint main() {\n ConnectionPool pool(3);\n std::vector threads;\n\n for (int i = 0; i < 10; ++i) {\n threads.emplace_back([&pool, i]() {\n Connection* conn = pool.acquire();\n conn->execute(\"SELECT * FROM users WHERE id = \" + std::to_string(i));\n std::this_thread::sleep_for(std::chrono::milliseconds(100));\n pool.release(conn);\n });\n }\n\n for (auto& t : threads) {\n t.join();\n }\n\n return 0;\n}\n```\n\n```csharp\nusing System;\nusing System.Collections.Concurrent;\nusing System.Threading;\nusing System.Threading.Tasks;\nusing System.Linq;\n\npublic class ConnectionPool\n{\n private readonly SemaphoreSlim semaphore;\n private readonly ConcurrentQueue pool;\n\n public ConnectionPool(int poolSize)\n {\n // SemaphoreSlim with initial and max count\n semaphore = new SemaphoreSlim(poolSize, poolSize);\n pool = new ConcurrentQueue();\n\n // Pre-create all connections\n for (int i = 0; i < poolSize; i++)\n {\n pool.Enqueue(new Connection(i));\n }\n }\n\n public Connection Acquire()\n {\n // Block until permit available\n semaphore.Wait();\n\n Connection conn;\n if (!pool.TryDequeue(out conn) || conn == null)\n {\n // Should not happen if Release() is used correctly\n semaphore.Release();\n throw new InvalidOperationException(\"Semaphore acquired but no connection was available in the pool.\");\n }\n\n return conn;\n }\n\n // Async version - preferred in async codebases\n public async Task AcquireAsync(CancellationToken ct = default(CancellationToken))\n {\n await semaphore.WaitAsync(ct);\n\n Connection conn;\n if (!pool.TryDequeue(out conn) || conn == null)\n {\n // Should not happen if Release() is used correctly\n semaphore.Release();\n throw new InvalidOperationException(\"Semaphore acquired but no connection was available in the pool.\");\n }\n\n return conn;\n }\n\n public Connection TryAcquire(int millisecondsTimeout)\n {\n if (semaphore.Wait(millisecondsTimeout))\n {\n Connection conn;\n if (!pool.TryDequeue(out conn) || conn == null)\n {\n // Should not happen if Release() is used correctly\n semaphore.Release();\n throw new InvalidOperationException(\"Semaphore acquired but no connection was available in the pool.\");\n }\n\n return conn;\n }\n return null; // Timed out\n }\n\n public void Release(Connection conn)\n {\n pool.Enqueue(conn);\n semaphore.Release();\n }\n\n public int AvailableConnections => semaphore.CurrentCount;\n}\n\npublic class Connection\n{\n public int Id { get; }\n\n public Connection(int id) => Id = id;\n\n public void Execute(string query)\n {\n Console.WriteLine($\"Connection {Id} executing: {query}\");\n }\n}\n\npublic class ConnectionPoolDemo\n{\n // Old Mono/C# compilers do not support async Main as an entry point\n public static void Main(string[] args)\n {\n MainAsync().GetAwaiter().GetResult();\n }\n\n private static async Task MainAsync()\n {\n var pool = new ConnectionPool(3); // Only 3 connections\n\n // 10 tasks competing for 3 connections\n var tasks = Enumerable.Range(0, 10).Select(async i =>\n {\n var conn = await pool.AcquireAsync();\n try\n {\n conn.Execute($\"SELECT * FROM users WHERE id = {i}\");\n await Task.Delay(100); // Simulate query time\n }\n finally\n {\n pool.Release(conn);\n }\n });\n\n await Task.WhenAll(tasks);\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"fmt\"\n \"sync\"\n \"time\"\n)\n\n// Semaphore using buffered channel\ntype Semaphore chan struct{}\n\nfunc NewSemaphore(n int) Semaphore {\n return make(chan struct{}, n)\n}\n\nfunc (s Semaphore) Acquire() {\n s <- struct{}{}\n}\n\nfunc (s Semaphore) Release() {\n <-s\n}\n\ntype Connection struct {\n ID int\n}\n\nfunc (c *Connection) Execute(query string) {\n fmt.Printf(\"Connection %d executing: %s\\n\", c.ID, query)\n}\n\ntype ConnectionPool struct {\n semaphore Semaphore\n pool chan *Connection\n}\n\nfunc NewConnectionPool(poolSize int) *ConnectionPool {\n cp := &ConnectionPool{\n semaphore: NewSemaphore(poolSize),\n pool: make(chan *Connection, poolSize),\n }\n\n // Pre-create all connections\n for i := 0; i < poolSize; i++ {\n cp.pool <- &Connection{ID: i}\n }\n\n return cp\n}\n\nfunc (cp *ConnectionPool) Acquire() *Connection {\n cp.semaphore.Acquire() // Block if all connections in use\n return <-cp.pool // Get connection from pool\n}\n\nfunc (cp *ConnectionPool) Release(conn *Connection) {\n cp.pool <- conn // Return connection to pool\n cp.semaphore.Release() // Release permit\n}\n\nfunc main() {\n pool := NewConnectionPool(3) // Only 3 connections\n\n var wg sync.WaitGroup\n\n // 10 goroutines competing for 3 connections\n for i := 0; i < 10; i++ {\n wg.Add(1)\n go func(taskID int) {\n defer wg.Done()\n\n conn := pool.Acquire()\n defer pool.Release(conn)\n\n conn.Execute(fmt.Sprintf(\"SELECT * FROM users WHERE id = %d\", taskID))\n time.Sleep(100 * time.Millisecond) // Simulate query time\n }(i)\n }\n\n wg.Wait()\n}\n```\n\n\nNotice how connections 0, 1, and 2 are reused. The semaphore ensures only 3 tasks run concurrently, while the other 7 wait their turn.\n\n---\n\n# Semaphore vs Mutex\n\nThis comparison comes up frequently in interviews. While a binary semaphore (permits=1) and a mutex can both limit access to one thread at a time, they have fundamental differences that matter in practice.\n\nA simple mental model:\n\n- A **mutex** answers: “Who is allowed to touch this shared state right now?”\n- A **semaphore** answers: “How many threads are allowed to proceed right now?” or “Has an event happened yet?”\n\n### Key Differences\n\n\n| Aspect | Mutex | Semaphore |\n|--------|-------|-----------|\n| **Ownership** | Yes - only the thread that locked can unlock | No - any thread can signal |\n| **Count** | Always 1 (binary) | Can be any N (counting) |\n| **Primary purpose** | Protecting critical sections | Resource counting and signaling |\n| **Priority inheritance** | Usually supported | Usually not supported |\n| **Release by different thread** | Error or undefined behavior | Perfectly valid |\n\n\n### Why Ownership Matters\n\nThe ownership difference has significant practical implications.\n\n**With a mutex**, the thread that locks it must be the one to unlock it. This enables:\n\n- **Priority inheritance:** If a low-priority thread holds a mutex that a high-priority thread needs, the OS can temporarily boost the low-priority thread's priority to avoid priority inversion. This requires knowing who owns the lock.\n- **Deadlock detection:** The system can track which thread holds which mutexes, enabling detection of circular wait conditions.\n- **Error checking:** The system can detect and report when a thread tries to unlock a mutex it doesn't own.\n\n**With a semaphore**, any thread can call `release()`. This enables:\n\n- **Signaling between threads:** Thread A does work, then releases a semaphore that Thread B is waiting on. A produces, B consumes.\n- **Asymmetric acquire/release:** The thread that acquires a permit doesn't have to be the one that releases it. This is essential for producer-consumer patterns.\n\n### When to Use Each\n\n#### **Use a mutex when:**\n\n- Protecting a critical section (data access)\n- You need the lock holder to be the one who unlocks\n- You want priority inheritance\n- One thread should lock and unlock as a pair\n\n#### **Use a semaphore when:**\n\n- Limiting concurrent access to N resources\n- Signaling between threads\n- Producer-consumer patterns\n- The acquirer and releaser may be different threads\n\nHere's code illustrating both patterns:\n\n\n```java\n// MUTEX pattern: protecting a critical section\n// The same thread that enters the synchronized block exits it\nsynchronized (lock) {\n // Only one thread at a time\n updateSharedState();\n}\n\n// SEMAPHORE pattern 1: limiting concurrent access\n// Same thread acquires and releases, but N threads can be inside\nSemaphore permits = new Semaphore(10);\npermits.acquire();\ntry {\n useConnection(); // Up to 10 concurrent users\n} finally {\n permits.release();\n}\n\n// SEMAPHORE pattern 2: signaling between threads\n// Different threads acquire and release!\nSemaphore signal = new Semaphore(0); // Start with 0 permits\n\n// Thread A (producer)\nprepareData();\nsignal.release(); // \"Signal that data is ready\"\n\n// Thread B (consumer)\nsignal.acquire(); // \"Wait until data is ready\"\nprocessData();\n```\n\n```python\nimport threading\n\n# MUTEX pattern: protecting a critical section\n# The same thread that enters the lock exits it\nlock = threading.Lock()\nwith lock:\n # Only one thread at a time\n update_shared_state()\n\n# SEMAPHORE pattern 1: limiting concurrent access\n# Same thread acquires and releases, but N threads can be inside\npermits = threading.Semaphore(10)\npermits.acquire()\ntry:\n use_connection() # Up to 10 concurrent users\nfinally:\n permits.release()\n\n# SEMAPHORE pattern 2: signaling between threads\n# Different threads acquire and release!\nsignal = threading.Semaphore(0) # Start with 0 permits\n\n# Thread A (producer)\ndef producer():\n prepare_data()\n signal.release() # \"Signal that data is ready\"\n\n# Thread B (consumer)\ndef consumer():\n signal.acquire() # \"Wait until data is ready\"\n process_data()\n```\n\n```cpp\n#include \n#include \n\n// MUTEX pattern: protecting a critical section\n// The same thread that locks the mutex unlocks it\nstd::mutex mtx;\n{\n std::lock_guard guard(mtx);\n // Only one thread at a time\n updateSharedState();\n}\n\n// SEMAPHORE pattern 1: limiting concurrent access\n// Same thread acquires and releases, but N threads can be inside\nstd::counting_semaphore<10> permits(10);\npermits.acquire();\ntry {\n useConnection(); // Up to 10 concurrent users\n} catch (...) {\n permits.release();\n throw;\n}\npermits.release();\n\n// SEMAPHORE pattern 2: signaling between threads\n// Different threads acquire and release!\nstd::counting_semaphore<1> signal(0); // Start with 0 permits\n\n// Thread A (producer)\nvoid producer() {\n prepareData();\n signal.release(); // \"Signal that data is ready\"\n}\n\n// Thread B (consumer)\nvoid consumer() {\n signal.acquire(); // \"Wait until data is ready\"\n processData();\n}\n```\n\n```csharp\nusing System.Threading;\n\n// MUTEX pattern: protecting a critical section\n// The same thread that enters the lock exits it\nprivate readonly object lockObj = new object();\nlock (lockObj)\n{\n // Only one thread at a time\n UpdateSharedState();\n}\n\n// SEMAPHORE pattern 1: limiting concurrent access\n// Same thread acquires and releases, but N threads can be inside\nvar permits = new SemaphoreSlim(10);\nawait permits.WaitAsync();\ntry\n{\n UseConnection(); // Up to 10 concurrent users\n}\nfinally\n{\n permits.Release();\n}\n\n// SEMAPHORE pattern 2: signaling between threads\n// Different threads acquire and release!\nvar signal = new SemaphoreSlim(0); // Start with 0 permits\n\n// Thread A (producer)\nvoid Producer()\n{\n PrepareData();\n signal.Release(); // \"Signal that data is ready\"\n}\n\n// Thread B (consumer)\nasync Task Consumer()\n{\n await signal.WaitAsync(); // \"Wait until data is ready\"\n ProcessData();\n}\n```\n\n```go\nimport \"sync\"\n\n// MUTEX pattern: protecting a critical section\n// The same goroutine that locks the mutex unlocks it\nvar mu sync.Mutex\nmu.Lock()\n// Only one goroutine at a time\nupdateSharedState()\nmu.Unlock()\n\n// SEMAPHORE pattern 1: limiting concurrent access\n// Same goroutine acquires and releases, but N can be inside\n// Go uses buffered channels as semaphores\npermits := make(chan struct{}, 10)\npermits <- struct{}{} // Acquire\nfunc() {\n defer func() { <-permits }() // Release\n useConnection() // Up to 10 concurrent users\n}()\n\n// SEMAPHORE pattern 2: signaling between threads\n// Different goroutines send and receive!\nsignal := make(chan struct{}, 1) // Buffered channel as semaphore\n\n// Goroutine A (producer)\ngo func() {\n prepareData()\n signal <- struct{}{} // \"Signal that data is ready\"\n}()\n\n// Goroutine B (consumer)\ngo func() {\n <-signal // \"Wait until data is ready\"\n processData()\n}()\n```\n\n\nIn the signaling pattern, notice that Thread A releases without ever acquiring, and Thread B acquires without ever releasing. This would be an error with a mutex, but it's the correct pattern for semaphore-based signaling.\n\n---\n\n# Performance Considerations\n\nSemaphores are heavily optimized, but they still have a cost, especially under contention. The key idea is similar to mutexes:\n\n- Uncontended operations are cheap.\n- Contention introduces queueing, blocking, and wakeups, which are expensive.\n\n### Operation Costs\n\n\n| Operation | Typical Latency | What Happens |\n|-----------|-----------------|--------------|\n| Uncontended acquire/release | 20-100 nanoseconds | Fast atomic operations on the counter |\n| Contended acquire (no wait) | 100-500 nanoseconds | Atomic operation fails, retry loop |\n| Contended acquire (must wait) | 1-10 microseconds | Thread sleeps, later wakes up (context switch) |\n| Timeout operations | Additional overhead | Timer management adds latency |\n\n\nSemaphores are heavier than raw atomics because they may maintain a wait queue and manage wakeups. But they are often simpler and cheaper than building the same behavior with ad-hoc condition variables.\n\n### Choosing the Right Tool\n\n\n| Scenario | Best Choice | Why |\n|----------|-------------|-----|\n| Mutual exclusion | Mutex/Lock | Ownership, priority inheritance, lower overhead |\n| Limit to exactly N | Counting Semaphore | Built for this exact purpose |\n| Atomic counter (no blocking) | AtomicInteger | Much lower overhead when blocking isn't needed |\n| One-time \"wait for ready\" | CountDownLatch | Simpler semantics for one-shot events |\n| Cyclical barrier | CyclicBarrier | Reusable barrier with simpler API |\n| Precise rate limiting | Token bucket | Better burst handling, smoother rate control |\n\n\nA useful rule: if your intent is “only one thread can enter,” reach for a mutex. If your intent is “only N threads can enter” or “wake someone when ready,” reach for a semaphore.\n\n### Optimization Strategies\n\n#### **1. Choose the right permit count**\n\nToo few permits causes unnecessary blocking and underutilization. Too many defeats the purpose of limiting. For connection pools, match the count to the actual pool size. For CPU-bound work, match the count to CPU cores.\n\n#### **2. Consider fairness trade-offs**\n\nFair semaphores guarantee FIFO ordering but have lower throughput. Non-fair semaphores allow \"barging\" (newly arriving threads can acquire before waiting threads) which improves throughput but can cause starvation.\n\n\n```java\n// Non-fair (default) - higher throughput\n// A newly arriving thread might acquire before threads that have been waiting\nSemaphore sem = new Semaphore(10);\n\n// Fair - guaranteed FIFO ordering, no starvation\n// But ~10-20% lower throughput due to queue management\nSemaphore fairSem = new Semaphore(10, true);\n```\n\n\nUse fair semaphores when wait times are critical (user-facing operations) or starvation is a concern (high contention with many threads). Use non-fair semaphores (the default) when throughput matters more than individual latency.\n\n#### **3. Use tryAcquire() for fallback paths**\n\nWhen you have an alternative to blocking, use non-blocking acquisition:\n\n\n```java\nif (semaphore.tryAcquire()) {\n try {\n usePreferredResource();\n } finally {\n semaphore.release();\n }\n} else {\n useFallbackResource(); // Don't block, use alternative\n}\n```\n\n\nThis is useful for graceful degradation: try the fast path, fall back to a slower alternative if resources are unavailable.\n\n---\n\n# Quiz","pageType":"concurrency-interview"}

Semaphores

Get Premium