Echtzeittheorie

Viele eingebettete Systeme müssen auf ihre Echtzeitfähigkeit untersucht werden. Echtzeitfähig bedeutet, dass ein Ergebnis innerhalb eines fest definierten Zeitintervalls garantiert berechnet wird. Um Systeme auf ihre Echtzeitfähigkeit zu überprüfen, werden Echtzeitanalysen verwendet. Am Institut erforschen wir solche Echtzeitanalysen.

 

 

Um ein System analytisch auf seine Echtzeitfähigkeit zu untersuchen werden die einzelnen Tasks häufig mit folgenden Parametern beschrieben:

  • Maximale Nettoausführungszeit c⁺: Die maximale Rechenzeit die eine Task ohne Berücksichtigung anderer Tasks benötigt.

  • Periode: Der zeitliche Abstand in dem Ereignisse auftreten.

  • Frist: Der Zeitpunkt relativ zum Auftreten eines Ereignisses, an dem dieses abgearbeitet sein muss.

Echtzeitanalyse mit ratenabhängigen Tasks

Bei einer Motorsteuerung gibt es Tasks mit variierenden Paramtern (Ausführungszeit, Periode, Frist) in Abhängigkeit der Motordrehzahl: sogenannte “ratenabhängige Tasks”. Die nachfolgende Abbildung zeigt eine ratenabhängige Task unter zwei verschiedenen Drehzahlen. So ist beispielsweise bei doppelter Drehzahl der Abstand zwischen zwei Ereignissen (die Periode) halb so groß:

 

 

Am Institut können Abschlussarbeiten (Projekt-, Bachelor- oder Masterarbeiten) absolviert werden, die sich mit der Erforschung von Echtzeitanalysen für ratenabhängige Tasks befassen. Mögliche Themen für ratenabhängige Tasks sind:

  • Implementierung einer exakten Antwortszeitanalyse

  • Berücksichtigung von Beziehungen zwischen ratenabhängigen Tasks

  • Echtzeitanalysen für verteilte Systeme (mit dem Real-Time Calculus)

Vergleich Antwortzeitanalyse und Echtzeitkalkühl

Innerhalb der Echtzeittheorie sind mehrere Verfahren zur Analyse bekannt. Unter anderem die Analyse mittels gezeiteter Automaten, die Antwortzeitanalyse und das Echtzeitkalkül. Insbesondere die letzten beiden Verfahren sind hier von Interesse. Für diese beiden Verfahren existieren eine Vielzahl von Arbeiten welche sich mit den unterschiedlichsten Aspekten von Echtzeitsystemen beschäftigen, wie Ablaufplaner, Bussysteme, Abhängigkeiten von Prozessen, etc.

 

 

In den Arbeiten welche die Antworzeitanalyse und das Echtzeitkalkül miteinander vergleichen, werden die Vergleiche immer empirisch durchgeführt. Das heißt es wird mindestens ein System beispielhaft herangezogen, beide Verfahren werden auf dieses System angewendet um schlussendlich die Ergebnisse der Verfahren miteinander zu vergleichen. Stattdessen sollen die Verfahren auf mathematischer theoretischer Ebene miteinander verglichen werden. Durch den mathematischen Vergleich wird ein besseres Verständnis über den Zusammenhang beider Verfahren erwartet. Des Weiteren können dadurch gegenbenfalls Methoden, Algorithm, etc. von einem Verfahren in das andere Verfahren übertragen werden.

Offene studentische Arbeiten

Masterarbeit

In this master thesis, in close cooperation with Continental, the possibilities of modelling embedded systems computing infrastructure in ChronSim are being analyzed. ChronSim from Inchron is an event-based simulator to reproduce the timing behavior of real-time systems.
A common problem based on the complexity of today´s embedded systems computing infrastructure is that schedulability is often hard to determine. Thus, complex models are needed to cover all modern aspects like multi-core systems, shared resources and hardware acceleration units. So far, most of the modelling and simulation at Continental regarding this topic is done with Continental proprietary tools. Moving these models to ChronSim will hopefully increase the possibilities of Optimization, the identification of bottlenecks and the worst-case behaviour. At the start, the
current models have to be reviewed and analyzed. Afterwards, a well-structured approach has to be evolved to obtain an extendable and easily maintainable conversion.

Anforderungen

