Predictability

One of the things we want to be able to do for a real-time system is validate that the system satisfies the timing constraints. This is difficult if the response times of jobs can vary wildly and erratically as job parameters (such as execution time) vary continuously.

Nonpreemptive EDF Anomaly

The above example shows that shortening the execution time of one job (shown in yellow) can cause another job (shown in blue) to miss its deadline.

2-CPU Priority Scheduling Anomalies

The above example shows how varying the execution time of one job can affect completion times on a two-CPU system in which jobs are assigned dynamically to a processor, but cannot migrate to another processor once started. The jobs are prioritized in the order J1, J2, J3, J4.

• The first schedule shows the behavior with the longest possible execution time of J₂
• The second schedule shows the behavior with the shortest possible execution time of J₂
• The second schedule shows the behavior with an intermediate execution time of J₂
• The third schedule shows the schedule in which J₂'s execution time leads to the best overall performance.

Who would have guessed that?

Predictability

• execution times will vary
• scheduling anomalies complicate validation
• exhaustive simulation with all possible combinations of execution times is impractical
• we need to restrict the model and scheduling technique to guarantee there are no anomalies --
  i.e. that the system is predictable

Formal Definition of Predictability

The following definitions assume we are given a specific scheduling algorithm and set of jobs to schedule.

The maximal schedule is the one produced if all jobs take their maximimum possible execution times.

The minimal schedule is the one produced if all jobs take their minimum possible execution times.

Start Time Predictability

J_i is start-time predictable iff, for every possible actual start time s(J_i) of J_i,

where s⁺(J_i) is the start time of J_i according to the maximal schedule and

s^-(J_i) is the start time of J_i according to the minimal schedule.

Completion/Finish Time Predictability

J_i is completion-time predictable iff, for every possible actual completion time f(J_i) of J_i,

f⁺(J_i) is the completion time of J_i according to the maximal schedule and f^-(J_i) is the completion time of J_i according to the minimal schedule.

Generalizations of Predictability Definition

A job is predictable iff it is start-time and completion-time predictable.

A set of jobs is predictable iff all the jobs in the set are predictable.

Predictability Restrictions

Theorem: The execution of every job in a set of independent preemptible jobs with fixed release times is predictable when scheduled in a priority-driven manner on one processor.

Proof: The proof is by induction on the priority of the job,
relative to the other jobs in the set.

Clearly, the highest priority job J₁ is predictable.

• It always starts at its release time.
• It always completes by its actual execution time.

Assume all the i-1 highest priority jobs J₁ ¼J_i-1 are predictable, and suppose that J_i is not predictable. There are only four ways this can happen:

1. s(J_i) > s⁺(J_i)
2. s(J_i) < s^-(J_i)
3. f(J_i) > f⁺(J_i)
4. f(J_i) < f^-(J_i)

Each of these cases leads to a contradiction. For example, consider case (1).

No job is scheduled before its release time, so s⁺(J_i) > r_i.

For every higher priority job J_k with r_k≤s⁺(J_i), f⁺(J_k) ≤ s⁺(J_i), or else J_i could not start.

By the induction hypothesis, f(J_k) ≤ f⁺(J_k), so by transitivity of ≤, f(J_k) ≤ s⁺(J_i).

It follows that in the actual schedule either the processor is idle at time s⁺(J_i) or some lower priority job is executing. Neither of these could be true with priority scheduling, so we have a contradiction.

The other cases are similar.

Linux Scheduling

Take a look at the code of the versions of the Linux scheduler (sched.c) and the RT Linux scheduler rtl_sched.c accessible via the links in this sentence. What scheduling algorithm does each use? Do they match any of the algorithms discussed here? Are they predictable?

T. P. Baker ($Id$)