Preemptive priority scheduling

Deep dive

How it works

In: tasks with fixed priorities (0 = lowest) and events that change readiness (release, ISR gives a semaphore, tick, unlock) · Out: which task runs next · State: per task: priority, saved context, stack; per priority one FIFO; one ready bitmap · Cost: O(1) pick; one context save and restore per switch

1. A task becomes ready (timer release, ISR signal, lock freed): append it to the FIFO of its priority and set that bit in the bitmap.
2. A task blocks, sleeps or finishes: remove it; if its FIFO is empty, clear the bit.
3. Pick: top = 31 - bitmap.leading_zeros(); the head of FIFO top runs. An empty bitmap runs the idle task.
4. Reschedule points, where the pick can change: a task blocks or yields, becomes ready (also from an ISR on its way out), a tick expires a delay or a slice, a lock is released.
5. If the pick differs from the running task, switch: save registers and stack pointer into the old control block, load the new one's. The preempted task stays at the head of its FIFO and resumes first at its level.
6. Equal priorities: FIFO runs a task until it blocks; with time slicing, an expired slice moves the running task to the back of its FIFO.
7. On Cortex-M the switch is deferred: an ISR or SysTick only sets the PendSV pending bit; PendSV runs at the lowest interrupt priority, after all other handlers have finished.
8. Critical sections mask interrupts or lock the scheduler around kernel structures; their length adds to every task's worst-case latency.

Real kernels differ in the data structure. FreeRTOS keeps one list per priority (pxReadyTasksLists); generic selection walks down from uxTopReadyPriority to the first non-empty list, and configUSE_PORT_OPTIMISED_TASK_SELECTION uses a 32-bit bitmap and clz (at most 32 priorities in the Cortex-M4F port). Zephyr's CONFIG_SCHED_MULTIQ is documented as an array of lists, one per priority; its source finds the top bit with a trailing-zeros count on a bitmask. Linux (sched(7)) keeps a runnable list per static priority, 1 to 99.

Code

A discrete-time, single-core simulator: a u32 bitmap with leading_zeros, one FIFO per priority, periodic releases, round-robin slices, and one lock with optional priority inheritance (std only; compiled and run).

