Echtzeitsysteme mit erweiterten Übungen - Exam

Aufgabe 1)

Echtzeitsysteme sind Computersysteme, die ihre Aufgaben innerhalb einer festgelegten Zeitspanne ausführen müssen.

• Determinismus: Vorhersehbares Verhalten
• Zeitschranken: Deadlines müssen eingehalten werden
• Reaktionsfähigkeit: Schnelle Reaktion auf externe Ereignisse
• Zuverlässigkeit: Hohe Verfügbarkeit und Fehlertoleranz
• Oft verwendet in: Automobilindustrie, Medizintechnik, Raumfahrt
• Echtzeitanforderungen:
  • Harte Echtzeitsysteme: Strikte Deadlines
  • Weiche Echtzeitsysteme: Flexible Deadlines
• Latency und Jitter minimieren

a)

Angenommen, Du entwirfst ein Echtzeitsystem für ein autonomes Fahrzeug. Beschreibe ausführlich, wie Du sicherstellen würdest, dass Deine Software deterministic und zeitlich vorhersehbar ist. Berücksichtige dabei Aspekte wie Scheduling, Ressourcenmanagement und Fehlertoleranz.

Lösung:

Angenommen, Du entwirfst ein Echtzeitsystem für ein autonomes Fahrzeug. Beschreibe ausführlich, wie Du sicherstellen würdest, dass Deine Software deterministisch und zeitlich vorhersehbar ist. Berücksichtige dabei Aspekte wie Scheduling, Ressourcenmanagement und Fehlertoleranz.Um sicherzustellen, dass die Software eines Echtzeitsystems für ein autonomes Fahrzeug deterministisch und zeitlich vorhersehbar ist, müssen verschiedene Aspekte berücksichtigt werden:

• Scheduling:
  • Prioritätenbasierte Planung: Verwende einen Echtzeitbetriebssystem (RTOS) mit einem prioritätsgesteuerten Schedulingsystem. Aufgaben, die kritische Deadlines haben, müssen höhere Prioritäten erhalten.
  • Fixed Priority Scheduling (FPS): Implementiere ein Scheduling-System mit festen Prioritäten, bei dem jede Aufgabe eine feste Priorität basierend auf ihrer Dringlichkeit erhält.
  • Rate Monotonic Scheduling (RMS): Nutze RMS für regelmäßige Aufgaben, wobei kürzere Aufgaben höhere Prioritäten erhalten.
  • Deadline Monotonic Scheduling (DMS): Verteile Prioritäten basierend auf der Deadline jeder Aufgabe, sodass Aufgaben mit kürzeren Deadlines höhere Prioritäten erhalten.
  • Task Preemption: Stelle sicher, dass hochpriorisierte Aufgaben niedrigpriorisierte unterbrechen können, um dringende Aufgaben pünktlich zu erledigen.
• Ressourcenmanagement:
  • Mutex und Semaphoren: Verwende Mechanismen wie Mutexe und Semaphoren, um den synchronisierten Zugriff auf gemeinsame Ressourcen zu gewährleisten und Deadlocks zu vermeiden.
  • Memory Management: Implementiere statisches Speichermanagement, um die Unvorhersehbarkeit von dynamischer Speicherzuweisung zu vermeiden.
  • Fixed Partitioning: Teile Ressourcen wie Speicher und CPU-Zeit vorab festen Aufgaben zu, um eine zeitlich vorhersehbare Ausführung zu gewährleisten.
  • Time Partitioning: Nutze Techniken wie Zeitpartitionierung, um sicherzustellen, dass jede Aufgabe innerhalb eines garantierten Zeitfensters ausgeführt wird.
• Fehlertoleranz:
  • Redundanz: Implementiere Hardware- und Software-Redundanz, um die Zuverlässigkeit des Systems zu erhöhen. Dies kann durch mehrere Sensoren, Backup-Systeme und redundante Kommunikationskanäle erreicht werden.
  • Error Detection und Correction: Verwende Fehlererkennungs- und Korrekturmechanismen, wie zum Beispiel CRC (Cyclic Redundancy Check) und Watchdog-Timer.
  • Fail-Safe Mechanismen: Füge Fail-Safe-Mechanismen hinzu, um das Fahrzeug in einen sicheren Zustand zu bringen, wenn ein Fehler auftritt. Dies könnte durch sicheres Anhalten des Fahrzeugs oder Umschalten auf einen manuell steuerbaren Modus erreicht werden.
• Minimierung von Latenz und Jitter:
  • Minimal Interrupt Latency: Reduziere die Unterbrechungslatenz durch ein effizientes Interrupt-Handling.
  • Real-Time Kernel: Verwende ein Echtzeitkernel mit minimalem Overhead und optimierter Kontextwechselzeit.

Durch eine sorgfältige Berücksichtigung all dieser Aspekte kannst Du sicherstellen, dass das Echtzeitsystem des autonomen Fahrzeugs deterministisch und zeitlich vorhersehbar bleibt, was insbesondere für die Sicherheit und Zuverlässigkeit des Fahrzeugs entscheidend ist.

b)

Berechne den maximalen Jitter für ein System mit folgenden Aufgaben und Zeitbeschränkungen:

• Aufgabe A: Ausführungszeit = 20ms, Deadline = 50ms
• Aufgabe B: Ausführungszeit = 10ms, Deadline = 25ms
• Aufgabe C: Ausführungszeit = 15ms, Deadline = 30ms

Veranschauliche Deine Berechnungen anhand eines Zeitdiagramms.

Lösung:

Berechne den maximalen Jitter für ein System mit folgenden Aufgaben und Zeitbeschränkungen:

• Aufgabe A: Ausführungszeit = 20ms, Deadline = 50ms
• Aufgabe B: Ausführungszeit = 10ms, Deadline = 25ms
• Aufgabe C: Ausführungszeit = 15ms, Deadline = 30ms

Um den maximalen Jitter für jedes dieser Systeme zu berechnen, müssen wir die Zeitschranken und die möglichen Verzögerungen berücksichtigen. Der Jitter ist die maximale Abweichung der tatsächlichen Ausführungszeit von der geplanten Ausführungszeit.

• Für Aufgabe A:
  • Ausführungszeit: 20ms
  • Deadline: 50ms
  • Maximale Verzögerung bis zur Deadline: 50ms - 20ms = 30ms
  Der Jitter für Aufgabe A beträgt daher maximal 30ms.
• Für Aufgabe B:
  • Ausführungszeit: 10ms
  • Deadline: 25ms
  • Maximale Verzögerung bis zur Deadline: 25ms - 10ms = 15ms
  Der Jitter für Aufgabe B beträgt daher maximal 15ms.
• Für Aufgabe C:
  • Ausführungszeit: 15ms
  • Deadline: 30ms
  • Maximale Verzögerung bis zur Deadline: 30ms - 15ms = 15ms
  Der Jitter für Aufgabe C beträgt daher maximal 15ms.

Um die Ergebnisse zu veranschaulichen, können wir ein Zeitdiagramm zeichnen:

|---------------------|---------------------|---------------------|---------------------|---------------------|0                    20                   40                    60                   80                    100Aufgabe A:|********************|                       (maximal 30ms Verzögerung)Aufgabe B:|**********           (maximal 15ms Verzögerung)Aufgabe C:|***************      (maximal 15ms Verzögerung)Legende:|: Zeitachse in Millisekunden*: Ausführungszeit der Aufgabe

Aus dem Diagramm wird ersichtlich, dass die maximale Verzögerung (Jitter) für die Aufgaben A, B und C wie oben berechnet 30ms, 15ms und 15ms beträgt. Diese Veranschaulichung hilft, die Pufferzeiten bis zu den Deadlines zu sehen und die möglichen Jitter besser zu verstehen.

c)

Erläutere den Unterschied zwischen harten und weichen Echtzeit-Anforderungen. Gib Beispiele für beide Arten von Echtzeitsystemen und diskutiere, wie Du die Einhaltung von Deadlines jeweils sicherstellen würdest.

Lösung:

Erläutere den Unterschied zwischen harten und weichen Echtzeit-Anforderungen. Gib Beispiele für beide Arten von Echtzeitsystemen und diskutiere, wie Du die Einhaltung von Deadlines jeweils sicherstellen würdest.

• Harte Echtzeitsysteme:
  • Definition: Bei harten Echtzeitsystemen müssen Deadlines strikt eingehalten werden. Ein Verfehlen einer Deadline kann katastrophale Folgen haben.
  • Beispiele:
    • Flugsteuerungssysteme in der Luftfahrt
    • Pazemaker in der Medizintechnik
    • Bremskontrollsysteme in Fahrzeugen
  • Sicherstellung der Deadlines:
    • Verwendung von Echtzeitbetriebssystemen (RTOS) mit festem Priority Scheduling oder Rate Monotonic Scheduling (RMS).
    • Implementierung von Task Preemption, um sicherzustellen, dass hochpriorisierte Aufgaben sofort ausgeführt werden können.
    • Statische Analyse und Worst-Case Execution Time (WCET) Berechnungen, um die maximale Ausführungszeit jeder Aufgabe genau zu bestimmen.
    • Redundante Systeme, um hohe Zuverlässigkeit sicherzustellen, z.B. durch Hardware- und Software-Redundanz.
• Weiche Echtzeitsysteme:
  • Definition: Bei weichen Echtzeitsystemen ist das Einhalten von Deadlines wünschenswert, aber nicht zwingend erforderlich. Ein Verfehlen einer Deadline führt meist zu einem Performanceverlust, jedoch nicht zu ernsthaften Konsequenzen.
  • Beispiele:
    • Streaming Dienste (z.B. Video- oder Audiostreaming)
    • Online-Gaming-Plattformen
    • Aufnahmesysteme für Fernsehen
  • Sicherstellung der Deadlines:
    • Verwendung von dynamischen Schedulingsystemen wie Earliest Deadline First (EDF), um Aufgaben basierend auf ihren Deadlines dynamisch zu planen.
    • Quality of Service (QoS) Mechanismen, um sicherzustellen, dass wichtige Aufgaben bevorzugt bearbeitet werden.
    • Implementierung von Puffern und Reserven, um Schwankungen in der Last auszugleichen.
    • Verwendung von adaptiver Ressourcenzuweisung, um in Zeiten hoher Belastung Ressourcen dynamisch neu zu verteilen.

Der Hauptunterschied zwischen harten und weichen Echtzeitsystemen liegt also in den Konsequenzen des Verfehlens von Deadlines: Bei harten Echtzeitsystemen müssen Deadlines strikt eingehalten werden, während bei weichen Echtzeitsystemen ein gewisser Spielraum vorhanden ist. Entsprechend unterscheiden sich auch die Techniken zur Einhaltung von Deadlines, um die spezifischen Anforderungen der jeweiligen Systeme zu erfüllen.

d)

Diskutiere die Rolle der Zuverlässigkeit in Echtzeitsystemen, insbesondere in kritischen Bereichen wie der Medizintechnik. Welche Methoden und Techniken würdest Du anwenden, um die Zuverlässigkeit eines Echtzeitsystems zu gewährleisten? Gehe auf mindestens drei verschiedene Ansätze ein.

Lösung:

Diskutiere die Rolle der Zuverlässigkeit in Echtzeitsystemen, insbesondere in kritischen Bereichen wie der Medizintechnik. Welche Methoden und Techniken würdest Du anwenden, um die Zuverlässigkeit eines Echtzeitsystems zu gewährleisten? Gehe auf mindestens drei verschiedene Ansätze ein.Zuverlässigkeit ist ein entscheidender Faktor in Echtzeitsystemen, insbesondere in kritischen Bereichen wie der Medizintechnik, wo ein Versagen des Systems lebensbedrohliche Folgen haben kann. Um die Zuverlässigkeit eines Echtzeitsystems zu gewährleisten, können verschiedene Methoden und Techniken angewendet werden:

• Redundanz:
  • Hardware-Redundanz: Integriere mehrfache, identische Hardware-Komponenten, um sicherzustellen, dass ein Ausfall einer Komponente nicht zum Gesamtausfall des Systems führt. Dies kann durch parallele und vielfältige Systemarchitekturen erreicht werden.
  • Software-Redundanz: Entwickle mehrere Software-Implementationen derselben Funktionalität, die parallel laufen (z.B. Triple Modular Redundancy). Falls eine Software-Instanz fehlschlägt, können die anderen weiterhin korrekt arbeiten.
  • Kommunikations-Redundanz: Nutze redundante Kommunikationswege, um sicherzustellen, dass die Datenübertragung auch bei Ausfall einer Verbindung gewährleistet ist.
• Fehlererkennung und Fehlerbehebung:
  • Watchdog-Timer: Implementiere Watchdog-Timer, die das System überwachen und im Falle eines Fehlers oder eines Stillstands der Software einen Neustart auslösen können.
  • Fehlerkorrekturcodes (ECC): Verwende ECC in Speicher- und Kommunikationssystemen, um Fehler zu erkennen und zu korrigieren. Zum Beispiel kann ein Cyclic Redundancy Check (CRC) verwendet werden, um Fehler in übertragenen Daten zu erkennen.
  • Heartbeat-Monitoring: Implementiere Heartbeat-Mechanismen, die regelmäßige Signale senden, um sicherzustellen, dass alle Teile des Systems ordnungsgemäß funktionieren. Ein fehlender Heartbeat-Signal kann auf einen Fehler hinweisen.
• Formale Verifikation und Tests:
  • Unit-Tests und Integrationstests: Entwickle umfassende Testfälle, die verschiedene Teile des Systems isoliert und kombiniert testen, um sicherzustellen, dass alle Komponenten korrekt zusammenarbeiten.
  • Formale Methoden: Wende formale Verifikationsmethoden an, um mathematisch zu beweisen, dass das System fehlerfrei ist und bestimmte Spezifikationen erfüllt. Dies beinhaltet Model Checking und die Verwendung von formalen Spezifikationssprachen.
  • Fehlertoleranz-Testverfahren: Führe gezielte Fehlertests durch, wie z.B. Failover-Tests und Tests unter extremen Bedingungen, um sicherzustellen, dass das System auch unter fehlerhaften Bedingungen robust bleibt.

Durch die Anwendung dieser Methoden und Techniken kann die Zuverlässigkeit von Echtzeitsystemen in kritischen Bereichen wie der Medizintechnik erheblich verbessert werden. Die Integration von Redundanz, effektiver Fehlererkennung und -behebung sowie rigorosen Verifikations- und Testverfahren hilft, das Risiko von Systemausfällen zu minimieren und die hohe Zuverlässigkeit zu gewährleisten, die für solche Anwendungen erforderlich ist.

Aufgabe 2)

Du betreust ein Echtzeitsystem, welches drei unterschiedliche Aufgaben nach einem festen Zeitplan ausführt. Die Ausführungszeiten und Periodenlängen dieser Aufgaben sind wie folgt spezifiziert:

• Aufgabe 1: Ausführungszeit (C1) = 2 ms, Periodenlänge (T1) = 10 ms
• Aufgabe 2: Ausführungszeit (C2) = 1 ms, Periodenlänge (T2) = 5 ms
• Aufgabe 3: Ausführungszeit (C3) = 2 ms, Periodenlänge (T3) = 15 ms

a)

a) Rate Monotonic Scheduling (RMS) Berechne die CPU-Auslastung für das oben stehende System anhand der RMS-Gleichung. Überprüfe anhand des RMS-Kriteriums, ob das System zufriedenstellend planbar ist. Zeige detailliert deine Rechenschritte.

• Nutze die Gleichung: \[ U = \frac{C_1}{T_1} + \frac{C_2}{T_2} + \frac{C_3}{T_3} \leq 3(2^{1/3} - 1)\]

Lösung:

Berechnung der CPU-Auslastung und Überprüfung der Planbarkeit nach dem Rate Monotonic Scheduling (RMS) Kriterium:

• Gegeben:
  • Aufgabe 1: Ausführungszeit (\textit{C1}) = 2 ms, Periodenlänge (\textit{T1}) = 10 ms
  • Aufgabe 2: Ausführungszeit (\textit{C2}) = 1 ms, Periodenlänge (\textit{T2}) = 5 ms
  • Aufgabe 3: Ausführungszeit (\textit{C3}) = 2 ms, Periodenlänge (\textit{T3}) = 15 ms

Berechnung der CPU-Auslastung:

1. Den RMS-Formel für die CPU-Auslastung ist:

U = \frac{C_1}{T_1} + \frac{C_2}{T_2} + \frac{C_3}{T_3}

2. Einsetzen der gegebenen Werte:

U = \frac{2}{10} + \frac{1}{5} + \frac{2}{15}

3. Berechnung der Brüche:

• \frac{2}{10} = 0.2
• \frac{1}{5} = 0.2
• \frac{2}{15} = \frac{2}{15} = 0.1333 (gerundet)

4. Summierung der Auslastungen:

 U = 0.2 + 0.2 + 0.1333 = 0.5333

Überprüfung der Planbarkeit:

Laut dem RMS-Kriterium muss die Gesamt-CPU-Auslastung kleiner gleich einem bestimmten Schwellenwert sein, damit das System zufriedenstellend planbar ist.

Das RMS-Kriterium:

 U \textless= n(2^{1/n} - 1) 

wobei n die Anzahl der Aufgaben (in diesem Fall n = 3) ist.5. Berechnung des RMS-Kriteriums:

 3(2^{1/3} - 1) 

Zunächst,

 2^{1/3} ≈ 1.2599 

Dann:

 3(1.2599 - 1) = 3(0.2599) = 0.7797 

Ergebnis:

• Die berechnete CPU-Auslastung (U) = 0.5333
• Der Schwellenwert nach RMS-Kriterium = 0.7797

Da 0.5333 ≤ 0.7797, ist das System zufriedenstellend planbar gemäß dem RMS-Kriterium.

Fazit:

• Die CPU-Auslastung beträgt 0.5333 (53.33%).
• Das System ist gemäß dem RMS-Kriterium planbar.

b)

b) Earliest Deadline First (EDF) und Least Laxity First (LLF) Vergleiche EDF und LLF Scheduling für das gleiche System. Erläutere die theoretischen Grundlagen, einschließlich wie die Prioritäten festgelegt werden, und führe eine kurze Analyse durch, um festzustellen, welcher Algorithmus in dieser Situation möglicherweise besser geeignet ist.

• Beispiel zur Deadline-Berechnung: Bestimme die Prioritäten der Aufgaben basierend auf ihren Deadlines und bestimme anschließend, welche Aufgabe zuerst ausgeführt wird.
• Beispiel zur Laxity-Berechnung: Berechne die Laxität jeder Aufgabe, definiert als \(T_i - C_i\), und bestimme anschließend die Prioritäten der Aufgaben basierend auf diesen Laxitäten.

Lösung:

Vergleich von Earliest Deadline First (EDF) und Least Laxity First (LLF) Scheduling:

Theoretische Grundlagen:

• Earliest Deadline First (EDF):
  • Beschreibung: Bei EDF werden die Prioritäten der Aufgaben basierend auf ihren Deadlines gesetzt. Die Aufgabe mit der frühesten Deadline hat die höchste Priorität.
  • Prioritätenfestlegung: Die Deadlines der Aufgaben sind typischerweise die nächsten Periodenlängen. Je kürzer die Zeit zur nächsten Deadline, desto höher die Priorität.
  • Vorteile: EDF ist optimal für unperiodische Systeme und kann eine CPU-Auslastung von bis zu 100% erreichen, solange die gesamte CPU-Auslastung aller Aufgaben <= 1 ist.
  • Beispiel zur Deadline-Berechnung für unser System: Aufgabe 1: Deadline = T1 = 10 msAufgabe 2: Deadline = T2 = 5 msAufgabe 3: Deadline = T3 = 15 ms Reihenfolge nach EDF: Aufgabe 2 (5 ms) → Aufgabe 1 (10 ms) → Aufgabe 3 (15 ms)
• Least Laxity First (LLF):
  • Beschreibung: Bei LLF wird die Laxität jeder Aufgabe berechnet. Genau wie die Deadline bei EDF bestimmt hier die Laxität die Priorität: Je geringer die Laxität, desto höher die Priorität.
  • Prioritätenfestlegung: Die Laxität L_i einer Aufgabe i wird als Differenz zwischen der Zeit zur nächsten Deadline T_i und der verbleibenden Ausführungszeit C_i berechnet: L_i = T_i - C_i.
  • Vorteile: LLF kann ebenfalls zu einer optimalen Planung führen. Allerdings kann es zu Problemen bei der Ausführung kommen, da sich die Laxitäten häufig ändern können, was zu erhöhten Kontextwechseln führt.
  • Beispiel zur Laxity-Berechnung für unser System:
    Aufgabe 1: Laxität = T1 - C1 = 10 ms - 2 ms = 8 msAufgabe 2: Laxität = T2 - C2 = 5 ms - 1 ms = 4 msAufgabe 3: Laxität = T3 - C3 = 15 ms - 2 ms = 13 ms Reihenfolge nach LLF: Aufgabe 2 (4 ms) → Aufgabe 1 (8 ms) → Aufgabe 3 (13 ms)

Analyse und Vergleich:

• EDF: In unserem Beispiel führt EDF dazu, dass Aufgabe 2 zuerst ausgeführt wird, gefolgt von Aufgabe 1 und Aufgabe 3.
• LLF: LLF ergibt eine ähnliche Reihenfolge, mit Aufgabe 2 zuerst, gefolgt von Aufgabe 1 und Aufgabe 3, basierend auf den Laxitäten der Aufgaben.
• Praxis: Beide Algorithmen scheinen für unser System gut geeignet zu sein. Allerdings hat EDF den Vorteil, weniger Kontextwechsel zu verursachen, was insbesondere bei Echtzeitsystemen mit festem Zeitplan von Vorteil sein kann. LLF kann dynamischer sein, jedoch kann dies zu mehr Overhead durch häufigere Kontextwechsel führen.

Fazit:

• Für dieses spezifische System wäre EDF wahrscheinlich die bessere Wahl, da es zu einer stabileren und effizienteren Planung führen kann.
• LLF könnte in dynamischeren Umgebungen von Vorteil sein, jedoch könnte der zusätzliche Overhead in diesem Szenario problematisch sein.

Aufgabe 3)

Ein Unternehmen plant, ein Echtzeitbetriebssystem (RTOS) für ein neues Raumfahrzeug zu entwickeln. Dies erfordert die Einhaltung strikter zeitlicher Vorgaben und die Gewährleistung hoher Zuverlässigkeit und Sicherheit. Das RTOS wird kritische Aufgaben koordinieren, wie z.B. die Steuerung der Antriebssysteme, die Verarbeitung von Sensordaten und die Kommunikation mit der Bodenstation.

a)

Welche Scheduling-Algorithmen würden Sie für dieses RTOS empfehlen und warum? Berücksichtigen Sie dabei die spezifischen Anforderungen eines Raumfahrzeugs und erklären Sie den Unterschied zwischen EDF (Earliest Deadline First) und RM (Rate Monotonic Scheduling).

Lösung:

Empfohlene Scheduling-Algorithmen für das RTOS

Angesichts der strikten zeitlichen Vorgaben und der Notwendigkeit hoher Zuverlässigkeit und Sicherheit im Raumfahrzeug, empfehle ich die Verwendung der folgenden Scheduling-Algorithmen:

• Earliest Deadline First (EDF)
• Rate Monotonic Scheduling (RMS)

Warum gerade diese Algorithmen?

• EDF (Earliest Deadline First):Dieser Algorithmus weist den Aufgaben Prioritäten basierend auf ihrer Deadline zu. Die Aufgabe mit der frühesten Deadline wird als nächstes ausgeführt. Vorteile von EDF sind:
• Optimal bei einstufiger Zeitplanung: EDF ist optimal für vorhersagbare Lasten und garantiert die Erfüllung aller Deadlines, sofern die Systemauslastung unter 100 % liegt.
• Anpassungsfähigkeit: EDF kann effektiv auf dynamische Änderungen reagieren, da es kontinuierlich neu plant, basierend auf den kommenden Deadlines.
• RM (Rate Monotonic Scheduling):Dieser Algorithmus ordnet Aufgaben Prioritäten basierend auf ihrer Ausführungsfrequenz zu. Die Aufgabe mit der höchsten Frequenz erhält die höchste Priorität. Vorteile von RMS sind:
• Statische Prioritäten: RMS ist einfach zu implementieren und vorhersehbar, da sich die Prioritäten nicht ändern.
• Effektivität bei Periodizität: RMS ist besonders gut geeignet für Systeme mit periodischen Aufgaben, wie sie häufig in Raumfahrzeugen vorkommen.

Unterschiede zwischen EDF und RM:

• Priorisierung:EDF priorisiert Aufgaben nach ihren Deadlines, während RM Aufgaben nach ihrer Rate oder Frequenz priorisiert.
• Flexibilität:EDF ist dynamisch und ändert die Prioritäten basierend auf Echtzeitbedingungen. RM hingegen verwendet statische Prioritäten und eignet sich daher besser für feste, periodische Aufgaben.
• Effizienz:EDF kann theoretisch bis zu einer Systemauslastung von 100 % effizient sein, während RM normalerweise nur bis etwa 69 % Systemauslastung garantiert ist.

Zusammenfassend kann gesagt werden, dass EDF besonders flexibel und optimal für dynamische Umgebungen ist, während RM durch seine Einfachheit und Vorhersagbarkeit besticht und besonders für periodische Aufgaben in Raumfahrzeugsystemen geeignet ist.

b)

Beschreiben Sie die Vorteile und Nachteile der statischen vs. dynamischen Speicherpartitionierung in Echtzeitbetriebssystemen. Welches Modell bevorzugen Sie für das Raumfahrzeug-RTOS und warum?

Lösung:

Statische vs. Dynamische Speicherpartitionierung in Echtzeitbetriebssystemen

Im Kontext eines Echtzeitbetriebssystems (RTOS) für Raumfahrzeuge ist die Speicherverwaltung ein kritischer Aspekt. Hier sind die Vor- und Nachteile beider Verfahren:

• Statische Speicherpartitionierung:

Vorteile:

• Vorhersagbarkeit: Da die Speicherzuteilung im Voraus festgelegt wird, sind die Speicheranforderungen und -limits für jede Aufgabe bekannt und können leicht verwaltet werden.
• Determinismus: Es gibt keine Laufzeitüberraschungen bezüglich der Speicherzuteilung, was eine konsistente Systemverhaltensweise gewährleistet.
• Einfacher Overhead: Weniger Laufzeit-Overhead, da die Speicherzuteilung nicht dynamisch verwaltet werden muss.

Nachteile:

• Unflexibilität: Änderungen oder Anpassungen während der Laufzeit sind schwierig, da Speicherbereiche bereits fest zugewiesen sind.
• Fragmentierung: Mögliche externe Fragmentierung, wenn der Speicher nicht effizient genutzt wird.
• Ressourcenverschwendung: Falls Anwendungen weniger Speicher als vorgesehen nutzen, bleiben die restlichen Ressourcen ungenutzt.

• Dynamische Speicherpartitionierung:

Vorteile:

• Flexibilität: Speicher kann je nach Bedarf zur Laufzeit zugewiesen werden, was eine effizientere Ressourcennutzung ermöglicht.
• Effizienz: Da Speicher dynamisch verwaltet wird, kann das System besser auf variable Anforderungen reagieren.
• Reduzierte Fragmentierung: Durch dynamisches Re-Allocieren kann die Fragmentierung reduziert werden.

Nachteile:

• Overhead: Die Verwaltung des Speichers zur Laufzeit kann zusätzlichen Overhead und Komplexität einführen.
• Unvorhersehbarkeit: Der Speicherbedarf kann zu Laufzeitanomalien führen, wobei plötzliche Speicherzuteilungen das Systemverhalten beeinflussen können.
• Potenzielle Instabilität: Dynamische Alokationen können dazu führen, dass die Speicherkapazität erschöpft wird, was bei kritischen Systemen problematisch ist.

Bevorzugtes Modell für das Raumfahrzeug-RTOS:

Für das RTOS eines Raumfahrzeugs ist statische Speicherpartitionierung zu bevorzugen. Die Gründe hierfür sind:

• Determinismus: In einem sicherheitskritischen Echtzeitsystem wie einem Raumfahrzeug müssen die Speicheranforderungen und -verhalten streng vorhersagbar und deterministisch sein.
• Zuverlässigkeit: Da die Zuverlässigkeit primär ist, minimiert die statische Speicherzuteilung die Risiken von Laufzeitfehlern und Speichererschöpfungen.
• Kontrolle: Es bietet mehr Kontrolle über die Ressourcenverteilung und deren Nutzung, was wichtig für die Planung und Validierung des Systems ist.

Zusammenfassend bietet die statische Speicherpartitionierung für ein Raumfahrzeug-RTOS mehr Sicherheit und Vorhersagbarkeit, was für die strikten zeitlichen Vorgaben und hohen Zuverlässigkeitsanforderungen eines solchen Systems entscheidend ist.

c)

Angenommen, das System verwendet eine Nachrichtenqueue für die Interprozesskommunikation. Erklären Sie, wie eine festgelegte Prioritätensortierung innerhalb der Queue sicherstellt, dass alle Nachrichten rechtzeitig verarbeitet werden. Berechnen Sie dabei die maximale Wartezeit für eine Nachricht, die als letzte in eine Queue mit n Nachrichten eingefügt wird, wobei jede Nachricht maximal T Zeit kostet.

Lösung:

Nachrichtenqueue mit Prioritätensortierung

In einem Echtzeitbetriebssystem (RTOS) wie dem für ein Raumfahrzeug ist die Interprozesskommunikation (IPC) entscheidend. Eine Möglichkeit zur Kommunikation zwischen Prozessen ist die Verwendung von Nachrichtenqueues. Um sicherzustellen, dass alle Nachrichten rechtzeitig verarbeitet werden, kann eine festgelegte Prioritätensortierung innerhalb der Queue implementiert werden.

Funktionsweise der Prioritätensortierung

Bei der Prioritätensortierung haben Nachrichten unterschiedliche Prioritäten, die bestimmen, in welcher Reihenfolge sie verarbeitet werden. Nachrichten mit höherer Priorität werden vor denen mit niedrigerer Priorität bearbeitet. Dies gewährleistet, dass kritische Nachrichten bevorzugt behandelt werden und rechtzeitig verarbeitet werden.

• Einfügen der Nachrichten: Jede Nachricht wird basierend auf ihrer Priorität in die Queue eingefügt. Nachrichten mit höherer Priorität werden weiter vorne in der Queue platziert.
• Verarbeitung der Nachrichten: Nachrichten werden in der Reihenfolge ihrer Priorität verarbeitet. Nachrichten mit der höchsten Priorität werden zuerst entnommen und bearbeitet.

Maximale Wartezeit Berechnung

Um die maximale Wartezeit für eine Nachricht zu berechnen, die als letzte in eine Queue mit n Nachrichten eingefügt wird, wobei jede Nachricht maximal T Zeit kostet, gehen wir davon aus, dass die zuletzt eingefügte Nachricht die niedrigste Priorität hat. Dies bedeutet, dass alle n Nachrichten vor ihr verarbeitet werden müssen, bevor sie an die Reihe kommt.

Berechnungsschritte:

• Anzahl der Nachrichten vor der neuen Nachricht: n
• Verarbeitungszeit jeder Nachricht: T

Maximale Wartezeit für die neue Nachricht:

• Die neue Nachricht muss warten, bis alle n Nachrichten vor ihr verarbeitet sind:
• Formel: \[ \text{Maximale Wartezeit} = n \times T \]

Beispiel:

• Anzahl der Nachrichten in der Queue: n = 5
• Verarbeitungszeit jeder Nachricht: T = 10 ms
• Maximale Wartezeit für die neue Nachricht:
• \[ \text{Maximale Wartezeit} = 5 \times 10 \text{ ms} = 50 \text{ ms} \]

Zusammenfassend stellt eine festgelegte Prioritätensortierung in der Nachrichtenqueue sicher, dass alle Nachrichten rechtzeitig verarbeitet werden, indem wichtigere Nachrichten bevorzugt behandelt werden. Die maximale Wartezeit für eine neue Nachricht, die ans Ende der Queue mit n Nachrichten eingefügt wird (jede mit einer Verarbeitungszeit von T), beträgt n \times T.

Aufgabe 4)

In einem Echtzeitbetriebssystem (RTOS) werden verschiedene Mechanismen zur Interprozesskommunikation und Synchronisation verwendet, um sicherzustellen, dass die Prozesse Daten effektiv austauschen und ihre Ausführung koordinieren können. Zu diesen Mechanismen gehören Mailboxen, Queues, Semaphore, Mutexe und Event Flags. Ein häufiges Problem in RTOS ist die Prioritätsinversion, bei der ein hoch priorisierter Task warten muss, weil ein niedrig priorisierter Task eine Ressource hält. Um dieses Problem zu lösen, kann das Priority Inheritance Protocol (PIP) verwendet werden. Für das Scheduling von Tasks bieten sich Algorithmen wie Rate Monotonic Scheduling und EDF (Earliest Deadline First) an.

a)

Teilaufgabe 1: Erkläre die Funktionsweise von Mailboxen und Queues in einem Echtzeitbetriebssystem. Welche Unterschiede bestehen zwischen diesen beiden Mechanismen und in welchen Szenarien wäre jeweils ein Mechanismus dem anderen vorzuziehen?

Lösung:

Teilaufgabe 1: Erkläre die Funktionsweise von Mailboxen und Queues in einem Echtzeitbetriebssystem. Welche Unterschiede bestehen zwischen diesen beiden Mechanismen und in welchen Szenarien wäre jeweils ein Mechanismus dem anderen vorzuziehen?

• Funktionsweise von Mailboxen: Eine Mailbox ist ein Mechanismus zur Interprozesskommunikation, bei dem Nachrichten zwischen Tasks ausgetauscht werden können. Jede Nachricht in einer Mailbox ist ein einzelnes Datenpaket fester Länge. Der Sender-Task schreibt eine Nachricht in die Mailbox, und der Empfänger-Task liest die Nachricht aus der Mailbox. Mailboxen sind besonders nützlich, wenn es darum geht, kleine Datenmengen oder Signale zwischen Tasks zu übertragen. Ein Task kann auf das Eintreffen einer Nachricht in einer Mailbox warten.

• Funktionsweise von Queues: Ein Queue ist ein Mechanismus, bei dem eine Liste von Datenpaketen (Nachrichten) in einer bestimmten Reihenfolge (normalerweise FIFO - First In, First Out) angeordnet ist. Tasks können Nachrichten an die Queue anhängen (enqueue) und sie von der Queue entnehmen (dequeue). Queues sind flexibler als Mailboxen, weil sie mehr als eine Nachricht zur gleichen Zeit aufnehmen können. Sie werden verwendet, wenn mehrere Nachrichten anstehen und in einer bestimmten Reihenfolge bearbeitet werden müssen.

• Unterschiede zwischen Mailboxen und Queues:
  • Anzahl der Nachrichten: Mailboxen können in der Regel nur eine Nachricht zur Zeit speichern, während Queues mehrere Nachrichten speichern können.
  • Länge der Datenpakete: Mailboxen haben eine feste Nachrichtenlänge, während Queues Nachrichten unterschiedlicher Längen handhaben können.
  • Nutzungszweck: Mailboxen sind für das Senden und Empfangen von einfachen Signalen oder kleinen Datenmengen geeignet, während Queues ideal für das Handling von größeren Datenmengen und das Verwalten einer Warteschlange von Nachrichten sind.
  • Synchronisation: Beide Mechanismen können zur Synchronisation verwendet werden, aber in unterschiedlicher Weise. Mit Mailboxen synchronisiert sich ein Task, indem er auf eine Nachricht wartet, während bei Queues ein Task auf Daten in der Queue wartet oder darauf, dass er in die Queue schreiben kann.

• Szenarien, in denen Mailboxen vorzuziehen sind: Mailboxen eignen sich für Echtzeitsysteme, in denen einfache und schnelle Signalisierungen zwischen Tasks erforderlich sind. Sie sind ideal, wenn die Übertragungsbandbreite klein ist und wenn nur eine Nachricht auf einmal gehandhabt werden muss.
• Szenarien, in denen Queues vorzuziehen sind: Queues sind vorzuziehen, wenn mehrere Nachrichten gespeichert und in einer bestimmten Reihenfolge verarbeitet werden müssen. Sie sind nützlich in Systemen, die eine höhere Datenbandbreite erfordern und bei denen Nachrichten unterschiedlichen Typs und unterschiedlicher Größe verarbeitet werden.

