Microkernel: Exokernel und L4 - Revision history

Allner: /* L4 */

2007-04-18T19:46:54Z

← Older revision		Revision as of 19:46, 18 April 2007
Line 151:		Line 151:
	Desweiteren muss der Kernel einen Interrupt in den Userspace weiterleiten, um dem Treiber das Behandeln des Interrupts zu ermöglichen. Dies wird erreicht, indem der Kernel Interrupts in IPC Nachrichten umwandelt und an einen assozierten Thread sendet. Der Kernel muss nichts über die Bedeutung des Interrupts wissen. Er weist jeder Hardware eine spezielle Thread-Id zu und sendet für einen Interrupt eine leere Nachricht mit dieser Id.		Desweiteren muss der Kernel einen Interrupt in den Userspace weiterleiten, um dem Treiber das Behandeln des Interrupts zu ermöglichen. Dies wird erreicht, indem der Kernel Interrupts in IPC Nachrichten umwandelt und an einen assozierten Thread sendet. Der Kernel muss nichts über die Bedeutung des Interrupts wissen. Er weist jeder Hardware eine spezielle Thread-Id zu und sendet für einen Interrupt eine leere Nachricht mit dieser Id.
	Ein Treiber assoziert sich mit dem ipc-Aufruf ASSOCIATE INTR für eine Interrupt und kann diesen nanach mittels des ipc-Aufrufs RECEIVE INTR empfangen.		Ein Treiber assoziert sich mit dem ipc-Aufruf ASSOCIATE INTR für eine Interrupt und kann diesen nanach mittels des ipc-Aufrufs RECEIVE INTR empfangen.

			=== Schlussbemerkung ===
			Der '''L4''' setzt im Gegensatz zum Exokernel eine zum Teil höhere Abstraktionseben ein. Zum Beispiel gibt es im Exokernel nur Systemaufrufe, die man für die Impementierung allgemeinerer IPC-Aufrufe nutzen kann. Es gibt eine feste API für die Implementation des '''L4''' Kernels, sowie die genannten Konzepte. Die eigentlich Implementierung des Kernel muss auf die verwendete Architektur optimiert werden, vor allem um eine performante Interprozesskommunikation zu erreichen. Dies ist aber nur der kleine Kernel, die im Userspace implementierten Server/Applikationen können, da sie die feste API verwenden, leicht portiert werden.

	== Quellen ==		== Quellen ==

Allner: /* Beispiele für die Verwendung/Umsetzung */

2007-04-18T19:33:10Z

Beispiele für die Verwendung/Umsetzung

← Older revision		Revision as of 19:33, 18 April 2007
Line 141:		Line 141:

	=== Beispiele für die Verwendung/Umsetzung ===		=== Beispiele für die Verwendung/Umsetzung ===
			==== Gerätetreiber ====
			Zur Implementierung von Gerätetreibern im Userspace ist zum einen der I/O Zugriff (Steuern/Übertragen von Daten) auf das Gerät und das Empfangen von Interupts von dem Gerät nötig. Hierzu werden die bekannten Abstraktionen Adressraum und IPC verwendet um dies für im Userspace verfügbar zu machen.

			'''I/O'''
			Zugriff auf den I/O-Bereich eines Gerätes wird dadurch erreicht, daß dieser in den Addressraum eines Thread eingeblendet wird. Dies funktioniert offensichtlich mit Memory-Mapped I/O, aber auch mit I/O Ports. Dies hängt von der gegebenen Hardware ab. Die x86 Architektur erlaubt den Zugriff auf Ports über eine kleine Speicherseite, diese kann aber nicht in den Hauptspeicher gemappt werden. Daher werden diese in einem seperaten Adressraum verwaltet. Dieser ist 64kb groß und jeder physische Port x muss in diesem Adressraum bzw. dem I/O Adressraumes an die gleiche Adresse x gemappt werden.
			Ein Treiber kann somit Zugriff auf die I/O Geräte erhalten, indem er den entsprechenden Bereich von einen Speichermanager erhält und diesen dann entsprechend verwendet. Der Speicher z.B. eines Graphikgerätes könnte in den Adressraum des Treibers gemappt und verwendet werden, während dieser das Gerät über den in den Adressraum „gemappten“ I/O port steuert. DMA ist analog möglich.

			'''Interrupts'''
			Desweiteren muss der Kernel einen Interrupt in den Userspace weiterleiten, um dem Treiber das Behandeln des Interrupts zu ermöglichen. Dies wird erreicht, indem der Kernel Interrupts in IPC Nachrichten umwandelt und an einen assozierten Thread sendet. Der Kernel muss nichts über die Bedeutung des Interrupts wissen. Er weist jeder Hardware eine spezielle Thread-Id zu und sendet für einen Interrupt eine leere Nachricht mit dieser Id.
			Ein Treiber assoziert sich mit dem ipc-Aufruf ASSOCIATE INTR für eine Interrupt und kann diesen nanach mittels des ipc-Aufrufs RECEIVE INTR empfangen.

	== Quellen ==		== Quellen ==

