The 1973 Paper Your Firmware Still Obeys
In 1973, C. L. Liu and James Layland published "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment" in the Journal of the ACM. Fifty-plus years later it remains the most-cited result in real-time systems, and every priority assignment you make in FreeRTOS or Zephyr is either following its advice or silently violating it. The paper answers a deceptively simple question: if you have periodic tasks on one CPU with fixed priorities, what's the right way to assign those priorities, and how much of the CPU can you safely use?
The answers: shortest period gets highest priority, and about 69%. Both deserve unpacking, because the second one surprises everyone the first time.
Rate-Monotonic Priority Assignment
The rule is mechanical. Each periodic task has a period T (how often it runs) and a worst-case execution time C (how long it needs per cycle). Rate-monotonic scheduling assigns priority strictly by rate: the task with the shortest period gets the highest priority, longest period gets the lowest. No judgment calls about which task feels important.
Liu and Layland proved this is optimal among all fixed-priority schemes for the classic model (independent periodic tasks, deadline equals period, preemptive scheduler): if any fixed-priority assignment can meet all deadlines, rate-monotonic can too. That optimality proof is why the rule survived fifty years unchanged. Your intuition about importance is worse than the arithmetic, and the failure mode of importance-based priorities is a "critical" slow task starving a fast loop, which is how you get the class of timing bugs that froze Mars Pathfinder.
The 69% Result
The famous half of the paper is the utilization bound. Sum each task's C/T, its fraction of the CPU, and Liu and Layland proved that n tasks are guaranteed schedulable under rate-monotonic if that total stays at or below n(2^(1/n) - 1). For one task the bound is 100%. For two, about 82.8%. As n grows the expression converges to ln 2, roughly 69.3%.
Read that carefully, because it says something uncomfortable: with many rate-monotonic tasks, you can only guarantee deadlines up to about 69% CPU utilization. The remaining 31% isn't wasted, background work runs in it, but it can't carry hard deadlines on the guarantee. When a spec sheet or a manager assumes 95% loading with deadlines intact, this fifty-year-old theorem is the citation for why not.
Two important footnotes. The bound is sufficient, not necessary: task sets above 69% often still meet every deadline, especially with harmonic periods (10 ms, 20 ms, 40 ms nests perfectly, and harmonic sets are schedulable to 100%). To know for sure above the bound, you run exact response-time analysis instead of the closed-form test. And the model assumes zero-cost context switches and independent tasks; every mutex and shared bus in your real firmware erodes the ideal.
Using It in Actual Firmware
The practical recipe is short. List every periodic activity with its true period and measured worst-case execution time, measured, not estimated, because C is where designs lie to themselves. Assign RTOS priorities strictly by period. Sum the C/T column. Under the n-task bound: provably fine. Between the bound and 100%: do response-time analysis or restructure toward harmonic periods. Over 100%: no scheduler can save you; that's a hardware or scope problem.
The discipline matters more than the math. Rate-monotonic turns priority assignment from a political argument into a spreadsheet column, and it gives the what-is-an-RTOS mental model its quantitative teeth: the scheduler guarantees the highest-priority ready task runs, and Liu-Layland tells you what that guarantee is worth end to end.
Frequently Asked Questions
What about earliest-deadline-first? EDF, analyzed in the same 1973 paper, is dynamic-priority and schedulable to 100% utilization on one CPU. It wins on paper; fixed-priority RMS wins in practice because every commercial RTOS implements fixed priorities natively, RMS behavior under overload degrades predictably (the slowest task misses first), and certification tooling is built around fixed-priority analysis.
Does rate-monotonic apply to interrupts? Conceptually yes: interrupt handlers are effectively the highest-priority tasks, so their load counts against the same utilization budget. A design that ignores ISR time in the C/T sum is analyzing a fantasy system.
My deadlines aren't equal to my periods. Now what? That's deadline-monotonic territory: assign by deadline instead of period, which reduces to RMS when deadlines equal periods. The 69% closed-form no longer applies; use response-time analysis, which every real-time textbook covers as the follow-on to Liu-Layland.
Is a 50-year-old paper really still current? Its assumptions get extended, multicore, shared caches, mixed criticality, but the core results are theorems, not benchmarks. Theorems don't go stale, which is why the paper still anchors the first lecture of every real-time systems course.
