prOSt primitive Operating System trial

Dokumentation

VP OPERATING SYSTEMS UNIV.-PROF. DR. CHRISTOPH KIRSCH

RENE LEIKERMOSER

CHRISTINA LANGREITER

ASTRID STOLLNBERGER

Universität Salzburg, 09.02.2007

prOSt Dokumentation

2

INHALTSVERZEICHNIS

1. EINLEITUNG ................................................................................................................................................. 3

2. ABSTRACT .................................................................................................................................................... 4

3. ENVIRONMENT............................................................................................................................................. 6

3.1 BOCHS .................................................................................................................................................. 6

3.2 PINTOS ................................................................................................................................................. 7

3.3 PROST .................................................................................................................................................. 8

3.4 GDB/DDD............................................................................................................................................... 8

3.5 ECLIPSE/CDT ........................................................................................................................................ 8

4. PROJEKT 1: THREADS ................................................................................................................................. 9

4.1 ALARM CLOCK.................................................................................................................................... 13

4.2 PRIORITY SCHEDULING ...................................................................................................................... 14

4.3 PRIORITY DONATION .......................................................................................................................... 15

5. PROJEKT 2: USER PROGRAMS................................................................................................................... 20

5.1 ARGUMENT PASSING........................................................................................................................... 23

5.2 SYSTEM CALLS ................................................................................................................................... 24

6. PROJEKT 3: VIRTUAL MEMORY ............................................................................................................... 27

6.1 SUPPLEMENTAL PAGE TABLE ............................................................................................................ 28

6.2 FRAME TABLE ALLOCATOR ................................................................................................................ 29

6.3 SWAP TABLE....................................................................................................................................... 30

6.4 PAGE FAULT HANDLER ...................................................................................................................... 31

6.5 STACK GROWTH.................................................................................................................................. 32

6.6 MEMORY MAPPED FILES ................................................................................................................... 32

6.7 PAGE REPLACEMENT ALGORITHM ..................................................................................................... 34

7. TESTS ......................................................................................................................................................... 36

8.1 PROJEKT 1: THREADS......................................................................................................................... 36

8.2 PROJEKT 2: USER PROGRAMS ............................................................................................................ 47

8.3 PROJEKT 3: VIRTUAL MEMORY .......................................................................................................... 48

8. CONCLUSIO ................................................................................................................................................ 49

9. QUELLEN.................................................................................................................................................... 50

prOSt Dokumentation

3

1. EINLEITUNG Bevor wir mit der Dokumentation unseres Betriebssystems beginnen, möchten wir uns gerne vorstellen und einen kleinen Überblick über die Vorlesung „Operating Systems“, sowie die Aufgabe, die uns dort gestellt wurde, geben. Wir sind drei Studenten der Universität Salzburg und nehmen dieses Semester an der Vorle-sung „Operating Systems“ unter der Leitung von Prof. Dr. Christoph Kirsch teil. Diese Vorle-sung ist eine Pflichtlehrveranstaltung im Rahmen des Magisterstudiums „Angewandte Infor-matik“. Sie soll uns eine Einführung in folgende Betriebsystem-Konzepte geben: Prozesse und Threads, Deadlocks, Speicherverwaltung, Input/Output, Filesysteme und Multiprozessor-systeme. Dabei orientiert sich Prof. Kirsch am Buch „Moderne Betriebssysteme“ von A. Ta-nenbaum. Das Ziel dieser Vorlesung ist, dass die Teilnehmer die prinzipielle Konstruktion von Betriebs-systemen verstehen, mit einem Fokus auf fundamentale und erweiterte Konzepte. Um das zu erreichen wurde uns im Rahmen dieser Lehrveranstaltung folgende Aufgabe gestellt: Teams of 2-3 students will be asked to design and implement (in user space) their own operat-

ing system in a programming language of their choice. The operating system must at least

include some form of concurrency support, memory management, device abstraction, and file

handling.

Das Ziel ist es durch diese praktische Erfahrung des Designs und der Implementierung eines Betriebssystems zu lernen, wie Nebenläufigkeit, Speicherverwaltung, Geräteabstraktion und Dateibehandlung funktionieren. Da es sehr schwierig ist alle Fachausdrücke bedeutungsgemäß zu übersetzen, behalten wir es uns vor in unserer Dokumentation die englischen Fachbegriffe zu verwenden. Für alle Leser, die nicht wissen, was genau ein Betriebssystem ist bzw. welche Aufgabe es hat, möchten wir an dieser Stelle eine kurze Definition anführen. Die meisten Rechnerbenutzer haben bereits gewisse Erfahrungen mit einem Betriebssystem gemacht, aber in der Regel ist es schwer ein Betriebssystem genau zu definieren. Ein Teil des Problems besteht darin, dass Betriebssysteme zwei an sich unabhängige Funktionen durchfüh-ren. Einerseits ist dies die Erweiterung der Hardware und zum anderen die Verwaltung von Ressourcen: Ein modernes Rechensystem besteht aus einem oder mehreren Prozessoren, Arbeitsspeicher, Platten, Druckern, einer Tastatur, einem Bildschirm, Netzwerkschnittstellen und anderen Ein-/Ausgabegeräten. Alles in allem handelt es sich um ein komplexes System. Die Erstellung von Programmen, die diese Komponenten verwalten und sie korrekt benutzen, ist eine extrem schwierige Aufgabe, selbst dann, wenn man von optimalen Lösungen absieht. Aus diesem Grund wurden Computer mit einer zusätzlichen Softwareschicht ausgestattet, die man Be-triebssystem nennt. Dessen Aufgabe ist es, vorhandene Geräte zu verwalten und Benutzerpro-grammen eine einfache Schnittstelle zur Hardware zur Verfügung zu stellen. (siehe [1], Kapitel 1)

prOSt Dokumentation

4

2. ABSTRACT Das Ziel dieses Projektes ist es ein einfaches Betriebsystem zu implementieren, um grundle-gende Techniken, wie Nebenläufigkeit, Synchronisationsprimitiven, Speicherverwaltung, Geräteabstraktion und Dateibehandlung anhand einer praktischen Übung verstehen zu lernen. Unser Betriebssystem wird in einer virtuellen Maschine laufen. Als virtuelle Maschine haben wir Bochs ausgewählt, das eine vollständige x86-Architektur emuliert. Wir haben uns dazu entschlossen unser Betriebsystem auf einem bereits bestehenden Be-triebssystem-Framework namens Pintos aufzubauen. Dieses unterstützt bereits Kernel-Threads, das Laden und Ausführen von Benutzerprogrammen und ein Filesystem. All diese Features sind aber nur minimal und in sehr einfacher Ausführung implementiert. Unsere Aufgabe ist es im Rahmen von 4 Teilprojekten diese Features zu erweitern, sowie ein weiteres in Form von virtuellem Speicher hinzuzufügen. Im Inhaltsverzeichnis auf Seite 2 kann man anhand der Unterpunkte von Kapitel 4 bis

Kapitel 7 auf den ersten Blick sehen, welche Features wir in unserem Betriebssystem

implementiert haben bzw. implementieren werden.

Für unser eigenes Verständnis und für diejenigen, die in den grundlegenden Techniken, die in Betriebssystemen verwendet werden nicht sattelfest sind, haben wir in unserer Dokumentation auch ein wenig Theorie miteinfließen lassen. Für noch detailliertere Informationen möchten wir auf die Dokumentation von Pintos [6] verweisen. Im ersten Projekt geht es darum ein Thread-System mit besonderem Fokus auf Nebenläufig-keit und Synchronisation zu implementieren. Pintos stellt bereits ein Thread-System mit mi-nimaler Funktionalität bereit. Dieses unterstützt Thread-Erzeugung, Thread-Beendigung, ei-nen einfachen Scheduler sowie Synchronisationsprimitiven in Form von Semaphoren, Locks und Zustandsvariablen. Unsere Aufgabe besteht darin diese Funktionalität zu erweitern, um ein besseres Verständnis für Synchronisationsprobleme zu erlangen. Im zweiten Projekt geht es darum, unserem Betriebssystem zu erlauben, Benutzerprogramme auszuführen. Pintos unterstützt bereits das Laden und Ausführen von Benutzerprogrammen, aber keinerlei Input bzw. Output und Interaktion ist möglich. Unsere Aufgabe in diesem Pro-jekt besteht darin, den Programmen zu erlauben mit dem Betriebssystem mittels System-Calls zu kommunizieren. Ein besonderer Fokus liegt in diesem Projekt auf dem Zugriff auf den virtuellen Speicherbereich von Benutzerprogrammen sowie auf den des Kernels. Da Benutzerprogramme aus einem Dateisystem geladen werden und viele System-Calls ein Dateisystem benutzen wurde ein solches bereits von Pintos zur Verfügung gestellt, allerdings in einer sehr einfachen aber dennoch kompletten Ausführung. In Projekt 3 wird das Hauptaugenmerk auf den Hauptspeicher gelegt, genauergesagt auf den virtuellen Speicher. Bis jetzt war die Anzahl und Größe der Programme, die ausgeführt wer-den können auf die Größe des Hauptspeichers limitiert. Unsere Aufgabe besteht jetzt darin, diese Einschränkung aufzuheben, indem nur die Teile eines Programms im Hauptspeicher gehalten werden, die gerade benötigt werden. Auf diese Ein- bzw. Auslagerung von Pro-grammteilen bzw. die Abbildung von virtuellem auf physischen Speicher werden wir uns hier konzentrieren.

prOSt Dokumentation

5

In Projekt 4 soll das von Pintos zur Verfügung gestellte Filesystem um einige Funktionalitä-ten erweitert werden. Diese umfassen zB erweiterbare Dateien und das Erlauben von Unter-verzeichnissen. Projekt 4 wurde von uns nicht implementiert.

prOSt Dokumentation

6

3. ENVIRONMENT

3.1 BOCHS Pintos ist nach dem kompilieren auf realer Hardware lauffähig. Da durch diese Vorgehens-weise Pintos (prOSt) jedoch extrem umständlich zu debuggen wäre – nach jedem Kompilier-vorgang müsste das Betriebssystem auf eine freie Festplattenpartition eines realen Computers aufgespielt werden und der PC danach neu gebootet werden – haben wir uns entschlossen unser Betriebssystem in einer virtuellen Maschine im user-space laufen zu lassen. Diese virtu-elle Maschine emuliert eine vollständige x86-Architektur, ein debuggen unseres Betriebssys-tems gestaltet sich dadurch wesentlich einfacher, da die virtuelle Maschine direkt aus dem Betriebssystem heraus gestartet werden kann. Als virtuelle Maschine kam dabei bochs [2] zum Einsatz, bochs lief unter einer openSuSE-Linux Umgebung in der Version 10.1 [3]. Die Installation und das Setup von bochs und pintos erwies sich nicht gerade als trivial, wes-halb wir hier nochmals einen Überblick dazu geben möchten, um somit allen interessierten eine Möglichkeit zu geben unser Betriebssystem zu testen, ohne schon an der ersten größeren Hürde zu scheitern. 1. Es wird der Quellcode von bochs in der Version 2.2.6 benötigt. Diese Version kann von

der bochs-Homepage unter [4] heruntergeladen werden.

2. Bei Verwendung von gcc ab der Version 4.1.0 sind die Quelldateien von bochs wie folgt zu patchen (die gcc-Version erhält man, indem man in einer Shell den Befehl gcc –v ein-gibt):

3. Danach kann Bochs mithilfe des Installationsskriptes unter $PINTOSDIR/src/misc/bochs-2.2.6-build.sh kompiliert und installiert werden. $PINTOSDIR bezieht sich auf das Ver-zeichnis, in dem Pintos extrahiert wurde.

Windows XP

VMware

openSuSE Linux

Bochs

prOSt

Pintos

prOSt Dokumentation

7

4. Gegebenenfalls müssen noch verschiedene Headerfiles nachinstalliert werden (z.b. ncur-

ses, X11).

3.2 PINTOS Pintos, das prOSt zugrundeliegende Betriebssystem kann von [5] heruntergeladen werden. Nach dem entpacken kann Pintos mit einem, von uns geschriebenen Skript kompiliert werden (dieses Skript befindet sich ebenfalls im tarball): #!/bin/bash

PROSTPATH=´pwd´

export PATH=$PATH:$PROSTPATH/utils

export PATH=$PATH:$PROSTPATH/misc

cd $PROSTPATH/userprog

make

cd $PROSTPATH/userprog/build

pintos-mkdisk fs.dsk 2

pintos -f -q

pintos -p $PROSTPATH/examples/echo -a echo -- -q

pintos -p $PROSTPATH/examples/ls -a ls -- -q

pintos -p $PROSTPATH/examples/text.txt -a text.txt -- -q

pintos -q run 'echo x'

pintos ls

pintos cat text.txt

Diff:

--- ./iodev/hdimage.h~ 2006-03-15 15:08:02.000000000 +0000

+++ ./iodev/hdimage.h 2006-03-15 15:10:18.000000000 +0000

@@ -272,16 +272,8 @@

off_t total_size;

void panic(const char * message);

- off_t

-#ifndef PARANOID

- sparse_image_t::

-#endif

- get_physical_offset();

- void

-#ifndef PARANOID

- sparse_image_t::

-#endif

- set_virtual_page(Bit32u new_virtual_page);

+ off_t get_physical_offset();

+ void set_virtual_page(Bit32u new_virtual_page);

void read_header();

ssize_t read_page_fragment(Bit32u read_virtual_page, Bit32u read_page_offset, size_t read_size, void * buf);

prOSt Dokumentation

8

3.3 PROST Da prOSt auf Pintos basiert, beziehen sich die obigen Angaben zum Starten von Pintos unter bochs natürlich gleichzeitig auch auf das Starten von prOSt unter bochs.

3.4 GDB/DDD Zum debuggen haben wir gdb eingesetzt (siehe [7]). Zeitweise haben wir auch das grafische Frontend ddd [8] zum debuggen benutzt. Ein Beispiel für ein Skript, das einen Debuglauf startet: #!/bin/bash

PROSTPATH=´pwd´

