Aufgabe 3: Pro-/Epilog

Wenn Geräte uns Unterbrechen, dann tun sie das oft nicht grundlos. Eine Tastatur möchte uns beispielsweise auf einen neuen Tastendruck hinweisen, den wir abholen und verarbeiten können. Aber damit verändern wir auch den Zustand des Systems.

Bleiben wir beim Beispiel Tastatur: Die Unterbrechungsbehandlung legt neue Tasten in einem Puffer, führt also ein produce aus. Unser Hauptprogramm entnimmt in einer Endlosschleife aus diesem Puffer, also ein consume. Wenn wir unser System damit starten, wird main ausgeführt, und in der Schleife consume aufgerufen. Wenn nun eine Unterbrechung, ein Tastendruck, kommt, dann wird der Ablauf unterbrochen, und die Unterbrechungsbehandlung führt das produce aus. Danach wird die Ausführung des Hauptprogramms fortgesetzt.

Was ist, wenn wir einfach naiv einen Puffer implementieren? Nun, die Variable pos wird von beiden verwendet, wenn consume ungünstig bei --pos unterbrochen wird, kann es ein Lost Update geben.

Ein bewährtes Hausmittel gegen das Erzeuger-Verbraucher-Problem ist der gegenseitige Ausschluss. Einfach die kritischen Abschnitte im Quelltext mit einem Mutex schützen und… es verklemmt sich, wenn die main gerade in consume lock() aufgerufen hat, und dann produce in der Unterbrechungsbehandlung ebenfalls lock versucht aufzurufen.

Mit viel Überlegung und atomaren Operationen wie Compare-And-Swap (CAS) können wir ein lock-freies consume und produce entwickeln – was auch wunderbar funktioniert.

Dieser Ansatz kann sehr effizient sein, stellt jedoch keine generische Lösung dar. Schlimmer noch, bei komplexeren Datenstrukturen kann eine derartige weiche Synchronisation sehr schnell kompliziert und damit auch fehleranfällig werden. Wenn wir nun jedoch ein erfolgreiches Betriebssystem schreiben wollen, müssen wir den Treiber- und Anwendungsentwicklern entgegenkommen und ihnen einfache Werkzeuge für solche Synchronisationsprobleme in die Hand geben – denn sonst wird unser Betriebssystem nicht genutzt.

Ein derart einfaches Werkzeug ist die harte Synchronisation: Dabei sperren wir mittels cli erst die Interrupts, bevor wir consume aufrufen. Sollte nun eine Unterbrechung ankommen, so wird diese verzögert, bis wir die Interrupts mit sti wieder freigeben. Erst danach wird die Unterbrechungsbehandlung aufgerufen und das produce ausgeführt.

Unsere einfache naive Implementierung vom Anfang ist also ausreichend. Aber was, wenn eine weitere Unterbrechung kommt? Nun, diese geht dann verloren.

Wir haben mit der harten Synchronisation nun eine einfache und wartbare Variante, welche aber hohe Latenzen verursacht und im schlimmsten Fall sogar Unterbrechungsanfragen verliert. Ideal wäre ein Hybrid, welcher die Vorteile von weicher und harter Synchronisation vereint, aus dem optimistischen und pessimistischen Ansatz einen Realistischen macht – was auch die Idee hinter dem Prolog/Epilog-Modell ist. Hierbei erledigt der Prolog das Nötigste auf der Ebene 1 mit gesperrten Interrupts.

Der Epilog arbeitet auf einer neuen Zwischenebene, der Ebene ½, bei welcher jedoch Unterbrechungen wieder erlaubt sind. Analog zu den Operationen für die Interruptebene 1 aus der harten Synchronisation definieren wir Operationen für die Ebene ½. Mit cli wird Ebene 1 betreten und mit sti verlassen, bei Ebene ½ sind das enter und leave. Das Äquivalent der Interruptleitung bei Ebene 1 ist die Funktion relay bei Ebene ½.

Beim Programmablauf wechseln wir vor einem kritischen Abschnitt mit enter auf die Ebene ½. Nach dem Abschnitt können wir diese mit leave wieder verlassen. Bei einem Interrupt wird direkt auf die Interruptebene 1 gewechselt, und dort der Prolog ausgeführt, welcher die nötigsten Arbeiten erledigt, beispielsweise die Daten vom Gerät abholt. Anschließend wechselt er mit relay auf die Ebene ½, und führt dort den Epilog aus, welcher beispielsweise die weitere Verarbeitung der abgeholten Daten übernimmt. Danach wird mit leave auch diese Ebene verlassen, und die Anwendung auf der Ebene 0 weiter ausgeführt.

Dieser Ansatz gibt den Treiber und Anwendungsentwickler ein einfaches Programmiermodell zur Hand, bedeutet aber allerdings einen gewissen Mehraufwand für uns. Ebenfalls stellt auch die neue Ebene einen gewissen zusätzlichen Aufwand zur Laufzeit dar, reduziert aber den Interruptverlust. Alles in allem stellt dies einen guten Kompromiss aus den beiden vorherigen Ansätzen dar. Die Umsetzung für unser Beispiel sieht auch entsprechend einfach aus, im Hauptprogramm schützen wir das consume mit enter und leave, das produce wird in den Epilog geschoben.

Beispiel: Während der Ausführung wird ein enter vor dem consume ausgeführt, welches auf die Ebene ½ wechselt. Wenn nun eine Unterbrechung – zum Beispiel durch einen Tastendruck kommt, wird auch diese Ebene ½ unterbrochen, und auf der Ebene 1 der Prolog ausgeführt. Dieser wird nun die Taste abholen und zwischenspeichern. Anschließend führt er relay aus, was einen Wechsel in die Ebene ½ versucht. Da diese Ebene aber gerade belegt ist, wird die Ausführung des Epilogs verzögert, in dem wir ihn in eine Warteschlange einhängen. Wir setzen den unterbrochenen Ablauf fort, consume wird fertig ausgeführt, und mit leave wird ein Wechsel auf die Ebene 0 initiiert. Hier wird jetzt allerdings zuerst geprüft, ob noch die Ausführung eines Epilogs anhängig ist – was auch der Fall ist. Dieser verzögerte Epilog wird nun ausgeführt, und nun wird beispielsweise die zwischengespeicherte Taste im produce verarbeitet. Selbst langsame I/O intensive Operationen wie die Ausgabe der Taste auf dem Bildschirm sind nun kein Problem. Im Anschluss wird diese Ebene mit leave wieder verlassen, und das Hauptprogramm führt seine Arbeit fort.