Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
Echtzeit-betriebssysteme
Prof. Dr. Dieter Zöbel
Universität Koblenz-LandauFachbereich Informatik, Institut für Softwaretechnik
Rheinau 1D-56075 Koblenz
http://www.uni-koblenz.de/˜zoebel
11. Dezember 2001
I
Inhaltsverzeichnis
1 Einf ührung 1
1.1 Grundmodell eines Echtzeitsystems . . . . . . 1
1.2 Prozesse . . . . . . . . . . . . . . . . . . . . . 7
1.3 Zeiten . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Betriebssysteme . . . . . . . . . . . . . . . . . 13
2 Echtzeitplanung 18
2.1 Grundlagen der Echtzeitplanung . . . . . . . . 18
2.2 Planen nach Fristen . . . . . . . . . . . . . . . 27
2.3 Planen nach monotonen Raten . . . . . . . . . 31
3 Synchronisierung 35
3.1 Grundlagen . . . . . . . . . . . . . . . . . . . . 35
3.2 Prioritätsumkehr . . . . . . . . . . . . . . . . . 37
3.3 Protokolle gegen die Prioritätsumkehr . . . . . 40
4 Betriebssysteme 43
4.1 Merkmale von Echtzeitbetriebssystemen . . . . 43
4.2 Aufbauprinzipien . . . . . . . . . . . . . . . . . 49
4.3 Speicherverwaltung . . . . . . . . . . . . . . . 53
II
4.4 Dateiverwaltung . . . . . . . . . . . . . . . . . 55
4.5 Treiber . . . . . . . . . . . . . . . . . . . . . . . 58
4.6 Unterbrechungen . . . . . . . . . . . . . . . . . 62
5 Beispiele 65
5.1 Solaris . . . . . . . . . . . . . . . . . . . . . . . 65
5.2 QNX . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3 POSIX . . . . . . . . . . . . . . . . . . . . . . . 69
5.4 µITRON . . . . . . . . . . . . . . . . . . . . . . 71
5.5 OSEK/VDX . . . . . . . . . . . . . . . . . . . . 74
6 Zusammenfassung 76
III
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
1 Einf ührung
1.1 Grundmodell eines Echtzeitsystems
DIN 44300[DIfN85]:
Ein Betrieb eines Rechensystems, bei dem Program-me zur Verarbeitung anfallender Daten ständig be-triebsbereit sind, derart, daß die Verarbeitungser-gebnisse innerhalb einer vorgegebenen Zeitspanneverfügbar sind.
Die Daten können je nach Anwendungsfall nach einerzeitlich zufälligen Verteilung oder zu vorherbestimm-ten Zeitpunkten anfallen.
Neben der semantischen Korrektheit müssen die Rechener-gebnisse auch rechtzeitig vorliegen.
Beispiele:
• Das Antiblockiersystem (ABS) bei Kraftfahrzeugen• Steuerung und Überwachung einer Papiermaschine• Übertragung von Audio- und Videodaten in Rechnernet-
zen
Dieter Zöbel 1.1 1
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Harte und weiche Echtzeitbedingungen
Öffnungsklauseln für weiche Echtzeitbedingungen
• mit kurzen bzw. zeitbegrenzten Überscheitungen,• mit einer geringen oder begrenzten Anzahl von Zeitüber-
schreitungen
Systeme mit weichen Echtzeitbedingungen werden typischer-weise mit stochastischen Methoden behandelt (z.B. der War-teschlangentheorie und der Markov-Theorie)
Beispiele:
• Anfragen an interaktive Buchungsysteme für Reisen• Anrufbearbeitung durch ein Call Center
Dieter Zöbel 1.1 2
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Harte Echtzeitsysteme
Forderungen:
• unter allen Umst ändenz. B. auch unter extremen Lastsituationen
• keine Zeit überschreitungenz. B. in keinem einzigen Fall
Anwendungsspezifische Hintergründe für die weitgehendenForderungen bei harten Echtzeitsystemen: Abwendung vonSchaden
• an Leib und Lebenz. B. Antiblockiersystem
• in finanzieller Hinsichtz. B. Produktionsprozesse
• in qualitativer Hinsichtz. B. Übertragungsqualität bei Telefongesprächen
Dieter Zöbel 1.1 3
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Das Grundmodell eines Echtzeitsystems
technisches System
Rechensystem
Alarmsystem MeßsystemStellsystem
externesSystem
internesSystem
Charakteristische Echtzeitbedingung1:
P [r + ∆t ≤ d|B] = 1
r Bereitzeit∆t Ausführungszeitd Frist
B Betriebsbedingung:
• Das System operiert fehlerfrei.• Zur Zeit gibt es nichts wichtigeres.
1Für harte und weiche Echtzeitsysteme
Dieter Zöbel 1.1 4
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Vorhersagbarkeit
Vielzitierte Forderung bei Echtzeitsystemen ([Lap93]):
Determiniertheit , d.h. jeder Berechnungsschritt istvon vorne herein bekannt.
Bereits bei Echtzeitsystemen mittlere Größe ist es nicht mehreffektiv möglich, Determiniertheit herzustellen. Deshalb abge-schwächte Forderung:
Vorhersehbarkeit bzw. Vorhersagbarkeit (engl.: pre-dictability), d. h. die Menge möglicher Rechenergeb-nisse muss feststehen und deren Bereitstellung mussin zeitlichen Grenzen liegen.
Eine weitere wichtige Forderung zielt auf Fehlertoleranz(engl.: failure tolerance) z.B. hoher Ausfallsicherheit durch red-undante Auslegung des Rechensystems.
Dieter Zöbel 1.1 5
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Eingebettete Systeme
(engl.: embedded system)
• Betonung der Umgebung, innerhalb deren ein Rechensy-stem operiert.
• vielfach synonym zum Begriff Echtzeitsysteme• vom Fachgebiet Echtzeitsysteme abgedeckt• markante Trennung zwischen Wirtssystem (engl.: host)
und Zielsystem (engl.: target)
Abbildung 1: Projekt EZauto : Autonome Steuerung eines Modell-LKW mit Hilfe eineseingebetteten Systems
Dieter Zöbel 1.1 6
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
1.2 Prozesse
Abstraktionsobjekt: Prozess
Vorgang in der Zeit
Allgemeine Bedeutung:Prozesse sind homogene Stellvertreter für die zu beschrei-bende Dynamik eines Systems
Starke Wirkzusammenhänge bilden einen Prozess,schwache Wirkzusammenhänge grenzen Prozessegegeneinander ab.
Start
Abschluß
Abbildung 2: Grundmodell eines Rechenprozesses: endlich, sequentiell, begrenzter Zu-standsraum
Dieter Zöbel 1.2 7
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Prozesse in der Informatik
(Rechen-)Prozesse2
techn. Prozeß
Schnittstelle
Rechenprozeß
Abbildung 3: Darstellung des Grundmodells mit Prozessen
• eine begrenzte Menge von Operationen• auf einem begrenzten Zustandsraum
Man unterscheidet programmiertechnisch:
• Prozesstyp• Prozessobjekt• Prozessausführung
2Der programmiertechnische Prozessbegriff kommt ursprünglich aus dem Fachgebiet der Betriebssy-steme und ist heute in dem eigenständigen Fachgebiet der parallelen Programmierung angesiedelt (vgl.[ZH88])
Dieter Zöbel 1.2 8
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Bsp: EZauto
Technische, menschliche und Rechenprozesse bilden einegeschlossen Kreis (engl.: closed loop):
Positionsbestimmung
Steuerung
Antrieb,Lenkung
Sicherheitsmanagement
Abbildung 4: grobes Prozessmodell für die autonome Steuerung des Modell-LKW
• Die technische Umgebung gibt Zeitbedingungen vor.• Die Rechenprozesse konkurrieren um den Prozessor.• Es gibt unterschiedliche Wichtigkeiten zwischen den Pro-
zessen.
Dieter Zöbel 1.2 9
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
1.3 Zeiten
Typische Unterscheidung:
PT physikalische ZeitProbleme: Normierung, Erfassbarkeit, Eindeutigkeit, Rela-tivität
RT Echtzeitder in Echtzeitsystemen benutzte Zeitbegriff
LT logische (virtuelle) Zeitdie in Simulationen verwendete Zeitbegriff, z. B. bei derSimulation meteorologischer Abläufe
Algebraische Unterscheidung:
physikalische Zeit EchtzeitPT ⊆ R RT ⊆ N
Dieter Zöbel 1.3 10
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Echtzeit
Die Echtzeit ist ein diskreter Wert, der in Rechensy-stemen zur Verfügung steht, um die physikalische Zeitso eng wie möglich anzunähern3.
Diskretisierung: durch einen Oszyllator der Frequenz f , z.B.f = 1010/sec
Bezugszeitspanne: ∆tG kleinstes Zeitintervall, das program-miertechnisch zur Verfügung steht.Ermittlung der Bezugszeitspanne durch Zählen der Oszylator-schwingungen mit einem Zähler nG4:
nG = max{n|n/f ≤ ∆tG}Abweichung δ:
δ =
∣∣∣∣∣∣1−nGf∆t
∣∣∣∣∣∣
3In der Mehrzahl der Definitionen wird Echtzeit mit physikalischer Zeit gleichgesetzt (z.B. [But97]).4Der Zähler nG ist üblicherweise Bestandteil eines Uhrbausteins.
Dieter Zöbel 1.3 11
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Physikalische Zeit und Echtzeit
Bei der Diskretisierung kommt es zu zwei Arten von Abwei-chungen zwischen der physikalischen Zeit und der Echtzeit:
• die Drift• die Rasterung
t
fnG
rt(t)
∆ Gt
t
t
Abbildung 5: Verlauf der Echtzeit rt über der physikalischen Zeit t
rt : PT −→ RTrt(t) = rt(0) +
nGf∆tG
t
Dieter Zöbel 1.3 12
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
1.4 Betriebssysteme
Allgemeine Aufgabe von Betriebssystemen:
Nutzbamachung des Rechensystems für die Benutzerund die Anwendungen
Aufgaben im einzelnen:
• ergonomische Benutzerschnittstelle• Ausnutzung der Leistungsfähigkeit• Schutz der Benutzer und Anwendungen untereinander• Bereitstellung einer breiten Palette von Dienstleistungen• Abstraktion von technischen Einzelheiten• :• :
Dieter Zöbel 1.4 13
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Echtzeitgesichtspunkte von Betriebssystemen
Betriebssystem+
Vorhersagbarkeit+
Skalierbarkeit+
Zeitverwaltung+
: : : :
Echtzeitbetriebssystem
Kategorisierung:
• Echtzeitbetriebssystemez.B. QNX, pSOS, VxWORKS, ...
• Laufzeitsystemez.B. RTKernel, Ada runtime system
• Standardschnittstellenz.B. POSIX, ITRON
Dieter Zöbel 1.4 14
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Spezifische Merkmalevon Echtzeitbetriebssystemen
Ziel: Schaffung der Voraussetzungen, dass jede Zeitbedin-gung individuell eingehalten werden kann.
Merkmale im einzelnen (vgl. auch [RL93], [ZA95], [WF96] und[LG99]) :
• prioritätsbezogene Prozessausführung• garantierte Reaktionszeiten auf Ereignisse hin• Verfügbarkeit der Unterbrechungsbehandlung auf Anwen-
dungsebene
• hochauflösende Zeitverwaltung• vorhersagbare Zeitspannen beim Zugriff auf Betriebsmittel
(Speicher, Dateien, ... )
• flexible Einbindung unterschiedlichster Geräte• Anbindung an echtzeitfähige Kommunikationssysteme
Dieter Zöbel 1.4 15
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Weitere Merkmale vonEchtzeitbetriebssystemen
Sicht von Software-Entwicklern:
• Ausführung von Plänen• software-technische Unterstützung bei der Entwicklung
von eingebetteten Systemen
– Software-Entwurf
– Methoden der Zeitanalyse
– Synchronisierungsoperationen
• Integration in eine Entwicklungsumgebung– Download-Mechanismen
– Remote Debug
– Monitoring und Test
• Erfüllung von Software-Standards (z.B. POSIX)
Dieter Zöbel 1.4 16
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Kategorisierung von Anwendungsfeldern
Der Bereich der Echtzeitsysteme lässt sich grob wie folgt ka-tegorisieren:
• Steuerung, Regelung und Überwachung von Anlagen(z.B. Kraftwerke, Produktionsanlagen, Laboraufbauten)
• eingebettete Systeme, d.h. das Rechensystem ist (mehroder weniger) vollständig integriert in ein technisches Sy-stem (z.B. Flugzeugsteuerung, Getriebesteuerung, CD-Spieler)
• Multimedia-Anwendungen (z.B. MPEG-Kompression und-Dekompression, Call-Center, Sprachübertragung in Da-tennetzen)
Zu jeder dieser Kategorien sind geeignete Betriebssystemeund Rechnerarchitekturen gefragt.
Dieter Zöbel 1.4 17
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
2 Echtzeitplanung
2.1 Grundlagen der Echtzeitplanung
Betrachtung: Ein Rechensystem mit einem Prozessor, aufdem die Prozesse zur Ausführung gelangen.
Prozesse bei Echtzeitsystemen:
Eine sequentielle und endliche Ausführung von Be-rechnungschritten auf einem begrenzten Zustands-raum.
Start
Abschluß
Dieter Zöbel 2.1 18
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Unterbrechbare und nicht unterbrechbare Prozesse
Abhängig von der Planungsstrategie oder dem zugrundelie-genden Ausführungssystem unterscheidet man zwischen:
• nicht unterbrechbaren (engl.: non preemptive) Prozessen,die vom Start bis zu ihrem Ende nicht (sichtbar) unterbro-chen werden können und
• unterbrechbaren (engl.: preemptive) Prozessen, diegrundsätzlich nach jedem Berechnungsschritt unterbro-chen werden können.
Mit einer Prozessumschaltung (engl.: context switch) wird derProzessor einem Prozess entzogen und einem anderen zuge-teilt.
Dieter Zöbel 2.1 19
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Prozessbeschreibende Gr ößen
Geg.: Prozessobjekt Pi5
Bereitzeit (engl.: ready time): ri Frühestmöglicher Zeitpunktfür die Ausführung von Pi auf dem Prozessor.
Ausführungszeit (engl.: execution time): ∆ti Die maxima-le Zeit, die die Berechnung von Pi auf dem Prozessorbenötigt.
Frist (engl.: deadline): di Zeitpunkt, zu dem die Ausführungdes prozesses Pi spätestens zu Ende sein muss.
5Pi steht stellvertretend auch für die j-te Ausführung des Prozesses Pi, d.h. für Pji .
Dieter Zöbel 2.1 20
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Weitere prozessbeschreibende Gr ößen
Startzeit (engl.: starting time): si Zeitpunkt des Beginns derAusführung von Pi.
Abschlusszeit (engl.: completion time): ci Zeitpunkt des En-des der Ausführung von Pi.
∆ei
ri=si ci di
Abbildung 6: Zeitdiagramm einer unterbrochenen Ausführung des Prozesses Pi auf einemProzessor
Dieter Zöbel 2.1 21
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Wiederholungseigenschaften von Prozessen
• periodische ProzesseBsp.: Anstoß der Prozessausführung, nachdem der Laser-Scanner auf dem Modell-LKW eine Positionserkennungdurchgeführt hat, d.h. alle 1/6 ms.
• aperiodische ProzesseBsp.: Die Unterbrechungsanforderungen (engl.: interrupt),die von der Bewegung einer Maus ausgehen.
• sporadische ProzesseBsp.: Anstoß der Prozessausführung durch einen Kontakt-geber am Zahnkranz eines Kraftstoffmotors.
• Prozesse mit AltersanforderungenBsp.: Das interne Abbild eines Ausschnittes der realenWelt darf nicht älter sein als eine vorgegebene Zeitspan-ne.
Dieter Zöbel 2.1 22
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Fristen bei periodischen Prozessen
Periode (engl.: period): ∆pi Die Periode definiert für ein Pro-zessobjekt Pi das Zeitintervall, in dem sich die Bereitzeitfür seine Ausführung wiederholt.
• Frist = Periode6Die Periode definiert den Rahmen für die j-te Ausführungvon Pi:
rji = (j − 1)∆pi + r1i j ≥ 1dji = j∆pi + r
1i
= rj+1i
• Frist ≤ PeriodeDie Ausführung von Pi muss schon bis zur Frist beendetsein.
• Frist ≥ PeriodeDie Ausführung von Pi darf die Periode bis zum Erreichender Frist überschreiten.
6Die häufigste Form der Echtzeitplanung bei periodischen Prozessen mit Fristen
Dieter Zöbel 2.1 23
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Echtzeitplanung
Ein Plan (engl.: schedule) für eine Menge von Prozessobjek-ten P = {P1, ..., Pn}7 ist eine diskrete Abbildung
s : N −→ {0, ..., n}Dabei besagt s(i) = j, dass sich der Prozessor im Intervall[(i − 1)∆tG, i∆tG) im Besitz des Prozesses j befindet bzw. fürj = 0 gerade nicht belegt ist.
1 1 1 2 2 1 1 0 0 0 1 1 1 3 3 3 1 1... ...
∆tG
Abbildung 7: Schema eines Planes für die Zuordung der Prozesse zu einem Prozessor
7Im folgenden immer nur als Menge von Indizes geführt: P = {1, ..., n}
Dieter Zöbel 2.1 24
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Darstellung von Pl änen
explizit: Es gibt eine vollständige Abbildung, die angibt, wel-cher Prozess von t1 bis t2 auf dem Prozessor auszuführenist.
Pi
t1 t2
Bei Implementierungen sind die an sich unendlichenPläne durch endliche (kurze) Anfangsstücke zu repräsen-tieren, die zyklisch ausgeführt werden.
implizit: Jedem Prozess wird eine feste Priorität zugeordnet(engl.: fixed priority scheduling) und nach dem Prinzipder priorit ätsbasierten Prozessausf ¨ uhrung wird jeweilsderjenige Prozess rechnend , der von den rechenberei-ten die höchste Priorität besitzt.
Dieter Zöbel 2.1 25
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Brauchbarkeit und Optimalit ät
Dieter Zöbel 2.1 26
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Definition: Ein (statischer) Plan für eine Menge von Pro-zessobjekten P = {1, ..., n} heißt brauchbar (engl.: feasi-ble), falls sämtliche Zeitbedingungen eingehalten werden.
Mit dem Nachweis der Existenz eines brauchbaren Planes istnoch kein solcher Plan gefunden.
Definition: Ein (statisches) Plansverfahren heißt optimal, fallses zu einer Menge von Prozessobjekten P = {1, ..., n}einen (expliziten oder impliziten) Plan findet, wenn ein sol-cher existiert.
2.2 Planen nach Fristen
Eignung:
• für unterbrechbare und nicht unterbrechbare Prozesse• in statischen und dynamischen Planungsverfahren
Stategie (EDF8):
Teile den Prozessor jeweils demjenigen rechenberei-ten Prozess i zu, dessen Frist den kleinsten Wert hat9.
8(engl.: earliest deadline first)9Variante: Planen nach Spielräumen (engl.: laxity). Hier wird der Prozessor demjenigen Prozess i zu-
geteilt, dessen Spielraum, d.h. ∆laxi = (di − ri)−∆ei, am kleinsten ist.
Dieter Zöbel 2.2 27
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Planen nach Fristen bei unterbrechbaren Prozessen
Betrachtungszeitpunkt t:
• Wenn ein Prozess i bereit wird: ri• Wenn ein Prozess i seine Berechnung beendet hat: ci
Verfahren EDF 10 Der Prozessor wird demjenigen rechenbe-reiten Prozess zugeteilt, dessen Frist zum Zeitpunkt t diekürzeste ist. Die Dauer ∆l der Prozessorzuteilung ist be-stimmt durch das Minimum aus
• der zum Zeitpunkt t verbleibenden Ausführungszeit,• der nächsten Bereitzeit eines anderen Prozesses.
10vgl. [ZA95] S. 38,39
Dieter Zöbel 2.2 28
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Periodische Prozesse
Gegegeben: Eine Prozessmenge P = {1, ..., n} unterbrechba-rer, periodischer Prozesse mit Fristen gleich Perioden (genau-er: di = ri + ∆pi)
Eigenschaften:
• Ein Prozess ist gekennzeichnet durch seine Ausführungs-zeit ∆ei und seine Periode ∆pi11.
• (Prozessor-)Auslastung:
U =∑i∈P
∆ei∆pi
• Notwendiges Merkmal für die Existenz eines brauchbarenPlans: U ≤ 1
• Pläne sind zyklisch und Wiederholen sich spätestens nachkgV {∆p1, ..., ∆pn} Zeiteinheiten.
11Die erste Bereitzeit r1i eines Prozesses kann jeden Wert annehmen.
Dieter Zöbel 2.2 29
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Ergebnisse des Planens nach Fristen bei periodischenProzessen
Lemma [LL73] Gegeben sei die Menge P = {1, ..., n} unter-brechbarer, periodischer Prozesse. Wenn es nach demPlanen nach Fristen zu einer Fristüberschreitung kommt,so kann davor kein Intervall existieren, in dem der Prozes-sor nicht zugeteilt wurde.
Satz Unterbrechbare, periodische Prozesse werden nachdem Planen nach Fristen brauchbar verplant, wenn gilt:
U ≤ 1
Dieter Zöbel 2.2 30
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
2.3 Planen nach monotonen Raten
Anstelle eines expliziten Planes werden den Prozessen Prio-ritäten zugeordnet (impliziter Plan).
Definition Die Rate eines Prozesses i ist der Kehrwert seinerPeriode.
RMS12 Regel:
Je kürzer die Periode eines Prozesses, um so höherseine Priorität.
rms : P −→ ZDabei muss für i, j ∈ P gelten13:
rms(i) < rms(j) ⇐⇒ 1∆pi
<1
∆pj
12(engl.: rate monotonic scheduling)13Konvention: i < j ⇐⇒ rms(i) < rms(j), d.h. der Prozeß mit höchstem Index hat auch die höchste
Priorität.
Dieter Zöbel 2.3 31
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Vorbereitende Ergebnisse des Planens nach monotonenRaten
Definition Unter dem kritischen Zeitpunkt eines Prozessesi versteht man diejenige Bereitzeit rki , die abhängig vonden Bereitzeiten aller übrigen Prozesse die Abschlußzeitcki maximal werden läßt. Entsprechend heißt [r
ki , c
ki ] kriti-
sches Intervall.
Lemma [LL73] Für einen Prozeß i ∈ P ist ein kritischer Zeit-punkt rki immer dann gegeben, wenn die Bereitzeiten allerhöher priorisierten Prozesse auf rki fallen.
Satz [LL73] (Optimalit ät von RMS) Sei P eine Prozeßmen-ge, für die eine gefundene Prioritätszuordnung bereitseinen brauchbaren Plan liefert. Dann wird auch die Prio-ritätszuordung nach monotonen Raten einen brauchbarenPlan liefern.
Dieter Zöbel 2.3 32
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Kleinste obere Schranke der Auslastung Umin
Es geht um die Frage, bis zu welcher Auslastung Umin14 beimPlanen nach monotonen Raten immer noch ein brauchbarerPlan gefunden wird.
Satz [LL73] Gegeben sei eine Menge P = {1, ..., n} unter-brechbarer, periodischer Prozesse, die nach monotonenRaten eingeplant werden sollen. Dann gilt:
Umin(n) = n(
n√
2− 1)
n ≥ 2
Korollar Es gilt:lim
n→∞n(
n√
2− 1)
= ln(n)
Tabelle der Auslastung Umin(n) :n 2 3 4 5 10 ∞
Umin(n) 0.828 0.780 0.757 0.743 0.718 0.690
14An anderer Stelle (z.B. [But97]) abgekürzt als Ulub (engl.: least upper bound).
Dieter Zöbel 2.3 33
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Bedeutung des Planens nach monotonen Raten
Vorteilhafte Eigenschaften, die RMS zum verbreitetsten Pla-nungsverfahren haben werden lassen:
• einfache Prüfung der Brauchbarkeit• einfache Darstellung durch Prioritätszuordnung• ausführbar auf jedem prioritätsbasierten Betriebssystem
bzw. Laufzeitsystem
• leichte Integration der Zeit für die notwendigen Prozes-sumschaltungen (durch Vorwegabzug von z.B. 5 %)
Nachteile:
• verschenkt erhebliche Prozessorleistung• verzögert wichtige Prozesse vor hochpriorisierten Prozes-
sen
Dieter Zöbel 2.3 34
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
3 Synchronisierung
3.1 Grundlagen
Ziel:
Auf der Grundlage handhabbarer und wohlverstande-ner Operationen sollen korrekte parallele Programmeentwickelt werden
Grundoperationen der Synchronisierung:
• Verzögern eines Prozesses, sofern seine Fortsetzung dieKorrektheit gefährden würde
• Anstoßen eines Prozesses, sobald seine Fortsetzung dieKorrektheit nicht mehr gefährdet
Zentrale Bedeutung: das kritische Gebiet
In einem kritischen Gebiet darf sich zu einem Zeit-punkt höchstens ein Prozess aufhalten.
Dieter Zöbel 3.1 35
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Methoden der Synchronisierung
Kategorisierung (vgl.: [ZH88], [HH89] und [And91]):
• elementare Synchonisierungsmethoden (z.B. nach Peter-son)
• Hardware-unterstützte Synchronisierungsoperationen(z.B. spin locks)
• Semaphore (bei fast allen Echtzeitbetriebssystemen)• Regions (z.B. in iRMX)• Monitore (z.B. in Java)• Nachrichtenübertragung (z.B. in QNX)• Fernaufrufe (z.B. in Ada)
Dieter Zöbel 3.1 36
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
3.2 Priorit ätsumkehr
Die parallelen Prozesse eines Echtzeitsystems sind nicht un-abhängig voneinander, sondern kooperieren miteinander, z.B.mittels gemeinsamer Daten. Zur Einhaltung der Konsistenzsind Zugriffe auf Daten zu synchronisieren.
E(cs)
L(cs)
Kritisches Gebiet cs
Betreten
Verlassen
Abbildung 8: Kritische Gebiete zur Erhaltung der Datenkonsistenz
Vorrangregel: Die Synchronisierungsbeziehungen dominie-ren die Prioritätsbeziehungen.
Dieter Zöbel 3.2 37
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Echtzeitbedingungen
(a) Echtzeitbedingungen bei unabhängigen Prozessen:
P [ri + ∆ei +n∑
j=i+1
∆pi∆pj
∆ej ≤ di|
√] = 1
(b) Echtzeitbedingungen bei Prozessen mit kritischen Gebie-ten:
s
1
Prozesse
3
2
s
s s
s
Legende
rechnend:
rechenbereit:
blockiert:
Abbildung 9: Zeitdiagramm für zwei Prozesse mit einem kritischen Gebiet s
P [ri + ∆ei +n∑
j=i+1
∆pi∆pj
∆ej +
i−1∑j=1
∆sj ≤ di|√] = 1
Dabei gibt ∆si für einen Prozess i an, wieviel Zeit er maxi-mal in einem seiner kritischen Gebiete verbringt.
Dieter Zöbel 3.2 38
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Priorit ätsumkehr
Die Prioritätsumkehr (engl. priority inversion) führt dazu, dassein Prozess mittlerer Priorität einen Prozess höherer Priorität,der wegen eines kritischen Gebietes blockiert ist, beliebig lan-ge verzögern kann [LR80].
1
Prozesse
3
2
s
s
Abbildung 10: Zeitdiagramm für zwei Prozesse mit einem kritischen Gebiet s
Die Prioritätsumkehr verletzt die Echtzeitbedingung. Die Vor-hersagbarkeit des Verhaltens geht verloren.
Dieter Zöbel 3.2 39
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
3.3 Protokolle gegen die Priorit ätsumkehr
wichtigste Protokolle (vgl. [SRL90])
• Prioritätsvererbung (engl. priority inheritance PIP)• Priortätsobergrenze (engl. priority ceiling PCP)
Grundidee allgemein: Ein höher priorisierter Prozess, derwegen eines kritischen Gebietes blockiert wird, verleihtseine Priorität an den oder diejenigen niedriger priorisier-ten Prozesse, die durch ihr Verlassen von kritischen Ge-bieten, die Fortsetzung des höher priorisierten Prozessesso schnell wie möglich erlauben.
Grundidee der Priorit ätsvererbung: Kritische Gebiete, diefrei sind, können betreten werden. Ist ein kritisches Ge-biet bereits belegt, dann wird der anfordernde Prozessblockiert und vererbt seine Priorität an die Prozesse dieihn direkt oder indirekt blockieren.
Grundidee der Priorit ätsobergrenze: Ein freies kritischesGebiet wird von einem Prozess nur dann betreten, wenner in der Folge nicht mehr von einem Prozess niedrigererPriorität blockiert werden kann.
Dieter Zöbel 3.3 40
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Schema der Priorit ätsvererbung
1
Prozesse
s
s
3
2
3
s
1
s
s
Abbildung 11: Durch die Vererbung der Priorität von Prozess 3 an Prozess 1 ist Prozess2 nicht mehr in der Lage den Prozess 3 beliebig lange zu verzögern.
Dieter Zöbel 3.3 41
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Praktische Bedeutung
Mittlerweile verfügt die Mehrzahl der Echtzeitbetriebsystemebzw. Laufzeitsysteme für Echtzeitprogrammiersprachen nacheigenen Angaben über Protokolle zur Prioritätsvererbung oderzur Prioritätsobergrenze15.
— PIP PCP andereBetriebs- AIX iRMX OS/Open pSOSsysteme OS-9 LynxOS OSEK/VDX Nucleus Plus
RMOS OS/Open ERCOS :WindowNT QNX
: Solaris :Tornado
VxWorksWindowsCEVRTX
: :POSIX 1003.4RTOS-UH :
Pearl RTKernelLaufzeit- Java virtual PERC’s Java : :
system machine virtual machine Ada 95 C-Executive
15Eine breite Übersicht findet sich im WWW unter http://www.realtime-info.be/encyc/market/rtos/rtos.html
Dieter Zöbel 3.3 42
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
4 Betriebssysteme
4.1 Merkmale von Echtzeitbetriebssystemen
Allgemeine Zielsetzung: Nutzbarmachung des Rechners
• ergonomische Benutzeschnittstelle• Ausnutzung der Fähigkeiten, insbesondere der Lei-
stungsfähigkeit
• Anpassung an wechselnde Aufgabenstellungen
Abbildung 12: Das Betriebssystem als Mittler
Dieter Zöbel 4.1 43
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Merkmale von Echtzeitbetriebssystemen
• Durchreichen von Unterbrechungsanforderungen (prio-ritätsabhängig) an die Anwendungsprogramme
• Mehrprogrammbetrieb mit der Möglichkeit der anwen-dungsspezifischen Zuordnung von Prioritäten
• Bereitstellung einer effizienten Zeit- und Weckverwaltung• einstellbare Zeitauflösung (Bezugszeitspanne ∆tG)• Überwachung der Einhaltung von Echtzeitbedingungen• Unterbrechbarkeit des Kerns (bzw. von Systemaufrufen)• asynchrone E/A-Operationen• Verhersagbarkeit der Zugriffsdauer auf Plattendatei-
en durch entsprechende Organisation (z.B. zusam-menhängende Folgen von Dateiblöcken)
• Möglichkeit zur Abschaltung der virtuellen Speicherver-waltung (z.B. zur Vermeidung unvorgesehener Seitenaus-tausche)
Dieter Zöbel 4.1 44
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Genealogie der Echtzeitbetriebssysteme
Kategorisierungsschemata
• Grad der Offenlegung: proprietär (z.B. iRMX) ↔ offen16(z.B. REAL/IX)
• Herkunft: Eigenentwickeltes Echtzeitbetriebssystem (z.B.QNX)↔ Integration von Echtzeitmerkmalen (z.B. AIX) ↔Weiterentwicklung eines Betriebssystems zu einem Echt-zeitbetriebssystem (z.B. LynxOS)
• Plattformabhängigkeit:– aus Betriebssystem-Sicht: Microsoft basiert (z.B. RTX-
DOS, EUROS) ↔ UNIX-basiert (z.B. pSOS)– aus Hardware-Sicht: Bindung an Prozessoren oder
an Boards: PC-basiert (z.B. RMOS, QNX) oder Intel-basiert (z.B. iRMX)
• Ausbaustufe: Ausführungssystem für parallele Prozesse(engl.: executive) (z. B. RTKernel) ↔ vollständig ausge-bautes Betriebssystem (z.B. Solaris)
16offen in dem Sinne, dass es herstellerunabhängige Standards wie POSIX.4 erfüllt
Dieter Zöbel 4.1 45
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Entwicklungslinien von Echtzeitbetriebssytemen
Standard BeispieleeigenständigeEntwicklung
proprietär iIRMXOS/9
angelehntan UNIX
offen QNX, REAL/IX
angelehnt an Mi-crosoft
vorwiegend pro-prietär
EUROS,WindowsCE
integriert in einuniversellesBetriebssystem
offen, proprietär Solaris, Ada
angelehnt an denPC
eher proprietär QNX, iRMX,WindowsCE
Dieter Zöbel 4.1 46
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Vor und Nachteile einer Anlehnung an ein vorhandenesBetriebssystem
Vorteile:
• größere Akzeptanz bei den Entwicklern• Verfügbarkeit von komfortablen Werkzeugen und Schnitt-
stellen (z.B. make, awk oder graphische Benutzerober-flächen)
Nachteile:
• Probleme mit der Größe und der Skalierbarkeit• Probleme mit der Rechtzeitigkeit
Dieter Zöbel 4.1 47
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Wie wird UNIX ein Echtzeitbetriebssystem?
• unterbrechbarer, skalierbarer Kern (ist für ein Echtzeitbe-triebssystem neu zu entwickeln)
• Bereitstellung einer hohen Zeitauflösung• prioritätsbasierte Prozessausführung• Ergänzung um leichtgewichtige Prozesse• Verhinderung des Seitenaustausches• kalkulierbare Zugriffszeiten auf Plattendateien• Erfüllung von Standards, z.B. POSIX 1003.1 und POSIX
1003.4
Dieter Zöbel 4.1 48
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
4.2 Aufbauprinzipien
Definition Der Kern ist der Teil des Betriebssystems, der un-verzichtbar für dessen Funktionalität ist.
Kategorisierung:
• Makrokern: Wesentliche Funktionalitäten des Betriebssy-stems sind im Kern zu finden (typischerweise monolithi-scher Aufbau, z.B. UNIX)
• Mikrokern: nur die notwendigste Funktionalität zum Be-treiben von Betriebssystemkomponenten gehört in denKern (alle Dienstleistungen, die Dateiverwaltung, Spei-cherverwaltung und Geräteverwaltung liegen außerhalbdes Kerns, z.B. QNX)
Umsetzung der Echtzeitanforderung der Unterbrechbarkeitdes Kerns (bzw. der Systemaufrufe):
• bei Makrokernen: durch Sollbruchstellen• bei Mikrokernen: durch minimalisierte Dienste des Kerns
Dieter Zöbel 4.2 49
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Vor- und Nachteile der Mikrokern-Architektur
Vorteile:
• Sichere Kapselung der Komponenten (Prozesse) einesBetriebssystems (durch die Speicherverwaltung)
• definierte Schnittstelle zum Kern (API), insbesondere zumZwecke des Interprozesskommunikation (IPC17)
• klare Trennung von Funktionalitäten zwischen Kern undden Prozessen, bzw. unter den Prozessen (Dienst- wieAnwenderprozesse)
• Skalierbarkeit, Anpassungsfähigkeit, Erweiterbarkeit undDynamik (z.B. Nachladen von Betriebssystemprozessenzur Laufzeit)
• Einfache Anpassung an neue Rechnerplattformen (durchden Austausch von Treibern und ggf. des Kerns)
Nachteil: (Noch) hoher Aufwand (vgl. [Lie96])
17(engl.: inter-process communication)
Dieter Zöbel 4.2 50
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Interprozesskommunikation (IPC)
Paradigma: Ein Betriebssystem und die umgebendenAnwenderprozesse kommuniziern mittels Nachrichten(transparent realisiert durch den Kern) miteinander.
Zentrale Aufgabe des Kerns: Abwicklung der Nachrich-tenübertragung
Vorteile:
• homogener Systemaufbau: Es gibt nur Prozesse.• klare Objektstruktur: Dientleistung und damit Datenma-
nipulation nur durch Methodenaufrufe an das Dienstlei-stungsobjekt.
Dienstprozess
Mikrokern
Anwenderprozess . . . . . .
Dieter Zöbel 4.2 51
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Bsp.: Mikrokernarchitektur von QNX
Scheduler
Interprozesskommunikation
NetzwerkschnittstelleInterrupt Redirector
ProzessProzess
Prozess
Netzan-bindung
Abbildung 13: Blockdiagramm zur Softwarearchitektur des Echtzeibetriebssystems QNX
Minimaler Umfang des Kerns für einbettete Anwendun-gen: ≈ 130KByte (nach Angaben von QNX: 64KByte[Qnx97]). Zusätzlich: IDE-Treiber 40KByte, Plattentreiber(fdisk) 130KByte
Dieter Zöbel 4.2 52
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
4.3 Speicherverwaltung
Adressierungsformen:
• direkte Adressierung• virtuelle Adressierung
– Lauffähigkeit großer Programme
– Schutz der Prozesse untereinander
– Segment- und/oder Seiteverwaltung basierend auf ei-ner MMU (memory management unit)
– Seitenaustauchverfahren (Dauer ≈ 200.000 Zugriffeauf den Hauptspeicher)
Probleme bzgl. Vorhersagbarkeit
• beim Anlaufen des Programms werden die Daten nachBedarf nachgeladen
• beim laufenden Betrieb kommt es zu unverhofften Seiten-austauschen
Dieter Zöbel 4.3 53
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Speicherverwaltung mit vorhersagbaren Ausf ¨ uhrungszei-ten
Vorkehrungen:
• Laden aller Programmseiten vor dem Programmstart• Vorbelegen von Hauptspeicher für die Stapel und Haufen• Vermeidung von dynamischen Speicherplatzanforderun-
gen
• Verbieten von Seitenaustauschen• Vermeiden des Kopierens von großen Datenmengen zwi-
schen Prozessen
Bsp.: Entsprechende Befehle unter dem Echtzeitbetriebs-system REAL/IX:
• stkexp() für das Vorbelegen von Speicher für den Stapel• plock() für das Verbieten von Seitenaustauschen
Dieter Zöbel 4.3 54
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
4.4 Dateiverwaltung
hier: Vorhersagbarkeit beim Zugriff auf die Festplatte:
• Zeitschranken für einzelne Lese- und Schreibzugriffe• Priorisierung von Zugriffsanforderungen• periodische Anforderungen von großen Datenmengen
(hauptsächlich bei Multimedia-Anwendungen)
Ursachen mangelnder Vorhersagbarkeit:
• Form der Auftragsabarbeitung durch den Treiber• Suchzeit für die Spur• Wartezeit auf den Sektor
weniger:
• Übertragung der Daten zum Controller• Abwicklung der Systemaufrufe
Dieter Zöbel 4.4 55
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Vorhersagbare Zugriffszeiten
Klassische Verfahren ohne Vorhersagbarkeit:
• FCFS (first come, first served)• SSTF (shortest seek time first)• SCAN (seq. Suchen nach der nächsten Spur)
Ziele unter Echtzeitgesichtspunkten:
• Einhalten der Fristen• Vermeiden von Übertragungslücken• hoher Grad an paralleler Auftragsabwicklung
Beachte:
• hoher Durchsatz und die Sicherung von Zeitbedingungensind konträre Ziele
• Eigenfunktionalität des Plattencontrollers und Topologieder Platte ist (oftmals) für den Treiber nicht offengelegt.
Dieter Zöbel 4.4 56
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Strategie f ür vorhersagbare Plattenzugriffe
SCAN-EDF (z.B. unter AIX)
• Zuordnung einer Frist für jeden Auftrag• Anwendung von EDF bzgl. der Frist der Aufträge −→ Ein-
haltung der Frist
• Anwendung des SCAN-Algorithmus für Aufträge mit glei-cher Frist −→ hoher Durchsatz
Bsp.: SCAN-EDF angewendet auf Aufträge der Form(Frist,Spur):(10, 201) → (10, 214) → (10, 235) → (10, 194) → (10, 176) →(11, 180)→ (11, 204)→ (11, 214) → (11, 239)
Dieter Zöbel 4.4 57
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
4.5 Treiber
Abstrakte Schnittstelle zu einem Gerät: Aus Anwendersicht istder Treiber ein Teil der Hardware, wie aus Treibersicht der Un-terbrechungprozess ein Teil der Hardware ist.
Zuordnung der Treiber
• bei Makrokernen: Teil des Kerns
Dieter Zöbel 4.5 58
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
• bei Mikrokernen: als ein Prozess (oder mehrere), mit ei-ner speziellen Priorität und einer standardisierten Schnitt-stelle, kann dynamisch zum Betriebssystem hinzugefügtwerden
Dieter Zöbel 4.5 58
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Anstoßen des Treibers
Man unterscheidet (vgl. [RL93])
• Initiator: nimmt den Auftrag an das ihm zugeordnete Gerätan, prüft die Auftragsparameter und reiht den Auftrag in dieWarteschlage ein.
• Kontinuator: arbeitet den nächsten Auftrag aus der Warte-schlange ab, sobald das Gerät über eine Unterbrechungs-anforderung die Fertigmeldung für den letzten Auftrag ge-geben hat.
Programmschema für einen Treiber, der über Nachrichten vonSeiten der Anwendung beauftragt und von Seiten des GerätesFertigmeldungen erhält:
DOwait for(msg,sender)// verarbeite ’msg’ von ’sender’
OD
Dieter Zöbel 4.5 59
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Auswirkungen der Mikrokern-Architektur
Entwicklungstendenzen
• Die Unterbrechungsbehandlung so kurz wie möglich (so-mit Verkürzung der Zeitdauer, die nicht vom Kern aus, d.h.der Prozessverwaltung aus, steuerbar ist.
• Einheitliche Anstoßmechanismen für Treiber wie für ande-re Prozesse, insbesondere was die Unterbrechungsanfor-derungen angeht.
Dieter Zöbel 4.5 60
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Abbildung 14: Die Prozesse, die bei Solaris einen Treiber aufbauen
Übertragung von Nutzdaten vom Hauptspeicher zumGerät
• I/O-mappedGetrennter Adressraum für Geräte und Zugriff über eigeneBefehle (z.BIN und OUT). Synchrone Auftragsabwicklungund Fertigmeldung des Gerätes via Interrupt
Dieter Zöbel 4.5 61
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
• memory mappedDer Speicher des Gerätes ist Teil des physikalischenAdressraumes, ggf. direkter Zugriff des Prozessors desperipheren Gerätes in den Hauptspeicher (z.B. geschütztdurch spin locks)
• DMA (direct memory access)Ein DMA-Controller ist über einen eigenen Bus mit demHauptspeicher verbunden. Autonome Abwicklung des Auf-trags und Fertigmeldung durch Interrupt.
Dieter Zöbel 4.5 61
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
4.6 Unterbrechungen
Grundsätzliche Zielsetzung: Unterbrechung des normalen Ab-laufs durch eine vorrangige Verarbeitung.
Klassen von Unterbrechungen
• Asynchron (interrupts) z.B.:– Timerinterrupt
– Meldung eines Spannungsausfalls
– Abschluss des Plattenzugriffs
– Abschluss des Sendens einer Nachricht
• Synchron (traps) z.B.:– arithmetische Fehler
– Seitenfehler
– Verletzung des Speicherschutzes
– Systemaufrufe
Dieter Zöbel 4.6 62
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Formen der Unterbrechungsbehandlung
Ablauf
1. Der Prozessor beendet die Ausführung des letzten Be-fehls (Unterbrechung18 des aktuellen Prozesses).
2. Die Ausführung des Prozessors wird auf den Unterbre-chungsprozess umgeschaltet.
3. Der Unterbrechungsprozess (ISR19) wird ausgeführt.
4. Durch einen speziellen Befehl wird die Rückkehr vomUnterbrechungsprozess zum aktuellen Prozess durch-geführt.
Treiber
Ein-/Ausgabe-
gerat..
Unterbrechungs-prozeß
Ein-/Ausgabe-
system
Betriebs-system
Abbildung 15: Der Unterbrechungsprozess kann aus programmiertechnischer Sicht alseine Komponente der Hardware aufgefasst werden.
18Man unterscheidet asynchrone Unterbrechungen (engl.: interrupt) von synchronen Unterbrechungen(engl.: traps)
19(engl.: interrupt service routine)
Dieter Zöbel 4.6 63
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Latenzen bei der Unterbrechungsbehandlung
Die Unterbrechungslatenz (engl.: interrupt latency) umfasstalle Zeitspannen vom Zeitpunkt der Auslösung der Unterbre-chung bis zum Beginn der Ausführung des Unterbrechungs-prozesses (Schritte 1. und 2.)
• Bsp.: unter LynxOS auf einem 33MHz Intel 386: 75µs• Bsp.: unter QNX auf einem 33MHz Intel 386: 15µs• Bsp.: unter QNX auf einem 133MHz Intel Pentium: 4.3µs
Strategie: Abarbeitung der ISR als Prozess des Echtzeitbe-triebssystems −→ Verzögerung für einen höher priorisiertenProzess: die Unterbrechungslatenz
Dieter Zöbel 4.6 64
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
5 Beispiele
5.1 Solaris
Merkmale:
• Universalbetriebssystem• unterbrechbarer Kern• Threadkonzept• klassenspezifische Prioritäten• Mehrprozessorfähigkeit• Synchronisierungsobjekte: mutex, r/w-lock, countingsemaphor, condition variable
• Prioritätsvererbung
Interrupt Threads
Realtime Threads
System Threads
TimesclicedThreads
0
59
99
159
dynamic priorities
fixed priorities
Abbildung 16: Prozessklassen von Solaris
Dieter Zöbel 5.1 65
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
5.2 QNX
Merkmale
• Mikrokern-Betriebssystem• Skalierbarkeit• extern: Dateiverwaltung, Netzwerkverwaltung, graphische
Oberfläche
• Interprozesskommunikation mittels synchroner Nachrich-tenübertragung (send(), receive(), reply())
• Netzwerktransparenz (TCP/IP-basiert: WAN, LAN, CAN,serielle Schnittstelle)
• prioritätsbasierte Prozessausführung• Prioritätsvererbung• einstellbare Zeitauflösung• PC-Plattform
Dieter Zöbel 5.2 66
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
synchrone Nachrichten ¨ ubertragung
Prinzip der synchronen Nachrichtenübertragung: Das Sendenund Empfangen von Nachrichten ist eine gemeinsame Opera-tion von Sender und Empänger, d.h. keiner kann dem anderenvorauslaufen.
Funk-modem
Steuer-ung
Antrieb,Lenkung
Laser-scanner
Laserdaten
Fahrdaten
Logdaten
Eingreifdaten
Abbildung 17: Funktionale Zerlegung von EZauto
Synchrone Nachrichtenübertragung heißt auch: beide Pro-zesse müssen gleichzeitig zur Nachrichtenübertragung be-reit sein. Das ist unmöglich, wenn Prozesse ereignisgesteuertsind oder unterschiedlich Perioden besitzen (hohe Wartezei-ten, Gefahr von Deadlock).
Dieter Zöbel 5.2 67
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Entwurf mit Briefk ästen
Zur Vermeidung von Deadlocks dienen Breifkästen (engl.:mailbox), die eine asynchrone Nachrichtenübertragung zwi-chen Prozessen realisieren.
Funk-modem
Steuer-ung
Antrieb,Lenkung
Laser-scanner
Logdaten
Eingreif-daten
Fahr-daten
Laser-daten
TimerTimer
Timer
Timer
Abbildung 18: Entwurf von EZauto mit den 4 ursprünglichen Prozessen, 4 Briefkästen und4 Timern
Dieter Zöbel 5.2 68
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
5.3 POSIX
Ziel: Schaffung von Kompatibilitäten, was die Portabilität von
• Code• Programmen• Daten (im Rahmen von Kommunikation)
angeht. Wichtigster Standard für Echtzeitsysteme: POSIX20
Zielsetzung der IEEE: Definition einer anwendungsspezifi-schen Programmierschnittstelle (API21) zum Betriebssystem(nicht notwendigerweise UNIX)
Working Groups CharterPOSIX.0 Open-system architecturePOSIX.1 Posix application interfacePOSIX.2 Shell and command utilitiesPOSIX.3 Testing and verification methodsPOSIX.4 Real-time extensions to POSIXPOSIX.5 Ada binding to POSIX.1... ...POSIX.13 Realtime application environment profilesPOSIX.14 Multiprocessing application environment profiles... ...POSIX.20 Ada binding to POSIX.4POSIX.21 Distributed real-time
20(engl.: portable operating system interface for computer environments)21(engl.: application programmers interface)
Dieter Zöbel 5.3 69
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
POSIX.4
Merkmale
• Thread22-Konzept• prioritätsbasierte Prozessausführung• Semaphore• hauptspeicherresidente Prozesse• gemeinsamer Hauptspeicher für Prozesse• Echtzeituhren• asynchrone Ein/Ausgabe
Vergleich
Prozess Thread
kann mehrere Threads enthalten ist einem Prozess zugeordnet
eigener Adressraum gemeinsamer Adressraum
besitzt Betriebsmittel z.B. offeneDateien
teilt Betriebsmittel mit den ande-ren Threads des Prozesses
Kommunikation mit anderen Pro-zessen über Pipes oder Nachrich-ten
Kommunikation mit anderenThreads über den gemeinsamSpeicher
22dt. Faden
Dieter Zöbel 5.3 70
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
5.4 µITRON
Ansatz: Offener Standard für die Entwicklung kleiner undkleinster engebetteter Systeme (Japan seit 1984, z.Zt. Version3.0 [Sak98]) TRON23-Philosophie:
Intelligent Objekte werden uns bald umgeben und un-sere alltäglichen Helfer sein.
Anwendungsbereiche (nach eigenen Angaben nur zivile Nut-zung):
• Audio/Video-Elektronik: Fernseher, Videokameras, Digi-talkameras
• Telekommunikation: Anrufbeantworter, Handies, ATM-Switches
• Datenverarbeitung: Infrarot-Druckerschnittstelle, Scanner• Automotive: Navigationssysteme, Einspritzung, Komfort-
funktionen
• Weiße Ware: Mikrowelle, Waschmaschine, Reis-Kocher• Spielzeug: Tamagoshi, sprechende Puppen, funkgesteu-
ertes Spielzeug
23Acronym aus: The Real-time Operating system Nucleus
Dieter Zöbel 5.4 71
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
TRON-Prinzipien
Vorrangige Ziele:
• höchstmögliche Leistung des zugrundeliegendenMikroprozessor- oder Mikrocomputersystems
• Anpassungsfähikeit an spezielle (integrierte) Peripherie• hohe Software-Produktivität durch ein spezielles (Lern-
und) Beschreibungskonzept der Systemaufrufe
• Kostenminimierung im Hardware-Bereich (Größenord-nung: wenige Euros)
• Amortisierung der Entwicklungskosten durch hohe Stück-zahlen
Zweitrangiges Ziel: Portabilität von Software
Typische Rechnerplattformen 24:
• Mikrocontroller MCU (micro controller units): Prozessor,RAM, ROM, A/D-Wandler, weitere Peripherie auf demChip (z.B. 32KByte ROM und 1KByte RAM)
• Mikroprozessoren MPU (micro processor units)Unterstützte Bitbreiten: 4, 8, 16, 32
24Beobachtung: Die Anzahl der verbauten MCUs ist etwa 10-mal so hoch wie die Zahl der verbautenMPUs (letztere z.B. in PCs)
Dieter Zöbel 5.4 72
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
TRON Standards
Bereiche: Scheduling, Synchonisierung, Fehler-Codes, Termi-nologie
Bsp.: Aufrufe nach dem Schema xxx yyy
cre tsk Erzeugen eines Prozesses
wup tsk Wecken eines Prozesses
wai sem P-Operation auf ein Semaphor
dis int Sperren von Interrupts
set tim Setzen eines Weckers
Prozess-verwaltung
Prozess-verwaltung
Prozess-verwaltung
Mailboxen Semaphore
Semaphore
Semaphore
dyn. Speicher-verwaltung
dyn. Speicher-verwaltung
Ereignis-signalisierung
Ereignis-signalisierung
Ereignis-signalisierung
Anpassung an den Prozessor
Reduktion auf die Erfordernisse der Anwendung
Abbildung 19: Anpassung der µITRON-Spezifikation an den Prozessor und die Anwen-dung
Dieter Zöbel 5.4 73
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
5.5 OSEK/VDX
Ziele von OSEK25/VDX:
• Portabilität und Wiederverwendbarkeit (gezielt fürSoftware-Anwendungen in Kraftfahrzeugen)
• Spezifikation abstrakter Schnittstellen bzgl. Echtzeitanfor-derungen, Kommunikation und Netzwerkmanagement
• Spezifikation abstrakter Schnittstellen zur Hardware• Skalierbarkeit der Implementierung auf das von der An-
wendung aus Notwendige
• Verifikation der FunktionalitätPartner (u.a.):
• Autoindustrie: BMW, Opel, Mercedes, Volkswagen,Renault, Fiat, Volvo
• Elektroindustrie und Zulieferer: Siemens, Philips, SGSThomson, Hella, Lucas, Bosch
• EDV: Windriver Systems, Integrated Systems• Wissenschaft: Universität Karlsruhe
25Akronym für offene Syteme und deren Schnittstelle zur Elektronik im Kraftfahrzeug
Dieter Zöbel 5.5 74
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
”automotive“ Merkmale• vollkommene Statik des Betriebssystems (z.B. alle Be-triebsmittel und Synchronisierungsobjekte vorab bekannt)
• statische Prioritätsvergabe und Prioritätsobergrenzen(PIP)
• präzises Modell für die Prozessausführung und Unterbre-chungsbehandlung (3 Kategorien von Unterbrechungs-routinen)
• generative Erzeugung der Laufzeitumgebung• Reduzierbarkeit auf RAM/ROM- Anwendungen• Anpassbarkeit an kleinste Prozessoren (≥ 8 Bit)
Untrebrechungs-behandlung
Systemfunktionen
Bereich derAnwendungsprozesse
festePriori-taet
hoch
niedrig
Abbildung 20: Prozessmodell
Dieter Zöbel 5.5 75
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
6 Zusammenfassung
Stand der Technik:
• Große Auswahl leistungsfähiger Betriebssysteme für un-terschiedliche Anwendungsfelder im Bereich der Echtzeit-systeme
• Aufgreifen von Konzepten und Methoden der Theorieder Echtzeitsysteme durch die Hersteller von Echtzeitbe-triebssystemen
• Bestrebungen zur Standardisierung, insbesondere auf derEbene von Systemaufrufen
Mängel beim jetzigen Stand der Technik
• Durchgängigkeit bei den Phasen der Software-Entwicklung (Analyse↔ Entwurf ↔ Implementierung)
• Leichtferigkeit ggf. Irreführung im Umgang mit feststehe-ned Begriffen (Latenzzeiten, Prioritätsvererbung, ... )
• Testbarkeit von Versprechungen der Hersteller von Echt-zeitbetriebssystemen (Test-Suiten, Benchmarks, ... )
Dieter Zöbel 6.0 75
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
Literatur
[And91] G. R. Andrews. Concurrent Programming. The Ben-jamin/Cummings Publishing Company, 1991.
[But97] G. C. Buttazzo. Hard Real-Time Computing Sy-stems: Predictable Scheduling, Algorithms and Ap-plications. Kluwer Academic Publishers, 1997.
[DIfN85] Deutsches Institut für Normung. Informationsverar-beitung – Begriffe, DIN 43000. Beuth-Verlag, Berlin,Köln, 1985.
[HH89] R. G. Herrtwich and G. Hommel. Kooperationund Konkurrenz. Nebenläufige, verteilte und echt-zeitabhängige Programmsysteme. Springer-Verlag,Berlin, 1989.
[Lap93] Phil Laplante. Real-Time Systems Design and Analy-sis: An Engineer’s Handbook. IEEE Press, New York,1993.
[LG99] Rudolf Lauber and Peter Göhner. Prozessautomati-sierung. Springer-Verlag, Berlin, 3. edition, 1999.
[Lie96] Jochen Liedtke. Toward real microkernels. Commu-nications of the ACM, 39(9):70–77, September 1996.
[LL73] C. L. Liu and James W. Layland. Scheduling algo-rithms for multiprogramming in a hard-real-time envi-
Dieter Zöbel Literatur 76
Echtzeitbetriebssysteme
infk
oin
fko
UniversitätKoblenz-Landau
InformatikFachbereich
ronment. Journal of the ACM, 20(1):46–61, January73.
[LR80] B. W. Lampson and D. D. Redell. Experiences withprocesses and monitors in mesa. Communicationsof the ACM, 23(2):105–117, February 1980.
[Qnx97] QNX Operating System. QNX Software SystemsLtd., Kanata, Ontario, Canada, 1997.
[RL93] Ulrich Rembold and Paul Levi. Realzeitsysteme zurProzeßautomatisierung. Hanser Verlag, München,1993.
[Sak98] Ken Sakamura. muITRON 3.0 – An open and por-table real-time operation system for embedded sy-stems. Los Alamitos, California, USA, ieee computersociety press edition, 1998.
[SRL90] Lui Sha, Ragunathan Rajkumar, and John P. Le-hoczky. Priority inheritance protocols: An approachto real-time synchronisation. IEEE Transactions onComputers, 39(9):1175–1185, September 1990.
[WF96] Jörg Wollert and Jörg Fiedler. atp-MarktanalyseEchtzeitbetriebssysteme. Automatisierungstechni-sche Praxis, 38:33–44, 1996.
Dieter Zöbel Literatur 77
[ZA95] Dieter Zöbel and Wolfgang Albrecht. Echtzeitsyste-me - Grundlagen und Techniken. Internat. ThomsonPubl., Bonn, Albany, 1995.
[ZH88] Dieter Zöbel and Horst Hogenkamp. Konzepte derparallelen Programmierung. Teubner-Verlag, Stutt-gart, 1988.
78