Als Paging (englisch page – Speicherseite) oder deutsch Kachelverwaltung 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.
Gelegentlich wird der Begriff Paging 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 einzelne Speicherseiten, sondern praktisch vollständige Prozesse auslagert.
Zweck des Pagings
Das wesentliche Problem, das durch Paging gelöst wird, ist die externe Fragmentierung. Darunter versteht man Folgendes: 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 somit diese 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 lösen, 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.
Des Weiteren benutzen die meisten heutigen Betriebssysteme virtuelle Adressräume, so dass jedem Prozess ein eigener, gegen andere Prozesse und das Betriebssystem abgeschotteter logischer Adressraum zur Verfügung steht. Diese sogenannte virtuelle Speicherverwaltung benutzt Paging, um nur die vom Programm benötigten Teile eines virtuellen Adressraums (angenähert mit Vielfachen der verwendeten Seitengröße) mit physikalischem Speicher zu hinterlegen.
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 ( engl. „pages“ ) bezeichnet. Auch der physikalische Speicher ist derart unterteilt - hier nennt man die einzelnen Stücke Seitenrahmen oder auch Kacheln ( engl. „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 ist es nicht mehr sinnvoll, 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.
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 Seitentabelle entnommen, der zweite Teil der virtuellen Adresse. 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 des Pagings 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.
In der Praxis wird z. B. unter UNIX-Betriebssystemen für die meisten Anwendungsfälle eine Größe des Auslagerungsspeichers vom zwei- bis dreifachen des Arbeitsspeichers empfohlen (abhängig davon, ob das jeweilige System den Auslagerungsspeicher zusätzlich zum Arbeitsspeicher oder den Arbeitsspeicher als echte Teilmenge des Auslagerungsspeichers verwaltet).
Kriterien und Strategien für die Seitenersetzung
Verschiedene Kriterien werden zur Bewertung herangezogen:
Zugehörigkeit der Speicherseite zum aktiven Prozess
Es hat sich gezeigt, dass Prozess-Scheduling-Algorithmen, die ohne Trennung der Speicherseiten nach Prozessen effizienter arbeiten, besonders wenn sich im laufenden Betrieb die Größe des Hauptspeichers ändert.
Letzter Zugriff auf die Speicherseite
R-Bit oder Reference-Bit zeigt an, ob auf die Speicherseite zugegriffen worden ist. Je nach Implementierung werden entweder in einem bestimmten Zeitintervall alle R-Bits auf 0 gesetzt oder man speichert neben R-Bits auch Zeitstempel ab.
Unversehrtheit der Speicherseite
M-Bit oder Modification-Bit zeigt an, dass der Speicherinhalt des Hauptspeichers sich gegenüber dem des Inhaltes auf der Festplatte geändert hat. Wird die Speicherseite ausgelagert, muss die Änderung zurück auf die Festplatte geschrieben werden. Ansonsten entfällt das Zurückschreiben und man spart sich einen teuren I/O-Zugriff.
Folgende Strategien werden verwendet:
First In - First Out (FIFO): Ist zwar einfach zu implementieren wird in der Praxis aber nicht verwendet.
Second Chance (SC): SC ist eine Weiterentwicklung von FIFO. Dabei wird geprüft ob eine Seite referenziert wurde, ist dies der Fall wird ihr R-Bit gelöscht und wieder an den Anfang der Schlange gesetzt.
Uhr/Clock: Ist eine schnellere Implementiertung von SC, da sie nicht auf Vertauschen beruht, sondern einen Zeiger benutzt, der auf die Seite zeigt welche am längsten im Speicher ist.
Least recently used (LRU): Die am längsten nicht genutzte Seite wird ausgelagert.
Not recently Used (NRU): 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 (NFU): Seitenzugriffe werden mit dem zeitlichen Abstand zur aktuellen Anfrage korreliert und so ein Wert ermittelt. NFU ist eine Variante von LRU in Software.
Sinkende Bedeutung des Verfahrens
Paging kostet auf jeden Fall Zeit: Selbst bei einem angemessen großen Working Set kommt es aufgrund 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, auch wenn eine Memory Management Unit vorhanden ist.
Andererseits ist seit den 1990er Jahren Arbeitsspeicher sehr billig geworden. Daher versucht man heutzutage, das Auslagern weitestgehend zu vermeiden, indem man den Arbeitsspeicher entsprechend großzügig bemisst.
Praktisch ungeeignet ist Paging für Echtzeit-Systeme, da es die Antwortzeiten nichtdeterministisch macht.
