Energiebeschränkte Echtzeitsysteme und ihre Worst-Case-Analysen

The increasing number of embedded systems spawns applications with critical constraints in both execution time and energy consumption. For their reliable operation, these energy-constrained real-time systems require bounds of their tasks' execution time as well as energy consumption in order to guarantee the completion within given resource budgets. While traditional worst-case program-code-analysis tools perform well in determining the worst-case execution time of tasks, they are not directly applicable to the problem of energy consumption: For the determination of energy-consumption bounds, it is insufficient to only consider real-time scheduling priorities, because any task can temporarily activate devices (e.g., transceivers) and thereby contribute to the whole system's power demand. This power demand, in turn, influences the energy consumption of all tasks in the system, irrespective of real-time priorities. Additional to the missing approaches for energy-consumption bounds, static worst-case analyzers, in general, come with the fundamental problem of unknown accuracies in the reported worst-case bounds. Since the actual worst case is not available from any benchmark program, it is impossible to compare the analyzer's reported bound and assess its pessimism, which inherently prevents comprehensive evaluations and validations of analysis techniques. This thesis addresses these problems by first presenting an approach to determining energy-consumption bounds while accounting for temporarily active devices, the fixed-priority real-time scheduling, synchronous task activations, and asynchronous interrupts. Since the analysis approach context-sensitively includes all possible interferences, it eventually determines the worst-case response energy consumption (WCRE) of tasks. The approach initially decomposes the target system under consideration of scheduling- and energy-relevant events. While relying on the decomposed representation, the approach then explores all possible system-wide program paths. Knowledge of these explored paths eventually allows determining WCRE bounds with means of sound problem formulations. To address the problem of the bounds' analysis pessimism, this thesis introduces a novel approach to assessing the accuracy of analyzers based on automatically generated benchmarks. This benchmark-generation algorithm combines small program patterns in a way that the worst case is available together with the woven benchmark. Knowledge of the generated benchmark's actual worst case then serves as a baseline for comprehensive evaluations and validations. The worst-case analysis approaches and their validation are the foundation to enable safe schedules. To complete the necessary components for reliably operating energy-constrained real-time systems, this thesis presents an operating-system kernel that utilizes worst-case resource bounds for time and energy. The kernel's scheduling approach dynamically reacts to scenarios where one resource becomes more critical than the other. This approach is aware of said analysis pessimism and effectively makes use of it while still guaranteeing the execution of critical tasks within statically determined time and energy bounds