Bound for a Busy-Interval Starting with Priority Inversion under EDF Scheduling

In this file, we define a bound on the length of a busy interval that starts with priority inversion (w.r.t. a job of a given task under analysis) under the EDF scheduling policy.

Consider any type of tasks.

Consider an arrival curve max_arrivals.

For brevity, let's denote the relative deadline of a task as D.

Consider an arbitrary task set ts ...

... and let tsk be any task to be analyzed.

Assume that there is a job j of task tsk and that job j's busy interval starts with priority inversion. Then, the busy interval can be bounded by a constant longest_busy_interval_with_pi. Intuitively, such a bound holds because of the following two observations. (1) The presence of priority inversion implies an upper bound on the job arrival offset A < D tsk_o - D tsk, where A is the time elapsed between the arrival of j and the beginning of the corresponding busy interval. (2) An upper bound on the offset implies an upper bound on the higher-or-equal-priority workload of each task.

Let lp_interference tsk_lp denote the maximum service inversion caused by task tsk_lp.

Let hep_interference tsk_lp denote the maximum higher-or-equal priority workload released within D tsk_lp.

Then, the amount of interfering workload incurred by a job of task tsk is bounded by maximum of lp_interference tsk_lp + hep_interference tsk_lp, where tsk_lp is such that D tsk_lp > D tsk.