Linux-Portierung auf den Mikrokern L4

Mikrokerne sind im Prinzip bis auf rudimentäre Fähigkeiten wie das Task-Switching abgespeckte Betriebssysteme. Jegliche zusätzliche Funktionalität wird zur Laufzeit dynamisch nachgeladen. Die Verwendung solcher Systeme verspricht eine Erhöhung der Modularität, der Flexibilität und der Sicherheit. Lange Zeit waren die Fachleute der Meinung, daß sich diese Vorteile aufgrund der Ineffizienz der vorhandenen Mikrokerne nicht durchsetzen lassen. Obwohl jahrelang auf diesem Gebiet geforscht und optimiert wurde, war irgendwann ein Punkt erreicht, an dem keine weiteren Verbesserungen mehr möglich schienen.

Mit der Vorstellung der Mikrokerne der zweiten Generation (Exokernel, L4) und ihrem radikal an Performance orientierten Design war das Argument der Ineffizienz vom Tisch.

Das Fehlen von speziell für sie entwickelten Anwendungen ist das größte Problem, das Mikrokerne im allgemeinen haben. Schließlich sind sie keine vollständigen Betriebssysteme, die ihr Dateisystem, Netzanbindung, Entwicklungswerkzeuge und so weiter von Haus aus mitbringen.

Programmierung nur auf anderen Plattformen