use std::collections::VecDeque;
#[derive(Clone, Copy)] enum Op { Run, Lock, Unlock } // Run = one tick of CPU; Lock/Unlock take no time
struct Task {
    base: usize, prio: usize, period: u32, offset: u32, script: Vec<Op>,
    pc: usize, active: bool, released: u32, resp_max: u32, ran: u32,
}
struct Sched {
    ready: Vec<VecDeque<usize>>, // one FIFO per priority, 31 = highest
    bitmap: u32,                 // bit p set <=> ready[p] is non-empty
    tasks: Vec<Task>,
    owner: Option<usize>, waiters: VecDeque<usize>, // one shared lock
    inherit: bool, slice: Option<u32>,
}
impl Sched {
    fn new(tasks: Vec<Task>, inherit: bool, slice: Option<u32>) -> Self {
        Sched { ready: vec![VecDeque::new(); 32], bitmap: 0, tasks, owner: None, waiters: VecDeque::new(), inherit, slice }
    }
    fn push(&mut self, id: usize) {
        let p = self.tasks[id].prio;
        self.ready[p].push_back(id); self.bitmap |= 1 << p;
    }
    fn remove(&mut self, id: usize) {
        let p = self.tasks[id].prio;
        self.ready[p].retain(|&x| x != id);
        if self.ready[p].is_empty() { self.bitmap &= !(1 << p); }
    }
    fn pick(&self) -> Option<usize> { // O(1): highest set bit, head of its FIFO
        if self.bitmap == 0 { return None; }
        self.ready[31 - self.bitmap.leading_zeros() as usize].front().copied()
    }
    fn set_prio(&mut self, id: usize, p: usize) { self.remove(id); self.tasks[id].prio = p; self.push(id); }
    fn finish(&mut self, id: usize, t: u32) { // job done at time t
        let k = &mut self.tasks[id];
        (k.active, k.resp_max) = (false, k.resp_max.max(t - k.released));
        self.remove(id);
    }
    fn run(&mut self, ticks: u32) -> Vec<Option<usize>> {
        let (mut trace, mut last, mut used) = (vec![], None, 0);
        for t in 0..ticks {
            for id in 0..self.tasks.len() { // releases: a new job arrives
                let k = &mut self.tasks[id];
                if k.active && k.pc == k.script.len() { self.finish(id, t); }
                let k = &mut self.tasks[id];
                if t >= k.offset && (t - k.offset) % k.period == 0 && !k.active {
                    (k.active, k.pc, k.released) = (true, 0, t);
                    self.push(id); // an overrunning job skips its next release
                }
            }
            loop { // zero-time ops are handled until someone runs or all block
                let Some(id) = self.pick() else { trace.push(None); break };
                let k = &mut self.tasks[id];
                if k.pc == k.script.len() { self.finish(id, t); continue; }
                match k.script[k.pc] {
                    Op::Run => {
                        k.ran += 1; k.pc += 1; trace.push(Some(id));
                        used = if last == Some(id) { used + 1 } else { 1 };
                        last = Some(id);
                        if self.slice == Some(used) { // slice over: to the back of its FIFO
                            used = 0;
                            let q = &mut self.ready[k.prio];
                            if let Some(h) = q.pop_front() { q.push_back(h); }
                        }
                        break;
                    }
                    Op::Lock if self.owner.is_none() => { self.owner = Some(id); k.pc += 1; }
                    Op::Lock => { // blocked: leave the ready queue, lend our priority
                        let (o, p) = (self.owner.unwrap(), k.prio);
                        self.remove(id); self.waiters.push_back(id);
                        if self.inherit && self.tasks[o].prio < p { self.set_prio(o, p); }
                    }
                    Op::Unlock => {
                        k.pc += 1; self.owner = None;
                        if k.prio != k.base { let b = k.base; self.set_prio(id, b); }
                        if let Some(w) = self.waiters.pop_front() { // hand the lock over
                            self.owner = Some(w); self.tasks[w].pc += 1; self.push(w);
                        }
                    }
                }
            }
        }
        trace
    }
}
fn task(prio: usize, period: u32, offset: u32, script: Vec<Op>) -> Task {
    Task { base: prio, prio, period, offset, script, pc: 0, active: false, released: 0, resp_max: 0, ran: 0 }
}
fn runs(n: usize) -> Vec<Op> { vec![Op::Run; n] }
fn main() {
    // 1. High preempts low at once: response = execution time (2); low pays 2 extra.
    let mut s = Sched::new(vec![task(3, 10, 3, runs(2)), task(1, 20, 0, runs(8))], false, None);
    s.run(40);
    assert_eq!((s.tasks[0].resp_max, s.tasks[1].resp_max), (2, 10));
    // 2. Equal priorities: FIFO without slicing, round-robin with a 2-tick slice.
    let two = || vec![task(2, 100, 0, runs(6)), task(2, 100, 0, runs(6))];
    let flat = |s: &mut Sched| s.run(12).into_iter().flatten().collect::<Vec<_>>();
    assert_eq!(flat(&mut Sched::new(two(), false, None)), [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]);
    assert_eq!(flat(&mut Sched::new(two(), false, Some(2))), [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]);
    // 3. Overload: a task using 100 % of the CPU starves everything below it.
    let mut s = Sched::new(vec![task(3, 4, 0, runs(4)), task(1, 20, 0, runs(3))], false, None);
    s.run(100);
    assert_eq!(s.tasks[1].ran, 0);
    // 4. Priority inversion: L(1) holds the lock, H(3) wants it, M(2) runs 6 ticks.
    let l = [vec![Op::Lock], runs(4), vec![Op::Unlock]].concat();
    let h = vec![Op::Run, Op::Lock, Op::Run, Op::Unlock];
    let mk = |inh| Sched::new(vec![task(1, 99, 0, l.clone()), task(3, 99, 1, h.clone()), task(2, 99, 2, runs(6))], inh, None);
    let (mut plain, mut pi) = (mk(false), mk(true));
    (plain.run(30), pi.run(30));
    assert_eq!((plain.tasks[1].resp_max, pi.tasks[1].resp_max), (11, 5)); // M no longer delays H
}

