StuBS
Virtuelle CPUs und Threadwechsel

Ein Prozess ist ein Programm in Ausführung, während Threads (manchmal auch Leichtgewichtsprozesse) die Einheit des Scheduling sind. Das Scheduling-System im Betriebssystem sieht lediglich Threads. In Betriebssystembau machen wir keine Unterscheidung zwischen Threads und Prozessen, weil zum Prozesskonzept normalerweise Isolation zwischen den Prozessen gehört. Diese Isolation wird erst in der Folgeveranstaltung Betriebssystemtechnik implementiert.

Ein Thread ist also die Einheit, die vom Dispatcher zur Ausführung gebracht wird, und damit das eigentlich aktive Objekt im System. Die Ressourcen, die bei der Ausführung beansprucht werden, sind die Prozessoren. Normalerweise gibt es mehr Threads als Prozessoren, weswegen ein Multiplexing der begrenzten Prozessoren auf alle Threads stattfinden muss. Wie bei den meisten Abstraktionen im Betriebssystem soll der Nutzer, hier Thread, nichts davon mitbekommen, dass ihm den Zugriff über eine Ressource nur teilweise gewährt wird. Also soll es für einen Thread – trotz des Teilens der Prozessoren – so wirken, als hätte er einen Prozessor für sich allein. Ein Prozessor hingegen kann jeweils nur einen einzigen Instruktionsstrom gleichzeitig ausführen (wir lassen hier Hyperthreading der Einfachheit außen vor, da es konzeptuell keinen Unterschied macht).

Virtuelle Prozessoren

Virtuelle CPUs; Links: direktes Abbilden der Aktivitäten auf eine physische CPU; Rechts: jede Aktivität erhält eine virtuelle CPU, die per Multiplexing auf die physische CPU abgebildet werden

Also virtualisieren wir Prozessoren und führen das Konzept von virtuellen Prozessoren ein: Jeder Thread bekommt einen Eigenen. Dieser virtuelle Prozessor führt den Code des Threads genauso aus, wie es die echte CPU täte, wenn auch etwas langsamer und mit Unterbrechungen. Die virtuellen Prozessoren werden dann auf die Prozessorkerne verteilt.

Diese Verteilung funktioniert durch Zeitmultiplexing, d.h. dem Verteilen einer Ressource durch zeitliches Umschalten: Eine Zeit lang darf Nutzer A die Ressource verwenden, dann muss er sie abgeben und Nutzer B darf sie exklusiv für ihre Zeiteinheit verwenden. In diesem Fall wird also die physische CPU auf die virtuellen Prozessoren zeitmultiplext. Durch ein schnelles Umschalten zwischen den virtuellen CPUs und damit durch das Durchwechseln der Threads entsteht eine Pseudo-Parallelität, also der Effekt, dass es für den Endnutzer so aussieht, als würden mehrere Aktivitäten gleichzeitig ablaufen. In Wirklichkeit läuft allerdings jede Aktivität einzeln auf dem Prozessor, und wird nur ab und an durch eine andere ersetzt. So werden letztlich auf der echten CPU die Instruktionen zweier Threads ineinander verzahnt, sodass mal Instruktionen des einen Threads und dann die eines anderen Threads ausgeführt werden.

Umschalten

Während Threads und virtuelle Prozessoren konzeptuell unterschiedlich sind, kann man technisch beide Konzepte zusammen verwenden, da immer genau ein Thread einer vCPU zugeordnet ist. Daher wird ab jetzt nur noch der Begriff Thread fürs Umschalten verwendet. Beim Umschalten zwischen Threads muss aus technischer Sicht der Zustand des Prozessors gesichert werden. Dabei werden die Registerwerte auf den Stack oder in einen bestimmten Speicherbereich gespeichert und schließlich auch der Stackpointer im Speicher hinterlegt. Dann kann der Stackpointer des Ziel-Threads geladen werden. Schließlich werden die Registerwerte aus dem Ziel-Stack (oder Ziel-Struktur) wiederhergestellt und der Instruktion-Pointer zurückgesetzt (durch die ret-Anweisung). Das Umschalten soll mithilfe der Funktion context_switch() implementiert werden.

In Pseudocode sähe das so aus:

context_switch(from, to):
CPU-Zustand in *from speichern
aus *to den CPU-Zustand laden

Näheres zu den auf x86 zu sichernden Registern kann in x86-ABI: Register und Stacklayout gefunden werden.

Wichtig bei der Implementierung eines Betriebssystem ist die Trennung zwischen Strategie (Policy) und Mechanismus (Mechanism). Dem Umschaltmechanismus, also dem Stück Code, welches die Registerwerte austauscht, ist es egal, welche Scheduling-Strategie mit dessen Hilfe implementiert wird.

