Analysis of Single-Processor EDF Schedulability

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.

This analysis is based on the following assumptions:

• all tasks are periodic
• all tasks are independent
• relative deadline ≤ period (* only used at one point in the proof)
• scheduling policy is preemptive EDF
  i.e., jobs with earlier deadline have higher priority
  • priority is static w.r.t. jobs
  • but dynamic w.r.t. tasks
  • we already have shown EDF is optimal

EDF Scheduling - Basic Result

C.L. Liu and J. W. Layland, ``Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment'', JACM 20.1 (January 1973) 46-61.

EDF Scheduling - Density Test for Preperiod Deadlines

Theorem: A set of n (periodic and aperiodic) tasks is schedulable by EDF scheduling if

Note that this test is only a sufficient condition for schedulabliity, while the test for the case that deadline=period is both necessary and sufficient.

The ratio &lambda_i is sometimes called the density of task τ _i.

The proof below is from T.P. Baker, ``Stack-Based Scheduling of Real-Time Processes'', in Advances in Real-Time Systems, IEEE Computer Society Press (1993) 64-96; reprinted from The Real-Time Systems Journal 3,1 (March 1991) 67-100, and only covers the case where d_i≤p_i.

J. Liu's book has a proof of the full result, that allows periods beyond the deadline. Most of the proof here applies for arbitrary deadlines. There is one more step to extend it to arbitrary deadlines, which we may discuss in class.

Proof of EDF WC Utilization/Density Bound

Plan: Assume the theorem is false; show that this leads to a contradiction.

Focus on a period preceding the first time that a job misses its deadline.

Let t be the first time a job misses its deadline. Let t′ be the last time before t such that there are no pending job execution requests with arrival times before t′ and deadlines before or at t. Since no requests can arrive before system start time, t′ is well defined. Since deadlines are all positive, t′ < t. By choice of t and t′, there is no idle time in [t′, t).

We call this the maximal busy interval ending at t because it is the longest interval ending at t that satisfies the following criteria:

• there is no time during the interval when the CPU is idle
• the only jobs that execute in the interval have deadlines in the interval (excluding the start point and including the endpoint)
• the only jobs that execute in the interval have release times in the interval (including the start point and excluding the endpoint)

Let A be the set of jobs that arrive in [t′, t) and have deadlines in [t′, t). By choice of t′, there are pending requests of jobs in A at all times during the interval [t′,t). Thus, by the EDF priority assignment, the only jobs that will be allowed to start in [t′, t) will be in A. These jobs can only be preempted by other jobs in A.

Let Δ = t - t′, that is, the length of the interval [t′,t). By choice of t′, d_i ≤ Δ, for every J_i in A. We have the situation shown in the figure below.

For the set of all jobs of τ_i in A, the total demand for CPU time in [t′, t) is not more than ke_i, where

In [t′, t) there is no idle time and the only jobs executing are those in A. Since there is an overflow, the total demand for processor time in [t′, t) exceeds Δ, so

Since ⌊X ⌋ ≤ X

We have

Since d_i ≤ Δ for i = 1,...,k

This last step is the only place in the proof where we rely on that deadline is less than or equal to period. Can you see how to work the algebra?

Tightness/Untightness of Bound

It is obvious that the above result is tight when relative deadlines are equal to periods, since then scheduling only fails when utilization exceeds 100%.

However, if deadline can be less than period the result is not ``only if''. For example, consider the following two tasks:

i   ei   di   pi  1 9 10 10 2 1 1 10

These tasks clearly fail the density test:

However, it can be seen that there can never be a missed deadline. Task τ₂ will always be able to preempt task τ₁, except when their deadlines coincide. When their deadlines do coincide, task τ ₁ will already have completed by the time τ₂ is released.

Note that there are at least two places in the proof where accuracy the estimation of demand in the busy interval is thrown away. One place is where the floor function is eliminated. Another is where Δ is replaced by d_i.

Can the theorem can be refined to give a tighter bound?

Sample Application - Liu's Robot Controller

• control-law computation: e_c ≤ 8ms, d_c = 10ms
• Built-In-Self-Test: e_b ≤ 50ms, d_b ≤ 1000ms
• telemetry: e_t ≤ 15ms, d_t a.s.a.p

Strengths of the Schedulability Test

Recall that single-processor preemptive scheduling of independent jobs has been proven to be predictable.

It follows that if we use worst-case execution times and the utilization/density test above we can rely that the task set will still be schedulable if the tasks take less time to execute. Thus, the test is robust w.r.t. execution times.

We did not make any assumptions about first release times (phasing) in the proof, so the result is robust in that sense.

The periods here are only lower bounds (minimum separation of release times), so the result applies to aperiodics as well as periodics, and is robust w.r.t. minor variations in period.

(In)stability under Overload

• "stability" under overload = if some tasks exceed their predicted worst-case execution times, causing deadlines to be missed, we can predict which tasks will be affected first
• EDF is unstable under overload conditions
• tasks that have missed deadline continue to receive highest priority
• one way to deal with this is to design to ensure there is no overload
• others include various load-shedding
  • cancel some tasks
    e.g. those with missed deadlines or low criticality
  • lower priority of tasks that have missed deadlines
• if the overload is short-term, this may not be as bad as it seems, since tasks are still completed in deadline order

It would be nice to have pictures of some examples here, showing what happens during overload.

Generalizations

• Deadline greater than period
  • replace d_i by min(d_i, p_i)
    does the proof still apply
  • Why would a person want to specify a deadline greater than the task period?
  • Why would a person want to specify a deadline less than the task period?
• multiprocessors
  • partition and then apply single-processor rule
  • consider global (single-queue) scheduling
  • what are the trade-offs?
  • how far can the above analysis be applied to the global case?

Using the Exact Demand/Load Bound

Recall that we started with the following formula for the maximum processor demand due to a task Δ in an interval of length Δ.

Consider the following pair of tasks.

demand(τ₁), and its linear upper and lower approximations

The upper diagonal line represents the approximation to the floor function used in the proof above. See how much accuracy is lost.

demand(τ₂), and its linear upper and lower approximations

demand(τ₁), demand(τ₂), and their sum

The total demand, and the sums of the upper and lower bounds. See how much more accuracy is lost, when we take the sum.

loadτ₁), and its hyperbolic upper and lower approximations

loadτ₂), and its hyperbolic upper and lower approximations

the total load, and the sums of the upper and lower bounds

the total load, and the sums of the upper and lower bounds

Later in the term we will study how to find global and local maxima of the demand and load functions. This will give us a way to test schedulability more precisely than with the utilzation and density tests.

Consider the following graph

© 1998, 2003, 2006 T. P. Baker. ($Id: edfproof.html,v 1.2 2008/08/25 11:18:48 baker Exp baker $)