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:

Which will be for example for . When the number of processes tends towards infinity this expression will tend towards:

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

Table of contents

1 Resource preemption, priority inheritance
2 Example
3 See Also

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

Process Period Execution time

P1 8 1

P2 5 2

P3 10 3

The utilization will be:

The teoretical limit for 3 processes will be:

Since the system is schedulable!