# A Comparative Study on the Schedulability of the EDZL Scheduling Algorithm on Multiprocessors
## 1 Introduction  
As multiprocessor systems running real-time applications become popular, there has been much research on algorithms that can correctly schedule real-time tasks with timing constraints as well as significantly utilize multiple processors (or multicores) [1; 2; 3; 4; 5; 6]. Some of them are optimal, i.e., they can fully utilize multiple processors, but they suffer from scheduling overhead such as task splitting and frequent preemption. EDZL (Earliest Deadline until Zero Laxity) [7; 8] is a practical real-time scheduling algorithm for multiprocessor systems. It is not optimal but it can achieve a high processor utilization with restricted scheduling overhead. Many researchers have extended or applied the EDZL algorithm to various applications. [PERSON] and [PERSON] [9] proposed a variant of EDZL, the LEZL (Largest Execution until Zero Laxity) scheduling algorithm. [PERSON] et al. [10] proposed the EVDZL (Earliest Virtual Deadline Zero Laxity) algorithm that applies EDZL to mobile GPU scheduling. There are other research works that apply EDZL scheduling algorithm to virtual cloud environments, mixed-criticality systems or large-scale real-time cloud systems [11; 12; 13; 14]. In reference [15], the EDZL algorithm was integrated with a task-level re-execution-based fault tolerance technique. To employ a real-time scheduling algorithm in real systems, a schedulability test for the algorithm is undoubtedly required. A schedulability test is a method that examines in advance whether a task set will be correctly scheduled by the scheduling algorithm or not. We can guarantee the satisfaction of the timing constraints (deadlines) of real-time tasks to implement a safe real-time system only if a given task set is admitted by one of the schedulability tests for the scheduling algorithm. If a task set that does not pass any schedulability test was executed, it might violate its timing constraints, i.e., miss a deadline. A deadline miss in hard real-time systems may cause a system failure or catastrophe. We do not perform a task set on a hard real-time system if the task set does not pass anyschedulability test. Note that there can be more than one schedulability test for a scheduling algorithm. Many researchers try to develop a tighter schedulability test because a tighter schedulability test can accommodate more tasks and admit more task sets. There have been several studies on the schedulability test for the EDZL algorithm. [PERSON] et al. [16] proposed the first EDZL schedulability test, which is based on a schedulable utilization bound. [PERSON]'s test is very simple and too pessimistic. It cannot guarantee the successful execution of task sets whose total utilization is higher than \((m+1)/2\) where \(m\) is the number of processors. [PERSON] et al. [17] presented a tighter test that can be applied to two processor systems. [PERSON] et al. [18] proposed a more elaborate, slack-based test. By computing the slack of tasks iteratively, it provides a much tighter condition than [PERSON]'s test. [PERSON]'s slack-based test outperforms [PERSON]'s test in terms of the number of admitted task sets. However, sometimes the slack-based test does not admit task sets with low total utilization that are admitted even by [PERSON]'s test. [PERSON] and [PERSON] [19] proposed a simple, but effective, utilization-based test. The utilization test has some advantages over the slack-based test. First, its implementation is simple and the computation complexity is lower than the slack-based test. Second, it outperforms the slack-based test in terms of the number of admitted task sets. Third, it dominates [PERSON]'s test, as we will prove in Section 4.1. Additionally, the authors showed that the utilization-based test and the slack-based test do not dominate each other. Later, [PERSON] and [PERSON] also proposed a demand-based test [20]. They developed a demand bound function for job-level dynamic priority scheduling and proposed a complicated but very tight EDZL schedulability test.