WEBVTT

00:00.000 --> 00:11.200
Bis jetzt hatten wir in unserem Stubs einen festen Faden pro CPU, haben also für jede

00:11.200 --> 00:13.600
Anwendung einen Kern exklusiv verwendet.

00:13.600 --> 00:19.520
Das wollen wir in dieser Aufgabe mittels kooperativen Scheduling so ändern, dass wir quasi beliebig

00:19.520 --> 00:21.960
viele Anwendungen gleichzeitig laufen lassen können.

00:21.960 --> 00:26.920
Im Beispiel laufen nur 9 Zähleranwendungen parallel.

00:26.920 --> 00:31.760
Dabei wird in der Ausgabe für jeden Kern eine eigene Farbe verwendet, um das Durchwechseln

00:31.760 --> 00:33.400
zu verdeutlichen.

00:33.400 --> 00:36.680
Externe Geräte wie die Tastatur bleiben natürlich auch weiterhin aktiv.

00:36.680 --> 00:42.680
Für die Umsetzung müssen wir nun erstmal down the rabbit hole und sowohl tiefer in

00:42.680 --> 00:48.880
die x86 Architektur als auch die System5 API einarbeiten, um in Assembler einen Kontextwechsel

00:48.880 --> 00:50.040
implementieren zu können.

00:50.040 --> 00:56.280
Im Anschluss sollen die Anwendungen so umgebaut werden, dass diese als Threads in einem Scheduler

00:56.280 --> 00:58.400
verwaltet werden können.

00:58.400 --> 01:02.400
Diese Verwaltung soll im Ordner thread bereitgestellt werden.

01:02.400 --> 01:05.560
Der systemneue Kontextwechsel wird in machine implementiert.

01:05.560 --> 01:11.200
Der Scheduler erlaubt Threads zur Ausführung dynamisch hinzuzufügen und wieder zu entfernen,

01:11.200 --> 01:14.400
mittels einer Liste von Zeigern auf Thread-Objekten.

01:14.400 --> 01:18.880
Mit guarded Scheduler gibt es eine einfache Systemaufruf Schnittstelle, damit dies auch

01:18.880 --> 01:24.000
von Anwendungen selbst gesteuert werden kann, zum Beispiel das Beenden einer anderen Anwendung.

01:24.000 --> 01:28.200
Die Anwendungen selbst sind von der Klasse thread-abgeleitet und werden in der Methode

01:28.200 --> 01:29.920
Action implementiert.

01:29.920 --> 01:34.840
Diese Methode ist in thread als pure virtual deklariert, muss also zwingend in jeder Ableitung

01:34.840 --> 01:36.760
implementiert werden.

01:36.760 --> 01:41.560
Eine Anwendung, welche das erste Mal per Kontextswitch eingelastet wird, soll ihre Ausführung bei

01:41.560 --> 01:44.680
der Methode Action beginnen.

01:44.680 --> 01:48.720
Wir bräuchten also die Adresse dieser Methode als Einsprungsfunktion.

01:48.720 --> 01:53.000
Allerdings ist diese Adresse gar nicht zu trivial zu ermitteln, wenn wir nur den Pointer

01:53.000 --> 01:55.120
zum thread-Objekt haben.

01:55.120 --> 02:00.480
Sie ist ein virtueller Member, die tatsächliche Adresse der Funktion wird also dynamisch zur

02:00.480 --> 02:05.880
Laufzeit durch die Vtable der Tabelle virtueller Methoden ermittelt, abhängig von welcher

02:05.880 --> 02:07.640
Anwendung das Objekt tatsächlich ist.

02:07.640 --> 02:15.160
Und wie so eine Vtable aufgebaut ist, ist natürlich wieder nicht im C++-Standard spezifiziert,

02:15.160 --> 02:18.280
sondern abhängig vom jeweiligen Übersetzer.

02:18.280 --> 02:22.680
Wir wollen aber eine generische Lösung, versuchen also gar nicht erst selbst diese Struktur

