Semaphore Concepts - Learning Module

Loading content...

0/240

Binary Semaphores

The Foundation of Mutual Exclusion

A binary semaphore is a semaphore whose value is restricted to 0 or 1. Despite being a special case of the counting semaphore, binary semaphores are so fundamental and widely used that they deserve dedicated study. They provide the conceptual foundation for mutual exclusion—ensuring that only one thread can access a critical section at a time.

Binary semaphores sit at a fascinating intersection: they are simple enough to reason about formally, yet powerful enough to implement any synchronization pattern. They are the building blocks from which mutexes, condition variables, and higher-level constructs can be built.

This page explores binary semaphores in depth: their semantics, the critical distinction from mutexes, their use in signaling patterns, implementation considerations, and their role as the ancestor of modern locking primitives.

Learning Objectives

By the end of this page, you will be able to: (1) Define binary semaphores precisely and explain their restriction to {0, 1}, (2) Distinguish binary semaphores from mutexes (a crucial distinction), (3) Implement mutual exclusion using binary semaphores, (4) Apply binary semaphores in signaling patterns, and (5) Understand when to choose binary semaphores over alternatives.

Definition and Semantics

Formal Definition

A binary semaphore is a semaphore S where:

Domain: S.value ∈ {0, 1}
Initial value: S.value ∈ {0, 1} (typically 1 for mutual exclusion, 0 for signaling)
Invariant: S.value never exceeds 1 and never goes below 0

The P and V operations behave as follows:

P(S):

If S.value = 1: set S.value = 0 and proceed
If S.value = 0: block until S.value becomes 1

V(S):

Set S.value = 1 (regardless of previous value)
If processes were blocked, wake one

Note the key distinction from counting semaphores: V on a binary semaphore at value 1 is idempotent—it keeps the value at 1 rather than incrementing to 2.

Binary Semaphore State Transitions
Current Value	Operation	New Value	Thread Effect
1	P()	0	Thread proceeds (acquired)
0	P()	0	Thread blocks (waits)
0	V()	1	Value set to 1, waiter woken
1	V()	1	No change (idempotent)

The Two Initial Value Patterns

Binary semaphores are initialized to either 0 or 1, with distinct purposes:

Initialized to 1: Mutual Exclusion

Represents an available lock
First P acquires (value → 0)
Subsequent P's block until V releases
Pattern: P(); critical_section(); V();

Initialized to 0: Signaling/Synchronization

Represents "event not yet occurred"
Any P blocks immediately (value already 0)
V signals that event has occurred (value → 1)
Pattern: Thread A waits with P(), Thread B signals with V()

binary_sem_patterns.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
// Pattern 1: Mutual Exclusion (init = 1)
binary_semaphore_t mutex;
binary_sem_init(&mutex, 1);  // Available
 
void critical_operation() {
    P(&mutex);          // Acquire (blocks if 0)
    
    // Only one thread here at a time
    access_shared_resource();
    
    V(&mutex);          // Release (sets to 1)
}
 
// Pattern 2: Signaling (init = 0)
binary_semaphore_t event;
binary_sem_init(&event, 0);  // Not yet signaled
 
// Thread A: Waiter
void wait_for_event() {
    P(&event);          // Block until signaled
    // Event has occurred
    react_to_event();
}
 
// Thread B: Signaler
void signal_event() {
    do_preparation();
    V(&event);          // Signal (sets to 1, wakes waiter)
    continue_work();
}

Binary ≠ Boolean

Don't confuse binary semaphores with boolean variables. A boolean variable has no blocking semantics—reading 'false' just gives you false. A binary semaphore with value 0 will BLOCK the calling thread until another thread sets it to 1. The blocking behavior is the entire point; the value being binary is incidental to the semantics.

Binary Semaphores vs. Mutexes: A Critical Distinction

One of the most important distinctions in synchronization is between binary semaphores and mutexes. They appear similar but have fundamentally different semantics.

The Key Difference: Ownership

Binary Semaphore:

No ownership. Any thread can call V(), regardless of which thread called P()
V() always succeeds, even if the thread never called P()
No concept of "the holder" of the semaphore

Mutex:

Has ownership. Only the thread that locked can unlock
Unlocking a mutex you don't own is undefined behavior or an error
The mutex knows which thread holds it

This difference has profound implications:

