Virtueller Speicher

Aufgaben des Speicherverwalters

• Verwaltung der freien und belegten Speicherbereiche
• Zuweisung von Speicherbereichen an Prozesse (nach Bedarf)
• Freigaben, wenn Prozesse abgeschlossen sind
• Durchführung von Auslagerungen zwischen Hauptspeicher und Platte

Virtueller Speicher Grundlagen

Problem: Arbeitsspeicher ist zu klein

Idee: Arbeitsspeicher und Externspeicher logisch so zu vereinen, dass sie wie ein einziger Speicher wirken.

Mit anderen Worten: Wir haben z.B. 256 MiB Hauptspeicher (RAM), gaukeln den Programmen aber z.B. 4 GiB verfügbaren Speicherbereich vor, stellen einen Adressraum von 4 GiB zur Verfügung. Der Trick dabei: Wir borgen uns den Speicher von der Festplatte.

Adressübersetzung

Bei modernen Betriebs-Systemen (BS, engl. OS für Operating System) bekommt jedes Programm einen eigenen Speicherbereich, dieser Bereich beginnt aus Sicht des Programms z.B. bei der Adresse 0. Das ist mit realem Speicher schlecht möglich, denn es gibt die Adresse 0 ja nur einmal real! Daher wird für jedes gestartete Programm seine Adresse 0 auf einen eigenen realen Hauptspeicherbereich abgebildet (übersetzt, transformiert), seine Adresse 0 existiert tatsächlich nur virtuell.

Hardware hilft

Hier kommt die Hardware eines Rechners ins Spiel, die Übersetzung muss besonders schnell sein, daher lohnt es sich das Ganze in Hardware zu bauen: Es gibt eine besondere Funktion des Chip-Satzes -die "Memory Management Unit" kurz die MMU

Lokalität und Seiten

Wie man leicht erkennen kann, wird so der Hauptspeicher schnell knapp. Man konnte jedoch folgendes über Programme in Erfahrung bringen:

• Programme die nichts zu tun haben brauchen "ihren" Speicher gerade nicht.
• Es gibt Programme, die sich viel "merken" es aber selten brauchen.
• Wenn Programme richtig arbeiten, tun sie es oft nur auf wenigen Speicherbereichen ihres Gesammtspeichers (Programm- und Daten-Bereich)

Erkenntnis: Anwendungen nutzen den Speicher gar nicht richtig intensiv! Warum ihnen nicht nur den Bereich geben, den sie grade brauchen?

Idee: Gib jedem das was er am dringensten braucht! Aber es sollte effektiv zu handhaben sein!!

Lösung: Unterteile den Hauptspeicher in Seiten (engl. Pages) einer optimalen einheitlichen Grösse und stimme alles darauf ab (eine einheitliche Grösse ist praktischer für die Handhabung durch BS und Hardware)! Der virtuelle Adressraum der Programme wird in eben solche Seiten unterteilt. Also die kleinste Einheit ist nun eine Seite (1 KiB .. 32 KiB je nach BS). Weil selten der gesammte virtuelle Speicherbereich eines Programms (Prozesses) benötigt wird, reicht es, eine jeweils kleine Menge von Seiten im Hauptspeicher zu halten. Nebenbei beschützt dieses Verfahren auch die Programme voreinander, keiner kann in den Speicherbereich des anderen greifen.

Arbeitsteilung MMU und BS (Hardware gegen Software)

Die MMU kümmert sich um das was innerhalb einer im Hauptspeicher befindlichen Seite passiert. Wenn ein Zugriff auf eine Adresse geschieht, für die sich im Haupspeicher keine Seite befindet, gibt sie einen Interrupt aus, eine Exception namens "Page Fault", nun ist das BS dran! Das BS trägt die Verantwortung für das Datei-System und damit für die Festplatte(n), somit muss es sich um fehlende Seiten im virtuellen Hauptspeicher kümmern.

MMU-Job

Programm A will auf virtuelle Speicheradresse x zugreifen, ist sie im Hauptspeicher, dann übersetze und adressiere sie real, sonst gib einen "Page Fault" aus, damit das BS die passende Seite lädt.

Welche Information muss die MMU vorhalten, um diesen Job erledigen zu können?

BS-Job

Stelle der MMU die Übersetzungstabelle des jeweiligen Prozesses zur Verfügung. Wenn die MMU einen Page-Fault meldet, stelle die benötigte Seite im Hauptspeicher bereit.

Adressübersetzung, Transformation

Die Materie ist relativ komplex, hier soll nur das Prinzip verdeutlicht werden anhand einer einstufigen Adressübersetzung, es gibt noch:

• Mehrstufige Tabellen
• Virtuelle Übersetzungstabellen
• Invertierte Übersetzungstabellen

Hintergrund: Beim einstufigen Verfahren werden die Tabellen zu groß!

Einstufige Adressübersetzung

Beispiel: Bei einem byteweise organisiertem Speicher sei der Virtueller Adressbereich 4 GiB = 2³² Adressen -> 32 Bit Adressbus, die Seitengrösse sei 4 KiB = 2¹² Adressen = 12 Bit-Adressen innerhalb einer Seite (nennt man Offset). Somit braucht man 32-12= 20 Bit um die einzelnen Seiten (nennt man Seitennummer) zu adressieren!

