Echtzeit-Scheduling für Multicore-Prozessoren

Synopsis

Scheduling auf einem Prozessor ist mit den optimalen Algorithmen EDF im dynamischen und RMS im statischen Fall weitgehend gelöst. Für den Mehrprozessor-Fall, wie er bei aktueller Hardware Standard ist, sind jedoch noch viele Probleme ungelöst. Dazu wurde und wird nach verbesserten Algorithmen und Heuristiken gesucht. Letztgenannte sind notwendig, um die kombinatorische Explosion der Verteilung von n Tasks auf m Prozessoren (beim partitionierten Ansatz) handhaben zu können.

Veröffentlichungen

2014

Dirk Müller, Alejandro Masrur, "The Schedulability Region of Two-Level Mixed-Criticality Systems Based on EDF-VD", in Proceedings of the Conference on Design, Automation and Test in Europe (DATE), 2014

@INPROCEEDINGS{MuMa:SchedRegEDF_VD:2014,
author = {Dirk Müller and Alejandro Masrur},
title = {{T}he Schedulability Region of Two-Level Mixed-Criticality Systems Based on {EDF-VD}},
booktitle = {Proceedings of the Conference on Design, Automation and Test in Europe (DATE)},
year = {2014},
address = {Dresden, Germany},
keywords = {realtime scheduling proj_schedtest}
Dirk Müller, "Schedulability Tests for Real-Time Uni- and Multiprocessor Systems. Focusing on Partitioned Approaches", Der Andere Verlag, 2014

@BOOK{Mu:SchedTestHabil:2014,
title = {Schedulability Tests for Real-Time Uni- and Multiprocessor Systems. Focusing on Partitioned Approaches},
publisher = {Der Andere Verlag},
location = {Uelvesbüll},
year = {2014},
author = {Dirk Müller},
isbn = {9783862474394},
url = {http://www.der-andere-verlag.de/bookshop/default.html?d_9783862474394_Muller__Dirk_2550.htm},
type = {Habilitationsschrift},
keywords = {realtime scheduling proj_schedtest}

2013

Dirk Müller, Matthias Werner, "A Note on "New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems"", IEEE Transactions on Computers, 62(2013)9, 1904-1905

@ARTICLE{MuWe:CircBurchardTest:2013,
author = {Dirk Müller and Matthias Werner},
title = {A Note on "New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems"},
journal = {IEEE Transactions on Computers},
year = {2013},
volume = {62},
pages = {1904-1905},
number = {9},
doi = {10.1109/TC.2012.244},
issn = {0018-9340},
keywords = {concepts realtime scheduling proj_schedtest}
Dirk Müller, Matthias Werner, "Exploiting Period Compatibility for Partitioned Rate-monotonic Scheduling using Circular Statistics", in Proc. of the 4th Int'l Real-Time Scheduling Open Problems Seminar (RTSOPS) at 25th Euromicro Int'l Conference on Real-Time Systems (ECRTS), 16-17, 2013

@INPROCEEDINGS{MuWe:CircStatRMS:2013,
author = {Dirk Müller and Matthias Werner},
title = {Exploiting Period Compatibility for Partitioned Rate-monotonic Scheduling using Circular Statistics},
booktitle = {Proc. of the 4th Int'l Real-Time Scheduling Open Problems Seminar (RTSOPS) at 25th Euromicro Int'l Conference on Real-Time Systems (ECRTS)},
year = {2013},
pages = {16-17},
month = jul,
keywords = {realtime scheduling proj_schedtest},
location = {Paris, France}
Dirk Müller, Matthias Werner, "Quantifying the Advantage of EDF vs. RMS Schedulability on a Uniprocessor Using a Differential Analysis and a Power-law Total Utilization Distribution", in Proc. of the 16th IEEE Computer Society symposium on object/component/servive-oriented realtime distributed computing (ISORC),, 2013

@INPROCEEDINGS{MuWe:EDF_RMS:2013,
author = {Dirk Müller and Matthias Werner},
title = {Quantifying the Advantage of EDF vs. RMS Schedulability on a Uniprocessor Using a Differential Analysis and a Power-law Total Utilization Distribution},
booktitle = {Proc. of the 16th IEEE Computer Society symposium on object/component/servive-oriented realtime distributed computing (ISORC)},
year = {2013},
pages = {},
month = jun,
keywords = {concepts realtime scheduling proj_schedtest},
location = {Paderborn, Germany}

2012

Dirk Müller, "Period Fitting for Rate-monotonic Scheduling Using a Circular Similarity Measure", in The 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2012), WiP Session, 427-430, 2012

@INPROCEEDINGS{Mu:PeriodFittingCircular:2012,
author = {Dirk Müller},
title = {{Period Fitting for Rate-monotonic Scheduling Using a Circular Similarity Measure}},
booktitle = {The 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2012), WiP Session},
year = {2012},
pages = {427--430},
month = aug,
keywords = {realtime scheduling proj_schedtest},
location = {Seoul, Korea}

2011

Dirk Müller, Matthias Werner, "Genealogy of Hard Real-Time Preemptive Scheduling Algorithms for Identical Multiprocessors", Central European Journal of Computer Science, 1(2011)3, 253-265

@ARTICLE{MuWe:GenealogyRT_MP:2011,
author = {Dirk Müller and Matthias Werner},
title = {Genealogy of Hard Real-Time Preemptive Scheduling Algorithms for Identical Multiprocessors},
journal = {Central European Journal of Computer Science},
year = {2011},
volume = {1},
pages = {253-265},
number = {3},
issn = {1896-1533},
keywords = {concepts realtime architecture proj_schedtest}
Dirk Müller, Matthias Werner, "Improved Heuristics for Partitioned Multiprocessor Scheduling Based on Rate-Monotonic Small-Tasks", in Proc. of the 19th International Conference on Real-Time and Network Systems (RTNS), 211-220, 2011

@INPROCEEDINGS{MuWe:ImprovedRMST:2011,
author = {Dirk Müller and Matthias Werner},
title = {Improved Heuristics for Partitioned Multiprocessor Scheduling Based on Rate-Monotonic Small-Tasks},
booktitle = {Proc. of the 19th International Conference on Real-Time and Network Systems (RTNS)},
year = {2011},
pages = {211-220},
month = sep,
keywords = {realtime scheduling proj_schedtest},
location = {Nantes, France}
Dirk Müller, Matthias Werner, "A Generalized View on Beneficial Task Sortings for Partitioned RMS Task Allocation on Multiprocessors", in Proc. of the 2nd Int'l Real-Time Scheduling Open Problems Seminar (RTSOPS) at 23rd Euromicro Int'l Conference on Real-Time Systems (ECRTS), 7-8, 2011

@INPROCEEDINGS{MuWe:SortPartRMS:2011,
author = {Dirk Müller and Matthias Werner},
title = {A Generalized View on Beneficial Task Sortings for Partitioned RMS Task Allocation on Multiprocessors},
booktitle = {Proc. of the 2nd Int'l Real-Time Scheduling Open Problems Seminar (RTSOPS) at 23rd Euromicro Int'l Conference on Real-Time Systems (ECRTS)},
year = {2011},
pages = {7-8},
month = jul,
keywords = {realtime scheduling proj_schedtest},
location = {Porto, Portugal}
Dirk Müller, Matthias Werner, "Towards Exact Thresholds for Scheduling n Tasks on m Processors Based on Partitioned EDF", in 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2011), WiP Session, 2011

@INPROCEEDINGS{MuWe:TresholdPartEDF:2011,
author = {Dirk Müller and Matthias Werner},
title = {Towards Exact Thresholds for Scheduling n Tasks on m Processors Based on Partitioned {EDF}},
booktitle = {17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2011), WiP Session},
year = {2011},
month = apr,
keywords = {realtime scheduling proj_schedtest},
location = {Chicago, USA}

2010

Dirk Müller, Matthias Werner, "Efficient RMS schedulability tests", in Proc. of the 1st Int'l Real-Time Scheduling Open Problems Seminar (RTSOPS) at 22nd Euromicro Int'l Conference on Real-Time Systems (ECRTS), 16-17, 2010

@INPROCEEDINGS{MuWe:EffRMS:2010,
author = {Dirk Müller and Matthias Werner},
title = {Efficient RMS schedulability tests},
booktitle = {Proc. of the 1st Int'l Real-Time Scheduling Open Problems Seminar (RTSOPS) at 22nd Euromicro Int'l Conference on Real-Time Systems (ECRTS)},
year = {2010},
pages = {16-17},
month = jul,
keywords = {realtime scheduling proj_schedtest},
location = {Brussels, Belgium}
Dirk Müller, "Accelerated Simply Periodic Task Sets for RM Scheduling", in Proc. of Embedded Real Time Software and Systems (ERTS$^2$), 46, 2010

@INPROCEEDINGS{Mue:ASPTS:2010,
author = {Dirk Müller},
title = {{Accelerated Simply Periodic Task Sets for {RM} Scheduling}},
booktitle = {Proc. of Embedded Real Time Software and Systems (ERTS{$^2$})},
year = {2010},
pages = {46},
address = {Toulouse, France},
month = may,
keywords = {realtime scheduling proj_schedtest},
url = {http://www.erts2010.moonaweb.com/Site/0ANDGY78/Fichier/PAPIERS%20ERTS%202010%202/ERTS2010_0140_final.pdf}

Ansprechpartner

Dirk Müller