Druckversion

Design Document Assignment 2

Bisher verfügt SWEB nur über einen statischen Speicher, in dem die Pages der Processe gelagert sind. Ziel dieses Assignments ist es SWEB um einen dynamischen Speicher zu erweitern, um die Inhalte vom schnellen Speicher auf das Filesystem auszulagern, sodass mehr Speicher vergeben werden kann. Um ein sinnvolles Caching zu betrieben, werden Statistiken zur Usage ermittelt und ein vorhandener Page-Replacement-Algorithmus implementiert. Kopieren des Speichers kostet Zeit, deswegen ist es ein Teil unserer Aufgabe bei einem fork() nicht auf einmal das komplette Speicherabild eines Prozesses zu kopieren, sondern erst bei Bedarf (Copy-On-Write). Ein weitere Teil der Aufgabe ist eine Interprozesskommunikation mittels Shared Memory zu ermöglicht (BonusTask). Das heißt das ein gemeinsamer Speicherbereich zum Austausch von Daten zur Verfügung gestellt und verwaltet wird. Selbstverständlich dürfen alle bestehenden Funktionen, unter Anderem die des vorigen Assignments, davon nicht eingeschränkt werden.

Grundlegende Designentscheidungen

Verwendung einer Inverted Page Table

Die von der x86 CPU-Architektur angebotenen Techniken zur Speicherverwaltung reichen für die Verwendung eines virtuellen Speichers nicht mehr aus. Deswegen verwenden wir eine Inverted Page Table die Metadaten zum statischen Speicher beinhaltet. Die Pagefault-Funktion ermöglicht uns einen Eingriff in den Prozess der Adressenauflösung.

Page Replacement via WS-Clock

Dieser durchsucht den Speicher nach Pages, die ein guter Kandidat für die Auslagerung wären. Da dieser Algorithmus maßgebend für eine effiziente Speicherverwaltung ist, wird die Implementierung flexibel gestaltet. So können nachträgliche Verbesserungen/Untersuchungen einfacher durchgeführt werden.

Shared Memory

Den Zugriff auf geteilte Ressourcen verwalten wir mit SIDs in der Prozessgruppen zusammengefasst werden.

Task 1 - Virtual Memory

Die Speicherverwaltung die bisher aus PageManager, den Loader -Instanzen, den UserProcessen und der Pagefault -Funktion resultierte, wird um einen zusätzlichen SwapManager erweitert. Diese Instanz bindet eine BDVirtualDevice (swap) ein und verwaltet diese.

Was ist alles Swap?

Alle Partitionen ab und inklusive der dritten werden als Swappartition erkannt und für diese wird ein SwapManager instanziert. Es wird jedoch immer der erste SwapManager als default verwendet. Ein SwapManager wird durch Ableiten von der Klasse Thread ausführbar gemacht, sodass er ab einem bestimmten Speicherverbrauch anfängt Pages auf die Partition auszulagern. Instanziert werden die Objekte in der startup -Funktion von SWEB.

Asynchron

Da benötigte I/O-Funktionen von der Klasse BDVirtualDevice verwendet werden und die Operationen viel Zeit beanspruchen, wird das SwapOut asynchron gestaltet. Dazu verwenden wir eine Liste die maximal 5 Einträge beinhaltet. Dadurch vermeiden wir, dass die Liste veraltet und der SwapManager nur mehr mit Pages auslagert, die schon gar nicht mehr verwendet werden.

Addressauflösung

Zur Auflösung der physikalischen zur virtuellen Adresse wird eine Inverted-Page-Table ( IPT) verwendet, die vom IPTManager verwaltet wird.

Beim Mapping von swap auf den virtuellen Speicher vom UserProcess werden Pageframes verwendet, die ähnlich wie die Pages am RAM organisiert sind. Dazu wird die Blocksize von swap auf die PAGE_SIZE gesetzt und die Belegung der Blöcke wird in einem Array mit aufgezeichnet.

