How a Preemptive RTOS Scheduler Picks the Next Task

Every deadline argument in a fixed-priority kernel rests on a single invariant: the task that runs is always the highest-priority task in the runnable set. A kernel that misses that invariant even occasionally cannot be reasoned about with the usual response-time analysis, because the analysis assumes the CPU is never given to a lower-priority task while a higher one waits. Building the invariant means maintaining a set of tasks that are ready, ordering that set cheaply, and switching context exactly when the ordering changes.

The states a task can occupy and why the ready set is small

A task in a small kernel occupies one of a handful of states: running, ready, blocked on a synchronisation object or a delay, suspended by explicit request, or terminated. Only the ready state and the running state compete for the processor. The blocked state is where most tasks spend most of their life, whether waiting for a timer to expire or for a queue to deliver a byte.

The size of the ready set is what makes the scheduler tractable. On a microcontroller with 32 KB of RAM, the practical number of tasks is in the single digits to low tens, and the number that are ready at any instant is usually two or three: the running task and the ones that were woken but not yet scheduled. A scheduler therefore does not need a general-purpose heap; an array indexed by priority is both faster and more predictable.

Priority in these kernels is usually a small integer, and the direction differs between kernels. In FreeRTOS the numerically highest priority value wins and the count of levels is a compile-time constant. µC/OS-II numbers them the other way: 0 is the highest priority and the idle task sits at OS_LOWEST_PRIO, the numerically largest value. µC/OS-III reversed that, so the highest value wins and level 0 is the idle task. The OSEK/AUTOSAR OS specification leaves the number of priority levels to the implementation and the configuration. The direction is arbitrary and only matters because every piece of documentation and every analysis formula is written in one convention. Confusing the two is a common source of inverted configurations when a code base is ported between kernels.

Bitmaps instead of searches

The classic implementation of the ready set is one bitmap of priority levels plus one ready list per level. A 32-level kernel uses a single 32-bit word; a 64-level kernel uses two words or a 64-bit word. Settling a bit when a task becomes ready costs one shift, one OR, and one store. Finding the highest-priority ready level costs a count-leading-zeros instruction on most target architectures, or a small lookup table when the architecture has no such instruction.

/* one bit per priority level; bit N set means level N has a ready task */
static volatile uint32_t ready_bitmap;

static inline void ready_set(unsigned prio)
{
    ready_bitmap |= (1u << prio);
}

static inline void ready_clear(unsigned prio)
{
    ready_bitmap &= ~(1u << prio);
}

/* highest set bit wins: 31 - clz(x) is the index of that bit in a 32-bit word */
static inline int highest_ready(void)
{
    if (ready_bitmap == 0u)
        return -1;                 /* nothing runnable but idle */
    return 31 - __builtin_clz(ready_bitmap);
}

The cost of the lookup is constant and independent of the task count, which is what makes the scheduler’s own execution time analysable. With a linear scan over task descriptors, the worst case is proportional to the number of tasks, so the scan’s loop count becomes part of the response-time budget and grows with every task added to the configuration. The bitmap removes that growth: the search is one instruction whatever the task count, and the number that enters the analysis is a constant.

One subtlety: the bitmap alone is not enough when several tasks share a priority level. Each level then needs a list of ready tasks at that level, and the scheduler must pick within the level. Most kernels use a first-in-first-out order within the level, which gives round-robin behaviour between equals and keeps the choice O(1). Time-slicing between equal priorities is a separate policy knob, enabled per level or per task; when it is disabled, the task at a level runs until it blocks or a higher priority becomes ready, and a task that never blocks starves its equals forever.

The switch path

Three events can change the ordering: a task blocks, a task is made ready, or the tick handler decides a time slice has expired. Each of them converges on the same test: compare the currently running task’s priority against the highest ready priority. If the running task is still the highest, nothing happens. If a higher one exists, the kernel must save the running context and load the ready one.

On a Cortex-M part the pend-and-tail-chain of the exception model makes this cheaper than a full switch. The kernel triggers a supervisor call or pends the context-switch exception, and the hardware stacks the caller-saved registers automatically on exception entry. Only the remaining callee-saved registers and the stack pointer need to be stored by the kernel, and the return from exception unstacks the rest. Because the switch happens in exception context, the deferred switch is taken at the next instruction boundary rather than at an arbitrary point, which removes the need for the caller to save state around a call that may switch.

Kernels that run on architectures without such hardware support store the full register file on the task’s stack. The store is five to twenty words depending on the architecture, plus the stack pointer, plus a status word; the load mirrors it. The whole save-restore pair is on the order of tens of cycles on a fast core and a few hundred on a small one, and it appears in the response time of every task that wakes a higher-priority one.

A dedicated interrupt stack, or a separate system stack used only while in exception mode, changes the accounting. If every task has its own stack and interrupts run on the current task’s stack, the per-task stack must be sized for the deepest interrupt path in the system, which is often far larger than the task’s own needs. A separate interrupt stack lets each task stack be sized for its own calls only, at the cost of the interrupt stack being shared and therefore needing the maximum nesting depth across all handlers.

Where preemption points actually sit

The kernel can only switch at points where it controls the code. Everything else runs to completion. Two consequences follow.

First, a kernel that disables interrupts for a section converts that section into an interference term for every task in the system, regardless of priority. A long critical section violates the priority invariant as surely as a scheduler bug: during it, a low-priority task is holding off a high-priority one. The interrupt-masking time is the number that must be bounded and documented, and it belongs in the response-time arithmetic alongside the kernel’s own execution time.

Second, the API calls that can block are exactly the points where the scheduler is invoked. A task calling into a queue receive with a timeout enters the kernel, notices the queue is empty, moves itself to the blocked state, and then runs the scheduler. A task calling a non-blocking API cannot be preempted at that point because nothing has changed. Cooperative scheduling is the same machinery with the scheduler only invoked at explicit yield points, which removes the preemption cost and adds the requirement that every task yield often enough for the application’s latency needs.

The ordering that the scheduler produces is what the analysis in rate-monotonic priority assignment assumes, and the guarantee only holds up to a utilisation bound; past it, deadlines can be missed in ways that need a different kind of analysis, covered in response-time analysis for fixed-priority sets.

Degenerate configurations

Several configurations break the invariant without looking broken.

The idle task is a real task with the lowest possible priority, and it exists so that the ready set is never empty. A system that leaves the idle priority equal to another task’s gets kernel behaviour that differs between builds; kernels typically allocate the idle task a slot in the task table and reduce the usable task count by one, which is why the maximum task count in a configuration is often one more than the number the application can create.

Priorities equal to the highest level can overflow the bitmap. A configuration that allows priority values up to and including the number of levels shifts by exactly the word width, which on most architectures is undefined behaviour rather than a zero result. Compile-time assertions on the configured level count catch this before it reaches hardware.

Tasks created with the same priority as the currently running task do not preempt it, and the new task stays ready until the running one blocks. This is not a bug but it surprises code that expects creation to imply scheduling; some kernels provide a start-suspended creation option precisely so that a set of tasks can be created and then released together.

Finally, priority is not a scheduling deadline. A task that is nominally the highest priority but wakes on a period shorter than its own execution time will still overflow, because the invariant only orders the ready set; it says nothing about whether the set can be completed in time. That question belongs to the analysis, and the analysis is only as good as the kernel’s conformance to the invariant.