Bild

Ich mach das mal kurz: Ich möchte euch Speicherverwaltung erklären. “Was soll denn das?”, mögt ihr euch vielleicht fragen. Nun es geht um die Frage, wie euer Computer es schafft, ständig mehrere Programme gleichzeitig auszuführen und sich dabei in der Verwaltung dieser Programme nicht verheddert.

Ich versuche mal eine Analogie zu finden, die man sich ein bisschen besser vorstellen kann, die aber wahrscheinlich an einigen Punkten anecken und scheitern wird. Aber besser als nichts. Nun denn…

Stellt euch vor ihr besitzt eine Lagerhalle mit sehr vielen, sehr großen Regalen. Ständig kommen Kunden an und wollen eine Kiste einlagern, eine andere wieder mitnehmen und für die nächste Woche gleich noch Platz reservieren. Sagen wir jede Sekunde tausend Kunden, dann wird die Dimension des Problems klarer.

Segmentierung

Erste naive Idee: Wenn ein Kunde kommt, sagt er wie viel Platz er benötigt und erhält diesen Platz in einem der Regale. Wir tragen in eine Tabelle ein, dass seine Kisten dort gelagert werden, damit wir sie später schneller wiederfinden und nicht komplett alle Regale absuchen müssen. Wichtig: Um uns weniger in der Tabelle merken zu müssen, schreiben wir uns für einen Kunden nur auf, wo sein Lagerplatz beginnt und wie viel er gelagert hat.

Mit dieser Strategie werdet ihr jedoch schnell Probleme bekommen: Wenn einige Kunden ihre Plätze wieder freiräumen und das Lager nach hinten hin langsam voll wird, dann entstehen viele unterschiedlich große Lücken. Wenn nun ein neuer Kunde sehr viel neuen Platz benötigt, könnt ihr ihm keinen so großen Platz am Stück bieten und müsst ihn ablehnen - oder euch riesig viel Arbeit machen und alle bisher eingelagerten Kisten so verschieben, dass die Freiräume nach hinten wandern (und natürlich die Tabelle anpassen). Das kann dauern und die tausend Kunden, die pro Sekunde ankommen werden ganz schön lange warten müssen, bis ihr mit diesem einen Kunden fertig seid.

In eurem Computer passiert Ähnliches: Prozesse (Kunden) benötigen um ausgeführt werden zu können Speicherplatz (Lagerplatz in der Lagerhalle). Diesen Platz fordern sie vom Betriebssystem (dem Lagerverwalter) an und geben diesen später wieder frei (Kunden holen Kisten wieder ab). Die naive Verwaltung, die ich gerade erklärt habe nennt man in der Informatik “Segmentierung”. Weil zusammenhängende Segmente in den Speicher eingelagert werden. Das Problem, dass nach einiger Zeit zwischen den Segmenten freier Speicher entsteht, der nicht gut genutzt werden kann, da diese freien Stücke sehr klein und unzusammenhängend sind, nennt man externe Fragmentierung.

Worüber wir in diesem Beispiel noch nicht gesprochen haben, ist die Frage danach, welche Lücke in der Lagerhalle wir für neue Kisten auswählen, wenn es mehrere Lücken gibt, die groß genug sind (also die Lücke größer ist, als der Platz der benötigt wird). Hier gibt es verschiedene Strategien:

  • First Fit: Wir gehen von vorne nach hinten durch unser Lager und wählen den ersten passenden Freiraum, den wir finden können für die neuen Kisten aus.
  • Best Fit: Wir wählen aus allen freien Lücken so aus, dass nach dem Einlagern der neuen Kisten der verbleibende Freiraum der Lücke möglichst minimal wird.
  • Worst Fit: Wir wählen aus allen freien Lücken so aus, dass nach dem Einlagern der neuen Kisten der verbleibende Freiraum der Lücke möglichst groß wird.

Welches die beste Vorgehensweise ist kommt auf unsere Kriterien an: Aufwand für das Finden neuer Einlagerungsplätze minimieren? Oder externe Fragmentierung minimieren?

Ein weiterer Nachteil dieser Strategie: Segmentierung beharrt darauf, dass ein Kunde seine Kisten nur “am Stück” lagern darf. Wir hatten uns ja in die Tabelle nur den Anfang der Lagerplatzes und dessen Länge gemerkt. Das heißt aber, dass eine Erweiterung des Lagerplatzes problematisch wird, wenn der Platz hinter dem bisherigen Lagerplatz des Kunden schon belegt ist. Aufwändige Umräumarbeiten werden dann nötig.

Virtualität

Machen wir das Spiel noch ein wenig komplizierter (so ist das nunmal): Die Lagerkunden haben ihr eigenes Kistenverwaltungssystem, mit dem sie ihre Kisten beschriften und einlagern lassen. Schließlich wollen sie nicht alleine von unserem Lagersystem abhängig sein und auch bei anderen Anbietern ihre Kisten lagern können und wiederfinden.

