Broadcast Operation: Waking All Waiting Threads - Broadcast: Waking Multiple Waiting Threads | OneNoughtOne

Operating SystemsBroadcast

Broadcast: Waking Multiple Waiting Threads

LevelIntermediate

Duration90 mins

TopicBroadcast

1 / 5

Broadcast Operation: Waking All Waiting Threads

The Power of Waking Everyone

In the world of condition variables, we've seen how signal() wakes a single waiting thread. But what happens when the state change affects all waiting threads, not just one? What if a resource becomes available that everyone can use, or if a condition that blocked many threads has finally been resolved for all of them?

This is where broadcast enters the picture—a primitive that wakes every thread waiting on a condition variable, not just one. While signal() is like tapping one person on the shoulder, broadcast is like shouting 'Everyone wake up!' in a crowded room.

The broadcast operation is one of the most powerful—and most misused—primitives in concurrent programming. Used correctly, it enables elegant solutions to complex synchronization problems. Used incorrectly, it creates performance nightmares and subtle bugs that are notoriously difficult to diagnose.

What You Will Learn

By the end of this page, you will understand the precise semantics of the broadcast operation, how it differs fundamentally from signal, the mechanisms by which it wakes all waiting threads, and the memory and scheduling implications that arise when multiple threads are awakened simultaneously. You will be able to reason precisely about broadcast's behavior in complex concurrent systems.

Broadcast Semantics: The Formal Definition

The broadcast operation on a condition variable awakens all threads currently waiting on that condition variable. This is in stark contrast to the signal operation, which wakes exactly one waiting thread (or no thread if the wait queue is empty).

Formal Specification:

Given a condition variable cv and a set of threads W = {t₁, t₂, ..., tₙ} currently blocked in cv.wait(), the operation cv.broadcast() performs the following:

Identify all waiters: Atomically snapshot the current wait queue containing all threads in W
Wake all threads: For each thread tᵢ in W, mark it as runnable and remove it from the wait queue
Mutex reacquisition: Each awakened thread must reacquire the mutex before returning from wait()
No ordering guarantees: The order in which awakened threads actually run is scheduler-dependent

The broadcast operation does not guarantee anything about the order of execution or which thread will acquire the mutex first—it only guarantees that all waiting threads will eventually be given a chance to compete for the mutex.

Critical Invariant

After a broadcast, all awakened threads must still reacquire the mutex before returning from wait(). This means they will compete for the mutex, and only one can hold it at any moment. The broadcast merely moves threads from 'blocked on condition' to 'ready to compete for mutex'—it does not grant them simultaneous access to the critical section.

Broadcast Semantics Pseudocode
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Broadcast operation semantics (simplified internal view)
typedef struct {
    mutex_t internal_lock;    // Protects wait queue
    queue_t wait_queue;       // Queue of waiting threads
} condition_variable_t;
 
// Broadcast operation - wakes ALL waiting threads
void cond_broadcast(condition_variable_t *cv) {
    // Acquire internal lock to protect wait queue manipulation
    mutex_lock(&cv->internal_lock);
    
    // Count of threads we will wake
    int threads_to_wake = queue_size(&cv->wait_queue);
    
    // Wake ALL threads in the wait queue
    while (!queue_is_empty(&cv->wait_queue)) {
        thread_t *t = queue_dequeue(&cv->wait_queue);
        
        // Mark thread as runnable
        // It will compete for the associated mutex
        scheduler_make_runnable(t);
    }
    
    mutex_unlock(&cv->internal_lock);
    
    // All 'threads_to_wake' threads are now eligible to run
    // They will compete for the mutex when scheduled
}
 
// Contrast with signal - wakes AT MOST ONE thread
void cond_signal(condition_variable_t *cv) {
    mutex_lock(&cv->internal_lock);
    
    if (!queue_is_empty(&cv->wait_queue)) {
        thread_t *t = queue_dequeue(&cv->wait_queue);
        scheduler_make_runnable(t);
        // Only ONE thread is awakened
    }
    // If queue is empty, signal is a no-op
    
    mutex_unlock(&cv->internal_lock);
}

Key semantic differences between broadcast and signal:

Aspect	signal()	broadcast()
Threads awakened	At most 1	All waiting
Empty queue behavior	No-op	No-op
Memory cost	Minimal	O(n) for n waiters
Scheduling cost	1 context switch	Up to n context switches
Lost signal risk	Yes (if not used carefully)	No
Thundering herd risk	No	Yes

The choice between signal and broadcast is not arbitrary—it depends fundamentally on the nature of the condition being signaled and how many threads can meaningfully proceed when that condition changes.

Why Signal Isn't Always Enough

To understand why broadcast exists, we must first understand scenarios where signal() is fundamentally insufficient. Consider these situations where waking just one thread would leave the system in an incorrect or suboptimal state:

Scenarios Where Signal Fails

•Asymmetric waiter conditions: Different threads wait for different conditions on the same condition variable. Signaling might wake a thread that cannot proceed, while one that could proceed remains asleep.
•Condition invalidation: The awakened thread might find the condition no longer holds by the time it reacquires the mutex (due to another thread), and it re-waits—now no thread proceeds despite resources being available.
•Multiple resources available: When multiple resources become available simultaneously, signal() wakes only one consumer, leaving other available resources unused.
•State transitions affecting all waiters: When a server shuts down, ALL connected clients need to wake up and handle disconnection—not just one.
•Barrier synchronization: When a barrier is satisfied, ALL threads at the barrier must proceed—not just one.

The Classic Example: Mixed Waiters Problem

Consider a bounded buffer where producers and consumers share a single condition variable. This is a common (but problematic) design pattern:

Mixed Waiters Problem
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// DANGEROUS: Single condition variable for both producers and consumers
// This pattern is prone to deadlock when using signal()
 
