To content
Department of Computer Science

Open Source and Free Software

In the following, open source and free software authored by DAES staffs are provided. The related publications are also provided in preprint format. If you use our contributions in your work, please refer to the corresponding publication. Note that the copyrights of the paper publications are associated with organizations like IEEE, ACM, etc.

Please contact Dr.-Ing. Kuan-Hsun Chen or the relevant authors if you have any further questions.

Supporting Multiprocessor Resource Synchronization Protocols in RTEMS

When considering recurrent tasks in real-time systems, concurrent accesses to shared resources, can cause race conditions or data corruptions. Such a problem has been extensively studied since the 1990s, and numerous resource synchronization protocols have been developed for both uni-processor and multiprocessor real-time systems, with the assumption that the implementation overheads are negligible. However, in practice, the implementation overheads may impact the performance of different protocols depending upon the practiced scenarios, e.g., resources are accessed locally or remotely, and tasks spin or suspend themselves when the requested resources are not available. In this paper, to show the applicability of different protocols in real-world systems, we detail the implementation of several state-of-the-art multiprocessor resource synchronization protocols in RTEMS. To study the impact of the implementation overheads, we deploy these implemented protocols on a real platform with synthetic task set. The measured results illustrate that the developed resource synchronization protocols in RTEMS are comparable to the existed protocol, i.e., MrsP.

Citation:
Junjie ShiJan Duy Thien PhamMalte MünchJan Viktor HafemeisterJian-Jia ChenKuan-Hsun Chen, Supporting Multiprocessor Resource Synchronization Protocols in RTEMS, arXiv:2104.06366, April 2021

The source will be released soon. Paper can be founded here.

Evaluation Framework for Self-Suspending Task Systems

In the real-time system community, the performance of newly designed scheduling algorithms or schedulability tests is typically examined either by theoretical methods, like dominance relations or speedup factors, or using empirical evaluations. Such empirical methods often evaluate the acceptance ratio of the new algorithm/test compare to other algorithms/tests based on synthesized task sets. However, it is often difficult to perform such a comparison since not all implementations are publicly available, use a different programming language, a different task generator, etc. Hence, for self-suspending tasks, we provide an easy to use evaluation framework with a preimplemented task generator, some pre-implemented schedulability tests, and an integrated plotting tool. The framework is written in Python and can be extended by including additional schedulability tests.

Citation:
Georg von der Brüggen, Milad Nayebi, Junjie Shi, Kuan-Hsun Chen, and Jian-Jia Chen, Evaluation Framework for Self-Suspending Task Systems, 10th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2019), July 2019

Paper

Repository

Event-based Miss Rate Simulator and Deadline Miss Rate

Timeliness is an important feature for many embedded systems. Although soft real-time embedded systems can tolerate and allow certain deadline misses, it is still important to quantify them to justify whether the considered systems are acceptable. In this paper, we provide a way to safely over-approximate the expected deadline miss rate for a specific sporadic real-time task under fixed-priority preemptive scheduling in uniprocessor systems. Our approach is compatible with the existing results in the literature that calculate the probability of deadline misses either based on the convolution-based approaches or analytically. We demonstrate our approach by considering randomly generated task sets with an execution behavior that simulates jobs that are subjected to soft errors incurred by hardware transient faults under a given fault rate. To empirically gather the deadline miss rates, we implemented an event-based simulator with a fault-injection module and release the scripts. With extensive simulations under different fault rates, we evaluate the efficiency and the pessimism of our approach. The evaluation results show that our approach is effective to derive an upper bound of the expected deadline miss rate and efficient with respect to the required computation time.

Citation:

Kuan-Hsun Chen, Georg von der Brüggen, and Jian-Jia Chen, "Analysis of Deadline Miss Rates for Uniprocessor Fixed-Priority Scheduling", RTCSA 2018: 168-178

Preprint 

Repository

Analytical Approaches for Deadline-Miss Probability

In soft real-time systems, applications usually can tolerate rare deadline misses. Therefore, probabilistic arguments and analyses are applicable in the timing analyses for this class of systems, as demonstrated in many existing researches. Convolution-based analyses allow deriving tight deadline-miss probabilities, but suffer from a high time complexity. Among the analytical approaches, which result in a significantly faster runtime than the convolution-based approaches, the Chernoff bounds provide the tightest results.

