Singularity

From SarWiki
Jump to: navigation, search

Singularity ist die Bezeichnung für den Prototyp eines neuartigen Betriebssystems, dass gegenwärtig bei Microsoft Research entwickelt wird und vor allem für den Einsatz auf x86-Plattformen konzipiert ist.

Die Besonderheit des Systems gegenüber etablierten Betriebssystemen, wie etwa Windows, Linux oder Solaris, besteht darin, dass Singularity den Schutz von Systemressourcen, insbesondere die Isolation einzelner Prozesse, ausschließlich mithilfe von Softwaremechanismen realisiert und sich dabei nicht auf die Unterscheidung verschiedener CPU-Betriebsmodi (x86-Privilege-Rings) stützt.


Begriffsbestimmung

/* TODO */

Motivation

Ziel der Entwicklung von Singularity ist es, ein Betriebssystem zu schaffen, das sich zum einen durch Eigenschaften wie Robustheit, Stabilität, Zuverlässigkeit und Sicherheit auszeichnet und zum anderen ausreichend leistungsfähig ist, um sich auch für den praktischen Einsatz im Alltag zu eignen.

Schutz von Ressourcen und Prozessisolation

Zu den wünschenswerten Eigenschaften eines Betriebssystems gehören unter anderem Robustheit, Zuverlässigkeit und Sicherheit. Um diese Eigenschaften zu gewährleisten, sind Mechanismen bereitzustellen, die das System und die zugrunde liegenden Hardwareressourcen vor Fehlern oder Schäden durch unsachgemäßen oder gar böswilligen Zugriff schützen. Eine zentrale Rolle kommt dabei der Prozessisolation zu: Das Betriebssystem stellt jedem Prozess einen privaten (Speicher-)Adressraum zur Verfügung, den nur er selbst zu modifizieren berechtigt ist. Diese Vorgehensweise schafft eine Barriere, die die Entstehung von Fehlern durch direkte Wechselwirkungen zwischen den einzelnen Prozessen und deren unkontrollierte, möglicherweise mit irreparablen Schäden verbundene Multiplikation verhindert.

Hardwareunterstützung

Handelsübliche Betriebssysteme stützen sich im Wesentlichen auf zwei Hardware-Features moderner Prozessoren, um einen willkürlichen Zugriff einzelner Prozesse auf beliebige Speicheradressen zu verhindern:

  1. Memory Management Unit (MMU)
    Sie überprüft die Zugriffsberechtigung eines Prozesses bei der Übersetzung von virtueller in physische Speicheradresse anhand der Pagetabelle.
  2. CPU-Betriebsmodi (x86-Privilege-Rings)
    Die Verwendung unterschiedlicher CPU-Betriebsmodi beschränkt die Ausführung bestimmter, als privilegiert gekennzeichneter Instruktionen auf den Kernel. Dazu gehören insbesondere diejenigen Instruktionen, die den Betrieb der MMU und die Adressüberprüfung betreffen, aber auch solche die bspw. für einen Zugriff auf die I/O-Controller des Systems benötigt werden. Als Konsequenz dieses Mechanismus ist ein Zugriff auf geschützte Ressourcen aus dem User-Modus nur mit Unterstützung des Kernels über entsprechende Systemrufe möglich.

Der große Nachteil dieser Vorgehensweise besteht in der Kostspieligkeit des Übergangs vom User- in den Kernel-Modus (Ring 3 nach Ring 0). Dabei fallen im Grunde genommen dieselben Arbeitsschritte an, wie sie auch bei einem Context-Switch durchzuführen sind:

  • Wechsel des CPU-Kontextes (Austausch von Instruction-Pointer und CPU-Registern, Fortführung der Abarbeitung auf dem Kernelstack)
  • Wechsel des Speicherkontextes (Laden der Pagetabelle für den Kernel, Flush des TLB auf x86-Architekturen)
  • Kopieren von Argumenten zwischen User- und Kernelspace

Dieselbe Arbeit ist noch einmal bei der Rückkehr aus dem Kernel zum Userprozess zu leisten.

Ein solch rigider, hardwaregestützter Prozessisolationsmechanismus benachteiligt bei konsequenter Anwendung vor allem diejenigen Prozesse, die häufig I/O-Operationen durchführen oder intensiv mit anderen Prozessen kommunizieren, da hierzu ständig Systemrufe auszuführen sind. Als Konsequenz daraus wird die strikte Isolierung von Prozessen in den heute verbreiteten Betriebssystemen an vielen Stellen zugunsten gesteigerter Performance und Flexibilität aufgeweicht.

Offene Prozessarchitektur

Bekannte Betriebssystemvertreter wie etwa Linux, Windows oder Solaris basieren auf einer offenen Prozessarchitektur ("Open Process Architecture"). Die einzelnen Adressräume sind zwar prinzipiell durch die obig beschriebenen Hardwaremechanismen voneinander getrennt, allerdings wird dies zwecks Kostenersparnis und Flexibilität nicht an allen Stellen konsequent durchgehalten.