export PATH=$PATH:$PROSTPATH/utils

export PATH=$PATH:$PROSTPATH/misc

cd $PROSTPATH/userprog

make

cd $PROSTPATH/userprog/build

pintos -v --gdb -- -q run 'echo hallo du'

3.5 ECLIPSE/CDT Als Entwicklungsumgebung haben wir die Eclipse-IDE [9] mit der C-Erweiterung cdt [10] verwendet.

prOSt Dokumentation

9

4. PROJEKT 1: THREADS Im ersten Projekt geht es darum ein Thread-System mit besonderem Fokus auf Nebenläufig-keit und Synchronisation zu implementieren. Pintos stellt bereits ein Thread-System mit mi-nimaler Funktionalität bereit. Unsere Aufgabe besteht darin diese Funktionalität zu erweitern, um ein besseres Verständnis für Synchronisationsprobleme zu erlangen. Die Implementierung dieses Projektes findet größtenteils in folgenden Arbeitsverzeichnissen bzw. Dateien statt:

- „devices“: timer.c - „threads“: thread.c, synch.c - „lib/kernel“: list.c

Folgende Komponenten werden von Pintos zur Verfügung gestellt:

- Thread-Erzeugung - Thread-Beendigung - ein einfacher Scheduler - Synchronisationsprimitiven: Semaphoren, Locks, Zustandsvariablen

THREAD-SYSTEM

Threads werden in Pintos als Struktur mit folgenden Feldern dargestellt. Wir führen hier nur die Felder an, die für das erste Projekt am wichtigsten sind. Natürlich werden im Laufe der Implementierung von uns noch einige Felder hinzugefügt. struct thread

{

/* Owned by thread.c. */

tid_t tid; /* Thread identifier. */

enum thread_status status; /* Thread state. */

...

int priority; /* Priority. */

/* Shared between thread.c and synch.c. */

struct list_elem elem; /* List element. */

...

...

}

Jeder Thread bekommt eine einzigartige Identifikationsnummer zugewiesen. Die Priorität eines Threads wird bei der Thread-Erzeugung als Parameter mitgegeben. Sie kann zwischen 0 und 63 liegen und ist defaultmäßig immer 31. Ein Listenelement besteht aus einem Pointer auf seinen Vorgänger und seinen Nachfolger. Dadurch kann man doppelt-verlinkte-Listen implementieren, wie es z.B. die Ready-Queue eine ist. Pintos stellt bereits die Infrastruktur für solche Listen bereit, diese findet man unter „lib/kernel/list.c“. Es existieren sehr hilfreiche Methoden z.B. zum Durchlaufen von Listen oder Einfügen und Löschen von Listenelementen. Nun wollen wir näher auf die möglichen Zustände von Threads und deren Übergänge einge-hen. Ein Thread kann folgende Zustände haben: running, blocked, ready und dying. Die nachfolgende Grafik visualisiert die möglichen Zustandsübergänge:

prOSt Dokumentation

10

1. Der Zustandsübergang von blocked zu ready wird in Pintos durch den von uns eingeführten Reactor realisiert, welcher im Abschnitt 4.1 erklärt wird. Damit ein Thread blockiert, muss als erstes der thread_block()-Funktionsaufruf ausgeführt werden. Soll der Thread dann wieder in die Ready-Queue eingereiht werden, muss thread_unblock() mit dem Thread als Parameter aufgerufen werden. 2. Den Zustandsübergang von ready zu running übernimmt der Scheduler. Er wählt einen Thread aus der Ready-Queue aus und lässt ihn laufen. Der Scheduler wird dabei in thread_yield() aufgerufen. 3. Der Übergang von blocked nach running ist nötig, wenn ein Thread dringend die CPU be-nötigt, der Scheduler wird dabei übergangen. In Pintos wird dieser Zustandsübergang nicht implementiert. 4. Wiederum der Scheduler übernimmt den Übergang von running nach ready. Der laufende Thread wird dabei von einem Thread aus der Ready-Queue abgelöst und wird selber in die Ready-Queue eingereiht. Das geschieht beim Aufruf von thread_yield(). 5. Soll ein laufender Thread blockiert werden, wird thread_block() aufgerufen. Der Thread wird solange blockiert, bis wieder thread_unblock() aufgerufen wird. An dieser Stelle wollen wir für ein besseres Verständnis die wichtigsten Funktionen für Thread-Systeme anführen, die bereits von Pintos implementiert wurden. Für mehr Details möchten wir hier auf den Reference-Guide (Anhang A) von Pintos verweisen. Die meisten dieser Implementierungen werden von uns später natürlich modifiziert werden (siehe Abschnitt 4.1 und 4.2). void thread_init (void){...}

Diese Funktion initialisiert das Thread-System und wird in der main()-Methode aufgerufen. Es wird der Anfangs-Thread, sowie die Ready-Queue erstellt.

running

ready

blocked

1.

2.

3.

4.

5.

prOSt Dokumentation

11

void thread_start (void){...}

Diese Funktion wird ebenfalls von der main()-Methode aufgerufen. Ihre Aufgabe ist es das preemptive Scheduling zu starten, den idle-Thread zu erstellen und die Interrupts einzuschal-ten. Der idle-Thread läuft immer, wenn sich kein Thread in der Ready-Queue befindet. tid_t thread_create (const char *name, int priority,

thread_func *function, void *aux) {…}

Hier wird ein neuer Thread erstellt und in die Ready-Queue gegeben, der eine Funktion func-tion(aux) ausführt, die als Parameter übergeben wird. void thread_block (void) {...}

Mit Hilfe dieser Methode wird der laufende Thread blockiert und es wird ein anderer Thread vom Scheduler ausgewählt. Der blockierte Thread läuft erst wieder weiter, wenn unblock() mit ihm als Parameter aufgerufen wird. void thread_unblock (struct thread *t) {...}

Diese Funktion reiht einen vorher blockierten Thread wieder in die Ready-Queue ein. void thread_exit (void) {...}

Hier wird der laufende Thread für immer beendet. void thread_yield (void) {...}

Diese Methode dient dazu den laufenden Thread in die Ready-Queue einzureihen und einen anderen Thread zu schedulen. Es kann natürlich sein, dass vom Scheduler wieder genau dieser Thread ausgewählt wird. Das kann zu aktivem Warten führen. static void schedule (void) {...}

Dieser einfache Scheduler kontrolliert, ob der laufende Thread seinen Status gerade geändert hat und wählt daraufhin den nächsten Thread in der Ready-Queue als laufenden Thread aus. Unsere Aufgabe wird es sein daraus einen prioritätsbasierten Scheduler zu implementieren. (siehe Abschnitt 4.2). Als nächstes möchten wir einen kleinen Überblick über die implementierten Synchronisati-onsprimitiven geben. SEMAPHOREN

Folgende Struktur repräsentiert einen Semaphor mit einem nicht-negativen Integer-Wert und einer Liste von Threads, die auf den Semaphor warten. struct semaphore

{

unsigned value; /* Current value. */

struct list waiters; /* List of waiting threads. */

};

void sema_init (struct semaphore *sema, unsigned value) {...}

Mit diesem Methodenaufruf wird ein Semaphor mit dem übergebenen Wert initialisiert. void sema_down (struct semaphore *sema) {...}

Diese Methode wartet so lange, bis der Wert des Semaphor positiv wird und dekrementiert ihn dann um 1. So lange der Wert des Semaphors 0 ist wird der Thread, der auf den Semaphor wartet in die Warteliste eingereiht und blockiert.

prOSt Dokumentation

12

void sema_up (struct semaphore *sema) {...}

Hier wird der Wert des Semaphors um 1 inkrementiert und der erste Thread in der Warteliste des Semaphors wieder in die Ready-Liste eingereiht. LOCKS

Folgende Struktur repräsentiert eine Sperre mit einem Zeiger auf den Thread, der die Sperre hält und einen Semaphor, der den Wert 1 annimmt, falls die Sperre betreten werden kann und 0, falls sie belegt ist. Es werden im Laufe der Priority-Donation-Implementierung (siehe Ka-pitel 4.3) noch Felder hinzugefügt. struct lock

{

struct thread *holder; /* Thread holding lock (for debugging). */

struct semaphore semaphore; /* Binary semaphore controlling access. */

};

void lock_init (struct lock *lock) {...}

Mit Hilfe dieser Methode wird eine neue Sperre initialisiert. Bei der Initialisierung wird die Sperre noch von keinem Thread gehalten und der Wert des Semaphors beträgt 1. void lock_acquire (struct lock *lock) {...}

Mittels dieser Methode ist es dem aufrufenden Thread möglich eine Sperre zu betreten. Er muss aber warten, bis die Sperre vom aktuellen Halter freigegeben wird, bis dahin wird er blockiert. In dieser Methode erfolgt außerdem der sema_down()-Aufruf, um den Semaphor auf 0 zu setzen, falls der anfragende Thread zum Halter wird. void lock_release (struct lock *lock) {...}

Hier gibt der aufrufende Thread die Sperre wieder frei, indem sema_up() aufgerufen wird und der Semaphor auf 1 gesetzt wird. Ein Thread kann eine Sperre nur dann freigeben, wenn er Halter dieser Sperre ist. ZUSTANDSVARIABLEN

Folgende Struktur repräsentiert eine Zustandsvariable, die aus einer Liste von wartenden Threads besteht. struct condition

{

struct list waiters; /* List of waiting threads. */

};

void cond_init (struct condition *cond) {...}

Mit dieser Methode wird eine neue Zustandsvariable initialisiert. void cond_wait (struct condition *cond, struct lock *lock) {...}

In dieser Methode wird die Sperre freigegeben und auf das Signal gewartet, das mitteilt, dass der Zustand, auf den man wartet, eingetroffen ist. Wird dieses Signal empfangen, wird wieder versucht mit acquire_lock() die Sperre zu erhalten. void cond_signal (struct condition *cond, struct lock *lock) {...}

Hier wird ein Thread wieder geweckt, der auf die übergebene Zustandsvariable wartet, die von der übergebenen Sperre geschützt wird. Diesen Methodenaufruf kann nur der Halter die-ser Sperre durchführen.

prOSt Dokumentation

13

4.1 ALARM CLOCK Unsere erste Aufgabe bestand darin die Alarm-Clock zu reimplementieren. Der Nachteil der vorherigen Implementierung lag darin, dass es zu aktivem Warten gekommen ist, wenn ein Thread für einige Zeit schlafen sollte. Der Thread kontrollierte in einer Schleife ständig, ob die Zeit bereits abgelaufen ist, falls nein, wurde einfach mit thread_yield() ein anderer Thread gescheduled. Wir mussten folgende Funktion modifizieren: void timer_sleep (int64_t ticks) {...}

Wenn diese Funktion aufgerufen wurde, wurde die Ausführung des laufenden Threads um die gewünschte Anzahl von Ticks verzögert. Damit es nicht mehr zu aktivem Warten kommt, haben wir als erstes eine neue Queue einge-führt, die Blocked-Queue. Immer, wenn ein Thread timer_sleep() aufruft, wird er mind. für die gewünschte Anzahl von Ticks in diese Queue eingereiht. Dann blockiert der Thread. Um sich die Start-Zeit des „Schlafenlegens“ sowie die Dauer des „Schlafens“ zu merken ha-ben wir jedem Thread zwei neue Felder gegeben: struct thread

{

...

int64_t ticks; /* ticks to sleep */

int64_t start; /* sleeping start */

...

}

Jetzt kümmert sich der so genannte Reactor um den blockierten Thread in der Blocked-Queue: static void reactor (void){...}

Die Aufgabe des Reactors ist es die Blocked-Queue ständig zu durchlaufen und nach Threads zu suchen, die schon lange genug geschlafen haben und wieder aufwachen sollen. Dabei ver-gleicht er die Zeit, die seit dem „Schlafenlegen“ vergangen ist mit der Anzahl der Ticks, die geschlafen werden sollen. Falls die Zeit bei einem Threads abgelaufen ist, wird er aus der Blocked-Queue entfernt und es wird unblock() aufgerufen. Dadurch wird er wieder in die Ready-Queue eingereiht und kann somit gescheduled werden. Der Reactor wird immer zusammen mit dem Scheduler aufgerufen, also in folgenden Metho-den: thread_yield(), thread_block(), thread_exit(); Da wir anschließend einen prioritätsorientierten Scheduler implementieren müssen, ist es wichtig, dass die Einreihung in die Blocked-Liste mit absteigender Priorität erfolgt. Dadurch werden die höherprioritären Threads als erstes aufgeweckt. Das prioritäre Einreihen wird in folgender Funktion implementiert: void put_in_blocked_list (struct thread *t) {...}

Die Ergebnisse der Tests für den korrekten Ablauf der Alarm-Clock sind im Abschnitt 8.1 zu finden. Wir haben für dieses Projekt folgende Methoden in den folgenden Dateien bearbeitet bzw. hinzugefügt: lib/kernel/list.c:

prOSt Dokumentation

14

readylist_empty()

readylist_pop_front()

threads/thread.c:

thread_init()

reactor()

next_thread_to_run()

void traverse_list(struct list *list);

void traverse_ready_list(void);

devices/timer.c:

timer_sleep()

