Abstract Response-Time Analysis with sequential tasks

In this section we propose the general framework for response-time analysis (RTA) of uni-processor scheduling of real-time tasks with arbitrary arrival models and sequential tasks. We prove that the maximum among the solutions of the response-time bound recurrence for some set of parameters is a response-time bound for tsk. Note that in this section we do rely on the hypothesis about task sequentiality. This allows us to provide a more precise response-time bound function, since jobs of the same task will be executed strictly in the order they arrive.

Consider any type of tasks ...

... and any type of jobs associated with these tasks.

Consider any valid arrival sequence with consistent, non-duplicate arrivals...

... and any ideal schedule of this arrival sequence.

... where jobs do not execute before their arrival nor after completion.

Assume that the job costs are no larger than the task costs.

Consider an arbitrary task set.

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

Consider a valid preemption model...

...and a valid task run-to-completion threshold function. That is, task_rtct tsk is (1) no bigger than tsk's cost, (2) for any job of task tsk job_rtct is bounded by task_rtct.

Let max_arrivals be a family of valid arrival curves, i.e., for any task tsk in ts, max_arrival tsk is (1) an arrival bound of tsk, and (2) it is a monotonic function that equals 0 for the empty interval delta = 0.

Assume we are provided with abstract functions for interference and interfering workload.

Let's define some local names for clarity.

In this section, we introduce a few new definitions to make it easier to express the new bound on the worst-case interference.

When assuming sequential tasks, we can introduce an additional hypothesis that ensures that the values of interference and workload remain consistent. It is important to note that before a busy interval of a job j of task tsk begins, both the cumulative task workload and task service must be equal within the interval [0, t1). This has an implication that a busy interval for job j cannot begin if there is another pending job of the same task tsk. This requirement makes sense only in the context of sequential tasks.

Next we introduce the notion of task interference. Intuitively, task tsk incurs interference when some of the jobs of task tsk incur interference. As a result, tsk cannot make any progress. More formally, task tsk experiences interference at a time instant time t, if at time t task tsk is not scheduled and there exists a job of tsk that (1) experiences interference and (2) has arrived before some time instant upper_bound. It is important to note two subtle points: according to our semantics of the interference function, jobs from the same task can cause interference to each other. In the definition of interference of a task we want to avoid such situations. That is why we use the term ~~ task_scheduled_at tsk t. Moreover, in order to make the definition constructive, we introduce an upper bound on the arrival time of jobs from task tsk. As a result, we need to consider only a finite number of jobs. For the function to produce the correct values it is enough to specify a sufficiently large upper_bound. Usually as upper_bound one can use the end of the corresponding busy interval.

We also define a decidable counterpart of this definition...

... and prove that the propositional and decidable definitions are equivalent.

Next we define the cumulative task interference.

We say that task interference is bounded by task_interference_bound_function (task_IBF) iff for any job j of task tsk cumulative task interference within the interval t1, t1 + R) is bounded by function [task_IBF(tsk, A, R)]. Note that this definition is almost the same as the definition of [job_interference_is_bounded_by] from the non-necessarily-sequential case. However, in this case we ignore the interference that comes from jobs from the same task.

In this section, we prove that the maximum among the solutions of the response-time bound recurrence is a response-time bound for tsk.

We assume that the schedule is work-conserving.

Unlike the previous theorem uniprocessor_response_time_bound_ideal, we assume that (1) tasks are sequential, moreover (2) functions interference and interfering_workload are consistent with the hypothesis of sequential tasks.

Assume we have a constant L that bounds the busy interval of any of tsk's jobs.

Next, we assume that task_interference_bound_function is a bound on interference incurred by the task.

Given any job j of task tsk that arrives exactly A units after the beginning of the busy interval, the bound on the total interference incurred by j within an interval of length Δ is no greater than task_rbf (A + ε) - task_cost tsk + task's IBF Δ. Note that in case of sequential tasks the bound consists of two parts: (1) the part that bounds the interference received from other jobs of task tsk -- task_rbf (A + ε) - task_cost tsk and (2) any other interference that is bounded by task_IBF(tsk, A, Δ).

Note that since we consider the modified interference bound function, the search space has also changed. One can see that the new search space is guaranteed to include any A for which task_rbf (A) ≠ task_rbf (A + ε), since this implies the fact that total_interference_bound (tsk, A, Δ) ≠ total_interference_bound (tsk, A + ε, Δ).

