A thread calls pthread_mutex_lock, but another thread owns the mutex. The caller cannot enter the critical section, yet repeatedly checking the lock would waste a CPU.

Instead, the thread can block. It enters the kernel, becomes non-runnable, and stops consuming CPU time until another thread makes progress possible.

That short description hides a difficult coordination problem. The kernel must record exactly what the thread awaits, remove it from CPU competition without missing a concurrent notification, and later make it runnable again.

Linux solves the general problem with scheduler state and wait queues. For many user-space synchronization primitives, it exposes a lower-level interface called a futex that keeps the uncontended case in user space and involves the kernel only when a thread may need to sleep or wake.

A thread that cannot currently make progress has two broad choices.

It can remain runnable and repeatedly test the condition:

This is busy waiting. The thread continues competing for CPU time even though most of its instructions only rediscover that it cannot proceed.

Alternatively, it can ask the kernel to block:

Waiting never leads straight back to Running. A woken thread still has to be selected, and that gap is scheduling delay.

While waiting, the thread is not on a runnable queue and receives no ordinary CPU time. The scheduler can give the CPU to another runnable thread.

Blocking is therefore not merely a long function call. It is a scheduling-state transition.

The kernel cannot remove a thread from execution and hope that something later remembers it. It needs a record connecting the waiting thread to the event that can wake it.

A wait queue is the general model for that record. Conceptually, an entry identifies:

Many kernel operations use wait-queue-like structures:

The exact kernel data structures differ across subsystems. “Wait queue” is the useful common model: the kernel records a task near the state or event that controls its wakeup.

The word queue does not guarantee strict first-in, first-out service. Wakeup selection and later CPU scheduling are separate policy decisions.

A naive blocking sequence contains a race:

Suppose the event occurs between steps 1 and 3:

The wakeup arrives before the thread is registered to receive it, so the thread sleeps waiting for an event that has already happened.

The wakeup found no registered waiter. The thread then slept after the condition became true and may wait indefinitely.

Correct blocking protocols make registration, condition validation, and the transition to a sleeping state atomic with respect to the corresponding wakeup path.

A simplified kernel pattern looks like:

The event-producing path uses compatible synchronization when it changes the condition and wakes queued tasks. Either the waiter observes the completed state change, or the producer observes the registered waiter. The notification cannot disappear into the gap between those outcomes.

Once the wait has been registered safely, the kernel can stop running the task:

A blocking call does not always block. The kernel checks first, and a satisfied condition returns immediately without any of the sleep machinery.

The context switch saves the blocked thread's CPU state. Its kernel stack remains associated with the unfinished system call, so execution can later resume inside the kernel and complete that call.

The blocked thread still exists. It retains its address space, user stack, open-resource references, and scheduling identity. Only its eligibility to execute has changed.

If no runnable work exists, the CPU can run an idle task or enter a low-power state. A blocked thread does not need a CPU merely to remain blocked.

An event producer may be another thread, an interrupt handler, a timer, or a device-completion path.

The wakeup path conceptually:

The awakened thread does not necessarily run immediately:

This distinction matters for latency. A resource can become available at time T, while the waiting thread resumes at T + scheduling delay.

A wakeup also does not normally hand ownership of a mutex or resource directly to the awakened thread. By the time it runs, another thread may have changed the state again. Correct waiters recheck the condition in a loop.

Linux has more than one sleeping task state.

An interruptible wait can end because the awaited event occurs or because an applicable signal becomes pending. A futex wait used by an ordinary user-space synchronization operation is interruptible.

An uninterruptible wait does not return early for ordinary signal handling. Linux commonly uses this state for kernel operations that must reach a safe completion point before the task continues.

The distinction controls how the wait can finish. It does not change the central property that the task is non-runnable and consumes no CPU while sleeping.

Timeouts add another wakeup source. A timed wait can return because the condition became promising, a signal interrupted it, or its deadline expired. Callers must distinguish the return reason and still recheck the protected state.

Entering the kernel for every lock and unlock would be wasteful when mutexes are usually uncontended.

If a mutex is unlocked, a thread can often acquire it with one atomic user-space operation:

An atomic compare-and-update moves the mutex word from unlocked to locked.

No task needs to sleep, so the kernel has no scheduling work to perform. Unlocking can also stay in user space when the state indicates that no waiters need notification.

This creates two paths:

The fast path is important because a well-designed program can execute millions of uncontended critical sections without paying a system-call and scheduling cost for each one.

The slow path needs a way to connect a user-space state word to a kernel wait. On Linux, that mechanism is a futex.

Futex is short for fast user-space locking. It is a Linux facility built around a 32-bit aligned word in user memory.

The user-space library owns the meaning of the word. A conceptual mutex encoding might use:

Real pthread_mutex_t layouts and state encodings are implementation details and can be more complex. Application code must never inspect or modify them directly.

For ordinary futex wait and wake operations, the kernel does not interpret the word as “a mutex owned by thread 8124.” It provides operations such as:

The library combines atomic operations, memory-ordering rules, and these kernel operations to implement the higher-level mutex contract.

A futex is a waiting and wakeup building block, not a complete mutex.

The essential futex wait request is:

Its meaning is:

Block only if the 32-bit word at address still equals expected_value.

The value check and the act of blocking are ordered atomically with respect to competing futex operations on the same futex word. This closes the gap between a user-space observation and kernel sleep.

Consider a mutex contender:

If the futex wait did not recheck the word, the contender could sleep after the unlock and miss the wakeup.

Instead, the kernel reads the current word. If it no longer equals the expected locked state, FUTEX_WAIT returns immediately with EAGAIN. The caller rechecks the mutex state rather than sleeping.

