Title | ||
---|---|---|
On the Design of an Optimal Multiprocessor Real-Time Scheduling Algorithm under Practical Considerations (Extended Version) |
Abstract | ||
---|---|---|
This research addresses the multiprocessor scheduling problem of hard
real-time systems, and it especially focuses on optimal and global schedulers
when practical constraints are taken into account. First, we propose an
improvement of the optimal algorithm BF. We formally prove that our adaptation
is (i) optimal, i.e., it always generates a feasible schedule as long as such a
schedule exists, and (ii) valid, i.e., it complies with the all the
requirements. We also show that it outperforms BF by providing a computing
complexity of O(n), where n is the number of tasks to be scheduled. Next, we
propose a schedulability analysis which indicates a priori whether the
real-time application can be scheduled by our improvement of BF without missing
any deadline. This analysis is, to the best of our knowledge, the first such
test for multiprocessors that takes into account all the main overheads
generated by the Operating System. |
Year | Venue | Keywords |
---|---|---|
2010 | Clinical Orthopaedics and Related Research | computational complexity,cluster computing,multiprocessor scheduling,operating system |
Field | DocType | Volume |
Multiprocessor scheduling,Fair-share scheduling,Scheduling (computing),Computer science,A priori and a posteriori,Real-time computing,Multiprocessing,Earliest deadline first scheduling,Dynamic priority scheduling,Distributed computing,Overhead (business) | Journal | abs/1001.4 |
Citations | PageRank | References |
1 | 0.36 | 6 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shelby Funk | 1 | 348 | 23.89 |
Vincent Nélis | 2 | 175 | 14.10 |
Joël Goossens | 3 | 666 | 49.22 |
Dragomir Milojevic | 4 | 111 | 12.25 |
Geoffrey Nelissen | 5 | 190 | 21.77 |