Virtuelle Speicherverwaltung

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Virtueller Speicher)
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.
Für dieses wichtige informationstechnische Konzept fehlen noch Belege, Hintergründe, Details etc.
Schemabild der Anwendung des virtuellen Speichermanagement:
links: virtueller Speicherraum pro Prozess, Speicher ist linear und unfragmentiert
rechts: reale Speicherquellen, typischerweise RAM oder Festplatte, mehrere, auch kleine Speicherfragmente können verwendet werden; in rot Speicherverwendung anderer Prozesse, unsichtbar im virtuellen Speicherraum

Die virtuelle Speicherverwaltung (engl. virtual memory management) ist eine spezielle Speicherverwaltung in einem Computer. Die Übersetzung des englischen Begriffs stellt eine Hypallage dar – nicht der Verwaltungsvorgang, sondern der zu verwaltende Speicher ist virtuell. Der virtuelle Speicher bezeichnet den vom tatsächlich vorhandenen Arbeitsspeicher unabhängigen Adressraum, der einem Prozess vom Betriebssystem zur Verfügung gestellt wird.

Das Konzept entstand in den 1950er Jahren und findet heute in nahezu allen modernen Betriebssystemen Verwendung.

Geschichte[Bearbeiten]

Das Konzept der virtuellen Speicherverwaltung entstand aus der Trennung in primäre Speichermedien, auf die der Prozessor direkt Zugriff hatte (meist Magnetkernspeicher), und sekundäre externe Speichermedien (meist Magnettrommelspeicher) in den Computern der 1950er Jahre und dem Wunsch, diese automatisch auf gleicher Ebene zu verwalten.[1]

Das Konzept des virtuellen Speichers wurde 1956 vom Physiker Fritz-Rudolf Güntsch an der Technischen Universität Berlin entwickelt.[2][3]

In Großbritannien wurde das Konzept beim Atlas-Computer Projekt von Tom Kilburn und Kollegen 1959 in einem Prototyp demonstriert. Der Computer kam 1962 auf den Markt. Das Konzept setzte sich im Verlauf der 1960er Jahre bei den meisten Betriebssystemen von Großrechnern durch (wie TSOS der Spectra 70 von RCA oder System/360 (Modell 67) und deren Nachfolger System/370 von IBM). Da zur effizienten Implementierung auch neue Hardware entwickelt werden musste, gab es in den 1960er Jahren noch Widerstände gegen eine vollständige Implementierung in Betriebssystemen. Systematische Tests, die ein Team um David Sayre bei IBM Ende der 1960er Jahre durchführte, fielen aber eindeutig zu Gunsten des Konzepts virtueller Speicher aus.[4][5]

Das Konzept fand in den 1970er Jahren Eingang auch bei Minirechnern, wie in das VMS Betriebssystem von DEC für dessen VAX-Rechner und in Unix (in der BSD Version). Beim PC setzte sich das Konzept mit der Weiterentwicklung der Prozessoren (bei Intel mit dem Protected Mode im Intel 80286 und dem Intel 80386 mit Memory Management Unit) auch in den Betriebssystemen durch, bei Microsoft ab Microsoft Windows 95.

Motivation[Bearbeiten]

Die ursprüngliche Motivation für eine Abstraktion der Speicheradressen mit virtuellen Adressen war die Vereinheitlichung der Benutzung und die mögliche Zusammenfassung verschiedener Speicherquellen. Dies wird von Güntsch in seiner Dissertation von 1957 so beschrieben:

„Der Programmierer braucht auf das Vorhandensein von Schnellspeichern keine Rücksicht zu nehmen (er braucht nicht einmal zu wissen, daß solche vorhanden sind). Denn es gibt nur eine Sorte von Adressen, mit denen programmiert werden kann, als wäre nur ein Speicher vorhanden.“

Eike Jessen: [3]

