Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
SpeicherSpeicher--verwaltungverwaltung
Kap. 4
Version vom 25.02.2005
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 2
Kap. 4 - Inhalt
ÜbersichtDirekte SpeicherbelegungLogische Adressierung und virtueller SpeicherSeitenverwaltungSegmentierungCacheSpeicherschutz
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 3
Übersicht I
Speicher ist neben dem Prozessor das wichtigste BetriebsmittelSpeicherhierarchie
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 4
Übersicht II
Typische Speicherhierarchie mit ZahlenZahlen sind sehr grobe Schätzungen
< 1KB
1 MB
128MB – 8GB
20-250GB
20-100GB
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 5
Übersicht III
EinteilungAnwenderprogrammeinterner Speicher: z.B. Verwaltung des Heaps durch garbage collector
Hauptspeicher Aufteilung auf Prozesse: globaler vs. lokaler Speicher bei Multiprozessorsystemen
Massenspeicher internes Management bei Dateien, z.B. der Swapdatei
StrategienKomplette Speicherbelegung (Prozeß) auslagern (swapping: langsam)
Speicherteile (Prozeßteile) auslagern
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 6
Direkte Speicherbelegung I
Einfache SpeicherbelegungEin Benutzerprogramm ohne Swapping oder Paging
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 7
Direkte Speicherbelegung II
Multiprogramming mit festen Partitionen
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 8
Direkte Speicherbelegung III
CPU Benutzung als Funktion der Zahl der Prozesse im SpeicherDegree of multiprogramming
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 9
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 10
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 11
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 12
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 13
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!)
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 14
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 15
Direkte Speicherbelegung VIII - Swapping
Speicherallokation ändert sich, wenn – Prozesse in den Speicher eingelagert werden
– den Speicher verlassen
Schattierte Flächen sind ungenutzter Speicher
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 16
Direkte Speicherbelegung IX - Swapping
• Platz für wachsendes Datensegment allokieren
• Platz für wachsendes Stack- und Datensegmentallokieren
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 17
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 18
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 19
Virtueller Speicher III – Funktion und Position der MMU
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 20
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 21
Seitenverwaltung I - Seitentabellen
Relation zwischenvirtuellen Adressenund physischen Speicheradressen wird durch die Seitentabelle beschrieben
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 22
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 23
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 !
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 24
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 25
Seitenverwaltung V – Adreßkonv.: 3-Level Tabellen
SPARC-Architektur (SUN)
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 26
Seitenverwaltung VI – Adreßkonv.: 4-Level-Tabellen
MC 68030 Motorola
Problem: 4 von 5 Speicherzugriffen sind overhead
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 27
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 28
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 29
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 30
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 31
Seitenverwaltung XI - Windows NT
Win2000: 32 Bit64 Bit vorgesehen
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)
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 32
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 33
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 34
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 35
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ß
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 36
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 37
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 38
Seitenverwaltung XVIII - Seitenreferenzen: Lokalitätsprinzip
Benutzte Seiten
Aus
führ
ungs
zeitp
unkt
e
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 39
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 40
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 41
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/OClustermengen, read ahead
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 42
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 43
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 44
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>t S tW
Prozeß 1
Prozeß 2
Prozeß 3
tW tSProzeß 1
Prozeß 2
Prozeß 3
thrashing: >
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 45
Seitenverwaltung XXV - Analyse von thrashing
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 46
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 47
Seitenverwaltung XXVII - Anti-Thrashing Strategien
PPF-Modell
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 48
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 49
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.
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 50
Seitenverwaltung XXX - Seitenverwaltung
Ablauf eines Page faults :
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 51
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“
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 52
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 53
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/XPBei 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.
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 54
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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 55
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 56
Segmentierung III
Lokale und globale Seitentabellen INTEL 80486Pro 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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 57
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
Betriebssysteme und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 58
Cache II
Konsistenzproblem
LösungenDirektschreiben write throughZurü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 und Grundlagen verteilter Systeme: © H. Weber, FH WiesbadenSpeicherverwaltung Folie 59
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