Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
11
Betriebssystembau
5. Übung
Olaf Spinczyk und Michael EngelArbeitsgruppe Eingebettete Systemsoftware
Lehrstuhl für Informatik 12TU Dortmund [email protected]://ess.cs.uni-dortmund.de/~os/
Betriebssystembau: 5. Übung 22
Agenda● Aufgabe 4
● Tipps und Tricks
● Aufgabe 5
● Überblick
● PIT-Programmierung
● Präemptives Scheduling
Betriebssystembau: 5. Übung 33
Agenda● Aufgabe 4
● Tipps und Tricks
● Aufgabe 5
● Überblick
● PIT-Programmierung
● Präemptives Scheduling
Betriebssystembau: 5. Übung 44
OO-StuBS: Aufgabe 4
Betriebssystembau: 5. Übung 55
Aufgabenteil a: Coroutine
Koroutinenwechsel „von Hand“
Betriebssystembau: 5. Übung 66
toc – Koroutinen für C-Programme
Strukturelementevoid *ebx, *esi, *edi, *ebp, *esp; Funktionen
void toc_settle (struct toc* regs, void* tos, void (*kickoff)(void*), void* object); Diese Funktion bereitet die Struktur toc für die erste Aktivierung vor.
void toc_go (struct toc* regs); Diese Funktion lädt die Prozessorregister mit den Inhalten der
Struktur regs.
void toc_switch (struct toc* regs_now, struct toc* regs_then); Diese Funktion führt einen Kontextwechsel durch. Dazu brauchen
nur die aktuellen Registerwerte in regs_now gesichert und durch die Werte von regs_then ersetzt werden.
Betriebssystembau: 5. Übung 77
toc – Koroutinen für C-Programme
Strukturelementevoid *ebx, *esi, *edi, *ebp, *esp; Funktionen
void toc_settle (struct toc* regs, void* tos, void (*kickoff)(void*), void* object); Diese Funktion bereitet die Struktur toc für die erste Aktivierung vor.
void toc_go (struct toc* regs); Diese Funktion lädt die Prozessorregister mit den Inhalten der
Struktur regs.
void toc_switch (struct toc* regs_now, struct toc* regs_then); Diese Funktion führt einen Kontextwechsel durch. Dazu brauchen
nur die aktuellen Registerwerte in regs_now gesichert und durch die Werte von regs_then ersetzt werden.
Aufruf aus C++ heraus erfordert Deklaration mit extern “C“!Aufruf aus C++ heraus erfordert Deklaration mit extern “C“!
kickoff ist eine C++-Funktion. Beim Aufruf von toc_settle ist daher ein Type-Cast erforderlich!Über tos soll der Stapel initialisiert werden. Geht das mit einem Zeiger auf void?
kickoff ist eine C++-Funktion. Beim Aufruf von toc_settle ist daher ein Type-Cast erforderlich!Über tos soll der Stapel initialisiert werden. Geht das mit einem Zeiger auf void?
Betriebssystembau: 5. Übung 88
Coroutine
MethodenCoroutine (void* tos);
Im Coroutinen Konstruktor werden die Registerwerte so initialisiert, dass der Stackpointer initial auf tos zeigt und bei der ersten Aktivierung die Ausführung mit der Funktion kickoff beginnt.
void go (); Diese Methode dient der ersten Aktivierung der ersten Koroutine im
System. Daher müssen hier keine Registerwerte gerettet werden.
void resume (Coroutine& next); Mit dieser Methode wird ein Koroutinenwechsel ausgelöst.
virtual void action () = 0; Die Methode action stellt die eigentliche Aufgabe der Koroutine dar.
Betriebssystembau: 5. Übung 99
Aufgabenteil b: Dispatcher
Koroutinenwechselüber den Dispatcher
Betriebssystembau: 5. Übung 1010
Arbeitsteilung● Scheduler● trifft strategische Entscheidungen zur Ablaufplanung●betrachtet wird immer eine Menge lauffähiger Fäden
- die Fäden sind allgemein in einer CPU-Warteschlange aufgereiht- die Sortierung erfolgt entsprechend der Scheduling-Strategie
●der aktuell laufende Prozess ist immer von der Entscheidung mit betroffen- dazu muss der laufende Faden jederzeit „greifbar“ sein- vor der Umschaltung ist ist der laufende Faden (beim Dispatching)
zu vermerken●ein ausgewählter neuer Faden wird dem Dispatcher
übergeben● Dispatcher●setzt die Entscheidungen durch und
schaltet Fäden (mit Hilfe von resume) um●merkt sich den gestarteten Faden
Betriebssystembau: 5. Übung 1111
Dispatcher
BeschreibungDer Dispatcher verwaltet den Life-Pointer, der die jeweils aktive Koroutine angibt und führt Prozesswechsel durch.
Methoden
Dispatcher () Der Konstruktor initialisiert den Life-Pointer mit Null, um anzuzeigen, dass noch keine
Koroutine bekannt ist.
void go (Coroutine& first) Mit dieser Methode wird die Koroutine first im Life-Pointer vermerkt und gestartet.
void dispatch (Coroutine& next) Diese Methode setzt den Life-Pointer auf next und führt einen Koroutinenwechsel vom
alten zum neuen Life-Pointer durch.
Coroutine* active () Hiermit kann abgefragt werden, welche Koroutine gerade im Besitz des Prozessors ist.
Betriebssystembau: 5. Übung 1212
Aufgabenteil c: Kooperatives Scheduling
Koroutinenwechselüber Scheduler
Betriebssystembau: 5. Übung 1313
Entrant
BeschreibungDie Klasse Entrant erweitert die Klasse Coroutine um die Möglichkeit, in
einfach verkettete Listen eingetragen zu werden, insbesondere auch in die Ready-Liste des Schedulers. Die Verkettungsmöglichkeit wird durch die Ableitung von Chain erreicht.
öffentliche Methoden
Entrant (void* tos); Der Entrant Konstruktor gibt nur den Parameter tos an den Coroutinen
Konstruktor weiter.
Betriebssystembau: 5. Übung 1414
Entrant
BeschreibungDie Klasse Entrant erweitert die Klasse Coroutine um die Möglichkeit, in
einfach verkettete Listen eingetragen zu werden, insbesondere auch in die Ready-Liste des Schedulers. Die Verkettungsmöglichkeit wird durch die Ableitung von Chain erreicht.
öffentliche Methoden
Entrant (void* tos); Der Entrant Konstruktor gibt nur den Parameter tos an den Coroutinen
Konstruktor weiter.
Vorsicht Mehrfachvererbung! Coroutine und Chain stehen in keiner Vererbungsbeziehung. Expliziter Type-Cast von einem zum anderen führt zu Problemen!
Vorsicht Mehrfachvererbung! Coroutine und Chain stehen in keiner Vererbungsbeziehung. Expliziter Type-Cast von einem zum anderen führt zu Problemen!
Betriebssystembau: 5. Übung 1515
SchedulerBeschreibung
Der Scheduler verwaltet die Ready-Liste (ein privates Queue Objekt der Klasse), also die Liste der lauffähigen Prozesse (Entrant Objekte). Die Liste wird von vorne nach hinten abgearbeitet. Dabei werden Prozesse, die neu im System sind oder den Prozessor abgeben, stets an das Ende der Liste angefügt.
öffentliche Methoden
void ready (Entrant& that) Mit dieser Methode wird der Prozess that beim Scheduler angemeldet. Er wird an das Ende der Ready-
Liste angefügt. void schedule ()
Diese Methode setzt das Scheduling in Gang, indem der erste Prozess von der Ready-Liste entfernt und aktiviert wird.
void exit () Hiermit kann sich ein Prozess selbst beenden. Er wird nun nicht wieder an das Ende der Ready-Liste
angefügt. Statt dessen wird nur der erste Prozess von der Ready-Liste heruntergenommen und aktiviert.
void kill (Entrant& that) Mit dieser Methode kann ein Prozess einen anderen (that) beenden. Der Prozess that wird einfach von
der Ready-Liste entfernt und erhält somit nie wieder den Prozessor. void resume ()
Hiermit kann ein Prozesswechsel ausgelöst werden, ohne dass der aufrufende Entrant wissen muss, welche anderen Entrant Objekte im System existieren und welcher davon sinnvollerweise aktiviert werden sollte.
Betriebssystembau: 5. Übung 1616
Agenda● Aufgabe 4
● Tipps und Tricks
● Aufgabe 5
● Überblick
● PIT-Programmierung
● Präemptives Scheduling
Betriebssystembau: 5. Übung 1717
Aufgabe 5: Zeitscheiben-Scheduler● Ziel: Schutz kritischer Betriebssystem-Abschnitte mit Hilfe
von Schleusen● Die Synchronisation der Aktivitäten innerhalb von OO-
Stubs soll auf die Verwendung einer Schleuse umgestellt werden
● Gleichzeitig soll nun eine grobgranulare Locking-Strategie verwendet und eine Systemaufrufschnittstelle definiert werden
● Der Scheduler soll ausgelöst durch den Timer-Interrupt Threads verdrängen können
Betriebssystembau: 5. Übung 1818
Aufgabe 5: Zeitscheiben-Scheduler● Hierzu müssen die Klassen Guarded_Scheduler, Thread,
PIT und Watch implementiert werden● Um aus Benutzerprogrammen heraus die geschützten
Methoden des Schedulers aufrufen zu können, darf die globale Variable scheduler nicht länger ein Objekt der Klasse Scheduler sein, sondern muss eine Instanz der Klasse Guarded_scheduler sein.
Betriebssystembau: 5. Übung 1919
Aufgabe 5: Zeitscheiben-Scheduler
Betriebssystembau: 5. Übung 2020
Präemptiver Fadenwechsel● CPU-Entzug durch Zeitgeberunterbrechung
● die Unterbrechung ist „nur“ ein impliziter Aufruf● Behandlungsroutine kann resume aufrufen
<resume>
<handler>
<app1>
<app2>
ret
resu
me
iret
resu
me
sti()
ret
Achtung: So geht es normalerweise nicht, denn resume trifft eine Scheduling-Entscheidung. Bei den notwendigen Datenstrukturen ist Unterbrechungssynchronisation zu beachten!
Achtung: So geht es normalerweise nicht, denn resume trifft eine Scheduling-Entscheidung. Bei den notwendigen Datenstrukturen ist Unterbrechungssynchronisation zu beachten!
Betriebssystembau: 5. Übung 2121
Fadenwechsel im Epilog● Implementierung
● Scheduler-Daten (Liste der laufbereiten Fäden)werden auf der Epilogebene angesiedelt
● alle Systemfunktionen, die diese Daten manipulieren,müssen zuvor die Epilog-Sperre anfordern (enter/leave)- Faden erzeugen, Faden beenden, freiwilliger Fadenwechsel, ...
● Grundregel beim Fadenwechsel● der abgebende Faden fordert die Sperre an
(ggf. implizit bei der Unterbrechungsbehandlung)● der aktivierte Faden muss die Sperre freigeben
● Tipps● aus dem Epilog heraus nie enter Aufrufen (Doppelanforderung)● Grundregel (s.o) gilt auch für die erste Fadenaktivierung
Mehr dazu in der Übung … also jetzt.Mehr dazu in der Übung … also jetzt.
Betriebssystembau: 5. Übung 2222
Aufgabe 5: Klasse Guarded_Scheduler● implementiert die Systemaufrufschnittstelle zum Scheduler● Die von ihm angebotenen Methoden werden direkt auf die
Methoden der Basisklasse abgebildet● Ihre Ausführung wird aber jeweils mit Hilfe eines Objekts der Klasse
Secure geschützt● Es werden keine Entrant-, sondern Thread-Objekte behandelt
● Öffentliche Methoden:● void ready (Thread& that)
- Mit dieser Methode wird der Prozess that beim Scheduler angemeldet
● void exit ()- Hiermit kann sich ein Prozess selbst beenden.
● void kill (Thread& that)- Mit dieser Methode kann ein Prozess einen anderen (that) beenden.
● void resume ()- Hiermit kann ein Prozesswechsel ausgelöst werden.
Betriebssystembau: 5. Übung 2323
Aufgabe 5: Klasse Guarded_Scheduler● Tipp
● Da die Methoden von Guarded_Scheduler die gleichen Namen haben wie die der Basisklasse Scheduler, verdecken sie diese normalerweise
● Dies kann verhindert werden, wenn bei dem Aufruf einer Methode der Name der Basisklasse explizit angeführt wird
● Beispiel:
Betriebssystembau: 5. Übung 2424
Aufgabe 5: Klasse Thread● Die Klasse Thread implementiert die Benutzerschnittstelle
eines Fadens● Zur Zeit ist Thread nichts weiter als ein neuer Name für
die Klasse Entrant● ... das wird sich in Aufgabe 6 noch ändern
● Öffentliche Methoden:● Thread (void* tos)
- Der Konstruktor leitet den Parameter tos an den Konstruktor der Basisklasse Entrant weiter.
Betriebssystembau: 5. Übung 2525
Aufgabe 5: Klasse PIT● Die Klasse PIT steuert den Programmable Interval Timer
(PIT) des PCs● Öffentliche Methoden
● PIT (int us)- Im Konstruktor wird der Timer so initialisiert, dass er in Abständen von ca.
us Mikrosekunden regelmäßig Unterbrechungen auslöst
- Da die Auflösung des Timerbausteins maximal 838 Nanosekunden beträgt, ist keine ganz exakte Einstellung im Mikrosekundenbereich möglich
● int interval ()- Gibt an, welches Unterbrechungsintervall eingestellt wurde.
● void interval (int us)- Stellt das Unterbrechungsintervall neu ein.
Betriebssystembau: 5. Übung 2626
Aufgabe 5: Klasse Watch● Watch sorgt für Behandlung der Zeitgeberunterbrechungen● Zeitscheiben werden verwaltet und bei Bedarf ein
Prozesswechsel ausgelöst● Öffentliche Methoden
● Watch (int us)- Im Konstruktor wird der Timer so initialisiert, dass er in Abständen von ca.
us Mikrosekunden regelmäßig Unterbrechungen auslöst.
● void windup ()- "zieht die Uhr auf"
- Dazu muss sich das Watch-Objekt bei der Plugbox plugbox anmelden
- ... und mit Hilfe des globalen PIC-Objekts pic die Unterbrechungen des Timer-Bausteins (repräsentiert durch das globale PIT Objekt pit) zulassen
● void prologue ()- Enthält den Prolog der Unterbrechungsbehandlung.
● void epilogue ()- In dieser Methode wird der Prozesswechsel ausgelöst.
Betriebssystembau: 5. Übung 2727
Agenda● Aufgabe 4
● Tipps und Tricks
● Aufgabe 5
● Überblick
● PIT-Programmierung
● Präemptives Scheduling
Betriebssystembau: 5. Übung 2828
Der Timer 8254: Verwendung● PCs besitzen zwei Timer-Bausteine vom Typ 8253 oder
8254● Mittlerweile natürlich auch im Chipsatz integriert
● Diese werden mit einem Takt von 1,19318 MHz betrieben● Unabhängig von der CPU-Frequenz!● Warum so ein „krummer“ Takt?
- 1,19318 MHz * 4 = 4,77 MHz
- ... die Taktfrequenz des Ur-IBM-PC!
- ... damals also doch nicht so unabhängig von der CPU-Frequenz
● Warum eine krumme Taktfrequenz wie 4,77 MHz für den Ur-PC?- 4,77 MHz * 12 = 14,31816 MHz
- ... das ist die Grundfrequenz, die für NTSC-Fernsehen benötigt wird
- ... also gibt es fertige, billige Quarze
- ... und man kann die Frequenz gleich zur Video-Erzeugung verwenden!
● PCs besitzen mittlerweile zwei dieser Timer-Bausteine
Betriebssystembau: 5. Übung 2929
Struktur des 8254
(aus dem intel-Datenblatt zum 8254)
Betriebssystembau: 5. Übung 3030
Nutzung des 8254 im PC● Bezeichnung des 8254: „PIT“
● Programmable Interval Timer
● Jeder 8254 besitzt drei unabhängige Zähleinheiten● Diese werden im PC unterschiedlich verwendet:
● Jeder Zähler besitzt einen eigenen Ausgang (OUTx)
Betriebssystembau: 5. Übung 3131
Nutzung des 8254 im PC● Die verschiedenen Verwendungen der Kanäle ergeben
sich durch die Verdrahtung der Ausgänge auf den PC-Mainboard:● OUT0 führt an Int 0 des (1.) PIC 8259● OUT1 führt an Kanal 0 des DMA-Controllers 8237● OUT2 führt (über ein schaltbares Gatter) an einen Verstärker● OUT0 des 2. PIT führt an den NMI-Eingang der CPU
- Über das NMI Mask Bit
- Im PC sind „Non Maskable“ Interrupts doch maskierbar ...
Betriebssystembau: 5. Übung 3232
Struktur eines Zählers im 8254
(aus dem intel-Datenblatt zum 8254)
Betriebssystembau: 5. Übung 3333
Programmierung des 8254● Jeder PIT kann mit Hilfe von vier Ports angesprochen
werden:
● Alle Ports sind 8 Bit breit!● Um 16 Bit Zählerwerte in den PIT zu schreiben, muss eine
besondere Vorgehensweise zum Einsatz kommen
Betriebssystembau: 5. Übung 3434
Programmierung des 8254● Zunächst muss dem 8254 über ein Steuerwort gesagt
werden, was er als nächstes tun soll:
Betriebssystembau: 5. Übung 3535
Programmierung des 8254● Der Modus bestimmt, wie der Zähler arbeitet und ob er mit
Hilfe seiner OUTx-Leitung externe Ereignisse auslöst● Im Modus 0 zählt der Zähler vom angegebenen Startwert
bis 0 herunter● Alle 838 ns● Wenn der Zählerwert 0 ist, wird die OUTx-Leitung auf „1“ gesetzt
● Zum Erzeugen periodischer Impulse eignet sich Modus 2 am besten● Hier wird beim Erreichen des Wertes 0 ein kurzer Impuls auf OUTx
erzeugt und der Zähler wird automatisch wieder mit dem ursprünglichen Startwert initialisiert
● Zur Einstellung eines 16 Bit Zählerwertes sind damit drei out-Befehle notwendig● Schreiben des Steuerwortes● Schreiben des nieder- und höherwertigen Bytes des Zählerwerts
Betriebssystembau: 5. Übung 3636
Spaß mit dem 8254● Das Intervall, mit dem ein Zähler im 8254 „tickt“, ist
anhängig von der Basisfrequenz● Der Zähler teilt diese Frequenz dann ganzzahlig● Bei einem initialen Zählerwert von 1 für Counter 0 wird
also eine Frequenz von 1,19318 MHz erzeugt● Zählerwert 2: f = 0,59659 MHz usw.● Initialwert für den Timer 0 im IBM PC: „0“
● Der PIT zählt erst herunter und vergleicht dann● Also wird der Zähler 2^16-mal heruntergezählt● Die Basisfrequenz wird also durch 65536 geteilt:
- 1,19318 MHz / 2^16 = 18,2 Hz
● Das ist die Standard Interrupt-Frequenz im PC
● Wir können also nicht beliebige Frequenzen generieren, aber immerhin eine ganze Menge ...
Betriebssystembau: 5. Übung 3737
Agenda● Aufgabe 4
● Tipps und Tricks
● Aufgabe 5
● Überblick
● PIT-Programmierung
● Präemptives Scheduling
Betriebssystembau: 5. Übung 3838
Präemptives Scheduling● … soll dafür sorgen, dass kein Prozess/Faden die CPU
monopolisiert. Bei OO-StuBS gilt das nur eingeschränkt:● Faden A rechnet 18 ms und ruft dann freiwillig resume() auf● Faden B rechnet dauerhaft und gibt nie freiwillig die CPU ab
● Wer mag, darf gerne echtes Round Robin oder Virtual Round Robin in sein OO-StuBS einbauen!
20 ms Periode
resume() resume() resume()
Unfair! Effektiv bekommt B nur 10% der CPU-Zeit.Unfair! Effektiv bekommt B nur 10% der CPU-Zeit.
Betriebssystembau: 5. Übung 3939
Agenda
Fragen?Fragen?
● Aufgabe 4
● Tipps und Tricks
● Aufgabe 5
● Überblick
● PIT-Programmierung
● Präemptives Scheduling