Die virtuelle Speicherverwaltung ermöglicht zudem die Implementierung von Speicherschutzmechanismen zur Separierung von

  • Programmen untereinander („horizontale Trennung“): Programme können (z. B. im Fehlerfall) nicht auf Speicher anderer Programme zugreifen;
  • Programmen gegen das Betriebssystem („vertikale Hierarchie“): Das Funktionieren des Betriebssystems darf nicht durch (fehlerhafte) Anwendungsprogramme gefährdet werden.

Eine weitere nützliche Eigenschaft des virtuellen Adressraums ist die Möglichkeit, jedem Prozess einen initial unfragmentierten, exklusiven Speicherraum zur Verfügung zu stellen. Ohne virtuellen Speicher entstünde oft Speicherfragmentierung des physischen Adressraums (prozess-übergreifend), welche durch virtuellen Speicher (pro Prozess, sowie meist deutlich größeren Adressraum als der phys. Speicher) weitgehend vermieden werden kann.

Funktionsweise[Bearbeiten]

Beziehung des Virtuellen Adressraums zum Physischen Adressraum für einen Prozess (32-Bit protected mode). Fragmentierter physischer Speicher wird dem Prozess im 2-GB-großen virtuellen Adressraum als kontinuierlich präsentiert.

Das Rechnersystem stellt jedem Prozess mit Adressen von 0 bis n-1 einen scheinbar zusammenhängenden lokalen Speicherbereich zur Verfügung, wobei n die Größe dieses Speicherbereichs ist. In Wirklichkeit besteht dieser Speicherbereich aus einzelnen Seiten definierter Größe („Pages“, veraltet auch „Kacheln“) innerhalb des virtuellen Adressraums des Prozesses. Diese virtuellen Pages werden wiederum auf physische Pages abgebildet, die irgendwo im physischen Speicher oder sogar in einer Auslagerungsdatei liegen. Beim Zugriff eines Prozesses auf eine Speicheradresse (eine virtuelle Adresse, andere Adressen kennt der Prozess gar nicht) übersetzt die Memory Management Unit (MMU) des Systems diese in die zugehörige aktuelle physische Adresse.

Die sogenannte Seitentabelle ist die Tabelle, welche der Transformation von virtuellen in physische Seitenrahmen dient. Anhand dieser Tabelle kann die MMU die virtuellen Adressen in reale Adressen übersetzen. Hier ist verzeichnet,

  • für welche virtuelle Page welche reale Page verwendet werden soll;
  • bei nicht verwendeter virtueller Page ist markiert, dass keine reale Page dafür verwendet wird;
  • bei ausgelagerter Page ist vermerkt, dass/wo im Pagefile (auch: „Swapfile“) der Inhalt gespeichert ist.

Die optimale Seitengröße (Größe einer Page) ist ein Kompromiss zwischen Häufigkeit von Seitenwechsel und Größe der Tabelle (übliche Größen: 4 KiB bei 32-Bit-virt.Adressraum, 4 MiB bei 64-Bit-virt.Adressraum).

Eine virtuelle Adresse beschreibt also einen Ort im Speicher eines Computersystems, dessen Betriebssystem eine virtuelle Speicherverwaltung zur Adressierung verwendet. Die Gesamtheit aller virtuellen Adressen wird auch als virtueller Adressraum bezeichnet.

Nur Betriebssysteme, die eine virtuelle Speicherverwaltung verwenden, können einen virtuellen Adressraum generieren und dadurch Speicherseiten, die physisch nicht zusammenhängend sind, für den Programmierer bzw. das Programm als logisch zusammenhängenden Speicherbereich abbilden.

Definition[Bearbeiten]

Gemeinsam sind den virtuellen Speicherverwaltungen heutzutage folgende Grundprinzipien:

  1. Alle von Prozessen verwendeten Adressen werden nur noch als virtuelle Adressen behandelt.
  2. Eine Memory Management Unit übersetzt die virtuellen Adressen in reale physische Adressen.
  3. Der durch die Gesamtheit aller möglichen virtuellen Adressen definierte virtuelle Adressraum, der den virtuellen Speicher bildet, wird genauso wie der tatsächlich vorhandene physische Arbeitsspeicher in gleich große Speicherabschnitte unterteilt. Die für diese Speicherabschnitte verwendeten deutschen Begriffe Kachel, Speicherseite oder Seitenrahmen sind synonym. Im Englischen wird dieser Speicherabschnitt pageframe genannt. Eine Page des virtuellen Adressraums wird auf eine Page (pageframe) des physischen Adressraums abgebildet.

