1 Linux Paging, Caching und Swapping. 1 Vortragsstruktur Paging – Das Virtuelle Speichermodell...

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 halbeZeitspanne

schlafen

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 halbeZeitspanne

schlafen

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_t Physische 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“