Vorlesung EchtzeitsystemeThema 1: Einführung

Robert Baumgartl

17. März 2015

1 / 35

Organisatorisches

I wahlobligatorisches Modul im HauptstudiumI 2/0/2, d. h., 90’ Vorlesung und 90’ Praktikum pro WocheI Vorlesung mittwochs, 7:30 Uhr, S 529 (Keuch!)I Lehrender: Prof. Robert Baumgartl

I robert.baumgartl@informatik.htw-dresden.deI dem Subject bitte „[EZS]“ voranstellenI Tel. 462 2510I Raum Z 126

I Praktikum im Labor Z 136cI mittwochs nach der Vorlesung, 9:20 UhrI Start: 2 Semesterwoche

I PrüfungI keine Prüfungsvorleistung (PVL)I wie immer (90’ ohne Hilfsmittel)

2 / 35

RessourcenFolien, Bücher

I Vorlesungsfolien (im PDF), Hausaufgaben, aktuelleInformationen erscheinen im Laufe des Semesters unterhttp://www.htw-dresden.de/~robge/ezs/ezs.html

I Jane W. S. Liu. Real-Time Systems. Prentice Hall, 2000I Alan Burns und Andy Wellings. Real-Time Systems and

Programming Languages. 3. Aufl. Addison-Wesley, 2001I Dieter Zöbel: Echtzeitsysteme. Springer, 2008. ISBN

978-3540763956, 29.95 eI Jim Cooling. Software Engineering for Real-Time Systems.

1. Aufl. Addison-Wesley, 2003

3 / 35

RessourcenWWW

I Kompendium; aus meinen bisherigen Veranstaltungenkompiliert

I Doug Jensens Site: http://www.real-time.org/I Computer-Related Incidents with Commercial Aircraft:

http://www.rvs.uni-bielefeld.de/publications/compendium/index.html

I news:comp.realtimeI GI-Fachgruppe Echtzeitsysteme: http://www.real-time.de/I Vorsicht - die deutsche Wikipedia taugt (bislang) nicht

besonders zur Erklärung des FachgebietsI Beispiel: Erklärung zur Prioritätsgrenze

4 / 35

Was machen wir hier eigentlich?

Die Webseite besagt:

„Die LV Echtzeitsysteme ist eine einsemestrigeEinführung in Theorie und Praxis vonRechensystemen, die zur Lösung zeitkritischerProbleme eingesetzt werden.“

= Kennenlernen von Verfahren und Methoden zur/zumI Entwurf,I Realisierung undI Analyse

von (Rechen-)systemen, die zeitliche Garantien gebenkönnen.

5 / 35

Thematische Übersicht

Prinzip: Anwendung des Echtzeitgedankens auf alle möglichenAspekte/Komponenten herkömmlicher Rechensysteme.Beispiele:I Echtzeit-SchedulingI echtzeitfähige RessourcenverwaltungI Echtzeit-KommunikationI Echtzeit-BetriebssystemeI Programmiersprachen für EchtzeitsystemeI Verifikation von Echtzeitsystemen

Allerdings gibt es auch noch einige originäre Themen:I ZeitI Fehlertoleranz

6 / 35

Verwandte Diskursbereiche

I Eingebettete SystemeI Rechnernetze und BetriebssystemeI Schedulingtheorie (Mathematik!)I Rechnerarchitektur

7 / 35

Voraussetzungen

I Grundlagen Programmierungstechnik (Zeigerkonzept,Listen, Bäume)

I Rechner- bzw. Prozessorarchitektur: Caches, Pipelines,Busse etc.

I Programmbeispiele in C, kaum AssemblerI Grundlagen Betriebssysteme (z.B. Scheduling,

Semaphore, Deadlock, Virtueller Speicher)

Am allerwichtigsten ist jedoch Interesse!

8 / 35

Was bedeutet „(in) Echtzeit“ ?

umgangssprachlich: Transformation der Eingangsdaten erfolgtmit der Geschwindigkeit ihres Empfangs. ( „xy läuft in Echtzeit“;xy ∈ {MP3-Encoder, Renderer, . . . })