4.2 PRIORITY SCHEDULING Unsere zweite Aufgabe bestand darin, in Pintos prioritätsbasiertes Scheduling einzuführen. Das heißt, immer wenn ein Thread in die Ready-Queue eingereiht wird, der eine höhere Prio-rität hat, als der laufende Thread, wird der Prozessor dem höherprioritären Thread überlassen. Um das zu erreichen war unser erster Schritt, die Ready-Queue zu reimplementieren. Da es in Pintos 64 Prioritäten gibt, wobei 0 am niedrigsten und 63 am höchsten ist, haben wir uns dazu entschieden auch 64 verschiedene Ready-Queues zu verwenden. Die neue Ready-Queue wird also in Form eines Arrays bestehend aus 64 Strukturen vom Typ Liste implementieren. Jede dieser Listen entspricht einer Priorität. Durch die Indizes des Arrays kann man bei dieser Va-riante sehr gut auf die einzelnen prioritätsbasierten Ready-Queues zugreifen, und man benö-tigt keinen Algorithmus für das absteigende Sortieren der Liste. Generell muss jetzt beim Einfügen in die Ready-Queues genau darauf geachtet werden, dass auch jeder Thread gemäß seiner Priorität in die richtige Queue eingefügt wird. Als nächstes wurde die unblock()-Methode so modifiziert, dass jedes Mal, nachdem der Thread wieder in die Ready-Queue eingefügt wird, kontrolliert wird, ob dieser nicht eine hö-here Priorität, als der laufende Prozess hat. Falls ja, wird thread_yield() aufgerufen. Um aus dem einfachen Scheduler einen Priority-Scheduler zu erstellen, mussten wir nur si-cherstellen, dass der nächste Thread, der gewählt wird, der höchstprioritäre der gesamten Ready-Queues ist. Dabei wird einfach das Array von hinten beginnend durchlaufen und das erste Element ausgegeben, da ja das Array bereits sortiert ist. Folgende Funktion musste dafür angepasst werden: static struct thread *next_thread_to_run (void) {...}

Ein Thread kann seine eigene Priorität jederzeit erhöhen oder senken. Im letzteren Fall muss er aber sofort den Prozessor abgeben, falls er danach nicht mehr der Thread mit der höchsten Priorität ist. Das wurde in folgender Methode realisiert: void thread_set_priority (int new_priority) {...}

Dabei wird die Priorität des laufenden Threads neu gesetzt. Ist sie niedriger als der höchstpri-oritäre Thread in der Ready-Queue wird sofort thread_yield() aufgerufen. Als nächstes mussten wir uns um die Synchronisationsprimitiven kümmern. Warten Threads auf eine Lock, Semaphore oder Zustandsvariable, muss der wartende Thread mit der höchsten Priorität als erstes aufgeweckt werden.

prOSt Dokumentation

15

Dafür mussten folgende Funktionen modifiziert werden: void sema_down (struct semaphore *sema) {...}

Hier wird der Thread, der auf die Semaphore wartet, gleich an der richtigen Stelle in der War-teliste eingefügt. Es wird folgender Algorithmus verwendet: Ist die Warteliste leer, wir der Thread am Anfang eingefügt. Ansonsten wird die Warteliste durchlaufen bis ein Thread gefunden wird, der eine kleinere Priorität hat als der Thread, der eingefügt werden soll. Daraufhin wird dieser Thread vor dem Thread mit der kleineren Priori-tät eingefügt. Wird kein Thread mit einer kleineren Priorität gefunden, wir der einzufügende Thread hinten an die Liste angefügt. Da die Methode sema_up() als nächsten Thread immer den ersten Thread der Warteliste aus-wählt und die Warteliste absteigend sortiert wird, wird sichergestellt, dass immer der Thread mit der höchsten Priorität die Semaphore bekommt. void cond_wait (struct condition *cond, struct lock *lock) {...}

Dasselbe Prinzip wie bei sema_down() wurde hier verwendet. Die Threads die auf eine Zu-standsvariable warten, werden gleich an der richtigen Stelle in der Warteliste eingefügt und diese wird somit der Priorität nach absteigend sortiert. Die Methode cond_signal() wählt wieder den ersten Thread der Warteliste aus. Die Ergebnisse der Tests für den korrekten Ablauf des Priority-Scheduling sind im Abschnitt 8.1 zu finden. Wir haben für dieses Projekt folgende Methoden in den folgenden Dateien bearbeitet: threads/thread.c:

thread_unblock()

thread_set_priority()

threads/sync.c:

sema_down()

cond_wait()

lock_acquire()

4.3 PRIORITY DONATION Ein wichtiger Punkt beim prioritätsbasierten Scheduling ist die Prioritätsinversion. Wir möch-ten kurz ein Beispiel dafür nennen: Angenommen es existieren 3 Threads mit den Prioritäten 31, 32 und 33. Der Thread mit der Priorität 31 hält eine Lock auf die der Thread mit Priorität 33 wartet. Thread 32 ist in der Ready-Queue. Thread 33 kann also nicht weiterarbeiten, da Thread 31 keine CPU-Zeit be-kommt, diese wird Thread 32 gegeben. Die Lösung für dieses Problem heißt Priority-Donation. Dabei spendet jeder Thread, der eine höher Priorität hat als der Halter der Lock, auf die der Thread wartet, seine Priorität dem Hal-ter dieser Lock. Im Beispiel würde Thread 33 seine Priorität Thread 31 schenken. Somit kann dieser weiterarbeiten und anschließend die Lock für Thread 33 freigeben. Nach der Freigabe erhält Thread 31 wieder seine ursprüngliche Priorität. Priority-Donation wurde von uns nur für Locks eingeführt, nicht für Semaphoren oder Zu-standsvariablen.

prOSt Dokumentation

16

Unsere Aufgabe war es alle möglichen Situationen der Priority-Donation zu bedenken. Ein Punkt dabei waren mehrfache Prioritäts-Spenden. Angenommen ein Thread ist Halter von mehreren Locks und es gibt mehrere Threads, die nacheinander diese Locks erwerben wollen. In diesem Fall wird die Priorität des Lockhalters mehrmals erhöht. Wir dann eine Lock frei-gegeben muss die Prioritätserhöhung wieder in der Richtigen Reihenfolge rückgängig ge-macht werden. Um das zu realisieren, haben wir für jeden Thread ein extra Prioritäts-Feld, ein so genanntes „Donation-Array“, sowie einen Zähler für die Spenden, die man erhalten hat, eingeführt. Au-ßerdem bekommt jeder Thread einen Zähler für die Locks bei denen er der Halter ist: struct thread

{

...

int lockcounter; /* counts locks acquired*/

int donated_priority; /* priority in presence of

priority donation*/

int donationarray[100][100]; /* logs donations */

int donated; /* counter for donations */

...

}

Das Array ist zweidimensional, in seiner Größe beschränkt und es wird mit dem Wert -1 initi-alisiert, da weder die ID einer Lock noch die Priorität eines Threads diesen Wert annehmen kann. Jede Zeile steht für eine Sperre für die der Thread Halter ist. In die Spalten werden die aufsteigenden Prioritäts-Spenden für jede Sperre eingetragen. In der ersten Spalte jeder Zeile steht die Identifikationsnummer jeder Lock. Diese Nummer wurde von uns als zusätzliches Feld einer Lock-Struktur eingeführt. Jede Identifikationsnummer ist einzigartig und wird beim Initialisieren der Sperre vergeben. Das befüllen des Donation-Arrays und inkrementieren des Donation-Zählers wird in folgen-der Methode implementiert: void lock_acquire (struct lock *lock) {...}

Hat die Sperre, die hier als Parameter übergeben wird bereits einen Halter, wird kontrolliert, ob die Priorität des Threads, der die Sperre betreten will, größer ist, als die des derzeitigen Halters. Falls ja, wird die höhere Priorität an den Halter gespendet, d. h. das zusätzliche Prio-ritäts-Feld „donated_priority“ bekommt einen neuen Wert. Die ursprüngliche Priorität des Halters befindet sich immer noch im alten Prioritäts-Feld „priority“. Danach wird der Donati-on-Counter um eins erhöht und die gespendete Priorität in das Array eingetragen. Damit man immer die richtige aktuelle Priorität eines Threads ermitteln kann musste folgende Methode modifiziert werden: int thread_get_priority (void) {...}

Diese Methode gibt die Priorität des laufenden Threads aus. Es wird kontrolliert, ob der Do-nation-Zähler des Threads größer als 0 ist bzw. ob der Lock-Zähler größer als 0 ist, falls ja, weiß man, dass Prioritäten gespendet wurden und es wird das donated_priority-Feld zurück-gegeben. Ansonsten wird das normale priority-Feld ausgegeben. Es ist sehr wichtig, dass man immer über diese Methode auf die Priorität des laufenden Threads zugreift und nicht direkt über die entsprechenden Felder, da nur so gewährleistet werden kann, dass die richtige Priori-tät ausgegeben wird. Für ein besseres Verständnis des Aufbaus eines Donation-Arrays möchten wir ein kleines Beispiel anführen:

prOSt Dokumentation

17

Angenommen ein Thread mit der Priorität 31 ist Halter von drei Locks mit den IDs 13, 26 und 30. Ein Thread mit der Priorität 32 will auf Lock 13 zugreifen, ein thread mit Priorität 33 auf Lock 26, ein weiterer Thread mit Priorität 34 auf Lock 13 und anschließend ein Thread mit Priorität 35 auf Lock 30. Daraus ergibt sich folgendes Donation-Array für den Halter der drei Locks, der jetzt Priorität 35 hat:

13 32 34 26 33 -1 30 35 -1

Der Donation-Zähler steht jetzt auf 4. Gibt ein Thread eine Sperre frei, wird der mögliche neue Halter der Sperre in die Ready-Queue eingeordnet. Dieser neue Halter hat höchstens dieselbe Priorität wie der alte Halter. Danach wird der Lock-Zähler des alten Halters um eins dekrementiert, thread_yield() aufge-rufen und der neue Halter bekommt die Chance zu laufen. Das geschieht in folgender Methode: void lock_release (struct lock *lock) {...}

Jetzt muss der alte Halter der Sperre an die neue Situation angepasst werden, das heißt, es muss die entsprechende Zeile im Donation-Array gelöscht, der Donation-Zähler um die ent-sprechende Anzahl von Donations dekrementiert und dem Thread wieder die richtige Priorität zugewiesen werden. All das wird ebenfalls in der Methode lock_aquire implementiert: Es wird als erstes kontrolliert, ob der Donation-Zähler größer 0 ist. Ist das der Fall, weiß man, dass Prioritäten gespendet wurden, die möglicherweise rückgängig gemacht werden müssen. Es muss ermittelt werden, wie viele Prioritätsspenden rückgängig gemacht werden müssen, dazu zählt man die Prioritäten in der entsprechenden Zeile des Donation-Arrays und dekre-mentiert den Donation-Zähler genau um diese Anzahl. Ist jetzt der Donation-Zähler 0, bekommt der alte Halter der Lock seine ursprüngliche Priori-tät zurück. Das Donation-Array des alten Halters wird wieder neu initialisiert. Ist allerdings der Donation-Zähler immer noch größer 0, weiß man, dass der derzeitige Halter der Sperre nicht seine ursprüngliche Priorität zurückbekommt, sondern eine höhere, die ihm gespendet wurde. Man muss jetzt ermitteln, welche Priorität aus dem Donation-Array das ist. Dazu wird kontrolliert, welche Priorität der neue Halter der Sperre hat. Hat dieser dieselbe Priorität, wie der alte Halter, weiß man, dass das die höchste Priorität ist, die dem alten Halter gespendet wurde. Die entsprechende Zeile im Donation-Array kann also gelöscht werden und der alte Halter nimmt die höchste Priorität an, die sich danach im Donation-Array befindet. In diesem Fall übernimmt folgende Methode die Zuweisung der richtigen Priorität: int search_donationarray(struct thread *t, int priority){...}

Diese Methode sucht im Donation-Array von Thread t nach der Priorität priority, löscht dann die Zeile, in der diese Priorität gefunden wurde und gibt die höchste Priorität aus, die sich danach im Donation-Array befindet. Anschließend muss der alte Halter wieder an die richtige Stelle in der Ready-Queue eingeord-net werden. Kommen wir auf unser vorheriges Beispiel zurück und durchlaufen diese Situation: Der Halter der Locks 13, 26 und 30 hat jetzt Priorität 35 und will Lock 30 freigeben. Es ergibt sich also folgendes Donation-Array:

13 32 34

prOSt Dokumentation

18

26 33 -1 -1 -1 -1

Der Donation-Zähler steht jetzt auf 3. Der Thread mit Priorität 35 wurde neuer Halter der Lock 30. Der ursprüngliche Halter der Lock 30 hat jetzt Priorität 34 und ist noch Halter von Lock 13 und 26. Gehen wir den zweiten Fall durch: Der Thread, der neuer Halter der Lock ist, hat eine niedri-gere Priorität als der alte Halter der Lock. In diesem Fall, wird einfach die entsprechende Zei-le aus dem Donation-Array gelöscht, der Donation-Counter dekrementiert und der alte Halter behält seine Priorität. In unserem Beispiel sieht das dann so aus: Der Halter der Locks 13, 26 und 30 hat Priorität 35 und will Lock 13 freigeben. Es ergibt sich folgendes Donation-Array:

-1 -1 -1 26 33 -1 30 35 -1

Der Donation-Zähler steht jetzt auf 2. Der Thread mit Priorität 34 wird neuer Halter der Lock 13. Die Priorität des Halters von Lock 26 und 30 beträgt immer noch 35. Anschließend wird in beiden Fällen kontrolliert, ob der Lock-Zähler 0 ist. Falls ja, wird das Donation-Array neu initialisiert. Eine weitere Situation in der Priority-Donation angewendet werden muss, stellt die ver-

schachtelte Prioritäts-Spende dar. Angenommen Thread 33 wartet auf eine Sperre, die Thread 32 hält. Dieser wiederum wartet auf eine Sperre, die Thread 31 hält. Thread 33 muss jetzt also seine Priorität Thread 32 und damit auch Thread 31 schenken, damit dieser als erster die Sperre freigeben kann. Um das zu realisieren wurde jedem Thread eine neue Liste zugewiesen: struct thread

{

...

struct list locksWaitingFor;

...

}

In dieser Liste befinden sich alle Sperren auf die der Thread warten muss. Dazu wurde jeder Sperre ein eigenes Feld zugewiesen, dass das Listenelement repräsentiert: struct lock

{

...

struct list_elem lock_elem;

...

}

Die verschachtelte Prioritäts-Spende wurde in der Methode lock_acquire() implementiert. Will ein Thread eine Sperre betreten, die bereits einen Halter hat, wird diese Sperre sofort in die Liste eingetragen. Kommt es anschließend zu einer Prioritäts-Spende, weil der Thread, der die Sperre betreten will eine höhere Priorität als der Halter der Sperre hat, muss auch die Priorität der Halter der

