Dual Priority and EDF: a closer look

International audienceIn the context of uniprocessor scheduling, two scheduling algorithms have beenvery much studied: one in the class of fixed task priority (FTP) where RateMonotonic (RM) is optimal and one in the class of fixed job priority (FJP),where Earliest Deadline First (EDF) is optimal. RM has the disadvantage ofimposing processor utilization less than 100% (i.e., 69% in the worst case) whileEDF scheduling can reach 100% of processor utilization.Some research have been done to overcome this sub-optimality problem. Ithas been shown that when periods are harmonic, the processor utilization boundof RM is identical to the one of EDF [1]. When no constraint is imposed on theperiods, the dual priority approach was introduced in 1993 [3]. The schedulerconsider two priorities and two phases for each task, each phase has a fixedpriority, the transition from a phase to another is made at a fixed time offsetfrom the task release. Dual priority approach is interesting as it is conjecturedthat a dual priority scheduling can reach the same performances as an EDFscheduler.In this paper, we revisit dual priority scheduling for uniprocessor systemswith implicit-deadline periodic task set. We recall existing conjectures. Then,we explicit a new class of scheduling FPk, a fixed priority scheduling that requiresat most k promotions at k fixed times. We show that dual priority and EDFscheduling are particular cases of FPk. Finally, we analyse EDF scheduling tryingto study how far it is from a dual priority scheduler in terms of promotions