Library prosa.implementation.facts.ideal_uni.preemption_aware

Require Export prosa.implementation.facts.generic_schedule.
Require Export prosa.implementation.definitions.ideal_uni_scheduler.
Require Export prosa.analysis.facts.model.ideal.schedule.
Require Export prosa.model.schedule.limited_preemptive.

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.

Require Import prosa.model.processor.ideal.
Require Export prosa.util.tactics.

Section NPUniprocessorScheduler.

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.

Let PState := ideal.processor_state Job.
Let idle_state : PState := None.

Suppose we are given a valid arrival sequence of such jobs, ...

Variable arr_seq : arrival_sequence Job.
Hypothesis H_valid_arrivals : valid_arrival_sequence arr_seq.

... a non-clairvoyant readiness model, ...

Context {RM: JobReady Job (ideal.processor_state Job)}.
Hypothesis H_nonclairvoyant_job_readiness: nonclairvoyant_readiness RM.

... and a preemption model.

Context `{JobPreemptable Job}.

For any given job selection policy ...

Variable choose_job : instant → seq Job → option Job.

... consider the schedule produced by the preemption-aware scheduler for the policy induced by choose_job.

Let schedule := pmc_uni_schedule arr_seq choose_job.
Let policy := allocation_at arr_seq 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.

    Theorem np_schedule_work_conserving:
      work_conserving arr_seq schedule.

  End WorkConservation.

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.

Hypothesis H_valid_preemption_behavior: valid_nonpreemptive_readiness RM schedule.

Finally, we assume the readiness model to be non-clairvoyant.

Hypothesis H_nonclairvoyant_readiness: nonclairvoyant_readiness RM.

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.

Lemma np_schedule_jobs_from_arrival_sequence:
jobs_come_from_arrival_sequence schedule arr_seq.

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.

Theorem jobs_must_be_ready:
jobs_must_be_ready_to_execute schedule.

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.

Hypothesis H_valid_preemption_behavior: valid_nonpreemptive_readiness RM schedule.

Given such a valid preemption model, we establish that the generated schedule indeed respects the preemption model semantics.

    Lemma np_respects_preemption_model :
      schedule_respects_preemption_model arr_seq schedule.

  End PreemptionCompliance.

End NPUniprocessorScheduler.