Built with Alectryon, running Coq+SerAPI v8.14.0+0.14.0. Bubbles () indicate interactive fragments: hover for details, tap to reveal contents. Use Ctrl+↑Ctrl+↓ to navigate, Ctrl+🖱️ to focus. On Mac, use ⌘ instead of Ctrl.
Notation"[ rel _ _ | _ ]" was already used in scope
fun_scope. [notation-overridden,parsing]
Notation"[ rel _ _ : _ | _ ]" was already used in
scope fun_scope. [notation-overridden,parsing]
Notation"[ rel _ _ in _ & _ | _ ]" was already used
in scope fun_scope. [notation-overridden,parsing]
Notation"[ rel _ _ in _ & _ ]" was already used in
scope fun_scope. [notation-overridden,parsing]
Notation"[ rel _ _ in _ | _ ]" was already used in
scope fun_scope. [notation-overridden,parsing]
Notation"[ rel _ _ in _ ]" was already used in scope
fun_scope. [notation-overridden,parsing]
Notation"_ + _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation"_ - _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation"_ <= _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation"_ < _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation"_ >= _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation"_ > _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation"_ <= _ <= _" was already used in scope
nat_scope. [notation-overridden,parsing]
Notation"_ < _ <= _" was already used in scope
nat_scope. [notation-overridden,parsing]
Notation"_ <= _ < _" was already used in scope
nat_scope. [notation-overridden,parsing]
Notation"_ < _ < _" was already used in scope
nat_scope. [notation-overridden,parsing]
Notation"_ * _" was already used in scope nat_scope.
[notation-overridden,parsing]
Require Export prosa.util.rel.Require Export prosa.util.list.From mathcomp Require Export seq.(** * The FP, JLFP, and JLDP Priority Classes *)(** In this module, we define the three well-known classes of priority relations: (1) fixed-priority (FP) policies, (2) job-level fixed-priority (JLFP) polices, and (3) job-level dynamic-priority (JLDP) policies, where (2) is a subset of (3), and (1) a subset of (2). *)(** As a convention, we use "hep" to mean "higher or equal priority." *)(** We define an FP policy as a relation among tasks, ... *)ClassFP_policy (Task: TaskType) := hep_task : rel Task.(** ... a JLFP policy as a relation among jobs, and ... *)ClassJLFP_policy (Job: JobType) := hep_job : rel Job.(** ... a JLDP policy as a relation among jobs that may vary over time. *)ClassJLDP_policy (Job: JobType) := hep_job_at : instant -> rel Job.(** NB: The preceding definitions currently make it difficult to express priority policies in which the priority of a job at a given time varies depending on the preceding schedule prefix (e.g., least-laxity first). That is, there is room for an even more general notion of a schedule-dependent JLDP policy, where the priority relation among jobs may vary depending both on time and the schedule prefix prior to a given time. This is left to future work. *)(** ** Automatic FP ➔ JLFP ➔ JLDP Conversion *)(** Since there are natural interpretations of FP and JLFP policies as JLFP and JLDP policies, respectively, we define conversions that express these generalizations. In practice, this means that Coq will be able to automatically satisfy a JLDP assumption if a JLFP or FP policy is in scope. *)(** First, any FP policy can be interpreted as an JLFP policy by comparing jobs according to the priorities of their respective tasks. *)
The default value for instance locality is currently
"local"in a section and"global" otherwise, but is
scheduled to changein a future release. For the time
being, adding instances outside of sections without
specifying an explicit locality attribute is therefore
deprecated. It is recommended to use "export" whenever
possible. Use the attributes #[local], #[global] and
#[export] depending on your choice. For example:
"#[export] Instance Foo : Bar := baz."
[deprecated-instance-without-locality,deprecated]
(** Second, any JLFP policy implies a JLDP policy that simply ignores the time parameter. *)
The default value for instance locality is currently
"local"in a section and"global" otherwise, but is
scheduled to changein a future release. For the time
being, adding instances outside of sections without
specifying an explicit locality attribute is therefore
deprecated. It is recommended to use "export" whenever
possible. Use the attributes #[local], #[global] and
#[export] depending on your choice. For example:
"#[export] Instance Foo : Bar := baz."
[deprecated-instance-without-locality,deprecated]
(** ** Properties of Priority Policies *)(** In the following section, we define key properties of common priority policies that proofs often depend on. *)SectionPriorities.(** Consider any type of tasks ... *)Context {Task : TaskType}.Context `{TaskCost Task}.(** ... and any type of jobs associated with these tasks, ... *)Context {Job : JobType}.Context `{JobTask Job Task}.(** .. and assume that jobs have a cost and an arrival time. *)Context `{JobArrival Job}.Context `{JobCost Job}.(** In the following section, we define properties of JLDP policies, and by extension also properties of FP and JLFP policies. *)SectionJLDP.(** Consider any JLDP policy. *)Context `{JLDP_policy Job}.(** We define what it means for a JLDP policy to be reflexive, transitive, and total. Note that these definitions, although phrased in terms of a given JLDP policy, can also be used for JLFP and FP policies due to the above-defined conversion instances. *)(** A JLDP policy is reflexive if the relation among jobs is reflexive at every point in time. *)Definitionreflexive_priorities := forallt, reflexive (hep_job_at t).(** A JLDP policy is transitive if the relation among jobs is transitive at every point in time. *)Definitiontransitive_priorities := forallt, transitive (hep_job_at t).(** A JLDP policy is total if the relation among jobs is total at every point in time. *)Definitiontotal_priorities := forallt, total (hep_job_at t).EndJLDP.(** Next, we define a property of JLFP policies. *)SectionJLFP.(** Consider any JLFP policy. *)Context `{JLFP_policy Job}.(** Recall that jobs of a sequential task are necessarily executed in the order that they arrive. An arbitrary JLFP policy, however, can violate the sequential tasks hypothesis. For example, consider two jobs [j1], [j2] of the same task such that [job_arrival j1 < job_arrival j2]. It is possible that a JLFP priority policy [π] will assign a higher priority to the second job [π j2 j1 = true]. But such a situation would contradict the natural execution order of sequential tasks. It is therefore sometimes necessary to restrict the space of JLFP policies to those that assign priorities in a way that is consistent with sequential tasks. To this end, we say that a policy respects sequential tasks if, for any two jobs [j1], [j2] of the same task, [job_arrival j1 <= job_arrival j2] implies [π j1 j2 = true]. *)Definitionpolicy_respects_sequential_tasks :=
forallj1j2,
job_task j1 == job_task j2 ->
job_arrival j1 <= job_arrival j2 ->
hep_job j1 j2.EndJLFP.(** Finally, we we define and observe two properties of FP policies. *)SectionFP.(** Consider any FP policy. *)Context `{FP_policy Task}.(** To express the common assumption that task priorities are unique, we define whether the given FP policy is antisymmetric over a task set [ts]. *)Definitionantisymmetric_over_taskset (ts : seq Task) :=
antisymmetric_over_list hep_task ts.(** Further, we observe that any [FP_policy] respects the sequential tasks hypothesis, meaning that later-arrived jobs of a task don't have higher priority than earlier-arrived jobs of the same task (assuming that task priorities are reflexive). *)
byeapply (REFL 0).Qed.EndFP.EndPriorities.(** We add the above observation into the "Hint Database" basic_facts, so Coq will be able to apply it automatically. *)GlobalHint Resolve respects_sequential_tasks : basic_facts.