Seitenersetzung: FIFO, LRU und die optimale Strategie

Der Speicher hat einige Seitenrahmen, die jeweils eine Seite aufnehmen. Das Programm fordert die Seiten in der Reihenfolge der Referenzfolge an. Liegt eine Seite bereits in einem Seitenrahmen, ist der Zugriff ein Treffer. Andernfalls tritt ein Seitenfehler auf. Sind alle Seitenrahmen belegt, muss eine Seite weichen: FIFO verdrängt die zuerst geladene Seite, LRU die am längsten nicht mehr verwendete und OPT diejenige, die erst am spätesten wieder gebraucht wird.

Rechenbeispiel — Seitenersetzung: FIFO, LRU und die optimale Strategie

Zugriffe	12

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Seitenersetzung: FIFO, LRU und die optimale Strategie

Der Speicher ist in gleich große Seitenrahmen unterteilt, die Daten eines Programms in Seiten derselben Größe. So passt jede Seite in jeden Seitenrahmen. Die Referenzfolge gibt an, auf welche Seiten ein Programm der Reihe nach zugreift. Ein Zugriff auf eine Seite, die nicht im Speicher liegt, verursacht einen Seitenfehler: Die Seite wird geladen. Ist kein Seitenrahmen frei, entscheidet eine Ersetzungsstrategie, welche Seite verdrängt wird. Eine Strategie zeigt bei einer Referenzfolge die Bélády-Anomalie, wenn sie mit F + 1 Seitenrahmen mehr Seitenfehler verursacht als mit F Seitenrahmen.

Was die einzelnen Symbole bedeuten

F: Anzahl der Seitenrahmen
n: Anzahl der Seiten in einer Schleife (durchgerechnete Aufgabe)
r: Anzahl der Schleifendurchläufe

Setzt voraus: Beim Demand Paging wird eine Seite erst geladen, wenn sie angefordert wird. Der Speicher ist anfangs leer, sodass der erste Zugriff auf jede Seite bei jeder Strategie einen Seitenfehler verursacht. Werden mehrere Seiten nicht mehr gebraucht, verdrängt OPT hier die Seite mit der kleinsten Nummer. Jeder Zugriff gilt genau einer Seite. Lese- und Schreibzugriffe werden nicht unterschieden; das Verdrängen einer Seite verursacht keine Kosten. Eine exakte Umsetzung von LRU müsste den Zeitpunkt jedes Speicherzugriffs festhalten. Das ist zu aufwendig. Deshalb nähern Betriebssystemkerne LRU mithilfe eines Referenzbits pro Seite an. Der bekannteste dieser Ansätze ist der Clock-Algorithmus.

Ein Seitenrahmen mehr, ein Seitenfehler mehr 🖖

Klick auf FIFO, 3 Seitenrahmen, dann auf FIFO, 4 Seitenrahmen. Die Referenzfolge lautet 1 2 3 4 1 2 5 1 2 3 4 5. Der größere Speicher verursacht mehr Seitenfehler: 10 gegenüber 9. Geh mit beiden Einstellungen bis zu Schritt 7, in dem Seite 5 angefordert wird. Bei 3 Seitenrahmen wurden die Seiten 1 und 2 bereits verdrängt und erneut geladen. Sie sind deshalb die zuletzt geladenen Seiten, und FIFO verdrängt Seite 4. Bei 4 Seitenrahmen blieben 1 und 2 durchgehend im Speicher. Seite 1 wurde als erste geladen; FIFO verdrängt sie genau einen Schritt, bevor das Programm sie wieder anfordert. Bélády, Nelson und Shedler beschrieben diesen Effekt 1969. Er ist selten: Wir haben FIFO für sämtliche Referenzfolgen mit weniger als 12 Zugriffen und beliebig vielen verschiedenen Seiten ausgeführt. Bei keiner tritt er auf. Von den 4.213.597 Folgen mit genau 12 Zugriffen zeigen 8 diesen Effekt. Folgen, die sich nur in der Benennung der Seiten unterscheiden, wurden dabei als dieselbe Folge gezählt. Alle 8 beginnen mit 1 2 3 4 1 2 5 1 und verursachen beim Wechsel von 3 auf 4 Seitenrahmen genau einen zusätzlichen Seitenfehler. Diese Folge ist die einzige der 8 mit 5 verschiedenen Seiten.

Mehr Speicher verursacht bei LRU und OPT nie mehr Seitenfehler 🖖

Klick auf LRU, 4 Seitenrahmen: Bei derselben Referenzfolge entstehen 8 Seitenfehler, gegenüber 10 mit 3 Seitenrahmen. Mit F Seitenrahmen hält LRU die F zuletzt verwendeten Seiten im Speicher. Mit F + 1 Seitenrahmen sind es dieselben Seiten und eine weitere. Daher sind in jedem Schritt sämtliche Seiten des kleineren Speichers auch im größeren vorhanden. Ein Zugriff, der bei 3 Seitenrahmen ein Treffer ist, bleibt bei 4 Seitenrahmen ein Treffer. FIFO hält die zuletzt geladenen Seiten im Speicher. Wie viele Seitenrahmen zur Verfügung stehen, beeinflusst jedoch, wann welche Seite geladen wird: Nach Schritt 7 enthalten 3 Seitenrahmen die Seiten 1, 2 und 5; 4 Seitenrahmen enthalten 2, 3, 4 und 5. Bei OPT sind die Seitenmengen ebenso ineinander enthalten wie bei LRU. Strategien mit dieser Eigenschaft heißen Stack-Algorithmen. In der Tabelle unter den Ergebnissen, die die Seitenfehler für jede Anzahl von Seitenrahmen angibt, steigt ihre Fehlerzahl deshalb nie an. Bei FIFO kann sie steigen. Die betreffende Zelle ist markiert.

