HomePublicationsPhD Thesis

Real-Time Software Transactional Memory
Ref: CISTER-TR-180504       Publication Date: 29, Apr, 2018

Abstract:
The current trend in the development of recent real-time embedded systems is driven by (i) a shift from single-core to multi-core platform architectures at the hardware level; (ii) a shift from sequential to parallel programming paradigms at the software level; and finally (iii) the ever increasing demand of new functionalities (e.g. additional tasks with specific timing requirements). These trends taken together increase the complexity of the system as a whole, and have a significant impact on the type of mechanisms that are adopted in order to guarantee both the functional and non-functional correctness of the system. This holds true especially in the case where these mechanisms have to maintain the correctness of data shared between different tasks executing concurrently in parallel.
The access to shared resources (e.g. main memory) on single-core systems has traditionally relied on lock-based mechanisms. At any time instant, a single task is granted an exclusive access to each shared resource. However, assuming the new settings, i.e. multi-core architectures executing a set of potentially parallel tasks sharing data, the big picture changes. Tasks executing in parallel on different cores and sharing the same data may have to compete before completing the execution. It has been proven that lock-based synchronisation approaches, which were sound in single-core context, do not to scale to multi-cores and, furthermore, they hinder the composability of the system, unfortunately.
On the path to solving these issues, Software Transactional Memory (STM) based approaches have been proposed as promising candidates. By using these alternative techniques, the underlying STM service would solve the conflicts between contending tasks while maintaining data consistency, and critical sections would be executed speculatively -- i.e. they are executed but if the result of the computation harms the system correctness, then changes made by the computation are reverted and the results are ignored. This way, the details on how to synchronise shared data would be hidden from the programmer, thus representing a significant advantage as compared to lock-based synchronisation techniques regarding the functional correctness of the system. Regarding the non-functional correctness instead, the use of STM based approaches in real-time systems also requires the tasks timing constraints to be met. This is due to the fact that each transaction aborting and repeating multiple times before its eventual commit incurs a timing overhead that might not be negligible and, therefore, must be taken into account to prevent deadline misses at runtime.
This work considers a set of potentially parallel real-time tasks sharing data and executed on a multi-core platform. Assuming this setting, first it proposes a complete framework where an STM service is associated to a set of fully partitioned scheduling algorithms in order to improve the predictability of the system as well as guaranteeing that the timing constraints are met for all the tasks. Then, it proposes the corresponding schedulability analysis for each pair of STM and scheduling algorithms. Finally, it proposes a lightweight syntax to enrich the original Ada programming language in order to support STM for concurrent real-time applications.

António Barros

Document:

View
PDF Download
PDF