Vorlesung Betriebssysteme IIThema 4: Hauptspeicherverwaltung

Robert Baumgartl

27. April 2015

1 / 49

FreispeicherverwaltungMotivation

Applikationen und das Betriebssystem selbst fordern zurLaufzeit Speicher an (und geben diesen später wieder zurück).→ Notwendigkeit der Verwaltung

I notwendig, zur Laufzeit Speicher an Anfordernde(Applikationen, BS) auszureichen und wiederentgegenzunehmen

I Schnittstelle: Menge an Funktionen, die Speicheranfordern und diesen wieder zurückgeben

2 / 49

FreispeicherverwaltungProbleme

I Fragmentierung:intern – Verlust durch feste Segmentgröße

(„Verschnitt“)extern – Verlust durch inkohärente Speicherung

(„Verstreuung“)→ Kompensation durchKompaktifizierung

Table ∼ – Verlust durch Speicherbedarf derVerwaltungsstrukturen

I LaufzeitkomplexitätI der Suche nach freiem SegmentI der Rückgabe des Segments (Wiedereinordnung)

Zwei grundlegende Management-Techniken:1. Bitmaps2. Listen

3 / 49

Bitmaps

I Anforderung wird auf einen oder mehrere Blöcke einerfixen Größe abgebildet

I „Karte“ des HauptspeichersI Blöcke (allocation units) einheitlicher GrößeI pro Block ein Bit:

I = 0→ Block freiI = 1→ Block belegt

A B C D E

belegt frei belegt belegt belegt belegtfrei frei

Allokations−

einheit

n

11111000

11111111

11001111

11111000

Bitmap

4 / 49

BitmapsBlockungsfaktor

I Parameter: Blockungsfaktor n, beeinflusst:I Speicherbedarf für die BitmapI interne Fragmentierung

I Gefahr der externen FragmentierungI fixe Größe der VerwaltungsstrukturI keine weiteren Verwaltungsinformationen in Bitmap

speicherbar

5 / 49

Freispeicherliste

I Idee: Suche nach einem “‘passenden”’ freien SegmentI ggf. Abtrennen des nicht benötigten RestesI d.h. , es werden stets exakt passende Segmente

ausgegeben (→ keine interne Fragmentierung)I pro Segment ein Element einer verkettete Liste (einfach,

doppelt, Ring), enthält:I AnfangsaddresseI LängeI belegt/frei-InformationI Zeiger auf Nachfolge-ElementI weitere Informationen, z. B. Eigentümer

A 0 5 5 3 B 8 6 C 14 4

18 2 D 20 6 E 26 3 29 3

Start

6 / 49

Blöcke mit integrierten Headern

Variante: Header ist in Blöcke integriert (belegt/frei-Bit, Länge,evntl. Zeiger auf NF)

Länge

0

Länge

0

Länge

1 1 1

Länge

Länge

...

Header

7 / 49

FreispeicherlisteSuchstrategien

Suchoperation bei Forderung eines Segmentes der Größe m:

First FitI Durchsuchen der Liste beginnend von StartI erstes freies Segment ≥ m wird genutztI ggf. Abtrennen des Überschusses (Teilung des Segments;

1 freies→ 1 belegtes + 1 freies)I Tendenz: anfangs belegte Segmente, später mehr freie

SegmenteNext FitI Start der Suche an letzer ErfolgspositionI sonst wie First FitI Tendenz zu größerer Fragmentierung als First Fit

8 / 49

FreispeicherlisteSuchstrategien II

Best FitI Suche in Liste nach bestpassendstem Element (kleinstes

Element, dessen Größe l ≥ m)I Suchaufwand!I Gefahr der Generierung unbenutzbar kleiner

RestsegmenteWorst FitI Suche nach größtmöglichem Element, um Nachteil von

Best Fit zu begegnenI → externe Fragmentierung !

Bei Freigabe eines Blockes:I Markierung als freiI Vereinigung mit freien Nachbarblöcken, wenn möglich

9 / 49

FreispeicherlisteTechniken zur Effizienzsteigerung

Verzögertes Vereinigen (Deferred Coalescing):I freigegebene Segmente nicht sofort mit freien

Nachbarsegmenten vereinigenI Effizienzsteigerung wenn Objekte einer Größe angefordert

