# A Comparative Study on the Schedulability of the EDZL Scheduling Algorithm on Multiprocessors
## 2 Background
### Real-Time Scheduling on Multiprocessors  
Real-time scheduling approaches on multiprocessors can be categorized, in terms of task migration, as partitioned and global. In the partitioned approach, tasks are divided into partitions and each partition is associated with a processor. Tasks cannot migrate between partitions (processors), i.e., a task is assigned to a processor statically and all jobs released by the task should execute on the processor. Each processor schedules a partition with one of uniprocessor scheduling algorithms such as RM (Rate Monotonic) [22], EDF \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline \(m\) & the number of processors \\ \(n\) & the number of tasks \\ \(\tau\) & periodic task set \\ \(\tau_{i}\) & the \(i^{th}\) task \\ \(\tau_{i,j}\) & the \(j^{th}\) job of \(\tau_{i}\) \\ \(c_{i}\) & the execution time of \(\tau_{i}\) \\ \(p_{i}\) & the period of \(\tau_{i}\) \\ \(d_{i,j}\) & the deadline of \(\tau_{i,j}\) \\ \(u_{i}\) & the utilization of \(\tau_{i}\) \\ \(U(\tau)\) & the total utilization of task set \(\tau\) \\ \(\tau^{(i)}\) & \(\tau^{(i)}=\{\tau_{i},\tau_{i+1},\ldots,\tau_{n}\}\) \\ \(r_{i,j}(t)\) & the remaining execution time of \(\tau_{i,j}\) at time \(t\) \\ \(lx_{i,j}(t)\) & the laxity of \(\tau_{i,j}\) at time \(t\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations. (Earliest Deadline First) [22], and DM (Deadline Monotonic) [23]. The merit of partitioned scheduling is that well-studied uniprocessor scheduling analysis can be applied for each processor. However, it is difficult to partition tasks optimally and achieve a high processor utilization [24]. In the global approach, tasks are fully migratable. All jobs can start or resume execution on any available processor. The merit of the global approach is that tasks are automatically load-balanced and no task partitioning is required. Uniprocessor scheduling algorithms can be adopted in the global scheduling approach [21; 25; 26]. EDF has strong points that it can be implemented efficiently [27] and the numbers of preemption and migration can be bounded [28]. Most of all, EDF is optimal on uniprocessor systems. However, EDF is not optimal on multiprocessors. Simply employing an optimal uniprocessor scheduling algorithm may not achieve high processor utilization in multiprocessor systems. EDF may fail to successfully schedule task sets with low total utilization on multiprocessors, suffering from Dhall's effect [29]. A high-utilization task with a long deadline (its laxity must be small) is apt to be interrupted by short deadline tasks and miss its deadline (due to its small laxity). One of the ways to overcome [PERSON]'s effect is assigning high priority to high-utilization tasks to give them more chance to execute. EDF-variant algorithms such as EDF-US[\(m/(2m-1)\)], fpEDF, and EDF\({}^{(k)}\) were developed to adopt this policy. EDF-US[\(m/(2m-1)\)] [30] assigns the highest priority to tasks with utilization greater than \(m/(2m-1)\) and assigns a normal priority to the remaining tasks based on EDF. EDF-US[\(m/(2m-1)\)] can successfully schedule any task set whose total utilization is less than or equal to \(m^{2}/(2m-1)\). fpEDF [31] gives the highest priority to, at most, \((m-1)\) largest-utilization tasks with a utilization greater than \(1/2\). The remaining tasks are also given a normal priority based on EDF. fpEDF can successfully schedule any task set whose total utilization is less than or equal to \((m+1)/2\). EDF\({}^{(k)}\) gives the highest priority to \((k-1)\) largest-utilization tasks and the remaining tasks are given a normal priority based on EDF. The schedulability of EDF\({}^{(k)}\) is discussed in Section 2.4. Since EDF\({}^{(k)}\) dominates EDF-US[\(m/(2m-1)\)] and fpEDF, as we will show in Section 2.4, it is sufficient to consider the schedulability of EDF\({}^{(k)}\). Another approach against Dhall's effect is raising the priority of urgent jobs dynamically. Laxity can be a metric for urgency.