Echtzeitsysteme mit erweiterten Übungen - Exam

Aufgabe 1)

Definition und Charakteristika von Echtzeitsystemen: Systeme, die darauf ausgelegt sind, auf Eingaben innerhalb einer bestimmten Zeitspanne (Echtzeit) zu reagieren, und bei denen die Zeit der Reaktion genauso wichtig ist wie das korrekte Verhalten.

• Zeitbestimmte Reaktionen: Muss innerhalb einer definierten Frist reagieren
• Zuverlässigkeit: Hohe Zuverlässigkeit und Verfügbarkeit
• Determinismus: Vorhersehbares Verhalten
• Harte Echtzeitsysteme: Fehlende Reaktion führt zu katastrophalen Konsequenzen
• Weiche Echtzeitsysteme: Fehlende Reaktion führt zu Leistungseinbußen, aber nicht zu katastrophalen Folgen
• Formale Deadline: Reaktionszeit muss mathematisch beschreibbar sein
• Beispiel: Flugsteuerungssysteme, Fahrzeugsteuerungen, medizinische Geräte
• d(T): Zeitzwischen Ankunft eines Reizes und dessen Verarbeitung

a)

Angenommen, Du entwickelst ein Flugsteuerungssystem, das als ein hartes Echtzeitsystem klassifiziert ist.

• a) Erläutere, warum es für ein Flugsteuerungssystem zwingend notwendig ist, die Eigenschaften eines harten Echtzeitsystems zu besitzen. Gehe dabei auf die Konsequenzen ein, die bei einer Nichteinhaltung der Echtzeitbedingungen entstehen können.
• b) Betrachte, dass die Zeit d(T) zur Verarbeitung eines Reizes im System 20ms beträgt. Berechne die maximal mögliche Anzahl von Reizeingaben pro Sekunde, die vom System verarbeitet werden können, ohne dass die Echtzeiteigenschaften verletzt werden.

Lösung:

Definition und Charakteristika von Echtzeitsystemen: Systeme, die darauf ausgelegt sind, auf Eingaben innerhalb einer bestimmten Zeitspanne (Echtzeit) zu reagieren, und bei denen die Zeit der Reaktion genauso wichtig ist wie das korrekte Verhalten.

• Zeitbestimmte Reaktionen: Muss innerhalb einer definierten Frist reagieren
• Zuverlässigkeit: Hohe Zuverlässigkeit und Verfügbarkeit
• Determinismus: Vorhersehbares Verhalten
• Harte Echtzeitsysteme: Fehlende Reaktion führt zu katastrophalen Konsequenzen
• Weiche Echtzeitsysteme: Fehlende Reaktion führt zu Leistungseinbußen, aber nicht zu katastrophalen Folgen
• Formale Deadline: Reaktionszeit muss mathematisch beschreibbar sein
• Beispiel: Flugsteuerungssysteme, Fahrzeugsteuerungen, medizinische Geräte
• d(T): Zeit zwischen Ankunft eines Reizes und dessen Verarbeitung

Angenommen, Du entwickelst ein Flugsteuerungssystem, das als ein hartes Echtzeitsystem klassifiziert ist.

• a) Erläutere, warum es für ein Flugsteuerungssystem zwingend notwendig ist, die Eigenschaften eines harten Echtzeitsystems zu besitzen. Gehe dabei auf die Konsequenzen ein, die bei einer Nichteinhaltung der Echtzeitbedingungen entstehen können.

a) Erläuterung der Notwendigkeit eines harten Echtzeitsystems für Flugsteuerungssysteme:Ein Flugsteuerungssystem muss zwingend die Eigenschaften eines harten Echtzeitsystems besitzen, weil die Sicherheit und das Leben der Passagiere und der Crew davon abhängen. Echtzeitsysteme zeichnen sich durch ihre Fähigkeit aus, Eingaben innerhalb einer strikt definierten Zeitspanne zu verarbeiten. Bei einem Flugsteuerungssystem sind die Reaktionszeiten entscheidend für die Steuerung, Navigation und Stabilisierung des Flugzeugs. Wenn das System die vorgegebenen Echtzeitbedingungen nicht einhält, können schwerwiegende Probleme entstehen, wie z. B.:

• Verzögerungen bei der Ausführung von Steuerbefehlen können zu unkontrollierten Flugmanövern führen.
• Eine verspätete Reaktion auf kritische Situationen, wie das Ausweichen vor Hindernissen oder das Stabilisieren bei Turbulenzen, kann zu Flugzeugabstürzen führen.
• Kommunikationsprobleme mit Bodenstationen oder anderen Flugzeugen aufgrund von Verzögerungen können die Flugkoordination beeinträchtigen und Kollisionsrisiken erhöhen.

Zusammengefasst, führt die Nichteinhaltung der Echtzeitbedingungen bei einem Flugsteuerungssystem zu potentiell katastrophalen Konsequenzen, weshalb es unbedingt erforderlich ist, dass ein solches System als hartes Echtzeitsystem ausgelegt ist.

• b) Berechnung der maximal möglichen Anzahl von Reizeingaben pro Sekunde

b) Berechnung der maximal möglichen Anzahl von Reizeingaben pro Sekunde:Die Zeit d(T) zur Verarbeitung eines Reizes im System beträgt 20ms. Um die maximale Anzahl von Reizeingaben pro Sekunde zu berechnen, können wir die folgende Beziehung verwenden:

• Verarbeitungszeit pro Reiz, d(T) = 20ms = \(\frac{20}{1000}\) Sekunden
• Maximale Anzahl von Reizeingaben pro Sekunde = \(\frac{1}{d(T)}\)

Nun setzen wir die Werte ein:

• Maximale Anzahl von Reizeingaben pro Sekunde = \(\frac{1}{\frac{20}{1000}}\) = \(\frac{1000}{20}\) = 50 Reizeingaben pro Sekunde

Das bedeutet, dass das System maximal 50 Reizeingaben pro Sekunde verarbeiten kann, ohne dass die Echtzeiteigenschaften verletzt werden.

b)

Weiche Echtzeitsysteme erlauben gewisse Flexibilität hinsichtlich der Einhaltung der festgelegten Zeitspannen.

• a) Diskutiere zwei Szenarien, bei denen ein weiches Echtzeitsystem besser geeignet wäre als ein hartes Echtzeitsystem und erkläre Deine Wahl.
• b) Angenommen, ein weiches Echtzeitsystem für eine Video-Streaming-Anwendung hat eine Ziel-Latenzzeit von 150ms. Wenn das System jedoch aufgrund von Überlastungen eine tatsächliche Latenzzeit von bis zu 250ms erreicht, wie würde sich dies auf die Benutzererfahrung auswirken? Begründe Deine Antwort.

Lösung:

Definition und Charakteristika von Echtzeitsystemen: Systeme, die darauf ausgelegt sind, auf Eingaben innerhalb einer bestimmten Zeitspanne (Echtzeit) zu reagieren, und bei denen die Zeit der Reaktion genauso wichtig ist wie das korrekte Verhalten.

• Zeitbestimmte Reaktionen: Muss innerhalb einer definierten Frist reagieren
• Zuverlässigkeit: Hohe Zuverlässigkeit und Verfügbarkeit
• Determinismus: Vorhersehbares Verhalten
• Harte Echtzeitsysteme: Fehlende Reaktion führt zu katastrophalen Konsequenzen
• Weiche Echtzeitsysteme: Fehlende Reaktion führt zu Leistungseinbußen, aber nicht zu katastrophalen Folgen
• Formale Deadline: Reaktionszeit muss mathematisch beschreibbar sein
• Beispiel: Flugsteuerungssysteme, Fahrzeugsteuerungen, medizinische Geräte
• d(T): Zeit zwischen Ankunft eines Reizes und dessen Verarbeitung

Weiche Echtzeitsysteme erlauben gewisse Flexibilität hinsichtlich der Einhaltung der festgelegten Zeitspannen.

• a) Diskutiere zwei Szenarien, bei denen ein weiches Echtzeitsystem besser geeignet wäre als ein hartes Echtzeitsystem und erkläre Deine Wahl.
• b) Angenommen, ein weiches Echtzeitsystem für eine Video-Streaming-Anwendung hat eine Ziel-Latenzzeit von 150ms. Wenn das System jedoch aufgrund von Überlastungen eine tatsächliche Latenzzeit von bis zu 250ms erreicht, wie würde sich dies auf die Benutzererfahrung auswirken? Begründe Deine Antwort.

• a) Zwei Szenarien, bei denen ein weiches Echtzeitsystem besser geeignet ist:

Szenario 1: Multimedia-AnwendungenEin typisches Beispiel für ein weiches Echtzeitsystem wäre eine Multimedia-Anwendung, wie zum Beispiel ein Musikplayer oder eine Video-Streaming-Anwendung. In solchen Systemen ist es tolerierbar, wenn es gelegentlich zu Verzögerungen kommt, solange diese nicht zu häufig oder zu lang sind. Ein paar Millisekunden Verzögerung bei der Wiedergabe von Musik oder Video werden vom Benutzer oft nicht bemerkt. Daher würde ein weiches Echtzeitsystem ausreichen, da es die notwendige Flexibilität bietet und trotzdem eine zufriedenstellende Leistung gewährleistet.Szenario 2: Online-SpieleEin weiteres Beispiel sind Online-Spiele. Hier ist ebenfalls eine Echtzeitverarbeitung gefordert, jedoch können gelegentliche leichte Verzögerungen toleriert werden, da diese selten zu katastrophalen Folgen führen. Weiche Echtzeitsysteme sind besser geeignet, um die Balance zwischen Performance und Flexibilität zu halten, die erforderlich ist, um eine zufriedenstellende Spielerfahrung zu gewährleisten, auch bei schwankender Netzwerkqualität.

• b) Auswirkungen einer erhöhten Latenzzeit auf die Benutzererfahrung bei einer Video-Streaming-Anwendung:

Erläuterung der Auswirkungen:Angenommen, eine Video-Streaming-Anwendung hat eine Ziel-Latenzzeit von 150ms, erreicht aber aufgrund von Überlastung eine tatsächliche Latenzzeit von bis zu 250ms, so würde dies verschiedene Auswirkungen auf die Benutzererfahrung haben:

• Verzögerte Wiedergabebeginn: Wenn Benutzer ein Video starten, würden sie eine längere Wartezeit bemerken, bevor das Video startet, was die Zufriedenheit verringert. Eine Latenz von 250ms könnte merklich hoch sein und dem Benutzer das Gefühl geben, das System sei träge.
• Pufferung und Unterbrechungen: Erhöhte Latenzzeiten erhöhen die Wahrscheinlichkeit von Pufferung und Wiedergabeunterbrechungen, besonders wenn die Bandbreite gering ist. Dies führt zu Frust und einer schlechten Benutzererfahrung.
• Synchronisationsprobleme: Bei Live-Streaming oder Videokonferenzen kann eine erhöhte Latenz zu Synchronisationsproblemen zwischen Audio und Video führen, was die Kommunikation behindern oder ärgerlich sein könnte.

