Library prosa.implementation.refinements.FP.fast_search_space

Require Export prosa.results.fixed_priority.rta.bounded_nps.
Require Export prosa.implementation.refinements.fast_search_space_computation.

Throughout this file, we work with Prosa's fixed-priority policy implementation.
#[local] Existing Instance NumericFPAscending.

First, we define the concept of higher-or-equal-priority and different task, ...
Definition ohep_task (tsk1 : Task) (tsk2 : Task) :=
  hep_task tsk1 tsk2 && (tsk1 != tsk2).

... cumulative request-bound function for higher-or-equal-priority tasks (including the task under analysis), ...
Definition total_hep_rbf (ts : seq Task) (tsk : Task) (Δ : duration) :=
  total_hep_request_bound_function_FP ts tsk Δ.

... and an analogous definition that does not include the task under analysis.
Definition total_ohep_rbf (ts : seq Task) (tsk : Task) (Δ : duration) :=
  total_ohep_request_bound_function_FP ts tsk Δ.

Next, we provide a function that checks a single point P=(A,F) of the search space when adopting a fully-preemptive policy.
Definition check_point_FP (ts : seq Task) (tsk : Task) (R : nat) (P : nat × nat) :=
  (task_rbf tsk (P.1 + ε) + total_ohep_rbf ts tsk (P.1 + P.2) ≤ P.1 + P.2) && (P.2 ≤ R).

Further, we provide a way to compute the blocking bound when using nonpreemptive policies.
Definition blocking_bound_NP (ts : seq Task) (tsk : Task) :=
  \max_(tsk_other <- ts | ~~ hep_task tsk_other tsk) (concept.task_cost tsk_other - ε).

Finally, we provide a function that checks a single point P=(A,F) of the search space when adopting a fully-nonpreemptive policy.
Definition check_point_NP (ts : seq Task) (tsk : Task) (R : nat) (P : nat × nat) :=
  (blocking_bound_NP ts tsk
   + (task_rbf tsk (P.1 + ε) - (concept.task_cost tsk - ε))
   + total_ohep_rbf ts tsk (P.1 + P.2) ≤ P.1 + P.2)
  && (P.2 + (concept.task_cost tsk - ε) ≤ R).

Search Space Definitions

First, we recall the notion of correct search space as defined by abstract RTA.
Definition correct_search_space (tsk : Task) (L : duration) :=
  [seq A <- iota 0 L | is_in_search_space tsk L A].

Next, we provide a computation-oriented way to compute abstract RTA's search space. We start with a function that computes the search space in a generic interval [a,b), ...
Definition search_space_emax_FP_h (tsk : Task) a b :=
  let h := get_horizon_of_task tsk in
  let offsets := map (muln h) (iota a b) in
  let emax_offsets := repeat_steps_with_offset tsk offsets in
  map predn emax_offsets.

... which we then apply to the interval [0, (L %/h).+1).
Definition search_space_emax_FP (tsk : Task) (L : duration) :=
  let h := get_horizon_of_task tsk in
  search_space_emax_FP_h tsk 0 (L %/h).+1.

In this section, we prove that the computation-oriented search space defined above contains each of the points contained in abstract RTA's standard definition.
Section FastSearchSpaceComputationSubset.

Consider a given maximum busy-interval length L, ...
  Variable L : duration.

... a task set with valid arrivals, ...
  Variable ts : seq Task.
  Hypothesis H_valid_arrivals : task_set_with_valid_arrivals ts.

... and a task belonging to ts with positive cost.
  Variable tsk : Task.
  Hypothesis H_positive_cost : 0 < task_cost tsk.
  Hypothesis H_tsk_in_ts : tsk \in ts.

Then, abstract RTA's standard search space is a subset of the computation-oriented version defined above.
  Lemma search_space_subset_FP :
    ∀ A, A \in correct_search_space tsk L → A \in search_space_emax_FP tsk L.

End FastSearchSpaceComputationSubset.