rate-monotonic scheduling (RMS)

Imagine you have several recurring chores, each repeating on its own clock: check the smoke alarm every minute, water the plant every hour, take out the trash every week. A sensible rule of thumb is to give the most frequent chore the highest priority, because it has the least slack before it must repeat. Rate-monotonic scheduling is exactly that rule, made precise for a processor running periodic tasks: assign each task a fixed priority based on how OFTEN it runs — the shorter the period (the higher the rate), the higher the priority.

Set the scene precisely. You have a set of periodic tasks; task i runs every Ti time units (its period) and needs at most Ci units of CPU each time (its worst-case execution time), and it must finish before its next release (deadline = period). RMS assigns priorities by rate: the task with the smallest period gets the highest priority, and these priorities are FIXED (static) — they never change at run time. The scheduler is preemptive and always runs the ready task with the highest priority. The beautiful result, proven by Liu and Layland in 1973, is that this fixed-priority assignment is OPTIMAL among all fixed-priority schemes (if any fixed-priority assignment can meet all deadlines, the rate-monotonic one can too), and there is a simple sufficient test: if the total CPU utilization, the sum of Ci/Ti over all tasks, is at most n*(2^(1/n) - 1) for n tasks, all deadlines are guaranteed. That bound starts at 1.0 for one task and decreases toward about 0.693 (ln 2) as n grows large.

It matters because it gives embedded designers a simple, analyzable, low-overhead recipe for guaranteeing that a set of periodic real-time tasks all meet their deadlines, with priorities you can compute on paper. The honest caveats: the classic utilization bound assumes tasks are independent, periodic, with deadline equal to period, with no blocking and instant preemption — real systems violate these (shared resources, jitter, interrupt overhead), so engineers use a more exact response-time analysis when utilization is above the bound. The bound is SUFFICIENT but not necessary: utilization above 0.693 does NOT mean deadlines will be missed, it just means the quick test no longer proves safety and you need the finer analysis. And RMS leaves up to about 31% of the CPU unusable in the worst guaranteed case — earliest-deadline-first can reach 100% but with dynamic priorities.