The kernel rechecks the word rather than trusting the caller's view of it. That recheck and the enqueue happen together, which closes the window where a wakeup could be missed.

A successful return from the wait means the task was woken, not that the lock has been acquired. Signals, timeouts, and other wakeup conditions can also end a wait. The surrounding loop must retry the user-space state transition.

The essential wake request is:

The kernel finds tasks waiting on the futex key derived from that address and makes up to the requested number runnable.

For a mutex unlock, waking one waiter is often sufficient:

The owner updates the mutex word to unlocked, calls FUTEX_WAKE(address, 1), and one waiter becomes runnable.

FUTEX_WAKE does not update the user-space word and does not transfer mutex ownership. The library must publish the unlocked state before requesting a wake. The awakened thread then competes to change that state atomically.

Waking more tasks than can make progress creates unnecessary scheduling and cache activity. Condition-variable broadcasts intentionally need many waiters to reconsider a predicate, while an ordinary mutex release normally needs only a limited wakeup.

A simplified Linux POSIX mutex path looks like this:

An uncontended lock never leaves user space. The kernel only appears on the failure path, which is why mutex cost depends so heavily on how much contention there actually is.

Unlocking follows the complementary path:

pthread_mutex_unlock publishes the unlocked state. If no waiters are indicated it returns in user space, and if waiters may exist it calls FUTEX_WAKE.

The diagrams omit implementation details, but they explain the performance boundary:

This is why lock contention costs more than the atomic instruction used by the fast path. It can include system calls, scheduler operations, context switches, cache-line transfers, and scheduling delay.

The numeric virtual address alone cannot always identify a futex.

Two unrelated processes can each have a private mapping at address 0x7000; those words must not share a wait queue. Conversely, two processes can map the same shared-memory word at different virtual addresses and need it to represent one futex.

Linux therefore derives an internal futex key from the address and mapping context.

Private futex operations tell the kernel that all participants use one process address space, allowing a cheaper lookup. Process-shared futexes derive identity from the shared backing memory so that different processes can rendezvous on the same underlying word.

Thread libraries select the appropriate form from the synchronization object's attributes. Application code normally uses the pthread or semaphore API rather than constructing futex keys itself.

Mutexes are the easiest futex example, but they are not the only use.

A condition-variable implementation can maintain a user-space sequence value. A waiter records the value, releases the associated mutex through the library protocol, and performs a futex wait if the sequence has not changed. Signaling changes the sequence and wakes eligible waiters.

A semaphore implementation can update its user-space count atomically when permits are available. If the count cannot satisfy a wait, it can use a futex to block until a post changes the state.

The exact algorithms vary between C libraries and versions. The recurring design is:

User-space atomic state handles the common case, and the kernel futex handles sleeping and waking.

The futex syscall does not replace the predicate loop, ownership rules, or memory ordering required by the higher-level primitive.

The following program has two modes.

In uncontended mode, one thread repeatedly locks and unlocks a mutex. In contended mode, a worker holds the mutex long enough for the initial thread to attempt the slow path.

Compile it on Linux:

Trace only futex system calls and follow all threads:

The uncontended loop normally produces no futex syscall for its mutex operations. The user-space atomic fast path is sufficient.

The contended run should contain operations resembling:

Exact arguments, return formatting, addresses, and incidental runtime calls vary with the C library and system. A trace records implementation behavior, not a portable mutex representation.

The short atomic-flag loop exists only to make the demonstration's lock-acquisition order likely and visible. It is not a replacement for a blocking notification mechanism in production code, and an extremely delayed initial thread could still miss the intended contention window.

strace adds overhead, so use it to understand control flow rather than to benchmark mutex latency. To obtain aggregate counts for a workload:

Heavy futex traffic is evidence that synchronization frequently reaches kernel paths. It is not proof that every call slept, and it does not by itself identify which application invariant or source-level mutex caused the activity.

Linux tools can show both task state and the kernel location associated with a wait:

A thread sleeping in a futex wait commonly appears with state S. The WCHAN column may show a futex-related kernel symbol, depending on the kernel build, permissions, and timing.

For one thread, inspect:

Blocking normally contributes a voluntary context switch because the thread gives up the CPU when it cannot proceed.

These observations are snapshots. A short wait can begin and end before a monitoring command samples it, and kernel symbol names differ across versions.

Blocking avoids wasting CPU during a wait, but it is not free.

A contended handoff can require:

The cost of one blocked acquisition accumulates through:

The awakened thread may also resume on a different CPU with colder cache state. Meanwhile, several waiters competing for one resource can create additional atomic traffic even if only one can enter the critical section.

This does not make blocking a mistake. If a thread cannot perform useful work for a meaningful or unpredictable interval, removing it from CPU competition is usually the correct system behavior.

The performance goal is to avoid unnecessary contention and unnecessary wakeups, not to keep blocked work artificially runnable.

Blocking is a scheduler transition that removes a thread from the runnable population until an event may allow progress. The kernel records the wait, changes the task state, schedules other work, and later makes the thread runnable when a producer triggers a wakeup. Becoming runnable does not mean running immediately, and every resumed waiter must recheck its condition.

Linux futexes let synchronization libraries keep uncontended operations in user space. FUTEX_WAIT blocks only if a 32-bit user-space word still matches an expected value, closing the lost-wakeup gap. FUTEX_WAKE makes selected waiters runnable but neither changes the word nor grants ownership.

A contended mutex can therefore cross into the kernel, use a futex wait queue, incur context switches, and experience scheduling delay. An uncontended mutex usually completes through atomic user-space operations without any futex syscall.