U-EDF: An Unfair but Optimal Multiprocessor Scheduling Algorithm for Sporadic Tasks
Ref: HURRAY-TR-120402 Publication Date: 11 to 13, Jul, 2012
U-EDF: An Unfair but Optimal Multiprocessor Scheduling Algorithm for Sporadic TasksRef: HURRAY-TR-120402 Publication Date: 11 to 13, Jul, 2012
A multiprocessor scheduling algorithm named U-EDF, was presented in  for the scheduling of periodic tasks with implicit deadlines. It was claimed that U-EDF is optimal for periodic tasks (i.e., it can meet all deadlines of every schedulable task set) and extensive simulations showed a drastic improvement in the number of task preemptions and migrations in comparison to state-of-the-art optimal algorithms. However, there was no proof of its optimality and U-EDF was not designed to schedule sporadic tasks.
In this work, we propose a generalization of U-EDF for the scheduling of sporadic tasks with implicit deadlines, and we prove its optimality. Contrarily to all other existing optimal multiprocessor scheduling algorithms for sporadic tasks, U-EDF is not based on the fairness property. Instead, it extends the main principles of EDF so that it achieves optimality while benefiting from a substantial reduction in the number of preemptions and migrations.
24th Euromicro Conference on Real-Time Systems (ECRTS 2012), IEEE, pp 13-23.
Record Date: 23, Apr, 2012