Vol. 4 No. 2 (2017)
Regular Papers

Per Processor Spin-Based Protocols for Multiprocessor Real-Time Systems

PDF
  • Sara Afshar,
  • Moris Behnam,
  • Reinder J. Bril,
  • Thomas Nolte
Sara Afshar
Mälardalen University
Moris Behnam
Mälardalen University
Reinder J. Bril
Technische Universiteit Eindhoven
Thomas Nolte
Mälardalen University
Cover LITES Vol.4 Iss.2 2017
DOI: https://doi.org/10.4230/LITES-v004-i002-a003

Published 2018-01-08

Keywords

  • Resource sharing,
  • Real-time systems,
  • Multiprocessors,
  • Spin-locks

How to Cite

[1]
Afshar, S., Behnam, M., Bril, R.J. and Nolte, T. 2018. Per Processor Spin-Based Protocols for Multiprocessor Real-Time Systems. Leibniz Transactions on Embedded Systems. 4, 2 (Jan. 2018), 03:1–03:30. DOI:https://doi.org/10.4230/LITES-v004-i002-a003.
Copyright Notice

Abstract

This paper investigates preemptive spin-based global resource sharing protocols for resource-constrained real-time embedded multi-core systems based on partitioned fixed-priority preemptive scheduling. We present preemptive spin-based protocols that feature (i) an increased schedulability ratio of task sets and reduced response jitter of tasks compared to the classical non-preemptive spin-based protocol, (ii) similar memory requirements for the administration of waiting tasks as for the non-preemptive protocol whilst only causing (iii) a minimal increase of the minimal number of required stacks per core from one to at most two, and (iv) strong progress guarantees to tasks. We complement these protocols with a unified worst-case response time analysis that specializes to the classical analysis for the non-preemptive protocol. The paper includes a comparative evaluation of the preemptive protocols and the non-preemptive protocol based on synthetic data.

PDF

