Echtzeitsysteme 2 - Verlässliche Echtzeitsysteme - Exam

Aufgabe 1)

Definition und Merkmale von EchtzeitsystemenEchtzeitsysteme sind Computersysteme, die innerhalb einer definierten Zeitspanne reagieren müssen. Dies ist kritisch für Anwendungen, bei denen Timing entscheidend ist.

• Determinismus: Vorhersagbares Verhalten und feste Antwortzeiten
• Schnelle Reaktionszeit: Häufig sehr kurze Antwortzeiten im Millisekunden- oder Mikrosekundenbereich
• Zuverlässigkeit: Hohe Verfügbarkeit und Fehlertoleranz
• Einhaltung von Deadlines: Strikte Fristeinhaltung, sowohl harte als auch weiche Echtzeitanforderungen
• Ressourcenkontrolle: Effiziente Nutzung und Management von Systemressourcen

a)

Erläutere den Unterschied zwischen harten und weichen Echtzeitanforderungen anhand eines konkreten Beispiels und erkläre, warum die Einhaltung von Deadlines in Echtzeitsystemen so wichtig ist.

Lösung:

Unterschied zwischen harten und weichen Echtzeitanforderungen

Um den Unterschied zwischen harten und weichen Echtzeitanforderungen zu verdeutlichen, betrachten wir zwei konkrete Beispiele:

• Hartes Echtzeitsystem: Ein Airbag-System in einem Auto. Wenn ein Unfall erkannt wird, muss der Airbag innerhalb von Millisekunden ausgelöst werden. Die Zeitspanne für die Reaktion ist strikt festgelegt und jede Verzögerung könnte fatale Folgen haben. Hierbei handelt es sich um eine harte Echtzeitanforderung, da das System exakt und unverzüglich reagieren muss und das Versagen absolut inakzeptabel ist.
• Weiches Echtzeitsystem: Ein Musik-Streaming-Dienst. Wenn ein Benutzer auf 'Play' drückt, sollte die Musik möglichst sofort starten, aber eine minimale Verzögerung wäre tolerierbar und würde keine kritischen Konsequenzen haben. Es ist zwar wichtig, zeitnah zu reagieren, aber die Anforderungen sind weniger strikt als bei einem harten Echtzeitsystem.

Warum ist die Einhaltung von Deadlines in Echtzeitsystemen so wichtig?

Die Einhaltung von Deadlines in Echtzeitsystemen ist aus folgenden Gründen von entscheidender Bedeutung:

• Sicherheit: In sicherheitskritischen Systemen wie dem oben genannten Airbag-System kann das Nichteinhalten von Deadlines zu katastrophalen Folgen führen. Die korrekte und rechtzeitige Ausführung der vorgegebenen Zeitvorgaben ist entscheidend für die Sicherheit der Benutzer.
• Zuverlässigkeit: Systeme wie industrielle Automatisierung oder Medizingeräte müssen konsistent und zuverlässig innerhalb der festgelegten Zeitgrenzen arbeiten, um ihre Aufgaben korrekt zu erfüllen. Jede Abweichung kann zu fehlerhaften Ergebnissen oder Systemausfällen führen.
• Nutzererfahrung: Auch in weniger kritischen Anwendungen wie bei einem Musik-Streaming-Dienst beeinflusst die Einhaltung von Deadlines die Nutzerzufriedenheit. Zu große Verzögerungen können Frustration verursachen und die Benutzererfahrung negativ beeinträchtigen.
• Effizienz: Echtzeitsysteme gewährleisten durch die Einhaltung von Zeitvorgaben eine effiziente Nutzung und Steuerung der Ressourcen. Dies ist besonders wichtig in Systemen mit begrenzten Ressourcen, um sicherzustellen, dass die Systemfunktionalität nicht beeinträchtigt wird.

b)

Angenommen, ein Echtzeitsystem hat eine maximale Reaktionszeit von 10 Millisekunden. Berechne die Wahrscheinlichkeit, dass das System eine Deadline verfehlt, wenn die tatsächliche Reaktionszeit normalverteilt ist mit einem Mittelwert von 8 Millisekunden und einer Standardabweichung von 1 Millisekunde. Nutze die Formel der Normalverteilung.

Lösung:

Berechnung der Wahrscheinlichkeit einer Deadline-Verfehlung in einem Echtzeitsystem

Angenommen, ein Echtzeitsystem hat eine maximale Reaktionszeit von 10 Millisekunden. Die tatsächliche Reaktionszeit ist normalverteilt mit einem Mittelwert von 8 Millisekunden und einer Standardabweichung von 1 Millisekunde.

Wir möchten die Wahrscheinlichkeit berechnen, dass die Reaktionszeit diese 10 Millisekunden überschreitet. Dies entspricht der Berechnung von \(P(X > 10)\), wobei \(X\) die Zufallsvariable für die Reaktionszeit ist.

Schritte zur Lösung:

• Wandle die Zufallsvariable in eine standardisierte Normalverteilung um (Z-Wert).
• Nutze die Normalverteilungstabelle, um die entsprechende Wahrscheinlichkeit zu finden.

Schritt 1: Standardisierung der Normalverteilung

Wir standardisieren die normale Zufallsvariable, indem wir den Z-Wert berechnen. Der Z-Wert kann berechnet werden mit der Formel:

\[ Z = \frac{{X - \mu }}{{\sigma }} \]

Hierbei ist:

• \(X = 10\): Die maximale Reaktionszeit
• \(\mu = 8 \): Der Mittelwert
• \(\sigma = 1 \): Die Standardabweichung

Berechnung des Z-Wertes:

\[ Z = \frac{{10 - 8}}{{1}} = \frac{{2}}{{1}} = 2 \]

Schritt 2: Berechnung der Wahrscheinlichkeit

Nun müssen wir die Fläche unter der Normalverteilungskurve rechts von \(Z=2\) bestimmen.

Die Wahrscheinlichkeit, dass \(Z > 2\) in einer Standard-Normalverteilung auftritt:

\[ P(Z > 2) = 1 - P(Z \leq 2) \]

Aus den Standard-Normalverteilungstabellen wissen wir, dass \(P(Z \leq 2)\) etwa 0.9772 ist.

Also:

\[ P(Z > 2) = 1 - 0.9772 = 0.0228 \]

Schlussfolgerung: Die Wahrscheinlichkeit, dass das System die Deadline von 10 Millisekunden verfehlt, beträgt etwa 2,28%.

c)

Diskutiere die Bedeutung von Determinismus in Echtzeitsystemen und gib Beispiele, wie Nicht-Determinismus schwerwiegende Folgen haben könnte, indem Du diese mit spezifischen Anwendungen verbindest.

Lösung:

Bedeutung von Determinismus in Echtzeitsystemen

Determinismus ist ein zentrales Merkmal von Echtzeitsystemen. Er bedeutet, dass das System auf gegebene Eingaben stets innerhalb vorhersehbarer und festgelegter Zeiten reagiert. Dies ist besonders wichtig, da viele Echtzeitanwendungen auf präzise und rechtzeitige Reaktionen angewiesen sind. Fehlender Determinismus kann in solchen Systemen schwerwiegende Konsequenzen haben.

Bedeutung von Determinismus:

• Vorhersagbarkeit: Dies erlaubt es Ingenieuren und Entwicklern, das Systemverhalten genauestens zu planen und zu simulieren, um sicherzustellen, dass die Anforderungen erfüllt werden.
• Stabilität und Zuverlässigkeit: Systeme mit deterministischem Verhalten sind stabiler und vorhersehbarer, was zu einer höheren Zuverlässigkeit führt.
• Sicherheit: Determinismus minimiert das Risiko unerwarteter Systemausfälle, die zu gefährlichen Situationen führen könnten.

Beispiele für schwerwiegende Folgen von Nicht-Determinismus:

Um die Bedeutung von Determinismus zu verdeutlichen, betrachten wir einige konkrete Beispiele:

• Medizinische Geräte: In einem Echtzeitsystem wie einem Herzschrittmacher oder einem Überwachungsgerät für lebenswichtige Funktionen muss das System ohne Verzögerungen exakt reagieren. Ein nicht-deterministisches Verhalten könnte dazu führen, dass Warnzeichen nicht rechtzeitig erkannt werden, was potenziell lebensgefährlich sein kann.
• Industrieautomation: In einer Fertigungsanlage, die von Robotern betrieben wird, muss jede Aktion innerhalb einer festgelegten Zeitspanne durchgeführt werden, um die Sicherheit der Arbeiter und die Integrität der Produkte zu gewährleisten. Nicht-deterministische Reaktionszeiten könnten zu gefährlichen Maschinenbewegungen oder fehlerhaften Produkten führen.
• Automobilsektor: In Fahrerassistenzsystemen wie dem automatischen Notbremsassistenten muss die Software auf Sensorereignisse (z. B. ein Hindernis auf der Fahrbahn) sofort reagieren. Nicht-Determinismus könnte dazu führen, dass das Fahrzeug nicht rechtzeitig bremst, was zu Unfällen führen kann.
• Luft- und Raumfahrt: Navigations- und Steuerungssysteme in Flugzeugen müssen äußerst präzise arbeiten. Ein nicht-deterministisches Verhalten könnte die Navigation beeinträchtigen und beispielsweise dazu führen, dass ein Flugzeug in turbulente Gebiete fliegt oder die falsche Höhe hält, was für Passagiere und Besatzung gefährlich sein könnte.

Fazit: Der Determinismus ist wesentlich für die Zuverlässigkeit, Sicherheit und Effizienz von Echtzeitsystemen. Ein nicht-deterministisches Verhalten in kritischen Anwendungen kann zu schwerwiegenden und sogar lebensbedrohlichen Konsequenzen führen, weshalb es von höchster Priorität ist, den deterministischen Charakter eines Echtzeitsystems sicherzustellen.

d)

Erkläre, wie Ressourcenkontrolle in Echtzeitsystemen zur Erreichung von Zuverlässigkeit und schneller Reaktionszeit beiträgt. Beschreibe mindestens zwei Techniken oder Algorithmen, die zur Ressourcenkontrolle in Echtzeitsystemen verwendet werden und deren Funktionsweise.

Lösung:

Ressourcenkontrolle in Echtzeitsystemen zur Erreichung von Zuverlässigkeit und schneller Reaktionszeit

Die Ressourcenkontrolle in Echtzeitsystemen ist von entscheidender Bedeutung, um sowohl Zuverlässigkeit als auch schnelle Reaktionszeiten sicherzustellen. Ohne effiziente Kontrolle und Zuweisung der Systemressourcen könnte es zu Verzögerungen, Engpässen oder sogar zu Systemausfällen kommen, was besonders in zeitkritischen Anwendungen inakzeptabel ist.

Bedeutung der Ressourcenkontrolle:

• Effizienz: Durch die effiziente Nutzung und Verwaltung von Systemressourcen wird sichergestellt, dass genügend Ressourcen für die Ausführung zeitkritischer Aufgaben zur Verfügung stehen.
• Zuverlässigkeit: Kontrollmechanismen stellen sicher, dass Systemressourcen konsistent und vorhersehbar zugewiesen werden, wodurch das System zuverlässiger wird.
• Schnelle Reaktionszeit: Durch die Priorisierung und rechtzeitige Zuweisung der Ressourcen können kritische Aufgaben schneller abgearbeitet werden, was kurze Antwortzeiten ermöglicht.

Techniken und Algorithmen zur Ressourcenkontrolle

Es gibt verschiedene Techniken und Algorithmen, die zur Ressourcenkontrolle in Echtzeitsystemen verwendet werden. Hier sind zwei typische Beispiele und deren Funktionsweise:

1. Echtzeitfähige Scheduling-Algorithmen

