1
Linux Paging, Caching und Swapping
1
Vortragsstruktur• Paging
– Das Virtuelle Speichermodell
– Die Page Table im Detail
– Page Allocation und Page Deallocation
– Memory Mapping & Demand Paging
• Caching– Die verschiedenen Caches
• Swapping– Welche Pages eines Prozesses werden ausgelagert
– Der Kernel Swap Demon (kswapd)
– Freimachen von Speicherseiten
1
VPFN 3VPFN 2VPFN 1VPFN 0
VPFN 2VPFN 1VPFN 0
PFN 7PFN 6PFN 5PFN 4PFN 3PFN 2PFN 1PFN 0
Prozeß 1 Prozeß 2
Virtuelle Speicherseite eines Prozesses
Physische Speicherseite eines Prozesses
Physische Speicherseite die von mehreren Prozessen gemeinsam genutzt wird
1
VPFN 3VPFN 2VPFN 1VPFN 0
VPFN 2VPFN 1VPFN 0
PFN 7PFN 6PFN 5PFN 4PFN 3PFN 2PFN 1PFN 0
Prozeß 1 Prozeß 2
Page TablePage Table
Virtuelle Speicherseite eines Prozesses
Physische Speicherseite eines Prozesses
Physische Speicherseite die von mehreren Prozessen gemeinsam genutzt wird
Page Table
1
Virtuell Physisch
Virtuelle Adresse 0x00484456
Page-Größe bei ix86 Systemen beträgt 4 Kilobyte, also 0x1000 B.
VPFN 0x484
Page Offset 0x456
PFN 0x89
Page Offset 0x456
Physische Adresse 0x00089456
Prozessor extrahiert Offset und VPFN
Prozessor greift auf Page Table 0x484 zu
Prozessor generiert physische Adresse und greift darauf zu
1
Vortragsstruktur• Paging
– Das Virtuelle Speichermodell– Die Page Table im Detail
– Page Allocation und Page Deallocation
– Memory Mapping & Demand Paging
• Caching– Die verschiedenen Caches
• Swapping– Welche Pages eines Prozesses werden ausgelagert
– Der Kernel Swap Demon (kswapd)
– Freimachen von Speicherseiten
1
Ein einzelner Page Table Eintrag eines Prozesses
V Zugriffsrechte D PFN
„Valid“ Flag
„Page Dirty“ Flag
1
Ein einzelner Page Table Eintrag eines Prozesses
V Zugriffsrechte D PFN
„Valid“ Flag
„Page Dirty“ Flag
Valid gesetzt
Valid gelöscht PFN gelöscht
PFN gesetzt Seite vorhanden
Seite ungültig (Page fault)
&
&
1
Ein einzelner Page Table Eintrag eines Prozesses
V Zugriffsrechte D PFN
„Valid“ Flag
„Page Dirty“ Flag
Valid gesetzt PFN gelöscht
Valid gelöscht PFN gesetzt
Valid gesetzt
Valid gelöscht PFN gelöscht
PFN gesetzt Seite vorhanden
Seite ungültig (Page fault)
Page fault: Demand Paging
Page fault: Seite im Swap
&
&
&
&
1
Ein einzelner Page Table Eintrag eines Prozesses
V Zugriffsrechte D PFN
„Valid“ Flag
„Page Dirty“ Flag
Eine neue Page wird geladen
Page wird geändert (beschrieben)
Page wird auf Datenträgerausgelagert in den Swap Bereich
Page wird dringend für einen anderen Prozeß benötigt
Seite wird verworfen
Page wird nicht beschrieben
1
Level 1 Level 2 Level 3 Byte in Seite
PFN PFN PFN Adresse
PGD
PGD: „Page Global Directory“.Vom Kernel initialisiert. Weist auf den ersten Page Table Level.
Physische Seite
1
Vortragsstruktur• Paging
– Das Virtuelle Speichermodell
– Die Page Table im Detail– Page Allocation und Page Deallocation
– Memory Mapping & Demand Paging
• Caching– Die verschiedenen Caches
• Swapping– Welche Pages eines Prozesses werden ausgelagert
– Der Kernel Swap Demon (kswapd)
– Freimachen von Speicherseiten
1
count
age
map_nr
„mem_map_t“ oder auch „Page“ Struktur:
Anzahl der Benutzer, die die Seite benutzen
Alter der Seite. Entscheidet, ob die Seite verworfen bzw. ausgelagert wird, wenn wieder Speicherplatz benötigt wird.
Physische PFN
1
0
1
2
3
4
5
PFN 0
1
2
3
4
5
6
7
8
...
Freie Speicherseite im Hauptspeicher (nicht alloziert)
free_area Vektor
1
4
0 0
1
2
3
4
5
PFN 0
1
2
3
4
5
6
7
8
...
Freie Speicherseite im Hauptspeicher (nicht alloziert)
mem_map Struktur
free_area Vektor
mem_map_t
1
4
0 0
1
2
3
4
5
PFN 0
1
2
3
4
5
6
7
8
...
Freie Speicherseite im Hauptspeicher (nicht alloziert)
mem_map Struktur
free_area Vektor
mem_map_t
map Bitmaps
1
Vortragsstruktur• Paging
– Das Virtuelle Speichermodell
– Die Page Table im Detail
– Page Allocation und Page Deallocation– Memory Mapping und Demand Paging
• Caching– Die verschiedenen Caches
• Swapping– Welche Pages eines Prozesses werden ausgelagert
– Der Kernel Swap Demon (kswapd)
– Freimachen von Speicherseiten
1
vm_ops
vm_endvm_start
mm_struct vm_area_struct
z.B. Code
z.B. initialisierteDaten (Variablen)..
Virtueller Speicher des Prozesses
Valid gesetzt PFN gelöschtDemand Paging
&
1
Vortragsstruktur• Paging
– Das Virtuelle Speichermodell
– Die Page Table im Detail
– Page Allocation und Page Deallocation
– Memory Mapping & Demand Paging
• Caching– Die verschiedenen Caches
• Swapping– Welche Pages eines Prozesses werden ausgelagert
– Der Kernel Swap Demon (kswapd)
– Freimachen von Speicherseiten
1
Buffer Cache
Page Cache
Swap Cache
Hardware Caches TLB (Translation Look-aside Buffers)
1
Buffer Cache
Block-Gerätetreiber
2 kB2 kB2 kB2 kB2 kB
Geräte-ID, Blocknummer
Hardware:Blockgerät (Festplatte)
Block wird geladen
1
Page Cache
Page fault handling code
PagePagePagePagePage
Datei, Datenoffset
Festplatte
Pointer auf mem_map_t
(single-page read ahead)
page_hash_table
mem_map_tmem_map_tmem_map_tmem_map_tmem_map_t
1
Swap Cache
Seite wird aus Swap File gelesen
Swap Cache erzeugt Page Table Entry (Swap File, Offset)
1
Swap Cache
Seite wird aus Swap File gelesen
Page wird geändert (beschrieben)
Swap Cache erzeugt Page Table Entry (Swap File, Offset)
Page wird nicht beschrieben
Swap Cache löscht den Page Table Entry
1
Swap Cache
Seite wird aus Swap File gelesen
Page wird geändert (beschrieben)
Swap Cache erzeugt Page Table Entry (Swap File, Offset)
Page wird nicht beschrieben
Swap Cache löscht den Page Table Entry
Seite soll ins Swap File ausgelagert werden
1
Swap Cache
Seite wird aus Swap File gelesen
Page wird geändert (beschrieben)
Page wird in Swap File geschrieben
Swap Cache erzeugt Page Table Entry (Swap File, Offset)
Seite wird verworfen.Grosse Zeitersparnis
Page wird nicht beschrieben
Swap Cache löscht den Page Table Entry
Seite nicht im Cache Seite im Cache
Seite soll ins Swap File ausgelagert werden
1
Hardware Caches TLB (Translation Look-aside Buffers)
CPU (Prozessor)
TLB
OS (Linux)
1
Hardware Caches TLB (Translation Look-aside Buffers)
CPU (Prozessor)
TLB
OS (Linux)
ExceptionTLB miss
neuer TLB
1
Hardware Caches TLB (Translation Look-aside Buffers)
CPU (Prozessor)
TLB
OS (Linux)exception bearbeitet
1
Vortragsstruktur• Paging
– Das Virtuelle Speichermodell
– Die Page Table im Detail
– Page Allocation und Page Deallocation
– Memory Mapping & Demand Paging
• Caching– Die verschiedenen Caches
• Swapping– Welche Pages eines Prozesses werden ausgelagert
– Der Kernel Swap Demon (kswapd)
– Freimachen von Speicherseiten
1
PFN 3PFN 2PFN 1PFN 0
PFN 7PFN 6PFN 5PFN 4
„Working Set“ eines Prozesses
Prozess mit Seiten im physischen Speicher
1
PFN 3PFN 2PFN 1PFN 0
PFN 7PFN 6PFN 5PFN 4
„Working Set“ eines Prozesses
countage
map_nr
countage
map_nr
mem_map_tProzess mit Seiten im physischen Speicher
1
PFN 3PFN 2PFN 1PFN 0
PFN 7PFN 6PFN 5PFN 4
„Working Set“ eines Prozesses
„Least Recently Used“ (LRU) Technik zur Bestimmung des
Seitenalters
countage
map_nr
countage
map_nr
mem_map_t
Linux
Prozess mit Seiten im physischen Speicher
1
LRU im Detail:
Seite wird alloziert Das Alter wird gesetzt auf: age = 3
Seitenzugriff Das Alter wird um 3 eröht,Maximalwert ist 20
„kswapd“ prüft das AlterDas Alter wird um 1 reduziert.
Wenn 0 erreicht wird,gilt die Seite als alt.
1
Vortragsstruktur• Paging
– Das Virtuelle Speichermodell
– Die Page Table im Detail
– Page Allocation und Page Deallocation
– Memory Mapping & Demand Paging
• Caching– Die verschiedenen Caches
• Swapping– Welche Pages eines Prozesses werden ausgelagert– Der Kernel Swap Demon (kswapd)
– Freimachen von Speicherseiten
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_high und free_pages_lowwerden initialisiert
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_low und free_pages_highwerden initialisiert
Anzahl freier Seiten unter free_pages_low?
nein
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_low und free_pages_highwerden initialisiert
Anzahl freier Seiten unter free_pages_low?
Anzahl freier Seiten unter free_pages_high?
nein
nein
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_low und free_pages_highwerden initialisiert
Anzahl freier Seiten unter free_pages_low?
Anzahl freier Seiten unter free_pages_high?
nein
nein
Don‘t Panic
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_low und free_pages_highwerden initialisiert
Anzahl freier Seiten unter free_pages_low?
Anzahl freier Seiten unter free_pages_high?
nein
neinja
Don‘t Panic
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_low und free_pages_highwerden initialisiert
Anzahl freier Seiten unter free_pages_low?
Anzahl freier Seiten unter free_pages_high?
nein
neinja
Don‘t Panic3 Seiten freimachen
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_low und free_pages_highwerden initialisiert
Anzahl freier Seiten unter free_pages_low?
Anzahl freier Seiten unter free_pages_high?
nein
neinja
Don‘t Panic3 Seiten freimachen
ja
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_low und free_pages_highwerden initialisiert
Anzahl freier Seiten unter free_pages_low?
Anzahl freier Seiten unter free_pages_high?
nein
nein
ja
ja
Don‘t Panic3 Seiten freimachen
6 Seiten freimachenNur halbeZeitspanneschlafen
1
Systeminitialisierung
kswapd wirdgeladen
Kernel Swap Timerwird initialisiert
free_pages_low und free_pages_highwerden initialisiert
Anzahl freier Seiten unter free_pages_low?
Anzahl freier Seiten unter free_pages_high?
nein
nein
ja
ja
Don‘t Panic3 Seiten freimachen
6 Seiten freimachenNur halbeZeitspanneschlafen
Zuletzt benutzte Methode wiederbenutzen:
1.) Page- und Buffer-Cache Seiten reduzieren
(z.B. Memory Mapped Files, Festplattendaten)
2.) System V Shared Memory Seiten auslagern (Swap File)
3.) Speicherseiten auslagern (Swap File)
1
Vortragsstruktur• Paging
– Das Virtuelle Speichermodell
– Die Page Table im Detail
– Page Allocation und Page Deallocation
– Memory Mapping & Demand Paging
• Caching– Die verschiedenen Caches
• Swapping– Welche Pages eines Prozesses werden ausgelagert
– Der Kernel Swap Demon (kswapd)– Freimachen von Speicherseiten
1
1.) Page- und Buffer-Cache Seiten reduzieren
(z.B. Memory Mapped Files, Festplattendaten)
Kein Swapping (Datenträgerzugriff) nötig!
mem_map mem_map_tPhysische Seiten
„clock“ Algorithmus
1
2.) System V Shared Memory Seiten auslagern (Swap File)
Physische Seiten
„clock“ Algorithmus Prozeß A
Prozeß B
Prozeß C
1
2.) System V Shared Memory Seiten auslagern (Swap File)
Physische Seiten
„clock“ Algorithmus
Page Tables
Prozeß A
Prozeß B
Prozeß C
1
2.) System V Shared Memory Seiten auslagern (Swap File)
Physische Seiten
„clock“ Algorithmus
Page Tables
Prozeß A
Prozeß B
Prozeß C
Page Table Eintrag „invalid“ setzen
PFN auf Swapposition setzen (Datei, Offset)
User Count für die Seite um 1 reduzieren (mem_map_t)
Wenn User Count = 0, dann Seite „swappen“
1
3.) Speicherseiten auslagern (Swap File)
kswapd
Prozeß A Prozeß B Prozeß C
Darf Prozeß geswappt werden?
1
3.) Speicherseiten auslagern (Swap File)
kswapd
Prozeß A Prozeß B Prozeß C
Darf Prozeß geswappt werden?
Dürfen Seiten geswappt werden? (nicht locked / shared)
1
3.) Speicherseiten auslagern (Swap File)
kswapd
Prozeß A Prozeß B Prozeß C
Darf Prozeß geswappt werden?
Dürfen Seiten geswappt werden? (nicht locked / shared)
Muß eine Seite geswappt werden oder kann man sie einfach verwerfen? (Können die Informationen anders wiederhergestellt werden?)
1
3.) Speicherseiten auslagern (Swap File)
kswapd
Prozeß A Prozeß B Prozeß C
Darf Prozeß geswappt werden?
Dürfen Seiten geswappt werden? (nicht locked / shared)
Muß eine Seite geswappt werden oder kann man sie einfach verwerfen? (Können die Informationen anders wiederhergestellt werden?)
Seite verwerfen Einige wenige Seiten wählen
Seiten ins Swap File auslagern
1
Vortragsende
„Linux Paging, Caching und Swapping“