216 E. Jessen: Die Entwicklung des virtuellen Speichers

Informatik Spektrum 19:216–219 (1996) © Springer-Verlag 1996

Unter einem virtuellen Speicher verstehen wir einen Speicher,derrealisiert wird durch einen schnellen,aber kleinen Speicher,der diegewünschte Zugriffszeit bietet,und einen großen,aber langsamenSpeicher,der die gewünschte Kapazität bietet.Zwischen beidenSpeichern werden automatisch, für den Zugreifer unsichtbar,Datenso ausgetauscht,daß möglichst viele Zugriffe aus dem schnellenSpeicher befriedigt werden [4, 12].Seit dem Ende der siebziger Jah-re, in verteilten Systemen, ist der kleine Speicher nicht so sehr durchseine technologisch bedingte Zugriffszeit charakterisiert, sonderndadurch,daß er am Ort des Zugreifers vorhanden ist,während diegroße Gesamtkapazität über das System verteilt angeordnet ist unddaher nur mit wesentlich schlechteren Zugriffszeiten erreichbar ist;dieses liegt oft nicht nur an der räumlichen Entfernung,sondernauch an der Realisierung der Zugriffsmechanismen durch Bot-schaften zwischen den verteilten Knoten des Systems.

Für die Geschichte der Informatik ist bedeutsam,daßam virtuellen Speicher erstmals das Konzept der Virtualisierungeiner Funktionseinheit entwickelt wurde.Erst später wurden vir-tuelle Prozessoren,virtuelle Maschinen,virtuelle Geräte und virtu-elle Kanäle geboren. Immer handelt es sich um die Realisierung ei-ner Funktionseinheit gewünschter funktionaler Eigenschaften ausunvollkommenen Bausteinen, typisch unter Rückgriff auf pro-grammierte Funktionen.Die Idee der Virtualisierung setzt sich indie Software fort und führt dort z.B.zur Datenabstraktion.Es han-delt sich um ein Kernkonzept der Informatik.

a0000005222Basiserfindung

Die Ideengeschichte des virtuellen Speichers beginnt im Jahr 1956,die Technologie der Rechner war noch durch Röhrenschaltungenbestimmt.Die Hauptspeicher wurden bereits in Kernspeichertech-nologie gebaut und hatten Kapazitäten bis 32 K Wörter.Als Sekun-därspeicher dienten vor allem Trommelspeicher,die sich sehr frühzu großer technischer Reife entwickelt hatten.Zugriffszeiten in derGrößenordnung von 10 bis 20 ms wurden damals schon erreicht.Großrechner arbeiteten nach dem Parallelprinzip und benutztenKernspeicher als Hauptspeicher und Trommelspeicher als Sekun-därspeicher,eventuell um Bandspeicher erweitert.

Es wurden rudimentäre Betriebssysteme eingesetzt,natürlich ohne Mehrprogrammbetrieb.Die Programmierschnitt-stelle war durch den Assembler bestimmt.Die wesentlichen Zei-

chen der künftigen Entwicklung waren aber bereits sichtbar: DieEinführung des Unterbrechungsmechanismus auf der RemingtonRand 1103 und die Programmiersprachen FORTRAN und ALGOL.

An der Technischen Universität Berlin schuf F.R.Güntsch 1956 als Mitarbeiter von W.Haack das Konzept einesRechners,der auf 10 asynchron laufendenTrommeln eine Speicher-kapazität von 105 Wörtern,gegliedert in 1000 Blöcke zu 100 Wör-tern,anbieten konnte.Der Prozessor dieser Maschine greift nichtdirekt auf die Trommelspeicher zu,sondern auf einen Schnellspei-cher mit einer Kapazität von insgesamt 600 Wörtern (6 Blöcken,Abb. 1).Ein wichtiges Motiv für diese Struktur war sicher die Syn-chronisation des Prozessors mit 10 (unter sich) asynchron rotie-renden Trommeln,vom heutigen Standpunkt ist aber viel bedeu-tender,daß hier erstmals durch das Zusammenspiel des Schnell-speichers mit den Trommelspeichern ein virtueller Speicher reali-siert wird. Jeder Zugriff des Prozessors in den Adreßraum von100 000 Wörtern hat als Ziel entweder eines der Register bzw.dieEin-/Ausgabe,oder er führt auf den Schnellspeicher.2 Blöcke desAdreßraums werden hierbei fest auf 2 Blöcke des Schnellspeichersabgebildet,während die Abbildung der übrigen Blöcke desAdreßraums dem Zugriffsprozeß folgt.Hierfür stehen 2 Doppel-blöcke im Schnellspeicher zur Verfügung.Sooft ein Befehl nicht imSchnellspeicher angetroffen wird,wird er mit dem ihn umgeben-den Doppelblock von der Trommel in den ersten Doppelblock desSchnellspeichers geladen.Entsprechend führt ein Zugriff auf einnicht im Schnellspeicher vorhandenes Datenwort zur Ersetzungdes Inhaltes der beiden nächsten Schnellspeicherblöcke (Abb. 1).Auf diese Art gelingt es,den Befehlzugriffsprozeß und den Daten-zugriffsprozeß voneinander zu trennen,und man kann ausnutzen,

