Kapitel 7 - Seitenersetzung
|
Inhalt
|
- Seitenersetzungsalgorithmen wie FiFo, LRU...
- Working Sets als dynamische Variante
- Problem der Seitengröße
|
Was sind Seitenersetzungsalgorithmen?
Falls eine Seite angefordert wird, aber kein Platz für deren Einlagerung im Speicher mehr vorhanden ist, so muss eine
andere Seite entfernt werden. Aber welche? Es gibt nun verschiedene Ansätze für dieses Problem...
Welcher wäre der beste Algorithmus zur Seitenersetzung?
Dieser ist theoretisch gegeben, aber nicht umsetzbar. Die Seite die am spätesten erst wieder verwendet wird,
wird ausgelagert. Da in einem Echtzeitsystem nie vorhersagbar ist, welcher Prozess wann wie lange aktiv sein wird, ist diese Strategie nicht
umsetzbar... In einem deterministischen Modell wäre er aber durchaus denkbar, da dort jeder Schritt eindeutig definiert ist.
Wie arbeitet die Seitenersetzung mit Not-Recently-Used?
Jede Seite bekommt zwei Statusbits zugeordnet. R wird gesetzt, wenn die Seite lesend oder schreibend referenziert wurde.
M wird gesetzt, falls die Seite verändert wird. Diese beiden Bits sind in jedem Seitentabelleneintrag enthalten und müssen
bei jeder Seitenreferenzierung aktualisiert werden.
Die zwei Bit stellen vier Klassen dar, welche genutzt werden um einen Paging-Algorithmus zu realisieren.
- nicht referenzierte und nicht modifizierte Seite
- nicht referenzierte und modifizierte Seite
- referenzierte und nicht modifizierte Seite
- referenzierte und modifizierte Seite
LRU wählt zufällig eine Seite aus der kleinstnummerierten Klasse zum Entfernen aus.
Wie arbeitet die Seitenersetzung mit Fifo - First In First Out?
Es wird eine Liste geführt, welche alle Seiten enthält. Neue Seiten werden an das Ende der Liste angefügt. So ist die
Liste nach dem Alter der Seiten sortiert.
Der FiFo Paging-Algorithmus macht nichts weiter, als bei einem Seitenfehler die älteste Seite zu entfernen, also die
Seite, die am Anfang der Liste steht.
Das Problem an Fifo ist, daß auch extrem häufig referenzierte Seiten ausgelagert werden. Um dies zu umgehen wird das
oben schon erwähnte R (Referenziert) Bit verwendet, um jeder Seite eine zweite Chance zu geben, falls das R-Bit nicht null ist.
Wie arbeitet die Seitenersetzung mit Second Chance?
Arbeitet wie Fifo, nur wird beim Entfernen des Kopfes nachgeschaut, ob das R Bit null ist. Wurde die Seite nie
referenziert, so wird sie entfernt, wie für FiFo üblich. Wurde sie aber referenziert, wird sie zum Ende der Liste
verschoben, als wurde sie neu geladen. Das R-Bit wird dabei auf Null gesetzt. So wird gewährleistet, das häufig
benutzte Seiten weniger oft als nicht referenzierte Seiten ausgelagert werden.
Second Chance ist ein durchaus guter Paging Algorithmus mit einem Nachteil. Es müssen ständig konstante Seiten
innerhalb der Liste von Anfang zum Ende verschoben werden. Diesen Nachteil bügelt der Uhr Algorithmus aus.
Wie arbeitet der Uhr-Seitenersetzungsalgorithmus?
Der Clock-Algorithmus arbeitet im Prinzip wie Second Chance, nur das anstelle einer FiFo Liste eine Ringliste
verwendet wird. Dabei wird in einem Pointer (Zeiger der Uhr) auf den aktuellen Anfang der Liste gezeigt. Bei
einer Second Chance muss nun nicht die Seite verschoben werden, es wird einfach der Zeiger auf das nächste
Element referenziert.
Der Uhr Algorithmus ist also eine Implementation von Second Chance mit einer Ringliste.
Wie arbeitet die Seitenersetzung mit Least-Recently-Used?
Dieser Paging Algorithmus versucht den Optimalen zu approximieren, indem es versucht die Seiten zu entfernen,
welche am Längsten nicht mehr benutzt wurden.
Die Implementation ist trotzdem nicht ganz einfach. Es müsste theoretisch eine Liste geführt werden, welche nach dem
oben genannten Kriterium sortiert ist. Diese Liste müsste nach jeder Seiteneinlagerung neu Sortiert werden. Da dies
eine zu komplexe Operation darstellt, muss dafür eine Softwarelösung approximiert werden, welche wesentlich schneller arbeitet.
Wie arbeitet die Seitenersetzung LRU mit Matrixumsetzung?
Es wird eine globale N x N Matrix für alle N Seiten geführt. Diese Matrix wird mit 0 initialisiert. Wird eine Seite x
referenziert, so wird die Zeile x auf 1 gesetzt und danach die Spalte x auf 0.
In jedem Moment ist die Zeile deren Summe am Kleinsten ist, die am wenigsten genutzte und die Zeile mit dem größten
Wert, die am häufigsten genutzte Seite.
Wenn die notwendige Hardware (Matrix) nicht vorhanden ist, muss ein anderer effizienter Paging Algorithmus benutzt
werden, der ohne jede Hardware auskommt.
Wie arbeitet die Seitenersetzung NFU - Not Frequently Used?
Bei jeder Uhrunterbrechung wird das Referenziert-Bit jeder Seite auf einen Softwarezähler, welcher mit null initialisiert
wurde, hinzuaddiert. Es wird also versucht zu zählen, wie oft eine Seite referenziert wird. Das Problem von NFU ist es,
dass Spitzen in der Referenzierung starke Auswirkungen auf den Zähler haben. So kann es vorkommen, daß eine Seite, welche
anfangs stark genutzt wurde und später nicht mehr, einer zyklisch genutzten Seite nicht zur Auslagerung vorgezogen wird.
Eine Modifikation von NFU versucht LRU zu simulieren und diesen Fehler aufzuheben.
Wie arbeitet die Seitenersetzung mit Aging - LRU durch Softwareemulation?
- Vor der Addition es Referenziert-Bits werden alle Zähler um eins nach rechts geschoben
- das Refenziert-Bit wird auf das am weitesten links stehende Bit addiert
Bei einem Seitenfehler wird auch hier die Seite mit dem kleinsten Fehler entfernt. Durch das Rechtsverschieben
verkleinert sich der Wert eines Zählers rapide und es wird verhindert, daß nur kurzeitig verwendete Seiten
fälschlicherweiße als oft referenziert angesehen werden...
- Not-Recently-Used (referenziert und modifiziert Bits - vier Zustände)
- Least-Recently-Used (Seiten die lange nicht benutzt worden auslagern) und LRU mit Matrixumsetzung
- FiFo, Second Chance, Uhr-Seitenersetzungsalgorithmus
- Aging - LRU durch Softwareemulation
|
|
|
Merktabelle: Seitenersetzungsalgorithmen |
Was sagt die Belady's Anomalie?
Eine Erhöhung der Seitenrahmen im Speicher, also mehr Speicher, heißt nicht zwangsläufig eine Verringerung von Seitenfehlern!
Was passiert beim Einsatz einer schnelleren Platte mit der Seitenfehlerrate?
Die Seitenfehlerrate steigt, da die Übertragungszeit für Seiten sinkt. Die Anzahl der gleichzeitig
ausführbaren Prozesse steigt, da jeder Prozeß nun mit weniger Seitenrahmen - und einer höheren Fehlerrate - "leben" kann.
Was sind Working Sets - dynamisches Seitenaustauschverfahren?
Prozess Arbeitsbereiche werden eingesetzt und die Zahl der Seitenfehler weiter zu minimieren. Ein Prozess
unterliegt auch einer Art Lokalität. Es werden im Mittel bestimmte Seiten häufiger und Andere sogut wie nie
oder gar nicht zur Prozessabarbeitung benötigt. Man nennt dies Referenzielle Lokalität.
Mit Arbeitsbereichen wird versucht Informationen vor dem Laden eines Prozesses auszunutzen, um häufig
verwendete Referenzen bevorzugt zu behandeln. Die Erfassung der für das Working Set notwendigen Daten wird auch
über eine Art Aging Algorithmus umgesetzt. Jede Seite gehört zu einem bestimmten Working Set. Wird eine Seite länger
als N Ticks nicht mehr benutzt, wird sie aus dem Working Set entfernt.
Die gewonnene Information des Working Sets kann verwendet werden, um den Clock Algorithmus zu verbessern. Und zwar
wird nicht nur nach einer nichtreferenzierten Seite geschaut, sondern auch ob die Seite zu einem Working Set gehört oder nicht.
Falls sie einem Arbeitsbereich angehört, wird sie übersprungen, egal ob im Moment referenziert oder nicht.
Welche Problematik tritt bei der Arbeitsmengenstrategie auf?
Das Hauptproblem ist die Seitenauslagerung durch Herausfallen von Seiten aus dem Working Set.
Seiten können aus dem Working Set ausgelagert werden, ohne das ein Seitenfehler vorliegt und ohne das für diese
Seite eine Neue eingelagert wurde. Die aktuelle Lokalität wird eben nur approximiert. Die Arbeitsmenge enthält
möglicherweise auch Seiten die nur einmal benutzt wurden. Der Übergang zu einer neuen Lokalität erfolgt nur allmählich.
Welche Gefahr besteht bei Seitenaustauschverfahren?
Gefahr des Seitenflatterns (Trashing). Bei Überlastung mit zu vielen Prozessen die entweder zu viele Pagefaults
produzieren und/oder zuwenig Seitenrahmen zur Verfügung haben, ist der Rechner weitgehend mit dem Ein-/und Auslagern
von Seiten beschäftigt und kann an den eigentlichen Aufgaben der Prozesse kaum noch weiterarbeiten. Effektive CPU
Auslastung sinkt durch viele Seitenfehler. Weitere Gefahr besteht dann durch zu einfach konstruierte Scheduler, die bei
sinkender CPU-Auslastung mit einer höheren Prozessintensität reagieren.
Page Damons können dem Abhilfe schaffen, weil sie Prozesse auslagern, wenn nicht mehr ausreichend Seitenrahmen im
Speicher zur Verfügung stehen.
Was kann man gegen Trashing (Seitenflattern) tun?
Page Dämons benutzten, denn dadurch wird die Anzahl der gleichzeitig aktiven Prozesse verringert und jedem Prozeß stehen
mehr Seitenrahmen zur Verfügung.
Wie wird die Seitengröße festgelegt?
Die Seitengröße ist normalerweise klein. Dies hat verschiedene Gründe sie klein zu halten, aber auch einen
wichtigen Grund, die Größe nicht zu klein zu definieren.
Im Mittel ist die letzte Seite eines Codestückes nur halb gefüllt, da logischerweise nicht jedes Code, Stack
oder Datensegment genau in eine Seite passen kann oder sich so auf mehrere verteilt, daß kein freier Speicher mehr verbleibt.
Des Weiteren muss beachtet werden, dass es auch viele kleine Segment gibt. Angenommen man legt eine Seitengröße
von 32 KB fest, so werden bei 4 KB großen Segmenten stets 28 KB verschwendet.
Andersherum benötigt man mit kleinen Seiten eine größere Seitentabelle, deren Anzahl proportional zur Seitengröße ist.
Des Weiteren muss man einkalkulieren, daß das Einladen einer Seite von Platte eine langwierige Operation ist.
Es ist trivial das das Einlagern von vier 8K-Seiten schneller ist, als das Einlagern von 64 512 Byte großen Seiten.
Es muss also ein Mittelweg gefunden werden, welcher einen optimalen Nutzen aus den oben genannten Kriterien zieht.
Verschwendung = Prozessgröße * Seitentabelleneintragsgöße / Seitengröße + Seitengröße / 2
Die Nullstellenberechnung der ersten Ableitung in Abhängigkeit der Seitengröße ergibt :
Optimale Seitengröße = Wurzel aus 2 * Prozessgröße * Seitentabelleneintragsgöße
|
|
|
|
|
| Kapitel 1 | Einleitung |
|
Ebenen- oder Schichtenmodell, Aufgaben...
|
| Kapitel 2 | Modelle |
|
Schichtenmodell, Betriebsmittel, Instanzen...
|
| Kapitel 3 | Aktivitäten |
|
Token, Multitasking, Prozesse,Timesharing...
|
| Kapitel 4 | Kritischer Abschnitt |
|
Gegenseitiger Ausschluss,Peterson,Semaphore...
|
| Kapitel 5 | Scheduling |
|
Prozessorzuteilung, Prioritätsscheduling, RR...
|
| Kapitel 6 | Speichermanagment |
|
Freispeicherverwaltung, Segmentierung, Paging...
|
| Kapitel 7 | Seitenersetzung |
|
NRU, FiFo, Second Chance, LRU, NFU, Aging...
|
| Kapitel 8 | Deadlocks |
|
Bedingungen, Erkennung und Auflösung...
|
| Kapitel 9 | Dateisysteme |
|
Freispeicherverwaltung, Festplattenscheduling...
|
|
|
|
|
|
|
|
|
Quellen:
|
Andrew S. Tanenbaum
Computerarchitektur
|
Andrew S. Tanenbaum
Moderne Betriebssysteme
|
Petterson
Computer Architectur & Design
|
Christian Märtin
Rechnerarchitekturen
|
Kalfa
Skript und Vorlesung
|
Word Wide Web
Verschiedenste Seiten
|
|
|
|
|
|
|
Home 