References

  1. Sara Afshar, Moris Behnam, Reinder J. Bril, and Thomas Nolte. Flexible spin-lock model for resource sharing in multiprocessor real-time systems. In Proceedings of the 9th IEEE International Symposium on Industrial Embedded Systems, SIES 2014, Pisa, Italy, June 18-20, 2014, pages 41-51. IEEE, 2014. URL: http://dx.doi.org/10.1109/SIES.2014.6871185
  2. Sara Afshar, Moris Behnam, Reinder J. Bril, and Thomas Nolte. On per processor spin-lock priority for partitioned multiprocessor real-time systems. Technical report, Mälardalen Real-Time Research Centre, Mälardalen University, 2014. URL: http://www.es.mdh.se/publications/3766-.
  3. James H. Anderson, Rohit Jain, and Kevin Jeffay. Efficient object sharing in quantum-based real-time systems. In Proceedings of the 19th IEEE Real-Time Systems Symposium, Madrid, Spain, December 2-4, 1998, pages 346-355. IEEE Computer Society, 1998. URL: http://dx.doi.org/10.1109/REAL.1998.739768
  4. Neil C. Audsley, Alan Burns, Mike M. Richardson, Ken Tindell, and Andy J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284-292, 1993. URL: http://dx.doi.org/10.1049/sej.1993.0034
  5. AUTOSAR release 4.1, specification of operating system, 2013. URL: http://www.autosar.org.
  6. Theodore P. Baker. Stack-based scheduling of realtime processes. Real-Time Systems, 3(1):67-99, 1991. URL: http://dx.doi.org/10.1007/BF00365393
  7. Enrico Bini and Giorgio C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. URL: http://dx.doi.org/10.1007/s11241-005-0507-9
  8. Aaron Block, Hennadiy Leontyev, Björn B. Brandenburg, and James H. Anderson. A flexible real-time locking protocol for multiprocessors. In 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), 21-24 August 2007, Daegu, Korea, pages 47-56. IEEE Computer Society, 2007. URL: http://dx.doi.org/10.1109/RTCSA.2007.8
  9. Björn B. Brandenburg. Scheduling and Locking in Multiprocessor Real-time Operating Systems. PhD thesis, University of North Carolina at Chapel Hill, Chapel Hill, NC, USA, 2011. AAI3502550.
  10. Björn B. Brandenburg and James H. Anderson. An implementation of the pcp, srp, d-pcp, m-pcp, and FMLP real-time synchronization protocols in litmus^rt. In The Fourteenth IEEE Internationl Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008, Kaohisung, Taiwan, 25-27 August 2008, Proceedings, pages 185-194. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/RTCSA.2008.13
  11. Reinder J. Bril, Elisabeth F. M. Steffens, and Wim F. J. Verhaegh. Best-case response times and jitter analysis of real-time tasks. J. Scheduling, 7(2):133-147, 2004. URL: http://dx.doi.org/10.1023/B:JOSH.0000014069.63823.e7
  12. Alan Burns and Andy J. Wellings. A schedulability compatible multiprocessor resource sharing protocol - mrsp. In 25th Euromicro Conference on Real-Time Systems, ECRTS 2013, Paris, France, July 9-12, 2013, pages 282-291. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.37
  13. Travis S. Craig. Queuing spin lock algorithms to support timing predictability. In Proceedings of the Real-Time Systems Symposium. Raleigh-Durham, NC, December 1993, pages 148-157. IEEE Computer Society, 1993. URL: http://dx.doi.org/10.1109/REAL.1993.393505
  14. Robert I. Davis and Marko Bertogna. Optimal fixed priority scheduling with deferred pre-emption. In Proceedings of the 33rd IEEE Real-Time Systems Symposium, RTSS 2012, San Juan, PR, USA, December 4-7, 2012, pages 39-50. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/RTSS.2012.57
  15. Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems.ACM Comput. Surv., 43(4):35:1-35:44, 2011. URL: http://dx.doi.org/10.1145/1978802.1978814
  16. UmaMaheswari C. Devi, Hennadiy Leontyev, and James H. Anderson. Efficient synchronization under global EDF scheduling on multiprocessors. In 18th Euromicro Conference on Real-Time Systems, ECRTS'06, 5-7 July 2006, Dresden, Germany, Proceedings, pages 75-84. IEEE Computer Society, 2006. URL: http://dx.doi.org/10.1109/ECRTS.2006.10
  17. Dario Faggioli, Giuseppe Lipari, and Tommaso Cucinotta. The multiprocessor bandwidth inheritance protocol. In 22nd Euromicro Conference on Real-Time Systems, ECRTS 2010, Brussels, Belgium, July 6-9, 2010, pages 90-99. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/ECRTS.2010.19
  18. Paolo Gai, Giuseppe Lipari, and Marco Di Natale. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. In Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS 2001), London, UK, 2-6 December 2001, pages 73-83. IEEE Computer Society, 2001. URL: http://dx.doi.org/10.1109/REAL.2001.990598
  19. Paolo Gai, Giuseppe Lipari, and Marco Di Natale. Stack size minimization for embedded real-time systems-on-a-chip. Design Autom. for Emb. Sys., 7(1-2):53-87, 2002. URL: http://dx.doi.org/10.1023/A:1019795414875
  20. Paolo Gai, Marco Di Natale, Giuseppe Lipari, Alberto Ferrari, Claudio Gabellini, and Paolo Marceca. A comparison of MPCP and MSRP when sharing resources in the janus multiple-processor on a chip platform. In Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2003), May 27-30, 2003, Toronto, Canada, page 189. IEEE Computer Society, 2003. URL: http://dx.doi.org/10.1109/RTTAS.2003.1203051
  21. Theodore Johnson and Krishna Harathi. A prioritized multiprocessor spin lock.IEEE Trans. Parallel Distrib. Syst., 8(9):926-933, 1997. URL: http://dx.doi.org/10.1109/71.615438
  22. Leonidas I. Kontothanassis, Robert W. Wisniewski, and Michael L. Scott. Scheduler-conscious synchronization.ACM Trans. Comput. Syst., 15(1):3-40, 1997. URL: http://dx.doi.org/10.1145/244764.244765
  23. John M. Mellor-Crummey and Michael L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors.ACM Trans. Comput. Syst., 9(1):21-65, 1991. URL: http://dx.doi.org/10.1145/103727.103729
  24. Ragunathan Rajkumar. Synchronization in Real-Time Systems: A Priority Inheritance Approach. Kluwer Academic Publishers, Norwell, MA, USA, 1991.
  25. Ola Redell and Martin Sanfridson. Exact best-case response time analysis of fixed priority scheduled tasks. In 14th Euromicro Conference on Real-Time Systems (ECRTS 2002), 19-21 June 2002, Vienna, Austria, Proceedings, pages 165-172. IEEE Computer Society, 2002. URL: http://dx.doi.org/10.1109/EMRTS.2002.1019196
  26. Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky. Priority inheritance protocols: An approach to real-time synchronization.IEEE Trans. Computers, 39(9):1175-1185, 1990. URL: http://dx.doi.org/10.1109/12.57058
  27. H. Takada and K. Sakamura. Predictable spin lock algorithms with preemption. In 11th IEEE Workshop on Real-Time Operating Systems and Software (RTOSS'94), pages 2-6, 1994. URL: http://dx.doi.org/10.1109/RTOSS.1994.292571
  28. Hideyuki Takada and Ken Sakamura. A novel approach to multiprogrammed multiprocessor synchronization for real-time kernel. In Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS '97), December 3-5, 1997, San Francisco, CA, USA, pages 134-143. IEEE Computer Society, 1997. URL: http://dx.doi.org/10.1109/REAL.1997.641276
  29. Alexander Wieder and Björn B. Brandenburg. On spin locks in AUTOSAR: blocking analysis of fifo, unordered, and priority-ordered spin locks. In Proceedings of the IEEE 34th Real-Time Systems Symposium, RTSS 2013, Vancouver, BC, Canada, December 3-6, 2013, pages 45-56. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/RTSS.2013.13