Document Open Access Logo

Fixed-Priority Memory-Centric Scheduler for COTS-Based Multiprocessors

Authors Gero Schwäricke , Tomasz Kloda , Giovani Gracioli , Marko Bertogna, Marco Caccamo

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2020.1.pdf
  • Filesize: 0.61 MB
  • 24 pages

Document Identifiers

Author Details

Gero Schwäricke
  • Technical University of Munich, Germany
Tomasz Kloda
  • Technical University of Munich, Germany
Giovani Gracioli
  • Federal University of Santa Catarina, Brazil
Marko Bertogna
  • Università di Modena e Reggio Emilia, Italy
Marco Caccamo
  • Technical University of Munich, Germany

Funding

  • Caccamo, Marco: Marco Caccamo was supported by an Alexander von Humboldt Professorship endowed by the German Federal Ministry of Education and Research.

Cite AsGet BibTex

Gero Schwäricke, Tomasz Kloda, Giovani Gracioli, Marko Bertogna, and Marco Caccamo. Fixed-Priority Memory-Centric Scheduler for COTS-Based Multiprocessors. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ECRTS.2020.1

Abstract

Memory-centric scheduling attempts to guarantee temporal predictability on commercial-off-the-shelf (COTS) multiprocessor systems to exploit their high performance for real-time applications. Several solutions proposed in the real-time literature have hardware requirements that are not easily satisfied by modern COTS platforms, like hardware support for strict memory partitioning or the presence of scratchpads. However, even without said hardware support, it is possible to design an efficient memory-centric scheduler. In this article, we design, implement, and analyze a memory-centric scheduler for deterministic memory management on COTS multiprocessor platforms without any hardware support. Our approach uses fixed-priority scheduling and proposes a global "memory preemption" scheme to boost real-time schedulability. The proposed scheduling protocol is implemented in the Jailhouse hypervisor and Erika real-time kernel. Measurements of the scheduler overhead demonstrate the applicability of the proposed approach, and schedulability experiments show a 20% gain in terms of schedulability when compared to contention-based and static fair-share approaches.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Embedded systems
  • Computer systems organization → Multicore architectures
  • Software and its engineering → Real-time schedulability
  • Security and privacy → Virtualization and security
Keywords
  • Schedulability Analysis
  • Scheduler Implementation
  • memory-centric Scheduling
  • Virtualization
  • Multiprocessor

Metrics

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

