Tools and Benchmarks for Real-Time Systems

WATERS'17 will hold a panel discussion on "Programming adaptive real-time systems".
The focus of the panel is detailed below. The objective of the panel is to share experiences and ideas. As such, we encourage you to suggest topics you would like to discuss during this panel.
-------
During this panel, we would like to discuss the programming of adaptive real-time systems. Here, the term adaptive refers to a system for which real-time characteristics can be modified at run-time (adding/removing tasks, changing task periods, etc), so as to cope with variations that are difficult, or even impossible, to predict (execution time, inputs from environment, ...).

We would like to focus on the software point-of-view of adaptive real-time systems programming, instead of the timing analysis point-of-view. We believe that this topic is currently not very well covered by the literature, and yet is of prime importance to the community. First, because it is a non-trivial problem and second, because assumptions made at the real-time model level may be impracticable at the functional level. For example, the popular Mixed Criticality scheduling approach assumes that low criticality tasks can be dropped when a high criticality task exceeds its initial execution time budget. However, a task that is dropped before completion must not produce side-effects, otherwise the functional correctness of the system may be compromised, which makes programming such a system is non-trivial.

For further information and references, please see attached pdf file.

A topic we would like to discuss concerns the choice of the design and programming tools. Adaptive real-time systems can be programmed with existing low-level languages (like C for instance), however it might be difficult to design and analyze large programs with complex adaptive behaviors and still guarantee correctness. Therefore, we would like to discuss higher level languages (Synchronous Languages, Simulink, etc), and their benefits and limitations for modeling adaptive real-time systems.

Hi Julien,

Thanks for proposing this panel! It looks like this paper : https://ecrts.eit.uni-kl.de/forum/viewt ... ?f=33&t=95 and also the keynote in the morning are related to the discussion you would like to have.

Best,
Sophie

Hi Sophie,

Indeed, thanks for pointing these out.

I just attached a more detailed description of the panel subject in the original post.

Best,
Julien

One interesting point from my side would be the following:

For some kind of functionalities it might be of great use to "introspect" what is going on on scheduling level. For instance, in model predictive control or when using so-called anytime algorithms, one might want to decide dynamically if another iteration of the algorithm (leading to better functional performance) can be performed.

Do you think there might be a sensible way to provide high-level programming primitives to enable such reasoning?

This is tightly related to the underlying Operating System. In most OS, it shouldn't be too complicated to get the spent/remaining execution budget of a task (though there may not be a dedicated API function). Providing language primitives to interrogate the OS on these aspects shouldn't be too hard either.

I think that the challenge here would rather be to introduce these primitives in a way such that the program can still be analyzed for schedulability. Assume for instance a program where some task A is replaced by some task A' if we realize at some point that there is not enough execution budget for A. Implicitely, this assumes that there is enough budget for A' in any case, so that either there is enough budget for A to execute and meet its deadline or instead A' executes and meet its deadline. If the condition for switching from A to A' is a mere Boolean expression, it can be quite difficult for an automated program analysis to infer this information (the pair A/A' always meets its deadline). Primitives must be built in a way such that the program clearly exhibits the fact that A never executes for more than a predefined budget.

On a related note, we proposed an alternative to scheduling introspection, which instead relies on parametric WCET analysis (https://hal.archives-ouvertes.fr/hal-01239158/). Instead of computing a constant WCET value, our proposed analysis produces a formula that depends on some dynamic parameters (e.g. cache state, input value, etc.). During execution, at job release, we can instantiate the formula (since parameter values are known at that point), check whether the obtained WCET is over some acceptable threshold and modify the program behavior accordingly, e.g. to replace A by A'. The advantage here is that A does not consume any budget at all if its WCET is too high, it is immediately replaced by A'.

At RealTime-at-work, we are developing such a language. It is called CPAL.
There are two use-cases for it. One is for timing-accurate simulation development, the second is for embedded dvpt (either by interpretation or code generation).
It is yet still immature in regards of our current discussion but the goal is to provide more and more supports. It is more high level than C.

It is really nice for timing accurate simulation for adaptive systems, and indeed harder for analysis.

Concerning @arne.hamann proposal, it looks very similar to computer graphic problem (ie frame timing). And usually it has impacts on the software architecture indeed.
Concerning @julien.forget proposal, parametric WCET is easily simulated within CPAL. Probably we should invest some time to demonstrate that by encoding some mälardalen benchmarks in CPAL...

As the panel’s focus is on the “higher level languages […] for modeling adaptive real-time systems”, two interesting topics can be explored besides the ones mentioned in the pdf.

1. Finite State Machines are widely used (e.g., Simulink) in model-based design of embedded systems. Many works (especially [1,2]) have been devoted to their implementation on a target execution platform and verification of their timing correctness.

2. Logical Execution Time, brought up in this year’s industrial challenge, is a real-time programming abstraction introduced in Giotto. This programming language imposes two constraints on task execution: i) inputs are always read at the beginning of task period and outputs are always written at its end, ii) mode switch does not terminate execution of any task. More reactive models respecting the above mentioned constraints can be proposed [3,4].


[1] M. Di Natale and H. Zeng, "Task implementation of synchronous finite state machines," 2012 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, 2012, pp. 206-211.
[2] H. Zeng and M. Di Natale, "Schedulability Analysis of Periodic Tasks Implementing Synchronous Finite State Machines," 2012 24th Euromicro Conference on Real-Time Systems, Pisa, 2012, pp. 353-362.
[3] N. F. Martinek et W. Pohlmann. Mode Switching in GIA – An Ada Based Real-Time Framework. Department of Scientific Computing, University of Salzburg.
[4] T. Kloda, B. d’Ausbourg, and L. Santinelli, "Towards a more flexible timing definition language,” in 12th International Workshop Quantitative Aspects of Programming Languages and Systems at ETAPS 2014, 2014.