Microkernel: Exokernel und L4

Zusammenfassung

Der L4 und der Exokernel, sind zwei Varianten der sogenannten µ-Kernel. Es werden kurz die Motivation für diesen Typus Kernel vorgestellt und danach die Charakteristika der beiden Modelle. Beim Exokernel ist dies sicheres Multiplexen der Hardware, Secure Bindings und Downloadable Code. Der L4 hält sich an traditionellere µ-Kernel-Konzepte und impementiert nur absolut notwendige Abstraktionen im Kernel. Dies sind nach den L4 Entwicklern eine Speicherabstraktion, eine Abstraktion der CPU (Threads, Scheduler) und der Interprozesskommunikation (IPC).

Motivation

µ-Kernelentwickler motivieren µ-Kernel gegenüber monolithischen Kernel, insbesondere in drei Punkten:

• hohes Abstraktionsniveau der Hardwareschnittstellen verhindert Flexibilität und demotiviert Innovation der Anwendungsentwickler bei der Implementation – neue Abstraktionen müssen auf bestehenden Abstraktionen aufsetzen.¹
• erschwerte Wartung des Kernels, denn alle Kernelbestandteile im monolithischen Kernel teilen sich einen Adressraum im Speicher. Somit kann ein Kernel-Prozess direkt auf einen anderen zugreifen. Klare Schnittstellendefinitionen zwischen den Komponenten sind nicht vorhanden oder können unterlaufen werden, und somit zu einem nicht zu überschauendem Kausalitätensystem führen.
• Gefährdung der Systemstabilität aus dem selben Grund wie zuvor: Ein Kernelprozess kann in den Speicher eines anderen schreiben und Code oder Daten manipulieren.

¹ Datenbankmanagementsysteme implementieren ein eigenes System, um Daten (Tabelle, Beziehungen, Indizies) auf der Festplatte zu speichern, welches unnötigerweise auf dem bestehenden Dateisystem implementiert wird.

Exokernel

Ein Exokernel ist kurz gesagt: Eine minimale Ausgabe eines Kernels, der wichtige Ressourcen – ohne viele Umwege über Abstraktionen – multiplext und den Anwendungen, die im Besitz einer Ressource sind, den Zugriff darauf sichert.

Prinzipien

Das Exokernelkonzept folgt drei Kernprinzipien:

1. Multiplexen der Hardware,
2. minimale Abstraktion der Hardware und
3. möglichst vollständige Repräsentation der Hardware.

Der daraus entstehende Kernel soll besonders stabil und schnell sein, denn er ist klein und überschaubar – damit auch leicht zu warten. Den Programmierern von Anwendungen räumt er viel Freiraum und großes Optimierungspotential bei der Umsetzung ihrer Algorithmen ein.

Multiplexen der Hardware heißt, dass jeder Prozess über den Kernel auf die Hardware zugreifen kann und das für ihn die Ressource scheinbar allein zur Verfügung steht – ein ähnlicher Ausdruck ist Virtualisierung. Dabei soll die Hardwarearchitektur so wenig wie möglich durch den Kernel abstrahiert werden. Das bedeutet auch, dass der Kernel sehr wenig Verwaltungsaufwand betreibt und wenig bis keine Ahnung von der Hardware hat, die er den Anwendungen gegenüber exponiert.

Dieses Vorgehen der minimalen Abstraktion steht im extremen Gegensatz zu den heute weit verbeiteten monolithischen Kerneln. Diese bieten den Prozessen eine hohe Abstraktionsebene der Hardware mit gewissen Funktionalitäten, wie zum Beispiel Arbeitsspeicher als virtueller Speicher mit Swapping oder die Festplatte als Dateisystem mit Rechteverwaltung.