Die verschiedenen virtuellen Speicherverwaltungen unterscheiden sich

  1. in der Größe des virtuellen Speicherraums,
  2. in der Speichergröße, die eine Page belegt,
  3. in der Art, wie die Memory Management Unit aus der virtuellen Adresse eine physische Adresse berechnet,
  4. in ihrer Seitenersetzungsstrategie, welche die Reaktion auf einen so genannten Seitenfehler, die Adressierung einer nicht im physischen Speicher vorhandenen virtuellen Adresse, festlegt und
  5. in der Behandlung von evtl. ausgelagerten Pages.

Technik[Bearbeiten]

Platzierungsstrategien von Betriebssystemen[Bearbeiten]

Fordert ein Programm Speicher vom Betriebssystem an, besitzt das Betriebssystem Freiheiten, wo im virtuellen Speicherraum des Prozesses es dem Programm den angeforderten Speicher zuweist. Mit geschickten Platzierungsstrategien kann eine kontinuierliche Fragmentierung des virtuellen Adressraums reduziert werden, was sowohl bei einer hohen Anzahl von Speicheranforderungen und -freigaben als auch bei stark gefülltem virtuellem Adressraum sehr relevant wird.

Strategien zur Wahl geeigneter Adressen sind:

FirstFit
erste ausreichende Lücke
BestFit
kleinste ausreichende Lücke. Nachteil: externe Fragmentierung
NextFit
nächster freier Speicher; startet an der Stelle, an der die letzten Daten eingefügt wurden (ringförmiges Durchsuchen)
WorstFit
größte ausreichende Lücke; Restlücke wird zusammengelegt

Paging[Bearbeiten]

Virtuelle Speichersegmente des Intel 80286.
Paging des Intel 80386, mit einer Page-Seitengröße von 4 KB.

Der Begriff Paging bezeichnet im engeren Sinn lediglich den Vorgang der Abbildung der virtuellen Adressen auf die physischen. Im weiteren (fehlerhaften) Sinne wird er synonym für Swapping benutzt.

Swapping[Bearbeiten]

Swapping ist die Auslagerung eines realen RAM-Speicherbereichs in einen anderen, sekundären Speicher, typischerweise in eine Auslagerungsdatei auf eine Festplatte durch das Betriebssystem.

Die Idee dahinter ist, dass bei typischen Computern die Festplatte deutlich größer ist als der verfügbare elektronische Speicher (RAM): Indem der Festplattenspeicher ebenfalls verwendet werden kann, um Speicheranfragen von Programmen zu bedienen, können Anfragen, die über das verfügbare RAM hinausgehen, dann über Swap-Speicher bis zur maximalen virtuellen Speichergröße pro Prozess bedient werden.

Nachteil ist, dass der auf Festplatte ausgelagerte Speicher deutlich langsamer zugreifbar ist als RAM - jedoch ermöglicht dieses Vorgehen das Funktionieren von Programmen mit hohem Speicherbedarf. Um den langsamen Zugriff zu mildern, versuchen Betriebssysteme mithilfe einer Speicherüberwachung, den RAM- und Swap-Speicher optimal auf die verschiedenen Prozesse zu verteilen. Speicherbereiche, auf die längere Zeit weder lesend noch schreibend zugegriffen wurde, werden bei Knappheit in den langsamen Swap-Speicher ausgelagert. Häufig benötigte Pages werden möglichst im RAM behalten.

