Paging

Dieser Artikel beschreibt das Paging als Methode der Speicherverwaltung in Rechnersystemen. Paging im Mobilfunk wird im Artikel Mobile Terminated Call erläutert.

Als Paging (im engl. abgeleitet von page (dt. Speicherseite)) bezeichnet man eine Methode der Hauptspeicherverwaltung durch Betriebssysteme. Dabei wird häufig aus Effizienzgründen die sogenannte Memory Management Unit des Prozessors eingesetzt, sofern der Prozessor eine solche bereitstellt.

Sehr häufig wird der Begriff Paging im deutschen Sprachraum allerdings synonym mit der gesamten virtuellen Speicherverwaltung gebraucht. Dieser Sprachgebrauch ist jedoch unpräzise, da das Paging nur einen - wenn auch zentralen - Aspekt der virtuellen Speicherverwaltung ausmacht.

Zu unterscheiden ist das Paging jedoch deutlich vom Swapping, da letzteres nicht nur auf Speicherseiten, sondern auf ganze Segmente des Speichers ausgeführt wird und somit Teil der Segmentierung ist.

Zweck des Pagings

Das wesentliche Problem, das durch Paging gelöst wird, ist das Problem der externen Fragmentierung. Dieses Problem ist das folgende: Jedem Prozess wird vom Betriebssystem ein Adressraum zugeordnet. Würde es sich hierbei um einen zusammenhängenden Hauptspeicherbereich handeln, so entstünden im Lauf der Zeit zwischen den Adressräumen der Prozesse Lücken, da neue Prozesse zumeist nicht dieselbe Speichermenge benötigen wie beendete Prozesse und diese somit nicht eins zu eins ersetzen können. Eine regelmäßige Neuordnung des Speichers (Kompaktifizierung genannt) wäre zwar möglich, aber sehr aufwändig. In erster Näherung kann man das Problem lindern, indem man die Prozesse segmentiert, d.h. nicht einen einzigen zusammenhängenden Adressraum, sondern mehrere kleinere Segmente an die Prozesse vergibt. Dies würde die externe Fragmentierung jedoch nicht vollständig beseitigen. Das Paging hingegen beseitigt die externe Fragmentierung gänzlich.

Funktionsweise

Beim Paging werden logischer Speicher und physikalischer Speicher unterschieden. Der logische Speicher beschreibt die Organisation des Hauptspeichers aus Programmsicht. Der physikalische Speicher ist durch den verfügbaren Hauptspeicher sowie ggf. zusätzlichen ausgelagerten Speicher (z.B. in Form einer Auslagerungsdatei) gegeben. Man unterteilt den logischen Speicher in gleich große Stücke, die man als Seiten (pages) bezeichnet. Auch der physikalische Speicher ist derart unterteilt - hier nennt man die einzelnen Stücke Seitenrahmen (frames). Eine Seite passt genau in einen Seitenrahmen. Um Seiten und Seitenrahmen einander zuordnen zu können, wird eine Seitentabelle verwendet. Dementsprechend existiert für jeden Prozess eine derartige Seitentabelle. Nun wird klar, warum hier keine externe Fragmentierung im Hauptspeicher mehr auftreten kann: Zwar ist der logische Speicher weiterhin zusammenhängend, im physischen Speicher können die benachbarten Seiten jedoch in weit von einander entfernt liegenden Seitenrahmen abgelegt werden. Die Reihenfolge der Seitenrahmen ist damit beliebig, und somit macht es auch keinen Sinn mehr, von Lücken und damit von externer Fragmentierung zu sprechen.

Da die Zugriffszeit auf einzelne physische Speicherzellen immer identisch ist, müssen keine Effizienzeinbußen in Kauf genommen werden. Da bei diesem Verfahren der Zugriff auf die Seitentabelle sehr häufig ist, verwenden moderne Prozessoren zu diesem Zweck in der Regel spezielle Hardware-Register, die sogenannte Memory Management Unit. (Dieser Artikel liefert Ihnen zusätzliche detaillierte Informationen über die Verwendung der Seitentabelle.)

Adressberechnung beim Paging

In der Terminologie der obigen Grafik entspricht eine logische Speicheradresse der virtuellen Adresse. Der physische Speicher heißt hier reale Adresse. Man entnimmt der Grafik, dass sich die physische Speicheradresse sehr einfach aus zwei Teilen berechnet: Der erste Teil wird der virtuellen Adresse entnommen, der zweite Teil der Seitentabelle. Dabei handelt es sich um zwei Binärzahlen. Werden diese konkateniert, so ergibt sich eine neue Binärzahl, die genau die physische Speicheradresse ist. Derartige Berechnungen werden von der Memory Management Unit ausgeführt.

Demand Paging

Wie oben schon erwähnt, wird der Paging-Mechanismus auch zur virtuellen Speicherverwaltung ausgenutzt. Erfolgt nun ein Zugriff auf eine Speicherseite, die nicht im Hauptspeicher, sondern im Auslagerungsspeicher abliegt, so wird zunächst ein Seitenfehler (engl. page fault) ausgelöst. Dieser führt zu einem Software-Interrupt und schließlich zum Laden der Seite in den Hauptspeicher. Diese Technik bezeichnet man als Demand Paging.

