U-EDF: An Unfair But Optimal Multiprocessor Scheduling Algorithm for Sporadic Tasks
2012
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.
Keywords:
- Computer science
- Real-time computing
- Deadline-monotonic scheduling
- Distributed computing
- Two-level scheduling
- Lottery scheduling
- Fair-share scheduling
- Algorithm
- Multiprocessor scheduling
- Rate-monotonic scheduling
- Fixed-priority pre-emptive scheduling
- Dynamic priority scheduling
- Parallel computing
- Earliest deadline first scheduling
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
26
References
63
Citations
NaN
KQI