Virtuelle Speicherverwaltung und Seitenersetzungsalgorithmen: Ein praktischer Leitfaden zu Page Tables und FIFO, LRU, CLOCK & OPT

Einleitung: Warum virtuelle Speicherverwaltung heute wichtiger denn je ist

Im Mai 2026, wo selbst Smartphones mit 16 GB RAM ausgestattet sind und KI-Assistenten wie ChatGPT-8 riesige Modelle im Speicher halten, ist das Verständnis von virtuellem Speicher und Seitenersetzungsalgorithmen entscheidend. Stell dir vor, du spielst das neueste Open-World-Game auf deinem Laptop – die Map lädt nahtlos, weil das Betriebssystem geschickt zwischen RAM und Swap-Datei wechselt. Genau das simulierst du in diesem Assignment: Page Tables und Algorithmen wie FIFO, LRU, CLOCK und OPT. Dieser Leitfaden hilft dir, die Konzepte hinter Csc369 Assignment 3 zu verstehen, ohne deine eigene Implementierung vorwegzunehmen.

Grundlagen: Was sind Page Tables und warum zwei Ebenen?

Ein Page Table ist die Übersetzungstabelle zwischen virtuellen und physischen Adressen. Moderne Systeme verwenden oft mehrstufige Page Tables, um Speicher zu sparen. In deiner Simulation nutzt du eine zweistufige Page Table: ein Page Directory (erste Ebene) und Page Tables (zweite Ebene). Jeder Eintrag im Page Directory zeigt auf eine Page Table, und jeder Page Table Eintrag (PTE) enthält die Frame-Nummer oder einen Swap-Offset. Die unteren 12 Bits eines PTE sind für Statusflags reserviert – z.B. ob die Seite gültig ist oder ob sie im Swap liegt. Wenn du find_physpage implementierst, übersetzt du eine virtuelle Adresse in eine physische, indem du die Bits der Adresse aufteilst: Directory-Index, Table-Index und Offset. Ein typischer Fehler ist, die Bitverschiebung für die Frame-Nummer zu vergessen – denk dran: frame_number << PAGE_SHIFT.

Demand Paging: Seiten nur laden, wenn sie gebraucht werden

Demand Paging bedeutet, dass eine Seite erst dann in den RAM geladen wird, wenn ein Programm darauf zugreift. Das spart Speicher und beschleunigt den Start. In deiner Simulation wird bei einem Page Fault die Seite aus der Swap-Datei geholt. Der Swap-Bereich ist so groß wie die Anzahl eindeutiger virtueller Seiten im Trace. Du musst also die maximale Anzahl an Seiten kennen, um den Swap zu dimensionieren. Ein guter Tipp: Zähle die eindeutigen virtuellen Seiten im Trace, bevor du die Simulation startest.

Seitenersetzungsalgorithmen: FIFO, LRU, CLOCK und OPT

Sobald der physische Speicher voll ist, muss eine Seite ersetzt werden. Hier kommen die Algorithmen ins Spiel. Jeder hat seine Stärken und Schwächen – vergleichbar mit verschiedenen Strategien in der Champions League: FIFO ist wie ein starres Abwehrsystem, LRU wie ein Trainer, der immer den zuletzt eingesetzten Spieler auswechselt, CLOCK wie ein Schiedsrichter, der nur ein Auge auf die Spieler hat, und OPT wie ein Orakel, das die Zukunft kennt.

FIFO (First-In-First-Out)

FIFO ersetzt die Seite, die am längsten im Speicher ist. Einfach zu implementieren: Du fügst neue Seiten am Ende einer Warteschlange hinzu und ersetzt die vorderste. Aber Vorsicht: FIFO leidet unter dem Belady's Anomaly – mehr Speicher kann zu mehr Seitenfehlern führen. In deiner Implementierung speicherst du die Einfügereihenfolge in der struct frame. Ein Tipp: Verwende einen zirkulären Index oder einen Timestamp.

Exaktes LRU (Least Recently Used)

LRU ersetzt die Seite, die am längsten nicht benutzt wurde. Das ist intuitiv und meist effizient, aber aufwändig zu implementieren. Du kannst einen Timestamp pro Frame speichern und bei jedem Zugriff aktualisieren. Oder du verwendest eine Liste, die bei jedem Zugriff die Seite nach vorne bewegt. In deiner Simulation musst du die Zugriffsreihenfolge genau verfolgen. LRU ist der Goldstandard – ähnlich wie ein KI-Modell, das selten genutzte Daten aus dem Cache wirft.

