4 Implementation

Der im Kapitel [hier] entworfene Linux-Server für den Mikrokern L4 wurde in einer ersten Version vollständig implementiert und im Internet unter der URL ftp://ftp.inf.tu-dresden.de/pub/os/L4/devel/ bereitgestellt. Der Server implementiert vollständig die Funktionalität eines Linux-Systems(1); wir hatten jedoch bisher wenig Gelegenheit, die Leistung des Servers genauer zu messen oder zu optimieren.

Die Anpassung an den L4-Mikrokern beläuft sich derzeit auf etwa 12000 Zeilen C-Quelltext (inklusive der von Linux/i386 übernommenen Teile, aber ohne bestimmte Header-Dateien, die von Linux/i386 mitbenutzt werden; zum Vergleich: die i386-Anpassung ist (ohne FPU-Emulation) etwa 18000 Zeilen groß; der Linux-Kern (ohne Architekturanpassung und Treiber) ist 167000 Zeilen groß, die mitgelieferten Treiber insgesamt 343600 Zeilen). Sie wurde in etwa viermonatiger Arbeit von vier Projekt-Beteiligten erstellt.

In diesem Kapitel gehen wir auf einzelne Aspekte der Implementation ein.

4.1 Maschinenabhängige Linux-Subsysteme

Maschinenabhängige Teile des Linux-Kerns, die vom L4-Kern nicht eingeschränkte Hardware-Schnittstellen benutzen oder beschreiben, konnten nahezu unverändert von Linux/i386 übernommen werden. Dies betrifft insbesondere folgenden Subsysteme:


Fußnoten:
  1. Für zwei Besonderheiten der Linux/i386-Implementation wurde keine Unterstützung implementiert: Virtual-8086-Modus und ladbare Kernmodule für Linux/i386

4.2 Interrupts

Die Interruptverwaltung wurde wie im Abschnitt [hier] besprochen implementiert: Beim Systemstart wird der Bottom-Half-Thread und Threads für jeden Interrupt gestartet, wobei letztere sofort versuchen, sich mit dem entsprechenden L4-IPC-Mechanismus an die Interrupt-Quellen anzuschließen [15].

Eine Besonderheit stellt lediglich der Uhreninterrupt dar, der alle 10 ms auftreten muß: Die Interruptquellen, die normalerweise für diesen Zweck benutzt werden (IRQs 0 und 8), sind vom L4-Kern für interne Zwecke reserviert. Daher wird das Warten auf den Uhreninterrupt mit dem IPC-Mechanismus des L4-Kerns durch Timeouts emuliert.

Durch dieses Verfahren ,,geht'' der Uhreninterrupt natürlich ungenau. Dies wird durch eine spezielle Synchronisation der Linux-Zeit (jiffies) mit der vom L4-Kern bereitgestellten Maschinenzeit ausgeglichen.

4.3 Kern- und Nutzeraktivitäten

Von besonderem Interesse sind hier der Kerneintritt und die Realisierung der synchronen Umschaltung zwischen den Kernaktivitäten, denn die L4-Anpassung muß gewährleisten, daß immer nur eine Instanz zu einer Zeit Linux-Code ausführt, da Linux nicht eintrittsinvariant ist.

4.3.1 Kerneintritt

Führt ein Linux-Programm einen Systemruf aus oder tritt eine Ausnahme oder ein Seitenfehler auf, so führt dies zu einer Nachricht an die zugeordnete Linux-Kern-Task, wie wir in Abschnitt [hier] gesehen haben. Nachdem diese Nachricht vom Kern empfangen wurde, muß der nicht eintrittsinvariante Linux-Code ausgeführt werden. Um zu verhindern, daß zwei Instanzen gleichzeitig Linux-Code ausführen, müssen sich alle Kern-Aktivitäten synchronisieren.

Vorbild für den Synchronisationsmechanismus war die Linux-Portierung auf OSF Mach, die ebenfalls ein Server-Modell realisiert [1]. Dort wird der Kerneintritt mit einem Mutex (C-Typ mutex_t) synchronisiert, einem binären Semaphor mit Warteschlange [23].

