Virtueller Speicher im Ernst: was ein Seitenfehler wirklich kostet

Der erste Grad hat die Form geklaert: die Adresse, die ein Programm sieht, ist virtuell, die MMU uebersetzt sie ueber eine Seitentabelle, und eine Seite, die nicht im RAM liegt, erzeugt einen Fehler, der sie von der Platte holt. Das war die Karte. Jetzt gehen wir die Strecke ab, denn in den Details lebt und stirbt die Leistung.

Das Erste, was die Karte verdeckt, ist dass die MMU es sich nicht leisten kann, bei jedem Zugriff die Seitentabelle zu lesen. Eine vierstufige Seitentabelle bedeutet vier voneinander abhaengige RAM-Zugriffe, bevor du die Daten ueberhaupt beruehrst, jeder Zugriff waere also fuenfmal langsamer. Deshalb haelt der Prozessor einen kleinen Cache der letzten Uebersetzungen: die TLB, typisch 64 bis 1536 Eintraege, voll assoziativ, direkt an der Pipeline. Ein Treffer kostet einen Takt. Deshalb laeuft ein Programm, das 100 MB mit guter Lokalitaet anfasst, fast mit voller Geschwindigkeit, obwohl die Seitentabelle riesig ist: es benutzt jeweils nur wenige tausend verschiedene Seiten.

Wenn die TLB daneben greift und die Seite nicht im Speicher ist, haelt die ganze Pipeline an. Die Hardware laeuft die Seitentabelle durch, sieht das geloeschte Praesenzbit und loest einen Fehler aus. Der Befehl wird mitten im Flug verworfen, der Trap-Handler laeuft, der Kernel findet oder raeumt einen Rahmen, liest 4 KiB vom Geraet, aktualisiert die Seitentabelle, traegt einen TLB-Eintrag ein und kehrt zurueck, um den Befehl zu wiederholen - der jetzt gelingt. Die Hardware erledigt den leichten Teil in Nanosekunden, die Software den teuren in Mikrosekunden.

TLB hit: 1 cycle
walk: 3 or 4 reads
RAM: 30 ns
SSD: 0.1 ms
HDD: 8 ms

fault rate: 1/1000
0.001 x 0.1 ms = 100 ns
30 ns -> 130 ns per accessDie Kostenleiter. Die SSD ist schnell genug, dass eine niedrige Fehlerrate verkraftbar ist, die drehende Platte nicht.

Wenn ein Rahmen gebraucht wird und der Speicher voll ist, muss etwas verdraengt werden. Die bestmoegliche Wahl, koennte man die Zukunft sehen, ist die Seite, die am spaetesten wieder gebraucht wird: die optimale Politik von Belady. Sie ist nicht implementierbar, aber sie ist das Massband. Die beste praktische Naeherung ist LRU - verdraenge die am laengsten unbenutzte Seite -, und hier ist der Haken, der zaehlt: exaktes LRU ist ebenfalls nicht implementierbar. Es verlangt einen Zeitstempel bei jedem Zugriff, also einen Schreibzugriff bei jedem Lesen, und genau das soll die TLB vermeiden. Deshalb naehern sich echte Kernel ihm an, und die Naeherung ist der Clock-Algorithmus.

Der Clock-Algorithmus haelt Rahmen in einer Kreisliste, jeder mit einem Referenzbit. Die Hardware setzt dieses Bit bei jedem Zugriff, und sie kann das umsonst. Wird ein Rahmen gebraucht, wandert der Zeiger: ist das Bit gesetzt, wurde die Seite kuerzlich benutzt, also loesche das Bit und gib ihr eine zweite Chance; ist das Bit geloescht, ist sie einen vollen Umlauf unberuehrt geblieben, also verdraenge sie. Die zweite Chance ist das Kluge daran - sie trennt Seiten, die einmal in einem Schub beruehrt wurden, von Seiten, die wirklich zum Arbeitset gehoeren, zum Preis von einem Bit und einem Durchlauf des Zeigers.

