Echtzeitsysteme

Prof. Dr. Dieter Zöbel

 

Aktuelles - Inhalte - Literatur - Aufgaben - Material -Organisation - Zielgruppe - Leistungsnachweis - Termine

Aktuelles

  • Die Veranstaltung Echtzeitsysteme umfasst 3 Stunden Vorlesung (V) und eine Stunde Übung (Ü) pro Woche. Die Veranstaltung findet statt in:
    Mi., 8:30 - 10:00 in A120 (2V)
    Do., 8:30 - 10:00 in B017 (1V+1Ü)

  • Die erste Übungsveranstaltung zur Vorlesung ist am Mi., 18.10.2017, 8:30-10:00 Uhr in Raum A120.

Inhalte

Die herausragende Eigenschaft von Echtzeitsystemen ist die Einhaltung von Zeitbedingungen. Diese spielen in den unterschiedlichsten Anwendungen, vom Tachometer eines Fahrrades, über das Antiblockiersystem eines Kraftfahrzeugs bis hin zu Bestandteilen einer Fertigungsanlage eine entscheidende Rolle. Für diese Anwendungen ist die Einhaltung von Zeitbedingungen ein unverzichtbares Korrektkeits- und Sicherheitskriterium, das in den verschiedensten Stufen der Software-Entwicklung entsprechende Konzepte und Methoden erfordert.

Im Rahmen der angebotenen Vorlesung Echtzeitsysteme kann nur ein Teil der Konzepte und Methoden, die dieses Fachgebiet auszeichnen, angesprochen werden. Dabei sollen jedoch die Belange der Anwendungen, wie sie heute als eingebettete Systeme in vielfältiger Weise in Fahrzeugen eingebaut und benutzt werden, besonders hervorgehoben werden. Wesentliche Themenschwerpunkte der Vorlesung werden deshalb die Ableitung und Behandlung von Zeitbedingungen in den ensprechenden Kontexten sowie entsprechnde Planungs- und Synchronisierungsstrategien einnehmen.

Gliederung der Vorlesung

  1. Einführung
    Grundmodell eines Echtzeitsystems, Prozessmodell, Zeiten und Uhren, Anwendungsbeispiele

  2. Grundlagen der Prozessplanung
    Modellbildung, Zyklische Planung, Planen nach monotonen Raten, Planen nach Fristen, Planen nach Spielräumen, Vergleich der Planungsverfahren

  3. Synchronisierung und Echtzeit
    Echtzeitbetriebssysteme, Konzepte der Synchronisierung von Prozessen, Prioritätsumkehr, Protokolle zur Prioritätsvererbung und zur Prioritätsobergrenze

  4. Rechnernetze und Echtzeit
    Echtzeitspezifische Klassifizierung der Rechnetze, zeitbewertete Busprotokolle, Zeitbewertete Netzprotokolle, Integration in die Prozessplanung

  5. Weitere Themen
    Rechnerarchitekturen, Mehrrechnerarchitekturen, Planung bei Mehrprozessorsysteme

Aufgaben

1. Aufgabenblatt

2. Aufgabenblatt

3. Aufgabenblatt

4. Aufgabenblatt

5. Aufgabenblatt

6. Aufgabenblatt

7. Aufgabenblatt

8. Aufgabenblatt

 

Material

Teile des Skripts zur Vorlesung liegen unter
http://userpages.uni-koblenz.de/~zoebel/EZmat/Skript/

 

