Uwe Dannowski

Dissertation, Fakultät für Informatik, Universität Karlsruhe, 12. Dezember 2007

Abstract:

Mikrokerne müssen maximal effizient sein. Als Basis feingliedrig komponentisierter Betriebssysteme stellen sie den Kommunikationsmechanismus zwischen den Komponenten zur Verfügung und spielen damit eine besonders leistungskritische Rolle im Gesamtsystem. Minimale Ausführungszeit und minimale Cachebenutzung des Mikrokerns sind dabei Schlüsselfaktoren. Gleichzeitig sollen Mikrokerne als zentrale Systemkomponente jedoch auch portabel und leicht wartbar sein. Traditionell werden diese Ziele als unvereinbar angesehen, da Mikrokerne für die jeweilige Systemkonfiguration optimiert werden müssen, um ausreichend effizient zu sein.

Aus der hohen Zahl möglicher Systemkonfigurationen eines portablen Mikrokerns ergibt sich ein Komplexitätsproblem. Durch Modularisierung und die damit erreichbare Konfigurierbarkeit kann der Umfang der notwendigen Optimierungen jedoch reduziert werden. Allgemein verwendbare und konfigurationsspezifische Teile des Kerns werden voneinander getrennt, in verschiedenen Modulen platziert und bei der Erzeugung eines Kerns entsprechend der Konfiguration zusammengefügt. Dieses Vorgehen wird bereits erfolgreich im portablen Mikrokern L4Ka::Pistachio angewandt. Durch Unzulänglichkeiten heutiger Programmiertechniken für Mikrokerne - hauptsächlich durch unzureichend feingranulare Konfigurierbarkeit - lassen sich jedoch Probleme wie übermässiger Präprozessoreinsatz und Quelltextduplikation oder, als Alternative, suboptimale Leistung nicht gänzlich vermeiden.

Der Einsatz objektorientierter Programmierung und speziell der Vererbung zum Zwecke der Konfiguration und Komposition von Kerndatenstrukturen ist ein Erfolg versprechender Ansatz, diese Strukturprobleme zu lösen. Konfigurationsspezifische Aspekte der Kernfunktionalität und die dafür benötigten Daten werden in relativ kleinen Klassen gekapselt, die je nach Zielsystem durch Vererbung zu vollständigen Klassen zusammengefügt werden. Jedoch verursacht die flexible Implementierung von Objektorientierung oft einen zusätzlichen Laufzeitaufwand, der in einem Mikrokern nicht tolerierbar ist. Zum einen werden zur Unterstützung dynamischer Polymorphie manche Funktionen durch indirekte und somit nicht vorhersagbare Sprünge realisiert und behindern dadurch eine zügige Ausführung der Instruktionsfolge durch den Prozessor. Zum anderen wird durch die Vererbungshierarchie die interne Struktur von Objekten in einer Weise festgelegt, die eine optimale Cache- Ausnutzung auf dem kritischen Pfad des Mikrokerns verhindert.

Diese Arbeit stellt ein automatisiertes Optimierungsverfahren vor, das es erlaubt, Objektorientierung zur Komposition von Datenstrukturen im Mikrokern einzusetzen, ohne die traditionell damit verbundenen Laufzeitkosten tragen zu müssen. Wissen, das dem Kernprogrammierer bekannt ist, jedoch nicht in geeigneterWeise an den Compiler weitergegeben werden kann, wird dazu verwandt, den Quelltext automatisch so umzuformulieren, dass der Compiler optimalen Code und optimale Datenstrukturen erzeugen kann. Die Transformationsschritte im Einzelnen sind:

1.) Das Umwandeln der Vererbungshierarchien ausgesuchter Klassen in einzelne Klassen ohne Vererbung unter Beibehaltung der Schnittstelle der Klassen. Dadurch wird verhindert, dass der Compiler unnötigerweise Code zur Laufzeitunterstützung für Polymorphie generiert. Da keine Vererbung stattfindet, kann die interne Struktur von Objekten der resultierenden Klasse nun gezielt beeinflusst werden.

