Upload
others
View
13
Download
0
Embed Size (px)
Citation preview
Echtzeitsysteme
Dieter Zöbel
Universität Koblenz-LandauFachbereich Informatik, Institut für Softwaretechnik
Inhaltsverzeichnis
1 Einführung 21.1 Merkmale von Echtzeitsystemen . . . . . . . . 3
1.1.1 Harte und weiche Echtzeitbedingungen 61.1.2 Determiniertheit und Vorhersagbarkeit . 111.1.3 Sicherheit und Zuverlässigkeit . . . . . 12
1.2 Das Grundmodell eines Echtzeitsystems . . . . 161.2.1 Paradigmatische Beispiele . . . . . . . 171.2.2 Aktionen und Akteure . . . . . . . . . . 201.2.3 Eingebettete Systeme . . . . . . . . . . 21
1.3 Prozesse . . . . . . . . . . . . . . . . . . . . . 261.3.1 Rechenprozesse . . . . . . . . . . . . . 271.3.2 Regelungstechnik . . . . . . . . . . . . 31
1.4 Echt und Zeit . . . . . . . . . . . . . . . . . . . 33
1.4.1 Schnelligkeit und Rechtzeitigkeit . . . . 341.4.2 Zeit auf dem Rechensystem . . . . . . . 371.4.3 Echtzeit . . . . . . . . . . . . . . . . . . 40
1.5 Beispiele . . . . . . . . . . . . . . . . . . . . . 41
2 Echtzeitplanung 452.1 Grundlagen der Echtzeitplanung . . . . . . . . 46
2.1.1 Prozessmodelle . . . . . . . . . . . . . 472.1.2 Prozessparameter . . . . . . . . . . . . 542.1.3 Echtzeitplanung . . . . . . . . . . . . . 60
2.2 Planen durch Suchen . . . . . . . . . . . . . . 702.3 Planen nach Fristen . . . . . . . . . . . . . . . 752.4 Planen nach Spielräumen . . . . . . . . . . . . 852.5 Planen nach festen Prioritäten . . . . . . . . . 882.6 Planen nach monotonen Raten . . . . . . . . . 902.7 Planen nach monotonen Fristen . . . . . . . . 992.8 Planen nach dem Server-Modell . . . . . . . . 103
2.8.1 Server für feste Prioritäten . . . . . . . 1052.8.2 Server für dynamische Prioritäten . . . 106
2.9 Zyklische Planungsverfahren . . . . . . . . . . 1072.10 Vergleich der Planungsverfahren . . . . . . . . 109
3 Betriebssysteme 1103.1 Merkmale von Echtzeitbetriebssystemen . . . . 111
i
3.2 Aufbauprinzipien . . . . . . . . . . . . . . . . . 1193.3 Speicherverwaltung . . . . . . . . . . . . . . . 1243.4 Datei und Geräteverwaltung . . . . . . . . . . . 1283.5 Treiber . . . . . . . . . . . . . . . . . . . . . . . 1323.6 Unterbrechungen . . . . . . . . . . . . . . . . . 1363.7 Beispiele für Echtzeitbetriebssysteme . . . . . 139
3.7.1 Solaris . . . . . . . . . . . . . . . . . . . 1403.7.2 VxWorks . . . . . . . . . . . . . . . . . 1413.7.3 QNX . . . . . . . . . . . . . . . . . . . . 1433.7.4 POSIX . . . . . . . . . . . . . . . . . . . 1463.7.5 µITRON . . . . . . . . . . . . . . . . . . 1513.7.6 OSEK/VDX . . . . . . . . . . . . . . . . 0
4 Synchronisierung 24.1 Grundlagen . . . . . . . . . . . . . . . . . . . . 34.2 Prioritätsumkehr . . . . . . . . . . . . . . . . . 134.3 Prioritätsvererbung . . . . . . . . . . . . . . . . 174.4 Prioritätsobergrenzen . . . . . . . . . . . . . . 214.5 Übersicht zur Prioritätsinversion . . . . . . . . 24
5 Rechnernetze 265.1 Grundlagen . . . . . . . . . . . . . . . . . . . . 275.2 Grundlagen . . . . . . . . . . . . . . . . . . . . 28
5.2.1 Formale Strukturen von Rechnernetzen 29
5.2.2 Aufbau von Rechnernetzen . . . . . . . 315.2.3 Drahtgebundene und drahtlose Rech-
nernetze . . . . . . . . . . . . . . . . . 395.3 Zugriffsprotokolle . . . . . . . . . . . . . . . . . 40
5.3.1 Zentralisierte Verfahren . . . . . . . . . 415.3.2 Arbitrationsverfahren . . . . . . . . . . . 425.3.3 Markengesteuerte Verfahren . . . . . . 445.3.4 Zeitmultiplex-Verfahren . . . . . . . . . 455.3.5 Modifikation nicht echtzeitfähiger Zu-
griffsprotokolle . . . . . . . . . . . . . . 465.4 Abschätzung der Echtzeiteigenschaften . . . . 51
5.4.1 Prozesse und Zugriffsprotokolle . . . . 525.4.2 Zeitgesteuerte Zugriffsprotokolle . . . . 585.4.3 Arbitrierende Zugriffsprotokolle . . . . . 625.4.4 Markengesteuerte Zugriffsprotokolle . . 72
6 Planung für Mehrprozessorsysteme 776.1 Einführung und Modellbildung . . . . . . . . . . 786.2 Anwendbarkeit klassischer Planungsverfahren 806.3 Proportional faires Scheduling . . . . . . . . . 936.4 Affinitäten zwischen Prozessen und Prozessoren102
6 Modellbildung 766.1 Entwurfsmuster . . . . . . . . . . . . . . . . . . 77
ii
6.2 Modellierungssprachen und Zustandsautomaten 816.3 Logiken und Algebren . . . . . . . . . . . . . . 826.4 Petri-Netze . . . . . . . . . . . . . . . . . . . . 83
7 Zeiten und Uhren 847.1 Echtzeit und physikalische Zeit . . . . . . . . . 857.2 Uhren und Wecker . . . . . . . . . . . . . . . . 907.3 Uhrsynchronisierung . . . . . . . . . . . . . . . 977.4 Ausführungzeiten von Anweisungen . . . . . . 103
7.5 Ableitung von Zeitbedingungen . . . . . . . . . 104
8 Rechnerarchitekturen und Prozessoren 105
9 Programmiersprachen 106
10 Softwaretechnik 107
11 Nachlese 108
iii
Echtzeitsystemei
Dieter Zöbel 0.0 - 1 1
Kapitel 1
Einführung
Dieses Kapitel befasst sich im Wesentlichen mit
• einer Standortbestimmung zum Fachgebiet Echtzeitsysteme,
• elementaren Begriffen wie harte und weiche Echtzeit,
• grundsätzlichen Abstraktionen wie Prozesse und Zeiten
• und Beispielen für Echtzeitsysteme.
2
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.1 Merkmale von EchtzeitsystemenDieser Abschnitt befasst sich im Wesentlichen mit
• der Eingrenzung auf harte Echtzeitsysteme,
• einem Grundmodell für Echtzeitsysteme
• und seinen formalen Eigenschaften.
Dieter Zöbel 1.1 - 1 2
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Definition des Begriffs Echtzeitsystem
DIN 44300[16]:
Ein Betrieb eines Rechensystems, bei dem Programme zur Verarbeitung anfal-lender Daten ständig betriebsbereit sind, derart, daß die Verarbeitungsergeb-nisse innerhalb einer vorgegebenen Zeitspanne verfügbar sind.
Die Daten können je nach Anwendungsfall nach einer zeitlich zufälligen Vertei-lung oder zu vorherbestimmten Zeitpunkten anfallen.
Neben der semantischen Korrektheit müssen die Rechenergebnisse auch rechtzeitigvorliegen.Beispiele:
• Das Antiblockiersystem (ABS) bei Kraftfahrzeugen
• Steuerung und Überwachung einer Papiermaschine
• Übertragung von Audio- und Videodaten in Rechnernetzen
Dieter Zöbel 1.1 - 2 3
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Alternative Definitionen
eeFurh91 A real-time computer system can be defined as a system that performs itsfunctions and responds to external, asynchronous events within a predictable (ordeterministic) amount of time.
[32] A real-time system is a system that must satisfy explicit (bounded) response-timeor risk severe consequences, including failure.
A failed system is a system which cannot satisfy one or more of the requirementslaid out in the formal system specification.
Dieter Zöbel 1.1 - 3 4
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.1.1 Harte und weiche Echtzeitbedingungen
Öffnungsklauseln für weiche Echtzeitbedingungen
• mit kurzen bzw. zeitbegrenzten Überschreitungen,
• mit einer geringen oder begrenzten Anzahl von Zeitüberschreitungen
Systeme mit weichen Echtzeitbedingungen werden typischerweise mit stochastischenMethoden behandelt (z.B. der Warteschlangentheorie und der Markov-Theorie)Beispiele:
• Anfragen an interaktive Buchungsysteme für Reisen
• Anrufbearbeitung durch ein Call Center
• Maus- und Cursorbewegung von graphischen Objekten
Dieter Zöbel 1.1 - 4 5
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Formulierung einer harten Zeitbedingung
Die Ausführung einer Aufgabe kann typischerweise frühestens mit einem Zeitpunkt rbeginnen und muss vor einem Zeitpunkt d abgeschlossen sein.Die Ausführung der Aufgabe nimmt typischerweise eine mindeste Zeitspanne ∆e inAnspruch.
Als Rechtzeitigkeit (engl.: timeliness) wird die Eigenschaft A bezeichnet:
A ≡ r + ∆e ≤ d
Dieter Zöbel 1.1 - 5 6
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Harte Zeitbedingungen bei einer Anwendung
Anwendung Ball on a Beam: Ziel ist das Ausbalancieren eines Balls auf einer Rinne.
Ein kommerziell vertriebenes Gerät der Firma i-math (Singapur) für didaktischenZwecke, so lassen sich daran beispielsweise unerschiedliche Regelungsalgorthmenherleiten und testen.
Dieter Zöbel 1.1 - 6 7
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Abschwächung einer harten Zeitbedingung
Kann man unter allen Umständen die Einhaltung einer Zeitbedingung zusichern?
nein
Es muss dargelegt werden, unter welchen Bedingungen B die Eigenschaft der Recht-zeitigkeit A zugesichert werden kann.In einem harten Echtzeitsystem ist die Zeitbedingung A bei Vorliegen der günstigenBedingung B unbedingt erfüllt, d.h. es gilt:
P [A | B] = 1
In unmittelbarem Bezug zu der jeweiligen Aufgabenstellung steht B beispielsweisedafür, dass
• weder technische Ausfälle auftreten,
• noch wichtigere Aufgaben zu erledigen sind.
Dieter Zöbel 1.1 - 7 8
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Harte Echtzeitsysteme
Forderungen:
• unter allen Umständenz. B. auch unter extremen Lastsituatio-nen
• keine Zeitüberschreitungenz. B. in keinem einzigen Fall
Hintergründe für die weitgehenden Forde-rungen bei harten Echtzeitsystemen: Si-cherheit = Menge der Maßnahmen zur
Abwendung von Schaden1
• an Leib und Lebenz. B. Antiblockiersystem
• in finanzieller Hinsichtz. B. Produktionsprozesse
• in qualitativer Hinsichtz. B. Übertragungsqualität bei Telefon-gesprächen
1Entspricht den severe consequences bei Laplante [32]
Dieter Zöbel 1.1 - 8 9
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.1.2 Determiniertheit und Vorhersagbarkeit
Vielzitierte Forderung bei Echtzeitsystemen: Determiniertheit, d.h. jeder Berech-nungsschritt ist von vorne herein bekannt ([32]):
A system is said to be deterministic if for each possible state, and each set ofinputs, a unique set of outputs and next state of the system can be determined.
Bereits bei Echtzeitsystemen mittlerer Größe ist es nicht mehr effektiv möglich, Deter-miniertheit herzustellen. Deshalb auch hier eine abgeschwächte Forderung:
Vorhersehbarkeit bzw. Vorhersagbarkeit (engl.: predictability), d. h. die Men-ge möglicher Rechenergebnisse muss feststehen und deren Bereitstellungmuss die vorgegebenen Zeitbedingungen erfüllen.
Dieter Zöbel 1.1 - 9 10
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.1.3 Sicherheit und Zuverlässigkeit
Sicherheit (engl.: safety) im technischen Sinn umfasst alle Maßnahmen eines(Echtzeit-)Systems, die dazu beitragen, Gefahren für Menschen, andere Lebewesenund Gegenstände auszuschließen.Dazu tragen im Einzelnen bei (vgl. [25]):
• Ausschluss von Fehlern und Ausfällen
• Reduzierung der Wahrscheinlichkeit von Fehlern und Ausfällen
• Beeinflussung der Auswirkung von Fehlern und Ausfällen
Insbesondere der letzte der Spiegelpunkte zielt auf die Fehlertoleranz (engl.: failuretolerance), d. h. die Funktionsfähigkeit durch eine redundante Auslegung des Systemsund seiner Teilsysteme zu gewährleisten.
Dieter Zöbel 1.1 - 10 11
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Zuverlässigkeit (1)
Die Zuverlässigkeit (engl.: dependability) ist eine allumfassende Eigenschaft des(Echtzeit-)Systems, das zu leisten, was den Anforderungen entspricht.Bezogen auf die englischen Begriffe subsummiert dependability die Eigenschaften(vgl. [5]): available, reliable, safe, confidential, integral, maintainable2
Die Zuverlässigkeit ist ein Maß dafür, dass ein (Echtzeit-)System seine Anforderungenerfüllt. Ein Echtzeitsystem kann als zuverlässig gelten, wenn das verbleibende Risiko1 − P [B] unter dem Grenzrisiko liegt und sowohl Rechtzeitigkeit, verkörpert durch dieZeitbedingung A, als auch Korrektheit, d.h. die funktionale Richtigkeit des Rechener-gebnisses, nachgewiesen ist.
Damit nimmt man mit 1− P [B] in Kauf, dass die Zeitbedingung A verletzt wird.
2Entsprechende deutsche Begriff sind nicht immer eindeutig zuzuordnen (, wie auch die Bedeutungen der englischen Begriffe nicht eindeutigdefiniert sind), aber hier der Versuch: verfügbar, dauerhaft verlässlich, sicher, vertrauenswürdig, widerspruchsfrei, wartbar.
Dieter Zöbel 1.1 - 11 12
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Zuverlässigkeit (2)
Während das Grenzrisiko ein Wahrscheinlichkeitsmaß darstellt, ist mit dem Begriff Ri-siko (engl.: risk) zweierlei verbunden:
• das Ausmaß des Schadens
• die Wahrscheinlichkeit, dass der Schaden auftritt
Es gibt verschiedene Methoden, um das Risiko zu analysieren und zu bewerten, z.B.mittels Risikographen (vgl. [17])
Für die Zuverlässigkeit spielt es eine große Rolle, ob das System korrekt in Betriebgenommen wurde und es im Verlaufe des Betriebs nicht zu Fehlern und Ausfällenkommt.
Dieter Zöbel 1.1 - 12 13
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Fehler und AusfälleEs finden sich folgende Definitionen (vgl: [38])Fehler (engl.: error): Ein inkorrekter innerer Zustand eines Systems wird als Fehlerbezeichnet. Ein Fehler, der die Grenzen des Systems erreicht und den vom Systemgeleisteten Dienst beeinflusst, ist die Ursache für einen Ausfall.
Ausfall (engl.: failure): Als Ausfall eines Systems wird die Abweichung des von Sy-stem geleisteten Dienstes von seinen spezifizierten und beabsichtigten Diensten be-zeichnet. Der Ausfall eines Systems ist ein Ereignis und wird von der Umgebung desSystems wahrgenommen.
Fehlerursache (engl.: fault): Der Auslöser, durch den ein System in einen unvorher-gesehenen Zustand überführt werden kann, wird als Fehlerursache bezeichnet. EineFehlerursache, die einen Fehler verursacht, wird als aktiv bezeichnet, eine Fehlerur-sache, die keinen Fehler verurschacht, wird als inaktiv bezeichnet.
Dieter Zöbel 1.1 - 13 14
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.2 Das Grundmodell eines Echtzeitsystems
tdr
externes System
internes SystemMesssystem Stellsystem
technisches System
Rechensystem
∆e
Charakteristische Echtzeitbedingung :
P [r + ∆e ≤ d|B] = 1
r Bereitzeit∆e Ausführungszeitd Frist
B Betriebsbedingung:
• Das System operiertfehlerfrei.
• Zur Zeit gibt es nichtsWichtigeres.
Dieter Zöbel 1.2 - 1 15
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.2.1 Paradigmatische Beispiele
Typisch für ein Fachgebiet: Es hat sei-ne kennzeichnenden Paradigmen (vgl.[31]).Eigenschaften:
• fachspezifischer Merkmalsträger
• übertragbares Lösungsschema
• Sichtbarkeit in der Fachwelt
• didaktische Bedeutung
Beispiel: Wippe (ähnlich zu dem in derwissenschaftlichen Welt bekanntenVersuch ball on a beam) Balanciereneiner Kugel auf einer ebenen Fläche
Dieter Zöbel 1.2 - 2 16
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Anwendungsfalldiagramm
• Bestimme Hauptaufgaben aus An-wendungssicht
• Bestimme die Aktoren für jedenAnwendungsfall und die Richtungihrer Einflussnahme
• Dokumentiere jeden Fall nach ei-nem Standardschema
Grobes Schema der Dokumentation
• Anwendungsfall
• Aktor
• Dokumentation
• Randbedingung
Dieter Zöbel 1.2 - 3 17
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Beispiel: Anwendungsfalldiagramm für die Wippe
Dokumentation
• Anwendungsfall autonom balan-cieren
• Aktor Kugel
• Dokumentation Balancieren derKugel ohne menschlichen Eingriff
• Randbedingung die Kugel darf un-ter keinen Umständen von derFläche fallen
Anwendungsfalldiagramm für die Wip-pe.
Dieter Zöbel 1.2 - 4 18
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.2.2 Aktionen und AkteureSchema einer typischen Echtzeitanwendung ausder Sicht der Daten (vgl. [49]):Das Messsystem erzeugt große Datenmengenund das Stellsystem benötigt große Datenmengen,während das Rechensystem auf der Grundlage we-niger, entscheidungsrelevanter Daten den Zustanddes technischen Systems erkennen und entspre-chend eingreifen muss.Der Vorgang wird auch als Steuerfunktion oder con-trol action CA (vgl. u.a. [47]) bezeichnet. Die CA bil-det die zentrale Aufgabe des Rechensystems. Da-vor findet die Datenreduktion und danach die Da-tenexpansion statt.
Dieter Zöbel 1.2 - 5 19
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.2.3 Eingebettete Systeme
(engl.: embedded system)
Der Begriff ist vielfach synonym zum Begriff Echtzeitsystem. Im Gegensatz zumZeitaspekt, der bei Echtzeitsystemen herausgestellt wird, zielt die Begrifflichkeit beiEingebetteten Systemen im Wesentlichen darauf, dass eine oft komplexe Dienst-leistung erbracht wird, ohne dass die Existenz des ausführenden Rechensystemsoffensichtlich ist.
Beispiel: Elektronisches Stabilitätsprogramm (ESP)Verhindern des Ausbrechens von Fahrzeugen bei der Kurvenfahrt durch gezielte Ein-griffe auf das Bremssystem.
Dieter Zöbel 1.2 - 6 20
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Definitionsversuche zu Eingebetteten Systemen
Die Eigenschaft, in einer Anwendungsumgebung aufzugehen, ist ein Kennzeichen voneingebetteten Systemen [20]:
Unter einem eingebetteten System versteht man ein Computersystem, das fe-ster Bestandteil eines Gerätes oder einer Anlage ist und für das Gesamtsystembestimmte funktionale und leistungsmäßige Anforderungen erfüllt.
Mit einem stärkeren Augenmerk auf die Wahrnehmung durch den Benutzer heißt esbei [36]:
Eingebettete Systeme sind informationsverarbeitende Systeme, die in eingrößeres Produkt integriert sind, und normalerweise nicht direkt vom Benut-zer wahrgenommen wird.
Dieter Zöbel 1.2 - 7 21
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Eigenschaften von Eingebetteten Systemen
• Betonung eines technischen Ge-samtsystems, innerhalb dessenein Rechensystem (Mikrocompu-ter) operiert
• Partitionierung der Funktionalität inHard- und Software (oft verknüpftmit Hardware/Software-Codesign,d.h. der integrierten Entwicklungvon Hard- und Softwarearchitektu-ren)
• vielfach synonym zum Begriff Echt-zeitsystem und in vielem vomFachgebiet Echtzeitsysteme abge-deckt
• markante Trennung zwischenWirtssystem (engl.: host) undZielsystem (engl.: target)
Beispiel: Projekt EZauto
Eingebettetes System für dasAutonome Fahren eines Modell-LKW
Dieter Zöbel 1.2 - 8 22
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Weitere Eigenschaften von Eingebetteten Systemennach [7]:
• Eingebettete Systeme erfüllen einespezifische Anwendung.
• Sie werden auf einem für dieseAnwendung geeigneten Prozessorausgeführt.
• Die für Eingebettete Systeme ein-gesetzten Prozessoren sind sehrunterschiedlich und überdeckenein weites Leistungs- und Preis-spektrum.
• Wenn ein Eingebettes System einBetriebssystem benutzt, dann vor-zugsweise ein Echtzeitbetriebssy-stem.
• Sie arbeiten meist unter ein-geschränkten oder außerordent-lichen Bedingungen (z.B. einge-schränkter Stromverbrauch).
• Eingebettete Systeme halten ihrenCode im ROM.
• Das Debugging von Eingebette-ten Systemen erfordert besondereHardware und Software.
Dieter Zöbel 1.2 - 9 23
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Komplexität am Beispiel eines Serienfahrzeugs
Viele Fahr- und Fahrerassistenzsysteme werden in Fahrzeugen durch vernetzte Steu-ergeräte realisiert.
Dieter Zöbel 1.2 - 10 24
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.3 ProzesseAbstraktionsobjekt: Prozess
Vorgang in der Zeit
Allgemeine Bedeutung:Prozesse sind homogene Stellvertreterfür die zu beschreibende Dynamik ei-nes Systems
Starke Wirkzusammenhängebilden einen Prozess, schwa-che Wirkzusammenhängegrenzen Prozesse gegenein-ander ab.
Start
Abschluß
Grundmodell eines Rechenprozesses:endlich, sequentiell,
eigener Zustandsraum
Dieter Zöbel 1.3 - 1 25
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.3.1 Rechenprozesse(Technische Prozesse und Rechenpro-zessea sind über eine Schittstelle mit-einander verbunden.
techn. Prozeß
Schnittstelle
Rechenprozeß
aDer programmiertechnische Prozessbegriff kommt ursprüng-lich aus dem Fachgebiet der Betriebssysteme und ist heute in demeigenständigen Fachgebiet der parallelen Programmierung ange-siedelt (vgl. [51])
Rechenprozess als Abstraktionsob-jekt:
• eine begrenzte Menge von Opera-tionen
• auf einem begrenzten Zustands-raum
Man unterscheidet programmiertech-nisch:
• Prozesstyp
• Prozessobjekt
• Prozessausführung
Dieter Zöbel 1.3 - 2 26
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Bsp.: Maus- und Cursorbewegung von graphischen ObjektenTechnische, menschliche und Rechen-prozesse bilden einen geschlossenenKreis (engl.: closed loop):
Bildschirm
Mensch
Maus
Zeichen-programm
Bildschirm-treiber
Maus-treiber
Schnittstelle
Rechenprozesse
technische
Prozesse
Prozessmodell für die Maus- undCursorbewegung
• Der Maustreiber nimmt ein gera-stertes Bild der Mausbewegungauf.
• Die Rechenprozesse konkurrierenum den Prozessor.
• Es gibt unterschiedliche Wichtig-keiten zwischen den Prozessen.
Dieter Zöbel 1.3 - 3 27
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Bsp: EZautoTechnische, menschliche und Rechenprozesse bilden einen geschlossenen Kreis(engl.: closed loop):
Positionsbestimmung
Steuerung
Antrieb,Lenkung
Sicherheitsmanagement
Grobes Prozessmodell für das autonome Fahren eines Modell-LKW
• Die technische Umgebung gibt Zeitbedingungen vor.
• Die Rechenprozesse konkurrieren um den Prozessor.
• Es gibt unterschiedliche Wichtigkeiten zwischen den Prozessen.
Dieter Zöbel 1.3 - 4 28
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Datenflussdiagramme
Prozesse treten in der Rolle zustands-verändernder Funktionen (Transforma-tionen) auf.
Datenflussdiagramme besitzen Trans-formationen (in Form von Kreisen oderOvalen) und Speicher (in Form offe-ner Rechtecke) sowie Datenflüsse (inForm gerichteter Kanten)
Dieter Zöbel 1.3 - 5 29
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.3.2 Regelungstechnik
Es gibt offensichtliche Analogien zwischen dem Grundmodell eines Echtzeitsystemsund dem Blockdiagramm eines Regelkreises. Beide haben sich jedoch recht un-abhängig entwickelt und stellen völlig unterschiedliche Lösungsansätze dar.
Regelabweichung
+
Messglied
Regler Stellglied
Regler-signal
Strecke
Störungen
Sollwert
(Führungsgröße) -
Istwert
(gemessene Größe)
Regel-größe
Stell-größe
Blockdiagramm eines Reglers, bestehend aus verschalteten Übertragungsgliedern.
Dieter Zöbel 1.3 - 6 30
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Beispiel Wippe
Ein typischer Lösungsansatz für das Problem der Wippe aus regelungstechnischerSicht basiert auf der Verschaltung von Übertragungsgliedern, die zwei verschachtelteRegelkreise enthält (vgl. [11]). In einem inneren Regelkreis wird der Motor, der dieRinne neigt, auf einen Sollwinkel gsoll(t) geregelt. In einem äußeren Regelkreis wirddie Kugel in die Sollposition xsoll(t) gebracht.
-+ +
g ( t )soll g ( t )ist x ( t )istx ( t )soll
i Motor KugelR a.. R i
--
Dieter Zöbel 1.3 - 7 31
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.4 Echt und ZeitDie Redensart in Echtzeit hat Eingang in den allgemeinen Sprachgebrauch gefunden.
Offensichtliche Absicht: Aufwertung von Verfahren und Geräten, die eine große Unmit-telbarkeit in der Erbringung ihres Dienstes aufweisen.
Beobachtung: Es gibt eine inflationäre Benutzung der Redensart in Echtzeit, ohnedass kennzeichnende Kriterien wie Rechtzeitigkeit, Vorhersagbarkeit, Sicherheit undZuverlässigkeit ausreichend nachgewiesen werden.
Dieter Zöbel 1.4 - 1 32
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.4.1 Schnelligkeit und Rechtzeitigkeit
Es wird zwar richtigerweise betont, dass ein Echtzeitsystem nicht durch dieschnellstmöglichen Verfahren, die zur Anwendung kommen, charakterisiert wird (vgl.[44]):
Rather than being fast (which is a relative term anyway), the most importantproperty of a real-time system should be predictability; ...
Aber schnelle Verfahren auf leistungsfähigen Rechnern und Netzwerken bei er-schwinglichen Kosten sind äußerst wichtige Voraussetzungen für die Verbreitung vonEchtzeitanwendungen in vielen Lebensbereichen (vgl. [44]):
Fast computing is helpful in meeting stringent timing specifications, ...
Dieter Zöbel 1.4 - 2 33
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Schnelligkeit
Viele Anwendungen werden erst dadurch sinnvoll und nutzbar, wenn die Berechnungschnell genug ist, damit sie in Echtzeit erfolgen kann.Beispiel: Drei markante Aufgaben sind bei der Verkehrszeichenerkennung im Rahmeneines Fahrerassistenzsystems zu bewältigen:
• Bearbeitung eines Kamenrabildes in zweiSchritten: Erkennung der Gestalt und Klassifi-zierung innerhalb eines Satzes von bekanntenVerkehrszeichen.
• Die Verfolgung der erkannten Verkehrszeichenund die Bestimmung ihrer Lage im Verhältniszum Fahrzeug, das sich auf sie zubewegt.
• Ausgabe zeitnaher und ergonomischer Hinwei-se über die Annäherung an ein Verkehrszei-chen.
detektiertesVerkehrszeichen
akustische undvisuelle Warnzeichen
LKS TSR ACC
MMS
Kamerabild
Ein Kamerabild wird fürunterschiedliche Assi-stenzsysteme genutzt.
Dieter Zöbel 1.4 - 3 34
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Physikalische Zeit
Der naturwissenschaftliche Zeitbegriff ist maßgeblich von der Physik geprägt. Sie istdurch die Relativitätstheorie keine Grundgröße mehr, sondern definiert sich über dieLichtgeschwindigkeit c.
Probleme: Domäne T (kontinuierlich oder diskret?), Normierung, Erfassbarkeit, Ein-deutigkeit
Bei Echtzeitsystemen wird die physikalische Zeit T typischerweise als eine globale,kontinuierliche Größe aufgefasst.
Dieter Zöbel 1.4 - 4 35
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.4.2 Zeit auf dem Rechensystem
Die Zeiterfassung auf dem Rechner geschieht über Uhrbausteine.
Uhrbausteine bestehen aus einem Oszillator der Frequenz f und einem Zähler, der dieSchwingungen des Oszillators zählt.
Typischerweise bietet ein Rechensystem Systemaufrufe an, um zu einem gegebebenZeitpunkt t die Uhrzeit ct(t) abzufragen.
Für die perfekte Uhr cp gilt: cp(t) = t
Dieter Zöbel 1.4 - 5 36
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Uhrzeit
Die Uhrzeit ct ∈ CT ist ein diskreter Wert, der in Rechensystemen zurVerfügung steht, um die physikalische Zeit so eng wie möglich anzunähern.
Diskretisierung: durch einen Oszillator der Frequenz f , z.B. f = 106/sec
Bezugszeitspanne: ∆tG kleinstes Zeitintervall, das (programmier-)technisch zurVerfügung steht.
Ermittlung der Bezugszeitspanne durch Zählen der Oszillatorschwingungen mit einemZähler nG3:
nG = max{n |n/f ≤ ∆tG}Abweichung ρ:
ρ =
∣∣∣∣1− nGf∆tG∣∣∣∣
3Der Zähler nG ist üblicherweise Bestandteil eines Uhrbausteins.
Dieter Zöbel 1.4 - 6 37
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Diskretisierung und Drift
Bei der Abbildung der physikalischenZeit auf die Echtzeit kommt es zu zweiArten von Abweichungen:
• die Drift
• die Diskretisierung
ct : T −→ CT
ct(t) = ct(0) +
⌊nGf∆tG
t
⌋f
n G
t
t
∆t G
ct (t )
ct(t)
Verlauf der Uhrzeit ct(t), aufgetragenüber der physikalischen Zeit t.
Dieter Zöbel 1.4 - 7 38
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.4.3 Echtzeit
In der Mehrzahl der Definitionen wird Echtzeit mit physikalischer Zeit gleichgesetzt(z.B. [9]).
Echtzeit lässt sich darüber hinaus als Abstraktionsbegriff auffassen, der einerseits dieglobale physikalische Zeit zugrundelegt.
Echtzeit ist der Versuch die physikalische Zeit im Rechnensystem verfügbar zumachen.
Andererseits wird Echtzeit als diskrete, vielfach ganzzahlige Größe verstanden, umZeitspannen in der Größe von Bezugszeitspannen zu zählen.
Das Fachgebiet Echtzeitsysteme benutzt den Abstraktionsbegriff Echtzeit insbesonde-re, um zeitliche Aussagen über Verfahren der Planung zu formulieren und abzuleiten.
Dieter Zöbel 1.4 - 8 39
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
1.5 BeispieleKategorisierung von AnwendungsfeldernDer Bereich der Echtzeitsysteme lässt sich grob wie folgt kategorisieren:
• Steuerung, Regelung und Überwachung von Anlagen (z.B. Kraftwerke, Produkti-onsanlagen, Laboraufbauten)
• eingebettete Systeme, d.h. das Rechensystem ist (mehr oder weniger) vollständigintegriert in ein technisches System (z.B. Flugzeugsteuerung, Getriebesteuerung,CD-Spieler)
• Multimedia-Anwendungen (z.B. MPEG-Kompression und -Dekompression, Call-Center, Sprachübertragung in Datennetzen)
Zu jeder dieser Kategorien sind geeignete Methoden aus fast allen Wissensgebietender Informatik gefragt.
Dieter Zöbel 1.5 - 1 40
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Produktionsanlage
Schema einer Papiermaschine mit denMesstellen M1 bis M4 zwischen deneinzelnen Arbeitsvorgängen: Stoffauf-lauf (SA), Vortrocknung (VT), Leim-presse (LP), Nachtrocknung (NT) undAufrollen (AR).
M1 M2 M3 M4
Technische- und assoziierte Rechen-prozesse (entsprechend mit ”Px“ be-zeichnet) der Papiermaschine.
M1 M2 M3 M4
SA VT LP NT AR
P P P P P
P P P P M1 M2 M3 M4
SA VT LP NT AR
Dieter Zöbel 1.5 - 2 41
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Automotive Anwendung (1)
Steuergeräte (engl.: electronic con-trol unit (ECU)) überwachen einzelneFunktionen im Fahrzeug:
Infrastruktur
Kommunikations-system
Mess-system
Stell-system
Anwendungsprozesse
Blockdiagramm eines Steuergerätes.
Die Steuergeräte, die über unter-schiedliche Rechnernetze verbundensind, bilden ein komplexes verteiltesSystem.
Funktional getrennte Fahrzeugbusse:
• Antrieb, z.B Motorsteuerung
• Karrosserie, z.B. Airbag
• Komfort, z.B. Klimaautomatik
Daneben Telematik, Diagnose undWartung.
Navigationssystem
Antiblockiersystem(ABS)
Abstandsregelung(ACC)
Motorsteuerung Klimaautomatik
Türkontrolle
Lenksäulenmodul
Grundmodul
Digitalradio
Diagnosemodul
Drehratengeber
Außenanschluss
Armaturen-tafel
Dieter Zöbel 1.5 - 3 42
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Automotive Anwendung (2)
Mit den Erfordernissen fortgeschrit-tener Fahrerasistensysteme (ADASa)und des autonomen Fahrens reichendie klassischen Strukturen der Vernet-zung im Auto nicht mehr aus. Denn dieLeistungsfähigkeit, insbesondere diedes CAN-Bus, ist nicht für bildgebendeDaten von Kameras, Radar- und Lidar-systemen ausgelegt.
aAdvanced Driver Assistance System
Dieter Zöbel 1.5 - 4 43
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Avionic Anwendung
Steuergeräte (engl.: electronic con-trol unit (ECU)) überwachen einzelneFunktionen im Flugzeug. Sie sind red-undant verbunden über ein Netzwerk,heutiger Standard: AFDXa.Dabei sind die Steuergeräte nicht di-rekt miteinander verbunden, sondernsind als Endgeräte (E) an die AFDX-Übertragungsknoten (SW) angebun-den.
aAvionics Full Duplex Switched Ethernet
Dieter Zöbel 1.5 - 5 44
EchtzeitsystemeKAPITEL 1. EINFÜHRUNG
Internet-Telefonie
Architektur der Sende- und Empfangs-komponente beim Telefonieren überInternet.
Puffern
Dekomprimieren
Wiedergeben
Abtasten
Komprimieren
Formatieren
Transportder Pakete im
Internet
Sende-komponenten
Empfangs-komponenten
Der Ton wird in eine Vielzahl von Ein-zelschritten verarbeitet und transpor-tiert.
Gliederung in Sende- und Empfangs-komponente (vgl. [40])
• einer Sendekomponente, beste-hend aus einer Abtasteinrichtung,die das analoge Signal digitali-siert, sowie einem Verfahren zurKompression und Formatierung inNachrichtenpakete, und
• einer Empfangskomponente, be-stehend aus einem Puffer und Ein-richtungen zur Dekompression undanalogen Wiedergabe der digitalenSignale.
Dieter Zöbel 1.5 - 6 45
Literaturverzeichnis
[1] QNX Operating System. QNX Software Systems Ltd., Kanata,Ontario, Canada, 1997.
[2] G. R. Andrews. Concurrent Programming. The Benja-min/Cummings Publishing Company, 1991.
[3] N. Audsley, A. Burns, M. Richardson, K. Tindell, and A. Wel-lings. Absolute and relative temporal constraints in hard real-time databases. In Proc. of IEEE Euromicro Workshop on RealTime Systems, February 1992.
[4] N. C. Audsley, A. Burns, M. F. Richardson, and A. J. Wellings.Hard real-time scheduling: The deadline monotonic approach.In Proc. 8th IEEE Workshop on Real-Time Operating Systemsand Software, Atlanta, May 1991.
[5] Algirdas Avizienis, Jean-Claude Laprie, Brian Randell, andCarl E. Landwehr. Basic concepts and taxonomy of depen-dable and secure computing. IEEE Trans. Dependable Sec.Comput., 1(1):11–33, 2004.
[6] Sanjoy K. Baruah, N. K. Cohen, C. Greg Plaxton, and Do-nald A. Varvel. Proportionate progress: A notion of fairnessin resource allocation. Algorithmica, 15(6):600–625, 1996.
[7] Arnold Berger. Embedded Systems Design. CMP Books, La-wrence, Kansas 66046, 2002.
[8] Enrico Bini, Giorgio Buttazzo, and Giuseppe Buttazzo. Ratemonotonic scheduling: The hyperbolic bound. IEEE Transacti-ons on Computers, 52(7):933–942, July 2003.
[9] Giorgio C. Buttazzo. Hard Real-Time Computing Systems:Predictable Scheduling, Algorithms and Applications. KluwerAcademic Publishers, 1997.
[10] John Carpenter, Shelby Funk, Anand Srinivasan, James An-derson, and Sanjoy Baruah. A categorization of real-time mul-tiprocessor scheduling problems and algorithms. In JosephY.-T. Leung, editor, Handbook of Scheduling - Algorithms, Mo-dels, and Performance Analysis, pages 30(1)–30(19). Chap-man and Hall, Boca Raton, 2004.
[11] Anton Cervin and Johan Eker. Control-scheduling codesignof real-time systems: The control server approach. Journal ofEmbedded Computing, 1(2):209–224, 2005.
[12] c.L. Liu. Scheduling algorithms for hard real-time system mul-tiprogramming of a single processor. JPL Space ProgramsSummary, II(1):37–60, 1969.
[13] Robert I. Davis and Alan Burns. A survey of hard real-timescheduling for multiprocessor systems. ACM Computing Sur-veys, 43(4):239–272, October 2011.
[14] Robert I. Davis, Alan Burns, Reinder J. Bril, and Johan J.Lukkien. Controller area network (CAN) schedulability ana-lysis: Refuted, revisited and revised. Rael-Time Systems,35(0):239–272, January 2007.
109
EchtzeitsystemeLITERATURVERZEICHNIS
[15] Michael L. Dertouzos. Control robotics: The procedural controlof physical processes. IFIP Congress, pages 807–813, 1974.
[16] Deutsches Institut für Normung. Informationsverarbeitung –Begriffe, DIN 43000. Beuth-Verlag, Berlin, Köln, 1985.
[17] Deutsches Institut für Normung. Funktionale Sicherheit sicher-heitsbezogener elektrischer/elektronischer/programmierbarerelektronischer Systeme, DIN 61508-5. VDE-Verlag, Berlin,1998.
[18] S. K. Dhall and C. L. Liu. On a real-time scheduling problem.Operations Research, 26:127–140, February 1978.
[19] Stuart Faulk, John Brackett, Paul Ward, and James Kirby. Thecore method for real-time requirements. IEEE Software, 9:22–33, September 1992.
[20] Hugo Fierz. Eingebettete Systeme als Architektur mechani-stischer Modelle. www.ciptool.ch/data/cip mech.pdf, ZürcherHochschule Winterthur.
[21] Borko Furht, Dan Grostick, David Gluch, Guy Rabbat, JohnParker, and Meg McRoberts. Real-Time UNIX Systems: De-sign and Application Guide. Kluwer Academic Publishers, Bo-ston, 1991.
[22] Carlo A. Furia, Dino Mandrioli, Angelo Marzenti, and MatteoRossi. Modeling time in computing: a taxonomy and a compa-rative survey. ACM Computing Surveys, 42(2):6:1–6:51, Fe-bruary 2010.
[23] Michael R. Garey and David S. Johnson. Computers and In-tractability. A Guide to the Theory of NP-Completeness. W. H.Freeman and Company, New York, San Francisco, 1979.
[24] A. Gujarati, F. Cerqueira, and B. J. Brandenburg. Multiproces-sor real-time scheduling with arbitrary affinities: From practi-ce to theory. Journal of Real-Time Systems, 51(4):440–483,2015.
[25] W. A. Halang and R. Konakovsky. Sicherheitsgerichtete Echt-zeitsysteme. Oldenbourg-Verlag, München, 1999.
[26] Fred Halsall. Data communications, computer networks, andopen systems. Addison-Wesley, third edition, 1992.
[27] R. G. Herrtwich. Betriebsmittelvergabe unter Echtzeitgesichts-punkten. Informatik-Spektrum, 14(2):123–136, 1991.
[28] R. G. Herrtwich and G. Hommel. Kooperation und Konkurrenz.Nebenläufige, verteilte und echtzeitabhängige Programmsy-steme. Springer-Verlag, Berlin, 1989.
Dieter Zöbel 11.0 - 1 1
EchtzeitsystemeLITERATURVERZEICHNIS
[29] W. A. Horn. Some simple scheduling algorithms. Naval Rese-arch Logistics Quaterly, 21:177–185, 1974.
[30] Hermann Kopetz. Real-Time Systems - Design Principles forDistributed Embedded Applications. Kluwer Academic Publis-hers, Boston, 1997.
[31] Th. S. Kuhn. Die Struktur der wissenschaftlichen Revolutio-nen. Suhrkamp Verlag, Frankfurt, 1969.
[32] Phil Laplante. Real-Time Systems Design and Analysis: AnEngineer’s Handbook. IEEE Press, New York, 1993.
[33] J. P. Lehoczky, L. Sha, and Y. Ding. The rate monotonic sche-duling algorithm: Exact characterization and average case be-havior. In Proceedings of the 10th IEEE Symposium on Real-Time Systems, pages 166–171, December 1989.
[34] Jochen Liedtke. Toward real microkernels. Communicationsof the ACM, 39(9):70–77, September 1996.
[35] C. L. Liu and James W. Layland. Scheduling algorithms formultiprogramming in a hard-real-time environment. Journal ofthe ACM, 20(1):46–61, January 73.
[36] Peter Marwedel. Eingebettete Systeme. Springer-Verlag, Ber-lin, 2007.
[37] A. K. Mok. Fundamental design problems of distributed sy-stems for the hard-real-time environment. PhD thesis, Massa-chusetts Institute of Technology, 1983.
[38] Philipp Nenninger. Vernetzung verteilter sicherheitsrelevanterSysteme im Kraftfahrzeug. Dissertation, Universität Karlsruhe,2007.
[39] Ulrich Rembold and Paul Levi. Realzeitsysteme zur Prozeß-automatisierung. Hanser Verlag, München, 1994.
[40] Sebastian Rieger. Streaming-Media und Multicasting in draht-losen Netzwerken. Technical Report Nr. 61, Gesellschaft fürwissenschaftliche Datenverarbeitung mbH Göttingen, 2003.
[41] Ken Sakamura. µITRON 3.0 – An open and portable real-timeoperation system for embedded systems. Los Alamitos, Cali-fornia, USA, ieee computer society press edition, 1998.
[42] Kenneth C. Sevcik and Marjory J. Johnson. Cyclic time pro-perties of the FDDI token ring protocol. IEEE Transactions onSoftware Engineering, 13(3):376–385, March 1987.
[43] Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky. Prio-rity inheritance protocols: An approach to real-time synchro-nisation. IEEE Transactions on Computers, 39(9):1175–1185,September 1990.
Dieter Zöbel 11.0 - 1 1
EchtzeitsystemeLITERATURVERZEICHNIS
[44] John A. Stankovic. Misconceptions about real-time computing:A serious problem for next generation systems. IEEE Transac-tions on Computers, 21(10):10–19, 1988.
[45] Mark J. Stanovich, Theodore P. Baker, and An-I Andy Wang.Throtteling on-disk schedulers to meet soft-real-time require-ments. In Real-Time and Embedded Technology and Appli-cation (RTAS’08), pages 331–341, St. Louis, Missouri, April2008. IEEE Computer Society.
[46] A. S. Tanenbaum. Computer Networks. Prentice-Hall Interna-tional Editions, Englewood Cliffs, NJ, second edition, 1988.
[47] Martin Törngren. Fundamentals of implementing real-timecontrol applications in distributed computer systems. Real-Time Systems, 14:219–250, 1998.
[48] Victor Varshavsky. Time, timing and clock in massively par-allel computing systems. In Third International Conferenceon Massively Parallel Computing Systems (PCS98), ColoradoSprings, Colorado, April 6-9 1998.
[49] Dieter Zöbel. Echtzeitsysteme - Grundlagen der Planung. eX-amen.press. Springer-Verlag, Berlin, 2008.
[50] Dieter Zöbel and Wolfgang Albrecht. Echtzeitsysteme -Grundlagen und Techniken. Lehrbuch. International ThomsonPublishing Company, Bonn, Albany, 1995.
[51] Dieter Zöbel and Horst Hogenkamp. Konzepte der parallelenProgrammierung. Teubner-Verlag, Stuttgart, 1988.
Dieter Zöbel 11.0 - 1 1