Verlauf der Vorlesung

  • 18.10. (V): Einordnung der der Vorlesung "Echtzeitsysteme" in das Studium der Informatik und Computervisualistik, Besprechung der Bedingungen für die Vergabe der Leistungspunkte, 1. Einführung, Merkmale von Echtzeitsystemen, DIN 44300, harte und weiche Echtzeitbedingungen, Beispiel: ball on a beam, Vergleich von Determiniertheit und Vorhersagbarkeit, Sicherheit und Zuverlässigkeit, Risiko als das Produkt aus dem Ausmaß des Schadens und der Wahrscheinlichkeit seines Auftretens, Grenzrisiko,
  • 19.10. (V): Fehlerursachen, Fehlerzustände und Ausfälle, 1.2 Grundmodell eines Echtzeitsystems, Paradigmatische Beispiele für Echtzeitsysteme, Beispiel: Sortieranlage, Anwendungsfalldiagramme und Datenflussdiagramme, Beispiel: Anwendungsfalldiagramm für die Anwendung Wippe, Abgrenzung zu eingebetteten Systemen, Cyber Physical Systems (CPS), 1.3 Prozesse, Grundmodell eines Rechenprozesses, Beispiel: Datenflussdiagramm für die Wippe, Aufbauschema eines Regelkreises
  • 2.11. (V): 1.4 Echt und Zeit, Bemerkungen zum Sprachgebrauch in Echtzeit, Beispiel: Bedeutung der Schnelligkeit bei Berechungen anhand der Verkehrszeichenerkennung (traffic sign recognition), physikalische Zeit und Echtzeit, Modellierung von Zeitpunkten, Zeitintervallen und Zeitspannen, Rechenregeln für Zeitpunkte und Zeitspannen, Unschärfen durch die Diskretisierung der physikalischen Zeit, Bestandteile eines Uhrbausteins, Abweichungen (Diskretisierung und Drift) verursacht durch den Uhrbaustein, Echtzeit als der Versuch der Abbildung der klassischen physikalischen Zeit in den Rechner, 1.5 Beispiele, Beispiel: Papiermaschine, Beispiel: Steuergerät, Beispiel: Internet-Telefonie,
    (Ü) Beschreibungsansätze für den softwaretechnischen Entwurf von Echtzeitanwendungen, Bauelemente von Datenflussdiagrammen
  • 8.11. (V): 2. Echtzeitplanung, 2.1 Grundlagen der Echtzeitplanung, Prozessmodell, unterbrechbare und nichtunterbrechbare Prozesse, periodische, sporadische und aperiodische Prozesse, Prozesstyp. Prozessobjekt, Prozessausführung,, Bsp.: Prozesstyp und Prozessobjekt in der Programmiersprache Ada, Prozessparameter, Bereitzeit, Ausführungszeit und Frist, Periode, Auslastung, Darstellung von Plänen, zeitgesteuerte und ereignisgesteuerte Prozessausführung, Brauchbarkeit von Plänen, Optimalität von Planungsverfahren
  • 9.11 (Ü): Funktionsweise eines Ottomotors, Betrachtung der verfügbaren Sensorwerte bei zwei Umläufen der Kurbelwelle, Herleitung der zeitlichen Anforderungen zur Erzeugung eines Zündfunkens für einen speziellen Zylinder, Bezug zum Aufgabenblatt 2,
    (V) Phasen der Echtzeitplanung, Zustandsmodelle für Prozesse, 2.2 Planen durch Suchen, Darstellung eines Planes, Planung für nicht unterbrechbare Prozesse, Verfahren 2: Planen durch Suchen unter Berücksichtigung von Bereitzeiten und Fristen, Nachweis der Optimalität von Verfahren 2 durch vollständige Induktion
  • 15.11. (V): Anwendung der Konstruktion zum Nachweis der Optimalität eines Verfahrens auf ein Menge nicht unterbrechbarer Prozesse, Nachweis der NP-Vollständigkeit des Problems der Verplanung nicht unterbrechbarer Prozesse (PROBLEM DER SEQUENZIERUNG VON INTERVALLEN), 2.3 Planen nach Fristen, Verfahren 3 zur Planung nach Fristen für nicht unterbrechbare Prozesse, Beschreibung der Ausführung unterbrechbarer Prozesse
  • 16.11. (Ü): Besprechung der Übungsaufgabe 1, Vergleichbarkeit von diskreten Zeiten rt(t),
    (V): Planen nach Fristen für unterbrechbare Prozesse, Bestimmung des nächsten Planungszeitpunktes mit der Funktion nextdispatch(t), Verfahren 4 zur Verplanung unterbrechbarer Prozesse nach Fristen, Optimalität des Verfahrens 4, Beispiel: Verplanung einer Prozessmenge nach Verfahren 4
  • 22.11. (V): Planen nach Fristen für periodische unterbrechbare Prozesse, Beispiel: Planen nach Fristen für periodische unterbrechbare Prozesse, Lemma 5: es gibt keine Planungslücke vor dem Zeitpunkt einer Fristverletzung, Satz 6: eine Prozessmenge ist genau dann brauchbar, wenn die Auslastung den Wert 1 nicht überschreitet, Abbildung des Planes nach Fristen auf Prioritäten, Planen nach Fristen als Planungsverfahren mit dynamischen Prioritäten, 2.4 Planen nach Spielräumen
  • 23.11. (Ü) Besprechung der Übungsaufgabe 2, restzeitiges Auslösen des Zundfunkens bei einem 3-zylindrigen Ottomotor,
    (V) Definition des Spielraums (laxity), Prioritätszuordnung nach LLF (least laxity first), Begründung der häufigen Prozessumschaltungen, Reduzierung der Zahl der Prozessumschaltungen bei MLLF (modified least laxity first), 2.5 Planen nach festen Prioritäten, Definition des kritischen Zeitpunktes, Bedeutung der brauchenbaren Einplanung eines Prozesses im kritischen Intervall
  • 29.11.: fällt aus
  • 30.11 (V)  2.6 Planern nach monotonen Raten, RMS (rate monotonic scheduling), Beispiel: Einplanung eines Prozesses aus der Randmenge nach RMS, Nachweis der Optimalität von RMS, Nachweis der Schranke von Liu und Layland
  • 6.12.: Beispiel: LL-Test, praktische Bedeutung des Planens nach monotonen Raten, Existenz verbesserter (hinreichender) Tests (z.B. HB-Test), Bedeutung der Antwortzeit, RT-Test (response time) basierend auf Antwortzeiten als hinreichendes und notwendiges Kriterium für Brauchbarkeit, 2.7 Planen nach monotonen Fristen, Bedeutung von DMS (deadline monotonic scheduling), LL-Test und RT-Test, Beispiel: DMS am Beispiel der "Wippe"
  • 7.12.: (Ü) Besprechung der Übungsaufgaben 3 und 4, Beispiel: Anwendung des RT-tests auf eine konkrete Prozessmenge,
    2.9 Zyklisches Planungsverfahren, äußerer und innerer Zyklus (major cycle time und minor cycle time), Programmschema für das zyklische Planen, Beispiel: zyklischer Plan
  • 13.12. Herleitung von Heuristiken zur Bestimmung der Dauer des inneren Zyklus, Beispiel: zyklischer Plan mit der Suche nach der Zeitspanne des inneren Zyklus, 2.8 Heterogene Prozessmenge, Integrierbarkeit von sporadischen Prozessen in die Planung periodischer Prozesse. Abbildung von aperiodischen Prozessen auf sogenannte server-Prozesse, Betrachtung des Polling-Server Ansatzes und Anwendung des LL-Tests, Betrachtung des Ansatzes Total Bandwidth Server (TBS)
  • 14.12. (Ü) Besprechung der Übungsaufgabe 6: Beweis der 100%-Auslastung von periodischen unterbrechbaren Prozessen bei harmonischen Perioden
    Beispiel zur Anwendung des TBS inklusive der Berechung von Fristen für aperiosisch bereitwerdende Prozesse, 5. Rechnernetze, 5.1 Grundlagen, formale Struktur von Rechnernetzen und den dort versendeten Rahmen (frames)
  • 20.12. Aufbau von Rechnernetzen und deren Echtzeiteigenschaften, Ende-zu-Ende Antwortzeiten, Schichtenmodell für Echtzeitnetze, Bedeutung der Zugriffsschicht (MAC, medium access layer), Topologien und Netzhierarchien, Beispiel: Busse bei Fahrzeugen und die Vernetzung der Netze, besondere Eigenschaften drahtloser Rechnernetze, Zeitintervalle mit Kollisionsgefahr, das hidden terminal Szenario,  Beispiel: voll vernetzte Drahtlosnetze beim Standard IEEE 802.11s
  • 21.12. (Ü) Besprechung der Übungsaufgabe 7,  Implementierung von RMS und EDF, Konzept des Zeitrads (time wheel), Nachweis der Notwendigkeit der Anwendung des RT-Tests auf alle Prozesse, Besprechung der Übungsaufgabe 8, Betrachtung der Zeiten für die Prozessumschaltung, Alternativen der Beachtung der Umschaltzeiten bei der Echtzeitplanung
  • 10.1. 5.3 Zugriffsprotokolle, Zentralisiertes Verfahren, Arbitrationsverfahren. Beispiel: Vergleich der Verbreitung des Signals bei Ethernet und beim CAN-Bus, markengesteuertes Verfahren, Zeitmultiplex-Verfahren, Beispiel: TTA (time-triggered architecture) und TTP (time-triggered protocol), Anpassung nicht echtzeitfahiger Zugriffsprotokolle, Beispiel: Eckpunkte des AFDX-Protokolls
  • 11.1. (Ü) Besprechung der Übungsaufgabe 10, Heuristiken bei der zyklischen Planung
    5.3 Abschätzung von Echtzeitbedingungen, Zustandsbetrachtung bei eionzelnen Knotenabhängig von exteren Ereignissen oder dem Empfangen eines Rahmens, Beispiel: steer by wire, Zeitbertachtung vom externen Ereignis bis zur Ankunft eines entsprechenden Rahmens bei einem anderen Knoten, holistische Planung, Übertragungszeit eines Rahmens auf einem Medium, Antwortzeit eines Rahmens, Anwendung der Planung auf ein zeitgesteuertes Netzwerk, Beispiel: Unterbringung eines Rahmens in verschiedene Runden eines Zyklus
  • 17.1. Zeitbedingungen bei arbitrierenden Zugriffsprotokollen, Blockadezeit und Beschäftigungsphase (busy period), Beispiel: Fristverletzung bei drei Rahmen unterschiedlicher Priorität, Rekursionsformel für die Beschäftigungsphase, Nachweis der Brauchbarkeit bei arbitrierenden Zugriffsprotokollen mut Analogien zum RT-Test, Beispiel, Zeitbedingungen bei markengesteuerten Zugriffsprotokollen, Regeln für Vorgabe der TTRT (target token rotation time), algorithmische Bestimmung der THT (token holding time), Maximale Verzögerung bis zum Versenden eines Rahmens von 2* TTRT, Beispiel
  • 18.1. Zeitparameter eines Virtuellen Link eines AFDX-Rechnernetzes mittels BAG (bandwidth allocation gap), Berechnung des Flatterns der Zeitpunkte der Übertragung eines Rahmens, 4. Synchronisierung, 4.1 Grundlagen, Prozessbegriff, Übersicht über die Methoden der Synchronisierung, kanonisch geschachtelte kritische Gebiete, Vorrang der Synchronisierung vor der Priorität, 4.2 Prioritätsumkehr, Schema der Prioritätsumkehr, Echtzeitbedingungen für Prozesse mit Synchronisierungsbeziehungen, Nichtunterbrechbarkeit kritischer Gebite mit der NPCS-Methode (nonpreemptive critical sections), 4.3 Prioritätsvererbung, PIP (priority inheritance protocol) Beschreibende Abbildungen zwischen Prozessen und kritischen Gebieten
  • 24.1. Beispiel: Ausführung eines parallelen Programms mit dem Aufbai der Abbildungen ownedBy und blockedBy, Herleitung der PIPd (delayed)-Variante des PIP, Blockierung maximal je einmal von einem niedriger priorisierten Prozess und maximal nur einmal von jedem kritischen Gebiet, Bewertung der Prioritätsvererbung, 4.4 Prioritätsobergrenzen, PCP (priority ceiling protocol), Anwendungsbereich des PCP im Vergleich zum PIP, Bedeutung der Obergrenze in den Abbildungen wants und ceiling
  • 25.1. (Ü) Besprechung des 7 Aufgabenblatts, Berechung der Echtzeitfähigkeit von Rahmen bei arbitrierenden Protokollen,
    Berechnung der aktuellen Obergrenze (aceiling) als Entscheidungskriterium zum Betreten kritischer Gebiete, Beispiel: Anwendung des PCP-Protokolls, 4.5 Übersicht zur Prioritätsinversion, Betriebssysteme und Laufzeitsysteme mit Protokollen zur Abwehr der Prioritätsumkehrung, 6. Planung für Mehrkernprozessoren, generalisierte Architektur von Mehrkernprozessoren, 6.1 Einführung und Modellbildung, Anwendbarkeit der Standardplanungsverfahren für Mehrprozessorsysteme, Beispiel: Anomalien bei RMS und EDF für Mehrprozessorsysteme
  • 31.1. Hinweise zur Art und zum Aufbau der Klausur
    6.2 Anwendbarkeit der klassischen Planungsverfahren, Kategorisierung von Planungsverfahren und Migrationseigenschaften von Prozessen nach Carpenter, weitere Migrantionseigenschften: clustered und APA (arbitrary processor affinity), Dhall-Effekt, Inklusionsbeziehung zwischen den Kategorien nach Carpenter, 6.3 Proportional faires Scheduling (p-fair), Intuition der P-Fairness
  • 1.2. (Ü) Besprechung des 8. Aufgabenblatts, Anwendung des PIPd-Protokolls auf Programmfragmente, Anwendung des PCP auf Programmfragmente,
    Zerlegung von Prozessausführungen in Zeitschlitze (slots), Verfolgung der Prozessausführung und Erfüllung der Plananforderungen, Optimalität der P-Fairness bei m Prozessoren, 6.4 Affinitäten zwischen Prozessen und Prozessoren
  • 7.1. (Ü) Nachtrag zu Thema Prioritätsvererbung: Berechnung von Blockadezeiten beim PIP
    Abbildungen zwischen Prozessen und Prozessoren unter Beachtung von Prioritäten, APA Scheduling Invariante, Beispiele:Abbildungen die der APA Scheduling Invarianten genügen oder nicht, Beispiel: Erzeugung einer Abbildung für eine gegebene Menge von Prozssoren auf einem gegebenen Mehrprozessor, 7. Echtzeitbetriebssysteme, relevate Eigenschaften, Übersicht über Echtzeitbetriebssysteme und Laufzeitsysteme
  • 8.1. (Ü) Anwendung der Echtzeitplanung nach EDF auf ein Mehrprozessorsystem mit Prozesszuordnung für eine Prozessausführung ( in de Notation von Carpenter: (EDF,ExM)),
    grundlegende Konzepte von Echtzeitsysteme, Beispeiel: OSEK/VDX und AUTOSAR