prOSt Dokumentation

19

Locks auf die der aktuelle Halter wartet, erhöht werden. Ebenfalls muss der Donation-Zähler dieser Halter erhöht werden und die Priorität in ihr Donation-Array eingetragen werden. Dazu wird die Liste mit den Locks, auf die der Halter der Lock wartet, durchlaufen und die Priorität an deren entsprechenden Halter gespendet. Natürlich muss auch die Liste dieser Hal-ter wieder durchlaufen werden usw. Wir haben keine Beschränkung der Verschachtelungstie-fe eingeführt. Wird ein Thread, der auf eine Sperre gewartet hat, Halter dieser Sperre, muss diese aus der Liste des Threads gelöscht werden, da er jetzt nicht mehr auf sie warten muss. Wir haben für dieses Projekt folgende Methoden in den folgenden Dateien bearbeitet bzw. hinzugefügt: threads/thread.c:

thread_get_priority()

void put_in_ready_list (struct thread *t)

void take_out_readylist ( struct thread *t)

void traverse_lockholder_list(struct list *list)

void traverse_donationarray(struct thread *t)

int search_donationarray(struct thread *t, int priority)

void init_donationarray(struct thread *t)

void init_line_donationarray(struct thread *t, int lid)

void put_in_donationarray(struct thread *t, int lid)

void put_lid_in_donationarray(struct thread *t, int lid)

int get_highest_priority_of_donationarray(struct thread *t, int priority)

int count_donationarray(struct thread *t, int lid)

threads/sync.c:

sema_down()

sema_up()

lock_acquire()

lock_release

Die Ergebnisse der Tests für den korrekten Ablauf der Priority-Donation sind im Abschnitt 8.1 zu finden.

prOSt Dokumentation

20

5. PROJEKT 2: USER PROGRAMS Im zweiten Projekt geht es darum, unserem Betriebssystem zu erlauben, Benutzerprogramme auszuführen. Pintos unterstützt bereits das Laden und Ausführen von Benutzerprogrammen, aber keinerlei Input bzw. Output und Interaktion ist möglich. Unsere Aufgabe in diesem Pro-jekt besteht darin, den Programmen zu erlauben mit dem Betriebssystem mittels System-Calls zu kommunizieren. Es wurde uns freigestellt, das Projekt 2 auf Projekt 1 aufzubauen oder neu zu starten. Da kei-nerlei Funktionalität von Projekt 1 (Alarm-Clock, Priority-Scheduling, Priority-Donation) in Projekt 2 benötigt wird, haben wir uns für letzteres entschieden. Die Implementierung dieses Projektes findet größtenteils in folgenden Arbeitsverzeichnissen bzw. Dateien statt:

- „userprog“: process.c, syscall.c, FILE-SYSTEM

Da Benutzerprogramme aus einem Dateisystem geladen werden und viele System-Calls ein Dateisystem benutzen wurde ein solches bereits von Pintos zur Verfügung gestellt, allerdings in einer sehr einfachen aber dennoch kompletten Ausführung. Die Implementierung dieses Dateisystems ist im Ordner „filesys“ zu finden. Da in Projekt 4 die Funktionalität dieses Dateisystems erweitert werden soll, wird bereits jetzt empfohlen, folgende Regeln einzuhalten:

- nur ein Prozess darf zu einem Zeitpunkt Code des Dateisystems ausführen - die Dateigröße wird bei der Erstellung festgelegt - die Anzahl der Dateien im Dateisystem ist limitiert - die Daten einer Datei müssen aufeinanderfolgende Sektoren der Festplatte belegen - keine Unterverzeichnisse sind erlaubt - Dateinamen sind auf 14 Zeichen begrenzt - wird eine geöffnete Datei gelöscht, kann sie noch solange vom Thread der sie geöffnet

hat benutzt werden, bis sie geschlossen wird Folgende Anweisungen müssen ausgeführt werden, um eine Festplatte zu simulieren: pintos-mkdisk fs.dsk 2 #erstellt eine 2 MB große Festplatte “fs.dsk”

pintos –f –q #formatiert die Festplatte und beendet Pintos

Um eine Datei in das Dateisystem zu kopieren, führt man folgende Anweisung aus: pintos –p ../../examples/echo –a echo -- -q

#kopiert die Datei “echo” aus dem Ordner “examples” in das Dateisystem #un-

ter dem Dateinamen “echo” und beendet Pintos anschließend

Um ein Benutzerprogramm auszuführen, wird diese Anweisung benötigt: pintos –q run ’echo x’

Mit folgender Anweisung können die Dateien des Filesystems aufgelistet werden: pintos ls

Mit dieser Anweisung löscht man eine Datei im Filesystem:

prOSt Dokumentation

21

pintos rm <dateiname>

Um den Inhalt einer Datei auszugeben, führt man folgende Anweisung aus: pintos cat <dateiname>

Da nur ein Prozess zu einem Zeitpunkt Code des Filesystems ausführen darf musste von uns noch die nötige Synchronisation implementiert werden. Wir haben dazu eine Sperre verwen-det. Die filesyslock wird in der Methode filesys_init() deklariert und initialisiert. Jedes Mal, wenn eine Methode des Filesystems aufgerufen wird, muss diese durch lock_aquire(filesyslock) geschützt werden und anschließend durch lock_release(filesyslock) wieder freigegeben werden. VIRTUAL MEMORY

In Pintos wird der virtuelle Speicher in 2 Abschnitte unterteilt: virtueller Speicherbereich für Benutzer und virtueller Speicherbereich für den Kernel. Der virtuelle Speicher für Benutzer reicht von Adresse 0 bis Adresse 0xc0000000, das ent-spricht 3 GB. Ab Adresse 0xc0000000 beginnt der virtuelle Speicher des Kernels. Dieser en-det bei 4 GB (siehe Abbildung). Jeder Prozess hat seinen eigenen virtuellen Speicherbereich und kann auch nur auf diesen zugreifen, jeder andere Zugriff(auf den virtuellen Speicherbereich des Kernels oder eines an-deren Prozesses) führt sofort zu einem Seiten-Fehler und der Beendigung des Prozesses. Bei einem Context-Switch von einem Prozess zum nächsten wird also auch ein neues Seitenver-zeichnis in das Prozessor-Basisregister für Seitenverzeichnisse geladen, dh die Seitentabellen des neuen Prozesses werden geladen. Das geschieht in der Methode pagedir_activate(). Der virtuelle Speicherbereich des Kernels ist global und wird 1:1 auf den physischen Spei-cherbereich abgebildet. Ein Kernel-Thread kann außerdem auf den virtuellen Speicherbereich des aktuell laufenden Benutzerprogramms zugreifen. Wir möchten an dieser Stelle auf Projekt 3 verweisen, wo der Aufbau des virtuellen Speichers genauer betrachtet wird.

4 GB Kernel VM

3 GB user Stack

User VM

uninizialized data segment (BSS)

inizialized data segment

code segment

128 MB

0

prOSt Dokumentation

22

MEMORY ALLOCATION

In Pintos kann man zwischen zwei verschiedenen Möglichkeiten wählen, um Speicher zu al-lozieren. Entweder man alloziert Speicher in Form von 4 KB großen Seiten oder in Form von Blöcken beliebiger Größe. Die Methoden zum Allozieren von Seiten befinden sich in der Datei „threads/palloc.c“ void *palloc_get_page (enum palloc_flags flags)

Hier wird eine freie Seite alloziert und ihre Adresse zurückgegeben. void *palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)

Hier werden page_cnt benachbarte Seiten alloziert. Es existieren 3 verschiedene Flags für das Allozieren von Seiten: PAL_ASSERT: Führt zu einer Kernel-Panic falls die Seite nicht alloziert werden kann und

sollte daher nicht für Benutzerprozesse verwendet werden. PAL_ZERO: Setzt alle Bytes der allozierten Seite auf 0. PAL_USER: Alloziert eine Seite des User-Pools, andernfalls des Kernel-Pools. Der Speicher, der alloziert werden kann, wird defaultmäßig in 2 Hälften geteilt: Kernel-Pool und User-Pool. Der User-Pool sollte für die Speicherallozierung von Benutzerprozessen ver-wendet werden. Darauf sollte besonders ab Projekt 3 geachtet werden. Bis dahin werden nur Seiten des Kernel-Pools alloziert. Jeder Pool wird durch eine Bitmap repräsentiert, in der jedes Bit für eine Seite steht. 0 bedeu-tet frei und 1 bedeutet belegt. Sollen n Seiten alloziert werden, wird die Bitmap solange durchsucht, bis n aufeinanderfolgende Nullen gefunden werden. Diese werden dann auf 1 gesetzt. Das entspricht einer „first-fit“-Strategie. Folgende Methoden geben die Seiten wieder frei: void *palloc_free_page (void *page) {...}

Hier wird die Seite an der Adresse page freigegeben. Das funktioniert nur, wenn diese Seite vorher mit palloc_get_page alloziert wurde. void *palloc_free_multiple (void *pages, size_t page_cnt) {...}

Hier werden page_cnt benachbarte Seiten, beginnend mit der Adresse pages freigegeben. Das funktioniert nur, wenn diese Seiten vorher mit palloc_get_multiple() alloziert wurden. Die Methode zum Allozieren von beliebig großen Blöcken befindet sich in der Datei „threads/malloc.c“ void *malloc (size_t size) {...}

Hier wird ein freier Block des Kernel-Pools, der mindestens size Bytes groß ist, alloziert und seine Adresse zurückgegeben. void *free (void *block) {...}

Hier wird ein Block, beginnend bei Adresse block, wieder freigegeben. Dieser muss vorher mit malloc() alloziert worden sein.

prOSt Dokumentation

23

5.1 ARGUMENT PASSING Pintos unterstützt das Übergeben von Argumenten an einen neuen Prozess nicht. Die erste Aufgabe war es, diese Funktion zu implementieren. Dazu musste folgende Methode modifi-ziert werden: tid_t process_execute (const char *file_name) {...}

Dieser Methode wurde nur der Dateiname als Argument übergeben. Es soll jetzt allerdings möglich gemacht werden den Filenamen, sowie alle Argumente zu übergeben. Diese werden als einzelner String repräsentiert, wobei der Filename und die einzelnen Argumente durch Leerzeichen getrennt werden. Man extrahiert als nächstes den Filenamen, indem man vor dem ersten Leerzeichen den String „abschneidet“. Der einzelne Filename sowie der ganze Kom-mando-String werden dann der Methode thread_create() übergeben und es wird ein neuer Thread erzeugt mit dem Namen <filename> und dieser führt die Methode execute_thread() mit dem Kommando-String als Parameter aus. static void execute_thread (void *file_name_){...}

Hier muss als nächstes der Kommando-String aufgeteilt werden, indem man die Leerzeichen als Seperator verwendet. Die erhaltenen Strings werden dann in einer Stringtabelle „argv“ gespeichert. Außerdem existiert ein Argumente-Zähler „argc“. Dazu ein kleines Beispiel: Soll das Benutzerprogramm ‚echo x y z’ ausgeführt werden wird der Methode execu-te_thread() der ganze Kommando-String übergeben. Danach werden die einzelnen Strings separiert und es ergibt sich folgende Stringtabelle:

argv[3] z argv[2] y argv[1] x argv[0] echo

Da in der Programmiersprache C Strings als Zeiger vom Typ „char“ repräsentiert werden, befinden sich natürlich nicht die Strings selbst in der Stringtabelle, sondern ihre Zeiger auf den jeweils ersten Buchstaben dieser Strings. Die Stringtabelle selbst (char *argv[argc-1])ist ein Zeiger auf die Adresse von argv[0], also eigentlich ein Zeiger auf einen Zeiger. Der Argumente-Zähler hat den Wert 4. Danach wird der Interrupt-Frame initialisiert und das Programm, das ausgeführt werden soll, geladen. Wurde das korrekt durchgeführt besteht der nächste Schritt darin, alle Argumente auf den Stack des neuen Prozesses zu legen. Dazu wurde beim Laden des Programms mit der Methode setup_stack() ein minimaler Stack initialisiert, indem eine mit Nullen gefüllte Seite aus dem Benutzer-Pool an die Spitze des Virtuellen Speichers des Benutzers abgebildet wird. Außerdem muss eine Abbildung von der virtuellen Benutzer-Seite zur virtuellen Kernel-Seite, also dem physischen Rahmen in die Seitentabelle des Threads eingetragen werden. Wir möch-ten an dieser Stelle auf Kapitel 3 verweisen, wo am Beginn einige grundlegende Begriffe des virtuellen Speichers besprochen werden. Da Pintos ELF-Programme lädt und ausführt, muss der Stack ein bestimmtes Format haben, bevor das jeweilige Programm ausgeführt werden kann. Der Stack bzw. Stack-Pointer sollten folgendermaßen initialisiert werden:

prOSt Dokumentation

24

Adresse Name Wert Typ Größe in Byte

0xbffffffe argv[3][...] z\0 char 2 0xbffffffc argv[2][...] y\0 char 2 0xbffffffa argv[1][...] x\0 char 2 0xbffffff5 argv[0][...] echo\0 char 5 0xbffffff4 word-align 0 char 1 0xbffffff0 argv[4] NULL char * 4 0xbfffffec argv[3] 0xbffffffe char * 4 0xbfffffe8 argv[2] 0xbffffffc char * 4 0xbfffffe4 argv[1] 0xbffffffa char * 4 0xbfffffe0 argv[0] 0xbffffff5 char * 4 0xbfffffec argv 0xbfffffe0 char ** 4 0xbfffffe8 argc 4 int 4 0xbfffffe4 return_address NULL void(*)() 4

