03 - Real-Time Operating Systems

Question 1

Welche Betriebssystem-Arten gibt es?

Answer 1

• General Purpose Operating Systems (GPOS): für “normale” Computer
• Real-Time Operating Systems (RTOS): für embedded Computer

Question 2

Warum brauchen Embedded Systems ein spezielles Betriebssystem?

Answer 2

Normale OS haben mehr Overhead und keine Zeitbasis, darum ist timing ein Problem.

Question 3

Was sind Schlüssel-Eigenschaften und Anforderungen an Real-Time Operating Systeme? (5)

Answer 3

• Deterministic temporal behavior
• Processing of external events with short response times
• Low resource usage: Energieeffizienz, Kompaktheit
• Reliability
• Scalability

Question 4

Was ist ein Prozess?

Answer 4

• Grundlage für parallele oder quasi-parallele Ausführung von Programmen
• enthält Programm in Ausführung und seinen Zustand (dynamisch)

Question 5

Was ist ein Programm?

Answer 5

Ist eine Sequenz von Statements (statisch).

Question 6

Was ist das Ziel der Concurrency in Embedded Systems?

Answer 6

Das Ziel ist Aktualität, weder zu früh noch zu spät.

Question 7

Welche Prozess-Zustände gibt es? (6)

Answer 7

• Created: Datenstrukturen sind erstellt, Ressourcen und Initialisierung erforderlich
• Ready: bereit für Zuweisung an Prozessor
• Running: im Besitz des Prozessors, bis der Scheduler die Entfernung einleitet
• Blocked: Warten auf ein Ereignis (z.B. Beendigung eines anderen Prozesses, Unterbrechung)
• Suspended: Prozess blockiert durch Betriebssystem oder anderen Prozess
• Dead: Beendigung von außen oder unabhängige, zugewiesene Ressourcen noch verfügbar

Question 8

Was umfasst das Prozess-Management?

Answer 8

• eine Liste für jeden Prozess-Zustand
• Zustandsübergänge durch Entfernung und Wiedereintritt
• Prozess Scheduler

Question 9

Was macht der Prozess Scheduler?

Answer 9

• Entfernen den Prozess aus der ready Liste und weisen ihn dem Prozessor zu
• Scheduling Entscheidungen umfassen Zeiten und Prozesse für die Prozessor-Zuweisung
• zuständig für Kontextwechsel: Speichern/Wiederherstellen des Registerinhalts

Question 10

Wofür ist die Timer Interrupt Service Routine zuständig?

Answer 10

Für die Abfertigung eines Prozesses.

Question 11

Wie läuft die Abfertigung eines Prozesses ab? (9)

Answer 11

• Interrupts deaktivieren
• Status (Register) im aktuellen Prozessdeskriptor speichern
• Speichern der Rücksprungadresse vom Stack für den aktuellen Prozess
• bestimmen, welcher Prozess ausgeführt werden soll (Scheduling)
• Wenn es derselbe ist, Interrupts aktivieren und return
• Prozesszustand in Maschinenregister kopieren
• ersetzen des Programmzählers auf dem Stack für den neuen Prozess
• Interrupts aktivieren
• return

Question 12

Was ist Sampling?

Answer 12

Unter Sampling (Abtastung) versteht man die periodische Abfrage des Zustands einer RT-Einheit durch einen Computer.

Question 13

Was ist ein Abtastintervall?

Answer 13

Die Zeit zwischen den Abtastpunkten wird als Abtastintervall bezeichnet.

Question 14

Wie wird die Länge des Abtastintervalls festgelegt?

Answer 14

Die Länge des Abtastintervalls wird durch die Dynamik der real-time Entity bestimmt.

Question 15

Was ist der Unterschied beim Sampling zwischen States und Events?

Answer 15

• States (Zustände) können durch Abtasten beobachtet werden

* Events (Ereignisse) müssen in einem Speicherelement (memory element, ME) gespeichert werden

Question 16

Was ist ein Interrupt?

Answer 16

• ist ein Hardware-Mechanismus, der periodisch (nach jeder Instruktion) den Zustand
einer spezifischen Signal Line überwacht

• wenn die Line aktiv ist, während der Interrupt nicht deaktiviert ist, wird die Kontrolle vom aktuellen Prozess an einen Prozess übertragen, der mit der Bedienung des
Interrupts verbunden ist

• ein externes Ereignis zwingt den Computer in den Interrupt-Service-Zustand

Question 17

