Properties of Readiness Models

In this file, we define commonsense properties of readiness models.

For any type of jobs with costs and arrival times ...

... and any kind of processor model, ...

... consider a notion of job readiness.

First, we define a notion of non-clairvoyance for readiness models. Intuitively, whether a job is ready or not should depend only on the past (i.e., prior allocation decisions and job behavior), not on future events. Formally, we say that the ReadinessModel is non-clairvoyant if a job's readiness at a given time does not vary across schedules with identical prefixes. That is, given two schedules sched and sched', the predicates job_ready sched j t and job_ready sched' j t may not differ if sched and sched' are identical prior to time t.

Next, we relate the readiness model to the preemption model.

In a preemption-policy-compliant schedule, nonpreemptive jobs must remain scheduled. Further, in a valid schedule, scheduled jobs must be ready. Consequently, in a valid preemption-policy-compliant schedule, a nonpreemptive job must remain ready until at least the end of its nonpreemptive section.

For the next definition, consider the tasks from which the jobs stem.

We say a readiness model is sequential iff only a task's earliest incomplete job is ready, meaning that later jobs can be executed only after all earlier jobs have been completed.