Vor diesem Problem standen Mitglieder der Betriebssystemgruppe der TU Dresden, die sich im Rahmen eines Forschungsprojektes mit der Entwicklung von echtzeitfähigen Systemen beschäftigen. Dabei verwendeten sie als Basis den von der GMD entwickelten L4-Mikrokern. Dessen Programmierung war mangels verfügbarer Werkzeuge nur durch Cross-Entwicklung auf anderen Systemen möglich. Da dies auf Dauer kein haltbarer Zustand war, entschloß sich die Dresdner Gruppe, ein vorhandenes, frei verfügbares Unix-System auf den L4 zu portieren. Aufgrund der Popularität und der dadurch bedingten hohen Verfügbarkeit von Treibern sowie der guten Portabilität, die sich in der Anzahl von Portierungen auf verschiedene Architekturen ausdrückt, fiel die Wahl auf Linux. Hinzu kam, daß die OSF mit MkLinux gezeigt hat, daß eine Portierung auf einen Mikrokern prinzipiell möglich ist - auch wenn Mach mit seiner Größe von 300 KByte vielleicht nicht als Mikrokern bezeichnet werden kann (siehe [[#literatur 1]]). Eines der Hauptziele bei der Linux-Portierung auf den L4-Mikrokern war die Erhaltung der Binärkompatibilität mit dem originalen Linux für i386-kompatible Prozessoren.

Ein anderer Grund für die Portierung eines Unix-Systems auf L4 war, daß das GMD-Produkt recht neu und dadurch noch etwas `grün' ist. Deshalb galt es, den Mikrokern zu stabilisieren, und nachzuweisen, daß die bereitgestellten Abstraktionen und Mechanismen ausreichend sowie flexibel genug sind, um eine Betriebssystem-Personality implementieren zu können.

Das Design des Mikrokerns L4 basiert auf zwei Thesen:

1. Effizienz und Flexibilität können nur durch Beschränkung des µ-Kerns auf eine minimale Menge von allgemeinen Abstraktionen und Mechanismen erreicht werden. Erfolgt die Implementierung von Strategien im Kern, wird es irgendwann eine Anwendung geben, die mit diesen nicht klarkommt. Deshalb realisiert ein L4-System Gerätetreiber und Strategien zur Speicherverwaltung sowie zum Scheduling mit Hilfe der von L4 bereitgestellten Primitive auf Nutzerebene.

2. Mikrokerne sind nicht portabel. Jede Architektur erfordert trotz gleichem Interface ihre eigenen, speziell an die Hardware angepaßten Algorithmen und Datenstrukturen, um optimale Performance zu erzielen.

Tasks realisieren Schutzkonzept

Beim Entwurf des Kerns ging der Entwickler davon aus, daß ein Mikrokern im wesentlichen Sicherheit garantieren muß. Deshalb stellt L4 Tasks sowohl als zentrale Abstraktion als auch als Sicherheitsdomäne zur Verfügung und garantiert ihre Autonomie. Als Task wird die Einheit eines geschützten Adreßraums und der darin laufenden Threads bezeichnet. Es ist einer Task nicht möglich, eine andere ohne deren Einverständnis zu manipulieren.

Linux als Serversystem auf dem L4-Mikrokern: Die L4-Anpassung erbringt die Low-Level-Dienste für den architekturunabhängigen Teil. Linux läuft komplett im User Level des Prozessors.

Da es Tasks aber trotz dieses strikten Schutzkonzeptes möglich sein muß, eine Wirkung nach außen auszuüben, implementiert L4 Interprozeßkommunikation (IPC). IPC ist ein Mechanismus zum Transfer von Informationen über Adreßraumgrenzen hinweg. Diese findet in L4 synchron und ungepuffert statt, das heißt, der Sender blockiert so lange, bis der Empfänger eine Empfangsoperation ausführt oder ein vom Sender spezifiziertes Timeout abläuft. Auf diesen IPC-Mechanismus wird nahezu alles in L4 zurückgeführt.

• Seitenfehler
  Um die Beschränkungen einer fest in den Kern eingebauten Speicherverwaltung zu vermeiden, führt L4 das Konzept der rekursiv konstruierten Adreßräume ein. Eine Task kann Seiten ihres eigenen Adreßraumes über IPC (und damit mit Zustimmung der anderen Task) in andere Adreßräume einblenden und sie durch Aufruf eines L4-Dienstes auch wieder ausblenden. Dieser Mechanismus ermöglicht es, beliebige Speicherverwaltungsstrategien zu implementieren. In L4 wird jedem Thread ein Pager zugeordnet. Greift der Thread auf eine Seite zu, die in seinem Adreßraum nicht vorhanden ist, bekommt der zugeordnete Pager eine Nachricht geschickt. Dieser beschafft die fehlende Seite und sendet sie als sogenannte Flexpage zurück. Der Transfer dieser Botschaft bewirkt ein Einblenden der im Adreßraum des Pagers bereitgestellten Seite in den Adreßraum der anderen Task und löst damit den Seitenfehler auf.
• Preemption (Verdrängung)
  Der L4-Kern implementiert Scheduling mit Zeitscheiben und harten Prioritäten. Um andere Scheduling-Strategien auf Nutzerebene implementieren zu können, stellt L4 den Preemption-Mechanismus bereit. Läuft die Zeitscheibe eines Thread ab, sendet L4 analog zum Seitenfehler eine `Zeitfehler'-Nachricht an einen zugeordneten Scheduler, der entsprechend der von ihm implementierten Strategie den nächsten Thread auswählt. Scheduler-Threads können auch die Priorität und die Länge der Zeitscheibe der von ihnen verwalteten Threads beeinflussen.
• Interrupts
  Von externen Geräten ausgelöste Hardware-Interrupts übersetzt derL4 in IPC-Nachrichten und sendet diese an die zugeordneten `Interrupt-Threads'.

Da der IPC-Mechanismus bei Mikrokernen eine zentrale Stellung einnimmt, bestimmt seine Leistung im allgemeinen die Gesamt-Performance des Systems. Hier nimmt L4 eine herausragende Stellung ein. Aufgrund des minimalistischen Designs und der Ausnutzung von Hardwareeigenschaften ist L4 sehr schnell und hat einen sehr geringen Overhead bei der IPC: nur circa 250 Takte bei einer kurzen Nachricht auf dem i486 gegenüber 5750 Takten beim Mach. Diese Leistung wird unter anderem dadurch erreicht, daß L4 sehr klein ist. Der Kern hat eine Größe von 12 KByte, wobei die des optimierten IPC-Pfades nur 1 KByte beträgt. Die Wahrscheinlichkeit, daß Kern und Applikation sich aus dem Cache verdrängen, wird dadurch verringert. Im Gegenzug ist es um so wahrscheinlicher, daß sich der am häufigsten benötigte Teil des L4, der IPC-Pfad, im First-Level-Cache befindet, was die Ausführung enorm beschleunigt. Einzelheiten dazu beschrieb Jochen Liedtke von der GMD auf einem Symposium zum Thema Betriebssysteme [[#literatur 2]].

Binärkompatibel zu Intel-Linux

Wie schon eingangs gesagt, bestand ein Hauptziel der Entwicklung in der Binärkompatibilität zur Intel-basierten Version. Der L4-basierte Linux-Kern sollte mit jeder gängigen Linux-Distribution zusammen laufen. Eine andere Prämisse war, möglichst wenige Änderungen am architekturunabhängigen Teil und den Gerätetreibern vorzunehmen. Das läßt zum einen die Möglichkeit offen, L4-spezifische Änderungen in den zentralen Linux-Source-Baum einfließen zu lassen, und ersparte zum anderen eine Menge Arbeit beim Anpassen der Architektur und der Entwicklung von Gerätetreibern.

Die gute Portabilität des Linux-Kerns gründet sich auf seinem modularen Aufbau: Die Implementierung ist klar in maschinenabhängige und -unabhängige Teile gegliedert. Um Linux auf eine neue Architektur zu portieren, muß man lediglich die Maschinenanpassung austauschen. Diese besteht im wesentlichen aus vier Bausteinen:

• Das Aktivitätenmanagement ist für das Prozessor-Scheduling und für den Aufbau der virtuellen Adreßräume der Prozesse zuständig und implementiert den Eintritt in den Kern und die Signalzustellung.
• Die Interrupt-Behandlungsroutinen müssen an Hardware-Interrupts angebunden werden.
• Ferner gibt es maschinenspezifischen Code für ansonsten architekturunabhängige Gerätetreiber wie den Floppy-Treiber.
• Zu guter Letzt muß die Binärschnittstelle zwischen dem Kern und den Anwendungsprogrammen (ABI, Application Binary Interface) definiert werden, wobei diese direkt von der Intel-Anpassung übernommen werden konnte - schließlich war Binärkompatibilität ein wichtiges Ziel.

Zwei L4-Tasks pro Linux-Prozeß

Um die Integrität des Linux-Kerns zu wahren und ihn vor fehlerhaften oder böswilligen Speicherzugriffen von Anwendungsprogrammen zu schützen, laufen Nutzer- und Kernaktivitäten in getrennten Tasks ab, die mittels IPC miteinander kommunizieren. Die Linux-Kern-Tasks fungieren als externe Pager für die Nutzer-Tasks und erbringen alle Linux-Dienste.

Linux verwaltet den Hauptspeicher architekturneutral mit Hilfe einer dreistufigen Seitentabellenhierarchie, die vom maschinenabhängigen Teil an die zugrundeliegende Speicherverwaltungsstruktur angepaßt werden muß. Im hier betrachteten Fall bildeten die Entwickler diese Hierarchie auf die Primitive des L4-Mikrokerns ab: erfolgt ein Zugriff auf eine noch nicht eingeblendete Seite, übersetzt L4 diesen Seitenfehler in eine Nachricht an den zugeordneten Pager-Thread. Dieser überprüft die Gültigkeit des Zugriffs und sendet anhand der von Linux verwalteten Seitentabelle die richtige Hauptspeicherseite als Flexpage-Nachricht zurück. Die Manipulation eines Seitentabelleneintrags wird in die entsprechende Flush-Operation des L4-Kerns umgewandelt.

Viele der Designentscheidungen leiten sich aus dem Copy-In-/-Out-Mechanismus ab, der für den Transfer von Parameter- und Ergebnisdaten zwischen dem Nutzer- und dem Kernadreßraum verantwortlich ist. Dazu blendet man den Nutzeradreßraum in die Kern-Task ein, so daß der Transfer durch eine einfache Speicherkopieroperation implementiert wird. Die Umschaltung zwischen den im Kern eingeblendeten Nutzeradreßräumen erfolgt durch Wechseln in die jedem Linux-Prozeß zugeordnete Kern-Task, da dies in L4 wesentlich schneller ist als eine Umschaltung des Adreßraums durch mehrmaliges Ein- und Ausblenden von Speicherseiten.

Jedem Linux-Prozeß ist eine Kern-Task zugeordnet, die den Nutzeradreßraum eingeblendet hat. So läßt sich Copy-In/-Out einfach realisieren.

Somit bilden Task-Paare das grundlegende Ausführungsmodell, wobei Code und Daten des Linux-Kerns in allen Kern-Tasks eingeblendet sind, aber immer nur eine aktiv ist. Um zum Adreßraum eines anderen Linux-Prozesses umzuschalten, weckt die gerade laufende Kern-Task die zu aktivierende mit einer IPC-Nachricht auf und legt sich schlafen, indem sie selbst auf eine Wecknachricht wartet. Zusätzlich gibt es einen Root Pager, der zum Aufbau des virtuellen Adreßraums der Kern-Tasks benötigt wird: Seitenfehler im Kern werden als Nachrichten an diesen Pager gesendet und von ihm entsprechend der Linux-Seitentabellen durch Seiten aus dem RAM befriedigt.

Einige Sonderaufgaben erfüllt die Kern-Task für Prozeß 0 (in Linux der idle-Prozeß): Zum Beispiel laufen in dieser Task die Threads, die in IPC-Nachrichten umgesetzte Hardware-Interrupts entgegennehmen. Linux unterscheidet zwischen zwei Prioritätsebenen für Interrupt-Behandlungsroutinen: Top Half und Bottom Half. Die hochpriorisierten Interrupt-Threads arbeiten die Top Halves sofort ab und stoßen dann via IPC die Abarbeitung der Bottom Halves in einem separaten Thread an, der eine geringere Priorität besitzt.

Kerneinsprung mit Trampolin

Ein Software-Interrupt (int 0x80) realisiert in i386-Linux die Systemaufruf-Schnittstelle. Die Ausführung dieses Befehls führt zu einem Wechsel in den Kernmodus, und Linux übernimmt die Kontrolle. Da jedoch auf L4 IPC die einzige Möglichkeit des Informationsaustauschs zwischen zwei Tasks darstellt, ist es erforderlich, diesen Software-Interrupt auf IPC abzubilden. Dazu bediente sich die L4-Gruppe des sogenannten Trampolinmechanismus: L4 behandelt nur einige Exceptions (Pagefault, Machine Check, General Protection), die verbleibenden werden zum virtuellen Prozessor des Thread gespiegelt, der sie ausgelöst hat. Dieser kann eine Tabelle mit Ausnahmebehandlungsroutinen installieren, die die gespiegelten Exceptions bearbeiten.

Ein Software-Interrupt (Assembleranweisung int n) führt zu einer General Protection Exception. Die Ausnahmebehandlung kann den mitgelieferten Fehlercode auswerten und die Nummer des Software-Interrupts ermitteln. Diesen Mechanismus machten sich die Entwickler zunutze.

Im Adreßraum jedes Linux-Prozesses wird eine Emulationsbibliothek eingeblendet, die neben dem Initialisierungscode auch den Code der Ausnahmebehandlungen für alle von Intel definierten Exceptions enthält. Die Handler sichern den Status des Thread entsprechend den Aufrufbedingungen des Linux-Kerns und senden eine Nachricht an den zugeordneten Linux-Server. Dieser analysiert die aufgetretene Exception und führt die entsprechende Aktion aus. Erkennt er eine General Protection Exception, deren Ursache ein int 0x80 ist, führt er den zugehörigen Systemruf aus. Sonst aktiviert er die Standard-Exception-Handler des Linux-Kerns.

Unix-Signale stellen aus Linux-Sicht einen Mechanismus für Callbacks vom Kern zu Nutzerprozessen dar. Um eine Signalbehandlungsroutine im Nutzerkontext ausführen zu können, muß der Stack der Nutzer-Task manipulierbar sein. Dies bedingt, daß sich die Task wiederum in einem definierten Zustand befindet. So kann das System nach Rückkehr aus der Behandlungsroutine die Signalmaske zurückstellen und den unterbrochenen Code fortsetzen. Soll ein Prozeß, der den Linux-Kern noch nicht betreten hat, ein Signal zugestellt bekommen, muß er zunächst von der Kern-Task zum Kerneleintritt gezwungen werden. Dies kann nicht ohne weiteres von außen erfolgen, da der Zustand eines Thread (Register und Stackpointer) nur von Threads derselben Task manipuliert werden kann. Dazu läuft in der Emulationsbibliothek ein spezieller Thread, der auf Nachrichten vom Linux-Kern wartet. Empfängt der Signal-Thread eine solche Nachricht, simuliert er für den Nutzer-Thread eine Exception, so daß dieser auf normalem Wege den Linux-Kern betritt (Senden einer IPC-Nachricht an die Linux-Task).

Optimierung steht noch aus

Nachdem die Portierung soweit erfolgt war, daß auf dem System nahezu alle Anwendungen liefen, führte die L4-Gruppe erste Benchmarks durch, um mögliche Engpässe zu finden. Diese ergaben, daß der Debugcode, der zum Erkennen von Fehlersituationen in L4 oder im Linux-Kern benötigt wird, sich stark auf die Performance auswirkt. Da L4 recht neu ist und die Dresdner Entwickler das erste Mal ein System darauf portiert haben, verfolgten sie einen extrem defensiven Programmierstil. Aus diesen Gründen macht es zur Zeit noch wenig Sinn hier konkrete Daten zu präsentieren.

Zur Messung verwendeten die Entwickler das Lmbench-Paket, mit dem sich Durchsätze und Latenzen auf Systemebene messen lassen. Die Benchmarks lieferten einige Hinweise auf mögliche Optimierungen. Diesen Hinweisen wird die L4-Gruppe in den nächsten Wochen nachgehen und das System bis an die Grenzen des Möglichen ausreizen. Diese Grenze setzen die IPC-Kosten und die der Binärkompatibilität. Aber diese sind auf L4 gering, so daß die Dresdner Entwickler mit einem schnellen, auf einem Mikrokern laufenden Linux rechnen, ohne zu Tricks wie der Verlagerung des Linux-Servers oder der Gerätetreiber in den Mikrokernadreßraum greifen zu müssen.

MICHAEL HOHMUTH & JEAN WOLTER

sind wissenschaftliche Mitarbeiter am Lehrstuhl Betriebssysteme der TU Dresden. Sie beschäftigen sich mit mikrokernbasierten Echtzeitsystemen.

Literatur

[1] Oliver Schmelzle, Markus Breilmann; RISC-Linux; Rohkost; Mach-basiertes Linux für Apples Power Macintosh; iX 7/96, S. 68 f.

[2] Jochen Liedtke; On µ-kernel construction; In: 15. ACM Symposium on Operating System Principles (SOSP), S. 237-250; http://borneo.gmd.de/RS/L4/sops95.ps

[3]Jochen Liedtke; L4 Reference Manual (Intel 486, Pentium, Pentium Pro); http://www.inf.tu-dresden.de/~mh1/l3/l4refx86.ps.gz

iX-TRACT

Entgegen der verbreiteten Meinung können moderne Mikrokernel-Architekturen wie der L4 von der GMD durchaus effizient sein. Linux läuft bei der Dresdner L4-Portierung vollständig im User Level des Prozessors ab. Binärkompatibilität zum `Original'-Linux für i386-Prozessoren sorgt dafür, daß der L4-basierte Kernel mit allen gängigen Distributionen zusammenarbeitet. Dem frühen Entwicklungsstadium entsprechend, bietet vor allem die Performance einiges Optimierungspotential.