Virtueller Speicher

Das Konzept des virtuellen Speichers ist heute ein Konzept der Rechnerarchitektur, das in praktisch jedem modernen, leistungsfähigen General-Purpose-Computer (Höchstleistungsrechner, PCs, Tablets, Smartphones) anzutreffen ist. Die Erfindung geht auf den deutschen Physiker Fritz Rudolf Güntsch zurück, der diese bahnbrechende Idee bereits 1956 als Teil seiner 1957 abgeschlossenen Dissertation [1] in einem internen Technischen Bericht der TU Berlin beschrieben hat. Obwohl der logische Entwurf des von ihm entworfenen Computers nie realisiert wurde, werden in seiner Konzeption eines virtuellen Speichers alle wesentlichen Aspekte – wenn auch in einer aus heutiger Sicht rudimentären Form – vollständig und schlüssig abgehandelt.

Schnell aber klein

Computer sind in aller Regel mit mindestens zwei Typen von Speichern ausgestattet: dem Hauptspeicher (auch Arbeitsspeicher genannt) und einem Massenspeicher (heute oft eine Festplatte).

Im Hauptspeicher müssen alle Programme mit den zugehörigen Daten geladen sein, die zur Ausführung bestimmt sind. Der Hauptspeicher zeichnet sich durch direkte, schnelle Lese- und Schreibzugriffe des Prozessors zu jeder Speicherzelle (üblicherweise ein Byte) aus, ist aber oft zu klein, um alle Programme und Daten komplett aufzunehmen. Der Massenspeicher hat eine wesentlich größere Speicherkapazität, aber um Größenordnungen längere Zugriffszeiten, da auf seine Inhalte nur blockweise über Ein-Ausgabe-Operationen zugegriffen werden kann. Vor Erfindung des virtuellen Speichers gehörte es deshalb zur Standardaufgabe einer Programmentwicklung, den begrenzten zur Verfügung stehenden Hauptspeicher zu verwalten. Dazu zählten folgende Aufgaben:

- Planung von Programm- und Datensektionen, die gemeinsam im Hauptspeicher zur Ausführung durch den Prozessor anwesend sein müssen,

- Steuerung der sektionsweisen Programmausführung,- Verdrängung von Programm- und Datensektionen aus dem Hauptspeicher auf den Massenspeicher vor einem Sektionswechsel,

- Nachladen von Programm- und Datensektionen vom Massenspeicher in den Hauptspeicher vor einem Sektionswechsel.

Die in jedem Anwendungsprogramm durchzuführende Speicherverwaltung war kostenaufwändig, fehleranfällig und verringerte die Portabilität (d.h. die Übertragbarkeit von Programmen auf einen neuen Computer) bei technologischen Fortschritten in der Speichertechnologie. Dieses Problem verschwand durch die Erfindung des virtuellen Speichers.

Ein virtueller Speicher ist ein imaginärer, also real nicht vorhandener Speicherraum mit sehr großer Kapazität, der einem einzelnen Anwendungsprogramm mit all seinen Daten bei dessen Ausführung zugeordnet wird. Die Größe dieses Speicherraums wird durch die Bitlänge einer virtuellen Adresse definiert, die der Prozessor für Lese- und Schreibzugriffe zu Speicherzellen generiert. Sie wird in einer gegebenen CPU-Architektur so gewählt, dass aus Sicht der Anwendungsprogramme Speicherengpässe praktisch ausgeschlossen sind.

Üblich in Computern mit virtuellem Speicherkonzept sind heute 32 oder 64 Bit lange Adressen, durch die Adressräume mit einer Kapazität von 232 bzw. 264 Speicherzellen gebildet werden können. Virtuelle Adressen werden bei der Ausführung von Maschinenbefehlen aus einer Verknüpfung der Inhalte von Basisregistern, Indexregistern und kurzen Distanzadressen dynamisch berechnet, bevor der eigentliche Zugriff zu der korrespondierenden Speicherzelle im virtuellen Speicher geschieht. Durch das Konzept des virtuellen Speichers wird eine Entkopplung der logischen Speicherstruktur eines Programms von der aktuell verfügbaren Speichertechnologie mit ihren inhärenten Besonderheiten und Beschränkungen erreicht.

Fiktiver Speicher