Binary Semaphore vs. Mutex Comparison
Aspect	Binary Semaphore	Mutex
Ownership	None (any thread can V)	Thread-owned (only locker unlocks)
Value tracking	0 or 1	Locked/Unlocked + owner thread ID
V/Unlock check	Always succeeds	May fail/abort if wrong thread
Primary use	Signaling, simple exclusion	Mutual exclusion with ownership
Recursive locking	Not supported (deadlock)	Can be supported (recursive mutex)
Priority inheritance	Not possible (no owner)	Possible (boost owner priority)
Debugging	Harder (no owner info)	Easier (can identify holder)

ownership_difference.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
// Demonstrating the ownership difference
 
// === BINARY SEMAPHORE: No ownership ===
binary_semaphore_t sem;
binary_sem_init(&sem, 1);
 
void thread_A() {
    P(&sem);          // Thread A "acquires"
    do_work_A();
    // Thread A finishes, but imagine it crashes here...
}
 
void thread_B() {
    // Thread A never released! But with semaphore:
    V(&sem);          // Thread B CAN release (no error)
    // This may be a bug, or intentional signaling
}
 
// === MUTEX: Ownership enforced ===
mutex_t mtx;
mutex_init(&mtx);
 
void thread_A() {
    mutex_lock(&mtx);   // Thread A owns
    do_work_A();
    // If A crashes without unlocking, mutex is stuck
    // But the system KNOWS thread A owns it
}
 
void thread_B() {
    mutex_unlock(&mtx);  // ERROR! Thread B doesn't own mtx
    // Behavior: undefined (crash, abort, silent corruption)
}

When Ownership Matters

Debugging: When a deadlock occurs, a mutex can tell you which thread holds it. Binary semaphores cannot—there's no "holder."

Priority Inheritance: If Thread L holds a mutex and high-priority Thread H waits, the system can boost L's priority. With binary semaphores, there's no owner to boost.

Recursive Locking: A recursive mutex allows the same thread to lock multiple times (incrementing a count). Binary semaphores cannot support this—the second P() by the same thread would deadlock.

Error Detection: A mutex can detect unlock-without-lock or wrong-thread-unlock errors. Semaphores cannot.

Choosing Correctly

Use mutexes for mutual exclusion (protecting critical sections). Use binary semaphores for signaling between threads or when ownership semantics don't apply. Using semaphores for pure mutual exclusion works but loses ownership benefits. Using mutexes for signaling (unlock from different thread) is typically an error or requires special API (e.g., Windows events).

Implementing Mutual Exclusion

The most common use of binary semaphores is implementing mutual exclusion—ensuring only one thread can execute a critical section at a time.

The Basic Pattern

Initialize semaphore to 1, bracketing the critical section with P and V:

mutual_exclusion.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
binary_semaphore_t critical_section_guard;
 
void init() {
    binary_sem_init(&critical_section_guard, 1);  // Available
}
 
// All threads use this pattern:
void protected_operation() {
    // === ENTRY SECTION ===
    P(&critical_section_guard);  // Acquire exclusive access
    // Only ONE thread proceeds past this point at a time
    
    // === CRITICAL SECTION ===
    // Safe to access/modify shared data
    read_shared_data();
    modify_shared_data();
    write_shared_data();
    
    // === EXIT SECTION ===
    V(&critical_section_guard);  // Release for others
    
    // === REMAINDER SECTION ===
    // Non-critical work
}

Proof of Mutual Exclusion

Claim: At most one thread can be in the critical section at any time.

Proof:

Initially, guard.value = 1
First thread to call P() succeeds: guard.value becomes 0
Any subsequent thread calling P() finds guard.value = 0 and blocks
When the first thread calls V(), guard.value becomes 1
Exactly one blocked thread (if any) wakes and its P() succeeds
By induction, at most one thread is ever past P() but before V()

Key insight: The critical section is protected because:

Entry requires decrementing from 1 to 0
Only one thread can do this at a time
Subsequent entries blocked until V() restores the value to 1

Handling Errors and Exceptions

A critical challenge: ensuring V() is called on ALL exit paths:

error_handling.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
// BAD: V not called on error path (semaphore leak)
void buggy_operation() {
    P(&guard);
    
    if (validate_input() != OK) {
        return;  // BUG! guard still held, will cause deadlock
    }
    
    do_work();
    V(&guard);
}
 
// GOOD: V called on all paths
void correct_operation() {
    P(&guard);
    
    if (validate_input() != OK) {
        V(&guard);  // Release before return
        return;
    }
    
    do_work();
    V(&guard);
}
 
// BETTER: Use cleanup mechanism (C++ RAII, Java try-finally, Go defer)
// C with cleanup label:
void robust_operation() {
    P(&guard);
    
    if (validate_input() != OK) {
        goto cleanup;
    }
    
    if (prepare_resources() != OK) {
        goto cleanup;
    }
    
    do_work();
    
cleanup:
    V(&guard);  // Always executed
}