b)

Teilaufgabe 2: Beschreibe detailliert, wie Semaphore und Mutexe dazu verwendet werden können, den gleichzeitigen Zugriff auf gemeinsame Ressourcen in einem Echtzeitbetriebssystem zu steuern. Gib konkrete Beispiele und Szenarien an, in denen sie ihre jeweilige Stärke ausspielen.

Lösung:

Teilaufgabe 2: Beschreibe detailliert, wie Semaphore und Mutexe dazu verwendet werden können, den gleichzeitigen Zugriff auf gemeinsame Ressourcen in einem Echtzeitbetriebssystem zu steuern. Gib konkrete Beispiele und Szenarien an, in denen sie ihre jeweilige Stärke ausspielen.

• Funktionsweise von Semaphore: Ein Semaphor ist eine Zählvariable, die dazu verwendet wird, den Zugriff auf eine begrenzte Anzahl von Ressourcen zu steuern. Es gibt zwei grundlegende Operationen, die auf einem Semaphor durchgeführt werden können: wait (P-Operation) und signal (V-Operation). Wenn ein Task auf eine Ressource zugreifen möchte, führt er eine wait-Operation durch, die den Zähler des Semaphors dekrementiert. Wenn der Zählerwert größer als null ist, kann der Task die Ressource betreten. Ist der Zähler jedoch null, muss der Task warten. Wenn der Task die Ressource nicht mehr benötigt, führt er eine signal-Operation durch, die den Zähler inkrementiert und möglicherweise einen wartenden Task aufweckt.
• Beispiel: Angenommen, es gibt eine Druckerressource, die von mehreren Tasks benutzt werden soll. Ein Semaphor mit einem Zähler von 1 kann verwendet werden, um sicherzustellen, dass immer nur ein Task zur gleichen Zeit auf den Drucker zugreifen kann.
• Szenario: Semaphore eignen sich besonders, um gar nicht oder schwer teilbare Ressourcen zu steuern, wie z.B. Drucker, Datenbanken oder Netzwerkverbindungen. Hierbei sorgen sie dafür, dass Zugriffe strukturiert und kontrolliert stattfinden.
• Funktionsweise von Mutexe: Ein Mutex (Mutual Exclusion) ist ein spezieller Typ von Semaphor, der den Zugriff auf eine kritische Sektion steuert, aber nur für einen Task zur gleichen Zeit. Ein Task, der einen Mutex besitzt, ist der einzige, der auf die kritische Sektion zugreifen kann. Andere Tasks müssen warten, bis der Mutex freigegeben wird.
• Beispiel: Betrachten wir ein Szenario, in dem mehrere Tasks auf eine gemeinsam genutzte Datenstruktur (z.B. eine gemeinsame Liste) zugreifen müssen. Ein Mutex kann verwendet werden, um sicherzustellen, dass immer nur ein Task gleichzeitig die Liste modifiziert.
• Szenario: Mutexe sind ideal für die Synchronisation von Small-Encoding-Critical-Sections wie das Updaten von gemeinsam genutzten Datenstrukturen, das Schreiben auf eine gemeinsame Datei oder Zugang zu gemeinsamen Speicherbereichen. Das Prioritätsvererbung-Protokoll kann zusätzlich verwendet werden, um Prioritätsinversion zu verhindern.
• Spezifische Szenarien für die Verwendung:
  • Semaphore: – Mehrere Tasks greifen auf eine Pool von Ressourcen wie Thread-Pools oder Verbindungspools zu. – Steuerung der Zugriffe auf Rate-limited Ressourcen, z.B. maximal 10 gleichzeitige Zugriffe auf einen bestimmten Server.
  • Mutexe: – Schutz einer einzigen geteilten Ressource wie ein Array, Variable oder Datenstruktur, die von mehreren Tasks gleichzeitig modifiziert werden könnte. – Extrem zeitkritische Bereiche, in denen Deadlock-Vermeidung durch Prioritätsvererbung notwendig ist.

c)

Teilaufgabe 3: Angenommen, in einem System tritt eine Prioritätsinversion auf. Erläutere, wie das Priority Inheritance Protocol (PIP) hilft, das Problem der Prioritätsinversion zu mindern, und illustriere dies anhand eines Beispiels.

Lösung:

Teilaufgabe 3: Angenommen, in einem System tritt eine Prioritätsinversion auf. Erläutere, wie das Priority Inheritance Protocol (PIP) hilft, das Problem der Prioritätsinversion zu mindern, und illustriere dies anhand eines Beispiels.

• Prioritätsinversion: Bei der Prioritätsinversion handelt es sich um eine Situation, in der ein hoch priorisierter Task (Task H) warten muss, weil ein niedrig priorisierter Task (Task L) eine von beiden benötigte Ressource hält. Dies kann dazu führen, dass sogar ein mittelpriorisierter Task (Task M), der keine Ressource benötigt, sowohl Task H als auch Task L blockiert, da er Task L überholt und Task H weiterhin auf die Ressource warten muss.
• Funktionsweise des Priority Inheritance Protocol (PIP): Das Priority Inheritance Protocol zielt darauf ab, das Problem der Prioritätsinversion zu lösen, indem es den niedrig priorisierten Task (Task L) temporär mit der Priorität des wartenden hoch priorisierten Tasks (Task H) ausstattet. Sobald Task L die Ressource freigibt, kehrt er zu seiner ursprünglichen Priorität zurück, und Task H kann die Ressource übernehmen und seine Arbeit fortsetzen. Dies verhindert, dass Task M (der mittlere Task) Task L überholt und Task H unnötig blockiert wird.
• Beispiel:
  1. Angenommen, es gibt drei Tasks in einem System:
     • Task L (niedrige Priorität)
     • Task M (mittlere Priorität)
     • Task H (hohe Priorität)
  2. Task L hält derzeit eine Ressource, die auch Task H benötigt, um weiterarbeiten zu können.
  3. Zwischenzeitlich beginnt Task H zu laufen und benötigt die Ressource, die von Task L gehalten wird. Da aber Task L die Ressource hält, muss Task H warten.
  4. Während Task H wartet, wird Task M aktiv und übernimmt die CPU-Zeit, da Task M eine höhere Priorität als Task L besitzt.
  5. Ohne PIP: Task H muss warten, bis Task M und schließlich Task L ihre Arbeit beenden und die Ressource freigeben.
  6. Mit PIP: Sobald Task H die Ressource benötigt und blockiert ist, übernimmt Task L die Priorität von Task H. Task M kann somit Task L nicht mehr überholen.
  7. Task L arbeitet nun mit der Priorität von Task H weiter, bis er die Ressource freigibt.
  8. Sobald die Ressource freigegeben wird, kehrt Task L zu seiner ursprünglichen Priorität zurück und Task H kann die Ressource übernehmen.
