Document Open Access Logo

Overrun-Resilient Multiprocessor Real-Time Locking

Authors Zelin Tong, Shareef Ahmed, James H. Anderson

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2022.10.pdf
  • Filesize: 0.81 MB
  • 25 pages

Document Identifiers

Author Details

Zelin Tong
  • University of North Carolina at Chapel Hill, NC, USA
Shareef Ahmed
  • University of North Carolina at Chapel Hill, NC, USA
James H. Anderson
  • University of North Carolina at Chapel Hill, NC, USA

Funding

Supported by NSF grants CPS 1837337, CPS 2038855, and CPS 2038960, ARO grant W911NF-20-1-0237, and ONR grant N00014-20-1-2698.

Cite As Get BibTex

Zelin Tong, Shareef Ahmed, and James H. Anderson. Overrun-Resilient Multiprocessor Real-Time Locking. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ECRTS.2022.10

Abstract

Existing real-time locking protocols require accurate worst-case execution time (WCET) estimates for both tasks and critical sections (CSs) in order to function correctly. On multicore platforms, however, the only seemingly viable strategy for obtaining such estimates is via measurements, which cannot produce a true WCET with certainty. The absence of correct WCETs can be partially ameliorated by enforcing execution budgets at both the task and CS levels and by using a locking protocol that is resilient to budget overruns, i.e., that ensures that the schedulability of non-overrunning tasks is not compromised by tasks that do overrun their budgets. Unfortunately, no fully overrun-resilient locking protocol has been proposed to date for multiprocessor systems. To remedy this situation, this paper presents two such protocols, the OR-FMLP and the OR-OMLP , which introduce overrun-resiliency mechanisms to two existing multiprocessor protocols, the spin-based FMLP and suspension-based global OMLP, respectively. In devising such mechanisms, undo code can be problematic. For the important locking use case of protecting shared data structures, it is shown that such code can be avoided entirely by using abortable critical sections, a concept proposed herein that leverages obstruction-free synchronization techniques. Experiments are presented that demonstrate both the effectiveness of the mechanisms introduced in this paper and their cost.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • Real-Time Systems
  • Real-Time Synchronization
  • Budget Enforcement

Metrics

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

Related Versions

Supplementary Materials

