Stichpunkte

Allgemein
	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
	da das Paging nur einen - wenn auch zentralen - Aspekt der virtuellen Speicherverwaltung ausmacht
	Dieser Sprachgebrauch ist jedoch unpräzise
	"Verbergen") 1 Zweck des Pagings 2 Funktionsweise 3 Adressberechnung beim Paging 4 Demand Paging 5 Thrashing und Working Set 6 Kriterien und Strategien für die Seitenersetzung 7 Sinkende Bedeutung des Verfahrens [Bearbeiten]
	sondern auf ganze Segmente des Speichers ausgeführt wird und somit Teil der Segmentierung ist. Inhaltsverzeichnis showTocToggle("Anzeigen"
	Zu unterscheiden ist das Paging jedoch deutlich vom Swapping
	da letzteres nicht nur auf Speicherseiten
Zweck des Pagings
	ist das Problem der externen Fragmentierung
	das durch Paging gelöst wird
	Das wesentliche Problem
	Dieses Problem ist das folgende: Jedem Prozess wird vom Betriebssystem ein Adressraum zugeordnet
	da neue Prozesse zumeist nicht dieselbe Speichermenge benötigen wie beendete Prozesse und diese somit nicht eins zu eins ersetzen können
	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
	aber sehr aufwändig
	Eine regelmäßige Neuordnung des Speichers (Kompaktifizierung genannt) wäre zwar möglich
	indem man die Prozesse segmentiert
	d.h. nicht einen einzigen zusammenhängenden Adressraum
	In erster Näherung kann man das Problem lindern
	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. [Bearbeiten]
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
	im physischen Speicher können die benachbarten Seiten jedoch in weit von einander entfernt liegenden Seitenrahmen abgelegt werden
	Nun wird klar
	warum hier keine externe Fragmentierung im Hauptspeicher mehr auftreten kann: Zwar ist der logische Speicher weiterhin zusammenhängend
	und somit macht es auch keinen Sinn mehr
	Die Reihenfolge der Seitenrahmen ist damit beliebig
	müssen keine Effizienzeinbußen in Kauf genommen werden
	von Lücken und damit von externer Fragmentierung zu sprechen. Da die Zugriffszeit auf einzelne physische Speicherzellen immer identisch ist
	Da bei diesem Verfahren der Zugriff auf die Seitentabelle sehr häufig ist
	die sogenannte Memory Management Unit. (Dieser Artikel liefert Ihnen zusätzliche detaillierte Informationen über die Verwendung der Seitentabelle.) [Bearbeiten]
	verwenden moderne Prozessoren zu diesem Zweck in der Regel spezielle Hardware-Register
Adressberechnung beim Paging
	In der Terminologie der obigen Grafik entspricht eine logische Speicheradresse der virtuellen Adresse
	Der physische Speicher heißt hier reale Adresse
	der zweite Teil der Seitentabelle
	dass sich die physische Speicheradresse sehr einfach aus zwei Teilen berechnet: Der erste Teil wird der virtuellen Adresse entnommen
	Man entnimmt der Grafik
	Dabei handelt es sich um zwei Binärzahlen
	die genau die physische Speicheradresse ist
	Werden diese konkateniert
	so ergibt sich eine neue Binärzahl
	Derartige Berechnungen werden von der Memory Management Unit ausgeführt. [Bearbeiten]
Demand Paging
	wird der Paging-Mechanismus auch zur virtuellen Speicherverwaltung ausgenutzt
	Wie oben schon erwähnt
	Erfolgt nun ein Zugriff auf eine Speicherseite
	die nicht im Hauptspeicher
	so wird zunächst ein Seitenfehler (engl. page fault) ausgelöst
	sondern im Auslagerungsspeicher abliegt
	Dieser führt zu einem Software-Interrupt und schließlich zum Laden der Seite in den Hauptspeicher
	Diese Technik bezeichnet man als Demand Paging. [Bearbeiten]
Thrashing und Working Set
	Diese Technik hat jedoch ihre Grenzen
	dann ist es überwiegend mit dem Nachladen und Auslagern von Seiten beschäftigt
	Wenn in einem Rechnersystem zu viele Seitenfehler auftreten
	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)
	darf der Arbeitsspeicher im Verhältnis zum Auslagerungsspeicher nicht zu klein sein
	Um Thrashing zu vermeiden
	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
	sondern arbeitet an einem Prozess
	In diesem Betriebszustand wartet der Prozessor nicht auf das Nachladen von Seiten
	während parallel für andere Prozesse Seiten nachgeladen werden
	muss p(s) ≤ t/T sein
	im Verhältnis zur Gesamtzahl aller für die Programmausführung benötigten Seiten (0 < s ≤ 1) p(s): Die Wahrscheinlichkeit eines Seitenfehlers
	der sich im Arbeitsspeicher befindet
	Entscheidend sind dabei folgende Größen: t: Die Zeit
	um auf eine Speicherstelle zuzugreifen T: Die Zeit
	die der Prozessor braucht
	die benötigt wird
	abhängig von s Damit Thrashing vermieden wird
	um eine Seite nachzuladen s: Der Anteil an Seiten
	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
	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
	Deshalb ist die Wahrscheinlichkeit sehr hoch
	ergeben unter diesen Bedingungen für w einen Wert von nicht wesentlich weniger als 0
	die bereits in den 1960er Jahren durchgeführt wurden
	5
	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
	Das bedeutet
	dass der Auslagerungsspeicher kaum größer als der Arbeitsspeicher sein darf. [Bearbeiten]
Kriterien und Strategien für die Seitenersetzung
	weil eine unveränderte Seite nicht auf den Hintergrundspeicher zurückgeschrieben werden muss
	Verschiedene Kriterien werden zur Bewertung herangezogen: Die Zugehörigkeit der Speicherseite zum aktiven Prozess Der letzte Zugriff auf die Speicherseite Die Unversehrtheit der Speicherseite
	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
	die entweder nicht benutzt oder modifiziert wurden und als letzte Gruppe erst Speicherseiten
	Danach Seiten
	die modifiziert und benutzt wurden
	Not frequently Used: Seitenzugriffe werden mit dem zeitlichen Abstand zur aktuellen Anfrage korreliert und so ein Wert ermittelt. [Bearbeiten]
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
	selbst wenn eine Memory Management Unit vorhanden ist. Andererseits ist seit den 1990er Jahren Arbeitsspeicher sehr billig geworden
	die Interrupts und die Umschaltvorgänge kleine Zeitverluste
	das Auslagern gänzlich zu vermeiden
	Daher versucht man heutzutage
	indem man den Arbeitsspeicher entsprechend großzügig bemisst
	Siehe auch: Memory Management Unit
	Virtueller Adressraum en:Paging et:Lehekülgede saalimine
	Swapping
	Segmentierung (Speicherverwaltung)
	Speicherseite
	Seitenfehler

Dieser Artikel basiert auf dem Artikel Paging aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.