Als Paging (vgl. engl. page „Speicherseite“) bezeichnet man die Methode der Speicherverwaltung per Seitenadressierung durch Betriebssysteme. Nur selten wird die deutsche Bezeichnung Kachelverwaltung verwendet.Verwendung Begriff "Kachelverwaltung": , abgerufen am 1. September 2014 Uni Ulm, Netzwerktreiber-Projekt, abgerufen am 1. September 2014 RabbitMQ 2.0.0 unterstützt aktuellen AMQP-Standard – Artikel bei Heise Developer, vom 26. August 2010
Das Paging ermöglicht eine virtuelle Speicherverwaltung. Der virtuelle Speicher bezeichnet den vom tatsächlich vorhandenen physischen Arbeitsspeicher unabhängigen Adressraum, der einem Prozess vom Betriebssystem zur Verfügung gestellt wird. Da meist mehr virtuelle Adressen existieren, als im physischen Arbeitsspeicher umsetzbar sind, werden einige Speicherbereiche vorübergehend auf die Festplatte ausgelagert.
Beim Paging wird der virtuelle Adressraum in gleich große Stücke unterteilt, die man als Seiten (engl. pages) bezeichnet. Auch der physische Adressraum ist derart unterteilt. Die entsprechenden Einheiten im physischen Speicher nennt man Seitenrahmen oder auch Kacheln (engl. page frames). Die Seiten werden in der sogenannten Seitentabelle (engl. page table) verwaltet, die Informationen darüber enthält, wo für eine (virtuelle) Seite der entsprechende (reale) Seitenrahmen im Arbeitsspeicher tatsächlich zu finden ist, sowie meistens Zusatzinformationen zum Beispiel zu Gültigkeit, Schreibrechten oder ob (sowie evtl. wohin) die Seite ausgelagert wurde.
Wenn ein Prozess eine virtuelle Adresse anspricht, die keiner physischen Arbeitsspeicher-Adresse zugeordnet ist, wird ein Systemaufruf ausgelöst. Dieser Aufruf wird Seitenfehler (engl. page fault) genannt. Als unmittelbare Folge des Seitenfehlers kommt es zu einer synchronen Prozessunterbrechung (Trap). Das Betriebssystem prüft dann, ob ein zugehöriger Seitenrahmen existiert und gerade ausgelagert ist – dann wählt es einen wenig benutzten Seitenrahmen aus, schreibt dessen Inhalt zurück auf die Festplatte, lädt den benötigten Seitenrahmen in den frei gewordenen Arbeitsspeicherbereich, ändert die Zuordnungstabelle und setzt den unterbrochenen Prozess mit dem fehlgeschlagenen Befehl fort.
Existiert zu der angeforderten virtuellen Adresse kein ausgelagerter Seitenrahmen, so kann das Betriebssystem entweder einen (ggf. zuvor „freigeschaufelten“) leeren realen Seitenrahmen zuordnen und den Prozess fortsetzen oder den Prozess abbrechen unter dem Hinweis „Seitenfehler“. Aktuell verbreitete Betriebssysteme brechen einen Prozess in diesem Fall ab.
Funktionsweise
Virtueller Adressraum mini|hochkant|Virtueller und physischer Speicher, wobei ein Teil des virtuellen Adressraums auf die Festplatte ausgelagert wird
Der physische Adressraum ist durch den tatsächlich verfügbaren Arbeitsspeicher (Hauptspeicher) gegeben. Eine physische Adresse ist eine reale Adresse einer Speicherzelle im Arbeitsspeicher. Meistens verwenden Prozesse jedoch nicht mehr physische, sondern nur noch virtuelle (logische) Adressen. Das Prinzip der virtuellen Speicherverwaltung ermöglicht es, dass alle aktiven Prozesse mehr Speicherplatz belegen dürfen, als tatsächlich im physischen Adressraum zur Verfügung steht. Die virtuellen Adressen bilden den virtuellen Adressraum. Diese gehen nun nicht direkt an den Speicherbus, sondern an die Memory Management Unit (MMU, dt. Speicherverwaltungseinheit), welche die virtuellen Adressen auf die physischen Adressen abbildet.Tanenbaum: Moderne Betriebssysteme. 2009, S. 243.
Aus der Sicht des Programmierers, der mit virtuellen Adressen arbeitet, erscheint der Adressraum (fast) unbegrenzt. Er braucht keine Rücksicht darauf zu nehmen, ob diese Adressen im real vorhandenen physischen Arbeitsspeicher wirklich existieren. Das Betriebssystem löst diese Aufgabe mit der vorübergehenden Auslagerung von Speicherbereichen auf einen Massenspeicher, meistens die Festplatte.Wüst: Mikroprozessortechnik. 2011, S. 173. Bei der Speicherverwaltung werden also Daten vom Arbeitsspeicher auf die Festplatte ein- und ausgelagert.
Häufig verfügt ein System über sehr viel mehr virtuellen als physischen Speicher. Konkret legt das installierte RAM fest, wie groß der physische Speicher ist, während der virtuelle Adressraum von der Architektur des Befehlssatzes abhängt. Mit einem 32-Bit-Prozessor kann man maximal Byte (also 4 GiB) Speicher adressieren, mit einem 64-Bit-System Byte (16 EiB), auch wenn beispielsweise nur 512 MiB RAM tatsächlich installiert sind.
Das Konzept der virtuellen Speicherverwaltung ist meist Basis für Multitasking, da so jeder Task einen eigenen Adressraum besitzen kann, was die Abschirmung der Tasks voneinander unterstützt; zusätzlich ist die Größe des Task-Adressraums nicht mehr abhängig davon, wie viel Arbeitsspeicher andere Tasks belegen.
Zur Organisation des virtuellen Speichers gibt es einerseits den segmentorientierten Ansatz (siehe Segmentierung), bei dem der Speicher in Einheiten unterschiedlicher Größen aufgeteilt ist, und andererseits den seitenorientierten Ansatz (Paging), bei dem alle Speichereinheiten gleich lang sind.
Seitenauslagerung
mini|hochkant=1.5|Paging mit Seiten im virtuellen (logischen) Speicher, Seitentabelle und Seitenrahmen im physischen Speicher Beim Paging wird der virtuelle Adressraum in gleich große Stücke unterteilt, die man als Seiten (engl. pages) bezeichnet. Auch der physische Adressraum ist derart unterteilt. Die entsprechenden Einheiten im physischen Speicher nennt man Seitenrahmen oder auch Kacheln (engl. page frames). Seiten und Seitenrahmen sind in der Regel gleich groß, beispielsweise 4 KiB.Wüst: Mikroprozessortechnik. 2011, S. 174; Tanenbaum: Moderne Betriebssysteme. 2009, S. 243.
Beispiel: Die physische Größe des Arbeitsspeichers sei 64 KiB. Ein Programm benötigt insgesamt 200 KiB Speicher. Um das größere Programm trotzdem auf dem kleineren Arbeitsspeicher ausführen zu können, kann man den Adressraum in Seiten (Pages) aufteilen, beispielsweise vier Seiten zu 64 KiB, wobei dann die letzte Seite nur teilweise gefüllt ist. Es befindet sich dann jeweils eine der vier Seiten im physischen Arbeitsspeicher, die anderen drei sind auf die Festplatte ausgelagert.
Der Teil der Festplatte, der für die ausgelagerten Seiten verwendet wird, wird Paging-Area oder Schattenspeicher genannt. Zum Ein- und Auslagern der Seiten existieren viele verschiedene Strategien. Grundsätzlich wird immer versucht, die Seiten im Arbeitsspeicher zu halten, die auch in naher Zukunft verwendet werden, um möglichst selten ein Paging durchzuführen.Mandl: Grundkurs Betriebssysteme. 2014, S. 223.
Solange die Speicherzugriffe Seiten betreffen, die im Arbeitsspeicher liegen, arbeitet das System ganz normal. Wird aber eine Seite im ausgelagerten Speicher angesprochen, muss die angeforderte Seite eingelagert werden (und unter Umständen eine andere Seite ausgelagert werden). Außerdem muss eine Adressabbildung aktiviert werden. Das ganze Verfahren heißt Seitenauslagerung oder Paging.
Seitentabellen
Adressabbildung
Im Multiprogramming-Betrieb stellt der Memory-Manager jedem Prozess einen eigenen virtuellen Adressraum zur Verfügung, d. h. eine Menge von Adressen, die ein Prozess zur Adressierung des Speichers benutzen kann.Anmerkung: Normalerweise hat jeder Prozess seinen eigenen Adressraum, der unabhängig von den Adressräumen der anderen Prozessen ist, mit Ausnahme von speziellen Umständen, wenn Prozesse ihre Adressräume teilen wollen. Der virtuelle Adressraum eines Prozesses wird nun beim Paging in Einheiten aufgebrochen, die sogenannten Seiten. Diese werden in der sogenannten Seitentabelle (page table) verwaltet, die Informationen darüber enthält, wo für eine Seite die entsprechenden Seitenrahmen im Arbeitsspeicher tatsächlich zu finden sind.Mandl: Grundkurs Betriebssysteme. 2014, S. 225; Tanenbaum: Moderne Betriebssysteme. 2009, S. 243–244. Mathematisch kann die Tabelle als eine Funktion aufgefasst werden, die die virtuelle Seitennummer als Argument nimmt und die Seitenrahmennummer (Page-Frame-Nummer) als Ergebnis liefert. Dadurch kann eine virtuelle Adresse auf eine physische Adresse abgebildet werden.Tanenbaum: Moderne Betriebssysteme. 2009, S. 246.
Eine virtuelle Adresse wird in zwei Teile zerlegt: Eine virtuelle Seitennummer (höherwertige Bits) und einen Offset (niederwertige Bits). Die virtuelle Seitennummer wird als Index für den Eintrag in der Seitentabelle benutzt. Der Offset stellt den relativen Abstand einer Adresse zu einer Basisadresse dar. Er ist also die Distanz, die die genaue Byteadresse innerhalb einer Seite angibt. Mit Hilfe der virtuellen Seitennummer als Index wird in der Seitentabelle der zugehörige Eintrag ausfindig gemacht. Dieser enthält einen Verweis auf den Seitenrahmen (Page-Frame). Die Seitenrahmennummer wird zur physischen Adresse ergänzt und zusammen mit der Distanz (Offset) erhält man die physische Adresse. Die Größe des Offsets sollte also so gewählt werden, dass damit jede Adresse innerhalb einer Seite angesprochen werden kann.Achilles: Betriebssysteme. 2006, S. 57; Tanenbaum: Moderne Betriebssysteme. 2009, S. 246; Mandl: Grundkurs Betriebssysteme. 2014, S. 225.
Die folgende Grafik veranschaulicht, wie aus einer virtuellen Adresse eine physische Adresse (hier: Reale Adresse) berechnet wird:
Datei:EinstufigeSeitentabelle.png
Die virtuelle Adresse besteht aus zwei Binärzahlen, die n-bit-lange Seitennummer und der m-bit-lange Offset. Der höherwertige Teil der physischen Adresse (hier: Basisadresse der realen Seite) wird der Seitentabelle entnommen, mit der Seitennummer als Index. Wird dieser mit dem Offset konkateniert, so ergibt sich eine neue Zahl, die genau die physische Speicheradresse ist. Derartige Berechnungen werden von der Memory Management Unit durchgeführt.
Die Adressen auf der Festplatte, an denen die ausgelagerten Seiten liegen, werden nicht in der Seitentabelle gespeichert. Diese enthält nur Informationen, die die Hardware zur Umrechnung einer virtuellen Adresse in eine physische benötigt. Bei der Behandlung von Seitenfehlern wird auf eigene Tabellen im Betriebssystem zurückgegriffen.Tanenbaum: Moderne Betriebssysteme. 2009, S. 247.
Aufbau eines Seitentabelleneintrages Über die Seitennummer als Index kann ein Eintrag in der Seitentabelle adressiert werden. Der genaue Aufbau eines solchen Eintrages ist stark maschinenabhängig. Die darin enthaltene Information ist jedoch von Maschine zu Maschine etwa gleich. Nach Andrew S. Tanenbaum (2009) sieht ein typischer Seitentabelleneintrag folgendermaßen aus:
500px
Die einzelnen Einträge haben dabei die folgenden Bedeutungen:Tanenbaum: Moderne Betriebssysteme. 2009, S. 246–247. Seitenrahmennummer: Eine physische Adresse im Arbeitsspeicher, auf den der Eintrag verweist (siehe Abschnitt oben). Present-/Absent-Bit: Dieses zeigt an, ob die Seite momentan im Arbeitsspeicher liegt (Bit auf 1 gesetzt) oder nicht (Bit auf 0 gesetzt). Letzteres erzeugt einen Seitenfehler. Protection-Bits (auch Schutzbits): Diese regeln den Zugriff auf die Seite. Im einfachsten Fall enthält das Feld nur 1 Bit, mit 0 für Lese- und Schreibzugriff und 1 für Schreibzugriff. Eine ausgefeiltere Methode benutzt drei Bits, jeweils eines für das Leserecht, eines für das Schreibrecht und eines für das Recht, die Seite auszuführen. M-Bit (Modified-Bit, auch Dirty-Bit): Das M-Bit wird gesetzt, wenn ein Programm auf eine Seite schreibt. Dies verwendet das Betriebssystem beim Auslagern einer Seite: Wenn die Seite verändert wurde, muss der Seitenrahmen zurück auf die Festplatte geschrieben werden, wenn nicht, kann er einfach überschrieben werden, weil die Kopie der Seite auf der Festplatte noch aktuell ist.