Name
Abstract | ||
|---|---|---|
A number of preemptive real-time scheduling algorithms, such as Earliest Deadline First (EDF), are known to be optimal on uni-processor systems under specified assumptions. However, no uni-processor optimal algorithm exists under the non-preemptive scheduling paradigm. Hence preemptive schemes strictly dominate non-preemptive schemes with respect to uni-processor feasibility. However, the 'goodness' of non-preemptive schemes, compared to uni-processor optimal preemptive scheduling schemes such as EDF, which can also be referred to as its sub-optimality, has not been fully investigated yet. In this paper, we apply resource augmentation, specifically processor speed-up, to quantify the sub-optimality of non-preemptive scheduling with respect to EDF, and apply the results to guarantee user specified upper-bounds on the preemption related scheduling costs. In particular, we derive an upper bound on the minimum processor speed-up required to guarantee the non-preemptive feasibility of tasks that are deemed feasible under the preemptive EDF, and we prove that, in the cases where, for all tasks in the task set, the largest execution requirement is not greater than the shortest deadline, this bound is equal to 4. We also show how the proposed approach enables a system designer to choose an optimal processor, in order to, e.g., guarantee specified upper bounds on the preemption related overheads. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ECRTS.2013.22 | Real-Time Systems |
Keywords | Field | DocType |
non-preemptive real-time scheduling,non-preemptive scheme,optimal preemptive scheduling scheme,optimal processor,non-preemptive scheduling paradigm,non-preemptive scheduling,preemptive scheme,preemption related scheduling cost,preemptive edf,preemptive real-time scheduling algorithm,non-preemptive feasibility,real time systems,scheduling,resource allocation,scheduling algorithms,earliest deadline first,schedules,silicon,computer and information science | Fixed-priority pre-emptive scheduling,Preemption,Fair-share scheduling,Computer science,Scheduling (computing),Real-time computing,Schedule,Rate-monotonic scheduling,Dynamic priority scheduling,Earliest deadline first scheduling,Distributed computing | Conference |
ISSN | Citations | PageRank |
1068-3070 | 4 | 0.40 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| abhilash thekkilakattil | 1 | 43 | 6.07 |
| Radu Dobrin | 2 | 169 | 22.41 |
| Sasikumar Punnekkat | 3 | 414 | 50.49 |