Zwischen den Grundprinzipien muss aber ein Kompromiss hergestellt werden: Ohne höhere Abstraktion ist selten Multiplexen möglich. Darum beschränken sich die Ur-Implementationen (Aegis und Xok) auf das Multiplexen des Arbeitsspeichers, der CPU, der Festplatte und des Netzwerkes. Man übertreibt sicher nicht, wenn man diese als die notwendigsten Bestandteile eines Computers bezeichnet. Andere Geräte, wie zum Beispiel der Drucker werden vom Kernel nicht multiplext, dies muss dann auf Anwendungsebene geschehen.

Vollständige Repräsentation der Hardware schließt im Fall des Exokernels sogar den Zugriff auf Direct Memory Access, Translation Lookaside Buffer oder eigentlich priviligierte Prozessorkommandos auf die ein User-Level-Prozess im Normalfall keinen Zugriff hätte – alles wird in den Anwendungsbereich exportiert, was dem Entwickler beim Optimieren helfen kann. Immer natürlich unter der Prämisse, dass dem Prozess nur soviel gestattet wird, dass er andere Prozesse nicht gefährden kann.

Umsetzungsideen

Um die Hardware sicher verteilen zu können, bedient sich der Kernel einem Konzept, dass Secure Bindings genannt wird. Ein Prozess kann vom Kernel ein Secure Binding von einer Hardwareressource anfordern. Ist diese Anforderung erfolgreich, wird der Prozess der Besitzer der Ressource und hat dann die Möglichkeit die Ressource nach seinem Belieben zu manipulieren, mit anderen zu teilen oder sie wieder freizugeben. Um von einer sicheren Verteilung zu sprechen, muss eine 1-zu-1-Beziehung zwischen Besitzer und Ressource vom Kernel gesichert sein.

Um die Hardware multiplexen zu können, wird die Ressource eines bestimmten Typus in mehrere kleinere Einheiten unterteilt, die dann einzeln zugewiesen werden können. Dabei soll diese Einteilung von der Natur der Ressource so wenig wie nur möglich abweichen:

1. eine Festplatte ist in Sektoren eingeteilt,
2. der Arbeitsspeicher in Seiten,
3. der Prozessor in eine feste Anzahl von Zeitquanten und
4. eine Soundkarte könnte in Kanäle aufgeteilt werden.

Zu bedenken ist, dass man für die Festplatte oder Soundkarte das Abstraktionsniveau noch niedriger halten könnte und direkt die Hardware-Ports exponiert. Hier wird zugunsten der Multiplexing-Eigenschaft ein höheres Niveau gewählt.

Der Kernel hat die Möglichkeit durch Visible Resource Revocation und ein Abort Protocol gesponsorte Ressourcen wieder zurück zu verlangen. Die Visible Resource Revocation ist als eine Art Bitte des Kernels zu verstehen, Ressourcen von einem Typ freizugeben (z.B.: physikalischer Arbeitsspeicher). Welche konkrete Instanz (z.B.: Speicherseite Nummer x) er freigeben möchte ist dem Prozess selbst überlassen. Das Abort Protocol ist die letzte Maßnahme des Kernels, um Ressourcen wieder zu erhalten, damit wird einem unkooperativen Prozess die Ressource einfach entzogen und dieser wird darüber informiert.

Üblicherweise findet Resource Revocation im monolithischen Systemen transparent oder invisible für den User-Level-Prozess statt – schön zu veranschaulichem am Beispiel des Auslagerungsspeichers: Wird der physikalische Arbeitsspeicher knapp, lagert der Kernel Speicherseiten aus. Davon wissen die Anwendungen aber gar nichts, sie könnten höchstens eine gewisse Latenz beim Zugriff auf eine ausgelagerte Speicherseite feststellen.

Ein weiteres interessantes Konzept im Exokernel ist der Downloadable Code. Dies ermöglicht einem Prozess Code in den Kernel zu laden, der auf bestimmte Ereignisse hin ausgeführt wird und anstelle des Prozesses reagieren kann. Um die Systemstabilität zu erhalten, nutzt man Methoden wie Sandboxing und Codeverifizierung. Die aus Downloadable Code gewonnenen Vorteile sind:

