https://www.mdu.se/

We present a method that enables an efficient implementation of the approximative response-timeanalysis (RTA) for tasks with offsets presented by Tindell [(1992)] and Palencia Gutierrez et al. [(1998)]. The method allows for significantly faster implementations of schedulability tools using RTA. Furthermore, reducing computation time, from tens of milliseconds to just a fraction of a millisecond, as we show, is a step towards online RTA in for example admission control systems. We formally prove that our reformulation of earlier presented equations is correct and allow us to statically represent parts of the equation, reducing the calculations during fix-point iteration. We show by simulations that the speedup when using our method is substantial. When task sets grow beyond a trivial number of tasksand/or transactions a speed-up of more than 100 times (10 transactions and 10 tasks/transaction) compared to the original analysis can be obtained.

In previous work, we presented a tight approximate response-time analysis for tasks with offsets. While providing a tight bound on response times, the tight analysis exhibits similarly long execution times as does the traditional methods for calculating response-times for tasks with offsets. The existing method for fast analysis of tasks with offsets is not applicable to the tight analysis. In this paper we extend the fast analysis to handle the distinguishing trait of the tight analysis; continuously increasing interference functions. Furthermore, we provide another speedup; by introducing pessimism in the modelling of interference at certain points, we speed up the convergence of the numerical solving for response-times without increasing the pessimism of the resulting response-times. The presented fast-and-tight analysis is guaranteed to calculate the same response-times as the tight analysis, and in a simulation study we obtain speedups of more than two orders of magnitude for realistically sized tasks sets compared to the tight analysis. We also demonstrate that the fast-and-tight analysis has comparable execution time to that of the fast analysis. Hence, we conclude that the fast- and-tight analysis is the preferred analysis technique when tight estimates of response-times are needed, and that we do not need to sacrifice tightness for analysis speed; both are obtained with the fast-and-tight analysis.

This paper will show how advanced embedded realtime systems, with functionality ranging from time-triggered control functionality to event-triggered user interaction, can be made more efficient. Efficient with respect to development effort as well as run-time resource utilization. This is achieved by using a hybrid, static and dynamic, scheduling strategy. The approach is applicable even for hard real-time systems since tight response time guarantees can be given by the response time analysis method for tasks with offsets. An industrial case study will demonstrate how this approach enables more efficient use of computational resources, resulting in a cheaper or more competitive product since more functionality can be fitted into legacy, resource constrained, hardware.