Beim Threadumschalten gibt es zwei Akteure: Zunächst hätten wir den Dispatcher, der den Mechanismus umsetzt. Er ist dafür zuständig, zwei bekannte Threads umzuschalten, er verfügt aber nicht über Wissen über die anderen im System vorhandenen Threads. Der Scheduler auf der anderen Seite trifft die Entscheidung, welcher Thread als nächstes laufen darf. Während der Dispatcher lediglich einmal pro Architektur implementiert wird, kann es beliebige Scheduling-Strategien zur Auswahl des nächsten Threads geben. Letztere sind sogar architekturunabhängig. Durch die Unterscheidung in Strategie und Mechanismus ist es also möglich, den Betriebssystemkern schneller auf neue Hardware zu portieren und weitere (bessere) Scheduling-Strategien unabhängig von der Architektur zu implementieren.

Erstellen von Threads

Mit context_switch() steht ein Mechanismus zur Verfügung, der von einem Kontrollfluss auf einen anderen umschalten kann. Dieser Mechanismus geht aber davon aus, dass der Thread schon einmal lief, weil er auf dem Ziel-Stack bestimmte Werte erwartet. Wie also sollen Threads behandelt werden, die noch nie gelaufen sind?

Weil das erstmalige Einlasten von Threads einen Sonderfall im Dispatcher darstellt, könnte man den Dispatcher um eine solche Abfrage erweitern. Dann müsste der Dispatcher bei jedem einzulastenden Thread nachschauen, ob er schon einmal gelaufen ist. Das erhöht die Komplexität und führt auch zu einer Performance-Reduzierung in der Laufzeit (wir erinnern uns: Umschalten passiert sehr häufig um die Pseudo-Parallelität aufrecht zu erhalten).

Daher soll der Stack bereits beim Erstellen des Thread-Objekts erzeugt und derart vorbereitet werden, dass context_switch ihn verwenden kann, um zum neuen Thread zu wechseln. Welche Werte müssten dann auf dem Stack sein? Konkret stellen wir folgende Anforderungen an das initiale Einlasten eines Threads:

  • Der Umschaltmechanismus darf (und muss) nicht angepasst werden.
  • Der neue Thread kann (nach einer Initialisierung) dem Scheduler übergeben werden, auch wenn er noch nie lief, und wird trotzdem normal behandelt.
  • Der neue Thread führt, wenn er zum ersten Mal eingelastet wird, eine spezielle Funktion aus, im Fall von BSB ist dies Thread::kickoff(). Sie soll in dieser Aufgabe lediglich zur Startfunktion springen, wird aber in nachfolgenden Aufgaben wichtig.

Das erstmalige Wechseln vom Bootcode in den ersten Thread auf einer CPU ist etwas anderes und sollte nicht vermischt werden. context_launch wechselt in den allerersten Thread, weil wir den Kontext der Herkunftskoroutine nicht mehr benötigen. Alle weiteren Kontextwechsel (auch in neue Thread) erfolgen dann mit context_switch.

Präemptives vs. kooperatives Umschalten

Der Vorgang der Kontrollabgabe eines Threads kann freiwillig geschehen, bspw. durch Aufgabe der CPU oder durch Aufrufen bestimmter Syscalls. Alternativ kann dem Thread die Kontrolle über die CPU auch entzogen werden, indem bspw. ein eingestellter Timer das Betriebssystem zum Umschalten bringt (kommt in der nächsten Aufgabe).

Beim kooperativen Umschalten geben Threads selbstständig die Kontrolle ab. Falsch programmierte Threads können das System dabei lahmlegen, wenn sie die Kontrolle nie abgeben oder in einer Endlosschleife stecken bleiben. Das Betriebssystem hat keine Möglichkeit, diesen Threads die Kontrolle über den Prozessor zu entziehen. Windows 3.1 verfügte bspw. über einen kooperativen Umschalt-Mechanismus.

Das präemptive Umschalten zeichnet sich meist durch einen regelmäßigen Timer-Interrupt aus, der den gerade ausgeführten Thread unterbricht und dann das Betriebssystem dazu bringt, ihn durch einen anderen Thread zu ersetzen (zu verdrängen). Der verdrängte Thread hat dabei keine Entscheidungsgewalt: Das System behält die volle Kontrolle, auch wenn sich Threads verklemmen oder in einer Endlosschleife festhängen.

Je nach eingesetztem System wird die eine oder andere Strategie gewählt. In Echtzeitsystemen ist z.B. kooperatives Umschalten durchaus üblich. Dort kann Threads vertraut werden, da sie aus derselben Codebasis und oftmals vom selben Entwickler-Team kommen. Andererseits werden die notwendigen Berechnungen über das Laufzeitverhalten ohne den regelmäßigen Interrupt stark vereinfacht. Betriebssysteme im Desktop-Bereich hingegen verwenden üblicherweise präemptives Umschalten, da potentiell bösartige Prozesse existieren können, die oftmals auch zum Start des Systems noch gar nicht bekannt sein müssen.