und freigegeben werdenI Vereinigung erst nach Verzögerung oder durch extra

AktivitätI → Objektcache (Slab Allocator)

Begrenzungsmarken (Boundary Tags)I Endebegrenzung jedes Segmentes durch zum Header

identischen FooterI vereinfacht Vereinigung mit unmittelbar vorangehendem

(freien) NachbarblockI Problem: Table Fragmentation

10 / 49

FreispeicherlisteTechniken zur Effizienzsteigerung II

Zusätzliche Verkettung freier SegmenteI schnellere SucheI kein zusätzlicher Speicherplatz nötig, da nur im

ungenutzten Speicher angelegt

...H F H H H HF F F F

Abbildung: Zusätzliche Verkettung freier Segmente

11 / 49

Getrennte Freispeicherlisten (Segregated Fits)

Idee: Array von Listen unterschiedlicherSegmentgröße(nklassen), um Suchaufwand zu reduzieren

Variante 1: Einfacher getrennter Speicher (Simple SegregatedStorage)I eine Liste pro SegmentgrößeI keine Teilung von SegmentenI Liste leer→ 1-2 Seiten mittels sbrk() anfordern, in

gleichgroße Blöcke teilen, in Liste einordnenI kein Transfer zwischen Listen ( keine Vereinigung mit

benachbarten Segmenten)I ziemlich effizient im durchschnittlichen FallI Worst Case?

12 / 49

Getrennte Freispeicherlisten (Segregated Fits)

Variante 2: Getrennte FitsI Liste leer→ Liste mit nächster Größe durchsucht, Teilung

eines gefundenen Segmentsa) exakte Listenb) Strikte Größenklassen mit Rundungc) Listen mit Größenintervallen

I ggf. Wiederholung der Suche in Listen mit größerenSegmenten

I Vereinigung benachbarter freier Segmente (sofort oderverzögert)

13 / 49

Buddy-Verfahren

Idee: System reicht Blöcke fester Größe k = 2N Bytes aus

I N Listen mit (exakter) SegmentgrößeI ausgereicht wird stets ein Block mit der Größe, die die

Anforderung am knappsten befriedigt (z. B. Anforderung 47KiB→ Auslieferung 64 KiB)

I wenn kein Block passender Größe vorhanden:1. Teilung eines nächstgrößeren (freien) Blockes2. Auslieferung einer Hälfte3. andere Hälfte (der „Buddy“) wird als frei in die

entsprechende Liste einsortiertI Initial enthält eine Liste genau einen Block, den gesamten

(freien) HauptspeicherI Bei Rückgabe wird geprüft, ob der Block ggf. mit seinem

Buddy vereinigt werden kann (und in der Liste dernächstgrößeren Blöcke eingeordnet werden kann)

14 / 49

Buddy-VerfahrenBeurteilung

I Aufwand bei Rückgabe des Speichers geringer als mitFreispeicherliste

I wirkt externer Fragmentierung entgegen, da stets maximalwieder vereinigt wird

I Hauptnachteil: Speicherplatzverschwendung (Verschnitt;interne Fragmentierung)

15 / 49

Virtueller SpeicherMotivation

Ziel:I Schutz der Aktivitäten voreinanderI die Größe des Hauptspeichers übersteigende

ProzesssystemeKonzept:I „Erweiterung“ des Hauptspeichers durch MassenspeicherI Privatisierung der AdressräumeI Partitionierung der virtuellen und des physischen

Adressraums (einheitliche, feste Größe; z. B. 4 KiB)

16 / 49

Virtueller SpeicherSeiten vs. Kacheln

I virtueller Adressraum→ logische Seiten (virtuelle Seiten,Pages)

I physischer Adressraum→ (gleichgroße) Kacheln(Seitenrahmen, Page Frames)

17 / 49

Virtueller SpeicherSeiten vs. Kacheln

Kacheln

A

P

Q

R

B

C

D

frei

frei

Prozeß 1

A

B

C

D

Prozeß 2

P

Q

R

physischer Hauptspeicher

Seiten

MMU+OS

virtueller Speicher

...

...

Abbildung: Abbildung logischer Seiten auf physische Kacheln18 / 49

Gestreute SpeicherungUmsetzung virtueller in physische Adresse

