Contact
Director
Prof. Gerhard Fohler
Secretary
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

Publications

Search Publications

show/hide

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
Download:

Abstract

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%.

Bibtex


Upcoming Events
Currently no events
Latest News:
29.11.17 13:00
Our paper titled "Evaluation of DREAMS resource management solutions on a mixed-critical...


04.09.17 11:03
Our paper titled "Modeling Offset Adaptations for Latency Minimization in Cascaded...


03.07.17 10:13
Our paper titled "DREAMS Toolchain: Model-Driven Engineering of Mixed-Criticality...


All News