For this thesis, a brief knowledge of real-time theory, computing architectures and embedded system
design are necessary. Basic knowledge of Python and C/C++ is helpful.

Ansprechpartner: Marco Philippi

Bachelorarbeit / Projektarbeit

In einer Motorsteuerung gibt es Aufgaben (Tasks) dessen Aufrufhäufigkeit, Berechnungsdauer und Zeitfristen von der Motordrehzahl abhängt. Diese Tasks und damit die Motorsteuerung als ganzes stellt deswegen eine große Herausforderung bezüglich seiner Echtzeitanalyse dar. Im Institut für Eingebettete System wurden mehrere Echtzeitanalysen [Feld et al.] für solche ratenabhängigen Tasks entwickelt.

Um die verschiedenen Analysen zu vergleichen soll daher in einer Bachelorarbeit ein Fallbeispiel (case-study) konstruiert werden, welches möglichst realistisch eine Motorsteuerung darstellt. Dabei müssen lediglich die für eine Echtzeitanalyse notwendige (also das Zeitverhalten beschreibende) Parameter generiert werden.

Der Umfang der Arbeit kann auf eine Projektarbeit angepasst werden.

Ansprechpartner: Prof. Frank Slomka

Masterarbeit

Um ein System analytisch auf seine Echtzeitfähigkeit zu untersuchen werden im wesentlichen drei Parameter benötigt: die Berechnungsdauern (Worst Case Execution Times), die Perioden und die Fristen der einzelnen Tasks. Bei einigen Systemen können diese Parameter dynamisch durch äußere Einflüsse variieren. Dieses Verhalten tritt insbesondere bei Motorsteuergeräten auf, bei denen die Drehzahl die genannten Parameter beeinflusst. Zusätzlich zu der Abhängigkeit von einer Drehzahl, gibt es weitere Beziehungen zwischen den Tasks, die vorgeben, dass die jeweiligen Ereignisse nur in einem minimalen Abstand zueinander auftreten können.

Der Real-Time Calculus ist ein mathematisch fundiertes Modell zur Analyse und Synthese verteilter Echtzeitsysteme. Bei diesem Modell des Task-Graphen wird durch Ankunftskurven die Anregung des Systems beschrieben. Jede Task modifiziert diese und es verbleibt die ausgehende Ereignisdichte und die verbleibende Rechenzeitkapazität.

Im Rahmen der Masterarbeit soll eine Analyse entwickelt und implementiert werden, welche sowohl die Abhängigkeiten zur Drehzahl als auch die Abhängigkeiten zwischen den Tasks berücksichtigt. Diese Analyse soll auf den Real-Time Calculus aufbauen, so dass verteilte Systeme analysiert werden können.

Ansprechpartner: Prof. Frank Slomka

Masterarbeit

Um ein System analytisch auf seine Echtzeitfähigkeit zu untersuchen werden im wesentlichen drei Parameter benötigt: die Berechnungsdauern (Worst Case Execution Times), die Perioden und die Fristen der einzelnen Tasks. Bei einigen Systemen können diese Parameter dynamisch durch äußere Einflüsse variieren. Dieses Verhalten tritt insbesondere bei Motorsteuergeräten auf, bei denen die Drehzahl die genannten Parameter beeinflusst. Im Institut wurde bereits eine Analyse für solche raten-abhängigen Tasks verwendet. Dabei wird allerdings von einem identischen Wert für die Beschleunigung und dem Abbremsen ausgegangen.

Ziel dieser Arbeit ist es, vorhandene Analysen so zu erweitern, dass unterschiedliche Werte für Beschleunigung und Bremsen angenommen werden können.

Ansprechpartner: Prof. Frank Slomka

Masterarbeit

Um ein System analytisch auf seine Echtzeitfähigkeit zu untersuchen werden im wesentlichen drei Parameter benötigt: die Berechnungsdauern (Worst Case Execution Times), die Perioden und die Fristen der einzelnen Tasks. Bei einigen Systemen können diese Parameter dynamisch durch äußere Einflüsse variieren. Dieses Verhalten tritt insbesondere bei Motorsteuergeräten auf, bei denen die Drehzahl die genannten Parameter beeinflusst.  [Pollex et al]

