- Generated on Tue Jul 13 2021 13:54:29 for StuBS by
1.9.1
|
StuBS
|
Bitfeld bezeichnet ein Feld von Bits mit jeweils eigener Semantik. Bspw. könnte ein 8-Bit Integer ein Bitfeld sein, wenn er im CGA-Videospeicher als Attribut-Eintrag verwendet werden soll. Dann hätten Bits 0-3 eine eigene Bedeutung (Vordergrundfarbe), 4-6 (Hintergrundfarbe) und das Bit 7 wiederum eine andere (blinkend).
Weiter kann ein Bitfeld ein Konstrukt von C/C++ sein, bei dem an einem struct die Länge eines Members in Bit angegeben wird. Zu beachten ist dabei, dass C/C++ das Feld dann "falsch herum" aufbaut, also vom Least Significant Bit (LSB) zum Most Significant Bit (MSB).
Achtung: Der C++-Compiler garantiert nur, dass die Länge der einzelnen Attribute mindestens die gewünschte Anzahl Bit besitzen. Um zu erreichen, dass sie genau die Anzahl Bits besitzen, ist es notwendig, den Compiler anzuweisen, die gesamte Struktur möglichst platzsparend im Speicher anzulegen.
Bspw.
Der Dispatcher implementiert den Mechanismus des Threadwechsels. Er trifft keine Scheduling-Entscheidung, d.h. er hat kein Wissen über die Threads im System, oder die Strategie, die für die Auswahl des nächsten Threads eingesetzt wird.
Unter gegenseitigem Ausschluss versteht man den Schutz eines Kritischer Abschnitt (Critical Section) s vor gleichzeitiger Ausführung auf zwei verschiedenen Prozessoren.
Bei der Interrupt-basierten Signalisierung wird vom externen Gerät eine Unterbrechungsanforderung an den Prozessor gesendet, wenn sich der Zustand des Geräts ändert. Das kann bspw. passieren, wenn im Empfangspuffer des Tastaturkontrollers ein neuer Code vorliegt, der vom Prozessor abgeholt werden soll. Der Kontrollfluss des Prozessors wird dann unterbrochen und eine Interrupt-Service-Routine ausgeführt.
Die Interrupt Descriptor Table (IDT) ist der Name von Intel x86 für die Interrupt Vector Table. Sie enthält Einträge pro möglichem Interrupt-Vektor, den die CPU verarbeiten kann. Mithilfe des vom Interrupt Controller gesendeten Vektors kann die CPU in dieser Tabelle den Zeiger auf die auszuführende Interrupt Service Routine (ISR) finden. Weiter können Interrupt Vektor Tabellen Informationen über zu Privilegienstufen enthalten, Informationen über den zu verwendenden Modus, o.Ä.
Eine Unterbrechungsanforderung wird von Geräten gesendet, indem die Interrupt-Leitung des Geräts aktiviert wird. Dann erkennen die Interrupt Controller (I/O APIC und LAPIC), dass ein Request vorliegt und aktivieren die Interrupt-Leitung des Prozessors.
Als Interrupt Service Routine wird ein Unterprogramm im Code bezeichnet, was beim Auftreten einer Unterbrechungsbehandlung vom Prozessor aufgerufen wird. Die ISR ist dafür zuständig die Unterbrechung zu behandeln, sodass der Prozessor seinen normalen Kontrollfluss weiter ausführen kann. Dafür kann es je nach Quelle der Unterbechung nötig sein aus einem Puffer des Geräts zu lesen oder ein Statusbit in einem Register zu setzen. Auf x86 muss dem LAPIC nach der Behandlung signalisiert werden, dass die Unterbrechung behandelt wurde.
Als maskieren bezeichnet man das Ausschalten der Interrupt-Leitung oder bestimmter Eingänge vom Interrupt Controller. Somit können einzelne Interrupt-Quellen oder externe Interrupts gänzlich ausgeschaltet werden, sodass Anforderungen nicht mehr an die CPU durchkommen. Auf x86 werden Interrupts mit dem Befehl cli auf der ausführenden CPU ausmaskiert und mit sti dort wieder eingeschaltet.
siehe Interrupt Descriptor Table (IDT).
Ein kritischer Abschnitt ist ein Abschnitt im Code, bei dem die gleichzeitige Ausführung von zwei CPUs zu Problemen führen kann, bspw. weil Datenstrukturen geteilt sind und der Zugriff atomar stattfinden muss, aber nicht ohne Weiteres kann. Bspw. müssen zwei Zeigerwerte "gleichzeitig" aktualisiert werden, damit eine doppelt verkettete Liste konsistent bleibt, was allerdingsBspw. müssen zwei Zeigerwerte "gleichzeitig" aktualisiert werden, damit eine doppelt verkettete Liste konsistent bleibt, was allerdings nicht ohne Weiteres möglich ist. Greifen zwei Prozessoren gleichzeitig auf inkonsistente Daten zu, kann es zu Race Condition s kommes kommen, wenn ein Prozessor die Datenstruktur verändert, während der andere sie lesen will. Zum Schutz eines kritischen Abschnitts muss ein Gegenseitiger Ausschluss (Mutual Exclusion, Mutex) implementiert werden.
Ein Thread legt sich aufgrund einer Bedingung schlafen. Während des Vorgangs ändert sich allerdings der Wert der Bedingung, sodass der Thread weiter laufen könnte. Allerdings bekommt er die Änderung nicht mehr mit und schläft für immer, weil der aufweckende Interrupt bereits kam und nicht erneut gesendet wird. Der Weckruf wurde also verpasst.
Siehe Gegenseitiger Ausschluss (Mutual Exclusion, Mutex).
Die internen Register eines Geräts werden im physischen Adressraum des Prozessors wie normaler Speicher auch eingeblendet. Im Gegensatz zum Port-based I/O kann somit auf die internen Register des Geräts direkt mit normalen mov-Instruktionen zugegriffen werden. So kann das Gerät u.A. ohne Wrapper in einer Hochsprache verwendet werden, die Zugriff auf beliebige Speicherstellen per Zeiger erlaubt.
Als Polling wird der Vorgang bezeichnet, ein Statusregister eines Geräts zyklisch abzufragen um Änderungen mitzubekommen. Dadurch wird eine Menge CPU-Zeit verbrannt, auch wenn es keine Änderungen am entsprechenden Gerät gab. Außerdem steht die CPU-Zeit so nicht für Anwendungsprogramme zur Verfügung, sondern wird im Betriebssystem verbracht, was den Durchsatz stark drücken würde. Eine einzelne Abfrage ist aber in vielen Fällen schneller als ein Interrupt, sodass Polling in bestimmten Szenarien sinnvoll sein kann. Außerdem dem Polling insgesamt deterministischer, was u.A. in Echtzeitbetriebssystemen sinnvoll ist.
Die internen Register eines Geräts werden nicht im physischen Adressraum des Prozessors eingeblendet, sondern müssen über so genannte I/O-Ports zugegriffen werden. Zum Umgang mit I/O-Ports existieren getrennte Befehle, in und out (auf x86 jeweils in Byte und Word-Varianten, d.h. der Zugriff auf 8 oder 16 Bit). Ein Zugriff auf I/O-Ports aus einer Hochsprache ist nur mit Assembler-Wrapper möglich, der die entsprechenden Befehle innerhalb der Sprache nutzbar macht (bei uns in machine/ioport.h). Der I/O-Port Adressraum ist vom physischen Adressraum getrennt.
Das Prolog-Epilog Modell zeichnet sich dadurch aus, dass die Interrupt Service Routinen in zwei Teile aufgeteilt werden. Der sehr kurze Prolog (manchmal auch Bottom Half, in Linux Top Half) macht, was unbedingt nötig ist, um die Hardware zufrieden zu stellen und den Interrupt zu behandeln. Der Epilog (manchmal auch Top Half, in Linux Bottom Half, in Windows Deferred Procedure Call) kann von Prologen verdrängt werden, kann allerdings nur im Gegenseitigen Ausschluss mit allen CPUs ausgefügrt werden. Er nimmt Modifikationen an Kern-Datenstrukturen vor, die vom Prolog nicht angefasst werden dürfen. Damit wird die Interrupt-Latenz kurz gehalten, weil Prologe die höchste Priorität im System haben, dann Epiloge, dann der normale Kontrollfluss.
Als Prozess bezeichnet man die Einheit der Isolation. In BSB beschäftigen wir uns nicht um Isolation, weshalb die Unterscheidung zwischen Prozess und Thread nicht existiert. In Linux sind an den Prozess die geöffneten Dateien, die Umgebung und das Speichermanagement gekoppelt.
Eine Race Condition tritt dann auf, wenn zwei (oder mehr) Prozessoren auf die gleichen Daten zugreifen. Durch die "zufälle" Verzahnung der ausgeführten Instruktionen kann es dann vorkommen, dass Updates verloren gehen (Lost Update), weil ein Prozessor einen veralteten Wert zurückschreibt und damit einen neueren Wert überschreibt. Gegen Race Conditions hilft die Serialisierung des Kritischer Abschnitt (Critical Section) mit Gegenseitiger Ausschluss (Mutual Exclusion, Mutex), also dem Schutz vor gleichzeitiger Ausführung.
Der Scheduler implementiert die Entscheidung, welcher Thread als nächstes ausgeführt wird. Er setzt auf den Mechanismus des Dispatcher, der die Entscheidung auf die Hardware bringen muss, d.h. welcher letztlich den Umschaltmechanismus implementiert.
Eine Semaphore ist ein Synchronisationsobjekt, welches einen Integer-Zähler beinhaltet. Der Zähler kann durch die Operationen P() (Prolaag, in Python acquire) erniedrigt und V() (Verhoog, in Python release) erhöht werden. Der Zählerwert kann vorinitialisiert werden. Fällt bei einem P()-Aufruf der Zähler auf Null, muss der rufende Thread warten.
Ein Lock, was den gegenseitigen Ausschluss zwischen Prozessoren realisiert. Dabei wird eine bool'sche Variable verwendet, die anzeigt ob der kritische Abschnitt frei ist, oder nicht. In der lock-Operation wird diese Variable atomar getestet und geschrieben; ist der kritische Abschnitt frei, kann der rufende Thread zurückkehren, ansonsten muss er warten, bis das test-and-set einen freien Abschnitt anzeigt. In der unlock-Operation wird die bool'sche Variable zurück gesetzt.
Der Thread (manchmal auch Leichtgewichtsprozess) ist die Einheit des Schedulings. Er teilt sich den Speicher mit allen anderen Threads in einem Prozess, weshalb zwischen Threads eines Prozesses schnell und effizient (und teilw. auch transparent für das Betriebssystem) gewechselt werden kann. In BSB kümmern wir uns nicht um Isolation, weshalb es keinen Unterschied zwischen einem Prozess und einem Thread gibt.
Ein Lock, was den gegenseitigen Ausschluss zwischen Prozessoren realisiert. Dabei werden zwei Integer-Zähler verwendet, der eine zeigt das nächste auszugebene Ticket an, der andere das aktuell bearbeitete Ticket. In der lock-Operation wird ein Ticket ausgeben und aktiv gewartet, bis das Ticket mit dem nächst zu bearbeitenden Ticket übereinstimmt. Bei der unlock-Operation wird lediglich das als nächstes zu bearbeitende Ticket um eins erhöht.
Beim Warten unterscheidet man grundlegend das aktive Warten (busy waiting) und das passive Warten. Der Prozessor wird beim aktiven Warten immer wieder die Bedingung überprüfen, und sobald sie sich erfüllt hat, weiterlaufen können. Beim passiven Warten wird der wartende Thread verdrängt und nicht in den Bereit-Zustand versetzt, solange die Bedingung nicht erfüllt ist. Erst wenn sie erfüllt wird, wird der wartende Thread wieder aufgeweckt und in den Bereit-Zustand versetzt, sodass der Scheduler ihn wieder einplanen kann. Während des aktiven Wartens gibt es keine andere Aktivität auf dem Prozessor, während beim passiven Warten andere Threads ausgeführt werden können.
1.9.1