Echtzeitsysteme - Exam

Aufgabe 1)

Echtzeitbetriebssysteme (RTOS) sind so konzipiert, dass sie zeitlich deterministisches Verhalten für Echtzeitanwendungen garantieren. Sie verwalten mehrere Tasks, ordnen diesen Prioritäten zu und nutzen verschiedene Scheduling-Algorithmen (z.B. Rate-Monotonic (RM) und Earliest Deadline First (EDF)), um sicherzustellen, dass Aufgaben rechtzeitig ausgeführt werden. Eine wesentliche Anforderung ist der effiziente Umgang mit Hardware-Interrupts, um die Latenz zu minimieren, und die Gewährleistung von Determinismus für zeitkritische Anwendungen.

a)

1. Aufgabenpriorisierung und Scheduling-Algorithmen: Erläutere die Grundprinzipien von RM und EDF Scheduling-Algorithmen. Gib an, wie jeder dieser Algorithmen arbeitet und unter welchen Bedingungen jeder optimal ist. Berechne für ein gegebenes Beispiel mit drei Tasks (T1 = {C1 = 1, T1 = 4}, T2 = {C2 = 2, T2 = 10}, T3 = {C3 = 1, T3 = 7}), ob RM und EDF Scheduler diese Tasks erfolgreich planen können und begründe Deine Antwort.

Lösung:

1. Aufgabenpriorisierung und Scheduling-Algorithmen:

• Rate-Monotonic (RM) Scheduling:RM-Scheduling ist ein fester Prioritätenscheduling-Algorithmus. Bei RM wird jeder Aufgabe (Task) eine Priorität zugewiesen, die umgekehrt proportional zu ihrer Periode (T) ist. Das bedeutet, dass Aufgaben mit kürzeren Perioden höhere Prioritäten haben. Dieser Algorithmus ist besonders nützlich für periodische Aufgaben mit festen, vorhersehbaren Anforderungen.Wenn die Perioden der Aufgaben kleiner sind, hat ihre Exekution höhere Priorität. Dies basiert auf der Annahme, dass kürzere Perioden auch kürzere Deadlines bedeuten.
• Earliest Deadline First (EDF) Scheduling:EDF-Scheduling verwendet einen dynamischen Prioritätenscheduling-Algorithmus. Hierbei wird die Priorität jeder Aufgabe basierend auf ihrer Deadline berechnet. Die Aufgabe mit der frühesten Deadline (also der kürzesten verbleibenden Zeit bis zum Abschluss) erhält die höchste Priorität und wird zuerst eingeplant. EDF passt sich ständig an, je nachdem, wie sich die Deadlines der Aufgaben näher kommen.Somit können auch unregelmäßige oder selten in Intervallen auftretende Aufgaben effizient behandelt werden.

Optimalitätsbedingungen:

• Rate-Monotonic: RM-Scheduling ist optimal für Aufgaben mit festen Perioden, solange die Gesamtauslastung des Systems unter der theoretischen Grenze von ca. 69,3% bleibt. Das bedeutet, dass RM garantiert, dass keine Deadline verpasst wird, wenn die Auslastung niedriger ist.
• Earliest Deadline First: EDF-Scheduling ist optimal, solange die Gesamtauslastung des Systems 100% nicht überschreitet. Da EDF dynamisch anpassbar ist, kann es eine vollständige Systemauslastung verwalten, sofern diese Grenze nicht überschritten wird.

Beispielberechnung:

• Gegebene Tasks: T1 = {C1 = 1, T1 = 4} T2 = {C2 = 2, T2 = 10} T3 = {C3 = 1, T3 = 7}
• Berechnung der Systemauslastung: Die Systemauslastung U wird wie folgt berechnet:

  U = \frac{C1}{T1} + \frac{C2}{T2} + \frac{C3}{T3} = \frac{1}{4} + \frac{2}{10} + \frac{1}{7} = 0,25 + 0,2 + 0,142857 = 0,592857

  Dies ergibt eine Gesamtauslastung von ca. 59,3%.
• Rate-Monotonic Scheduling (RM): Die berechnete Gesamtauslastung von 59,3% liegt unter der RM-Grenze von 69,3%. Daher kann RM diese Aufgaben erfolgreich planen.
• Earliest Deadline First Scheduling (EDF): Da die berechnete Gesamtauslastung von 59,3% auch unter der 100% Grenze von EDF liegt, kann EDF diese Aufgaben ebenfalls erfolgreich planen.

Zusammenfassung: Sowohl RM- als auch EDF-Algorithmus können die gegebenen Aufgaben mit den genannten Auslastungen erfolgreich planen, da die berechnete Systemauslastung von 59,3% innerhalb der jeweiligen Grenzwerte liegt.

b)

2. Interrupt-Handling: Beschreibe, wie ein RTOS mit Hardware-Interrupts umgeht. Diskutiere die Bedeutung der Latenz bei der Verarbeitung von Interrupts und wie diese minimiert werden kann. Zeichne ein Sequenzdiagramm, das den Ablauf eines Interrupt-Handling-Prozesses in einem RTOS zeigt.

Lösung:

2. Interrupt-Handling:

• Umgang mit Hardware-Interrupts in einem RTOS:Ein Echtzeitbetriebssystem (RTOS) muss schnell und effizient auf Hardware-Interrupts reagieren, um zeitkritische Aufgaben zu gewährleisten. Der Prozess des Interrupt-Handlings umfasst typischerweise die folgenden Schritte:
  • Erfassen des Interrupts: Sobald ein Hardware-Interrupt auftritt, wird dies von der entsprechenden Interrupt-Controller-Hardware erkannt und ein Signal an die CPU gesendet.
  • Interrupt-Service-Routine (ISR): Der Prozessor wechselt von der laufenden Task zur entsprechenden Interrupt-Service-Routine, um den Interrupt zu bearbeiten. Diese Routine ist oft so kurz und schnell wie möglich, um die Systemlatenz zu minimieren.
  • Speichern des Kontexts: Der aktuelle Zustand der unterbrochenen Task (Register, Programmzähler, usw.) wird gespeichert, damit diese nach Abschluss der ISR fortgesetzt werden kann.
  • Bearbeitung des Interrupts: Die ISR führt alle notwendigen Arbeiten aus, die durch den Interrupt erforderlich sind (z.B. Daten von einem Gerät lesen, einen Puffer aktualisieren).
  • Wiederherstellung des Kontexts: Nachdem die ISR ihre Aufgabe erledigt hat, wird der vorherige Kontext wiederhergestellt, und die ursprüngliche Task wird fortgesetzt.
  • Scheduler-Aufruf: Falls erforderlich, kann nach Abschluss der ISR der Scheduler aufgerufen werden, um sicherzustellen, dass die höchste Prioritätsaufgabe ausgeführt wird.

Bedeutung der Latenz bei der Verarbeitung von Interrupts:Die Latenz ist entscheidend in einem RTOS, da sie die Zeit beschreibt, die verstreicht, bevor ein Interrupt verarbeitet wird. Niedrige Latenzzeiten sind besonders wichtig für zeitkritische Anwendungen, da Verzögerungen zu Fehlern oder Leistungsbeeinträchtigungen führen können.Minimierung der Latenz:

• Optimierung der ISR: Die Interrupt-Service-Routine sollte so kurz und effizient wie möglich sein, um die Unterbrechungen im System zu minimieren.
• Prioritätensystem: Hohe Prioritäten für wichtige ISRs und entsprechende Scheduling-Algorithmen sicherstellen, dass zeitkritische Interrupts schnell verarbeitet werden.
• Hardware-Unterstützung: Verwendung eines fortschrittlichen Interrupt-Controllers, der die Prioritäten der Interrupts effizient verwaltet.
• Reduzierung nicht notwendiger Interrupts: Sicherstellen, dass nur wirklich notwendige Interrupts aktiviert sind und überflüssige Interrupts vermieden werden.

Sequenzdiagramm:Das folgende Sequenzdiagramm illustriert den Ablauf eines Interrupt-Handling-Prozesses in einem RTOS.

c)

3. Determinismus und geringe Latenz: Was bedeutet Determinismus in einem Echtzeitsystem und warum ist er entscheidend für die meisten Echtzeitanwendungen? Berechne die maximale Antwortzeit (Worst Case Response Time, WCRT) für die Tasks im obigen Beispiel (T1, T2, T3) unter der Annahme, dass kein Preemption Overhead und keine Interrupts auftreten. Zeige alle Deine Berechnungen im Detail.

Lösung:

3. Determinismus und geringe Latenz:

• Determinismus in einem Echtzeitsystem:Determinismus bedeutet in einem Echtzeitsystem, dass das Systemverhalten in Bezug auf die Ausführung von Aufgaben (Tasks) vorhersehbar und wiederholbar ist. Das bedeutet, dass jede Aufgabe innerhalb festgelegter Zeitgrenzen abgeschlossen wird. Dies ist entscheidend, da viele Anwendungen, wie z. B. industrielle Steuerungen, medizinische Geräte und Flugzeugsteuerungen, auf die zeitgerechte Ausführung von Aufgaben angewiesen sind. Ein Versagen bei der rechtzeitigen Ausführung kann zu Fehlern oder Sicherheitsrisiken führen.
• Geringe Latenz:Latenz ist die Verzögerung zwischen dem Auftreten eines Ereignisses und dem Beginn der Verarbeitung dieses Ereignisses. In Echtzeitsystemen ist es entscheidend, diese Latenz so gering wie möglich zu halten, um sicherzustellen, dass zeitkritische Aufgaben sofort bearbeitet werden.

• Berechnung der maximalen Antwortzeit (Worst Case Response Time, WCRT): Unter der Annahme, dass kein Preemption Overhead und keine Interrupts auftreten, können wir die WCRT für die drei Tasks (T1, T2, T3) berechnen. Die WCRT bestimmt die Zeitspanne, die jede Aufgabe benötigt, um abgeschlossen zu werden, einschließlich der Verzögerung durch andere Aufgaben mit höherer Priorität.
• Gegebene Tasks:T1 = {C1 = 1, T1 = 4} T2 = {C2 = 2, T2 = 10} T3 = {C3 = 1, T3 = 7}
• Berechnung der WCRT: Für jede Aufgabe berechnen wir die Antwortzeit unter Berücksichtigung aller höheren Prioritätsaufgaben.
• WCRT Berechnung für T1: Da T1 die höchste Priorität hat, wird sie nicht durch andere Tasks verzögert. Daher ist die Antwortzeit von T1 gleich der Ausführungszeit. WCRT(T1) = C1 = 1
• WCRT Berechnung für T2: T2 kann während ihrer Ausführungszeit von T1 verzögert werden. Die Antwortzeit von T2 ergibt sich aus der eigenen Ausführungszeit plus der maximalen Verzögerung durch T1. R2 = C2 + WCRT(T1) = 2 + 1 = 3 WCRT(T2) = 3
• WCRT Berechnung für T3: T3 kann während ihrer Ausführungszeit sowohl von T1 als auch von T2 verzögert werden. R3 = C3 + WCRT(T1) + WCRT(T2) = 1 + 1 + 2 = 4 WCRT(T3) = 4