Each scenario is an assert: a preempting task's response time equals its execution time; equal priorities interleave 0 0 1 1 … under a 2-tick slice; the low task never runs under overload; a medium task stretches the high task's response from 5 to 11 ticks until inheritance is on.

Complexity and constants

• Enqueue, dequeue and (with the bitmap) pick are O(1); the generic FreeRTOS scan is O(priorities).
• Memory: a list head per priority, a control block and a stack per task. On Cortex-M a switch saves 8 words stacked by hardware plus r4-r11 and the return code pushed by PendSV (FreeRTOS port), plus 16 FPU registers if the task used the FPU.
• Pick throughput, measured on this Mac (Apple M4 Pro, single thread, release build): about 1.7 ns per pick including the random bit flip driving each iteration, order of 580 M picks/s. Bit scan only, not a context switch.

Efficiency

• Cost: a pick is a few ns (measured above); the context switch dominates: a few dozen words of stack traffic on Cortex-M, more with FPU state, plus cache and TLB refill on larger cores (not measured). Periodic tick wake-ups also cost idle energy, which tickless idle removes. Bound: switch memory traffic and masked-interrupt time, not selection.
• Levers:
  • bitmap plus clz instead of scanning priorities — O(priorities) to O(1) (FreeRTOS configUSE_PORT_OPTIMISED_TASK_SELECTION) — at most 32 priorities per word
  • tickless idle — no periodic wake-ups while idle (FreeRTOS configUSE_TICKLESS_IDLE) — battery-powered devices
  • short ISRs deferring work to a task — shorter masked sections — all designs
  • time slicing off (configUSE_TIME_SLICING = 0) — no tick-driven switches among equals — when peers block often anyway
  • one shared stack for run-to-completion tasks (RTIC) — no per-task stack — when tasks never block mid-body
• Naive → standard → state of the art:
  • scan all tasks on every event · O(tasks)
  • per-priority FIFOs, bitmap and clz, deferred PendSV switch · O(1) pick
  • tasks as interrupt handlers run by the interrupt controller (RTIC) · no software scheduler, one stack

Implementation notes

• Assign priorities by design: shorter period higher (Liu and Layland 1973); re-run the rate-monotonic test when execution times change.
• Put PendSV and SysTick at the lowest interrupt priority (the FreeRTOS port does) so a switch never interrupts another handler.
• FreeRTOS's Cortex-M critical sections raise BASEPRI, leaving higher-priority interrupts live; Zephyr's k_sched_lock() stops preemption without masking interrupts.
• ISRs run before any thread (Zephyr docs): keep them short, hand work to a task (interrupt handling).
• On Linux leave sched_rt_runtime_us at its 950000 default (5 % reserved for normal threads) or set RLIMIT_RTTIME, so a spinning real-time thread cannot freeze the machine (sched(7)).

Pitfalls

• Priority inversion: low holds a lock, high waits, medium runs. Mars Pathfinder's 1997 resets were this: the bus mutex had inheritance off. Use priority inheritance or ceilings.
• A high task that never blocks starves all below it, including a lowest-priority watchdog supervisor.
• Long ISRs or masked sections inflate latency for every task.

Variants and alternatives

In production

• Spacecraft: VxWorks on Mars Pathfinder (preemptive priority scheduling, and the inversion above).
• General-purpose OS: Linux SCHED_FIFO and SCHED_RR; see real-time Linux scheduling.
• Microcontroller firmware: FreeRTOS and Zephyr (fixed priorities, optional slicing, tickless idle); RTIC for Rust on Cortex-M.

Implementations

Sources

• C. L. Liu, J. W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, JACM 20(1), 1973. paper
• L. Sha, R. Rajkumar, J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Trans. Computers 39(9), 1990. paper
• Zephyr Project, Scheduling (kernel services). docs · priority_q.h
• FreeRTOS-Kernel source: tasks.c, Cortex-M4F port.c, portmacro.h
• Linux man-pages, sched(7). man page
• Mike Jones, What Happened on Mars? (account of D. Wilner's keynote at RTSS 1997). email
• RTIC book. docs