Jedes Mal, wenn ein Kunde also eine Kisten bei uns abholen möchte, muss vorher seine eigene Kistenadresse übersetzt werden in die tatsächliche Adresse in unserem Lagersystem. Konkret: Der Kunde sagt zu uns, er möchte gerne in Kiste 5 etwas nachschauen. Allerdings steht seine Kiste 5 nicht am fünften Platz in unserer Halle. Wir müssen daher zuerst nachschauen (in unserer Tabelle) wo sich der Lagerplatz des Kunden befindet und dann dort die fünfte Kiste auswählen.

In der Informatik nennt man die eigene Kistenadresse des Kunden (des Prozesses) eine virtuelle Adresse. Der tatsächliche Standort in unserer Lagerhalle (nachdem wir in der Tabelle nachgeschaut haben) nennt sich physische Adresse (im Speicher). Die virtuelle Speicherverwaltung ist ein sehr wichtiges Konzept, da sie es ermöglicht, dass Programme geschrieben werden können ohne dass man dafür wissen muss, wie genau der Speicher des Computers aussieht, auf dem das Programm laufen soll - eben genau so, wie es den Lagerhallenkunde nicht interessiert wie wir die Kisten verwalten. Er möchte nur seine Kiste 5 haben.

Bessere Ansätze

Wir haben gesehen, dass Segmentierung nicht unbedingt die beste Lösung ist und einige Probleme mit sich bringt. Aber es gibt Hoffnung und Alternativen :)

Wir entscheiden uns in den Lagerregalen in Zukunft Container fester Größe einzusetzen, in die unsere Kunden ihre Kisten einlagern können. Außerdem müssen die Container eines Kunden nicht mehr hintereinander stehen, sondern können über die ganze Lagerhalle verstreut stehen.

Seht ihr schon den Vorteil: Wir haben das Problem der externen Fragmentierung gelöst. Alle Lücken haben die gleiche Größe und was neu eingelagert wird hat immer genau die Größe eines Containers. Außerdem müssen wir uns keine Gedanken mehr darüber machen, welche freie Lücke wir auswählen. Es ist schlichtweg egal. Auch Forderungen nach zusätzlichem Lagerplatz können problemlos abgewickelt werden (muss ja nicht mehr am Stück liegen).

Dieses Prinzip nennt sich in der Informatik Paging. Wir teilen den Speicher dafür in feste Größen ein, die Frames (Containerlagerplätze). Wenn nun ein Prozess eine neue Page (Container) anfordert, wir diese in das Frame gelegt.

Leider ist die Welt nicht immer ganz so rosig wie sie scheint. Denn wie euch vielleicht aufgefallen ist, kommen wir nun nicht mehr mit der einfachen Lagertabelle klar, die wir bei der Segmentierung verwendet haben. Wir legen daher für jeden(!) Kunden (Prozess) eine Tabelle an, in der eingetragen ist, welche Containernummer seiner Kistennummer entspricht. In der Informatik nennt man diese Tabelle Page Table.

Ein weiteres (kleineres) Problem ist die interne Fragmentierung: Wenn Kunden einen ganzen Container anfordern müssen, obwohl sie nur eine ganz kleine Kiste lagern wollen, dann wird Platz verschwendet. Da aber Prozesse in der Regel in Relation zur Page-Größe sehr viel mehr Speicher anfordern, fällt die letzte nicht ganz ausgenutzte Page nicht so sehr ins Gewicht.

Wie sieht das also im Computer tatsächlich aus:

Bild

Ab hier fängt das Lagerhallenmodell an zu wackeln, daher werde ich das nun weglassen.

Der RAM den wir sehen ist der Speicher, auf den Prozesse zugreifen wollen, die auf der CPU laufen. Dazwischen befindet sich ein CACHE, der Daten die oft benötigt werden vorhält und deutlich schnelleren Zugriff ermöglicht als der RAM.

Wir hatten gesagt, dass es für jeden Prozess eine Page Table gibt, in der von virtuellen Adressen in physische Adressen übersetzt wird. Darum kümmert sich die MMU - Memory Management Unit (ist auch oft direkt in die CPU integriert). Die MMU greift dabei auch auf den TLB zurück, den Translation Lockaside Buffer. Es ist relativ aufwändig für jeden Speicherzugriff zuerst einmal in der Page Table nachzuschauen (um die physische Adresse herauszufinden), da Zugriffen auf den RAM sehr langsam sind. Dafür nutzt man den TLB. Er speichert ein paar dieser Adresszuordnungen zwischen.

Man könnte nun hier noch auf die Speicherhierarchie an sich eingehen und wie Caches intern organisiert sind, allerdings würde das den Rahmen hier sprengen. Vielleicht wird das ja mal ein separater Artikel.

Wer jetzt sofort noch etwas mehr erfahren möchte, der sei an die allwissende Halde verwiesen:

Ich freue mich über Fragen!

Artikelfoto: cc-by-nc-sa 2.0 von Zanthia Grafik zu Memory Management: cc-by-nc-sa 2.0 von Stefan Trauth 

Weitere Artikel