You are here: RTS-Portal>>Publications


Search Publications


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

Category: Conference
Author(s)Mitra Nasri, Gerhard Fohler
SourceEuromicro Conference on Real-Time Systems (ECRTS), To appear.
Date Jul 2016


In many real-time systems, preemption is either impossible or prohibitively expensive. The problem of scheduling non-preemptive periodic tasks with known release offsets is known to be NP-Hard. In this paper, we investigate the existing non-preemptive scheduling algorithms in both categories of work-conserving 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 using online non-work-conserving algorithms it is possible to schedule more task sets. In our work, we discuss the challenges to design the 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. Further we present a tighter necessary condition for schedulability of non-preemptive tasks. We also provide an IIP for EDF based on looking into a number of jobs in future. Through the experiments we show that the our IIP for EDF significantly increases the schedulability of non-preemptive tasks, particularly in periodic task sets. While our schedulability ratio is more than 80%, the state of the art work-conserving algorithms are about 15%.


Upcoming Events
Currently no events
Latest News:
20.07.20 16:37
Our paper titled "Enabling Fog-based Industrial Robotics Systems" by Mohammed Shaik,...

17.07.20 12:25
Our paper titled "Distributed Decision-making for Safe and Secure Global Resource Management...

09.04.20 16:47
Dear students, things will run differently this semester, we are figuring out how we can...

All News