Dies funktioniert konkret, indem ab einem gewissen Füllgrad des RAMs besondere Prozesse („Page stealer“) beginnen, länger nicht benutzte Seiten auszulagern, um zusätzlichen physischen Platz zu gewinnen, damit das System auf eine entsprechende Anforderung schnell reagieren kann. Dieser Vorgang ist asynchron zu den Anwendungen und belastet das System nicht sonderlich. Trotzdem ist die Zugriffsgeschwindigkeit der Festplatte relevant. Weiter unten sind die wichtigsten Seitenersetzungsstrategien aufgelistet. Üblicherweise wird eine Kombination aus mehreren Verfahren angewandt: Zuerst ungelesene, dann unveränderte, dann länger nicht veränderte Seiten auslagern. Soweit eine noch aktuelle Kopie einer Seite in der Auslagerungsdatei existiert, kann diese Seite ohne Weiteres zum Überschreiben freigegeben werden.

Ein Seitenfehler (engl.: page fault) tritt auf, wenn ein Programm auf eine Seite zugreift, die sich gerade nicht im Hauptspeicher befindet, sondern ausgelagert wurde. Dies löst eine Programmunterbrechung (engl.: trap) aus. Das Betriebssystem sorgt nun dafür, dass der angeforderte Speicherbereich wieder in den Hauptspeicher geladen wird, damit das Programm darauf zugreifen kann. Die Seite kann nun durchaus physisch an anderer Stelle liegen als ursprünglich, die Memory Management Unit berücksichtigt das entsprechend. Die virtuelle Adresse bleibt davon unverändert. Ein Seitenfehler verursacht also keinen Abbruch, sondern eine Aktion, die dem Prozess anschließend die normale Weiterverarbeitung erlaubt.

Das Zurückholen solcher Seiten ist ein Vorgang, der deutlich länger dauert, als nur auf eine Hauptspeicheradresse zuzugreifen. Deshalb verlangsamen Seitenfehler, wenn sie in hohem Umfang auftreten, die Programmgeschwindigkeit erheblich. So lange es dem Page stealer gelingt, Speicherplatz im Hauptspeicher zu Verfügung zu stellen, ist der Seitenfehler relativ schnell behoben. Problematisch wird es, wenn der nötige Platz im Hauptspeicher nicht vorhanden ist und der Trap warten muss, bis der Page stealer diesen Platz geschaffen hat. Die Situation kann eskalieren, sodass sich das System hauptsächlich mit der Behandlung von Seitenfehlern beschäftigt und gravierende Geschwindigkeitseinbußen verzeichnet. Page stealer und die Traps greifen beide auf die Auslagerungsdatei zu und lasten ab einem gewissen Punkt die betroffenen Festplatten komplett aus. Dieser Effekt wird als Seitenflattern bzw. thrashing bezeichnet.

Seitenersetzungsstrategien von Betriebssystemen[Bearbeiten]

Typische Strategien, um die Verwendung von RAM und langsameren sekundären Speichern für alle Prozesse zu optimieren, sind:

not recently used (NRU)
Teilt Seiten anhand des Use-Bits und Dirty-Bits aus der Seitentabelle in vier Klassen und entfernt zufällig eine aus der untersten, nicht-leeren Klasse.
first in, first out (FIFO)
Jede Seite bekommt Zeitstempel und wird nach FIFO verwaltet: „älteste raus, hinten rein, vorne raus“
Second-Chance-Algorithmus
Variante von FIFO, die verhindert, dass Seiten ausgelagert werden, die noch häufig benutzt werden.
least frequently used (LFU)
Jede Seite hat ein Feld, das Aufschluss über letzte Nutzung gibt; bei Seitenfehler müssen alle Seiten auf bislang nicht benutzte Zeit durchsucht werden
Working-Set-Algorithmus
Ersetzt gleich den ganzen Arbeitsbereich (working set) eines Prozesses. Er zählt zu den Prepaging-Strategien, da Seiten geladen werden, bevor sie benötigt werden.
Clock-Algorithmus
Funktionsweise analog zum Second-Chance-Algorithmus. Die Seiten werden in Form einer virtuellen Uhr mit Zeigern abgebildet. Im Verdrängungsfall wird der Uhrzeiger so lange um ein Element weitergeschaltet, bis eine Seite mit einem zurückgesetzten R-Bit gefunden wird. Seiten mit gesetztem R-Bit werden bei der Überquerung des Zeigers zurückgesetzt. Bei großer Anzahl an Hauptspeicherseiten ist dieses Verfahren zu langsam. Daher werden z. B. bei BSD-Unix zwei Zeiger mit konstantem Abstand zur Laufzeitverbesserung verwendet. Der vordere Zeiger setzt das R-Bit im Seitendeskriptor zurück, der hintere prüft das R-Bit und führt bei zurückgesetztem Bit die Verdrängung durch.
Belady-Theorem der optimalen Verdrängung
Hierbei werden die Seiten verdrängt, die in Zukunft am längsten nicht referenziert werden. Nicht umsetzbar, da das Programmverhalten nicht vorhergesagt werden kann.

