# A Comparative Study on the Schedulability of the EDZL Scheduling Algorithm on Multiprocessors
## 2 Background
### EDZL Schedulability Test  
EDZL employs a ZL policy. EDZL gives priority to a job based on EDF. If a job's laxity becomes zero, ZL policy changes the priority of the job to the highest one. There are several studies on the EDZL schedulability test. In reference [8], the authors showed that EDZL dominates EDF. This implies that any sufficient schedulability test for EDF scheduling can be used for EDZL scheduling. Based on this, [PERSON] et al. [16] proposed a schedulable utilization bound-based schedulability test. They proved that any task set satisfying \(U(\tau)\leq(m+1)/2\) is schedulable by EDZL. This is the first EDZL schedulability test. Later, [PERSON] et al. [17] presented a tighter test for \(m=2\). [PERSON] et al. [18] proposed a slack-based test. By computing the slack of tasks iteratively, it checks whether \((n-m)\) tasks have a positive slack lower bound, i.e., whether no more than \(m\) tasks may have zero laxity at the same time. Algorithm 1 is the pseudo-code for the iterative slack-based EDZL schedulability test, where  
\[n_{i}^{*}(s_{i}^{lb})=\left\lfloor\frac{max(0,p_{k}-s_{i}^{lb})}{p_{i}}\right\rfloor \tag{1}\]  
and  
\[\epsilon_{i}(s_{i}^{lb})=min(e_{i},max(0,p_{k}-s_{i}^{lb})-n_{i}^{*}(s_{i}^{lb} )p_{i}). \tag{2}\]  
[PERSON]'s slack-based test outperforms [PERSON]'s test substantially in terms of the number of admitted task sets. But they do not dominate each other. That is, there exists a task set that can be admitted by [PERSON]'s test but not by the slack-based test, and vice versa. In addition, the slack-based test shows a higher time complexity than [PERSON]'s test. ```
1:\(s^{lb}\leftarrow(0,\ldots,0)\)
2:repeat
3:\(converged\gets True\)
4:\(infeasible\gets 0\)
5:for\(k\in\{1,\ldots,n\}\)do
6:\(newSlack\gets p_{k}-e_{k}-\frac{1}{m}\sum_{i\
eq k}min(n_{i}^{*}(s_{i}^ {lb})\cdot e_{i}+e_{i}(s_{i}^{lb}),p_{k}-e_{k})\)
7:if\(s_{k}^{lb}<newSlack\)then
8:\(s_{k}^{lb}\gets newSlack\)
9:\(converged\gets False\)
10:endif
11:if\(s_{k}^{lb}\leq 0\)then
12:\(infeasible\gets infeasible+1\)
13:endif
14:done
15:untilconvergedor\(infeasible\leq m\)
16:return\(infeasible\leq m\)
```  
**Algorithm 1** Iterative slack-based EDZL schedulability test [18]  
[PERSON] and [PERSON] [19] proposed a utilization-based test (Theorem 1). It leverages the EDF schedulability test proposed in reference [21] and the fact that EDZL dominates EDF [8]. The merit of this test is simplicity. Since Equation (3) includes only task utilization values, the test performs in a lower time complexity than the slack-based test and the demand-based test. Moreover, the authors showed that the utilization-based test can admit much more task sets than [PERSON]'s slack-based test. It is known that the utilization-based test and the slack-based test do not dominate each other [19]. However, the dominance between the utilization-based test and [PERSON]'s test has not been disclosed. **Theorem 1** (Theorem 2 in reference [19]). : _On \(m\) identical processors, task set \(\tau\) will be correctly scheduled by EDZL if there exists \(m^{\prime}=1,2,\ldots,m\) such that_  
\[\sum_{\tau_{i}\in T_{1}}u_{i}\leq m^{\prime}-(m^{\prime}-1)\cdot\max_{\tau_{i }\in T_{1}}u_{j} \tag{3}\]  
_where_  
\[T_{1}=\{\tau_{i}\in T\mid\tau_{i}\
otin m-m^{\prime}\text{ tasks with the largest }u_{i}\}.\]  
Later, [PERSON] and [PERSON] derived a demand-bound function for EDZL and developed a demand-based test [20]. They also presented the demand-based test for LLF (Least Laxity First) scheduling [41]. These are the first demand-based tests for job-level dynamic priority scheduling. They demonstrated that the demand-based test for EDZL outperforms the slack-based test and the utilization-based test through simulation. However, the dominance between them was not fully discovered. The authors showed that the demand-based test is not dominated by other tests. However, whether the demand-based test dominates other tests is not disclosed. Theorem 2 shows the test, where the demand bound function of \(\tau_{i}\) in an interval of length \(l\) is defined as follows.