DocumentCode :
3371655
Title :
On non-preemptive scheduling of period and sporadic tasks
Author :
Jeffay, Kevin ; Stanat, Donald F. ; Martel, Charles U.
Author_Institution :
Dept. of Comput. Sci., North Carolina Univ., Chapel Hill, NC, USA
fYear :
1991
fDate :
4-6 Dec 1991
Firstpage :
129
Lastpage :
139
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
Keywords :
computational complexity; real-time systems; scheduling; arbitrary release times; concrete periodic tasks; conditions; earliest-deadline-first; intractable; non-preemptive EDF algorithm; periodic tasks; real-time scheduling; schedulability; scheduling algorithm; scheduling model; specified release times; sporadic tasks; uniprocessor; universal algorithm; Aerospace electronics; Computer displays; Computer graphics; Hardware; Head; Processor scheduling; Real time systems; Scheduling algorithm; Sufficient conditions; TV;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Real-Time Systems Symposium, 1991. Proceedings., Twelfth
Conference_Location :
San Antonio, TX
Print_ISBN :
0-8186-2450-7
Type :
conf
DOI :
10.1109/REAL.1991.160366
Filename :
160366
Link To Document :
بازگشت