CLOCK (mit einem Referenzbit)

CLOCK ist eine Näherung an LRU mit geringerem Aufwand. Jeder Frame hat ein Referenzbit, das bei Zugriffen gesetzt wird. Der Algorithmus durchläuft die Frames im Kreis (wie ein Uhrzeiger) und ersetzt den ersten Frame mit Bit 0. Wenn das Bit 1 ist, wird es auf 0 gesetzt und weitergemacht. Das ist effizient und vermeidet die Kosten eines exakten LRU. In deiner Implementierung brauchst du einen Zeiger, der sich im Kreis bewegt. CLOCK wird in vielen echten Betriebssystemen verwendet – z.B. im Linux-Kernel.

OPT (Optimaler Algorithmus)

OPT ersetzt die Seite, die am längsten nicht mehr benötigt wird. Dazu musst du die Zukunft kennen – in einer Simulation ist das möglich, weil der gesamte Trace vorliegt. OPT dient als Benchmark: Kein Algorithmus kann besser sein. In deiner Implementierung berechnest du für jede Seite den nächsten Zugriffszeitpunkt und ersetzt die mit dem spätesten. Das ist zwar rechenintensiv, aber für die Auswertung unverzichtbar.

Praktische Umsetzung: Tipps zu den Datenstrukturen

In pagetable.h kannst du Felder für die Algorithmen hinzufügen. Markiere sie klar, z.B. int lru_timestamp oder int fifo_queue_next. Für CLOCK brauchst du ein int ref_bit und einen globalen Zeiger clock_hand. Achte darauf, dass deine Änderungen nicht mit der vorhandenen struct frame kollidieren. Die coremap ist ein Array von Frames – jedes Element repräsentiert einen physischen Frame. Wenn du einen Frame freigibst, setze in_use auf 0 und aktualisiere die Algorithmus-spezifischen Felder.

Trace-Programme und Auswertung

Du bekommst drei Trace-Programme und sollst ein viertes mit interessantem Speicherverhalten wählen. Das kann ein Spiel-Trace sein oder ein KI-Inferenz-Trace. Führe die Simulation für Speichergrößen 50, 100, 150 und 200 Frames durch. Notiere Hit Rate, Hit Count, Miss Count, Eviction Count (gesamt, clean, dirty). Dirty Pages sind solche, die beschrieben wurden und auf die Festplatte zurückgeschrieben werden müssen. Die Tabellen helfen dir, die Algorithmen zu vergleichen. Erwarte, dass OPT die höchste Hit Rate hat, gefolgt von LRU und CLOCK, während FIFO oft schlechter abschneidet. Mit steigender Speichergröße verbessert sich LRU stetig, während FIFO manchmal sogar schlechter wird (Belady).

Vergleich der Algorithmen: Was die Tabellen verraten

In deinem README vergleichst du die Ergebnisse. Typischerweise zeigt OPT die wenigsten Page Faults, da es die Zukunft kennt. LRU ist nah dran, aber teurer. CLOCK ist ein guter Kompromiss. FIFO ist einfach, aber anfällig für Anomalien. Achte darauf, dass die Dirty Eviction Counts bei Algorithmen mit vielen Ersetzungen höher sind – das bedeutet mehr I/O. Ein interessanter Trend: Bei LRU sinkt die Miss Rate mit mehr Speicher fast linear, während FIFO Plateaus haben kann.

Häufige Fehler und wie du sie vermeidest

• Bitverschiebung vergessen: Die Frame-Nummer muss um PAGE_SHIFT nach links verschoben werden, um Platz für Statusbits zu lassen.
• Swap-Größe falsch berechnet: Bestimme die Anzahl eindeutiger virtueller Seiten vorab, sonst läuft der Swap über.
• Referenzbit in CLOCK nicht aktualisiert: Setze das Bit bei jedem Zugriff, sonst funktioniert der Algorithmus nicht.
• LRU-Timestamp nicht monoton: Verwende einen globalen Zähler, der bei jedem Zugriff inkrementiert wird.

Fazit: Von der Theorie zur Praxis

Dieses Assignment ist eine hervorragende Gelegenheit, die Theorie der virtuellen Speicherverwaltung praktisch zu erleben. Die Algorithmen, die du implementierst, stecken in jedem Betriebssystem – von deinem Smartphone bis zum Supercomputer. Wenn du die Konzepte verstehst, kannst du auch moderne Entwicklungen wie Caching in KI-Chips oder Speichermanagement in Cloud-Systemen besser nachvollziehen. Viel Erfolg bei deiner Implementierung!