Zusammenfassung:Die maximalen Antwortzeiten (WCRT) für die Aufgaben lauten:

• WCRT(T1) = 1
• WCRT(T2) = 3
• WCRT(T3) = 4

Zusammenfassend ist der Determinismus in Echtzeitsystemen wichtig, um sicherzustellen, dass Aufgaben innerhalb vorhersehbarer und fester Zeitrahmen erfüllt werden. Die Berechnung der maximalen Antwortzeit (WCRT) für die Tasks zeigt, wie wichtig es ist, zeitkritische Anforderungen zu erfüllen, um die Funktionalität und Sicherheit von Echtzeitanwendungen zu gewährleisten.

d)

4. Speicherverwaltung: Erkläre, wie ein RTOS Speicherressourcen managed und warum Speicherisolation wichtig ist. Diskutiere mindestens zwei verschiedene Speicherverwaltungsstrategien, die in RTOS verwendet werden, und gib Beispiele für mögliche Problemfelder bei jeder dieser Strategien. Nutze Diagramme, um die Funktionsweise der Speicherverwaltung zu verdeutlichen.

Lösung:

4. Speicherverwaltung:

• Speicherressourcenmanagement in einem RTOS: Ein Echtzeitbetriebssystem (RTOS) muss den verfügbaren Speicher effizient verwalten, um sicherzustellen, dass jede Aufgabe (Task) ausreichend Speicherressourcen erhält, während Speicherlecks und Fragmentierung minimiert werden. Zu den Hauptanforderungen gehören die Zuweisung von Speicher an verschiedene Tasks, die Freigabe von Speicher nach der Nutzung und die Sicherstellung, dass keine unerlaubten Zugriffe auf den Speicherbereich anderer Tasks erfolgen.
• Bedeutung der Speicherisolation: Speicherisolation ist wichtig, um sicherzustellen, dass Tasks nicht auf den Speicher anderer Tasks zugreifen können, wodurch Datenintegrität und Systemsicherheit gewährleistet werden. Speicherisolation verhindert, dass Fehler oder böswillige Tasks den Speicher anderer Tasks beschädigen oder kompromittieren. Dies ist besonders wichtig für sicherheitskritische Anwendungen, bei denen Datenintegrität und systemweite Stabilität oberste Priorität haben.

Speicherverwaltungsstrategien:

• 1. Statische Speicherzuweisung:Bei der statischen Speicherzuweisung wird der Speicher für jede Aufgabe bei Systemstart fest zugewiesen. Diese Methode ist vorhersehbar und eliminiert die Notwendigkeit zur Laufzeit Speicher zu verwalten.
  • Vorteile:- Vorhersehbarkeit: Der Speicherbedarf jeder Aufgabe ist im Voraus bekannt.- Kein Laufzeit-Overhead: Da alle Zuordnungen beim Systemstart vorgenommen werden, gibt es keinen Overhead zur Laufzeit.
  • Nachteile:- Ineffizienz: Möglicherweise wird mehr Speicher zugewiesen, als tatsächlich benötigt wird, was zu einer ineffizienten Speicher-Nutzung führt.- Fehlende Flexibilität: Der Speicherbedarf kann nach Systemstart nicht mehr angepasst werden.
• 2. Dynamische Speicherzuweisung:Bei der dynamischen Speicherzuweisung wird der Speicher zur Laufzeit angefordert und freigegeben. Diese Methode erlaubt eine flexible Nutzung des Speichers basierend auf aktuellen Bedarfen.
  • Vorteile:- Flexibilität: Speicherzuweisungen können dynamisch basierend auf den aktuellen Anforderungen vorgenommen werden.- Effizienz: Der Speicher wird nur bei Bedarf zugewiesen und freigegeben, wodurch eine effizientere Nutzung möglich ist.
  • Nachteile:- Fragmentierung: Der verfügbare Speicher kann fragmentiert werden, was zu Ineffizienz und einer erhöhten Wahrscheinlichkeit führt, dass Speicheranforderungen fehlschlagen.- Laufzeit-Overhead: Die Verwaltung von Speicherzuweisungen und -freigaben erzeugt zusätzlichen Overhead zur Laufzeit.

Diagramme zur Veranschaulichung:

• Statische Speicherzuweisung:>
  • Dieses Diagramm zeigt, wie Tasks zur Laufzeit Speicher anfordern und freigeben, mit unterschiedlichen Speicheranforderungen und variablen Zuweisungen, einschließlich Event-Markierungen und Pufferung.

Aufgabe 2)