Die MMU soll nun entscheiden ob sich eine virtuelle Adresse im Hauptspeicher befindet und wenn ja wo.

Wie viele Einträge hat in unserem Beispiel die Übersetzungstabelle? 2²⁰ = 1 Mi

Information eines Übersetzungs-Tabellen-Eintrags

Hier nur ein didaktisches Beispiel, die realen Verhältnisse hängen vom Betriebssystem und der Hardware ab!

• Ist Seite vorhanden?
• Stimmt Seite im Hauptspeicher mit der Festplattenseite überein ("clean" oder "dirty")?
• Wie lautet die reale Seitenadresse im Hauptspeicher?

Beispiel für max. 16 GByte = 2³⁴ Byte Hauptspeicher

Ein Eintrag benötigt hier 24 Bit = 3 Byte.

Beispiel: Die Seitengrösse betrage 1 KiByte, ein Prozess belege 16 KiByte virtuellen Speicher der reale Speicher sei 1MiByte gross.

Wie viele Zeilen hat die Seitentabelle? Antwort: 16 KiByte / 1 KiByte = 16

Die Staus-Info benötigt 2 Bit, wie viele Bit benötigt die reale Seitennummer in unserem Beispiel? Antwort: log₂ (1 MiByte / 1 KiByte) = 10

Die virtuelle Adresse 0x2CFE soll angesprochen werden. In welcher Zeile der Seitentabelle findet sich die physikalische Adresse? Antwort: Trunc (0x2CFE / 1024) = 11 Erläuterung: Trunc (0x2CFE / 1024) bedeutet die hinteren 10 Bit abzuschneiden: 0010 1100 1111 1110 -> 00 1011

Aufgabe [nach Handreichung LS Stuttgart H-05/101]: Ein Prozess benötigt einen Speicher von 8 KiByte, der Speicher ist in Seiten zu je 2 KiByte unterteilt.

1. Aus wie vielen Seiten besteht der virtuelle Speicher des Prozesses und wie lauten die Anfangs- und Endadressen der Seiten (in Hex angeben)? Antwort: 4 Seiten: 0 - 0x7FF; 0x800 - 0xFFF; 0x1000 - 0x17FF; 0x1800 - 0x1FFF;

2. Folgende Seitentabelle des Prozesses sei gegeben:

PB3 und PB4 sind Plattenblöcke, die anderen Adressen liegen im Hauptspeicher.

Der Prozess liest nun die virtuellen Adressen 0x100A und 0x1810.

Geben Sie für die beiden virtuellen Adressen die zugehörige reale Arbeitsspeicheradresse (falls sich die Seite im Arbeitsspeicher befindet) bzw. die Nummer des Plattenblocks und den Offset innerhalb des Plattenblocks (falls die Seite momentan auf dem Plattenspeicher steht) an.

Antwort: 0x100A liegt auf PB4 Byte 10; 0x1810 liegt im Arbeitsspeicher auf 0x810 bzw. 2048 + 16 = 2064

3. Erklären Sie, wie das Betriebssystem auf eine virtuelle Adresse reagiert, die auf den Plattenspeicher zeigt. Antwort: Das BS holt die Seite von der Festplatte in den Arbeitsspeicher, ist dafür zunächst kein Platz wird zuvor eine andere Seite aus dem Arbeitsspeicher verdrängt, auf Platte ausgelagert.

Fragen

Warum funktioniert das Auslagern auf ca. 1000 mal langsamere Festplatte so gut, was "treibt" so ein Programm tatsächlich mit so viel Speicher? Lokalitäts-Prinzip: Anwendungen verwenden meist nur einen kleinen Teil ihrer Sub-Routienen zur selben Zeit. Die Verarbeitung geschiet oft nur in einem kleinen Teil des Daten-Raums..

Wie teilt man den "teuren" Hauptspeicher auf viele Programme am besten auf? Der Hauptspeicher wird portioniert und entsprechend verschiedener Strategien zugeteilt. Leider gibt es nicht die beste Lösung, nur einige Strategien

Wie sieht ein Eintrag in der Übersetzungstabelle aus?

Wie lautet die Berechnungsvorschrift um an den Eintrag zu kommen (die Adresse des Eintrags in der Tabelle zu berechnen)?

Teilen und Herrschen

Gegeben ist ein byteweise organisierter Speicher mit 1 MiB. Der Speicher soll in 1 KiB grossen Blöcken (Seiten) verwaltet werden.

• Wie viele Adressleitungen werden für den gesammten Speicher benötigt? Jedes Byte soll adressiert werden, daher 2²⁰ Adressen => 20 Leitungen
• Wie viele 1 KiB-Seiten gibt es? 1024 Seiten a 1024 Byte ergeben 1 MIB
• Wie viele Adressleitungen benötigt man zur Adressierung innerhalb einer Seite (Offset-Adressen)? 1024 = 2¹⁰ => 10 Leitungen
• Wie viele Adressleitungen benötigt man zur Adressierung der einzelnen Seiten? 1024 = 2¹⁰ => 10 Leitungen