Condition Variables

Locks and Mutexes provide mutual exclusion—they prevent multiple threads from modifying shared data simultaneously. However, threads also need a way to coordinate and signal one another when specific conditions change (e.g., when a queue has room for more items). For this, we use Condition Variables.

1. Learning Objectives

• Understand how Condition Variables allow threads to yield execution and wait for specific state changes.
• Solve the classic Producer-Consumer Problem using bounded queues.
• Explain the causes and prevention of Spurious Wakeups.
• Differentiate between signaling one thread (notify()) and signaling all waiting threads (notifyAll()).
• Trace how the JVM manages wait queues and monitor lock sets during signaling.

2. Problem & Naive Solution

Suppose you are building a print job queue. Producer threads add document tasks to a shared queue, and a Consumer thread (representing a printer) processes tasks from the queue. If the queue is empty, the consumer must wait; if the queue is full, the producers must wait.

The Naive Solution (Busy Wait Checks)

A developer attempts to coordinate execution by running active checks on the queue size inside a loop:

3. Issues with the Naive Approach

• CPU Waste: If the queue remains empty for hours, the consumer thread runs a continuous loop on a CPU core checking queue.isEmpty(), wasting electricity and resources.
• Lock Contention: The consumer constantly acquires and releases the synchronized monitor lock on the queue, blocking producer threads from acquiring the lock to insert new items.

4. Producer-Consumer Buffer Queue

Below is a diagram of a shared bounded buffer. If the buffer is full, producers wait in the notFull condition queue; if the buffer is empty, consumers wait in the notEmpty condition queue.

5. Theory: Signaling and Spurious Wakeups

Let's explore the core concepts and mechanics of condition variables:

A. Condition Variables & Monitors

A Condition Variable provides a queue of threads waiting for a specific logical condition to become true. It is always associated with a Mutex (or Lock Monitor). A thread must acquire the lock before it can wait or signal on the condition variable.

• await() / wait(): Releases the associated lock, suspends the thread, and places it in the condition variable's wait set. When it wakes up, it re-acquires the lock before returning.
• signal() / notify(): Wakes up one thread from the condition variable's wait set, moving it to the lock's acquisition queue.
• signalAll() / notifyAll(): Wakes up all threads in the condition variable's wait set. This is safer than notifying a single thread, as it avoids issues like waking up a thread that cannot proceed, which can cause the application to hang.

B. Spurious Wakeups

A thread waiting on a condition variable can wake up *spuriously*—meaning it wakes up without receiving a signal from another thread. This can happen due to internal OS scheduler optimizations or interrupts. To handle this, always verify the condition in a while loop, not an if statement:

6. Syntax Explanation

Languages use specific classes to implement locks and condition signaling:

• Java: Uses ReentrantLock and its newCondition() method to instantiate condition variables (Condition). It provides await(), signal(), and signalAll() methods.
• Python: Uses threading.Condition(lock), which provides wait(), notify(), and notify_all() methods.
• C++: Uses std::condition_variable along with a std::unique_lock<std::mutex>. It provides wait(), notify_one(), and notify_all() methods.

7. Step-by-Step Implementation

1. Instantiate Lock and Conditions: Create a lock and two condition variables (e.g., notFull and notEmpty).
2. Implement Producer (Put): Acquire the lock. Wrap the buffer full check in a while loop calling notFull.await(). Once space is available, add the item and signal notEmpty.signal(). Release the lock.
3. Implement Consumer (Take): Acquire the lock. Wrap the buffer empty check in a while loop calling notEmpty.await(). Once an item is available, retrieve it and signal notFull.signal(). Release the lock.
4. Verify Execution: Run multiple producers and consumers, and confirm that the queue size stays within bounds.

8. Complete Code (Bounded Blocking Queue)

This program implements a thread-safe bounded blocking queue using condition variables to coordinate producers and consumers.

9. Code Walkthrough

• Atomic State Releases: The key step occurs inside await() / wait(). The JVM atomically releases the acquired lock monitor and suspends the thread. This allows other threads to acquire the lock and modify the queue, preventing deadlocks.
• Safe Wake-up Verification: When a waiting thread is woken up by a signal, it must wait to re-acquire the lock before returning from await(). Because it can wake up spuriously, we use a while loop to re-evaluate the queue size condition.

10. Internal Working (Monitor Wait Sets)

Let's explore how the JVM handles condition signaling internally:

• Lock Entry Queue (BLOCKED): The queue of threads waiting to acquire the lock monitor.
• Condition Wait Set (WAITING): When a thread calls await(), the JVM moves it from the active CPU execution queue to the condition's private Wait Set queue. The thread is now suspended.
• Transitioning States: When signal() is called, the JVM pops a thread from the Wait Set and places it back in the Lock Entry Queue. The thread transitions from WAITING to BLOCKED, competing to acquire the lock monitor. Once it acquires the lock, it transitions to RUNNABLE and resumes execution.

11. Complexity Analysis

• Time Complexity: await() and signal() are $O(1)$ operations, as they interact with pre-allocated queue lists.
• Space Complexity: $O(N)$ space, where $N$ is the number of threads waiting in the queue.

12. Best Practices

• Always Hold the Lock When Accessing Conditions: You must hold the associated lock when calling wait() or notify(). Calling these methods without holding the lock throws an error (e.g., IllegalMonitorStateException in Java).
• Prefer notifyAll() over notify(): Waking up a single thread (notify()) can cause issues if that thread cannot proceed (e.g., if a producer wakes up another producer while the queue is full). Waking up all threads (notifyAll()) is safer, as all threads will evaluate their conditions, ensuring progress.

13. Common Mistakes

• Using if Instead of while for Wait Checks: Checking the condition using an if block. If the thread is woken up spuriously or preempted before it can run, it will proceed to modify the queue without verifying the condition, causing data corruption.
• Calling notify() Inside the Wrong Monitor Scope: Calling notify() on Object A while holding a synchronized lock monitor on Object B. This throws an IllegalMonitorStateException at runtime.

14. Interview Discussion

15. Practice Exercises

• Easy: Write a program that coordinates two threads to print "Ping" and "Pong" alternately using condition variables.
• Medium: Build a thread-safe task runner where worker threads wait for task submissions. When a task is added, a worker thread wakes up and processes it.
• Hard: Implement a custom Read-Write Lock using locks and condition variables in Java.

16. Challenge Problem

Design a Thread-Safe Concurrent Mailbox. The mailbox has a maximum capacity of 5 messages. It supports two operations:

• send(Message msg): Blocks if the mailbox is full.
• receive(String recipient): Blocks if there are no messages for the specified recipient.

Use locks and condition variables to implement the mailbox, ensuring that receiving threads are only notified when a message is added for their specific recipient.

17. Summary & Cheat Sheet

• Condition Variables allow threads to block and wait for specific state changes without busy-waiting.
• Always wait inside a while loop to protect against spurious wakeups.
• Calling wait() releases the lock monitor, allowing other threads to acquire it and modify the shared state.
• Prefer notifyAll() over notify() to prevent thread starvation and hangs.

18. Quiz

19. Next Lesson Preview

In the next lesson, we will cover Coarse vs. Fine-grained Locking. We will learn how to optimize locking granularity, reduce lock contention, and understand lock striping techniques!