Non-Work-Conserving Non-Preemptive Scheduling: Motivations, Challenges, and Potential Solutions


Frau Dr. Mitra Nasri Max Planck Institut für Software Systeme (MPI-SWS), Kaiserslautern

20.12.1016, 13:30, room 4981


In many real-time systems, preemption is either impossible or prohibitively expensive. For example, if a message is sent to a controller area network (CAN), it cannot be interrupted unless it is entirely sent. In the context of control systems, preemption will cause I/O delay which negatively affects the quality of control of the controller due to the aging of the sampled data. With non-preemptive execution, however, the I/O delay will be minimized. Nonpreemptive scheduling improves the accuracy of the worst-case execution time (WCET) estimation methods, which in turn result in less execution time variations (jitters) and more predictability in the behavior of the control system. Since there will be no preemption, no context switch will happen, and hence, the affinity of data in the cache will not be destroyed by executing another task in the system. Moreover, non-preemptive scheduling simplifies resource management policies in the system due to the fact that the executing task has an exclusive right to access all resources without being blocked by locks or other resource sharing mechanisms. Despite the previously mentioned benefits, non-preemptive scheduling of periodic tasks with known release offsets is known to be an NP-Hard problem. There are two main limitations in the current approaches in the state-of-theart: (i) the existing analysis for systems with no known offset is too pessimistic, (ii) the existing online scheduling algorithms significantly limit the maximum WCET of the tasks due to their greedy work-conserving nature. In this talk, we investigate the existing non-preemptive scheduling algorithms in both categories of workconserving and non-work-conserving algorithms, where in the former, the processing resource is not allowed to be idle as long as there is an unfinished job in the system. While describing the advantages and weaknesses of the existing scheduling solutions we show that it is possible to schedule more task sets using online non-workconserving algorithms. We discuss the challenges to design an idle-time insertion policy (IIP) which can be combined with the existing scheduling policies such as the earliest deadline first (EDF), rate monotonic (RM), etc. We also talk about the schedulability analysis of these new non-work-conserving scheduling policies. As an example, we show a condition in which each task will be executed strictly periodic, i.e., with no sampling delay jitter and with the minimum I/O delay.


Mitra Nasri is a post-doc at Max Planck Institute for Software Systems (MPI-SWS) in Kaiserslautern. She works on real-time scheduling and schedulability analysis, non-preemptive and limited preemptive scheduling, algorithm design, real-time control systems, and parameter assignment and optimization problems. Before being a part of MPI-SWS, she was a post-doc at the Chair of Real-Time Systems in Technische Universität Kaiserslautern. She received her Ph.D. degree with the excellent grade in January 2015 on the topic “Analyzing and improving quality of service of real-time embedded systems in dynamic environments” from the University of Tehran (Iran). During her Ph.D., she was a visiting researcher in Technische Universität Kaiserslautern for 8 months with the support of a scholarship from DAAD. She earned her master degree in 2008 from the Department of Computer Engineering at the Iran University of Science and Technology (Tehran), with the highest cumulative GPA among other students in the same program. She got her bachelor degree in 2005 from the same university. She was born in Esfahan (Iran) in 1983.