Der Stackpointer muss also auf 0xbfffffe4 initialisiert werden. Der Stack startet bei Adresse 0xc0000000, dh. das erste Argument beginnt bei Adresse 0xbffffffe, da es 1 Byte groß ist. Nachdem die Argumente auf den Stack gelegt wurden kann man für einen schnelleren Zugriff an der nächsten Adresse, die ein Vielfaches von 4 ist ein word-align-Feld einfügen. Die Größe dieses Feldes variiert somit von 1-4 Byte. Anschließend wird ein Null-Pointer eingefügt, sowie Pointer auf alle Felder der String-Tabelle argv in absteigender Reihenfolge. Danach werden noch ein Pointer auf den argv[0]-Pointer dieser String-Tabelle sowie der Argumente-Zähler auf den Stack gelegt. Das letzte Feld ist die Return-Adresse, auf die der Stack-Pointer initialisiert werden muss.

5.2 SYSTEM CALLS Die Implementierung des Systemcallhandlers und der Systemcalls findet im Arbeitsverzeich-nis „userprog/syscall.c“ statt. Der Systemcallhandler soll die Systemcall-Nummer und ver-schiedenste Argumente der Systemcalls übernehmen und daraufhin geeignete Aktionen durchführen. Die jeweiligen Nummern der Systemcalls werden in „lib/syscalls-nr.h“ definiert: /* die Systemaufrufe in der Reihenfolge der Implementierung */

#define SYS_HALT 0 /* beendet das Betriebssystem */

#define SYS_EXIT 1 /* beendet einen Prozess */

#define SYS_CREATE 4 /* erstellen einer Datei*/

#define SYS_REMOVE 5 /* löschen einer Datei */

#define SYS_OPEN 6 /* öffnen einer Datei*/

#define SYS_CLOSE 12 /* schließen einer Datei */

#define SYS_READ 8 /* lesen aus einer Datei */

#define SYS_WRITE 9 /* in eine Datei schreiben */

#define SYS_SEEK 10 /* Position in einem File verändern */

#define SYS_TELL 11 /* aktuelle Position in einem File */

#define SYS_FILESIZE 7 /* Größe eines Files */

#define SYS_EXEC 2 /* einen anderen Prozess starten */

Der Systemcall-Handler befindet sich in „userprog/syscall.c“ unter folgender Methode: static void syscall_handler (struct intr_frame *f UNUSED) {...}

prOSt Dokumentation

25

Es handelt sich dabei um eine große if-Abfrage. Jeder Aufruf eines Systemcalls holt sich die entsprechenden Parameter vom Stack. Jeder Systemaufruf wurde mit einem speziellen Pro-gramm getestet, diese Programme befinden sich im Verzeichnis examples. Wir haben folgende Systemcalls in „userprog/syscall.c“ implementiert: SYSTEMCALL: HALT void halt() {...}

Schaltet das Betriebssystem ab. Testprogramm: halt.c SYSTEMCALL: EXIT void exit(int status) {...}

Beendet einen Prozess und gibt einen bestimmten Status zurück, z.B. 0 für „alles okay“. Testprogramm: exit.c SYSTEMCALL: CREATE bool create(const char * file, unsigned initial_size) {...}

Erzeugt eine neue Datei mit dem Namen file und der Größe initial_size. Testprogramm: touch.c SYSTEMCALL: REMOVE bool remove(const char * file) {...}

Löscht die Datei mit dem Dateinamen file. Testprogramm: delete.c SYSTEMCALL: OPEN int open(const char * file) {...}

Öffnet die Datei mit dem Namen file. Testprogramm: open.c SYSTEMACALL: CLOSE void close(int fd) {...}

Schließt die Datei mit dem Filedeskriptor fd. Testprogramm: open.c

SYSTEMCALL: READ int read(int fd, void * buffer, unsigned length) {...}

Ließt aus der Datei mit dem Filedeskriptor fd und speichert die ersten length-Bytes der Datei in buffer. Testprogramm: cat.c

SYSTEMCALL: WRITE int write(int fd, const void * buffer, unsigned length) {...}

Schreibt in die Datei mit dem Filedeskriptor fd. Testprogramm: cat.c

SYSTEMCALL: SEEK void seek(int fd, unsigned position) {...}

Schiebt den Positionszeiger der Datei mit dem Filedeskriptor fd um position weiter. Testprogramm: seektell.c

prOSt Dokumentation

26

SYSTEMCALL: TELL unsigned tell(int fd) {...}

Gibt den Positionszeiger der Datei mit dem Filedeskriptor fd zurück. Testprogramm: seektell.c

SYSTEMCALL: FILESIZE int filesize(int fd) {...}

Liefert die Größe der Datei mit dem Filedeskriptor fd. Testprogramm: filesize.c

SYSTEMCALL: EXEC pid_t exec(const char * file) {...}

Führt die Datei mit dem Namen file aus. Testprogramm: readalot.c

Details zu den Vorgaben, wie die Systemaufrufe zu implementieren waren, finden sich unter [6] in den Kapitel 3.3.4 System Calls und 3.5: 80x86 Calling Convention. Alle implemetierten Systemaufrufe orientieren sich an den Vorgaben aus lib/user/syscall.h Der Ablauf eines Systemaufrufs:

• Zuerst wird die Nummer des Systemaufrufs in lib/syscall-nr.h ermittelt. • Mit dieser Nummer wird nach lib/user/syscall.c gesprungen. Von hier aus wird nach

userprog/syscall.c gesprungen. • In der dort befindlichen if-Abfrage wird die dem syscall entsprechende Funktion auf-

gerufen. • Die Argumente, die der Systemaufruf benötigt, werden zuvor mittels der

get_from_stack_*-Aufrufen vom Stack geholt. • Ausführung des Systemaufrufs. • Eventuelle Rückgabewerte werden im Register eax der Interruptframes f gespeichert.

prOSt Dokumentation

27

6. PROJEKT 3: VIRTUAL MEMORY In Projekt 3 wird das Hauptaugenmerk auf den Hauptspeicher gelegt, genauergesagt auf den virtuellen Speicher. Bis jetzt war die Anzahl und Größe der Programme, die ausgeführt wer-den können auf die Größe des Hauptspeichers limitiert. Unsere Aufgabe besteht jetzt darin, diese Einschränkung aufzuheben, indem nur die Teile eines Programms im Hauptspeicher gehalten werden, die gerade benötigt werden. Der Rest des Programms befindet sich auf der Festplatte. Die Ein- bzw. Auslagerung von Programmteilen bzw. die Abbildung von virtuel-lem auf physischen Speicher wird uns also ab jetzt beschäftigen. Projekt 3 wird auf Projekt 2 aufgebaut. Es ist also wichtig, dass Projekt 2 fehlerfrei funktio-niert, da diese Fehler auch Probleme beim aktuellen Projekt verursachen können. Die Implementierung dieses Projektes findet größtenteils in folgenden Arbeitsverzeichnissen bzw. Dateien statt:

- „vm“: vm.c - “threads”: thread.c - “userprog”: process.c

Alle Testprogramme für Projekt 2 (siehe 8.2) müssen auch mit Virtual Memory laufen. Des-halb ist es wichtig, diese Testprogramme ab jetzt vom Ordner „vm/build“ und nicht mehr von „userprog/build“ aus zu starten. Da Virtueller Speicher (VM) ein sehr komplexes Thema ist, das leicht zu Verwirrungen füh-ren kann, möchten wir an dieser Stelle einige Begriffe, die von uns verwendet werden erklä-ren. PAGES (SEITEN)

Wenn wir von Pages bzw. Seiten sprechen, dann meinen wir einen 4 KB großen Speicherbe-reich des VM. Eine Seite muss also immer an einer Adresse beginnen, die ein Vielfaches von 4 ist. Eine solche virtuelle Adresse hat 32 Bit, wovon 20 Bit die Seitennummer und 12 Bit der Offset sind. Wir möchten an dieser Stelle auf Projekt 2 verweisen, wo erklärt wird, wie der virtuelle Spei-cher eines Prozesses aufgebaut ist. FRAMES (RAHMEN)

Mit Frames bzw. Rahmen bezeichnen wir einen 4 KB großen Speicherbereich des physischen Speichers. Wiederum muss eine physische Adresse ein Vielfaches von 4 sein und hat 32 Bit, wovon 20 Bit die Rahmennummer und 12 Bit der Offset sind. In Pintos wird der virtuelle Speicherbereich des Kernels direkt auf den physischen Speicher abgebildet, dh die erste Seite des Kernel-VM (virtuelle Adresse 0xc0000000) entspricht dem ersten Rahmen (physische Adresse 0) des physischen Speichers. Dadurch kann man über den Kernel-VM auf einen Rahmen zugreifen, was in einem Betriebssystem-Kernel oft nötig ist.

prOSt Dokumentation

28

PAGE TABLES (SEITENTABELLEN)

Unter einer Seitentabelle (PT) verstehen wir eine Datenstruktur, die der Prozessor verwendet, um die virtuelle Adresse einer Seite in die physische Adresse eines Rahmens zu übersetzen. Es wird dabei die Seitennummer (20 Bit der virtuellen Adresse) in die Rahmennummer (20 Bit der physischen Adresse) umgewandelt. Der Offset bleibt derselbe. Wie das genau geschieht, möchten wir jetzt erklären: Neben den Seitentabellen gibt es als übergeordnete Struktur noch ein Seitenverzeichnis (Page Directory, PD), das als Seite, bestehend aus 1024 32-Bit Einträgen (PDE) dargestellt wird, wovon jeder Eintrag auf die physische Start-Adresse einer Seitentabelle zeigen kann. Die ers-ten 10 Bits (Bits 32 – 23) der virtuellen Adresse stellen den Index des Seitenverzeichnisses dar. Die nächsten 10 Bits (Bits 22 – 13) der virtuellen Adresse stellen den Index der Seitenta-belle dar. Eine Seitentabelle ist wiederum eine Seite, die aus 1024 32-Bit Einträgen (PTE) besteht. Ein Seitentabelleneintrag zeigt auf die physische Start-Adresse einer Seite, also auf den Rahmen. Zu dieser physischen Adresse wird noch der 12-Bit Offset (Bits 12 – 1) hinzu-gefügt und man erhält die genaue physische Adresse der gewünschten Daten. Das Seitenverzeichnis kann also aus max. 1024 Seitentabellen bestehen und jede Seitentabelle aus max. 1024 Seiten. Bei einer Größe von 4 KB pro Seite, stellt eine Seitentabelle 4 MB vir-tuellen Speicher dar und ein Seitenverzeichnis 4 GB virtuellen Speicher. Jeder Thread besitzt sein eigenes Seitenverzeichnis mit den zugehörigen Seitentabellen. Die-ses wird in der Struktur Thread im Feld pagedir gespeichert und muss geladen werden damit der Prozessor Programm-Code des Threads ausführen kann.

6.1 SUPPLEMENTAL PAGE TABLE Wir haben eine zusätzliche Seitentabelle implementiert, um zusätzliche Informationen über jede Seite zu speichern. Sie ergänzt also die übliche Seitentabelle, deren Einträge ein vorge-gebenes Format haben und deren Verwendung deshalb eingeschränkt wird. Die zusätzliche Seitentabelle ist lokal, dh. jeder Thread besitzt seine eigene Tabelle. Dazu musste in der Struktur thread folgendes Feld neu eingefügt werden: struct list supp_page_table;

Diese Seitentabelle in Form einer doubly-linked Liste implementiert, die bei der Erzeugung eines Threads in thread_create() initialisiert wird. Ein Eintrag in die zusätzliche Seitentabelle hat folgende Struktur: struct sup_page_table_entry{

struct list_elem spt_elem;

enum page_location location;

void *virtual_address;

void *physical_address; //Adresse im physischen Speicher (RAM)

int offset; //Offset im Filesystem bzw. Swap-Bereich

int fd; //File-Deskriptor für memory-mapped-file, sollte >= 2 sein

int notZero; //Länge der Daten einer Seite (nicht Null)

};

Die Einträge in der zusätzlichen Seitentabelle sind geordnet nach ihrer virtuellen Adresse. Eine Seite kann sich an folgenden 4 Stellen befinden: enum page_location{

prOSt Dokumentation

29

RAM, //Seite befindet sich im Hauptspeicher

DISK, //Seite befindet sich im Filesystem

SWAP, //Seite befindet sich im Swap-Bereich

ZERO //Seite ist leer (mit Nullen aufgefüllt)

};

Jeder Eintrag besitzt eine Referenz auf seinen physischen Rahmen im Hauptspeicher bzw. einen Offset, wenn sich die Seite im Filesystem bzw. im Swap-Bereich befindet. Damit das von uns implementierte Virtual Memory auch benutzt wird, mussten wir in pro-cess.c folgende Methode modifizieren: static bool load_segment (...){...}

In dieser Methode werden solange es Bytes der Datei mit dem Benutzerprogramm zu lesen gibt, Einträge in der zusätzlichen Seitentabelle aufgebaut. Wir müssen zwischen 3 Möglich-keiten unterscheiden: die Seite ist mit Daten vollgeschrieben, die Seite ist leer, also mit Nul-len gefüllt und die Seite ist nicht ganz mit Daten vollgeschrieben, dh der Rest muss mit Nul-len aufgefüllt werden. Zu diesem Zweck wird mit dem Frame-Table-Allocator (siehe nächstes Kapitel) ein freier Rahmen im Hauptspeicher alloziert, die gültigen Daten eingelesen und der verbleibende Platz der Seite mit Nullen aufgefüllt. Mit folgendem Aufruf wird eine neue Ab-bildung von der virtuellen Seite im Benutzerraum auf eine virtuelle Seite im Kernelraum her-gestellt: bool install_page_with_vm (void *upage, void *kpage, bool writable){...}

Diese Methode entspricht dem alten install_page()-Aufruf von process.c, als noch kein Virtual Memory existierte. Die Abbildung von der Benutzer-Seite zur Kernel-Seite wird deshalb her-gestellt, da die virtuellen Seiten des Kernels 1:1 auf den Hauptspeicher abgebildet sind. Man stellt so eine indirekte Abbildung von einer virtuellen Benutzer-Seite zu ihrem physischen Rahmen im Hauptspeicher her.