Hermann Kopetz: “A real-time computer system is a computersystem in which the correctness of the system behaviourdepends not only on the logical results of the computations, butalso on the physical instant at which these results areproduced.” 1

Jane Liu: “. . . a real-time system is required to complete itswork and deliver its services on a timely basis.” 2

1Hermann Kopetz. Real-Time Systems. 3. Norwell, MA: Kluwer Academic Publishers, 1999, , S. 2.2Jane W. S. Liu. Real-Time Systems. Prentice Hall, 2000, , S. 1.

9 / 35

Was bedeutet „(in) Echtzeit“ ?

DIN 44300: „Echtzeitbetrieb ist ein Betrieb einesRechensystems, bei dem Programme zur Verarbeitunganfallender Daten ständig betriebsbereit sind derart, daß dieVerarbeitungsergebnisse innerhalb einer vorgegebenenZeitspanne verfügbar sind.“

dt. Wikipedia: „Von Echtzeitsystemen [...] spricht man, wenn einSystem ein Ergebnis innerhalb eines vorher fest definiertenZeitintervalles garantiert berechnet, also bevor eine bestimmteZeitschranke erreicht ist. Die Größe des Zeitintervalles spieltdabei keine Rolle [...].“

10 / 35

Schlussfolgerung

Das bedeutet:I sowohl die Korrektheit,I als auch die Dauer der Ermittlung

der Ergebnisse wird garantiert.

In Nicht-Echtzeit-Systemen wird i. a. nur die Korrektheitgarantiert.

Vereinfachung: Eine bestimmte zeitliche Schranke (Deadline)wird nicht überschritten.

Verhalten eigentlich auch in „normalen“ Systemen erwünscht,z.B. bei der Reaktion auf Benutzereingaben (Problem:Aufwand).

11 / 35

Nochmals . . .

Was bedeutet „die Dauer der Operation wird garantiert“?

Ganz einfach: eine Spezifikation legt fest, wie lange dieOperation maximal dauern darf, und das Echtzeitsystemgarantiert, dass diese maximale Dauer niemals überschrittenwird, was immer auchI innerhalb des Systems undI in der Umwelt

passieren mag.

Die Maximaldauer nennen wir (relative) Deadline (derOperation).

12 / 35

Häufige Mißverständnisse und Fehlannahmen

I Echtzeitsysteme sind sehr schnelle Rechner.→ Widerspruch: Prozessoren in Echtzeitsystemen sind häufig

niedriggetaktete Mikrocontroller.I Präemptive Prozessorvergabe ermöglicht prinzipiell ein

Echtzeitsystem.→ reicht nicht aus; Windows Vista ist kein EchtzeitsystemI Moore’s Law bewirkt, daß Echtzeitsysteme überflüssig

werden.→ Falsche Annahme, dass „Echtzeit“ schnell bedeutetI Es kann sowieso keine Garantie der Funktionsfähigkeit

eines Rechners gegeben werden, daher sindEchtzeitsysteme nicht notwendig.

I Echtzeitsysteme werden in Assembler programmiert.

13 / 35

Häufige Mißverständnisse und Fehlannahmen

I Echtzeitsysteme sind sehr schnelle Rechner.→ Widerspruch: Prozessoren in Echtzeitsystemen sind häufig

niedriggetaktete Mikrocontroller.I Präemptive Prozessorvergabe ermöglicht prinzipiell ein

Echtzeitsystem.→ reicht nicht aus; Windows Vista ist kein EchtzeitsystemI Moore’s Law bewirkt, daß Echtzeitsysteme überflüssig

werden.→ Falsche Annahme, dass „Echtzeit“ schnell bedeutetI Es kann sowieso keine Garantie der Funktionsfähigkeit

eines Rechners gegeben werden, daher sindEchtzeitsysteme nicht notwendig.

I Echtzeitsysteme werden in Assembler programmiert.

14 / 35

Häufige Mißverständnisse und Fehlannahmen

I Echtzeitsysteme sind sehr schnelle Rechner.→ Widerspruch: Prozessoren in Echtzeitsystemen sind häufig

