Name
Title | ||
|---|---|---|
An Improved Speedup Factor for Sporadic Tasks with Constrained Deadlines Under Dynamic Priority Scheduling |
Abstract | ||
|---|---|---|
Schedulability is a fundamental problem in real-time scheduling, but it has to be approximated due to the intrinsic computational hardness. As the most popular algorithm for deciding schedulability on multiprocess platforms, the speedup factor of partitioned-EDF is challenging to analyze and is far from being determined. Partitioned-EDF was first proposed in 2005 by Barush and Fisher [1], and was shown to have a speedup factor at most 3-1/m, meaning that if the input of sporadic tasks is feasible on m processors with speed one, partitioned-EDF will always succeed on m processors with speed 3-1/m. In 2011, this upper bound was improved to 2.6322-1/m by Chen and Chakraborty [2], and no more improvements have appeared ever since then. In this paper, we develop a novel method to discretize and regularize sporadic tasks, which enables us to improve, in the case of constrained deadlines, the speedup factor of partitioned-EDF to 2.5556-1/m, very close to the asymptotic lower bound 2.5 in [2]. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/RTSS.2018.00058 | 2018 IEEE Real-Time Systems Symposium (RTSS) |
Keywords | DocType | Volume |
Sporadic tasks, resource augmentation, partitioned scheduling, demand bound function | Conference | abs/1807.08579 |
ISSN | ISBN | Citations |
1052-8725 | 978-1-5386-7909-8 | 0 |
PageRank | References | Authors |
0.34 | 9 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xin Han | 1 | 213 | 24.49 |
| Liang Zhao | 2 | 0 | 0.68 |
| Zhishan Guo | 3 | 329 | 34.04 |
| Xingwu Liu | 4 | 19 | 12.77 |