Echtzeitfähige Scheduling-Algorithmen sind notwendig, um zu gewährleisten, dass die wichtigsten Programme oder Tasks zur richtigen Zeit ausgeführt werden. Ein bekanntes Beispiel ist der Rate Monotonic Scheduling (RMS) Algorithmus:

• Rate Monotonic Scheduling (RMS):

  RMS ist ein präemptiver Prioritäts-Scheduling-Algorithmus, bei dem die Prioritäten der Tasks basierend auf ihren Perioden zugewiesen werden. Tasks mit kürzeren Perioden haben höhere Prioritäten. Der Algorithmus funktioniert wie folgt:

  • Jede Task hat eine feste Ausführungsperiode und benötigt eine feste Ausführungszeit innerhalb dieser Periode.
  • Tasks mit kürzeren Perioden (häufiger wiederkehrend) erhalten höhere Prioritäten.
  • Das System präemptiert Tasks mit niedrigeren Prioritäten zugunsten höher priorisierter Tasks.

  Durch diese Priorisierung stellt RMS sicher, dass kritische, häufig wiederkehrende Tasks bevorzugt ausgeführt werden, was zu schnellen Reaktionszeiten führt.

2. Ressourcenreservierung

Ein anderer Ansatz zur Ressourcenkontrolle ist die Ressourcenreservierung, bei der bestimmten Tasks explizit Ressourcen zugewiesen werden, um deren rechtzeitige Ausführung sicherzustellen:

• Budgeted Resource Allocation:

  Hierbei erhalten Tasks ein Budget an Systemressourcen wie CPU-Zeit oder Speicher. Dieser Ansatz funktioniert wie folgt:

  • Jede Task wird mit einem vorbestimmten Budget an Ressourcen versehen.
  • Das System überwacht die Ressourcennutzung durch jede Task und stellt sicher, dass das Budget nicht überschritten wird.
  • Sollten Aufgaben ihr Budget überschreiten, können sie niedriger priorisiert oder auf später verschoben werden.

  Durch die Zuweisung von festen Budgets wird sichergestellt, dass wichtige Aufgaben ihre benötigten Ressourcen erhalten, was die Systemzuverlässigkeit erhöht und schnelle Reaktionszeiten sicherstellt.

Schlussfolgerung:

Die Ressourcenkontrolle ist essentiell, um in Echtzeitsystemen sowohl Zuverlässigkeit als auch schnelle Reaktionszeiten gewährleisten zu können. Techniken wie Echtzeitfähige Scheduling-Algorithmen (z.B. Rate Monotonic Scheduling) und Ressourcenreservierung (z.B. Budgeted Resource Allocation) spielen dabei eine wesentliche Rolle, indem sie die effiziente Verwaltung und Zuweisung der Systemressourcen ermöglichen.

Aufgabe 2)

Betrachte die Unterscheidung zwischen Hart- und Weichzeit-Echtzeitsystemen.Hartzeitsysteme müssen alle zeitlichen Bedingungen strikt einhalten, während Weichzeitsysteme diese nicht strikt einhalten müssen.

• Hartzeitsysteme: Versagen führt zu Systemfehlern.
• Weichzeitsysteme: Versagen führt zu Qualitätsminderung, aber nicht zu Systemfehlern.
• Beispiele: Hartzeitsystem - Flugsteuerung; Weichzeitsystem - Multimedia-Anwendung.
• Formale Definition: Eine Echtzeitanforderung gilt als hart wenn ihr Übertreten fatale Konsequenzen hat, andernfalls ist sie weich.

a)

Wie würdest Du ein System beurteilen, das zur Überwachung und Steuerung eines medizinischen Geräts in einem Operationssaal verwendet wird? Erläutere deine Antwort und beziehe Dich dabei auf die konkrete Einhaltung der zeitlichen Bedingungen, wie sie oben beschrieben und formal definiert sind. Berücksichtige mögliche Konsequenzen eines Versagens dieser Bedingungen.

Lösung:

Ein System, das zur Überwachung und Steuerung eines medizinischen Geräts in einem Operationssaal verwendet wird, sollte als Hartzeitsystem betrachtet werden. Hier ist eine detaillierte Erläuterung, warum das so ist:

• Strikte Einhaltung zeitlicher Bedingungen: In einem Operationssaal ist es entscheidend, dass alle sicherheitskritischen Systeme strikt innerhalb der festgelegten Zeitrahmen arbeiten. Beispielsweise müssen Vitalparameter wie Herzschlag und Atmung in Echtzeit überwacht und kontrolliert werden. Jede Verzögerung kann lebensbedrohliche Folgen haben.
• Konsequenzen eines Versagens: Das Nichterfüllen dieser Echtzeitanforderungen kann zu schwerwiegenden Systemfehlern führen, einschließlich dem Versagen des medizinischen Geräts und möglicherweise dem Verlust von Menschenleben. Dies entspricht der Definition eines Hartzeitsystems, bei dem das Versagen der zeitlichen Bedingungen fatale Konsequenzen hat.
• Beispiel: Ein Beatmungsgerät, das die Atmung eines Patienten unterstützt, muss sofort reagieren, wenn ein bestimmter Sauerstoffgehalt erreicht wird. Versagen dabei hätte katastrophale Auswirkungen und stellt somit sicher, dass es innerhalb der Kategorie der Hartzeitsysteme liegt.

Zusammenfassend lässt sich sagen, dass aufgrund der kritischen Natur der Aufgabe und der möglichen fatalen Konsequenzen eines Versagens die Überwachung und Steuerung eines medizinischen Geräts in einem Operationssaal in die Kategorie der Hartzeitsysteme gehört.

b)

Angenommen, Du planst die Implementierung einer Multimedia-Anwendung und möchtest sicherstellen, dass sie so nahe wie möglich einem Hartzeitsystem entspricht, dabei aber immer noch als Weichzeitsystem eingestuft werden kann. Beschreibe mögliche Strategieansätze, um zeitliche Bedingungen zu verbessern und gleichzeitig sicherzustellen, dass ein gelegentliches Verfehlen dieser Bedingungen nur zu Qualitätseinbußen und nicht zu Funktionsausfällen führt. Verwende mathematische Formeln oder Algorithmen, wenn erforderlich, um deine Erklärungen präziser und nachvollziehbarer zu machen.

