Marco Maida authored 2 years ago and Björn Brandenburg committed 2 years ago

This commit defines and adds facts about a concrete arrival sequence in
which tasks release jobs "as quickly as possible" as allowed by their
respective arrival-curve constraints. This maximal arrival sequence is
used in POET to generate assumption-less certificates.

Kimaya Bedarkar authored 2 years ago and Björn Brandenburg committed 2 years ago

The current definitions of `respects_JLFP_policy_at_preemption_time`
and `respects_FP_policy_at_preemption_time` use the predicate
`hep_job_at`. This predicate does not make sense for `JLFP`
and `FP` policies. To avoid this, these definitions should
instead use the definition `respects_JLDP_policy_at_preemption_point`.
Doing this requires coercions from `JLFP` to `JLDP` and from
`FP` to `JLFP`. This patch also introduces these coercions.

Pierre Roux authored 3 years ago and Björn Brandenburg committed 2 years ago

It is exactly big1_eq

Pierre Roux authored 3 years ago and Björn Brandenburg committed 2 years ago

It was subsumed by sum_nat_gt0

Pierre Roux authored 3 years ago and Björn Brandenburg committed 2 years ago

Too specific and one liner with existing MathComp lemmas.

Pierre Roux authored 3 years ago and Björn Brandenburg committed 2 years ago

Subsumed by existing MathComp lemmas on division.

Pierre Roux authored 3 years ago and Björn Brandenburg committed 2 years ago

leq_trans and leq_addr seem to be enough.

Pierre Roux authored 3 years ago and Björn Brandenburg committed 2 years ago

Too specific.

Sergey Bozhko authored 3 years ago and Björn Brandenburg committed 2 years ago

This commit also removes one spurious dependency on ideal uni-processor.
That is, previously file [model/service_of_jobs.v] imported
[processor.ideal], which is wrong, since [model/service_of_jobs.v]
assumes no specific model for processor.

Kimaya Bedarkar authored 2 years ago and Björn Brandenburg committed 2 years ago

As described in #92, the name `np_uni_schedule` is problematic. This
patch renames the scheduler to the more appropriate `pmc_uni_schedule`.

Closes: #92

Kimaya Bedarkar authored 2 years ago and Björn Brandenburg committed 2 years ago

To complement the existing interpretation, add one more instance of
numeric fixed priority that assigns higher priority to lower numeric
values.

Pierre Roux authored 2 years ago and Björn Brandenburg committed 2 years ago

Rename the type-class parameter to `job_preemptive_points` to avoid a
name clash with the the definition of the same name.

Keep `JobPreemptionPoints` to match `TaskPreemptionPoints`. This does
not  result in a name clash.

NB: This requires bumping up the "depth" parameter of `rt_auto` and `rt_eauto`.

As a benefit, it becomes possible to automatically use RBFs in the
context of periodic tasks, sporadic tasks, and tasks with arrival
curves. Full example:

```
Require Import prosa.model.task.arrival.periodic.
Require Import prosa.model.task.arrival.periodic_as_sporadic.
Require Import prosa.model.task.arrival.sporadic_as_curve.
Require Import prosa.model.task.arrival.curve_as_rbf.

Section AutoArrivalModelConversion.

  Context {Job : JobType} `{JobArrival Job}.
  Context {Task : TaskType} `{PeriodicModel Task} `{JobTask Job Task}.

  Variable ts : TaskSet Task.

  Variable arr_seq : arrival_sequence Job.
  Hypothesis H_consistent_arrivals: consistent_arrival_times arr_seq.
  Hypothesis H_uniq_arr_seq: arrival_sequence_uniq arr_seq.

  Hypothesis H_valid_periods : valid_periods ts.
  Hypothesis H_respects : taskset_respects_periodic_task_model arr_seq ts.

  Context `{JobCost Job} `{TaskCost Task}.
  Hypothesis H_valid_costs : jobs_have_valid_job_costs.

  (** Interpret as an RBF. *)

  Goal valid_taskset_request_bound_function ts (task_max_rbf max_arrivals).
  Proof. by rt_auto. Qed.

  Goal taskset_respects_max_request_bound arr_seq ts.
  Proof. rt_eauto. Qed.

End AutoArrivalModelConversion.
```

This commit makes it possible to transparently interpret periodic
tasks as sporadic tasks, and sporadic tasks as tasks with an arrival
curve, such that all proof obligations can satisfied by `rt_auto` and
`rt_eauto`. Full example:

```
Require Import prosa.model.task.arrival.periodic.
Require Import prosa.model.task.arrival.periodic_as_sporadic.
Require Import prosa.model.task.arrival.sporadic_as_curve.

Section AutoArrivalModelConversion.

  Context {Job : JobType} `{JobArrival Job}.
  Context {Task : TaskType} `{PeriodicModel Task} `{JobTask Job Task}.

  Variable ts : TaskSet Task.

  Variable arr_seq : arrival_sequence Job.
  Hypothesis H_consistent_arrivals: consistent_arrival_times arr_seq.
  Hypothesis H_uniq_arr_seq: arrival_sequence_uniq arr_seq.

  Hypothesis H_valid_periods : valid_periods ts.

  Hypothesis H_respects : taskset_respects_periodic_task_model arr_seq ts.

  (** 1. Interpret as sporadic: *)
  Goal valid_taskset_inter_arrival_times ts.
  Proof. by rt_auto. Qed.

  Goal taskset_respects_sporadic_task_model ts arr_seq.
  Proof. by rt_auto. Qed.

  (** 2. Interpret as an arrival curve. *)
  Goal valid_taskset_arrival_curve ts max_arrivals.
  Proof. by rt_auto. Qed.

  Goal taskset_respects_max_arrivals arr_seq ts.
  Proof. by rt_eauto. Qed.

End AutoArrivalModelConversion.

```

- move all to `prosa.model.task.arrival`
- unify names to `${FOO}_as_${BAR}.v`