6.2 FRAME TABLE ALLOCATOR Eine weitere Aufgabe in Projekt 3 ist es einen sogenannten Frame-Table-Allocator zu imple-mentieren. Vorerst soll allerdings noch keine Seitenersetzung bzw. Swapping implementiert werden. Es wird also angenommen, dass es immer freie Rahmen gibt. Sollten irgendwann die Rahmen ausgehen, soll einfach eine Fehlermeldung ausgegeben werden. Um unseren physischen Speicher zu verwalten, haben wir eine globale Rahmentabelle in Form einer doubly-linked Liste implementiert. struct list frame_table;

Diese Tabelle wird beim start des Thread-Systems in thread_start() initialisiert. Die Rahmentabelle enthält für jeden Rahmen, der eine Seite des VM enthält, einen Eintrag. Ein Eintrag in der Rahmentabelle hat folgende Struktur: struct frame_table_entry{

struct list_elem ft_elem;

void *physical_address;

struct thread *owner;

struct sup_page_table_entry *ref_spt_entry;

};

Jeder Eintrag enthält also eine Referenz auf eine belegte Seite des VM und eine Referenz auf den Thread dieser Seite. Die Einträge für die Rahmen werden der Reihenfolge nach, wie sie alloziert werden in die Rahmentabelle eingefügt. Das heißt ein Eintrag für einen neuen Rah-men wird hinten an die Liste angehängt, so wird es gewährleistet, dass sich der Rahmen, mit

prOSt Dokumentation

30

der ältesten Seite am Kopf der Liste befindet, was wichtig für den LRU-Seitenersetzungsalgorithmus ist. Durch die globale Rahmentabelle wird es möglich eine effiziente Strategie zu entwickeln, die entscheidet, welcher physische Rahmen für eine andere Seite des VM freigegeben werden soll, falls keine anderen freien Rahmen mehr zur Verfügung stehen. void *frame_allocator(){...}

