On non-preemptive scheduling of period and sporadic tasks. Jeffay, K., Stanat, D. F., & Martel, C. U. In Proceedings Twelfth Real-Time Systems Symposium, pages 129–139, December, 1991. 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
{"_id":"GoDeLKNXjzRjspEZw","bibbaseid":"jeffay-stanat-martel-onnonpreemptiveschedulingofperiodandsporadictasks-1991","authorIDs":[],"author_short":["Jeffay, K.","Stanat, D. F.","Martel, C. U."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","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":[{"propositions":[],"lastnames":["Jeffay"],"firstnames":["Kevin"],"suffixes":[]},{"propositions":[],"lastnames":["Stanat"],"firstnames":["Donald","F."],"suffixes":[]},{"propositions":[],"lastnames":["Martel"],"firstnames":["Charles","U."],"suffixes":[]}],"month":"December","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","bibtex":"@inproceedings{jeffay1991nonpreemptive,\n\ttitle = {On non-preemptive scheduling of period and sporadic tasks},\n\tdoi = {10.1109/REAL.1991.160366},\n\tabstract = {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}},\n\tbooktitle = {Proceedings {Twelfth} {Real}-{Time} {Systems} {Symposium}},\n\tauthor = {Jeffay, Kevin and Stanat, Donald F. and Martel, Charles U.},\n\tmonth = dec,\n\tyear = {1991},\n\tkeywords = {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},\n\tpages = {129--139}\n}\n\n","author_short":["Jeffay, K.","Stanat, D. F.","Martel, C. U."],"key":"jeffay1991nonpreemptive","id":"jeffay1991nonpreemptive","bibbaseid":"jeffay-stanat-martel-onnonpreemptiveschedulingofperiodandsporadictasks-1991","role":"author","urls":{},"keyword":["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"],"downloads":0},"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero/romain_jacob","creationDate":"2020-03-11T17:05:50.096Z","downloads":0,"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"],"search_terms":["non","preemptive","scheduling","period","sporadic","tasks","jeffay","stanat","martel"],"title":"On non-preemptive scheduling of period and sporadic tasks","year":1991,"dataSources":["GSdyza34Yogv8tQFT"]}