typedef struct {
    int buffer[BUFFER_SIZE];
    int count;
    int in, out;
    pthread_mutex_t mutex;
    pthread_cond_t cond;  // Shared by BOTH producers AND consumers
} bounded_buffer_t;
 
void producer(bounded_buffer_t *buf, int item) {
    pthread_mutex_lock(&buf->mutex);
    
    // Wait while buffer is FULL
    while (buf->count == BUFFER_SIZE) {
        pthread_cond_wait(&buf->cond, &buf->mutex);
    }
    
    // Insert item
    buf->buffer[buf->in] = item;
    buf->in = (buf->in + 1) % BUFFER_SIZE;
    buf->count++;
    
    // Signal that buffer state changed
    // BUG: What if this wakes another PRODUCER when buffer is still near-full?
    pthread_cond_signal(&buf->cond);  // PROBLEM!
    
    pthread_mutex_unlock(&buf->mutex);
}
 
void consumer(bounded_buffer_t *buf, int *item) {
    pthread_mutex_lock(&buf->mutex);
    
    // Wait while buffer is EMPTY
    while (buf->count == 0) {
        pthread_cond_wait(&buf->cond, &buf->mutex);
    }
    
    // Remove item
    *item = buf->buffer[buf->out];
    buf->out = (buf->out + 1) % BUFFER_SIZE;
    buf->count--;
    
    // Signal that buffer state changed
    // BUG: What if this wakes another CONSUMER when buffer is still near-empty?
    pthread_cond_signal(&buf->cond);  // PROBLEM!
    
    pthread_mutex_unlock(&buf->mutex);
}
 
// SCENARIO LEADING TO DEADLOCK:
// 1. Buffer is full: 2 consumers sleeping, 1 producer sleeping
// 2. Consumer A runs, consumes item, count = BUFFER_SIZE - 1
// 3. Consumer A signals, wakes... Consumer B (wrong thread type!)
// 4. Consumer B wakes, count > 0, so it consumes, count = BUFFER_SIZE - 2
// 5. Consumer B signals, wakes... Consumer A (who re-entered wait)
// 6. Consumer A wakes, count > 0, consumes, count = BUFFER_SIZE - 3
// 7. All consumers sleeping (count = 0), producer still sleeping
// 8. DEADLOCK: No one will wake the producer!

The Root Cause

The fundamental problem is that signal() makes NO guarantee about WHICH thread it wakes. When different thread types (producers/consumers) share a condition variable, a signal intended for one type might wake the other type. If the wrong type wakes and re-waits, and if this happens repeatedly, the intended recipient may never wake—leading to deadlock.

The Broadcast Solution:

One way to fix this problem is to use broadcast instead of signal. By waking ALL waiting threads, we guarantee that if any thread of the correct type is waiting, it will be awakened:

Broadcast Fixes Mixed Waiters
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Using broadcast to fix the mixed waiters problem
// (Note: Separate condition variables is often a better solution)
 
void producer(bounded_buffer_t *buf, int item) {
    pthread_mutex_lock(&buf->mutex);
    
    while (buf->count == BUFFER_SIZE) {
        pthread_cond_wait(&buf->cond, &buf->mutex);
    }
    
    buf->buffer[buf->in] = item;
    buf->in = (buf->in + 1) % BUFFER_SIZE;
    buf->count++;
    
    // Broadcast wakes ALL waiters
    // Both any waiting consumers AND any waiting producers
    // At least one consumer will be able to proceed
    pthread_cond_broadcast(&buf->cond);  // SAFE but potentially wasteful
    
    pthread_mutex_unlock(&buf->mutex);
}
 
void consumer(bounded_buffer_t *buf, int *item) {
    pthread_mutex_lock(&buf->mutex);
    
    while (buf->count == 0) {
        pthread_cond_wait(&buf->cond, &buf->mutex);
    }
    
    *item = buf->buffer[buf->out];
    buf->out = (buf->out + 1) % BUFFER_SIZE;
    buf->count--;
    
    // Broadcast wakes ALL waiters
    // Both any waiting producers AND any waiting consumers
    // At least one producer will be able to proceed (if any waiting)
    pthread_cond_broadcast(&buf->cond);  // SAFE but potentially wasteful
    
    pthread_mutex_unlock(&buf->mutex);
}
 
// Now the scenario works correctly:
// 1. Buffer is full: 2 consumers sleeping, 1 producer sleeping
// 2. Consumer A runs, consumes item, count = BUFFER_SIZE - 1
// 3. Consumer A BROADCASTS, wakes ALL: Consumer B AND Producer P
// 4. Consumer B wakes, acquires mutex first, count > 0, consumes
// 5. Consumer B BROADCASTS again
// 6. Producer P eventually acquires mutex, count < BUFFER_SIZE, produces
// 7. No deadlock possible!

Broadcast Mechanics: What Actually Happens

Let's trace through exactly what happens during a broadcast operation, examining the state transitions and the race for mutex reacquisition that follows.

Step-by-Step Broadcast Execution:

Consider a condition variable with 4 threads waiting: T1, T2, T3, T4. Thread T0 calls broadcast().

INITIAL STATE:
─────────────────────────────────────────────────────
 Condition Variable CV │ Mutex M        │ Thread States
─────────────────────────────────────────────────────
 Wait Queue:           │ Held by: T0    │ T0: RUNNING
 [T1] → [T2] → [T3] → [T4] │              │ T1: BLOCKED (waiting on CV)
                        │                │ T2: BLOCKED (waiting on CV)
                        │                │ T3: BLOCKED (waiting on CV)
                        │                │ T4: BLOCKED (waiting on CV)
─────────────────────────────────────────────────────

Phase 1: Broadcast Execution (T0 calls pthread_cond_broadcast(&CV))

