Assignment 2 - Virtual Memory

Abgabeschluss: Design 16.12.2011, Implementierung 18.1.2012 - jeweils 18:00

Punktevergabe

Aufgabe	Unteraufgabe	Punkte
Designdokument		5
Virtual Memory
	Page Replacement Algorithmus	8
	Copy on Write	7
	Swap-Device-Verwaltung	7
	Virtual-Memory-Verwaltung	7
	Tests	6
Optionale Tasks		25

Um bei Assignment 2 positiv zu sein, müssen

aus dem verpflichtenden Teil (Virtual Memory) mindestens 20 Punkte
für das Designdokument mindestens ein Punkt
und insgesamt mindestens 25 Punkte

erzielt werden.

Pflicht-Task - Virtual Memory (35 Punkte)

Bisher

hatten Sie ein Speichermanagement, das lineare Adressen über einen paging-Mechanismus auf den realen Hauptspeicher abgebildet hat. Jetzt soll das ganze virtuell werden - echter Virtueller Speicher ist gefragt! Aus den linearen Adressen werden vollwertige virtuelle Adressen, und Page-Frames werden, bei Platzmangel, ausgelagert.

Theorie :

Um einen beliebig großen Speicher "vorzutäuschen", werden bei Platzmangel Seiten im dem Hauptspeicher freigemacht und deren Inhalte auf die Festplatte ausgelagert. Mit Hilfe der Paging Mechanismen ist es möglich, bei Bedarf diese Seiten wieder von der Festplatte in den Hauptspeicher zu holen. Programme werden auch nicht mehr automatisch vollständig in den Speicher geladen, somit könnten auch Prozesse gestartet werden, die größer sind als der gesamte Hauptspeicher. In der Page Table wird durch ein Present-Bit gekennzeichnet, ob sich die entsprechende Seite (Page) im Hauptspeicher befindet oder auf der Festplatte.

Befindet sich eine benötigte Page nicht im Hauptspeicher, so wird von der Hardware eine PageFaultException geworfen, und die entsprechende Page aus dem Binary bzw. der Auslagerungsdatei in den Hauptspeicher geladen (SwapIn). Ist der Hauptspeicher voll, so muss zuerst eine Page ausgelagert werden (SwapOut); welche Page ausgelagert wird, entscheidet die Replacement Policy.

Ihre Implementierung :

Modifizieren Sie SWEB so, dass die Mechanismen des Virtuellen Speichers umgesetzt werden. Wie in der Vorlesung besprochen existieren hier eine Reihe von Optionen, von denen die meisten auch hier bei SWEB umsetzbar sind. Sie haben hier sehr viele Freiheiten.

Mindestvoraussetzungen für Ihre Implementierung sind:

Programmcode darf nicht ausgelagert werden, da dieser ja jederzeit vom Binary nachgeladen werden kann!
Es ist ein Kernel-Thread zu schreiben, der "im Hintergrund" Seiten fürs Auslagern auswählt, sodass es bei einem auftretenden pagefault immer eine freie Seite gibt!
Erweitern Sie Demand- Paging dahingehend, dass beim Pagemanger prinzipiell "immer" ein freier Pageframe angefordert werden kann.
Swapping muss auf ein dafür vorgesehenes Blockdevice erfolgen.
Um echte VM-Stimmung aufkommen zu lassen, sollten Sie Ihrer Maschine nicht allzuviel RAM geben, da Sie vermutlich keine besonders großen User-Programme schreiben werden. Durch Anlegen großer Arrays etc. lässt sich hier jedoch auch der RAM-Verbrauch geeignet künstlich erhöhen. Jedenfalls müssen Sie Ihr Testkonzept so auslegen, dass auch echte Swapping-Situationen entstehen!
Achten Sie auf die Geschwindigkeit! Wenn noch genügend Speicher frei ist sollte der Performance-Verlust des Systems sehr gering sein. Versuchen Sie auch bei einer vollen Auslastung des physikalischen Speichers unnötigen Performance-Verlust zu vermeiden.
Implementieren Sie eine vernünftige Replacement-Strategie. Reines FIFO ist jedenfalls verboten, je besser Ihre Lösung desto besser Ihre Punktezahl.
Statistikfuntkionen: Sammeln Sie statistische Werte wie
- Anzahl der pagefaults (je Prozess)
- Anzahl der verwendeten pageframes (je Prozess)
- Anzahl der verwendeten frames im Swap-Bereich (je Prozess)
- Anzahl der freien Seiten (RAM bzw. SWAP)
und schreiben Sie die nötigen Systemcalls, um diese Infos im Userspace verfügbar zu machen. Ein Userprogramm, das diese Infos ausliest und schön formattiert ausgibt, ist ebenfalls zu implementieren.
Die nachfolgenden Calls sollen zur Verfügung gestellt werden.Dabei gilt: PID = 0 berechnet die Information für den currentProcess. PID > 0 für den gg. Prozess. Überlegen Sie sich sinnvolle Rückgabewerte für nicht (mehr) existierende Prozesse.
- int sweb_stats_pagefaults(int pid);
  liefert die Anzahl der Pagefault des gg. Prozesses.