Zusammenfassend lässt sich sagen, dass eine erhöhte Latenzzeit von 250ms in einem weichen Echtzeitsystem für Video-Streaming zu einer weniger optimalen Benutzererfahrung führen würde. Während die Anwendung weiterhin funktional bleibt, könnten die beschriebenen Verzögerungen und Unterbrechungen die Benutzerzufriedenheit deutlich beeinträchtigen.

Aufgabe 2)

Du bist als Entwickler beauftragt, ein Echtzeitsystem zur Steuerung von Produktionsmaschinen in einer Fabrik zu entwerfen. Dazu musst Du präzise zeitliche Abläufe und Abhängigkeiten spezifizieren und modellieren. Es ist notwendig, sowohl absolute als auch relative Zeitangaben sowie diskrete Ereignisse und Zustandswechsel zu berücksichtigen. Als Werkzeuge stehen Dir UML-Diagramme und Petri-Netze zur Verfügung.

a)

Aufgabe 1: Modellierung von Zeitbeziehungen

• Erstelle ein UML-Sequenzdiagramm, das den Ablauf eines Arbeitsprozesses darstellt. Verwende die Zeitbeziehungen t_start, t_end und τ, um die Dauer und Abfolge der einzelnen Prozessschritte präzise zu beschreiben.
• Erkläre, wie Du in Deinem Modell sowohl absolute als auch relative Zeitangaben integriert hast.

Lösung:

Aufgabe 1: Modellierung von Zeitbeziehungen

• Erstelle ein UML-Sequenzdiagramm, das den Ablauf eines Arbeitsprozesses darstellt. Verwende die Zeitbeziehungen t_start, t_end und τ, um die Dauer und Abfolge der einzelnen Prozessschritte präzise zu beschreiben.
• Erkläre, wie Du in Deinem Modell sowohl absolute als auch relative Zeitangaben integriert hast.

Lösung:

1. UML-Sequenzdiagramm:

Hier ist ein UML-Sequenzdiagramm, das den Ablauf eines Arbeitsprozesses darstellt. Dabei verwenden wir t_start (Startzeitpunkt), t_end (Endzeitpunkt) und τ (Dauer) für eine präzise Beschreibung der zeitlichen Abläufe:

 +-------------------------+--------------------+-------------------------+ | Maschine 1              | Maschine 2         | Maschine 3              | +-------------------------+--------------------+-------------------------+ |  t_start                |                    |                         | |  |---------------------|                    |                         | |  |Step A (τA)|                    |                         | |  t_end                  |                    |                         | |                         |  t_start2|                         | |                         |  |---------------| |                         | |                         |  |Step B (τB)| |                         | |                         |  t_end2 |                         | |                                                  t_start3| |                                                  |---------------------| |                                                  |Step C (τC)| |                                                  t_end3    | +-------------------------+--------------------+-------------------------+

Beschreibung der Prozessschritte:

• Step A: t_start = Startzeitpunkt von Step A. t_end = Endzeitpunkt von Step A. τA = Dauer von Step A.
• Step B: t_start2 = Startzeitpunkt von Step B. t_end2 = Endzeitpunkt von Step B. τB = Dauer von Step B.
• Step C: t_start3 = Startzeitpunkt von Step C. t_end3 = Endzeitpunkt von Step C. τC = Dauer von Step C.

2. Integration von absoluten und relativen Zeitangaben:

In diesem Modell haben wir sowohl absolute als auch relative Zeitangaben integriert:

• Absolute Zeitangaben: Der Startzeitpunkt t_start, t_start2, und t_start3 sowie die Endzeitpunkte t_end, t_end2, und t_end3 können als absolute Zeitstempel (z.B. in Sekunden seit dem Start des Systems) betrachtet werden. Diese geben exakte Zeitpunkte im Prozess an.
• Relative Zeitangaben: Die Dauer τ der einzelnen Schritte (z.B. τA, τB, und τC) sind relative Zeitangaben. Sie geben an, wie lange ein bestimmter Prozessschritt dauert, unabhängig vom absoluten Zeitpunkt.

Auf diese Weise wird eine klare und präzise zeitliche Abfolge der Prozessschritte in Deinem Modell erreicht, was für die Steuerung von Produktionsmaschinen in Echtzeit von entscheidender Bedeutung ist.

b)

Aufgabe 2: Ereignismodellierung

• Modelliere die Zustandswechsel und diskreten Ereignisse eines Maschinensteuerungssystems mithilfe eines Petri-Netzes. Kennzeichne die Übergänge deutlich und beschrifte die Knoten mit den entsprechenden Zuständen und Ereignissen E_i und E_j.
• Nutze die Formel für den Zeitabstand \(\tau\) zwischen den Ereignissen und zeige an einem Beispiel, wie ein Zustandswechsel mit einer relativen Zeitangabe modelliert wird.

Lösung:

Aufgabe 2: Ereignismodellierung

• Modelliere die Zustandswechsel und diskreten Ereignisse eines Maschinensteuerungssystems mithilfe eines Petri-Netzes. Kennzeichne die Übergänge deutlich und beschrifte die Knoten mit den entsprechenden Zuständen und Ereignissen E_i und E_j.
• Nutze die Formel für den Zeitabstand \(\tau\) zwischen den Ereignissen und zeige an einem Beispiel, wie ein Zustandswechsel mit einer relativen Zeitangabe modelliert wird.