02:22.680 --> 02:27.360
nachzulaufen, sondern lassen den Übersetzer den entsprechenden Code generieren, mittels

02:27.360 --> 02:28.800
der Hilfsfunktion kickoff.

02:28.800 --> 02:35.080
Diese bekommt als Parameter den Zeiger auf den thread und ruft damit dann Action auf.

02:35.080 --> 02:39.040
Der Übersetzer muss für diesen Aufruf in kickoff entsprechend selbst die Auflösung

02:39.040 --> 02:40.440
mittels der Vtable einbauen.

02:40.440 --> 02:46.960
Unsere Einsprungsfunktion ist somit nun also nicht die Methode Action selbst, sondern kickoff,

02:46.960 --> 02:48.880
welches dann eben diese Methode aufruft.

02:48.880 --> 02:54.520
Und entsprechend müssen wir auch den Stack vorbereiten, was wir über die Funktion prepare

02:54.520 --> 02:55.520
context erledigen.

02:55.520 --> 03:01.120
Diese erhält als ersten Parameter die Adresse des Top of Stack, also das obere Ende des

03:01.120 --> 03:02.520
jeweiligen Stacks.

03:02.520 --> 03:07.600
Dazu soll für jeden Thread ein 4096 Byte großer Speicher reserviert werden.

03:07.600 --> 03:13.920
Der zweite Parameter ist der Funktionszeiger zur eben erwähnten kickoff-Funktion, welcher

03:13.920 --> 03:17.200
mit den in param spezifizierten Parameter aufgerufen wird.

03:17.200 --> 03:23.040
Der Rückkabewert ist die Adresse des letzten Eintrags, die auf diesem Stack hinzugefügt

03:23.040 --> 03:26.560
wurde, somit also der initiale Stackpointer für den Thread.

03:26.560 --> 03:31.600
Die ganze Vorbereitung des Stacks wollen wir in C++ schreiben und können für die einzelnen

03:31.600 --> 03:34.520
Einträge im Stack hervorragend die Pointer-Arrhythmetik nutzen.

03:34.520 --> 03:40.680
Dazu hilft es, sich im Zweifelsfall den Stack nochmal mit einer Skizze zu veranschaulichen.

03:40.680 --> 03:47.400
Wir reservieren für den Stack unsere Anwendungen foo und bar jeweils 4K-Speicher, zum Beispiel

03:47.400 --> 03:51.080
indem wir ein CharArray mit 4096 Einträgen anlegen.

03:51.080 --> 03:57.360
Der Übersetzer wird uns die Arrays übrigens gleich richtig im Speicher ausrichten, alternativ

03:57.360 --> 04:00.640
könne man das auch über das Schlüsselwort alignAs erreichen.

04:00.640 --> 04:08.960
Unser Top of Stack bei foo ist somit am oberen Ende des Arrays 4096 Bytes weiter als die

04:08.960 --> 04:09.960
Startadresse.

04:09.960 --> 04:17.080
Bitte nicht instinktiv 4095 nehmen, wie man bei diesem Array auf den höchsten Eintrag

04:17.080 --> 04:18.080
zugreifen würde.

04:18.080 --> 04:24.240
Denn das würde zwar derzeit auch noch funktionieren, solange wir kein SSI verwenden, aber die Speicherzugriffe

04:24.240 --> 04:29.000
auf dem Stack wären da nicht mehr ausgerichtet, was eine langsame Zugriffsgeschwindigkeit

04:29.000 --> 04:30.000
zur Folge hätte.

04:30.000 --> 04:36.720
Da der C-Standard keine Pointer-Arrhythmetiken mit Void-Pointer erlaubt, casten wir den Top

04:36.720 --> 04:41.080
of Stack zu einem Void-Pointer-Pointer, dann geht auch wieder die Pointer-Arrhythmetik.

04:41.080 --> 04:47.800
Ich habe die Variable passenderweise auch RSP genannt und wir bilden da nun auch die Push-Semantik

