Ziel dieser Aufgabe ist es, den isolierten Prozessen effiziente Primitiven zum Nachrichtenaustausch (message passing) anzubieten, sowie einen Systemaufruf zur Prozesserzeugung, ähnlich dem Unix-fork(), bereitzustellen.

Systemaufrufe

Folgende Systemaufrufe sollen implementiert werden:

int getpid()
 
void send(int id, void *sbuffer, size_t ssize, void *rbuffer, size_t rsize)
 
int recv(void *buffer, size_t size)
 
void reply(int id, void *buffer, size_t size)
 
int fork()

getpid(): Liefert die Prozess-Identifikationsnummer des aufrufenden Prozesses. Diese Nummer soll im laufenden System eindeutig sein.
send(): Sendet die Nachricht in sbuffer mit der Länge ssize synchron und blockierend an den Prozess mit der Nummer id. Die Operation blockiert solange bis der Empfänger die Nachricht mit recv() entgegennimmt und mit Hilfe von reply() eine Antwort schickt. Diese Antwort steht dann in rbuffer mit der Maximallänge rsize zur Verfügung.
recv(): Wartet auf eine Nachricht die in buffer mit der Maximallänge size abgelegt wird. Der Rückgabewert gibt die Identifikationsnummer des Senders an.
reply(): Schickt eine Antwortnachricht an den mit id identifizierten Prozess. Diese Funktion soll nicht blockieren und nur erfolgreich sein falls der Zielprozess tatsächlich ein send() zu diesem Prozess ausführt bzw. auf dessen Fertigstellung wartet.
fork(): Erzeugt einen neuen Prozess der eine Kopie des aktuellen Prozesses ist. Auch der neue Prozess wird bei Aktivierung aus dem fork()-Aufruf zurückkehren. Das einzige Unterscheidungsmerkmal ist die Prozess-Identifikationsnummer. Der Rückgabewert der Funktion ist die Identifikationsnummer des jeweils anderen Prozesses.

Die Puffer für send(), recv() und reply(), sollten am besten an Seitengrenzen liegen. Eine Möglichkeit, dies statisch zu erreichen, bietet der GCC mit __attribute__ ((aligned (x))) und einer Konstanten für x an. Anfangs sollten diese Systemaufrufe durch explizites Kopieren der Inhalte der betroffenen Seiten implementiert werden.

Kopie bei Schreibzugriff (Copy-on-Write)

In einem zweiten Schritt sollen die Seiten nur in den jeweils anderen Adressraum eingeblendet werden und erst im Fall eines Schreibzugriffs physikalisch kopiert werden.

Um Schreibzugriffe zu erkennen und anschließend Seiten kopieren zu können, müssen folgende Mechanismen implementiert werden:

Einblenden einer Seite in einen anderen Adressraum.
Betroffene Seiten als nur lesbar (read only) in den beteiligten Adressräumen markieren.
Ein spezieller pagefault handler (IRQ 14), der dann die Art des Fehlers feststellt, bei einer nur lesbaren Seite eine physikalische Kopie erzeugt und die Adressraumabbildung entsprechend anpasst.
Eine Schattentabelle für physikalische Seitenadressen soll die Anzahl der Referenzen auf COW-Seiten zählen. Wenn nur noch eine Referenz übrig ist, muss die Seite bei Schreibzugriffen nicht kopiert werden.

Bei send/recv bzw. reply/send sollen die Inhalte der Puffer nur dann mit Hilfe von COW kopiert werden, wenn die Nachrichtengröße mindestens der Seitengröße entspricht (Verschnitt regulär kopieren).

Genaue Informationen zum Paging und Pagefaults finden sich im Intel-Handbuch in Kapitel 4. fork soll natürlich nicht den Kernelbereich mitkopieren. Bei COW kann es vorkommen, dass die betroffenen Seiten bereits durch vorherige Übertragungen/fork()s COW-abgebildet sind, und die Referenzzähler entsprechend angepasst werden müssen. Der TLB wird beim Schreiben von cr3 implizit geleert. Einzelne Einträge können mit dem Assembler-Befehl invlpg invalidiert werden. Dieser Befehl funktioniert nur richtig mit indirekter Adressierung über ein Register: asm volatile(`"invlpg (%0)`" : : `"r`"(address) : `"memory`");