Lösung:

1. Petri-Netz zur Modellierung der Zustandswechsel und diskreten Ereignisse:

Hier ist eine Darstellung eines Petri-Netzes, das die Zustandswechsel und Ereignisse eines Maschinensteuerungssystems zeigt:

 [Zustand 1]----[E_1]---->[Zustand 2]----[E_2]---->[Zustand 3]----[E_3]---->[Zustand 4] || |         |       (τ_1)       |         |       (τ_2)       |         |       (τ_3)       ||         v                      v                      v                      v       /     [E_1]                 [E_2]                 [E_3]                 [E_4]

Beschreibung der Ereignisse und Zustände:

• Zustand 1: Der Anfangszustand der Maschine. Bereit für den Start des Prozesses.
• Ereignis E₁: Übergang von Zustand 1 zu Zustand 2. Dies könnte das Starten der Maschine oder ein spezifischer Prozessschritt sein. Dauer τ1.
• Zustand 2: Zwischenzustand nach dem ersten Ereignis, wartet auf das nächste Ereignis.
• Ereignis E₂: Übergang von Zustand 2 zu Zustand 3. Dies könnte ein weiterer Prozessschritt oder ein spezifischer Maschinenzustand sein. Dauer τ2.
• Zustand 3: Zwischenzustand nach dem zweiten Ereignis, wartet auf das nächste Ereignis.
• Ereignis E₃: Übergang von Zustand 3 zu Zustand 4. Dies könnte das Beenden der Maschine oder ein abschließender Prozessschritt sein. Dauer τ3.
• Zustand 4: Endzustand der Maschine. Prozess abgeschlossen.

2. Beispiel für einen Zustandswechsel mit relativer Zeitangabe:

Betrachte die Formel für den Zeitabstand \(\tau\) zwischen den Ereignissen:

• \(\tau = t_{end} - t_{start}\)

Nachdem die Maschine in Zustand 1 gestartet wurde (Ereignis E₁), dauert es eine bestimmte Zeit \( \tau_1 \), bis die Maschine in Zustand 2 übergeht. Zum Beispiel:

• Zustand 1 zu Zustand 2: t_{start} = 0 s (Startzeitpunkt von Zustand 1) t_{end} = 10 s (Endzeitpunkt von Zustand 1 und Startzeitpunkt von Zustand 2) Somit ist der Zeitabstand \( \tau_1 \) = 10 s.

Dieses Prinzip wird auf alle nachfolgenden Zustandswechsel angewendet:

• Zustand 2 zu Zustand 3: t_{start} = 10 s (Startzeitpunkt von Zustand 2) t_{end} = 20 s (Endzeitpunkt von Zustand 2 und Startzeitpunkt von Zustand 3) Somit ist der Zeitabstand \( \tau_2 \) = 10 s.
• Zustand 3 zu Zustand 4: t_{start} = 20 s (Startzeitpunkt von Zustand 3) t_{end} = 30 s (Endzeitpunkt von Zustand 3 und Startzeitpunkt von Zustand 4) Somit ist der Zeitabstand \( \tau_3 \) = 10 s.

Durch die Nutzung dieser Methode wird die Modellierung der Zustandswechsel und diskreten Ereignisse in einem Maschinensteuerungssystem präzise und verständlich dargestellt.

Aufgabe 3)

Ein Unternehmen plant die Einführung eines neuen Echtzeitsystems zur Steuerung eines autonomen Fahrzeugs. Das System soll verschiedene Aufgaben mit festen zeitlichen Vorgaben ausführen, einschließlich Sensorabfragen, Datenverarbeitung und Steuerbefehlen. Dazu müssen sie entscheiden, ob sie ein hartes oder weiches Echtzeitsystem implementieren. Darüber hinaus müssen sie geeignete Scheduling-Algorithmen wie RM oder EDF anwenden.

a)

(a) Erläutere den Unterschied zwischen harten und weichen Echtzeitsystemen. Diskutiere, welche Art von Echtzeitsystem für das autonome Fahrzeug geeignet ist und warum.

Lösung:

(a) Der Unterschied zwischen harten und weichen Echtzeitsystemen kann wie folgt erklärt werden:

• Hartes Echtzeitsystem: In einem harten Echtzeitsystem müssen alle Aufgaben innerhalb ihrer festgelegten Zeitvorgaben (Deadlines) abgeschlossen sein. Verfehlen einer Deadline führt zu einem Systemversagen oder zumindest zu erheblichen Problemen. Ein Beispiel ist ein Flugzeugsystem, bei dem ein Versagen katastrophale Folgen haben kann.
• Weiches Echtzeitsystem: In einem weichen Echtzeitsystem ist es akzeptabel, wenn einige Aufgaben gelegentlich ihre Deadlines verfehlen. Solche Verzögerungen führen nicht zu einem vollständigen Systemversagen, sondern nur zu einer Verschlechterung der Leistung. Beispiele hierfür sind Video-Streaming-Anwendungen, bei denen ein kleiner Verlust an Frames tolerierbar ist.

Für das autonome Fahrzeug ist ein hartes Echtzeitsystem besser geeignet. Dies liegt daran, dass das Fahrzeug in der realen Welt operiert und die Sicherheit von Menschen gewährleistet werden muss. Wenn eine Deadline verfehlt wird, könnte dies zu gefährlichen Situationen führen, wie z.B. Unfällen. Daher ist es entscheidend, dass alle sensorischen Abfragen, Datenverarbeitungen und Steuerbefehle innerhalb ihrer vorgegebenen Zeitgrenzen abgeschlossen werden, um eine sichere und zuverlässige Funktion des autonomen Fahrzeugs zu gewährleisten.

