EN 
DE Time-critical paths throughout the entire system
Authors: Christian Dietrich, Leibniz University Hannover, Peter Wägemann, Friedrich-Alexander University Erlangen-Nuremberg
Contribution – Embedded Software Engineering Congress 2017
To guarantee the timeliness of tasks in real-time systems, determining worst-case response times is essential. The challenge lies in precisely analyzing all activities of the entire system, such as synchronous system calls and asynchronous interrupts, without making overly pessimistic assumptions. To solve this problem, we developed the SysWCET analysis approach, which enables the first integrated formulation of the response time problem. This formulation encompasses the complete computing system, taking into account all tasks, all interrupts, and the schedule.
Response time analysis of real-time systems
The worst-case response time (WCRT) for processing a task is a crucial metric for real-time systems that must deliver results within specific time constraints. WCRT measures the duration from the occurrence of a (physical) event (e.g., a hardware interrupt) until the delivery of the result (e.g., setting a motor parameter). It thus characterizes the end-to-end response time of a task. However, when considering a system that processes multiple tasks using multiple threads, calculating the WCRT for a task is significantly more complex than calculating the worst-case execution time of the task while neglecting other threads. For example, hardware interrupts can asynchronously interrupt an executing thread, leading to an increase in the response time of the interrupted thread. Furthermore, activating the real-time operating system (RTOS) via a system call can lead to pre-emption if a higher-priority thread becomes executable. Both cases, asynchronous and synchronous preemptions, can also occur in combination if the RTOS is enabled in interrupt handling. Consequently, the entire system (RTOS, interrupts, other threads) must always be considered for the correct calculation of the WCRT of a task.
Problems with composite response time analysis
Traditionally, WCRT analysis is performed in two steps. First, each activity (threads and interrupt handlers) is considered in isolation, and a WCET is calculated pessimistically. Here, the RTOS acts as a boundary that the analysis cannot exceed. In the second step, these WCETs are then accumulated pessimistically based on the scheduling strategy. Thus, the WCETs of all higher-priority tasks are added to the WCET of the task under consideration (see Figure 1)., PDF).
In this example, a WCET is first calculated for both threads (A, B), the interrupt service routine (ISR), and the RTOS (ISR=300, A=103, B=200, RTOS=21). To calculate the WCRT for thread A, one starts with the WCET for A: 103 cycles. If thread B has a higher priority, the costs for B and the two RTOS activations (one way and one way) are added: 103 + 2 × 21 + 200 = 345 cycles. Activating the ISR also results in a total of: 345 + 2 × 21 + 300 = 687 cycles.
The problem with this composite WCRT analysis is, firstly, its coarse granularity at the thread level, and secondly, the inability to formulate interactions between threads. In very few real-time systems are the individual tasks independent of each other. The longest path in one thread may not occur simultaneously with the longest path in another thread. The previous example will now be examined in greater detail (see Figure 2)., PDF).
From the control flow graph of Thread A, we know that Thread B can only be activated if the rightmost path, which is not the longest path through A, is traversed. Furthermore, it can be assumed that not every path through the kernel has the same execution time. With this knowledge alone, which can be derived directly from the structure of the overall system, a more precise WCRT estimate can be made.
Furthermore, domain experts often possess additional knowledge about the system's behavior. For example, interrupts may be restricted and only occur in the left path of Thread A. Additionally, it's possible that the ISR takes the first of the two outputs when it interrupts Thread A.
Bringing all this knowledge together, it becomes clear that the path representing the longest WCRT for this example system has the following course: Start in Thread A, right path, activation and switch to Thread B, processing of B, switch to A, end in A. In total, this results in a WCRT of 1+10+14+200+11+2=238 cycles, which is significantly more precise than the WCRT of 687 cycles determined by composite analysis.
In our research, we developed SysWCET[1]: an automated end-to-end response time analysis for OSEK systems. Using an integrated problem formulation, we not only capture application and kernel code, but also offer the possibility of formulating cross-thread dependencies.
Holistic system analysis of OSEK systems
SysWCET is based on an analysis[2] of entire OSEK systems, which considers not only the static configuration but also the dynamic interaction between application code and the operating system. In summary, this interaction can be described by the global control flow, which runs through both the application's program logic and the kernel: A thread makes a system call, thereby changing the kernel state; the kernel reacts to this change and switches to the control flow of another thread.
The OSEK-OS standard, which is largely also included in AUTOSAR, forms the basis of our systems. Developed in the automotive industry, the OSEK standard describes static real-time systems used on electronic control units (ECUs). "Static" here refers to the fact that the system configuration is fixed at compile time. In a configuration file (OIL file), the developer defines, for example, which threads exist, where their entry points are, their priority, and whether a thread can wait for a software event.
In the first step of our analysis, we read this configuration and extract the control-flow graphs (CFGs) of all functions from the application code. To facilitate the analysis of the extracted application logic, we group larger regions within the CFGs into atomic basic blocks (ABBs), which are executed atomically from the perspective of the operating system kernel. An ABB thus comprises the code between two system calls.
In the next step of the analysis, we combine the CFGs, the system configuration, and the OSEK semantics to obtain the system's state-transition graph (STG). Starting with the operating system's state at boot, we explicitly traverse all system states, thus obtaining all possible paths through the entire system in a single graph. This will now be illustrated in the following example.
In Figure 3 (see PDFFigure 1 shows an example system with three threads and an Interrupt Service Routine (ISR). The low-priority thread, Low, is started and activates the high-priority thread, High, in its rightmost path. To keep the example clear, the interrupt that activates the ISR can only occur in Figures 1 and 4. When the ISR is executed, it always activates the middle-priority thread, Med.
In Figure 4 (see PDFThe entire state graph for the example application is shown in Figure 1. Each node corresponds to a single system state, which includes, among other things, the program counter of the currently running thread and the list of all executable threads (not shown). The edges indicate how the system can switch between these states through system calls, interrupts, or the application logic. In the start state (edge a), Thread Low will execute ABB 1, where three things can happen: (1, edge f) The left path in A is taken, and we execute ABB 3 next. (2, edge b) We execute ABB 2 next, which in turn activates Thread High (edge c). (3, edge x) An interrupt occurs, Low is evicted, and Thread Med, activated by the ISR, is executed first before Thread Low continues in ABB 1 (edge h).
Response time analysis as an ILP problem
The STG (System Task Group) is the union of all possible instruction sequences (execution paths) through the entire system (including interrupts and RTOS). To calculate the worst possible response time for a task, we need to find the longest path on the STG between the first and last instructions of the task. For this purpose, we apply the implicit path-enumeration technique (IPET) at the system level.
IPET is already used at the program level to determine the WCET of a program. The control flow graph of a program is formulated as an optimization problem and translated into an integer linear program (ILP). During optimization, the execution frequency for each base block is determined and weighted by its execution time.
Since the STG is a control flow graph, we can use IPET to formulate an ILP that contains a state frequency for each system state, indicating how often that state is visited in the worst-case scenario. Furthermore, we embed an ILP fragment formulated using IPET for each ABB and derive its activation frequency from the state frequencies. In this way, we obtain an integrated ILP that includes both the possible global control flows resulting from the scheduling and the instruction level.
To determine the scalability of the SysWCET methodology, we examined the control software of a quadcopter, which consists of 11 threads, 3 alarms, and one ISR. Within minutes, we were able to test WCRT for various tasks in this application, even though these tasks interrupt each other and use the RTOS for synchronization.
Summary
With SysWCET, we have developed an analytical approach for system-wide response time analysis that considers all relevant activities of the real-time system and summarizes them in a unified problem definition. Complete systems can be automatically analyzed with a reasonable analysis effort of just a few minutes to determine reliable response time bounds. The SysWCET implementation is available under an open-source license. https://gitlab.cs.fau.de/syswcet
literature
[1] C. Dietrich, P. Wägemann, P. Ulbrich, D. Lohmann; SysWCET: Whole-System Response-Time Analysis for Fixed-Priority Real-Time Systems; in Proceedings of the 23rd Real-Time and Embedded Technology and Applications Symposium (RTAS '17), 2017
[2] C. Dietrich, M. Hoffmann, D. Lohmann; Global Optimization of Fixed-Priority Real-Time Systems by RTOS-Aware Control-Flow Analysis; ACM Transactions on Embedded Computing Systems (ACM TECS), no. 16, 2017
Download the article as a PDF file
Real-time – MicroConsult Training & Coaching
Do you want to bring yourself up to date with the latest technology?
Then find out more here MircoConsult offers training courses/seminars/workshops and individual coaching on the topic of embedded and real-time software development.
Training & coaching on the other topics in our portfolio can be found here. here.
Real-time expertise
Valuable expertise in the field of embedded and real-time software development is available. here Available for you to download free of charge.
You can find expertise on other topics in our portfolio here. here.
