Operating Systems Group
Operating Systems Group
Professur Betriebssysteme

Real-time scheduling for multicore processors

 

Synopsis

Scheduling on a uniprocessor is widely solved by the optimal algorithms EDF (dynamic case) and RMS (static case). Though, in the multiprocessor case which is standard for state-of-the-art hardware, many problems have not been solved yet. To this end, we have looked for and look for improved algorithms and heuristics. The latter ones are necessary in order to handle the combinatorial explosion of allocating n tasks to m processors (with the partitioned scheduling approach).

Publications

    2014

  1. 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}
  2. 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}


    3. 2013

  3. 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}
  4. 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}
  5. 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}


    6. 2012

  6. 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}


    7. 2011

  7. 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}
  8. 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}
  9. 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}
  10. 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}


    11. 2010

  11. 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}
  12. 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}

Contact