Generische und betriebssystemgewahre statische Analysen von Echtzeitapplikationen auf Ein- und Mehrkernsystemen zur Optimierung nichtfunktionaler Eigenschaften

Thesis
Generische und betriebssystemgewahre statische Analysen von Echtzeitapplikationen auf Ein- und Mehrkernsystemen zur Optimierung nichtfunktionaler Eigenschaften

Gerion Entrup PHD thesisLeibniz Universität Hannover2024.
PDF Details [BibTex]

×

BibTex Entry

@thesis{entrup:24:phd,
author = {Gerion Entrup},
entrysubtype = {Thesis},
institution = {Leibniz Universität Hannover},
title = {Generische und betriebssystemgewahre statische Analysen von Echtzeitapplikationen auf Ein- und Mehrkernsystemen zur Optimierung nichtfunktionaler Eigenschaften},
year = {2024},
}

Close

Kurzfassung (Deutsch)

Eingebettete Systeme sind in ein sie umgebendes System integrierte Rechensysteme. Im Gegensatz zu generischen Rechensystemen erfüllen sie damit nur eine, vor ihrer Inbetrieb­ nahme bereits festgelegte Funktion. Oft sind an diese Funktion auch noch zeitlich kritische Bedingungen geknüpft, die das System zu einem Echtzeitsystem machen. Beides eröffnet ein Potential für statische Maßschneiderung, das das der generischen Systeme übersteigt. Statische Maßschneiderung benötigt immer eine vorhergehende statische Analyse, die der anschließenden Optimierung die notwendigen Informationen zuführt. In dieser Arbeit bewege ich mich in diesem Feld und entwerfe dazu verschiedene betriebsgewahre statische Analysen, die eine Echtzeitanwendung um die Verwendung des Echtzeitbetriebssystems analysieren. Sie haben dabei das primäre Ziel der anschließenden Maßschneiderung und Optimierung des Echtzeitbetriebssystems auf die Anwendung und die damit einhergehende Verbesserung der nichtfunktionalen Eigenschaften des Gesamtsystems. Neben der Grundlagenvorstellung bettet der erste Teil der Arbeit dazu erstmals die ver­ wandten Vorarbeiten in einen theoretischen Kontext, der deren Schwächen aufzeigt: Sie sind in verschiedener Kombination nur auf statische Systeme anwendbar, arbeiten nur mit genau einer Echtzeitbetriebssystemschnittstelle, können nur mit Systemen mit einem Kern umgehen oder liefern keine Informationen bezüglich möglicher Optimierung. Mit ARA habe ich ein statisches Analyse-Framework geschaffen, das diese Probleme an­ geht: Es kombiniert verschiedene bestehende und neuentwickelte statische Analysen mit verschiedenen Echtzeitbetriebssystemmodellen und ist so in der Lage, eine Vielzahl von Echtzeitanwendungen automatisiert zu analysieren und passende Informationen für ei­ ne nachgelagerte Optimierung zu liefern. Konkret beinhaltet ARA die neu geschaffene statische Instanz- und Interaktionsanalyse, die Anwendungen untersuchen können, die gegen eine dynamische Echtzeitsystemschnittstelle geschrieben wurden. Sie ermitteln dort die Menge der dynamisch erstellten Betriebssystemobjekte und deren Interaktionen. Überdies ermöglicht die neu entwickelte MultiSSE eine vollständige abstrakte Analyse eines Mehrkernsystems. Sie bildet den dabei notwendigen abstrakten Betriebssystemzu­ stand über alle Kerne nur an den Stellen, an denen dieser durch Kontrollflussinformationen oder eine Zeitanalyse notwendig ist. Durch die Trennung der Analysen in betriebssystem­ spezifische und generische Teile, sowie dem Entwurf einer gemeinsamen Schnittstelle zwischen verschiedenen Echtzeitbetriebssystemen konnte ich anschließend die Analysen betriebssystemagnostisch mit Anwendungen für AUTOSAR OS, FreeRTOS, Zephyr und POSIX durchführen und evaluieren. Meine Forschungsgruppe hat verschiedene Synthesen entwickelt, die auf Basis der Analyse­ ergebnisse ein optimiertes System erzeugt haben. Wir konnten dabei die Systemstartzeit bei dynamischen Systemen um bis zu 44% senken und eine Verbesserung des Schlupfes um bis zu 35% für Mehrkernsysteme erreichen. Ich konnte überdies die Wirksamkeit der Schnittstelle mit der Analyse von 8 Echtweltanwendungen zeigen. In der Domäne der ein­ gebetteten Systeme zeigt diese Arbeit als Ergebnis somit die erfolgreiche Erweiterung von betriebssystemgewahren Analysen auf dynamische Systeme und Mehrkernsysteme sowie deren Generalisierung in einem gemeinsamen Framework, das den Vergleich und das Aus­ führen verschiedener Analysen mit Anwendungen verschiedener Echtzeitbetriebssysteme ermöglicht.