Die Merkmale einer offenen Prozessarchitektur lassen sich wie folgt zusammenfassen:

  • Verwendung von Shared Memory
  • Unterstützung für dynamisches Generieren und Nachladen von Programmcode
    Durch Reflektionsmechanismen ist es Prozessen möglich, ihren eigenen Programmcode zur Laufzeit zu analysieren und modifizieren (Bsp.: Just-In-Time Compilation von Programmcode durch die Java Virtual Machine). Ebenso lassen sich Programmerweiterungen und Plug-ins zur Laufzeit direkt in den Adressraum eines Prozesses laden. So ist bspw. eine Vielzahl an Treibern heutzutage von vorne herein als Modul realisiert, das dynamisch in den Kernel eingebunden werden kann.
  • Bereitstellung einer universellen System-API, die die direkte Modifikation der Daten eines Prozesses ermöglicht (Bsp.: Debugging-APIs für unprivilegierte Prozesse)

Die Nachteile einer solchen Architektur liegen auf der Hand:

  • Shared Memory stellt zwar einen effektiven Kommunikationsmechanismus dar, ist aber aufgrund der erforderlichen Zugriffssynchronisation recht fehleranfällig und geht mit der Kopplung des Fehlerverhaltens aller beteiligten Prozesse einher.
  • Dynamisch nachladbare Softwarekomponenten enthalten potenziell fehlerhaften oder gar böswilligen Code. Trotzdem werden sie ohne weitere Sicherheitsvorkehrungen direkt in den privaten Adressraum eines Prozesses, ja häufig sogar direkt in den Kernel eingebunden. So wird bspw. berichtet, dass bis zu 85% aller diagnostizierten Windows-Crashes auf fehlerhafte Treiber zurückzuführen sind [2].
  • Die Implementation von Erweiterungen geschieht häufig unter Verwendung privater Details des Hostcodes, d.h.: ohne die Verwendung klar definierter Interfaces. Diese Verquickung von Host und Erweiterung erschwert zum einen die Wartbarkeit und verursacht zum anderen schnell Kompatibilitätsprobleme, falls sich der Hostcode an entscheidenden Stellen ändert.
  • Die Möglichkeit Code zur Laufzeit einzubinden, stellt eine erhebliche Schwierigkeit für die Optimierung und Verifikation der Korrektheit des Programmcodes durch den Compiler oder andere statische Werkzeuge dar. Diese können in der Regel nicht davon ausgehen, dass sich der bestehende Code zwischen zwei Instruktionen zur Laufzeit nicht ändert. So ist es vorab bspw. unmöglich vorherzusagen, ob ein bestimmter Programmteil zur Laufzeit überhaupt Verwendung finden wird oder nicht. Folglich kann ein Compiler diesen auch nicht von vorneherein als toten Code einstufen und von der Übersetzung ausnehmen. Die Optimierung des Programmcodes muss also zu großen Teilen zur Laufzeit erfolgen, was sich negativ auf die Performance auswirken kann.


Das Hauptziel der Entwicklung von Singularity bestand in der Beseitigung der Schwächen einer offenen Prozessarchitektur, die durch die Aufweichung der Prozessisolation entstehen, wobei es Mechanismen zu entwickeln galt, die effektive Systemrufe sowie eine performante Interprozesskommunikation ermöglichen.

Architektur des Singularity Prototyps

Singularity verfolgt das Konzept einer geschlossenen Prozessarchitektur ("Sealed Process Architecture"). Ein spezielles Prozessmodell, der softwareisolierte Prozess ("Software Isolated Process" oder SIP), kombiniert mit einem eigens entwickelten Kommunikationsmechanismus, dem so genannten Channel, sorgt dafür, dass das System eine akzeptable Performance erreicht.

Geschlossene Prozessarchitektur

Eine geschlossene Prozessarchitektur zeichnet sich durch die vier folgenden Invarianten aus:

  1. "Fixed Code Invariant"
    Ist ein Prozess einmal gestartet, so kann sein Programmcode nachträglich nicht mehr verändert werden. Dynamisches Generieren oder Nachladen von Code werden durch das System nicht unterstützt. Module sowie Programmerweiterungen werden jeweils als eigenständiger Prozess gestartet, der mit der Host-Applikation auf gesondertem Wege kommuniziert.
  2. "State Isolation Invariant"
    Der direkte Zugriff auf die Daten eines Prozesses ist nur ihm selbst und keinem anderen Prozess gestattet. Es ist einem Prozess demnach strikt untersagt, einen gültigen Verweis auf Daten eines anderen Prozesses zu besitzen.
  3. "Explicit Communication Invariant"
    Die gesamte Interprozesskommunikation erfolgt über explizite (verbose) Mechanismen. Der Sender einer Nachricht identifiziert sich explizit gegenüber dem Adressaten, sodass dieser die Möglichkeit erhält, den Empfang oder die Weiterleitung von Mitteilungen abzulehnen. Eine Kommunikationsmöglichkeit über Shared Memory besteht nicht.
  4. "Closed API Invariant"
    Die System-API darf keinem unprivilegierten Prozess Funktionalitäten bereitstellen, die es ihm erlauben, eine der drei anderen Invarianten zu verletzen.
    Beispiel : Export einer universellen Debugging-API, die einen lesenden und schreibenden Zugriff auf Daten eines beliebigen Prozesses ohne dessen Einwilligung ermöglicht.
    Allgemein : direkte Verwendung privilegierter CPU-Assemblerinstruktionen durch unprivilegierte Prozesse.


