Limited Preemptive Scheduling in Real-time Systems
2016 (English)Doctoral thesis, monograph (Other academic)
Preemptive and non-preemptive scheduling paradigms typically introduce undesirable side effects when scheduling real-time tasks, mainly in the form of preemption overheads and blocking, that potentially compromise timeliness guarantees. The high preemption overheads in preemptive real-time scheduling may imply high resource utilization, often requiring significant over-provisioning, e.g., pessimistic Worst Case Execution Time (WCET) approximations. Non-preemptive scheduling, on the other hand, can be infeasible even for tasksets with very low utilization, due to the blocking on higher priority tasks, e.g., when one or more tasks have WCETs greater than the shortest deadline. Limited preemptive scheduling facilitates the reduction of both preemption related overheads as well as blocking by deferring preemptions to favorable locations in the task code.
In this thesis, we investigate the feasibility of limited preemptive scheduling of real-time tasks on uniprocessor and multiprocessor platforms. We derive schedulability tests for global limited preemptive scheduling under both Earliest Deadline First (EDF) and Fixed Priority Scheduling (FPS) paradigms. The tests are derived in the context of two major mechanisms for enforcing limited preemptions, viz., defer preemption for a specified duration (i.e., Floating Non-Preemptive Regions) and defer preemption to the next specified location in the task code (i.e., Fixed Preemption Points). Moreover, two major preemption approaches are considered, viz., wait for the lowest priority job to become preemptable (i.e., a Lazy Preemption Approach (LPA)) and preempt the first executing lower priority job that becomes preemptable (i.e., an Eager Preemption Approach (EPA)). Evaluations using synthetically generated tasksets indicate that adopting an eager preemption approach is beneficial in terms of schedulability in the context of global FPS. Further evaluations simulating different global limited preemptive scheduling algorithms expose runtime anomalies with respect to the observed number of preemptions, indicating that limited preemptive scheduling may not necessarily reduce the number of preemptions in multiprocessor systems. We then theoretically quantify the sub-optimality (the worst-case performance) of limited preemptive scheduling on uniprocessor and multiprocessor platforms using resource augmentation, e.g., processor speed-up factors to achieve optimality. Finally, we propose a sensitivity analysis based methodology to control the preemptive behavior of real-time tasks using processor speed-up, in order to satisfy multiple preemption behavior related constraints. The results presented in this thesis facilitate the analysis of limited preemptively scheduled real-time tasks on uniprocessor and multiprocessor platforms.
Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2016.
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 199
Computer Science Software Engineering
Research subject Computer Science
IdentifiersURN: urn:nbn:se:mdh:diva-31274ISBN: 978-91-7485-254-7OAI: oai:DiVA.org:mdh-31274DiVA: diva2:911669
2016-05-27, Gamma, Mälardalens högskola, Västerås, 13:15 (English)
Bril, Reinder, Associate Professor
Punnekkat, Sasikumar, ProfessorDobrin, Radu, Associate Professor
FunderSwedish Research Council
The examining committee consists of Professor Giorgio Buttazzo, Sant’Anna School of Advance studies-Pisa; Professor Gerhard Fohler, Technical University Kaiserslautern; Associate Professor Liliana Cucu-Grosjean, INRIA.
Reserve: Associate Professor Damir Isovic, MDH.2016-03-142016-03-142016-04-27Bibliographically approved