Library prosa.analysis.facts.preemption.job.limited

Require Export prosa.model.schedule.limited_preemptive.
Require Export prosa.analysis.definitions.job_properties.
Require Export prosa.analysis.facts.behavior.all.
Require Export prosa.analysis.facts.model.sequential.
Require Export prosa.analysis.facts.model.ideal_schedule.

Throughout this file, we assume the job model with limited preemption points.

Require Import prosa.model.preemption.limited_preemptive.

Platform for Models with Limited Preemptions

In this section, we prove that instantiation of predicate job_preemptable to the model with limited preemptions indeed defines a valid preemption model.

Section ModelWithLimitedPreemptions.

Consider any type of tasks ...

Context {Task : TaskType}.
Context `{TaskCost Task}.

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

  Context {Job : JobType}.
  Context `{JobTask Job Task}.
  Context `{JobArrival Job}.
  Context `{JobCost Job}.

In addition, assume the existence of a function that maps a job to the sequence of its preemption points.

Context `{JobPreemptionPoints Job}.

Consider any arrival sequence.

Variable arr_seq : arrival_sequence Job.

Next, consider any limited ideal uni-processor schedule of this arrival sequence ...

  Variable sched : schedule (ideal.processor_state Job).
  Hypothesis H_schedule_respects_preemption_model:
    schedule_respects_preemption_model arr_seq sched.

...where jobs do not execute after their completion.

Hypothesis H_completed_jobs_dont_execute: completed_jobs_dont_execute sched.

Next, we assume that preemption points are defined by the job-level model with limited preemptions.

Hypothesis H_valid_limited_preemptions_job_model:
valid_limited_preemptions_job_model arr_seq.

First, we prove a few auxiliary lemmas.

Section AuxiliaryLemmas.

Consider a job j.

Variable j : Job.
Hypothesis H_j_arrives : arrives_in arr_seq j.

Recall that 0 is a preemption point.

Remark zero_in_preemption_points: 0 \in job_preemption_points j.

Using the fact that job_preemption_points is a non-decreasing sequence, we prove that the first element of job_preemption_points is 0.

Lemma zero_is_first_element: first0 (job_preemption_points j) = 0.

We prove that the list of preemption points is not empty.

Lemma list_of_preemption_point_is_not_empty:
0 < size (job_preemption_points j).

Next, we prove that the cost of a job is a preemption point.

Lemma job_cost_in_nonpreemptive_points: job_cost j \in job_preemption_points j.

As a corollary, we prove that the sequence of non-preemptive points of a job with positive cost contains at least 2 points.

    Corollary number_of_preemption_points_at_least_two:
      job_cost_positive j →
      2 ≤ size (job_preemption_points j).

Next we prove that "anti-density" property (from preemption.util file) holds for job_preemption_point j.

    Lemma antidensity_of_preemption_points:
      ∀ (ρ : work),
        ρ ≤ job_cost j →
        ~~ (ρ \in job_preemption_points j ) →
        first0 (job_preemption_points j) ≤ ρ < last0 (job_preemption_points j).

We also prove that any work that doesn't belong to preemption points of job j is placed strictly between two neighboring preemption points.

    Lemma work_belongs_to_some_nonpreemptive_segment:
      ∀ (ρ : work),
        ρ ≤ job_cost j →
        ~~ (ρ \in job_preemption_points j )→
        ∃ n,
          n .+1 < size (job_preemption_points j) ∧
          nth 0 (job_preemption_points j) n < ρ < nth 0 (job_preemption_points j) n .+1.

Recall that file job.parameters also defines notion of preemption points. And note that job.parameter.job_preemption_points cannot have a duplicating preemption points. Therefore, we need additional lemmas to relate job.parameter.job_preemption_points and limited.job_preemption_points].

First we show that the length of the last non-preemptive segment of job.parameter.job_preemption_points is equal to the length of the last non-empty non-preemptive segment of limited.job_preemption_points.

    Lemma job_parameters_last_np_to_job_limited:
        last0 (distances (parameter.job_preemption_points j)) =
        last0 (filter (fun x ⇒ 0 < x) (distances (job_preemption_points j))).

Next we show that the length of the max non-preemptive segment of job.parameter.job_preemption_points is equal to the length of the max non-preemptive segment of limited.job_preemption_points.

    Lemma job_parameters_max_np_to_job_limited:
      max0 (distances (parameter.job_preemption_points j)) =
      max0 (distances (job_preemption_points j)).

  End AuxiliaryLemmas.

We prove that the fixed_preemption_point_model function defines a valid preemption model.

Lemma valid_fixed_preemption_points_model_lemma:
valid_preemption_model arr_seq sched.

End ModelWithLimitedPreemptions.
Hint Resolve valid_fixed_preemption_points_model_lemma : basic_facts.