vault

Wait Queues and Task Blocking

15 min read

Wait Queues and Task Blocking

A wait queue is the kernel’s fundamental primitive for “go to sleep until something happens.” When a kernel thread needs to block — waiting for data on a socket, for a buffer to be writable, for a child to exit — it does not spin and it does not poll; it adds itself to a wait_queue_head_t associated with the event, marks itself non-runnable, and calls schedule() to give up the CPU. When the event occurs, whoever caused it calls wake_up() on that same queue, which walks the list of waiters and asks the scheduler to make them runnable again. The entire construct is just a spinlock-protected linked list of waiters (per include/linux/wait.h, Linux 6.12 LTS), and the single hardest thing about it is not the data structure but the lost-wakeup race: the careful dance of setting your state before re-checking the condition, fenced by a memory barrier, so that a wakeup arriving in the gap between “I decided to sleep” and “I actually slept” is never lost.

This note owns the sleep/wakeup primitive — the queue, the canonical loop, the wait_event*() macros, exclusive versus non-exclusive waiters, and the barrier-and-recheck correctness argument. It describes wakeup from the queue’s side (walking the list, calling each waiter’s callback). The scheduler-internal act of flipping one task from sleeping to runnable belongs to Wakeups and try_to_wake_up; the meaning of the states a sleeper sets (TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE, TASK_KILLABLE) is the subject of Process States and the Task State Machine — recapped here only enough to make the loop make sense.

Mental Model

A wait queue is a rendezvous point named by the event, not by the waiter. Many tasks can sleep on one queue; many code paths can wake it. The waiter’s job is to atomically declare “I am about to sleep waiting for condition C” and then, only if C is still false, actually sleep — because between declaring intent and sleeping, the condition might become true and a wakeup might fire. If the waiter slept unconditionally it could miss that wakeup and sleep forever. The whole design exists to close that window.

sequenceDiagram
  participant W as Waiter (CPU 1)
  participant Q as wait_queue_head
  participant K as Waker (CPU 0)
  W->>Q: prepare_to_wait_event(): add entry to list
  W->>W: set_current_state(TASK_INTERRUPTIBLE)
  Note over W: smp_store_mb() — full barrier
  W->>W: if (condition) break  // recheck!
  K->>K: condition = true
  Note over K: full barrier in try_to_wake_up()
  K->>Q: wake_up(): walk list, call func()
  Q->>W: try_to_wake_up(): __state = TASK_RUNNING
  W->>W: schedule() returns, loop, condition true
  W->>Q: finish_wait(): remove entry, __state = RUNNING

The sleep/wakeup handshake and the race it defeats. What it shows: the waiter adds itself, sets its non-runnable state behind a full memory barrier, then re-checks the condition; the waker sets the condition, executes its own barrier, and walks the queue calling each entry’s wake function. The insight: the barrier on each side is the load-bearing element — it guarantees that if the waker’s “condition = true” store happens-before its wakeup, the waiter’s recheck cannot have read the old condition and missed the wakeup. Either the waiter sees the condition true on recheck (and never sleeps), or it has published its non-runnable state in time for the waker’s try_to_wake_up() to see it and flip it back. The window is closed.

The Data Structures

From include/linux/wait.h (6.12 LTS):

struct wait_queue_head {
    spinlock_t        lock;
    struct list_head  head;
};
typedef struct wait_queue_head wait_queue_head_t;
 
struct wait_queue_entry {
    unsigned int        flags;
    void                *private;     /* the task_struct of the waiter */
    wait_queue_func_t   func;         /* callback invoked on wakeup */
    struct list_head    entry;
};

The head is a lock plus a list. Each entry is one sleeping task’s node: private points at its [[The task_struct Process Descriptor|task_struct]], func is the callback the wakeup machinery invokes (defaulting to autoremove_wake_function, which calls try_to_wake_up() and then unlinks the entry), and flags carries WQ_FLAG_EXCLUSIVE and friends. A head is declared statically with DECLARE_WAIT_QUEUE_HEAD(name) or initialised at runtime with init_waitqueue_head(&wq). An entry is built on the waiter’s stack with DEFINE_WAIT(name) (which wires private = current and func = autoremove_wake_function).

The flags values that matter:

#define WQ_FLAG_EXCLUSIVE  0x01   /* wake-one: stop after this waiter */
#define WQ_FLAG_WOKEN      0x02   /* used by the wait_woken() protocol */
#define WQ_FLAG_PRIORITY   0x10   /* insert at head, consume event first */

The Canonical Sleep Loop