I bei jeder (!) SpeicherreferenzI ausgeführt durch Hardware (Memory Management Unit –

MMU im Prozessor)I Indexierung einer Tabelle (Seitentabelle, Page Table)I Seitentabelle durch BS verwaltet, existiert pro Prozess

+

Seitennummer Index

...

physische

Adresse

Hauptspeicher

Seitentabelle

0x8000 RW

RO

RWX

RO

...

...

...

0x1000

0x3000

0x4000

1

1

0

0x0000

0x1000

0x2000

0x4000

selektiertes

Wort

virtuelle Adresse

PProtSeitenadressen

1

19 / 49

Seitentabelleneintrag (Page Table Entry – PTE)Aufbau (Beispiel)

P Page Frame NumberProtRCD M

I PFN – Page Frame Number – Adresse derentsprechenden physischen Kachel

I P – Present-Bit – Seite ist im Hauptspeicher (oder aufMassenspeicher ausgelagert)

I Prot – Protection – Lese-/Schreib-/Ausführungs-Operationsind (nicht) erlaubt

I M – Modified (“dirty”) – Kachel wurde beschrieben (→muss vor Auslagerung auf Massenspeicherzurückgeschrieben werden)

I R – Referenced – Seite wurde durch den Prozess(irgendwann einmal) gelesen, referenziert

I CD – Cache disable – Seiteninhalt darf nicht gecachtwerden (wichtig bei memory-mapped devices)

20 / 49

Größe der einstufigen Seitentabelle

Problem: Größe der Seitentabelle (muß hintereinander imSpeicher stehen)

Beispiel

Seitengröße 4 KiB, 32 Bit Adressbreite→ Index 12 Bit (212 = 4096)→ Seitennummer 20 Bit groß (32-12=20)→ Seitentabelle kann 220 Einträge enthalten→ resultierende Größe der Seitentabelle 4 MByte (pro

Prozess!)

21 / 49

Größe der Seitentabelle

Lösung: Baum von Seitentabellen (→ Hierarchie)I langsamerer Zugriff, da mehrere Subtabellen aufgesucht

werden müssenI Subtabellen dafür kürzer und flexibler (auf Anforderung

anlegbar)I zwei- (Intel i386), drei- und vierstufige HierarchienI Verbesserung des Timings durch einen Cache, der

Adressumsetzungen virtuell→ physisch aufbewahrt:Translation Lookaside Buffer (TLB)

22 / 49

Beispiel: Zweistufige Seitentabelle (i386)

Register CR3

gewähltes ByteSeite

gewählte

PTE

physischer Adreßraum

1024 Einträge1024 EinträgePage Directory Page Tables

PD−Eintrag

Byte−Index Adressevirtuelle

PT−IndexPD−Index

23 / 49

Demand Paging

Idee: Benötigte Seiten werden erst bei Bedarf in denHauptspeicher geladen. Ist der physische Speicher restlosausgenutzt, so muss zuvor eine andere Seite ausgelagertwerden.Prinzipieller Ablauf

1. Prozess referenziert eine Adresse (neuer Befehl, Zugriffauf Datum)

2. MMU führt Adressübersetzung aus3. BS prüft:

I referenzierte Seite im physischen Speicher→ Ausführungder Instruktion, Weiterarbeit

I referenzierte Seite momentan ausgelagert→ Seitenfehler(Page Fault, Software-Interrupt)

24 / 49

Seitenfehler (Pagefault)

1. Prozess wird angehalten (blockiert)2. BS sucht freie HS-Kachel3. falls keine freie HS-Kachel verfügbar→ Auswahl einer

auszulagernden Seite, Auslagerung auf Festplatte4. Einlesen der referenzierten Seite in (nun) freie HS-Kachel

von Festplatte5. Weiterarbeit des blockierten Prozesses

Pro Seitenfehler bis zu 2 Festplattenzugriffe notwendig!

Einfachere Alternative: Swapping: ganze Prozesse werdenausgelagert!

25 / 49

Einlagerungsstrategien

I Demand Paging: Einblenden einer Seite bei Referenz(spätestmöglicher Zeitpunkt, Lazy Evaluation)

I Prepaging: Seiten werden im voraus eingeblendet.Sinnvoll bei kontinuierlicher Ablage auf Massenspeicher;angewandt z.B. bei Start eines neuen Prozesses(Windows NT).

