In *Proceedings Twelfth Real-Time Systems Symposium*, pages 129–139, December, 1991.

doi abstract bibtex

doi abstract bibtex

A fundamental problem in the theory of real-time scheduling is examined: scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time. The authors give a necessary and sufficient set of conditions C for a set of periodic or sporadic tasks to be schedulable for arbitrary release times of the tasks. They show that any set of periodic or sporadic tasks that satisfies C can be scheduled with an earliest-deadline-first (EDF) scheduling algorithm. The authors present the scheduling model, briefly review the literature in real-time scheduling, prove that the non-preemptive EDF algorithm is universal for sets of tasks, whether periodic or sporadic, and demonstrate the absence of a universal algorithm for periodic tasks with specified release times. It is proved that the problem of deciding schedulability of a set of concrete periodic tasks is intractable.\textless\textgreater

@inproceedings{jeffay1991nonpreemptive, title = {On non-preemptive scheduling of period and sporadic tasks}, doi = {10.1109/REAL.1991.160366}, abstract = {A fundamental problem in the theory of real-time scheduling is examined: scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time. The authors give a necessary and sufficient set of conditions C for a set of periodic or sporadic tasks to be schedulable for arbitrary release times of the tasks. They show that any set of periodic or sporadic tasks that satisfies C can be scheduled with an earliest-deadline-first (EDF) scheduling algorithm. The authors present the scheduling model, briefly review the literature in real-time scheduling, prove that the non-preemptive EDF algorithm is universal for sets of tasks, whether periodic or sporadic, and demonstrate the absence of a universal algorithm for periodic tasks with specified release times. It is proved that the problem of deciding schedulability of a set of concrete periodic tasks is intractable.{\textless}{\textgreater}}, booktitle = {Proceedings {Twelfth} {Real}-{Time} {Systems} {Symposium}}, author = {Jeffay, Kevin and Stanat, Donald F. and Martel, Charles U.}, month = dec, year = {1991}, keywords = {Aerospace electronics, Computer displays, Computer graphics, Hardware, Head, Processor scheduling, Real time systems, Scheduling algorithm, Sufficient conditions, TV, arbitrary release times, computational complexity, concrete periodic tasks, conditions, earliest-deadline-first, intractable, non-preemptive EDF algorithm, periodic tasks, real-time scheduling, real-time systems, schedulability, scheduling, scheduling algorithm, scheduling model, specified release times, sporadic tasks, uniprocessor, universal algorithm}, pages = {129--139} }

Downloads: 0