Static and dynamic scheduling of sporadic tasks for single-processor systems

Sporadic tasks in hard-real-time systems, as defined by Mok [14], are characterized by triples (e, d, p), 1 ≤ e ≤ d, e ≤ p. Two successive requests by the same task will be separated by at least p time units, and the task must be scheduled e time units within d time units of a request. A scheduling algorithm is said to be static if it does not depend on the sequence of requests; otherwise at is dynamic. We present here three major results. The first is that no static algorithm can be optimal. The second is that, modulo certain assumptions that imply scalability, no dynamic algorithm can take less than O(n) online time per slot scheduled. The third result is a fast scheduling algorithm based on pinwheel scheduling.