Built with
Alectryon , running Coq+SerAPI v8.19.0+0.19.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 .
Require Export prosa.analysis.abstract .ideal.abstract_seq_rta.[Loading ML file ssrmatching_plugin.cmxs (using legacy method) ... done ] [Loading ML file ssreflect_plugin.cmxs (using legacy method) ... done ] [Loading ML file ring_plugin.cmxs (using legacy method) ... done ] [Loading ML file coq-elpi.elpi ... done ] [Loading ML file zify_plugin.cmxs (using legacy method) ... done ] [Loading ML file micromega_plugin.cmxs (using legacy method) ... done ] [Loading ML file btauto_plugin.cmxs (using legacy method) ... done ] Notation "_ + _" was already used in scope nat_scope.
[notation-overridden,parsing,default]Notation "_ - _" was already used in scope nat_scope.
[notation-overridden,parsing,default]Notation "_ <= _" was already used in scope nat_scope.
[notation-overridden,parsing,default]Notation "_ < _" was already used in scope nat_scope.
[notation-overridden,parsing,default]Notation "_ >= _" was already used in scope nat_scope.
[notation-overridden,parsing,default]Notation "_ > _" was already used in scope nat_scope.
[notation-overridden,parsing,default]Notation "_ <= _ <= _" was already used in scope
nat_scope. [notation-overridden,parsing,default]Notation "_ < _ <= _" was already used in scope
nat_scope. [notation-overridden,parsing,default]Notation "_ <= _ < _" was already used in scope
nat_scope. [notation-overridden,parsing,default]Notation "_ < _ < _" was already used in scope
nat_scope. [notation-overridden,parsing,default]Notation "_ * _" was already used in scope nat_scope.
[notation-overridden,parsing,default]
Require Import prosa.util.int.New coercion path [GRing.subring_closedM;
GRing.smulr_closedN] : GRing.subring_closed >-> GRing.oppr_closed is ambiguous with existing
[GRing.subring_closedB; GRing.zmod_closedN] : GRing.subring_closed >-> GRing.oppr_closed.
[ambiguous-paths,coercions,default] New coercion path [GRing.subring_closed_semi;
GRing.semiring_closedM] : GRing.subring_closed >-> GRing.mulr_closed is ambiguous with existing
[GRing.subring_closedM; GRing.smulr_closedM] : GRing.subring_closed >-> GRing.mulr_closed.
New coercion path [GRing.subring_closed_semi;
GRing.semiring_closedD] : GRing.subring_closed >-> GRing.addr_closed is ambiguous with existing
[GRing.subring_closedB; GRing.zmod_closedD] : GRing.subring_closed >-> GRing.addr_closed.
[ambiguous-paths,coercions,default] New coercion path [GRing.sdivr_closed_div;
GRing.divr_closedM] : GRing.sdivr_closed >-> GRing.mulr_closed is ambiguous with existing
[GRing.sdivr_closedM; GRing.smulr_closedM] : GRing.sdivr_closed >-> GRing.mulr_closed.
[ambiguous-paths,coercions,default] New coercion path [GRing.subalg_closedBM;
GRing.subring_closedB] : GRing.subalg_closed >-> GRing.zmod_closed is ambiguous with existing
[GRing.subalg_closedZ; GRing.submod_closedB] : GRing.subalg_closed >-> GRing.zmod_closed.
[ambiguous-paths,coercions,default] New coercion path [GRing.divring_closed_div;
GRing.sdivr_closedM] : GRing.divring_closed >-> GRing.smulr_closed is ambiguous with existing
[GRing.divring_closedBM; GRing.subring_closedM] : GRing.divring_closed >-> GRing.smulr_closed.
[ambiguous-paths,coercions,default] New coercion path [GRing.divalg_closedBdiv;
GRing.divring_closedBM] : GRing.divalg_closed >-> GRing.subring_closed is ambiguous with existing
[GRing.divalg_closedZ; GRing.subalg_closedBM] : GRing.divalg_closed >-> GRing.subring_closed.
[ambiguous-paths,coercions,default] Notation "_ - _" was already used in scope
distn_scope. [notation-overridden,parsing,default]
Require Import prosa.analysis.abstract .ideal.cumulative_bounds.
Require Import prosa.analysis.facts.readiness.basic.
Require Import prosa.model.schedule.priority_driven.
Require Import prosa.model.priority.gel.
Require Import analysis.facts.priority.gel.
Require Export prosa.analysis.facts.model.task_cost.
(** * Abstract RTA for GEL-Schedulers with Bounded Priority Inversion *)
(** In this module we instantiate the abstract response-time analysis
(aRTA) for GEL-schedulers assuming the ideal uni-processor model and
real-time tasks with arbitrary arrival models. *)
(** The important feature of this instantiation is that
it allows reasoning about the meaningful notion of priority
inversion. However, we do not specify the exact cause of priority
inversion (as there may be different reasons for this, like
execution of a non-preemptive segment or blocking due to resource
locking). We only assume that the duration of priority inversion is
bounded. *)
Section AbstractRTAforGELwithArrivalCurves .
(** We consider tasks and jobs with the given parameters. *)
Context {Task : TaskType} `{TaskCost Task} `{TaskRunToCompletionThreshold Task}
`{TaskMaxNonpreemptiveSegment Task} `{MaxArrivals Task}.
Context {Job : JobType} `{JobTask Job Task} {Arrival : JobArrival Job}
{Cost : JobCost Job} `{JobPreemptable Job} `{PriorityPoint Task}.
(** We assume the basic readiness model. *)
#[local] Existing Instance basic_ready_instance .
(** ** A. Defining the System Model *)
(** We begin by defining the system model. First,
we model arrivals using an arrival sequence. We assume
that the arrival is consistent and does not contain duplicates. *)
Variable arr_seq : arrival_sequence Job.
Hypothesis H_valid_arrival_sequence : valid_arrival_sequence arr_seq.
(** We consider a valid, ideal uniprocessor schedule... *)
Variable sched : schedule (ideal.processor_state Job).
Hypothesis H_sched_valid : valid_schedule sched arr_seq.
(** ... that respects the GEL policy at every preemption point. *)
Hypothesis H_respects_policy : respects_JLFP_policy_at_preemption_point arr_seq sched (GEL Job Task).
(** We assume that all arrivals have valid job costs. *)
Hypothesis H_valid_job_cost :
arrivals_have_valid_job_costs arr_seq.
(** We model the tasks in the system using a task set [ts].
We assume that all jobs in the system come from this task set. *)
Variable ts : list Task.
Hypothesis H_all_jobs_from_taskset : all_jobs_from_taskset arr_seq ts.
(** We assume that the task set respects the arrival curve
defined by [max_arrivals]. *)
Hypothesis H_valid_arrival_curve : valid_taskset_arrival_curve ts max_arrivals.
Hypothesis H_is_arrival_curve : taskset_respects_max_arrivals arr_seq ts.
(** The task under consideration [tsk] is contained in [ts]. *)
Variable tsk : Task.
Hypothesis H_tsk_in_ts : tsk \in ts.
(** While we do not assume an explicit preemption model,
we assume that any preemption model under consideration
is valid. We also assume that the run-to-completion-threshold
of the task [tsk] is valid. *)
Hypothesis H_valid_preemption_model :
valid_preemption_model arr_seq sched.
Hypothesis H_valid_run_to_completion_threshold :
valid_task_run_to_completion_threshold arr_seq tsk.
(** As mentioned, we assume that the priority inversion for the task
[tsk] is bound by [priority_inversion_bound]. *)
Variable priority_inversion_bound : duration -> duration.
Hypothesis H_priority_inversion_is_bounded :
priority_inversion_is_bounded_by arr_seq sched tsk priority_inversion_bound.
(** ** B. Encoding the Scheduling Policy and Preemption Model *)
(** Next, we encode the scheduling policy and preemption model using
the functions [interference] and [interfering_workload]. To this
end, we simply reuse the general definitions of interference and
interfering workload that apply to any JLFP policy, as defined
in the module [analysis.abstract.ideal.iw_instantiation]. *)
#[local] Instance ideal_jlfp_interference : Interference Job :=
ideal_jlfp_interference arr_seq sched.
#[local] Instance ideal_jlfp_interfering_workload : InterferingWorkload Job :=
ideal_jlfp_interfering_workload arr_seq sched.
(** ** C. Abstract Work Conservation *)
(** Let us recall the abstract and classic notations of work conservation. *)
Let work_conserving_ab := definitions.work_conserving arr_seq sched.
Let work_conserving_cl := work_conserving.work_conserving arr_seq sched.
(** We assume that the schedule is work-conserving in the classic sense,
which allows us to apply [instantiated_i_and_w_are_coherent_with_schedule]
to conclude that abstract work-conservation also holds. *)
Hypothesis H_work_conserving : work_conserving_cl.
(** ** D. Bounding the Maximum Busy-Window Length *)
(** Next, we define [L] as the fixed point of the given equation.
Given this definition of [L], we can apply the theorem
[instantiated_busy_intervals_are_bounded] to prove that [L]
bounds the length of the busy window. *)
Variable L : duration.
Hypothesis H_L_positive : L > 0 .
Hypothesis H_fixed_point : L = total_request_bound_function ts L.
(** ** E. Defining [task_IBF] *)
(** Next, we define [task_IBF] and prove that [task_IBF] bounds
the interference incurred by any job of [tsk]. *)
(** Consider the following parametrized interval. *)
Let interval (tsk_o : Task) (A : instant):=
((A + ε)%:R + task_priority_point tsk - task_priority_point tsk_o)%R.
(** We define the bound on the total higher-or-equal-priority (HEP) workload
produced during the interval [Δ] as the sum of the RBFs of all tasks in
the task set [ts] (excluding [tsk]) over the minimum of [Δ] and [interval]. *)
Let bound_on_total_hep_workload (A Δ : duration) :=
\sum_(tsk_o <- ts | tsk_o != tsk)
task_request_bound_function tsk_o (minn `|Num.max 0 %R (interval tsk_o A)| Δ).
(** Finally, [task_IBF] for an interval [R] is defined as the sum of
[bound_on_total_hep_workload] in [R] and [priority_inversion_bound]. *)
Let task_IBF (A R : duration) := priority_inversion_bound A + bound_on_total_hep_workload A R.
(** For convenience, we define the following acronym. *)
Let PP (task : Task) := (task_priority_point task).
(** In this section, we prove the soundness of [task_IBF]. We start
by establishing a bound on the HEP workload.*)
Section HepWorkloadBound .
(** Consider any job [j] of task [tsk] that
has a positive job cost and is in the arrival
sequence. *)
Variable j : Job.
Hypothesis H_j_arrives : arrives_in arr_seq j.
Hypothesis H_job_of_tsk : job_of_task tsk j.
Hypothesis H_job_cost_positive : job_cost_positive j.
(** Assume the busy interval of [j] is given by <<[t1,t2)>>. *)
Variable t1 t2 : duration.
Hypothesis H_busy_interval : definitions.busy_interval sched j t1 t2.
(** Assume the relative arrival time of [j] is given by [A]. *)
Let A := job_arrival j - t1.
(** Consider any arbitrary interval [Δ] within the busy window. *)
Variable Δ : duration.
Hypothesis H_Δ_in_busy : t1 + Δ < t2.
(** Consider the set of jobs arriving in <<[t1, t1 + Δ)>>. *)
Let jobs := arrivals_between arr_seq t1 (t1 + Δ).
(** We define a predicate to identify higher priority jobs coming from the task [tsk]. *)
Let GEL_from (tsk : Task) := fun (jo : Job) => hep_job jo j && (job_task jo == tsk).
(** First, consider the case where [interval ≤ Δ]. *)
Section ShortenRange .
(** Consider any task [tsk_o] distinct from [tsk].
Assume [tsk_o] is in [ts]. *)
Variable tsk_o : Task.
Hypothesis H_tsko_in_ts : tsk_o \in ts.
Hypothesis H_neq : tsk_o != tsk.
(** If [Δ] is greater than [interval] for [tsk_o] and [A], ... *)
Hypothesis H_Δ_ge : (interval tsk_o A <= Δ%:R)%R.
(** ... then the workload of jobs satisfying the predicate [GEL_from]
in the interval <<[t1,t1 + Δ)>> is equal to the workload in
the interval <<[t1, t1 + interval [tsk_o] [A])>>.
Note that, we use the functions [Z.to_nat] to [Z.of_nat] to convert
integers to natural numbers and vice-versa. *)
Lemma total_workload_shorten_range :
workload_of_jobs (GEL_from tsk_o)
(arrivals_between arr_seq t1 (t1 + Δ))
<= workload_of_jobs (GEL_from tsk_o)
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsk_o A)%R|).Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R
workload_of_jobs (GEL_from tsk_o)
(arrivals_between arr_seq t1 (t1 + Δ)) <=
workload_of_jobs (GEL_from tsk_o)
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsk_o A)%R|)
Proof .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R
workload_of_jobs (GEL_from tsk_o)
(arrivals_between arr_seq t1 (t1 + Δ)) <=
workload_of_jobs (GEL_from tsk_o)
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsk_o A)%R|)
have BOUNDED: `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <= t1 + Δ by lia .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ
workload_of_jobs (GEL_from tsk_o)
(arrivals_between arr_seq t1 (t1 + Δ)) <=
workload_of_jobs (GEL_from tsk_o)
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsk_o A)%R|)
rewrite (workload_of_jobs_nil_tail _ _ BOUNDED) // => j' IN' ARR'.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) ARR' : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
job_arrival j'
~~ GEL_from tsk_o j'
rewrite /GEL_from.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) ARR' : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
job_arrival j'
~~ (hep_job j' j && (job_task j' == tsk_o))
case : (eqVneq (job_task j') tsk_o) => TSK'; last by rewrite andbF.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) ARR' : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
job_arrival j' TSK' : job_task j' = tsk_o
~~ (hep_job j' j && true)
rewrite andbT; apply : contraT => /negPn HEP.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) ARR' : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
job_arrival j' TSK' : job_task j' = tsk_o HEP : hep_job j' j
false
move : (hep_job_arrives_after_zero _ j' HEP) => GT0.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) ARR' : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
job_arrival j' TSK' : job_task j' = tsk_o HEP : hep_job j' j GT0 : (0 <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R
false
move : (hep_job_arrives_before _ j' HEP) => EARLIEST.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) ARR' : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
job_arrival j' TSK' : job_task j' = tsk_o HEP : hep_job j' j GT0 : (0 <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R EARLIEST : ((job_arrival j')%:R <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R
false
move : H_job_of_tsk; rewrite /job_of_task => /eqP TSK.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) ARR' : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
job_arrival j' TSK' : job_task j' = tsk_o HEP : hep_job j' j GT0 : (0 <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R EARLIEST : ((job_arrival j')%:R <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R TSK : job_task j = tsk
false
move : ARR'; rewrite /interval => LATEST.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) TSK' : job_task j' = tsk_o HEP : hep_job j' j GT0 : (0 <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R EARLIEST : ((job_arrival j')%:R <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R TSK : job_task j = tsk LATEST : `|Num.max 0 %R
(t1%:R +
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o))%R| <=
job_arrival j'
false
have LATEST': ((t1 + A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o <= (job_arrival j')%:R)%R by lia .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsk_o : Task H_tsko_in_ts : tsk_o \in ts H_neq : tsk_o != tsk H_Δ_ge : (interval tsk_o A <= Δ%:R)%R BOUNDED : `|Num.max 0 %R (t1%:R + interval tsk_o A)%R| <=
t1 + Δ j' : Job IN' : j' \in arrivals_between arr_seq t1 (t1 + Δ) TSK' : job_task j' = tsk_o HEP : hep_job j' j GT0 : (0 <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R EARLIEST : ((job_arrival j')%:R <=
(job_arrival j)%:R +
task_priority_point (job_task j) -
task_priority_point (job_task j'))%R TSK : job_task j = tsk LATEST : `|Num.max 0 %R
(t1%:R +
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o))%R| <=
job_arrival j' LATEST' : ((t1 + A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o <=
(job_arrival j')%:R)%R
false
by move : LATEST'; rewrite -TSK -TSK' => LATEST'; lia .
Qed .
End ShortenRange .
(** Using the above lemma, we prove that [bound_on_total_hep_workload]
bounds the sum of higher-priority workload over all tasks in [ts]. *)
Corollary sum_of_workloads_is_at_most_bound_on_total_hep_workload :
\sum_(tsk_o <- ts | tsk_o != tsk) workload_of_jobs (GEL_from tsk_o) jobs
<= bound_on_total_hep_workload A Δ.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool
\sum_(tsk_o <- ts | tsk_o != tsk)
workload_of_jobs (GEL_from tsk_o) jobs <=
bound_on_total_hep_workload A Δ
Proof .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool
\sum_(tsk_o <- ts | tsk_o != tsk)
workload_of_jobs (GEL_from tsk_o) jobs <=
bound_on_total_hep_workload A Δ
apply leq_sum_seq => tsko INtsko NEQT.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk
workload_of_jobs (GEL_from tsko) jobs <=
task_request_bound_function tsko
(minn `|Num.max 0 %R (interval tsko A)| Δ)
have [EQ|EQ] := leqP Δ `|Num.max 0 %R (interval tsko A)|.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : Δ <= `|Num.max 0 %R (interval tsko A)|
workload_of_jobs (GEL_from tsko) jobs <=
task_request_bound_function tsko Δ
{ Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : Δ <= `|Num.max 0 %R (interval tsko A)|
workload_of_jobs (GEL_from tsko) jobs <=
task_request_bound_function tsko Δ
exact : (workload_le_rbf' arr_seq tsko). } Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : `|Num.max 0 %R (interval tsko A)| < Δ
workload_of_jobs (GEL_from tsko) jobs <=
task_request_bound_function tsko
`|Num.max 0 %R (interval tsko A)|
apply : (leq_trans (total_workload_shorten_range _ _ _ _)) => //; [lia |].Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : `|Num.max 0 %R (interval tsko A)| < Δ
workload_of_jobs (GEL_from tsko)
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsko A)%R|) <=
task_request_bound_function tsko
`|Num.max 0 %R (interval tsko A)|
rewrite /GEL_from.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : `|Num.max 0 %R (interval tsko A)| < Δ
workload_of_jobs
(fun jo : Job =>
hep_job jo j && (job_task jo == tsko))
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsko A)%R|) <=
task_request_bound_function tsko
`|Num.max 0 %R (interval tsko A)|
have [EQ1|EQ1] := lerP 0 %R (interval tsko A).Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : `|Num.max 0 %R (interval tsko A)| < Δ EQ1 : (0 <= interval tsko A)%R
workload_of_jobs
(fun jo : Job =>
hep_job jo j && (job_task jo == tsko))
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsko A)%R|) <=
task_request_bound_function tsko `|interval tsko A|
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : `|Num.max 0 %R (interval tsko A)| < Δ EQ1 : (0 <= interval tsko A)%R
workload_of_jobs
(fun jo : Job =>
hep_job jo j && (job_task jo == tsko))
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsko A)%R|) <=
task_request_bound_function tsko `|interval tsko A|
have -> : `|Num.max 0 %R (t1%:R + interval tsko A)%R|
= t1 + `|interval tsko A| by lia .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : `|Num.max 0 %R (interval tsko A)| < Δ EQ1 : (0 <= interval tsko A)%R
workload_of_jobs
(fun jo : Job =>
hep_job jo j && (job_task jo == tsko))
(arrivals_between arr_seq t1
(t1 + `|interval tsko A|)) <=
task_request_bound_function tsko `|interval tsko A|
exact : workload_le_rbf'.
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset j : Job H_j_arrives : arrives_in arr_seq j H_job_of_tsk : job_of_task tsk j H_job_cost_positive : job_cost_positive j t1, t2 : duration H_busy_interval : definitions.busy_interval sched j t1
t2 A := job_arrival j - t1 : nat Δ : duration H_Δ_in_busy : t1 + Δ < t2 jobs := arrivals_between arr_seq t1 (t1 + Δ) : seq Job GEL_from := fun (tsk : Task) (jo : Job) =>
hep_job jo j && (job_task jo == tsk): Task -> Job -> bool tsko : Task INtsko : tsko \in ts NEQT : tsko != tsk EQ : `|Num.max 0 %R (interval tsko A)| < Δ EQ1 : (interval tsko A < 0 )%R
workload_of_jobs
(fun jo : Job =>
hep_job jo j && (job_task jo == tsko))
(arrivals_between arr_seq t1
`|Num.max 0 %R (t1%:R + interval tsko A)%R|) <=
task_request_bound_function tsko `|0 %R|
rewrite arrivals_between_geq /workload_of_jobs ?big_nil //; lia .
Qed .
End HepWorkloadBound .
(** Finally, we prove that [task_IBF] bounds the interference incurred by [tsk]. *)
Corollary instantiated_task_interference_is_bounded :
task_interference_is_bounded_by
arr_seq sched tsk task_IBF.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset
task_interference_is_bounded_by arr_seq sched tsk
task_IBF
Proof .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset
task_interference_is_bounded_by arr_seq sched tsk
task_IBF
move => t1 t2 Δ j ARR TSK BUSY LT NCOMPL A OFF.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) A : nat OFF : relative_arrival_time_of_job_is_A sched j A
cumul_cond_interference (nonself arr_seq sched) j t1
(t1 + Δ) <= task_IBF A Δ
move : (OFF _ _ BUSY) => EQA; subst A.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1)
cumul_cond_interference (nonself arr_seq sched) j t1
(t1 + Δ) <= task_IBF (job_arrival j - t1) Δ
move : (posnP (@job_cost _ Cost j)) => [ZERO|POS].Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) ZERO : job_cost j = 0
cumul_cond_interference (nonself arr_seq sched) j t1
(t1 + Δ) <= task_IBF (job_arrival j - t1) Δ
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) ZERO : job_cost j = 0
cumul_cond_interference (nonself arr_seq sched) j t1
(t1 + Δ) <= task_IBF (job_arrival j - t1) Δ
exfalso ; move : NCOMPL => /negP COMPL; apply : COMPL.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) ZERO : job_cost j = 0
completed_by sched j (t1 + Δ)
by rewrite /completed_by /completed_by ZERO.
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
cumul_cond_interference (nonself arr_seq sched) j t1
(t1 + Δ) <= task_IBF (job_arrival j - t1) Δ
rewrite -/(cumul_task_interference _ _ _ _ _).Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
cumul_task_interference arr_seq sched j t1 (t1 + Δ) <=
task_IBF (job_arrival j - t1) Δ
rewrite (leqRW (cumulative_task_interference_split _ _ _ _ _ _ _ _ _ _ _ _ _)) //=.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
cumulative_priority_inversion arr_seq sched j t1
(t1 + Δ) +
cumulative_another_task_hep_job_interference arr_seq
sched j t1 (t1 + Δ) <=
task_IBF (job_arrival j - t1) Δ
rewrite /I leq_add //.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
cumulative_priority_inversion arr_seq sched j t1
(t1 + Δ) <=
priority_inversion_bound (job_arrival j - t1)
+ Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
cumulative_priority_inversion arr_seq sched j t1
(t1 + Δ) <=
priority_inversion_bound (job_arrival j - t1)
exact : cumulative_priority_inversion_is_bounded.
+ Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
cumulative_another_task_hep_job_interference arr_seq
sched j t1 (t1 + Δ) <=
bound_on_total_hep_workload (job_arrival j - t1) Δ
eapply leq_trans; first exact : cumulative_interference_is_bounded_by_total_service.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
service_of_jobs sched (another_task_hep_job^~ j)
(arrivals_between arr_seq t1 (t1 + Δ)) t1 (t1 + Δ) <=
bound_on_total_hep_workload (job_arrival j - t1) Δ
eapply leq_trans; first exact : service_of_jobs_le_workload.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
workload_of_jobs (another_task_hep_job^~ j)
(arrivals_between arr_seq t1 (t1 + Δ)) <=
bound_on_total_hep_workload (job_arrival j - t1) Δ
eapply leq_trans.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
workload_of_jobs (another_task_hep_job^~ j)
(arrivals_between arr_seq t1 (t1 + Δ)) <= ?n
* Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
workload_of_jobs (another_task_hep_job^~ j)
(arrivals_between arr_seq t1 (t1 + Δ)) <= ?n
eapply reorder_summation; eauto 2 => j' IN _.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost jj' : Job IN : j' \in arrivals_between arr_seq t1 (t1 + Δ)
job_task j' \in ?ys
by apply H_all_jobs_from_taskset; eapply in_arrivals_implies_arrived; exact IN.
* Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j TSK : job_of_task tsk j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost j
\sum_(y <- ts | y != job_task j)
\sum_(x <- arrivals_between arr_seq t1 (t1 + Δ) |
(hep_job^~ j) x && (job_task x == y)) job_cost x <=
bound_on_total_hep_workload (job_arrival j - t1) Δ
move : TSK => /eqP TSK; rewrite TSK.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost jTSK : job_task j = tsk
\sum_(y <- ts | y != tsk)
\sum_(x <- arrivals_between arr_seq t1 (t1 + Δ) |
hep_job x j && (job_task x == y)) job_cost x <=
bound_on_total_hep_workload (job_arrival j - t1) Δ
eapply sum_of_workloads_is_at_most_bound_on_total_hep_workload; eauto 2 .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset t1, t2 : instant Δ : nat j : Job ARR : arrives_in arr_seq j BUSY : definitions.busy_interval sched j t1 t2 LT : t1 + Δ < t2 NCOMPL : ~~ completed_by sched j (t1 + Δ) OFF : relative_arrival_time_of_job_is_A sched j
(job_arrival j - t1) POS : 0 < job_cost jTSK : job_task j = tsk
job_of_task tsk j
by apply /eqP.
Qed .
(** ** F. Defining the Search Space *)
(** In this section, we define the concrete search space for [GEL].
Then, we prove that, if a given [A] is in the abstract search space,
then it is also included in the concrete search space. *)
(** In order to define the concrete search space, we
define the predicates [task_rbf_changes_at], ... *)
Definition task_rbf_changes_at (A : duration) :=
task_request_bound_function tsk A != task_request_bound_function tsk (A + ε).
(** ... [bound_on_total_hep_workload_changes_at], ... *)
Definition bound_on_total_hep_workload_changes_at A :=
has (fun tsko =>
((tsk != tsko) && (interval tsko (A - ε) != interval tsko A)))
ts.
(** ... and [priority_inversion_changes_at]. *)
Definition priority_inversion_changes_at (A : duration) :=
priority_inversion_bound (A - ε) != priority_inversion_bound A.
(** Finally, we define the concrete search space as the set containing
all points less than [L] at which any of the bounds on priority inversion, task [rbf],
or bound on total HEP workload changes. *)
Definition is_in_search_space (A : duration) :=
(A < L) && (priority_inversion_changes_at A
|| task_rbf_changes_at A
|| bound_on_total_hep_workload_changes_at A).
(** In this section, we prove that for any job [j] of [tsk],
if [A] is in the abstract search space, then it is also in
the concrete search space. *)
Section ConcreteSearchSpace .
(** To rule out pathological cases with the concrete search space,
we assume that the task cost is positive and the arrival curve
is non-pathological. *)
Hypothesis H_task_cost_pos : 0 < task_cost tsk.
Hypothesis H_arrival_curve_pos : 0 < max_arrivals tsk ε.
(** For [j], the total interference bound is defined as follows. *)
Let total_interference_bound (A Δ : duration) :=
task_request_bound_function tsk (A + ε) - task_cost tsk + task_IBF A Δ.
(** Consider any point [A] in the abstract search space. *)
Variable A : duration.
Hypothesis H_A_is_in_abstract_search_space :
search_space.is_in_search_space L total_interference_bound A.
(** Then, [A] is also in the concrete search space. *)
Lemma A_is_in_concrete_search_space :
is_in_search_space A.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A
is_in_search_space A
Proof .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A
is_in_search_space A
move : H_A_is_in_abstract_search_space => [-> | [/andP [POSA LTL] [x [LTx INSP2]]]];
apply /andP; split => //.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A
priority_inversion_changes_at 0
|| task_rbf_changes_at 0
|| bound_on_total_hep_workload_changes_at 0
{ Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A
priority_inversion_changes_at 0
|| task_rbf_changes_at 0
|| bound_on_total_hep_workload_changes_at 0
apply /orP; left ; apply /orP; right .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A
task_rbf_changes_at 0
rewrite /task_rbf_changes_at task_rbf_0_zero // eq_sym -lt0n add0n.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A
0 < task_request_bound_function tsk 1
by apply task_rbf_epsilon_gt_0 => //.
} Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x
priority_inversion_changes_at A
|| task_rbf_changes_at A
|| bound_on_total_hep_workload_changes_at A
apply contraT; rewrite !negb_or => /andP [/andP [/negPn/eqP PI /negPn/eqP RBF] WL].Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) WL : ~~ bound_on_total_hep_workload_changes_at A
false
exfalso ; apply INSP2.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) WL : ~~ bound_on_total_hep_workload_changes_at A
total_interference_bound (A - 1 ) x =
total_interference_bound A x
rewrite /total_interference_bound subnK // RBF.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) WL : ~~ bound_on_total_hep_workload_changes_at A
task_request_bound_function tsk (A + 1 ) -
task_cost tsk + task_IBF (A - 1 ) x =
task_request_bound_function tsk (A + 1 ) -
task_cost tsk + task_IBF A x
apply /eqP; rewrite eqn_add2l /task_IBF PI eqn_add2l.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) WL : ~~ bound_on_total_hep_workload_changes_at A
bound_on_total_hep_workload (A - 1 ) x ==
bound_on_total_hep_workload A x
rewrite /bound_on_total_hep_workload.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) WL : ~~ bound_on_total_hep_workload_changes_at A
\sum_(tsk_o <- ts | tsk_o != tsk)
task_request_bound_function tsk_o
(minn `|Num.max 0 %R (interval tsk_o (A - 1 ))| x) ==
\sum_(tsk_o <- ts | tsk_o != tsk)
task_request_bound_function tsk_o
(minn `|Num.max 0 %R (interval tsk_o A)| x)
apply /eqP; rewrite big_seq_cond [RHS]big_seq_cond.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) WL : ~~ bound_on_total_hep_workload_changes_at A
\sum_(i <- ts | (i \in ts) && (i != tsk))
task_request_bound_function i
(minn `|Num.max 0 %R (interval i (A - 1 ))| x) =
\sum_(i <- ts | (i \in ts) && (i != tsk))
task_request_bound_function i
(minn `|Num.max 0 %R (interval i A)| x)
apply eq_big => // tsk_i /andP [TS OTHER].Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) WL : ~~ bound_on_total_hep_workload_changes_at A tsk_i : Task TS : tsk_i \in ts OTHER : tsk_i != tsk
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i (A - 1 ))| x) =
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i A)| x)
move : WL; rewrite /bound_on_total_hep_workload_changes_at => /hasPn WL.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) tsk_i : Task TS : tsk_i \in ts OTHER : tsk_i != tsk WL : {in ts,
forall x : Task,
~~
((tsk != x) &&
(interval x (A - 1 ) != interval x A))}
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i (A - 1 ))| x) =
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i A)| x)
move : {WL} (WL tsk_i TS) => /nandP [/negPn/eqP EQ|/negPn/eqP WL].Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) tsk_i : Task TS : tsk_i \in ts OTHER : tsk_i != tsk EQ : tsk = tsk_i
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i (A - 1 ))| x) =
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i A)| x)
{ Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) tsk_i : Task TS : tsk_i \in ts OTHER : tsk_i != tsk EQ : tsk = tsk_i
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i (A - 1 ))| x) =
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i A)| x)
by move : OTHER; rewrite EQ => /neqP. } Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) tsk_i : Task TS : tsk_i \in ts OTHER : tsk_i != tsk WL : interval tsk_i (A - 1 ) = interval tsk_i A
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i (A - 1 ))| x) =
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i A)| x)
have [leq_x|gtn_x] := leqP `|Num.max 0 %R (interval tsk_i A)| x.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) tsk_i : Task TS : tsk_i \in ts OTHER : tsk_i != tsk WL : interval tsk_i (A - 1 ) = interval tsk_i A leq_x : `|Num.max 0 %R (interval tsk_i A)| <= x
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i (A - 1 ))| x) =
task_request_bound_function tsk_i
`|Num.max 0 %R (interval tsk_i A)|
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) tsk_i : Task TS : tsk_i \in ts OTHER : tsk_i != tsk WL : interval tsk_i (A - 1 ) = interval tsk_i A leq_x : `|Num.max 0 %R (interval tsk_i A)| <= x
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i (A - 1 ))| x) =
task_request_bound_function tsk_i
`|Num.max 0 %R (interval tsk_i A)|
by rewrite WL (minn_idPl leq_x).
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset H_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : duration H_A_is_in_abstract_search_space : search_space.is_in_search_space
L
total_interference_bound
A POSA : 0 < ALTL : A < L x : nat LTx : x < L INSP2 : total_interference_bound (A - 1 ) x <>
total_interference_bound A x PI : priority_inversion_bound (A - 1 ) =
priority_inversion_bound A RBF : task_request_bound_function tsk A =
task_request_bound_function tsk (A + 1 ) tsk_i : Task TS : tsk_i \in ts OTHER : tsk_i != tsk WL : interval tsk_i (A - 1 ) = interval tsk_i A gtn_x : x < `|Num.max 0 %R (interval tsk_i A)|
task_request_bound_function tsk_i
(minn `|Num.max 0 %R (interval tsk_i (A - 1 ))| x) =
task_request_bound_function tsk_i x
by rewrite WL (minn_idPr (ltnW gtn_x)).
Qed .
End ConcreteSearchSpace .
(** ** G. Stating the Response-Time Bound [R] *)
(** Finally, we define the response-time bound [R] as follows. *)
Variable R : duration.
Hypothesis H_R_is_maximum :
forall (A : duration),
is_in_search_space A ->
exists (F : duration),
A + F >= priority_inversion_bound A
+ (task_request_bound_function tsk (A + ε) - (task_cost tsk - task_rtct tsk))
+ bound_on_total_hep_workload A (A + F) /\
R >= F + (task_cost tsk - task_rtct tsk).
Section ResponseTimeReccurence .
(** In order to connect the concrete definition of [R]
with the shape of response-time bound equation that aRTA expects,
we prove the theorem [correct_search_space]. *)
(** To rule out pathological cases with the concrete search space,
we assume that the task cost is positive and the arrival curve
is non-pathological. *)
Hypothesis H_task_cost_pos : 0 < task_cost tsk.
Hypothesis H_arrival_curve_pos : 0 < max_arrivals tsk ε.
(** We define the total interference as defined above. *)
Let total_interference_bound (A Δ : duration) :=
task_request_bound_function tsk (A + ε) - task_cost tsk + task_IBF A Δ.
(** We know that if [A] is in the abstract search then it is in the concrete search space.
We also know that if [A] is in the concrete search space then there exists an [R] that
satisfies [H_R_is_maximum]. Using these facts, here we prove that if [A]
is in the abstract search space then, there exists a solution to the response-time
equation as stated in the aRTA. *)
Corollary correct_search_space :
forall A ,
search_space.is_in_search_space L total_interference_bound A ->
exists F ,
A + F >= task_request_bound_function tsk (A + ε) - (task_cost tsk - task_rtct tsk) +
task_IBF A (A + F) /\ R >= F + (task_cost tsk - task_rtct tsk).Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
RH_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat
forall A : nat,
search_space.is_in_search_space L
total_interference_bound A ->
exists F : nat,
task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk) + task_IBF A (A + F) <=
A + F /\ F + (task_cost tsk - task_rtct tsk) <= R
Proof .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
RH_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat
forall A : nat,
search_space.is_in_search_space L
total_interference_bound A ->
exists F : nat,
task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk) + task_IBF A (A + F) <=
A + F /\ F + (task_cost tsk - task_rtct tsk) <= R
move => A IN.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
RH_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : nat IN : search_space.is_in_search_space L
total_interference_bound A
exists F : nat,
task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk) + task_IBF A (A + F) <=
A + F /\ F + (task_cost tsk - task_rtct tsk) <= R
edestruct H_R_is_maximum as [F [FIX NEQ]];
first by eapply A_is_in_concrete_search_space => //.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
RH_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : nat IN : search_space.is_in_search_space L
total_interference_bound A F : duration FIX : priority_inversion_bound A +
(task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A (A + F) <=
A + F NEQ : F + (task_cost tsk - task_rtct tsk) <= R
exists F : nat,
task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk) + task_IBF A (A + F) <=
A + F /\ F + (task_cost tsk - task_rtct tsk) <= R
exists F ; split => [|//].Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
RH_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : nat IN : search_space.is_in_search_space L
total_interference_bound A F : duration FIX : priority_inversion_bound A +
(task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A (A + F) <=
A + F NEQ : F + (task_cost tsk - task_rtct tsk) <= R
task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk) + task_IBF A (A + F) <=
A + F
rewrite -{2 }(leqRW FIX).Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
RH_task_cost_pos : 0 < task_cost tskH_arrival_curve_pos : 0 < max_arrivals tsk 1 total_interference_bound := fun A Δ : duration =>
task_request_bound_function
tsk (A + 1 ) -
task_cost tsk +
task_IBF A Δ: duration -> duration -> nat A : nat IN : search_space.is_in_search_space L
total_interference_bound A F : duration FIX : priority_inversion_bound A +
(task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A (A + F) <=
A + F NEQ : F + (task_cost tsk - task_rtct tsk) <= R
task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk) + task_IBF A (A + F) <=
priority_inversion_bound A +
(task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A (A + F)
by rewrite addnA [_ + priority_inversion_bound A]addnC -!addnA.
Qed .
End ResponseTimeReccurence .
(** ** H. Soundness of the Response-Time Bound *)
(** Finally, we prove that [R] is a bound on the response time of the
task [tsk]. *)
Theorem uniprocessor_response_time_bound_edf :
task_response_time_bound arr_seq sched tsk R.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
R
task_response_time_bound arr_seq sched tsk R
Proof .Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
R
task_response_time_bound arr_seq sched tsk R
move => js ARRs TSKs.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js
job_response_time_bound sched js R
move : (posnP (@job_cost _ Cost js)) => [ZERO|POS].Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js ZERO : job_cost js = 0
job_response_time_bound sched js R
{ Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js ZERO : job_cost js = 0
job_response_time_bound sched js R
by rewrite /job_response_time_bound /completed_by ZERO. } Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js POS : 0 < job_cost js
job_response_time_bound sched js R
eapply uniprocessor_response_time_bound_seq with
(task_IBF := task_IBF) (L := L) => //.Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js POS : 0 < job_cost js
work_conserving arr_seq sched
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js POS : 0 < job_cost js
work_conserving arr_seq sched
exact : instantiated_i_and_w_are_coherent_with_schedule.
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js POS : 0 < job_cost js
sequential_tasks arr_seq sched
exact : GEL_implies_sequential_tasks.
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js POS : 0 < job_cost js
interference_and_workload_consistent_with_sequential_tasks
arr_seq sched tsk
exact : instantiated_interference_and_workload_consistent_with_sequential_tasks.
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js POS : 0 < job_cost js
busy_intervals_are_bounded_by arr_seq sched tsk L
exact : instantiated_busy_intervals_are_bounded.
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js POS : 0 < job_cost js
task_interference_is_bounded_by arr_seq sched tsk
task_IBF
exact : instantiated_task_interference_is_bounded.
- Task : TaskType H : TaskCost Task H0 : TaskRunToCompletionThreshold Task H1 : TaskMaxNonpreemptiveSegment Task H2 : MaxArrivals Task Job : JobType H3 : JobTask Job Task Arrival : JobArrival Job Cost : JobCost Job H4 : JobPreemptable Job H5 : PriorityPoint Task arr_seq : arrival_sequence Job H_valid_arrival_sequence : valid_arrival_sequence
arr_seq sched : schedule (ideal.processor_state Job) H_sched_valid : valid_schedule sched arr_seq H_respects_policy : respects_JLFP_policy_at_preemption_point
arr_seq sched (GEL Job Task) H_valid_job_cost : arrivals_have_valid_job_costs
arr_seq ts : seq Task H_all_jobs_from_taskset : all_jobs_from_taskset
arr_seq ts H_valid_arrival_curve : valid_taskset_arrival_curve ts
max_arrivals H_is_arrival_curve : taskset_respects_max_arrivals
arr_seq ts tsk : Task H_tsk_in_ts : tsk \in ts H_valid_preemption_model : valid_preemption_model
arr_seq sched H_valid_run_to_completion_threshold : valid_task_run_to_completion_threshold
arr_seq tsk priority_inversion_bound : duration -> duration H_priority_inversion_is_bounded : priority_inversion_is_bounded_by
arr_seq sched tsk
priority_inversion_bound work_conserving_ab := work_conserving arr_seq sched : Prop work_conserving_cl := work_conserving.work_conserving
arr_seq sched : Prop H_work_conserving : work_conserving_cl L : duration H_L_positive : 0 < LH_fixed_point : L = total_request_bound_function ts L interval := fun (tsk_o : Task) (A : instant) =>
((A + 1 )%:R + task_priority_point tsk -
task_priority_point tsk_o)%R: Task ->
instant ->
ssrint_int__canonical__GRing_SemiRing bound_on_total_hep_workload := fun A Δ : duration =>
\sum_(tsk_o <- ts |
tsk_o != tsk)
task_request_bound_function
tsk_o
(minn
`|
Num.max 0 %R
(interval tsk_o A)|
Δ): duration ->
duration -> nat task_IBF := fun A R : duration =>
priority_inversion_bound A +
bound_on_total_hep_workload A R: duration -> duration -> nat PP := [eta task_priority_point] : Task -> offset R : duration H_R_is_maximum : forall A : duration,
is_in_search_space A ->
exists F : duration,
priority_inversion_bound A +
(task_request_bound_function tsk
(A + 1 ) -
(task_cost tsk - task_rtct tsk)) +
bound_on_total_hep_workload A
(A + F) <=
A + F /\
F + (task_cost tsk - task_rtct tsk) <=
Rjs : Job ARRs : arrives_in arr_seq js TSKs : job_of_task tsk js POS : 0 < job_cost js
forall A : duration,
search_space.is_in_search_space L
(fun A0 Δ : duration =>
task_request_bound_function tsk (A0 + 1 ) -
task_cost tsk + task_IBF A0 Δ) A ->
exists F : duration,
task_request_bound_function tsk (A + 1 ) -
(task_cost tsk - task_rtct tsk) + task_IBF A (A + F) <=
A + F /\ F + (task_cost tsk - task_rtct tsk) <= R
exact : correct_search_space.
Qed .
End AbstractRTAforGELwithArrivalCurves .