Library prosa.results.ovh.fp.fully_nonpreemptive
Require Export prosa.model.job.properties.
Require Export prosa.model.composite.valid_task_arrival_sequence.
Require Export prosa.analysis.facts.readiness.sequential.
Require Export prosa.analysis.facts.model.overheads.schedule.
Require Export prosa.analysis.facts.preemption.task.nonpreemptive.
Require Export prosa.analysis.facts.preemption.rtc_threshold.nonpreemptive.
Require Export prosa.analysis.abstract.restricted_supply.task_intra_interference_bound.
Require Export prosa.analysis.abstract.restricted_supply.bounded_bi.fp.
Require Export prosa.analysis.abstract.restricted_supply.search_space.fp.
Require Export prosa.analysis.facts.model.task_cost.
Require Export prosa.analysis.facts.model.overheads.sbf.fp.
Require Export prosa.model.composite.valid_task_arrival_sequence.
Require Export prosa.analysis.facts.readiness.sequential.
Require Export prosa.analysis.facts.model.overheads.schedule.
Require Export prosa.analysis.facts.preemption.task.nonpreemptive.
Require Export prosa.analysis.facts.preemption.rtc_threshold.nonpreemptive.
Require Export prosa.analysis.abstract.restricted_supply.task_intra_interference_bound.
Require Export prosa.analysis.abstract.restricted_supply.bounded_bi.fp.
Require Export prosa.analysis.abstract.restricted_supply.search_space.fp.
Require Export prosa.analysis.facts.model.task_cost.
Require Export prosa.analysis.facts.model.overheads.sbf.fp.
RTA for Fully Non-Preemptive FP Scheduling on Uniprocessors with Overheads
Defining the System Model
- the processor model,
- tasks, jobs, and their parameters,
- the task set and the task under analysis,
- the sequence of job arrivals,
- the absence of self-suspensions,
- an arbitrary schedule of the task set, and finally,
- a supply-bound function to account for overhead-induced delays.
Processor Model
Tasks and Jobs
... and their associated jobs, where each job has a corresponding task
job_task, an execution time job_cost, and an arrival time
job_arrival.
Furthermore, assume that jobs and tasks are fully non-preemptive.
#[local] Existing Instance fully_nonpreemptive_job_model.
#[local] Existing Instance fully_nonpreemptive_task_model.
#[local] Existing Instance fully_nonpreemptive_rtc_threshold.
#[local] Existing Instance fully_nonpreemptive_task_model.
#[local] Existing Instance fully_nonpreemptive_rtc_threshold.
The Job Arrival Sequence
Variable arr_seq : arrival_sequence Job.
Hypothesis H_valid_task_arrival_sequence : valid_task_arrival_sequence ts arr_seq.
Hypothesis H_valid_task_arrival_sequence : valid_task_arrival_sequence ts arr_seq.
Additionally, we assume that all jobs in arr_seq have positive execution
costs. This requirement is not fundamental to the analysis approach itself
but reflects an artifact of the current proof structure specific to upper
bounds on the total duration of overheads.
Absence of Self-Suspensions
The Schedule
Context {FP : FP_policy Task}.
Hypothesis H_priority_is_reflexive : reflexive_task_priorities FP.
Hypothesis H_priority_is_transitive : transitive_task_priorities FP.
Hypothesis H_priority_is_reflexive : reflexive_task_priorities FP.
Hypothesis H_priority_is_transitive : transitive_task_priorities FP.
Consider a non-preemptive, work-conserving, valid uniprocessor schedule
with explicit overheads that corresponds to the given arrival sequence
arr_seq (and hence the given task set ts).
Variable sched : schedule (overheads.processor_state Job).
Hypothesis H_valid_schedule : valid_schedule sched arr_seq.
Hypothesis H_work_conserving : work_conserving arr_seq sched.
Hypothesis H_nonpreemptive_sched : nonpreemptive_schedule sched.
Hypothesis H_valid_schedule : valid_schedule sched arr_seq.
Hypothesis H_work_conserving : work_conserving arr_seq sched.
Hypothesis H_nonpreemptive_sched : nonpreemptive_schedule sched.
We assume that the schedule respects the given FP scheduling policy.
Furthermore, we require that the schedule ensures two additional
properties: jobs of the same task are executed in the order of their
arrival, ...
... and preemptions occur only when strictly required by the scheduling
policy (specifically, a job is never preempted by another job of equal
priority).
Bounding the Total Overhead Duration
Variable DB CSB CRPDB : duration.
Hypothesis H_valid_overheads_model : overhead_resource_model sched DB CSB CRPDB.
Hypothesis H_valid_overheads_model : overhead_resource_model sched DB CSB CRPDB.
To conservatively account for the maximum cumulative delay that task tsk
may experience due to scheduling overheads, we introduce an overhead
bound. This term upper-bounds the maximum cumulative duration during
which processor cycles are "lost" to dispatch, context-switch, and
preemption-related delays in a given interval.
Under FP scheduling, the bound in an interval of length Δ is determined
by the arrivals of tasks with higher-or-equal priority relative to
tsk. Up to n such arrivals can lead to at most 1 + 2n segments
without a schedule change, each potentially incurring dispatch,
context-switch, and preemption-related overhead.
We denote this bound by overhead_bound for the task under analysis
tsk.
Let overhead_bound Δ :=
(DB + CSB + CRPDB) × (1 + 2 × \sum_(tsk_o <- ts | hep_task tsk_o tsk) max_arrivals tsk_o Δ).
(DB + CSB + CRPDB) × (1 + 2 × \sum_(tsk_o <- ts | hep_task tsk_o tsk) max_arrivals tsk_o Δ).
Workload Abbreviations
Additionally, we let total_hep_rbf denote the cumulative request-bound
function w.r.t. all tasks with higher-or-equal priority ...
... and use total_ohep_rbf as an abbreviation for the cumulative
request-bound function w.r.t. all tasks with higher-or-equal priority
other than task tsk itself.
Maximum Length of a Busy Interval
Definition busy_window_recurrence_solution (L : duration) :=
L > 0
∧ L ≥ overhead_bound L
+ blocking_bound ts tsk
+ total_hep_rbf L.
L > 0
∧ L ≥ overhead_bound L
+ blocking_bound ts tsk
+ total_hep_rbf L.
Response-Time Bound
Definition rta_recurrence_solution L R :=
∀ (A : duration),
is_in_search_space tsk L A →
∃ (F : duration),
A ≤ F ≤ A + R
∧ F ≥ overhead_bound F
+ blocking_bound ts tsk
+ (rbf tsk (A + ε) - (task_cost tsk - ε))
+ total_ohep_rbf F
∧ A + R ≥ F + (overhead_bound (A + R) - overhead_bound F)
+ (task_cost tsk - ε).
∀ (A : duration),
is_in_search_space tsk L A →
∃ (F : duration),
A ≤ F ≤ A + R
∧ F ≥ overhead_bound F
+ blocking_bound ts tsk
+ (rbf tsk (A + ε) - (task_cost tsk - ε))
+ total_ohep_rbf F
∧ A + R ≥ F + (overhead_bound (A + R) - overhead_bound F)
+ (task_cost tsk - ε).
Finally, using the sequential variant of abstract restricted-supply
analysis, we establish that, given a bound on the maximum busy-window
length L, any such R is indeed a sound response-time bound for task
tsk under fully-non-preemptive fixed-priority scheduling on a unit-speed
uniprocessor subject to scheduling overheads.