References

  1. A. Agrawal, G. Fohler, J. Freitag, J. Nowotsch, S. Uhrig, and M. Paulitsch. Contention-Aware Dynamic Memory Bandwidth Isolation with Predictability in COTS Multicores: An Avionics Case Study. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017), pages 2:1-2:22, 2017. Google Scholar
  2. A. Alhammad and R. Pellizzoni. Schedulability Analysis of Global Memory-predictable Scheduling. In 2014 Inter. Conference on Embedded Software (EMSOFT), pages 1-10, October 2014. Google Scholar
  3. A. Alhammad, S. Wasly, and R. Pellizzoni. Memory Efficient Global Scheduling of Real-Time Tasks. In 21st IEEE Real-Time and Embedded Technology and Applications Symposium, pages 285-296, April 2015. Google Scholar
  4. ARM. Primecell Level 2 Cache Controller (PL310) - Technical Reference Manual, Revision: r2p0. http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0246c/index.html. Accessed: 2019-10-07. URL: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0246c/index.html.
  5. S. Bak, G. Yao, R. Pellizzoni, and M. Caccamo. Memory-Aware Scheduling of Multicore Task Sets for Real-Time Systems. In 2012 IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pages 300-309, August 2012. Google Scholar
  6. M. Becker, D. Dasari, B. Nicolic, B. Akesson, V. Nélis, and T. Nolte. Contention-Free Execution of Automotive Applications on a Clustered Many-Core Platform. In 2016 28th Euromicro Conference on Real-Time Systems (ECRTS), pages 14-24, July 2016. Google Scholar
  7. B. B. Brandenburg and M. Gül. Global Scheduling Not Required: Simple, Near-Optimal Multiprocessor Real-Time Scheduling with Semi-Partitioned Reservations. In 2016 IEEE Real-Time Systems Symposium (RTSS), pages 99-110, November 2016. Google Scholar
  8. P. Burgio, A. Marongiu, P. Valente, and M. Bertogna. A memory-centric approach to enable timing-predictability within embedded many-core accelerators. In 2015 CSI Symposium on Real-Time and Embedded Systems and Technologies (RTEST), pages 1-8, October 2015. Google Scholar
  9. G. C. Buttazzo, M. Bertogna, and G. Yao. Limited Preemptive Scheduling for Real-Time Systems. A Survey. IEEE Transactions on Industrial Informatics, 9(1):3-15, February 2013. Google Scholar
  10. N. Capodieci, R. Cavicchioli, P. Valente, and M. Bertogna. SiGAMMA: Server Based Integrated GPU Arbitration Mechanism for Memory Accesses. In Proceedings of the 25th International Conference on Real-Time Networks and Systems (RTNS), pages 48-57, 2017. Google Scholar
  11. J.-J. Chen, G. Nelissen, W.-H. Huang, M. Yang, B. Brandenburg, K. Bletsas, C. Liu, P. Richard, F. Ridouard, N. Audsley, R. Rajkumar, D. de Niz, and G. von der Brüggen. Many Suspensions, Many Problems: A Review of Self-Suspending Tasks in Real-Time Systems. Real-Time Systems, 55(1):144-207, January 2019. Google Scholar
  12. C. Dall, S.W. Li, J. T. Lim, and J. Nieh. ARM Virtualization: Performance and Architectural Implications. SIGOPS Oper. Syst. Rev., 52(1):45-56, August 2018. Google Scholar
  13. R. I. Davis and A. Burns. A Survey of Hard Real-time Scheduling for Multiprocessor Systems. ACM Comput. Surv., 43(4):35:1-35:44, October 2011. Google Scholar
  14. R. I. Davis, A. Burns, R. J. Bril, and J. J. Lukkien. Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised. Real-Time Systems, 35(3):239-272, April 2007. Google Scholar
  15. G. Durrieu, M. Faugère, S. Girbal, D. Gracia Pérez, C. Pagetti, and W. Puffitsch. Predictable Flight Management System Implementation on a Multicore Processor. In Embedded Real Time Software (ERTS), February 2014. Google Scholar
  16. P. Emberson, R. Stafford, and R.I. Davis. Techniques For The Synthesis Of Multiprocessor Tasksets. In WATERS at the Euromicro Conference on Real-Time Systems, pages 6-11, July 2010. Google Scholar
  17. Evidence. Erika Enterprise RTOS v3, October 2018. Accessed: 2019-10-16. URL: http://www.erika-enterprise.com/.
  18. H. Falk, S. Altmeyer, P. Hellinckx, B. Lisper, W. Puffitsch, C. Rochange, M. Schoeberl, R.B. Sørensen, P. Wägemann, and S. Wegener. TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research. In 16th International Workshop on Worst-Case Execution Time Analysis (WCET), pages 2:1-2:10, 2016. Google Scholar
  19. G. Gracioli, A. Alhammad, R. Mancuso, A. A. Fröhlich, and R. Pellizzoni. A Survey on Cache Management Mechanisms for Real-Time Embedded Systems. ACM Comput. Surv., 48(2):32:1-32:36, November 2015. Google Scholar
  20. G. Gracioli, R. Tabish, R. Mancuso, R. Mirosanlou, R. Pellizzoni, and M. Caccamo. Designing Mixed Criticality Applications on Modern Heterogeneous MPSoC Platforms. In 31st Euromicro Conference on Real-Time Systems (ECRTS), pages 27:1-27:25, 2019. Google Scholar
  21. N. Guan, M. Stigge, W. Yi, and G. Yu. Cache-aware Scheduling and Analysis for Multicores. In Proceedings of the Seventh ACM International Conference on Embedded Software, pages 245-254, 2009. Google Scholar
  22. A. Hamann and R. Ernst. TDMA Time Slot and Turn Optimization with Evolutionary Search Techniques. In Design, Automation and Test in Europe, pages 312-317, March 2005. Google Scholar
  23. F. Hebbache, M. Jan, F. Brandner, and L. Pautet. Shedding the Shackles of Time-Division Multiplexing. In 2018 IEEE Real-Time Systems Symposium (RTSS), pages 456-468, December 2018. Google Scholar
  24. R. E. Kessler and M. D. Hill. Page Placement Algorithms for Large Real-indexed Caches. ACM Trans. Comput. Syst., 10(4):338-359, November 1992. Google Scholar
  25. H. Kim, D. de Niz, B. Andersson, M. Klein, O. Mutlu, and R. Rajkumar. Bounding Memory Interference Delay in COTS-based Multi-Core Systems. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 145-154, April 2014. Google Scholar
  26. H. Kim and R. Rajkumar. Real-Time Cache Management for Multi-Core Virtualization. In 2016 International Conference on Embedded Software (EMSOFT), pages 1-10, October 2016. Google Scholar
  27. J. Kiszka, V. Sinitsyn, H. Schild, and contributors. Jailhouse Hypervisor. Siemens AG on GitHub, https://github.com/siemens/jailhouse, 2018. Accessed: 2019-10-10. URL: https://github.com/siemens/jailhouse.
  28. T. Kloda, M. Solieri, R. Mancuso, N. Capodieci, P. Valente, and M. Bertogna. Deterministic Memory Hierarchy and Virtualization for Modern Multi-Core Embedded Systems. In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 1-14, April 2019. Google Scholar
  29. A. Kostrzewa, S. Saidi, L. Ecco, and R. Ernst. Flexible TDM-Based Resource Management in on-Chip Networks. In Proceedings of the 23rd International Conference on Real Time and Networks Systems (RTNS), page 151–160, 2015. Google Scholar
  30. J. P. Lehoczky. Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines. In Proceedings of the 11th Real-Time Systems Symposium, pages 201-209, December 1990. Google Scholar
  31. J. Liedtke, H. Haertig, and M. Hohmuth. OS-Controlled Cache Predictability for Real-Time Systems. In Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS), pages 213-, 1997. Google Scholar
  32. R. Ma, W. Ye, A. Liang, H. Guan, and J. Li. Cache Isolation for Virtualization of Mixed General-purpose and Real-time Systems. J. Syst. Archit., 59(10):1405-1413, November 2013. Google Scholar
  33. C. Maia, G. Nelissen, L. Nogueira, L. M. Pinho, and D. G. Pérez. Schedulability Analysis for Global Fixed-Priority Scheduling of the 3-Phase Task Model. In IEEE 23rd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 1-10, August 2017. Google Scholar
  34. R. Mancuso, R. Dudko, E. Betti, M. Cesati, M. Caccamo, and R. Pellizzoni. Real-Time Cache Management Framework for Multi-core Architectures. In 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 45-54, April 2013. Google Scholar
  35. J. Martins, A. Tavares, M. Solieri, M. Bertogna, and S. Pinto. Bao: A Lightweight Static Partitioning Hypervisor for Modern Multi-Core Embedded Systems. In Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2020), pages 3:1-3:14, 2020. Google Scholar
  36. J. Matějka, B. Forsberg, M. Sojka, Z. Hanzálek, L. Benini, and A. Marongiu. Combining PREM Compilation and ILP Scheduling for High-performance and Predictable MPSoC Execution. In Proc. of the 9th Inter. Workshop on Programming Models and Applications for Multicores and Manycores (PMAM), pages 11-20, 2018. Google Scholar
  37. A. Melani, M. Bertogna, R. I. Davis, V. Bonifaci, A. Marchetti-Spaccamela, and G. Buttazzo. Exact Response Time Analysis for Fixed Priority Memory-Processor Co-Scheduling. IEEE Transactions on Computers, 66(4):631-646, April 2017. Google Scholar
  38. P. Modica, A. Biondi, G. Buttazzo, and A. Patel. Supporting Temporal and Spatial Isolation in a Hypervisor for ARM Multicore Platforms. In 2018 IEEE International Conference on Industrial Technology (ICIT), pages 1651-1657, February 2018. Google Scholar
  39. M. Nasri, G. Nelissen, and B. B. Brandenburg. A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), pages 9:1-9:23, 2018. Google Scholar
  40. R. Pellizzoni, E. Betti, S. Bak, G. Yao, J. Criswell, and M. Caccamo. Predictable Execution Model: Concept and Implementation. Technical report, University of Illinois at Urbana-Champaign, June 2010. URL: http://hdl.handle.net/2142/16605.
  41. R. Pellizzoni, E. Betti, S. Bak, G. Yao, J. Criswell, M. Caccamo, and R. Kegley. A Predictable Execution Model for COTS-Based Embedded Systems. In 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 269-279, April 2011. Google Scholar
  42. L. T. X. Phan, M. Xu, and I. Lee. Cache-aware Interfaces for Compositional Real-time Systems: Invited Paper. SIGBED Rev., 13(3):52-55, August 2016. Google Scholar
  43. I. Puaut and C. Pais. Scratchpad memories vs locked caches in hard real-time systems: a quantitative comparison. In Design, Automation and Test in Europe Conference and Exposition (DATE), pages 1484-1489, 2007. Google Scholar
  44. R. Rajkumar. Real-Time Synchronization Protocols for Shared Memory Multiprocessors. In Proceedings.,10th International Conference on Distributed Computing Systems, pages 116-123, May 1990. Google Scholar
  45. R. Ramsauer, J. Kiszka, D. Lohmann, and W. Mauerer. Look Mum, no VM Exits! (Almost). Proceedings of the 13th Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), May 2017. Google Scholar
  46. J. M. Rivas, J. Goossens, X. Poczekajlo, and A. Paolillo. Implementation of Memory Centric Scheduling for COTS Multi-Core Real-Time Systems. In 31st Euromicro Conference on Real-Time Systems (ECRTS), pages 7:1-7:23, 2019. Google Scholar
  47. J. Rosen, A. Andrei, P. Eles, and Z. Peng. Bus Access Optimization for Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip. In 28th IEEE International Real-Time Systems Symposium (RTSS), pages 49-60, December 2007. Google Scholar
  48. B. Rouxel, S. Skalistis, S. Derrien, and I. Puaut. Hiding Communication Delays in Contention-Free Execution for SPM-Based Multi-Core Architectures. In 31st Euromicro Conference on Real-Time Systems (ECRTS), pages 25:1-25:24, 2019. Google Scholar
  49. M. Schoeberl, L. Pezzarossa, and J. Sparsø. A Multicore Processor for Time-Critical Applications. IEEE Design Test, 35(2):38-47, April 2018. Google Scholar
  50. L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions on Computers, 39(9):1175-1185, September 1990. Google Scholar
  51. V. Shivappa. x86: Intel Cache Allocation Technology support. https://lwn.net/Articles/622893/. Accessed: 2019-10-07. URL: https://lwn.net/Articles/622893/.
  52. M. R. Soliman, G. Gracioli, R. Tabish, R. Pellizzoni, and M. Caccamo. Segment Streaming for the Three-Phase Execution Model: Design and Implementation. In IEEE Real-Time Systems Symposium (RTSS), December 2019. Google Scholar
  53. R. Tabish, R. Mancuso, S. Wasly, A. Alhammad, S. S. Phatak, R. Pellizzoni, and M. Caccamo. A Real-Time Scratchpad-Centric OS for Multi-Core Embedded Systems. In 2016 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 1-11, April 2016. Google Scholar
  54. C. Tessler and N. Fisher. BUNDLE: Real-Time Multi-threaded Scheduling to Reduce Cache Contention. In 2016 IEEE Real-Time Systems Symposium (RTSS), pages 279-290, November 2016. Google Scholar
  55. K. Tindell and J. Clark. Holistic Schedulability Analysis for Distributed Hard Real-time Systems. Microprocess. Microprogram., 40(2-3):117-134, April 1994. Google Scholar
  56. E. Wandeler and L. Thiele. Optimal TDMA Time Slot and Cycle Length Allocation for Hard Real-Time Systems. In Asia and South Pacific Conference on Design Automation, 2006., pages 6 pp.-, January 2006. Google Scholar
  57. S. Wasly and R. Pellizzoni. Hiding Memory Latency Using Fixed Priority Scheduling. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 75-86, April 2014. Google Scholar
  58. J. Xiao, S. Altmeyer, and A. Pimentel. Schedulability Analysis of Non-preemptive Real-Time Scheduling for Multicore Processors with Shared Caches. In 2017 IEEE Real-Time Systems Symposium (RTSS), pages 199-208, December 2017. Google Scholar
  59. G. Yao, R. Pellizzoni, S. Bak, E. Betti, and M. Caccamo. Memory-centric scheduling for multicore hard real-time systems. Real-Time Systems, 48(6):681-715, November 2012. Google Scholar
  60. G. Yao, R. Pellizzoni, S. Bak, H. Yun, and M. Caccamo. Global Real-Time Memory-Centric Scheduling for Multicore Systems. IEEE Trans. on Computers, 65(9):2739-2751, September 2016. Google Scholar
  61. G. Yao, H. Yun, Z. P. Wu, R. Pellizzoni, M. Caccamo, and L. Sha. Schedulability Analysis for Memory Bandwidth Regulated Multicore Real-Time Systems. IEEE Transactions on Computers, 65(2):601-614, February 2016. Google Scholar
  62. Y. Ye, R. West, Z. Cheng, and Y. Li. COLORIS: A Dynamic Cache Partitioning System Using Page Coloring. In 2014 23rd International Conference on Parallel Architecture and Compilation Techniques (PACT), pages 381-392, August 2014. Google Scholar
  63. Y. Ye, R. West, J. Zhang, and Z. Cheng. MARACAS: A Real-Time Multicore VCPU Scheduling Framework. In 2016 IEEE Real-Time Systems Symposium (RTSS), pages 179-190, November 2016. Google Scholar
  64. H. Yun, R. Mancuso, Z.P. Wu, and R. Pellizzoni. PALLOC: DRAM Bank-Aware Memory Allocator for Performance Isolation on Multicore Platforms. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 155-166, April 2014. 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 Imprint Privacy Contact