Library prosa.analysis.facts.model.overheads.sbf.fp

In this section, we define an SBF for the FP scheduling policy in the presence of overheads.
Consider any type of tasks...
  Context {Task : TaskType}.
  Context {FP : FP_policy Task}.
  Context `{MaxArrivals Task}.

... an arbitrary task set ts, ...
  Variable ts : seq Task.

... and bounds DB, CSB, and CRPDB on dispatch overhead, context-switch overhead, and preemption-related overhead, respectively.
  Variable DB CSB CRPDB : duration.

Consider a task tsk.
  Variable tsk : Task.

We define the blackout bound for FP in an interval of length Δ as the number of jobs with higher-or-equal priority (w.r.t. a given task tsk) that can arrive in Δ times two, plus one, multiplied by the sum of all overhead bounds.
The "+1" accounts for the fact that n arrivals can result in up to 1 + 2n segments without a schedule change, and thus up to 1 + 2n intervals wherein overhead duration is bounded by DB + CSB + CRPDB.
Under FP scheduling the set of tasks that needs to be considered is restricted: only jobs of tasks with higher-or-equal priority relative to tsk can cause schedule changes, which allows the blackout bound to be stated in terms of this subset of tasks.
First, we define the FP SBF as the interval length minus the FP blackout bound.
  #[local] Instance fp_ovh_sbf : SupplyBoundFunction :=
    fun ΔΔ - fp_blackout_bound Δ.

Next, we define the "slowed-down" version of the FP SBF as the interval length minus the slowed-down blackout bound. The slowdown ensures that the resulting SBF is monotone and unit-growth, which is necessary to obtain response-time bounds using aRSA. This slowed-down FP SBF is used internally in the analysis, while the unmodified FP SBF is used to state the top-level analysis result.
In the following section, we show that the SBF defined above is indeed a valid SBF.
We assume the classic (i.e., Liu & Layland) model of readiness without jitter or self-suspensions, wherein pending jobs are always ready.
  #[local] Existing Instance basic_ready_instance.

Consider any type of tasks ...
  Context {Task : TaskType}.
  Context `{MaxArrivals Task}.

... and any type of jobs associated with these tasks.
  Context {Job : JobType}.
  Context `{JobTask Job Task}.
  Context `{JobArrival Job}.
  Context `{JobCost Job}.
  Context `{JobPreemptable Job}.

Consider an FP-policy that indicates a higher-or-equal priority relation, and assume that this relation is reflexive and transitive.
Consider any valid arrival sequence...
... and any explicit-overhead uni-processor schedule without superfluous preemptions of this arrival sequence.
Assume that the schedule respects the FP policy.
Assume that the preemption model is valid.
We consider an arbitrary task set ts ...
  Variable ts : seq Task.

... and assume that all jobs stem from tasks in this task set.
We assume that max_arrivals is a family of valid arrival curves that constrains the arrival sequence arr_seq, i.e., for any task tsk in ts, max_arrival tsk is (1) an arrival bound of tsk, and ...
... (2) a monotone function that equals 0 for the empty interval delta = 0.
We assume that all jobs have positive cost. This restriction is not fundamental to the analysis, but rather an artifact of the current proof structure in the library.
  Hypothesis H_all_jobs_have_positive_cost :
     j,
      arrives_in arr_seq j
      job_cost_positive j.

Finally, we assume that the schedule respects a valid overhead resource model with dispatch overhead DB, context-switch overhead CSB, and preemption-related overhead CRPDB.
  Variable DB CSB CRPDB : duration.
  Hypothesis H_valid_overheads_model :
    overhead_resource_model sched DB CSB CRPDB.

We show that the slowed SBF is monotone.
  Lemma overheads_sbf_monotone :
     tsk,
      sbf_is_monotone (fp_ovh_sbf_slow ts DB CSB CRPDB tsk).

In addition, we note that fp_blackout_bound is monotone as well.
  Remark fp_blackout_bound_monotone :
     tsk,
      monotone leq (fp_blackout_bound ts DB CSB CRPDB tsk).

The slowed SBF is also a unit-supply SBF.
Lastly, we prove that the slowed SBF is valid.