Lösung:

Um sicherzustellen, dass eine Multimedia-Anwendung so nahe wie möglich einem Hartzeitsystem entspricht, dabei aber dennoch als Weichzeitsystem eingestuft werden kann, sollten verschiedene Strategieansätze in Betracht gezogen werden:

• Latenz-Management: Eine entscheidende Strategie ist das Management von Latenzzeiten. Dies kann durch die Verwendung effizienter Algorithmen und Datenstrukturen sowie durch die Implementierung von Pufferspeichern (Buffer) erreicht werden, um kleine Einbrüche in der Datenübertragung auszugleichen. Der optimale Pufferzeitraum \(\tau\) kann berechnet werden als:

\[ \tau = \frac{d_n - d_o}{2} \]

Hierbei gilt:

• \(\tau\) - Pufferzeit
• \(d_n\) - tatsächlich gemessene Übermittlungsdauer
• \(d_o\) - erwartete Übermittlungsdauer

\[ \tau_{\text{avg}} = \frac{\sum_{i=1}^{n} \tau_i}{n} \]

Dies ermöglicht es, die durchschnittliche Pufferzeit \(\tau_{\text{avg}}\) zu berechnen, wodurch die allgemeine Puffer-Performance überwacht werden kann.

\[ w(i) = \frac{1}{\text{Latenzzeit pro Aufgabe}} \]

Durch diese Priorisierung erhalten Aufgaben mit kürzerer Latenzzeit eine höhere Priorität.

\[ \text{Gesamtdatensicherung durch zusätzliche Paritätsbits in FEC-Codes} \]

\[ \text{Adaptive Bitrate (ABR)} : \left\{  \begin{array}{ll}  \tau_{\text{avg}} < \tau_{\text{baseline}} &\rightarrow \text{Threshold = 0.8} \  \tau_{\text{avg}} > \tau_{\text{baseline}} &\rightarrow \text{Threshold = 0.85}  \end{array} \right. \]

Durch diese adaptiven Algorithmen kann die Videoqualität dynamisch angepasst werden, um die Nutzererfahrung zu verbessern, ohne die Funktionalität der Anwendung abrupt zu beeinträchtigen.

Durch diese Strategieansätze kann die Multimedia-Anwendung genauere zeitliche Bedingungen einhalten und gleichzeitig sicherstellen, dass gelegentliche Verfehlungen nur zu Qualitätseinbußen und nicht zu Funktionsausfällen führen.

Aufgabe 3)

Planung von Aufgaben in Echtzeitsystemen: Angesichts einer Menge von Aufgaben, die in einem Echtzeitsystem zu planen sind, sollen alle Echtzeitanforderungen erfüllt werden. Betrachte die folgenden Aspekte:

• Unterscheidung von harten, weichen und festen Echtzeitsystemen
• Wichtigste Scheduling-Algorithmen: Rate Monotonic (RM), Earliest Deadline First (EDF)
• Feasibility-Tests zur Sicherstellung, dass alle Aufgaben ihre Fristen einhalten
• Nutzung von Prioritäten für das Scheduling
• Rückrechnung von Überlastungen zur Überprüfung der Systemauslastung
• Berücksichtigung von Präemptions- und Kontextwechselkosten

a)

Unterscheidung von Echtzeitsystemen: Definiere harte, weiche und feste Echtzeitsysteme. Erläutere anhand eines Beispiels für jede Kategorie, welches die Schlüsselkriterien zur Einordnung des Systems geben.

Lösung:

Unterscheidung von Echtzeitsystemen:

• Harte Echtzeitsysteme: Diese Systeme müssen strikt innerhalb ihrer vorgegebenen Fristen arbeiten. Ein Fehlverhalten kann zu katastrophalen Konsequenzen führen. Beispiel: Ein autonomes Fahrzeug, das eine Fußgängererkennung implementiert. Wenn das System nicht rechtzeitig reagiert, kann es zu Unfällen kommen. Der Schlüssel hier ist die absolute Einhaltung der Friste.
• Weiche Echtzeitsysteme: Bei diesen Systemen ist die Einhaltung der Fristen wünschenswert, aber nicht zwingend erforderlich. Ein Überschreiten der Fristen führt zu einem Qualitätsverlust, ist aber nicht katastrophal. Beispiel: Ein Video-Streaming-Dienst. Falls Frames nicht rechtzeitig angezeigt werden, kann die Videoqualität leiden, aber es führt nicht zu gefährlichen Situationen. Der Schlüssel hier ist die Qualität der Dienstleistung.
• Feste Echtzeitsysteme: Diese Systeme müssen ihre Aufgaben innerhalb eines definierten Zeitrahmen abschließen. Diese Definition ermöglicht jedoch eine gewisse Flexibilität im Gegensatz zu harten Echtzeitsystemen. Beispiel: Ein Produktionsband in einer Fabrik, bei dem jeder Prozessschritt innerhalb einer vorgegebenen Zeitspanne abgeschlossen sein muss. Falls dies nicht gelingt, wird die Effizienz des Systems beeinträchtigt, aber es ist nicht unbedingt kritisch. Der Schlüssel hier ist die zeitliche Konsistenz.

b)

Scheduling-Algorithmen: Eine Reihe von Aufgaben (T1: Periode = 5ms, Bearbeitungszeit = 1ms; T2: Periode = 7ms, Bearbeitungszeit = 1ms; T3: Periode = 20ms, Bearbeitungszeit = 4ms) soll entweder mit dem Rate Monotonic (RM) oder Earliest Deadline First (EDF) Algorithmus geplant werden. Bestimme für beide Algorithmen:

• Die Zuweisung der Prioritäten
• Ein Zeitdiagramm, das den Scheduling für eine Periode von 20ms zeigt
• Beurteile, ob die Aufgaben ihre Fristen einhalten und begründe die Entscheidung