Organisation (in Bearbeitung)

  • Die Übungsaufgaben werden spätestens bis jeweils freitags in Netz gestellt und sind bis zum nächsten Donnerstag zu bearbeiten.
  • Die gelösten Übungsaufgaben sind unter Angabe der Autorenschaft in .pdf-Form an die Email-Adresse zoebel@uni-koblenz.de zu schicken.

Zielgruppe

  • Master Informatik, Schwerpunkt in der Informatik (MSE) oder Wahlpflicht Informatik
  • Master Computervisualisitik, Schwerpunkt (MSE), Wahlpflicht Informatik
  • Master Wirtschaftsinformatik, Schwerpunkt (MSE), Wahlpflicht Informatik

Leistungsnachweis

  • Die Teilnehmer der Veranstaltung haben sich auf ...  geeinigt. Die Klausur findet in Raum ...  ab ... :00 statt.
  • Es müssen mindestens 50% der Punkte der Übungsblätter erreicht werden, um an der mündlichen Prüfung teilnehmen zu können.
  • In einem vorherigen Semester erworbene Klausurzulassungen werden nicht anerkannt. Ausgenommen davon sind Studierende, die aufgrund von Fehlversuchen verpflichtet sind, an der nächsten Klausur zu "Echtzeitsysteme" teilzunehmen. In diesem Fall wird für die Wiederholung keine neue Zulassung benötigt. Der bzw. die Studierende ist sogar verpflichtet an der jeweils nächsten Hauptklausur teilzunehmen.
  • Um an der mündlichen Prüfung teilnehmen zu können, ist eine vorherige Anmeldung zur Klausur notwendig. Die Anmeldung ist verbindlich! Wer sich anmeldet und unentschuldigt nicht mitschreibt, dessen Klausur wird mit 0 Punkten (nicht bestanden) gewertet.

