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

Sara Afshar, Moris Behnam, Reinder J. Bril, Thomas Nolte

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.


Keywords


Resource sharing; Real-time systems; Multiprocessors; Spin-locks

Full Text:

PDF

References


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

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

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

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

AUTOSAR release 4.1, specification of operating system, 2013. URL: http://www.autosar.org.

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ragunathan Rajkumar. Synchronization in Real-Time Systems: A Priority Inheritance Approach. Kluwer Academic Publishers, Norwell, MA, USA, 1991.

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

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

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

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

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




DOI: https://doi.org/10.4230/LITES-v004-i002-a003

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v004-i002-a003-pdf1

Copyright (c) 2017 Sara Afshar, Moris Behnam, Reinder J. Bril, and Thomas Nolte

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en
To make this site work properly, we sometimes place small data files called cookies on your device. Cookies are only here to manage user sessions. Cookies aren’t required for simply visiting the site and read content.
OK




Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. | Imprint | Data Privacy Policy