% Hauptseminar Betriebssysteme. Exokernel Architektur
% Von Chris Hodges
% 18. Mai 2000
%
% Handouts.
%

\documentclass[a4paper,twoside]{article}
\usepackage{epsfig}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{headings}
\sloppy
\author{Chris Hodges $<$hodges@in.tum.de$>$}
\title{{\small Technische Universität München\\
Forschungs- und Lehreinheit XIII}\\
\vspace{1cm}
Hauptseminar\\Neue Betriebssysteme\\
Ansätze für Betriebssysteme der Zukunft\\
\vspace{2cm}
\Huge
\bf Exokernel}
\date{18-Mai-2000}
\pagestyle{empty}
\begin{document}
\pagestyle{empty}
\maketitle
\newpage
~\pagestyle{plain}
\newpage
\tableofcontents
\newpage~\newpage
\pagestyle{headings}
\section{Einleitung}

Blickt man auf die letzten 20 Jahre der Kernel- und
Betriebssystementwicklung zurück, so wurden die Probleme schwacher
Leistung, ungenügender Zuverlässigkeit, schlechter Anpassungsfähigkeit
und mangelnder Flexibilität nicht befriedigend gelöst. Der Grund dafür
scheint die unzureichende und ineffiziente Abstraktion zu sein, die von den
traditionellen Betriebssystemen vorgenommen werden. Abstraktionen wie z.B.
Festplattenblöcke als Dateien und CPU-Zeit als Prozesse sind als solche
wichtig und sinnvoll. Sie bieten ein portables Interface für
Applikationsprogrammierer, die durch dieses API nichts über die der
Maschine unterliegenden Hardware wissen müssen. Durch die Abstraktion
können Funktionialitäten der verschiedenen Ressourcen auf hohem Niveau
erreicht werden.

\subsection{Motivation}

Der Nachteil der Abstraktion ist jedoch der Informationsverlust und die daraus
entstehende Schwierigkeit, spezielle Applikationen an bestimmte
Bedürfnisse zu optimieren. So unterliegt Ressourcenbereitstellung und
-schutz allein der Kontrolle des Betriebssystemkerns, wobei letzteres
zu globalen Performanceeinbußen führen kann (durch Kontextwechsel
zwischen Kernel- und User-Modus). Weiterhin ist der Programmierer an die
beschränkte Funktionalität der Schnittstelle gebunden, die spezielle
Anpassungen und Innovationen verhindert.

\subsection{Lösungsansatz}

Die ab 1995 am Massachusetts Institute of Technology entwickelte
\textit{Exokernel Architektur} stellt eine radikale und innovative Lösung
dieser Probleme der traditionellen Betriebssysteme bereit. Wie oben
dargestellt, ist die Abstraktion der ursächliche Grund für die mangelnde
Flexibilität der herkömmlichen Kerne. Ziel des Exokernels ist es daher,
die Abstraktionen so weit wie möglich aus dem Kern zu entfernen und
stattdessen nur die Bereitstellung von Systemressourcen über ein einfaches
Interface zum Kern zu ermöglichen. Der Exokernel \textit{verwaltet
jedoch die Ressourcen selbst nicht} -- er besitzt keine Kenntnisse
über deren Inhalt und Funktionsweise. Im Zentrum steht die
\textit{Bereitstellung} und der \textit{Schutz des Zugriffs} auf diese. Der
Schutz soll jedoch nicht zugriffsbasiert sein (d.h. eine Überprüfung der
Berechtigung bei jedem Zugriff), sondern bei der Anforderung der Ressource
festgelegt werden. Jegliche Verwaltungsfunktionalität, die über die oben
genannten Punkte hinaus geht, soll von unprivilegierten Applikationen
gehandhabt werden.

Damit die Vorteile der Abstraktion jedoch nicht verloren gehen, gibt es
eine Metaebene zwischen den Applikationen und dem Exokernel, sog.
Betriebssysteme in Bibliotheken (engl. library operating system, kurz
libOS), die allerdings den User-Applikationen von den Privilegien her
gleichgestellt sind. So sind die Applikationen nicht beschränkt auf eine
bestimmte Schnittstelle, sondern können bei speziellen Bedürfnissen
eigene, für die Anwendung optimierte, libOS'e entwickeln und verwenden.

\section{Exokernel-Konzepte}

Es folgt nun eine grobe Übersicht darüber, was einen Exokernel ausmacht,
welche Prämissen dieser verfolgt, welche Ziele man dabei im Auge hat und
wie man diese in der Praxis realisieren kann.

\begin{table}[tbp]
\begin{center}
  \mbox{\epsfxsize=0.75\textwidth \epsffile{overview.eps}}
  \caption{\small \label{overview} Beispielhaftes Exokernel-System.
Standard UNIX-Applikationen laufen über das ExOS libOS-Betriebssystem.
Gleichzeitig ist jedoch auch eine hochoptimierte Anwendung installiert
(Cheetah), die ein eigenes Dateisystem (C-FFS) und eine schnelle TCP/IP
Implementation besitzt (für andere Teile werden aber auch die ExOS
Schnittstellen verwendet).}
  \end{center}
\end{table}

\subsection{Design-Ziele}

Damit die Applikationen so gut wie möglich vom Exokernel-Design
profitieren können, wurden vom MIT einige Design-Prinzipien aufgestellt:

\subsubsection{Trennung von Schutz und Verwaltung}

Der Kern soll sich auf die Mechanismen zum Schutz der jeweiligen Ressourcen
beschränken. So kann z.B. Speicher seitenweise, die CPU in Zeitscheiben
und Festplattenspeicher in Blockeinheiten geschützt werden. Die Strategien
zur Verwaltung können dann direkt von den Applikationen übernommen
werden. Der Schutz der Ressourcen erfolgt über elementare Mechanismen der
Allokation und Revokation, sowie für das Teilen (\textit{sharing}) der
Ressourcen unter den Applikationen\footnote{an dieser Stelle bietet sich
an, Optimierungen für das häufigste Auftreten von Sharing durchzuführen,
nämlich, daß sich beide Applikationen gegenseitig vertrauen} und der
Überwachung der Zugehörigkeit der Ressourcen zu den Applikationen, die sie
angefordert haben.

In monolithischen Systemen bedeutet der Schutz der Ressourcen meist, daß
der Kern von deren Semantik wissen muß und dadurch bereits Teile der
Kernschnittstellen feststehen. Dazu kommt, daß die Autorisation in vielen
Fällen bei jedem Zugriff geprüft wird und dadurch das System ausbremst. Der
Exokernel muß Ressourcen schützen können, ohne deren Semantik zu kennen.
Die Überprüfung der Autorisation erfolgt einmalig bereits bei der Zuweisung
der Ressource und muß nicht bei jedem Zugriff verifiziert werden. Dies kann
z.B. bei Dateisystemen etwas schwierig werden, aber wie wir später sehen
werden, wurde dies auch zufriedenstellend gelöst.

\subsubsection{Offenlegen der Hardware}

Um den Applikationen ein größtmögliches Maß an Informationen liefern zu
können, soll die Schnittstelle des Kerns zu den
Applikationen\footnote{diese wird mit API (\textit{Application Programmers
Interface}) bezeichnet} einen möglichst niedrigen Abstraktionsgrad besitzen
und die Ressourcen der Hardwareebene entsprechen. Der Programmierer einer
Applikation soll alle Informationen zur unterliegenden Hardware bekommen
können (z.B. DMA-Kanäle, physikalischer Speicher, MMU-Mappings etc.) und
auch die Ressourcen auf diesem Niveau reservieren können.

Im Gegensatz zu einigen anderen Mikrokernels, wird hierbei jedoch keine
virtuelle Maschine simuliert. Es wird den Applikationen die physikalische
Hardware veräußert, um einem Informationsverlust durch Virtualisierung der
Hardware entgegenzuwirken, die sich wiederum negativ auf die Performance
auswirken kann.

Z.B. nützt es nichts, wenn eine Applikation eigene Paging-Strategien für
den virtuellen Speicher realisiert, wenn der Kern selbst den Speicher
virtuell verwaltet und dadurch die Optimierung durch die spezielle
Paging-Strategie zunichte macht.

\subsubsection{Explizite Allokation und sichtbare Revokation}

Bei traditionellen Kernen werden bei der Allokation implizite
Entscheidungen über zu reservierende Ressource getroffen. Die
Revokation\footnote{Revokation bedeutet hier die (erzwungene) Rückgabe
eines Betriebsmittels, die z.B. von einer anderen Applikation benötigt
wird} erfolgt normalerweise für die Applikation völlig transparent. D.h.
die Applikation erfährt nichts davon, daß z.B. aufgrund von Speichermangel
Teile des Datenbereichs der Applikation auf die Festplatte ausgelagert
worden sind und kann diese Informationen nicht nutzen, um selbst zu
bestimmen, welcher Bereich am wenigsten verwendet wird und deshalb ein
Auslagern vertretbar wäre.

Beim Exokernel hingegen werden die Ressourcen explizit angefordert, wobei
dem Kern z.B. mitgeteilt werden kann, wann und welcher Diskblock reserviert
werden soll, um ein optimales Layout auf der Festplatte der Daten zu
ermöglichen und die Kopfbewegungen zu minimieren.

Bei der Revokation bekommt die Applikation vorher eine Nachricht darüber,
daß eine Ressource zurückzugeben ist und kann dann selbst darüber
entscheiden, welche Instanz freigegeben werden soll. Dies kann auch dafür
benutzt werden, um in einen speicherkonservativeren Modus einer Applikation
zu wechseln.

\subsubsection{Schutz von Einheiten minimaler Größe}

Um den Overhead für die Verwaltung und Verteilung von Ressource-Einheiten
so gering wie möglich zu halten, werden diese Einheiten kleinstmöglich
gewählt (z.B. auf Diskblock-Niveau anstatt ganzer
Partitionen).\footnote{natürlich bedeutet dies womöglich einen höheren
Speicherbedarf} Gröbere Einheiten machen auch den Schutz dieser
schwierig, da die Ressourcen nicht in kleineren Einheiten zwischen den
Applikationen geshared werden können als der Exokernel sie schützt.

Normalerweise verfolgen sowohl der Kern als auch die Applikation, welche
Ressourcen ihnen gehören. Um den doppelten Aufwand für die Verwaltung zu
reduzieren soll der Exokernel die Applikationsstrukturen zu diesem Zweck
mitbenutzen können (ohne deren Semantik verstehen zu müssen).