Wir implementierten diese Funktionalität für L4 nach, wobei wir für die Suspendieren/Fortsetzen-Semantik den L4-IPC-Mechanismus benutzten: Um sich schlafenzulegen, hängt sich der aktuelle Thread in eine Warteschlange ein und wartet dann auf eine Aufweck-Nachricht von einem anderen Thread, der das Mutex gerade freigibt.

Nun ist es möglich, den gesamten Linux-Kern mit dem Mutex KernelLock zu schützen, welches vor der Abarbeitung von Linux-Code gesetzt und danach wieder freigegeben werden muß.

4.3.2 Umschaltung zwischen Kernaktivitäten

In Linux wird die Umschaltung zu anderen Kern-Aktivitäten durch Aufruf der Funktion schedule() ausgeführt. Diese Funktion entscheidet, welche Kern-Aktivität als nächste laufen soll und aktiviert diese.

Im Gegensatz zu Linux/i386 wird unter L4 diese Funktion nicht regelmäßig vom Uhreninterrupt aufgerufen, um Präemption von Nutzeraktivitäten zu erreichen, da Linux/L4 ein serverbasiertes System ist und die Umschaltung zwischen Nutzer-Tasks bereits vom L4-Scheduler durchgeführt wird (vgl. Abschnitt [hier]).

schedule() wird also nur explizit von Kernaktivitäten benutzt, um sich zu suspendieren. Es muß lediglich gewährleistet werden, daß keine Aktivität schedule() verläßt, bis ihr Linux-Prozeß-Zustand (wieder) auf TASK_RUNNING gesetzt ist.

Die Linux-Portierung auf OSF Mach benutzt zum Warten auf diese Bedingung eine Condition Variable (C-Typ condition_t) [23]. Auch in diesem Fall implementierten wir diese Funktionalität für L4 nach, und zwar die Libmach-Funktionen condition_wait() und condition_signal(): Erstere gibt ein angegebenes Mutex frei und wartet auf das Eintreten einer Bedingung, die durch eine Condition Variable repräsentiert wird, und letztere signalisiert ebendiese Bedingung.

Damit läßt sich die grundlegende Funktionalität von schedule() wie folgt erbringen:

if (current->state == TASK_RUNNING)
  {
    thread_yield();             /* kurz zu anderen bereiten
                                   Aktivitaeten umschalten */
  }
else
  do
    {
      ...
      kernel_will_exit();       /* Kontext freigeben (current usw.) */
      condition_wait(&(task->tss.condition), &KernelLock, task);
      kernel_has_entered(task); /* Kontext wiederherstellen */ 
      ...
    }
  while (current->state != TASK_RUNNING);

Außerdem muß in der Linux-Funktion wake_up_process(), die den Zustand einer Task auf TASK_RUNNING setzt, ein Aufruf zu condition_signal() eingefügt werden, damit suspendierte Tasks weiterlaufen können, wenn sie aus Sicht von Linux wieder rechenbereit werden.

4.4 Speicherverwaltung

Wie bereits erwähnt, manipuliert Linux den virtuellen Adreßraum seiner Aktivitäten mit einer vom architekturabhängigen Teil zu implementierenden Seitentabellen-Schnittstelle. Diese Schnittstelle geht von einer dreistufigen Seitentabellen-Hierarchie aus, die von der Architekturanpassung in das von der jeweils benutzten Maschine verwendete Format umgewandelt werden muß (z.B. Intel: zweistufige Hierarchie; PowerPC: invertierte Seitentabellen).

Für die Portierung auf L4 verwendeten wir die Architekturanpassung aus Linux/i386, so daß durch die Adreßraum-Manipulationen des Linux-Kerns letztendlich eine für den Intel-Prozessor geeignete zweistufige Seitentabellen-Hierarchie entsteht.

