1
SpeicherSpeicher--verwaltungverwaltung
Kap. 4
Version vom 05.10.2009
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 2
Kap. 4 - Inhalt
ÜbersichtDirekte SpeicherbelegungLogische Adressierung und virtueller SpeicherSeitenverwaltungSegmentierungCacheSpeicherschutz
2
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 3
Übersicht I
Speicher ist neben dem Prozessor das wichtigste BetriebsmittelSpeicherhierarchie
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 4
Übersicht II
Typische Speicherhierarchie mit ZahlenZahlen sind sehr grobe Schätzungen
< 1KB
1 MB
1GB – 16GB
100-1500GB
40-200GB
3
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 5
Übersicht III
Unterschiedliche Strategien für verschiedene Bereiche
Anwenderprogrammeinterner Speicher: z.B. Verwaltung des Heaps durch Speichermanager oder garbage collector
Hauptspeicher Aufteilung auf Prozesse: globaler vs. lokaler Speicher bei Multiprozessorsystemen
Massenspeicher internes Management bei Dateien, z.B. der Swapdatei
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 6
Übersicht IV
Wesentliche Strategien der Speicherverwaltung für Prozesse
Komplette Speicherbelegung (Prozeß) auslagern (swapping: langsam)
Speicherteile (Prozeßteile) auslagern
4
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 7
Direkte Speicherbelegung I
Einfache SpeicherbelegungEin Benutzerprogramm ohne Swapping oder Paging
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 8
Direkte Speicherbelegung II
Multiprogramming mit festen Partitionen
5
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 9
Direkte Speicherbelegung III
CPU Benutzung als Funktion der Zahl der Prozesse im SpeicherDegree of multiprogramming
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 10
Direkte Speicherbelegung IV
Zuordnung durch feste TabellenTabelleneinheit (z.B. 1Bit) gibt Zustand einer Speichereinheit (z.B. 32Bit-Wort oder 4KB-Einheit, ...) an
98 A76543 C21 B0
... 1 1 1 0 0 1 1 1 1 1... 9 8 7 6 5 4 3 2 1 0
Speicherbelegung Belegungstabelle
FREI
6
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 11
Direkte Speicherbelegung V
Zuordnung durch verzeigerte Listen
Speicherbelegung Belegungsliste
98 A76543 C21 B0
FREI.len=2FREI.start=5
C.len=3C.start=2
B.len=2B.start=0
A.len=3A.start=7
Anfang
FREI
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 12
Direkte Speicherbelegung VI - Belegungsstrategien
Unabhängig von der Art der Verwaltung derSpeicherbelegungslisten gibt es verschiedene Strategien, um aus der Menge der unbelegten Speicherblöcke den geeignetsten heraus-zusuchen. Ziele: Anzahl der freien Bereich minimierenGröße der freien Bereiche maximieren
7
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 13
Direkte Speicherbelegung VII - Belegungsstrategien
FirstFitNimm das erste, ausreichend große Stück. Aber: Reststücke
NextFitwie FirstFit, aber führe Speicherindex mit
BestFitkleinste freie Stück, das paßt
WorstFitgrößte freie Stück, um große Reststücke zu erreichen
QuickFiteine Liste pro Anforderungsgröße, also pro Datentyp
Buddy-SystemeListen von 2n großen Speicherstücken: 256B, 512B, 1024B, 2048B, ...Kein passendes Stück da: Zerteilen des nächstgrößeren.Verschmelzen mit jeweils dem Partnerstück bei gleichem Adressenanfang
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 14
Direkte Speicherbelegung VI - Bewertung
Bewertung der Belegungsstrategien
FirstFit > NextFit, WorstFit, BestFit
Kenntnisse über Speicheranforderungen: QuickFit
Leistungsfähigkeit der buddy-SystemeÜberschlagsrechnung:
mittl. Anforderung = 75%, vergeudet 25%tats. Belegung
⇒ schnell, aber nicht effizient
Verbesserung: halbe oder viertel Partner (aber: Verwaltung!)
8
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 15
Direkte Speicherbelegung VII - Fragmentierung
Fragmentierung und Verschnitt
Interner Verschnitt Interne Zersplitterung durch Heap-BelegungAbhilfe: garbage collector des Programmiersystems
Externer VerschnittFreier Platz zwischen den Programmen im AuslagerungsbereichAbhilfe: zuerst Einlagern großer Prozesse, dann Auffüllen mit kleinen. → swapping kleiner Programme (gegen SJF-Strategie!)Oder: Speicheraufteilung in verschieden große Bereiche, jede mit eigener Warteschlange (IBM OS/MFT): ineffizient!
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 16
Direkte Speicherbelegung VIII - Swapping
Speicherallokation ändert sich, wenn – Prozesse in den Speicher eingelagert werden
– den Speicher verlassen
Schattierte Flächen sind ungenutzter Speicher
9
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 17
Direkte Speicherbelegung IX - Swapping
• Platz für wachsendes Datensegment allokieren
• Platz für wachsendes Stack- und Datensegmentallokieren
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 18
Virtueller Speicher I - Wozu?
Probleme & EinzellösungenProbleme & EinzellösungenSpeicherzusatzbelegung
Prozeß auslagern, neuen Speicher reservieren, neu einlagernExternen Verschnitt zum Prozeß dazuschlagen (stack & heap)
Relozierung von Programmcoderel. Adressen für GOTO bei allen CPU-Typen bei Einlagerung oder zur Laufzeit absolute Adr. errechnen
SpeicherschutzBetriebssystemkern darf nicht korrumpiert werden (fences,limits), spezielle HW-EinheitProgrammiermodell soll klar, einfach und uniform sein
10
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 19
Virtueller Speicher II
Forderung: lineares ProgrammiermodellFragmente sollen zusammenhängend erscheinenNur inaktive Programmteile werden ausgelagert
Implementierung durch Memory Management Unit MMU
Beliebig langer, Fragmentierter,durchgehender Speicher endlicheri Speicher
∞...
10000
...
90008FFF
...
80007FFF
...0000
13000
...
C000
B8FF...
A900
A783
...2784
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 20
Virtueller Speicher III – Funktion und Position der MMU
11
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 21
Virtueller Speicher IV - Wichtige Begriffe
Seiten: Adreßraum ist in Einheiten gleicher Größe (sog. Seiten) aufgeteiltSeitenrahmen: physischer Speicher ist in Einheiten gleicher Größe (sog. Seitenrahmen oder Seitenkacheln) aufgeteiltSeitentabellen: verwalten Zuordung zwischen Seiten und SeitenrahmenSegmente: ähnlich wie Seiten, nur ungleich großSegmenttabellen: ähnlich wie Seitentabellen, mit Größeninformation
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 22
Seitenverwaltung I - Seitentabellen
Relation zwischenvirtuellen Adressenund physischen Speicheradressen wird durch die Seitentabelle beschrieben
12
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 23
Seitenverwaltung II - Grundmodell virt. Adreßkonversion
Virtuelle Adresse
PageNr 6 offset
Physikal.Adresse
Seitentabelle Hauptspeicherbelegung
Basisadresse 6 offset
7 Basisadresse 766 Basisadresse 65 Basisadresse 54 Basisadresse 43 Basisadresse 32 Basisadresse 21 Basisadresse 10 Basisadresse 0 ~ ~
~ ~Page 7
~ ~
HSB LSB1 1 0
Page 6
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 24
Seitenverwaltung III - Adreßkonversion
Problem: virt. Adreßraum >> phys.AdreßraumRiesige Seitentabellen! Sei Seitengröße=offset=12 Bit ≅ 4KB Seitenrahmen (page frame)
16 Bit: 4 Bit ≅ 16 Einträge32 Bit: 20 Bit ≅ 1 Mill. Einträge64 Bit: 52 Bit ≅ 4 ⋅1015 Einträge
Adreßbegrenzungkleiner Adreßraum, z.B. 30 Bit (1 GB) → 18 Bit ≅ 256 KB Tabelle
Aber: Vergeudung von Platz, da meist nicht benötigt !
13
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 25
Seitenverwaltung IV - Adreßkonversion
Multi-Level-Tabellen
page base table Seitentabellen 2 Speicherbelegung(Seitentabelle1)
3 nicht existent2 nicht existent1 nicht existent0 Seitenadresse7
3 nicht existent2 Seitenadresse51 Seitenadresse 10 Seitenadresse 2
3 nicht existent2 Seitenadresse 61 Seitenadresse 30 Seitenadresse 4
7 Tafeladresse 76 nicht existent5 nicht existent4 nicht existent3 nicht existent2 nicht existent1 Tafeladresse 10 Tafeladresse 0
SeitentabelleProzeßkontext
001 01 offset Virtuelle Adresse
Page 3
~ ~
~ ~Page 7
~ ~offset
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 26
Seitenverwaltung V – Adreßkonv.: 3-Level Tabellen
SPARC-Architektur (SUN)
14
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 27
Seitenverwaltung VI – Adreßkonv.: 4-Level-Tabellen
MC 68030 Motorola
Problem: 4 von 5 Speicherzugriffen sind overhead
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 28
Seitenverwaltung VII - Adreßkonversion
Problem: Multi-Level-Tabellen sind langsamSPARC: 3-stufig, MC68030 4-stufig (80% länger)und benötigen Tabellenplatz für jeden Prozeß extra.
Lösung. Invertierte Seitentabellen
,
ProzeßId=1virt. reell
0 51 -2 23 -4 75 -
ProzeßId=2virt. reell
0 01 -2 -3 -4 15 3
reell virtuell ProcId0 0 21 4 22 2 13 5 24 - -5 0 16 - -7 4 1
15
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 29
Seitenverwaltung VIII - Adreßkonversion
Problem: Inverse Tabellen sind langsamDurchsuchen der gesamten Tabelle
Lösung. Assoziativer Tabellencache
Assoziativ-speicher
Abfragewort Antwort
ProcId virtuelle reelle Seite1 0 0 0 0 0 01 0 1 0 0 0 10 1 0 0 1 0 21 0 0 1 0 1 30 1 0 0 0 0 50 1 1 0 0 0 7↑ ↑ ↑ ↑ ↑ ↑ ⇓0 1 0 0 0 0 5
X
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 30
Seitenverwaltung IX - Shared Memory
Globale Variablen (Prozeßkommunikation)Gemeinsamer Puffer (Semaphor-geregelter Zugriff)Gemeinsam genutzer Code (C-Bibliothek, ..)
⇒ BS-geregelter Zugriff memory mapping
…
Datenvirt. Seite 5
…Prozeß A
…
RAM-Seite123…
phys. Speicher
…
Datenvirt.Seite 10
…Prozeß B…
Datenvirt. Seite 2
…Prozeß C
frei-geben
16
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 31
Seitenverwaltung X - Unix
HPHP--UX: UX: 32 Bit + 16/32 Bit space register4 Segmente (Quadranten) unterschiedl. Funktionalität
Memory-mapped devices(kernel mode)
4GB I/O map
shared memory
3GB • shared libs• shared mem-mapped files
2GB • user stack• u_area• heap• data
1GB
user program0 GB code
I
II
III
IV
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 32
Seitenverwaltung XI - Windows NT
Windows 2000/XP/Vista/7 : 32 oder 64 Bit
Virtual memory managerfür Seitenverwaltung 4KB-64KB Seiten2-stufige Seitentabellenpage directory/ page table = PFDShared memory Sonderregelung3.Stufe: zentrale prototype page table
Kernel mode Adressierungdurch 30 Bit phys. Adresse
4 GBlocked
3 GB paged
2 GB kernel
user process0 (paged)
17
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 33
Seitenverwaltung XII - Strategien zur Seitenersetzung
Problem: Begrenzter Hauptspeicher. Welche alte Seite soll durch benötigte Seite ersetzt werden? (Scheduling für Seitenaustauschprozessor) Folge von benötigten Seiten: Referenzfolge
Optimale Strategie (Belady 1966)Ersetze die Seite, die am spätesten benutzt werden wirdBeispiel: 0 1 2 3 4 0 1 5 6 0 1 2 3 4 ...
Ziel 0 1 2 3 4 0 1 5 6 0 1RAM1 0 0 0 0 0 0 0 0 0 0 0RAM2 - 1 1 1 1 1 1 1 1 1 1RAM3 - - 2 4 4 6 6
t = 1 2 3 4 5 6 7 8 9 10 11
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 34
Folge 1 2 3 1 4 1 3 2 3 RAM1 1 1 1 1 4 4 4 RAM2 - 2 2 2 2 1 1 1 RAM3 - - 3 3 3 3 3 2
t = 1 2 3 4 5 6 7 8 9
Seitenverwaltung XIII - Strategien zur Seitenersetzung
ProblemProblem: Referenzfolge i.A. nicht bekannt.Ansatz: Statistik notieren pro Seite
Bits R= referenced Reset durch Timer oder EreignisM= modified
FIFO-Strategien: Ersetze die älteste Seitenur älteste Seite ersetzen: Problem mit Hauptseite
18
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 35
Seitenverwaltung XIV - Strategien zur Seitenersetzung
Der clock-AlgorithmusMarkierung im Ringpuffer „letzte Seite“ kreist
Überspringen einer Seite bei R=1 (Second-Chance-Algorithmus)
Älteste Seite
Neue Seite
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 36
Seitenverwaltung XV - Strategien zur Seitenersetzung
Die NRU-Strategie (Not Recently Used)Ersetze die Seite mit geringster Nutzung in einem gemeinsamen ZeitraumMit Prioritätsliste bessere Statistik-Ausnutzung:
1) R = 0, M = 0 wenig Nutzung zuerst ersetzen. Clock-Alg!2) R = 0, M = 1 beschriebene Seite3) R = 1, M = 0 genutzte Seite4) R = 1, M = 1 genutzte beschriebene Seiten zuletzt
Ersetze Seite mit kleinster Nummer (2R+M)
Problem: Geringe Differenzierung (Seiten mit gleichem Status)
Not Frequently Used NFU, Least Frequently Used LFUErsetze die Seite mit geringster BenutzungsfrequenzZeitspanne = Existenzzeit des ProzessesProblem: früher aktuelle Seiten dominieren zu lange, „träges“ Verhalten
Alterungsprozeß einführen! Linux: Einen Zähler pro Seite, bei jeder Referenz hochzählen,
Dekrementieren durch Hintergrundsprozeß
19
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 37
Seitenverwaltung XVI - Strategien zur Seitenersetzung
Die LRU-Strategie (Least Recently Used)Seite mit kleinster Benutzungswahrscheinlichkeit (längste Zeitspanne seit letzter Benutzung) zuerst ersetzen
1 1 0 0 0 → 1 0 0 1 1 1 0 1 Seite A
0 1 1 0 1 → 1 1 0 1 1 0 1 0 Seite B
0 1 0 1 0 → 0 1 0 1 1 0 1 1 Seite C
4 3 2 1 0 –1 –2 –3 –4 –5 –6 –7 –8 Zeitpunkt t
R-Bit
Folge 1 2 3 1 4 1 3 2 3 RAM1 1 1 1 1 1 1 1 1 1 RAM2 - 2 2 2 4 4 2 RAM3 - - 3 3 3 3 3 3 3
t = 1 2 3 4 5 6 7 8 9
Zählen durch Schieberegister: 8 Bit-Zahl ~ Aktualität
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 38
Seitenverwaltung XVII - Seitenmengen: Das working set
Arbeitsmenge (working set) eines ProzessesMinimale Seitenzahl pro Prozeßfenster (Denning 1980)
Mittlere Seitenzahl pro ProzeßBeispiel: Variable A,B,C,D sind auf verschiedenen Seiten
MOVE A,BMOVE C,D
Denning Working set = 5, unabhängig von evtl. zusätzlichen Seiten
LokalitLokalitäätsprinziptsprinzip!Einlagern von nötigen Seiten: demand pagingEinlagern des working set: prepaging
20
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 39
Seitenverwaltung XVIII - Seitenreferenzen: Lokalitätsprinzip
Benutzte SeitenA
usfü
hrun
gsze
itpun
kte
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 40
Folge 1 2 3 1 4 1 3 2 3 RAM1 1 1 1 1 1 1 1 1 1 RAM2 - 2 2 2 4 4 2 RAM3 - - 3 3 3 3 3 3 3
t = 1 2 3 4 5 6 7 8 9
Seitenverwaltung XIX - Strategien zur Seitenersetzung
Die Working Set-StrategieSeite außerhalb des working set-Fensters zuerst ersetzenFenster > Speichergröße
21
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 41
Seitenverwaltung XX - Modellierung und Analyse
Optimale SeitenlängeOptimale SeitenlängeHauptspeichergröße k, SW-Seitengröße s Einstufige Seitentabelle mit k/s Einträgen pro ProzeßDatenlänge ist aus ]0,s] mittl. Verschnitt s/2
mittl. Speicherverlust V = (s/2 + k/s) ≡ k fv
größ. Seiten kleinere Tabellen, mehr Verschnittklein. Seiten größere Tabellen, weniger Verschnitt
∂
∂
V ssopt( )
= 012
02−
=
ksopt
12 2=
ksopt
2kOptimum: Ableitung von V(s) wird null
⇔ ⇔ ⇔ sopt=
und Verlustfaktor fv = 2/sopt
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 42
Seitenverwaltung XXI - Modellierung und Analyse
Weitere KriterienWeitere Kriterien für optimale Seitengröße
große Seiten haben hohen Verschnitt bei geringen zusätzl. Speicheranforderungen (höh. Mittl. Verschnitt)
Zeit, um eine Seite auf den Massenspeicher zu schieben: kleinere Seiten sind schneller geschrieben, aber langsamer gefunden
Speicherverschnitt bei mittl. Dateigröße von 1 kB => nicht zu große Seiten!
Kleine Seitengröße, große Transfermengen => I/O Clustermengen, read ahead
22
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 43
Ziel 3 4 0 1 5 6 0 1 2 3 5 6 3 4 0 1 5 6 0 1 2 3 5 6 Ziel RAM1 0 4 4 4 6 6 6 6 6 6 0 0 0 0 5 5 5 5 3 3 RAM1
RAM2 1 1 0 0 0 0 0 2 2 2 1 1 1 1 1 6 6 6 6 5 RAM2
RAM3 2 2 3 1 1 1 1 1 3 3 2 2 2 2 2 2 0 0 0 0 RAM3
RAM4 3 3 2 2 5 5 5 5 5 5 5 3 3 3 3 3 3 3 1 1 1 1 RAM4
- 4 4 4 4 4 4 4 2 2 2 RAM5
Seitenverwaltung XXII - Modellierung und Analyse
Optimale SeitenzahlOptimale Seitenzahl pro Prozeß ?
Beispiel FIFO 4 vs. 5 Seiten für Referenzfolge
Beladys Anomalie: Mehr Ersetzungen trotz mehr Seiten!
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 44
Seitenverwaltung XXIII - Modellierung und Analyse
Beispiel LFU 4 Seiten vs. 5 SeitenStack-Notation Zeit
RAM 0 1 3 4 0 1 0 1 RAM
RAM 2 3 4 0 1 1 6 0 1 2 3 5 2 3 4 0 1 1 6 0 1 2 3 5 RAMRAM 1 2 3 4 0 0 1 6 0 1 2 3 1 2 3 4 0 0 1 6 0 1 2 3 RAMRAM 0 1 2 3 4 5 5 5 6 0 1 2 0 1 2 3 4 5 5 5 6 0 1 2 RAM
DISK 0 1 2 3 4 4 4 5 6 0 1 0 1 2 3 4 4 4 5 6 0 1 RAM
DISK 2 3 3 3 4 5 6 0 2 3 3 3 4 5 6 0 DISKDISK 2 2 2 3 4 4 4 2 2 2 3 4 4 4 DISK
a) 4 RAM-Seiten b) 5 RAM-Seiten
LFU-Liste mittels Stack-Liste implementierbar unabhängig von der RAM/DISK-Grenze
Keine Anomalie für alle Stack-Algorithmen beweisbar
Häu
figke
it
23
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 45
Seitenverwaltung XXIV - thrashing
Beobachtung: Bei sehr vielen Prozessen läuft plötzlich das Gesamtsystem langsamer, stattdessen starke Plattenaktivität
Erklärung: Wartezeiten kehren sich um CPU PPUn Prozesse, jeder m<k Seiten
Keine Verzögerung>tS tW
Prozeß 1
Prozeß 2
Prozeß 3
tW tSProzeß 1
Prozeß 2
Prozeß 3
thrashing: >
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 46
Seitenverwaltung XXV - Analyse von thrashing
24
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 47
Seitenverwaltung XXVI - Anti-Thrashing Strategien
SpeicherangebotSpeicherangebot muß genügen für working set bei gegebenem Verhältnis Seitenverweilzeit tS
Seitenwechseldauer tT
Page Fault Frequency-Modell PPFWenn Seitenersetzungen pro Zeiteinheit (Seitentauschrate)
> Schwelle, Prozesse stillegen.< Schwelle, Prozesse aktivieren.
(Dynamische Strategie: etwas besser als die statische working-set-Strategie)
Working Set Modellnur so viele Prozesse, wie Speicher für alle working sets fester Größe reicht (z.B. Siemens:BS2000, IBM:CP67)
Programmierungsmaßnahmenlokaler code (inline), lokale Adressreferenzen (z.B. Matrizenmultiplikation) → kleines σT (nötige Seitenzahl)
HardwaremaßnahmenGroße Seiten → großes tS (Festplattenverzögerung!)mehrere parallele swap-Festplatten → kleineres tT
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 48
Seitenverwaltung XXVII - Anti-Thrashing Strategien
PFF-Modell
25
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 49
Seitenverwaltung XXVIII - Anti-Thrashing Strategien
Lazy evaluation Vermeide unnötigen Seitentausch
Copy On WriteSeitenkopie erst durchführen, wenn darauf geschrieben wird
Page Out PoolAuszulagernde Seiten zwischenspeichern (standby)
Globale vs. lokale StrategienSpeicheraufteilung je nach ProzeßgrößeStrategien (PPF, LRU,..) nicht isoliert pro Prozeß, sondern global für alle Seiten aller Prozesse (z.B. PPF gleich für alle Prozesse). Nachteil: Nicht „gerecht“
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 50
Seitenverwaltung XXIX - Seitenverwaltung
ProblemeProbleme
Paging DemonKapselung als idle-Prozeß, z.B. für page out pool
I/O Pages und Shared Pages (besonders wichtige Seiten)
DMA für ausgelagerte Prozesse: Fehler!Gemeinsame Bibliotheken, shared memory: Probleme beim Auslagern!
Page faults und Instruktionsgrenzen
Bei Seitenfehler: Wiederholung des Befehls. Aber wo fing er an? Rekonstruktionszeit nötig bei Microcode.
26
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 51
Seitenverwaltung XXX - Seitenverwaltung
Ablauf eines Page faults :
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 52
Seitenverwaltung XXXI - Unix: Seitenersetzungsstrategien
HP-UX: Swapping vs. Paging
Swapping: schneller Zugriff, z.B. für Prozeßauslagerungz.B. swap disk, swap section einer Platte, swap directory im Dateisystem
Pageout demondesfree < freierSpeicher < 25% des Anwenderspeichers:
periodischer reset des R-Bits, ∆t warten, Auslagern der Seiten mit R=0
swapper demonfreierSpeicher < desfree:
swapper demon desaktiviert Prozesse + sweep out, bis Min. erreicht.Min,Max für Hysterese gegen „Seitenflattern“
27
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 53
Seitenverwaltung XXXII - Windows NT: Seitenersetzungsstrategien
FIFO-Seitenersetzung im NormalfallKeine globale Seitenabstimmung der Prozesse, da
lokales Seitenmanagement pro Prozeß subjektiv gerechter Wenig aufwendigAuslagerung häufig benutzter Seiten gemildert durch page out pool
Automatic Copy on write unnötiges Kopieren verhindern
Neue Prozesse (POSIX): Seiten mit copy on write verhindert Kopieren von Elternseiten für Kinder (Codeüberlagerung)
Dynamic Link Library DLL nur bei write kopiert, sonst nicht.
Automatic workset trimming zu wenig Speicher daAlle Prozesse mit aktueller Seitenzahl (working set) >min verkleinernBei Seitenfehlern wird working set „geclustert“ vergrößert (größere effektive Seitenlänge!)
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 54
Seitenverwaltung XXXIII - Konfigurationsmöglichkeiten
UNIXBei der Installation des Systems wird eine Swap-Partition angelegt, deren Grösse man festlegen kann.Später können weitere Swapbereiche in Form von Partitionen und Files hinzugefügt werden, sogar Swapping über NFS ist möglich.
Windows NT/2000/XP/Vista/7Bei der Installation wird ein gewisser Standard eingestellt, derin der Systemsteuerung abgeändert werden kann, was Größe und Verteilung der Swapbereiche auf die Platten angeht.
28
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 55
Segmentierung I
SegmenteSegmente statt globalem linearem AdressraumProblem: Kollision der Adreßräume bei wachsenden Datenstrukturen
UNIX-Segmente
Oberer Speicher(Heap)
Daten
Programm
Laufzeitsystem
StackArgumente/
Optionen
Compiler-Segmente
Symboltabellen
Quelltext
Tabellen
Parser-Baumstrukturen
Stack
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 56
CPU/MMU
SegmentRegisterDaten B
Code B
DatenBlock 1
DatenBlock 2
Daten ACode A
Stack
ES
Extended-Daten
Segmentierung II
Seitentabelle Segmenttabelle (Segmentregister)Beispiel: Intel 80286
Speicher
CSCode DS
Daten
SSStack
29
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 57
Segmentierung III
Lokale und globale Seitentabellen INTEL 80486
Pro Prozeß: Local Description Table LDTAlle Prozesse: Global Description Table GDT
LDT-Register
LDT
…
…GDT-Register
GDT
…
…
DatenSegment
CodeSegment
CodeSegment
CodeSegment
DatenSegment
Globale Segmente
Prozeß B
LDT CodeSegment
DatenSegment
Prozeß A
CPU
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 58
Cache I
Schneller Speicherzugriff durch schnellen Hilfsspeicher (Cache) bei Lokalitätseigenschaft
Pipeline-burst-Cache Adresse
Daten
Prozessor SpeicherDRAMburst
CACHE
Befehls/Daten-Cache
Adresse Daten
Prozessor
Speicher DRAM
CACHE
30
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 59
Cache II
Konsistenzproblem
LösungenDirektschreiben write through
Zurückschreiben write backAktualisieren copy back mittels snooper (Überwachung)Beispiel: Intel MESI Statuswort für Cachespeicher
Adresse
Read
Daten Write
Prozessor CACHESpeicherDRAM
Ein-/Ausgabe-einheiten
DMA
Betriebssysteme © H. Weber, FH WiesbadenSpeicherverwaltung Folie 60
Speicherschutz I
Virt.Speicher: keine Adressiermöglichkeit des NachbarnZugriffsrechte bei jeder Seite bzw. Segment (UNIX, NT)VM Manager (Windows NT)
Execute onlyGemeinsame Bibliotheken
Guard PageBei Benutzung Signalerzeugung guard page exceptionNo Accessbei nichtex. oder gesperrten Seiten: Debuggingsignal
Copy on WriteSpeicherschutz: Bei Zugriff nur Schreiben auf Kopie
Sicherheitsstufen kernel mode vs. user modez.B. Intel 80386: real mode→virtual mode:user /dll /system /kernelZugriff und Sprünge nur auf Seiten mit größerer/gleicher Statuszahl