AFTER BROADCAST (before T0 releases mutex):
─────────────────────────────────────────────────────
 Condition Variable CV │ Mutex M         │ Thread States
─────────────────────────────────────────────────────
 Wait Queue:           │ Held by: T0     │ T0: RUNNING
 [EMPTY]               │ Wait Queue:     │ T1: BLOCKED (waiting on M)
                        │ [T1]→[T2]→[T3]→[T4] │ T2: BLOCKED (waiting on M)
                        │                 │ T3: BLOCKED (waiting on M)
                        │                 │ T4: BLOCKED (waiting on M)
─────────────────────────────────────────────────────

The broadcast moved all 4 threads from the condition variable's wait queue to the mutex's wait queue. They are still blocked—but now they're blocked on the mutex, not the condition.

Phase 2: T0 Releases Mutex

AFTER T0 RELEASES MUTEX:
─────────────────────────────────────────────────────
 Condition Variable CV │ Mutex M         │ Thread States
─────────────────────────────────────────────────────
 Wait Queue:           │ Held by: T1     │ T0: RUNNING (past critical)
 [EMPTY]               │ Wait Queue:     │ T1: RUNNING (recheck condition!)
                        │ [T2]→[T3]→[T4]  │ T2: BLOCKED (waiting on M)
                        │                 │ T3: BLOCKED (waiting on M)
                        │                 │ T4: BLOCKED (waiting on M)
─────────────────────────────────────────────────────

Now T1 acquired the mutex and can continue executing in its wait() call. The first thing it must do is re-check the condition in its while loop.

Phase 3: Sequential Mutex Handoff

Each thread acquires the mutex one at a time, re-checks its condition, and either:

Proceeds if the condition is satisfied
Re-waits if the condition is not satisfied

SEQUENTIAL EXECUTION:
─────────────────────────────────────────────────────
Time │ Mutex Holder │ Action                  │ Outcome
─────────────────────────────────────────────────────
 t1  │ T1           │ Recheck while(cond)     │ cond=false, proceed
 t2  │ T2           │ Recheck while(cond)     │ cond=true, RE-WAIT!
 t3  │ T3           │ Recheck while(cond)     │ cond=true, RE-WAIT!
 t4  │ T4           │ Recheck while(cond)     │ cond=true, RE-WAIT!
─────────────────────────────────────────────────────
                                                     
 Outcome: Only T1 actually proceeded!               
 T2, T3, T4 woke up, acquired mutex, checked,       
 found condition still true, and went back to sleep.
                                                     
 This is the essence of the THUNDERING HERD problem.
─────────────────────────────────────────────────────

The While Loop is Critical

This detailed trace shows why condition variables MUST always use while loops, not if statements. After broadcast, multiple threads wake up and compete for the mutex. Only one can proceed at a time. By the time thread T2 gets the mutex, the condition may have changed again (T1 consumed the resource). Without the while loop re-check, T2 would proceed incorrectly.

Memory Ordering and Visibility Guarantees

The broadcast operation has important memory ordering implications that are essential to understand for correct concurrent programming.

Memory Visibility After Broadcast:

When a thread calls broadcast after modifying shared state, the following guarantees hold:

Before broadcast: The broadcasting thread modifies shared state while holding the mutex
Broadcast call: Acts as a release operation (on most implementations)
Mutex release: Provides the formal memory barrier
Waking threads: Each thread that reacquires the mutex sees all modifications made before the broadcast

The key insight is that memory visibility is not guaranteed by broadcast itself, but by the mutex operations that surround it.

Memory Ordering with Broadcast
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Memory ordering guarantees illustrated
 
typedef struct {
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    int data;
    int ready_count;
    int total_expected;
} shared_state_t;
 
// Signaling thread modifies state and broadcasts
void signal_all_ready(shared_state_t *state) {
    pthread_mutex_lock(&state->mutex);
    
    // (1) Modify shared state while holding mutex
    state->data = compute_important_value();
    state->ready_count = state->total_expected;
    
    // (2) MEMORY ORDERING: All writes above are guaranteed to be
    // visible to any thread that subsequently acquires this mutex.
    // The mutex_unlock provides the release barrier.
    
    // (3) Wake all waiting threads
    pthread_cond_broadcast(&state->cond);
    
    pthread_mutex_unlock(&state->mutex);
    // (4) Release barrier here ensures visibility
}
 
// Waiting threads
void wait_for_ready(shared_state_t *state) {
    pthread_mutex_lock(&state->mutex);
    // (5) MEMORY ORDERING: mutex_lock provides acquire barrier
    
    while (state->ready_count == 0) {
        pthread_cond_wait(&state->cond, &state->mutex);
        // After waking, mutex is reacquired with full visibility
    }
    
    // (6) Here we are GUARANTEED to see:
    //     - state->data as set by signal_all_ready()
    //     - state->ready_count as set by signal_all_ready()
    //     - Any other modifications made before the broadcast
    
    int local_data = state->data;  // Guaranteed correct value
    
    pthread_mutex_unlock(&state->mutex);
    
    process_data(local_data);
}

Common Mistake: Broadcast Without Mutex

Calling broadcast without holding the mutex is technically allowed in POSIX but can lead to lost wakeups and race conditions. If you modify shared state and then release the mutex before broadcasting, a new waiter could enter wait() after your unlock but before your broadcast, and then be stuck waiting forever. Always broadcast while holding the mutex for safety.

The Happens-Before Relationship:

In formal memory model terms, broadcast establishes the following relationships:

┌─────────────────────────────────────────────────────────────┐
│            HAPPENS-BEFORE CHAIN WITH BROADCAST              │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Thread T0 (Broadcaster):                                   │
│    state.data = 42;        // Write W1                      │
│          ↓                                                  │
│    broadcast();            // Release semantics             │
│          ↓                                                  │
│    mutex_unlock();         // Release barrier               │
│          │                                                  │
│          │ ─────────── synchronizes-with ────────────→      │
│          │                                                  │
│  Thread T1/T2/T3/T4 (Waiters):                             │
│          │                                                  │
│    mutex_lock();           // Acquire barrier               │
│          ↓                                                  │
│    read(state.data);       // READ R1: sees 42 (from W1)   │
│                                                             │
│  The synchronizes-with edge guarantees W1 happens-before R1│
└─────────────────────────────────────────────────────────────┘

This formal relationship guarantees that all modifications made by the broadcaster before the unlock are visible to all threads that wake up and acquire the mutex.

POSIX pthread_cond_broadcast: The Standard Interface

The POSIX Threads standard defines the broadcast operation through pthread_cond_broadcast(). Understanding its precise specification is essential for writing portable, correct concurrent code.

POSIX Broadcast Specification
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <pthread.h>
 
// Function signature
int pthread_cond_broadcast(pthread_cond_t *cond);
 
// Parameters:
//   cond - pointer to the condition variable to broadcast on
//
// Return value:
//   0        - Success
//   EINVAL   - cond does not refer to an initialized condition variable
//
// Behavior:
//   - Unblocks ALL threads currently blocked on the condition variable
//   - If no threads are blocked, the function has no effect
//   - The threads are unblocked in an unspecified order
//   - Each unblocked thread must reacquire the mutex before returning from wait()
//   - The calling thread need not hold the mutex
//     (but this is rarely a good idea in practice)
 
// Example: Barrier implementation using broadcast
typedef struct {
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    int count;            // Number of threads that have arrived
    int threshold;        // Number of threads to wait for
    int generation;       // Barrier generation (for reuse)
} barrier_t;
 
int barrier_init(barrier_t *b, int threshold) {
    pthread_mutex_init(&b->mutex, NULL);
    pthread_cond_init(&b->cond, NULL);
    b->count = 0;
    b->threshold = threshold;
    b->generation = 0;
    return 0;
}
 
int barrier_wait(barrier_t *b) {
    pthread_mutex_lock(&b->mutex);
    
    int my_generation = b->generation;
    b->count++;
    
    if (b->count == b->threshold) {
        // Last thread to arrive: release all others
        b->count = 0;
        b->generation++;  // New generation for barrier reuse
        
        // BROADCAST: Wake ALL waiting threads
        pthread_cond_broadcast(&b->cond);
        
        pthread_mutex_unlock(&b->mutex);
        return PTHREAD_BARRIER_SERIAL_THREAD;  // Indicate this thread was last
    } else {
        // Wait for other threads
        while (my_generation == b->generation) {
            pthread_cond_wait(&b->cond, &b->mutex);
        }
        pthread_mutex_unlock(&b->mutex);
        return 0;
    }
}
 
int barrier_destroy(barrier_t *b) {
    pthread_mutex_destroy(&b->mutex);
    pthread_cond_destroy(&b->cond);
    return 0;
}

pthread_cond_broadcast vs pthread_cond_signal Comparison
Aspect	pthread_cond_signal	pthread_cond_broadcast
Threads awakened	At most one	All blocked threads
Empty wait queue	No-op (returns 0)	No-op (returns 0)
Return value	0 on success, EINVAL on error	0 on success, EINVAL on error
Must hold mutex?	Not required by spec, but recommended	Not required by spec, but recommended
Wake order	Unspecified (usually FIFO)	Unspecified
Scheduling priority	Implementation-defined	Implementation-defined
Typical use case	One waiter can proceed	All waiters might need to proceed

Implementation Tip

Although POSIX allows calling broadcast without holding the mutex, most production code should call broadcast while holding the mutex. This ensures that the state change and the notification are atomic from the perspective of waiting threads, preventing subtle race conditions.

Implementation Variations Across Systems

Different operating systems and threading libraries implement broadcast with subtle variations. Understanding these differences is crucial for writing portable and performant concurrent code.

Linux's Native POSIX Thread Library (NPTL) implements condition variables using futexes (fast userspace mutexes).

Broadcast Implementation:

Uses FUTEX_WAKE with a count of INT_MAX to wake all waiters
Threads are moved from the futex wait queue to the runnable state
The kernel handles wake-up ordering based on scheduler policies
Supports priority inheritance when configured

Performance Characteristics:

Wake-up is O(n) where n is the number of waiters
Context switch overhead for each woken thread
Kernel involvement is minimal but present

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Simplified view of glibc pthread_cond_broadcast internals
// (Actual implementation is more complex)
 