Abb.1: Hardware- Vs Softwareisolation

Obwohl dieses Systemdesign offensichtlich wesentliche Schwächen einer offenen Prozessarchitektur beseitigt, tut sich bei der konkreten Umsetzung doch vor allem eine gewichtige Schwierigkeit auf:
Um die Zustandsisolation (Invariante 2) der einzelnen Prozesse zu gewährleisten, sind die herkömmlichen, hardwaregestützten Mechanismen (CPU-Betriebsmodi und MMU) offensichtlich ungeeignet, da bei ihrer Verwendung vor allem der Übergang vom User- in den Kernel-Modus zu kostspielig ausfiele. Im Falle der Nachrichtenübermittlung wäre zusätzlich ein erheblicher Kopieraufwand zu betreiben. Die auszutauschenden Daten müssten jeweils über den Kernel vom Adressraum des Senders vollständig in denjenigen des Empfängers kopiert werden.

Singularity begegnet diesem Problem wie folgt:
Der bekannte Hardwaremechanismus zur Zugriffskontrolle wird durch eine größtenteils statisch durchführbare, softwarebasierte Überprüfung der Zustandsisolation ersetzt, was sich äußerst günstig auf die Systemperformance auswirkt. Das zur Implementation des Systems verwendete C#-Derivat Sing# verfügt zudem über eine erweiterte Syntax, die eine explizite Spezifikation des Kommunikationsverhaltens von Prozessen unterstützt, wie sie die Kommunikationsinvariante der geschlossenen Prozessarchitektur fordert. Hierdurch wird die Einhaltung der Zustandsisolation selbst im kritischen Fall der Interprozesskommunikation, während der zwangsläufig Daten zwischen Prozessen ausgetauscht werden, bereits zur Installationszeit verifizierbar. Aufgrund der Verwendung von Softwaretools zur Überwachung der Isolation werden Prozesse in Singularity auch als softwareisolierte Prozesse ("Software Isolated Processes" oder SIPs) bezeichnet. Der zur Kommunikation verwendete Channel-Mechanismus bietet zudem die Möglichkeit, selbst große Datenmengen ohne Kopieraufwand zwischen einzelnen SIPs zu versenden.

Typ- und Speichersicherheit

Typ- und Speichersicherheit sind eng miteinander verwobene Eigenschaften einer Programmiersprache. Sie bilden die Grundlage der Prozessisolation in Singularity.

Typsicherheit garantiert, dass der Inhalt einer Variablen eines bestimmten Typs immer korrekt interpretiert und manipuliert wird, d.h. unter anderem keine Operationen auf einem Datenobjekt ausgeführt werden, die für den speziellen Objekttyp nicht definiert sind und daher mit hoher Wahrscheinlichkeit zu Fehlern führen. Cast-Operationen zu nicht verwandten Typen sind somit in jedem Fall untersagt.

Speichersicherheit unterbindet den willkürlichen Zugriff auf beliebige Speicheradressen, stellt sicher, dass Referenzen innerhalb eines Programms stets auf Speicherbereiche verweisen, die mit einem gültigen Datenobjekt belegt sind, und beseitigt auf diese Weise weitere typische Quellen für Programmfehler. Zu diesem Zweck wird auf ein manuelle Speicherverwaltung mithilfe von Pointern und Pointerarithmetik verzichtet. Garbage-Collectoren übernehmen die Deallokation von Heapspeicher und verhindern das Auftreten von dangling References.

Speichersicherheit ist ohne Typsicherheit nicht denkbar. Ohne diese wäre es problemlos möglich, bspw. einen Integer zu einem Pointer zu casten und damit - das Vorhandensein eines zusätzlichen Schutzes durch das Betriebssystem ausgeschlossen - Zugriff auf nahezu beliebige Speicheradressen zu erlangen. Ebenso bildet Speichersicherheit eine notwendige Voraussetzung für die Typsicherheit einer Sprache. Ein willkürlicher Speicherzugriff über Zeiger würde das Kopieren eines beliebigen, typfremden Datenojekts in den Speicherbereich einer jeden Variablen erlauben.

Beispiele für sichere, objektorientierte Sprachen sind z.B.: Java, Python oder C#, auf das auch die zur Implementation von Singularity verwendete Sprache Sing# aufbaut.

SIPs - Softwareisolierte Prozesse

