A Comparative Study on the Schedulability of the EDZL Scheduling Algorithm on Multiprocessors

Abstract

As multiprocessor (or multicore) real-time systems become popular, there has been much research on multiprocessor real-time scheduling algorithms. This work evaluates EDZL (Earliest Deadline until Zero Laxity), a scheduling algorithm for real-time multiprocessor systems. First, we compare the performance of EDZL schedulability tests. We measure and compare the ratio of task sets admitted by each test. We also investigate the dominance between EDZL schedulability tests and discover that the union of the demand-based test and the utilization-based test is an effective combination. Second, we compare the schedulability of EDZL and EDF(k). We prove that the union of the EDZL schedulability tests dominates the EDF(k) schedulability test, i.e., the union of the EDZL schedulability tests can admit all task sets admitted by the EDF(k) schedulability test. We also compare the schedulability of EDZL and EDF(k) through scheduling simulation by measuring the ratio of successfully scheduled task sets. EDZL can successfully schedule 7.0% more task sets than EDF(k).

Keywords

• multiprocessor
• real-time
• schedulability
• EDZL
• EDF(k)
• dominance