Library prosa.results.periodic.simulation.variable_costs

Simulation Certificates for Variable Job Costs

In this module, we combine the simulation theorem in prosa.results.periodic.simulation.interval, which applies when each job executes for its task's worst-case execution time (WCET), with the job-cost sustainability argument in prosa.analysis.facts.sustainability.cost to extend the schedulability guarantee obtained via simulation to schedules in which job costs are variable (i.e., not fixed to the WCET).

Workload and Supplied Schedules

Let us begin with the system model. The two schedules share tasks, job arrivals, and deadlines, but the execution costs and readiness models differ.
Consider periodic tasks with offsets, WCETs, and relative deadlines, ...
  Context {Task : TaskType} `{TaskOffset Task} `{PeriodicModel Task}
          `{TaskCost Task} `{TaskDeadline Task}.

... and their jobs.
  Context {Job : JobType} `{JobTask Job Task} `{JobArrival Job}.

Let ts be the task set whose guarantees we want to establish, and let arr_seq describe its arrivals. The two schedules share this workload.
Jobs arrive periodically starting at their tasks' offsets.
Now consider a reference WCET schedule and a schedule with variable job costs on an ideal uniprocessor ...
... and the corresponding job-cost parameters.
For convenience, we name the two cost functions as follows.
Each reference job executes for its task's full WCET.
  Hypothesis H_fixed_reference_costs :
    ∀ j,
      arrives_in arr_seq j →
      reference_job_cost j = task_cost (job_task j).

In the second schedule, job costs may vary freely (up to the WCET).
  Hypothesis H_variable_costs_bounded :
    ∀ j,
      arrives_in arr_seq j →
      variable_job_cost j ≤ task_cost (job_task j).

Readiness depends on whether a job has completed, so we supply a readiness model using each schedule's execution costs.
The simulation theorem is specific to basic job readiness.
Both schedules must be valid under their respective cost and readiness models.
Both schedules must be work-conserving, but for different reasons. Work conservation in the reference schedule supports the finite simulation bound. In the schedule with variable job costs, it supports the service comparison that carries the deadline guarantees across.
For the simulation result to hold, the system must not be overloaded.

Deadline Transfer

Let both schedules follow the same JLFP order, including tie-breaking.
The priority order needs to satisfy two properties for the combined argument: antisymmetry for cost sustainability and hyperperiod consistency for the finite simulation theorem.
The simulation theorem starts from a finite deadline check in the reference schedule.
Our conclusion concerns all deadlines in the schedule with variable job costs.
With all definitions in place, we can now connect the two arguments. The finite-check theorem first establishes that every deadline in the WCET reference schedule is met. Basic readiness supplies the job-readiness agreement needed by cost sustainability, which then carries those guarantees to the schedule with variable job costs.