1. weniger Kontextwechsel und Privilegienwechsel zwischen Kernel und Anwendungen und
2. damit einhergehend eine schnellere Reaktionszeit auf bestimmte Hardwareereignisse.

Downloadable Code wird zum Beispiel eingesetzt, um Netzwerkpakete an die zuständigen Anwendungen zu verteilen. Der Kernel führt bei einem eingehenden Ethernetpaket (seine rudimentäre Abstraktionsebene für Netzwerkkommunikation) von einem Prozess hineingeladenen Code aus, der wiederum das TCP/IP in Bruchstücken versteht und anhand von Merkmalen – wie IPAdresse und Port – bestimmen kann, ob das Paket zu seiner Anwendung gehört. Ist dies der Fall, kann er zum Beispiel die Anwendung – wenn sie geschlafen haben sollte – schedulen und das Paket an sie übermitteln, oder aber das Paket direkt beantworten ohne die Anwendung zu wecken.

Schlussbemerkung

Leider ging aus dem, für diesen Text zugrundeliegendem Papier (siehe Quellen: Exokernel) nicht hervor, welche Gründe oder Maßstäbe der Kernel für das Zurückfordern einer Ressource ansetzt. So blieben auch weitere Details ungeklärt. Da der Exokernel aber ein Konzept, eine Idee ist, bleibt der Implementation am Ende vorbehalten, in welchem Maße die gegebenen Ansätze genutzt werden.

L4

Der L4 orientiert sich im Gegensatz zum Exokernel an traditionellen (µ-)Kerneln. Und lässt nur Konzepte/Abstraktionen im Kernel zu, so sie anders nicht zu implementieren sind. Dies ist nötig, wenn sie priviligierte Operationen verwenden, die nur vom Kernel verwendet werden können. Darauf aufsetzend können weitere Abstraktionen im Userspace umgesetzt werden (z.B. Speichermanagment, Gerätetreiber, etc.).

Konzepte die im Kernel umgesetzt werden, sind ein Modell für den Adressraum (Speicherabstraktion), welches die Implementierung eines Speichermanagers im Userspace erlaubt, ein Thread-Modell und ein Modell für die IPC.

Im folgenden wird kurz auf jedes Modell eingegangen, wie es der L4 benutzt.

Prinzipien

Speicherabstraktion

Der L4 Kern stellt kein Speichermanagement bereit, wie dies monolithische Kernel oder frühere µ-Kernel tun. Im L4 gibt es nur eine einfache Abstraktion des Hardware Konzepts eines Adressraumes. Mit diesem ermöglicht dieser den geschützten Zugriff auf den Speicher aber auch das gemeinsame Nutzen von Speicher zwischen Threads. Der Kern kennt nur ein grundlegendes Adressraumkonzept und erlaubt die Implementierung der Speicherverwaltung einem Server im Usermode.

Dazu benutzt der Kern das Konzept eines rekursiv Aufbaus des Adressraumes außerhalb des Kernels. Beim Systemstart gibt es einen initialen Adressraumes, der den gesamten physikalischen Speicher umfasst und von einem initialen Speichermanager im Userspace verwaltet wird. Um andere Adressräume aufzubauen sind drei Operationen implementiert.

Map

Erlaubt dem Besitzer eines Adressraumes Seiten aus dem eigenen in einen anderen Adressraum einzublenden, falls der Empfänger einverstanden ist. Auf die Seiten sind danach in beiden Adressräumen zugreifbar.

Flush

Erlaubt dem Besitzer eines Adressraumes Seiten die er in seinem Adressraum besitzt und zuvor mit an andere direkt oder indirekt vergeben hat, aus den anderen Adressräumen zu entfernen.

Grant

Erlaubt dem Besitzer eines Adressraumes Seiten aus dem eigenen in einen anderen Adressraum zu verschieben, falls der Empfänger einverstanden ist. Die Seite ist danach nicht mehr im Adressraum des ursprünglichen Besitzers vorhanden.

