Real-time calculus : revisit and improvement

Abstract

Real-time systems widely exist in our daily life, e.g., avionics, automotive electronics, wireless communications. In a real-time system, the correctness of the system behavior depends not only on the logical results of the computations, but also on the physical instant at which these results are produced. Satisfying the time constraints of a real-time system is equally or even more important than other aspects of performance requirements, thus developing analysis techniques to determine the whether time constraints are satisfed deserves the most concern. As a real-time performance analysis framework, Real-Time Calculus is proved to be appropriate for networked real-time systems, providing the suffciently expressive and effective analysis for timing behaviors. This thesis revisits Real-Time Calculus, improves the analysis of fundamental abstract components and proves the correctness of basic properties, thus improving the overall timing analysis of real-time systems under the Real-Time Calculus framework. In detail, the work in this thesis includes (1) Improving the analysis of GPC (Greedy Processing Component), which is a fundamental abstract component in Real-Time Calculus and mainly applied for modeling priority-based resource arbitration. The improvement involves two aspects: First, this thesis revises the misunderstanding part in the original proof of calculating output curves in GPC and confirms the correctness of existing calculations for output curves of GPC. Second, two different methods are proposed to derive more precise output arrival curves of GPC, thus improving the analysis preciseness of GPC. (2) Improving the analysis of AND connector, another widely used abstract component for synchronization operations. This thesis first identifies a problem in the existing analysis of AND connector that may lead to negative values in the output curves, and presents corrections to the problem. Then the existing dual-input AND connector is generalized to synchronize more than two input event streams. (3) Proving the Pay-Burst-Only-Once property in Real-Time Calculus. Pay-Burst-Only-Once is one of the most important properties in Network Calculus, the root of Real-Time Calculus. Naturally, people would expect the Pay-Burst-Only-Once property to also hold in Real-Time Calculus since Real-Time Calculus builds up on and shares many similarities with Network Calculus. In fact, existing work has used it in some performance analysis problems. Unfortunately, the Pay-Burst-Only-Once property has never been proved in Real-Time Calculus. There are even some results seeming to be against the Pay-Burst-Only-Once property in Real-Time Calculus. As a result, it leaves an important open problem to fnd out whether the Pay-Burst-Only-Once property holds in RTC. This thesis answers this problem by proving that the property indeed holds. Besides, this thesis improves global EDF scheduling by integrating analysis techniques of Network Calculus and real-time scheduling theory. Different from most existing analysis techniques analyzing sporadic tasks for global EDF, this thesis considers bursty tasks which have more general arrival patterns. In detail, shapers are adopted to eliminate burst in original system inputs and generate sporadic job sequences, and then the delay bound of each task is calculated. To further improve the proposed approach, a heuristic algorithm is designed to make as more tasks as possible to meet their deadlines by adjusting settings of shapers. All the above theoretical results are implemented in Real-Time Calculus Toolbox and experiments show that the proposed methods and algorithms can lead to improvement of precision and effciency.