{"title":"Condition Variables","description":"","content":"Picture this: you have a thread that needs to process data, but the data isn't ready yet. What do you do? \n\nThe naive approach is to keep checking in a loop: \"Is the data ready? No. Is it ready now? Still no. How about now?\" \n\nThis busy-waiting approach burns CPU cycles doing absolutely nothing useful. It's like refreshing your email inbox every second waiting for an important message, instead of just letting your phone notify you when it arrives.\n\nCondition variables offer an elegant solution to this problem. They let a thread go to sleep and wait until another thread explicitly wakes it up, signaling that the condition it was waiting for has changed. The waiting thread consumes zero CPU while asleep, and wakes up exactly when needed.\n\nThis chapter explores how condition variables work under the hood, why they must always be paired with a mutex, and how to avoid the subtle bugs that can turn condition variable code into a debugging nightmare.\n\n---\n\n# What is a Condition Variable?\n\nA condition variable is a synchronization primitive that allows threads to wait until a particular condition becomes true. Unlike a semaphore, which signals when a resource counter becomes non-zero, a condition variable signals when any arbitrary predicate, any boolean condition you define, becomes true.\n\nThe fundamental insight behind condition variables is the separation of two distinct concerns:\n\n1. **Protecting shared state** (handled by the mutex)\n2. **Waiting for state changes** (handled by the condition variable)\n\nThis separation matters more than it might seem at first. The mutex ensures that only one thread can read or modify the shared state at a time. The condition variable provides an efficient way to wait for that state to change, without burning CPU cycles in a polling loop. Neither primitive alone solves the coordination problem. \n\nA mutex alone would require busy-waiting; waiting alone without mutual exclusion leads to race conditions. Together, they form a complete solution.\n\nTo visualize how this works, consider the following diagram. Multiple consumer threads can add themselves to a wait queue, sleeping until a producer thread signals the condition variable. When the producer signals, one of the waiting threads wakes up and can proceed with its work.\n\n\n```mermaid\nflowchart LR\n subgraph CV[\"Condition Variable\"]\n WQ[Wait Queue]:::queue\n end\n\n T1[Thread 1
Producer]:::producer\n T2[Thread 2
Consumer]:::consumer\n T3[Thread 3
Consumer]:::consumer\n\n T2 --> |wait| WQ\n T3 --> |wait| WQ\n T1 --> |signal| WQ\n WQ --> |wake| T2\n\n classDef producer fill:#69db7c,stroke:#000,color:#000\n classDef consumer fill:#00ceff,stroke:#000,color:#000\n\tclassDef queue fill:#ffd43b,stroke:#000,color:#000\n```\n\n\nIn this scenario, Thread 2 and Thread 3 are consumers waiting for data. They've called `wait()` and are now sleeping in the condition variable's wait queue, consuming no CPU time. \n\nThread 1, the producer, generates data and signals the condition variable. The signal wakes up Thread 2 (chosen arbitrarily from the wait queue), which can then process the data. Thread 3 remains sleeping until another signal arrives. \n\nNotice that the signal doesn't transfer data directly. It simply says \"something changed, wake up and check.\" The woken thread must then examine the shared state to see what changed.\n\nAt the API level, a condition variable provides three core operations:\n\n\n| Operation | Description |\n|-----------|-------------|\n| **wait()** | Release the mutex, sleep until signaled, then reacquire the mutex |\n| **signal() / notify()** | Wake one waiting thread |\n| **broadcast() / notifyAll()** | Wake all waiting threads |\n\n\nHere's the critical point to keep in mind: `wait()` is always called while holding a mutex, and it atomically releases that mutex before sleeping. When the thread wakes up, it reacquires the mutex before returning from `wait()`. \n\nThis atomicity is not just a convenience feature. It's fundamental to correctness. Without it, there would be a gap between checking the condition and going to sleep where a signal could arrive and be lost forever. We'll explore exactly why this matters shortly, but for now, remember: the atomic release-and-wait behavior is what makes condition variables safe to use.\n\n---\n\n# Use-Cases of Condition Variables\n\nNow that we know what condition variables are, let's understand why they're indispensable. The best way to appreciate their value is to see what happens without them.\n\n### The Busy-Wait Problem\n\nWithout condition variables, you might write code like this to wait for data:\n\n\n```java\n// BAD: Busy-waiting wastes CPU\nwhile (!dataReady) {\n // Spin, burning CPU cycles\n}\nprocessData();\n```\n\n\nThis looks innocent enough. The logic is correct: keep checking until the condition is true, then proceed. But the execution is disastrous:\n\n- **CPU waste**: The thread runs at 100% CPU doing nothing useful. On a laptop, this drains battery. On a server, it steals cycles from threads that have actual work to do. The CPU could be running other threads, handling I/O, or simply saving power.\n- **Poor scalability**: If you have 1000 threads all spinning like this, your system grinds to a halt. Each spinning thread consumes a full CPU core's worth of scheduling time.\n- **Priority inversion**: On some systems, this spinning thread might starve the very thread that would set `dataReady = true`, creating a paradoxical deadlock. The producer can't run because the consumer is monopolizing the CPU waiting for the producer.\n- **Heat and power**: In data centers, unnecessary CPU usage translates directly to higher electricity bills and cooling costs. Multiply a few spinning threads across thousands of servers, and you're burning real money.\n\n### The Proper Solution\n\nCondition variables eliminate busy-waiting entirely. Instead of spinning in a loop, the thread tells the operating system \"wake me when something changes.\"\n\n\n```java\n// GOOD: Sleep until signaled\nmutex.lock();\nwhile (!dataReady) {\n condition.wait(mutex); // Sleep, release mutex, wake, reacquire\n}\nprocessData();\nmutex.unlock();\n```\n\n\nLook at what this code does differently. The thread acquires the mutex, checks the condition, and if the condition is false, calls `wait()`. This is where the magic happens. The `wait()` call releases the mutex (allowing other threads to modify the shared state) and puts the thread to sleep in a single atomic operation. \n\nThe thread is now completely dormant, consuming essentially zero CPU. The operating system removes it from the scheduler's run queue entirely.\n\nWhen the producer sets `dataReady = true` and signals the condition variable, the consumer wakes up, reacquires the mutex, verifies the condition is actually true (more on why this verification is necessary later), and proceeds with its work. The thread went from waiting to working with no wasted cycles in between.\n\n### Common Use Cases\n\nCondition variables appear throughout concurrent programming, often in places you might not immediately recognize. Here are some scenarios where they're the natural choice:\n\n- **Producer-consumer queues**: Consumers wait for items to appear in a queue, rather than polling it repeatedly. This is perhaps the most common use case and one we'll explore in depth later.\n- **Bounded buffers**: Producers wait when the buffer is full; consumers wait when it's empty. Both directions need coordination, making this a two-condition-variable problem.\n- **Thread pools**: Worker threads sleep until tasks arrive, then wake up to process them. Without condition variables, worker threads would either spin-wait (wasteful) or sleep for fixed intervals (unresponsive).\n- **Barriers**: A group of threads waits until all participants reach a synchronization point before any proceed. The last thread to arrive signals everyone else.\n- **One-time initialization**: Multiple threads might need a resource that takes time to initialize. All wait until initialization completes, then all proceed together.\n- **Resource availability**: Threads wait for a specific resource (like a database connection from a pool) to become free. When a connection is returned to the pool, a waiting thread wakes up to use it.\n\n---\n\n# How Condition Variables Work\n\nUnderstanding what happens inside `wait()` and `signal()` is crucial for using condition variables correctly. These operations seem simple on the surface, but their implementation involves careful coordination between the condition variable, the mutex, and the operating system's scheduler. \n\nLet's trace through the lifecycle step by step.\n\n#### **When a thread calls `wait()`:**\n\n1. The thread atomically releases the mutex and adds itself to the condition variable's wait queue. These two operations happen as a single indivisible action. This atomicity is the key to avoiding lost wakeups.\n2. The thread blocks (sleeps) and is removed from the scheduler's run queue. At this point, the thread consumes no CPU time.\n3. When another thread signals, this thread moves from the wait queue to the ready queue, making it eligible to run again.\n4. The thread reacquires the mutex. This might involve waiting if another thread currently holds it. The thread won't proceed until it has the mutex.\n5. Finally, `wait()` returns and the thread continues execution, now holding the mutex.\n\n#### **When a thread calls `signal()`:**\n\n1. If threads are waiting in the condition variable's queue, one is selected. The selection policy varies by implementation; some use FIFO ordering, others don't guarantee any particular order.\n2. That thread moves from the wait queue to the ready queue.\n3. The signaled thread will compete for the mutex when the scheduler runs it. Importantly, the signaling thread might still hold the mutex, in which case the awakened thread will block on the mutex.\n\nThe following state diagram shows the lifecycle of a thread using a condition variable.\n\n\n```mermaid\nstateDiagram-v2\n [*] --> HoldingMutex: lock()\n\n HoldingMutex --> Waiting: wait() releases mutex\n Waiting --> Signaled: signal() received\n Signaled --> HoldingMutex: reacquire mutex\n HoldingMutex --> [*]: unlock()\n\n classDef holding fill:#69db7c,stroke:#000,color:#000\n classDef waiting fill:#ffa94d,stroke:#000,color:#000\n classDef signaled fill:#00ceff,stroke:#000,color:#000\n\n class HoldingMutex holding\n class Waiting waiting\n class Signaled signaled\n```\n\n\nThe diagram shows how a thread starts by acquiring the mutex (green state), then enters the waiting state (orange) when it calls `wait()`. A signal moves it to the signaled state (blue), but it must reacquire the mutex before returning to active execution. This mutex reacquisition is automatic but might involve waiting if other threads hold the mutex.\n\nOne subtle point: the signaled state is transient. The thread doesn't do any work there; it's just waiting to reacquire the mutex. Only after successfully reacquiring the mutex does the thread return from `wait()` and continue executing user code. This means there's always a window between being signaled and actually running where other things can happen, which is why the while loop is essential.\n\n### Why use the Mutex?\n\nThis is one of the most important concepts to understand, and one that often confuses newcomers. Condition variables must always be used with a mutex. This isn't just a convention or a best practice; it's a fundamental requirement for correctness.\n\n**Without a mutex, you get a race condition.**\n\nTo understand why, consider what happens when a consumer checks the condition and then waits, without holding a lock.\n\n\n```plaintext\nThread A (consumer): Thread B (producer):\n1. Check: dataReady is false\n 2. Set dataReady = true\n 3. signal()\n4. wait() - MISSED THE SIGNAL!\n (sleeps forever)\n```\n\n\nBetween step 1 (checking the condition) and step 4 (waiting), the producer ran, set the data, and signaled. But the consumer wasn't in the wait queue yet when the signal arrived. This is the critical window: the consumer has decided it needs to wait, but hasn't actually started waiting yet. The signal arrives during this gap and vanishes into the void.\n\nSignals don't queue up or persist. They're like shouting into a room: if no one is listening, the message is lost. Signals only wake threads that are already waiting. So the consumer misses the signal entirely and sleeps forever, waiting for a signal that already happened.\n\nThis is called the **lost wakeup problem**, and it's a classic concurrency bug. Programs with lost wakeups often work fine under light load (the timing doesn't align to expose the bug) but hang mysteriously under heavy load or in production.\n\n**With a mutex, this race cannot happen:**\n\n\n```plaintext\nThread A (consumer): Thread B (producer):\n1. lock()\n2. Check: dataReady is false\n3. wait() atomically: [blocked on lock()]\n - releases mutex\n - adds to wait queue\n - sleeps\n 4. lock() - succeeds now\n 5. dataReady = true\n 6. signal()\n 7. unlock()\n8. wakes, reacquires mutex\n9. Check: dataReady is true\n10. proceed!\n```\n\n\nThe key is step 3. The `wait()` operation atomically releases the mutex and adds the thread to the wait queue. \"Atomically\" means these two things happen as an inseparable unit. There's no window between releasing the mutex and being in the wait queue where a signal could slip through unnoticed.\n\nWhile the consumer holds the mutex (steps 1-3), the producer can't acquire it (it blocks at step 4). Once the consumer enters the wait queue and releases the mutex, the producer can proceed. When the producer signals, the consumer is guaranteed to be waiting and will receive the signal.\n\n### The Wait Internals\n\nLet's look more closely at what `wait()` does internally. Understanding these mechanics helps you reason about timing, predict behavior under edge cases, and debug problems when they arise. The following flowchart breaks down the operation into its component steps:\n\n\n```mermaid\nflowchart LR\n A[wait called]:::primary --> B[Add thread to
wait queue]:::secondary\n B --> C[Release mutex
atomically]:::orange\n C --> D[Sleep until
signaled]:::purple\n D --> E[Move to
ready queue]:::secondary\n E --> F[Reacquire mutex
may block]:::orange\n F --> G[Return from wait]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nFirst, adding to the wait queue and releasing the mutex (steps B and C) happen atomically, preventing lost wakeups. Second, after being signaled (step D), the thread doesn't immediately return from `wait()`. It must first reacquire the mutex (step F), which might involve additional waiting if other threads hold the mutex. Only after successfully reacquiring the mutex does `wait()` return.\n\nThis reacquisition requirement explains why you must use a while loop around `wait()`. After reacquiring the mutex, the condition might have changed again, so you must recheck it.\n\n---\n\n# Condition Variables in Practice\n\nNow that we understand the mechanics, let's see how to use condition variables in real code. Each programming language has its own syntax and idioms, but the underlying pattern is always the same: acquire mutex, check condition in a while loop, wait if false, proceed if true.\n\n### Basic Wait-Notify Pattern\n\nLet's start with the simplest possible use case: one thread waits for another thread to produce some data. This forms the foundation for more complex patterns.\n\n\n#### Java\n\nJava provides two APIs for condition variables: the intrinsic `Object.wait()/notify()` mechanism that works with `synchronized`, and the explicit `Condition` interface that works with `Lock` objects.\n\n#### **Using Object.wait() / notify()**\n\nThis approach ties the condition variable to an object's intrinsic lock. Any Java object can serve as both a lock (via `synchronized`) and a condition variable (via `wait()`/`notify()`).\n\n\n```java\npublic class DataProcessor {\n private final Object lock = new Object();\n private boolean dataReady = false;\n private String data;\n\n // Consumer: wait for data\n public String waitForData() throws InterruptedException {\n synchronized (lock) {\n while (!dataReady) { // Always use while, not if\n lock.wait(); // Releases lock, sleeps, reacquires\n }\n dataReady = false; // Reset for next time\n return data;\n }\n }\n\n // Producer: provide data\n public void provideData(String newData) {\n synchronized (lock) {\n data = newData;\n dataReady = true;\n lock.notify(); // Wake one waiting thread\n }\n }\n}\n```\n\n\nLet's trace through what happens in this code:\n\n1. **Consumer calls `waitForData()`**: It enters the synchronized block, acquiring the intrinsic lock on the `lock` object.\n2. **Consumer checks `dataReady`**: If false, it calls `wait()`.\n3. **`wait()` releases the lock and sleeps**: Now other threads can acquire the lock.\n4. **Producer calls `provideData()`**: It acquires the lock, sets the data, sets `dataReady = true`, and calls `notify()`.\n5. **`notify()` wakes the consumer**: The consumer moves to the ready queue but still needs the lock.\n6. **Producer exits synchronized block**: This releases the lock.\n7. **Consumer reacquires the lock**: Now it can continue from where it left off in the while loop.\n8. **Consumer rechecks `dataReady`**: It's now true, so the loop exits and the consumer processes the data.\n\nThe key insight is that `wait()` always releases the lock before sleeping and reacquires it before returning. This all happens automatically within the `wait()` call.\n\n#### **Using Condition interface (preferred for new code)**\n\nThe explicit `Condition` interface offers more flexibility, including the ability to have multiple conditions associated with a single lock.\n\n\n```java\nimport java.util.concurrent.locks.*;\n\npublic class DataProcessor {\n private final Lock lock = new ReentrantLock();\n private final Condition dataAvailable = lock.newCondition();\n private boolean dataReady = false;\n private String data;\n\n public String waitForData() throws InterruptedException {\n lock.lock();\n try {\n while (!dataReady) {\n dataAvailable.await(); // Like wait()\n }\n dataReady = false;\n return data;\n } finally {\n lock.unlock();\n }\n }\n\n public void provideData(String newData) {\n lock.lock();\n try {\n data = newData;\n dataReady = true;\n dataAvailable.signal(); // Like notify()\n } finally {\n lock.unlock();\n }\n }\n}\n```\n\n\nThe pattern is almost identical, but notice a few differences. The lock is explicitly created as a `ReentrantLock`, and the condition is created from the lock via `lock.newCondition()`. The try/finally block ensures the lock is always released, even if an exception occurs. \n\nThis explicit approach has a significant advantage: you can create multiple condition objects associated with the same lock. For instance, a bounded buffer might have `notEmpty` (for consumers to wait on) and `notFull` (for producers to wait on), both protected by the same lock.\n\n\n---\n\n# Example: Producer-Consumer with Bounded Buffer\n\nThe bounded buffer is the classic condition variable example, and for good reason: it elegantly demonstrates why you might need multiple conditions. A bounded buffer is a fixed-size queue where producers add items and consumers remove them. \n\nThe interesting constraint: producers must wait when the buffer is full, and consumers must wait when it's empty. This bidirectional waiting can't be elegantly solved with a single condition variable. You need two: one for \"buffer has space\" and one for \"buffer has items.\"\n\n\n#### Java\n\n\n```java\nimport java.util.concurrent.locks.*;\nimport java.util.LinkedList;\nimport java.util.Queue;\n\nclass BoundedBuffer {\n private final Queue buffer = new LinkedList<>();\n private final int capacity;\n\n private final Lock lock = new ReentrantLock();\n private final Condition notFull = lock.newCondition();\n private final Condition notEmpty = lock.newCondition();\n\n public BoundedBuffer(int capacity) {\n this.capacity = capacity;\n }\n\n public void put(T item) throws InterruptedException {\n lock.lock();\n try {\n // Wait while buffer is full\n while (buffer.size() == capacity) {\n notFull.await();\n }\n buffer.add(item);\n notEmpty.signal(); // Wake a waiting consumer\n } finally {\n lock.unlock();\n }\n }\n\n public T take() throws InterruptedException {\n lock.lock();\n try {\n // Wait while buffer is empty\n while (buffer.isEmpty()) {\n notEmpty.await();\n }\n T item = buffer.poll();\n notFull.signal(); // Wake a waiting producer\n return item;\n } finally {\n lock.unlock();\n }\n }\n}\n\n// Usage example:\n\npublic class ProducerConsumerDemo {\n public static void main(String[] args) {\n BoundedBuffer buffer = new BoundedBuffer<>(5);\n\n // Producer\n Thread producer = new Thread(() -> {\n try {\n for (int i = 0; i < 20; i++) {\n buffer.put(i);\n System.out.println(\"Produced: \" + i);\n }\n } catch (InterruptedException e) {\n Thread.currentThread().interrupt();\n }\n });\n\n // Consumer\n Thread consumer = new Thread(() -> {\n try {\n for (int i = 0; i < 20; i++) {\n int item = buffer.take();\n System.out.println(\"Consumed: \" + item);\n Thread.sleep(100); // Slow consumer\n }\n } catch (InterruptedException e) {\n Thread.currentThread().interrupt();\n }\n });\n\n producer.start();\n consumer.start();\n }\n}\n```\n\n\nLet's examine the structure of this implementation:\n\n**Two separate condition variables**: `notFull` for producers waiting for space, and `notEmpty` for consumers waiting for items. Both conditions share the same lock because they protect the same shared state (the buffer).\n\n**The `put()` method**: A producer acquires the lock, checks if the buffer is at capacity, and waits on `notFull` if it is. Once space is available (either immediately or after waking), it adds the item and signals `notEmpty` to wake any waiting consumers.\n\n**The `take()` method**: A consumer acquires the lock, checks if the buffer is empty, and waits on `notEmpty` if it is. Once an item is available, it removes it and signals `notFull` to wake any waiting producers.\n\nWith a slow consumer (the `Thread.sleep(100)`), the producer will quickly fill the buffer and then block on `notFull.await()`. Each time the consumer removes an item, it signals `notFull`, allowing the producer to add one more item. The flow self-regulates.\n\n\n\n> **Why use two conditions instead of one?**\n>\n> Efficiency. When a producer adds an item, only consumers need to wake up. When a consumer removes an item, only producers need to wake up. If we used a single condition variable and called `signalAll()` after each operation, we'd potentially wake threads that still can't proceed. \n>\n> For example, if the buffer is full and a consumer takes one item, waking all waiting producers just to have most of them go back to sleep is wasteful.\n\n\n### Sequence Diagram: Producer-Consumer Flow\n\nTo solidify understanding, let's trace through a complete interaction between a producer, a bounded buffer, and a consumer. Reading code is one thing; seeing the temporal flow of operations is another. This sequence diagram shows the timeline of operations and how the threads coordinate, including what happens when both the \"buffer empty\" and \"buffer full\" conditions come into play.\n\n\n```mermaid\nsequenceDiagram\n participant P as Producer\n participant B as Buffer\n participant C as Consumer\n\n Note over B: buffer empty\n\n C->>B: take()\n Note over C: wait on notEmpty\n\n P->>B: put(item1)\n B-->>C: notEmpty.signal()\n Note over C: wake, return item1\n\n P->>B: put(item2)\n P->>B: put(item3)\n P->>B: put(item4)\n P->>B: put(item5)\n Note over B: buffer full (capacity=5)\n\n P->>B: put(item6)\n Note over P: wait on notFull\n\n C->>B: take()\n B-->>P: notFull.signal()\n Note over P: wake, add item6\n```\n\n\nLet's walk through this timeline:\n\n1. **Consumer arrives first**: The buffer is empty, so the consumer has nothing to take. It calls `take()`, sees the buffer is empty, and waits on `notEmpty`.\n2. **Producer adds item1**: The producer calls `put(item1)`. The buffer now has one item. The producer signals `notEmpty`, waking the consumer.\n3. **Consumer wakes and retrieves item1**: The consumer reacquires the lock, rechecks the condition (buffer is not empty), and returns item1.\n4. **Producer fills the buffer**: The producer adds items 2 through 5. The buffer reaches capacity (5 items).\n5. **Producer tries to add item6**: The buffer is full, so the producer waits on `notFull`.\n6. **Consumer takes an item**: The consumer removes an item, creating space. It signals `notFull`, waking the producer.\n7. **Producer wakes and adds item6**: The producer reacquires the lock, rechecks the condition (buffer is not full), and successfully adds item6.\n\nThis dance continues as long as producers and consumers are active, with the buffer serving as a shock absorber between different processing speeds.\n\n---\n\n# Performance Considerations\n\nCondition variables are already far more efficient than busy-waiting, but there's still room for optimization. The main performance considerations involve choosing between `signal()` and `broadcast()`, and minimizing lock contention after wakeups.\n\n### Signal vs Broadcast\n\n\n| Operation | Behavior | Use When |\n|-----------|----------|----------|\n| `signal()` / `notify()` | Wake one thread | Only one thread can proceed |\n| `broadcast()` / `notifyAll()` | Wake all threads | Multiple threads might proceed, or using single condition for multiple predicates |\n\n\n**The Thundering Herd Problem:** If you use `broadcast()` when only one thread can proceed, N-1 threads wake up, check the condition, find it false, and go back to sleep. This wastes CPU cycles and creates lock contention. All N threads try to acquire the mutex one by one, only to find they have nothing to do. With hundreds of waiting threads, this can cause noticeable latency spikes.\n\n\n```java\n// BAD: Broadcasting when only one can proceed\nbuffer.put(singleItem);\nnotEmpty.signalAll(); // Wakes all consumers, but only one gets the item\n\n// GOOD: Signal when only one can proceed\nbuffer.put(singleItem);\nnotEmpty.signal(); // Wakes one consumer\n```\n\n\n**When to use broadcast/notifyAll:**\n\n- The condition change allows multiple threads to proceed (e.g., adding multiple items to a queue)\n- You're using a single condition variable for multiple predicates (not recommended, but sometimes unavoidable)\n- You're shutting down and all threads should wake to check a shutdown flag\n\n### Lock Contention\n\nEvery thread that wakes up from a condition variable must reacquire the mutex before proceeding. With many waiters, this creates a serialization bottleneck. The following diagram shows what happens when multiple threads wake up simultaneously:\n\n\n```mermaid\nsequenceDiagram\n participant T1 as Thread 1\n participant T2 as Thread 2\n participant T3 as Thread 3\n participant L as Lock\n\n Note over T1,T3: All wake from notifyAll()\n\n T1->>L: acquire lock\n Note over T1: check condition, proceed\n T1->>L: release lock\n\n T2->>L: acquire lock (was waiting)\n Note over T2: check condition, proceed or wait again\n T2->>L: release lock\n\n T3->>L: acquire lock (was waiting)\n Note over T3: check condition, proceed or wait again\n```\n\n\nThis diagram illustrates the serialization that occurs after a `notifyAll()`. Each thread must acquire the lock one at a time, check its condition, and either proceed or go back to waiting. With many threads, this serialization becomes a bottleneck.\n\nStrategies to reduce contention:\n\n- Use `signal()` instead of `broadcast()` when only one thread can proceed\n- Use multiple condition variables to partition waiters\n- Consider lock-free alternatives for extremely high-performance scenarios\n\n### Optimization: Unlock Before Notify (C++)\n\nIn C++, you can unlock the mutex before calling `notify_one()`:\n\n\n```cpp\nvoid producer() {\n {\n std::lock_guard lock(mtx_);\n data_ = newData;\n ready_ = true;\n } // Unlock here\n cv_.notify_one(); // Notified thread can acquire lock immediately\n}\n```\n\n\nThis is a minor optimization. If you notify while holding the lock, the notified thread wakes up but immediately blocks trying to acquire the mutex (which you still hold). By unlocking first, the notified thread can acquire the mutex without this extra context switch.\n\nThe optimization is minor because modern schedulers handle this case efficiently, but it doesn't hurt and follows the principle of holding locks for the minimum necessary time.\n\n---\n\n# Implementing a Semaphore with Condition Variables\n\nTo demonstrate condition variables in action and reinforce the concepts, let's implement a semaphore from scratch. This exercise is valuable for two reasons: it shows how higher-level synchronization primitives can be built from lower-level ones, and it's a common interview question.\n\nA semaphore maintains a permit count. `acquire()` decrements the count (waiting if it's zero), and `release()` increments it (waking a waiter if any exist). If you've followed the chapter so far, this implementation should feel natural.\n\n\n```java\npublic class SemaphoreImpl {\n private final Lock lock = new ReentrantLock();\n private final Condition permits = lock.newCondition();\n private int count;\n\n public SemaphoreImpl(int initialPermits) {\n this.count = initialPermits;\n }\n\n public void acquire() throws InterruptedException {\n lock.lock();\n try {\n while (count == 0) {\n permits.await();\n }\n count--;\n } finally {\n lock.unlock();\n }\n }\n\n public void release() {\n lock.lock();\n try {\n count++;\n permits.signal();\n } finally {\n lock.unlock();\n }\n }\n}\n```\n\n```python\nclass SemaphoreImpl:\n def __init__(self, initial_permits):\n self.condition = threading.Condition()\n self.count = initial_permits\n\n def acquire(self):\n with self.condition:\n while self.count == 0:\n self.condition.wait()\n self.count -= 1\n\n def release(self):\n with self.condition:\n self.count += 1\n self.condition.notify()\n```\n\n```cpp\nclass SemaphoreImpl {\n std::mutex mtx_;\n std::condition_variable cv_;\n int count_;\n\npublic:\n explicit SemaphoreImpl(int initialPermits) : count_(initialPermits) {}\n\n void acquire() {\n std::unique_lock lock(mtx_);\n cv_.wait(lock, [this] { return count_ > 0; });\n --count_;\n }\n\n void release() {\n {\n std::lock_guard lock(mtx_);\n ++count_;\n }\n cv_.notify_one();\n }\n};\n```\n\n```csharp\nusing System.Threading;\n\npublic class SemaphoreImpl\n{\n private readonly object lockObj = new object();\n private int count;\n\n public SemaphoreImpl(int initialPermits)\n {\n count = initialPermits;\n }\n\n public void Acquire()\n {\n lock (lockObj)\n {\n while (count == 0)\n {\n Monitor.Wait(lockObj);\n }\n count--;\n }\n }\n\n public void Release()\n {\n lock (lockObj)\n {\n count++;\n Monitor.Pulse(lockObj);\n }\n }\n\n public bool TryAcquire(int millisecondsTimeout)\n {\n lock (lockObj)\n {\n if (count > 0)\n {\n count--;\n return true;\n }\n\n if (!Monitor.Wait(lockObj, millisecondsTimeout))\n {\n return false; // Timed out\n }\n\n // Re-check after wait (might be spurious wakeup)\n if (count > 0)\n {\n count--;\n return true;\n }\n return false;\n }\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"sync\"\n)\n\ntype SemaphoreImpl struct {\n mu sync.Mutex\n cond *sync.Cond\n permits int\n}\n\nfunc NewSemaphore(initialPermits int) *SemaphoreImpl {\n s := &SemaphoreImpl{\n permits: initialPermits,\n }\n s.cond = sync.NewCond(&s.mu)\n return s\n}\n\nfunc (s *SemaphoreImpl) Acquire() {\n s.mu.Lock()\n defer s.mu.Unlock()\n\n for s.permits == 0 {\n s.cond.Wait()\n }\n s.permits--\n}\n\nfunc (s *SemaphoreImpl) Release() {\n s.mu.Lock()\n defer s.mu.Unlock()\n\n s.permits++\n s.cond.Signal()\n}\n\nfunc (s *SemaphoreImpl) TryAcquire() bool {\n s.mu.Lock()\n defer s.mu.Unlock()\n\n if s.permits > 0 {\n s.permits--\n return true\n }\n return false\n}\n```\n\n\nThe implementation is straightforward: `acquire()` waits while count is zero, then decrements; `release()` increments and signals. The while loop in `acquire()` handles spurious wakeups.\n\n---\n\n# Quiz","pageType":"concurrency-interview"}

Get Premium