2.) Das Umordnen der Datenelemente innerhalb der Definition ausgesuchter Klassen, so dass die resultierende Anordnung der Daten innerhalb der Objekte dieser Klassen zu optimaler Cache-Benutzung auf dem kritischen Pfad führt.

 Diese Schritte werden - für den Kernprogrammierer transparent - zur Übersetzungszeit vor Aufruf des Compilers durchgeführt. Damit ergibt sich trotz separater Übersetzung der einzelnen Quelltextdateien effektiv eine Optimierung des Gesamtprogramms Mikrokern. Durch die Realisierung der Transformationen auf Quelltextbasis wird kein speziell angepasster Kern-Compiler benötigt, und es wird weitestgehende Unabhängigkeit vom eingesetzten Compiler erreicht.

Bislang war automatisches Umordnen der Felder einer Klasse nur in typsicheren Sprachen gefahrlos möglich. Für Objekte, deren Struktur nicht durch kern-externe Spezifikationen vorgegeben ist, lässt sich die Manipulation der Objektstruktur jedoch auch in typunsicheren Sprachen voll automatisieren, ohne dabei die Korrektheit des Kerns zu gefährden.

Die Entscheidung über die Auswahl der leistungskritischen Klassen im Mikrokern ist unabhängig vom Zielsystem und kann daher statisch erfolgen. Der kritische Pfad und die Zugriffsfolge sind jedoch einsatzabhängig und müssen deshalb während eines Profiling-Laufs bestimmt werden. Dabei kann durch gezielte Ausnutzung von mikrokernspezifischen Eigenschaften eine sehr kompakte und leicht auswertbare Darstellung der Zugriffsinformationen erreicht werden. Beispiele für solche Eigenschaften sind der extrem kurze kritische Pfad sowie die geringe Anzahl der referenzierten Kernobjekte und eine sehr hohe Ähnlichkeit der Zugriffsmuster auf dem kritischen Pfad.

Die Entscheidung über die Auswahl der leistungskritischen Klassen im Mikrokern ist unabhängig vom Zielsystem und kann daher statisch erfolgen. Der kritische Pfad und die Zugriffsfolge sind jedoch einsatzabhängig und müssen deshalb während eines Profiling-Laufs bestimmt werden. Dabei kann durch gezielte Ausnutzung von mikrokernspezifischen Eigenschaften eine sehr kompakte und leicht auswertbare Darstellung der Zugriffsinformationen erreicht werden. Beispiele für solche Eigenschaften sind der extrem kurze kritische Pfad sowie die geringe Anzahl der referenzierten Kernobjekte und eine sehr hohe Ähnlichkeit der Zugriffsmuster auf dem kritischen Pfad.

Über die Vermeidung des Laufzeitaufwands der Vererbung hinaus erlaubt das Verfahren, leistungskritische Klassen automatisch für den spezifischen Einsatzfall des Mikrokerns zu optimieren, so dass die notwendigen Anpassungen nicht mehr manuell vom Programmierer vorgenommen werden müssen. Die automatische Transformation des Quelltextes beschränkt sich dabei auf die Definitionen der laufzeitkritischen Klassen. Teile des Kerns, die diese Klassen lediglich benutzen, bleiben somit unangetastet.

Das vorgestellte Verfahren wird exemplarisch auf den L4Ka::Pistachio Mikrokern angewandt und evaluiert. Die Leistung eines Kerns mit Vererbungshierarchie und optimierten Klassen wird der des für eine Architektur handoptimierten Originalkerns ohne Vererbung gegenübergestellt. Dabei zeigt sich, dass das Verfahren die Laufzeitkosten der Vererbung vollständig beseitigt und darüber hinaus bisher ungenutztes Optimierungspotential ausschöpfen kann.

BibTex:

@phdthesis{dannowski07towards,
  author = {Uwe Dannowski},
  title =  {Towards Fast and Portable Microkernels},
  school = {Universit\"at Karlsruhe (TH)},
  address = {Germany},
  year = {2007},
  month = dec
}