Einleitung: In einem autonomen Fahrzeugsystem müssen verschiedene Echtzeitanforderungen erfüllt werden, um die Sicherheit und Effizienz des Fahrzeugs zu gewährleisten. Diese Anforderungen können in zwei Kategorien eingeteilt werden - Hard-Realzeit und Soft-Realzeit. Das autonome System beinhaltet Sensoren zur Erfassung der Fahrzeugumgebung, Algorithmen zur Entscheidungsfindung und Aktuatoren zur Steuerung des Fahrzeugs.Szenario: Stellen wir uns vor, dass in Deinem autonomen Fahrzeug folgende Ereignisse stattfinden:

• Ein Kollisionsvermeidungssystem (Hard-Realzeit) muss Hindernisse innerhalb von 50 ms erkennen und ausweichen.
• Der Entertainment-Controller (Soft-Realzeit) aktualisiert die Liste der verfügbaren Lieder, dies muss innerhalb von 2 Sekunden geschehen.
• Ein System zur Warnung vor potenziellen Gefahren (Soft-Realzeit) meldet je nach Bedrohungsniveau in Echtzeit, Verzögerungen bis zu 200 ms sind akzeptabel.

a)

Analysiere das Kollisionsvermeidungssystem unter den gegebenen Hard-Realzeit-Anforderungen. Welche Konsequenzen könnte es haben, wenn das System die 50 ms Zeitvorgabe nicht einhält?

Lösung:

Analyse des Kollisionsvermeidungssystems:

• Hard-Realzeit-Anforderungen: Das Kollisionsvermeidungssystem in Deinem autonomen Fahrzeug muss Hindernisse innerhalb von 50 ms erkennen und entsprechende Ausweichmanöver einleiten.

Konsequenzen bei Nichteinhaltung der 50 ms Zeitvorgabe:

• Erhöhtes Unfallrisiko: Wenn das System die 50 ms Zeitvorgabe nicht einhält, kann es zu Verzögerungen bei der Hinderniserkennung und den Ausweichmanövern kommen. Dies kann direkt zu einer Kollision führen, da das Fahrzeug nicht rechtzeitig reagiert.
• Schäden an Fahrzeugen und Infrastruktur: Eine Kollision kann zu erheblichen Schäden am Fahrzeug und auch an der umliegenden Infrastruktur führen. Dies bedeutet hohe Kosten für Reparaturen und mögliche rechtliche Konsequenzen.
• Verletzungen oder Todesfälle: Die größte Gefahr besteht in der Möglichkeit von Verletzungen oder gar Todesfällen der Insassen des Fahrzeugs und anderer Verkehrsteilnehmer, wenn das Kollisionsvermeidungssystem nicht schnell genug reagiert.
• Verlust des Vertrauens: Eine mangelnde Zuverlässigkeit des Kollisionsvermeidungssystems kann zu einem Vertrauensverlust in autonome Fahrzeugsysteme führen. Dies könnte die Akzeptanz solcher Technologien in der Gesellschaft erheblich beeinträchtigen.
• Rechtliche und regulatorische Konsequenzen: Ein Versagen des Hard-Realzeit-Systems könnte rechtliche Folgen für den Hersteller des Fahrzeugs und den Betreiber nach sich ziehen. Dies könnte zu Strafen, Schadensersatzforderungen und verschärften Regulierungen führen.

b)

Berechne die Wahrscheinlichkeit des Versagens des Unterhaltungssystems, wenn die Aktualisierung der Liederliste durchschnittlich 1,8 Sekunden dauert und die Verteilung der Verzögerung normal ist mit einer Standardabweichung von 0,1 Sekunden.

Lösung:

Berechnung der Wahrscheinlichkeit des Versagens des Unterhaltungssystems:

• Die Aktualisierung der Liederliste dauert durchschnittlich 1,8 Sekunden.
• Die Verzögerung der Aktualisierung ist normal verteilt mit einer Standardabweichung von 0,1 Sekunden.
• Die maximale akzeptable Zeit für die Aktualisierung beträgt 2 Sekunden.

Um die Wahrscheinlichkeit des Versagens des Unterhaltungssystems zu berechnen, wenn die Aktualisierung länger als 2 Sekunden dauert, nutzen wir die Eigenschaften der Normalverteilung.

Gegeben:

• Mittelwert (\textmu) = 1,8 Sekunden
• Standardabweichung (\textsigma) = 0,1 Sekunden
• Grenzwert (x) = 2 Sekunden

Wir berechnen den z-Wert, der angibt, wie viele Standardabweichungen ein Wert vom Mittelwert entfernt ist. Der z-Wert wird wie folgt berechnet:

\[\text{z} = \frac{x - \textmu}{\textsigma} = \frac{2 - 1,8}{0,1} = 2\]

Nun nutzen wir die Standardnormalverteilungstabelle oder ein entsprechendes Tool, um die Wahrscheinlichkeit zu finden, dass der z-Wert größer als 2 ist.

Für z = 2 beträgt die Wahrscheinlichkeit, dass ein Wert darunter liegt, etwa 0,9772. Daher ist die Wahrscheinlichkeit, dass ein Wert darüber liegt (das heißt, dass die Aktualisierungszeit länger als 2 Sekunden dauert), 1 - 0,9772 = 0,0228.