SIPs bilden das Gegenstück zu Prozessen in handelsüblichen Betriebssystemen, zeichnen sich aber im Gegensatz zu diesen durch einige Besonderheiten aus:

  • SIPs sind abgeschlossene Coderäume, d.h.: sie sind nicht befähigt, zur Laufzeit Code (Klassen, Bibliotheken, etc.) nachzuladen (Fixed Code Invariant).
  • SIPs sind typ- und speichersicher.
    Die Typ- und Speichersicherheit des SIP-Codes kann in Singularity zum Großteil bereits zur Compilezeit überprüft werden. In einigen Fällen, bspw. zur Überprüfung dynamischer Typen, sind allerdings weiterhin Laufzeittests erforderlich.
    Die statische Verifikation der Typ- und Speichersicherheit läuft in mehreren Schritten ab:
    Das Compiler-Frontend übersetzt den vorliegenden Programmcode zunächst in eine Zwischenrepräsentation vergleichbar mit dem Java Bytecode, die als Microsoft Intermediate Language (MSIL) oder Common Intermediate Language (CIL) bezeichnet wird. Dabei wird die Typsicherheit des nativen Programms überprüft.
    Das produzierte Kompilat ist ebenfalls mit Typinformation ausgestattet, die ausgenutzt wird, um in einem zweiten Schritt auch dessen Typsicherheit zu verifizieren. Fehler, die mit der Übersetzung in den Zwischencode zusammenhängen, können so rechtzeitig erkannt werden.
    Im letzten Schritt wird schließlich der Zwischencode durch das Compiler-Backend in ausführbaren x86-Code überführt. Derzeit wird die Entwicklung einer Typed Assembly Language (TAL) angestrebt, die es ermöglichen soll, den an sich typlosen, ausführbaren Binärcode mithilfe eines schlanken Verifikators ein weiteres Mal auf seine Sicherheit hin zu überprüfen, um Fehler im abschließenden Compilationsschritt aufzuspüren. Solange diese Arbeit noch nicht abgeschlossen ist, kommen nur solche Sprachen für die Applikationsprogrammierung in Frage, die sich nach MSIL übersetzen lassen. Alternativ ist es möglich, bereits bestehende, in anderen Sprachen verfasste Programme in einer hardwareisolierten Domäne zur Ausführung zu bringen (siehe [1]).
Abb.2: SIPs und Exchange Heap
  • SIPs sind in der Lage, untereinander Nachrichten auszutauschen. Diese werden in einer speziell zu diesem Zweck vorgesehenen Hauptspeicherregion, dem Exchange Heap, verwahrt und können über so genannte Channels versandt werden.
    Für jeden Channel existiert ein Kommunikationsvertrag (Contract), der den Typ des Channels, den Typ der versendeten Nachrichten und den Ablauf der Kommunikation explizit spezifiziert. Anhand dieser Information lässt sich wiederum bereits zur Compilezeit überprüfen, dass die geforderte Zustandsisolation nicht durch Übergabe von Objektreferenzen oder den parallelen Zugriff auf Nachrichten durch Sender und Empfänger verletzt wird, und dass Typ- sowie Speichersicherheit auch während der Kommunikation gewahrt bleiben (Explicit Communication Invariant).
  • SIPs sind unprivilegierte Prozesse.
    Die Ausführung privilegierter Operationen bleibt auf den Kernel beschränkt, der eine eigene softwareisolierte Domäne bildet. Die Trennung zwischen privilegierten und unprivilegierten Prozessen erfolgt nicht wie gewohnt unter Nutzung der verschiedenen Betriebsmodi der x86-Hardware, sondern wird auch in diesem Fall durch eine statische Überprüfung der Programme zum Zeitpunkt der Installation vollzogen. Unprivilegierte Programme, deren Code auf privilegierte CPU-Instruktionen zurückgreift, werden vom System abgelehnt.
    Zugriff auf privilegierte Operationen erhalten SIPs - wie auch in anderen Betriebssystemen üblich - nur mittels Systemruf. Der Kernel exportiert aber keine Funktionalitäten, die eine Verletzung der Architekturinvarianten erlauben könnte. Systemrufe akzeptieren lediglich primitive Argumente (Closed API Invariant).
  • SIPs bilden geschlossene, komplett voneinander isolierte Objekträume (State Isolation Invariant).
    Kein SIP besitzt eine direkte Referenz auf Objekte eines anderen SIPs. Nachrichten haben zu jedem Zeitpunkt einen eindeutigen Besitzer, der über ein exklusives Zugriffsrecht verfügt. Die Isolation ergibt sich direkt aus der verifizierten Typ- und Speichersicherheit, den geschilderten Kommunikationsregeln und der API-Invariante:
    Da der Zugriff auf fremde Objekte über Pointerarithmetik, Cast-Operationen oder mittels privilegierter Instruktionen ausgeschlossen ist, wäre ein solches Unterfangen theoretisch nur noch über die direkte Herausgabe von Objektreferenzen durch andere SIPs oder aber eine geteilte Verfügung über Nachrichteninhalte möglich. Derartige Aktionen lassen sich jedoch unter Zuhilfenahme der Kommunikationsinvariante ebenfalls vollständig unterbinden.
Konsequenzen für die Systemperformance:
  • Aufgrund der für SIPs geltenden Zustandsisolation lassen sich jeweils individuelle , auf die Bedürfnisse der entsprechenden Applikation zugeschnittene Laufzeitumgebungen und Garbage-Collectoren verwenden, was sich positiv auf die Laufzeitperformance der Prozesse auswirkt.
  • Alle SIPs können mitsamt dem Kernel und dem Exchange Heap in ein- und demselben virtuellen Adressraum im Privilege-Ring 0 laufen, ohne dass dabei eine Gefahr von Zugriffsverletzungen für laufende Prozesse oder die Hardware besteht. Es kann also eine systemweit einheitlich geltende Pagetabelle zur Adressübersetzung eingesetzt werden, was den Verwaltungsaufwand für Prozesse erheblich reduziert und die Prozesserzeugung vereinfacht. Ebenso profitiert die Performance des Kontextwechsels, bei dem nun auf einen Wechsel des Speicherkontextes und einen Flush des Translation Lookaside Buffer (TLB) verzichtet werden kann.
    Systemrufe lassen sich unter diesen Voraussetzungen wie gewöhnliche Funktionsaufrufe ausführen, also, ohne dass dabei ein Wechsel des Stacks, des Adressraums oder des CPU-Betriebsmodus erforderlich wäre, woraus sich ein erheblicher Geschwindigkeitszuwachs ergibt. Stackframes des Kernels sind für den Garbage-Collector entsprechend zu kennzeichnen.


