Generality of GEL

In the following, we make some formal remarks on the obvious generality of GEL w.r.t. EDF and FIFO, and the somewhat less obvious conditional generality w.r.t. fixed-priority scheduling. We begin with the general setup.

Consider any type of tasks with relative priority points, ...

... jobs of these tasks, and ...

... any processor model.

Suppose the jobs have arrival times and costs, and allow for any preemption and readiness models.

GEL Generalizes EDF

First, let us consider EDF, the namesake of GEL, which it trivially generalizes by design.

Suppose the tasks have relative deadlines.

If each task's priority point is set to its relative deadline, ...

... then the GEL policy reduces to EDF.

GEL Generalizes FIFO

GEL similarly generalizes FIFO in a trivial manner.

If each task's priority point is set to zero, ...

... then the GEL policy reduces to FIFO.

GEL Conditionally Generalizes FP

We now turn to fixed-priority scheduling. GEL does not generalize fixed-priority scheduling in all circumstances. However, if priority points are carefully chosen, tasks are sequential, and fixed task priorities are unique, then GEL can be equivalent to a given arbitrary fixed-priority policy.

Consider GEL scheduling with arbitrary tie-breaking ...

... and an arbitrary valid arrival sequence.

For ease of reference, we refer to the difference between the relative priority points of two given tasks as pp_delta.

Before we tackle the conditional equivalence, we first establish a helper lemma on the priority of backlogged jobs that sits at the core of the argument.

Consider two arbitrary jobs j and j', ...

... their corresponding tasks tsk and tsk', ...

...an arbitrary schedule, ...

... and an arbitrary point in time t.

Suppose the relative priority point of tsk' is larger than that of tsk ...

... and that the difference between the priority points of the two tasks bounds the maximum response time of j' in sched.

We are now ready to state the auxiliary lemma: under the above assumptions, if j has arrived by time t and j' is backlogged, then j's priority under GEL is higher than or equal to j''s priority.

With the auxiliary lemma in place, we now state the main assumptions under which conditional generality can be shown. Consider any given reflexive and total fixed-priority policy.

We require that the priorities of tasks that feature in the schedule are unique. That is, no two tasks that contribute jobs to the arrival sequence share a fixed priority.

We further require that the assigned relative priority points are monotonic with decreasing task priority: the relative priority point offset of a lower-priority task must not be less than that of any higher-priority task (that features in the arrival sequence).

To state the third and fourth assumptions, we require an arbitrary, valid schedule to be given.

We require that the difference in relative priority points between a higher- and lower-priority task exceeds the maximum response time of the lower-priority task in the given schedule. In other words, the priority points of lower-priority tasks must be chosen to be "large enough" to be sufficiently far enough in the future to avoid interfering with any concurrently pending jobs of higher-priority tasks.

FP-compliance does not constrain jobs of the same task, whereas a given GEL policy may resolve ties arbitrarily when both jobs have the same priority point. Hence, in the only ambiguous case, we explicitly rule out tie-breaking that disagrees with the required job-level priority order.

Finally, we require that tasks execute sequentially.

Under the four conditions stated above, GEL generalizes the given FP policy.