Mit diesen 3 Operationen ist es möglich Speichermanagement und Paging außerhalb des Kernels zu implementieren. Dafür sind prinzipiell nur die beiden Befehle map und flush notwendig.

Die Befehle grant und map benötigen IPC, da sie auf das Einverständnis des Empfängers angewiesen sind. Der zugehörige ipc-Aufruf ist zwar an dem Empfänger adressiert, daß eigentlich einblenden in den Adressraum des Threads übernimmt aber natürlich der Kernel. Der flush Befehl ist als eigenständiger Systemaufruf implementiert.

Um Speicher anzufordern, fragt ein Thread einen Speichermanager an, der diesem dann den entsprechenden Speicher, so dies möglich ist, in dessen Adressraum einfügt. Zur Kommunikation mit dem initialen Speichermanager gibt es ein $\sigma _{0}$-Protokoll.

Threads und Scheduler

Der Kern kennt Threads als Abstraktion für eine Ausführungseinheit. Ein Task sind mehrere Threads mit dem gleichen Adressraum. Dies unterscheidet sich nicht wesentlich von gängigen Kerneln, lediglich die Implementierung ist stark optimiert (Arrays statt Listen, etc) und die Systembefehle zur Erstellung/Stoppen/Manipulieren der Threads unterscheidet sich etwas, ebenso wie die Threads ausgeführt werden (Scheduler). Die Motiviation Threads im Kernel zu haben ist vorrangig die, daß jeder Thread einen Adressraumes besitzt, und Änderungen an diesem vom Kern kontrolliert werden müssen.

Der L4 besitzt einen prioritätsbasierten, preemptiven Scheduler, der vom Userspace aus manipulierbar ist (thread_schedule). Desweiteren gibt es die Möglichkeit für Threads ihre aktuelle Zeitscheibe (thread_switch) an einen anderen Thread abzugeben, was auch zur implementation eines Userspace Schedulers verwendet werden kann. Bei ipc-Aufrufen wir implizit ein thread_switch ausgeführt.

Wie der Scheduler im Kernel genau implementiert ist, wird vom L4 nicht genau definiert, um mögliche Optimierungen zuzulassen. Er muss das Vergeben von Prioritäten und Zeitscheiben an Threads zulassen.

Interprozesskommunikation

Um Kommunikation zwischen den Threads zu ermöglichen, muss der Kern konsequenterweise auch IPC unterstützen. Der Kern kann so ipc-Aufrufe überprüfen und gegebenenfalls umleiten. Desweiteren wird diese auch, wie schon erwähnt, für die die grant und map Operationen benötigt, wobei wie schon beschrieben, das Einbinden des Speichers in den Adressraum des Empfängers der Kern übernimmt, er also die Nachricht selbst interpretiert.

Die IPC überträgt Nachrichten synchron und ungepuffert zwischen 2 Threads. Dafür muss Einverständnis zwischen Sender und Empfänger geben. Eine Nachricht können beliebige Daten sein oder der Verweis auf beliebige Speicherseiten für map und grant.

Implementiert ist dies so, daß es IPC-Aufrufe jeweils für das Senden und Empfangen gibt (sowie für senden&empfangen (rpc) bzw. empfangen und senden). Der Sender blockiert bis seine Nachricht angenommen wurde (oder Timeout) und der Empfänger wartet bis er eine Nachricht eines bestimmten Senders erhält (oder Timeout).

Da die Performance eines µ-Kernels stark von der IPC abhängt, ist diese im L4 stark für eine Architektur optimiert. Desweiteren verwendet er 3 Konzepte zur Optimierung: Passing Short Messages, Copying Large Data Messages, Lazy Scheduling. Bei Interesse empfiehlt sich ein Blick in das Paper. Dort wird die IPC des L4 mit anderen µ-Kernel verglichen und gezeigt, daß diese performant implementiert werden kann. Die schlechte Performance früherer µ-Kernel in diesem Bereich, war einer der Hauptgründe, weswegen diese wieder unpopulärer wurden.

