How does an RTOS scheduler pick the next task to run?
Short answer: It keeps one ready list per priority and a bitmap with one bit per priority that has ready tasks. To pick the next task, it finds the highest set bit (one CLZ instruction on Cortex-M3+), then takes the task at the head of that priority's list (rotating it to the end for round-robin). This makes scheduling O(1), independent of the number of tasks, which is essential for deterministic timing.
#include <stdint.h>
#define NUM_PRIO 32
typedef struct tcb { struct tcb *next; uint8_t prio; /* saved SP, stack, ... */ } tcb_t;
static tcb_t *ready_head[NUM_PRIO], *ready_tail[NUM_PRIO];
static uint32_t ready_bitmap; /* bit p set = some task of priority p is ready */
void make_ready(tcb_t *t)
{
t->next = NULL;
if (ready_tail[t->prio]) ready_tail[t->prio]->next = t; else ready_head[t->prio] = t;
ready_tail[t->prio] = t;
ready_bitmap |= 1u << t->prio;
}
tcb_t *pick_next(void) /* highest number = highest priority here */
{
if (!ready_bitmap) return NULL; /* only the idle task: handled separately */
unsigned p = 31u - (unsigned)__builtin_clz(ready_bitmap);
tcb_t *t = ready_head[p];
ready_head[p] = t->next; /* rotate for round robin among equals */
if (!ready_head[p]) { ready_tail[p] = NULL; ready_bitmap &= ~(1u << p); }
return t; /* caller re-adds it via make_ready() if still ready */
}
Other pieces of a scheduler
- Delayed list: blocked tasks with timeouts, sorted by wake-up time (FreeRTOS keeps two lists to handle tick-count overflow); the tick handler moves expired tasks to ready.
- Event lists: each queue/semaphore has a list of waiting tasks sorted by priority, so the highest-priority waiter wakes first.
- Scheduling points: tick interrupt, any API call that unblocks a higher-priority task, task blocking or yielding, ISR exit.
- Idle task when nothing else is ready.
FreeRTOS specifics: configUSE_PORT_OPTIMISED_TASK_SELECTION uses CLZ and limits priorities to 32; the generic method scans from the top priority down. Zephyr offers a simple list, a scalable red-black tree, or a multi-queue backend (CONFIG_SCHED_*).
Design-interview extension: "add resource management": combine with priority-inheritance mutexes (next questions) and admission checks for deadlines.