Unser Frame-Table-Allocator ersetzt den früheren Aufruf von get_page() in process.c Die wichtigste Aufgabe unseres Frame-Table-Allocators besteht also darin, einen unbenutzten Rahmen zu allozieren, was sehr einfach ist, wenn freie Rahmen zur Verfügung stehen. Ist kein Rahmen frei, muss entschieden werden, welcher von seiner virtuellen Seite befreit werden soll. Das geschieht mit Hilfe des gewählten Seitenersetzungsalgorithmus. Näheres zu unse-rem Seitenersetzungsalgorithmus wird im Kapitel 6.4 erläutert. Dieser wählt einen Rahmen aus, der eine Seite enthält, die durch eine andere ersetzt werden kann Der nächste Schritt besteht darin den physischen Rahmen von seiner Seite zu befreien. Das erledigt folgende Methode: void evict_frame(struct frame_table_entry *ft_entry) {

Diese Methode entfernt die Referenz auf den physischen Rahmen, der Seite, die ersetzt wer-den soll und entfernt den Eintrag in der Rahmentabelle. Falls nötig wird die ersetzte Seite vorher ausgelagert, dh im File-System bzw. Swap-Bereich gespeichert. Danach kann der nun freie Rahmen für die neue Seite benutzt werden, dh der entsprechende Eintrag in der Rahmen-tabelle erhält einen neuen Zeiger auf die neue Seite und diese erhält eine Referenz auf den Rahmen. Synchronisation ist bei der Benutzung der globalen Rahmentabelle ein wichtiges Thema. Fol-gende Situation könnte auftreten: Bei Prozess A tritt ein Seitenfehler auf. Diese Seite befindet sich im physischen Rahmen, den Prozess B gerade von dieser Seite befreien und in ihm eine neue Seite speichern will. Dieses Problem wird von uns mit Hilfe einer Lock für die globale Rahmentabelle gelöst. struct lock frame_table_lock;

Diese Sperre wird beim Start des Thread-Systems in thread_start() initialisiert. Das bedeutet, dass zu einem Zeitpunkt nur ein Prozess auf die globale Rahmentabelle zugrei-fen kann.

6.3 SWAP TABLE Die Swaptabelle enthält Einträge für alle Swap-Slots im Swap-Bereich. Ein Swap-Slot ent-spricht der Größe einer Seite (dh 4 KB bzw. 8 512 Byte-Segmente) und kann entweder belegt oder frei sein. Mit Hilfe der Swaptabelle kann man einen freien Swap-Slot auswählen, um eine Seite zu speichern, die ausgelagert werden muss, dh. ihr physischer Rahmen muss von ihr befreit werden, um eine neue Seite zu speichern. Wird die ausgelagerte Seite wieder zu-rückgeschrieben, dh sie belegt wieder einen physischen Rahmen muss der Swap-Slot geleert werden. Dies ist auch der Fall, wenn der Prozess, dessen Seite ausgelagert wurde, beendet wird. Es ist zu beachten, dass Swap-Slots nur für die Auslagerung von Seiten verwendet wer-den.

prOSt Dokumentation

31

Man kann in Pintos als Swap-Bereich eine eigene Festplatte verwenden, die mit folgendem Befehl erzeugt und danach automatisch bei jedem Start von Pintos miteingebunden wird: pintos-mkdisk swap.dsk n #erstellt eine n MB große Festplatte

#“swap.dsk”

Es ist zu beachten, dass man sich bei der Ausführung dieses Befehls im Verzeichnis „vm/build“ befindet. Wir haben die Swaptabelle in Form einer globalen Bitmap implementiert. In Pintos stehen bereits Methoden zur Erzeugung und Modifikation von Bitmaps zur Verfügung. struct bitmap swap_table;

Da die Swaptabelle global ist, mussten wir natürlich noch für die entsprechende Synchronisa-tion sorgen. Das haben wir mit Hilfe einer Lock implementiert: struct lock swap_table_lock

Wird eine Seite in den Swap-Bereich geschrieben, muss der dafür verwendete Slot in der Swap-Tabelle mit 1, also als belegt gekennzeichnet werden. Wird eine Seite vom Swap-Bereich gelesen, muss der gelesene Slot anschließend in der Swap-Tabelle mit 0, also frei gekennzeichnet werden. Beim Schreiben einer Seite in den Swap-Bereich wird der erste freie Slot der gefunden wer-den kann ausgewählt, dh das entspricht einer first-fit-Strategie.

6.4 PAGE FAULT HANDLER Um Seitenfehler zu behandeln benutzen wir wieder unsere zusätzliche Seitentabelle, da in ihr für jede Seite gespeichert wird, wo sich diese gerade befindet. Tritt ein Seitenfehler auf, wird diese virtuelle Seite in der zusätzlichen Seitentabelle gesucht, um ihre die Stelle herauszufinden, wo sie sich befindet. In Projekt 2 bedeutete ein Seitenfeh-ler, dass ein Fehler im Kernel oder im Benutzerprogramm aufgetreten ist. Das ist ab Projekt 3 nicht mehr länger der Fall. Ab jetzt bedeutet ein Seitenfehler, dass sich diese Seite noch nicht im Hauptspeicher befindet, dh noch nicht auf einen physischen Rahmen abgebildet wurde und daher erst aus einer Datei im Filesystem oder aus dem Swap-Bereich geladen werden muss. Unsere nächste Aufgabe besteht also darin einen anspruchsvolleren Page-Fault-Handler zu implementieren. Dazu muss folgende Methode in “userprog/exception.c“ modifiziert werden: void page_fault (){...}

Diese Methode führt im Groben folgende Schritte aus: 1. Die Seite, die einen Fehler ausgelöst hat in der zusätzlichen Seitentabelle finden und mit

dem Eintrag die Stelle finden, wo sich die Seite befindet. Diese befinden sich entweder im Filesystem, im Swap-Bereich oder ist einfach nur eine leere Seite mit lauter Nullen.

Falls die Seite im VM nicht abgebildet wurde, dh dass keine Daten zu finden sind, sich die Seite im virtuellen Adressraum des Kernels befindet oder eine read-only-Seite geschrie-ben werden soll, handelt es sich um einen ungültigen Zugriff. In diesem Fall muss der Prozess sofort beendet werden und all seine Ressourcen freigegeben werden.

2. Als nächstes muss ein Rahmen belegt werden, in dem die Seite gespeichert werden soll. Dieser wird mit Hilfe des Frame-Table-Allocators (siehe 6.2) gesucht.

3. Die Daten werden in den Rahmen geschrieben. Sie werden entweder aus einem File oder aus dem Swap-Bereich gelesen oder sie werden als lauter Nullen dargestellt.

prOSt Dokumentation

32

4. Jetzt muss die Referenz von der virtuellen Seite, die einen Seitenfehler ausgelöst hat, zum physischen Rahmen hergestellt werden, dh es entsteht ein Eintrag in der Seitentabelle. Dazu wird die Methode install_page_with_vm() verwendet.

6.5 STACK GROWTH Eine weitere Aufgabe, die in Projekt 3 implementiert werden muss, ist es dem Stack zu erlau-ben zu wachsen. In Projekt 2 wurde der Stack als einzelne Seite am Beginn des virtuellen Ad-ressraums des Benutzers implementiert. Jetzt soll es möglich gemacht werden, dass der Stack zusätzliche Seiten alloziert, falls er über seine aktuelle Größe hinauswächst. Da sofort ein Seitenfehler auftritt, wenn der Stack über seine aktuelle Größe hinauswächst müssen wir in der Methode page_fault() die Allozierung von neuen Stack-Seiten implemen-tieren. Zu diesem Zweck haben wir der Struktur thread ein neues Feld gegeben: void *stack_start;

Dieses Feld gibt die aktuelle virtuelle Startadresse des Stacks an, und wird mit der Adresse der letzten Seite im Virtuellen Speicher des Benutzers initialisiert (3GB – 4KB). In der Methode page_fault() muss also kontrolliert werden, ob der Stackpointer über diese virtuelle Startadresse hinausgewachsen ist. Falls ja muss die virtuelle Startadresse wieder um 4KB hinuntergesetzt werden und für diese neue Adresse eine Seite alloziert werden. Unser Stack kann nicht uneingeschränkt wachsen. Wir erlauben maximal eine Größe von 8 MB. Dafür haben wir für jeden Thread einen Zähler für die allozierten Stack-Seiten imple-mentiert, der höchstens den Wert 2048 (mal 4 KB = 8 MB) annehmen kann. Bevor eine neue Seite alloziert wird, muss kontrolliert werden, ob der Zähler diesen Wert bereits erreicht hat.

6.6 MEMORY MAPPED FILES Es gibt eine Möglichkeit Read- und Write-Systemcalls, bei denen auf das Dateisystem zuge-griffen wird zu umgehen. Dabei wird eine gesamte Datei im Virtuellen Speicher eines Prozes-ses abgebildet und das Benutzerprogramm kann dadurch die Befehle direkt auf den Daten der Datei ausführen. Um für jeden Thread zu speichern welche Dateien er in den virtuellen Speicher geladen hat, haben wir ein Array von Strukturen mit 128 Feldern implementiert. struct mm_table_entry mm_array[128];

Ein Eintrag in dieses Array sieht folgendermaßen aus: struct mm_table_entry{

struct file *file;

int bytes;

void *start_address;

int mapped_pages

};

Ein Eintrag besteht also aus einem Zeiger zur geöffneten Datei, der Größe der eingelagerten Datei, der Startadresse im VM und der Anzahl der Seiten die eingelagert wurden. Das Array wird init_thread() initialisiert, dh. die Referenzen werden mit NULL und die Größe der Bytes, sowie die Anzahl der Seiten mit 0 für alle Felder belegt.

prOSt Dokumentation

33

Über den File-Deskriptor fd einer Datei greift man auf das entsprechende Array-Feld zu. Das bedeutet, dass ein Thread maximal 126 memory-mapped-Dateien besitzen kann, da die File-Deskriptoren 0 und 1 bereits für Konsolen-Input und Output belegt sind. Die Tabelle für die memory mapped Dateien ist außerdem nötig, um für diese Seiten mögli-che Seitenfehler richtig zu behandeln und sicherzustellen, dass die abgebildeten Dateien ande-re Segmente des Prozesses nicht überlappen. Um Speicherabbildungen möglich zu machen, müssen folgende Systemcalls implementiert werden: bool mmap (int fd, void *addr){...}

Mit dieser Methode wird die geöffnete Datei mit dem File-Descriptor fd in den virtuellen Speicherbereich des Prozesses abgebildet. Die Datei wird dabei in aufeinanderfolgende Seiten beginnend bei der Adresse addr gespeichert. Soll eine Seite, die durch mmap() eine Abbildung einer Datei ist, ausgelagert werden, muss diese Seite in die Datei, von der sie abgebildet wurde, zurückgeschrieben werden. Die mmap()-Methode gibt 1 zurück, wenn die die Speicherabbildung innerhalb des Prozesses richtig durchgeführt werden konnte. Tritt ein Fehler auf, wird 0 zurückgegeben und die Spei-cherabbildungen des Prozesses bleiben unverändert. In folgenden Fällen können Fehler auftreten:

- die geöffnete Datei mit dem File-Descriptor fd hat die Länge 0 - addr ist kein Vielfaches von 4 - die abgebildeten Seiten überlappen eine bereits bestehende Abbildung - addr ist 0, da Pintos annimmt, dass die virtuelle Seite 0 nicht abgebildet wird - die Dateien mit dem File-Descriptor 1 und 0 können nicht abgebildet werden, da diese

den Konsolen-Input bzw. Output repräsentieren - der fd ist größer als 128. Es können nur max 126 Dateien gleichzeitig geöffnet sein.

Die Abbildung muss in der Tabelle für die Speicherabbildungen des Prozesses eingetragen werden. bool munmap (int fd){...}

Diese Methode hebt die Speicherabbildung der Datei mit dem File-Deskriptor fd wieder auf. Das funktioniert nur, wenn die Datei durch einen vorherigen mmap()-Aufruf desselben Pro-zesses im Virtual Memory abgebildet wurde und die Abbildung nicht schon vorher aufgeho-ben wurde. Das kann man mittels der Tabelle der Speicherabbildungen des Prozesses kontrol-lieren. Befindet sich eine Referenz auf die Datei mit dem File-Deskriptor fd in der Tabelle, weiß man, dass die Speicherabbildung gültig ist und noch nicht rückgängig gemacht wurde. Alle Seiten, die geschrieben wurden (Kontrolle des Dirty-Bits) müssen in die Datei, die abge-bildet wurde zurückgeschrieben werden. Alle Seiten der Abbildung werden danach aus der zusätzlichen Seitentabelle des Threads gelöscht. Anschließend kann man den Eintrag in der Tabelle der Speicherabbildungen des Prozesses löschen. Alle Speicherabbildungen werden implizit aufgehoben, wenn ein Prozess beendet wird. Dh man muss bei der Beendigung eines Prozesses darauf achten, dass geschriebene Seiten in die Datei zurückgeschrieben werden.

prOSt Dokumentation

34

Wird ein File geschlossen oder gelöscht, hat das keine Auswirkungen auf seine Speicherab-bildungen. Wurde eine Abbildung erstellt, ist sie solange gültig bis sie mit dem munmap()-Aufruf aufgehoben wird oder der Prozess beendet wird.

6.7 PAGE REPLACEMENT ALGORITHM Unsere nächste Aufgabe ist es einen Seitenersetzungsalgorithmus zu implementieren, der Last-Recently-Used (LRU) approximiert und zumindest so effizient ist, wie der Second-Chance bzw. der Clock-Algorithm. LRU bedeutet, dass bei einem Seitenfehler die Seite ent-fernt wird, die am längsten unbenutzt ist. Wir werden im Anschluss beide Algorithmen beschreiben, wir haben uns allerdings dazu ent-schlossen den Second-Chance-Algorithmus zu implementieren void second_chance_algorithm(){...}

ACCESSED AND DIRTY BITS

Um einen effizienten Seitenersetzungsalgorithmus zu implementieren, gibt es bei jedem Sei-tentabelleneintrag (PTE) zwei hilfreiche Bits. Es handelt sich dabei um das Accessed (R-Bit) und das Dirty (M-Bit) Bit. Beim Accessed-Bit handelt es sich um Bit 5 des 32-Bit Seitentabelleneintrags. Es wird bei jedem Lesen und Schreiben der Seite bzw. des Rahmens von der CPU auf 1 gesetzt. Beim Dirty-Bit handelt es sich um Bit 6 des 32-Bit Seitentabelleneintrags. Es wird von der CPU nur auf 1 gesetzt, wenn die Seite bzw. der Rahmen geschrieben wird. Diese beiden Bits werden von der CPU nicht wieder auf 0 gesetzt. Unsere Aufgabe ist es im Rahmen des Seitenersetzungsalgorithmus diese Bits zum richtigen Zeitpunkt wieder auf 0 zu setzen. Von Pintos werden bereits für das Abrufen und Setzen dieser Bits Methoden zur Ver-fügung gestellt. SECOND CHANCE ALGORITHM

Dieser Seitenersetzungsalgorithmus ist eine einfache Variante von FIFO. Bei FIFO wird ein-fach die älteste Seite im Speicher ausgelagert, egal ob sie häufig benutzt wird oder nicht. Die-se Ineffizienz wird beim Second-Chance-Algorithmus vermieden. Dieser führt im Groben folgende Schritte aus: 1. Das Accessed Bit der ältesten Seite im Speicher wird kontrolliert. Wie beim FIFO-

Verfahren befindet sich eine Liste von allen Seiten im Speicher. Seiten, die neu eingela-gert werden, werden hinten an die Liste angehängt, dh die älteste Seite befindet sich am Listenanfang.

2. Ist das Accessed Bit der ältesten Seite auf 1 gesetzt, weiß man, dass diese Seite schon einmal gelesen bzw. geschrieben wurde. Das Accessed Bit wird auf 0 gesetzt, die Seite an das Ende der Liste angehängt und die Ladezeit auf die aktuelle Zeit gesetzt. Es sieht jetzt so aus, als ob diese Seite gerade erst geladen wurde.

3. Ist das Accessed Bit der ältesten Seite nicht gesetzt, weiß man, dass sie nie benutzt wurde. Man kann sie also sofort ersetzen. Dazu muss man das Dirty-Bit kontrollieren.

prOSt Dokumentation

35

4. Ist das Dirty-Bit auf 1 gesetzt, weiß man, dass die Seite geschrieben wurde. Man muss sie also bevor sie überschrieben wird auf die Festplatte zurück schreiben, damit dort die Da-ten aktuell sind.

5. Ist das Dirty-Bit auf 0, weiß man, dass die Seite nie geschrieben wurde und man kann sie einfach überschreiben.

CLOCK ALGORITHM

Da beim Second-Chance-Algorithmus ständig Seiten in der Liste verschoben werden, werden beim Clock-Algorithmus die Seiten in einer ringförmigen Liste in Form einer Uhr gehalten. Der Uhrzeiger zeigt immer auf die älteste Seite. Tritt ein Seitenfehler auf, werden bei diesem Algorithmus folgende Schritte durchgeführt: 1. Das Accessed-Bit der ältesten Seite, also die Seite auf die der Uhrzeiger zeigt, wird kon-

trolliert. 2. Ist das Accessed Bit der ältesten Seite auf 1 gesetzt, wird es gelöscht und auf 0 gesetzt und

der Uhrzeiger rückt um eine Seite vor. Dieser Vorgang wird solange wiederholt bis eine Seite mit Accessed Bit 0 gefunden wird.

3. Ist das Accessed Bit der ältesten Seite auf 0 gesetzt, wird diese Seite ausgelagert, dazu muss wieder das Dirty-Bit kontrolliert werden. Die neue Seite wird an dieser Stelle einge-fügt und der Uhrzeiger rückt um eine Seite weiter.

Die Ergebnisse der Tests für Projekt 3 sind im Abschnitt 8.3 zu finden.

prOSt Dokumentation

36

7. TESTS In der Datei „constants.h“ befinden sich die Systemparameter. Für unsere Testprogramme kann man hier Einstellungen für die Ausgabe vornehmen.

8.1 PROJEKT 1: THREADS Die Testprogramme für Projekt 1 befinden sich im Verzeichnis “Projekt1/tests/threads“. ALARM-SINGLE

prOSt booting with 4,096 kB RAM...

Kernel command line: run alarm-single

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'alarm-single':

(alarm-single) begin

(alarm-single) Creating 5 threads to sleep 1 times each.

(alarm-single) Thread 0 sleeps 10 ticks each time,

(alarm-single) thread 1 sleeps 20 ticks each time, and so on.

(alarm-single) If successful, product of iteration count and

(alarm-single) sleep duration will appear in nondescending order.

(alarm-single) thread 0: duration=10, iteration=1, product=10

(alarm-single) thread 1: duration=20, iteration=1, product=20

(alarm-single) thread 2: duration=30, iteration=1, product=30

(alarm-single) thread 3: duration=40, iteration=1, product=40

(alarm-single) thread 4: duration=50, iteration=1, product=50

(alarm-single) end

Execution of 'alarm-single' complete.

ALARM-MULTIPLE

prOSt booting with 4,096 kB RAM...

Kernel command line: run alarm-multiple

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'alarm-multiple':

(alarm-multiple) begin

(alarm-multiple) Creating 5 threads to sleep 7 times each.

(alarm-multiple) Thread 0 sleeps 10 ticks each time,

(alarm-multiple) thread 1 sleeps 20 ticks each time, and so on.

(alarm-multiple) If successful, product of iteration count and

(alarm-multiple) sleep duration will appear in nondescending order.

(alarm-multiple) thread 0: duration=10, iteration=1, product=10

(alarm-multiple) thread 0: duration=10, iteration=2, product=20

(alarm-multiple) thread 1: duration=20, iteration=1, product=20

(alarm-multiple) thread 2: duration=30, iteration=1, product=30

(alarm-multiple) thread 0: duration=10, iteration=3, product=30

(alarm-multiple) thread 3: duration=40, iteration=1, product=40

(alarm-multiple) thread 1: duration=20, iteration=2, product=40

(alarm-multiple) thread 0: duration=10, iteration=4, product=40

(alarm-multiple) thread 4: duration=50, iteration=1, product=50

prOSt Dokumentation

37

(alarm-multiple) thread 0: duration=10, iteration=5, product=50

(alarm-multiple) thread 2: duration=30, iteration=2, product=60

(alarm-multiple) thread 1: duration=20, iteration=3, product=60

(alarm-multiple) thread 0: duration=10, iteration=6, product=60

(alarm-multiple) thread 0: duration=10, iteration=7, product=70

(alarm-multiple) thread 3: duration=40, iteration=2, product=80

(alarm-multiple) thread 1: duration=20, iteration=4, product=80

(alarm-multiple) thread 2: duration=30, iteration=3, product=90

(alarm-multiple) thread 4: duration=50, iteration=2, product=100

(alarm-multiple) thread 1: duration=20, iteration=5, product=100

(alarm-multiple) thread 3: duration=40, iteration=3, product=120

(alarm-multiple) thread 2: duration=30, iteration=4, product=120

(alarm-multiple) thread 1: duration=20, iteration=6, product=120

(alarm-multiple) thread 1: duration=20, iteration=7, product=140

(alarm-multiple) thread 4: duration=50, iteration=3, product=150

(alarm-multiple) thread 2: duration=30, iteration=5, product=150

(alarm-multiple) thread 3: duration=40, iteration=4, product=160

(alarm-multiple) thread 2: duration=30, iteration=6, product=180

(alarm-multiple) thread 4: duration=50, iteration=4, product=200

(alarm-multiple) thread 3: duration=40, iteration=5, product=200

(alarm-multiple) thread 2: duration=30, iteration=7, product=210

(alarm-multiple) thread 3: duration=40, iteration=6, product=240

(alarm-multiple) thread 4: duration=50, iteration=5, product=250

(alarm-multiple) thread 3: duration=40, iteration=7, product=280

(alarm-multiple) thread 4: duration=50, iteration=6, product=300

(alarm-multiple) thread 4: duration=50, iteration=7, product=350

(alarm-multiple) end

Execution of 'alarm-multiple' complete.

ALARM-NEGATIVE /*Tests timer_sleep(-100). Only requirement is that it not crash.*/

prOSt booting with 4,096 kB RAM...

Kernel command line: run alarm-negative

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'alarm-negative':

(alarm-negative) begin

(alarm-negative) PASS

(alarm-negative) end

Execution of 'alarm-negative' complete.

ALARM-PRIORITY /*Checks that when the alarm clock wakes up threads, the higher-priority

threads run first.*/

prOSt booting with 4,096 kB RAM...

Kernel command line: run alarm-priority

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'alarm-priority':

(alarm-priority) begin

(alarm-priority) Thread priority 30 woke up.

(alarm-priority) Thread priority 29 woke up.

prOSt Dokumentation

38

(alarm-priority) Thread priority 28 woke up.

(alarm-priority) Thread priority 27 woke up.

(alarm-priority) Thread priority 26 woke up.

(alarm-priority) Thread priority 25 woke up.

(alarm-priority) Thread priority 24 woke up.

(alarm-priority) Thread priority 23 woke up.

(alarm-priority) Thread priority 22 woke up.

(alarm-priority) Thread priority 21 woke up.

unblock!

ab dieser Stelle ist Thread 1 mit Priority 0 lockholder!

(alarm-priority) end

Execution of 'alarm-priority' complete.

ALARM-ZERO /* Tests timer_sleep(0), which should return immediately.*/

prOSt booting with 4,096 kB RAM...

Kernel command line: run alarm-zero

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'alarm-zero':

(alarm-zero) begin

(alarm-zero) PASS

(alarm-zero) end

Execution of 'alarm-zero' complete.

PRIORITY-CHANGE /* Verifies that lowering a thread's priority so that it is no

longer the highest-priority thread in the system causes it to

yield immediately. */

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-change

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-change':

(priority-change) begin

(priority-change) Creating a high-priority thread 2.

(priority-change) Thread 2 now lowering priority.

(priority-change) Thread 2 should have just lowered its priority.

(priority-change) Thread 2 exiting.

(priority-change) Thread 2 should have just exited.

(priority-change) end

Execution of 'priority-change' complete.

PRIORITY-CONDVAR /* Tests that cond_signal() wakes up the highest-priority thread

waiting in cond_wait(). */

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-condvar

373 pages available in kernel pool.

prOSt Dokumentation

39

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-condvar':

(priority-condvar) begin

(priority-condvar) Thread priority 23 starting.

(priority-condvar) Thread priority 22 starting.

inserted back

(priority-condvar) Thread priority 21 starting.

inserted back

(priority-condvar) Thread priority 30 starting.

inserted (priority-condvar) Thread priority 29 starting.

inserted

(priority-condvar) Thread priority 28 starting.

inserted

(priority-condvar) Thread priority 27 starting.

inserted

(priority-condvar) Thread priority 26 starting.

inserted

(priority-condvar) Thread priority 25 starting.

inserted

(priority-condvar) Thread priority 24 starting.

inserted

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 30 to Thread 1!

Donationarray of 1:

1430-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 30 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 29 to Thread 1!

Donationarray of 1:

1429-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 29 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 28 to Thread 1!

Donationarray of 1:

1428-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

prOSt Dokumentation

40

(priority-condvar) Thread priority 28 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 27 to Thread 1!

Donationarray of 1:

1427-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 27 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 26 to Thread 1!

Donationarray of 1:

1426-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 26 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 25 to Thread 1!

Donationarray of 1:

1425-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 25 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 24 to Thread 1!

Donationarray of 1:

1424-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 24 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 23 to Thread 1!

Donationarray of 1:

1423-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

prOSt Dokumentation

41

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 23 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 22 to Thread 1!

Donationarray of 1:

1422-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 22 woke up.

(priority-condvar) Signaling...

incremented Donation-counter: 1

donated priority 21 to Thread 1!

Donationarray of 1:

1421-1-1-1

-1-1-1-1-1

-1-1-1-1-1

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-condvar) Thread priority 21 woke up.

(priority-condvar) end

Execution of 'priority-condvar' complete.

PRIORITY-FIFO /* Creates several threads all at the same priority and ensures

that they consistently run in the same round-robin order.*/

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-fifo

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-fifo':

(priority-fifo) begin