Allner: /* Interprozesskommunikation */

2007-04-18T18:35:29Z

Interprozesskommunikation

← Older revision		Revision as of 18:35, 18 April 2007
Line 137:		Line 137:

	Da die Performance eines µ-Kernels stark von der IPC abhängt, ist diese im '''L4''' stark für eine Architektur optimiert. Desweiteren verwendet er 3 Konzepte zur Optimierung: ''Passing Short Messages'', ''Copying Large Data Messages'', ''Lazy Scheduling''. Bei Interesse empfiehlt sich ein Blick in das Paper. Dort wird die IPC des '''L4''' mit anderen µ-Kernel verglichen und gezeigt, daß diese performant implementiert werden kann. Die schlechte Performance früherer µ-Kernel in diesem Bereich, war einer der Hauptgründe, weswegen diese wieder unpopulärer wurden.		Da die Performance eines µ-Kernels stark von der IPC abhängt, ist diese im '''L4''' stark für eine Architektur optimiert. Desweiteren verwendet er 3 Konzepte zur Optimierung: ''Passing Short Messages'', ''Copying Large Data Messages'', ''Lazy Scheduling''. Bei Interesse empfiehlt sich ein Blick in das Paper. Dort wird die IPC des '''L4''' mit anderen µ-Kernel verglichen und gezeigt, daß diese performant implementiert werden kann. Die schlechte Performance früherer µ-Kernel in diesem Bereich, war einer der Hauptgründe, weswegen diese wieder unpopulärer wurden.

			Desweiteren enthält der µ-Kernel ein Konzept zur Überwachung der IPC (''Clans''). Dies ist nicht zwingend nötig, wird von Entwicklern aber so begründet, daß dies die Performance des Kernels, speziell der IPC, nicht stark beeinträchtigt und im Userspace nur mit größeren Performanceeinbußen möglich wäre.

	=== Beispiele für die Verwendung/Umsetzung ===		=== Beispiele für die Verwendung/Umsetzung ===

Allner: /* Interprozesskommunikation */

2007-04-18T18:32:40Z

Interprozesskommunikation

← Older revision		Revision as of 18:32, 18 April 2007
Line 130:		Line 130:

	==== Interprozesskommunikation ====		==== Interprozesskommunikation ====
			Um Kommunikation zwischen den Threads zu ermöglichen, muss der Kern konsequenterweise auch IPC unterstützen. Der Kern kann so ipc-Aufrufe überprüfen und gegebenenfalls umleiten. Desweiteren wird diese auch, wie schon erwähnt, für die die grant und map Operationen benötigt, wobei wie schon beschrieben, das Einbinden des Speichers in den Adressraum des Empfängers der Kern übernimmt, er also die Nachricht selbst interpretiert.

			Die IPC überträgt Nachrichten synchron und ungepuffert zwischen 2 Threads. Dafür muss Einverständnis zwischen Sender und Empfänger geben. Eine Nachricht können beliebige Daten sein oder der Verweis auf beliebige Speicherseiten für ''map'' und ''grant''.

			Implementiert ist dies so, daß es IPC-Aufrufe jeweils für das Senden und Empfangen gibt (sowie für senden&empfangen (rpc) bzw. empfangen und senden). Der Sender blockiert bis seine Nachricht angenommen wurde (oder Timeout) und der Empfänger wartet bis er eine Nachricht eines bestimmten Senders erhält (oder Timeout).

			Da die Performance eines µ-Kernels stark von der IPC abhängt, ist diese im '''L4''' stark für eine Architektur optimiert. Desweiteren verwendet er 3 Konzepte zur Optimierung: ''Passing Short Messages'', ''Copying Large Data Messages'', ''Lazy Scheduling''. Bei Interesse empfiehlt sich ein Blick in das Paper. Dort wird die IPC des '''L4''' mit anderen µ-Kernel verglichen und gezeigt, daß diese performant implementiert werden kann. Die schlechte Performance früherer µ-Kernel in diesem Bereich, war einer der Hauptgründe, weswegen diese wieder unpopulärer wurden.

	=== Beispiele für die Verwendung/Umsetzung ===		=== Beispiele für die Verwendung/Umsetzung ===

