Login

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 Tasks

Ref: HURRAY-TR-120402       Publication Date: 11 to 13, Jul, 2012

Abstract:
A multiprocessor scheduling algorithm named U-EDF, was presented in [1] 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.

Authors:
Geoffrey Nelissen
,
Vandy Berten
,
Vincent NĂ©lis
,
Joel Goossens
,
Dragomir Milojevic


24th Euromicro Conference on Real-Time Systems (ECRTS 2012), IEEE, pp 13-23.
Pisa, Italy.

DOI:10.1109/ECRTS.2012.36.



Record Date: 23, Apr, 2012