b)

(b) Angenommen, es gibt drei Aufgaben im System mit folgenden Parametern:

• Task 1: Period (T₁) = 50 ms, Ausführungszeit (C₁) = 15 ms, Deadline (D₁) = 50 ms
• Task 2: Period (T₂) = 100 ms, Ausführungszeit (C₂) = 25 ms, Deadline (D₂) = 100 ms
• Task 3: Period (T₃) = 200 ms, Ausführungszeit (C₃) = 30 ms, Deadline (D₃) = 200 ms

Berechne die Utilization (U) des Systems und entscheide, ob das System unter Nutzung der RM (Rate-Monotonic) Scheduling-Algorithmus planbar ist.

Lösung:

(b) Um die Utilization (\textit{U}) des Systems zu berechnen, müssen wir die Summe der Verhältnisse der Ausführungszeiten (\textit{C}) zu ihren jeweiligen Perioden (\textit{T}) für alle Aufgaben bestimmen. Wir haben drei Aufgaben mit den angegebenen Parametern:

• Task 1: \textit{T}₁ = 50 ms, \textit{C}₁ = 15 ms, \textit{D}₁ = 50 ms
• Task 2: \textit{T}₂ = 100 ms, \textit{C}₂ = 25 ms, \textit{D}₂ = 100 ms
• Task 3: \textit{T}₃ = 200 ms, \textit{C}₃ = 30 ms, \textit{D}₃ = 200 ms

Die Utilization (\textit{U}) des Systems wird wie folgt berechnet:

\textit{U} = \frac{\textit{C}₁}{\textit{T}₁} + \frac{\textit{C}₂}{\textit{T}₂} + \frac{\textit{C}₃}{\textit{T}₃}

Einsetzen der gegebenen Werte ergibt:

\textit{U} = \frac{15}{50} + \frac{25}{100} + \frac{30}{200}

Um die Berechnungen durchzuführen:

• \frac{15}{50} = 0.3
• \frac{25}{100} = 0.25
• \frac{30}{200} = 0.15

Somit ergibt sich:

\textit{U} = 0.3 + 0.25 + 0.15 = 0.7

Die maximale Utilization (\textit{U}_max) für \textit{n} Aufgaben unter Nutzung der RM (Rate-Monotonic) Scheduling-Algorithmus kann berechnet werden mit der Formel:

\textit{U}_max = \textit{n}(2^{\frac{1}{n}}-1)

Für den Fall \textit{n} = 3:

\textit{U}_max = 3(2^{\frac{1}{3}}-1)

Rechnen wir das aus:

2^{\frac{1}{3}} ≈ 1.26

Also:

\textit{U}_max = 3(1.26-1) = 3(0.26) ≈ 0.78

Da die berechnete Utilization (\textit{U} = 0.7) kleiner ist als die maximale Utilization (\textit{U}_max = 0.78), ist das System unter Nutzung des RM Scheduling-Algorithmus planbar.

c)

(c) Erkläre den EDF (Earliest Deadline First) Scheduling-Algorithmus. Vergleiche ihn mit dem RM-Algorithmus in Bezug auf Effizienz und Planbarkeit für das gegebene Aufgabenset.

Lösung:

(c) Der EDF (Earliest Deadline First) Scheduling-Algorithmus und der RM (Rate-Monotonic) Scheduling-Algorithmus sind zwei gängige Methoden zur Planung von Echtzeitsystemen.

• EDF (Earliest Deadline First): Bei EDF wird die Aufgabe mit der nächstgelegenen Deadline zuerst ausgeführt. Das bedeutet, dass das System ständig die Deadlines der aktuellen Aufgaben überwacht und jene Aufgabe priorisiert, deren Deadline am frühesten erreicht wird. EDF ist ein dynamischer Scheduling-Algorithmus, weil die Priorität der Aufgaben zur Laufzeit, basierend auf den aktuellen Deadlines, geändert wird.
• RM (Rate-Monotonic): Bei RM werden die Aufgaben anhand ihrer Perioden priorisiert. Die Aufgabe mit der kürzesten Periode erhält die höchste Priorität und wird zuerst ausgeführt. RM ist ein statischer Prioritäts-Scheduling-Algorithmus, da die Prioritäten der Aufgaben im Voraus und unabhängig von ihrer Laufzeit bestimmt werden.

Vergleich von EDF und RM:

• Effizienz: EDF gilt im Allgemeinen als effizienter als RM, weil es flexibler mit unterschiedlichen Deadlines umgehen kann. Bei EDF können alle Aufgaben planbar gemacht werden, solange die Gesamtauslastung (U) des Systems <= 1 (100 %) ist. RM ist für die Planung von Aufgaben konservativer und kann nur Aufgaben planen, solange die Gesamtauslastung (U) unter einer spezifischen Schranke liegt (beispielsweise U_max = 0.78 für 3 Aufgaben).
• Planbarkeit: Da EDF dynamisch ist, kann es oft eine größere Anzahl von Aufgaben planen als RM. Wenn die Deadlines der Aufgaben nah beieinander liegen oder sich ändern, kann EDF besser anpassen und sicherstellen, dass mehr Aufgaben termingerecht ausgeführt werden.

