CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 2 min read

Rate-monotonic

In plain words: The task that repeats most often should be allowed to go first, since its next deadline is nearest. Rate-monotonic scheduling (RM) assigns a fixed priority to each task, higher for a shorter period (a higher rate). The task with the highest priority among the ready ones runs, and it preempts the running task.

Take two tasks, made up to show the idea. T1 needs 2 units every 5 units. T2 needs 4 units every 7 units. The total utilisation is 2 ÷ 5 + 4 ÷ 7 = 0.40 + 0.57 = 0.97. T1 has the shorter period, so it has the higher priority. A timeline over the first 14 units (1 stands for T1, 2 for T2):

time:   0 1 2 3 4 5 6 7 8 9 10 11 12 13
runs:   1 1 2 2 2 1 1 2 2 2  1  1  2  .

T2's first job is ready at 0 and must finish by 7. It gets units 2, 3 and 4, then T1's second job (ready at 5) preempts it for 5 and 6. T2 resumes at 7 and finishes at 8, so it misses its deadline of 7 by 1 unit.

A test, due to Liu and Layland (1973), says when RM is guaranteed to work. For n tasks, RM meets all deadlines if the total utilisation is at most n × (2^(1/n) − 1). For 2 tasks this is 0.828, for 3 tasks 0.780, and it tends to 0.693 as n grows. Our set has 0.97, above 0.828, so the test gives no guarantee, and the timeline shows the miss.

The test is only sufficient. A set above the bound may still work. Three tasks with (C, T) of (1, 4), (2, 6) and (3, 12) have a total utilisation of 0.25 + 0.33 + 0.25 = 0.83, above 0.78, and a timeline shows that all deadlines are met:

time:  0 1 2 3 4 5 6 7 8 9 10 11
runs:  1 2 2 3 1 3 2 2 1 3  .  .

Rate-monotonic scheduling

Rate-monotonic scheduling is a fixed-priority policy for periodic tasks in which the task with the shortest period has the highest priority and preempts any lower one; it is guaranteed to meet all deadlines when the total utilisation does not exceed n × (2^(1/n) − 1) for n tasks.

Example: for two tasks, the guaranteed limit is 0.828, so a set with a utilisation of 0.97 may fail, as T2 did above.

Check yourself: 1. Why does T1 have the higher priority? 2. What is the utilisation bound for 3 tasks? 3. Does a set above the bound always miss a deadline?