- int sweb_stats_physical_pages(int pid);
  liefert die Anzahl der Physical Page Frames die der gg. Prozess in Verwendung hat.
- int sweb_stats_swapped_pages(int pid);
  liefert die Anzahl der Page Frames auf dem Swap-Device die der gg. Prozess in Verwendung hat.
- int sweb_stats_free_physical_pages();
  liefert die Anzahl der freien physikalischen Seiten zurück.
- int sweb_stats_free_swap_page_frames();
  liefert die Anzahl der freien Page Frames auf dem Swap-Device zurück.

Folgende Aufgabenbereiche ergeben sich dabei:

Virtual Memory verwalten:
- Im Kernel muss dafür gesorgt werden dass Swapping mit den vorhandenen Virtual Memory Mechanismen zusammenarbeitet. Dabei wird es insbesondere nötig sein, Seiten auszulagern (SwapOut) sobald der physikalische Speicher voll wird, und wieder einzulagern sofern die Seite benötigt wird.
- SwapOut:
  - Das Auslagern wird von einem eigenen Kernel-Thread gesteuert, der dafür zu sorgen hat, dass bei Pagefaults möglichst immer eine freie Seite verfügbar ist. Über eine eigene Bitmap, die die benutzten Plätze im Swap-Device verwaltet, wird ein freier Platz gesucht. Durch den Page Replacement Algorithmus wird ermittelt welche Seite ausgelagert werden soll. Diese wird an die zuvor ermittelte Position im Swap-Device kopiert, wenn das dirty-Bit gesetzt ist, ansonsten wurde die Page nicht veröndert und ein nochmaliges Speichern ist nicht erforderlich. Beachten Sie, dass ein Auslagern von Codeseiten generell nicht erlaubt ist.
  - Sie sollen außerdem mit Hilfe von Userprogrammen, die verschiedene PageFaultExceptions bewusst provozieren, das Verhalten Ihrer Implementierung prüfen und bewerten.
- SwapIn:
  - Die gesuchte Page wird im Swap-Device lokalisiert. Ist im Hauptspeicher noch ein freier Platz vorhanden, so wird die Page unmittelbar in den Speicher geladen, und die Pagetable aktualisiert.
Page Replacement Algorithmus:
Mit Hilfe eines von Ihnen gewählten Algorithmus wird jene Page im Hauptspeicher ausgesucht, die "geswappt" werden soll. Überlegen Sie sich auch, mit welchen Testprogrammen Sie die Stärken und Schwächen des implementierten Algorithmus testen werden.
Swap_Device verwalten:
Als Swapbereich ist für alle Prozesse ein einziges Blockdevice zu verwenden. Um eine bestimmte Page eines Prozesses in ihrem Swap-Device zu finden, erstellen Sie eine geeignete Datenstruktur ähnlich einer Pagetable. Zumindest folgende Informationen werden Sie für jeden Prozess benötigen: virtuelle Page-Nummer, Position im Swap-Device und readonly-Bit der Page. Zum Auffinden der freien Einträge im Swap kann beispielsweise eine Bitmap verwendet werden. Wird ein Prozess beendet, müssen die ihm zugehörigen Pages freigegeben werden.
Copy-on-Write:
In Assignment 1 ja bereits ein fork/exec-Konzept umgesetzt. Bei einem fork entstehen zwei geklonte Prozesse, die beide dasselbe tun sollen und idente Speicherbereiche haben. Das Kopieren des Speichers kostet Zeit und kann entfallen, wenn nach dem fork einer der Prozesse ein exec macht. Eine Möglichkeit des Vermeidens ist, die Pagetables der beiden Prozesse so auszulegen, dass die PTEs beider Prozesse auf dieselben Speicherbereiche zeigen und erst beim ersten Schreibzugriff auf eine Seite diese eine Seite dupliziert wird. Ihre Aufgabe ist es, dieses Feature zu implementieren. Beachten - und testen! - Sie bitte auch, dass ein Prozess auch mehrfach geklont werden kann, und daher eine page mehr als zwei Prozessen zugeordnet sein kann. Auch das Auslagern einer derartigen Seite ist korrekt zu behandeln.

Änderung Designdokument:

Bei A2 darf Ihr Executive Summary bis zu vier Seiten lang sein!

Optionaler Task: Shared Memory

Task 2 ist optional, muss also nicht einmal versucht werden.

Implementieren Sie die Möglichkeit, dass zwei oder mehrere User-Prozesse einen gemeinsamen Speicherbereich zum Austausch von Daten verwenden können. Nach Zuordnung des gemeinsamen Speicherbereiches müssen diese ganz normal über Pointer verwendbar sein! Erstellen Sie ein geeignetes Konzept. Beantworten Sie mit Ihrem Konzept folgende Fragestellungen:

Welche Services müssen Sie hier anbieten und wie können die Prozesse diese Services anfordern?
Wenn mehrere Prozesse verschiedene gemeinsame Speicherbereiche verwenden wollen, wie können Sie dies unterscheiden? Wie sagt ein Prozess dem Betriebssystem, auf welchen dieser Speicherbereiche er den Zugriff anfordert?
Wie - und wo - wird der gemeinsame Speicher in den virtuellen Adressraum jedes einzelnen Prozesses "eingeblendet"?
(Wie) kann die Größe des gemeinsamen Speichers erhöht werden, falls der Prozess das möchte, oder hat der Bereich nach der Erzeugung eine fixe Größe?
Was machen Sie bei fork? Überlegen Sie sich was sinnvolles...

Diese - und sicher noch einige weitere Fragen - müssen Sie in Ihrem Konzept beantworten. Sie haben hier wieder ausreichend Spielraum bei Ihrer Implementierung - toben Sie sich aus!
Allerdings müssen Sie doch wieder unsere API-Vorstellungen einhalten. Als Interface haben Sie die folgenden syscalls zu verwenden:

int shm_open(const char *name, int oflag, mode_t mode);
int shm_unlink(const char *name);
void *mmap(void *addr, size_t len, int prot, int flags,int fildes, off_t off);
int munmap(void *addr, size_t len);

Optionaler Task: Memory Mapped I/O

Filezugriffe können, wie Sie in Assignment 1 ja bereits gesehen haben, über filesystemspezifische Syscalls erfolgen. Eine Alternative ist, die benötigte Datei in den Adressraum eines Prozesses einzublenden. Dazu implementieren Sie Syscalls

void *mmap(void *addr, size_t len, int prot, int flags,int fildes, off_t off); int munmap(void *addr, size_t len);

wobei

fildes der filedescriptor einer bereits mit open geöffneten Datei
len die Anzahl der zu mappenden Bytes angibt. Maximal so viele Bytes der Datei sind dann über dieses Mapping ansprechbar.
prot gibt den Zugriffsschutz an: PROT_READ - nur lesen, PROT_WRITE - auch schreiben.
flags (optional) erlaubt es, das Verhalten beim Einblenden einer Datei in die Speicherbereiche mehrerer Prozesse zu steuern. Hierbei gilt:

MAP_SHARED: Änderungen an der Datei in einem Prozess sind auch in einem anderen Prozess sofortsichtbar. Modifikationen werden auch im File gespeichert.
MAP_PRIVATE: Änderungen wirken sich weder auf den File noch auf mappings anderer Prozesse aus.

off das Offset des File-Deskriptor Mappings

mmap liefert die Startadresse des Mappings. Mit munmap wird dann der File wieder ausgeblendet (sozusagen das "close"). Der parameter von munmap ist die Startadresse, die vom mmap-Call zurückgegeben wurde. Ein munmap mit einer anderen Adresse muss zu einem Fehler führen. Wo sie das einblenden, ist an sich Ihre Entscheidung. Die Überlegungen dazu werden ähnlich sein wie bei sbrk (siehe weiter unten). Mehrere Filemappings sollten wohl auch möglich sein und bei einem fork muss die Datei auch im neuem Userprozess verfügbar sein!

Dass Sie ein ausführliches Testprogramm schreiben werden müssen, ist selbstverständlich.

Änderung Designdokument:

Bei A2 darf Ihr Executive Summary bis zu vier Seiten lang sein!

Optionaler Task: sbrk und malloc

Ein Programm verwendet normalerweise mehrere Datenbereiche, die oft in Segmenten organisiert sein können:

Der Datenbereich ist oft in BSS (mit Null initialisierte Bereiche) und DATA-Abschnitte (initialisierte Variable, Konstante) unterteilt. Zwar könnte man den Teil des Adressraums, der nicht von diesen Bereichen belegt ist, vom Programm aus jederzeit verwenden, wenn die Speicherverwaltung das zuließe. Da das jedoch selten Sinn macht, wird ein pagefault in diesem nicht verwendeten Bereich als Fehler betrachtet. Für dynamische Speicherverwaltung kann man aber den Datenteil erweitern lassen. Dafür sind unter Unix die syscalls brk und sbrk definiert. brk steht für break und meint die ABGrenze zwischen heap und nicht verwendetem Speicherbereich. Der syscall brk setzt die Grenze auf die als Parameter angegebene Speicheradresse, während sbrk den break um die angegebenen Anzahl an Bytes vergrößert. Die Aufrufe sind wie folgt definiert:

int brk(void *end_data_segment);
void *sbrk(ptrdiff_t increment);

Bei Erfolg gibt brk 0 zurück und sbrk einen Pointer auf den neu angeforderten Bereich. Der erste Teil dieser Aufgabe ist die Implementierung des Systemcalls sbrk. sbrk lässt sich dann unter Verwendung von brk implementieren.

Für dynamische Speicherverwaltung aus Userprogrammen heraus ist die Verwendung dieser Syscalls wohl etwas mühsam. Daher werden für die Praxis malloc und free verwendet.

void *malloc(size_t size);
void free(void *s);

Ein Beispiel der Verwendung:

char* newString; 
newString = malloc(128);
...
free(newString);

Diese Routinen sind als library-Routinen auszuführen, die den sbrk-Syscall verwenden, um neuen Speicher vom System zu erhalten.