« »

GRABS Übungsaufgaben Virtueller Speicher Übersetzung virtueller Adressen

Übersetzung virtueller Adressen

Sie untersuchen den Speicher eines 32-Bit RISC-V-Prozessors und gelangen zu dem folgenden Diagramm:

Diagramm zur Adressübersetzung. Die virtuelle Adresse ist aufgeteilt in 10 Bit für L2, 10 Bit für L1 und 12 Bit für den Offset. Die physische Adresse alloziert 20 Bit für PPN und 12 Bit für den Offset. Das Diagramm zeigt außerdem drei Tabellen. Ein mit “satp” beschrifteter Pfeil zeigt auf Zeile 0 einer Tabelle mit dem Namen “Page directory”. Die Tabelle enthält folgende vier Einträge: Zeile 0 mit PPN “0x00000” und Flags “V”. Zeile 1 mit PPN “0x2020” und Flags “V”. Zeile 2 mit PPN “0x01234” und Flags “V”. Zeile 3 mit PPN “0x02040” und Flags “V”. Ein mit dem Wert “0x02020000” beschrifteter Pfeil zeigt auf Zeile 0 einer weiteren Tabelle mit dem Namen “Page table”. Diese hat folgende vier Einträge: Zeile 0 mit PPN “0xD0017” und Flags “–”. Zeile 1 mit PPN “0xBA5ED” und Flags “VRX”. Zeile 2 mit PPN “0x1005E” und Flags “VRW”. Zeile 3 mit PPN “0xF00D1” und Flags “VRW”. Ein mit dem Wert “0x02040000” beschrifteter Pfeil zeigt auf Zeile 0 einer weiteren Tabelle mit dem Namen “Page table”. Diese hat folgende vier Einträge: Zeile 0 mit PPN “0x13371” und Flags “VRW”. Zeile 1 mit PPN “0xFEE75” und Flags “VRX”. Zeile 2 mit PPN “0xBABE5” und Flags “–”. Zeile 16 mit PPN “0xF0015” und Flags “VRX”. Die Bedeutung der Flags wird durch eine Legende erklärt: “V” für “Valid”, “R” für “Read”, “W” für “Write” und “X” für “Execute”.

Bestimmen Sie für die angegebene zweistufige Seitentabelle die jeweiligen physischen Adressen zu den folgenden virtuellen Adressen.

Diese Aufgabe war Teil der Klausur im Sommersemester 2024 (Zweittermin).

a)

Level 3: Anwenden

Virtuelle Adresse 0x00C02CCC

Lösung 
   0    0    C    0    2    C    C    C (hex)
0000 0000 1100 0000 0010 1100 1100 1100 (binär)
VVVV VVVV VVTT TTTT TTTT OOOO OOOO OOOO

(V = Verzeichnis, T = Tabelle, O = Offset)
  • Index des Seitenverzeichnisses (level 1): 3 → zeigt auf Seitentabelle 0x02040000
  • Index des Seitentabelleneintrags (level 0): 2 → zeigt auf die physische Seitenzahl 0xBABE5
  • gemeinsam mit dem Offset 0xCCC (niedrigste 12 Bit) ergibt sich:

Physische Adresse: 0xBABE5CCC.

b)

Level 3: Anwenden

Virtuelle Adresse 0x00400000

Lösung 
   0    0    4    0    0    0    0    0 (hex)
0000 0000 0100 0000 0000 0000 0000 0000 (binär)
VVVV VVVV VVTT TTTT TTTT OOOO OOOO OOOO

(V = Verzeichnis, T = Tabelle, O = Offset)

Adresse in Einzelteile zerlegen:

  • Index des Seitenverzeichnisses (level 1): 1
  • Index des Seitentabelleneintrags (level 0): 0
  • Offset: 0x000 (niedrigste 12 Bit)

Adresse übersetzen:

  • Seitenverzeichnis an Index 1 zeigt auf Seitentabelle 0x02020000
  • Seitentabelle 0x02020000 an Index 0 zeigt auf die physische Seitenzahl 0xD0017
  • gemeinsam mit dem Offset ergibt sich:

Physische Adresse: 0xD0017000

c)

Level 3: Anwenden

Virtuelle Adresse 0x00401124

Lösung 
   0    0    4    0    1    1    2    4 (hex)
0000 0000 0100 0000 0001 0001 0010 0100 (binär)
VVVV VVVV VVTT TTTT TTTT OOOO OOOO OOOO

(V = Verzeichnis, T = Tabelle, O = Offset)
  • Index des Seitenverzeichnisses (level 1): 1 → zeigt auf Seitentabelle 0x02020000
  • Index des Seitentabelleneintrags (level 0): 1 → zeigt auf die physische Seitenzahl 0xBA5ED
  • gemeinsam mit dem Offset 0x124 (niedrigste 12 Bit) ergibt sich:

Physische Adresse: 0xBA5ED124

d)

Level 3: Anwenden

Die folgenden vier Instruktionen werden nacheinander (Reihenfolge 1, 2, 3, 4) ausgeführt.

la   a0, 0x00400124
lw   a1, 0(a0)
addi a0, a0, 0x1000
sw   a1, 0(a0)

Das Programm löst zwei Seitenfehler aus. Geben Sie jeweils an, in welcher Zeile ein Seitenfehler (en. Page Fault) ausgelöst wird, auf welche physische Adresse (wenn vorhanden) zugegriffen werden sollte und geben Sie an, was die Ursache für den Seitenfehler ist. Nutzen Sie hierfür die oben angegebene Seitentabelle.

Hinweis: Gehen Sie davon aus, dass das Laden von Instruktionen keine Seitenfehler auslöst.

Lösung

Ablauf:

  • Zeile 1: Die virtuelle Adresse 0x00400124 wird in a0 gespeichert.
    • Die physische Seitennummer (PPN) entspricht 0xD0017 (siehe Teilaufgabe b).
  • Zeile 2: Der Wert an der Adresse, die in a0 gespeichert ist, wird geladen und in a1 gespeichert.
  • Zeile 3: Auf die Adresse in a0 wird 0x1000 addiert → 0x00401124.
    • Die physische Seitennummer (PPN) entspricht nun 0xBA5ED (siehe Teilaufgabe c).
  • Zeile 4: Der Wert in a1 wird im Speicher an die Adresse geschrieben, die in a0 gespeichert ist.

Erster Seitenfehler:

  • Auslöser: Zeile 2
  • Physische Adresse: 0xD0017124
  • Ursache: Seitentabelleneintrag weist keine Berechtigungen aus, Eintrag ungültig (fehlendes V-Bit)

Zweiter Seitenfehler:

  • Auslöser: Zeile 4
  • Physische Adresse: 0xBA5ED124
  • Ursache: Seitentabelleneintrag weist keine Schreibberechtigung aus (W-Bit nicht gesetzt)

e)

Level 3: Anwenden

Zusatzaufgabe: Folgende zusätzliche Aufgaben können zum Üben verwendet werden. Alle Lösungen befinden sich im folgenden Lösungsblock.

  1. Bestimmen Sie die physische Adresse zur virtuellen Adresse 0x00403003.
  2. Auf welchen Index in welcher Seitentabelle zeigt die virtuelle Adresse 0x007FFFFF?
  3. Löst der Versuch, im Speicher einen Wert an die Adresse 0x00C10C10 zu schreiben, einen Seitenfehler aus?
Lösung
  1. Physische Adresse: 0xF00D1003.
  2. Index 1023 in Seitentabelle 0x02020000.
  3. Physische Adresse: 0xF0015C10. Seitenfehler, da keine Schreibberechtigung gegeben (W-Bit nicht gesetzt).

Lernziele

In dieser Aufgabe …

  • üben die Studierenden das Ablesen von physischen Adressen anhand einer mehrstufigen Seitentabellenstruktur.
  • erkennen die Studierenden das Auftreten eines Page Faults anhand der Seitentabellen- und -verzeichniseinträge.
  • stellen die Studierenden eine Verbindung zwischen Speichermanagement und der Programmausführung her.