Library prosa.implementation.facts.ideal_uni.preemption_aware

Properties of the Preemption-Aware Ideal Uniprocessor Scheduler

This file establishes facts about the reference model of a preemption-model-aware ideal uniprocessor scheduler.
The following results assume ideal uniprocessor schedules.
Consider any type of jobs with costs and arrival times, ...
  Context {Job : JobType} `{JobCost Job} `{JobArrival Job}.

... in the context of an ideal uniprocessor model.
Suppose we are given a valid arrival sequence of such jobs, ...
... a non-clairvoyant readiness model, ...
... and a preemption model.
  Context `{JobPreemptable Job}.

For any given job selection policy ...
... consider the schedule produced by the preemption-aware scheduler for the policy induced by choose_job.
To begin with, we establish that the preemption-aware scheduler does not induce non-work-conserving behavior.
  Section WorkConservation.

If choose_job does not voluntarily idle the processor, ...
    Hypothesis H_non_idling:
       t s,
        choose_job t s = idle_state s = [::].

... then we can establish work-conservation.
First, we observe that allocation_at yields idle_state only if there are no backlogged jobs.
    Lemma allocation_at_idle:
       sched t,
        allocation_at arr_seq choose_job sched t = idle_state
        jobs_backlogged_at arr_seq sched t = [::].

As a stepping stone, we observe that the generated schedule is idle at a time t only if there are no backlogged jobs.
    Lemma idle_schedule_no_backlogged_jobs:
       t,
        ideal_is_idle schedule t
        jobs_backlogged_at arr_seq schedule t = [::].
From the preceding fact, we conclude that the generated schedule is indeed work-conserving.
The next result establishes that the generated preemption-model-aware schedule is structurally valid, meaning all jobs stem from the arrival sequence and only ready jobs are scheduled.
  Section Validity.

First, any reasonable job selection policy will not create jobs "out of thin air," i.e., if a job is selected, it was among those given to choose from.
    Hypothesis H_chooses_from_set: t s j, choose_job t s = Some j j \in s.

Second, for the schedule to be valid, we require the notion of readiness to be consistent with the preemption model: a non-preemptive job remains ready until (at least) the end of its current non-preemptive section.
Finally, we assume the readiness model to be non-clairvoyant.
For notational convenience, recall the definition of a prefix of the schedule based on which the next decision is made.
    Let sched_prefix t :=
      if t is t'.+1 then schedule_up_to policy None t' else empty_schedule idle_state.

We begin by showing that any job in the schedule must come from the arrival sequence used to generate it.
Next, we show that any job selected by the job selection policy must be ready.
    Theorem chosen_job_is_ready:
       j t,
        choose_job t (jobs_backlogged_at arr_seq (sched_prefix t) t) == Some j
        job_ready schedule j t.

Starting from the previous result we show that, at any instant, only a ready job can be scheduled.
Finally, we show that the generated schedule is valid.
    Theorem np_schedule_valid:
      valid_schedule schedule arr_seq.

  End Validity.

Next, we observe that the resulting schedule is consistent with the definition of "preemption times".
  Section PreemptionTimes.

Again, we require that the job-selection policy is reasonable.
    Hypothesis H_chooses_from_set: t s j, choose_job t s = Some j j \in s.

For notational convenience, recall the definition of a prefix of the schedule based on which the next decision is made.
    Let prefix t := if t is t'.+1 then schedule_up_to policy idle_state t' else empty_schedule idle_state.

First, we observe that non-preemptive jobs remain scheduled as long as they are non-preemptive.
    Lemma np_job_remains_scheduled:
       t,
        prev_job_nonpreemptive (prefix t) t
        schedule_up_to policy idle_state t t = schedule_up_to policy idle_state t t.-1.

From this, we conclude that the predicate used to determine whether the previously scheduled job is nonpreemptive in the computation of np_uni_schedule is consistent with the existing notion of a preemption_time.
    Lemma np_consistent:
       t,
        prev_job_nonpreemptive (prefix t) t
        ~~ preemption_time arr_seq schedule t.

  End PreemptionTimes.

Finally, we establish the main feature: the generated schedule respects the preemption-model semantics.
  Section PreemptionCompliance.

As a minimal validity requirement (which is a part of valid_preemption_model), we require that any job in arr_seq must start execution to become nonpreemptive.
    Hypothesis H_valid_preemption_function :
       j,
        arrives_in arr_seq j
        job_cannot_become_nonpreemptive_before_execution j.

Second, for the schedule to be valid, we require the notion of readiness to be consistent with the preemption model: a non-preemptive job remains ready until (at least) the end of its current non-preemptive section.
Given such a valid preemption model, we establish that the generated schedule indeed respects the preemption model semantics.