Anpassungen waren lediglich in den Funktionen set_pte() und pte_clear notwendig, die von Linux zum Manipulieren eines Seitentabelleneintrags verwendet werden: Um eine Seite auszublenden oder nicht-schreibbar einzublenden, wird der L4-Systemruf l4_fpage_unmap() aufgerufen.

Tritt nun ein Seitenfehler auf (d.h. der entsprechende Pager-Thread erhält eine Seitenfehler-Nachricht), so bildet unser Pager die Funktion der Intel-CPU nach: Er schlägt die entsprechende Seite in der Intel-Seitentabelle nach, prüft die Zugriffsattribute der Tabelleneinträge, ruft gegebenfalls die entsprechenden Linux-Seitenfehler-Prozeduren auf (do_no_page() für nicht vorhandene Seiten, do_wp_page() für schreibgeschützte Seiten) und sendet letztendlich die Seite als L4-Flexpage an den Thread zurück, in dem der Seitenfehler aufgetreten war.

4.5 Signalzustellung

Wie in Abschnitt [hier] besprochen, wurde die Signalzustellung mit Hilfe eines im Nutzeradreßraum laufenden speziellen Threads realisiert, der Meldungen über neue Signale vom Linux-Server empfängt und dann dem Nutzer-Thread Ausnahmen zustellt.

Die Nachrichten an den Signal-Thread können von jeder Kern-Task generiert werden. Die Versendung erfolgt in der Linux-Prozedur generate(), die für das Setzen von Signal-Flags in einer Prozeß-Datenstruktur verantwortlich ist.

Interessant an der Implementation dieses Mechanismus waren im wesentlichen zwei Aspekte:

Das erste Problem wurde durch Einführung eines Locks under_kernel_control in der Prozeß-Datenstruktur gelöst, das unmittelbar beim Eintritt in den Linux-Kern gesetzt wird. Ist es für die zu signalisierende Task bereits gesetzt, kann die Signal-Nachricht wegoptimiert werden.

Das zweite Problem konnte durch ein Lock emu_local_lock gelöst werden, das die von der Ausnahmebehandlung im Nutzer-Adreßraum benutzte Datenstruktur schützt und das bei jeder Ausnahme sofort von der Ausnahmebehandlung gesetzt wird. Der Signal-Thread darf keine Signal-bedingte Ausnahme zustellen, solange er dieses Lock nicht erwerben kann.

Im Normalfall kann der Signal-Thread in diesem Fall die Signal-Nachricht sogar ignorieren, da der Nutzer-Thread ohnehin gerade den Kern betritt. Problematisch ist jedoch der Zustand, in dem der Prozeß zwar den Kern betreten, die Signalzustellung aber bereits durchgeführt hat: In diesem Fall darf der Signal-Thread die Nachricht nicht ignorieren, sondern muß die Ausnahme nach der Rückkehr des Nutzer-Threads aus dem Kern zustellen. Um letzteren Fall zu erkennen, wurde ein für den Signal-Thread sichtbares Flag sigs_handled eingeführt, das unmittelbar vor der Signalzustellung im Linux-Kern gesetzt wird.

4.6 Zusammenfassung

Wir implementierten ein auf dem Mikrokern L4 laufendes Linux-System, das zu Linux/i386 ABI-kompatibel ist. Das System kann in den Multi-User-Modus booten, und die wichtigste Applikationssoftware für Linux läuft (X Window System, Netzwerksoftware, Compiler usw.).

Bisher nicht realisiert wurden die Systemrufe zur Unterstützung des Virtual-8086-Modus der Intel-CPU und eine Schnittstelle für Kernmodule, die für Linux/i386 generiert wurden.

Das Ziel, möglichst keine Änderungen am architekturunabhängigen Teil des Linux-Kerns vorzunehmen, konnte weitestgehend eingehalten werden; es waren lediglich kleine Änderungen am Scheduler und am Signalzustellungsmechanismus und unbedeutende Änderungen an einigen Device-Treibern notwendig.


Michael Hohmuth
29. August 1996