Desweiteren enthält der µ-Kernel ein Konzept zur Überwachung der IPC (Clans). Dies ist nicht zwingend nötig, wird von Entwicklern aber so begründet, daß dies die Performance des Kernels, speziell der IPC, nicht stark beeinträchtigt und im Userspace nur mit größeren Performanceeinbußen möglich wäre.

Beispiele für die Verwendung/Umsetzung

Gerätetreiber

Zur Implementierung von Gerätetreibern im Userspace ist zum einen der I/O Zugriff (Steuern/Übertragen von Daten) auf das Gerät und das Empfangen von Interupts von dem Gerät nötig. Hierzu werden die bekannten Abstraktionen Adressraum und IPC verwendet um dies für im Userspace verfügbar zu machen.

I/O Zugriff auf den I/O-Bereich eines Gerätes wird dadurch erreicht, daß dieser in den Addressraum eines Thread eingeblendet wird. Dies funktioniert offensichtlich mit Memory-Mapped I/O, aber auch mit I/O Ports. Dies hängt von der gegebenen Hardware ab. Die x86 Architektur erlaubt den Zugriff auf Ports über eine kleine Speicherseite, diese kann aber nicht in den Hauptspeicher gemappt werden. Daher werden diese in einem seperaten Adressraum verwaltet. Dieser ist 64kb groß und jeder physische Port x muss in diesem Adressraum bzw. dem I/O Adressraumes an die gleiche Adresse x gemappt werden. Ein Treiber kann somit Zugriff auf die I/O Geräte erhalten, indem er den entsprechenden Bereich von einen Speichermanager erhält und diesen dann entsprechend verwendet. Der Speicher z.B. eines Graphikgerätes könnte in den Adressraum des Treibers gemappt und verwendet werden, während dieser das Gerät über den in den Adressraum „gemappten“ I/O port steuert. DMA ist analog möglich.

Interrupts Desweiteren muss der Kernel einen Interrupt in den Userspace weiterleiten, um dem Treiber das Behandeln des Interrupts zu ermöglichen. Dies wird erreicht, indem der Kernel Interrupts in IPC Nachrichten umwandelt und an einen assozierten Thread sendet. Der Kernel muss nichts über die Bedeutung des Interrupts wissen. Er weist jeder Hardware eine spezielle Thread-Id zu und sendet für einen Interrupt eine leere Nachricht mit dieser Id. Ein Treiber assoziert sich mit dem ipc-Aufruf ASSOCIATE INTR für eine Interrupt und kann diesen nanach mittels des ipc-Aufrufs RECEIVE INTR empfangen.

Schlussbemerkung

Der L4 setzt im Gegensatz zum Exokernel eine zum Teil höhere Abstraktionseben ein. Zum Beispiel gibt es im Exokernel nur Systemaufrufe, die man für die Impementierung allgemeinerer IPC-Aufrufe nutzen kann. Es gibt eine feste API für die Implementation des L4 Kernels, sowie die genannten Konzepte. Die eigentlich Implementierung des Kernel muss auf die verwendete Architektur optimiert werden, vor allem um eine performante Interprozesskommunikation zu erreichen. Dies ist aber nur der kleine Kernel, die im Userspace implementierten Server/Applikationen können, da sie die feste API verwenden, leicht portiert werden.

Quellen

• Exokernel: An Operating System Architecture for Application-Level Resource Management

– Dawson R. Engler, M. Frans Kaashoek, and James O’Toole Jr. - [1]

• Exodisk: maximizing application control over storage management – Robert Grimm [2]
• L4: Liedtke, J. "On µ-Kernel Construction." In Proceedings of the Fifteenth ACM Symposium on Operating System Principles (Copper Mountain Resort, CO. Dec. 3-6). ACM Press, New York, NY, 1995, pp. 237-250.
• L4: L4 Reference Manual 486, Pentium, Pentium Pro (1996) Version 2.0, Jochen Liedtke
• L4 Gerätetreiber Beispiel: [3]