niedriggetaktete Mikrocontroller.I Präemptive Prozessorvergabe ermöglicht prinzipiell ein

Echtzeitsystem.→ reicht nicht aus; Windows Vista ist kein EchtzeitsystemI Moore’s Law bewirkt, daß Echtzeitsysteme überflüssig

werden.→ Falsche Annahme, dass „Echtzeit“ schnell bedeutetI Es kann sowieso keine Garantie der Funktionsfähigkeit

eines Rechners gegeben werden, daher sindEchtzeitsysteme nicht notwendig.

I Echtzeitsysteme werden in Assembler programmiert.

15 / 35

Häufige Mißverständnisse und Fehlannahmen

I Echtzeitsysteme sind sehr schnelle Rechner.→ Widerspruch: Prozessoren in Echtzeitsystemen sind häufig

niedriggetaktete Mikrocontroller.I Präemptive Prozessorvergabe ermöglicht prinzipiell ein

Echtzeitsystem.→ reicht nicht aus; Windows Vista ist kein EchtzeitsystemI Moore’s Law bewirkt, daß Echtzeitsysteme überflüssig

werden.→ Falsche Annahme, dass „Echtzeit“ schnell bedeutetI Es kann sowieso keine Garantie der Funktionsfähigkeit

eines Rechners gegeben werden, daher sindEchtzeitsysteme nicht notwendig.

I Echtzeitsysteme werden in Assembler programmiert.

16 / 35

Häufige Mißverständnisse und Fehlannahmen

I Echtzeitsysteme sind sehr schnelle Rechner.→ Widerspruch: Prozessoren in Echtzeitsystemen sind häufig

niedriggetaktete Mikrocontroller.I Präemptive Prozessorvergabe ermöglicht prinzipiell ein

Echtzeitsystem.→ reicht nicht aus; Windows Vista ist kein EchtzeitsystemI Moore’s Law bewirkt, daß Echtzeitsysteme überflüssig

werden.→ Falsche Annahme, dass „Echtzeit“ schnell bedeutetI Es kann sowieso keine Garantie der Funktionsfähigkeit

eines Rechners gegeben werden, daher sindEchtzeitsysteme nicht notwendig.

I Echtzeitsysteme werden in Assembler programmiert.

17 / 35

Häufige Mißverständnisse und Fehlannahmen

I Echtzeitsysteme sind sehr schnelle Rechner.→ Widerspruch: Prozessoren in Echtzeitsystemen sind häufig

niedriggetaktete Mikrocontroller.I Präemptive Prozessorvergabe ermöglicht prinzipiell ein

Echtzeitsystem.→ reicht nicht aus; Windows Vista ist kein EchtzeitsystemI Moore’s Law bewirkt, daß Echtzeitsysteme überflüssig

werden.→ Falsche Annahme, dass „Echtzeit“ schnell bedeutetI Es kann sowieso keine Garantie der Funktionsfähigkeit

eines Rechners gegeben werden, daher sindEchtzeitsysteme nicht notwendig.

I Echtzeitsysteme werden in Assembler programmiert.

18 / 35

Häufige Mißverständnisse und Fehlannahmen

I Echtzeitsysteme sind sehr schnelle Rechner.→ Widerspruch: Prozessoren in Echtzeitsystemen sind häufig

niedriggetaktete Mikrocontroller.I Präemptive Prozessorvergabe ermöglicht prinzipiell ein

Echtzeitsystem.→ reicht nicht aus; Windows Vista ist kein EchtzeitsystemI Moore’s Law bewirkt, daß Echtzeitsysteme überflüssig

werden.→ Falsche Annahme, dass „Echtzeit“ schnell bedeutetI Es kann sowieso keine Garantie der Funktionsfähigkeit

eines Rechners gegeben werden, daher sindEchtzeitsysteme nicht notwendig.

I Echtzeitsysteme werden in Assembler programmiert.

19 / 35

Häufige Mißverständnisse und Fehlannahmen

I Echtzeitsysteme sind sehr schnelle Rechner.→ Widerspruch: Prozessoren in Echtzeitsystemen sind häufig