26 / 49

Seitenaustauschverfahren

Frage: Welche Seite soll ausgelagert werden?

I Ähnlichkeit zur Ersetzungsstrategie in CachesI Strafe (Penalty) sehr hoch, da Massenspeicherzugriff:

I 1 Instruktion benötigt ca. 0.3 ns bei 3 GHz TaktI 1 Festplattenoperation benötigt ca. 10 msI → Zeit für ≈ 30 · 106 Instruktionen

I Worst Case?

27 / 49

SeitenaustauschverfahrenOptimales Verfahren; LRU

Optimales VerfahrenI lagert diejenige Seite aus, die am längsten nicht benötigt

wird (in Zukunft)I schwierig ohne eingebauten HellseherI wichtig zum Vergleich realer Verfahren

Least Recently Used (LRU)I Heuristik: Seiten die lange nicht referenziert wurden,

werden auch in Zukunft kaum gebrauchtI exaktes LRU schwierig („älteste Seite auslagern“)I vgl. CacheI Approximation: NRU

28 / 49

SeitenaustauschverfahrenNot Recently Used (NRU)

Not Recently Used (NRU)I Ausnutzung des Referenced- und des Modified-Bits im

SeitentabelleneintragI periodisches Rücksetzen des R-Bits durch BS (z.B. durch

Timerinterrupt gesteuert)I R-Bit wird automatisch (durch MMU) gesetzt, sobald Seite

referenziert wurdeI M-Bit gesetzt, wenn Seiteninhalt modifiziert wurde („dirty“)→ vor Auslagerung zurückschreiben

29 / 49

SeitenaustauschverfahrenNot Recently Used (NRU), contd.

I 4 Klassen von Seiten unterscheidbar:R M Beschreibung0 0 Seite wurde nicht referenziert0 1 Seite wurde lange nicht referenziert, aber (irgendwann)

verändert1 0 Seite wurde referenziert, aber nicht modifiziert1 1 Seite wurde referenziert und geändert

I bei Bedarf zunächst Auslagerung von {00}-SeitenI wenn keine verfügbar, dann {01}-Seiten, dann {10}-Seiten,

usw.

30 / 49

SeitenaustauschverfahrenFIFO; 2nd Chance

First In, First Out (FIFO)I Idee: ältere Seiten zuerst auslagernI keine Berücksichtigung der Referenz

Second ChanceI verbessert FIFOI Auslagerungskandidat (AK): älteste Seite

I R == 0→ Seite wird ausgelagertI R == 1→ R := 0, Kandidat: nächstälteste Seite

I Anordnung der Seiten in Ringliste, Zeiger auf AK→„Uhralgorithmus“

31 / 49

SeitenaustauschverfahrenNFU; Aging

Not Frequently Used (NFU)I Betrachtung der ReferenzierungshäufigkeitI pro Seite ein Zähler, periodisches Aufaddieren des R-BitsI Auslagerung der am seltensten genutzten Seite (kleinster

Zählerstand)I später eingelagerte Seiten benachteiligtI benötigt: Vergessen veralteter Zählerstände

AgingI Modifikation von NFU:

I alle Zähler vor Aufaddieren des R-Bits 1 Bit nach rechtsgeschoben

I R-Bit wird an höchste Bitposition des Zählers geschrieben

32 / 49

SeitenaustauschverfahrenAging, contd.

1 0 1 0 1 1

10000000 11000000 111000000

1

2

3

4

5

R−Bits 1 0 1 1 1 0 0 1 1 01 0 0 1 0 1 0 1 0 0 0 1 0 0

1000000000000000

10000000

00000000

10000000

10000000

01000000

00000000

11000000

01000000

11000000

00100000

10000000

01100000

10100000

11110000

01100000

01000000

10110000

01010000

01111000

10110000

10001000

00100000

01011000

00101000

1 2 3 4 5Tick

00010000

Abbildung: Beispiel für den Aging-Algorithmus

I Shift-Operation realisiert „Vergessen“ alter ZählerständeI Häufigkeit und Zeitpunkt der Referenzierung relevant

33 / 49

Konzept der Arbeitsmenge (Working Set)

