Document Open Access Logo

Semi-Partitioned Scheduling of Dynamic Real-Time Workload: A Practical Approach Based on Analysis-Driven Load Balancing

Authors Daniel Casini, Alessandro Biondi, Giorgio Buttazzo

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2017.13.pdf
  • Filesize: 0.85 MB
  • 23 pages

Document Identifiers

Author Details

Daniel Casini
Alessandro Biondi
Giorgio Buttazzo

Cite As Get BibTex

Daniel Casini, Alessandro Biondi, and Giorgio Buttazzo. Semi-Partitioned Scheduling of Dynamic Real-Time Workload: A Practical Approach Based on Analysis-Driven Load Balancing. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECRTS.2017.13

Abstract

Recent work showed that semi-partitioned scheduling can achieve near-optimal schedulability performance, is simpler to implement compared to global scheduling, and less heavier in terms of runtime overhead, thus resulting in an excellent choice for implementing real-world systems. However, semi-partitioned scheduling typically leverages an off-line design to allocate tasks across the available processors, which requires a-priori knowledge of the workload. Conversely, several simple global schedulers, as global earliest-deadline first (G-EDF), can transparently support dynamic workload without requiring a task-allocation phase. Nonetheless, such schedulers exhibit poor worst-case performance.

This work proposes a semi-partitioned approach to efficiently schedule dynamic real-time workload on a multiprocessor system. A linear-time approximation for the C=D splitting scheme under partitioned EDF scheduling is first presented to reduce the complexity of online scheduling decisions. Then, a load-balancing algorithm is proposed for admitting new real-time workload in the system with limited workload re-allocation. A large-scale experimental study shows that the linear-time approximation has a very limited utilization loss compared to the exact technique and the proposed approach achieves very high schedulability performance, with a consistent improvement on G-EDF and pure partitioned EDF scheduling.

Subject Classification