Lösung:

Scheduling-Algorithmen:

• Die Zuweisung der Prioritäten
• Rate Monotonic (RM) Algorithmus:
• Die Prioritäten werden basierend auf den Perioden zugewiesen: Kürzere Perioden haben höhere Prioritäten.
• T1: Periode = 5ms (höchste Priorität)
• T2: Periode = 7ms (mittlere Priorität)
• T3: Periode = 20ms (niedrigste Priorität)
• Earliest Deadline First (EDF) Algorithmus:
• Die Prioritäten werden basierend auf den bevorstehenden Deadlines der Aufgaben zugewiesen. Die Aufgabe mit der frühesten Deadline erhält die höchste Priorität.
• Die Priorität wird während der Ausführung laufend geändert.
• Ein Zeitdiagramm, das den Scheduling für eine Periode von 20ms zeigt
RM Zeitdiagramm (Rate Monotonic):

Zeit (ms) | Aufgabe  ----------------------- 0-1      | T1 1-2      | (idle) 2-3      | (idle) 3-4      | (idle) 4-5      | (idle) 5-6      | T1 6-7      | (idle) 7-8      | T2 8-9      | (idle) 9-10     | (idle) 10-11    | T1 11-12    | (idle) 12-13    | (idle) 13-14    | (idle) 14-15    | (idle) 15-16    | T1 16-17    | T2 17-18    | (idle) 18-19    | T3 19-20    | T3  

Zeit (ms) | Aufgabe  ----------------------- 0-1      | T1 1-2      | (idle) 2-3      | (idle) 3-4      | (idle) 4-5      | (idle) 5-6      | T1 6-7      | (idle) 7-8      | T2 8-9      | T2 9-10     | (idle) 10-11    | T1 11-12    | (idle) 12-13    | (idle) 13-14    | (idle) 14-15    | (idle) 15-16    | T1 16-17    | T2 17-18    | T3 18-19    | T3 19-20    | T3 

• T1: Period = 5ms, Bearbeitungszeit = 1ms: In jedem Zyklus aufgerufen. -> Frist OK
• T2: Period = 7ms, Bearbeitungszeit = 1ms: Nicht in allen Zyklen aufgerufen. -> Frist verpasst
• T3: Period = 20ms, Bearbeitungszeit = 4ms: Bearbeitung innerhalb 20ms Periode. -> Frist OK
• RM Scheme fails because T2 misses its deadline since it's not scheduled in every required cycle.

• T1: Period = 5ms, Bearbeitungszeit = 1ms: In jedem Zyklus aufgerufen. -> Frist OK
• T2: Period = 7ms, Bearbeitungszeit = 1ms: In jedem Zyklus aufgerufen. -> Frist OK
• T3: Period = 20ms, Bearbeitungszeit = 4ms: Bearbeitung innerhalb 20ms Periode. -> Frist OK
• With EDF, all deadlines are met as tasks with closer deadlines are scheduled efficiently.

c)

Feasibility-Tests: Führe für die Aufgaben T1, T2 und T3, von denen in der vorherigen Sub-Exercise die Rede ist, einen Feasibility-Test durch, um zu überprüfen, ob das System mit Rate Monotonic (RM) planbar ist. Verwende dazu die entsprechenden mathematischen Formeln.

• Gib die allgemeine Formel für den Suffizienztest von RM an
• Berechne für den Test den Systemauslastungsfaktor
• Erkläre, wie Deine Ergebnisse die Planbarkeit unterstützen oder widersprechen

Lösung:

Feasibility-Tests: Um zu überprüfen, ob das System mit den Aufgaben T1, T2 und T3 unter Verwendung des Rate Monotonic (RM) Algorithmus planbar ist, führen wir einen Feasibility-Test durch. Hier sind die Schritte:

• Allgemeine Formel für den Suffizienztest von RM: Die generelle Auslastungsformel im RM-Algorithmus lautet: \[U = \sum_{i=1}^{n} \frac{C_i}{T_i} \] Dabei sind:
  • \(C_i\): Bearbeitungszeit der Aufgabe \(i\)
  • \(T_i\): Periode der Aufgabe \(i\)
  Der Suffizienztest für die Planbarkeit lautet: \[U \leq n(2^{\frac{1}{n}} - 1) \] Für drei Aufgaben (\(n=3\)) ergibt das: \[U_{\text{max}} = 3 \left(2^{\frac{1}{3}} - 1\right) \approx 0.779 \]

d)

Berücksichtigung von Präemptions- und Kontextwechselkosten: Angenommen in Deinem Echtzeitsystem entstehen für jede Präemption und jeden Kontextwechsel Kosten von 0,1ms. Analysiere die Auswirkungen dieser Kosten auf das Zuführungsdiagramm, das Du zuvor erstellt hast. Berechne die Gesamtauslastung und erkläre, ob das System unter diesen Bedingungen noch in der Lage ist, alle Aufgaben innerhalb der vorgegebenen Zeitrahmen zu erfüllen.

Lösung:

Berücksichtigung von Präemptions- und Kontextwechselkosten: Angenommen, in unserem Echtzeitsystem entstehen für jede Präemption und jeden Kontextwechsel Kosten von 0,1ms. Wir analysieren nun die Auswirkungen dieser Kosten auf das zuvor erstellte Zuführungsdiagramm und berechnen die Gesamtauslastung des Systems unter diesen neuen Bedingungen.