Die Wahrscheinlichkeit des Versagens (d.h., dass die Aktualisierung der Liederliste länger als 2 Sekunden dauert) beträgt also:

2,28%.

c)

Erkläre, wie das Gefahrenerkennungssystem unter den Soft-Realzeit-Anforderungen arbeiten würde, wenn unterschiedliche Bedrohungsniveaus variable Zeitgrenzen zwischen 100 ms und 200 ms haben. Wie würde das System mit diesen Anforderungen umgehen und wie würde die Leistungskriterien evaluiert?

Lösung:

Erklärung des Gefahrenerkennungssystems unter Soft-Realzeit-Anforderungen:

Das Gefahrenerkennungssystem in Deinem autonomen Fahrzeug soll Bedrohungen in Echtzeit melden, wobei die akzeptablen Verzögerungen je nach Bedrohungsniveau zwischen 100 ms und 200 ms variieren. Hier ist, wie das System diese Anforderungen umsetzen und seine Leistung bewerten würde:

• Bedrohungsniveaus und ihre Zeitgrenzen:
  • Hohes Bedrohungsniveau: Meldungen müssen innerhalb von 100 ms erfolgen.
  • Mittleres Bedrohungsniveau: Meldungen innerhalb von 150 ms sind akzeptabel.
  • Niedriges Bedrohungsniveau: Meldungen können bis zu 200 ms Verzögerung haben.
• Implementierung des Systems:
  • Priorisierung: Das System priorisiert die Verarbeitung von Bedrohungen basierend auf deren Niveau. Höhere Bedrohungsniveaus werden bevorzugt behandelt, um die strikteren Zeitgrenzen einzuhalten.
  • Optimierte Algorithmusauswahl: Für die schnellere Erkennung bei hohen Bedrohungen könnte das System auf optimierte Algorithmen zurückgreifen, die speziell für Geschwindigkeit bei geringfügig höherer Ressourcennutzung entwickelt wurden.
  • Adaptive Ressourcenverteilung: Das System kann dynamisch mehr Rechenleistung und Speicherkapazität auf Bedrohungserkennung umleiten, wenn ein hohes Bedrohungsniveau erkannt wird, um die strikteren Anforderungen zu erfüllen.
• Leistungskriterien und Evaluierung:
  • Messung der Erkennungszeit: Die Zeit von der Bedrohungserkennung bis zur Meldung wird kontinuierlich gemessen und aufgezeichnet.
  • Statistische Analyse: Die Erkennungszeiten werden statistisch analysiert, um sicherzustellen, dass die meisten Meldungen innerhalb der akzeptablen Zeitgrenzen liegen. Es könnten Kennzahlen wie Durchschnitt, Median und Prozentrang (z.B. 99. Perzentil) verwendet werden.
  • Fehlerquoten: Die Anzahl der Meldungen, die die akzeptablen Zeitgrenzen überschreiten, wird überwacht. Eine niedrige Fehlerquote (z.B. weniger als 1% der Meldungen) wäre ein Indikator für gute Systemleistung.
  • Stresstests: Unter verschiedenen simulierten Bedrohungsszenarien wird das System auf seine Belastbarkeit und Fähigkeit getestet, die Soft-Realzeit-Anforderungen konsistent zu erfüllen.
  • Feedback-Loop: Basierend auf den Evaluierungsergebnissen wird das System kontinuierlich angepasst und verbessert, um eventuelle Schwächen zu beheben und die Leistungsfähigkeit zu steigern.

Durch diese Ansätze würde das Gefahrenerkennungssystem in der Lage sein, die variablen Soft-Realzeit-Anforderungen effektiv zu erfüllen und seine Leistung kontinuierlich zu bewerten und zu optimieren.

Aufgabe 3)

Planung und Scheduling-AlgorithmenPlanung und Scheduling-Algorithmen in Echtzeitsystemen steuern die Ausführung von Aufgaben, um Fristen einzuhalten.

• Deterministische vs. nicht-deterministische Algorithmen
• Echtzeitbetriebssysteme verwenden harte und weiche Echtzeitscheduling-Strategien
• Häufige Algorithmen: RMS (Rate Monotonic Scheduling), EDF (Earliest Deadline First)
• Prioritätszuweisung und Kontextwechsel sind entscheidend
• Nutzung von Zeitdiagrammen zur Visualisierung

a)

Stelle die Hauptunterschiede zwischen deterministischen und nicht-deterministischen Scheduling-Algorithmen dar. Gehe insbesondere darauf ein, wie sich diese Unterschiede auf harte und weiche Echtzeitsysteme auswirken können.

Lösung:

Unterschiede zwischen deterministischen und nicht-deterministischen Scheduling-AlgorithmenDeterministische und nicht-deterministische Scheduling-Algorithmen haben unterschiedliche Eigenschaften und Auswirkungen auf Echtzeitsysteme, insbesondere auf harte und weiche Echtzeitsysteme.

• Deterministische Algorithmen

• Deterministische Algorithmen haben vorhersehbare und wiederholbare Verhaltensweisen. Das bedeutet, dass die Ausführungszeiten und -reihenfolgen der Aufgaben immer gleich sind.
• Diese Algorithmen sind besonders geeignet für harte Echtzeitsysteme, bei denen Zeitvorgaben strikt eingehalten werden müssen. Ein Beispiel ist das Rate Monotonic Scheduling (RMS).
• Bei harten Echtzeitsystemen sind die Konsequenzen für das Nichteinhalten von Fristen schwerwiegend, daher ist Vorhersehbarkeit ein Muss.

