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

Fallbeispiel Motorsteuerung

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: Timo Feld

Ereignisabhängigkeiten in verteilten Systemen

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: Timo Feld

Echtzeitanalyse für ratenabhängige Tasks

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: Timo Feld

Echtzeitanalyse verteilter Systeme mit Berücksichtigung variabler Fristen

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: Timo Feld

Simulation eines Motorsteuergerätes mit ChronSim

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: Timo Feld

Implementierung und Vergleich einer Bibliothek zur min-plus und max-plus Algebra

Das Echtzeitkalkül ist ein Verfahren zur Echtzeitanalyse, welches maßgeblich Faltungs- und Entfaltungsoperationen in der min-plus und max-plus Algebra verwendet. Eine Implementation hierzu ist die RTC Toolbox. Es ist eine Bibliothek zu implementieren welche die RTC Toolbox ersetzen kann gemäß den Vorgaben aus der Veröffentlichung "An Algorithmic Toolbox for Network Calculus" von Anne Bouillard und Éric Thierry. Des Weiteren sollen die beiden Bibliotheken miteinander verglichen werden. Ansprechpartner: Victor Pollex

Mathematischer Vergleich von Methoden der Antwortzeitanalyse und dem Echtzeitkalkül

Für die Echtzeitanalyse eines Systems existieren mehrere Methoden. Darunter befinden sich die Antwortzeitanalyse und das Echtzeitkalkül. Die Arbeiten in der Literatur zu diesen Analysemethoden befassen sich meist mit nur einer dieser Methoden. In den Arbeiten die sich mit beiden Methoden gemeinsam befassen werden diese meist empirisch miteinander verglichen. Daher sollen diese Methoden theoretisch / mathematisch verglichen werden. Die Abschlussarbeit beschränkt sich auf einzelne Aspekte dieser Methoden. Ansprechpartner: Victor Pollex

Implementierung eines Echtzeitanalysepakets für Mathematica

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: Victor Pollex, Frank Slomka

Optimierung der Ausführungszeiten von eingebetteten Echtzeitsystemen mit Ereignisströmen

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:

Untersuchung des Laufzeitverhaltens effizienter Echtzeitanalysen mit Mathematik-Systemen

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: Mohammadreza Sadeghi, Marco Philippi