Thrashing und Working Set

Diese Technik hat jedoch ihre Grenzen. Wenn in einem Rechnersystem zu viele Seitenfehler auftreten, dann ist es überwiegend mit dem Nachladen und Auslagern von Seiten beschäftigt. Der Prozessor verharrt die meiste Zeit im Wartezustand, die verfügbare Rechenleistung sinkt dramatisch. Da der Rechner in diesem Betriebszustand gewissermaßen nur leeres Stroh drischt, bezeichnet man ihn auch als Thrashing (Dreschen).

Um Thrashing zu vermeiden, darf der Arbeitsspeicher im Verhältnis zum Auslagerungsspeicher nicht zu klein sein. Zu jedem gegebenen Zeitpunkt sollte mindestens einer der Prozesse, die das System zu verarbeiten hat, vom Prozessor bearbeitet werden können, das heißt: Seine Daten oder Programmbefehle, die aktuell bearbeitet werden, befinden sich im Arbeitsspeicher. In diesem Betriebszustand wartet der Prozessor nicht auf das Nachladen von Seiten, sondern arbeitet an einem Prozess, während parallel für andere Prozesse Seiten nachgeladen werden.

Entscheidend sind dabei folgende Größen:

t: Die Zeit, die der Prozessor braucht, um auf eine Speicherstelle zuzugreifen
T: Die Zeit, die benötigt wird, um eine Seite nachzuladen
s: Der Anteil an Seiten, der sich im Arbeitsspeicher befindet, im Verhältnis zur Gesamtzahl aller für die Programmausführung benötigten Seiten (0 < s ≤ 1)
p(s): Die Wahrscheinlichkeit eines Seitenfehlers, abhängig von s

Damit Thrashing vermieden wird, muss p(s) ≤ t/T sein. Der minimale Anteil w an Seiten, der sich im Speicher befinden muss, wird bestimmt durch die Gleichung

p(w) = t/T.

Er wird als Working Set bezeichnet.

Wären die Zugriffe auf den Speicher gleich verteilt, so wäre p(s) = 1 - s. Erfreulicherweise treten die Speicherzugriffe jedoch lokal gehäuft auf: In den meisten Fällen folgt ein Programmschritt dem nächsten. Auch die Daten werden meist in Reihen bearbeitet, beispielsweise wenn Rechenoperationen auf ganze Tabellen angewendet werden. Deshalb ist die Wahrscheinlichkeit sehr hoch, dass der nächste Programmschritt und das nächste benötigte Datenelement sich auf derselben Seite befinden, wie der gerade verarbeitete Schritt und das gerade verarbeitete Element.

Auf der anderen Seite ist das Verhältnis T/t typischerweise sehr groß: RAM-Speicher ist mehr als 100 mal so schnell wie Plattenspeicher.

Experimentelle Messungen und Berechnungen, die bereits in den 1960er Jahren durchgeführt wurden, ergeben unter diesen Bedingungen für w einen Wert von nicht wesentlich weniger als 0,5. Das bedeutet, dass der Auslagerungsspeicher kaum größer als der Arbeitsspeicher sein darf.

Kriterien und Strategien für die Seitenersetzung

Verschiedene Kriterien werden zur Bewertung herangezogen:

Die Zugehörigkeit der Speicherseite zum aktiven Prozess
Der letzte Zugriff auf die Speicherseite
Die Unversehrtheit der Speicherseite, weil eine unveränderte Seite nicht auf den Hintergrundspeicher zurückgeschrieben werden muss, sondern direkt durch die neue angeforderte Seite überschrieben werden kann.

Folgende Strategien werden verwendet:

First In - First Out
Least recently used: Die am längsten nicht genutzte Seite wird ausgelagert.
Not recently Used: Seiten, die innerhalb eines Zeitintervalls nicht benutzt und nicht modifziert wurden, werden bevorzugt ausgelagert. Danach Seiten, die entweder nicht benutzt oder modifiziert wurden und als letzte Gruppe erst Speicherseiten, die modifiziert und benutzt wurden.
Not frequently Used: Seitenzugriffe werden mit dem zeitlichen Abstand zur aktuellen Anfrage korreliert und so ein Wert ermittelt.

Sinkende Bedeutung des Verfahrens

Paging kostet auf jeden Fall Zeit: Selbst bei einem angemessen großen Working Set kommt es auf Grund von statistischen Unregelmäßigkeiten hin und wieder zu Wartezeiten für den Prozessor. Außerdem verursachen die Seitenverwaltung selbst, die Interrupts und die Umschaltvorgänge kleine Zeitverluste, selbst wenn eine Memory Management Unit vorhanden ist.

Andererseits ist seit den 1990er Jahren Arbeitsspeicher sehr billig geworden. Daher versucht man heutzutage, das Auslagern gänzlich zu vermeiden, indem man den Arbeitsspeicher entsprechend großzügig bemisst.

Siehe auch: Memory Management Unit, Seitenfehler, Segmentierung (Speicherverwaltung), Speicherseite, Swapping, Virtueller Adressraum