int __pthread_cond_broadcast(pthread_cond_t *cond) {
    // Check for valid condition variable
    if (cond == NULL) return EINVAL;
    
    // Atomically wake all waiters using futex
    // FUTEX_WAKE with INT_MAX means "wake everyone"
    syscall(SYS_futex, &cond->__data.__lock, 
            FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
    
    return 0;
}

The Broadcast vs Signal Decision Framework

Choosing between signal and broadcast is one of the fundamental decisions in condition variable programming. This section provides a systematic framework for making the right choice.

The Decision Criteria:

Use signal() when ALL of the following are true:

Uniform waiters: All waiting threads are waiting for the same logical condition
One can proceed: The state change allows exactly one waiter to proceed
Interchangeable work: Any waiter can handle the work (threads are equivalent)
Simple condition: The condition predicate is the same for all waiters

Use broadcast() when ANY of the following are true:

Different conditions: Waiters may be waiting for different conditions on the same CV
Multiple can proceed: The state change allows multiple waiters to proceed
All must respond: All waiters need to respond to the state change (e.g., shutdown)
Condition complexity: You're unsure whether signal is sufficient

Signal is Correct

•Single producer, single consumer
•Thread pool with identical tasks
•Simple mutex-protected queue
•Single resource availability
•Homogeneous waiter population

Broadcast is Required

•Barrier synchronization
•Shutdown notification
•State transitions affecting all
•Reader-writer lock transitions
•Mixed or heterogeneous waiters

The Conservative Choice

When in doubt, use broadcast. It's always correct (though potentially less efficient). Signal can cause subtle bugs if used incorrectly, while broadcast's main downside is performance. Correctness should always trump performance in concurrent programming. You can optimize to signal later once you've proven correctness.

Summary: The Broadcast Operation

We've explored the broadcast operation in depth—from its formal semantics to its implementation across different systems. Let's consolidate the essential knowledge:

Key Takeaways

•Broadcast wakes ALL waiting threads — Every thread blocked on the condition variable is made runnable, moving from the CV's wait queue to competing for the mutex.
•Threads still must reacquire the mutex — Broadcast merely wakes threads; they cannot proceed until they each acquire the mutex, one at a time.
•The while loop is essential — Because multiple threads wake up and only one can hold the mutex at a time, each must re-check the condition after waking.
•Memory visibility comes from the mutex — Broadcast itself doesn't provide memory barriers; the mutex lock/unlock pair ensures visibility.
•Broadcast is always correct, signal may not be — When unsure, broadcast is the safe choice. Signal is an optimization that requires careful analysis.
•Different conditions on same CV require broadcast — If waiters are heterogeneous (e.g., producers and consumers sharing a CV), broadcast prevents deadlock.

Next Steps:

Now that you understand the mechanics of broadcast, the next page explores when to broadcast—the circumstances and design patterns that call for broadcast over signal, and how to recognize these situations in real-world code.

Page Complete

You now understand the broadcast operation at a deep level—its semantics, mechanics, memory ordering implications, and variations across platforms. You're equipped to reason about when broadcast is necessary and how it behaves in complex concurrent systems. Next, we'll explore the specific scenarios that call for broadcast.

1 / 5

Loading learning content...

Operating SystemsBroadcast

Broadcast: Waking Multiple Waiting Threads

LevelIntermediate

Duration90 mins

TopicBroadcast

1 / 5

Broadcast Operation: Waking All Waiting Threads

The Power of Waking Everyone

What You Will Learn

Broadcast Semantics: The Formal Definition

Formal Specification:

Given a condition variable cv and a set of threads W = {t₁, t₂, ..., tₙ} currently blocked in cv.wait(), the operation cv.broadcast() performs the following:

Identify all waiters: Atomically snapshot the current wait queue containing all threads in W
Wake all threads: For each thread tᵢ in W, mark it as runnable and remove it from the wait queue
Mutex reacquisition: Each awakened thread must reacquire the mutex before returning from wait()
No ordering guarantees: The order in which awakened threads actually run is scheduler-dependent

Critical Invariant

Broadcast Semantics Pseudocode
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Broadcast operation semantics (simplified internal view)
typedef struct {
    mutex_t internal_lock;    // Protects wait queue
    queue_t wait_queue;       // Queue of waiting threads
} condition_variable_t;
 
// Broadcast operation - wakes ALL waiting threads
void cond_broadcast(condition_variable_t *cv) {
    // Acquire internal lock to protect wait queue manipulation
    mutex_lock(&cv->internal_lock);
    
    // Count of threads we will wake
    int threads_to_wake = queue_size(&cv->wait_queue);
    
    // Wake ALL threads in the wait queue
    while (!queue_is_empty(&cv->wait_queue)) {
        thread_t *t = queue_dequeue(&cv->wait_queue);
        
        // Mark thread as runnable
        // It will compete for the associated mutex
        scheduler_make_runnable(t);
    }
    
    mutex_unlock(&cv->internal_lock);
    
    // All 'threads_to_wake' threads are now eligible to run
    // They will compete for the mutex when scheduled
}
 
// Contrast with signal - wakes AT MOST ONE thread
void cond_signal(condition_variable_t *cv) {
    mutex_lock(&cv->internal_lock);
    
    if (!queue_is_empty(&cv->wait_queue)) {
        thread_t *t = queue_dequeue(&cv->wait_queue);
        scheduler_make_runnable(t);
        // Only ONE thread is awakened
    }
    // If queue is empty, signal is a no-op
    
    mutex_unlock(&cv->internal_lock);
}

Key semantic differences between broadcast and signal:

Aspect	signal()	broadcast()
Threads awakened	At most 1	All waiting
Empty queue behavior	No-op	No-op
Memory cost	Minimal	O(n) for n waiters
Scheduling cost	1 context switch	Up to n context switches
Lost signal risk	Yes (if not used carefully)	No
Thundering herd risk	No	Yes

Why Signal Isn't Always Enough

Scenarios Where Signal Fails

•Asymmetric waiter conditions: Different threads wait for different conditions on the same condition variable. Signaling might wake a thread that cannot proceed, while one that could proceed remains asleep.
•Condition invalidation: The awakened thread might find the condition no longer holds by the time it reacquires the mutex (due to another thread), and it re-waits—now no thread proceeds despite resources being available.
•Multiple resources available: When multiple resources become available simultaneously, signal() wakes only one consumer, leaving other available resources unused.
•State transitions affecting all waiters: When a server shuts down, ALL connected clients need to wake up and handle disconnection—not just one.
•Barrier synchronization: When a barrier is satisfied, ALL threads at the barrier must proceed—not just one.

The Classic Example: Mixed Waiters Problem

Consider a bounded buffer where producers and consumers share a single condition variable. This is a common (but problematic) design pattern:

Mixed Waiters Problem
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// DANGEROUS: Single condition variable for both producers and consumers
// This pattern is prone to deadlock when using signal()
 
typedef struct {
    int buffer[BUFFER_SIZE];
    int count;
    int in, out;
    pthread_mutex_t mutex;
    pthread_cond_t cond;  // Shared by BOTH producers AND consumers
} bounded_buffer_t;
 
void producer(bounded_buffer_t *buf, int item) {
    pthread_mutex_lock(&buf->mutex);
    
    // Wait while buffer is FULL
    while (buf->count == BUFFER_SIZE) {
        pthread_cond_wait(&buf->cond, &buf->mutex);
    }
    
    // Insert item
    buf->buffer[buf->in] = item;
    buf->in = (buf->in + 1) % BUFFER_SIZE;
    buf->count++;
    
    // Signal that buffer state changed
    // BUG: What if this wakes another PRODUCER when buffer is still near-full?
    pthread_cond_signal(&buf->cond);  // PROBLEM!
    
    pthread_mutex_unlock(&buf->mutex);
}
 
void consumer(bounded_buffer_t *buf, int *item) {
    pthread_mutex_lock(&buf->mutex);
    
    // Wait while buffer is EMPTY
    while (buf->count == 0) {
        pthread_cond_wait(&buf->cond, &buf->mutex);
    }
    
    // Remove item
    *item = buf->buffer[buf->out];
    buf->out = (buf->out + 1) % BUFFER_SIZE;
    buf->count--;
    
    // Signal that buffer state changed
    // BUG: What if this wakes another CONSUMER when buffer is still near-empty?
    pthread_cond_signal(&buf->cond);  // PROBLEM!
    
    pthread_mutex_unlock(&buf->mutex);
}
 
// SCENARIO LEADING TO DEADLOCK:
// 1. Buffer is full: 2 consumers sleeping, 1 producer sleeping
// 2. Consumer A runs, consumes item, count = BUFFER_SIZE - 1
// 3. Consumer A signals, wakes... Consumer B (wrong thread type!)
// 4. Consumer B wakes, count > 0, so it consumes, count = BUFFER_SIZE - 2
// 5. Consumer B signals, wakes... Consumer A (who re-entered wait)
// 6. Consumer A wakes, count > 0, consumes, count = BUFFER_SIZE - 3
// 7. All consumers sleeping (count = 0), producer still sleeping
// 8. DEADLOCK: No one will wake the producer!

The Root Cause

The Broadcast Solution:

One way to fix this problem is to use broadcast instead of signal. By waking ALL waiting threads, we guarantee that if any thread of the correct type is waiting, it will be awakened:

Broadcast Fixes Mixed Waiters
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Using broadcast to fix the mixed waiters problem
// (Note: Separate condition variables is often a better solution)
 
void producer(bounded_buffer_t *buf, int item) {
    pthread_mutex_lock(&buf->mutex);
    
    while (buf->count == BUFFER_SIZE) {
        pthread_cond_wait(&buf->cond, &buf->mutex);
    }
    
    buf->buffer[buf->in] = item;
    buf->in = (buf->in + 1) % BUFFER_SIZE;
    buf->count++;
    
    // Broadcast wakes ALL waiters
    // Both any waiting consumers AND any waiting producers
    // At least one consumer will be able to proceed
    pthread_cond_broadcast(&buf->cond);  // SAFE but potentially wasteful
    
    pthread_mutex_unlock(&buf->mutex);
}
 
void consumer(bounded_buffer_t *buf, int *item) {
    pthread_mutex_lock(&buf->mutex);
    
    while (buf->count == 0) {
        pthread_cond_wait(&buf->cond, &buf->mutex);
    }
    
    *item = buf->buffer[buf->out];
    buf->out = (buf->out + 1) % BUFFER_SIZE;
    buf->count--;
    
    // Broadcast wakes ALL waiters
    // Both any waiting producers AND any waiting consumers
    // At least one producer will be able to proceed (if any waiting)
    pthread_cond_broadcast(&buf->cond);  // SAFE but potentially wasteful
    
    pthread_mutex_unlock(&buf->mutex);
}
 
// Now the scenario works correctly:
// 1. Buffer is full: 2 consumers sleeping, 1 producer sleeping
// 2. Consumer A runs, consumes item, count = BUFFER_SIZE - 1
// 3. Consumer A BROADCASTS, wakes ALL: Consumer B AND Producer P
// 4. Consumer B wakes, acquires mutex first, count > 0, consumes
// 5. Consumer B BROADCASTS again
// 6. Producer P eventually acquires mutex, count < BUFFER_SIZE, produces
// 7. No deadlock possible!

Broadcast Mechanics: What Actually Happens

Let's trace through exactly what happens during a broadcast operation, examining the state transitions and the race for mutex reacquisition that follows.

Step-by-Step Broadcast Execution:

Consider a condition variable with 4 threads waiting: T1, T2, T3, T4. Thread T0 calls broadcast().

INITIAL STATE:
─────────────────────────────────────────────────────
 Condition Variable CV │ Mutex M        │ Thread States
─────────────────────────────────────────────────────
 Wait Queue:           │ Held by: T0    │ T0: RUNNING
 [T1] → [T2] → [T3] → [T4] │              │ T1: BLOCKED (waiting on CV)
                        │                │ T2: BLOCKED (waiting on CV)
                        │                │ T3: BLOCKED (waiting on CV)
                        │                │ T4: BLOCKED (waiting on CV)
─────────────────────────────────────────────────────

Phase 1: Broadcast Execution (T0 calls pthread_cond_broadcast(&CV))

AFTER BROADCAST (before T0 releases mutex):
─────────────────────────────────────────────────────
 Condition Variable CV │ Mutex M         │ Thread States
─────────────────────────────────────────────────────
 Wait Queue:           │ Held by: T0     │ T0: RUNNING
 [EMPTY]               │ Wait Queue:     │ T1: BLOCKED (waiting on M)
                        │ [T1]→[T2]→[T3]→[T4] │ T2: BLOCKED (waiting on M)
                        │                 │ T3: BLOCKED (waiting on M)
                        │                 │ T4: BLOCKED (waiting on M)
─────────────────────────────────────────────────────

The broadcast moved all 4 threads from the condition variable's wait queue to the mutex's wait queue. They are still blocked—but now they're blocked on the mutex, not the condition.

Phase 2: T0 Releases Mutex

AFTER T0 RELEASES MUTEX:
─────────────────────────────────────────────────────
 Condition Variable CV │ Mutex M         │ Thread States
─────────────────────────────────────────────────────
 Wait Queue:           │ Held by: T1     │ T0: RUNNING (past critical)
 [EMPTY]               │ Wait Queue:     │ T1: RUNNING (recheck condition!)
                        │ [T2]→[T3]→[T4]  │ T2: BLOCKED (waiting on M)
                        │                 │ T3: BLOCKED (waiting on M)
                        │                 │ T4: BLOCKED (waiting on M)
─────────────────────────────────────────────────────

Now T1 acquired the mutex and can continue executing in its wait() call. The first thing it must do is re-check the condition in its while loop.

Phase 3: Sequential Mutex Handoff

Each thread acquires the mutex one at a time, re-checks its condition, and either:

Proceeds if the condition is satisfied
Re-waits if the condition is not satisfied

SEQUENTIAL EXECUTION:
─────────────────────────────────────────────────────
Time │ Mutex Holder │ Action                  │ Outcome
─────────────────────────────────────────────────────
 t1  │ T1           │ Recheck while(cond)     │ cond=false, proceed
 t2  │ T2           │ Recheck while(cond)     │ cond=true, RE-WAIT!
 t3  │ T3           │ Recheck while(cond)     │ cond=true, RE-WAIT!
 t4  │ T4           │ Recheck while(cond)     │ cond=true, RE-WAIT!
─────────────────────────────────────────────────────
                                                     
 Outcome: Only T1 actually proceeded!               
 T2, T3, T4 woke up, acquired mutex, checked,       
 found condition still true, and went back to sleep.
                                                     
 This is the essence of the THUNDERING HERD problem.
─────────────────────────────────────────────────────

The While Loop is Critical

Memory Ordering and Visibility Guarantees

The broadcast operation has important memory ordering implications that are essential to understand for correct concurrent programming.

Memory Visibility After Broadcast:

When a thread calls broadcast after modifying shared state, the following guarantees hold:

Before broadcast: The broadcasting thread modifies shared state while holding the mutex
Broadcast call: Acts as a release operation (on most implementations)
Mutex release: Provides the formal memory barrier
Waking threads: Each thread that reacquires the mutex sees all modifications made before the broadcast

The key insight is that memory visibility is not guaranteed by broadcast itself, but by the mutex operations that surround it.

Memory Ordering with Broadcast
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Memory ordering guarantees illustrated
 
typedef struct {
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    int data;
    int ready_count;
    int total_expected;
} shared_state_t;
 
// Signaling thread modifies state and broadcasts
void signal_all_ready(shared_state_t *state) {
    pthread_mutex_lock(&state->mutex);
    
    // (1) Modify shared state while holding mutex
    state->data = compute_important_value();
    state->ready_count = state->total_expected;
    
    // (2) MEMORY ORDERING: All writes above are guaranteed to be
    // visible to any thread that subsequently acquires this mutex.
    // The mutex_unlock provides the release barrier.
    
    // (3) Wake all waiting threads
    pthread_cond_broadcast(&state->cond);
    
    pthread_mutex_unlock(&state->mutex);
    // (4) Release barrier here ensures visibility
}
 
// Waiting threads
void wait_for_ready(shared_state_t *state) {
    pthread_mutex_lock(&state->mutex);
    // (5) MEMORY ORDERING: mutex_lock provides acquire barrier
    
    while (state->ready_count == 0) {
        pthread_cond_wait(&state->cond, &state->mutex);
        // After waking, mutex is reacquired with full visibility
    }
    
    // (6) Here we are GUARANTEED to see:
    //     - state->data as set by signal_all_ready()
    //     - state->ready_count as set by signal_all_ready()
    //     - Any other modifications made before the broadcast
    
    int local_data = state->data;  // Guaranteed correct value
    
    pthread_mutex_unlock(&state->mutex);
    
    process_data(local_data);
}

Common Mistake: Broadcast Without Mutex

The Happens-Before Relationship:

In formal memory model terms, broadcast establishes the following relationships:

┌─────────────────────────────────────────────────────────────┐
│            HAPPENS-BEFORE CHAIN WITH BROADCAST              │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Thread T0 (Broadcaster):                                   │
│    state.data = 42;        // Write W1                      │
│          ↓                                                  │
│    broadcast();            // Release semantics             │
│          ↓                                                  │
│    mutex_unlock();         // Release barrier               │
│          │                                                  │
│          │ ─────────── synchronizes-with ────────────→      │
│          │                                                  │
│  Thread T1/T2/T3/T4 (Waiters):                             │
│          │                                                  │
│    mutex_lock();           // Acquire barrier               │
│          ↓                                                  │
│    read(state.data);       // READ R1: sees 42 (from W1)   │
│                                                             │
│  The synchronizes-with edge guarantees W1 happens-before R1│
└─────────────────────────────────────────────────────────────┘

This formal relationship guarantees that all modifications made by the broadcaster before the unlock are visible to all threads that wake up and acquire the mutex.

POSIX pthread_cond_broadcast: The Standard Interface

The POSIX Threads standard defines the broadcast operation through pthread_cond_broadcast(). Understanding its precise specification is essential for writing portable, correct concurrent code.

POSIX Broadcast Specification
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <pthread.h>
 
// Function signature
int pthread_cond_broadcast(pthread_cond_t *cond);
 
// Parameters:
//   cond - pointer to the condition variable to broadcast on
//
// Return value:
//   0        - Success
//   EINVAL   - cond does not refer to an initialized condition variable
//
// Behavior:
//   - Unblocks ALL threads currently blocked on the condition variable
//   - If no threads are blocked, the function has no effect
//   - The threads are unblocked in an unspecified order
//   - Each unblocked thread must reacquire the mutex before returning from wait()
//   - The calling thread need not hold the mutex
//     (but this is rarely a good idea in practice)
 
// Example: Barrier implementation using broadcast
typedef struct {
    pthread_mutex_t mutex;
    pthread_cond_t cond;
    int count;            // Number of threads that have arrived
    int threshold;        // Number of threads to wait for
    int generation;       // Barrier generation (for reuse)
} barrier_t;
 
int barrier_init(barrier_t *b, int threshold) {
    pthread_mutex_init(&b->mutex, NULL);
    pthread_cond_init(&b->cond, NULL);
    b->count = 0;
    b->threshold = threshold;
    b->generation = 0;
    return 0;
}
 
int barrier_wait(barrier_t *b) {
    pthread_mutex_lock(&b->mutex);
    
    int my_generation = b->generation;
    b->count++;
    
    if (b->count == b->threshold) {
        // Last thread to arrive: release all others
        b->count = 0;
        b->generation++;  // New generation for barrier reuse
        
        // BROADCAST: Wake ALL waiting threads
        pthread_cond_broadcast(&b->cond);
        
        pthread_mutex_unlock(&b->mutex);
        return PTHREAD_BARRIER_SERIAL_THREAD;  // Indicate this thread was last
    } else {
        // Wait for other threads
        while (my_generation == b->generation) {
            pthread_cond_wait(&b->cond, &b->mutex);
        }
        pthread_mutex_unlock(&b->mutex);
        return 0;
    }
}
 
int barrier_destroy(barrier_t *b) {
    pthread_mutex_destroy(&b->mutex);
    pthread_cond_destroy(&b->cond);
    return 0;
}

pthread_cond_broadcast vs pthread_cond_signal Comparison
Aspect	pthread_cond_signal	pthread_cond_broadcast
Threads awakened	At most one	All blocked threads
Empty wait queue	No-op (returns 0)	No-op (returns 0)
Return value	0 on success, EINVAL on error	0 on success, EINVAL on error
Must hold mutex?	Not required by spec, but recommended	Not required by spec, but recommended
Wake order	Unspecified (usually FIFO)	Unspecified
Scheduling priority	Implementation-defined	Implementation-defined
Typical use case	One waiter can proceed	All waiters might need to proceed

Implementation Tip

Implementation Variations Across Systems

Different operating systems and threading libraries implement broadcast with subtle variations. Understanding these differences is crucial for writing portable and performant concurrent code.

Linux's Native POSIX Thread Library (NPTL) implements condition variables using futexes (fast userspace mutexes).

Broadcast Implementation:

Uses FUTEX_WAKE with a count of INT_MAX to wake all waiters
Threads are moved from the futex wait queue to the runnable state
The kernel handles wake-up ordering based on scheduler policies
Supports priority inheritance when configured

Performance Characteristics:

Wake-up is O(n) where n is the number of waiters
Context switch overhead for each woken thread
Kernel involvement is minimal but present

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Simplified view of glibc pthread_cond_broadcast internals
// (Actual implementation is more complex)
 
int __pthread_cond_broadcast(pthread_cond_t *cond) {
    // Check for valid condition variable
    if (cond == NULL) return EINVAL;
    
    // Atomically wake all waiters using futex
    // FUTEX_WAKE with INT_MAX means "wake everyone"
    syscall(SYS_futex, &cond->__data.__lock, 
            FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
    
    return 0;
}

The Broadcast vs Signal Decision Framework

Choosing between signal and broadcast is one of the fundamental decisions in condition variable programming. This section provides a systematic framework for making the right choice.

The Decision Criteria:

Use signal() when ALL of the following are true:

Uniform waiters: All waiting threads are waiting for the same logical condition
One can proceed: The state change allows exactly one waiter to proceed
Interchangeable work: Any waiter can handle the work (threads are equivalent)
Simple condition: The condition predicate is the same for all waiters

Use broadcast() when ANY of the following are true:

Different conditions: Waiters may be waiting for different conditions on the same CV
Multiple can proceed: The state change allows multiple waiters to proceed
All must respond: All waiters need to respond to the state change (e.g., shutdown)
Condition complexity: You're unsure whether signal is sufficient

Signal is Correct

•Single producer, single consumer
•Thread pool with identical tasks
•Simple mutex-protected queue
•Single resource availability
•Homogeneous waiter population

Broadcast is Required

•Barrier synchronization
•Shutdown notification
•State transitions affecting all
•Reader-writer lock transitions
•Mixed or heterogeneous waiters

The Conservative Choice

Summary: The Broadcast Operation

We've explored the broadcast operation in depth—from its formal semantics to its implementation across different systems. Let's consolidate the essential knowledge:

Key Takeaways

•Broadcast wakes ALL waiting threads — Every thread blocked on the condition variable is made runnable, moving from the CV's wait queue to competing for the mutex.
•Threads still must reacquire the mutex — Broadcast merely wakes threads; they cannot proceed until they each acquire the mutex, one at a time.
•The while loop is essential — Because multiple threads wake up and only one can hold the mutex at a time, each must re-check the condition after waking.
•Memory visibility comes from the mutex — Broadcast itself doesn't provide memory barriers; the mutex lock/unlock pair ensures visibility.
•Broadcast is always correct, signal may not be — When unsure, broadcast is the safe choice. Signal is an optimization that requires careful analysis.
•Different conditions on same CV require broadcast — If waiters are heterogeneous (e.g., producers and consumers sharing a CV), broadcast prevents deadlock.

Next Steps:

Page Complete

1 / 5