Library prosa.results.periodic.simulation.schedulability

Schedulability Test for Periodic Tasks

In this module, we turn the simulation result into a proper schedulability test (i.e., an executable procedure) for fully preemptive scheduling on an ideal uniprocessor. The caller must supply a task set, a periodic arrival sequence, and a scheduling policy. Prosa's reference scheduler builds a schedule of the jobs in the given arrival sequence with their tasks' full WCETs. The test procedure then checks the deadlines of all jobs arriving up to and including the simulation horizon.

Checking Procedure

We begin by defining the schedulability testing procedure.
Section PeriodicChecker.

Consider periodic tasks with offsets, WCETs, and relative deadlines, ...
  Context {Task : TaskType} `{TaskOffset Task} `{PeriodicModel Task}
          `{TaskCost Task} `{TaskDeadline Task}.

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

... and a given JLFP scheduling policy.
  Context (policy : JLFP_policy Job).

Let ts be the task set to check, with arrivals supplied by arr_seq.
  Variable ts : TaskSet Task.
  Variable arr_seq : arrival_sequence Job.

For the reference schedule, assume each job executes for its task's full WCET.
  #[local] Instance wcet_job_cost : JobCost Job :=
    { job_cost j := task_cost (job_task j) }.

We construct a fully preemptive schedule for the basic readiness model, as required by the periodic simulation theorem.
  #[local] Instance reference_job_ready :
    JobReady Job (ideal.processor_state Job) :=
    basic_ready_instance.
  #[local] Existing Instance fully_preemptive_job_model.

We obtain the WCET schedule from uni_schedule, Prosa's reference uniprocessor scheduler implementation.
We must check every job released through the inclusive arrival cutoff.
The actual checking procedure: first make sure all tasks have valid periods and that the processor is not permanently overloaded, and then check the deadlines of all jobs arriving up to and including the simulation horizon.
We next note the properties that the checking procedure establishes.
If the checker returns true, then the periods are reasonable, ...
... the workload does not permanently overload the processor, and ...
... all jobs arriving up to and including the simulation horizon meet their deadlines.

Schedulability Guarantee

With the checker in hand, we now certify the schedulability of a periodic workload with variable job costs.
Section Schedulability.

Consider periodic tasks and their jobs, as above.
  Context {Task : TaskType} `{TaskOffset Task} `{PeriodicModel Task}
          `{TaskCost Task} `{TaskDeadline Task}.
  Context {Job : JobType} `{JobTask Job Task} `{JobArrival Job}.

Let ts and arr_seq describe the workload to be certified, ...
... under a given total, transitive, and antisymmetric JLFP scheduling policy whose relative job priorities are consistent across hyperperiods.
Consider the task set's infinite periodic arrival sequence.
Allow jobs to exhibit variable execution costs, up to their WCETs.
Consider any given valid, work-conserving, fully preemptive schedule of these jobs under a basic readiness model (i.e., without self-suspensions or release jitter).
Under these assumptions, the extended simulation result for variable job costs jlfp_finite_deadline_check_with_variable_costs applies if the checking procedure returns true.
Finally, we obtain the desired schedulability guarantee by restating the previous theorem at the level of tasks.