Schedulability tests based on utilization

RM Scheduling

Schedulability tests for RM based on task utilization.

• Valid with preemption, n independent tasks, D=T.

• Liu&Layland’s (1973), Least Upper Bound (LUB).

  • => One execution per period guaranteed.

• Bini&Buttazzo&Buttazzo’s (2001), Hyperbolic Bound.

  • => One execution per period guaranteed.

Interpretation of the Liu&Layland test

=> task set not schedulable (overload) – necessary condition.

=> task set is schedulable – sufficient condition.

=> the test is indeterminate.

Some values

Example 1

Task properties.

• 
• one execution per period is guaranteed.

Example 2

Task properties.

• 
• one execution per period is NOT guaranteed.
• But the task set is schedulable (see Gantt chart).

Example 3

Task set properties.

• 
• one execution per period is NOT guaranteed.
• And the task set indeed is not schedulable (see Gantt chart).

Harmonic Periods

Particular case: if the task periods are harmonic then the task set is schedulable iif U(n) ≤ 1.

• E.g. Γ = {(1, 2); (2, 4)}