RTA for FIFO Scheduling on Uniprocessors with Overheads

In the following, we derive a response-time analysis for FIFO schedulers, assuming a workload of sporadic real-time tasks, characterized by arbitrary arrival curves, executing upon a uniprocessor subject to scheduling overheads. To this end, we instantiate the sequential variant of abstract Restricted-Supply Analysis (aRSA) as provided in the prosa.analysis.abstract.restricted_supply module.

Defining the System Model

Before any formal claims can be stated, an initial setup is needed to define the system model under consideration. To this end, we next introduce and define the following notions using Prosa's standard definitions and behavioral semantics:

• 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

Consider a unit-speed uniprocessor subject to scheduling overheads.

Tasks and Jobs

Consider tasks characterized by a WCET task_cost, an arrival curve max_arrivals, and a run-to-completion threshold task_rtct, ...

... and their associated jobs, where each job has a corresponding task job_task, an execution time job_cost, an arrival time job_arrival, and a list of preemption points job_preemptable.

The Task Set and The Task Under Analysis

Consider an arbitrary task set ts, and ...

... let tsk be any task in ts that is to be analyzed.

The Job Arrival Sequence

Allow for any possible arrival sequence arr_seq consistent with the parameters of the task set ts. That is, arr_seq is a valid arrival sequence in which each job's cost is upper-bounded by its task's WCET, every job stems from a task in ts, and the number of arrivals respects each task's max_arrivals bound.

We assume that tsk is described by a valid task run-to-completion threshold. That is, there exists a task parameter task_rtct such that task_rtct tsk is

• (1) no larger than tsk's WCET, and
• (2) for any job of task tsk, the job's run-to-completion threshold job_rtct is bounded by task_rtct tsk.

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

We assume the classic (i.e., Liu & Layland) model of readiness without jitter or self-suspensions, wherein pending jobs are always ready.

The Schedule

Consider a work-conserving, valid uniprocessor schedule with explicit overheads that corresponds to the given arrival sequence arr_seq (and hence the given task set ts).

We assume that the schedule complies with some valid preemption model. Under FIFO scheduling, the specific choice of preemption model does not matter, since the resulting schedule behaves as if it were non-preemptive: jobs are executed in arrival order without preemption.

We assume that the schedule respects the FIFO scheduling policy.

Furthermore, we require that the schedule has no superfluous preemptions; that is, 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

We assume that the scheduling overheads encountered in the schedule sched are bounded by the following upper bounds:

• the maximum dispatch overhead is bounded by DB,
• the maximum context-switch overhead is bounded by CSB, and
• the maximum cache-related preemption delay is bounded by 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 FIFO scheduling, the bound in an interval of length Δ is determined by the total number of arrivals in the system. In this case, up to n such arrivals can lead to at most 1 + n segments without a schedule change, each potentially incurring dispatch, context-switch, and preemption-related overhead. Unlike JLFP and FP, FIFO does not require doubling the arrivals (i.e., 1 + 2n), because all jobs are treated uniformly and there are no preemptions caused by higher-priority jobs. We denote this bound by overhead_bound for the task under analysis tsk.

Workload Abbreviations

For brevity in the following definitions, we introduce a number of local abbreviations. We let rbf denote the task request-bound function, which is defined as task_cost(T) × max_arrivals(T,Δ) for a task T.

Maximum Length of a Busy Interval

In order to apply aRSA, we require a bound on the maximum busy-window length. To this end, let L be any positive solution of the busy-interval "recurrence" (i.e., inequality) overhead_bound L + total_RBF ts L ≤ L, as defined below. As the lemma busy_intervals_are_bounded_rs_fifo shows, under EDF scheduling, this condition is sufficient to guarantee that the maximum busy-window length is at most L, i.e., the length of any busy interval is bounded by L.

Response-Time Bound

Having established all necessary preliminaries, it is finally time to state the claimed response-time bound R. A value R is a response-time bound for task tsk if, for any given offset A in the search space (w.r.t. the busy-window bound L), the response-time bound "recurrence" (i.e., inequality) has a solution F not exceeding R.

Finally, using the abstract restricted-supply analysis, we establish that any R that satisfies the stated equation is a sound response-time bound for FIFO scheduling on a unit-speed uniprocessor subject to scheduling overheads.