04:47.800 --> 04:53.320
vom x86 Stack nach, um beispielsweise einen konstanten Wert darauf zu legen.

04:53.320 --> 05:00.120
Zuerst ein RSP-, das aufgrund der Pointer-Arrhythmetik bei 64 Bit die Adresse um 8 Bytes verringert

05:00.120 --> 05:04.720
und dann den Hexwert ThatBeefBadFood an die resultierende Adresse schreibt.

05:04.720 --> 05:11.200
Dies wird dank littleandian wieder rückwärts, also beginnend mit dem kleinstwertigen Byte

05:11.200 --> 05:18.600
an die derzeitige Adresse geschrieben, was im Feld 4088 des CharArrays 0x0d entspricht.

05:18.600 --> 05:26.760
Das höchstwertige Byte 0xde steht 7 Bytes weiter, in Stack-Food-Index 4095.

05:26.760 --> 05:32.600
Wenn wir nun Zeige auf Variablen und Funktionen auf diesen Stack legen wollen, funktioniert

05:32.600 --> 05:33.600
das genauso.

05:33.600 --> 05:38.960
Zuerst wieder auf den nächsten Speichereintrag springen und in diesen dann die Adresse schreiben,

05:38.960 --> 05:40.320
hier von einem Thread-Objekt.

05:40.320 --> 05:44.200
Und so kann nun der ganze Stack vorbereitet werden.

05:44.200 --> 05:48.840
Der Rückgabewert von PrepareContext ist dann auch die Adresse, auf welche die Variable

05:48.840 --> 05:50.320
RSP am Ende zeigt.

05:50.320 --> 05:57.480
Und schöne Probleme, welche uns in dieser Aufgabe leicht begegnen können, sind Stapelüberläufe.

05:57.480 --> 06:03.120
Die 4K Stack reichen zwar bei korrekter Nutzung vollkommen aus, sind aber bei Fehlern auch

06:03.120 --> 06:04.120
schnell voll.

06:04.120 --> 06:09.200
Und dann wird einfach der Speicher darunter weiter voll geschrieben, was nicht selten

06:09.200 --> 06:11.080
der nächste Anwendungs-Stack ist.

06:11.080 --> 06:15.880
Im vorherigen Beispiel liegt auch direkt unter Stack Bar der Stack Foo.

06:15.880 --> 06:21.840
Das ist besonders perfide, weil dann bei einem Fehler in Bar vielleicht Foo als erstes in

06:21.840 --> 06:23.200
einen Trap läuft.

06:23.200 --> 06:26.760
Und man dort dann lange nach einem Fehler suchen kann.

06:26.760 --> 06:28.280
Willkommen in der Dieberkölle.

06:28.280 --> 06:34.320
Sehr schnell erreicht man dieses Problem übrigens auch, wenn für die Arrays der Anwendungs-Stacks

06:34.320 --> 06:39.120
kein statischer Speicher zugewürzen wird, sondern diese auf dem initialen Stack angelegt

06:39.120 --> 06:40.120
werden.

06:40.120 --> 06:45.280
Dieser ist nämlich selbst nur 4K groß und in MP-Stubs liegen die Stacks für die verschiedenen

06:45.280 --> 06:47.400
Kerne ebenfalls direkt hintereinander.

06:47.400 --> 06:51.000
Einen Heap haben wir noch nicht.

06:51.000 --> 06:56.000
Die dynamische Speicherverwaltung kommt erst später, ebenso wie dynamische Vergrößerung

06:56.000 --> 06:59.600
der Stacks und zwar nächstes Semester in Betriebssystemtechnik.

06:59.600 --> 07:05.320
Aber wir können uns das Leben trotzdem etwas vereinfachen, zum Beispiel indem wir versuchen,

07:05.320 --> 07:07.400
solche Überläufe zu erkennen.

07:07.400 --> 07:11.920
Dazu nehmen wir einen sogenannten Stack Canary, einen Stapelkanadienvogel.