for (;;) {
  frame = frames[hand];
  if (frame.ref_bit == 1) {
    frame.ref_bit = 0;
    hand = (hand + 1) % nframes;
  } else {
    evict(frame);
    break;
  }
}Der Clock-Algorithmus vollstaendig. Der Zeiger laeuft um und gibt jeder kuerzlich benutzten Seite genau eine weitere Chance.

Nun die Eigenschaft, die Ersetzungspolitiken ueberhaupt interessant macht. Ein Stack-Algorithmus ist einer, bei dem die Menge der im Speicher liegenden Seiten in N Rahmen immer eine Teilmenge der Menge in N+1 Rahmen ist. LRU ist ein Stack-Algorithmus, mehr Speicher kann also nie mehr Fehler verursachen. FIFO ist keiner, und Clock auch nicht, und die Folge ist die Belady-Anomalie: es gibt Zugriffsfolgen, bei denen vier Rahmen mehr Fehler erzeugen als drei. Das ist keine seltene Kuriositaet, sondern das direkte Symptom einer Politik, die ohne ein globales Verstaendnis von Aktualitaet entscheidet, und deshalb kuemmern sich Produktivkernel um LRU-artige Altersverfolgung statt um einen einfachen Rundlauf.

reference string   1 2 3 4 1 2 5 1 2 3 4 5

3 frames           9 faults
4 frames          10 faults

FIFO    more frames -> more faults
CLOCK   more frames -> more faults
LRU     more frames -> never worse
OPT     more frames -> never worseDie klassische Zugriffsfolge. Die ersten fuenf Fehler genuegen, damit vier Rahmen schlechter sind als drei.

Das Arbeitset eines Prozesses ist die Menge der Seiten, die er in einem Zeitfenster aktiv benutzt. Passt diese Menge in den Speicher, der ihm zugeteilt wurde, ist die Fehlerrate niedrig und stoert kaum. Passt sie nicht, hat der Prozess ein Problem: jede Seite, die er verdraengt, ist eine, die er bald wieder braucht, also erzeugt der naechste Zugriff einen Fehler, der wieder eine gebrauchte Seite verdraengt, und so weiter.

working set: 20 MiB
5 threads: 100 MiB
RAM: 64 MiB

resident set: 12 MiB
fault -> evict -> fault -> evictEin konkreter Fall: fuenf Threads mit je 20 MiB in einem Container mit 64 MiB RAM.

Das ist Thrashing, und es erklaert das Symptom, das jeder schon gesehen hat und wenige benennen koennen. Die Maschine wirkt vollstaendig eingefroren: die Maus stockt, nichts reagiert, die Plattenlampe leuchtet durchgehend. Du siehst dir die Prozessorlast an, und sie ist ueberhaupt nicht hoch. Der Grund ist, dass ein fehlernder Prozess blockiert und nicht am Laufen ist. Er sitzt in der Warteschlange, waehrend das Geraet arbeitet, also ist die CPU im Leerlauf - und der Scheduler startet daraufhin einen anderen Prozess, der prompt auf seinen eigenen Seiten fehlgreift, die Seiten des ersten verdraengt und ebenfalls blockiert. Der Prozessor ist leer, weil jeder lauffaehige Thread auf ein 4-KiB-Lesen wartet, und das System ist langsam, nicht weil es zu viel rechnet, sondern weil es zwischen zwei Plattenoperationen fast nichts rechnet. Mehr Prozesse machen es schlimmer, was der Intuition widerspricht, mehr Arbeit halte die CPU beschaeftigt.

Zwei Hardwarehinweise, die die Zahlen veraendern. Erstens transparente Riesenseiten: der Kernel kann Teile des Speichers mit 2-MiB-Seiten statt 4-KiB-Seiten abbilden, was die noetigen TLB-Eintraege um den Faktor 512 senkt. Fuer eine Datenbank, die eine Tabelle scannt, kann das ein grosser Gewinn sein. Zweitens, und in die andere Richtung, kann es ein Verlust sein: eine 2-MiB-Seite muss ganz geschrieben werden, ein Programm, das 4 KiB einer Riesenseite veraendert, zahlt also 2 MiB Ein- und Ausgabe. Deshalb hat der Kernel die Modi always und madvise, und deshalb hat die Voreinstellung ueber die Versionen hinweg gewechselt.