Für das angegebene Aufgabenset (siehe Teil (b)):

• Für RM wurde bereits festgestellt, dass die Gesamtauslastung (0.7) kleiner als die maximale erlaubte Auslastung (0.78) ist, somit ist das System planbar.
• Für EDF: Die Gesamtauslastung (U = 0.7) ist <= 1, was bedeutet, dass das System ebenfalls unter EDF planbar ist.

Zusammenfassend lässt sich sagen, dass beide Algorithmen für das gegebene Aufgabenset geeignet sind. EDF bietet jedoch generell eine höhere Effizienz und bessere Planbarkeit, besonders wenn die Aufgabenanzahl steigt oder wenn Deadlines variieren.

d)

(d) Beschreibe, wie Prioritäten und Präemption im Kontext von Echtzeitsystemen funktionieren. Gib ein Beispiel, wie Präemption bei der Ausführung einer hochpriorisierten und einer niedrigpriorisierten Aufgabe in einem autonomen Fahrzeug eingesetzt werden kann.

Lösung:

(d) Prioritäten und Präemption sind wesentliche Konzepte im Kontext von Echtzeitsystemen und bestimmen, wie Aufgaben verwaltet und geplant werden, um sicherzustellen, dass zeitliche Vorgaben erfüllt werden.

• Prioritäten: Jeder Aufgabe wird eine Priorität zugewiesen, die bestimmt, wie wichtig es ist, dass diese Aufgabe im System ausgeführt wird. Aufgaben mit höherer Priorität werden vor Aufgaben mit niedrigerer Priorität ausgeführt. Zum Beispiel kann eine Aufgabe, die eine sofortige Steuerreaktion erfordert, eine höhere Priorität haben als eine Routine-Datenspeicherung.
• Präemption: Präemption bedeutet, dass eine laufende Aufgabe unterbrochen wird, um eine andere, höher priorisierte Aufgabe auszuführen. Sobald die höher priorisierte Aufgabe abgeschlossen ist, wird die unterbrochene Aufgabe fortgesetzt. Dies stellt sicher, dass kritische Aufgaben rechtzeitig bearbeitet werden können, auch wenn weniger dringende Aufgaben laufend sind.

Beispiel im autonomen Fahrzeug:

Annahmen:

• Hochpriorisierte Aufgabe: Echtzeitverarbeitung von Sensorinformationen zur Vermeidung von Kollisionen (kritisch für die Sicherheit).
• Niedrigpriorisierte Aufgabe: Regelmäßige Datenprotokollierung zur späteren Analyse (weniger kritisch).

Szenario:

• Beginn: Das Fahrzeug ist unterwegs, und die niedrigpriorisierte Aufgabe (Datenspeicherung) wird ausgeführt.
• Sensorereignis: Ein plötzliches Hindernis wird von den Sensoren erkannt, und die hochpriorisierte Aufgabe (Sensorverarbeitung zur Kollisionsvermeidung) wird ausgelöst.
• Präemption: Die laufende Datenspeicherung wird sofort unterbrochen, und die Aufgabe der Kollisionsvermeidung wird ausgeführt.
• Fortsetzung: Sobald die notwendige Berechnung zur Kollisionsvermeidung abgeschlossen und entsprechende Steuerbefehle an das Fahrzeug gesendet wurden, wird die unterbrochene Datenspeicherung wieder fortgesetzt.

Durch den Einsatz von Prioritäten und Präemption wird sichergestellt, dass in kritischen Momenten (z.B. zur Verhinderung eines Unfalls) die notwendige Reaktionszeit erreicht wird, während weniger dringende Aufgaben (z.B. Datenspeicherung) zu einem späteren, sichereren Zeitpunkt fortgeführt werden können.

Aufgabe 4)

Kontext: In einem Echtzeitsystem müssen verschiedene Aufgaben mit unterschiedlichen Zeitbeschränkungen bearbeitet werden. Diese Aufgaben umfassen harte Deadlines, weiche Deadlines, sporadische Aufgaben und periodische Aufgaben. Harte Deadlines müssen unbedingt eingehalten werden, während weiche Deadlines leichte Überschreitungen tolerieren. Sporadische Aufgaben treten unregelmäßig auf und periodische Aufgaben wiederholen sich in einem festen Zyklus. Ein versäumter Termin (Deadline-Miss) kann entweder Systemversagen verursachen oder akzeptiert werden, je nach Art der Deadline.

a)

Beschreibe die Unterschiede zwischen einer harten und einer weichen Deadline. Nenne jeweils ein Beispiel aus der Praxis, bei dem eine harte Deadline und eine weiche Deadline eine Rolle spielen könnten.

Lösung:

Unterschiede zwischen harter und weicher Deadline

• Harte Deadline: Eine harte Deadline ist ein Zeitpunkt, der unbedingt eingehalten werden muss. Wenn eine harte Deadline überschritten wird, kann dies schwerwiegende Konsequenzen haben, bis hin zu einem vollständigen Systemversagen. Beispiele:
  • In einem Flugzeug, das Autopilot-System: Wenn der Autopilot eine Steuerungsentscheidung nicht innerhalb einer sehr kurzen, festgelegten Zeit trifft, kann dies zu einem Absturz führen.
  • In medizinischen Geräten wie einem Herzschrittmacher: Wenn der Schrittmacher einen elektrischen Impuls nicht rechtzeitig abgibt, kann dies zu lebensbedrohlichen Zuständen führen.
