Q18Real Time Systems

Question

Explain in detail the Rate Monotonic Scheduling (RMS) algorithm. Discuss its schedulability bounds and provide an example to illustrate its operation.

Answer 1

RMS is the absolute foundational algorithm of Real-Time Systems. Invented by Liu and Layland in 1973, it is a Static, Preemptive, Priority-Driven scheduling algorithm mathematically engineered exclusively for independent, periodic tasks. The architectural genius of RMS lies in its extreme simplicity and its mathematically provable optimality for static priorities.

The OS does not dynamically guess priorities. Priorities are hardcoded offline using a single, rigid mathematical physics rule: The shorter the period ( $T_{i}$ ), the higher the absolute priority.

If Task A runs every 10ms, and Task B runs every 50ms, Task A is mathematically assigned the higher priority.
Because Priority $\propto \frac{1}{T _{i}}$ (which is the execution Rate), the algorithm is named "Rate Monotonic".

How does an engineer mathematically guarantee that a nuclear reactor won't miss a deadline before turning it on? They use the RMS Utilization Bound.

First, calculate the actual Total CPU Utilization: $U = \sum_{i = 1}^{n} \frac{C _{i}}{T _{i}}$
Then, calculate the strict mathematical RMS Bound based on the number of tasks ( $n$ ): $U_{b o u n d} = n (2^{1/ n} - 1)$

The Law: If $U \leq U_{b o u n d}$ , all $n$ tasks are mathematically guaranteed to meet all deadlines.

For $n = 1$ , $U_{b o u n d} = 1.00$ (100%)
For $n = 2$ , $U_{b o u n d} = 0.828$ (82.8%)
For $n \to \infty$ , $U_{b o u n d} = ln (2) \approx 0.693$ (69.3%)

This means that if you keep your CPU utilization below 69.3%, you can throw an infinite number of independent tasks at RMS, and it will mathematically NEVER miss a deadline. This provides a catastrophic safety margin for engineers.

Consider two tasks: - Task 1: $C_{1} = 20, T_{1} = 50$ (High Priority) - Task 2: $C_{2} = 35, T_{2} = 100$ (Low Priority)

Step 1 (Schedulability Test): $U = (20/50) + (35/100) = 0.4 + 0.35 = 0.75$ . The bound for $n = 2$ is $0.828$ . Since $0.75 < 0.828$ , the system is mathematically guaranteed to work.
Step 2 (Execution at $t = 0$ ): Both tasks release. Task 1 has higher priority. Task 1 executes from $t = 0$ to $t = 20$ .
Step 3 ( $t = 20$ ): Task 1 finishes. Task 2 violently takes the CPU and begins executing.
Step 4 ( $t = 50$ ): Task 1 hits its next period and releases again. The OS violently preempts Task 2 (which has executed 30 out of its 35 units). Task 1 runs from $t = 50$ to $t = 70$ .
Step 5 ( $t = 70$ ): Task 1 finishes. Task 2 resumes and executes its final 5 units, finishing at $t = 75$ , well before its $t = 100$ deadline.

Q18Real Time Systems

Question

Answer