RAII Pattern for Semaphores

In languages with destructors (C++, Rust) or defer (Go), wrap P/V in a guard object: constructor calls P(), destructor calls V(). This ensures V() is called when the guard goes out of scope, even if exceptions occur. Java's try-with-resources and Python's 'with' statement serve the same purpose for semaphores implementing the appropriate interfaces.

The Signaling Pattern

Beyond mutual exclusion, binary semaphores excel at signaling—one thread waiting for an event that another thread will cause.

The Basic Signaling Pattern

Initialize semaphore to 0. Waiter calls P() (blocks). Signaler calls V() (wakes waiter).

signaling_pattern.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
// One-time event signaling
binary_semaphore_t initialization_complete;
 
void init() {
    binary_sem_init(&initialization_complete, 0);  // Not yet complete
}
 
void initializer_thread() {
    // Perform lengthy initialization
    load_configuration();
    connect_to_database();
    warm_up_caches();
    
    // Signal completion
    V(&initialization_complete);  // Value: 0 → 1
    
    // Can continue with other work
}
 
void worker_thread() {
    // Wait for initialization before starting
    P(&initialization_complete);  // Blocks until V()
    
    // Guaranteed: initialization is complete
    start_processing_requests();
}

Rendezvous (Two-Way Signaling)

Two threads must both reach a point before either continues:

rendezvous.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
// Rendezvous: both threads wait for each other
binary_semaphore_t arrived_A;
binary_semaphore_t arrived_B;
 
void init() {
    binary_sem_init(&arrived_A, 0);
    binary_sem_init(&arrived_B, 0);
}
 
void thread_A() {
    do_work_before_rendezvous();
    
    V(&arrived_A);        // Signal: A has arrived
    P(&arrived_B);        // Wait for B to arrive
    
    // Both are here
    do_work_after_rendezvous();
}
 
void thread_B() {
    do_work_before_rendezvous();
    
    V(&arrived_B);        // Signal: B has arrived
    P(&arrived_A);        // Wait for A to arrive
    
    // Both are here
    do_work_after_rendezvous();
}
 
// Note: Order of V then P prevents deadlock
// If both did P then V: deadlock (both waiting, neither signals)

Signaling Advantages

•No busy waiting — Waiter sleeps, consumes no CPU
•Clear semantics — V means 'event occurred', P means 'wait for event'
•Works across threads — Signaler doesn't need to know who's waiting
•One-shot and repeating — Works for both patterns

Signaling Considerations

•V before P — Signal not lost (value becomes 1)
•Multiple waiters — One V wakes one waiter (not all)
•Multiple signals — Signals may 'accumulate' (use carefully)
•Cancellation — No built-in way to cancel a P wait

Signal Accumulation

If V() is called multiple times before any P(), a binary semaphore stays at 1 (not 2, 3...). This means 'extra' signals are lost. For counting signals, use a counting semaphore. For complex conditions, use condition variables which don't have 'state'—they only wake currently-waiting threads.

Implementation Details

Implementing binary semaphores raises specific considerations beyond general semaphore implementation.

Ensuring Binary Property

The key implementation detail is preventing the value from exceeding 1:

binary_sem_impl.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
// Binary semaphore implementation
typedef struct binary_semaphore {
    int value;          // Only 0 or 1
    spinlock_t lock;
    wait_queue_t waiters;
} binary_sem_t;
 
void binary_sem_init(binary_sem_t *s, int initial) {
    assert(initial == 0 || initial == 1);
    s->value = initial;
    spinlock_init(&s->lock);
    wait_queue_init(&s->waiters);
}
 
void P(binary_sem_t *s) {
    spinlock_acquire(&s->lock);
    
    while (s->value == 0) {
        // Block and release lock atomically
        wait_queue_add(&s->waiters, current_thread);
        current_thread->state = BLOCKED;
        spinlock_release(&s->lock);
        schedule();  // Switch to another thread
        spinlock_acquire(&s->lock);  // Reacquire on wakeup
    }
    
    // value was 1; make it 0
    s->value = 0;
    
    spinlock_release(&s->lock);
}
 
void V(binary_sem_t *s) {
    spinlock_acquire(&s->lock);
    
    // Set value to 1 (even if already 1)
    s->value = 1;  // NOT s->value++ (would break binary property)
    
    // Wake ONE waiter if any exist
    if (!wait_queue_empty(&s->waiters)) {
        thread_t *waiter = wait_queue_remove_first(&s->waiters);
        waiter->state = READY;
        add_to_ready_queue(waiter);
    }
    
    spinlock_release(&s->lock);
}