Auch die Umsetzung der Softwareisolation ist noch mit ungelösten Problemen, z.B.: dem Umgang mit DMA behaftet. Auf eine genauere Betrachtung wird aber an dieser Stelle verzichtet.

Interprozesskommunikation über Channels

Channels stellen einen universellen, bidirektionalen Kommunikationsmechanismus dar, den SIPs in Singularity zur effektiven Interaktion untereinander oder mit dem Kernel nutzen. Dabei ist stets sicherzustellen, dass die Kommunikationspartner beim Austausch von Nachrichten isoliert bleiben (State Isolation Invariant)!

Exchange Heap

Der Exchange Heap repräsentiert eine speziell für die Übermittlung von Nachrichten vorgesehene Hauptspeicherregion, die sich in ein- und demselben Adressraum mit den SIPs sowie dem Singularity-Kernel befindet.
Neben den eigentlichen Nachrichten enthält der Heap auch die Endpunkte der Channels, über die die Versendung stattfindet.
Alle im Bereich des Heaps abgelegten Daten unterliegen speziellen Restriktionen, die die Zustandsisolation als Systeminvariante auch während des Nachrichtenaustauschs garantieren:

  • Der Exchange Heap beinhaltet weder Objekte (Attribute + Funktionen) noch Referenzen auf Objekte, die sich im Objektraum eines SIPs befinden. Folglich handelt es sich bei Nachrichten ausnahmslos um primitive Datentypen oder Strukturen. Verweise in den Exchange Heap selber sind diesen allerdings grundsätzlich gestattet. So lassen sich auch komplexere Datenkonstrukte als Nachricht übermitteln.
  • Jedes Datum innerhalb des Heaps lässt sich zu jedem Zeitpunkt einem eindeutigen Besitzer (Prozess oder Thread) zuordnen. Mit dem Versenden einer Nachricht wird gleichzeitig das zugehörige Zugriffsrecht vom Sender an den Empfänger abgetreten und kann ohne dessen Kooperation auch nicht wieder erlangt werden.

Gerade im Rahmen der Interprozesskommunikation wird die Bedeutung der Zustandsisolation für die Fehlertoleranz des Systems deutlich:
Sind verschiedene Anwendungen intensiv über geteilte Datenstrukturen miteinander verwoben, ist es im Fehlerfalle nahezu unmöglich, eine saubere Fehlererholung durchzuführen, da hierzu nun nicht mehr nur der lokale Programmzustand, sondern eben auch derjenige der einzelnen Kommunikationspartner berücksichtigt werden muss. Eine Beendigung des fehlerhaften Prozesses samt Freigabe seiner Ressourcen - mit oder ohne geteilte Daten - gestaltet sich ebenfalls problematisch. Dieses Vorgehen hinterließe alle anderen Beteiligten in einem potenziell nicht konsistenten Zustand. Folglich besteht der einzige Ausweg zumeist in der vollständigen Terminierung aller Interaktionspartner (Bsp.: Java VM).
In Singularity lässt sich eine solche Situation weitaus eleganter lösen.
Da sich SIPs allgemein keinen Speicher teilen, ist es immer möglich, einen fehlerhaften Prozess zu beenden und dessen Speicherressourcen freizugeben, ohne dass dabei die Gefahr von Inkonsistenzen oder des Zugriffs auf dangling References für andere Prozesse bestünde. Diese werden über die neue Situation mit einer Exception durch den Kernel informiert, wodurch eine Fehlererholung angestoßen wird, die sich ausschließlich mit den lokalen Gegebenheiten des jeweiligen Prozesses auseinandersetzen muss.

Channels

Ein Channel stellt ein Konstrukt aus genau zwei Endpunkten dar, die über Verweise miteinander verbunden sind, und zwischen denen bidirektional Nachrichten verschickt werden können. Die Endpunkte liegen als Strukturen im Exchange Heap vor und lassen sich so selbst als Nachrichten über bestehende Channels versenden. Auf diese Weise besteht die Möglichkeit, ein dynamisch wachsendes Kommunikationsnetzwerk zwischen einzelnen SIPs zu schaffen. Die Endpunkte eines Channels nehmen bei der Kommunikation verschiedene Rollen ein, die an das bekannte Client-Server-Modell angelehnt sind. Sie werden als Exporter (Exp vgl. Server) und Importer (Imp vgl. Client) bezeichnet. Endpunkte besitzen zusätzlich einen speziellen Typ, der durch den zugrunde liegenden Contract bestimmt wird (Bsp: Contract1.Imp, Contract1.Exp).

Contracts