Welche Prozesse werden zur Behandlung eines Interrupts verwendet?

Answer 17

• Zeitfenster wird durch ersten dynamischen TT-Prozess geöffnet
• Während des Zeitfensters kann es zu einem Interrupt kommen
• der dritte Prozess, der ET-Interrupt Service-Prozess, wird aktiviert und schließt das Zeitfenster
• Zeitfenster wird durch zweiten dynamischen TT-Prozess geschlossen, wenn kein Interrupt aufgetreten ist

Question 18

Was ist Scheduling?

Answer 18

• Entscheidung zur Ausführung eines Prozesses mit den folgenden Teilen:
• assignment (Zuordnung): welcher Prozessor den Prozess ausführen soll
• ordering (Reihenfolge): in welcher Reihenfolge soll jeder Prozessor seine Prozesse ausführen soll
• timing (Zeitpunkt): die Zeit, zu der jeder Prozess ausgeführt wird

Question 19

Welche zwei Scheduler Arten gibt es?

Answer 19

• Fully-Static Scheduler: trifft alle drei Entscheidungen zur Designzeit (vor der Laufzeit)
• Fully-Dynamic Scheduler: trifft alle Entscheidungen zur Laufzeit

Question 20

Welche Klassifizierungen gibt es beim Scheduling? (4)

Answer 20

• Best Effort vs. Guaranteed
• Static vs. Dynamic
• Preemptive (unterbrechbar) vs. Nonpreemptive
• Central vs. Distributed

Question 21

Welche Klassifizierung gibt es für eine Prozess Ankunft? (3)

Answer 21

• periodic
• sporadic
• aperiodic

Question 22

Wann kann ein neuer Prozess beim non-preemptive scheduling versendet werden?

Answer 22

Wenn der aktuelle Prozess abgeschlossen wird.

Question 23

Wann kann ein neuer Prozess beim preemptive scheduling versendet werden?

Answer 23

• Bei einem Timer-Interrupt
• Bei einem I/O Interrupt (möglicherweise)
• Wenn ein neuer Prozess erstellt wird oder ein Prozess beendet wird
• Wenn der aktuelle Prozess einen Mutex blockiert oder freigibt
• Wenn der aktuelle Prozess auf einer Semaphore blockiert
• Wenn der Zustand einer Semaphore geändert wird

• Wenn der aktuelle Prozess einen Betriebssystemaufruf tätigt (Dateisystem Zugriff,
Netzwerk Zugriff)

Question 24

Welche Assumptions werden über Prozesse gemacht/benötigt? (7)

Answer 24

• Release time/ Arrival time
• Start time
• Finish time
• Execution time
• Deadline
• Period
• Priorities fixed/dynamic

Question 25

Was ist die Response Time?

Answer 25

Ist die Zeit, die zwischen der ersten Aktivierung des Prozesses und der Beendigung seiner Ausführung verstreicht

Question 26

Was ist Laxity (Nachlässigkeit)?

Answer 26

Ist die Zeitdifferenz zwischen der Deadline und der verbleibenden Ausführungszeit.

Question 27

Was ist Static Scheduling (Time Triggered Control)?

Answer 27

• Alle Scheduling Entscheidungen werden zur Kompilierzeit getroffen. Die zeitliche Prozessstruktur ist fest. Zur Laufzeit muss der Dispatcher eine Tabellensuche durchführen, um zu jedem Zeitpunkt zu entscheiden, welcher Prozess als nächstes ausgeführt werden muss
• Static Schedules sind so gestaltet, dass alle Anforderungen an Vorrang und gegenseitigen Ausschluss zwischen den Prozessen erfüllt sind (implizite Synchronisation) und die Laufzeit optimiert ist. (Kein Overhead für Warte- und Signaloperationen).

Question 28

Was ist Dynamic Scheduling?

Answer 28

• Alle Scheduling Entscheidungen werden online getroffen, d. h. auf der Grundlage der
bereitstehenden Prozesse.

• Gegenseitiger Ausschluss und Synchronisation müssen erzwungen werden durch explizite Synchronisationskonstrukte (z.B. Warteoperationen) zur Laufzeit erzwungen werden.
• Vorteile: Flexibilität, es werden nur Ressourcen beansprucht, die auch tatsächlich genutzt werden
• Nachteile: Rechenressourcen für die Planung und Synchronisierung erforderlich, Garantien sind schwer zu unterstützen

Question 29

Wie funktioniert Rate-Monotonic Scheduling (RMS)?