niedriggetaktete Mikrocontroller.I Präemptive Prozessorvergabe ermöglicht prinzipiell ein

Echtzeitsystem.→ reicht nicht aus; Windows Vista ist kein EchtzeitsystemI Moore’s Law bewirkt, daß Echtzeitsysteme überflüssig

werden.→ Falsche Annahme, dass „Echtzeit“ schnell bedeutetI Es kann sowieso keine Garantie der Funktionsfähigkeit

eines Rechners gegeben werden, daher sindEchtzeitsysteme nicht notwendig.

I Echtzeitsysteme werden in Assembler programmiert.

20 / 35

Sekundäre Anforderungen an Echtzeitsysteme

I hohe ArbeitsgeschwindigkeitI FehlertoleranzI Kosteneffizienz

I niedriger EnergiebedarfI hohe Ressourcenauslastung (Prozessor, Speicher)

−→ Kompromiss je nach Einsatzfall nötig!

21 / 35

Härte eines Echtzeitsystems

a) hartes EZ-System: Verletzung einer Deadline hatkatastrophale Konsequenzen für das System bzw. dieUmwelt.

b) weiches EZ-System: Verletzung einer Deadline führt zumAbsinken des Wertes des Ergebnisses, Einfluß auf die„Güte“ des Dienstes, Systemleistung sinkt mit der Anzahlverletzter Deadlines.

c) „mittelhartes“ EZ-System: Nach Überschreiten derDeadline ist das Ergebnis wertlos, jedoch keineKatastrophe (sog. “firm deadline”)

22 / 35

Härte eines EchtzeitsystemsWas passiert bei Verletzung einer Deadline?

3 Möglichkeiten, je nach „Wert“ des Ergebnisses nachÜberschreitung der Deadline td :

0t t t

0 0td td td

Wert desErgebnisses

sehr grosz

Abbildung: Hartes, weiches und „mittelhartes“ Echtzeitsystem

23 / 35

Härte eines EchtzeitsystemsAnmerkungen

I Unterscheidung zwischen harten und weichenEZ-Systemen nicht immer trivial, insbesondere derÜbergang zwischen weichen und Nicht-Echtzeit-Systemenist oftmals fließend.

I Fehlertoleranz bei harten EZ-Systemen meistausgeprägter

I Idee der “Flexible Computations”: Aktivität wird geteilt ineine essentielle und eine wahlfreie Phase. Die essentiellePhase muß unbedingt bis zur Deadline abgeschlossensein. Wahlfreie Phase erhöht die Güte des Resultats.Beispiel: Ermittlung der Raumkoordinaten einerRaumsonde.

I Komplettierung vor Deadline oftmals unerwünscht

24 / 35

Klassifizierungsmerkmale von Echtzeitsystemen

1. „Härte“ der Deadline2. Zuverlässigkeit und Fehlertoleranz (Sicherheit,

Fehlererkennung)3. Verteilung: zentralisiertes oder verteiltes Echtzeitsystem4. zeitgesteuertes oder ereignisgesteuertes System5. interaktives oder autonomes System6. hierarchisches oder Einzelsystem7. zyklische oder/und asynchrone Aktivitäten

25 / 35

Eingebettete Systeme

Echtzeitsysteme konstituieren häufig Eingebettete Systeme(embedded systems):

“Embedded computers are defined to be those wherethe computer is used as a component within a system:not as a computing engine in its own right. [...]” 3

d.h. der Computer ist Teil eines Geräts (und das Gerät ist keinComputer im klassischen Sinne).

3Jim Cooling. Software Engineering for Real-Time Systems. 1. Aufl. Addison-Wesley, 2003, , S. 12.26 / 35

Eingebettete SystemeMerkmale

I komplexe Interaktion mit Umwelt und andereneingebetteten Systemen

I werden häufig autonom betriebenI hohe Anforderungen an ZuverlässigkeitI ersetzen zunehmend mechanische SystemeI Hard- und Software werden gemeinsam entworfen

(HW/SW-Codesign).I Einsatz eines Prozessors „von außen“ häufig nicht