Contracts ("Kommunikationsverträge") bilden das Fundament für den gesamten Kommunikationsvorgang, der zwischen zwei Prozessen über den dazugehörigen Channel abläuft. Sinn und Zweck eines Contracts ist es, alle Details dieses Vorgangs so explizit wie möglich zu formulieren (Explicit Communication Invariant), um anhand dieser Information vor allem die Wahrung der Zustandsisolation während des Datenaustausches in vollem Umfang überprüfen zu können. Das von den Singularity-Entwicklern entworfene C#- Derivat Sing# unterstützt die Formulierung solcher Contracts durch eine spezielle Syntaxerweiterung.
Contracts werden grundsätzlich aus der Perspektive des Exporters (Servers) verfasst. Die Angaben für den Importer (Client) ergeben sich als Komplement hierzu, weshalb sie nicht noch einmal gesondert aufgeführt werden.
Folgende Angaben sind obligatorisch:

  • Nachrichtentyp und Nachrichtenargumente. Optional kann eine Richtung angegeben werden, in der eine Nachricht über einen Channel versendet werden kann. Ist diese nicht spezifiziert, wird implizit eine bidirektionale Verwendbarkeit angenommen. In jedem Fall sind die für Nachrichtenargumente geltenden Einschränkungen zu beachten (siehe Exchange Heap).
  • Ein Kommunikationsprotokoll, das die Reihenfolge erwarteter und versendeter Nachrichten sowie daran gekoppelte Aktionen auflistet. Zur Protokollbeschreibung werden endliche Automaten verwendet.

Zusätzlich zum eigentlichen Vertragstext sind alle Methoden anzugeben, die auf den Endpunkten des durch den Contract definierten Channels ausgeführt werden können.

Abb.3: Simpler Contract
Abb.4: Methoden auf Channelendpunkten

Abbildung 3 zeigt einen einfachen Contract:
Der Exp wartet in einer Endlosschleife auf eine Nachricht des Typs Request und reagiert auf deren Erhalt mit einer entsprechenden Antwort (Reply) oder einer Fehlermeldung (Error). Die Methoden, die einem Entwickler zur Implementierung des angegebenen Kommunikationsprotokolls zur Verfügung stehen, sind in Abbildung 4 deklariert.

Die Korrektheit des Contracts sowie die Einhaltung der in ihm gemachten Angaben durch eine Applikation, werden durch den Sing#-Compiler ("Bartok") überwacht. Dieser bricht den Compilationsprozess ab, falls der Vertrag einen erkennbaren Fehler enthält oder der Applikationscode in irgendeinem Punkt vom diesem abweicht. Durch die explizite Regelung der Kommunikation im Contract und dessen strikte Durchsetzung durch den Compiler, wird der Rahmen für die Interprozesskommunikation so eng abgesteckt, dass eine Verifikation der Zustandsisolation (Typsicherheit der Nachrichten, korrekte Übertragung von Zugriffsrechten) ebenfalls nahezu vollständig zur Compilezeit vollzogen werden kann.

Implementation des Nachrichtenaustauschs

Grundsätzlich gilt: Sendeoperationen in Singularity sind nicht blockierend, das Empfangen von Nachrichten hingegen findet synchron statt.
Channel-Endpunkte sind als miteinander durch Pointer verbundene Strukturen implementiert, die sich im Exchange Heap befinden. Sie bestehen im Wesentlichen aus einer Queue für Nachrichten und einer Signalvariablen, über die dem Empfänger das Anliegen einer Nachricht angezeigt werden kann.
Vereinfacht gestaltet sich das Versenden einer größeren Nachricht wie folgt:

  1. Der Sender reserviert zunächst Speicher für den Nachrichteninhalt im Exchange Heap, auf den er anschließend über einen Pointer zugreifen kann. Da der Exchange Heap - genauso wie auch der restliche Heapspeicher des Systems - unter Kontrolle des Kernels steht, ist dazu ein Systemruf erforderlich. Variablen, für die Speicher im Exchange Heap alloziert werden soll, müssen explizit im Programmcode als solche gekennzeichnet werden (Bsp.: R* in ExHeap pr = new ... ), um sie von Daten auf dem privaten Heap eines SIPs unterscheiden zu können. Für Letzteren ist die Verwendung von Pointern aus Gründen der Typ- und Speichersicherheit untersagt.
  2. Nach Erstellung des Nachrichteninhaltes wird der zugehörige Pointer als Argument an den gewünschten, zuvor im Contract vereinbarten Message-Typ übergeben.
  3. Per Zeiger erreicht der Sender den ihm eigenen Channel-Endpunkt im Exchange Heap, der mit seinem Gegenstück wiederum durch einen Zeiger verbunden ist. Dort wird nun die zu versendende Nachricht in die Empfangsqueue eingereiht.
  4. Der Sender signalisiert dem Kernel, dass eine Nachricht für den Empfänger-SIP vorliegt, sodass dieser vom Scheduler aufgeweckt werden kann.

