Definition of Work Conservation

In this module, we introduce a restrictive definition of work-conserving schedules. The definition is restrictive because it does not yet cover multiprocessor scheduling (there are plans to address this in future work). The definition does however cover effects such as jitter or self-suspensions that affect whether a job can be scheduled at a given point in time because it is based on the general notion of a job being backlogged (i.e., ready and not executing), which is parametric in any given job readiness model.

Consider any type of jobs...

... with arrival times and costs ...

... and any kind of processor model.

Further, allow for any notion of job readiness.

Given an arrival sequence and a schedule ...

... we say that a scheduler is work-conserving iff whenever a job j is backlogged, the processor is always busy executing another job j_other. Note that this definition is intentionally silent on matters of priority.