Software Transactional Memory for Real-Time Systems

Funded by NSF Computer Systems Research Program.

PI: Jim Anderson.

The Challenge.

Safety-critical real-time applications must be certified before being deployed. Considering today's hardware landscape, it is desirable for such applications to be able to leverage the considerable processing power afforded by multicore machines. However, certifying real-time constraints on such machines is challenging due to parallelism-related issues. One aspect of an application's design that parallelism seriously complicates is the need for efficient task synchronization. In work on throughput-oriented computing, this need has been the driving force behind considerable recent work on a concept called transactional memory (TM), which can be realized in software, hardware, or some combination of the two. When a TM framework is employed, programmers must merely annotate code sections that require synchronization; the TM framework itself determines how synchronization is actually achieved. The goal for such a framework is to enable programmers to more easily produce correct performant code.

There has been relatively little work to date on TM frameworks for safety-critical real-time systems, yet an especially strong case for TM can be made in this setting. Certification is time-consuming and expensive. For example, for a large aircraft, total software development costs can easily exceed $1 billion, and 50% of this amount is typically due to certification. To ease such costs, it is very desirable to reuse previously certified hardware and software components, including the real-time operating system (RTOS) and any middleware employed. In the same way, the certification process regarding synchronization could be greatly eased if a certified real-time TM framework were available that enables real-time-related synchronization choices to be automatically and correctly resolved. This project is directed at the development of such a framework in the form of real-time software transactional memory (STM).

The Approach.

The development of the proposed real-time STM framework will be shaped by the fundamental thesis that real-time STM should be lock-based and avoid retry-based mechanisms. This thesis goes against the prevailing view concerning STM in prior work. However, almost all of this prior work has been directed at throughput-oriented systems, where average-case performance is the main concern, and retry-based mechanisms are used, most typically in the context of non-blocking synchronization techniques. Such mechanisms can be effective if transaction retries are rare on average. In a real-time system, however, correctness hinges on the worst case, and worst-case bounds on transaction retries can be unacceptably high on multicore machines.

The research agenda to be followed in developing the proposed real-time STM framework will involve work on new optimal contention-sensitive multiprocessor real-time locking protocols, new analysis for certifying timing requirements that more tightly accounts for priority-inversion blocking (pi-blocking), new static-analysis methods that enable real-time locking protocols to be automatically configured to lessen pi-blocking, and experimental-evaluation efforts involving multicore platforms of various designs.

Significance.

The advent of multicore technology has created serious certification issues in the design of complex cyber-physical systems, such as in the avionics and automotive arenas. There is currently much uncertainty in industry as to how to move forward in this regard. The research in this project would provide infrastructure that would alleviate such certification issues as they pertain to synchronization.



Key Publications


C. Nemitz, T. Amert, and J. Anderson, " Real-Time Multiprocessor Locks with Nesting: Optimizing the Common Case", Real-Time Systems, special issue of outstanding papers from the 25th International Conference on Real-Time Networks and Systems (RTNS 2017), Volume 55, Issue 2, pages 296-348, April 2019. PDF . Appendix with additional graphs: PDF . Code: Tar Ball .


C. Nemitz, T. Amert, M. Goyal, and J. Anderson, " Concurrency Groups: A New Way to Look at Real-Time Multiprocessor Lock Nesting", Proceedings of the 27th International Conference on Real-Time Networks and Systems, November 2019, to appear. PDF . Additional appendices: PDF . Code: Compressed tar file .


C. Nemitz and J. Anderson, " Work in Progress: Lock-Based Software Transactional Memory for Real-Time Systems", Proceedings of the 39th IEEE Real-Time Systems Symposium, pp. 147-150, December 2018. PDF .


C. Nemitz, T. Amert, and J. Anderson, " Using Lock Servers to Scale Real-Time Locking Protocols: Chasing Ever-Increasing Core Counts", Proceedings of the 30th Euromicro Conference on Real-Time Systems, pp. 25:1-25:24, July 2018. Winner, best paper award. PDF . Longer version with full appendices: PDF . Code: Tar Ball .


C. Nemitz, T. Amert, and J. Anderson, " Real-Time Multiprocessor Locks with Nesting: Optimizing the Common Case", Proceedings of the 25th International Conference on Real-Time Networks and Systems, pp. 38-47, October 2017. Winner, best student paper award. PDF . Longer version with appendices and additional graphs: PDF . Code: Compressed tar file .


Other papers that acknowledge this grant can be found on the PI's Publications Page .



Last modified 6 August 2019