Rate Monotone Utilization Bound

These notes make use of mathematical symbols that may not be visible with the default settings on some versions of some browsers.

If a blank space appears to the left of any of the names in the table above, or the symbol looks strange, try changing the font settings on your browser or using a different browser.

We will be looking at a slightly different proof, and a slightly different way of stating the theorem than the one in Jane Liu's book. The result in the book is as follows:

L&L RM Utilization Bound (version in Jane Liu's book)

Note that

and

This means that any set of two periodic tasks can be scheduled by the RM algorithm, provided the total utilization is less than or equl to 0.82, and that any set of (any number of) tasks with total utilization less than or equal to 0.69 can also be scheduled.

Overview of Proofs

The proofs are all based on identifying a worst-case system of n tasks; that is, a set of tasks that is:

• critical, meaning that increasing the execution time or decreasing the period of any task in the set will make the system unschedulable, and such that
• the utilization of this task set is the minimum over all such critical systems of tasks

Both the original proof and the proof in Jane Liu's book first prove the theorem for the special case of task sets where p₁ < ... p_n ≤ 2p₁, and argue separately that this generalization can be removed.

Within that special case, of tasks whose periods differ by at most a factor of two, the first step is to apply the Critical Zone Theorem, to find the worst-case phasing of tasks.

The second step is to characterize the execution times e_i of this worst-case task set in terms of the periods p_i.

The third step is to find values of the periods p_i that minimize the utilization over all critical systems, using the methods of calculus. This results in a set of recurrence relations.

The final step is to solve this set of recurrences for the actual utilization of this worst-case task set.

Instead of following J. Liu's proof exactly, I will present my own version of the theorem and proof, which are a bit closer to the original L&L paper.

RM Utilization Bound Theorem

RM scheduling is feasible for a task set with execution times E=(e₁,...,e_m) and periods P=(p₁,...,p_m) if (but not only if)

U(P,E)=

m ∑ i=1

ei/pi ≤ m(21/m-1)

Period & Compute Time Assignments

Any system of tasks is characterized with respect to RM schedulability by a pair of vectors (P,E), where E = (e₁,...,e_m) is the task compute time assignment and P = (p₁,...,p_m) is the task period assignment.

A system of tasks (P,E) is feasible under RM scheduling if there are no missed deadlines, for all possible task phasings (start times).

A system of tasks (P,E) is infeasible under RM scheduling if there is at least one missed deadline, for some combination of task phasings.

We want to prove that the utilization of any infeasible systems of m (or fewer) tasks is greater than or equal to m(2^1/m-1), or, more precisely,

Here "glb" stands for "greatest lower bound", which is either the minimum value in the set (if the set has a minimum), or the greatest value that is less than every value in the set (if the set does not have a minimum).

To prove this bound, we look at the boundary between the feasible and and infeasible tasks systems. We call the task systems on this boundary critical.

Critical Task Sets

A task is critical in a feasible task system if its execution time e_i cannot be increased without causing the task system to become infeasible.

A system of tasks (P,E) is critical if it is feasible and every task in it is critical. That is, there is no execution time e_i that can be increased without causing an overflow for some task phasing.

A system of tasks (P,E) is barely critical if it is critical, but if any task were removed the system would no longer be critical. That is, if we removed any task there would be some other execution time e_i that could then be increased without making the task system infeasible.

Example: Critical but not Barely Critical

The figure above shows that system (P,E) = ((5,7,35),(2,3,6)) is critical. It is not barely critical, since the system ((5,7),(2,3)), consisting of the red and blue tasks alone, is still critical.

Barely Critical Systems Bound Utilization of Infeasible Systems

Lemma 1:

Proof:Let (P,E) be any infeasible task system with m tasks. Reduce the task execution times in E infinitesimally until the task set is feasible, working one task at a time and starting with the lowest priority (i.e., highest numbered) task. (If the execution time of the lowest priority task is reduced to zero and the system is still infeasible, remove the task entirely and continue reducing the execution time of the new lowest priority task.) This process can only reduce the total system utilization, and eventually results in a task set that is critical. The resulting system is barely critical, has m or fewer tasks, and differs only infinitesimally in utilization from an infeasible task system with the same number of tasks.

Conversely, given any barely critical task system of m tasks, we can increase the utilization infinitesimally and obtain an infeasible system with the same number of tasks.

It follows that there is no separation between the greatest lower bounds of the utilizations of the two sets.

Bringing Periods Close Together

Lemma 2:

Proof: Since the set on the right is a subset of the set on the left, it is clear that the glb of the set on the right is greater than or equal to the glb of the set on the left. Therefore, we only need to show that for any (P,E) in the set on the left that is not in the set on the right, there is some other (P',E') in the set on the right whose utilization is less than or equal to that of (P,E).

Suppose (P,E) is barely critical and p_i ≤ p_m/2 for some 1 ≤ i < m. Let K = ⌈ p_m/p_i ⌉. It follows that

Let (P',E') be like (P,E), except that p'_i = Kp_i and e'_m = e_m +(K-1)e_i.

Since Kp_i ≤ p_m,

That is, utilization is decreased or unchanged.

The time taken by task i in the critical zone of task m is reduced by (K-1)e_i, but the execution time of task m is increased by the same amount, so task m is still critical and so the task system (P',E') is still barely critical, and in addition we have p_i > p_m/2.

We can repeat the same transformation of periods and execution times until we have a barely critical system (P',E') such that p_i > p_m/2 for every 1 < i < m, whose utilization is no higher than that of (P,E).

We have shown that to find the greatest lower bound of the utilizations of all overloaded systems of m tasks we only need to look at the barely critical systems of m or fewer tasks, such that the ratio of any two task periods is less than two.

Worst Case Compute Times

Lemma 3: Among all the barely critical m-task systems such that p_m < 2p_i for all i < m, the minimum utilization is achieved when

and

Basic idea:

Any unmet demand after p_i+1 cannot contribute to missing the deadline of task i+1.

Proof by Induction

Induction Hypothesis H(n): If (P,E) minimizes utilization among the barely critical m-task systems such that p_m < 2p_i for all i < m, and n < m
then e_i = p_i+1-p_i for i=1,...,n.

Basis: H(0) is trivially true.

Induction Step: We assume the hypothesis H(j-1) is true for some j < m, and show H(j) must be true.

Consider the critical zones. The induction hypothesis means that the second job of each task i < j completes entirely in the interval [p_i,p_i+1].
Moreover, this means the intervals [0,p_j-p₁] and [p₁,p_j] are completely utilized by tasks 1,...,j-1.

We want to show e_j= p_j+1-p_j. We assume e_j ≠ p_j+1-p_j, and show that this leads to a contradiction.

Case 1: e_j > p_j+1-p_j

Suppose e_j=p_j+1-p_j+δ, where δ > 0; i.e., task j does not complete in the interval [p_j,p_j+1].

Let (P,E') be the same as (P,E) except the excess compute-time of e_j is moved e'_j+1. That is, e_j'=e_j-δ and e'_j+1=e_j+1+δ. Now, since p_j < p_j+1,

Thus U(P,E) > U(P,E').

We know that (P,E') is barely critical, since (P,E) is critical and e'_j+1 uses all the execution time relinquished by e'_j in the interval [0, p_m]. This contradicts our assumption that E minimizes U among the critical feasible compute-time assignments for P. Thus, Case 1 cannot hold.

Case 2: e_j < p_j+1-p_j

Suppose e_j < =p_j+1-p_j; i.e., task j does not fully utilize the interval [p_j,p_j+1].

By the induction hypothesis, the first j-1 tasks all complete their first execution by time p_j-1-p₁ and complete their second execution by time p_j-1.

By the hypothesis for this case, task j completes before times p_j-p_j-1 and p_j.

Since the second release of tasks j+1 and higher do not occur until after time p_j+1, only task m can execute in the δ-length interval between the completion of task j and time p_j+1.

We can create a new compute-time assignment E' by taking δ compute-time from task m and giving δ/2 to task j. Let e_j' = e_j+&delta/2;, and e'_m = e_m-δ.

Since p_j > p_m/2,

That is, the transformation from (P,E) to (P,E') decreased the system utilization.

since the time we added to the execution time of task j is exactly balanced by the time we took away from the execution of task m, the schedule is still at least critical.

We may have made the scheduling infeasible, since by increasing the execution time of task j by δ we cause the first executions of tasks j+1,..., m (all the lower priority tasks) to be delayed by δ. One of the tasks j+1,...,m-1 may now miss a deadline. If this happens, we can apply the technique of Lemma 1 to find a barely critical system (P'',E'') that has utilization less than (P,E').

This contradicts the assumption that (P,E) minimizes total utilization among the collection of all barely critical task sets, so Case 2 cannot hold.

This completes the proof of Lemma 3.

Summary

The effect of what we have shown so far is to eliminate the variables e₁,...e_m by expressing them in terms of p₁,...,p_m.

Lemma 3 tells us directly that e_i = p_i+1 - p_i, for i=1,...,m-1. This implies that each of tasks 1,...,m-1 must complete exactly two executions in the interval [0,p_m]. We also know that since E is critical, task m must fully utilize the remaining time in the interval [0,p_m]. It follows that

Outline of Rest of L&L Proof

• worst case for m is when

  ei = pi+1 - pi for i = 1,2,...,m-1

  em = pm - 2

  m-1 ∑ i=1

  (pi+1 - pi) = 2p1-pm

• compute partial derivatives of U
• show second partial derivatives are all positive
• solve system of recurrences for U'(P,E)=0

Relationship of E to P

and so

Taking Partial Derivatives w.r.t. p_i

for i=2... m-1

Existence Of Global Minimum

A unique global minimum exists, since all the partial derivatives are positive:

for i=2 ... m-1

Solving for the Minimum

Solving the Recurrences

Let x = p₁ and y=p₂, and observe the pattern of the recurrence:

Since p₂ = 2p₁²/p_m, we can obtain a formula for y in terms of x:

Computing the Utilization

Through further research, many of the restrictions of the original Liu & Layland analysis have been lifted. Indeed, these efforts have probably constituted the main stream of research in real time systems for the past decade or so.

Below, we list some of these extensions, which we will review briefly orally in class now. Most of these we will revisit, going into more more detail, during the next few weeks.

Lifting Restrictions (1)

1. Tasks are all periodic
   • background processing
   • periodic server (with or without priority exchange)
   • deferrable server
   • other servers (sporadic, constant bandwidth, etc.)
2. CPU is always available (no cycle-stealing, via interrupts, DMA)
   • model cycle-stealing as tasks (periodic or deferred server)
   • model cycle-stealing as reduced CPU capacity (IPS)
3. Preemption has no cost
   • at most one preemption per request,
     so add it into execution time of preempting task
4. Preemption can be done at any time (no critical sections)
   • bound length of critical sections, adjust analysis
   • priority inheritance
   • priority-ceiling, and other bounded-blocking protocols
5. Deadline = period
   • schedule by relative deadline (if deadline shorter than period)
   • use buffers (if deadline longer than period) -- if U ≤ 1
6. Frequency = importance
   • period transformation (i.e. time-slicing)
7. Execution times are constant (harder problem)
   • reserve CPU capacity
   • allow for some failures (use time-slicing for core), e.g., various aperiodic server models
8. Tasks are independent (harder problem)
   • merge dependent tasks with same period, run on one processor
   • deadline propagation, for I/O tasks
   • use buffers, and separate tasks by a full cycle
9. There is only one processor (hardest?).
• schedule each processor separately
• new results on MP EDF & RM schedulability

For most of the above techniques we will not have time to go through the analysis at the level of detail we have just completed for the basic EDF and RM schedulability results. Instead, we will describe the technique, give an informal argument for why it works, and discuss how it can be applied.

Several of these techniques will come up in a case study, in which the rate-monotonic analysis technique is applied to a small but realistic problem.