Stresstest für das Copy-on-Write

Sicher zu stellen, dass eine Copy-on-Write Implementierung das richtige tut, ist schwierig. Wir haben uns daher eine Anwendung ausgedacht, die alle Funktionalitäten aus der dritten Aufgabe auf Randfälle testet.

Die Anwendung

#include "syscall.h"
 
char __attribute__((aligned(4096))) sbuf[4097];
char __attribute__((aligned(4096))) rbuf[4097];
 
void main() {
    fork();
    fork();
    int ppid = getpid();
    int other = fork();
    if (ppid == other) {
        /* child */
        sbuf[0] = 3;
        sbuf[4096] = ppid;
        send(other, sbuf, 4097, rbuf, 4097);
 
        char msg[] = "REPLY: AA\n";
        msg[7] += rbuf[0];
        msg[8] += 3 + ppid;
        write(/*fd */ 0, msg, /*len=*/ 10, /* x= */ -1, /*y*/ -1);
    } else {
        /* parent */
        int X = recv(rbuf, sizeof(rbuf));
        rbuf[0] = rbuf[0] + rbuf[4096];
        reply(X, rbuf, 4097);
    }
 
    exit();
}

Diese Anwendung spaltet sich mit fork() in 4 Paare von Fäden auf. Innerhalb jedes Paares wird ein Faden auf eine Nachricht warten (parent) und der andere Faden (child) schickt seinem Partner eine Nachricht. Der empfangende Faden errechnet aus der Nachricht einen Wert und sendet den Buffer zurück. Am Ende beenden sich alle acht Fäden mit exit().

Als Ausgabe wird das Programm etwas ähnliches ausgeben wie:

REPLY: DD
REPLY: GG
REPLY: EE
REPLY: FF

Die Zeilen können in beliebiger Reihenfolge auftreten. Die beiden Buchstaben nach dem REPLY hängen dabei von eurer Implementierung der Fadennummer ab. Allerdings müssen die beiden Buchstaben, die folgen, in allen Fällen gleich sein!

Die Messung

Um eure Implementierung mit unserer Musterlösung zu vergleichen, könnt ihr eine Messung der freien Seiten durchführen. Um vergleichbare Aussagen zu machen, müsst ihr die Anzahl der freien Seiten messen, die euer Allokator verwaltet, ausgeben. Diese Zahlen müsst ihr an zwei Stellen ausgeben:

Direkt vor dem scheduler.schedule() in der main()
Am Anfang der IdleThread::action()

Dabei sollt ihr die Anzahl der verfügbaren Kernelpages und die Anzahl der verfügbaren Userpages ausgeben. Die Anzahl der freien Seiten darf dabei steigen, aber auf keinen Fall fallen! Und ihr dürft keine Seiten ausgeben, die in den Multibootinformationen reserved sind.

Der QEMU soll mit 128 MiB (default) RAM ausgestattet sein.

Was sagt die Musterlösung?

Die Musterlösung ignoriert alle Seiten unterhalb von 0x100000. Unser Speichererkennungsmechanismus erkennt 32478 freie Seiten. Die Regionen, die dafür bei uns verwendet werden, sind folgende:

module 0x0x118000-0x0x11f000 user/build/initrd.img
kernel 0x100000-0x116010
(available) 0x100000 0x7ffdfff
 \-> use! 0x100000-0xfffff 0 pages
 \-> use! 0x117000-0x117fff 1 pages
 \-> use! 0x121000-0x7ffdfff 32477 pages
(reserved) 0x7ffe000 0x7ffffff
(reserved) 0xfffc0000 0xffffffff

Am ersten Messpunkt benötigt unser System 49 Seiten:

allocator: 49 pages used
allocator: 28669 free userpages; 111 MByte
allocator: 3760 free kernelpages; 14 MByte

Am zweiten Messpunkt benötigt unser System 42 Seiten:

allocator: 42 pages used
allocator: 28670 free userpages; 111 MByte
allocator: 3766 free kernelpages; 14 MByte

Diese Abnahme im Seitenverbrauch liegt daran, dass im ersten Messpunkt sowohl ein Benutzerfaden als auch der Idle-Faden existieren. Am zweiten Messpunkt existiert nur noch der Idle-Faden. Unsere Initial Ramdisk verbraucht 7 Seiten.