Library rt.implementation.parallel.bertogna_fp_example
Require Import rt.util.all.
Require Import rt.model.basic.job rt.model.basic.task
rt.model.basic.schedule rt.model.basic.schedulability
rt.model.basic.priority rt.model.basic.platform
rt.model.basic.interference.
Require Import rt.analysis.parallel.workload_bound
rt.analysis.parallel.interference_bound_fp
rt.analysis.parallel.bertogna_fp_comp.
Require Import rt.implementation.parallel.job
rt.implementation.parallel.task
rt.implementation.parallel.schedule
rt.implementation.parallel.arrival_sequence.
From mathcomp Require Import ssreflect ssrbool ssrnat eqtype seq bigop div.
Module ResponseTimeAnalysisFP.
Import Job Schedule SporadicTaskset Priority Schedulability Platform
Interference InterferenceBoundFP WorkloadBound
ResponseTimeIterationFP.
Import ConcreteJob ConcreteTask ConcreteArrivalSequence ConcreteScheduler.
(* In this section, we instantiate a simple example to show that the theorems
contain no contradictory assumptions. *)
Section ExampleRTA.
Let tsk1 := {| task_id := 1; task_cost := 2; task_period := 6; task_deadline := 6|}.
Let tsk2 := {| task_id := 2; task_cost := 3; task_period := 8; task_deadline := 6|}.
Let tsk3 := {| task_id := 3; task_cost := 2; task_period := 12; task_deadline := 12|}.
(* Let ts be a task set containing these three tasks (sorted by rate-monotonic priority). *)
Program Let ts := Build_set [:: tsk1; tsk2; tsk3] _.
Section FactsAboutTaskset.
Fact ts_has_valid_parameters:
valid_sporadic_taskset task_cost task_period task_deadline ts.
Proof.
intros tsk IN.
repeat (move: IN ⇒ /orP [/eqP EQ | IN]; subst; compute); by done.
Qed.
Fact ts_has_constrained_deadlines:
∀ tsk,
tsk ∈ ts →
task_deadline tsk ≤ task_period tsk.
Proof.
intros tsk IN.
repeat (move: IN ⇒ /orP [/eqP EQ | IN]; subst; compute); by done.
Qed.
End FactsAboutTaskset.
(* Assume there are two processors. *)
Let num_cpus := 2.
(* Recall the FP RTA schedulability test. *)
Let schedulability_test :=
fp_schedulable task_cost task_period task_deadline num_cpus.
(* Now we show that the schedulability test returns true. *)
Fact schedulability_test_succeeds :
schedulability_test ts = true.
Proof.
unfold schedulability_test, fp_schedulable, fp_claimed_bounds; simpl.
unfold total_interference_bound_fp, div_floor.
rewrite big_nil div0n addn0 /=.
unfold div_floor; simpl.
set I2 := total_interference_bound_fp task_cost task_period [:: (tsk1, 2)].
assert (H1: I2 3 = 2).
{
by rewrite /I2 /total_interference_bound_fp big_cons big_nil; compute.
}
assert (H2: I2 4 = 2).
{
by rewrite /I2 /total_interference_bound_fp big_cons big_nil; compute.
}
rewrite H1 H2.
have H3: 3 + 2 %/ num_cpus = 4 by compute.
rewrite H3 H2 H3 H2 H3.
have H4: 3 < 6 by compute.
rewrite H4; clear H4 H2 H1 I2.
unfold fp_bound_of_task.
have H5: per_task_rta task_cost task_period num_cpus tsk3 [:: (tsk1, 2); (tsk2, 4)] (max_steps task_cost task_deadline tsk3) = 4.
{
Ltac g := rewrite /total_interference_bound_fp /interference_bound_generic
/W /max_jobs /div_floor /div_ceil !big_cons big_nil /= /higher_priority_task /= ?addn0; compute.
rewrite /per_task_rta iterSr /div_floor.
set x10 := total_interference_bound_fp _ _ _ _.
have I10: x10 = 5 by unfold x10; g.
rewrite I10 iterSr.
set x9 := total_interference_bound_fp _ _ _ _.
have I9: x9 = 5 by unfold x9; g.
rewrite I9 iterSr.
set x8 := total_interference_bound_fp _ _ _ _.
have I8: x8 = 5 by unfold x8; g.
rewrite I8 iterSr.
set x7 := total_interference_bound_fp _ _ _ _.
have I7: x7 = 5 by unfold x7; g.
rewrite I7 iterSr.
set x6 := total_interference_bound_fp _ _ _ _.
have I6: x6 = 5 by unfold x6; g.
rewrite I6 iterSr.
set x5 := total_interference_bound_fp _ _ _ _.
have I5: x5 = 5 by unfold x5; g.
rewrite I5 iterSr.
set x4 := total_interference_bound_fp _ _ _ _.
have I4: x4 = 5 by unfold x4; g.
rewrite I4 iterSr.
set x3 := total_interference_bound_fp _ _ _ _.
have I3: x3 = 5 by unfold x3; g.
rewrite I3 iterSr.
set x2 := total_interference_bound_fp _ _ _ _.
have I2: x2 = 5 by unfold x2; g.
rewrite I2 iterSr.
set x1 := total_interference_bound_fp _ _ _ _.
have I1: x1 = 5 by unfold x1; g.
rewrite I1 iterSr.
set x0 := total_interference_bound_fp _ _ _ _.
have I0: x0 = 5 by unfold x0; g.
by rewrite /= I0; compute.
}
by rewrite H5.
Qed.
(* Let arr_seq be the periodic arrival sequence from ts. *)
Let arr_seq := periodic_arrival_sequence ts.
(* Assume rate-monotonic priorities. *)
Let higher_priority : JLDP_policy arr_seq :=
(FP_to_JLDP job_task (RM task_period)).
Section FactsAboutPriorityOrder.
Lemma ts_has_unique_priorities :
FP_is_antisymmetric_over_task_set (RM task_period) ts.
Proof.
unfold RM; intros tsk tsk' IN IN' HP HP'.
have EQ: task_period tsk = task_period tsk' by apply/eqP; rewrite eqn_leq HP HP'.
clear HP HP'.
rewrite !in_cons 2!in_nil 2!orbF in IN IN'; des; rewrite IN IN'; try (by done);
subst tsk tsk'; simpl in *; by done.
Qed.
Lemma priority_is_total :
FP_is_total_over_task_set (RM task_period) ts.
Proof.
unfold RM; intros tsk tsk' IN IN'.
destruct (leqP (task_period tsk) (task_period tsk'));
[by left | by right; apply ltnW].
Qed.
End FactsAboutPriorityOrder.
(* Let sched be the work-conserving RM scheduler. *)
Let sched := scheduler job_cost num_cpus arr_seq higher_priority.
(* Recall the definition of deadline miss. *)
Let no_deadline_missed_by :=
task_misses_no_deadline job_cost job_deadline job_task sched.
(* Next, we prove that ts is schedulable with the result of the test. *)
Corollary ts_is_schedulable:
∀ tsk,
tsk ∈ ts →
no_deadline_missed_by tsk.
Proof.
intros tsk IN.
have VALID := periodic_arrivals_valid_job_parameters ts ts_has_valid_parameters.
have TSVALID := ts_has_valid_parameters.
unfold valid_sporadic_job, valid_realtime_job in *; des.
apply taskset_schedulable_by_fp_rta with (task_cost := task_cost)
(task_period := task_period) (task_deadline := task_deadline)
(ts0 := ts) (higher_priority0 := RM task_period); try (by done).
- by apply ts_has_constrained_deadlines.
- by apply ts_has_unique_priorities.
- by apply priority_is_total.
- by apply RM_is_transitive.
- by apply periodic_arrivals_all_jobs_from_taskset.
- by apply periodic_arrivals_are_sporadic.
- by apply scheduler_jobs_must_arrive_to_execute.
- apply scheduler_completed_jobs_dont_execute; intro j'.
-- by specialize (VALID j'); des.
-- by apply periodic_arrivals_is_a_set.
- by apply scheduler_work_conserving.
- apply scheduler_enforces_policy.
-- by intros t; apply RM_is_transitive.
{
unfold FP_to_JLDP; intros t x y; apply/orP.
by apply priority_is_total; rewrite periodic_arrivals_all_jobs_from_taskset.
}
- by apply schedulability_test_succeeds.
Qed.
End ExampleRTA.
End ResponseTimeAnalysisFP.
Require Import rt.model.basic.job rt.model.basic.task
rt.model.basic.schedule rt.model.basic.schedulability
rt.model.basic.priority rt.model.basic.platform
rt.model.basic.interference.
Require Import rt.analysis.parallel.workload_bound
rt.analysis.parallel.interference_bound_fp
rt.analysis.parallel.bertogna_fp_comp.
Require Import rt.implementation.parallel.job
rt.implementation.parallel.task
rt.implementation.parallel.schedule
rt.implementation.parallel.arrival_sequence.
From mathcomp Require Import ssreflect ssrbool ssrnat eqtype seq bigop div.
Module ResponseTimeAnalysisFP.
Import Job Schedule SporadicTaskset Priority Schedulability Platform
Interference InterferenceBoundFP WorkloadBound
ResponseTimeIterationFP.
Import ConcreteJob ConcreteTask ConcreteArrivalSequence ConcreteScheduler.
(* In this section, we instantiate a simple example to show that the theorems
contain no contradictory assumptions. *)
Section ExampleRTA.
Let tsk1 := {| task_id := 1; task_cost := 2; task_period := 6; task_deadline := 6|}.
Let tsk2 := {| task_id := 2; task_cost := 3; task_period := 8; task_deadline := 6|}.
Let tsk3 := {| task_id := 3; task_cost := 2; task_period := 12; task_deadline := 12|}.
(* Let ts be a task set containing these three tasks (sorted by rate-monotonic priority). *)
Program Let ts := Build_set [:: tsk1; tsk2; tsk3] _.
Section FactsAboutTaskset.
Fact ts_has_valid_parameters:
valid_sporadic_taskset task_cost task_period task_deadline ts.
Proof.
intros tsk IN.
repeat (move: IN ⇒ /orP [/eqP EQ | IN]; subst; compute); by done.
Qed.
Fact ts_has_constrained_deadlines:
∀ tsk,
tsk ∈ ts →
task_deadline tsk ≤ task_period tsk.
Proof.
intros tsk IN.
repeat (move: IN ⇒ /orP [/eqP EQ | IN]; subst; compute); by done.
Qed.
End FactsAboutTaskset.
(* Assume there are two processors. *)
Let num_cpus := 2.
(* Recall the FP RTA schedulability test. *)
Let schedulability_test :=
fp_schedulable task_cost task_period task_deadline num_cpus.
(* Now we show that the schedulability test returns true. *)
Fact schedulability_test_succeeds :
schedulability_test ts = true.
Proof.
unfold schedulability_test, fp_schedulable, fp_claimed_bounds; simpl.
unfold total_interference_bound_fp, div_floor.
rewrite big_nil div0n addn0 /=.
unfold div_floor; simpl.
set I2 := total_interference_bound_fp task_cost task_period [:: (tsk1, 2)].
assert (H1: I2 3 = 2).
{
by rewrite /I2 /total_interference_bound_fp big_cons big_nil; compute.
}
assert (H2: I2 4 = 2).
{
by rewrite /I2 /total_interference_bound_fp big_cons big_nil; compute.
}
rewrite H1 H2.
have H3: 3 + 2 %/ num_cpus = 4 by compute.
rewrite H3 H2 H3 H2 H3.
have H4: 3 < 6 by compute.
rewrite H4; clear H4 H2 H1 I2.
unfold fp_bound_of_task.
have H5: per_task_rta task_cost task_period num_cpus tsk3 [:: (tsk1, 2); (tsk2, 4)] (max_steps task_cost task_deadline tsk3) = 4.
{
Ltac g := rewrite /total_interference_bound_fp /interference_bound_generic
/W /max_jobs /div_floor /div_ceil !big_cons big_nil /= /higher_priority_task /= ?addn0; compute.
rewrite /per_task_rta iterSr /div_floor.
set x10 := total_interference_bound_fp _ _ _ _.
have I10: x10 = 5 by unfold x10; g.
rewrite I10 iterSr.
set x9 := total_interference_bound_fp _ _ _ _.
have I9: x9 = 5 by unfold x9; g.
rewrite I9 iterSr.
set x8 := total_interference_bound_fp _ _ _ _.
have I8: x8 = 5 by unfold x8; g.
rewrite I8 iterSr.
set x7 := total_interference_bound_fp _ _ _ _.
have I7: x7 = 5 by unfold x7; g.
rewrite I7 iterSr.
set x6 := total_interference_bound_fp _ _ _ _.
have I6: x6 = 5 by unfold x6; g.
rewrite I6 iterSr.
set x5 := total_interference_bound_fp _ _ _ _.
have I5: x5 = 5 by unfold x5; g.
rewrite I5 iterSr.
set x4 := total_interference_bound_fp _ _ _ _.
have I4: x4 = 5 by unfold x4; g.
rewrite I4 iterSr.
set x3 := total_interference_bound_fp _ _ _ _.
have I3: x3 = 5 by unfold x3; g.
rewrite I3 iterSr.
set x2 := total_interference_bound_fp _ _ _ _.
have I2: x2 = 5 by unfold x2; g.
rewrite I2 iterSr.
set x1 := total_interference_bound_fp _ _ _ _.
have I1: x1 = 5 by unfold x1; g.
rewrite I1 iterSr.
set x0 := total_interference_bound_fp _ _ _ _.
have I0: x0 = 5 by unfold x0; g.
by rewrite /= I0; compute.
}
by rewrite H5.
Qed.
(* Let arr_seq be the periodic arrival sequence from ts. *)
Let arr_seq := periodic_arrival_sequence ts.
(* Assume rate-monotonic priorities. *)
Let higher_priority : JLDP_policy arr_seq :=
(FP_to_JLDP job_task (RM task_period)).
Section FactsAboutPriorityOrder.
Lemma ts_has_unique_priorities :
FP_is_antisymmetric_over_task_set (RM task_period) ts.
Proof.
unfold RM; intros tsk tsk' IN IN' HP HP'.
have EQ: task_period tsk = task_period tsk' by apply/eqP; rewrite eqn_leq HP HP'.
clear HP HP'.
rewrite !in_cons 2!in_nil 2!orbF in IN IN'; des; rewrite IN IN'; try (by done);
subst tsk tsk'; simpl in *; by done.
Qed.
Lemma priority_is_total :
FP_is_total_over_task_set (RM task_period) ts.
Proof.
unfold RM; intros tsk tsk' IN IN'.
destruct (leqP (task_period tsk) (task_period tsk'));
[by left | by right; apply ltnW].
Qed.
End FactsAboutPriorityOrder.
(* Let sched be the work-conserving RM scheduler. *)
Let sched := scheduler job_cost num_cpus arr_seq higher_priority.
(* Recall the definition of deadline miss. *)
Let no_deadline_missed_by :=
task_misses_no_deadline job_cost job_deadline job_task sched.
(* Next, we prove that ts is schedulable with the result of the test. *)
Corollary ts_is_schedulable:
∀ tsk,
tsk ∈ ts →
no_deadline_missed_by tsk.
Proof.
intros tsk IN.
have VALID := periodic_arrivals_valid_job_parameters ts ts_has_valid_parameters.
have TSVALID := ts_has_valid_parameters.
unfold valid_sporadic_job, valid_realtime_job in *; des.
apply taskset_schedulable_by_fp_rta with (task_cost := task_cost)
(task_period := task_period) (task_deadline := task_deadline)
(ts0 := ts) (higher_priority0 := RM task_period); try (by done).
- by apply ts_has_constrained_deadlines.
- by apply ts_has_unique_priorities.
- by apply priority_is_total.
- by apply RM_is_transitive.
- by apply periodic_arrivals_all_jobs_from_taskset.
- by apply periodic_arrivals_are_sporadic.
- by apply scheduler_jobs_must_arrive_to_execute.
- apply scheduler_completed_jobs_dont_execute; intro j'.
-- by specialize (VALID j'); des.
-- by apply periodic_arrivals_is_a_set.
- by apply scheduler_work_conserving.
- apply scheduler_enforces_policy.
-- by intros t; apply RM_is_transitive.
{
unfold FP_to_JLDP; intros t x y; apply/orP.
by apply priority_is_total; rewrite periodic_arrivals_all_jobs_from_taskset.
}
- by apply schedulability_test_succeeds.
Qed.
End ExampleRTA.
End ResponseTimeAnalysisFP.