« »

GRABS Übungsaufgaben Virtueller Speicher Mehrstufiges Paging

Mehrstufiges Paging

Ein Rechner mit seitenbasiertem virtuellem Speicher hat einen physischen Speicher mit $2^{32}$ adressierbaren Byte und einer Seitengröße von 8 KiB. Jedem Prozess wird ein virtueller Adressraum von 4 GiB zugewiesen. Seitentabelleneinträge sind 32 Bit groß. Die Seitentabellen werden im auslagerbaren Speicher gehalten.

a)

Level 3: Anwenden

Warum ist einstufiges Paging für dieses System ungeeignet?

Lösung
  • einstufiges Paging: Die erste (und einzige) Ebene der Tabelle hat Platz für alle Seiteneinträge.
  • Anzahl der Seiten je Prozess: 4 GiB ÷ 8 KiB = $2^{32} ÷ 2^{13} = 2^{32−13} = 2^{19}$
  • Größe der Seitentabelleneinträge: 32 Bit = 4 Byte
  • Größe der Seitentabelle je Prozess: $2^{19} · 2^2$ Byte = $2^{21}$ Byte = 2 MiB
  • verschwendet also Speicherplatz, insbesondere, wenn viele Seitentabelleneinträge nicht gefüllt sind

b)

Level 1: Wissen

Wie funktioniert zweistufiges Paging im Allgemeinen und welche Abwägungen müssen bedacht werden?

Lösung

Allgemein:

  • im Gegensatz zu einstufigem Paging gibt es beim zweistufigen Paging zwei Tabellenarten:
    • Seitenverzeichnis (Index für die Seitentabellen)
    • (kleinere) Seitentabellen
  • Virtuelle Adresse wird in Verzeichnisindex, Seitentabellenindex und Offset zerlegt

Seitentabellenstruktur = Kompromiss

  • einerseits: Tabelle soll möglichst klein sein
  • andererseits: mehr Stufen bedeuten mehr Suchaufwand im Falle eines TLB-Fehlzugriffs

Alternatives Beispiel: virtuelle 32-Bit-Adressen in der sv32-Seitentabellenstruktur von RISC-V (RV32)

  • Seitentabellen der Ebenen 0 und 1 haben 1024 Einträge oder weniger (siehe Teilaufgabe c)
  • eine Seitentabelle passt somit direkt in eine Seite des virtuellen Speichersystems
  • folglich: zweistufige Seitentabelle mit $2^{32-2·10}$ B = $2^{12}$ B = 4.096 KiB je Seite und $2^{10} = 1024$ Einträgen für Ebene 0 und 1

c)

Level 3: Anwenden

Wie viele Bits würden bei zweistufigem Paging den beiden Stufen zugeteilt werden? Welche Abwägungen spielen bei dieser Design-Entscheidung eine Rolle? Bedenken Sie, dass Seitenverzeichnisse und Seitentabellen üblicherweise je einen kompletten Seitenrahmen belegen.

Hinweis
  • eine zweistufige Seitentabelle teilt eine virtuelle Adresse in drei Teile auf
  • Offset beträgt 13 Bit (Seitengröße von 8 KiB = $2^{13}$ Byte)
  • verbleibende Bit: 32 - 13 = 19 → in zwei Hälften aufgeteilt
+----------------------------+-------------------------+---------------+
| Verzeichnisindex (level 1) | Tabellenindex (level 0) | Seiten-Offset |
+----------------------------+-------------------------+---------------+
 31                         ? ?                      13 12            0
Lösung

Idee 1: 9 Bit für einen Eintrag der Ebene 1, 10 Bit für einen Eintrag der Ebene 0

  • Größe des Verzeichnisses und der Tabellen:
    • Seitenverzeichnis: $2^{9}$ Einträge · 4 Byte je Eintrag = 2.048 Byte
    • Seitentabellen: $2^{10}$ Einträge · 4 Byte je Eintrag = 4.096 Byte
  • Speicherplatzauslastung bei voller Belegung:
    • Seitenverzeichnis nutzt 2 KiB von 8 KiB
    • Seitentabellen nutzen 4 KiB von 8 KiB
    • insgesamt: (2 KiB + $2^9$ · 4 KiB) ÷ (8 KiB + $2^9$ · 8 KiB) = 2.050 KiB ÷ 4.104 KiB
    • somit etwa 50 % verschwendet

Ideen zur Optimierung:

  • je mehr Ebenen es gibt, desto mehr Seitentabellen gibt es
  • auf den unteren Ebenen gibt es exponentiell mehr als auf den oberen
  • verschwendeter Platz auf den unteren Ebenen darum besonders schwerwiegend
  • folglich: auf den unteren Ebenen den gesamten Speicherplatz nutzen, verbleibende Bits für das Seitenverzeichnis nutzen

Idee 2: 8 Bit für einen Eintrag der Ebene 1, 11 Bit für einen Eintrag der Ebene 0

  • Größe des Verzeichnisses und der Tabellen:
    • Seitenverzeichnis: $2^{8}$ Einträge · 4 Byte je Eintrag = 1.024 Byte
    • Seitentabellen: $2^{11}$ Einträge · 4 Byte je Eintrag = 8.192 Byte
  • Speicherplatzauslastung bei voller Belegung:
    • Seitenverzeichnis nutzt 1 KiB von 8 KiB
    • Seitentabellen nutzen 8 KiB von 8 KiB
    • insgesamt: (1 KiB + $2^8$ · 8 KiB) ÷ (8 KiB + $2^8$ · 8 KiB) = 2.049 KiB ÷ 2.056 KiB
    • somit nur etwa 0,3 % verschwendet

Lernziele

In dieser Aufgabe …

  • analysieren die Studierenden den Speicherbedarf des einstufigen Pagings.
  • reproduzieren die Studierenden den Kompromiss, der mit mehrstufigem Paging verbunden ist.
  • untersuchen die Studierenden die interne Fragmentierung der Seitentabellenstruktur bei unterschiedlichen Adressaufteilungen.