Die Funktionen in ArchMemory wurden erweitert um den Speicherzustand in der IPT abzubilden.

Die verschiedenen Typen von Pages und deren Kennzeichnungen im PTE (Page-Table-Entry) sind:

• SWAP: Die Page ist am swap verfügbar. Der Index auf dem Pageframe am swap ist in der page_base_adress vom PTE gespeichert oder im IPT sofern die Page auch im statischen Speicher verfügbar ist.
• SHARED: Die Page wird von mindestens zwei Prozessen referenziert. Solche Pages entstehen im Fall von Shared Memory oder Copy-On-Write Mappings.
• DIRTY: Die Inhalte der Page wurden verändert. -> Der Inhalt am Swap ist outdated.

Eine virtuelle Page "existiert", wenn entweder PRESENT, SWAPPED oder MEMIO-Flag gesetzt ist. Das SHARED-Flag wird immer im Zusammenhang mit diesen verwendet.

Swapoperationen

Die Auslagerung findet erst statt, sobald wenige Pages im statischen Speicher frei sind. Ab wann bestimmt eine Konstante (SWAPOUT_THRESHOLD). Diese ist in debug.h definiert . Defaultmäßig ist sie auf 5 (zu Testzwecken). EXEC Pages werden zwar als SWAPPED markiert aber nicht in das Swapdevice geschrieben, beim Ersetzen (=evict) der EXEC Page wird SWAPPED wieder auf 0 gesetzt und PRESENT auf 0. Dies bewirkt, dass bei einem Pagefault wieder aufs binary zugegriffen wird. Ersetzt werden Pages aus dem RAM erst dann, wenn eine Speicheranforderung stattfindet und keine Seite im RAM mehr frei ist.

Ablauf von SwapIn

Ein SwapIn wird immer dann ausgeführt, sobald bei einem PageFault das PRESENT -Flag nicht gesetzt und das SWAPPED -Flag gesetzt ist.

Anhand der page_table_base_adress im IPTs wird die Swap-Adresse ermittelt. Anschließend wird die Page an eine neue physikalische Adresse kopiert. Schlussendlich wird die Page noch zur IPT hinzugefügt.

Ablauf von SwapOut

Es wird auf die Liste to_be_swapped_ zugegriffen, die vom PRAThread befüllt wird. Ist diese leer, wird eine zufällige Page ausgewählt. Es wird überprüft ob das DIRTY -Flag der übergebenen Page gesetzt ist. Ist dies der Fall wird die Seite in den virtuellen Speicher geswappt, das SWAPPED -Flag auf 1 gesetzt. Sind das DIRTY und SWAPPED -Flag nicht gesetzt, wird auch in den Swap geschrieben. Fuer den Fall, dass DIRTY = 0 und SWAPPED = 1 geschieht nichts (Swap ist aktuell).

Virtuelle Zeitmessung

Die von WSClock geforderte virtuelle Zeit wird lokal im jeweiligen UserProcess gespeichert und bei jedem Timer -Interrupt erhöht (wenn dieser Prozess ausgefuehrt wird). Die Systemzeit wird in der Variable uptime_ gespeichert (InterruptUtils). Dies ist ein Counter der in INT0 erhöht wird um die Laufzeit des Systems zu approximieren.

Statistiken zum virtuellen Speicher

Informationen zu den Speicherzugriffen werden aufgezeichnet, um die Qualität des PRA zu messen. Die Libc -Funktion int stats(int which_stat, int which_process) ruft diesen Syscall auf. Dieser implementiert grundlegende Statistikabfragen.

Der Parameter which_stat entscheidet, welche Statistik wir abfragen wollen:

• 0 = # der Pagefaults im Prozess
• 1 = # der verwendeten Pageframes im RAM vom Prozess
• 2 = # der verwendeten Pageframes im Swap vom Prozess
• 3 = # der freien Pageframes im RAM
• 4 = # der freien Pageframes im Swap
• 5 = Runtime des Prozesses
• 6 = Systemuptime
• 7 = Anzahl der Pageframes des Prozesses, die nur im RAM liegen
• 8 = Anzahl der Pageframes des Prozesses, die nur im Swap liegen

Der Übergabeparameter which_process entscheidet, für welchen Prozess wir die Statistiken haben wollen, wobei 0 für den aufrufenden Prozess steht und jede Zahl > 0 für eine ProzessID.

Änderungen im PageManager

Im PageManager ist eine neue Funktion throttleRAM(uint32 pages_to_throttle) vorhanden. Diese Funktion setzt eine Anzahl an Pages im statischen Speicher auf Reserved. Damit können wir zu Testzwecken den Speicher begrenzen. Der PageManager sucht jetzt zusätzlich wenn keine freie Page im statischen Speicher vorhanden ist eine Page (via SwapManager::evictPage()) die überschrieben werden kann.

SwapManager

Dieser Thread läuft im Hintergrund und schreibt Pages in den zugehörigen swap, die zum Auslagern markiert sind, die noch nicht im swap liegen und Pages, die zum Auslagern markiert sind und bereits im Swap liegen, aber ihr dirty bit gesetzt haben.

Im SwapManager wird in einer Liste festgehalten welche Blöcke im swap belegt sind (0 = frei, 1 = belegt). In der wird nach First Fit ein Block zum Beschreiben ausgesucht.

Page Replacement Algorithmus

Dieser Thread markiert die Pages zum auslagern. Dieser implementiert den von uns gewählten Page-Replacement-Algorithmus. Wir haben uns für WSClock entschieden, weil dieser Algorithmus für uns großes Verbesserungspotenzial aufweist und zudem leicht erweitert werden kann. Ein Möglichkeit wäre eine Modifizierung des zur Page gehörenden Zählers, um zusätzlich zur Aktualität der Page die long-term-utility einfließen zu lassen.

Beim Durchsuchen des Speichers wird das ACCESSED -Flag, das DIRTY -Flag und der Timestamp angeschaut. Wenn der Timestamp kleiner als das Workingset ist, dann gehen wir zur nächsten Page. Wenn der Timestamp älter ist als das Workingset und das DIRTY -Flag gesetzt, dann teilen wir dem SwapManager mit, dass diese Seite ausgelagert werden kann. Das Flag ACCESSED wird auf 0 gesetzt und der aktuelle Timestamp wird geschrieben.

Die Größe des Workingsets wird durch die Anzahl der Pagefaults bestimmt. Wenn ein unterer Schwellwert unterschritten wird, wird sie verkleinert, wenn ein oberer Schwellwert überschritten wird, wird sie vergrößert.

Inverted Page Table

Dient zum Übersetzen der physikalische Adresse mit PID auf die virtuelle Page. Wird direkt im statischen Speicher angelegt (unmittelbar nach den Kernelpages) und kann nicht ausgelagert werden. Die Größe wird mit 'IPT_ENTRY_SIZE * (Total RAM Pages - Pages of Kernel)' bestimmt. Es werden also darin nur die vom UserSpace benutzbaren Pages, aber nicht die Pages des Kernels gemappt.

Beinhaltet folgende Informationen zu jeder Page im statischen Speicher

• virtuelle_page
• pid
• swap_adresse
• memory type (exec, stack, .. um zu entscheiden ob und wie swappbar)

Die swap_adresse wird beim SwapOut in die page_base_adress im PTE der zugehörigen virtuellen Page kopiert. Der Memory Type wird nach einem SwapIn auf einen Typ gesetzt, der anzeigt, dass diese Page immer ausgelagert werden kann.

Task 2 - Memory Mapped I/O

