Priority Inversion in a Busy Interval

In this module, we reason about priority inversion that occurs during a busy interval due to non-preemptive sections.

Consider any type of tasks ...

... and any type of jobs associated with these tasks.

Consider any valid arrival sequence ...

... and any uniprocessor schedule of this arrival sequence.

Consider a JLFP policy that indicates a higher-or-equal priority relation, and assume that the relation is reflexive and transitive.

Consider a valid preemption model with known maximum non-preemptive segment lengths.

Further, allow for any work-bearing notion of job readiness.

We assume that the schedule is valid ...

... and that the schedule respects the scheduling policy at every preemption point.

Consider any job j of tsk with positive job cost.

Consider any busy interval prefix [t1, t2) of job j.

Lower Priority In Busy Intervals

First, we state some basic properties about a lower priority job executing in the busy interval of the job under consideration. From the definition of the busy interval it follows that a lower priority job can only be executing inside the busy interval as a result of priority inversion.

Consider a lower-priority job.

Consider an instant t within the busy window of the job such that jlp is scheduled at t.

First, we prove that no time from t1 up to the instant t can be a preemption point.

Then it follows that the job must have been continuously scheduled from t1 up to t.

Any lower-priority jobs that are scheduled inside the busy-interval prefix [t1,t2) must arrive before that interval.

Finally, we show that lower-priority jobs that are scheduled inside the busy-interval prefix [t1,t2) must also be scheduled before the interval.

In this section, we prove that priority inversion only occurs at the start of the busy window and occurs due to only one job.

Suppose job j incurs priority inversion at a time t_pi in its busy window.

First, we show that there is no preemption time in the interval [t1,t_pi].

Next, we show that the same job will be scheduled from the start of the busy interval to the priority inversion time t_pi.

Thus, priority inversion takes place from the start of the busy interval to the instant t_pi, i.e., priority inversion takes place continuously.

As a simple corollary to the lemmas proved in the previous section, we show that for any two jobs j1 and j2 that cause priority inversion to job j, it is the case that j1 = j2.

Consider a time instant ts1 in [t1, t2) ...

... and a lower-priority (w.r.t. job j) job j1 that is scheduled at time ts1.

Similarly, consider a time instant ts2 in [t1, t2) ...

... and a lower-priority job j2 that is scheduled at time ts2.

Then, j1 is equal to j2.

From the above lemmas, it follows that either job j incurs no priority inversion at all or certainly at time t1, i.e., the beginning of its busy interval.

Next, we use the above facts to establish bounds on the maximum priority inversion that can be incurred in a busy interval.

Priority Inversion due to Non-Preemptive Sections

First, we introduce the notion of the maximum length of a nonpreemptive segment among all lower priority jobs (w.r.t. a given job j) arrived so far.

Note that any bound on the max_lp_nonpreemptive_segment function is also be a bound on the maximum priority inversion (assuming there are no other mechanisms that could cause priority inversion). This bound may be different for different scheduler and/or task models. Thus, we don't define such a bound in this module.

First, assuming proper non-preemptive sections, ...

... we observe that the maximum non-preemptive segment length of any task that releases a job with lower priority (w.r.t. a given job j) and non-zero execution cost upper-bounds the maximum possible non-preemptive segment length of any lower-priority job.

Next, we prove that the function max_lp_nonpreemptive_segment indeed upper-bounds the priority inversion length.

In this section, we require the jobs to have valid bounded non-preemptive segments.

First, we prove that, if a job with higher-or-equal priority is scheduled at a quiet time t+1, then this is the first time when this job is scheduled.

Thus, there must be a preemption time in the interval t1, t1 + max_lp_nonpreemptive_segment j t1. That is, if a job with higher-or-equal priority is scheduled at time instant t1, then t1 is a preemption time. Otherwise, if a job with lower priority is scheduled at time t1, then this job also should be scheduled before the beginning of the busy interval. So, the next preemption time will be no more than max_lp_nonpreemptive_segment j t1 time units later. We proceed by doing a case analysis.

(1) Case when the schedule is idle at time t1.

Assume that the schedule is idle at time t1.

Then time instant t1 is a preemption time.

(2) Case when a job with higher-or-equal priority is scheduled at time t1.

Assume that a job jhp with higher-or-equal priority is scheduled at time t1.

Then time instant t1 is a preemption time.

The following argument requires a unit-service assumption.

(3) Case when a job with lower priority is scheduled at time t1.

Assume that a job jhp with lower priority is scheduled at time t1.

To prove the lemma in this case we need a few auxiliary facts about the first preemption point of job jlp.

Let's denote the progress of job jlp at time t1 as progr_t1.

Consider the first preemption point of job jlp after progr_t1.

For correctness, we also assume that fpt does not exceed the length of the maximum non-preemptive segment.

First we show that fpt is indeed the first preemption point after progr_t1.

Thanks to the fact that the scheduler respects the notion of preemption points we show that jlp is continuously scheduled in time interval [t1, t1 + fpt).

Thus, assuming an ideal-progress processor model, job jlp reaches its preemption point at time instant t1 + fpt, which implies that time instant t1 + fpt is a preemption time.

And since fpt ≤ max_lp_nonpreemptive_segment j t1, t1 ≤ t1 + fpt ≤ t1 + max_lp_nonpreemptive_segment j t1.

For the next step, we assume an ideal-progress processor.

Next, we combine the above facts to conclude the lemma.

As Case 3 depends on unit-service and ideal-progress assumptions, we require the same here.

By doing the case analysis, we show that indeed there is a preemption time in the time interval [t1, t1 + max_lp_nonpreemptive_segment j t1].

In this section we prove that if a preemption point ppt exists in a job's busy window, it suffers no priority inversion after ppt. Equivalently the cumulative_priority_inversion of the job in the busy window t1,t2 is bounded by the cumulative_priority_inversion of the job in the time window t1,[ppt]).

Consider the preemption point ppt.

We first establish the aforementioned result by showing that j cannot suffer priority inversion after the preemption time ppt ...

... and then lift this fact to cumulative priority inversion.