Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
L4Mikrokernel der 2. Generation
Vortrag zum Seminar „Konzepte von Betriebssystemkomponenten“
Alexander Wü[email protected]
Friedrich-Alexander-Universität Erlangen-Nürnberg
24. Juli 2006
arw (FAU) L4 24. Juli 2006 1 / 26
Inhalt
1 EinführungL4
2 MikrokernelDefinitionSubsystemeNicht im Kernel
3 L4 und die Probleme der ersten GenerationOverhead durch KontextwechselSpeichereffektePortabilität
4 Schluss
arw (FAU) L4 24. Juli 2006 2 / 26
Einführung
Kapitelübersicht
1 EinführungL4
2 MikrokernelDefinitionSubsystemeNicht im Kernel
3 L4 und die Probleme der ersten GenerationOverhead durch KontextwechselSpeichereffektePortabilität
4 Schluss
arw (FAU) L4 24. Juli 2006 3 / 26
Einführung L4
Allgemeines zu L4
Mikrokernel der 2. Generation
soll vor allem die Performanceprobleme der ersten Generationbeseitigen
entworfen und implementiert von Jochen Liedtke
mehrere Implementierungen mit kompatibler API verfügbar
arw (FAU) L4 24. Juli 2006 4 / 26
Mikrokernel
Kapitelübersicht
1 EinführungL4
2 MikrokernelDefinitionSubsystemeNicht im Kernel
3 L4 und die Probleme der ersten GenerationOverhead durch KontextwechselSpeichereffektePortabilität
4 Schluss
arw (FAU) L4 24. Juli 2006 5 / 26
Mikrokernel Definition
Was ist ein Mikrokernel?
Definition
Ein Mikrokernel ist ein Kernel, der nur aus solchen Subsystemenbesteht, die für die gewünschten Funktionen unbedingt Teil desKernels sein müssen.
arw (FAU) L4 24. Juli 2006 6 / 26
Mikrokernel Definition
Anforderungen
Interaktivität: Mehrere Benutzerprozesse, Interrupts
Unabhaengigkeit: Subsysteme können unabhängig voneinanderGarantien einhalten.
Integrität: Ein Subsystem kann sich auf die Garantien einesanderen verlassen; zwei Subsysteme müssen sicherkommunizieren können.
Die Hardware benutzt seitenbasierte Speicherverwaltung.
Der Kernel stellt dieselben Abstraktionen auf allen Architekturenzur Verfügung.
arw (FAU) L4 24. Juli 2006 7 / 26
Mikrokernel Subsysteme
Adressraumverwaltung
Ist Teil des Kernels weil...
... Trennung der Speicherbereiche sonst nicht implementiert werdenkönnte.
... Adressraumverwaltung privilegierte Operationen erfordert.
besteht aus 3 grundlegenden Operationen, grant , mapundflush
eventuell auch Zugriffsrechte (read/write)
Auslagerung („paging“) und Speicherverwaltung sind ausserhalbdes Kernels implementiert.
E/A-Ports und „memory mapped I/O“ können ebenfalls ausserhalbdes Kernels behandelt werden.
arw (FAU) L4 24. Juli 2006 8 / 26
Mikrokernel Subsysteme
Threads
Threads sind Aktivitäten, die innerhalb eines Adressraumesausgeführt werden.Sie werden charakterisiert durch:
Registerinhalte (vor allem IP und SP)Speicherbereich
Im Kernel weil...
... gewünschte Trennung der Speicherbereiche sonst nicht realisiertwerden kann. Jede Änderung im Speicherbereich eines Threads mussvom Kernel kontrolliert werden können.
arw (FAU) L4 24. Juli 2006 9 / 26
Mikrokernel Subsysteme
IPC
Im Kernel weil...
... bei der Kommunikation zwischen Threads Adressgrenzenüberschreitend Daten ausgetauscht werden müssen.
klassisch durch Austausch von Nachrichten
andere Verfahren wie Prozeduraufrufe können durchNachrichtenaustausch nachgebildet werden.
Interrupts werden auf Nachrichten abgebildet.
arw (FAU) L4 24. Juli 2006 10 / 26
Mikrokernel Subsysteme
„unique identifier“
Threads müssen Kommunikationspartner kennen
entweder Threads oder Kommunikationskanäle muessen UIDshaben
Im Kernel weil...
... nur der Kernel Integrität sicherstellen kann
arw (FAU) L4 24. Juli 2006 11 / 26
Mikrokernel Nicht im Kernel
Nicht im Kernel
Speichermanagment: Server ausserhalb des Kernels verteiltSpeicher.
Auslagerungs-Server
Gerätetreiber: Hardwarezugriffe über ge-map-ten Speicher undInterrupt-Nachrichten.
Kommunikation über Rechnergrenzen: Protokolle können überIPC benutzt werden und ihrerseits Gerätetreiber nutzen.
UNIX-Server: Systemaufrufe können emuliert werden.
arw (FAU) L4 24. Juli 2006 12 / 26
L4 und die Probleme der ersten Generation
Kapitelübersicht
1 EinführungL4
2 MikrokernelDefinitionSubsystemeNicht im Kernel
3 L4 und die Probleme der ersten GenerationOverhead durch KontextwechselSpeichereffektePortabilität
4 Schluss
arw (FAU) L4 24. Juli 2006 13 / 26
L4 und die Probleme der ersten Generation Overhead durch Kontextwechsel
Kontextwechsel
„widely believed“: Adressraumwechsel und Threadwechsel sindprinzipiell teuer.
Wird scheinbar durch Messungen bestätigt.Wechsel zerlegbar in 2 Vorgänge:
Wechsel zwischen Kernel und UserAdressraumwechsel
arw (FAU) L4 24. Juli 2006 14 / 26
L4 und die Probleme der ersten Generation Overhead durch Kontextwechsel
Kernel-User-Wechsel
Wie funktionierts?
Stack wechseln
in privilegierten Modus des Prozessors wechseln
eigentlich nur ein spezieller Funktionsaufruf
Was kostets?
Messung per getpid auf einem 50 MHz486er
Mach: 18 µs=̂900 Takte, davon 800 Takteoverhead
L31: maximal bis 180 Takte, minimal 123, davon 15 bzw. 57overhead
Ursache: Andere Implementierung
1Vorgänger zu L4arw (FAU) L4 24. Juli 2006 15 / 26
L4 und die Probleme der ersten Generation Overhead durch Kontextwechsel
kurzer Ausflug: TLB
Definition
Der Translation Lookaside Buffer (TLB) ist ein Bestandteil der MMU,der die Zuordnung von logischen zu physikalischen Adressen cached.Ein tagged TLB speichert zusaetzlich zu jedem Paar aus logischer undphysikalischer Adresse eine ID fuer den Adressraum.
Bei einem untagged TLB wird der Inhalt des TLB bei einemAdressraumwechsel ungültig („TLB flush“).
Wird bei einem Speicherzugriff die Adresse nicht im TLB gefunden(„TLB miss“), muss in der Seitentabelle nachgesehen werden.
Die Kosten dafuer sind hoch.
Die Kosten fallen je nach „working set“ eines Threads mehrmalsan.
arw (FAU) L4 24. Juli 2006 16 / 26
L4 und die Probleme der ersten Generation Overhead durch Kontextwechsel
Adressraumwechsel
Kosten und Verfahren sehr stark architekturabhängig
Kosten ergeben sich aus Wechsel der Segment- oderSeitentabelle und TLB flush
bei tagged-TLB-Architekturen sehr billig weil TLB flush wegfällt
bei Architekturen ohne tagged TLB im schlimmsten Fall einigehundert Takte overhead
durch geschickte Wahl des Verfahrens sind die Kosten aberminimierbar
arw (FAU) L4 24. Juli 2006 17 / 26
L4 und die Probleme der ersten Generation Overhead durch Kontextwechsel
Threadwechsel
im Beispiel RPC, bei dem1 byte verschickt wird
Kosten setzen sich ausAdressraumwechsel,system call,Parameterübergabe undStackwechsel zusammen
schnell genug um auchInterrupts zu bearbeiten
Messwerte
arw (FAU) L4 24. Juli 2006 18 / 26
L4 und die Probleme der ersten Generation Speichereffekte
Speichereffekte
memory cycle overheadper instruction (MCPI)
bei Mach laut Messungenbis zu 0.25 Takte proProzessorbefehl
Ursache sind gegenseitigeVerdrängungen aus demCache zwischen Kernelund Anwendungen
als Lösung wird eineVerkleinerung des „cacheworking set“ angegeben
Messwerte
arw (FAU) L4 24. Juli 2006 19 / 26
L4 und die Probleme der ersten Generation Portabilität
Portabilität von Mikrokerneln
Probleme
früher: Mikrokernel hatten eine Abstraktion für die Hardware
Abstraktion erzeugt overhead und verhindert spezielleOptimierungen
speziell Adressraumwechsel sollten für die Architektur optimiertsein
selbst zwischen 486 und Pentium bestehen signifikanteUnterschiede
arw (FAU) L4 24. Juli 2006 20 / 26
L4 und die Probleme der ersten Generation Portabilität
Portabilität von Mikrokerneln
Auswirkungen
anderer Prozessor bedingt anderes Design
Mikrokernel sind nicht portabel
aber ein prozessorspezifischer Mikrokernel kann Basis fuer einportables Betriebssystem sein
arw (FAU) L4 24. Juli 2006 21 / 26
Schluss
Kapitelübersicht
1 EinführungL4
2 MikrokernelDefinitionSubsystemeNicht im Kernel
3 L4 und die Probleme der ersten GenerationOverhead durch KontextwechselSpeichereffektePortabilität
4 Schluss
arw (FAU) L4 24. Juli 2006 22 / 26
Schluss
andere Ansätze
andere Ansätze
Synthesis: „Compiler“ im Kernel integriert, der bei Systemaufrufenzur Laufzeit optimierten Code für diesen speziellen Systemaufrufmit diesen speziellen Parametern generiert
Spin: Erweiterung dazu, ermöglicht vom Benutzer geschriebenezur Laufzeit übersetzte Systemaufrufe
Exokernel: auf die R2000-Architektur zugeschnitten, stellt aberkeine Abstraktion bereit sondern nur architekturabhängigeBausteine („primitives“)
arw (FAU) L4 24. Juli 2006 23 / 26
Schluss
Zusammenfassung
Zusammenfassung
Mikrokernel bieten nur einen minimalen Satz an Abstraktionen
Für unsere angegebenen Anforderungen: Adressräume, Threads,IPC, UIDs
Das Design muss genau auf die Eigenheiten der Architekturrücksicht nehmen
arw (FAU) L4 24. Juli 2006 24 / 26
Schluss
aus der Presse
auf slashdot.org
arw (FAU) L4 24. Juli 2006 25 / 26
Schluss
Quellen
J. LiedtkeOn µ-Kernel Construction.ACM Operating Systems Review, Dezember 1995, Proceedings ofthe 15th ACM Symposium on Operating Systems Principles(SOSP ’95).
H. Hartig et. al.The Performance of µ-Kernel-Based Systems.ACM Operating Systems Review, Dezember 1996, Proceedings ofthe 16th ACM Symposium on Operating Systems Principles(SOSP ’96).
arw (FAU) L4 24. Juli 2006 26 / 26
L4L4Linux, DROPS und Benchmarks
Vortrag zum Seminar „Konzepte von Betriebssystemkomponenten“
Alexander Wü[email protected]
Friedrich-Alexander-Universität Erlangen-Nürnberg
24. Juli 2006
arw (FAU) L4 24. Juli 2006 1 / 17
Inhalt
1 L4LinuxAllgemeinesImplementierung
2 DROPS
3 Benchmarks
4 Schluss
arw (FAU) L4 24. Juli 2006 2 / 17
L4Linux
Kapitelübersicht
1 L4LinuxAllgemeinesImplementierung
2 DROPS
3 Benchmarks
4 Schluss
arw (FAU) L4 24. Juli 2006 3 / 17
L4Linux Allgemeines
Allgemeines zu L4Linux
Modifiziertes Linux als Prozess in L4
Paravirtualisierung: Hardwarezugriff über modifizierte Treiber, dieMechanismen des Wirtssystems nutzen
Entwickelt für die Benutzung in „DROPS“
arw (FAU) L4 24. Juli 2006 4 / 17
L4Linux Implementierung
Implementierung von L4Linux
Änderungen an Linux nur im architekturabhängigen TeilInterrupthandlerSpeicherverwaltung
L4 unverändert
Linux-Gerätetreiber unverändert
Linux-Benutzerprozesse sind einzelne L4-Prozesse
Syscalls werden auf L4-IPC abgebildet
Scheduling durch L4
Binärkompatibel zu x86 Linux
arw (FAU) L4 24. Juli 2006 5 / 17
DROPS
Kapitelübersicht
1 L4LinuxAllgemeinesImplementierung
2 DROPS
3 Benchmarks
4 Schluss
arw (FAU) L4 24. Juli 2006 6 / 17
DROPS
DROPS
Echtzeitsystem zusammen mitbenutzerinteraktivem„time-sharing“ L4Linux
Aufbauend auf L4 und L4Linux
Managment vonSystemresourcen
Akronym
DresdenReal-timeOperatingSystem Project
arw (FAU) L4 24. Juli 2006 7 / 17
DROPS
DROPS
arw (FAU) L4 24. Juli 2006 8 / 17
DROPS
Implementierung von DROPS
Resourcentrennung für CPU, Speicher, Netzwerk, SCSI, Cacheuvm.
Resourcentrennung erfordert Gerätetreiber in L4
Treiber in Linux durch Stubs ersetzt
Managmentprozess in L4 erhält beim Booten alle Resourcen
Dieser delegiert an Echtzeitprozesse und L4Linux
gezähmtes („tamed“) L4Linux
arw (FAU) L4 24. Juli 2006 9 / 17
Benchmarks
Kapitelübersicht
1 L4LinuxAllgemeinesImplementierung
2 DROPS
3 Benchmarks
4 Schluss
arw (FAU) L4 24. Juli 2006 10 / 17
Benchmarks
Benchmarks
arw (FAU) L4 24. Juli 2006 11 / 17
Benchmarks
Benchmarks
arw (FAU) L4 24. Juli 2006 12 / 17
Benchmarks
Benchmarks
arw (FAU) L4 24. Juli 2006 13 / 17
Schluss
Kapitelübersicht
1 L4LinuxAllgemeinesImplementierung
2 DROPS
3 Benchmarks
4 Schluss
arw (FAU) L4 24. Juli 2006 14 / 17
Schluss
Zusammenfassung
L4 deutlich schneller als Mach
L4Linuxmit etwa 5 % Einbußen gegenüber nativem Linux
Aber bei speziellen Operationen oft nur halb so schnell
Echtzeitsystem koexistiert mit L4Linux
arw (FAU) L4 24. Juli 2006 15 / 17
Schluss
Quellen
J. LiedtkeOn µ-Kernel Construction.ACM Operating Systems Review, Dezember 1995, Proceedings ofthe 15th ACM Symposium on Operating Systems Principles(SOSP ’95).
H. Härtig et. al.The Performance of µ-Kernel-Based Systems.ACM Operating Systems Review, Dezember 1996, Proceedings ofthe 16th ACM Symposium on Operating Systems Principles(SOSP ’96).
arw (FAU) L4 24. Juli 2006 16 / 17
Schluss
Quellen
H. Härtig, M. Hohmuth, J. WolterTaming Linux.Proceedings of PART ’98: The 5th Australasian Conference onParallel and Real-Time Systems, September 1998, Springer.
div. Autorenhttp://os.inf.tu-dresden.de/
arw (FAU) L4 24. Juli 2006 17 / 17