A Note on the Suboptimality of Nonpreemptive Real-time Scheduling
| Autor: | Michael Short, Donglai Xu, Fathi Abugchem |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Rate-monotonic scheduling
Earliest deadline first scheduling Fixed-priority pre-emptive scheduling General Computer Science Control and Systems Engineering Least slack time scheduling Computer science Two-level scheduling Dynamic priority scheduling Parallel computing Fair-share scheduling Deadline-monotonic scheduling |
| Zdroj: | IEEE Embedded Systems Letters. 7:69-72 |
| ISSN: | 1943-0671 1943-0663 |
| DOI: | 10.1109/les.2015.2426657 |
| Popis: | In this letter, processor speedup analysis is used to strengthen recent results regarding the suboptimality of uniprocessor nonpreemptive earliest deadline first (npEDF) scheduling. The suboptimality of npEDF is defined as the minimum amount of increase in the processor speed that is needed to guarantee the npEDF schedulability of any feasible task set. We show that any preemptively schedulable task set that is not schedulable by npEDF will become schedulable on a processor speeded up by a factor of not more than one plus the value of the largest execution requirement divided by the shortest relative deadline of any task. This reduces the pessimism compared to the best previous bound by factor of at least two. In addition, for the case of nonpreemptive Fixed Priority scheduling, we also show that twice this speedup bound is enough to guarantee the schedulability of any feasible task set. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|