Published 2018-01-08
Keywords
- Resource sharing,
- Real-time systems,
- Multiprocessors,
- Spin-locks
How to Cite
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.
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