Empirische Beobachtung: eine bestimmte Anzahleingeblendeter Seiten ist optimal.I Anzahl zu gering→ hohe Seitenfehlerrate,I Anzahl zu groß→ Speicherverschwendung,

möglicherweise kein Prozess mehr bereit.Prinzip: Die Arbeitsmenge W (t ,∆) sind diejenigen Seiteneines Prozesses, die zwischen dem aktuellen Zeitpunkt t undeinem Zeitpunkt t −∆ in der Vergangenheit referenziertwurden.

34 / 49

Beispiel für eine Arbeitsmenge

Referenz- ∆kette 2 3 4 524 24 24 24 2415 24, 15 24,15 24,15 24,1518 15, 18 24,15,18 24,15,18 24,15,1823 18, 23 15,18,23 24,15,18,23 24,15,18,2324 23, 24 18,23,24 ? ?17 24, 17 23, 24, 17 18, 23, 24, 17 15, 18, 23, 24, 1718 17, 18 24, 17, 18 ? 23, 24, 17, 1824 18, 24 ? 17, 18, 24 ?18 ? 24, 18 ? 17, 24, 1817 18, 17 24, 18, 17 ? ?17 17 18, 17 ? ?15 17, 15 17, 15 18, 17, 15 24, 18, 17, 1524 15, 24 17, 15, 24 17, 15, 24 ?17 24, 17 ? ? 17, 15, 2424 ? 27, 24 ? ?18 24, 18 17, 24, 18 17, 24, 18 15, 17, 24, 18

Tabelle: Beispiel der Entwicklung der Arbeitsmenge eines Prozessesfür unterschiedliche ∆ (Bach: The Design of the UNIX OperatingSystem. 1986, S. 287) 35 / 49

Konzept der Arbeitsmenge (Working Set)

Es giltW (t ,∆ + 1) ⊇W (t ,∆)

d.h., die Arbeitsmenge wächst monoton mit ∆. Weiterhin gilt fürdie Menge der referenzierten Seiten

1 ≤W (t ,∆) ≤ min(∆,N)

wobei N die Gesamtzahl der referenzierten Seiten einesProzesses bezeichnet. Der Parameter ∆ kann alsFenstergröße in die Referenzierungsvergangenheit desProzesses aufgefasst werden.

36 / 49

Abhängigkeit der Größe der Arbeitsmenge von ∆

|W (t ,∆)|

∆∆0

37 / 49

Abhängigkeit der Größe der Arbeitsmenge von ∆

I „gesättigtes“ Verhalten: ab einem bestimmten Punkt (∆0)ändert sich die Größe der Arbeitsmenge nicht mehrgravierend (Ursache: Lokalitätsprinzip)

I minimale Größe der Arbeitsmenge |W (t ,∆0)|, bestimmtdie Grenze zwischen niedriger und hoher Pagefault-Rate

I Working Set unterliegt zyklischen Veränderungen; manunterscheidet transiente und stabile Zustände

38 / 49

Idee für eine Ersetzungsstrategie. . . basierend auf dem Working Set

I W für jeden Prozess beobachtenI zyklisch alle diejenigen Seiten eines Prozesses entfernen,

die nicht zu W gehörenI Prozess darf nur aktiviert werden, wenn seine

Arbeitsmenge im Hauptspeicher eingeblendet

Probleme:I exakte Messung, Logging des WS aufwendig

ApproximationI Wahl von ∆:

I zu klein→ PF-Rate des Prozesses steigtI zu groß→ Speicherverschwendung

I keine Adaption bei Größenänderung der Arbeitsmenge

39 / 49

Beladys Anomalie

Vergrößerung von W führt normalerweise zu Verringerung derPage-Fault-Rate des betroffenen Prozesses, jedoch . . .

I 5 virtuelle SeitenI Ersetzungsstrategie FIFOI (willkürliche ) Referenzierungskette: 0→ 1→ 2→ 3→ 0→ 1→ 4→ 0→ 1→ 2→ 3→ 4

0 1 2 3 0 1 4 0 1 2 3 4

0 1

0

0

1

1

2 3 0 1 4 4 4 2 3 3

älteste Seite

jüngste Seite

2

2

3

3

0

0

1 1 1

0 0

4

1

2

4

2

4

PF

Ref.−Kette

Abbildung: Beladys Beispiel mit W = 3 Seitenrahmen

40 / 49