Historische Notizen

Die Entwicklung des virtuellen Speichers

Eike Jessen,Institut für Informatik der TU München, D-80290 München,e-mail: jessen@informatik.tu-muenchen.de

Eike Jessen

Abb. 1 Güntschs Konzept von 1956: Schnellspeicher von 600Wörtern in 6 Blöcken,automatischer Austausch mit Hin-tergrundspeicher, realisiert als 10 asynchrone Trommeln.

E. Jessen: Die Entwicklung des virtuellen Speichers 217

daß jeder für sich eine bessere Lokalität als der Gesamtprozeß hat.In dem Doppelblock des Adreßraums,der fest dem 3.Doppelblockdes Schnellspeichers zugeordnet ist,kann der Programmierer häu-fig gebrauchte Befehlsfolgen und Daten unterbringen.Um zu ver-hindern,daß selten zugegriffene Befehlsfolgen oder Daten zu einerschädlichen Ersetzung im Schnellspeicher führen, ist die Maschinemit einigen Befehlen ausgestattet,die den Schnellspeicher umge-hen und den Prozessor direkt auf die Trommel zugreifen lassen.

Damit ist der virtuelle Speicher geboren,und Güntschschreibt zu Recht in seiner Dissertation von 1957:„Der Program-mierer braucht auf das Vorhandensein von Schnellspeichern keineRücksicht zu nehmen (er braucht nicht einmal zu wissen,daß sol-che vorhanden sind).Denn es gibt nur eine Sorte von Adressen,mit denen programmiert werden kann,als wäre nur ein Speichervorhanden“[7].

a0000005222Dimensionen der weiteren Entwicklung

Die Entwicklung der Rechnerstrukturen läßt sich im wesentlichenin vier Dimensionen verfolgen.Diese sind: die Programmierpara-digmen,die Technologie,die Nutzung der Nebenläufigkeit und dieNutzung der Verteilung.Für die weitere Entwicklung der Idee desvirtuellen Speichers sind vor allem die letzten drei bedeutsam ge-wesen.Abb.2 zeigt, in welchen zeitlichen Stufen die Basisidee diegenannten Dimensionen durchdrang.Für die Speichertechnikbrachte die technologische Weiterentwicklung vor allem auch dieVerfeinerung der Hierarchie, so daß die technologische Dimensionhier als die Dimension der Hierarchiebildung erscheint.

a0000005222Nebenläufigkeit

Für die weitere Entwicklung ist zunächst die Dimension der Ne-benläufigkeit am wichtigsten.Die erste Maschine,die das Prinzipdes virtuellen Speichers betriebstüchtig präsentiert, ist die Ferran-ti-Atlas [8].Die Ferranti-Atlas war eine der ersten Maschinen,dieaufgrund eines detaillierten Konzeptes der Betriebsführung ent-worfen wurde.Das Betriebskonzept der Atlas verquickt das Prinzipdes virtuellen Speichers,der Programmunterbrechung und desMehrprogrammbetriebs.Damit wird es erstmals möglich,bei Er-setzung eines Inhaltes im Schnellspeicher (jetzt Hauptspeicher)die Transportzeit durch Übergang auf einen rechenbereiten Pro-zeß zu nutzen.Dazu muß der Schnellspeicher wesentlich größersein als im Konzept von 1956.Damit stellt sich zugleich das Pro-blem einer Ersetzungsstrategie,die festlegt,welcher Inhalt beiNachladen erforderlichenfalls aufgegeben werden muß (Atlas-Al-gorithmus).Ähnlich wie in der Basiserfindung von 1956 erscheintauch hier ein Schnellspeicherbereich,der (jetzt von allen Prozes-sen) unter einem festen Teiladreßraum greifbar ist.Er dient jetztdazu,Maschinenunterprogramme aufzunehmen,auf die die Ma-schine die Interpretation von Komplexbefehlen zurückführt (Ein-führung der Instruction Traps).Die Gliederung des Adreßraums inBlöcke (die seit der Atlas „Seiten“ – pages – heißen),erlaubtschließlich noch,den Adreßraum gestreut auf den Hauptspeicherabzubilden,womit sich die Speicherverwaltung erleichert.