erkennbarI arbeiten häufig unter Echtzeit-BedingungenI Kosten für Reparatur übersteigen (häufig) Kosten des

Systems.

27 / 35

Beispiele für Echtzeitsysteme

Herzschrittmacher:I 1 Prozessor, 500 000 Lines of Code (LoC)

Abbildung: Größenvergleich Herzschrittmacher vs. 50-Pence-Stück

28 / 35

Beispiele für Echtzeitsysteme

Boeing 777:I ca. 1200 Prozessoren, 4 Milliarden LoC

Abbildung: Boeing 777 – ein etwas größeres Echtzeitsystem

29 / 35

Beispiele für Echtzeitsysteme, cont’dDigitaler Video-Recorder für HDTV

I Fernsehbild HDTV: 1920x1080 Punkte, 24 Bit Farbtiefe(maximal)

I d.h. ein unkomprimiertes Bild benötigt1920 · 1080 · 3 Byte = 6075 KiB.

I Wiedergaberate: (bis zu) 60 Hz (Bilder pro Sekunde)

I in t =1

60s = 16.6 ms muss das Bild abgespeichert sein

I =̂ End-zu-End-Transferrate von ≈ 356 MiB/sI sehr gute Festplatten erreichen ca. 100 MiB/sI → Kompressionsverfahren erforderlich

30 / 35

Beispiele für Echtzeitsysteme, cont’d

Beispiel: Digitale Schiedsrichterassistenz im Fußball

I Sender im Ball und den Schienbeinschonern der SpielerI extreme Anforderungen: Ball (bis 160 km/h) trifft auf

Pfosten, Nässe, Vibrationen. . .I Auflösung: ZentimeterbereichI → Positionsbestimmung in Echtzeit (WITRACK-System

des Fraunhofer IIS)I Goal Line Technology System der Cairos AG:

http://www.cairos.com/unternehmen/gltsystem.php

31 / 35

Weitere Einsatzfelder

I Luft- und Raumfahrt: Flugkontrollsystem, Steuerung vonRaketenmotoren, Satelliten

I Digitale Steuerungen: Proportional Integral DerivativeController, Robotersteuerungen, Computertomograph

I Automotive-Bereich: ABS, ESP, Airbag-Steuerung,Navigationssysteme, Motormanagement, CAN-undFlexRay-Bus

I Signalverarbeitung: RADAR, Verfolgung (Tracking) vonObjekten, Bilderkennung, Unterhaltungselektronik

I Multimedia-Systeme: En- und Dekodierung vonAudio/Video-Strömen, Klang- und Sprachsynthese, VoIP,Video Storage Server

I Echtzeit-Datenbanken

32 / 35

Aktuelle Forschungsgebiete (→ Diplomthemen?!)

I Multiprozessor-SchedulingI Worst Case Execution TimingI Verifikation von echtzeitfähigen SystemenI Synchrone ProgrammiersprachenI Echtzeitabstraktionen für Betriebssysteme

33 / 35

Zusammenfassung: Was haben wir gelernt?

1. Echtzeitsysteme sichern die Rechtzeitigkeit allerrelevanten Operationen.

2. harte vs. weiche vs. „mittelharte“ Echtzeitsysteme3. Begriffe: Deadline, eingebettetes System4. Wenn etwas (umgspr.) in Echtzeit läuft, dann ist die

Eingangsdatenrate gleich der Ausgangsdatenrate.(Beispiel: Echtzeit-3D-Darstellung)

5. Echtzeitsysteme sind außerordentlich interessant.

34 / 35

Vertiefende Literatur

Die hier aufgeführten Texte sind Lesevorschläge. Da diese demUrheberrecht unterliegen (die Texte, nicht die Vorschläge),kann ich sie nicht einfach ins Netz stellen, sondern stelle sieIhnen auf Anfrage zur Verfügung.

I John A. Stankovic. “Strategic Directions in Real-Time andEmbedded Systems”. In: ACM Computing Surveys 28.4(Dez. 1996), S. 751–763

I John Stankovic. “Misconceptions About Real-TimeComputing”. In: IEEE Computer 21.10 (Okt. 1988),S. 10–19

35 / 35