• Ursprüngliches Zeitdiagramm: RM Zeitdiagramm (Rate Monotonic):

  Zeit (ms) | Aufgabe  ----------------------- 0-1      | T1 1-2      | (idle) 2-3      | (idle) 3-4      | (idle) 4-5      | (idle) 5-6      | T1 6-7      | (idle) 7-8      | T2 8-9      | (idle) 9-10     | (idle) 10-11    | T1 11-12    | (idle) 12-13    | (idle) 13-14    | (idle) 14-15    | (idle) 15-16    | T1 16-17    | T2 17-18    | (idle) 18-19    | T3 19-20    | T3  

  Earliest Deadline First (EDF):

  Zeit (ms) | Aufgabe  ----------------------- 0-1      | T1 1-2      | (idle) 2-3      | (idle) 3-4      | (idle) 4-5      | (idle) 5-6      | T1 6-7      | (idle) 7-8      | T2 8-9      | T2 9-10     | (idle) 10-11    | T1 11-12    | (idle) 12-13    | (idle) 13-14    | (idle) 14-15    | (idle) 15-16    | T1 16-17    | T2 17-18    | T3 18-19    | T3 19-20    | T3  

• Identifikation der Präemptions- und Kontextwechsel:
  • RM Zeitdiagramm:
    • Präemption/Kontextwechsel bei Wechsel von T1 zu idle (0-1 ms: T1, 1-2 ms: idle)
    • Präemption/Kontextwechsel bei Wechsel von idle zu T1 (4-5 ms: idle, 5-6 ms: T1)
    • Präemption/Kontextwechsel bei Wechsel von idle zu T2 (6-7 ms: idle, 7-8 ms: T2)
    • Präemption/Kontextwechsel bei Wechsel von idle zu T1 (10-11 ms: idle, 11-12 ms: T1)
    • Präemption/Kontextwechsel bei Wechsel von idle zu T1 (14-15 ms: idle, 15-16 ms: T1)
    • Präemption/Kontextwechsel bei Wechsel von idle zu T2 (16-17 ms: T2, 17-18 ms: idle)
    • Präemption/Kontextwechsel bei Wechsel von idle zu T3 (18-19 ms: T3, 19-20 ms: T3 → idle)
    Insgesamt: 7 Kontextwechsel
• EDF Zeitdiagramm:
  • Präemption/Kontextwechsel bei Wechsel von T1 zu idle (0-1 ms: T1, 1-2 ms: idle)
  • Präemption/Kontextwechsel bei Wechsel von idle zu T1 (4-5 ms: idle, 5-6 ms: T1)
  • Präemption/Kontextwechsel bei Wechsel von idle zu T2 (6-7 ms: T2, 7-8 ms: T2)
  • Präemption/Kontextwechsel bei Wechsel von idle zu T1 (10-11 ms: idle, 11-12 ms: T1)
  • Präemption/Kontextwechsel bei Wechsel von idle zu T1 (14-15 ms: idle, 15-16 ms: T1)
  • Präemption/Kontextwechsel bei Wechsel von idle zu T2 (16-17 ms: T2, 17-18 ms: T3)
  • Präemption/Kontextwechsel bei Wechsel von idle zu T3 (18-19 ms: T3, 19-20 ms: T3 → idle)
  Insgesamt: 7 Kontextwechsel

Aufgabe 4)

In diesem Szenario soll der Unterschied zwischen deterministischem und probabilistischem Scheduling in Echtzeitsystemen untersucht werden. Gegeben ist ein Echtzeitsystem, das für sicherheitskritische Anwendungen (z.B. in der Luftfahrt) verwendet wird. Ziel ist es, geeignete Scheduling-Strategien zu identifizieren, die sowohl die Zuverlässigkeit als auch die Effizienz des Systems gewährleisten. Betrachte die folgenden Kriterien: feste Zeitpläne, garantiertes Timing-Verhalten, Wahrscheinlichkeitsverteilung für Zeitpläne, und Flexibilität bei Unsicherheiten.

a)

Analysiere die gegebenen Anforderungen und identifiziere die Vorteile und Nachteile von deterministischem Scheduling in diesem Kontext. Welche Algorithmen könnten verwendet werden und warum eignen sie sich besonders für sicherheitskritische Systeme? Diskutiere mindestens zwei mögliche Algorithmen.

Lösung:

Analyse der Anforderungen und Identifikation von Vor- und Nachteilen des deterministischen Schedulings

Deterministisches Scheduling bedeutet, dass die Aufgaben in einem Echtzeitsystem nach einem festen, vorher bestimmten Zeitplan ausgeführt werden. In sicherheitskritischen Anwendungen, wie beispielsweise in der Luftfahrt, haben deterministische Zeitpläne mehrere Vorteile:

• Garantiere Timing-Verhalten: Da der Zeitplan festgelegt ist, kann genau bestimmt werden, wann jede Aufgabe ausgeführt wird. Dies führt zu vorhersehbarem Timing-Verhalten, das in sicherheitskritischen Systemen unerlässlich ist.
• Hohe Zuverlässigkeit: Der feste Zeitplan stellt sicher, dass alle zeitkritischen Aufgaben innerhalb ihrer Deadlines ausgeführt werden, was die Zuverlässigkeit des Systems erhöht.
• Einfachere Validierung und Verifikation: Weil das Timing-Verhalten vorhersehbar ist, ist es leichter, das System zu testen und zu validieren, um sicherzustellen, dass alle Anforderungen erfüllt werden.

Jedoch gibt es auch bestimmte Nachteile:

• Geringe Flexibilität: Deterministische Zeitpläne sind nicht gut für Systeme geeignet, bei denen sich die Aufgaben oder ihre Prioritäten während der Laufzeit ändern können.
• Schwierigere Anpassung an Unsicherheiten: Da der Zeitplan fest ist, kann das System Schwierigkeiten haben, auf unerwartete Ereignisse oder Störungen zu reagieren.

Mögliche Algorithmen für deterministisches Scheduling

Für sicherheitskritische Systeme gibt es verschiedene Algorithmen, die sich besonders eignen:

1. Rate-Monotonic Scheduling (RMS)

Beschreibung: Rate-Monotonic Scheduling ist ein statischer Prioritätsalgorithmus, bei dem Aufgaben mit kürzerer Periode höhere Priorität haben. Jede Aufgabe wird in festen Zeitintervallen ausgeführt.

Vorteile:

• Gut geeignet für Systeme mit festen Intervallen.
• Einfach zu implementieren und zu analysieren.
• Kann garantiert werden, dass alle Aufgaben innerhalb ihrer Deadlines ausgeführt werden, solange die CPU-Auslastung unter einem kritischen Wert bleibt.

Nachteile:

• Weniger flexibel bei variierenden Aufgabenanforderungen bzw. unsicheren Bedingungen.
• Effizienz kann sinken, wenn die Perioden der Aufgaben sehr unterschiedlich sind.

2. Earliest Deadline First (EDF)

Beschreibung: Earliest Deadline First ist ein dynamischer Prioritätsalgorithmus, bei dem die Aufgabe mit der frühesten Deadline die höchste Priorität hat.

Vorteile:

• Optimaler Algorithmus für wissen-schaftliche Lasten, kann bis zu 100% CPU-Auslastung erreichen.
• Flexibler als RMS, da er auf variable Aufgabenanforderungen besser reagieren kann.
• Nützlicher für Systeme mit unterschiedlichen oder unvorhersehbaren Lasten.

Nachteile:

• Schwieriger zu implementieren als RMS.
• Kann unter gewissen Bedingungen zu erhöhter CPU-Auslastung und weniger Vorhersagbarkeit im Vergleich zu statischen Algorithmen führen.

Beide Algorithmen haben ihre eigenen Stärken und Schwächen, aber für sicherheitskritische Systeme können sowohl Rate-Monotonic Scheduling als auch Earliest Deadline First geeignete Wahl sein, abhängig von den spezifischen Anforderungen und Bedingungen des Systems.

b)

Betrachte dasselbe Szenario, aber dieses Mal aus der Perspektive des probabilistischen Schedulings. Welche Vorteile bietet diese Scheduling-Strategie in einem adaptiven Umfeld? Wie würde sich dies auf die Zuverlässigkeit und das Timing-Verhalten des Systems auswirken? Diskutiere den Einsatz von Wahrscheinlichkeitsmodellen und beziehe mathematische Gleichungen zur Bestimmung von Antwortzeiten mit ein.

Lösung:

Analyse der Vorteile von probabilistischem Scheduling in einem adaptiven Umfeld

Beim probabilistischen Scheduling wird nicht davon ausgegangen, dass die Ausführungszeiten und Ankunftszeiten der Aufgaben exakt bekannt sind. Stattdessen werden Wahrscheinlichkeitsverteilungen zur Modellierung dieser Zeiten verwendet. Dies bietet mehrere Vorteile in einem adaptiven Umfeld:

• Flexibilität: Probabilistisches Scheduling kann besser auf Änderungen in der Arbeitslast und unvorhersehbare Ereignisse reagieren, da es nicht auf festen Zeitplänen basiert.
• Erhöhte Ressourcenausnutzung: Da Zeitpläne dynamisch angepasst werden können, kann das System Ressourcen effizienter nutzen.
• Robustheit gegenüber Unsicherheiten: Durch die Verwendung von Wahrscheinlichkeitsmodellen können Unsicherheiten besser berücksichtigt und das System robuster gestaltet werden.

Auswirkungen auf Zuverlässigkeit und Timing-Verhalten

Die Verwendung von probabilistischen Modellen kann eine Reihe von Auswirkungen auf die Zuverlässigkeit und das Timing-Verhalten des Systems haben:

• Zuverlässigkeit: Durch die Modellierung der Unsicherheiten können Wahrscheinlichkeiten dafür berechnet werden, dass Aufgaben ihre Deadlines einhalten. Dies kann die Zuverlässigkeit des Systems unter variablen Bedingungen erhöhen.
• Timing-Verhalten: Obwohl das Timing-Verhalten nicht so vorhersehbar wie bei deterministischem Scheduling ist, können Wahrscheinlichkeitsaussagen über die Antwortzeiten gemacht werden. Dies kann bei der Planung und Anpassung helfen.

Einsatz von Wahrscheinlichkeitsmodellen

Um die Antwortzeiten und Deadlines in einem probabilistischen Scheduling-Modell zu bestimmen, werden Wahrscheinlichkeitsverteilungen verwendet:

Beispiel: Nehmen wir an, die Ausführungszeit einer Aufgabe folgt einer Exponentialverteilung mit der Rate \(\lambda\). Die Verteilung der Antwortzeit kann dann mit entsprechenden mathematischen Modellen berechnet werden.

• Exponentialverteilung: Wenn die Ausführungszeit X einer Aufgabe einer Exponentialverteilung mit Parameter \(\lambda\) folgt, dann ist die Wahrscheinlichkeit, dass die Ausführungszeit kürzer als ein bestimmter Wert x ist, gegeben durch:

• Mittlere Antwortzeit: Falls die Ankunftszeit einer Aufgabe einer Poisson-Verteilung folgt und die Ausführungszeit einer Exponentialverteilung, kann die mittlere Antwortzeit durch folgende Gleichung berechnet werden:
\(E[T] = \frac{1}{\mu - \lambda}\)
• Hierbei ist:
  • \(E[T]\): Mittlere Antwortzeit \(\mu\): der Rate der Exponentialverteilung der Ausführungszeit \(\lambda\): der Rate der Poisson-Verteilung der Ankunftszeit

Schlussfolgerung

Probabilistisches Scheduling bietet in einem adaptiven Umfeld zahlreiche Vorteile, insbesondere durch seine Flexibilität und Robustheit gegenüber Unsicherheiten. Die Verwendung von Wahrscheinlichkeitsmodellen ermöglicht es, die Zuverlässigkeit und das Timing-Verhalten des Systems unter variablen Bedingungen besser abzuschätzen und anzupassen. Dadurch kann die Effizienz des Systems erheblich gesteigert werden.

c)

Vergleiche und kontrastiere die beiden Scheduling-Strategien (deterministisch vs. probabilistisch) anhand eines konkreten Beispiels: Ein Echtzeitsystem, das in einem autonom fahrenden Fahrzeug verwendet wird. Beziehe in deine Antwort ein, wie beide Ansätze die Planungssicherheit und die Flexibilität beeinflussen könnten. Führe Berechnungen durch, um die Effizienz und die Zuverlässigkeit beider Ansätze zu quantifizieren.