Speicherfragmentierung[Bearbeiten]

Bei Systemen ohne virtuelle Speicherverwaltung tritt potentiell eine kontinuierliche Fragmentierung des realen Speicherraums über die Laufzeit ein. D.h. die erfolgreiche Funktion eines neu gestarteten Programms ist nicht deterministisch garantiert und hängt vom Fragmentierungszustand des physischen Speichers ab. Ohne virtuelle Speicherverwaltung kann es vorkommen, dass bei mehreren Programmläufen trotz gleichbleibender Speicheranforderung diese manchmal aufgrund von Fragmentierung nicht bedient werden können, obwohl insgesamt immer genügend Speicher frei ist. Beispielsweise bei MS-DOS, einem OS ohne virtuelles Speichermanagement, wurde versucht, dieses Problem mit komplizierten Speicheroptimierern (EMM386.EXE, QEMM etc.) zu minimieren. Bei diesen Speicheroptimierern wurde versucht, Gerätetreiber und TSR-Programm über eine iterativ ermittelte optimale Lade-Reihenfolge möglichst unfragmentiert in den physischen Speicher zu platzieren, um nachfolgenden Programmen möglichst große Speicherblöcke zur Verfügung stellen zu können. Dieses Vorgehen minimiert das Problem der physischen Speicherfragmentierung jedoch nur und löst es nicht, im Gegensatz zu virtuellem Speichermanagement, welches startenden Programmen einen immer gleichen, unfragmentierten Speicherraum bietet.

Jedoch können Programme auch mit virtuellen Speichermanagement über kontinuierliches explizites Speicher-Allokieren und -Deallokieren (malloc(), free()) oder ungeschickt festplatzierten Programmbibliotheken (DLLs)[6] ihren virtuellen Speicherraum selbst fragmentieren und damit ebenfalls in laufzeitabhängige "Out-of-Memory"- Situationen laufen. Dies trat in den 2000ern am Ende der 32-Bit PC-Ära als praktisches Problem auf (4-GB-Grenze); der virtuelle Adressraum war nicht mehr signifikant größer als der typische physische RAM-Ausbau, immer mehr Programme verwendeten entsprechend viel Arbeitsspeicher. Bei speicherintensiven Anwendungen wie z. B. wissenschaftlichen Simulationen (z. B. mit Matlab) oder aufwändigen 3D-Computerspiele (wie Gothic 3[7], Supreme Commander[8]) führte dies zu gehäuften Out-of-Memory-Problemen, trotz „genügend“ physischem und virtuellem (Gesamt-)Speicher.

Ist der virtuelle Speicherraum jedoch deutlich größer als die Anforderungen des Prozesses, so ist eine Fragmentierung des virtuellen Speicherraums kein praktisches Problem, da genügend alternative unfragmentierte Adressen und Adressbereich vorhanden sind. Mit der 64-Bit x86 AMD64-Architektur wurden die virtuellen Adressraumgrößen deutlich vergrößert (auch, um diesem Problem zu begegnen), und auf absehbare Zeit sollte eine Fragmentierung des virtuellen Speicherraums keine Rolle für PC-Programme spielen.

Zuordnung von virtuellen Pages zu realen Pageframes[Bearbeiten]

In Mehrprozessorsystemen ist der real vorhandene Arbeitsspeicher häufig nach dem NUMA-Prinzip angebunden. Das Betriebssystem sollte dann günstigerweise die virtuellen Pages eines Threads zu solchen realen Pageframes zuordnen, die an dem Prozessor angebunden sind, der den Thread rechnet.