• Weiche Deadline: Eine weiche Deadline ist ein Zeitpunkt, der idealerweise eingehalten werden sollte, aber das Überschreiten dieser Zeitspanne wird in gewissen Grenzen toleriert. Die Konsequenzen sind weniger schwerwiegend und können oft akzeptiert werden. Beispiele:
  • In einem Media-Streaming-Dienst: Wenn der Dienst ein paar Millisekunden später Puffer lädt, wird dies vom Benutzer möglicherweise kaum bemerkt.
  • Bei einem Live-Videospiel: Leichte Verzögerungen bei der Anzeige von Spieleraktionen können toleriert werden, solange das Spiel im Allgemeinen flüssig bleibt.

b)

Gegeben sei ein Echtzeitsystem mit folgenden Aufgaben:

• Aufgabe A: Harte Deadline alle 100 ms
• Aufgabe B: Weiche Deadline alle 150 ms
• Aufgabe C: Sporadisch, Ankunft im Durchschnitt alle 200 ms
• Aufgabe D: Periodisch, Zykluszeit 50 ms

Bestimme den maximalen CPU-Auslastungsfaktor, wenn die Ausführungszeit einer jeden Aufgabe gleich 10 ms beträgt.

Lösung:

Bestimmung des maximalen CPU-Auslastungsfaktors

Um den maximalen CPU-Auslastungsfaktor zu berechnen, müssen wir die Ausführungszeit jeder Aufgabe durch ihre jeweilige Periode teilen und die Ergebnisse addieren. Der CPU-Auslastungsfaktor (auch bekannt als CPU-Utilization) gibt an, wie viel Prozent der CPU-Zeit von den Aufgaben beansprucht wird.

Gegebene Daten

• Aufgabe A: Harte Deadline alle 100 ms, Ausführungszeit 10 ms
• Aufgabe B: Weiche Deadline alle 150 ms, Ausführungszeit 10 ms
• Aufgabe C: Sporadisch, Ankunft im Durchschnitt alle 200 ms, Ausführungszeit 10 ms
• Aufgabe D: Periodisch, Zykluszeit 50 ms, Ausführungszeit 10 ms

Berechnung des CPU-Auslastungsfaktors

Die Berechnungsformel für den CPU-Auslastungsfaktor bei jeder Aufgabe lautet:

\(\text{Auslastungsfaktor} = \frac{\text{Ausführungszeit}}{\text{Periode}}\)

• Aufgabe A: \(\text{Auslastungsfaktor}_A = \frac{10}{100} = 0.1\)
• Aufgabe B: \(\text{Auslastungsfaktor}_B = \frac{10}{150} \approx 0.067\)
• Aufgabe C: \(\text{Auslastungsfaktor}_C = \frac{10}{200} = 0.05\)
• Aufgabe D: \(\text{Auslastungsfaktor}_D = \frac{10}{50} = 0.2\)

Der maximale CPU-Auslastungsfaktor ist die Summe der einzelnen Auslastungsfaktoren:

\(\text{maximaler CPU-Auslastungsfaktor} = \text{Auslastungsfaktor}_A + \text{Auslastungsfaktor}_B + \text{Auslastungsfaktor}_C + \text{Auslastungsfaktor}_D\)

Einsetzen der Werte ergibt:

\(\text{maximaler CPU-Auslastungsfaktor} = 0.1 + 0.067 + 0.05 + 0.2 = 0.417\)

Somit beträgt der maximale CPU-Auslastungsfaktor 0.417 oder 41.7%.

c)

Erstelle ein Scheduling-Algorithmus (z.B. Rate Monotonic Scheduling oder Earliest Deadline First) für die oben genannten Aufgaben und erkläre, wie der Algorithmus sicherstellt, dass die harten Deadlines immer eingehalten werden.

Lösung:

Erstellung eines Scheduling-Algorithmus: Rate Monotonic Scheduling (RMS)

Rate Monotonic Scheduling (RMS) ist ein prioritätsbasierter präemptiver Scheduling-Algorithmus, der häufig in Echtzeitsystemen verwendet wird. Bei RMS werden den Aufgaben Prioritäten basierend auf ihrer Zykluszeit (Periode) zugewiesen: Je kürzer die Periode, desto höher die Priorität. Da RMS eine analyzierte und bewährte Methode ist, eignet es sich gut für Systeme mit festen Perioden, insbesondere wenn harte Deadlines eingehalten werden müssen.

Anwendung von RMS auf die gegebenen Aufgaben

Die Aufgaben haben die folgenden Perioden:

• Aufgabe A: Periode 100 ms (harte Deadline)
• Aufgabe B: Periode 150 ms (weiche Deadline)
• Aufgabe C: Durchschnittliche Ankunftszeit 200 ms (sporadisch)
• Aufgabe D: Periode 50 ms (periodisch)

Basierend auf RMS weisen wir den Aufgaben Prioritäten zu:

1. Aufgabe D (höchste Priorität, Periode 50 ms)
2. Aufgabe A (zweithöchste Priorität, Periode 100 ms)
3. Aufgabe B (dritthöchste Priorität, Periode 150 ms)
4. Aufgabe C (niedrigste Priorität, durchschnittliche Ankunftszeit 200 ms)

Sicherstellung der harten Deadlines

Um sicherzustellen, dass die harten Deadlines immer eingehalten werden, führt der RMS-Algorithmus folgende Schritte aus:

