Rate Monotonic Scheduling

Rate-monotonic scheduling (RMS) is a fixed-priority scheduling algorithm for periodic real-time tasks in which tasks with shorter periods are assigned higher priorities. The algorithm was proved optimal by Liu and Layland in 1973: among all fixed-priority assignments, rate-monotonic scheduling yields the highest processor utilization bound while still guaranteeing that all deadlines are met. The utilization bound for n tasks is n(2^(1/n) − 1), which approaches ln 2 ≈ 0.693 as n grows — meaning rate-monotonic scheduling can guarantee schedulability for task sets using up to approximately 69% of processor capacity.

The significance of the Liu-Layland result is not merely algorithmic. It is epistemological: it proved that real-time scheduling admits provable optimality guarantees, and that these guarantees can be computed without simulating every possible execution trace. The result underlies the design of real-time operating systems and is the foundation upon which more sophisticated scheduling algorithms — including earliest-deadline-first and priority inheritance protocols — are built. Rate-monotonic scheduling is not the best algorithm for all real-time systems, but it is the algorithm that proved the field was a science rather than a craft.