• Nicht-deterministische Algorithmen

• Nicht-deterministische Algorithmen können unterschiedliche Ausführungszeiten und -ergebnisse haben, da sie flexibel auf veränderte Bedingungen reagieren.
• Diese Algorithmen sind oft besser geeignet für weiche Echtzeitsysteme, bei denen gelegentliche Verzögerungen tolerierbar sind. Ein Beispiel ist das Earliest Deadline First (EDF).
• Weiche Echtzeitsysteme können mit den flexibleren und oftmals effizienteren Zuteilungen nicht-deterministischer Algorithmen besser umgehen, solange die durchschnittliche Leistung den Anforderungen entspricht.

Zusammenfassung

• Deterministische Algorithmen sind für harte Echtzeitsysteme essenziell, da sie garantieren, dass alle Fristen eingehalten werden.
• Nicht-deterministische Algorithmen sind flexibler und besser geeignet für weiche Echtzeitsysteme, in denen gelegentliche Verzögerungen akzeptabel sind.

c)

Erkläre den Unterschied zwischen Prioritätszuweisung und Kontextwechsel. Beschreibe ein Szenario, in dem ein häufiger Kontextwechsel auftreten könnte und warum dies die Systemleistung beeinträchtigen könnte.

Lösung:

Unterschied zwischen Prioritätszuweisung und KontextwechselUm die Konzepte der Prioritätszuweisung und des Kontextwechsels und deren Einfluss auf die Systemleistung besser zu verstehen, betrachten wir beide Begriffe im Detail:

• Prioritätszuweisung

Die Prioritätszuweisung ist der Prozess, bei dem jedem Prozess oder jeder Aufgabe im System eine bestimmte Priorität zugewiesen wird. Prioritäten können statisch (fixiert) oder dynamisch (je nach Systemzustand oder Aufgabe) vergeben werden. Höhere Prioritäten bedeuten, dass der Prozess oder die Aufgabe bevorzugt ausgeführt wird.Beispiele:

• Statische Prioritätensysteme, wie sie beim Rate Monotonic Scheduling (RMS) verwendet werden, basieren auf festen Prioritäten gemäß den Perioden der Aufgaben.
• Beim Earliest Deadline First (EDF) werden Prioritäten dynamisch basierend auf den Fristen der Aufgaben zugewiesen.

• Kontextwechsel

Ein Kontextwechsel ist der Vorgang, bei dem der Prozessor von der Ausführung einer Aufgabe oder eines Prozesses zur Ausführung einer anderen wechselt. Dies beinhaltet das Speichern des aktuellen Zustands der laufenden Aufgabe (Registrierinhalte, Prozessorzustand) und das Laden des Zustands der nächsten Aufgabe. Kontextwechsel treten auf, wenn:

• Ein höher priorisierter Prozess verfügbar wird.
• Ein laufender Prozess blockiert oder beendet wird.

Beispiele:

• Ein Echtzeitbetriebssystem kann einen Kontextwechsel durchführen, wenn eine Interrupt-Service-Routine (ISR) ausgeführt werden muss.
• Ein System, das Time-Slicing verwendet, um CPU-Zeit schematisch zwischen Aufgaben zu verteilen.

Szenario für häufige Kontextwechsel und AuswirkungenEin Szenario mit häufigen Kontextwechseln könnte ein System sein, das vielen hochfrequenten Interrupts ausgesetzt ist. Beispielsweise könnte ein Netzwerkserver stark ausgelastet sein und kontinuierlich Netzwerkpakete empfangen und verarbeiten müssen:

• Jeder Netzwerkinterrupt löst einen Kontextwechsel aus, um die eingehenden Pakete zu verarbeiten.
• Zwischen diesen Interrupts müssen reguläre Aufgaben des Servers ausgeführt werden, was ebenfalls Kontextwechsel erfordert.

Warum häufige Kontextwechsel die Systemleistung beeinträchtigen können:

• Kontextwechsel verursachen Overhead, da der Zustand des aktuellen Prozesses gespeichert und der Zustand des nächsten Prozesses geladen werden muss. Diese Vorgänge verbrauchen Prozessorzeit und Ressourcen.
• Kernresourcen und Caches müssen möglicherweise neu geladen werden, was zu Leistungseinbußen führen kann.
• Zu viele Kontextwechsel können zu schlechter Cache-Performance führen, da Daten von laufenden Aufgaben häufiger verdrängt werden.

Zusammenfassung

• Die Prioritätszuweisung bestimmt, welche Aufgaben bevorzugt ausgeführt werden, während der Kontextwechsel die Aufgabe tatsächlich wechselt.
• Häufige Kontextwechsel, insbesondere in hochfrequenten Umgebungen wie stark ausgelasteten Netzwerkservern, können die Systemleistung durch erhöhten Overhead und schlechtere Cache-Effizienz erheblich beeinträchtigen.

d)