Diese Vorgehensweise bringt ein offensichtliches Problem mit sich: Nach der Übergabe von Nachrichten bleiben beim Sender dangling Pointer zurück! Diese verweisen entweder auf Nachrichtenargumente, die gerade von einem anderen SIP modifiziert werden, oder aber auf einen bereits freigegebenen, undefinierten Speicherbereich. Die manuelle Verwaltung des Exchange-Heap-Speichers untergräbt also ohne weitere Vorkehrungen ganz eindeutig die Typ- und Speichersicherheit und damit auch die Zustandsisolation interagierender SIPs.
Die Invarianten der restlichen Architektur und die explizite Spezifikation des Kommunikationsablaufs über Contracts schränken jedoch, wie bereits angedeutet, den Handlungsspielraum für Prozesse und Threads in diesem Zusammenhang so sehr ein, dass eine nahezu vollständige, statische Überwachung des Ressourcenflusses für die Interprozesskommunikation möglich wird. So stellt der Compiler neben der Einhaltung der im Contract vereinbarten Nachrichtenformate und Aktionsfolgen sicher, dass

  • jeder Prozess nur auf Regionen im Exchange Heap zugreift, die er momentan besitzt, d.h. die er bspw. selbst alloziert hat oder ihm als Nachrichtenargument, bzw. Rückgabewert einer Methode übergeben wurden. Für Applikationen, die über mehr als einen Thread verfügen, sind zusätzliche Laufzeitmechanismen erforderlich. Dieses Vorgehen kann gleichzeitig zur Synchronisation von Prozessen zwecks Vermeidung von Race-Conditions herangezogen werden. Primäres Ziel bleibt in diesem Zusammenhang allerdings die Entkopplung des Fehlerverhaltens von Prozessen (siehe Exchange Heap).
  • keine Speicherlecks entstehen.

(Genauere Informationen hierzu finden sich in [5].)

Die Möglichkeit, große Datenmengen per Zeigerübergabe, d.h.:ohne zusätzlichen Kopieraufwand, und unter gleichzeitiger Aufrechterhaltung der Zustandsisolation zu verschicken, trägt neben den bereits beschriebenen, günstigen Eigenschaften der SIPs entscheidend zur Effektivität des Gesamtsystems bei.

Systemkomponenten im Überblick

Abb.5: Systemkomponenten im Überblick

Abbildung 5 zeigt die Systemkomponenten von Singularity im Überblick.
Dabei handelt es sich auf den ersten Blick um eine typische Microkernelarchitektur. Der Kernel selbst stellt lediglich einige Basisfunktionalitäten, wie Page-, I/O-, Channel-Management und Scheduling bereit, während alle anderen Systemkomponenten, insbesondere Treiber, als unprivilegierte SIPs außerhalb des Kernels laufen.
Da jedoch sämtliche Systembestandteile im Kernel-Modus der CPU (Ring 0) sowie demselben Adressraum ausgeführt werden, könnte man den vorliegenden Systemaufbau ebenso gut als einen einzigen, monolithischen Kernel interpretieren, dessen Einzelteile lediglich durch softwarebasierte Mechanismen besonders voneinander abgegrenzt sind.


Anmerkung: Die gemeinsame Nutzung von Bibliotheken durch SIPs im Read-Only-Modus ist grundsätzlich mit den Invarianten einer geschlossenen Prozessarchitektur vereinbar. Inwieweit dies jedoch in Singularity zum jetzigen Entwicklungszeitpunkt bereits umgesetzt ist, konnten wir bei unseren Recherchen nicht definitiv herausfinden.

Systemperformance

Ein wesentliches Ziel bei der Entwicklung des Singularity Prototyps war es, ein System zu schaffen, dass neben Robustheit, Zuverlässigkeit und Sicherheit mit einer Performance aufwarten kann, die einen praktischen Einsatz im Alltag erlaubt und sich mit derjenigen etablierter Betriebssysteme messen kann.

Kosten senkende Faktoren

Folgende Faktoren tragen zur Senkung der Kosten der geschlossenen Prozessarchitektur in Singularity bei:

  • Effektive statische Optimierung des Programmcodes auf Grundlage der Fixed-Code-Invariante. Kein Run-Time-Overhead durch Nachladen von Klassen, Bibliotheken, etc. .
  • Verwendung auf die jeweilige Applikation speziell zugeschnittener Laufzeitumgebungen und Garbage-Collektoren.
  • Preiswerte Context-Switches. Ein Wechsel des Adressraums und Flush des TLB ist nicht notwendig.
  • Schnelle Systemrufe. Sie entsprechen simplen Funktionsaufrufen auf dem Userstack.
  • Effektiver Austausch großer Nachrichten durch Pointerübergabe. Ein aufwendiges Kopieren ist unnötig.

Benchmarking

Tab.1: Kosten von Basisfunktionen

Tabelle 1 vergleicht die Performance einiger grundlegender Funktionen auf verschiedenen Systemen. Weitere Tests lassen sich den angegebenen Quellen entnehmen.
Als Testplattform kam in allen Fällen ein AMD Athlon 64 3000+ (1.8 GHz) mit 1 GB RAM zum Einsatz. Bei den neben Singularity untersuchten Betriebssystemen handelt es sich um FreeBSD 5.3, Red Hat Fedora Core 4 (Kernel 2.6.11-x) und Windows XP (SP2).
Die untersuchten Basisfunktionen wurden zwischen 100x und 20.000x durchgeführt. Als Ergebnis ist jeweils der Mittelwert der für die Ausführung benötigten CPU-Zyklen angegeben.

  • API-Call

