1 Linux Paging, Caching und Swapping. 1 Vortragsstruktur Paging – Das Virtuelle Speichermodell –Die Page Table im Detail –Page Allocation und Page Deallocation

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


– Das Virtuelle Speichermodell– Die Page Table im Detail







1

Ein einzelner Page Table Eintrag eines Prozesses

V Zugriffsrechte D PFN

„Valid“ Flag

„Page Dirty“ Flag

1



„Valid“ Flag


Valid gesetzt

Valid gelöscht PFN gelöscht

PFN gesetzt Seite vorhanden

Seite ungültig (Page fault)

&

&

1



„Valid“ 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



„Valid“ 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



– Die Page Table im Detail– Page Allocation und Page Deallocation






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

...


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

...


mem_map Struktur

free_area Vektor

mem_map_t

map Bitmaps

1




– Page Allocation und Page Deallocation– Memory Mapping und Demand Paging





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










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





Swap Cache löscht den Page Table Entry

1

Swap Cache






Seite soll ins Swap File ausgelagert werden

1

Swap Cache



Page wird in Swap File geschrieben


Seite wird verworfen.Grosse Zeitersparnis



Seite nicht im Cache Seite im Cache

Seite soll ins Swap File ausgelagert werden

1


CPU (Prozessor)

TLB

OS (Linux)

1


CPU (Prozessor)

TLB

OS (Linux)

ExceptionTLB miss

neuer TLB

1


CPU (Prozessor)

TLB

OS (Linux)exception bearbeitet

1










1

PFN 3PFN 2PFN 1PFN 0


„Working Set“ eines Prozesses

Prozess mit Seiten im physischen Speicher

1




countage

map_nr

countage

map_nr

mem_map_tProzess mit Seiten im physischen Speicher

1




„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







• Swapping– Welche Pages eines Prozesses werden ausgelagert– Der Kernel Swap Demon (kswapd)


1

Systeminitialisierung

kswapd wirdgeladen

Kernel Swap Timerwird initialisiert

free_pages_high und free_pages_lowwerden initialisiert

1


kswapd wirdgeladen


free_pages_low und free_pages_highwerden initialisiert

Anzahl freier Seiten unter free_pages_low?

nein

1


kswapd wirdgeladen




Anzahl freier Seiten unter free_pages_high?

nein

nein

1


kswapd wirdgeladen





nein

nein

Don‘t Panic

1


kswapd wirdgeladen





nein

neinja

Don‘t Panic

1


kswapd wirdgeladen





nein

neinja

Don‘t Panic3 Seiten freimachen

1


kswapd wirdgeladen





nein

neinja


ja

1


kswapd wirdgeladen





nein

nein

ja

ja


6 Seiten freimachenNur halbeZeitspanne

schlafen

1


kswapd wirdgeladen





nein

nein

ja

ja


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








– 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


Physische Seiten

„clock“ Algorithmus Prozeß A

Prozeß B

Prozeß C

1


Physische Seiten


Page Tables

Prozeß A

Prozeß B

Prozeß C

1


Physische Seiten


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


kswapd

Prozeß A Prozeß B Prozeß C

Darf Prozeß geswappt werden?

1


kswapd



Dürfen Seiten geswappt werden? (nicht locked / shared)

1


kswapd




Muß eine Seite geswappt werden oder kann man sie einfach verwerfen? (Können die Informationen anders wiederhergestellt werden?)

1


kswapd




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“

Documents

1 Linux Paging, Caching und Swapping. 1 Vortragsstruktur Paging – Das Virtuelle Speichermodell –Die Page Table im Detail –Page Allocation und Page Deallocation