Name
Title | ||
|---|---|---|
Hyperbolic Utilization Bounds for Rate Monotonic Scheduling on Homogeneous Multiprocessors |
Abstract | ||
|---|---|---|
The utilization bounds for partitioned multiprocessor scheduling are a function of task allocation algorithms and the schedulability conditions selected for uniprocessor scheduling algorithms. In this paper, we use rate-monotonic scheduling on each processor and present the lower and upper limits of the utilization bounds for all reasonable task allocation heuristics. Unlike previous work, the hyperbolic bound due to Bini et. al., instead of the Liu & Layland bound, is adopted to do the schedulability test on uniprocessors. We also derive the utilization bounds with respect to the worst fit allocation algorithm and reasonable allocation decreasing heuristics, and the two bounds are found to coincide with the worst and best achievable multiprocessor utilization bounds, respectively. Analytical and experimental results show that the proposed utilization bound performs better than the existing bound under quite a lot of parameter settings, and combining these two bounds together can significantly (up to 3 times) increase the number of schedulable task sets with little extra overhead. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TPDS.2013.213 | IEEE Transactions on Parallel and Distributed Systems |
Keywords | Field | DocType |
processor scheduling,schedulability test,task allocation heuristics,partitioned multiprocessor scheduling,homogeneous multiprocessors,liu & layland bound,hyperbolic bound,resource allocation,real-time system,multiprocessing systems,rate-monotonic scheduling,uniprocessor scheduling algorithms,multiprocessor,rate monotonic scheduling,hyperbolic utilization bounds,task allocation algorithms,real time systems,real time system,scheduling,resource management | Fixed-priority pre-emptive scheduling,Multiprocessor scheduling,Fair-share scheduling,Computer science,Deadline-monotonic scheduling,Parallel computing,Two-level scheduling,Real-time computing,Least slack time scheduling,Rate-monotonic scheduling,Earliest deadline first scheduling,Distributed computing | Journal |
Volume | Issue | ISSN |
25 | 6 | 1045-9219 |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hongya Wang | 1 | 17 | 5.71 |
| Lihchyun Shu | 2 | 130 | 17.32 |
| Wei Yin | 3 | 0 | 0.34 |
| Yingyuan Xiao | 4 | 754 | 103.20 |
| Jiao Cao | 5 | 6 | 1.11 |