Lösung:

Vergleich und Kontrastierung von deterministischem und probabilistischem Scheduling in autonomen Fahrzeugen

In einem Echtzeitsystem eines autonom fahrenden Fahrzeugs müssen verschiedene Aufgaben wie Sensorverarbeitung, Entscheidungsfindung und Steuerung mit hoher Zuverlässigkeit und Effizienz durchgeführt werden. Im Folgenden werden deterministische und probabilistische Scheduling-Strategien verglichen und kontrastiert und ihre Auswirkungen auf Planungssicherheit und Flexibilität analysiert.

Deterministisches Scheduling

Deterministisches Scheduling verwendet feste Zeitpläne, um die Ausführungszeiten der Aufgaben zu bestimmen. Zum Beispiel könnte ein Sensorverarbeitungstask jede 100 Millisekunden (ms) ausgeführt werden, während Entscheidungsfindung jede 500 ms und Steuerung jede 50 ms ausgeführt werden.

Vorteile:

• Planungssicherheit: Die Aufgaben werden exakt nach einem vorher festgelegten Plan ausgeführt, was zu einem vorhersehbaren und garantierten Timing-Verhalten führt.
• Zuverlässigkeit: Deadlines können durch sorgfältige Planung garantiert werden, was besonders in sicherheitskritischen Anwendungen wie autonomen Fahrzeugen wichtig ist.

Nachteile:

• Geringe Flexibilität: Der feste Zeitplan ist nicht gut geeignet für unvorhersehbare Ereignisse oder Lastveränderungen.
• Ressourcenauslastung: Weniger effiziente Ausnutzung der Systemressourcen, da der Zeitplan starr ist und nicht auf Überlastsituationen reagieren kann.

Probabilistisches Scheduling

Probabilistisches Scheduling löst die Aufgaben basierend auf Wahrscheinlichkeiten, um flexibler auf Änderungen und Unsicherheiten zu reagieren. Anstatt feste Intervalle zu verwenden, werden Wahrscheinlichkeitsverteilungen eingesetzt. Zum Beispiel könnte die Sensorverarbeitung im Durchschnitt alle 100 ms ausgeführt werden, aber mit einer gewissen Varianz um diesen Mittelwert herum.

Vorteile:

• Flexibilität: Kann besser auf Laständerungen und unvorhersehbare Ereignisse reagieren.
• Effizienz: Dynamische Anpassung der Ressourcenauslastung führt in der Regel zu einer effizienteren Nutzung der Systemressourcen.
• Robustheit: Durch die Berücksichtigung von Wahrscheinlichkeiten können Unsicherheiten besser gemanagt werden.

Nachteile:

• Unvorhersehbarkeit: Schwieriger, das Timing-Verhalten exakt vorherzusagen, was zu potenziellen Planungsunsicherheiten führen kann.
• Zuverlässigkeit: Es besteht das Risiko, dass Deadlines unter ungünstigen Bedingungen nicht immer eingehalten werden können.

Konkretes Beispiel: Vergleich der Effizienz und Zuverlässigkeit

Betrachten wir ein autonomes Fahrzeug, das drei wichtige Aufgaben regelmäßig ausführen muss:

• Sensorverarbeitung: alle 100 ms
• Entscheidungsfindung: alle 500 ms
• Steuerung: alle 50 ms

Deterministisches Scheduling:

Unter einem deterministischen Ansatz hätte jede dieser Aufgaben eine feste zeitliche Periode basierend auf ihrem Intervall:

• Sensorverarbeitung: alle 100 ms
• Entscheidungsfindung: alle 500 ms
• Steuerung: alle 50 ms

Die folgenden Berechnungen quantifizieren die Zuverlässigkeit:

• Alle Aufgaben werden strikt nach Plan ausgeführt.
• Keine Abweichungen oder Verzögerungen, solange die Systemauslastung < 100% bleibt.

Probabilistisches Scheduling:

Unter einem probabilistischen Ansatz könnten die Intervalle Wahrscheinlichkeitsverteilungen folgen. Nehmen wir an, die Ausführungszeit X einer Aufgabe folgt einer Exponentialverteilung mit Parameter \(\lambda\).

• Der Durchschnitt der Intervalle bleibt gleich (Sensorverarbeitung alle 100 ms), aber mit Varianz.
• Für die Berechnung der Wahrscheinlichkeit, dass eine Aufgabe innerhalb einer bestimmten Zeit x abgeschlossen wird:

\(P(X \leq x) = 1 - e^{-x\lambda}\)

• Die mittlere Antwortzeit E[T] kann durch folgende Gleichung berechnet werden, wenn die Ankunftszeit Poisson-verteilt ist und die Ausführungszeit exponential:

\(E[T] = \frac{1}{\mu - \lambda}\)

Hierbei ist \(\mu\) die Rate der Exponentialverteilung für die Ausführungszeit und \(\lambda\) die Rate der Poisson-Verteilung der Ankunftszeit.

Schlussfolgerungen

Zusammenfassend lässt sich sagen, dass deterministisches Scheduling eine höhere Planungssicherheit und Zuverlässigkeit bietet, besonders in sicherheitskritischen Systemen wie autonomen Fahrzeugen. Probabilistisches Scheduling bietet jedoch erhöhte Flexibilität und Effizienz, indem es besser auf unvorhersehbare Änderungen reagiert.

Für ein autonomes Fahrzeug, bei dem Sicherheit und garantiertes Timing von größter Bedeutung sind, wäre deterministisches Scheduling in der Regel die bevorzugte Wahl. Probabilistisches Scheduling könnte jedoch in weniger sicherheitskritischen Szenarien oder als ergänzende Strategie verwendet werden, um die Effizienz zu steigern und die Anpassungsfähigkeit zu verbessern.