Termine

  • Die erste Prüfung (in Form einer Klausur nach Wunsch der Teilnehmer der Veranstaltung)  zur Vorlesung Echtzeitsysteme findet am 26.2.2018 in Raum B017 ab 10:00 statt.
  • Die zweite Prüfung (in Form einer mündliche Prüfung) zur Vorlesung Echtzeitsysteme findet voraussichtlich am 5.4.2018 in Raum ??? ab 10:00 statt.


Literatur

Sanjoy Baruah, Marko Bertonga, Giorgio B. Buttazzo. Multiprocessor Scheduling for Real-Time Systems, Springer-Verlag, 2015

Giorgio C. Buttazzo. Hard Real-Time Computing Systems. Kluwer Academic Publishers, 2005.

Hermann Kopetz, Real-Time Systems. Springer-Verlag, 2011

Peter Marwedel. Eingebettete Systeme. Springer-Verlag, 2007.

Alan C. Shaw. Real-Time Systems and Software. John Wiley and Sons, 2001.

Michael P. Witzak. Echtzeitbetriebssysteme. Franzis Verlag, 2000.

Heinz Wörn, Uwe Brinkschulte. Echtzeitsysteme. Springer-Verlag , 2005.

Dieter Zöbel. Echtzeitsysteme - Grundlagen der Planung. Springer-Verlag 2008