A Comparison of Scheduling Algorithms for Multiprocessors

Scheduling multiple processors in a computer system while providing real-time guarantees remains an interesting and challenging problem, despite being a topic of study for decades. Throughout these years of investigation, many algorithms have been proposed, analyzed, and evaluated. In this study, we intend to compare and evaluate three of these multiprocessor schedul-ing algorithms: the classic, simple algorithm global EDF, the optimal P-fair algorithm PF, and a newer, optimal algorithm LLREF that intends to improve on existing P-fair algorithms and global EDF variants. We empirically investigate the ability of global EDF to schedule randomly generated task sets as compared to PF and LLREF, which can schedule any task set with a total utilization less than the number of processors. We also investigate the overhead of all three algorithms in terms of task migrations and required scheduler invocations for randomly generated tasks. Our results verify that LLREF outperforms PF. Additionally, they show that global EDF still outperforms LLREF and PF in terms of required scheduler invocations and task migrations; however, our results also demonstrate that global EDF cannot feasibly schedule the same variety of task sets as LLREF and PF.