• Vorteile von PIP:
  • Reduziert die Wartezeit für hoch priorisierte Tasks.
  • Verhindert, dass mittelpriorisierte Tasks die niedrig priorisierten Tasks überholen, die kritische Ressourcen halten.
  • Erhöht die Reaktionsfähigkeit und Effizienz des Systems, insbesondere in Echtzeitanwendungen.

d)

Teilaufgabe 4: Vergleiche die Scheduling-Algorithmen Rate Monotonic Scheduling (RMS) und Earliest Deadline First (EDF). Stelle die mathematischen Grundlagen dieser Algorithmen dar und diskutiere ihre Vor- und Nachteile. Berechne für folgendes Beispiel, bei dem drei Tasks mit den Perioden 5, 10 und 20 Millisekunden und jeweils einer Ausführungszeit von 1 Millisekunde existieren, ob RMS und EDF zu einer rechtzeitigen Ausführung der Tasks führen.

Lösung:

Teilaufgabe 4: Vergleiche die Scheduling-Algorithmen Rate Monotonic Scheduling (RMS) und Earliest Deadline First (EDF). Stelle die mathematischen Grundlagen dieser Algorithmen dar und diskutiere ihre Vor- und Nachteile. Berechne für folgendes Beispiel, bei dem drei Tasks mit den Perioden 5, 10 und 20 Millisekunden und jeweils einer Ausführungszeit von 1 Millisekunde existieren, ob RMS und EDF zu einer rechtzeitigen Ausführung der Tasks führen.

• Rate Monotonic Scheduling (RMS):
  • Mathematische Grundlagen: RMS ist ein statischer Prioritäts-Scheduling-Algorithmus, bei dem die Priorität einer Task durch ihre Periode bestimmt wird. Je kürzer die Periode, desto höher die Priorität. Die Auslastung (Utilisierung) eines Systems mit \( n \) Tasks darf eine bestimmte Schranke nicht überschreiten, die durch die folgende Formel gegeben ist: \[ U_{RMS} \text{= } (\frac{n}{2^\frac{1}{n} - 1}) \] wobei \( n \) die Anzahl der Tasks repräsentiert.
  • Vorteile:
    • Einfach zu implementieren und zu verstehen.
    • Optimal für präemptives Scheduling bei festen Prioritäten.
    • Können garantierte Echtzeitausführungen bieten, wenn die Prozessorlast bestimmte Schranken nicht überschreitet.
  • Nachteile:
    • Geringere Prozessorlast verglichen mit EDF.
    • Nicht optimal für dynamische Prioritäten oder variable Perioden.
• Earliest Deadline First (EDF):
  • Mathematische Grundlagen: EDF ist ein dynamisches Prioritäts-Scheduling, bei dem Aufgaben nach ihrem nächsten Fälligkeitstermin priorisiert werden. Tasks mit der frühesten Deadline erhalten die höchste Priorität. EDF kann bis zu 100% der Prozessorkapazität ausnutzen, solange die Summe der Task-Utilisierungen nicht über 1 liegt: \[ U_{EDF} \text{= } \frac{C1}{T1} + \frac{C2}{T2} + \frac{C3}{T3} + \text{...} + \frac{Cn}{Tn} \text{≤ 1} \] wobei \( C \) die Ausführungszeit und \( T \) die Periode repräsentiert.
  • Vorteile:
    • Optimal für dynamische Prioritäten und variable Perioden.
    • Maximale Prozessorlast: Kann bis zu 100% der Prozessorressourcen ausnutzen ohne Verfehlung der Deadlines.
  • Nachteile:
    • Komplexer in der Implementierung.
    • Overhead höher als bei RMS, da Prioritäten dynamisch berechnet werden müssen.
• Beispielrechnung: Gegebene Tasks:
  • Task T1: Periode = 5 ms, Ausführungszeit = 1 ms
  • Task T2: Periode = 10 ms, Ausführungszeit = 1 ms
  • Task T3: Periode = 20 ms, Ausführungszeit = 1 ms
  RMS-Berechnung:
  • Priorität wird durch die Periode bestimmt:
    • T1 (höchste Priorität)
    • T2
    • T3 (niedrigste Priorität)
  • Prüfe Utilisierung: \[ U_{RMS} = \frac{C1}{T1} + \frac{C2}{T2} + \frac{C3}{T3} \] \[ U_{RMS} = \frac{1}{5} + \frac{1}{10} + \frac{1}{20} = 0.2 + 0.1 + 0.05 = 0.35 \] Die Schranke für drei Tasks bei RMS lautet: \[ U_{RMS} \text{max} = n \times (2^\frac{1}{n} - 1) \] \[ U_{RMS} \text{max} = 3 \times (2^\frac{1}{3} - 1) \text{≈ 0.779} \] Da 0.35 < 0.779, kann RMS alle Tasks fehlerfrei planen.
EDF-Berechnung:
• Prüfe Utilisation: \[ U_{EDF} = \frac{C1}{T1} + \frac{C2}{T2} + \frac{C3}{T3} \] \[ U_{EDF} = \frac{1}{5} + \frac{1}{10} + \frac{1}{20} = 0.35 \] Da die Nutzung ≤ 100% ist, kann EDF alle Deadlines einhalten, weil 0.35 < 1.0.
• Fazit: Beide Algorithmen, RMS und EDF, werden zu einer rechtzeitigen Ausführung der Tasks in dem gegebenen Beispiel führen.
  • RMS sorgt durch statische Prioritäten für einen übersichtlichen Ablauf.
  • EDF kann flexibler auf dynamische Änderungen und unterschiedliche Deadlines reagieren, nutzt jedoch mehr Rechenressourcen durch die ständige Neuberechnung der Prioritäten.