Answer 29

• für Prozesse sind jeweils WCET und Priorität gegeben

• falls die Perioden ein Vielfaches voneinander sind, kann die maximale CPU-Auslastung
gegen 1 gehen

• es wird davon ausgegangen, dass es keine Mutexe, Semaphoren, blockierende I/O und
keine Prioritätsbeschränkungen gibt

• Prioritäten werden statisch anhand der Periodendauer eines Jobs festgelegt: je kürzer die Periodendauer eines Jobs, desto höher ist seine Priorität

Question 30

Wie funktioniert Earliest Deadline First (EDF)?

Answer 30

• Prozess mit frühster Deadline wird zuerst ausgeführt
• bei einer Anzahl unabhängiger Prozesse mit Deadlines, wird so geplant, dass die maximale Verspätung (lateness) minimiert wird
• lateness_max = max(finishing time - Deadline)
• Beachten: lateness_max ist negativ wenn alle Deadlines eingehalten werden

Question 31

Wie funktioniert Least Laxity (LL)?

Answer 31

• Laxity: Differenz zwischen Deadline und CPU Zeit
• dynamisches preemptive scheduling mit dynamischen Prioritäten
• Prozesse mit kürzester Laxity bekommt höchste (dynamische) Priorität
• ist in uniprozessor Systemen ein optimaler Algorithmus
• Priorität wird mit der Zeit höher, da die Laxity summiert wird

Question 32

Was ist ein Precedence Graph?

Answer 32

Ein gerichteter azyklischer Graph (DAG) zeigt Vorrangigkeiten (precedences) an, die angeben, welche Prozesse abgeschlossen werden müssen, bevor andere Prozesse beginnen.

Question 33

Wie funktioniert Latest Deadline First (LDF)

Answer 33

• LDF-Scheduling Strategy baut einen Schedule rückwärts auf

• bei einem gerichteten azyklischen Graphen (DAG) wird Blattknoten mit der spätesten Frist, der als letzter terminiert werden soll, gewählt und arbeitet sich von hinten nach
vorne

• LDF Schedules berücksichtigt alle Abhängigkeiten und hält alle Deadlines ein

Question 34

Was meint Brittleness (Zerbrechlichkeit)?

Answer 34

Generell sind alle Algorithmen zerbrechlich: eine kleine Änderung kann große, unerwartete Konsequenzen haben.

Question 35

Was besagt Richard’s Anomalie Theorem?

Answer 35

Wenn ein Prozess Set mit festen Prioritäten, Ausführungszeiten und Vorrangsbeschränkungen nach Prioritäten auf einer festen Anzahl von Prozessoren geplant wird und dann die Anzahl der Prozessoren erhöht, die Ausführungszeiten verkürzt oder Prioritätsbeschränkungen aufgeweicht werden, kann das die Länge des Zeitplans erhöhen.

Question 36

Was ist Priority Inversion?

Answer 36

• Von einer Prioritätsumkehr spricht man, wenn ein Prozess mit höherer Priorität durch einen Prozess mit niedrigerer Priorität blockiert wird
• Situation kann entstehen, wenn gegenseitiger Ausschluss erzwungen werden muss

Question 37

Was ist Priority Inheritance (Prioritätsvererbung)?

Answer 37

Wenn ein Prozess einen oder mehrere Prozesse mit höherer Priorität blockiert, ignoriert
er seine ursprüngliche Priorität und erhält die höchste Prioritätsstufe aller Prozesse, die er blockiert. Nach dem Verlassen des kritischen Abschnitts kehrt der Prozess zu seiner ursprünglichen Priorität zurück. (Dieses Protokoll der Prioritätsvererbung schützt nicht
vor Deadlocks siehe Abbildung)

Question 38

Was ist das Ziel des Priority Ceiling Protokolls?

Answer 38

Ziel ist es Deadlocks zu verhindern, die auftreten können, wenn Prioritätsvererbung eingesetzt wird.

Question 39

Wie funktioniert das Priority Ceiling Protocol?

Answer 39

• Weisen Sie jeder Semaphore eine Prioritätsobergrenze zu
• Die Prioritätsgrenze ist gleich dem Prozess mit der höchsten Priorität, der diese Semaphor benutzen darf

• der Prozess T darf nur dann einen neuen kritischen Abschnitt beginnen, wenn die Priorität von T höher ist als die Prioritätsobergrenzen aller Semaphoren, die von
anderen Tasks als T gesperrt sind.