Library prosa.model.priority.deadline_monotonic
(* ----------------------------------[ coqtop ]---------------------------------
Welcome to Coq 8.11.2 (June 2020)
----------------------------------------------------------------------------- *)
Require Export prosa.model.priority.classes.
Deadline-Monotonic Fixed-Priority Policy
Instance DM (Task : TaskType) `{TaskDeadline Task} : FP_policy Task :=
{
hep_task (tsk1 tsk2 : Task) := task_deadline tsk1 ≤ task_deadline tsk2
}.
{
hep_task (tsk1 tsk2 : Task) := task_deadline tsk1 ≤ task_deadline tsk2
}.
In this section, we prove a few basic properties of the DM policy.
Consider any kind of tasks with relative deadlines...
...and jobs stemming from these tasks.
DM is reflexive.
Lemma DM_is_reflexive : reflexive_priorities.
(* ----------------------------------[ coqtop ]---------------------------------
1 subgoal (ID 43)
Task : TaskType
H : TaskDeadline Task
Job : JobType
H0 : JobTask Job Task
============================
reflexive_priorities
----------------------------------------------------------------------------- *)
Proof. by move⇒ ?; rewrite /hep_job_at /JLFP_to_JLDP /hep_job /FP_to_JLFP /hep_task /DM.
(* ----------------------------------[ coqtop ]---------------------------------
No more subgoals.
----------------------------------------------------------------------------- *)
Qed.
(* ----------------------------------[ coqtop ]---------------------------------
1 subgoal (ID 43)
Task : TaskType
H : TaskDeadline Task
Job : JobType
H0 : JobTask Job Task
============================
reflexive_priorities
----------------------------------------------------------------------------- *)
Proof. by move⇒ ?; rewrite /hep_job_at /JLFP_to_JLDP /hep_job /FP_to_JLFP /hep_task /DM.
(* ----------------------------------[ coqtop ]---------------------------------
No more subgoals.
----------------------------------------------------------------------------- *)
Qed.
DM is transitive.
Lemma DM_is_transitive : transitive_priorities.
(* ----------------------------------[ coqtop ]---------------------------------
1 subgoal (ID 51)
Task : TaskType
H : TaskDeadline Task
Job : JobType
H0 : JobTask Job Task
============================
transitive_priorities
----------------------------------------------------------------------------- *)
Proof. by intros t y x z; apply leq_trans.
(* ----------------------------------[ coqtop ]---------------------------------
No more subgoals.
----------------------------------------------------------------------------- *)
Qed.
(* ----------------------------------[ coqtop ]---------------------------------
1 subgoal (ID 51)
Task : TaskType
H : TaskDeadline Task
Job : JobType
H0 : JobTask Job Task
============================
transitive_priorities
----------------------------------------------------------------------------- *)
Proof. by intros t y x z; apply leq_trans.
(* ----------------------------------[ coqtop ]---------------------------------
No more subgoals.
----------------------------------------------------------------------------- *)
Qed.
DM is total.
Lemma DM_is_total : total_priorities.
(* ----------------------------------[ coqtop ]---------------------------------
1 subgoal (ID 59)
Task : TaskType
H : TaskDeadline Task
Job : JobType
H0 : JobTask Job Task
============================
total_priorities
----------------------------------------------------------------------------- *)
Proof. by move⇒ t j1 j2; apply leq_total.
(* ----------------------------------[ coqtop ]---------------------------------
No more subgoals.
----------------------------------------------------------------------------- *)
Qed.
End Properties.
(* ----------------------------------[ coqtop ]---------------------------------
1 subgoal (ID 59)
Task : TaskType
H : TaskDeadline Task
Job : JobType
H0 : JobTask Job Task
============================
total_priorities
----------------------------------------------------------------------------- *)
Proof. by move⇒ t j1 j2; apply leq_total.
(* ----------------------------------[ coqtop ]---------------------------------
No more subgoals.
----------------------------------------------------------------------------- *)
Qed.
End Properties.
We add the above lemmas into a "Hint Database" basic_facts, so Coq
will be able to apply them automatically.
Hint Resolve
DM_is_reflexive
DM_is_transitive
DM_is_total
: basic_facts.
DM_is_reflexive
DM_is_transitive
DM_is_total
: basic_facts.