Keywords
  • Semi-partitioned scheduling
  • dynamic workload
  • real-time

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Anderson, V. Bud, and U.C. Devi. An EDF-based scheduling algorithm for multiprocessor soft real-time systems. In 17th Euromicro Conference on Real-Time Systems (ECRTS 05), Palma de Mallorca, Spain, July 6-8 2005. Google Scholar
  2. B. Andersson, K.Bletsas, and S. Baruah. Scheduling arbitrary-deadline sporadic task systems on multiprocessors. In Real-Time Systems Symposium, 2008, Barcelona, Spain, Nov 30 - Dec 3 2008. Google Scholar
  3. T. P. Baker. Multiprocessor EDF and deadline monotonic schedulability analysis. In 24th IEEE International Real-Time Systems Symposium (RTSS 03), Cancun, Mexico, Dec, 3-5 2003. Google Scholar
  4. N. Balakrishnan and V. B. Nevzorov. A Primer on Statistical Distributions. Wiley, 2003. Google Scholar
  5. S. Baruah and T. P. Baker. Global EDF schedulability analysis of arbitrary sporadic task systems. In Euromicro Conference on Real-Time Systems (ECRTS 08), Prague, Czech Republic, July, 2-4 2008. Google Scholar
  6. S. K. Baruah, L. E. Rosier, and R. R. Howell. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-time systems, 2(4):301-324, 1990. Google Scholar
  7. A. Bastoni, B. B. Brandenburg, and J. H. Anderson. Is semi-partitioned scheduling practical? In 23rd Euromicro Conference on Real-Time Systems, Porto, Portugal, July, 5-8 2011. Google Scholar
  8. M. Bertogna, M. Cirinei, and G. Lipari. Schedulability analysis of global scheduling algorithms on multiprocessor platforms. IEEE Transactions on Parallel and Distributed Systems, 20(4):553-566, April 2009. Google Scholar
  9. E. Bini and G. C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1):129-154, May 2005. Google Scholar
  10. A. Block, J. H. Anderson, and G. Bishop. Fine-grained task reweighting on multiprocessors. In 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), Hong Kong, China, July, 17-19 2005. Google Scholar
  11. A. Block and J. H. Anderson. Accuracy versus migration overhead in real-time multiprocessor reweighting algorithms. In 12th International Conference on Parallel and Distributed Systems - (ICPADS'06), Minneapolis, USA, July, 12-15 2006. Google Scholar
  12. B. Brandenburg and M. Gül. Global scheduling not required: Simple, near-optimal multiprocessor real-time scheduling with semi-partitioned reservations. In Proceedings of the 37th IEEE Real-Time Systems Symposium (RTSS 2016), Porto, Portugal, November 29 - December 2 2016. Google Scholar
  13. A. Burns, R. Davis, P. Wang, , and F. Zhang. Partitioned EDF scheduling for multiprocessors using a C=D task splitting scheme. Real-Time Systems, 48:3-33, 2012. Google Scholar
  14. G. Buttazzo, G. Lipari, M. Caccamo, and L. Abeni. Elastic scheduling for flexible workload management. IEEE Transactions on Computers, 51(3):289-302, March 2002. Google Scholar
  15. D. Casini, A. Biondi, and G. Buttazzo. Semi-partitioned scheduling of dynamic real-time workload: A practical approach based on analysis-driven load balancing, online material. URL: https://retis.sssup.it/~d.casini/sp-dyn.
  16. H. Cho, B. Ravindran, and E. D. Jensen. An optimal real-time scheduling algorithm for multiprocessors. In Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS 2006), Rio de Janeiro, Brazil, 5-8 December 2006. Google Scholar
  17. T. Cucinotta, L. Abeni, L. Palopoli, and G. Lipari. A robust mechanism for adaptive scheduling of multimedia applications. Journal ACM Transactions on Embedded Computing Systems, 10(4):1-24, Nov. 2011. Google Scholar
  18. R. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for Multiprocessor Systems. ACM Computing Surveys, 43(4):35:1-35:44, 2011. Google Scholar
  19. M. L. Dertouzos and A. K. Mok. Multiprocessor On-Line Scheduling of Hard-Real-Time Tasks. IEEE Transactions on Software Engineering, 15(12):1497-1506, Dec. 1989. Google Scholar
  20. N. Fisher, T. P. Baker, and S. Baruah. Algorithms for determining the demand-based load of a sporadic task system. In 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'06), Sydney, Australia, Aug, 16-18 2006. Google Scholar
  21. N. Fisher, J. Goossens, and S. Baruah. Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible. Real-Time Systems, 45(1):26-71, June 2010. Google Scholar
  22. N. W. Fisher. The Multiprocessor Real-Time Scheduling of General Task Systems. PhD thesis, University of North Carolina at Chapel Hill, 2007. Google Scholar
  23. G.Manimaran and C. S. R. Murthy. An efficient dynamic scheduling algorithm for multiprocessor real-time systems. IEEE Transactions on Parallel and Distributed Systems, 9(3):312-319, Mar. 1998. Google Scholar
  24. J. Goossens, S. Funk, and S. Baruah. Priority-driven scheduling of periodic task systems on multiprocessors. Real-Time Systems, 25(2):187-205, Sept. 2003. Google Scholar
  25. S. Kato and N. Yamasaki. Portioned static-priority scheduling on multiprocessors. In 2008 IEEE International Symposium on Parallel and Distributed Processing, Miami, Florida, USA, April, 14-18 2008. Google Scholar
  26. S. Kato and N. Yamasaki. Semi-partitioned fixed-priority scheduling on multiprocessors. In 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2009), San Francisco, CA, USA, April 13-16 2009. Google Scholar
  27. S. Kato, N. Yamasaki, and Y. Ishikawa. Semi-partitioned scheduling of sporadic task systems on multiprocessors. In 21st Euromicro Conference on Real-Time Systems, Dublin, Ireland, July, 1-3 2009. Google Scholar
  28. K. Konstanteli, T. Cucinotta, K. Psychas, and T. Varvarigou. Admission control for elastic cloud services. In 2012 IEEE Fifth International Conference on Cloud Computing, Honolulu, HI, USA, June, 24-29 2012. Google Scholar
  29. J. Lee and K. G. Shin. Schedulability analysis for a mode transition in real-time multi-core systems. In Proceedings of the 2013 IEEE 34th Real-Time Systems Symposium (RTSS 2013), Washington, DC, USA, December 2013. Google Scholar
  30. A. Mamat, Y. Lu, J. Deogun, and S. Goddard. An efficient algorithm for real-time divisible load scheduling. In 16th IEEE Real-Time and Embedded Technology and Applications Symposium, Stockholm, Sweden, April, 12-15 2010. Google Scholar
  31. A. Mamat, J. Deogun Y. Lu, and S. Goddard. Real-time divisible load scheduling with advance reservations. In 2008 Euromicro Conference on Real-Time Systems, Prague, Czech Republic, July, 2-4 2008. Google Scholar
  32. E. Massa, G. Lima, P. Regnier, G. Levin, and S. Brandt. Quasi-partitioned scheduling: optimality and adaptation in multiprocessor real-time systems. Real-Time Systems, 52(5):566-597, 2016. Google Scholar
  33. G. Nelissen, V. Berten, V. Nelis, J. Goossens, and D. Milojevic. U-EDF: An unfair but optimal multiprocessor scheduling algorithm for sporadic tasks. In 24th Euromicro Conference on Real-Time Systems (ECRTS 2012), Pisa, Italy, July 11-13 2012. Google Scholar
  34. W. Nie, S. Zhou, K. J. Lin, and S. D. Kim. An on-line capacity-based admission control for real-time service processes. IEEE Transactions on Computers, 63(9):2134-2145, Sept. 2014. Google Scholar
  35. V. Nélis, J. Marinho, B. Andersson, and S. M. Petters. Global-EDF scheduling of multimode real-time systems considering mode independent tasks. In Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS 2011), Porto, Portugal, July 6-8 2011. Google Scholar
  36. J. Real and A. Crespo. Mode change protocols for real-time systems: A survey and a new proposal. Real-Time Systems, 26(2):161-197, March 2004. Google Scholar
  37. P. Regnier, G. Lima, E. Massa, G. Levin, , and S. Brandt. Multiprocessor scheduling by reduction to uniprocessor: an original optimal approach. Real-Time Systems, 49(4):436-474, 2013. Google Scholar
  38. L. Santinelli, G. Buttazzo, and E. Bini. Multi-moded resource reservations. In 17th IEEE Real-Time and Embedded Technology and Applications Symposium, Chicago, Illinois, USA, April, 11-13 2011. Google Scholar
  39. I. Shin and I. Lee. Compositional real-time scheduling framework with periodic model. Journal ACM Transactions on Embedded Computing Systems, 7(3):1-39, April 2008. Google Scholar
  40. P. Souto, P. B. Sousa, R. I. Davis, K. Bletsas, and E. Tovar. Overhead-aware schedulability evaluation of semi-partitioned real-time schedulers. In 21st International Conference on Embedded and Real-Time Computing Systems and Applications, Hong Kong, China, August 19-21 2015. Google Scholar
  41. N. Stoimenov, L. Thiele, L. Santinelli, and G. Buttazzo. Resource adaptations with servers for hard real-time systems. In 10th International Conference on Embedded Software (EMSOFT 2010), Scottsdale, Arizona, USA, October, 24-29 2010. Google Scholar
  42. F. Zhang and A. Burns. Schedulability analysis for real-time systems with EDF scheduling. IEEE Trans. Computers, 58(9):1250-1258, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact