EDZL (Earliest Deadline first until Zero Laxity) is an efficient and practical scheduling algorithm on multiprocessor systems. It has a comparable number of context switch to EDF (Earliest Deadline First) and its schedulable utilization seems to be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3 m / 4 = 0.75 m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m (1 - 1 / e) ≈ 0.6321 m, where e ≈ 2.718 is the Euler's number.
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications