Blocking Primitives: How a Task Waits Without Spinning

A while (!flag) {} loop burns a core and, worse, prevents every lower-priority task from running, because the spinning task never leaves the ready state. The mechanism that replaces it is the blocked state: the waiting task is removed from the ready set entirely, and the scheduler’s invariant is preserved because a blocked task is not competing for the processor. The whole point of a semaphore, queue, mailbox, or event group in an RTOS is to make a task leave the ready set and later re-enter it at the moment the resource becomes available.

What “waiting” has to store

A blocked task still needs to be found when the event occurs. The kernel therefore keeps a list attached to each synchronisation object of all tasks waiting on it, and a task descriptor carries the fields needed to reinsert it.

The traditional representation is a doubly linked list per object, ordered by waiting task priority or by arrival. When a semaphore is given, the kernel takes the head of the list, removes it, and places that task in the ready set. With a priority-ordered list, insertion is a search and the give is O(1); with a FIFO list, insertion is O(1) and the give still O(1), but the highest-priority waiter may not be the one woken. Most real-time kernels choose the priority-ordered list because a FIFO order allows a low-priority task to hold the wake-up slot while a high-priority task waits behind it, which is precisely the kind of unbounded delay that the priority scheme exists to prevent.

The task also stores what it is waiting for and the result of the wait. A take with a timeout must distinguish “acquired” from “timed out” when it resumes, and the kernel records the outcome in the task’s control block before making it ready. Without that field, a task cannot tell a successful take from a timeout without a second look at the object, which is racy if another task takes the object in between.

The take path, instruction by instruction

The following is the shape of a mutex take with a timeout, in pseudocode that mirrors what the kernels do:

int take(mutex_t *m, uint32_t timeout_ticks)
{
    unsigned key = irq_save();            /* atomic w.r.t. the ready set */

    if (m->owner == NULL) {
        m->owner = current_task;
        irq_restore(key);
        return 0;                          /* fast path: no kernel entry */
    }
    if (timeout_ticks == 0) {
        irq_restore(key);
        return -EBUSY;                     /* polling non-blocking take */
    }

    list_insert(&m->waiters, current_task);   /* ordered by priority */
    current_task->waiting_on = m;
    current_task->wake_result = -ETIMEDOUT;   /* default if the timer fires */
    block_current(timeout_ticks);             /* state, timer, schedule */
    irq_restore(key);

    return current_task->wake_result;
}

Three things in that sequence matter more than the rest.

The fast path does not enter the scheduler. When the object is free, the take is a compare, a store, and two interrupt-mask operations, and the calling task keeps running. Making the uncontended case fast is worth more than making the contended case elegant, because a well-designed system spends most of its time on uncontended paths.

The default result is set before blocking, not after waking. The timer that implements the timeout writes -ETIMEDOUT into the field when it fires; the give path overwrites it with zero before making the task ready. Setting the default first means the give path only has to record success, and a timer that fires concurrently with a give cannot leave the field uninitialised.

The interrupts are masked across the list insertion and the block, not merely across the compare. If the task inserted itself into the waiter list and then enabled interrupts before blocking, a give could arrive in the window between insertion and block, wake the task, and leave it both ready and blocked. Kernels that must avoid long mask times use a lock-free or per-object critical section instead, but the window must be closed either way.

Waking: the give path and the deferred switch

The give path is short but has one non-obvious obligation: after making the woken task ready, it must check whether the woken task has higher priority than the current one, and if so, yield to it. On a kernel with a deferred switch, that check is a flag and the actual switch happens at the next kernel exit point. On a kernel that switches inline, it happens immediately, inside the give call.

This is where a common bug lives. A give called from an interrupt handler hands the woken task a ready slot, and the handler must not switch context itself, because the handler is in exception mode and the task it interrupted is not at a safe point. The kernel instead pends a context-switch exception, which the hardware takes as soon as the handler returns. If the handler was already at the lowest nesting level, the switch happens before any task code executes again. If it was nested inside another interrupt, the switch waits for unwinding, which means a system with long nested handlers has additional wake-up latency entirely unrelated to the semaphore.

The latency from “give happens” to “woken task executes its first instruction” is therefore the sum of: the remaining interrupt handler code, exception return and stacking, the scheduler’s choice of the next task, the register restore, and — if a wait-on-event instruction is not available — the pipeline refill. On small cores the total is measured in microseconds rather than milliseconds; the analysis in interrupt latency and kernel overhead breaks it into the pieces that can be bounded separately.

Timeouts and the tick

A timeout is implemented by a list of tasks ordered by expiry tick, with the list head being the next thing to expire. The tick handler decrements nothing; it compares the current tick count against the head’s expiry and pops the expired entries, moving each to the ready set with the timeout result recorded.

Storing an absolute expiry rather than a countdown removes the per-tick work proportional to the number of blocked tasks. A countdown implementation decrements every waiting task’s counter on every tick, which turns the tick handler into an O(n) loop over the blocked set. Absolute expiry makes the common case a single comparison against the head, so the tick cost is independent of the number of blocked tasks. The price is wrap-around: a counter that advances at the tick rate eventually wraps, and comparisons must be written as (int32_t)(now - deadline) >= 0 rather than now >= deadline so that the wrap is invisible as long as the maximum timeout is less than half the counter’s range.

Timeout granularity is one tick. A task asking to wait 5 ticks resumes somewhere between 4 and 5 ticks after the request, depending on where in the tick period it blocked. Systems that need tighter resolution either raise the tick rate or add a second timer path with a finer resolution, at the cost of more interrupts per second and a bigger interference term for everything else.

A timeout of zero is not a blocking operation; it is a poll. Kernels implement it as the fast path with an immediate failure, which is why a zero-timeout take can be called from an interrupt handler while a blocking one cannot. The distinction between “try” and “take” exists in the API precisely because the two have different legality in interrupt context, not because they differ in efficiency.

Counting semaphores, queues, and the rest

The same blocked-list machinery serves queues, where the list has two heads — one for senders waiting for space and one for receivers waiting for data — and events, where the wake condition is a mask rather than a count. A queue with capacity N and a waiters list behaves like a counting semaphore whose count is the free space, plus a memory region; the wake-up logic is identical.

The differences that matter are in what happens at the boundaries. A queue send that finds the queue full blocks on the space list, and the task that receives from the queue wakes the head of the space list after removing an item. A queue of length one with an overwrite-style send is the standard way to build a mailbox: a new item replaces the old one instead of blocking, the receive blocks, and the mailbox holds the newest item rather than a backlog.

Priority inheritance at the mutex layer is what keeps these primitives from converting a design bug into an unbounded delay; priority inversion and the blocking time it causes covers the mechanism and its costs.

Costs and degenerate cases

The memory cost per synchronisation object is a list head of two pointers plus a count or a buffer pointer: a few words, plus one word per waiting task’s link. The task cost is the field set in the control block, again a few words.

Deleting a task that is blocked on a queue leaves a dangling entry in the list unless the kernel walks every object and removes it. Kernels that support task deletion require an explicit deletion path that is O(number of objects) or that leaves a tombstone the next give must skip; systems that avoid task deletion entirely avoid the problem.

A semaphore used as an event flag, where two tasks block on the same object and a single give wakes only one, is a classic mistake when the intended semantics are broadcast. A task that waits for a state change rather than for a token should use an event-group or mailbox construct that wakes all waiters, especially if the waiters are at different priorities and the give happens repeatedly.

Timing out at exactly the moment of a give produces either result, and both are correct; the application must be written to tolerate a timeout even when the resource appeared available at the same instant. Treating the timeout path as unreachable is the assumption that breaks first under load.