Rate-monotonic scheduling

Rate-monotonic scheduling is a scheduling principle employed in real-time operating systems. The basic principle is that if all processes (tasks, threads) to be scheduled has:

• Strict deadlines
• No data dependencies (process x does not transmit data to process y which y are in turn dependent of)
• No resource sharing (processes x and y will not try to use the same resource, e.g. a hardware resource)
• Deterministic periodicity
• Statically scheduled (priorities does not change during execution)

And the swithcing of tasks takes no (zero) time, then by assigning the process with the shortest period (highest frequency) the highest priority, the task with the next shortest period the next highest priority and so on, then all processes can be proven to meet their deadlines. The CPU utilization can be proven to be:

$U=m(2^{\frac {1}{m}}-1)$

Which will be for example $0.8284$ for $m=2$. When the number of processes tends towards infinity this expression will tend towards:

$\lim _{m\rightarrow \infty }m(2^{\frac {1}{m}}-1)=\ln 2\approx 0.693147\ldots$

So a rough estimate is that RMS in the general case only utilize $69\%$ of the CPU. Thus, no more than this amount of the CPU shall be allocated to processes, or the system may fail.

Example

Process	Period	Execution time
P1	8	1
P2	5	2
P3	10	3

The utilization will be:

${\frac {1}{8}}+{\frac {2}{5}}+{\frac {2}{10}}=0.725$

The teoretical limit for 3 processes will be:

$U=3(2^{\frac {1}{3}}-1)=0.77976\ldots$

Since $0.725<0.77976...$ the system is schedulable!

See Also

• Scheduling
• Earliest deadline first scheduling