Rate-monotonic scheduling

• 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:

<math>U = m(2^\frac{1}{m} - 1)</math>

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

<math>\lim_{m \rightarrow \infty} m(2^\frac{1}{m} -1) = \ln 2 \approx 0.693147\ldots</math>

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

Resource preemption, priority inheritance

In many practical applications, resources are shared and the unmodified RMS will be subject to priority inversion[?] and deadlock hazards. In practice, this is mostly solved by introducing priority inheritance.

The principle of priority inheritance is that a shared resource will be tied to the accessing processes, and if one process with a lower priority than the currently running process holds this resource, and the currently running process needs it, the current process will be preempted[?], and the process holding the resource will be raised to the priority of the currently running process until it releases the resource, and at that time it will be preempted and assigned it's previously held priority.

Example

The utilization will be:

<math>\frac{1}{8} + \frac{2}{5} + \frac{2}{10} = 0.725</math>

The teoretical limit for 3 processes will be:

<math>U = 3(2^\frac{1}{3} - 1) = 0.77976\ldots</math>

Since <math>0.725 < 0.77976...</math> the system is schedulable!

See Also

• Scheduling
• Earliest deadline first scheduling