Bei diesem Test galt es, eine jeweils leicht erreichbare Kernelstruktur per Systemruf auszulesen. Hier kann Singularity aus den bereits erwähnten Gründen mit einer 5-10 fach erhöhten Ausführungsgeschwindigkeit gegenüber den Konkurrenten punkten.

  • Thread Yield

Die Messungen wurden im Falle von Singularity und Windows für Kernel-Level-Threads, im Falle der beiden UNIX-Vertreter für User-Level-Threads (Pthreads) durchgeführt. Von der Verwendung von Kernel-Level-Threads wurde bei Letzteren abgesehen, da die Ergebnisse weitaus schlechter ausfielen, als dies für die schlussendlich gewählte Variante der Fall war. Singularity liegt auch bei diesem Test deutlich vorn. Die Ursache für diesen Geschwindigkeitsvorteil ist höchstwahrscheinlich in der Implementation des Schedulers zu suchen. Eine Erläuterung findet sich in den verwendeten Quellen nicht.

  • Message Ping/Pong

Hierbei handelt es sich um einen einfachen "Ping-Pong"-Test, bei dem eine Nachricht mit der Größe eines Bytes zwischen zwei Prozessen hin und her versandt wurde. Auf den beiden UNIX-Systemen kamen Sockets, im Falle von Windows eine Named Pipe und für Singularity Channels zum Einsatz. Obwohl bei einer solch geringen Größe, Singularitys Fähigkeit zur kopiefreien Übermittlung von Nachrichten über Channels gar nicht zum Tragen kommt, sind hier Ergebnisse zu beobachten, die um Faktor 4-9 unter denen der anderen Betriebssysteme liegen. Dies lässt sich unter anderem damit begründen, dass Sender und Empfänger im gleichen Adressraum liegen und die zur Auslieferung der Nachricht nötigen Systemrufe auf Singularity wiederum sehr effizient abgewickelt werden können.

  • Create Process

Bei der Erzeugung eines neuen Prozesses sticht vor allen Dingen das Windows-Ergebnis hervor, was aber angesichts der Tatsache, dass hier anders als im UNIX Prozessressourcen nicht vom Vaterprozess ererbt werden, nicht weiter verwundert. Die Ursache für das erneut gute Abschneiden von Singularity könnte neben dem günstigen Kostenfaktor Systemruf vor allem darin zu suchen sein, dass der Verwaltungsaufwand bei der Prozesserzeugung, bspw. durch die Verwendung einer systemweit einheitlichen Pagetabelle, wesentlich geringer ausfällt als bei der Konkurrenz.


Singularity ist also anscheinend durchaus in der Lage, sich zumindest bezüglich der Performance einfachster Basisoperationen mit etablierten Systemen zu messen. Es soll jedoch nicht verschwiegen werden, dass dies an anderer Stelle, z.B.: der Performance des Dateisystems noch nicht der Fall ist. Die Entwickler begründen dies damit, dass die in Singularity verwendeten Caching-Algorithmen längst noch nicht so fein an die Besonderheiten des Systems angepasst seien wie dies bei Produkten wie Linux oder Windows bereits geschehen konnte, welche sich schon seit Jahr und Tag auf dem Markt befinden (siehe dazu [3], [4]).

Quellen und Weblinks

  1. Homepage des Singularity Projekts
  2. Aiken, Manuel Fähndrich, Chris Hawblitzel Galen C. Hunt, and James R. Larus: Deconstructing Process Isolation, ACM SIGPLAN Workshop on Memory Systems Correctness and Performance (MSPC 2006) at ASPLOS 2006, San Jose, CA, October 2006.
  3. Galen C. Hunt, Mark Aiken, Paul Barham, Manuel Fähndrich, Chris Hawblitzel Orion Hodson, James R. Larus, Steven Levi, Nick Murphy, Bjarne Steensgaard, David Tarditi, Ted Wobber, and Brian D. Zill: Sealing OS Processes to Improve Dependability and Security, Microsoft Research Technical Report MSR-TR-2006-51, Microsoft Corporation, Redmond, WA, April 2006.
  4. Galen C. Hunt, James R. Larus, Martín Abadi, Mark Aiken, Paul Barham, Manuel Fähndrich, Chris Hawblitzel Orion Hodson, Steven Levi, Nick Murphy, Bjarne Steensgaard, David Tarditi, Ted Wobber, and Brian Zill: An Overview of the Singularity Project, Microsoft Research Technical Report MSR-TR-2005-135, Microsoft Corporation, Redmond, WA, October 2005.
  5. Manuel Fähndrich, Mark Aiken, Chris Hawblitzel, Orion Hodson, Galen C. Hunt, James R. Larus, and Steven Levi: Language Support for Fast and Reliable Message-based Communication in Singularity OS, Proceedings of EuroSys2006, Leuven, Belgium, April 2006. ACM SIGOPS.

  6. Mauerer, Wolfgang: Linux-Kernelarchitektur - Konzepte, Strukturen und Algorithmen von Kernel 2.6, Hanser 2004, ISBN: 3-446-22566-8.

  7. Folien zum Vortrag