Die Implementierung erlaubt es, einen Bereich in den Speicher zu mappen, der größer als das File ist. Es stehen 3 Syscalls zur Verfuegung: SC_FMAP, SC_FUNMAP und SC_FMAPFLUSH. SC_FMAP erstellt das Mapping, SC_FUNMAP entfernt das Mapping und SC_FMAPFLUSH schreibt Änderungen in das File zurueck, wenn es mit Schreibberechtigung geöffnet wurde.

• void *fmap(int fildes, int len, int prot, int flags)
• int funmap(void *pa)
• int fmapflush(void *pa)

SC_FMAP

Beim mappen eines Files in den RAM wird mittels Syscall im UserProcess die Funktion mapFileToMem ausgefuehrt. Der Filedescriptor des zu mappenden Bereichs muss bereits existieren (= das File geoeffnet sein). Die Laenge in Bytes wird uebergeben und ob das File nur lesbar oder auch schreibbar ist. Im UserProcess wird fuer jeden mappenden Bereich ein Eintrag in der file_map_list_ erstellt. Dieser ist ein struct, der den Filedescriptor, die virtuelle Adresse der Startpage des gemappten Bereichs, die Laenge in Bytes und in Pages und den Zugriffsschutz speichert. ArchMemory::getFreeVirtualMem sucht nach einem freien Speicherbereich der benoetigten Laenge (von der oberen 2GB Grenze nach unten, firstfit). Wenn kein freier Speicher mehr verfuegbar ist, wird eine Kernel Panic geworfen. Ansonsten werden die Pages reserviert (PAGE_IOMAPPED = 1) und die unterste als Pointer auf diese Adresse zurueckgeliefert.

Hier ist on-demand paging anwenden, es wird also nicht sofort physikalischer RAM Speicher für die Kopie des gesamten Files angefordert, sondern jeweils nur eine Page.

SC_FUNMAP

Beim unmappen wird ueberprueft, ob es sich um einen gueltigen Pointer handelt. Dann werden die Pages unmapped und der Eintrag aus der file_map_list_ entfernt.

SC_FMAPFLUSH

Mit diesem Syscall werden Aenderungen ins File zurueckgeschrieben. Es wird immer die Anzahl an Bytes in das File geschrieben, die gemapped wurde. Wenn also mehr Bytes gemapped wurden als im File waren, wird das File vergroessert. Zuerst wird auf einen gueltigen Pointer ueberprueft und ob das File schreibbar geoeffnet wurde. Dann wird von den veraenderten Pages gelesen und in das File zurueckgeschrieben.

Shared Memory mit CoW als Sonderfall.

Durch ein geeignetes Sharing Konzept ist es moglich mit einer Klasse ShareManager und einer zentralen Liste sowohl das CoW als auch Shared Memory als beinahe identische Faelle zu verwalten.

Es wird ein PTE Flag Shared eingeführt.
PIDs die Seiten miteinander teilen werden in ShareIDs zusammengefasst.

