Semaphore Implementation
Blocking Implementation
Read aloud is unavailable in this browser.
The Art of Waiting Efficiently
When Edsger Dijkstra introduced semaphores in 1965, he solved a profound problem: how can multiple processes coordinate access to shared resources without wasting computational power? The answer lies in blocking—a mechanism that allows threads to voluntarily relinquish the CPU while waiting for a condition to become true.
Blocking semaphores represent a fundamental departure from busy-waiting approaches. Instead of spinning in a tight loop consuming CPU cycles, a blocked thread is removed from the CPU's run queue entirely, allowing other work to proceed. When the awaited resource becomes available, the blocked thread is awakened and resumes execution.
This page explores the intricate machinery behind blocking semaphore implementations—the data structures, algorithms, and system-level integrations that make efficient thread coordination possible.
By the end of this page, you will understand: the internal architecture of blocking semaphores, how wait queues manage suspended threads, the atomicity requirements for correct blocking, the integration with scheduler and memory subsystems, and the tradeoffs between blocking and spinning implementations.
Anatomy of a Blocking Semaphore
A blocking semaphore consists of two fundamental components: an integer counter and a wait queue. Together, these structures enable the semaphore to track resource availability and manage the set of threads waiting for that resource.
The Integer Counter:
The semaphore's counter (traditionally denoted S or value) represents the number of available units of the protected resource. For a binary semaphore (mutex), this value alternates between 0 and 1. For counting semaphores, it ranges from 0 to the maximum resource count.
- When the counter is positive, resources are available for immediate acquisition
- When the counter is zero, all resources are currently held by other threads
- When the counter is negative (in some implementations), the absolute value indicates the number of waiting threads
The Wait Queue:
The wait queue is a data structure that holds references to threads blocked on this semaphore. When a thread attempts to decrement the counter below zero, it is enqueued in this structure and suspended. When another thread increments the counter via a signal operation, a thread is dequeued and awakened.
The choice of queue discipline—FIFO, priority-based, or LIFO—has profound implications for fairness and performance.
12345678910111213141516171819202122232425262728293031323334353637
// Fundamental blocking semaphore structuretypedef struct semaphore { // Current value of the semaphore // Positive: resources available // Zero: no resources, but no waiters // Negative (optional): absolute value = waiter count int value; // Spinlock protecting semaphore state // Required for atomicity on multiprocessors spinlock_t lock; // Queue of waiting threads // Discipline determines fairness properties struct wait_queue_head wait_list; // Debug information (optional) #ifdef CONFIG_DEBUG_LOCK const char *name; void *owner; // For debugging binary semaphores unsigned long acquired_at; #endif} semaphore_t; // Wait queue entry - one per blocked threadtypedef struct wait_queue_entry { unsigned int flags; // Wait type flags struct task_struct *private; // The waiting thread/task wait_queue_func_t func; // Wake function callback struct list_head entry; // Links in the wait queue} wait_queue_entry_t; // Wait queue head - container for the queuetypedef struct wait_queue_head { spinlock_t lock; // Protects the queue itself struct list_head head; // Head of the linked list} wait_queue_head_t;Some semaphore implementations allow the counter to go negative, where |value| indicates the number of waiters. Others keep the counter at zero and track waiters separately. The Linux kernel traditionally used non-negative values, while POSIX semantics allow for either approach. The key invariant is: if value < 0, exactly |value| threads are blocked.
The Wait (P/Down) Operation
The wait operation (historically called P from Dutch proberen, "to try," or down in Unix terminology) is the heart of semaphore blocking semantics. This operation attempts to decrement the semaphore counter and blocks the calling thread if the counter would become negative.
The Fundamental Algorithm:
- Acquire the semaphore's internal lock — This lock protects the counter and wait queue from concurrent modification
- Test the counter value — Determine if resources are available
- If counter > 0 — Decrement the counter and release the lock; the caller proceeds
- If counter ≤ 0 — Prepare the thread for sleeping:
- Create and initialize a wait queue entry
- Add the entry to the semaphore's wait queue
- Set the thread state to TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE
- Release the lock (critical timing!)
- Invoke the scheduler to context switch away
- Upon waking — The thread resumes, reacquires the lock (if needed), and verifies it now holds the resource
Critical Atomicity Requirement:
The transition from "checking the counter" to "sleeping" must be handled with extreme care. There exists a dangerous window between releasing the lock and actually sleeping. If a signal (V operation) arrives during this window, it could be lost—the signaling thread finds no one in the wait queue because our thread hasn't added itself yet, but our thread then sleeps forever.
Modern implementations solve this by linking the lock release and sleep atomically, typically via scheduler integration.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
// Blocking wait operation implementationvoid semaphore_wait(semaphore_t *sem) { // Disable preemption and acquire internal lock spin_lock_irqsave(&sem->lock, flags); // Fast path: resource immediately available if (sem->value > 0) { sem->value--; spin_unlock_irqrestore(&sem->lock, flags); return; } // Slow path: must block // Decrement to indicate we're waiting (if using negative convention) sem->value--; // Prepare current thread for sleeping DEFINE_WAIT(wait); // Allocates wait_queue_entry on stack for (;;) { // Add ourselves to the wait queue prepare_to_wait(&sem->wait_list, &wait, TASK_UNINTERRUPTIBLE); // Double-check: maybe signal arrived while we prepared if (sem->value >= 0) { // Resource became available break; } // Release lock and sleep atomically // This is the critical section - schedule() won't return // until we're woken up spin_unlock_irqrestore(&sem->lock, flags); schedule(); // Context switch to another thread spin_lock_irqsave(&sem->lock, flags); // We've been awakened - loop back to verify condition } // Clean up our wait queue entry finish_wait(&sem->wait_list, &wait); spin_unlock_irqrestore(&sem->lock, flags);} // Interruptible version - can be interrupted by signalsint semaphore_wait_interruptible(semaphore_t *sem) { spin_lock_irqsave(&sem->lock, flags); if (sem->value > 0) { sem->value--; spin_unlock_irqrestore(&sem->lock, flags); return 0; // Success } sem->value--; DEFINE_WAIT(wait); for (;;) { prepare_to_wait(&sem->wait_list, &wait, TASK_INTERRUPTIBLE); if (sem->value >= 0) break; // Check for pending signals if (signal_pending(current)) { // We're being interrupted sem->value++; // We're leaving, restore count finish_wait(&sem->wait_list, &wait); spin_unlock_irqrestore(&sem->lock, flags); return -EINTR; // Interrupted! } spin_unlock_irqrestore(&sem->lock, flags); schedule(); spin_lock_irqsave(&sem->lock, flags); } finish_wait(&sem->wait_list, &wait); spin_unlock_irqrestore(&sem->lock, flags); return 0; // Success}| State | Description | Implications |
|---|---|---|
TASK_RUNNING | Thread is executing or ready to execute | Consumes CPU time, on run queue |
TASK_INTERRUPTIBLE | Thread is sleeping but can be woken by signals | Not on run queue, signal-responsive |
TASK_UNINTERRUPTIBLE | Thread is sleeping and cannot be interrupted | Used for critical waits (disk I/O) |
TASK_KILLABLE | Like uninterruptible but responds to fatal signals | Modern hybrid for robustness |
The Signal (V/Up) Operation
The signal operation (historically V from Dutch verhogen, "to raise," or up in Unix terminology) releases a unit of the protected resource by incrementing the semaphore counter. If threads are waiting, one is awakened to acquire the newly available resource.
The Fundamental Algorithm:
- Acquire the semaphore's internal lock — Ensures atomic modification
- Increment the counter — Release one unit of resource
- Check for waiters — If the wait queue is non-empty:
- Dequeue a thread according to the queue discipline (typically FIFO)
- Wake up that thread by changing its state and adding it to the run queue
- Release the internal lock — Allow other operations to proceed
The Wake-Up Mechanics:
Waking a thread involves several steps that coordinate with the scheduler:
- The thread's state changes from
TASK_INTERRUPTIBLEorTASK_UNINTERRUPTIBLEtoTASK_RUNNING - The thread is added back to the scheduler's run queue
- If the awakened thread has higher priority than the current thread, a reschedule may be triggered
Convoys and Thundering Herds:
When multiple threads are waiting and the signal operation wakes only one thread at a time, we achieve orderly handoff of the resource. However, if the implementation wakes all waiters (as some condition variable implementations do), we get the "thundering herd" problem—many threads wake up, but only one can proceed.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
// Signal operation implementationvoid semaphore_signal(semaphore_t *sem) { unsigned long flags; // Acquire internal lock spin_lock_irqsave(&sem->lock, flags); // Increment the counter - one more resource available sem->value++; // Wake up one waiter if any exist // wake_up wakes exactly one thread from the queue if (!list_empty(&sem->wait_list.head)) { // Wake the first waiter (FIFO discipline) wake_up(&sem->wait_list); } spin_unlock_irqrestore(&sem->lock, flags);} // More detailed wake implementationvoid wake_up(wait_queue_head_t *wq_head) { unsigned long flags; wait_queue_entry_t *curr, *next; spin_lock_irqsave(&wq_head->lock, flags); // Iterate through waiters list_for_each_entry_safe(curr, next, &wq_head->head, entry) { // Call the wake function for this entry // Typically: default_wake_function unsigned int ret = curr->func(curr, TASK_NORMAL, 0, NULL); // If exclusive wake (most semaphore waiters): // Wake only one and stop if (curr->flags & WQ_FLAG_EXCLUSIVE) { if (ret) // Successfully woke this task break; } } spin_unlock_irqrestore(&wq_head->lock, flags);} // The actual task wake functionint default_wake_function(wait_queue_entry_t *wq_entry, unsigned mode, int flags, void *key) { struct task_struct *task = wq_entry->private; // Try to wake the task return try_to_wake_up(task, mode, flags);} // Core scheduler wake function (simplified)int try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) { unsigned long flags; int cpu, success = 0; raw_spin_lock_irqsave(&p->pi_lock, flags); // Check if task is in the expected state if (!(p->state & state)) goto out; // Set task to running p->state = TASK_RUNNING; // Select CPU for the task (load balancing considerations) cpu = select_task_rq(p, wake_flags); // Add task to the run queue activate_task(rq, p, 0); // Check if we need to preempt current task check_preempt_curr(rq, p, wake_flags); success = 1;out: raw_spin_unlock_irqrestore(&p->pi_lock, flags); return success;}Semaphore waiters are typically marked as 'exclusive' (WQ_FLAG_EXCLUSIVE), meaning a signal wakes exactly one. This contrasts with non-exclusive waiters (used in some broadcast scenarios) where all waiters are awakened. The exclusive flag prevents the thundering herd problem and ensures O(1) wake-up cost.
Wait Queue Management
The wait queue is the critical data structure that manages blocked threads. Its implementation must balance several competing concerns: O(1) insertion and removal, memory efficiency, cache friendliness, and fairness properties.
Data Structure Choices:
Most implementations use a doubly-linked list for the wait queue:
- Insertion at tail: O(1) with a tail pointer, ensures FIFO ordering
- Removal from head: O(1), wakes the longest-waiting thread first
- Arbitrary removal: O(1) for a node removing itself (interruptible waits)
- Memory: Each waiting thread has one
wait_queue_entrystructure
Alternative structures exist for specialized use cases:
- Priority heap: O(log n) operations, but ensures highest-priority waiter is woken first
- Circular buffer: Fixed-size, cache-friendly, but limits maximum waiters
- Lock-free queue: Higher complexity but avoids lock contention on the queue itself
The Wait Queue Entry Lifecycle:
- Allocation: Typically on the waiting thread's stack (cheap, automatic cleanup)
- Initialization: Set the
privatefield tocurrent(the calling thread) - Enqueueing: Add to the wait queue under the queue's lock
- Sleeping: Thread blocks via
schedule() - Dequeueing on wake: The signaling thread removes the entry
- Cleanup:
finish_wait()handles any race conditions
Memory Location Matters:
Using stack-allocated wait queue entries is elegant—no heap allocation, no memory leaks. But it requires the entry to remain valid while the thread sleeps. Since the thread's stack isn't deallocated during sleep, this works perfectly. The DEFINE_WAIT() macro handles this idiom.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
// Wait queue initialization and operations // Initialize a wait queue headvoid init_waitqueue_head(wait_queue_head_t *wq_head) { spin_lock_init(&wq_head->lock); INIT_LIST_HEAD(&wq_head->head);} // Initialize a wait queue entryvoid init_waitqueue_entry(wait_queue_entry_t *wq_entry, struct task_struct *task) { wq_entry->flags = 0; wq_entry->private = task; wq_entry->func = default_wake_function; INIT_LIST_HEAD(&wq_entry->entry);} // Stack-based wait entry allocation#define DEFINE_WAIT(name) \ wait_queue_entry_t name = { \ .private = current, \ .func = autoremove_wake_function, \ .entry = LIST_HEAD_INIT(name.entry), \ } // Prepare to wait - add to queue and set statevoid prepare_to_wait(wait_queue_head_t *wq_head, wait_queue_entry_t *wq_entry, int state) { unsigned long flags; wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE; spin_lock_irqsave(&wq_head->lock, flags); // Only add if not already in a wait queue if (list_empty(&wq_entry->entry)) __add_wait_queue(wq_head, wq_entry); // Add to head (some impls) set_current_state(state); spin_unlock_irqrestore(&wq_head->lock, flags);} // Prepare for exclusive wait (semaphore style)void prepare_to_wait_exclusive(wait_queue_head_t *wq_head, wait_queue_entry_t *wq_entry, int state) { unsigned long flags; wq_entry->flags |= WQ_FLAG_EXCLUSIVE; // Mark as exclusive spin_lock_irqsave(&wq_head->lock, flags); if (list_empty(&wq_entry->entry)) __add_wait_queue_entry_tail(wq_head, wq_entry); // FIFO! set_current_state(state); spin_unlock_irqrestore(&wq_head->lock, flags);} // Finish waiting - clean up after being wokenvoid finish_wait(wait_queue_head_t *wq_head, wait_queue_entry_t *wq_entry) { unsigned long flags; // Set back to running (might already be) __set_current_state(TASK_RUNNING); // Only remove if still queued (might have been removed by waker) if (!list_empty_careful(&wq_entry->entry)) { spin_lock_irqsave(&wq_head->lock, flags); list_del_init(&wq_entry->entry); spin_unlock_irqrestore(&wq_head->lock, flags); }} // Auto-remove wake function - removes entry upon wakingint autoremove_wake_function(wait_queue_entry_t *wq_entry, unsigned mode, int sync, void *key) { int ret = default_wake_function(wq_entry, mode, sync, key); if (ret) list_del_init(&wq_entry->entry); // Remove from queue return ret;}- •Stack allocation for entries — Eliminates heap allocation overhead and memory leaks; entry lifetime matches sleep duration
- •Doubly-linked list — O(1) insertion at tail (FIFO), O(1) removal from anywhere (for interrupted waits)
- •Exclusive flag — Prevents thundering herd by waking only one waiter per signal
- •Tail insertion for fairness — The longest-waiting thread is woken first, preventing starvation
- •Auto-remove on wake — The waking path removes the entry, simplifying cleanup and reducing races
Scheduler Integration
Blocking semaphores require deep integration with the operating system scheduler. When a thread blocks on a semaphore, it must be removed from the CPU's run queue. When awakened, it must be added back. This integration involves several critical coordination points.
The Context Switch Path:
When a thread calls schedule() after failing to acquire a semaphore:
- State check: The scheduler verifies the thread's state is
TASK_INTERRUPTIBLEorTASK_UNINTERRUPTIBLE - Run queue removal: The thread is removed from the run queue (if still present)
- Context selection: The scheduler picks the next thread to run based on its scheduling policy
- Context switch: CPU registers, stack pointer, and page table are switched to the new thread
- Control transfer: The new thread resumes execution
The blocked thread now exists only in the semaphore's wait queue—invisible to the scheduler until awakened.
The Wake-Up Path:
When another thread signals the semaphore:
- Wait queue access: The signaling thread acquires the wait queue lock
- Waiter selection: The first waiter (FIFO) is dequeued
- State transition: The waiter's state becomes
TASK_RUNNING - Run queue insertion: The waiter is added to a run queue (possibly on a different CPU)
- Preemption check: If the woken thread has higher priority, a reschedule is triggered
- Lock release: The signal operation completes
Multi-CPU Considerations:
On SMP systems, the woken thread might run on a different CPU than the signaling thread. This introduces cache migration costs but enables parallelism. Smart wake-up heuristics try to balance:
- CPU affinity: Prefer the CPU where the waiter last ran (warm cache)
- Load balancing: Avoid overloading busy CPUs
- NUMA locality: Keep threads and their data on the same NUMA node
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
// Scheduler integration for blocking // The main schedule function (simplified)void __schedule(bool preempt) { struct task_struct *prev, *next; struct rq *rq; int cpu; cpu = smp_processor_id(); rq = cpu_rq(cpu); prev = rq->curr; // The currently running task // Lock the run queue raw_spin_lock(&rq->lock); // If prev is not RUNNING, it needs to be dequeued // This happens when a task called schedule() after blocking if (prev->state != TASK_RUNNING && !preempt) { // Remove from run queue - task is blocking deactivate_task(rq, prev, DEQUEUE_SLEEP); // For interruptible sleeps, check for signals if (prev->state == TASK_INTERRUPTIBLE && signal_pending(prev)) { prev->state = TASK_RUNNING; activate_task(rq, prev, ENQUEUE_HEAD); } } // Pick the next task to run next = pick_next_task(rq, prev); if (prev != next) { rq->curr = next; // Perform the actual context switch // This switches stacks, registers, and address space context_switch(rq, prev, next); // After switch, we're running as 'next' // prev might be running on another CPU by now! } raw_spin_unlock(&rq->lock);} // Wake up a specific taskint wake_up_process(struct task_struct *p) { return try_to_wake_up(p, TASK_NORMAL, 0);} // Core wake-up logicint try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) { struct rq *rq; int cpu; // Grab the task's lock raw_spin_lock_irqsave(&p->pi_lock, flags); // Verify task is in expected state if (!(p->state & state)) goto out; // Transition to running p->state = TASK_RUNNING; // Select CPU for the task // Consider: affinity, load, NUMA topology cpu = select_task_rq(p, wake_flags); // Get the run queue for that CPU rq = cpu_rq(cpu); raw_spin_lock(&rq->lock); // Add to run queue activate_task(rq, p, 0); // Check if we should preempt the current task if (rq->curr->prio > p->prio) { // Woken task has higher priority resched_curr(rq); // Request reschedule } raw_spin_unlock(&rq->lock); out: raw_spin_unlock_irqrestore(&p->pi_lock, flags); return success;} // Select CPU for awakened task (simplified)int select_task_rq(struct task_struct *p, int wake_flags) { // First choice: the CPU where task last ran (cache affinity) int prev_cpu = task_cpu(p); // If that CPU is idle, use it if (idle_cpu(prev_cpu)) return prev_cpu; // Otherwise, find a suitable CPU // Consider: same NUMA node, low load, idle state return select_idle_sibling(prev_cpu);}The order of operations is crucial: set state BEFORE checking conditions, and BEFORE calling schedule(). If you set state to INTERRUPTIBLE after checking the semaphore value, a wake-up between the check and state change would be lost. The pattern is: (1) set_current_state(INTERRUPTIBLE); (2) if (!condition) schedule(); (3) __set_current_state(RUNNING);
Atomicity and the Lost Wake-Up Problem
The most insidious bug in blocking synchronization is the lost wake-up problem. This occurs when a signal arrives precisely as a thread is transitioning to sleep, but before it has actually blocked. The signal finds no one to wake (the thread hasn't slept yet), and the thread then sleeps forever.
The Race Condition Anatomy:
Thread A (waiting) Thread B (signaling)
───────────────── ────────────────────
if (sem.value <= 0) {
sem.signal()
// No waiters found!
sleep()
// Sleep forever!
}
Thread A checks the condition and finds it must wait. Before it can enter the sleep state, Thread B signals. Thread B scans the wait queue but finds no one—Thread A hasn't added itself yet. Thread B's signal is lost. Thread A then sleeps, unaware that the resource is now available.
The Solution: State-Before-Test Pattern
The solution relies on careful ordering and the semantics of the thread state field:
- Set state to sleeping BEFORE checking condition — Even though you're not actually sleeping yet
- The signaling thread checks our state — It will see we're "sleeping" and add us to run queue
- If we actually sleep, we can be woken correctly
- If condition is true, reset state before returning
This works because the state transition is atomic and visible to other CPUs (with proper memory barriers).
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
// WRONG: Race condition leading to lost wake-upvoid semaphore_wait_BROKEN(semaphore_t *sem) { spin_lock(&sem->lock); while (sem->value <= 0) { spin_unlock(&sem->lock); // DANGER ZONE: signal could arrive here! // We're not in the wait queue yet // but we're about to sleep schedule(); // May sleep forever if signal was sent above spin_lock(&sem->lock); } sem->value--; spin_unlock(&sem->lock);} // CORRECT: Atomicity via state-before-test patternvoid semaphore_wait_CORRECT(semaphore_t *sem) { DEFINE_WAIT(wait); spin_lock(&sem->lock); while (sem->value <= 0) { // Step 1: Add to wait queue AND set state to sleeping // This must happen atomically with respect to the signaler prepare_to_wait_exclusive(&sem->wait_list, &wait, TASK_UNINTERRUPTIBLE); // After this point, any signal() will find us and wake us spin_unlock(&sem->lock); // Step 2: Actually sleep // Safe now - signaler will see our state and wake us schedule(); // Step 3: We've been woken - recheck condition spin_lock(&sem->lock); } // Step 4: Condition satisfied, clean up finish_wait(&sem->wait_list, &wait); sem->value--; spin_unlock(&sem->lock);} // The prepare_to_wait function (critical for correctness)void prepare_to_wait_exclusive(wait_queue_head_t *wq_head, wait_queue_entry_t *wq_entry, int state) { unsigned long flags; wq_entry->flags |= WQ_FLAG_EXCLUSIVE; spin_lock_irqsave(&wq_head->lock, flags); // Atomically: // 1. Add to wait queue if (list_empty(&wq_entry->entry)) __add_wait_queue_entry_tail(wq_head, wq_entry); // 2. Set our state to "sleeping" // Uses memory barrier to ensure visibility set_current_state(state); spin_unlock_irqrestore(&wq_head->lock, flags); // Now signalers will: // - Find us in the wait queue // - See our state as INTERRUPTIBLE/UNINTERRUPTIBLE // - Call wake_up, which checks our state and wakes us} // Memory barriers in set_current_state#define set_current_state(state_value) \ do { \ smp_store_mb(current->state, (state_value)); \ } while (0) // smp_store_mb: store with full memory barrier// Ensures the state write is visible to all CPUs// before any subsequent memory operations- •Set state before checking condition — Use
set_current_state(TASK_INTERRUPTIBLE)before testing the semaphore value - •Add to wait queue under lock — The wait queue entry must be visible before releasing the lock
- •Use memory barriers —
smp_store_mbensures state changes are visible to other CPUs - •Double-check after waking — The condition might not be true (spurious wake-up); loop and re-check
- •Reset state on exit — Call
__set_current_state(TASK_RUNNING)after the condition is satisfied
Memory Barriers and Ordering
On modern multi-core processors, memory operations can be reordered for performance. Compilers may rearrange code, and CPUs may execute loads and stores out of order. For blocking semaphores to work correctly, specific memory ordering guarantees must be enforced.
Why Ordering Matters:
Consider the wait operation:
set_current_state(TASK_INTERRUPTIBLE); // Write A
if (sem.value > 0) { ... // Read B
If the CPU reorders Read B before Write A, we might check the semaphore value before our state is visible to signaling threads. A wake-up could be lost.
Similarly, in the signal operation:
sem.value++; // Write X
if (!list_empty(&sem.wait_list)) // Read Y
wake_up(...);
If Read Y happens before Write X, a waiter might not see the incremented value and incorrectly sleep.
Memory Barrier Types:
- Full barrier (smp_mb): Prevents reordering of any loads/stores across this point
- Read barrier (smp_rmb): Ensures prior reads complete before subsequent reads
- Write barrier (smp_wmb): Ensures prior writes complete before subsequent writes
- Acquire barrier: Reads/writes after this point cannot be moved before it
- Release barrier: Reads/writes before this point cannot be moved after it
Barriers in Semaphore Implementation:
Spinlocks inherently provide acquire/release semantics:
spin_lockhas acquire semantics (operations inside the critical section stay inside)spin_unlockhas release semantics (operations inside the critical section complete first)
Additionally, set_current_state() includes a full memory barrier to ensure state visibility.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
// Memory barrier placement in semaphore operations // Correct wait with explicit barrier explanationvoid semaphore_wait_with_barriers(semaphore_t *sem) { DEFINE_WAIT(wait); spin_lock(&sem->lock); // ACQUIRE barrier while (sem->value <= 0) { // set_current_state includes smp_store_mb // which is a store + full memory barrier set_current_state(TASK_INTERRUPTIBLE); // The barrier in set_current_state ensures: // - Our state write is visible BEFORE... // - ...the signal path checks our state __add_wait_queue(&sem->wait_list, &wait); spin_unlock(&sem->lock); // RELEASE barrier // Between unlock and schedule(), our state is visible // Any signaler will see us as INTERRUPTIBLE schedule(); spin_lock(&sem->lock); // ACQUIRE barrier } __set_current_state(TASK_RUNNING); finish_wait(&sem->wait_list, &wait); sem->value--; spin_unlock(&sem->lock); // RELEASE barrier} // Signal with explicit barrier explanationvoid semaphore_signal_with_barriers(semaphore_t *sem) { spin_lock(&sem->lock); // ACQUIRE barrier sem->value++; // write barrier implicit in wake_up (via try_to_wake_up) // ensures value increment is visible before state check if (!list_empty(&sem->wait_list)) { // wake_up includes barriers in try_to_wake_up wake_up(&sem->wait_list); } spin_unlock(&sem->lock); // RELEASE barrier} // Memory barrier macros (architecture-specific)// x86: LOCK prefix provides similar guarantees// ARM: DMB (Data Memory Barrier) instruction// RISC-V: FENCE instruction // Full memory barrier#define smp_mb() __asm__ __volatile__("mfence" ::: "memory") // Write memory barrier#define smp_wmb() __asm__ __volatile__("sfence" ::: "memory") // Read memory barrier #define smp_rmb() __asm__ __volatile__("lfence" ::: "memory") // Store with memory barrier (what set_current_state uses)#define smp_store_mb(var, value) \ do { \ WRITE_ONCE(var, value); \ smp_mb(); \ } while (0)You rarely need explicit memory barriers in semaphore code because spinlocks already provide them. spin_lock() acts as an acquire barrier and spin_unlock() acts as a release barrier. This is why the lock-based implementation 'just works' on most architectures without manual barrier insertion.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.