Erstelle ein Zeitdiagramm für das oben beschriebene Aufgabenset (A1, A2, A3) unter Verwendung des Earliest Deadline First (EDF) Scheduling-Algorithmus für die ersten 20 ms. Erkläre, wie Deadlines in diesem Szenario verwaltet werden und welche Aufgabe in jedem Zeitslot ausgeführt wird.

Lösung:

Zeitdiagramm und Erklärung des Earliest Deadline First (EDF) Scheduling-AlgorithmusUm ein Zeitdiagramm für die Aufgaben A1, A2 und A3 unter Verwendung des Earliest Deadline First (EDF) Scheduling-Algorithmus für die ersten 20 ms zu erstellen, müssen wir die Deadlines und die Ausführungszeiten der Aufgaben berücksichtigen:

• A1: Periode = 5 ms, Ausführungszeit = 1 ms
• A2: Periode = 10 ms, Ausführungszeit = 2 ms
• A3: Periode = 20 ms, Ausführungszeit = 4 ms

Im EDF-Algorithmus wird die Aufgabe mit der frühesten Deadline zuerst ausgeführt. Deadlines werden periodisch aktualisiert.Deadlines der Aufgaben:

• A1: Deadlines sind bei 5 ms, 10 ms, 15 ms, 20 ms usw.
• A2: Deadlines sind bei 10 ms, 20 ms usw.
• A3: Deadlines sind bei 20 ms usw.

Zeitdiagramm (0 - 20 ms):

• 0 - 1 ms: A1
• 1 - 3 ms: A2
• 3 - 4 ms: A1
• 4 - 6 ms: A2
• 6 - 7 ms: A1
• 7 - 8 ms: Leerlauf (keine Aufgabe benötigt die CPU)
• 8 - 9 ms: A1
• 9 - 10 ms: A2
• 10 - 11 ms: A1
• 11 - 15 ms: A3
• 15 - 16 ms: A1
• 16 - 17 ms: Leerlauf
• 17 - 18 ms: A1
• 18 - 20 ms: A2

Erklärung der Deadlines und des Zeitdiagramms:

• Zeit 0 - 1 ms: A1 wird ausgeführt, da seine Deadline bei 5 ms liegt, was die früheste ist.
• Zeit 1 - 3 ms: A2 wird ausgeführt, da seine Deadline bei 10 ms liegt, die nächste Deadline nach A1 ist.
• Zeit 3 - 4 ms: A1 wird erneut ausgeführt, da die nächste Deadline bei 5 ms liegt.
• Zeit 4 - 6 ms: A2 wird erneut ausgeführt, da seine Deadline bei 10 ms näher ist als die nächste Deadline von A3.
• Zeit 6 - 7 ms: A1 wird erneut ausgeführt, da seine Deadline bei 10 ms ist und die nächste Deadline ist.
• Zeit 7 - 8 ms: Keine Aufgabe hat eine bevorstehende Deadline, also bleibt die CPU im Leerlauf.
• Zeit 8 - 9 ms: A1 wird ausgeführt, da die nächste Deadline bei 10 ms liegt.
• Zeit 9 - 10 ms: A2 wird ausgeführt, da die nächste Deadline bei 10 ms liegt.
• Zeit 10 - 11 ms: A1 wird erneut ausgeführt, da die nächste Deadline bei 15 ms liegt.
• Zeit 11 - 15 ms: A3 wird ausgeführt, da die nächste Deadline bei 20 ms liegt.
• Zeit 15 - 16 ms: A1 wird erneut ausgeführt, da seine nächste Deadline bei 20 ms liegt.
• Zeit 16 - 17 ms: Keine Aufgabe hat eine bevorstehende Deadline, also bleibt die CPU im Leerlauf.
• Zeit 17 - 18 ms: A1 wird erneut ausgeführt, da seine Deadline bei 20 ms und die nächst bevorstehende Deadline ist.
• Zeit 18 - 20 ms: A2 wird ausgeführt, da die nächste Deadline bei 20 ms liegt.

So wird basierend auf den Deadlines, die in regelmäßigen Abständen aktualisiert werden, bestimmt, welche Aufgabe in jedem Zeitslot ausgeführt wird. Im EDF-Szenario wickelt das System Aufgaben prioritär in der Reihenfolge ihrer Deadlines ab, um sicherzustellen, dass die nächste bevorstehende Frist immer zuerst berücksichtigt wird.

Aufgabe 4)

Betrachte ein hochkritisches Echtzeitsystem, das sich in einem modernen Automobil befindet und darauf ausgelegt ist, verschiedene Steuergeräte (ECUs) zu verbinden. Die Kommunikation zwischen diesen Steuergeräten muss deterministisch sein, um sicherzustellen, dass alle erforderlichen Daten innerhalb festgelegter Zeitrahmen übertragen werden. Dafür werden Protokolle und Standards wie TTP, IEEE 1588 PTP, CAN (mit TTCAN) und FlexRay verwendet.

Die Latenz und die exakte Zeitsynchronisation spielen eine wesentliche Rolle, und verschiedene Protokolle bieten unterschiedliche Lösungen für diese Herausforderungen.

a)

a) Erkläre detailliert das Prinzip des Time-Triggered Protocols (TTP) und dessen Verwendung in hochkritischen Anwendungen. Beschreibe, wie die Zeitsynchronisation zwischen den Steuergeräten erreicht wird und wie Kollisionen bei der Datenübertragung vermieden werden.