Da der virtuelle Speicher eine Fiktion ist, muss er auf die beiden existierenden Speichertypen (Hauptspeicher und Massenspeicher) transparent abgebildet werden. Im Kern besteht die Aufgabe darin, lange virtuelle Adressen des virtuellen Speicherraums in kürzere Adressen des gewöhnlich viel kleineren physischen Hauptspeichers automatisch zu transformieren. Damit dieser Abbildungsprozess effizient, d.h. zu vertretbaren Ausführungs- und Speicherkosten erledigt werden kann, ist eine blockweise Abbildung unumgänglich. Dazu wird der virtuelle Speicher in Blöcke gleicher Länge (den Seiten, engl. pages) gegliedert, die auf Speicherblöcke im physischen Hauptspeicher (den Kacheln, engl. frames) abgebildet werden. Eine virtuelle Adresse <s,d> besteht deshalb aus einer Seitenadresse s und einer Relativadresse d (displacement) für die Adressierung von Speicherzellen innerhalb einer Seite. Bei der Transformation von einer virtuellen Adresse wird nun lediglich die Seitenadresse p durch eine Kacheladresse k ersetzt. Das displacement d wird in der resultierenden realen Hauptspeicheradresse <k,d> unverändert aus der virtuellen Adresse übernommen.

Wie aber kann die Realität des knappen Arbeitsspeichers und die Fiktion eines virtuellen Speichers in einer Realisierungsidee zusammengeführt werden? Kern ist eine neue Computerkomponente, die Memory Management Unit (MMU), die transparent für den Prozessor die Abbildung von virtuellen Adressen auf reale Hauptspeicheradressen vornimmt und dabei auch auf den Massenspeicher zugreift, um durch Verdrängung von Seiten aus dem Hauptspeicher Platz für dringend benötigte Seiten zu schaffen, die dann in den Hauptspeicher geladen werden. Die Aufgaben einer MMU können so zusammengefasst werden:

- Ersetzung der virtuellen Adresse <s,d> durch die reale Adresse <k,d>, sofern die Abbildung existiert

- Besorgen einer Kachel sofern der Seite s keine Kachel zugeordnet ist und Herstellung der Abbildung s -> k. Die Besorgung einer Kachel bedingt u.U. die Verdrängung einer Seite aus dem Hauptspeicher und das Nachladen der benötigten Seite vom Massenspeicher in die frei gewordene Kachel. Dieser Vorgang wird als Seitenersetzung bezeichnet.

Die MMU kümmert sich

Die Transformation einer virtuellen Adresse in eine reale Hauptspeicheradresse geschieht über sog. Seitentabellen per Hardware. Jedem in der Ausführung begriffenen Programm ist eine eigene Seitentabelle zugeordnet. Alle Seitentabellen sind in einem reservierten und geschützten Teil des Hauptspeichers untergebracht. Über spezielle Register, die Seitentabellendeskriptoren, greift die MMU auf die gerade aktuelle Seitentabelle zu. Jeder Tabellenplatz der Seitentabelle, der durch die Seitenadresse s angesteuert wird, enthält einen Seitendeskriptor, in dem (im Falle einer vorhandenen Abbildung s->k) die Kacheladresse k und einige Status- und Schutzbits für diese Seite gespeichert sind. Die Status-Bits (Präsenzbit, Referenzbit, Dirty-Bit) werden durch die Hardware gesetzt und unterstützen die Implementierung von effizienten Seitenersetzungsalgorithmen. Fehlt bei einem Zugriff zum virtuellen Speicher durch den Prozessor die Zuordnung zu einer Kachel in der Seitentabelle, dann wird per Hardware ein sog. Seitenfehler ausgelöst. Er hat den augenblicklichen Stopp des Programms und die Aktivierung der Komponente Seitenersetzung zur Folge, die vollständig als Teil des Betriebssystems in Software realisiert ist. Ihre Aufgabe ist es, durch Inspektion der Statusbits eine geeignete Kachel im Hauptspeicher zu finden, die die benötigte Seite aufnehmen kann. Dazu muss ggf. die in dieser Kachel eingelagerte Seite auf den Massenspeicher verdrängt werden. Bei der Suche nach einer geeigneten Seite waren die theoretischen Untersuchungen zu dieser Fragestellung Ender der 60er Jahre sehr hilfreich. Dabei spielt das Konzept der Lokalität eine große Rolle; die optimale Verdrängungstrategie, die die in der Zukunft am längsten nicht referenzierte Seite verdrängt, ist zwar nicht implementierbar, hat aber die Entwicklung von Algorithmen wie Least-Recently-Used oder Least-Frequently-Used befördert, die in ihrer Wirkung der optimalen Verdrängung sehr nahe kommen. Nachdem die fehlende Seite im Zuge der Seitenersetzung erfolgreich in eine Kachel des Hauptspeichers geladen und die Abbildung s->k im Seitendeskriptor der Seitentabelle eingetragen wurde, kann das angehaltene Programm fortgesetzt werden.

