Prof. Gerhard Fohler
Stephanie Jung
Phone: +49 631 205 2086

Office Hours
Mon/Tue: 13:00-16:00
Wed-Fri: 08:00-11:00
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:
11.03.18 19:00
Our paper titled "Towards Hybrid Wired-Wireless Networks in IndustrialApplications" by...

29.01.18 10:00
Our paper titled "Job-Shifting: An Algorithm for Online Admission of Non-Preemptive Aperiodic...

02.01.18 13:43
17.01.2018, 10:00-11:30 @ 13-305 on "Developing RTOS hypervisor for high-assurance...

All News