The single most important pattern in this note, lifted from the documentation comment in include/linux/sched.h:

for (;;) {
    set_current_state(TASK_UNINTERRUPTIBLE);   /* (1) declare intent + barrier */
    if (CONDITION)                             /* (2) recheck under the barrier */
        break;
    schedule();                                /* (3) actually sleep */
}
__set_current_state(TASK_RUNNING);             /* (4) back to runnable */

Step by step. (1) set_current_state(TASK_UNINTERRUPTIBLE) writes the non-runnable state into current->__state and issues a full memory barrier (smp_store_mb). This ordering is the crux: the state store must be globally visible before the condition load in step (2). (2) re-check CONDITION. If it is already true — because it became true after the caller’s earlier check but before we set our state — we break without ever sleeping, having only briefly set and then cleared our state in step (4). (3) if the condition is still false, schedule() removes us from the run queue and switches to another task; we are now genuinely asleep. (4) when schedule() eventually returns (because a waker flipped us back to TASK_RUNNING), we loop, re-check, and on success set TASK_RUNNING and continue.

The matching waker side:

CONDITION = 1;
wake_up(&wq);     /* wake_up_state() / try_to_wake_up() runs a full barrier */

Why the barriers are mandatory: imagine no barrier between the state store (1) and the condition load (2). The CPU is free to reorder them — to load CONDITION first (seeing it false), then store TASK_UNINTERRUPTIBLE. Meanwhile the waker, on another CPU, sets CONDITION = 1 and calls wake_up(), which reads our __state and sees TASK_RUNNING (our store has not landed yet), so it does nothing. Now we store TASK_UNINTERRUPTIBLE and schedule() — asleep forever, with the condition true and no further wakeup coming. The lost wakeup. set_current_state()’s smp_store_mb() on our side, paired with the full barrier inside [[Wakeups and try_to_wake_up|try_to_wake_up()]] on the waker’s side, forbids exactly that reordering: either we see CONDITION true on recheck, or the waker sees our non-runnable state. The kernel’s Documentation/memory-barriers.txt calls this the “sleep and wakeup” pattern and treats it as the canonical motivating example for smp_store_mb().

Note the subtle but critical difference between set_current_state() (barrier — use in the loop) and __set_current_state() (no barrier — use in step (4) where we are already committed to running and need no ordering against a waker).

The wait_event*() Macros — the Loop, Wrapped

Almost no driver writes the raw loop; they use the wait_event*() family, which encapsulates it. The core is ___wait_event() from include/linux/wait.h:

#define ___wait_event(wq_head, condition, state, exclusive, ret, cmd)      \
({                                                                         \
    struct wait_queue_entry __wq_entry;                                    \
    long __ret = ret;                                                      \
    init_wait_entry(&__wq_entry, exclusive ? WQ_FLAG_EXCLUSIVE : 0);       \
    for (;;) {                                                             \
        long __int = prepare_to_wait_event(&wq_head, &__wq_entry, state);  \
        if (condition)                                                     \
            break;                                                         \
        if (___wait_is_interruptible(state) && __int) {                    \
            __ret = __int;        /* signal: bail with -ERESTARTSYS */     \
            goto __out;                                                    \
        }                                                                  \
        cmd;                      /* usually schedule() */                 \
    }                                                                      \
    finish_wait(&wq_head, &__wq_entry);                                    \
__out:  __ret;                                                             \
})

This is the canonical loop generalised over four parameters: the queue, the condition, the state to sleep in, the exclusive flag, and the command run to sleep (schedule(), io_schedule(), schedule_timeout()). prepare_to_wait_event() does the enqueue-and-set-state under the queue lock; if the state is interruptible and a signal arrived, __int is non-zero and the macro bails out with the error. finish_wait() cleans up. The named wrappers just pick the parameters:

  • wait_event(wq, cond) — sleep in TASK_UNINTERRUPTIBLE, non-exclusive, schedule(). Will not wake on signals (the D state).
  • wait_event_interruptible(wq, cond) — sleep in TASK_INTERRUPTIBLE; returns -ERESTARTSYS if a signal arrives. The workhorse for syscall paths; callers must check the return value.
  • wait_event_killable(wq, cond) — sleep in TASK_KILLABLE; wakes only on a fatal signal (SIGKILL). See Process States and the Task State Machine for the signal_pending_state() logic that distinguishes these.
  • wait_event_timeout(wq, cond, timeout) — like wait_event but bounded; uses schedule_timeout() and returns the remaining jiffies (0 on timeout).
  • wait_event_idle(wq, cond) — sleeps in TASK_IDLE (uninterruptible but excluded from load average) for long-lived kernel-thread waits.

