Library prosa.analysis.facts.priority.fifo

In this section, we prove some fundamental properties of the FIFO policy.
Section BasicLemmas.

We assume the basic (i.e., Liu & Layland) readiness model under which any pending job is ready.
  #[local] Existing Instance basic_ready_instance.

Consider any type of jobs with arrival times and execution costs.
  Context `{Job : JobType} {Arrival : JobArrival Job} {Cost : JobCost Job}.

Consider any arrival sequence of such jobs ...
  Variable arr_seq : arrival_sequence Job.

... and the resulting ideal uniprocessor schedule. We assume that the schedule is valid and work-conserving.
Suppose jobs have preemption points ...
  Context `{JobPreemptable Job}.

...and that the preemption model is valid.
Assume that the schedule respects the FIFO scheduling policy whenever jobs are preemptable.
We observe that there is no priority inversion in a FIFO-compliant schedule.
  Lemma FIFO_implies_no_priority_inversion :
     j t,
      arrives_in arr_seq j
      pending sched j t
      ¬ priority_inversion sched j t.
  Proof.
    movej t ARRIVES /andP [ARRIVED /negP NCOMPL] [NSCHED [jlp /andP [SCHED PRIO]]].
    move: PRIO; rewrite /hep_job /FIFO -ltnNgeLT.
    apply: NCOMPL; eapply early_hep_job_is_scheduled; rt_eauto.
    by intros t'; apply/andP; split; unfold hep_job_at, JLFP_to_JLDP, hep_job, FIFO; lia.
  Qed.

We prove that in a FIFO-compliant schedule, if a job j is scheduled, then all jobs with higher priority than j have been completed.
  Lemma scheduled_implies_higher_priority_completed :
     j t,
      scheduled_at sched j t
       j_hp,
        arrives_in arr_seq j_hp
        ~~hep_job j j_hp
        completed_by sched j_hp t.
  Proof.
    movej' t SCHED j_hp ARRjhp HEP.
    have EARLIER: job_arrival j_hp < job_arrival j' by rewrite -ltnNge in HEP.
    eapply (early_hep_job_is_scheduled arr_seq _ sched _ _ _ _ j_hp j' _ _ _ t).
    Unshelve. all : rt_eauto.
    movet'; apply /andP; split ⇒ //.
    by apply ltnW.
  Qed.

The next lemma considers FIFO schedules in the context of tasks.
  Section SequentialTasks.

If the scheduled jobs stem from a set of tasks, ...
    Context {Task : TaskType}.
    Context `{JobTask Job Task}.

... then the tasks in a FIFO-compliant schedule necessarily execute sequentially.
    Lemma tasks_execute_sequentially : sequential_tasks arr_seq sched.
    Proof.
      movej1 j2 t ARRj1 ARRj2 SAME_TASKx LT ⇒ //.
      eapply (early_hep_job_is_scheduled); try rt_eauto.
      by move⇒ ?; apply /andP; split; [apply ltnW | rewrite -ltnNge //=].
    Qed.

  End SequentialTasks.

Finally, let us further assume that there are no needless preemptions among jobs of equal priority.
In the absence of superfluous preemptions and under assumption of the basic readiness model, there are no preemptions at all in a FIFO-compliant schedule.
  Lemma no_preemptions_under_FIFO :
     j t,
      ~~ preempted_at sched j t.
  Proof.
    movej t.
    apply /negP.
    intros CONTR.
    move: CONTR ⇒ /andP [/andP [SCHED1 NCOMPL] SCHED2].
    move : H_schedule_is_valid ⇒ [COME MUST].
    move: (ideal_proc_model_sched_case_analysis sched t) ⇒ [IDLE |[s INTER]].
    { specialize (H_work_conservation j t).
      destruct H_work_conservation as [j_other SCHEDj_other]; first by eapply (COME j t.-1 SCHED1).
      - do 2 (apply /andP; split; last by done).
        eapply scheduled_implies_pending in SCHED1; try rt_eauto.
        move : SCHED1 ⇒ /andP [HAS COMPL].
        by apply leq_trans with t.-1; [exact HAS| lia].
      - move: SCHEDj_other IDLE.
        rewrite scheduled_at_def ⇒ /eqP SCHED /eqP IDLE.
        by rewrite IDLE in SCHED. }
    { specialize (H_no_superfluous_preemptions t j s).
      have HEP : ~~ hep_job j s.
      {
        apply H_no_superfluous_preemptions; last by done.
        by repeat (apply /andP ; split; try by done).
      }
      rewrite /hep_job /fifo.FIFO -ltnNge in HEP.
      eapply (early_hep_job_is_scheduled arr_seq ) in SCHED1; try rt_eauto.
      - apply scheduled_implies_not_completed in INTER; rt_eauto.
        by eapply (incompletion_monotonic sched s t.-1 t) in INTER; [move: INTER ⇒ /negP|lia].
      - by move⇒ ?; apply /andP; split; [apply ltnW | rewrite -ltnNge //=]. }
  Qed.

It immediately follows that FIFO schedules are non-preemptive.