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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

15 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014
Uitgeverij	Association for Computing Machinery, Inc.
Pagina's	331-340
Aantal pagina's	10
ISBN van elektronische versie	978-1-4503-2727-5
DOI's	https://doi.org/10.1145/2659787.2659806
Status	Gepubliceerd - 8 okt. 2014
Extern gepubliceerd	Ja
Evenement	22nd International Conference on Real-Time Networks and Systems, RTNS 2014 - Versailles, Frankrijk Duur: 8 okt. 2014 → 10 okt. 2014

Congres

Congres	22nd International Conference on Real-Time Networks and Systems, RTNS 2014
Land/Regio	Frankrijk
Stad	Versailles
Periode	8/10/14 → 10/10/14

Toegang tot document

10.1145/2659787.2659806

Andere bestanden en links

Link to publication in Scopus

Invited talk at UvA: "The past, present, and future trends in real-time systems design"
Nasri, M. (Spreker)
6 sep. 2023
Activiteit: Types gesprekken of presentaties › Genodigd spreker › Wetenschappelijk
Keynote at CompSys 2023: "The right action at the right time: past, present, and future trends in real-time systems design"
Nasri, M. (Spreker)
28 jun. 2023
Activiteit: Types gesprekken of presentaties › Genodigd spreker › Wetenschappelijk

Citeer dit

@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., blz. 331-340, 22nd International Conference on Real-Time Networks and Systems, RTNS 2014, Versailles, Frankrijk, 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. blz. 331-340.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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

Samenvatting

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Activiteiten

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"

Citeer dit