Lösung:

a) Erkläre detailliert das Prinzip des Time-Triggered Protocols (TTP) und dessen Verwendung in hochkritischen Anwendungen. Beschreibe, wie die Zeitsynchronisation zwischen den Steuergeräten erreicht wird und wie Kollisionen bei der Datenübertragung vermieden werden.

Time-Triggered Protocol (TTP)

• Grundprinzip: TTP basiert auf einem zeitgesteuerten Kommunikationsansatz, bei dem alle Nachrichten zu vordefinierten Zeitpunkten innerhalb eines Kommunikationszyklus gesendet werden. Dieser Ansatz garantiert, dass jede Nachricht zu einer festgelegten Zeit übertragen wird, wodurch die Deterministik und Vorhersagbarkeit der Kommunikation sichergestellt wird.
• Verwendung in hochkritischen Anwendungen: TTP wird häufig in sicherheitskritischen Anwendungen wie dem Automobilsektor, der Luft- und Raumfahrt sowie der Industrieautomation eingesetzt. Das Hauptziel ist es, eine verlässliche und vorhersagbare Datenübertragung zu gewährleisten, um die für die Sicherheit und Funktionalität essentiellen Daten rechtzeitig zu kommunizieren.

Zeitsynchronisation

• Zur Erreichung einer genauen Zeitsynchronisation wird in TTP eine global koordinierte Zeitbasis verwendet. Jeder Kommunikationszyklus ist in sogenannte Zeitschlitze unterteilt, und jeder Knoten im Netzwerk hat seine eigene Zeitscheibe, in der er Daten senden kann.
• Die Knoten synchronisieren ihre Uhren regelmäßig, indem sie spezielle Synchronisationsnachrichten empfangen und ihre lokalen Uhren entsprechend anpassen. Dies stellt sicher, dass alle Knoten stets dieselbe Zeitbasis verwenden und die Zeitschlitze exakt eingehalten werden.

Vermeidung von Kollisionen

• Durch die feste Zuweisung von Zeitschlitzen an jeden Knoten wird sichergestellt, dass nur ein Knoten zu einer bestimmten Zeit sendet. Dies eliminiert die Möglichkeit von Kollisionen zwischen Nachrichten, da die Zeitpunkte der Übertragungen genau geplant sind.
• Des Weiteren sind die Zeitschlitze so gestaltet, dass sie mögliche Jitter (Variationen in der Übertragungszeit) berücksichtigen, wodurch eine robustere Kommunikation gewährleistet wird.

b)

b) Angenommen, Du hast ein System mit 5 Steuergeräten, die über ein FlexRay-Netzwerk kommunizieren. Jedes Steuergerät hat festgelegte Zeitfenster für die Übertragung von Nachrichten. Berechne die maximale Übertragungsverzögerung, die auftreten könnte, wenn sich eine Nachricht des Steuergeräts 1 an Steuergerät 3 richten soll. Gegeben sind folgende Zeitfenster für den Zyklus: Steuergerät 1 (0-10 ms), Steuergerät 2 (10-20 ms), Steuergerät 3 (20-30 ms), Steuergerät 4 (30-40 ms), Steuergerät 5 (40-50 ms).

Hinweis: Gehe davon aus, dass die Zykluszeit fest bei 50 ms liegt und die Übertragung innerhalb eines Zyklus startet.

Lösung:

b) Angenommen, Du hast ein System mit 5 Steuergeräten, die über ein FlexRay-Netzwerk kommunizieren. Jedes Steuergerät hat festgelegte Zeitfenster für die Übertragung von Nachrichten. Berechne die maximale Übertragungsverzögerung, die auftreten könnte, wenn sich eine Nachricht des Steuergeräts 1 an Steuergerät 3 richten soll. Gegeben sind folgende Zeitfenster für den Zyklus: Steuergerät 1 (0-10 ms), Steuergerät 2 (10-20 ms), Steuergerät 3 (20-30 ms), Steuergerät 4 (30-40 ms), Steuergerät 5 (40-50 ms).

Hinweis: Gehe davon aus, dass die Zykluszeit fest bei 50 ms liegt und die Übertragung innerhalb eines Zyklus startet.

Maximale Übertragungsverzögerung:

• Die Nachricht wird von Steuergerät 1 innerhalb seines Zeitfensters (0-10 ms) gesendet.
• Nachdem Steuergerät 1 die Nachricht gesendet hat, kann Steuergerät 3 die Nachricht erst in seinem eigenen Zeitfenster (20-30 ms) empfangen.
• Die maximale Übertragungsverzögerung tritt auf, wenn Steuergerät 1 die Nachricht am Ende seines Zeitfensters, also bei 10 ms, sendet. Steuergerät 3 kann die Nachricht dann erst ab Beginn seines Zeitfensters, also bei 20 ms, empfangen.

Berechnung:

• Die Nachricht wird bei 10 ms gesendet.
• Die Nachricht wird bei 20 ms empfangen.
• Daraus ergibt sich eine maximale Übertragungsverzögerung von:

Formel:Übertragungsverzögerung = Empfangszeit - Sendezeit

Übertragungsverzögerung = 20 ms - 10 ms = 10 ms

Die maximale Übertragungsverzögerung beträgt somit 10 ms.