Schlüsselwörter — betriebssystemgewahre Analyse, Mehrkernanalyse, Echtzeitsysteme, dynamische Systeme

Abstract (English)

Embedded systems are computing systems integrated into a surrounding system. In contrast to generic computing systems, they only fulfill a function that is strictly predefined before runtime. Often, it additionally contains time-critical constraints that make the system a real-time system. Both properties give a potential for static optimization that exceeds that of generic systems. Static tailoring always requires a prior static analysis that provides the necessary information for the subsequent optimization. In this work, I develop multiple such static analyses. They all analyze how an application uses the real-time operating system for a following tailoring of the operating system to the application resulting in an improvement of the non-functional properties of the overall system. Besides foundational work, the first part of this thesis embeds the related existing analyses in a theoretical context for the first time, showing their weaknesses: In various combinations, these analyses only work with static systems, are only able to understand exactly one real-time–operating-system interface, can only deal with systems with one core or do not provide any information regarding possible optimization. With ARA, I have created a static analysis framework that addresses these problems: It combines various existing and newly developed static analyses with different real-time– operating-system models and is thus able to automatically analyze a variety of applications providing information for a following optimization. Specifically, ARA includes the newly created static instance and interaction analysis, two analyses that can analyze applications that are written against a dynamic real-time–operating-system interface. They determine the number of dynamically created operating-system objects and their interactions. With the MultiSSE, I have also developed an analysis that allows a complete abstract analysis of a multi-core system. It creates the necessary abstract operating-system state across all cores only at those points where it is necessary due to control flow information or a time analysis. By separating the analyses into an operating-system–specific and a generic part, as well as the design of a common interface between different real-time operating systems, I was additionally able to apply the analyses in an operating-system–agnostic way with applications for AUTOSAR OS, FreeRTOS, Zephyr and POSIX. My research group has developed various syntheses for creating an optimized system based on the analyses results. We were able to lower the system-start time for dynamic system up to 44% and an get an improvement of slack of up to 35% for multi-core systems. Furthermore, I was also able to demonstrate the effectiveness of the interface by analyzing 8 real-world applications. In the embedded-systems domain, this thesis thus demonstrates the successful extension of operating-system–aware analyses to dynamic systems and multi-core systems as well as their generalization in a common framework that enables the comparison and execution of different analyses with applications of different real-time operating systems.

keywords — operating-system aware analysis, multi-core analysis, real-time systems, dynamic systems

Source Code

The source code is available on Github in form of multiple repositories, including ARA. The meta-repo PARROT servers as start for building ARA and automatically checks out all other necessary repositories. The tag entrup-phd-thesis marks the commit relevant for this thesis.

The source code of the PHD thesis is available on Codeberg.

Artifacts

I provide a systemd container image with the evaluation artifacts. You will need Systemd-Machined to run the container.

Download (TODO)