Aufgabe 3 – Prolog/Epilog-Modell

Transkript zum Übungsvideo (Folien ).

Rein oberflächlich betrachtet ist bei der Musterlösung zu Aufgabe 3 kein Unterschied zur vorherigen Aufgabe erkennbar, Unterbrechungen werden wie gewohnt im Round Robin-Verfahren von den Kernen abgearbeitet. Aber unter der Haube steckt eine Änderung, die es in sich hat: Bisher haben wir lediglich Interruptsperren verwendet, um kritische Abschnitte in StuBS zu schützen. Stattdessen kommt nun das Prolog/Epilog-Modell zum Einsatz.

Das bedeutet nun nicht, das wir gänzlich ohne cli und sti auskommen – vereinzelt werden diese weiterhin noch gebraucht, um sehr kurze Abschnitte zu sichern. Aber in Anwendungen nutzen wir nun stattdessen den Epilog, wessen Funktionen enter, leave und relay in Guard implementiert werden. Die Treiberschnittstelle Gate bietet statt trigger nun prolog und epilog an. Entsprechend müssen auch die Treiber sowie die Unterbrechungsbehandlung angepasst werden. Da Epiloge auch verzögert werden können, stellt GateQueue eine Epilogwarteschlange mit den elementaren Funktionen enqueue und dequeue zur Verfügung.

Während in OOStuBS insgesamt eine verkettete Liste ausreicht, braucht in MPStuBS jeder Kern eine eigene Warteschlange. Dadurch stellen wir sicher, dass der Epilog auch auf derselben CPU wie der Prolog ausgeführt wird. Dabei darf in einer Warteschlange derselbe Epilog nicht mehrfach vorkommen, also beispielsweise, wenn wir auf einer CPU lange in Ebene ½ sind und dort bereits zwei Tastaturunterbrechungen und Prologe hatten, dann ist dennoch nur ein Tastaturepilog in dieser Warteschlange.

Diese Designentscheidung macht uns das Leben einfacher, da wir den Verkettungszeiger – den next pointer – für die Epilogwarteschlange einfach als Klassenattribut in Gate anlegen können, wie der Epilog im Beispiel der beiden Tastaturprologe das behandeln soll, bleibt euch überlassen, eine Möglichkeit ist hierfür ein Ringpuffer, um mehrere Tasten speichern zu können. Oder aber nur eine Taste wird gespeichert, und die andere verworfen – was konzeptionell kein großer Unterschied ist, nur ein Puffer der Länge 1.

Bei MPStuBS kann es nun aber durchaus vorkommen, das derselbe Epilog in “unterschiedlichen” Epilogwarteschlangen – beispielsweise auf CPU 1 und 3 – gleichzeitig eingereiht ist. Für die Tastatur ist das nun noch nicht wichtig, jedoch brauchen wir dieses Verhalten in späteren Aufgaben noch, für Timer und Interprozessorinterrupts. Und im Mehrkernbetrieb ist außerdem darauf zu achten, dass zu keinem Zeitpunkt mehr als ein Kern auf der Epilogebene arbeitet. Dies lässt sich mit einem sogenannten Big Kernel Lock bewerkstelligen – einer Umlaufsperre, welche dafür sorgt, dass andere Kerne, welche in die Epilogebene wollen, aktiv warten, wenn diese Ebene gerade belegt ist. Für die Implementierung muss hier der Ticketlock verwendet werden. Er ist nicht nur fairer, sondern aufgrund von Cacheeffekten bei unserer Testhardware – Stichwort Hyperthreading – kann es bei einem Spinlock vorkommen, dass zwei Kerne komplett verhungern. Und obwohl es nur um wenige Codezeilen geht, sollte man auch die Reihenfolge von Sperraufrufe genau durchdenken.

Das gewünschte Verhalten von MPStuBS vertiefen wir an einem Beispiel mit zwei Kernen: Zuerst wechselt CPU 0 mit enter auf die Epilogebene. Danach führt CPU 1 ebenfalls ein enter aus, jedoch ist die Ebene belegt, und sie muss warten. Sobald CPU 0 dann fertig ist und wieder auf die Anwendungsebene wechselt, kann CPU 1 den kritischen Abschnitt betreten. Nun wird CPU 0 durch ein Ereignis unterbrochen, wechselt auf die Interruptebene und führt den Prolog aus. Im Anschluss wird relay ausgeführt, und da diese CPU zum Zeitpunkt der Unterbrechung nicht in der Epilogebene war, wird nun versucht in die Ebene ½ zu wechseln und dort den Epilog auszuführen. Allerdings ist diese Ebene gerade von CPU 1 belegt, also muss aktiv gewartet werden bis diese wieder frei wird. Währenddessen wird die CPU 1 unterbrochen, auf der Interruptebene wird der Prolog ausgeführt, und relay aufgerufen. Da die CPU sich bei der Unterbrechung jedoch bereits selbst auf Ebene ½ befand, wird der Epilog in die Warteschlange gehängt, und die vorherige Ausführung fortgesetzt. Sobald CPU 1 damit fertig ist, wird mittels leave versucht die Ebene zu verlassen, und dabei festgestellt, dass noch ein Epilog auf dieser CPU anhängig ist – der von der letzten Unterbrechung. Dieser wird abgearbeitet, und anschliessend, da die Epilogwarteschlange der CPU nun leer ist, die Ebene wirklich verlassen. Nun kann CPU 0, welche die ganze Zeit aktiv gewartet hatte, endlich die Ebene ½ betreten und den Epilog zur ersten Unterbrechung ausführen. Da auch bei ihr kein weiterer Epilog in der Warteschlange ist, wechselt auch sie danach zurück auf die Anwendungsebene.