Consider any value R, and assume that for any relative arrival time A from the search space there is a solution F of the response-time recurrence that is bounded by R. In contrast to the formula in "non-sequential" Abstract RTA, assuming that tasks are sequential leads to a more precise response-time bound. Now we can explicitly express the interference caused by other jobs of the task under consideration. To understand the right part of the fix-point in the equation, it is helpful to note that the bound on the total interference (bound_of_total_interference) is equal to task_rbf (A + ε) - task_cost tsk + task_IBF tsk A Δ. Besides, a job must receive enough service to become non-preemptive task_lock_in_service tsk. The sum of these two quantities is exactly the right-hand side of the equation.

In this section we prove a few simple lemmas about the completion of jobs from the task considering the busy interval of the job under consideration.

Consider any two jobs j1 j2 of tsk.

Consider the busy interval [t1, t2) of job j1.

We prove that if a job from task tsk arrived before the beginning of the busy interval, then it must be completed before the beginning of the busy interval

Next we prove that if a job is pending after the beginning of the busy interval [t1, t2) then it arrives after t1.

Since we are going to use the uniprocessor_response_time_bound_ideal theorem to prove the theorem of this section, we have to show that all the hypotheses are satisfied. Namely, we need to show that hypotheses H_sequential_tasks, H_i_w_are_task_consistent and H_task_interference_is_bounded_by imply H_job_interference_is_bounded, and the fact that H_R_is_maximum_seq implies H_R_is_maximum. In this section we show that there exists a bound for cumulative interference for any job of task tsk, i.e., the hypothesis H_job_interference_is_bounded holds.

Consider any job j of tsk.

Consider the busy interval [t1, t2) of job j.

Let's define A as a relative arrival time of job j (with respect to time t1).

Consider an arbitrary time x ...

... such that t1 + x is inside the busy interval...

... and job j is not completed by time t1 + x.

In this section, we show that the cumulative interference of job j in the interval [t1, t1 + x) is bounded by the sum of the task workload in the interval t1, t1 + A + ε) and the cumulative interference of [j]'s task in the interval [t1, t1 + x). Note that the task workload is computed only on the interval [t1, t1 + A + ε). Thanks to the hypothesis about sequential tasks, jobs of task [tsk] that arrive after [t1 + A + ε] cannot interfere with [j].

We start by proving a simpler analog of the lemma that states that at any time instant t ∈ [t1, t1 + x) the sum of interference j t and scheduled_at j t is no larger than the sum of the service received by jobs of task tsk at time t and task_iterference tsk t. Next we consider 4 cases.

Consider an arbitrary time instant t ∈ [t1, t1 + x).

Assume the processor is idle at time t.

In case when the processor is idle, one can show that interference j t = 1, scheduled_at j t = 0. But since interference doesn't come from a job of task tsk task_interference tsk = 1. Which reduces to 1 ≤ 1.

Assume a job j' from another task is scheduled at time t.

If a job j' from another task is scheduled at time t, then interference j t = 1, scheduled_at j t = 0. But since interference doesn't come from a job of task tsk task_interference tsk = 1. Which reduces to 1 ≤ 1.

Assume a job j' (different from j) of task tsk is scheduled at time t.

If a job j' (different from j) of task tsk is scheduled at time t, then interference j t = 1, scheduled_at j t = 0. Moreover, since interference comes from a job of the same task task_interference tsk = 0. However, in this case service_of_jobs of tsk = 1. Which reduces to 1 ≤ 1.

Assume that job j is scheduled at time t.

If job j is scheduled at time t, then interference = 0, scheduled_at = 1, but note that service_of_jobs of tsk = 1, therefore inequality reduces to 1 ≤ 1.

We use the above case analysis to prove that any time instant t ∈ [t1, t1 + x) the sum of interference j t and scheduled_at j t is no larger than the sum of the service received by jobs of task tsk at time t and task_iterference tsk t.

Next we prove cumulative version of the lemma above.

On the other hand, the service terms in the inequality above can be upper-bound by the workload terms.

Finally, we show that the cumulative interference of job j in the interval [t1, t1 + x) is bounded by the sum of the task workload in the interval t1, t1 + A + ε) and the cumulative interference of [j]'s task in the interval <<[t1, t1 + x)>>.

In order to obtain a more convenient bound on the cumulative interference, we need to abandon the actual workload in favor of a bound that depends on task parameters only. So, we show that the actual workload of the task excluding workload of any job j is no greater than the bound on the workload excluding the cost of job j's task.

Finally, we use the lemmas above to obtain the bound on interference in terms of task_rbf and task_interference.

In this section, we prove that H_R_is_maximum_seq implies H_R_is_maximum.

Consider any job j of tsk.

For simplicity, let's define a local name for the search space.

We prove that H_R_is_maximum holds.

Finally, we apply the uniprocessor_response_time_bound theorem, and using the lemmas above, we prove that all the requirements are satisfied. So, R is a response-time bound.