References

  1. A. Alon and A. Morrison. Deterministic abortable mutual exclusion with sublogarithmic adaptive rmr complexity. In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing, pages 27-36, 2018. Google Scholar
  2. J. Anderson, R. Jain, and K. Jeffay. Efficient object sharing in quantum-based real-time systems. In Proceedings of the 19th IEEE Real-Time Systems Symposium, pages 346-355, 1998. Google Scholar
  3. M. Asberg, T. Nolte, and M. Behnam. Resource sharing using the rollback mechanism in hierarchically scheduled real-time open systems. In Proceedings of the 19th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 129-140, 2013. Google Scholar
  4. S. Baruah, V. Bonifaci, and A. Marchetti-Spaccamela. The global EDF scheduling of systems of conditional sporadic DAG tasks. In Proceedings of the 27th Euromicro Conference on Real-Time Systems, pages 222-231, 2015. Google Scholar
  5. M. Behnam, T. Nolte, M. Asberg, and R. Bril. Overrun and skipping in hierarchically scheduled real-time systems. In Proceedings of the 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pages 519-526, 2009. Google Scholar
  6. M. Behnam, I. Shin, T. Nolte, and M. Nolin. Sirap: A synchronization protocol for hierarchical resource sharingin real-time open systems. In Proceedings of the International Conference on Embedded Software, pages 279-288, 2007. Google Scholar
  7. M. Bertogna, G. Buttazzo, M. Marinoni, G. Yao, F. Esposito, and M. Caccamo. Preemption points placement for sporadic task sets. In Proceedings of the 22nd Euromicro Conference on Real-Time Systems, pages 251-260, 2010. Google Scholar
  8. A. Biondi, G. Buttazzo, and M. Bertogna. Supporting component-based development in partitioned multiprocessor real-time systems. In Proceedings of the 27th Euromicro Conference on Real-Time Systems, pages 269-280, 2015. Google Scholar
  9. A. Block, H. Leontyev, B. Brandenburg, and J. Anderson. A flexible real-time locking protocol for multiprocessors. In Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pages 47-56, 2007. Google Scholar
  10. B. Brandenburg. Scheduling and Locking in Multiprocessor Real-time Operating Systems. PhD thesis, University of North Carolina at Chapel Hill, 2011. Google Scholar
  11. B. Brandenburg. Multiprocessor Real-Time Locking Protocols, pages 1-99. Springer, 2020. Google Scholar
  12. B. Brandenburg and J. Anderson. Optimality results for multiprocessor real-time locking. In Proceedings of the 31st IEEE Real-Time Systems Symposium, pages 49-60, 2010. Google Scholar
  13. A. Burns. Preemptive priority based scheduling: An appropriate engineering approach. Advances in Real-Time Systems, pages 225-248, 1994. Google Scholar
  14. G. Buttazzo, M. Bertogna, and G. Yao. Limited preemptive scheduling for real-time systems. A survey. IEEE Transactions on Industrial Informatics, 9(1):3-15, 2013. Google Scholar
  15. J. Calandrino, H. Leontyev, A. Block, U. Devi, and J. Anderson. LITMUS^RT: A testbed for empirically comparing real-time multiprocessor schedulers. In Proceedings of the 27th IEEE Real-Time Systems Symposium, pages 111-126, 2006. Google Scholar
  16. F. Cazorla, L. Kosmidis, E. Mezzetti, C. Hernandez, J. Abella, and T. Vardanega. Probabilistic worst-case timing analysis: Taxonomy and comprehensive survey. ACM Computing Surveys, 52(1):14:1-14:35, 2019. Google Scholar
  17. 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
  18. R. Davis and L. Cucu-Grosjean. A survey of probabilistic timing analysis techniques for real-time systems. Leibniz Transactions on Embedded Systems, 6(1):03:1-03:60, 2019. Google Scholar
  19. D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing, volume 4167, pages 194-208, 2006. Google Scholar
  20. D. Faggioli, G. Lipari, and T. Cucinotta. Analysis and implementation of the multiprocessor bandwidth inheritance protocol. Real Time Systems, 48(6):789-825, 2012. Google Scholar
  21. K. Fraser. Practical lock-freedom. PhD thesis, University of Cambridge, UK, 2003. Google Scholar
  22. T. Harris and K. Fraser. Language support for lightweight transactions. In Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programing, Systems, Languages, and Applications, pages 388-402, 2003. Google Scholar
  23. T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. Commununications of the ACM, 51(8):91-100, 2008. Google Scholar
  24. T. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing memory transactions. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 14-25, 2006. Google Scholar
  25. M. Herlihy, V. Luchangco, and M. Moir. Obstruction-free synchronization: Double-ended queues as an example. In Proceedings of the 23rd International Conference on Distributed Computing Systems, pages 522-529, 2003. Google Scholar
  26. M. Herlihy, V. Luchangco, M. Moir, and W. Scherer. Software transactional memory for dynamic-sized data structures. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, pages 92-101, 2003. Google Scholar
  27. P. Holman and J. Anderson. Locking in Pfair-scheduled multiprocessor systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium, pages 149-158, 2002. Google Scholar
  28. P. Holman and J. Anderson. Locking under Pfair scheduling. ACM Transactions on Computer Systems, 24(2):140-174, 2006. Google Scholar
  29. P. Jayanti. Adaptive and efficient abortable mutual exclusion. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, pages 295-304, 2003. Google Scholar
  30. T. Johnson and K. Harathi. Interruptible critical sections. Technical Report TR94-007, University of Florida, 1994. Google Scholar
  31. H. Kim, S. Wang, and R. Rajkumar. vMPCP: A synchronization framework for multi-core virtual machines. In Proceedings of the 35th IEEE Real-Time Systems Symposium, pages 86-95, 2014. Google Scholar
  32. N. Kim, B. Ward, M. Chisholm, C.-Y. Fu, J. Anderson, and F.D. Smith. Attacking the one-out-of-m multicore problem by combining hardware management with mixed-criticality provisioning. In Proceedings of the 22nd IEEE Real-Time Embedded Technology and Applications Symposium, pages 49-160, April 2016. Google Scholar
  33. H. Lee. Fast local-spin abortable mutual exclusion with bounded space. In Proceedings of the 14th International Conference on Principles of Distributed Systems, pages 364-379, 2010. Google Scholar
  34. C. Maiza, H. Rihani, J. Rivas, J. Goossens, S. Altmeyer, and R. Davis. A survey of timing verification techniques for multi-core real-time systems. ACM Computing Surveys, 52(3):56:1-56:38, 2019. Google Scholar
  35. V. Marathe, M. Spear, A. Acharya C. Heriot, D. Eisenstat, W. Scherer, and M. Scott. Lowering the overhead of nonblocking software transactional memory. Technical report, University of Rochester, November 2006. Google Scholar
  36. M. Nasri, G. Nelissen, and B. Brandenburg. A response-time analysis for non-preemptive job sets under global scheduling. In Proceedings of the 30th Euromicro Conference on Real-Time Systems, volume 106, pages 9:1-9:23, 2018. Google Scholar
  37. R. Rajkumar. Real-time synchronization protocols for shared memory multiprocessors. In Proceedings of the 10th International Conference on Distributed Computing Systems, pages 116-123, 1990. Google Scholar
  38. M. Scott. Non-blocking timeout in scalable queue-based spin locks. In Proceedings of the 21st Annual Symposium on Principles of Distributed Computing, pages 31-40, 2002. Google Scholar
  39. T. Springer, S. Peter, and T. Givargis. Resource synchronization in hierarchically scheduled real-time systems using preemptive critical sections. In Proceedings of the 17th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, pages 293-300, 2014. Google Scholar
  40. M. Stigge, P. Ekberg, N. Guan, and W. Yi. The digraph real-time task model. In Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 71-80, 2011. Google Scholar
  41. Z. Tong, S. Ahmed, and J. Anderson. Overrun-resilient multiprocessor real-time locking (longer version), 2022. URL: http://jamesanderson.web.unc.edu/papers/.
  42. J. Turek, D. Shasha, and S. Prakash. Locking without blocking: Making lock based concurrent data structure algorithms nonblocking. In Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 212-222, 1992. Google Scholar
  43. R. Wilhelm. Real time spent on real time (invited talk). In Proceedings of the 41st IEEE Real-Time Systems Symposium, pages 1-2, 2020. Google Scholar
  44. R. Wisniewski, L. Kontothanassis, and M. Scott. High performance synchronization algorithms for multiprogrammed multiprocessors. In Proceedings of the 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 199-206, 1995. Google Scholar
  45. K. Yang, G. Elliott, and J. Anderson. Analysis for supporting real-time computer vision workloads using OpenVX on multicore+GPU platforms. In Proceedings of the 23th International Conference on Real-Time Networks and Systems, pages 77-86, 2015. 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