Ein anderer Ansatz für die Realisierung eines virtuel-len Speichers entstand ab 1963 in der Burroughs B 5000 bzw.B 5500[2].Hier wird der Schnellspeicher nicht mit Einheiten fester Größenachgeladen,sondern mit sogenannten Segmenten,also Daten-und Programmstrukturen uniformer Zugriffseigenschaft,die ver-schiedene Formate haben können.

Es liegt nahe,beide Konzepte miteinander zu verbin-den und mit Hilfe der Seitenadressierung Ausschnitte aus denmöglicherweise großen Segmenten in einfacher Weise im Haupt-speicher anzuordnen.Dieser Schritt ist durch zwei Maschinen desJahres 1967 gekennzeichnet,die zugleich die Geburt der universel-len Teilnehmersysteme kennzeichnen: die General Electric GE 645und IBM/360 Mod.67 [5,6].Spätestens mit diesen Maschinen warsichtbar,daß die Idee des virtuellen Speichers auch die Bereitstel-lung von privaten Adreßräumen aller koexistenten Prozesse erlau-ben würde,Virtualisierung also Vervielfältigung erlaubt.Die Funk-tionen in den Rechnern bereitzustellen,war einfacher,als daraufaufbauende Betriebssysteme zu schreiben.So kam es dazu,daß dieEinführung von privaten Adreßräumen der Prozesse erst Ende der60er Jahre, ja sogar in vielen Betriebssystemfamilien erst Mitte der70er Jahre an die Benutzer weitergegeben wurde.

Die wichtigsten Schritte in der Ausweitung des Prin-zips des virtuellen Speichers auf neue Schichten der Technologieund Hierarchie waren die Einführung des Cache Memory mit derIBM/360 Mod 85 [3] (Abb.3) und später der Übergang zu verteil-ten Dateisystemen und die ersten Realisierungen von virtuell glo-balen Speichern in verteilten Systemen,etwa Mitte der 80er Jahre.Mit den beiden letzten Schritten erfolgt zugleich ein Schritt indem Freiheitsgrad „Verteilung“.Das erste Cache Memory ähneltstark der Erfindung von 1956.Wie dort handelt es sich um einenreinen Hardwaremechanismus.Das Cache Memory hat eine Ka-pazität von 16 Blöcken von 1 KB.Wie 1956 oder 1962,wird für jedenBlock die Blocknummer in Registern,zu einem „tag memory“

Abb. 2 Dimensionen der Entwicklung des virtuellen Speichers.

218 E. Jessen: Die Entwicklung des virtuellen Speichers

vereinigt, festgehalten.Aber anders wird bei Laden eines Blocksaus dem Hauptspeicher nicht das ganze Volumen von 1 KB,son-dern nur der aktuell benötigte Teilblock von 64 B transportiert.Das liegt daran,daß sukzessives Heranschaffen der Teilblöcke ausdem Hauptspeicher keinen wesentlichen zusätzlichen Zeitauf-wand erforderte.