07:11.920 --> 07:18.240
Im Bergbau wurden früheres dynaminsgebenden Kanadienvögel ganz mit nach unten genommen.

07:18.240 --> 07:21.760
Solang sie dort einfach rumgezwitschert haben, war alles in Ordnung.

07:21.760 --> 07:26.200
Aber wenn sie leise wurden und tot von der Stange fielen, war matte Wetter, zu wenig

07:26.200 --> 07:28.880
Sauerstoff in der Luft.

07:28.880 --> 07:32.960
Unser Kanadienvogel in Stubs besteht aus einem magischen Wert.

07:32.960 --> 07:35.880
Den schreiben wir ganz unten auf jeden Stack.

07:35.880 --> 07:39.360
Im Beispiel 0x55AA.

07:39.360 --> 07:43.960
Solange dieser magische Wert intakt ist, der Kanadienvogel also noch lebendig ist, passt

07:43.960 --> 07:44.960
alles.

07:44.960 --> 07:49.480
Aber wenn er mal nicht mehr dort steht, dann wird auch unsere Luft dünn.

07:49.480 --> 07:53.520
Er wurde überschrieben, der Stapel ist vermutlich übergelaufen und es droht ungemach.

07:53.520 --> 07:59.640
Ein guter Zeitpunkt um diesen Wert zu prüfen, ist natürlich vor jedem Kontextwechsel.

07:59.640 --> 08:04.960
Ob ihr diesen Warnmechanismus implementieren wollt, bleibt euch überlassen.

08:04.960 --> 08:08.960
Er kann euch aber unter Umständen eine langwierige Suche nach Käfern ersparen.

08:08.960 --> 08:18.920
Wir haben nun Stacks und Threads detailliert behandelt.

08:18.920 --> 08:22.600
Widmen wir uns nun der Thread-Verwaltung, dem Scheduler.

08:22.600 --> 08:27.560
Dieser hat mit der ReadyList eine Warteschlange für Threads, welche über die Methode ready

08:27.560 --> 08:28.960
gefüllt wird.

08:28.960 --> 08:32.920
Schedule startet die Ausführung des ersten Threads, übergibt also die Kontrolle den

08:32.920 --> 08:33.920
Choroutinen.

08:33.920 --> 08:39.680
Mit resume wird zum nächsten Thread gewechselt, je nachdem was als nächstes in der ReadyListe

08:39.680 --> 08:40.680
liegt.

08:40.680 --> 08:45.560
Mit exit kann ein Thread sich selbst und mit kill einen beliebigen anderen beenden.

08:45.560 --> 08:49.520
Er wird also nicht mehr in die Warteschlange zugefügt bzw. aus ihr entfernt.

08:49.520 --> 08:55.080
Aber sorgt für diese Aufgabe unbedingt dafür, dass es immer genug Threads in der Warteschlange

08:55.080 --> 08:58.000
gibt, sie also auch trotz kill niemals leer läuft.

08:58.000 --> 09:04.280
Da wir in dieser Aufgabe noch auf kooperative Scheduling setzen, müssen unsere Anwendungen

09:04.280 --> 09:09.280
zugeschrieben werden, dass sie die Kontrolle freiwillig abgeben, eben durch regelmäßige

09:09.280 --> 09:11.560
Aufrufe von Scheduler resume.

09:11.560 --> 09:16.600
In unserer Main werden die Anwendungen zu Beginn instanziert und nach der Initialisierung

09:16.600 --> 09:21.400
des Systems mittels Ready in die Warteschlange eingefügt, um mit Schedule die Kontrolle

09:21.400 --> 09:22.400
übergeben.

09:22.400 --> 09:28.080
Bei der Ausführung dieses Codes wird zu Beginn bei Schedule mittels Kontextwechsels erstmalig

09:28.080 --> 09:29.880
in den ThreadApp foo gewechselt.