Der Real-Time-Calculus ist ein mathematisch fundiertes Modell zur Analyse und Synthese verteilter Echtzeitsysteme. Bei diesem Modell des Task-Graphen wird durch Ankunftskurven die Anregung des Systems beschrieben. Jede Task modifiziert diese und es verbleibt die ausgehende Ereignisdichte und die verbleibende Rechenzeitkapazität.

Im Institut für Eingebettete Systeme/Echtzeitsysteme wurden bereits aufbauend auf dem Real-Time Calculus Analysen für variable Parameter entwickelt. Bei diesen Analysen wird allerdings bei jeder Tasks von der minimalen Frist ausgegangen was die Analyse pessimistischer macht.

Ziel dieser Masterarbeit ist der Entwurf und die Implementierung einer neuen (oder die Erweiterung einer vorhandenen) Analyse für verteilte Systeme, welche variable Fristen berücksichtigt und die Genauigkeit verbessert.

Ansprechpartner: Prof. Frank Slomka

Masterarbeit

Um ein System analytisch auf seine Echtzeitfähigkeit zu untersuchen werden im wesentlichen drei Parameter benötigt: die Berechnungsdauern (Worst Case Execution Times), die Perioden und die Fristen der einzelnen Tasks. Bei Motorsteuergeräten variieren diese Parameter dynamisch in Abhängigkeit der Motordrehzahl.

Chronsim ist ein Simulationstool mit dem man das Zeitverhalten eines eingebetteten Systems simulieren kann. Im rahmen einer Masterarbeit soll ein Motorsteuergerät mit ChronSim simuliert werden. Dabei sollen die Auswirkungen der variierenden Parameter in Abhängigkeit der Motordrehzahl untersucht werden.

Ansprechpartner: Prof. Frank Slomka

In der Abschlussarbeit soll ein Paket für Mathematica implementiert werden. Das Packet soll dem Nutzer die Möglichkeit geben eine Echtzeitanalyse auf symbolischer Ebene durchführen zu können.

Ansprechpartner: Prof. Frank Slomka

Masterarbeit

Um bei eingebetteten Echtzeitsystemen Energie zu sparen, probiert man unter anderem, die Prozessorleistung herabzusetzen. Damit das System noch funktioniert, müssen bestimmte Anforderungen weiterhin gültig sein. Bei Echtzeitsystemen handelt es sich hierbei in erster Linie um die fristgerechte Abarbeitung von Teilaufgaben. Für einen ideellen Prozessor bestimmte Ausführungszeiten werden mit vorgegebenen Zeitschranken verglichen und damit die Echtzeitfähigkeit des Geräts geprüft. Eine Methodik, diesen Test möglichst schnell durchzuführen und Garantien abgeben zu können, sind Ereignisströme. Aus ihnen generiert man eine Rechenzeitanforderungsfunktion, um die benötigte Rechenzeit nach oben abzuschätzen und diese mit der tatsächlich verfügbaren zu vergleichen. Aufgabe dieser Arbeit ist es, in diesen Vergleich eine Optimierung einzubauen, die die einzelnen Ausführungszeiten maximiert und die Fristen optimiert. Aufgrund der Struktur dieses Problems eignet sich hierfür eine lineare Optimierung. Sicher ist dies nicht der erste Ansatz, dieses Problem anzugehen und so ist es Teil der Aufgabenstellung, bekannte Arbeiten zu studieren und die eigene Optimierung mit den Ergebnissen der bekannten Arbeiten zu vergleichen.

Ansprechpartner: Prof. Frank Slomka

Masterarbeit

 

Am Institut wurde eine neue Methode zur Analyse von Echtzeitsystemen entwickelt. Das neue Verfahren erlaubt eine elegantere Modellierung dieser Systeme. Die Analyse wurde prototypisch mit einem Computeralgebra-System (CAS) implementiert. In dieser Masterarbeit soll untersucht werden wie die Implementierung bezüglich der Rechenzeit effizienter gestaltet werden kann. Dazu sollen Parallelisierungen des CAS und bereits vorhandene Compiler genutzt werden. Ggf. ist zu untersuchen ob auch auf GPUs gerechnet werden kann. Zusätzlich kann das neue Verfahren in MATLAB implementiert werden. Die unterschiedlichen Umsetzungen sind dann bezüglich ihres Laufzeitverhaltens zu vergleichen.

Ansprechpartnern: Marco Philippi