Strict Binary Semaphore

Some systems provide a strict binary semaphore (or BoundedSemaphore in Python) that errors if V is called when value is already 1:

strict_binary_sem.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
// Strict binary semaphore: V on value=1 is an error
int V_strict(binary_sem_t *s) {
    spinlock_acquire(&s->lock);
    
    if (s->value == 1) {
        // Already signaled - this is likely a bug
        spinlock_release(&s->lock);
        return -EOVERFLOW;  // Or assert/abort
    }
    
    s->value = 1;
    
    if (!wait_queue_empty(&s->waiters)) {
        thread_t *waiter = wait_queue_remove_first(&s->waiters);
        waiter->state = READY;
        add_to_ready_queue(waiter);
    }
    
    spinlock_release(&s->lock);
    return 0;
}
 
// Python's BoundedSemaphore
// >>> sem = threading.BoundedSemaphore(1)
// >>> sem.release()  # ValueError: Semaphore released too many times

Binary Semaphore Implementation Choices
Aspect	Standard Binary	Strict Binary	Trade-off
V on value=1	No-op (stays at 1)	Error/exception	Strictness vs. tolerance
Bug detection	Bugs may be hidden	Bugs surface quickly	Debugging vs. robustness
Signaling use	Multiple V's okay	Must track signal state	Flexibility vs. correctness
Implementation	Simpler	Slightly more complex	Complexity vs. safety

Choosing Standard vs. Strict

Use strict binary semaphores during development to catch bugs early. Standard binary semaphores are more forgiving but may hide logic errors. For mutual exclusion (matched P/V pairs), strictness helps catch missing P's. For signaling (where V may happen 'extra'), standard may be more appropriate.

Building Higher-Level Constructs

Binary semaphores are powerful building blocks. We can construct many higher-level synchronization primitives from them.

Building a Mutex from Binary Semaphores

A mutex adds ownership tracking to a binary semaphore:

mutex_from_binary_sem.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
// Mutex built from binary semaphore + ownership
typedef struct mutex {
    binary_sem_t sem;
    thread_id_t owner;     // Who currently holds it
    bool locked;           // Is it held?
} mutex_t;
 
void mutex_init(mutex_t *m) {
    binary_sem_init(&m->sem, 1);  // Available
    m->owner = INVALID_THREAD_ID;
    m->locked = false;
}
 
void mutex_lock(mutex_t *m) {
    P(&m->sem);                   // Acquire semaphore
    m->owner = current_thread_id();
    m->locked = true;
}
 
int mutex_unlock(mutex_t *m) {
    if (!m->locked || m->owner != current_thread_id()) {
        return -EPERM;            // Not owner! Error.
    }
    m->locked = false;
    m->owner = INVALID_THREAD_ID;
    V(&m->sem);                   // Release semaphore
    return 0;
}
 
// Now we have ownership semantics!

Building a Counting Semaphore from Binary Semaphores

We can even build counting semaphores from binary ones:

counting_from_binary.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
// Counting semaphore from binary semaphores
typedef struct counting_sem {
    int value;              // The count
    binary_sem_t mutex;     // Protects 'value'
    binary_sem_t delay;     // For blocking waiters
} counting_sem_t;
 
void counting_sem_init(counting_sem_t *s, int initial) {
    s->value = initial;
    binary_sem_init(&s->mutex, 1);
    binary_sem_init(&s->delay, 0);  // Initially blocks
}
 
void counting_P(counting_sem_t *s) {
    P(&s->mutex);
    s->value--;
    
    if (s->value < 0) {
        // Must wait - release mutex so others can signal
        V(&s->mutex);
        P(&s->delay);  // Block here until V
    } else {
        V(&s->mutex);
    }
}
 
void counting_V(counting_sem_t *s) {
    P(&s->mutex);
    s->value++;
    
    if (s->value <= 0) {
        // There are waiters (value was negative)
        V(&s->delay);  // Wake one
    }
    V(&s->mutex);
}
 
// Note: This implementation uses "negative value = waiter count" semantics

The Universality of Binary Semaphores

This ability to build other primitives demonstrates that binary semaphores are computationally universal for synchronization—any synchronization problem solvable with other primitives can be solved with binary semaphores alone.

However, this doesn't mean you should always use raw binary semaphores:

Higher-level primitives (mutexes, condition variables, monitors) provide clearer semantics
They often have optimized implementations
They provide better error checking and debugging
They express intent more clearly in code