Allner: /* L4 */

2007-04-18T18:23:19Z

← Older revision		Revision as of 18:23, 18 April 2007
Line 103:		Line 103:

	Im folgenden wird kurz auf jedes Modell eingegangen, wie es der '''L4''' benutzt.		Im folgenden wird kurz auf jedes Modell eingegangen, wie es der '''L4''' benutzt.
			=== Prinzipien ===

	=== Speicherabstraktion ===		==== Speicherabstraktion ====
	Der '''L4''' Kern stellt kein Speichermanagement bereit, wie dies monolithische Kernel oder frühere µ-Kernel tun. Im L4 gibt es nur eine einfache Abstraktion des Hardware Konzepts eines Adressraumes. Mit diesem ermöglicht dieser den geschützten Zugriff auf den Speicher aber auch das gemeinsame Nutzen von Speicher zwischen Threads. Der Kern kennt nur ein grundlegendes Adressraumkonzept und erlaubt die Implementierung der Speicherverwaltung einem Server im Usermode.		Der '''L4''' Kern stellt kein Speichermanagement bereit, wie dies monolithische Kernel oder frühere µ-Kernel tun. Im L4 gibt es nur eine einfache Abstraktion des Hardware Konzepts eines Adressraumes. Mit diesem ermöglicht dieser den geschützten Zugriff auf den Speicher aber auch das gemeinsame Nutzen von Speicher zwischen Threads. Der Kern kennt nur ein grundlegendes Adressraumkonzept und erlaubt die Implementierung der Speicherverwaltung einem Server im Usermode.

Allner: /* L4 */

2007-04-18T18:22:44Z

← Older revision		Revision as of 18:22, 18 April 2007
Line 120:		Line 120:
	Um Speicher anzufordern, fragt ein Thread einen Speichermanager an, der diesem dann den entsprechenden Speicher, so dies möglich ist, in dessen Adressraum einfügt. Zur Kommunikation mit dem initialen Speichermanager gibt es ein <math>\sigma_0</math>-Protokoll.		Um Speicher anzufordern, fragt ein Thread einen Speichermanager an, der diesem dann den entsprechenden Speicher, so dies möglich ist, in dessen Adressraum einfügt. Zur Kommunikation mit dem initialen Speichermanager gibt es ein <math>\sigma_0</math>-Protokoll.

	=== Threads und Scheduler ===		==== Threads und Scheduler ====
	Der Kern kennt Threads als Abstraktion für eine Ausführungseinheit. Ein Task sind mehrere Threads mit dem gleichen Adressraum. Dies unterscheidet sich nicht wesentlich von gängigen Kerneln, lediglich die Implementierung ist stark optimiert (Arrays statt Listen, etc) und die Systembefehle zur Erstellung/Stoppen/Manipulieren der Threads unterscheidet sich etwas, ebenso wie die Threads ausgeführt werden (Scheduler).		Der Kern kennt Threads als Abstraktion für eine Ausführungseinheit. Ein Task sind mehrere Threads mit dem gleichen Adressraum. Dies unterscheidet sich nicht wesentlich von gängigen Kerneln, lediglich die Implementierung ist stark optimiert (Arrays statt Listen, etc) und die Systembefehle zur Erstellung/Stoppen/Manipulieren der Threads unterscheidet sich etwas, ebenso wie die Threads ausgeführt werden (Scheduler).
	Die Motiviation Threads im Kernel zu haben ist vorrangig die, daß jeder Thread einen Adressraumes besitzt, und Änderungen an diesem vom Kern kontrolliert werden müssen.		Die Motiviation Threads im Kernel zu haben ist vorrangig die, daß jeder Thread einen Adressraumes besitzt, und Änderungen an diesem vom Kern kontrolliert werden müssen.
Line 128:		Line 128:
	Wie der Scheduler im Kernel genau implementiert ist, wird vom L4 nicht genau definiert, um mögliche Optimierungen zuzulassen. Er muss das Vergeben von Prioritäten und Zeitscheiben an Threads zulassen.		Wie der Scheduler im Kernel genau implementiert ist, wird vom L4 nicht genau definiert, um mögliche Optimierungen zuzulassen. Er muss das Vergeben von Prioritäten und Zeitscheiben an Threads zulassen.

	=== Interprozesskommunikation ===		==== Interprozesskommunikation ====

	=== Beispiele für die Verwendung ===		=== Beispiele für die Verwendung/Umsetzung ===

	== Quellen ==		== Quellen ==