Eine Schleife mit einer Seite zu viel verursacht bei LRU nur Seitenfehler 🖖

Klick auf Schleife, LRU: 5 Seiten werden bei 4 Seitenrahmen 3-mal der Reihe nach gelesen. Jeder der 15 Zugriffe verursacht einen Seitenfehler. Die am längsten nicht mehr verwendete Seite ist nämlich stets diejenige, die die Schleife als Nächstes anfordert. FIFO verhält sich hier genauso. Klick auf Schleife, OPT, und die Zahl sinkt auf 7. OPT verdrängt die Seite, die erst am spätesten wieder gebraucht wird. In den Schritten 5 und 9 ist das die gerade gelesene Seite. Welche Seite das ist, weiß OPT nur, weil es vor der Entscheidung die gesamte restliche Referenzfolge liest. Das kann kein Betriebssystem. OPT liefert einen Vergleichsmaßstab: die geringste Anzahl von Seitenfehlern, die eine Strategie bei dieser Referenzfolge erreichen könnte. Gib der Schleife einen 5. Seitenrahmen, und alle drei Strategien verursachen 5 Seitenfehler, einen pro Seite.

Aufgabe vollständig gelöst

Wann LRU bei jedem Zugriff einen Seitenfehler verursacht 5 Schritte
Klick auf Schleife, OPT und bestimme, bei welchen Zugriffen die 7 Seitenfehler auftreten. Betrachte dann ein Programm, das ein Array von 100 Seiten 1.000-mal aufsummiert. Es stehen 99 Seitenrahmen zur Verfügung. Wie viele Seitenfehler entstehen mit LRU, wie viele mit OPT? Wie viele sind es mit einem 100. Seitenrahmen?

Öffne diese Aufgabe im Tool
1. Im Beispiel verursachen die ersten 5 Zugriffe Seitenfehler: 4 füllen die leeren Seitenrahmen, der 5. verdrängt eine Seite. Danach treten die Seitenfehler in den Schritten 9 und 13 auf, im Abstand von 4 Zugriffen: 5 + 2 = 7.
  
  $5 + 2 = 7 faults: steps 1 - 5, 9, 13$
2. Bei n − 1 Seitenrahmen und einer Schleife über n Seiten fehlt genau eine Seite der Schleife im Speicher. Tritt ein Seitenfehler auf, wird die unmittelbar zuvor gelesene Seite erst am spätesten wieder gebraucht: nach n − 1 Zugriffen. Im letzten Durchlauf werden manche Seiten nicht mehr benötigt; OPT kann dann auch eine davon verdrängen. Nach dem Verdrängen liegen die Seiten für die nächsten n − 2 Zugriffe im Speicher. Der nächste Seitenfehler tritt deshalb n − 1 Zugriffe später auf, im Beispiel nach 4 Zugriffen.
  
  $n - 1 frames : one fault every n - 1 references$
3. LRU mit 99 Seitenrahmen: Verursacht der Zugriff auf Seite p einen Seitenfehler, enthalten die Seitenrahmen alle anderen Seiten. Am längsten nicht mehr verwendet wurde p + 1, also die Seite, die die Schleife als Nächstes anfordert. Jeder der 100 × 1.000 = 100.000 Zugriffe verursacht einen Seitenfehler. Im Beispiel gilt das ebenso für alle 15 Zugriffe. FIFO verdrängt dieselben Seiten.
  
  $LRU : 100 \times 1000 = 100000$
4. OPT: Die ersten 99 Zugriffe füllen die Seitenrahmen. Ab dem 100. Zugriff tritt alle 99 Zugriffe ein Seitenfehler auf, bei den Zugriffen 100, 199, 298, … Das sind 1 + ⌊(100.000 − 100) / 99⌋ = 1 + 1.009 = 1.010 Seitenfehler. Insgesamt ergeben sich 99 + 1.010 = 1.109. Das entspricht n + ⌊n(r − 1)/(n − 1)⌋ mit n = 100 und r = 1.000.
  
  $OPT : 99 + (1 + ⌊ \frac{100 000 - 100}{99} ⌋) = 99 + 1010 = 1109 = n + ⌊ \frac{n ( r - 1 )}{n - 1} ⌋$
5. Mit einem 100. Seitenrahmen passt das gesamte Array in den Speicher. Jede der drei Strategien verursacht dann 100 Seitenfehler, einen pro Seite. Nach dem ersten Durchlauf treten keine mehr auf.
  
  $F = 100 : 100 faults$
Antwort

LRU: 100.000, OPT: 1.109, mit einem zusätzlichen Seitenrahmen: 100. Eine Schleife, deren Seitenzahl die Zahl der Seitenrahmen um eins übersteigt, ist der ungünstigste Fall für LRU. Der zusätzliche Seitenrahmen senkt hier die Zahl der Seitenfehler um den Faktor 1.000.

$LRU 100000, OPT 1109, 100 with one frame more$

Lernpfad

Was eine Datenstruktur mit wenig Aufwand leistet

Quellen (1)

The first insight's date and attribution: the anomaly, and its formal treatment for FIFO: L. A. Belady, R. A. Nelson and G. S. Shedler, "An anomaly in space-time characteristics of certain programs running in a paging machine," Communications of the ACM 12(6), 349–353, June 1969.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.