Der Entwurf eines virtuellen Speichers von Güntsch ist den technologischen Beschränkungen der Speichertechnologie seiner Zeit – aber auch dem damaligen Stand der Softwaretechnologie - geschuldet. Betriebssysteme waren noch nicht erfunden, der Ein-Programm-Betrieb war Stand der Technik. Der Hauptspeicher in Güntsch’s Entwurf bestand aus drei Kacheln zu je 200 Speicherworten: eine Programmkachel, eine Datenkachel und eine Kachel, die zwei Sektoren auf dem Massenspeicher fest zugeordnet war. Der Massenspeicher bestand aus einer Batterie von 10 Trommelspeichern mit je 100 Sektoren zu je 100 Speicherworten. Das ergab einen virtuellen Speicher von 100.000 Speicherworten, der 1:1 auf den Trommelspeicher abgebildet wurde. Eine Seitenersetzung über Seitentabellen erübrigte sich, der Hauptspeicher war ohnehin zu klein dafür. Die MMU konnte mit diesen Einschränkungen vollständig in Hardware realisiert werden. Status- und Schutzbits waren bei dem geplanten Ein-Programm-Betrieb überflüssig.

Fritz Rudolf Güntsch war mit seiner bahnbrechenden Erfindung seiner Zeit um einige Jahre voraus. Erst 1962 wurde das Konzept des virtuellen Speichers erneut erfunden [2] und im Atlas-Computer des englischen Herstellers Ferranti erstmalig realisiert. Eike Jessen hat durch seine Publikation in Annals of the History of Computing [3] dafür gesorgt, dass die Pionierleistung von Fritz Rudolf Güntsch nicht in Vergessenheit gerät. Weitere Details und theoretische Grundlagen zum virtuellen Speicher findet man in [4].

Späte Entdeckung

Im Titel seiner Dissertation ist bei Günsch nicht die Rede von einem virtuellen Speicher, sondern von einem „automatischen Schnellspeicherbetrieb“, wobei mit dem Schnellspeicher der heutige Arbeitsspeicher gemeint ist (in Abgrenzung zu Massenspeichern wie z.B. damaligen Trommelspeichern). Möglicherweise war dies der Grund, dass die große Bedeutung der Erfindung von Güntsch in der Fachwelt nicht rechtzeitig erkannt bzw. zur Kenntnis genommen wurde.

Tatsächlich hat sich das Konzept der Virtualisierung zu einem der mächtigsten Konzepte in der Informatik entwickelt. Man versteht darunter einen Abstraktionsprozess, in dem von technologischen Besonderheiten und Beschränkungen einer gegebenen Hardwaretechnologie abstrahiert wird. Bei konsequenter Anwendung des Prinzips der Virtualisierung resultiert eine Entkopplung von allgemein gültiger logischer Struktur und physischer Struktur eines Computersystems. Software, die für virtuelle Computersysteme entwickelt wird, behält ihre Gültigkeit, obwohl sich die Hardwaretechnologie ständig verändert. Bei Einführung einer neuen Hardwaretechnologie muss lediglich die Abbildung der logischen Struktur auf die tatsächlich vorhandene physische Struktur angepasst werden.

Die Erfindung des virtuellen Speichers durch Fritz Rudolf Güntsch war die erste bekannte Anwendung des Prinzips der Virtualisierung in der Informatik, die heute in verschiedenen Ausprägungen eine Verallgemeinerung, z.B. in Form von virtuellen Maschinen, erfahren hat. Güntsch hat mit seiner Erfindung nicht nur die moderne Architektur von Computern wesentlich beeinflusst, sondern mit dem Konzept der Virtualisierung auch die Methodik in der Informatik durch ein mächtiges Konzept bereichert.

Literatur:
[1] F.R. Güntsch: Logischer Entwurf eines digitalen Rechengerätes mit mehreren asynchron laufenden Trommeln und automatischem Schnellspeicherbetrieb, Dissertation D83, TU Berlin 1957
[2] T. Kilburn, D.B.G. Edwards, M.J. Lanigan, F.H. Sumner: One Level Storage Systems, IRE Trans. Electronic Computers 11 (1962), pp. 223 – 245
[3] E. Jessen: Origin of the Virtual Memory Concept, Annals of the History of Computing, Oct. – Dec. (2004), pp. 71 - 72
[4] Peter J. Denning: Virtual Memory, ACM Computing Surveys Band 2 (1970), pp. 153-189