Allner: /* Quellen */

2007-04-18T18:20:09Z

Quellen

← Older revision		Revision as of 18:20, 18 April 2007
Line 137:		Line 137:
	– Dawson R. Engler, M. Frans Kaashoek, and James O’Toole Jr. - [http://sar.informatik.hu-berlin.de/teaching/2006-w%20Advanced%20Operating%20System%20Principles%20(Seminar)/papers/exokernel.pdf]		– Dawson R. Engler, M. Frans Kaashoek, and James O’Toole Jr. - [http://sar.informatik.hu-berlin.de/teaching/2006-w%20Advanced%20Operating%20System%20Principles%20(Seminar)/papers/exokernel.pdf]
	* Exodisk: maximizing application control over storage management – Robert Grimm [http://citeseer.ist.psu.edu/grimm96exodisk.html]		* Exodisk: maximizing application control over storage management – Robert Grimm [http://citeseer.ist.psu.edu/grimm96exodisk.html]
			* L4: Liedtke, J. "On µ-Kernel Construction." In Proceedings of the Fifteenth ACM Symposium on Operating System Principles (Copper Mountain Resort, CO. Dec. 3-6). ACM Press, New York, NY, 1995, pp. 237-250.
			* L4: L4 Reference Manual 486, Pentium, Pentium Pro (1996) Version 2.0, Jochen Liedtke
			* L4 Gerätetreiber Beispiel: [http://i30www.ira.uka.de/teaching/coursedocuments/117/week12-sdi1.pdf]

Allner: /* Threads und Scheduler */

2007-04-18T18:10:18Z

Threads und Scheduler

← Older revision		Revision as of 18:10, 18 April 2007
Line 122:		Line 122:
	=== Threads und Scheduler ===		=== Threads und Scheduler ===
	Der Kern kennt Threads als Abstraktion für eine Ausführungseinheit. Ein Task sind mehrere Threads mit dem gleichen Adressraum. Dies unterscheidet sich nicht wesentlich von gängigen Kerneln, lediglich die Implementierung ist stark optimiert (Arrays statt Listen, etc) und die Systembefehle zur Erstellung/Stoppen/Manipulieren der Threads unterscheidet sich etwas, ebenso wie die Threads ausgeführt werden (Scheduler).		Der Kern kennt Threads als Abstraktion für eine Ausführungseinheit. Ein Task sind mehrere Threads mit dem gleichen Adressraum. Dies unterscheidet sich nicht wesentlich von gängigen Kerneln, lediglich die Implementierung ist stark optimiert (Arrays statt Listen, etc) und die Systembefehle zur Erstellung/Stoppen/Manipulieren der Threads unterscheidet sich etwas, ebenso wie die Threads ausgeführt werden (Scheduler).
	Die Motiviation Threads im Kernel zu haben ist vorrangig die, daß jeder Thread einen Adressraumes besitzt, und Änderungen an ~~diesemvom~~ Kern kontrolliert werden müssen.		Die Motiviation Threads im Kernel zu haben ist vorrangig die, daß jeder Thread einen Adressraumes besitzt, und Änderungen an diesem vom Kern kontrolliert werden müssen.

	Der ''L4 ''besitzt einen prioritätsbasierten, preemptiven Scheduler, der vom Userspace aus manipulierbar ist (thread_schedule). Desweiteren gibt es die Möglichkeit für Threads ihre aktuelle Zeitscheibe (thread_switch) an einen anderen Thread abzugeben, was auch zur implementation eines Userspace Schedulers verwendet werden kann. Bei ipc-Aufrufen wir implizit ein thread_switch ausgeführt.		Der '''L4''' besitzt einen prioritätsbasierten, preemptiven Scheduler, der vom Userspace aus manipulierbar ist (thread_schedule). Desweiteren gibt es die Möglichkeit für Threads ihre aktuelle Zeitscheibe (thread_switch) an einen anderen Thread abzugeben, was auch zur implementation eines Userspace Schedulers verwendet werden kann. Bei ipc-Aufrufen wir implizit ein thread_switch ausgeführt.

	Wie der Scheduler im Kernel genau implementiert ist, wird vom L4 nicht genau definiert, um mögliche Optimierungen zuzulassen. Er muss das Vergeben von Prioritäten und Zeitscheiben an Threads zulassen.		Wie der Scheduler im Kernel genau implementiert ist, wird vom L4 nicht genau definiert, um mögliche Optimierungen zuzulassen. Er muss das Vergeben von Prioritäten und Zeitscheiben an Threads zulassen.

Allner: /* Threads und Scheduler */

2007-04-18T18:08:43Z

Threads und Scheduler

← Older revision		Revision as of 18:08, 18 April 2007
Line 121:		Line 121:

	=== Threads und Scheduler ===		=== Threads und Scheduler ===
			Der Kern kennt Threads als Abstraktion für eine Ausführungseinheit. Ein Task sind mehrere Threads mit dem gleichen Adressraum. Dies unterscheidet sich nicht wesentlich von gängigen Kerneln, lediglich die Implementierung ist stark optimiert (Arrays statt Listen, etc) und die Systembefehle zur Erstellung/Stoppen/Manipulieren der Threads unterscheidet sich etwas, ebenso wie die Threads ausgeführt werden (Scheduler).
			Die Motiviation Threads im Kernel zu haben ist vorrangig die, daß jeder Thread einen Adressraumes besitzt, und Änderungen an diesemvom Kern kontrolliert werden müssen.

			Der ''L4 ''besitzt einen prioritätsbasierten, preemptiven Scheduler, der vom Userspace aus manipulierbar ist (thread_schedule). Desweiteren gibt es die Möglichkeit für Threads ihre aktuelle Zeitscheibe (thread_switch) an einen anderen Thread abzugeben, was auch zur implementation eines Userspace Schedulers verwendet werden kann. Bei ipc-Aufrufen wir implizit ein thread_switch ausgeführt.

			Wie der Scheduler im Kernel genau implementiert ist, wird vom L4 nicht genau definiert, um mögliche Optimierungen zuzulassen. Er muss das Vergeben von Prioritäten und Zeitscheiben an Threads zulassen.

	=== Interprozesskommunikation ===		=== Interprozesskommunikation ===

Allner: /* Speicherabstraktion */

2007-04-18T17:59:00Z

Speicherabstraktion

← Older revision		Revision as of 17:59, 18 April 2007
Line 105:		Line 105:

	=== Speicherabstraktion ===		=== Speicherabstraktion ===
			Der '''L4''' Kern stellt kein Speichermanagement bereit, wie dies monolithische Kernel oder frühere µ-Kernel tun. Im L4 gibt es nur eine einfache Abstraktion des Hardware Konzepts eines Adressraumes. Mit diesem ermöglicht dieser den geschützten Zugriff auf den Speicher aber auch das gemeinsame Nutzen von Speicher zwischen Threads. Der Kern kennt nur ein grundlegendes Adressraumkonzept und erlaubt die Implementierung der Speicherverwaltung einem Server im Usermode.

			Dazu benutzt der Kern das Konzept eines rekursiv Aufbaus des Adressraumes außerhalb des Kernels. Beim Systemstart gibt es einen initialen Adressraumes, der den gesamten physikalischen Speicher umfasst und von einem initialen Speichermanager im Userspace verwaltet wird. Um andere Adressräume aufzubauen sind drei Operationen implementiert.

			;Map: Erlaubt dem Besitzer eines Adressraumes Seiten aus dem eigenen in einen anderen Adressraum einzublenden, falls der Empfänger einverstanden ist. Auf die Seiten sind danach in beiden Adressräumen zugreifbar.

			;Flush: Erlaubt dem Besitzer eines Adressraumes Seiten die er in seinem Adressraum besitzt und zuvor mit an andere direkt oder indirekt vergeben hat, aus den anderen Adressräumen zu entfernen.

			;Grant: Erlaubt dem Besitzer eines Adressraumes Seiten aus dem eigenen in einen anderen Adressraum zu verschieben, falls der Empfänger einverstanden ist. Die Seite ist danach nicht mehr im Adressraum des ursprünglichen Besitzers vorhanden.
			Mit diesen 3 Operationen ist es möglich Speichermanagement und Paging außerhalb des Kernels zu implementieren. Dafür sind prinzipiell nur die beiden Befehle map und flush notwendig.

			Die Befehle grant und map benötigen IPC, da sie auf das Einverständnis des Empfängers angewiesen sind. Der zugehörige ipc-Aufruf ist zwar an dem Empfänger adressiert, daß eigentlich einblenden in den Adressraum des Threads übernimmt aber natürlich der Kernel. Der flush Befehl ist als eigenständiger Systemaufruf implementiert.

			Um Speicher anzufordern, fragt ein Thread einen Speichermanager an, der diesem dann den entsprechenden Speicher, so dies möglich ist, in dessen Adressraum einfügt. Zur Kommunikation mit dem initialen Speichermanager gibt es ein <math>\sigma_0</math>-Protokoll.

	=== Threads und Scheduler ===		=== Threads und Scheduler ===