One applicable application for the above analytical approaches is transient-fault tolerance with software fault-tolerant techniques. The execution time of a job of a sporadic/periodic task may differ, depending upon the occurrence of soft errors and the applied error detection and recovery mechanisms. We model a periodic/sporadic real-time task under such a scenario by using two different worst-case execution times (WCETs), in which one is with the occurrence of soft errors and another is not. Based on a probabilistic soft-error model, the WCETs are hence with different probabilities. 

Here we include all the analytical techniques we proposed in SIES 2017, ECRTS 2018 and DATE 2019.

Citation:
Kuan-Hsun Chen and Jian-Jia Chen, Probabilistic Schedulability Tests for Uniprocessor Fixed-Priority Scheduling under Soft Errors, SIES 2017: 1-8.

Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, Katharina Morik, "Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems", ECRTS 2018: 6:1-6:22

Kuan-Hsun Chen, Niklas Ueter, Georg von der Brüggen, and Jian-Jia Chen, "Efficient Computation of Deadline-Miss Probability and Potential Pitfalls", DATE 2019: 896-901

Preprint: SIES 2017ECRTS 2018 and DATE 2019

Repository

Overrun Handling in RTEMS

Real-time operating systems are not only used in embedded real-time systems but also useful for the simulation and validation of those systems. During the evaluation of our paper about Systems with Dynamic Real-Time Guarantees that appears in RTSS 2016 we discovered certain unexpected system behavior in the open-source real-time operating system RTEMS. In the current implementation of RTEMS (version 4.11), overruns of an implicit-deadline task, i.e., deadline misses, result in unexpected system behavior as they may lead to a shift of the release pattern of the task. This also has the consequence that some task instances are not released as they should be. In the paper we explain the reason why such problems occur in RTEMS and our solutions. The proposed solution now is adopted into the current implementation of RTEMS (version 4.12).

Citation:
Kuan-Hsun Chen, Georg von der Brüggen and Jian-Jia Chen, Overrun Handling for Mixed-Criticality Support in RTEMS, In 4th International Workshop on Mixed-Criticality Systems (WMC), Porto, Portugal, November 2016.

Paper

Repository

Implementation and Evaluation of Multiprocessor Resource Synchronization Protocol (MrsP) on LITMUSRT

Preventing race conditions or data corruptions for concurrent shared resource accesses of real-time tasks is a challenging problem. By adopting the resource synchronization protocols, such a problem has been studied in the literature, but there are not enough evaluations that consider the overhead from the implementations of different protocols. In this paper, we discuss our implementation of the Multiprocessor Resource Sharing Protocol (MrsP) and the Distributed Non-Preemptive Protocol (DNPP) on LITMUS RT . Both of them are released in open source under GNU General Public License (GPL2). To study the impact of the implementation overhead, we deploy different synchronization scenarios with generated task sets and measure the performance with respect to the worst-case response time. The results illustrate that generally the implementation overhead is acceptable, whereas some unexpected system overhead may happen under distributed synchronization protocols on LITMUSRT.

Citation:
Junjie Shi, Kuan-Hsun Chen, Shuai Zhao, Wen-Hung Huang, Jian-Jia Chen, and Andy Wellings, Implementation and Evaluation of Multiprocessor Resource Synchronization Protocol (MrsP) on LITMUSRT, 13th Workshop on Operating Systems Platforms for Embedded Real-Time Applications, Dubrovnik, Kroatia, June 2017.

Paper

Repository

Saturn: An Integrated Simulator for Power and Thermal Management Algorithm Development

Due to the diversity of the hardware architectures and the uncertainty of the workloads, processor and system designers prefer to apply simulation-based method to design and evaluate power and thermal management algorithms. Saturn is an integrated, powerful, and efficient simulator. It consists of three well-known simulators, namely, Sniper, a many core processor simulator; McPAT, a power dissipation simulator, and HotSpot, a thermal simulator. Saturn establishes an integrated environment for developing and evaluating power and thermal management algorithms for many-core processors, which realizes a dynamic closed loop processing control flow and provides completed interfaces as well as tracing mechanism for designers. Saturn is released in open source under GNU General Public License (GPL2).

Paper will come later.

Manual

Repository