Library prosa.behavior.ready

Require Export prosa.behavior.service.

Readiness of a Job

We define a general notion of readiness of a job: a job can be scheduled only when it is ready, as determined by the predicate job_ready. This notion of readiness is a general concept that is used to model jitter, self-suspensions, etc. Crucially, we require that any sensible notion of readiness is a refinement of the notion of a pending job, i.e., any ready job must also be pending.
Class JobReady (Job : JobType) (PState : ProcessorState Job)
      {jc : JobCost Job} {ja : JobArrival Job} :=
  {
    job_ready : schedule PState Job instant bool;

    
What follows is the consistency requirement: We require any reasonable readiness model to consider only pending jobs to be ready.
    _ : sched j t, job_ready sched j t pending sched j t;
  }.

Backlogged Jobs

Based on the general notion of readiness, we define what it means to be backlogged, i.e., ready to run but not executing.
Section Backlogged.
Consider any kinds of jobs and any kind of processor state.
  Context {Job : JobType} {PState : ProcessorState Job}.

Allow for any notion of readiness.
  Context {jc : JobCost Job} {ja : JobArrival Job} {jr : JobReady Job PState}.

Job j is backlogged at time t iff it is ready and not scheduled.
  Definition backlogged (sched : schedule PState) (j : Job) (t : instant) :=
    job_ready sched j t && ~~ scheduled_at sched j t.

End Backlogged.

Validity of a Schedule

With the readiness concept in place, we define the notion of valid schedules.
Section ValidSchedule.
Consider any kind of jobs and any kind of processor state.
  Context {Job : JobType} {PState : ProcessorState Job}.

Consider any schedule.
  Variable sched : schedule PState.

  Context `{JobArrival Job}.

We define whether jobs come from some arrival sequence...
..., whether a job can only be scheduled if it has arrived ...
  Definition jobs_must_arrive_to_execute :=
     j t, scheduled_at sched j t has_arrived j t.

  Context {jc : JobCost Job} {ja : JobArrival Job} {jr : JobReady Job PState}.

..., whether a job can only be scheduled if it is ready ...
... and whether a job cannot be scheduled after it completes.
We say that the schedule is valid iff
  • jobs come from some arrival sequence
  • a job is scheduled if it is ready
Note that we do not explicitly require that a valid schedule satisfies jobs_must_arrive_to_execute or completed_jobs_dont_execute because these properties are implied by jobs_must_be_ready_to_execute.