Each wrapper begins with might_sleep() (a debugging check that fires if called in atomic context) and an early if (condition) break; so the common “already satisfied” case never touches the queue at all.

Exclusive vs Non-Exclusive Waiters — Defeating the Thundering Herd

When wake_up() fires, how many waiters does it wake? That depends on the WQ_FLAG_EXCLUSIVE flag and the wake count. The core walker, __wake_up_common() from kernel/sched/wait.c:

list_for_each_entry_safe_from(curr, next, &wq_head->head, entry) {
    unsigned flags = curr->flags;
    int ret = curr->func(curr, mode, wake_flags, key);   /* try_to_wake_up via func */
    if (ret < 0)
        break;
    if (ret && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
        break;
}

It walks the list head-to-tail. For each entry it calls func (which, via default_wake_function → try_to_wake_up(), actually wakes the task and returns non-zero if a wake happened). The stopping rule is the key: it keeps going until it has woken nr_exclusive exclusive waiters (for wake_up(), nr_exclusive == 1). Non-exclusive waiters do not decrement the counter, so they are all woken; exclusive waiters are woken one (or nr) at a time and then the walk stops.

The arrangement that makes this work: add_wait_queue() (non-exclusive) inserts at the head, while add_wait_queue_exclusive() inserts at the tail. So the list is “all non-exclusive waiters, then all exclusive waiters.” A single wake_up() wakes every non-exclusive waiter plus exactly one exclusive waiter — then stops, leaving the remaining exclusive waiters asleep.

This is the cure for the thundering herd. Consider N tasks all blocked in accept() on one listening socket. If they were all non-exclusive, one incoming connection would wake all N; they would all race to accept(), one would win, and N-1 would re-sleep — a stampede that wastes CPU and scheduler work. By registering as exclusive waiters (which accept() does), only one is woken per connection. wake_up() (nr_exclusive = 1) wakes one; wake_up_all() (nr_exclusive = 0, which !--nr_exclusive never zeroes) wakes everyone — used when the event genuinely concerns all waiters (e.g. a buffer that all of them can now read).

WQ_FLAG_PRIORITY (used by, e.g., add_wait_queue_priority()) inserts an exclusive waiter at the very head, ahead of the non-exclusive ones, so it consumes the event first — used by io_uring and a few latency-sensitive paths.

The Low-Level Building Blocks

For code that cannot use the macros (it needs to drop and re-take a lock around schedule(), say), the explicit primitives from kernel/sched/wait.c are used directly:

  • prepare_to_wait(wq, entry, state) — under the queue lock: add the entry if not already queued, then set_current_state(state). The non-exclusive variant inserts at head.
  • prepare_to_wait_exclusive(wq, entry, state) — same, but sets WQ_FLAG_EXCLUSIVE and inserts at the tail; returns whether the queue was empty.
  • finish_wait(wq, entry) — __set_current_state(TASK_RUNNING) then, if still queued, take the lock and unlink. It uses list_empty_careful() to check queued-ness outside the lock as a fast path, falling back to the locked unlink only if needed. This matters because the entry lives on the sleeping task’s stack — leaving it linked after the function returns would corrupt the queue with a pointer into a defunct stack frame.
void prepare_to_wait(struct wait_queue_head *wq_head,
                     struct wait_queue_entry *wq_entry, int state)
{
    unsigned long flags;
    wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
    spin_lock_irqsave(&wq_head->lock, flags);
    if (list_empty(&wq_entry->entry))
        __add_wait_queue(wq_head, wq_entry);
    set_current_state(state);                 /* the barrier lives here */
    spin_unlock_irqrestore(&wq_head->lock, flags);
}

The explicit pattern is then: prepare_to_wait() → check condition → schedule() → loop → finish_wait(). The queue lock (spin_lock_irqsave) serialises list mutation against concurrent wakers, and is IRQ-safe because wakeups frequently happen from interrupt handlers.

The wait_woken() Variant — When the Lock Is Held Differently

A second correctness protocol exists for cases where the waiter cannot hold the queue lock across the condition check (some networking paths). wait_woken() / woken_wake_function() use an explicit WQ_FLAG_WOKEN flag plus paired barriers instead of the state-store-then-recheck dance. From kernel/sched/wait.c:

long wait_woken(struct wait_queue_entry *wq_entry, unsigned mode, long timeout)
{
    set_current_state(mode);                                   /* A: barrier */
    if (!(wq_entry->flags & WQ_FLAG_WOKEN) && !kthread_should_stop_or_park())
        timeout = schedule_timeout(timeout);
    __set_current_state(TASK_RUNNING);
    smp_store_mb(wq_entry->flags, wq_entry->flags & ~WQ_FLAG_WOKEN);  /* B: barrier */
    return timeout;
}
int woken_wake_function(struct wait_queue_entry *wq_entry, unsigned mode, int sync, void *key)
{
    smp_mb();                              /* C: barrier */
    wq_entry->flags |= WQ_FLAG_WOKEN;
    return default_wake_function(wq_entry, mode, sync, key);
}

Here the waker sets a flag on the entry (WQ_FLAG_WOKEN) under barrier C before waking, and the waiter checks that flag instead of an external condition; barriers A and B on the waiter pair with C on the waker so that either the waiter observes the flag (and skips the sleep) or the waker’s flag-set is ordered after the waiter’s state-set (so the wakeup lands). It is the same lost-wakeup problem solved with a per-entry flag rather than the shared __state recheck — useful when the recheck cannot be done atomically with the sleep.

Failure Modes

  • Lost wakeup → permanent sleep. Forgetting the barrier (using __set_current_state in the loop, or checking the condition before setting state) reopens the race. Symptom: a task wedged in S/D with the condition already satisfied; nothing ever wakes it. This is why you always use set_current_state() (barrier) in the loop and always re-check the condition after setting state, never before.
  • Spurious wakeups → must always re-check. wake_up() may wake a task whose condition is not actually true (shared queues, broadcast wakeups). The for(;;) loop with the condition recheck is mandatory precisely because a wakeup is a hint to re-evaluate, not a guarantee the condition holds. Code that sleeps once and assumes the condition is true on return is buggy.
  • Thundering herd. Using non-exclusive waiters where exclusive is correct (e.g. many threads accepting on one socket) wakes all of them per event; only one makes progress and the rest re-sleep, burning CPU. Fix: add_wait_queue_exclusive() / wait_event_*_exclusive().
  • Stack-resident entry left linked. If finish_wait() (or remove_wait_queue()) is skipped on an error path, the queue retains a pointer into the now-defunct stack frame — a use-after-return corruption. The ___wait_event() macro’s structure guarantees finish_wait() runs on every exit; hand-rolled loops must be just as careful.
  • Ignoring the interruptible return value. wait_event_interruptible() returns -ERESTARTSYS on signal; treating that as success and proceeding as if the condition were met is a real and common driver bug.

Alternatives and When to Choose Them

  • Completions (struct completion, Documentation/scheduler/completion.rst) are a thin, race-free wrapper built on wait queues for the specific “wait until this one-shot event is done” pattern (e.g. wait for a kthread to finish init). Reduce the condition to a single done flag; prefer them over open-coded wait-queue loops when the semantics are “wait for completion of X.” They are a sibling primitive, not a competitor — see Linux Kernel Synchronization MOC.
  • epoll/poll/select (Documentation/filesystems/epoll.rst) layer on wait queues from userspace’s perspective — file descriptors register wait-queue callbacks so that becoming-readable wakes the poller. The mechanism underneath is exactly the wait queue described here.
  • Futexes put the waiting in userspace and only enter the kernel on contention; the kernel side of a futex still parks the waiter, but on a hashed kernel wait structure rather than a driver’s wait_queue_head_t. For the userspace-synchronisation contrast see Futex and OS Synchronization Primitives.
  • Busy-waiting / spinlocks are the right answer only when the wait is shorter than the cost of a context switch and you are in atomic context; for anything that might block for an indefinite or non-trivial time, a wait queue (which yields the CPU) is correct. See Linux Kernel Synchronization MOC.

Production Notes

Wait queues are everywhere in the kernel: every blocking read()/write(), socket recv(), accept(), pipe, inotify, and futex-on-contention path bottoms out in one. The exclusive-waiter optimisation for accept() is a textbook production win — before it, accept-heavy servers (and the early epoll) suffered measurable thundering-herd overhead under high connection rates. The wait_woken() protocol was introduced specifically for the networking receive path where the original recheck-under-lock pattern did not fit, and the LWN coverage of wait-queue and epoll scalability documents the long tail of races and fixes in this area. The single most consequential operational lesson is the one the barrier enforces: the lost-wakeup race is real, it is timing-dependent (so it passes testing and bites in production under load), and the entire ceremony of set_current_state + recheck + finish_wait exists to make it impossible — which is why kernel review rejects any hand-rolled sleep loop that deviates from it.

See Also

Graph View

Backlinks