Spätere Cache Memories haben das Prinzip des virtuel-len Hauptspeichers,daß eine Seite einen beliebigen freien Platz imHauptspeicher einnehmen kann,verlassen. Im Zusammenhangmit Cache Memories wurde dieses Prinzip „assoziativ“ genannt; esgestaltet die Ortsermittlung und die Ersetzungsstrategie komplex.Rigoros kann man nur einen zulässigen Platz vorsehen (direkt ab-bildendes Cache Memory),was einen gezielten Zugriff erlaubt undeine Ersetzungsstrategie erübrigt,oder als Kompromiß nur eineTeilmenge der Orte im Cache Memory (Gruppen-assoziatives Ca-che Memory).Außerdem verließ man die großformatigen Seitenals Abbildungseinheit und ging dazu über,die Transporteinheit„Block“ von 8 bis 32 B Größe auch als Einheit der Abbildung zu be-nutzen.Seit 1990 erweiterte man die Hierarchie nochmals undsetzte zwei Cache Memories zwischen Prozessor und Hauptspei-cher (1.und 2.Ebene).

a0000005222Verteilung

Ab 1972/73 werden Cache Memories auch in Mehrprozessoranla-gen eingesetzt.Damit tritt ein zunächst nebensächlich aussehen-des Problem auf,dessen Bewältigung für die weitere Entwicklungaußerordentlich kennzeichnend ist; die bis heute gefundenen Lö-sungen sind nicht zufriedenstellend,und das Problem ist noch im-mer Gegenstand intensiver Forschung.

Schon indem die Ein-/Ausgabe auf Inhalte des Haupt-speichers zugreift,von denen Kopien aktuell im Cache Memorydes Prozessors gehalten werden, ist es möglich,daß unter einerAdresse in zwei Zellen voneinander abweichende Werte zugegrif-fen werden,wenn auch nur einer der beiden Zugreifer (Prozessor,Ein-/Ausgabe) schreibt.Das Problem verschärft sich mit der Ein-führung weiterer Prozessoren mit eigenen Ausschnitten in eigenenCache Memories.Besondere Hilfsmechanismen werden erforder-lich,um die Kohärenz der Zugriffe (jeder Lesezugriff findet denWert vor,der zuletzt in eine Zelle dieser Adresse geschrieben wur-de) im erforderlichen Umfang sicherzustellen [10].

Da der Hauptspeicher zugleich mit dem Hintergrund-speicher einen klassischen virtuellen Speicher bildet,besteht nochdie Möglichkeit, zur Adressierung der Cache Memories Prozeß-adressen oder Maschinenadressen des Hauptspeichers einzuset-zen,womit sich weitere Freiheitsgrade und Probleme ergeben.Ty-pische Lösungen für das Problem der Kohärenz sehen etwa folgen-dermaßen aus:• „store through“: jeder Schreiboperation in einem Speicher folgt

„schritthaltend“ ein Schreiben in allen anderen Speichern un-ter derselben Adresse.Diese Technik ist scheinbar unkomplex,zwingt aber bei Folgen von Schreiboperationen den Prozessorherunter auf die Arbeitsgeschwindigkeit des Hauptspeichers.Bei auch nur etwa gleichzeitigen Schreiboperationen mehrererProzessoren auf dieselbe Adresse kann die endlich schnelleAusbreitung der sekundären Schreiboperation dazu führen,daß voneinander abweichende Werte in Zellen derselben

Adresse auftreten.Es ist dann besser,die sekundären Schreib-operationen nur als Löschoperationen auszuführen,und damitzu erzwingen,daß erforderlichenfalls Inhalte aus demHauptspeicher nachgeladen werden,der von allen Zugreifernbeschrieben wird und die Zugriffe eindeutig serialisiert.Beiguter Entkoppelung der Zugriffsprozesse der einzelnen Prozes-soren kann diese Technik auch zu kleinerer Belastung des Ge-samtsystems führen,als das reine „store through“-Prinzip.

• Der gesamte Adreßraum wird in Partitionen eingeteilt,die imfolgenden als Seiten bezeichnet werden,mit denen sie gelegent-lich übereinstimmen.Zu jedem Zeitpunkt ist eine Seite be-schreibbar,dann hat sie genau einen Schreibeigentümer,derdieses Recht hat,oder sie steht für beliebig viele Lesezugreiferoffen.Ein Schreibwunsch führt dazu,daß irgendwann die Seitedem bisherigen Schreibeigentümer oder den Lesezugreifernentzogen wird.Ein gültiges Exemplar der Seite wird bei demeinzigen Schreibeigentümer oder aber bei allen Lesezugreiferngeführt.Hierzu müssen Zugreiferverzeichnisse geführt werden,was zentral oder verteilt geschehen kann.Der Schreibeigentü-mer schreibt schritthaltend in den Hauptspeicher oder ver-schiebt dieses bis zur Rückübertragung von Inhalten aus demCache-Memory in den Hauptspeicher („Copy-Back-Technik“).