Beispiele[Bearbeiten]

  • AMD64-Architektur: Von den 64 Bit der virtuellen Speicheradressen sind in der ersten CPU-Generation 48 Bit physisch für die Virtuelle Speicherverwaltung implementiert (d.h. die ersten 16 Bit der virtuellen Adresse müssen 00hex sein, da nur 48 Bit möglich sind - der virt. Adressraum ist also auf 2^48 Byte beschränkt). Hierfür wird eine vierstufige Seitentabelle verwendet. Die 48 Bit teilen sich auf in je 9 Bit für die vier Seitentabellen plus 12 Bit Offset.
  • IA-32-Architektur: Eine virtuelle Adresse ist 32 Bit lang. Es wird eine zweistufige Seitentabelle verwendet. Die 32 Bit teilen sich auf in je 10 Bit für die zwei Seitentabellen plus 12 Bit Offset.
  • IA-32-Architektur mit PAE: Eine virtuelle Adresse ist 32 Bit lang. Es wird eine dreistufige asymmetrische Seitentabelle verwendet. Die 32 Bit teilen sich auf in 2 Bit für die erste Seitentabelle und je 9 Bit für die zwei weiteren Seitentabellen plus 12 Bit Offset.

Bei der IA-32-Architektur ist der Arbeitsspeicher in Speicherseiten aufgeteilt, deren mögliche Größen und Anfangsadressen durch die Hardware vorgegeben sind. Wird auf eine Adresse zugegriffen, der zurzeit keine physische Speicherseite zugeordnet ist, so muss das Betriebssystem die Memory Management Unit anweisen, an dieser Stelle eine bestimmte freie Speicherseite einzublenden. Steht keine freie Speicherseite mehr zur Verfügung, so muss eine andere Speicherseite frei gemacht werden, wobei der Inhalt vom Betriebssystem z. B. auf die Festplatte ausgelagert wird. Diesen Vorgang bezeichnet man als Paging. Die Größe des virtuellen Adressraums kann aus der Definition der virtuellen Adresse berechnet werden. So ist beispielsweise in einer IA-32-Architektur eine virtuelle Adresse 32 Bit breit, zweimal je 10 Bit für eine zweistufige Seitentabelle und 12 Bit für den Offset. Somit lassen sich 210 x 210 x 212 Byte adressieren. Das sind 232 Byte, also 4 GiB.

Einzelnachweise[Bearbeiten]

  1. Peter J. Denning Before memory was virtual, 1996, pdf
  2. E. Jessen: Origin of the Virtual Memory Concept. IEEE Annals of the History of Computing. Band 26. 4/2004, S. 71 ff.
  3. a b Eike Jessen: Die Entwicklung des virtuellen Speichers. In: Springer Berlin / Heidelberg (Hrsg.): Informatik-Spektrum. 19, Nr. 4, 1996, S. 216-219. doi:10.1007/s002870050034.
  4. History of Virtual Memory, George Mason University
  5. Peter J. Denning Performance modelling- experimental computer science at its best, 1981, pdf
  6. Brett Shoelson: Is your memory fragmented? What can you do about it? (englisch) mathworks.com. 8. Mai 2009. Abgerufen am 14. Juli 2012.
  7. VIII. Community Patch v1.6 (englisch) madvulture.de. Abgerufen am 5. September 2012: „- Fixed some memory fragmentation for performance improvements.
  8. Ryan Smith: A Messy Transition: Practical Problems With 32bit Addressing In Windows - A Case Study: Supreme Commander (englisch) anandtech.com. S. 4. 12. Juli 2007. Abgerufen am 5. September 2012: „Finally at 22 minutes in to the game, the game crashes as the virtual size has reached the 2.6GB barrier we have reconfigured this system for. Perhaps the most troubling thing at this point is that Supreme Commander is not aware that it ran out of user space in its virtual address pool, as we are kicked out of the game with a generic error message.

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]