Library prosa.analysis.facts.busy_interval.ideal.inequalities

In this file, we prove some inequalities that always hold inside the busy interval of a job. Throughout this file we assume the ideal uniprocessor model.
Consider any kind of tasks and their jobs, each characterized by an arrival time, a cost, and an arbitrary notion of readiness.
  Context {Task : TaskType} {Job : JobType} `{JobTask Job Task}.
  Context `{JobArrival Job} `{JobCost Job} {JR :JobReady Job (ideal.processor_state Job)}.

Consider a JLFP policy that is reflexive and respects sequential tasks.
Consider a consistent arrival sequence that does not contain duplicates.
Consider any valid ideal uniprocessor schedule defined over this arrival sequence.
Consider a set of tasks ts that contains all the jobs in the arrival sequence.
  Variable ts : list Task.
  Hypothesis H_all_jobs_from_taskset : all_jobs_from_taskset arr_seq ts.

Consider a task tsk.
  Variable tsk : Task.

Consider a job j of the task tsk that has a positive job cost.
  Variable j : Job.
  Hypothesis H_j_arrives : arrives_in arr_seq j.
  Hypothesis H_job_of_tsk : job_of_task tsk j.
  Hypothesis H_job_cost_positive: job_cost_positive j.

Consider the ideal JLFP definitions of interference and interfering workload.
Consider the busy interval for j is given by [t1,t2).
Let us denote the relative arrival time by A.
  Let A := job_arrival j - t1.

Consider any arbitrary time Δ inside the busy interval.
  Variable Δ: duration.
  Hypothesis H_Δ_in_busy : t1 + Δ < t2.

First, we prove that if the priority inversion is bounded then, the cumulative priority inversion is also bounded.
  Section PIBound.

Consider the priority inversion in any given interval is bounded by a constant.
Then, the cumulative priority inversion in any interval is also bounded.
Let jobs denote the arrivals in the interval Δ.
Next, we prove that the cumulative interference from higher priority jobs of other tasks in an interval is bounded by the total service received by the higher priority jobs of those tasks.
Consider a valid arrival curve that is followed by the task set ts.
Suppose all arrivals have WCET-compliant job costs.
Consider a task tsk_o that is not equal to tsk.
    Variable tsk_o : Task.
    Hypothesis H_tsko_in_ts: tsk_o \in ts.
    Hypothesis H_neq: tsk_o != tsk.

We prove that the workload of higher priority jobs of a task tsk in any interval is bound by the request bound function of the task in that interval.