# A Comparative Study on the Schedulability of the EDZL Scheduling Algorithm on Multiprocessors
## 3 Comparing EDZL Schedulability Tests
### Dominance between EDZL Schedulability Tests  
Figure 5 shows the number of test instances admitted by each test and their intersections. The number of test instances admitted by the demand-based test is 884,159,737 (=181,804,304 + 93,269,942 + 1,280,464 + 607,805,027). The number of test instances admitted by the utilization-based test is 701,454,278 (=379,191 + 93,269,942 + 118 + 607,805,027). The number of test instances admitted by the slack-based test is 609,085,609 (=1,280,464 + 607,805,027 + 118).  
Figure 4: Admission ratio when \(m=5\).  
Figure 5: Number of test instances admitted by each test and their intersections.  
Figure 3: Admission ratio when \(m=4\).  
The figure implies that the three EDZL schedulability tests do not dominate each other. The number of test instances admitted only by the demand-based test is 181,804,304. An example is \(\tau^{A}=\{(1,2),(2,3),(3,4)\}\) on two processors. This test instance is admitted by the demand-based test but not by the utilization-based test nor by the slack-based test. The number of test instances admitted only by the utilization-based test is 379,191. An example is \(\tau^{B}=\{(1,3),(1,6),(6,7),(5,10)\}\) on two processors. This test instance is admitted by the utilization-based test, but not by the demand-based test nor by the slack-based test.  
An interesting result is that there is no test instance admitted only by the slack-based test. We explored the experiment results carefully and found out that the demand-based test does not dominate the slack-based test, i.e., there are test instances admitted by the slack-based test but not by the demand-based test (e.g., \(\{(1,3),(1,4),(1,4),(3,12),(3,13)\}\) on two processors). And the utilization-based test does not dominate the slack-based test, either, i.e., there are test instances admitted by the slack-based test but not by the utilization-based test (e.g., \(\{(1,2),(2,4),(1,7),(3,8)\}\) on two processors). However, any test instance admitted by the slack-based test can be also admitted by the demand-based test or the utilization-based test in our experiments. Of course, this does not imply that the union of the demand-based test and the utilization-based test (we denote this by _Demand + Util_) dominates the slack-based test. But the experimental results imply that Demand + Util is effective for the EDZL schedulability test.  
As mentioned in Section 3.1, most task sets whose total utilization is below [PERSON]'s schedulable utilization bound are admitted by the three schedulability tests. However, some task sets are admitted by [PERSON]'s test but are not admitted by the slack-based test. An example is task set \(\tau=\{(3,5),(1,6),(4,8),(1,10),(1,11)\}\) on two processors. Its total utilization is 1.46. This test instance is admitted by [PERSON]'s test but not admitted by the slack-based test. There are many test instances that are admitted by the slack-based test but not admitted by [PERSON]'s test. The slack-based test and [PERSON]'s test do not dominate each other.  
[PERSON]'s schedulable utilization bound is the same as fpEDF's. As mentioned in Section 2.2, fpEDF can correctly schedule any task set \(\tau\) if \(U(\tau)\leq(m+1)/2\). This implies that any task set admitted by [PERSON]'s test is also schedulable by fpEDF. According to Lemma 2.4, the task set is admitted by the EDF\({}^{(k)}\) schedulability. Since the EDF\({}^{(k)}\) schedulability test and the utilization-based EDZL schedulability test are equivalent (Theorem 2.2), the task set can be also admitted by the utilization-based test. Therefore, Theorem 2.2 follows.  
The utilization-based schedulability test dominates [PERSON]'s schedulability test.