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

Mitra Nasri; Sanjoy Baruah; Gerhard Fohler; Mehdi Kargahi

doi:10.1145/2659787.2659806

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 proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014
Publisher	Association for Computing Machinery, Inc.
Pages	331-340
Number of pages	10
ISBN (Electronic)	978-1-4503-2727-5
DOIs	https://doi.org/10.1145/2659787.2659806
Publication status	Published - 8 Oct 2014
Externally published	Yes
Event	22nd International Conference on Real-Time Networks and Systems, RTNS 2014 - Versailles, France Duration: 8 Oct 2014 → 10 Oct 2014

Conference

Conference	22nd International Conference on Real-Time Networks and Systems, RTNS 2014
Country/Territory	France
City	Versailles
Period	8/10/14 → 10/10/14

Access to Document

10.1145/2659787.2659806

Cite this

@inproceedings{ae76c88609fd4dcba3f8a70ade0a549a,

title = "On the optimality of RM and EDF for non-preemptive real-time harmonic tasks",

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.",

author = "Mitra Nasri and Sanjoy Baruah and Gerhard Fohler and Mehdi Kargahi",

year = "2014",

month = oct,

day = "8",

doi = "10.1145/2659787.2659806",

language = "English",

pages = "331--340",

booktitle = "Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014",

publisher = "Association for Computing Machinery, Inc.",

address = "United States",

note = "22nd International Conference on Real-Time Networks and Systems, RTNS 2014 ; Conference date: 08-10-2014 Through 10-10-2014",

}

Nasri, M, Baruah, S, Fohler, G & Kargahi, M 2014, On the optimality of RM and EDF for non-preemptive real-time harmonic tasks. in Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014. Association for Computing Machinery, Inc., pp. 331-340, 22nd International Conference on Real-Time Networks and Systems, RTNS 2014, Versailles, France, 8/10/14. https://doi.org/10.1145/2659787.2659806

On the optimality of RM and EDF for non-preemptive real-time harmonic tasks. / Nasri, Mitra; Baruah, Sanjoy; Fohler, Gerhard et al.
Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014. Association for Computing Machinery, Inc., 2014. p. 331-340.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Nasri, Mitra

AU - Baruah, Sanjoy

AU - Fohler, Gerhard

AU - Kargahi, Mehdi

PY - 2014/10/8

Y1 - 2014/10/8

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

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

UR - http://www.scopus.com/inward/record.url?scp=84953427020&partnerID=8YFLogxK

U2 - 10.1145/2659787.2659806

DO - 10.1145/2659787.2659806

M3 - Conference contribution

AN - SCOPUS:84953427020

SP - 331

EP - 340

BT - Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014

PB - Association for Computing Machinery, Inc.

T2 - 22nd International Conference on Real-Time Networks and Systems, RTNS 2014

Y2 - 8 October 2014 through 10 October 2014

ER -

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

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Invited talk at UvA: "The past, present, and future trends in real-time systems design"

Keynote at CompSys 2023: "The right action at the right time: past, present, and future trends in real-time systems design"

Cite this

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

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Activities

Invited talk at UvA: "The past, present, and future trends in real-time systems design"

Keynote at CompSys 2023: "The right action at the right time: past, present, and future trends in real-time systems design"

Cite this