Library rt.analysis.uni.susp.dynamic.oblivious.fp_rta

Require Import rt.util.all.
Require Import rt.model.arrival.basic.job rt.model.arrival.basic.task rt.model.arrival.basic.arrival_sequence
               rt.model.priority rt.model.suspension rt.model.arrival.basic.task_arrival.
Require Import rt.model.schedule.uni.schedule rt.model.schedule.uni.schedulability.
Require Import rt.model.schedule.uni.susp.suspension_intervals
               rt.model.schedule.uni.susp.schedule rt.model.schedule.uni.susp.platform.
Require Import rt.analysis.uni.basic.fp_rta_comp.
Require Import rt.analysis.uni.susp.dynamic.oblivious.reduction.

Module SuspensionObliviousFP.

  Import Job TaskArrival SporadicTaskset Suspension Priority Schedulability
         PlatformWithSuspensions SuspensionIntervals.
  Export ResponseTimeIterationFP ReductionToBasicSchedule.

  (* In this section, we formalize the suspension-oblivious RTA
     for fixed-priority tasks under the dynamic self-suspension model.
     This is just a straightforward application of the reduction
     in analysis/uni/susp/dynamic/oblivious/reduction.v with the basic
     response-time analysis for uniprocessor FP scheduling. *)

  Section ReductionToBasicAnalysis.

    Context {SporadicTask: eqType}.
    Variable task_cost: SporadicTask time.
    Variable task_period: SporadicTask time.
    Variable task_deadline: SporadicTask time.

    Context {Job: eqType}.
    Variable job_arrival: Job time.
    Variable job_cost: Job time.
    Variable job_deadline: Job time.
    Variable job_task: Job SporadicTask.

    (* Let ts be any task set to be analyzed... *)
    Variable ts: taskset_of SporadicTask.

    (* ...such that tasks have valid parameters. *)
    Hypothesis H_valid_task_parameters:
      valid_sporadic_taskset task_cost task_period task_deadline ts.

    (* Next, consider any job arrival sequence with consistent, duplicate-free arrivals,... *)
    Variable arr_seq: arrival_sequence Job.
    Hypothesis H_arrival_times_are_consistent: arrival_times_are_consistent job_arrival arr_seq.
    Hypothesis H_arrival_sequence_is_a_set: arrival_sequence_is_a_set arr_seq.

    (* which all jobs come from task set ts, ... *)
    Hypothesis H_jobs_from_taskset:
       j, arrives_in arr_seq j job_task j \in ts.

    (* ...have valid parameters,...*)
    Hypothesis H_valid_job_parameters:
        arrives_in arr_seq j
        valid_sporadic_job task_cost task_deadline job_cost job_deadline job_task j.

    (* ... and satisfy the sporadic task model. *)
    Hypothesis H_sporadic_tasks:
      sporadic_task_model task_period job_arrival job_task arr_seq.

    (* Consider any FP policy that is reflexive, transitive and total, indicating
       "higher or equal task priority". *)

    Variable higher_eq_priority: FP_policy SporadicTask.
    Hypothesis H_priority_is_reflexive: FP_is_reflexive higher_eq_priority.
    Hypothesis H_priority_is_transitive: FP_is_transitive higher_eq_priority.
    Hypothesis H_priority_is_total: FP_is_total_over_task_set higher_eq_priority ts.

    (* Assume that the total suspension time of any job is bounded according
       to the dynamic suspension model. *)

    Variable next_suspension: job_suspension Job.
    Variable task_suspension_bound: SporadicTask time.
    Hypothesis H_dynamic_suspensions:
      dynamic_suspension_model job_cost job_task next_suspension task_suspension_bound.

    (* As part of the analysis, we are going to use task costs inflated with suspension bounds, ... *)
    Let inflated_cost := inflated_task_cost task_cost task_suspension_bound.

    (* ...with the condition that they are no larger than the deadline nor the period of each task. *)
    Hypothesis H_inflated_cost_le_deadline_and_period:
        tsk \in ts
          inflated_cost tsk task_deadline tsk
          inflated_cost tsk task_period tsk.

    (* Now we proceed with the schedulability analysis. *)
    Section MainProof.

      (* Consider any suspension-aware schedule of the arrival sequence... *)
      Variable sched: schedule Job.
      Hypothesis H_jobs_come_from_arrival_sequence:
        jobs_come_from_arrival_sequence sched arr_seq.

      (* ...where jobs only execute after they arrive... *)
      Hypothesis H_jobs_must_arrive_to_execute: jobs_must_arrive_to_execute job_arrival sched.

      (* ...and no longer than their execution costs. *)
      Hypothesis H_completed_jobs_dont_execute: completed_jobs_dont_execute job_cost sched.

      (* Also assume that the schedule is work-conserving when there are non-suspended jobs, ... *)
      Hypothesis H_work_conserving: work_conserving job_arrival job_cost next_suspension arr_seq sched.

      (* ...that the schedule respects job priority... *)
      Hypothesis H_respects_priority:
        respects_FP_policy job_arrival job_cost job_task next_suspension arr_seq
                           sched higher_eq_priority.

      (* ...and that suspended jobs are not allowed to be scheduled. *)
      Hypothesis H_respects_self_suspensions:
        respects_self_suspensions job_arrival job_cost next_suspension sched.

      (* For simplicity, let's also define some local names. *)
      Let task_is_schedulable :=
        task_misses_no_deadline job_arrival job_cost job_deadline job_task arr_seq sched.

      (* Next, recall the response-time analysis for FP scheduling instantiated with
         the inflated task costs. *)

      Let claimed_to_be_schedulable :=
        fp_schedulable inflated_cost task_period task_deadline higher_eq_priority.

      (* Then, we prove that if this suspension-oblivious response-time analysis suceeds... *)
      Hypothesis H_claimed_schedulable_by_suspension_oblivious_RTA:
        claimed_to_be_schedulable ts.

      (* ...then no task misses its deadline in the suspension-aware schedule.
         The proof is a straightforward application of the following lemma from
         reduction.v: suspension_oblivious_preserves_schedulability. *)

      Theorem suspension_oblivious_fp_rta_implies_schedulability:
          tsk \in ts
          task_is_schedulable tsk.

    End MainProof.

  End ReductionToBasicAnalysis.

End SuspensionObliviousFP.