The idea: the highest priority always runs
A normal Linux scheduler (CFS, now EEVDF) is about fairness: every task gets a share of the CPU. A real-time scheduler is about priority: the runnable task with the highest priority runs, now, and keeps running until something with a higher priority wakes up. That makes response times predictable, which is what a motor controller, an audio thread or a spacecraft needs. It also means a low-priority task can wait forever, and a lock can make a high-priority task wait for a low one. The page runs three tasks on one CPU, one tick per step, and draws who runs on a Gantt chart.
SCHED_FIFO and SCHED_RR
Linux has two real-time policies, each with a priority from 1 to 99 (higher wins). A SCHED_FIFO task runs until it blocks, calls sched_yield() or ends. No timer takes the CPU back from it; only a task with a higher priority that wakes up preempts it, and then the preempted task waits at the head of its priority's queue, so it goes on first afterwards. SCHED_RR is the same plus a time slice (/proc/sys/kernel/sched_rr_timeslice_ms, 100 ms by default; 3 ticks on the page). The slice only rotates tasks of the same priority: a lower-priority task still never runs while a higher one is runnable.
| SCHED_FIFO (Demo: SCHED_FIFO) | SCHED_RR (Demo: SCHED_RR) | |
|---|---|---|
| A and B, both prio 50, 6 ticks each | A runs to the end, then B | A and B take turns every 3 ticks |
| C, prio 80, wakes at tick 5 | preempts A at once (ticks 5–6) | preempts B at once (ticks 5–6) |
| B first runs at tick | 8 | 3 |
| done at tick | A 8, C 7, B 14 | A 11, C 7, B 14 |
RT tasks starve normal tasks: RT throttling
Ordinary processes run under SCHED_OTHER (scheduled by CFS/EEVDF, with nice values). They only get the CPU when no real-time task is runnable. A SCHED_FIFO task stuck in a loop therefore freezes every normal task on that CPU, including the shell you would use to kill it (Demo: RT busy loop starves CFS: shell gets no CPU for the last 28 ticks). As a safety net Linux has RT throttling: real-time tasks may use sched_rt_runtime_us = 950000 of every sched_rt_period_us = 1000000, so normal tasks keep 50 ms of each second. The page scales it to 8 of every 10 ticks (Demo: RT throttling: shell runs in ticks 18–19 and 28–29 and finishes at tick 30). Writing -1 to sched_rt_runtime_us turns the limit off. Recent kernels (6.12 and later) reserve that time with a deadline "fair server" instead, with the same effect.
Priority inversion
Locks break the simple rule. Take three tasks: L (prio 10) locks mutex m; H (prio 90) wakes up, preempts L and asks for m, so H blocks until L unlocks. That wait is fine as long as it is short: L only has to finish its critical section. But now M (prio 50) wakes up. It does not need m, and it outranks L, so it preempts L. L cannot run, so it cannot unlock, so H keeps waiting, for as long as M runs. The high task is effectively running at the medium task's priority: a priority inversion, and its length has no bound (Demo: priority inversion: H is blocked for 13 ticks, from tick 3 to 15, and finishes at tick 19, after M).
The Mars Pathfinder, 1997
A few days after Pathfinder landed on Mars in July 1997, the lander began to reset itself, losing data each time. It ran the VxWorks real-time OS. A high-priority task, bc_dist, moved data on the "information bus"; a low-priority meteorological task (ASI/MET) also published to the bus and took the bus's mutex to do so; a long-running communications task sat at medium priority. When the weather task held the mutex, bc_dist blocked on it, and the comms task preempted the weather task. A watchdog in the scheduler task bc_sched then saw that bc_dist had not finished its cycle and reset the whole system (Demo: Mars Pathfinder watchdog reset: the reset at tick 12). Engineers at JPL reproduced the reset on a copy of the lander on Earth, found the cause in the trace, and uploaded a small patch that turned on priority inheritance for that mutex. The resets stopped (Demo: Pathfinder with inheritance: bus done at tick 7).
Priority inheritance
With priority inheritance, a task that owns a mutex runs at the highest priority of the tasks waiting for it. When H blocks on m, L is lifted to prio 90, so M cannot preempt it. L finishes the critical section, unlocks, drops back to prio 10, and H gets m at once. H's wait is now bounded by the length of L's critical section, whatever other tasks do (Demo: priority inheritance fixes it: H is blocked for 3 ticks, ticks 3–5, and finishes at tick 9 instead of 19). M still finishes, just later (tick 19 instead of 13). An alternative is the priority ceiling protocol (PTHREAD_PRIO_PROTECT): every task that locks the mutex runs at a fixed ceiling priority while it holds it, which also prevents some deadlocks.
| PTHREAD_PRIO_NONE | PTHREAD_PRIO_INHERIT | |
|---|---|---|
| L's priority while H waits for m | 10 (its own) | 90 (inherited from H) |
| Can M preempt L? | yes ✗ | no ✓ |
| H blocked on m | 13 ticks, grows with M | 3 ticks, the rest of L's critical section |
| H done at tick | 19 | 9 |
Using it on Linux
Start a program with a real-time policy with chrt -f 50 ./prog (FIFO) or chrt -r 50 ./prog (RR), or call sched_setscheduler() / pthread_setschedparam(); this needs CAP_SYS_NICE or an rtprio limit. For a mutex shared between threads of different priorities, set the protocol before creating it:
pthread_mutexattr_t a;
pthread_mutexattr_init(&a);
pthread_mutexattr_setprotocol(&a, PTHREAD_PRIO_INHERIT);
pthread_mutex_init(&m, &a);glibc then uses a PI futex (FUTEX_LOCK_PI): the kernel records the owner's thread id in the futex word and boosts it through an rt_mutex, following chains of locks (A waits for B, which waits for C). The kernel's own sleeping locks become rt_mutexes with inheritance in a PREEMPT_RT kernel. The plain futex-based mutex has no inheritance, which is the default (PTHREAD_PRIO_NONE).
See also CPU scheduling (FCFS, round robin, priority scheduling and CFS on the same processes), preemptive vs cooperative scheduling, the Linux context switch and mutex vs spinlock.
What the page leaves out
One CPU only: on a multi-core machine each CPU has its own run queues, and the kernel pushes and pulls RT tasks between CPUs so that the highest-priority ones run somewhere. A context switch takes no time here, the RT slice and throttling numbers are scaled down, and there is one mutex, so there are no inheritance chains and no deadlocks. The page also leaves out SCHED_DEADLINE (earliest deadline first with a runtime budget), SCHED_BATCH and SCHED_IDLE, nice values inside CFS, interrupt handlers and softirqs, which run above every task, and schedulability analysis (rate-monotonic priorities and the formulas that prove deadlines are met). VxWorks priorities on Pathfinder count the other way (0 is the highest); the page uses Linux numbers.