\subsubsection{Verwendung physikalischer Namen}

Das Exokernel-API soll physikalische Namen verwenden, wo dies möglich ist.
Physikalische Namen enthalten wertvolle Informationen, die vom
Programmierer für Optimierungen verwendet werden können (z.B. beinhaltet die
Diskblocknummer die Position auf der Platte, die wichtigste Variable für
die Performance eines Dateisystems). Die Übersetzung virtueller Namen
zu physikalischen hingegen benötigt mehr Speicher und führt womöglich zu
weiterer Diskaktivität.

Abstraktionen dieser Art können auf Applikationsniveau (oder in den
\mbox{libOS'en}) stattfinden, ohne die Flexibilität und die Möglichkeiten der
Innovation zu reduzieren.

Beispielsweise verwendet \texttt{xcp}, ein Kopierprogramm unter ExOS, die
Blockinformationen, um sich zuerst die Diskblocknummern aller zu
kopierenden Dateien zu besorgen und diese Liste dann zu sortieren.
\texttt{xcp} liest dann zusammenhängende Bereiche in den Speicher und
schreibt diese wieder (ohne sie mit der CPU zu berühren) direkt in den
Zielbereich auf der Festplatte. \texttt{xcp} erreicht damit
durchschnittlich die doppelte Geschwindigkeit im Vergleich zu \texttt{cp}.

\subsubsection{Kern-Informationen veröffentlichen}

Der Exokernel soll Informationen sammeln und bereitstellen, an die die
Applikationen meist nur schwierig oder überhaupt nicht heran kommen können.
Dies können z.B. Informationen darüber sein, welche Speicherseite welchen
Festplattenblock ''cachet'', oder eine LRU-Statistik\footnote{LRU = Last
recent used} über die Nutzung von Speicherseiten, die nur der Kern
erstellen könnte. Diese Statistik könnte z.B. der Applikation die
Entscheidung bei der Revokation erleichtern.

\subsection{Realisierung}

Wie man nun die vorgestellten Design-Prinzipien praktisch umsetzen kann,
soll folgender Abschnitt erläutern.

\subsubsection{Betriebssysteme als Bibliotheken}

Wie bereits in der Einleitung beschrieben, sollen die Vorteile der
Abstraktion bei traditionellen Betriebssystemen nicht verloren gehen. Der
Exokernel bietet nur rudimentäre Funktionen zum Schutz der Ressourcen, eine
gut handhabbare Schnittstelle für den Applikationsprogrammierer bietet er
jedoch nicht. Als Ebene zwischen dem Kern und den Applikationen treten nun
die eigentlichen Betriebssysteme, die als (dynamische) Bibliotheken
realisiert sind und die Funktionalität herkömmlicher Betriebssysteme
bereitstellen (z.B. virtueller Speicher, Dateisysteme, Prozesse etc.).
Diese sog. libOS'e koexistieren harmonisch untereinander und laufen im
Benutzermodus, so daß sie von jedem beliebig ausgetauscht oder erweitert
werden können. Für die Portierung von Unix-Programmen existiert z.B. ein
libOS namens ExOS mit POSIX-Schnittstelle, auf dem fast alle
Unix-Applikationen unverändert laufen.

Für spezielle Bedürfnisse einer Applikation oder Optimierungen kann also
ein neues libOS entworfen oder nur Teile davon neu implementiert werden;
natürlich kann auch direkt auf die Exokernel-API zugegriffen werden. Die
Entwicklung gestaltet sich dabei sehr einfach, da man parallel zum
laufenden System sicher arbeiten kann, ohne durch die Modifikationen an
einem libOS die Programme eines anderen libOS zu gefährden (und daher das
System ständig neu rebooten zu müssen). Dadurch erschließt sich jeder
Anwendung das volle Potential an Innovationsmöglichkeiten, das sonst nur
privilegierter Software zusteht.

\subsubsection{Secure bindings}

Die bei herkömmlichen Betriebssystemen zu den größten Performance-Einbußen
führende Aufgabe, durch die Überwachung der Zugriffsrechte auf Ressourcen,
Stabilität und Sicherheit auf einem System zu gewährleisten, wurde bei
Exokernel effizient durch den sog. \textit{secure bindings} Mechanismus
gelöst. Anstatt die Autorisation bei jeder Nutzung überprüfen und dabei
die Semantik der Ressource verstehen zu müssen (was der Flexibilität und
Erweiterbarkeit offensichtlich abträglich wäre), wird stattdessen durch
eine Secure binding eine einmalige Verknüpfung einer Ressource zu einer
Applikation erstellt. Nur bei der Erstellung muß der Kern über die
Bedeutung im Klaren sein und kann bei der späteren Nutzung allein über
diese Secure binding die Zugriffsrechte zu einer Ressource gewähren.

In einigen Fällen werden Secure bindings bereits per Hardware realisiert,
wie z.B. bei der MMU-Mapping Table\footnote{auch TLB (Translation Lookaside
Buffer) genannt}, die den Zugriff auf Speicherseiten schützt.

Für den speziellen Fall der Dateisysteme hat man sich sog.
\textit{untrusted deterministic functions} (UDFs) einfallen lassen, die dem
Dateisystem die Freiheiten über das Blocklayout lassen, mit denen sich aber
dem Kernel beweisen läßt, daß die Funktion, die ermittelt, wem welcher
Block gehört, immer das richtige Ergebnis liefert. Auf die UDFs wird im
Abschnitt über in den Kern ladbaren Code noch eingegangen.

\subsubsection{Sichtbare Revokation von Ressourcen}

Wie bereits oben erwähnt benutzen traditionelle Betriebssysteme
unsichtbare Revokation. Dies bedeutet, daß sich der Kern (oder ein
privilegierter Server) bei Ressourcenknappheit selbständig und unsichtbar
für die Applikation darum kümmert, daß gewisse Ressourcen freigegeben oder
im Falle physikalischen Speichers auf Platte ausgelagert und bei Bedarf
wieder zurückgelesen werden. Dies bedeutet jedoch, daß die Applikation
weder Kontrolle über die zu freigebenden Ressourcen, noch Informationen
darüber bekommt, daß Ressourcen benötigt werden.

Der Exokernel-Ansatz verwendet sichtbare Revokation, um der Applikation die
Strategie selbst zu überlassen, welche Instanz einer Ressource wie
freigegeben werden soll. Dies bedeutet, daß der Kern der Applikation
lediglich meldet, daß er eine Ressource benötigt, die ihm die Applikation
innerhalb eines festgelegten Zeitrahmens zugänglich machen muß.

Kommt die Applikation der Aufforderung (ggf. nach einer weiteren Mahnung)
nicht nach, so entreißt der Kernel der Applikation gewaltsam eine Ressource
durch Aufkündigung der Secure binding und meldet dies über ein sog.
Abbruch-Protokoll, damit die Applikation Gelegenheit hat, ihre internen
Verwaltungstabellen auf den neuesten Stand zu bringen. Muß der Zustand
einer Ressource in diesem Fall gesichert werden, so kann der Kern diesen
auf Platte auslagern. Alternativ dazu kann die Applikation oder ein libOS
auch einen Vektor zu einer Struktur angeben (den sog. ''repossession
vector''), die festlegt, wo in diesem Fall die Daten ausgelagert werden
sollen.

Eine völlig willkürliche Revokation von Ressourcen könnte jedoch die
Funktionsfähigkeit gewisser Applikationen und im besonderen von
Betriebssystemen in einer Bibliothek beeinträchtigen oder unmöglich machen
(z.B. wenn Speicherseiten mit Ausnahmebehandlungscode oder -strukturen
auf Platte ausgelagert werden würden), so daß der Exokernel eine
geringe Anzahl physikalischer Ressourcen zusichert, die nicht vom Kern
zurückgefordert werden.

\subsubsection{In den Kern ladbarer Code}

Bei manchen Anwendungen werden bei einer hohen Frequenz an kleinen
Datensätzen geringe Latenzzeiten benötigt. Als Beispiel seien hier
Ether\-net-Paket\-fil\-ter genannt oder serielle
Hoch\-ge\-schwin\-dig\-keits\-über\-tra\-gungen mit kleinem FiFo-Puffer. Im
Normalfall würde das eine hohe Anzahl von
Kontextwechseln\footnote{Kontextwechsel sind erforderlich, um in den Kern
ein- und auszutreten. Je nach Rechnerarchitektur kann dies verhältnismäßig
lange dauern (besonders bei langen Pipelines)} zwischen dem Kern- und dem
Benutzermodus erfordern und daher zu suboptimaler Performance führen.
Der Exokernel sieht daher die Verwendung von in den Kern ladbaren
Programmcode vor, um dieses Kontextwechselproblem zu eliminieren.

Diese Techniken wurden in der Exokernelarchitektur verwendet für:
\begin{itemize}
\item \textit{Application-specific safe handlers} (ASHs)\\
Dabei werden Ereignisse Teile unprivilegierter Applikationen zugeordnet und
direkt nach Auftreten im Kernmodus ausgeführt, ohne durch den Scheduler
Prozessorzeit zugewiesen zu bekommen. Dies kann benutzt werden, um auf
bestimmte Hardwaresignale zu warten (z.B. Interrupts).

Um zu verhindern, daß dieser potentiell fehlerhafte oder böswillige \mbox{Code}
den Kern zu Absturz bringt, wird dieser durch eine Kombination von
\textit{sandboxing} und Codeinspektion geschützt und verifiziert. Beim
Sandboxing wird die Umgebung vor illegalen Speicherzugriffen geschützt, bei
der Codeinspektion wird unter anderem der Codeabschnitt auf Sprünge auf
Bereiche außerhalb des ASHs geprüft. Dies kann natürlich kein 100\%-tiger
Schutz sein, da diese Mechanismen durch z.B. Änderung der MMU-Tabellen (der
Code läuft ja im priviliertem Kernel-Modus!) und selbst-mo\-di\-fi\-zie\-ren\-dem
Code umgangen werden können.
\item \textit{Dynamic packet filters} (DPFs)\\
DPFs filtern Netzwerkpakete und übergeben diese an die richtige
Em\-pfän\-ger\-appli\-kation. Da DPFs in einer eigenen effizienten, aber
beschränkten Sprache geschrieben und zur Laufzeit in den Kernel kompiliert
werden, kann böswilliger Gebrauch (z.B. zum Umlenken von Ethernet-Paketen)
vermieden und Determinismus bestätigt werden.

\item \textit{Untrusted deterministic functions} (UDFs)\\
UDFs sind interpretierte, deterministische Funktionen in einer
pseudo-assembler Notation, mit denen der Exokernel die Zugehörigkeit eines
Disk-Blocks zu einem Dateisystem überprüfen kann, ohne die Semantik oder
das Datenlayout zu kennen. Dadurch bleibt gemäß den Design-Zielen des
Exokernels die Flexibilität erhalten.

UDFs sind Schablonen für jeden Blocktyp, um an die Owner-In\-for\-ma\-tio\-nen zu
gelangen. Um die Funktionsweise der \texttt{owns}-Funktion zu verifizieren
kann einfach ein Block \textit{b} alloziert werden: Die Menge der
allozierten Blöcke vor der Allokation plus Block \textit{b} muß der
resultierenden Menge entsprechen. Da UDFs nicht Turing-vollständig sind, da
sie keine randomisierten Daten miteinbeziehen können, sind sie
deterministisch und damit ist die Funktionsweise garantiert.
\end{itemize}

\begin{table}[tbp]
\begin{center}
  \mbox{\epsfxsize=0.75\textwidth \epsffile{kernelcode.eps}}\\~\\
  \caption{\small \label{kernelcode} Beispiel für ASHs, DPFs und UDFs. Die
schnelle TCP-Implementation läd einen Paket-Filter in den Kern, der
X-Server installiert einen ASH für die Auswertung der Tastatur und
Mausereignisse und Screenblanker verwendet einen weiteren ASH um diese
Ereignisse abzufangen, falls er aktiv ist. UDFs werden von den
Dateisystemen installiert, um den Zugriff auf die Plattenblöcke zu
schützen.}
  \end{center}
\end{table}

\section{Implementierungen in der Praxis}

Die große Frage ist natürlich nun: Kann man ein Exokernelsystem nach diesen
Richtlinien realisieren und wie sieht es mit der propagierten Leistung
tatsächlich aus? Am Massachusetts Institute of Technology wurden bisher
drei Exokernelsysteme implementiert: \textit{Aegis}, \textit{Glaze} und
\textit{Xok}. Aegis war der erste Ansatz und die einfachste Umsetzung für
DECstations mit MIPS Prozessoren (DEC2100, DEC3100 und DEC5000). Aegis
sollte zeigen, daß bereits bei Mikrobenchmarks das Exokernel-System den
Literaturwerten um eine Ordnung überlegen ist. Glaze war als Version für
eine experimentelle SPARC-basierte Multiprozessormaschine konzipiert. Xok
ist die neueste, am weitesten vorangeschrittene und ausgereifteste
Implementation eines Exokernels für x86 Prozessoren. Sowohl Aegis als auch
Xok verwenden standardmäßig das POSIX-kompatible Bibliotheksbetriebssystem
\textit{ExOS}, mit dem die meisten Unixprogramme (z.B. perl, gcc, telnet,
csh) auf den beiden Systemen unverändert lauffähig sind. ExOS ist damit
quasi ein Unix in einer Bibliothek. Glaze verwendete \textit{PhOS}, ein auf
Parallelität ausgelegtes Bibliotheksbetriebssystem. Auf Glaze soll hier
nicht weiter eingegangen werden.

\subsection{Aegis / ExOS}

Aegis soll zeigen, daß Exokernel und sicheres Multiplexen von
Hardwareressourcen sehr effizient sein können. Dazu vergleichen wir die
Leistung von Aegis / ExOS mit Ultrix4.2, einem hochoptimierten,
monolithischen UNIX Betriebssystem. Wir betrachten dazu einige
aussagekräftige Benchmarks über den Kernel.

\subsubsection{Ausnahmebehandlung}

Die schnelle Behandlung von Ausnahmebedingungen (\textit{exceptions}) ist
wichtig für eine geringe Latenzzeit und allgemein ein Indikator für die
Effizienz des Kerns. Tabelle \ref{exceptions} zeigt einen groben Überblick
darüber, daß Aegis bei diesen Low-Level Operationen rund zwei Ordnungen
schneller ist als Ultrix. Dies rührt vor allem daher, daß Aegis nur
Datenstrukturen verwendet, die von der MMU nicht übersetzt werden müssen und
keine Unterscheidung zwischen Exceptions aus dem Kernel und der Applikation
treffen muß.

\begin{table}[tbp]
  \begin{center}
  \begin{tabular}{|l|l|l|r|r|}
  \hline
  \textbf{Maschine} & MHz & \textbf{OS} & \textbf{Überlauf} & \textbf{Speicherschutzfehler} \\
  \hline
  DEC2100 & 12.5 MHz & Ultrix & 208,0 & 238,0 \\
  DEC2100 & 12.5 MHz & Aegis & 2,8 & 3,0 \\
  \hline
  DEC3100 & 16.67 MHz & Ultrix & 151,0 & 177,0 \\
  DEC3100 & 16.67 MHz &Aegis & 2,1 & 2,3 \\
  \hline
  DEC5000/125 & 25.0 MHz & Ultrix & 130,0 & 154,0 \\
  DEC5000/125 & 25.0 MHz & Aegis & 1,5 & 1,5 \\
  \hline
  \end{tabular}
  \caption{\small \label{exceptions} Zeit um eine Ausnahmebedingung zu behandeln. Zeiten in Mikrosekunden.}
  \end{center}
\end{table}

\subsubsection{Interprozeßkommunikation}

Für die Realisierung effizienter Interprozeßkommunikation (IPC) und deren
Abstraktion bietet Aegis sog. geschützte Kontrolltransfers
(\textit{protected control transfer}). Der Mechanismus übergibt im Grunde
genommen nur die CPU (und den Prozeßkontext) dem Kommunikationspartner und
führt dessen Programmcode an einer vereinbarten Stelle aus. Dabei bleiben
die Prozessorregister unverändert und können als Puffer für Nachrichten
verwendet werden. Aegis garantiert dabei, daß dieser Prozeß atomar ist,
d.h. er nicht durch andere Kontextwechsel unterbrochen wird.

Aegis unterscheidet dabei zwischen asynchronem (nur die verbleibende Zeit
der aktuellen Zeitscheibe wird dem Partner übergeben) und synchronem
Kontrolltransfer (alle zukünftigen Zeitscheiben werden dem Partner
übergeben, bis dieser die Kontrolle wieder durch einen synchronen Transfer
an den Initiator zurückgibt).

\begin{table}[tbp]
  \begin{center}
  \begin{tabular}{|l|l|l|r|r|}
  \hline
  \textbf{Maschine} & MHz & \textbf{OS} & \textbf{pipe} & \textbf{shm} \\
  \hline
  DEC2100 & 12.5 MHz & Ultrix & 326,0 & 187,0 \\
  DEC2100 & 12.5 MHz & Aegis & 30,9 & 12,4 \\
  \hline
  DEC3100 & 16.67 MHz & Ultrix & 243,0 & 139,0 \\
  DEC3100 & 16.67 MHz &Aegis & 22,6 & 9,3 \\
  \hline
  DEC5000/125 & 25.0 MHz & Ultrix & 199,0 & 118,0 \\
  DEC5000/125 & 25.0 MHz & Aegis & 14,2 & 5,7 \\
  \hline
  \end{tabular}
  \caption{\small \label{ipc} Zeit für Interprozeßkommunikation mit der
  Hilfe von pipes und shared memory. Zeiten in Mikrosekunden.}
  \end{center}
\end{table}

Mit der Verwendung nutzungsgeteilten Speichers (\textit{shared memory}) und
diesen geschützten Kontrolltransferen werden in ExOS die üblichen
Abstraktionen wie \textit{pipes} implementiert. Die Überlegenheit dieser
Implementation zeigt sich in der Tabelle \ref{ipc}. Hier wurde ein Zähler
zwischen zwei Prozessen hin- und hergereicht und dabei jedes mal
inkrementiert. Ultrix verwendet dabei standard Unix-Pipes. Bei der Nutzung
von shared memory (shm) für den Zeiger ist der Geschwindigkeitsvorteil noch
einmal größer. Dies liegt u.a. auch an der Tatsache, daß Ultrix keinen
\textit{yield}-Aufruf kennt, um die verbleibende CPU-Zeit einem anderen
Prozeß zu übergeben.

\subsubsection{Dynamische Netzwerk-Paketfilter}

Bei Netzwerk-Paketfiltern muß die Reaktionszeit möglichst gering gehalten
werden. Würde man aus dem Netzwerk eintreffende Pakete den entsprechenden
Anwendungen zuordnen, indem man sie von Prozeß zu Prozeß weiterreicht, so
wird man bei einer großen Anzahl von Filtern mit proportional wachsenden Kosten
für Kontextwechsel rechnen müssen. Außerdem verhindert dies nicht die
Möglichkeit des Ausspionierens von Paketen, die nicht für diese Applikation
bestimmt waren (\textit{spoofing}).

Aegis nutzt nun für seine \textit{Dynamic Packet Filter} (DPF) die
Möglichkeit, Code in den Kern zu laden. Normalerweise sind Paketfilter
interpretierte Programme und dementsprechend langsam. Der DPF produziert
hingegen nativen Maschinencode bei der Installation des Filters. Als
Nebeneffekt lassen sich damit auch Überlappungen erkennen und entsprechend
bösartige Filter abweisen. In Tabelle \ref{dpf} sind die Ergebnisse eines
Experiments, bei dem 60 Byte Pakete über Ethernet 4096 mal hin- und
hergeschickt wurden, zuerst ohne DPFs, dann mit und schließlich der
Ultrix-Referenzwert.

\begin{table}[tbp]
  \begin{center}
  \begin{tabular}{|l|c|r|}
  \hline
  \textbf{Maschine} & \textbf{OS} & \textbf{Latenzzeit}  \\
  \hline
  DEC5000/125 & Aegis/ExOS ohne DPF & 320 \\
  DEC5000/125 & Aegis/ExOS mit DPF & 259 \\
  DEC5000/125 & Ultrix & 3400 \\
  \hline
  \end{tabular}
  \caption{\small \label{dpf} Latenzzeit für die Beantwortung eines 60 Byte
  Pakets ohne DPF, mit DPF und unter Ultrix. Zeiten in Mikrosekunden.}
  \end{center}
\end{table}

\subsubsection{\textit{Application-Specific Safe Handlers} (ASH)}

Intern werden die obengenannten Paketfilter durch die etwas allgemeinere
Variante der sog. \textit{Application-specific safe handlers} realisiert.
Diese in den Kern geladenen Routinen laufen im Kontext des Kerns (müssen
also nicht über den Prozeß-Scheduler in den Kontext der jeweiligen Prozesse
gebracht werden) und können Prozesse aufgrund von Ereignissen aufwecken
(z.B. indem sie ein Signal oder eine Nachricht an diesen Prozeß schicken).
Der Vorteil ist das bereits mehrfach erwähnte Wegfallen von Kontextwechseln
für die Ausführung nur weniger Zeilen Code für eine Abfrage.

\subsection{Xok / ExOS}

Nachdem Aegis bereits im Mikro\-bench\-mark-Be\-reich be\-ein\-druck\-en\-de
Per\-for\-mance\-stei\-ger\-ung\-en gezeigt hat, wie verhält es sich nun mit der
globalen Leistung unoptimierter Software? Wie steht es mit den Vorteilen
eines maßgeschneiderten libOS für eine große Applikation? Dazu betrachten
wir ab nun Xok, den Exokernel für x86 Architekturen und vergleichen ihn
mit OpenBSD.

\subsubsection{Unoptimierte Software}

Tabelle \ref{unmod} zeigt, daß selbst unmodifizierte, sprich, nicht speziell
für den Exokernel optimierte Applikationen bereits gleich schnell oder gar
schneller laufen. Daraus kann man schließen, daß die globale Leistung eines
Exokernel-Systems keine substantiellen Geschwindigkeitseinbußen durch das
Multiplexen der Hardware auf niedrigem Niveau erfährt -- eher das
Gegenteil ist der Fall.

\begin{table}[tbp]
\begin{center}
  \mbox{\epsfxsize=0.75\textwidth \epsffile{unmodunix.eps}}
  \caption{\small \label{unmod} Performance unmodifizierter UNIX
  Applikationen. Xok/ExOS und OpenBSD/C-FFS verwenden ein C-FFS Dateisystem,
  während Free/OpenBSD ihr natives FFS Dateisystem verwenden. Zeiten in
  Sekunden.}
  \end{center}
\end{table}

\subsubsection{Cheetah Web-Server}

Der \textit{Cheetah HTTP/1.0 Server} ist das beste Beispiel dafür, wieviel
Geschwindigkeit man durch aggressive Optimierung aus einem Exokernel-System
holen kann. Er nutzt folgende Optimierungen aus, um die bis zu 8x höhere
Leistung erreichen:

\begin{description}
\item[Verschmolzener Datei- und Sendepuffer] Cheetah vermeidet
jegliches Be\-rüh\-ren der Daten im Speicher durch die CPU und die Existenz
eines zweiten Retransmissionspuffers für Pakete. Der Dateicache kann direkt
über die Netzwerkhardware ausgegeben werden, da die nötigen Checksummen
bereits mit den Dateien abgespeichert wurden.
\item[Paketverschmelzungen] Cheetah verzögert das Senden redundanter
Bestätigungspakete bei HTTP Seitenanforderungen, da es davon ausgeht, diese
gleichzeitig mit den Dokumenten verschicken zu können (besonders bei
kleinen Dokumenten).
\item[Dateigruppierung auf Basis des HTML-Dokuments] Cheetah ordnet (wenn
möglich) die Dateien auf der Festplatte so an, daß zusammengehörige
Dateiblöcke (im Sinne der Anfragesequenz durch das übergeordnete HTML-Dokument)
kontinuierlich hintereinander gelesen werden können. Dies führt zu einer
Steigerung des Durchsatzes bis zu einem Faktor von zwei (falls die Dateien
nicht bereits im Cache waren).

\end{description}

\begin{table}[tbp]
\begin{center}
  \mbox{\epsfxsize=0.75\textwidth \epsffile{cheetah.eps}}
  \caption{\small \label{cheetah} HTTP Dokumentdurchsatz abhängig von der
Dokumentgröße. \textbf{NCSA/BSD} repräsentiert einen NCSA/1.4.2 Server unter
OpenBSD, \textbf{Harvest/BSD} entspricht einem Harvest proxy cache unter OpenBSD,
\textbf{Socket/BSD} repräsentiert den Cheetah-HTTP Server, der die TCP-Sockets von
OpenBSD verwendet. \textbf{Socket/Xok} entspricht Socket/BSD, nur daß die TCP/IP
Implementation von Xok verwendet wird, \textbf{Cheetah/Xok} repräsentiert
den Cheetah-HTTP Server, der die optimierten TCP- und
Datei\-system\-implemen\-tationen ausnutzt.}
  \end{center}
\end{table}

Was aus der Tabelle nicht ersichtlich ist: Alle socket-basierten
Implementationen sind begrenzt auf etwa 16,5 MB/s bei 100\% CPU Auslastung,
während bei Cheetah über 29,3 MB/s durchgesetzt werden, wobei die CPU über
30\% der Zeit untätig ist. Dies stellt also eher eine Begrenzung der
Performance durch die verwendete Netzwerkhardware dar, als eine
Rechenleistungserschöpfung.

\subsection{Probleme}

Nach all diesen sehr beeindruckenden Ergebnissen darf man natürlich nicht
vergessen, daß es natürlich auch Probleme gibt.

\subsubsection{Schwieriges Schnittstellendesign}

Die Entwicklung einer Schnittstelle zu einem Exokernel ist äußerst
schwierig. Das Ziel, die Ressourcen des Systems zu veräußern, muß immer
garantieren, auch genug Schutzmöglichkeiten zu bieten. Während der
Entwicklung des Exokernels wurden die APIs mehrfach neu definiert. Eine
konsistente Schnittstelle ist jedoch für die Kompatiblität sehr wichtig.

\subsubsection{Sicherheit}

In der jetzigen Implementierung sind einige globale Kernelstrukturen nicht
schreib\-ge\-schützt und können von jeder Applikation verändert werden. Dies
könnte ausgenutzt werden, um Angriffe auf die Systemstabilität und
Sicherheit zu führen. Bei allen Geschwindigkeitstests wurden beim Zugriff
auf diese Strukturen zwei zusätzliche Kern-Aufrufe mit eingebaut, um den
Schutz dieser Datenbereiche zu simulieren. Natürlich sollte es kein Problem
darstellen, diese Strukturen tatsächlich zu schützen, dies stand jedoch bei
der Entwicklung des Exokernels nicht direkt an erster Stelle.

Durch die Freigabe privilegierter CPU Befehle für Applikationen muß das
System darauf achten, daß z.B. der TLB nicht unsachgemäß verändert wird.
Ich persönlich halte es für schwierig, alle Programmiertricks auszuschließen, um
derartige Modifikationen zu vermeiden.

Ähnliches gilt für das Herunterladen von Code in den Kern. Sandboxing und
Codeinspektion mögen einen großen Schutz bieten, aber um jede mögliche
böswillige Manipulation zu verhindern, bedarf es komplexer
Verifikationsmechanismen (mit meist nicht-polynomialer Laufzeit). Dies ist
auch der Grund, warum Application Safe Handlers (ASHs) in der jetzigen
Implementation von Xok nicht mehr verwendet werden: nicht-interpretierter,
nativer Code einer Turing-vollständigen Sprache kann nicht ausreichend
verifiziert werden. DPFs (kompiliert) und UDFs (interpretiert) sind jedoch
gut und sicher in den Kern ladbar.

\subsubsection{Verlust von Informationen}

Aufgrund der Implementation hoher Abstraktionen auf Applikationsniveau
kommt es oft zu einem gewissen Verlust wertvoller Informationen. Wenn z.B.
virtueller Speicher und das Dateisystem von einer Applikation verwaltet
werden, so kann der Kern nicht mehr zwischen Speicherseiten unterscheiden,
die Plattenblöcke oder virtuellen Speicher beinhalten.

\subsubsection{Codegröße}

Da nun jede Applikation ein eigenes libOS verwenden kann, besteht die
Gefahr, daß die Anwendungen sehr groß werden (die Nutzung von shared
libraries anstatt hinzugelinkter Codestücke schafft hier nur teilweise
Abhilfe). Dazu kommt noch, daß es schwierig ist, libOS'e zu schreiben, die
sich selbst bei Bedarf dynamisch in den Speicher laden, was also zu einem
höheren Speicherbedarf führt.

\subsubsection{Verfügbarkeit}

Im Gegensatz zu den anderen Betriebssystemen wie NetBSD oder Linux ist im
Moment kein Exokernel-System wirklich einsatzfähig.\footnote{Es ist jedoch
möglich, die derzeitige Version von Xok mit einigem Aufwand auf einem
x86-System zu installieren, auch die Sourcen sind im Internet verfügbar}
Die Entwicklung geht meines Erachtens etwas zäh voran und so ist in
frühestens 3-5 Jahren mit einem stabilen und ausgereiften System zu
rechnen. Es ist noch nicht abzusehen, welche weiteren Probleme wohl bei
einer breiteren Nutzung eines Exokernels auftreten können.

Jedes System ist nur so gut, wie das, was der Applikationsprogrammierer
daraus macht. Wenn sich niemand an die Programmierrichtlinien hält, könnten
die Freiheiten der Exokernel-Architektur zu globalem Chaos führen.

\section{Schlußfolgerung}

Der Exokernel-Ansatz beweist, daß sich viele Probleme moderner
Betriebssysteme durch die Elimination der Abstraktionen und der
Verwaltungsarbeit der Systemressourcen aus dem Kern lösen läßt. Ein wenig
habe ich jedoch das Gefühl, daß er die Probleme nur auf die
Applikationsebene verschiebt. Aber das reicht aus, um (dank den
Betriebssystemen als Bibliotheken) Optimierungen und Innovationen bereits
dem Nicht-Kernel-Entwickler auf eine einfache Art und Weise zu ermöglichen.

Ein Exokernel ist jedoch kein Allheilmittel: Er kann nicht verhindern, daß
schlecht programmierte Software langsam läuft. Dennoch bin ich der Meinung,
daß dieser Ansatz verfolgungswürdig ist und man nach einigen Jahren
weiterer Forschung auf diesem Gebiet durchaus ein ausgereiftes System in
den Händen halten wird, daß eine echte Alternative zu den derzeitigen
monolithischen Systemen bietet.

\nocite{*}
\newpage
\addcontentsline{toc}{part}{Literaturverzeichnis}
\bibliographystyle{plaindin}
\bibliography{CH-Exo}

Alle Dokumente sind zu finden auf\\
\texttt{http://amsterdam.lcs.mit.edu/PDOS-papers.html}

\end{document}