Die beschriebenen Verfahren streben alle die strikte Kohärenz an,d.h.nie sei es möglich,daß zwei Zugreifer unter einer Maschinen-adresse verschiedene Werte lesen können.Verfahren der striktenKohärenz sind wahrscheinlich zu einschränkend für Systeme mitvielen Prozessoren und hohen Leistungsanforderungen.

Das Kohärenzproblem ist in klassischen Mehrprozes-sorsystemen entstanden,die im allgemeinen nicht der Klasse derverteilten Systeme zugerechnet werden.Tatsächlich handelt es sichaber hierbei um ein Problem der Verteilung,da in der Vielprozes-sorstruktur mit privaten Cache-Memories die Unsicherheit überden Gesamtzustand der Eintragungen in den Cache-Memoriesimmanent ist.Ohne Eingriff in den Betrieb ist ein konsistenter Zu-stand des Speichers nicht zu ermitteln.

Diese Problematik tritt natürlich umso mehr in den Sy-stemen auf,die üblicherweise als verteilt angesehen werden,den

Abb. 3 Prinzip des ersten Cache Memory (IBM/360 Modell 85,1969.

Multirechnersystemen.Etwa ab 1980 beginnt die Entwicklung vonverteilten Dateisystemen [11].Ein Kennzeichen dieser Systeme ist,daß Kopien von Dateien zum Zugreifer transportiert werden,umerträgliche Zugriffszeiten zu bieten.Damit wird der zweite, jünge-re Aspekt des virtuellen Speichers sichtbar: der kleine Speichergünstiger Zugriffszeit muß nicht technologisch schneller sein alsdie anderen Speicher im System,sondern er ist am Ort des Zugrei-fers vorhanden.Wenn auch nur ein Zugreifer unter mehreren aufeine Datei schreibt,entsteht wieder das schon bekannte Kohärenz-problem.Eine typische Lösung ist,wie schon beschrieben,auf ei-ner Datei zu einem Zeitpunkt nur entweder einen Schreiber odereine beliebige Anzahl von Lesern zuzulassen.

Etwa ab Mitte der 80er Jahre erscheinen erste Konzep-te,dasselbe Organisationsschema auch auf die Hauptspeicher ineinem Vielrechnersystem anzuwenden (Abb.4), [1,9].Für jedenRechner in dem verteilten System wird in dessen privatem Spei-cher eine Seitenmenge als Ausschnitt aus dem verteilten Speicherdes Gesamtsystems organisiert.Diese besteht im allgemeinen ausKopien von Inhalten,die auch in anderen Speichern vorhandensind.Das Nichtvorhandensein einer Seite führt wie im klassischenvirtuellen Speicher zur Blockierung des verfolgten Prozesses,derwieder aufgenommen werden kann,wenn über das Netz diebenötigte Seite herangeschafft ist.

Natürlich stellt sich hiermit wiederum das Problem derKohärenz.Man kann auf strikter Kohärenz bestehen,z.B. indemman die Technik des „einen Schreibers oder n Lesern“ benutzt.Wahrscheinlich werden sich aber Lösungen durchsetzen,die nurschwache Kohärenz bieten,d.h.es ist möglich,daß zwei Zugreiferunter derselben Adresse verschiedene Werte vorfinden können. In-kohärente Zugriffe werden allerdings so eingeschränkt,daß dieBerechnungsergebnisse trotzdem akzeptabel sind.Eine Möglich-keit besteht in der Durchsetzung sogenannter serieller Konsistenz:obwohl Zugreifer abweichende Werte lesen können,bleiben dieZugriffsfolgen aller Zugreifer für sich betrachtet korrekt,und dieGesamtheit der Berechnungsergebnisse aller Zugreifer fällt nichtanders aus als unter einem erlaubten Ablauf bei strikter Kohärenz;dieser muß aber nicht mit dem wirklichen Ablauf übereinstim-men.Es ergeben sich damit also dieselben Verhältnisse wie bei se-rialisierbaren Transaktionssystemen in Datenbanken.Eine nochweitergehende Möglichkeit besteht darin,die Kohärenz jeweils nurzwischen Partnerprozessen sicherzustellen,die einen Synchroni-sationspunkt durchlaufen.Das bedeutet etwa,daß ein Prozeß,dereine wait-Operation überschreitet,das Ergebnis aller Schreibope-

rationen zum Zeitpunkt der korrespondierenden signal-Operati-on seines Partnerprozesses erhält.Außerhalb von expliziten Syn-chronisationspunkten wird keine Garantie für Kohärenz über-nommen.Korrekte Berechnungen setzen damit korrekte Synchro-nisation voraus.Wünschenswert wäre es,den Programmierer vondiesen Operationen zu befreien.

In dieser Ausprägung des virtuellen Speichers wird al-so die Funktionalität eines gemeinsamen Speichers in einem ver-teilten System erzeugt,der Speicher ist virtuell gemeinsam.

Die gerade beschriebenen Lösungswege,die auf demVerschicken von Kopien beruhen,sind übrigens nicht die einzigen.Man kann auch das Zugriffsobjekt am entfernten Ort belassen,ver-meidet dann die Kohärenzprobleme,muß aber sehr effizient mit je-dem nichtlokalen Zugriff auf eine andere Befehlsfolge umschaltenund – wegen der Häufigkeit nichtlokaler Zugriffe – viele ausführ-bare Befehlsfolgen bereithalten,um den Prozessordurchsatz auf-rechtzuerhalten,(viel„fädige“ – multithreaded – Architekturen). Inbeiden Fällen wird eine tragfähige Basis für konventionelle Pro-grammierparadigmen in einem verteilten System gebaut.DieseEntwicklung ist noch in vollem Fluß.Es sieht allerdings bereitsheute so aus,als ob sie für die Nutzung verteilter Systeme von ähn-licher Bedeutung sein wird,wie das Konzept von 1956 für die klas-sischen Rechner in den 60er und 70er Jahren geworden ist.

a0000005222Literatur

1. Abramson, D.A, Keedy, I. L.: Implementing a large virtual memoryin a distributed computing system, Proc. of the 18th Hawaii Inter-national Conf. on System Sciences 1985

2. Barton, R. S.: A new approach to the functional design of a digitalcomputer, Proc.Western Joint Computer Conf. 1961, S. 393–396

3. Conti, C. J., Gibson, D. H., Pitkowsky, S. H.: Structural Aspects ofthe System 360/85: General Organisation, IBM Systems Journal, 7(1968), S.2–14

4. Denning, P. I.: Virtual memory, Computing Surveys, 2 (1970), S.153–189

5. Gibson, C. T.: Time Sharing in the IBM System/360 Model 67,AFIPS Proc. Spring Joint Computer Conf. 1966, S. 61–78

6. Glaser, E. L., Couleur, I. F., Oliver G.A.: System design of a compu-ter for time sharing applications AFIPS Proc. Fall Joint ComputerConf. 1965, S. 197–202

7. Güntsch, F. R.: Logischer Entwurf eines digitalen Rechengerätesmit mehreren asynchron laufenden Trommeln und automati-schem Schnellspeicherbetrieb, Dissertation, Technische Univer-sität Berlin, D 83, Berlin 1957

8. Kilburn, T., Edwards, D. B. G., Lanigan, M. J., Sumner, F. H.: One-le-vel storage system, IRE Trans. Electronic Computers, 11 (1962), S.223–245

9. Li, K.: Shared virtual memory on loosely coulpled multiproces-sors, PhD-These,Yale University, 1986

10. Scheurich, C. Dubois, M.: Correct memory operations of cache-based multiprocessors, 14 th International Symp. on ComputerArchitecture Conf. Proc. 1987

11. Tanenbaum,A. S., van Renesse, R.: Distributed Operating Systems,ACM Computing Surveys, 17 (1985), S. 419–470

12. Wilkes, M.V.: Slave memories and dynamic storage allocation,IEEE Trans. ElectronicComputers, 14 (1965), S. 270–271

E. Jessen: Die Entwicklung des virtuellen Speichers 219

Abb. 4 Virtuell gemeinsamer Speicher in einem Mehrrech-nersystem.