Operating Systems Group
Operating Systems Group

Real-time scheduling for multicore processors



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



  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 
  2. Dirk Müller, "Schedulability Tests for Real-Time Uni- and Multiprocessor Systems. Focusing on Partitioned Approaches", Der Andere Verlag, 2014

  3. 2013

  4. 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 
  5. 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 
  6. 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 

  7. 2012

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

  9. 2011

  10. 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 
  11. 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 
  12. 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 
  13. 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 

  14. 2010

  15. Dirk Müller, "Accelerated Simply Periodic Task Sets for RM Scheduling", in Proc. of Embedded Real Time Software and Systems (ERTS$^2$), 46, 2010 
  16. 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