1
Q
Welche Operating Systems gibt es?
A
- General Purpose Operating Systems (GPOS) für normale Computer
- Real Time Operating Systems (RTOS) für eingebettete Computer
2
Q
Warum braucht ein eingebettetes System ein spezielles Operating System?
A
Es gibt fundamentale Unterschiede in:
- Verfügbarkeit
- Sicherheit
- Zeitlicher Vorhersagbarkeit
- Gleichzeitigkeit
- Parallelität
3
Q
Was sind die Haupteigenschaften und Anforderungen für ein Real-Time Operating System?
A
- Deterministisches zeitliches Verhalten
- Verarbeitung von externen Ereignissen mit kurzen Reaktionszeiten
- Geringer Ressourcenverbrauch
- Verlässlichkeit
- Skalierbarkeit
4
Q
Was ist ein Process?
A
- Programm in Ausführung und sein Zustand (dynamisch)
- Grundlage für parallele und quasi-parallele Ausführung von Programmen
5
Q
Was ist ein Programm?
A
Abfolge von Anweisungen (statisch)
6
Q
Was ist die Motivation für Processes?
A
- Effektivere Nutzung von Ressourcen
- Anforderung gleichzeitiger Aktionen
7
Q
Was ist das Ziel der Concurrency (Gleichzeitigkeit) in Embedded Systems?
A
Das Ziel ist Aktualität, weder zu früh, noch zu spät
8
Q
Was gehört zum Process Management?
A
- Liste für jeden Process Status
- Zustandsübergänge durch Entfernung und Wiedereintritt
- Process Scheduler
9
Q
Was macht der Process Scheduler?
A
- Entferne den Process aus der Bereitschaftsliste und weise ihn dem Prozessor zu
- Scheduling Entscheidungen berücksichtigen Zeiten und Processes für Prozessor Zuweisung
- Zuständig für Kontextwechsel: Speichern/Wiederherstellen des Registerinhalts
10
Q
Welche Process Zustände gibt es?
A
- Created
- Ready
- Running
- Blocked
- Suspended
- Dead
11
Q
Wofür ist die Timer Interrupt Service Routine zuständig?
A
Für die Abfertigung eines Prozesses
12
Q
Wie läuft die Abfertigung eines Prozesses ab?
A
- Interrupts deaktivieren
- 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, Interrupt aktivieren und Return
- Prozesszustand in Maschinenregister kopieren
- Ersetzen des Programmzählers auf dem Stack für den neuen Prozess
- Interrupts aktivieren
- Return
13
Q
Was ist Sampling?
A
Unter Sampling versteht man die periodische Abfrage des Zustands einer RT-Entity durch einen Computer
14
Q
Wie bezeichnet man die Zeit zwischen zwei Abtastpunkten?
A
Abtastintervall
15
Q
Wodurch wird die Länge eines Abtastintervalls bestimmt?
A
Die Länge eines Abtastintervalls wird bestimmt durch die Dynamik der Echtzeiteinheit
16
Q
Was ist der Unterschied beim Sampling zwischen States und Events?
A
- States (Zustände) können durch Abtasten beobachtet werden
- Events (Ereignisse) müssen in einem Speicherelement gespeichert werden
17
Q
Was ist ein Interrupt?
A
- Ein Interrupt ist ein Hardware-Mechanismus, der periodisch (nach jeder Instruktion) den Zustand einer spezifischen Signal Line überwacht
- Wenn die Linie aktiv ist, während der Interrupt nicht deaktiviert ist, wird die Kontrolle vom aktuellen Prozess an einem Prozess übertragen, der mit der Bedienung des Interrupts verbunden ist
- Ein externes Ereignis zwingt den Computer in den Interrupt-Service Zustand
18
Q
Welche drei Prozesse werden verwendet, um einen Interrupt zu behandeln?
A
- 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
19
Q
Was ist Scheduling?
A
- Assignment: Welcher Prozessor soll den Prozess ausführen
- Ordering: In welcher Reihenfolge soll jeder Prozessor seine Prozesse ausführen
- Timing: Der Zeitpunkt, zu dem jeder Prozess ausgeführt wird
20
Q
Welche zwei Arten von Schedulern gibt es?
A
- Fully-static Scheduler
- Fully-dynamic Scheduler
21
Q
Was ist ein fully-static Scheduler?
A
- Trifft alle drei Entscheidungen zur Designzeit (vor der Laufzeit)
- Gegenseitiger Ausschluss und Vorrangsbedingungen können gewährleistet werden auf der Grundlage des Zeitplans
- Schwierigkeiten bei der Vorhersage der Ausführungszeit
22
Q
Was ist der Nachteil des fully-static Schedulers?
A
Alle Probleme müssen zur Designzeit bekannt sein
23
Q
Was ist ein fully-dynamic Scheduler?
A
- Trifft alle Entscheidungen zur Laufzeit
- Attraktiv für nicht kritische Systeme
- Flexibler als ein fully-static Scheduler
24
Q
Was ist das Problem des fully-dynamic Schedulers?
A
Eine gute Schedule zu finden und diese zu erstellen benötigt Zeit, die dann nicht für den Prozessor verwendet werden kann
25
Welche Klassifizierungen gibt es beim Scheduling?
- Best Efford vs. Guaranteed
- Static vs. Dynamic
- Preemtive (unterbrechbar) vs. Nonpreemtive
- Central vs. Distributed
26
Welche Klassifizierungen gibt es für eine Prozess Ankunft?
- Periodic: Zeit zwischen zwei Arrivals bekannt
- Sporadic: Minimum interarrival time bekannt
- Aperiodic: Unmöglich zeitliche Garantien zu geben -> Kommt vielleicht nie
27
Wann kann ein neuer Prozess beim nonpreemtive Scheduling versendet werden?
Wenn der aktuelle Prozess abschließt
28
Welche Annahmen werden über Prozesse gemacht bzw. benötigt?
- Release time / Arrival time
- Start time
- Finish time
- Execution time
- Deadline
- Period
- Fixed oder dynamic priorities
29
Was ist die Response Time?
Die Response Time, ist die Zeit, die zwischen der ersten Aktivierung des Prozesses und der Beendigung seiner Ausführung verstreicht
30
Was ist die Laxity (Nachlässigkeit)?
Laxity, ist die Zeitdifferenz zwischen der Deadline und der verbleibenden Ausführungszeit
31
Was bezeichnet man als eine feasible schedule?
Eine feasible schedule ist, wenn alle Prozessausführungen ihre Deadlines einhalten
32
Woran kann man Scheduler vergleichen?
- Ob alle Prozessausführungen ihre Deadlines erreichen
- Erreichbare Prozessorauslastung
- Maximale Verspätungen
- Gesamtfertigstellungszeit oder Produktionsspanne
33
Was sind die Vorteile von Dynamic Scheduling?
- Flexibilität
- Es werden nur Ressourcen beansprucht, die auch tatsächlich genutzt werden
34
Was sind die Nachteile von Dynamic Scheduling?
- Rechenressourcen werden für die Planung und Synchronisation benötigt
- Garantien sind schwer zu unterstützen
- Replica determinism?
35
Wie funktioniert Rate-Monotonic Scheduling (RMS)?
- Für die Prozesse sind WCET und Prioritäten gegeben
- Falls die Perioden ein Vielfaches voneinander sind, kann die maximale CPU-Auslastung gegen 1 gehen
- Annahme: keine Mutexe, Samaphoren, blockierende I/O und keine Prioritätsbeschränkungen
- Prioritäten werden statisch anhand der Periodendauer eines Prozesses festgelegt
36
Wie funktioniert Earliest Deadline First (EDF)?
- Prozess mit frühester Deadline wird zuerst ausgeführt
- Bei einer Anzahl unabhängiger Prozesse mit Deadlines, wird so geplant, dass die maximale Lateness minimiert wird
37
Wie funktioniert Least Laxity (LL)?
- Dynamisches preemtive Scheduling mit dynamischen Prioritäten
- Prozess mit kürzester Laxity bekommt höchste dynamische Priorität
- Optimaler Algorithmus in Uniprozessor Systemen
- Priorität wird mit der Zeit höher, da die Laxity summiert wird
38
Was ist ein Precedence Graph?
Ein gerichteter azyklischer Graph (DAG) zeigt precedences (Vorrangigkeiten) an, die angeben, welche Prozesse abgeschlossen werden müssen, bevor andere Prozesse beginnen
39
Wie funktioniert Latest Deadline First (LDF)?
- Baut eine Schedule rückwärts auf
- Bei einem gerichteten azyklischen Graphen wird der Blattknoten mit der spätesten Deadline, der als letzter terminieren soll, gewählt und von dort aus arbeitet man sich von hinten nach vorne
- LDF berücksichtigt alle Abhängigkeiten und hält alle Deadlines ein
40
Was meint Brittleness (Zerbrechlichkeit)?
Generell sind alle Algorithmen zerbrechlich: Eine kleine Änderung kann große, unerwartete Konsequenzen haben
41
Was besagt Richards Anomalie Theorem?
Wenn ein Prozess Set mit festen Prioritäten, Ausführungszeiten und Vorrangsbeschränkungen nach Prioritäten auf einer festen Anzahl von Prozessen geplant wird und dann die Anzahl der Prozessoren erhöht, die Ausführungszeiten verkürzt oder die Prioritätsbeschränkungen aufgeweicht werden, kann das die Länge des Zeitplans erhöhen
42
Was ist Priority Inversion (Prioritätsumkehr)?
- Wenn ein Prozess mit höherer Priorität durch einen Prozess mit niedriger Priorität blockiert wird
- Entsteht, wenn ein gegenseitiger Ausschluss erzwungen werden muss
43
Was ist eine mögliche Lösung für Priority Inversion?
Priority Inheritance
44
Was ist Priority Inheritance (Prioritätsvererbung)?
- 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
- Nachher kehrt der Prozess zu seiner ursprünglichen Priorität zurück
- Schützt nicht vor Deadlocks
45
Was ist das Ziel des Priority Ceiling Protokolls?
Das Ziel des Priority Ceiling Protokolls ist es Deadlocks zu verhindern, die auftreten können, wenn Prioritätsvererbung eingesetzt wird
46
Wie funktioniert das Priority Ceiling Protokoll?
- Jeder Semaphore wird eine Prioritätsobergrenze zugewiesen
- Die Prioritätsgrenze ist gleich dem Prozess mit der höchsten Priorität, der dieser Semaphor benutzen darf
- Ein Prozess darf nur dann einen neuen kritischen Abschnitt beginnen, wenn die Priorität von ihm höher ist als die Prioritätsobergrenzen aller Semaphoren, die von anderen Tasks gesperrt sind
