On the optimality of RM and EDF for non-preemptive real-time harmonic tasks

Mitra Nasri, Sanjoy Baruah, Gerhard Fohler, Mehdi Kargahi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)

Abstract

In this paper, we study non-preemptive uniprocessor realtime scheduling using the non-preemptive RM (npRM) and EDF (npEDF) scheduling algorithms. We discuss the limitations of existing studies, identifying pessimism in current schedulability analysis and inefficiencies in existing processor speedup results. Focusing on harmonic task sets, we show that even with restrictions placed on the execution times of the tasks, npRM and npEDF are not able to schedule all feasible task sets. We obtain necessary conditions for the feasibility of the harmonic tasks with arbitrary integer period ratios. Then we derive sufficient conditions for the schedulability of npRM and npEDF upon harmonic task sets. Based on these conditions, a superior speedup factor which guarantees the schedulability in cases where there are fewer restrictions on the execution times is derived. Results from simulation experiments show an average speedup factor three times less than the only existing feasible method to obtain speedup factor.

Original languageEnglish
Title of host publicationProceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014
PublisherAssociation for Computing Machinery, Inc.
Pages331-340
Number of pages10
ISBN (Electronic)978-1-4503-2727-5
DOIs
Publication statusPublished - 8 Oct 2014
Externally publishedYes
Event22nd International Conference on Real-Time Networks and Systems, RTNS 2014 - Versailles, France
Duration: 8 Oct 201410 Oct 2014

Conference

Conference22nd International Conference on Real-Time Networks and Systems, RTNS 2014
Country/TerritoryFrance
CityVersailles
Period8/10/1410/10/14

Fingerprint

Dive into the research topics of 'On the optimality of RM and EDF for non-preemptive real-time harmonic tasks'. Together they form a unique fingerprint.

Cite this