1. Zuweisung von Prioritäten: Für jede Aufgabe wird eine feste Priorität basierend auf ihrer Periode zugewiesen. Dies bedeutet, dass Aufgaben mit kürzeren Perioden immer höhere Priorität haben.
2. Präemptiv Scheduling: Höher priorisierte Aufgaben können zu jeder Zeit niedrigere Priorität Aufgaben unterbrechen (präempieren), um sicherzustellen, dass sie rechtzeitig ausgeführt werden.
3. Rechtzeitige Ausführung: Da Aufgabe A eine harte Deadline hat und ihr eine höhere Priorität als Aufgabe B und C zugewiesen wird, wird sie immer rechtzeitig ausgeführt. Aufgabe D hat die höchste Priorität und wird ebenfalls immer rechtzeitig ausgeführt.
4. Sporadische Aufgaben: Aufgabe C wird ausgeführt, wenn CPU-Zeit verfügbar ist und die höher priorisierten Aufgaben (D, A und B) beendet oder präemtiert sind.

Zusammenfassung

Im RMS-Algorithmus stellen die folgenden Punkte sicher, dass harte Deadlines in einem Echtzeitsystem immer eingehalten werden:

• Fixe Prioritäten basierend auf der Periodenlänge, wobei kürzere Perioden höhere Prioritäten erhalten.
• Präemptive Planung, die höher priorisierten Aufgaben ermöglicht, niedrig priorisierte Aufgaben zu unterbrechen.
• Rechtzeitige Ausführung der Aufgaben mit harter Deadline durch Zuweisung höherer Priorität.

d)

Angenommen, Aufgabe C tritt zweimal in kurzer Folge auf und führt zu einem Deadline-Miss. Welche Maßnahmen könnten in einem Echtzeitsystem implementiert werden, um sicherzustellen, dass keine weiteren harten Deadlines verpasst werden? Diskutiere Vor- und Nachteile der vorgeschlagenen Maßnahmen.

Lösung:

Maßnahmen zur Sicherstellung, dass keine harten Deadlines verpasst werden

Eine plötzlich erhöhte Auftretensrate von sporadischen Aufgaben wie Aufgabe C kann zu Deadline-Misses führen. Um sicherzustellen, dass in einem Echtzeitsystem keine weiteren harten Deadlines verpasst werden, können verschiedene Maßnahmen implementiert werden:

1. Prioritätsanpassung

Eine Möglichkeit besteht darin, die Prioritäten von Aufgaben dynamisch anzupassen. Wenn Aufgabe C unerwartet häufiger auftritt, könnte man die Priorität der harten Deadline-Aufgaben (Aufgabe A) auf die höchste Stufe setzen, um sicherzustellen, dass sie nicht durch sporadische Aufgaben beeinträchtigt werden.

• Vorteile:- Sicherstellung, dass harte Deadlines immer vorrangig behandelt werden können.- Flexible Reaktion auf Veränderungen der Systembelastung.
• Nachteile:- Kann zu einer Verzögerung bei anderen Aufgaben führen.- Erfordert ein komplexeres Scheduling-Management.

2. Überwachung und Begrenzung der Ressourcen

Implementiere Mechanismen zur Ressourcenüberwachung und Begrenzung, um sicherzustellen, dass sporadische Aufgaben wie Aufgabe C das System nicht überlasten. Eine Möglichkeit wäre es, die Anzahl der zulässigen Instanzen von sporadischen Aufgaben innerhalb eines bestimmten Zeitraums zu begrenzen.

• Vorteile:- Verhindert eine Überlastung durch sporadische Aufgaben.- Einfacher zu implementieren als dynamische Prioritätsanpassungen.
• Nachteile:- Sporadische Aufgaben könnten möglicherweise nicht rechtzeitig verarbeitet werden.- Erfordert eine sorgfältige Konfigurationsoptimierung.

3. Lastverteilung

Sollte die Systemarchitektur es erlauben, kann eine Lastverteilung auf mehrere Prozessoren oder Systeme die Belastung durch sporadische Aufgaben reduzieren. Aufgaben könnten auf separate CPUs oder Threads verteilt werden, um Interferenzen zu minimieren.

• Vorteile:- Parallelisierung verbessert die Reaktionszeiten.- Minimiert die Auswirkungen einer erhöhten Last auf einzelne Komponenten.
• Nachteile:- Erhöhte Komplexität der Systemarchitektur.- Erfordert möglicherweise zusätzliche Hardware-Ressourcen.

4. Implementierung eines Watchdog-Timers

Ein Watchdog-Timer könnte genutzt werden, um das System kontinuierlich zu überwachen. Wird eine harte Deadline verpasst, könnte eine sofortige Korrekturmaßnahme wie das Neustarten des Systems oder das Anpassen der Prioritäten durchgeführt werden.

• Vorteile:- Schnelle Reaktion auf Fehlerzustände.- Betrieb des Systems im fehlerfreien Zustand wird gewährleistet.
• Nachteile:- Erhöht die Systemkomplexität.- Kann zu kurzzeitigen Unterbrechungen im Systembetrieb führen.

Zusammenfassung

Die Umsetzung dieser Maßnahmen erfordert ein sorgfältiges Gewichten der Vor- und Nachteile. Dynamische Prioritätsanpassungen und Ressourcenüberwachung bieten große Vorteile bezüglich der Verlässlichkeit, jedoch auf Kosten komplexerer Implementierungen und möglichen Verzögerungen bei anderen Aufgaben. Lastverteilung und Watchdog-Timer bieten ebenfalls wirksame Strategien, erfordern aber eine ausgeklügelte Systemarchitektur und können zusätzliche Hardware-Ressourcen verlangen.