(priority-fifo) 16 threads will iterate 16 times in the same order each

time.

(priority-fifo) If the order varies then there is a bug.

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

prOSt Dokumentation

42

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) iteration: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(priority-fifo) end

Execution of 'priority-fifo' complete.

PRIORITY-PREEMPT /* Ensures that a high-priority thread really preempts.*/

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-preempt

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-preempt':

(priority-preempt) begin

(priority-preempt) Thread high-priority iteration 0

(priority-preempt) Thread high-priority iteration 1

(priority-preempt) Thread high-priority iteration 2

(priority-preempt) Thread high-priority iteration 3

(priority-preempt) Thread high-priority iteration 4

(priority-preempt) Thread high-priority done!

(priority-preempt) The high-priority thread should have already completed.

(priority-preempt) end

Execution of 'priority-preempt' complete.

PRIORITY-SEMA /* Tests that the highest-priority thread waiting on a semaphore

is the first to wake up. */

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-sema

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-sema':

(priority-sema) begin

(priority-sema) Thread priority 30 woke up.

(priority-sema) Back in main thread.

(priority-sema) Thread priority 29 woke up.

(priority-sema) Back in main thread.

(priority-sema) Thread priority 28 woke up.

(priority-sema) Back in main thread.

(priority-sema) Thread priority 27 woke up.

(priority-sema) Back in main thread.

(priority-sema) Thread priority 26 woke up.

(priority-sema) Back in main thread.

(priority-sema) Thread priority 25 woke up.

(priority-sema) Back in main thread.

(priority-sema) Thread priority 24 woke up.

(priority-sema) Back in main thread.

(priority-sema) Thread priority 23 woke up.

(priority-sema) Back in main thread.

(priority-sema) Thread priority 22 woke up.

(priority-sema) Back in main thread.

prOSt Dokumentation

43

(priority-sema) Thread priority 21 woke up.

(priority-sema) Back in main thread.

(priority-sema) end

Execution of 'priority-sema' complete.

PRIORITY-DONATE-LOWER /* The main thread acquires a lock. Then it creates a

higher-priority thread that blocks acquiring the lock, causing

it to donate their priorities to the main thread. The main

thread attempts to lower its priority, which should not take

effect until the donation is released. */

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-donate-lower

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-donate-lower':

(priority-donate-lower) begin

incremented Donation-counter: 1

donated priority 41 to Thread 1!

Donationarray of 1:

1441-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-lower) Main thread should have priority 41. Actual prior-

ity: 41.

(priority-donate-lower) Lowering base priority...

(priority-donate-lower) Main thread should have priority 41. Actual prior-

ity: 41.

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-lower) acquire: got the lock

(priority-donate-lower) acquire: done

(priority-donate-lower) acquire must already have finished.

(priority-donate-lower) Main thread should have priority 21. Actual prior-

ity: 21.

(priority-donate-lower) end

Execution of 'priority-donate-lower' complete.

PRIORITY-DONATE-MULTIPLE /* The main thread acquires locks A and B, then it creates two

higher-priority threads. Each of these threads blocks

acquiring one of the locks and thus donate their priority to

the main thread. The main thread releases the locks in turn

and relinquishes its donated priorities.*/

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-donate-multiple

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-donate-multiple':

prOSt Dokumentation

44

(priority-donate-multiple) begin

incremented Donation-counter: 1

donated priority 32 to Thread 1!

Donationarray of 1:

1432-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-multiple) Main thread should have priority 32. Actual

priority: 32.

incremented Donation-counter: 2

donated priority 33 to Thread 1!

Donationarray of 1:

1432-1-1-1

1533-1-1-1

-1-1-1-1-1

(priority-donate-multiple) Main thread should have priority 33. Actual

priority: 33.

decremented Donation-Counter: 1

nach put in ready list:

Ready-Liste 0: 2

Ready-Liste 32: 1

Donationarray of 1:

1432-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-multiple) Thread b acquired lock b.

(priority-donate-multiple) Thread b finished.

(priority-donate-multiple) Thread b should have just finished.

(priority-donate-multiple) Main thread should have priority 32. Actual

priority: 32.

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-multiple) Thread a acquired lock a.

(priority-donate-multiple) Thread a finished.

(priority-donate-multiple) Thread a should have just finished.

(priority-donate-multiple) Main thread should have priority 31. Actual

priority: 31.

(priority-donate-multiple) end

Execution of 'priority-donate-multiple' complete.

PRIORITY-DONATE-MULTIPLE2 /* The main thread acquires locks A and B, then it creates three

higher-priority threads. The first two of these threads block

acquiring one of the locks and thus donate their priority to

the main thread. The main thread releases the locks in turn

and relinquishes its donated priorities, allowing the third thread

to run.

In this test, the main thread releases the locks in a different

order compared to priority-donate-multiple.c.*/

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-donate-multiple2

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-donate-multiple2':

prOSt Dokumentation

45

(priority-donate-multiple2) begin

incremented Donation-counter: 1

donated priority 34 to Thread 1!

Donationarray of 1:

1434-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-multiple2) Main thread should have priority 34. Actual

priority: 34.

incremented Donation-counter: 2

donated priority 36 to Thread 1!

Donationarray of 1:

1434-1-1-1

1536-1-1-1

-1-1-1-1-1

(priority-donate-multiple2) Main thread should have priority 36. Actual

priority: 36.

(priority-donate-multiple2) Main thread should have priority 36. Actual

priority: 36.

decremented Donation-Counter: 1

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-multiple2) Thread b acquired lock b.

(priority-donate-multiple2) Thread b finished.

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-multiple2) Thread a acquired lock a.

(priority-donate-multiple2) Thread a finished.

(priority-donate-multiple2) Thread c finished.

(priority-donate-multiple2) Threads b, a, c should have just finished, in

that order.

(priority-donate-multiple2) Main thread should have priority 31. Actual

priority: 31.

(priority-donate-multiple2) end

Execution of 'priority-donate-multiple2' complete.

PRIORITY-DONATE-NEST /* Low-priority main thread L acquires lock A. Medium-priority

thread M then acquires lock B then blocks on acquiring lock A.

High-priority thread H then blocks on acquiring lock B. Thus,

thread H donates its priority to M, which in turn donates it

to thread L. */

prOSt booting with 4,096 kB RAM...

Kernel command line: run priority-donate-nest

373 pages available in kernel pool.

372 pages available in user pool.

Calibrating timer... 102,400 loops/s.

Boot complete.

Executing 'priority-donate-nest':

(priority-donate-nest) begin

incremented Donation-counter: 1

donated priority 32 to Thread 1!

Donationarray of 1:

1432-1-1-1

-1-1-1-1-1

prOSt Dokumentation

46

-1-1-1-1-1

(priority-donate-nest) Low thread should have priority 32. Actual prior-

ity: 32.

incremented Donation-counter: 1

donated priority 33 to Thread 3!

Donationarray of 3:

1533-1-1-1

-1-1-1-1-1

-1-1-1-1-1

nested: donated priority 33 to Thread 1!

Donationarray of 1:

143233-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-nest) Low thread should have priority 33. Actual prior-

ity: 33.

decremented Donation-Counter: 0

Donationarray of 1:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-nest) Medium thread should have priority 33. Actual pri-

ority: 33.

(priority-donate-nest) Medium thread got the lock.

decremented Donation-Counter: 0

Donationarray of 3:

-1-1-1-1-1

-1-1-1-1-1

-1-1-1-1-1

(priority-donate-nest) High thread got the lock.

(priority-donate-nest) High thread finished.

(priority-donate-nest) High thread should have just finished.

(priority-donate-nest) Middle thread finished.

(priority-donate-nest) Medium thread should just have finished.

(priority-donate-nest) Low thread should have priority 31. Actual prior-

ity: 31.

(priority-donate-nest) end

Execution of 'priority-donate-nest' complete.

prOSt Dokumentation

47

8.2 PROJEKT 2: USER PROGRAMS Mit der hex_dump()-Funktion kann man sich die Speicherbelegung ausgeben lassen. Diese hilfreiche Funktion haben wir auch bei der Belegung des Stacks für ein Benutzerprogramm benutzt. Folgende Ausgabe wird bei der Ausführung von ‚echo x y z’ geliefert: Executing 'echo x y z': Stack - virtuell:

bfffffd0 04 81 04 08-04 00 00 00 e0 ff ff bf | ............|

bfffffe0 f5 ff ff bf fa ff ff bf-fc ff ff bf fe ff ff bf |................|

bffffff0 00 00 00 00 00 65 63 68-6f 00 78 00 79 00 7a 00 |.....echo.x.y.z.|

c0000000 53 ff 00 f0 53 ff 00 f0-53 ff 00 f0 53 ff 00 f0 |S...S...S...S...|

Stack - physisch:

c02b1fd0 04 81 04 08-04 00 00 00 e0 ff ff bf | ............|

c02b1fe0 f5 ff ff bf fa ff ff bf-fc ff ff bf fe ff ff bf |................|

c02b1ff0 00 00 00 00 00 65 63 68-6f 00 78 00 79 00 7a 00 |.....echo.x.y.z.|

c02b2000 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00 |................|

x y z

Prozess echo mit exit(0) beendet

prOSt Dokumentation

48

8.3 PROJEKT 3: VIRTUAL MEMORY Die Testprogramme für Projekt 3 befinden sich ebenfalls im Verzeichnis ‚examples’. TESTMEM.C /* Dieses Tesprogramm erstellt im Virtual Memory eines Prozesses mit dem

mmap()-Systemcall Speicherabbildungen von 2 Dateien, anschließend wird e-

xit() aufgerufen und somit die Speicherabbildungen des Prozesses mit dem

munmap()-Systemcall wieder rückgängig gemacht.*/

Executing 'testmem text.txt text2.txt':

...

Seitentabelle: 134512640 134516736 134520832 134524928 -1073745920

134529024 in SPT eingefuegt!

Seitentabelle: 134512640 134516736 134520832 134524928 134529024 -

1073745920

134533120 in SPT eingefuegt!

Seitentabelle: 134512640 134516736 134520832 134524928 134529024 134533120

-1073745920

134537216 in SPT eingefuegt!

Seitentabelle: 134512640 134516736 134520832 134524928 134529024 134533120

134537216 -1073745920

gemapped!

134569984 in SPT eingefuegt!

Seitentabelle: 134512640 134516736 134520832 134524928 134529024 134533120

134537216 134569984 -1073745920

134574080 in SPT eingefuegt!

Seitentabelle: 134512640 134516736 134520832 134524928 134529024 134533120

134537216 134569984 134574080 -1073745920

134578176 in SPT eingefuegt!

Seitentabelle: 134512640 134516736 134520832 134524928 134529024 134533120

134537216 134569984 134574080 134578176 -1073745920

gemapped!

Prozess testmem mit exit(0) beendet

Wir sehen bei dieser Ausgabe unsere zusätzliche Seitentabelle vor Beginn der Speicherabbil-dungen der Dateien, diese besteht aus 5 Seiten. Danach wird test.txt mit 9,6 KB im Virtual Memory abgebildet, dh es werden 3 Seiten in die zusätzliche Seitentabelle eingetragen. Da-nach wird dasselbe mit test2.txt durchgeführt.

prOSt Dokumentation

49

8. CONCLUSIO Wir sind sehr stolz, dass wir es trotz einiger Startschwierigkeiten geschafft haben, drei von vier Projekten erfolgreich zu implementieren. Die größten Probleme hatten wir zu Beginn des Semesters beim Aufbau einer einheitlichen Entwicklungsumgebung für alle Projektmitglieder. Es hat uns sehr viel Zeit und Mühe gekos-tet das Betriebssystem-Framework Pintos und die virtuelle Maschine Bochs under Linux bzw. Windows zum Laufen zu bringen. Auch beim Einrichten und Benutzen der Subversion (SVN) hatten wir im Laufe des Semes-ters einige Probleme. Außerdem gestaltete sich das Testen bzw. Debuggen in einigen Projekten als extrem schwie-rig. Trotz Allem können wir jetzt am Ende des Semesters als Resumee ziehen, dass wir das Ziel der Lehrveranstaltung erreicht haben. Auch wenn wir es innerhalb der vorgegebenen Zeit nicht geschafft haben unser prOSt vollständig zu implementieren, können wir behaupten, dass wir jetzt verstehen, was wirklich hinter einem Betriebsystem steckt. Wenn wir unser Betriebssystem noch einmal implementieren müssten, würden wir auf jeden Fall versuchen, dass wir zu Beginn des Projektes nicht so viel Zeit verlieren, damit der Zeit-druck am Ende des Semesters nicht wieder so groß ist. Außerdem würden wir die Projekte eventuell in einer anderen Reihenfolge implementieren, als es von Pintos vorgegeben wird. Wir sollten auch noch versuchen uns nicht wieder in zu viel Details und Optimierungen zu verlieren, damit wirklich alle Projekte vollständig implementiert werden können.

prOSt Dokumentation

50

9. QUELLEN [1] Tanenbaum, Andrew S. (2002). Moderne Betriebssysteme. 2. überarbeitete Auflage.

Prentice Hall, München, Germany [2] http://bochs.sourceforge.net

Die virtuelle Maschine bochs [3] http://www.opensuse.org/

openSuSE, das zugrunde liegende Betriebssystem, auf dem bochs mit unserem Betriebssystem läuft

[4] http://sourceforge.net/project/showfiles.php?group_id=12580&package_id=17475

Downloadseite für bochs in der Version 2.2.6 [5] http://www.stanford.edu/class/cs140/pintos/pintos.tar.gz

Der Pintos-Quellcode [6] http://www.stanford.edu/class/cs140/projects/pintos/pintos.pdf Die vollständige Dokumentation von Pintos [7] http://www.gnu.org/software/gdb/gdb.html Die Webseite von gdb, dem ‘GNU Project Debugger’ [8] http://www.gnu.org/software/ddd/ Das grafische Frontend für gdb [9] http://www.eclipse.org/ Die Eclipse-IDE [10] http://www.eclipse.org/cdt/ cdt, das C-Plugin für Eclipse