How Does Rate-Monotonic Scheduling Assign Priorities?

Rate-Monotonic Scheduling is a classic real-time scheduling algorithm that assigns fixed priorities to periodic tasks based on their execution periods. Tasks with shorter periods receive higher priorities, ensuring that more frequent operations get immediate access to the processor. Introduced by Liu and Layland in 1973, this approach provides mathematical guarantees for task schedulability through provable CPU utilization bounds.

Static Priority Assignment by Periodicity

In a classical real-time system, each periodic task \(\tau_i\) is characterized by its worst-case execution time \(C_i\) and its period \(T_i\), which also serves as its relative deadline \(D_i = T_i\). Rate-Monotonic Scheduling (RMS) is a static-priority, preemptive algorithm. Once priorities are assigned before execution begins, they do not change at runtime.

The priority assignment rule is straightforward: priority is inversely proportional to the task period. A task with a smaller period \(T_i\) has a higher request rate \(1/T_i\), and therefore receives a higher priority. Whenever a higher-priority task becomes ready to run, it immediately preempts any currently executing lower-priority task.

Assumptions of the Classical Model

The provable guarantees of RMS rely on a specific set of classical computing assumptions:

• All tasks are strictly periodic with constant periods.
• Relative deadlines equal the respective periods (\(D_i = T_i\)).
• Tasks are independent, meaning they do not share resources or block each other.
• Context-switching overhead and scheduling overhead are negligible.
• Execution times are bounded by known worst-case values \(C_i\).

Provable CPU Utilization Bounds

The total CPU utilization \(U\) of a set of \(n\) periodic tasks is defined as the sum of the ratios of each task's execution time to its period:

\[U = \sum_{i=1}^{n} \frac{C_i}{T_i}\]

Liu and Layland proved that a set of \(n\) independent periodic tasks is guaranteed to be schedulable under RMS if the total CPU utilization satisfies the following sufficient condition:

\[U \le n\left(2^{1/n} - 1\right)\]

For a single task (\(n = 1\)), the bound is \(1.0\) (100% utilization). For two tasks (\(n = 2\)), the bound drops to approximately \(0.828\). As the number of tasks approaches infinity, the utilization bound converges to:

\[\lim_{n \to \infty} n\left(2^{1/n} - 1\right) = \ln 2 \approx 0.693\]

This means any set of independent periodic tasks whose combined utilization is at or below \(69.3\%\) is guaranteed to meet all deadlines under Rate-Monotonic Scheduling, regardless of the specific task periods.

Beyond the Utilization Bound

The Liu and Layland bound is a sufficient condition, not a necessary one. Task sets with total utilization above \(n(2^{1/n} - 1)\) can still be schedulable depending on the relationship between their periods. In particular, if all task periods are harmonic—meaning every period is an integer multiple of shorter periods—the schedulable utilization bound reaches \(100\%\) (\(U \le 1.0\)).

When utilization exceeds the Liu and Layland bound and periods are not harmonic, exact schedulability can be verified using Response Time Analysis (RTA). RTA computes the worst-case response time \(R_i\) for each task by summing its own execution time and the interference from all higher-priority tasks:

\[R_i = C_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i}{T_j} \right\rceil C_j\]

If \(R_i \le T_i\) holds for every task \(\tau_i\), the task set is guaranteed to be schedulable.