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

Echtzeitanalyse für eine Motorsteuerung

Masterarbeit/Bachelorarbeit/Projektarbeit

Mit der Antwortzeitanalyse können Mono-Prozessor-Systeme, die mit festen Prioritäten gesteuert sind auf ihre Echtzeitfähigkeit überprüft werden. Dabei wird für jede Task eine maximale Antwortzeit berechnet: die Zeit die eine Task vom Zeitpunkt ihrer Anregung bis zum Vorliegen des Ergebnisses maximal benötigt. Die jeweiligen Antwortzeiten der Tasks werden anschließend mit den zugehörigen Fristen verglichen, um das System auf seine Echtzeitfähigkeit zu überprüfen.

Bei der klassischen Antwortzeitanalyse wird davon ausgegangen, dass die Ereignisse aller Tasks gleichzeitig auftreten können. Es gibt aber durch die Anwendung vorhandene Beziehungen zwischen Tasks, die vorgeben, dass die jeweiligen Ereignisse nur in einem minimalen Abstand zueinander auftreten können.

Bei Motorsteuergeräten sind diese Beziehungen sehr exakt vorgegeben. Hier werden bei einigen Tasks die Ereignisse nicht durch feste Perioden, sondern durch bestimmte Winkel-Positionen angeregt (sogenannte ratenabhängige Tasks).

In einer vorangegangenen Arbeit wurde bereits eine Analyse entwickelt, welche solche Beziehungen berücksichtigt [Feld, Slomka]. Diese Analyse ist allerdings nur für Tasksets konzipiert, welche ausschließlich aus ratenabhängigen Tasks besteht. Ziel dieser Masterarbeit ist es diese Analyse zu erweitern, so dass gemischte Tasksets (aus ratenabhängigen und periodischen Tasks) analysiert werden können.

Das Thema kann im Umfang an eine Master-, Bachelor- oder 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

Bachelorarbeit

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

Echtzeitanalyse für verteilte Systeme mit variablen Taskausführungszeiten (ausgehende Ereignisdichte)

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 für Eingebettete Systeme/Echtzeitsysteme wurden bereits Analysen entwickelt, welche diese Problematik berücksichtigen [Pollex et al]. Diese sind allerdings für Mono-Prozessor-Systeme konzipiert.

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. Es soll aufbauend auf dem Real-Time Calculus eine Analyse für verteilte Systeme erforscht werden, welche variable Parameter berücksichtigt.

Ziel dieser Masterarbeit ist ein Teil-Ziel hieraus: der Entwurf und die Implementierung für die Bestimmung der ausgehenden Ereignisdichte.

Ansprechpartner: Timo Feld

Echtzeitanalyse für verteilte Systeme mit variablen Taskausführungszeiten (verbleibende Rechenzeitkapazität)

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 für Eingebettete Systeme/Echtzeitsysteme wurden bereits Analysen entwickelt, welche diese Problematik berücksichtigten [Pollex et al]. Diese sind allerdings für Mono-Prozessor-Systeme konzipiert.

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. Es soll aufbauend auf dem Real-Time Calculus eine Analyse für verteilte Systeme erforscht werden, welche variable Parameter berücksichtigt.

Ziel dieser Masterarbeit ist ein Teil-Ziel hieraus: der Entwurf und die Implementierung für die Bestimmung der verbleibenden Rechenzeitkapazität.

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:

Projektspezifische Publikationen


4.
pdf
Feld, Timo; Slomka, Frank
Sufficient Response Time Analysis considering Dependencies between Rate-Dependent Tasks
Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE)
März 2015
3.
default
Davis, Rob; Feld, Timo; Pollex, Victor; Slomka, Frank
Schedulability Tests for Tasks with Variable Rate-Dependent Behaviour under Fixed Priority Scheduling
20th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS),
April 2014
2.
default
Pollex, Victor; Feld, Timo; Slomka, Frank; Margull, Ulrich; Mader, Ralph; Wirrer, Gerhard
Sufficient real-time analysis for an engine control unit
Proceedings of the 21st International conference on Real-Time Networks and Systems (RTNS),
Oktober 2013
1.
pdf
Pollex, Victor; Feld, Timo; Slomka, Frank; Margull, Ulrich; Mader, Ralph; Wirrer, Gerhard
Sufficient Real-Time Analysis for an Engine Control Unit with Constant Angular Velocities
Proceedings of the Design Automation and Test Conference in Europe (DATE)
März 2013
Export als: BibTeX, XML