In einer neuen Singleton Klasse ShareManager wird eine globale Liste shared_list_ erstellt und verwaltet.
In dieser sind gespeichert (SID, (PID, (vPage_base, #Pages, CoW Type) ) )
Eine SID haelt also mehrere PIDs. Eine PID kann natürlich auch mehreren SIDs angehören.
Das Paar (SID, PID) identifiziert den gesharten Bereich mit der Information vPage_base, #Pages, CoW Type, CoW Pages Remaining.

Ein Vorhandensein der virtuellen Page einer PID im Bereich einer share_list_ (vpage_base - vpage_base+#pages) ist noch keine Garantie, dass diese tatsächlich geshart wird, erst das Share Flag gibt Gewissheit.
Damit spart mann sich das genaue Festhalten in Listen, welche Seiten von CoW Prozessson tatsächlich noch geshart sind.

In dieser Art ist es möglich einen gesharten Bereich in verschiedenen Prozessen virtuell verschieden zu mappen.
Lediglich die SID muss übereinstimmen.

CoW Type identifiziert das Verhalten des PID in der SID bei Schreibzugriff.

CoW 0 .. kein CoW (Bonustask Share Memory)
CoW 1 .. CoW Verhalten

Auf diese Weise können der Fall unterschieden werden in dem ein geforkter Prozess einen write Zugriff macht.
In diesem Fall wird eine lokale Kopie des gesharten Bereichs erstellt, die PTE.Base Adresse angepasst und shared 0 gesetzt.

Da in der share_list_ nicht genau vermerkt ist welche Seiten tatsächlich noch geshart werden, sondern nur das grundlegende Verhältniss der PIDs, kann über das Shared Flag der virtuellen Page aller PIDs tatsächlich geprüft werden ob die Seite noch von einer bestimmten PID geshart wird.

Fork Ablauf mit CoW:

Setzen aller existierenden PTE Flags (existierend = swapped oder present flag gesetzt) auf Shared 1, Writeable 0.
Deep Copy aller existierenden PTEs in neuen Prozess. (PTE.Base Adressen zeigen auf Speicher des forkenden).
Eintragen der PID in SID (wenn Prozess mit CoW bereits in SID vorhanden, dieser beitreten, sonst neue).

Lesender Zugriff: kein Pagefault, PTE.Base Adressen aller Processe zeigen auf selben physikalischen Speicher .

Schreibender Zugriff:
PageFault.
Pruefen ob aufgrund von writeable 0, und ob shared 1.
Wenn ja, dann CoW Situation.
Aus eigener PID und share_list den CoW Typ ermittlen.
CoW 0 .. Access Error
CoW 1 .. lokale Speicherkopie des aktuellem Abbildes von PTE.Base Adresse erstellen,
PTE.Base Adresse auf lokale Kopie zeigen lassen und shared auf 0 setzen.
Nur tun, wenn auch tatsächlich mit jemandem geshart wird.

Freigabe von Shared Memory (shared Flag 1):
Wenn CoW 0, prüfen ob Seite mit jemandem geshart wird, wenn nein nur eigene PTE löschen (Shared = 0),
sonst physikalische Kopie löschen.

Es reicht hier in der IPT eine PID (irgendeine der entsprechenden SID) zu speicher.
Wenn nun ein Swap Ereigniss auftritt, kann ueber die virtuelle Page und die PID die SID und somit alle anderen PIDs mit denen geshared wird ermittelt werden.
Es muss also gar keine Information für den Swap Bereich gespeichert werden, da bei SwapIn ja die virtuelle Page und die PID bekannt ist und das selbe möglich ist.

Bei Swap Out also prüfen ob virtuelle Page Shared=1,
dann über share_list_ alle PIDs in SID ermitteln und das
Present, Swapped Flag und die Base Adresse zu allen
(wo Shared=1) propagieren.

Copy On Write

Bei Copy On Write werden alle PTEs kopiert und die Einträge zu den zu kopierenden Pages auf read only gesetzt. Somit wird beim ersten Schreibzugriff von egal welchem Prozess ein Pagefault auftreten. Bei diesem Pagefault muss eine Kopie für den schreibenden Prozess erstellt werden und die Page des schreibenden Prozesses wieder auf writeable gesetzt werden. Genauer Ablauf siehe Shared Memory mit CoW als Sonderfall.

Appendix

Implementationsdetails

Neue Klassen

• PRAThread - Thread der die Timestamps aktualisiert und Seiten zum Swappen markiert
• IptManager - Verwaltet eine Liste mit Metadaten zu jeder Seite im RAM
• ShareManager - Regelt gemeinsamen Speicherzugriff
• SwapManager - Verwaltet Swappartition und Cached Seiten auf der Swappartition und stellt eine reservierte Seite dem PageManager zur Verfügung
• Random - Generiert Pseudorandomisierte Zahlen
• Elf - Definiert ELF Struktur

Grobe Änderungen

• ArchMemory
  • getFreeVirtualMem - such ab der oberen Grenze vom Userspace hinab bis eine Lücke gefunden wurde, die groß genug ist
  • checkAdressValid - Page ist im Virtuellen Speicher verfügbar falls present oder iomapped oder swapped
• Loader
  • loadOnePageFromMemMappedFile - wird bei pagefault mit iomapped flag aufgerufen, page wird angefordert, gemapped und inhalt von datei wird geladen falls offset innerhalb der datei
• Scheduler
• Syscall
• UserProcess
• PageManager

Scheduler

Hält jetzt eine List processlist_; dazugehörige Funktionen sind: void addToProcessList(UserProcess* to_add); void removeFromProcessList(uint32 pid); UserProcess* getProcessFromList(uint32 pid);

Neue Attribute/Methoden in UserProcess

• processpagefaults_ = Anzahl der pagefaults (je Prozess)
• processruntime_ = Counter, der jedes Mal, wenn der Prozess dran kommt, hochzählt
• tau_ = Tau des jeweiligen Processes

• getruntime()
• increaseruntime()
• getpagefaults()
• increasepagefaults()
• checkprocesstau()
• getprocesstau()
• setprocesstau()

Änderungen

• paging-definitions
• InterruptUtils
• debug.h
• UserProcess
• MountMinix
• main.cpp

Neue Libc Bibliotheksfunktion

• /libc/src/vscalls.c

Neue Tests

Zum Testen sind in der main.cpp Testfaelle einzukommentieren. (Siehe main.cpp bzw README fuer Anleitung)

• stats.sweb: gibt verschiedene Statistiken ueber das System aus. Dazu wird stdin-test benoetigt, da von diesem Statistiken ausgeben werden. Nach beenden von stats.sweb kann dieses noch einmal von der Konsole gestartet werden
• swap1000.sweb: Zeigt ein ausfuehrliches Swapverhalten mit verschiedenen Statistiken, mit inkludiertem fork und cow.
• cowtest.sweb: Zeigt das neue Verhalten wobei bei einem fork nicht sofort der gesamte Speicher kopiert wird.
• memiotest.sweb: Ein erstelltes Textfile wird in den Speicher gemappt, gelesen, geandert, und wieder zuruckgeschrieben.
• ondemandmemio.sweb: Zeigt impizit das on demand paging Verhalten des Memory Mapped IO.
• memiomultiproc1.sweb: Zeigt Interprozesskommunikation mithilfe eines gemeinsam gemappten Files.
• sharedmem.sweb: Demonstriert Interprozesskommunikation ueber gesharte Pages.
• fork-stress.sweb: CoW Verhalten mit unbegrenzten Forks.

Neue Syscalls

• sc_share(arg1, arg2) wenn die sid noch nicht existiert wird eine share in der share_map erstellt mit den page welche dafür allokiert wurden und dem useprocess. wenn die sid existiert wird dem share eintrag eine share struct hinzugefügt
• sc_unshare(arg1)
• sc_stats(arg1, arg2) #pagefaults, #pages_in_ram, #pages_in_swap, #pages_ram_free, #pages_swap_free
• sc_fmap(uint32 fildes, uint32 len, uint32 prot, uint32 flags) - speicherstelle wird gesucht (fd, #bytes, #pages, prot) wird in UserProcess::file_map_list gespeichert, IOMAPPED wird gesetzt, pointer zurückgeliefert
• sc_funmap(arg1) - es wird der passende eintrag zum pointer gesucht (dieser muss auf die erste page zeigen), alle pages werden unmapped (PTE gelöscht)
• sc_fmapflush(arg1) - der inhalt im speichert wird aufs file geschrieben

Änderungen Syscalls

• execve arg wird nicht mit angegeben
• pthread_create to_create wird nicht mit angegeben
• pthread_join return_val wird nicht mit angegeben