The Assembly Language of Synchronization

Binary semaphores are to synchronization what assembly language is to programming: powerful, foundational, and sometimes necessary, but often better encapsulated in higher-level abstractions. Understand them deeply so you can debug and implement when needed, but prefer higher-level primitives for application code.

Binary Semaphores Across Platforms

Binary semaphore availability and semantics vary across platforms. Let's examine the major systems.

POSIX

POSIX doesn't distinguish binary from counting semaphores at the API level—both use sem_t. You create a binary semaphore by initializing with 1:

posix_binary_sem.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <semaphore.h>
 
// POSIX: Binary semaphore is just sem_t with value 0 or 1
sem_t binary_sem;
 
void init_as_mutex() {
    sem_init(&binary_sem, 0, 1);  // pshared=0 (same process), value=1
}
 
void init_as_signal() {
    sem_init(&binary_sem, 0, 0);  // value=0, will block until signaled
}
 
// Note: POSIX doesn't enforce the binary property!
// You could call sem_post() multiple times and value becomes 2, 3, ...
// It's up to you to use it correctly as binary
 
// For true mutex semantics with ownership, use pthread_mutex_t:
#include <pthread.h>
pthread_mutex_t real_mutex = PTHREAD_MUTEX_INITIALIZER;

C++20 Binary Semaphore

C++20 introduced std::binary_semaphore as a standard library type:

cpp_binary_sem.cpp
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
#include <semaphore>
#include <thread>
 
// C++20 explicit binary semaphore type
std::binary_semaphore signal_sem{0};  // For signaling (init 0)
std::binary_semaphore mutex_sem{1};   // For exclusion (init 1)
 
// Signaling example
void producer() {
    do_preparation();
    signal_sem.release();  // V operation (C++ naming)
}
 
void consumer() {
    signal_sem.acquire();  // P operation
    process_result();
}
 
// Mutex usage (but prefer std::mutex for this)
void protected_operation() {
    mutex_sem.acquire();  // Lock
    // Critical section
    modify_shared_data();
    mutex_sem.release();  // Unlock
}
 
// std::binary_semaphore is typedef for std::counting_semaphore<1>
// The template parameter is the maximum value (1 for binary)

Binary Semaphore APIs Across Platforms
Platform	Type/API	Binary Enforcement	Notes
POSIX	sem_t with value 0/1	Not enforced	Same API as counting
C++20	std::binary_semaphore	Compile-time max 1	typedef for counting_semaphore<1>
Java	Semaphore(1)	Not enforced	Same class, just permits=1
Python	BoundedSemaphore(1)	Runtime enforced	Raises ValueError on over-release
Windows	CreateSemaphore(1, 1)	lMaximumCount enforced	Separate max from initial
FreeRTOS	xSemaphoreCreateBinary()	Separate type	Optimized binary implementation

Embedded Systems Optimization

In embedded RTOS like FreeRTOS, binary semaphores often have optimized implementations separate from counting semaphores. They use less memory and have faster operations since they don't need to track a count. If your platform offers a dedicated binary semaphore type, prefer it over counting semaphores initialized to 1.

Summary

We have explored binary semaphores comprehensively—their definition, the critical distinction from mutexes, usage patterns, and implementation details. Let's consolidate the key insights:

Key Takeaways

•Definition — Binary semaphores have values restricted to 0 or 1, used for mutual exclusion (init=1) or signaling (init=0).
•No Ownership — Unlike mutexes, any thread can call V. This enables signaling patterns but loses debugging and priority inheritance benefits.
•Mutual Exclusion — P before critical section, V after. Guarantees at most one thread in critical section. Ensure V on all paths.
•Signaling Pattern — Waiter calls P (blocks on value=0), signaler calls V (sets value=1, wakes waiter). Clean event notification.
•Idempotent V — V on a value=1 binary semaphore stays at 1 (no accumulation). Multiple signals may be 'lost.'
•Building Blocks — Binary semaphores can build mutexes, counting semaphores, and other primitives—they're computationally universal for synchronization.
•Platform Variation — Some platforms enforce binary property (C++20, Windows); others just use counting semaphores with value 0/1 (POSIX).

Module Complete: Semaphore Concepts

Congratulations! You have mastered the fundamental concepts of semaphores—Dijkstra's breakthrough invention, the P (wait) and V (signal) operations, counting semaphores for resource management, and binary semaphores for mutual exclusion and signaling. You now possess the foundational knowledge to understand and solve the classic synchronization problems explored in subsequent modules: producer-consumer, readers-writers, and dining philosophers.