Beladys Anomalie, contd.

0 1 2 3 0 1 4 0 1 2 3 4

0 1

0

0

1

1

2 3 4 2 3jüngste Seite

2 2

Ref.−Kette

älteste Seite 0 0

3

2

1

0

3

1

2

1

2

3 4

0

3

2

4

3

0

1

4

0

1

1

0

2

3

4

1

PF

Abbildung: Beladys Beispiel mit W = 4 Seitenrahmen

I Vergrößerung des WS führt zu Erhöhung der PF-Rate(W = 3→ 9PF, W = 4→ 10PF)

I unerwartetes Verhalten, AnomalieI konstruiertes BeispielI abhängig vom Seitenersetzungsverfahren; LRU

unempfindlich41 / 49

Weitere Aspekte zur Seitenersetzung

I optimale Seitengröße?I lokale vs. globale ErsetzungsstrategienI variable vs. konstante Größe des Working SetI viele weitere ErsetzungsstrategienI alternative Mechanismen der Suche in Seitentabellen

42 / 49

Schnittstelle zum Betriebssystem UNIXmalloc() und free()

I Semantik: Anforderung von Heap-Speicher, bzw. dessenRückgabe

I Funktionen der C-Bibliothek (→ portabel)I eine der Hauptquellen für Programmfehler ist fehlerhafter

Umgang mit diesen FunktionenI weitere Funktionen: realloc(), calloc()

I unter UNIX gewöhnlich mittels brk() realisiert (jedochauch mit mmap())

I Implementierung stark systemabhängigI viele Allokatoren vergrößern Heap zwar, verkleinern

jedoch nicht (Optimierung)I Seiten werden bei malloc() weder initialisiert noch

zwangsweise eingeblendetI bekannteste Implementation: Doug Lea’s Allocator

43 / 49

Speicherabbild eines Prozesses

(BSS)

Stack

initialisierte Daten

uninitialisierte Daten

Text

null−initialisiert

aus Datei eingelesen

durch

Heap

High

Low

Umgebung, Argumente

"break"

exec()

44 / 49

Der Systemruf brk()

int brk(void *end_data_segment);I setzt das Ende des Heaps auf end_data_segment,

vorausgesetztI Wert ist plausibel,I das System hat noch genügend Speicher,I maximale Heapgröße des Prozesses wird nicht

überschrittenI genutzt z. B. zur Implementierung von malloc() & Co.I weitere Funktion der C-Bibliothek: sbrk()I malloc() und brk() nicht gleichzeitig verwendbarI im Vergleich zu malloc() viel elementarer

45 / 49

Stackanforderung mittels alloca()

void *alloca(size_t size);

I alloziiert size Bytes auf dem Stack (!)I keine Rückgabefunktion benötigt (Warum?)I nicht für alle Systeme verfügbar

“The alloca function is machine and compilerdependent. On many systems its implementationis buggy. Its use is discouraged.” (man alloca,2.6er Linux-System)

I Implementierung durch Inline-Code ( nicht als Argumenteiner Parameterliste nutzbar)

46 / 49

Ausschalten des Pagings (Pinning)

I Verhinderung des Auslagernsa) einzelner Seiten mittels mlock()b) des gesamten Adressraums mittels mlockall()

I für (weiche) Echtzeit- und sicherheitskritischeApplikationen

I Rückbau mit munlock()/munlockall()I vergrößert Pagefault-Rate für nichtpinnende Prozesse

47 / 49

Memory-mapped Filesaka ‘speichereingeblendete Dateien’

I mmap(), munmap(), mremap(), msync()I blendet Dateien (oder Geräte) in den Hauptspeicher einI Granularität: SeitenI gemeinsame oder exklusive Einblendung möglichI d. h. eingeblendete Dateien werden wie Hauptspeicher

manipuliert (ersetzt klassischeopen/read/write/close-Schnittstelle)

I modern

48 / 49

Was haben wir gelernt?

I Hauptspeicherverwaltung: Bitmaps, Listen,Buddy-Verfahren

I Virtueller Speicher: Funktionsweise, Ablauf des Pagefault,relevante Datenstrukturen

I Ersetzungsstrategien (LFU, NFU, Aging & Co., WorkingSet )

I API zum Hauptspeicher von unix-artigen BS

49 / 49