09:29.880 --> 09:35.640
Dort wird kickoff aufgerufen mit dem Zeiger auf den Thread als Parameter.

09:35.640 --> 09:41.080
Dadurch wird wiederum die Action Methode aufgerufen, welche foo ausgibt und mittels resume den

09:41.080 --> 09:45.000
nächsten Thread die Kontrolle übergibt, nämlich App bar.

09:45.000 --> 09:50.840
Hier wird ebenfalls über kickoff in Action gewechselt, bar ausgegeben und wieder ein

09:50.840 --> 09:52.000
Wechsel veranlasst.

09:52.000 --> 09:56.560
Der nächste Thread wird aus der Ready Liste genommen, der derzeitige Thread wandert dorthin

09:56.560 --> 09:57.560
zurück.

09:57.560 --> 10:03.400
App foo setzt nun dort fort, wo zuletzt resume ausgeführt wurde und wiederholt nur die Schleife,

10:03.400 --> 10:08.440
gibt also erneut foo aus, bevor mittels resume wieder nach bar gewechselt wird und so weiter.

10:08.440 --> 10:14.600
Der ganze Ablauf spielt sich dabei auf der Anwendungsebene ab, sofern wir nicht durch

10:14.600 --> 10:16.960
externe Geräte unterbrochen werden.

10:16.960 --> 10:20.600
Deren Behandlungsroutinen aus der vorherigen Aufgabe funktionieren aber weiterhin.

10:20.600 --> 10:27.200
Der gezeigte Ablauf funktioniert so in O-Stops problemlos, die Konsistenz ist immer gesichert.

10:27.200 --> 10:33.040
Aber in M-P-Stops, hier können zum Beispiel gleichzeitig mehrere Kerne auf die Warteschlange

10:33.040 --> 10:36.200
zugreifen und diese ist dafür nicht ausgelegt.

10:36.200 --> 10:40.360
Aber dafür haben wir doch in der letzten Aufgabe etwas entwickelt.

10:40.360 --> 10:46.520
Wir führen einfach die Operationen vom Scheduler inklusive Kontextwechsel ausschließlich auf

10:46.520 --> 10:48.120
der Epilog-Ebene aus.

10:48.120 --> 10:53.960
Vor dem Schedule wird diese Ebene betreten, auf App foo gewechselt und dort Kickoff ausgeführt.

10:53.960 --> 10:59.600
Nun müssen wir die Ebene verlassen und um ein zauberes Design zu haben, wird dies gleich

10:59.600 --> 11:04.400
als erstes in Kickoff erledigt, damit Action auch auf der Anwendungsebene ausgeführt wird.

11:04.400 --> 11:10.720
Dort wird wieder die Ausgabe getätigt, dann wieder Epilog-Ebene betreten und der Kontextwechsel

11:10.720 --> 11:11.720
ausgeführt.

11:11.720 --> 11:18.560
App bar beginnt analog in Kickoff, Ebene verlassen, Action und Ausgabe, Epilog-Ebene wieder betreten,

11:18.560 --> 11:20.240
Kontextwechsel mittels Resume.

11:20.240 --> 11:26.240
In App foo muss nun die Ebene erst verlassen werden, bevor die Ausgabe kommt und sie dann

11:26.240 --> 11:29.480
erneut betreten wird für das nächste Resume.

11:29.480 --> 11:33.360
Dieser Ablauf wird besonders in der Ebenenübersicht deutlich.

11:33.360 --> 11:39.760
Und weil es mühselig ist, jedes Mal Guard Enter und Guard Leave vor dem Aufruf einer

11:39.760 --> 11:45.200
Scheduler-Methode zu schreiben, kapseln wir dies im Guarded Scheduler.

11:45.200 --> 11:49.600
Er hat also nach außen hin die gleichen Schnittstellen wie das Scheduler, wechsel jedoch nur in die

11:49.600 --> 12:07.360
Epilog-Ebene und agiert beim eigentlichen Aufruf als Proxy an Scheduler.