Library prosa.results.edf.rta.floating_nonpreemptive

RTA for EDF with Floating Non-Preemptive Regions

In this module we prove the RTA theorem for floating non-preemptive regions EDF model.

Setup and Assumptions

Consider any type of tasks ...
  Context {Task : TaskType}.
  Context `{TaskCost Task}.
  Context `{TaskDeadline Task}.

... and any type of jobs associated with these tasks.
  Context {Job : JobType}.
  Context `{JobTask Job Task}.
  Context `{JobArrival Job}.
  Context `{JobCost Job}.

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

We assume that jobs are limited-preemptive.
  #[local] Existing Instance limited_preemptive_job_model.

Consider any arrival sequence with consistent, non-duplicate arrivals.
Assume we have the model with floating non-preemptive regions. I.e., for each task only the length of the maximal non-preemptive segment is known and each job level is divided into a number of non-preemptive segments by inserting preemption points.
Consider an arbitrary task set ts, ...
  Variable ts : list Task.

... assume that all jobs come from this task set, ...
... and the cost of a job cannot be larger than the task cost.
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.
Let tsk be any task in ts that is to be analyzed.
  Variable tsk : Task.
  Hypothesis H_tsk_in_ts : tsk \in ts.

Next, consider any valid ideal uni-processor schedule with limited preemptions of this arrival sequence ...
Next, we assume that the schedule is a work-conserving schedule...
... and the schedule respects the policy defined by the job_preemptable function (i.e., jobs have bounded non-preemptive segments).

Total Workload and Length of Busy Interval

We introduce the abbreviation rbf for the task request bound function, which is defined as task_cost(T) × max_arrivals(T,Δ) for a task T.
Next, we introduce task_rbf as an abbreviation for the task request bound function of task tsk.
  Let task_rbf := rbf tsk.

Using the sum of individual request bound functions, we define the request bound function of all tasks (total request bound function).
We define a bound for the priority inversion caused by jobs with lower priority.
  Definition blocking_bound A :=
    \max_(tsk_other <- ts | (blocking_relevant tsk_other)
                             && (task_deadline tsk_other > task_deadline tsk + A))
     (task_max_nonpreemptive_segment tsk_other - ε).

Next, we define an upper bound on interfering workload received from jobs of other tasks with higher-than-or-equal priority.
Let L be any positive fixed point of the busy interval recurrence.
  Variable L : duration.
  Hypothesis H_L_positive : L > 0.
  Hypothesis H_fixed_point : L = total_rbf L.

Response-Time Bound

To reduce the time complexity of the analysis, recall the notion of search space.
Consider any value R, and assume that for any given arrival offset A in the search space, there is a solution of the response-time bound recurrence which is bounded by R.
  Variable R : duration.
  Hypothesis H_R_is_maximum:
     (A : duration),
      is_in_search_space A
       (F : duration),
        A + F blocking_bound A + task_rbf (A + ε) + bound_on_total_hep_workload A (A + F)
        R F.

Now, we can leverage the results for the abstract model with bounded nonpreemptive segments to establish a response-time bound for the more concrete model with floating nonpreemptive regions.