Modul: B-BS Betriebssysteme SS 2011 Prof. Dr. Rüdiger Brause Adaptive Systemarchitektur Institut für Informatik Fachbereich Informatik und Mathematik

Modul: B-BSBetriebssystemeSS 2011

Prof. Dr. Rüdiger BrauseAdaptive SystemarchitekturInstitut für InformatikFachbereich Informatik und Mathematik (12)

Speicher-verwaltung

Betriebssysteme: © R.Brause, J.W.G-Universität Frankfurt a.M. Folie 2Speicherverwaltung

Thrashing

Speicherorganisation

Virtueller Speicher

Seitenersetzung

Segmentierung, Caching


Speicherverwaltung :

Einteilung Anwenderprogrammeinterner Speicher: garbage collector

Hauptspeicher Aufteilung auf Prozesse: globaler vs. Lokaler Speicher

Massenspeicher internes Management bei Dateien (DBMS)

StrategienFrüher: Komplette Speicherbelegung (Prozeß) auslagern (swapping: langsam)

Jetzt: Speicherteile (Prozeßteile) auslagern



Zuordnung durch feste TabellenTabelleneinheit (z.B. 1Bit) gibt Zustand einer Speichereinheit (z.B. 32Bit-Wort) 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


A.len = 3A.start = 7


Zuordnung durch verzeigerte Listen

Speicherbelegung Liste der Belegung

98 A76543 C21 B0

FREI.len = 2FREI.start = 5

C.len = 3C.start = 2

B.len = 2B.start = 0

Anfang

FREI


Speicherorganisation: 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. Aber: winzige, unbrauchbare Reststücke

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



Bewertung der Belegungsstrategien

FirstFit > NextFit, WorstFit, BestFit

ex. Kenntnisse über Speicheranforderungen: QuickFit

Leistungsfähigkeit der buddy-Systeme:

mittl. Anforderung = ?tats. Belegung

Überschlagsrechnung !



Bewertung der Belegungsstrategien

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: © R.Brause, J.W.G-Universität Frankfurt a.M. Folie 9

Frage

Angenommen, Sie haben sowohl einige unregelmäßige Speicheranfragen als auch viele gleicher, vorher bekannter Größe.

Welche Strategie implementieren Sie?

Antwort:

Hier ist eine Mischstrategie sinnvoll, also sowohl eine Qickfit-Verwaltung als auch ein FirstFit-Verwaltung.

Speicherverwaltung



Fragmentierung und Verschnitt

Interner Verschnitt Interne Zersplitterung durch Heap-BelegungAbhilfe: garbage collector des Programmiersystems

Externer VerschnittFreier Platz zwischen den Programmen im AuslagerungsbereichAbhilfen:

zuerst Einlagern großer Prozesse, dann Auffüllen mit kleinen.

swapping kleiner Programme (gegen SJF-Strategie!) Speicheraufteilung in verschieden große Bereiche, jeder mit eigener

Warteschlange (IBM OS/MFT): ineffizient! Zusammenschieben des Speichers: zeitaufwändig!


Thrashing


Virtueller Speicher

Seitenersetzung



Virtueller Speicher - Wozu?

Probleme & FixesSpeicherzusatzbelegung von Programmen

Unix: Prozeß auslagern, neuen Speicher reservieren, neu einlagern Externen Verschnitt zum Prozeß dazuschlagen (stack & heap)

Relozierung von Programmcode rel. Adressen für GOTO bei allen CPU-Typen (!?) bei Einlagerung oder zur Laufzeit absolute Adr. errechnen

Speicherschutz vor Programmen Betriebssystemkern darf nicht korrumpiert werden (fences,limits),

spezielle HW-Einheit Programmiermodell soll klar, einfach und uniform sein

(Fehlervermeidung)


Forderung: lineares Programmiermodell

Fragmente sollen zusammenhängend erscheinen

Bei Speicheranforderung werden nur inaktive Programmteile ausgelagert

Implementierung durch Memory Management Unit MMU

Virtueller Speicher

Beliebig langer, Fragmentierter,

durchgehender virt. Speicher

endlicher, physikalischer Speicher

¥...

10000

...

9000

8FFF...

8000

7FFF

...0000

13000

...

C000

B8FF...

A900

A783

...2784


Grundmodell virtueller Adreßkonversion

Virtuelle Adresse

6

Seitentabelle

7 Basisadresse 76 Basisadresse 65 Basisadresse 54 Basisadresse 43 Basisadresse 32 Basisadresse 21 Basisadresse 10 Basisadresse 0

Basisadresse 6 offset

PageNr offset

HSB LSB1 1 0

3 Bit

Hauptspeicherbelegung

~ ~

~ ~

~ ~Page 7

Page 6Seiten-rahmenBasisadr.

ex. nicht: page fault interrupt ! Suchen und Einlagern der benötigten Seite

Prozeßkontext

Physikal. Adresse


Adreßkonversion

Problem: virt. Adreßraum >> phys.AdreßraumRiesige Seitentabellen!

Seitentabelle bei Seitengröße = offset = 12 Bit 4KB Seitenrahmen (page frame) Wortgröße Tabellengröße16 Bit: 4 Bit 16 Einträge32 Bit: 20 Bit 1 Mill. Einträge64 Bit: 52 Bit 4 1015 Einträge

Fix: AdreßbegrenzungVorteil: kleiner Adreßraum, z.B. 30 Bit (1 GB) 18 Bit 256 KB Tabelle, aber auch bei 50KB-Prozeß!

Nachteil: Vergeudung von Platz, da meist nicht benötigt !


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

Seitentabelle

Prozeßkontext

001 01 offset Virtuelle Adresse

Page 3

~ ~

~ ~Page 7

~ ~offset

Linux: 10 Bit 10 Bit 12 Bit-Seite

Linux: 1 MB Tabellen, 1 KB Tabelle jeweils 4KB 4GB Speicher


Adreßkonversion: 3-Level Tabellen

SPARC-Architektur (SUN)

0

0

0 0


Frage

Angenommen, bei jedem Zugriff muss die virtuelle Adresse durch eine 3-level-Tabelle in eine physikalische Adresse übersetzt werden. Wieviel Leseschritte müssen mit der virtuellen Adresse

durchgeführt werden, um schließlich das gewünschte Datum lesen zu können?

Wie viele Verzögerungstakte erfährt also der Zugriff?

Antwort Dekodieren der virtuellen Adresse: Auslesen der 1.Level-Tabelle: 1. Schritt Auslesen der 2.Level-Tabelle: 2. Schritt Auslesen der 3.Level-Tabelle: 3. Schritt Auslesen der physikalischen Adresse: 4. Schritt 3 von 4 Lesezugriffen sind overhead, also nur ¼ Leistung!

Speicherverwaltung


Adreßkonversion: 4-Level-Tabellen

MC 68030 Motorola

Problem: 4 von 5 Speicherzugriffen sind overhead


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 SeitentabellenNimm nur die erfolgreichen Zugriffe.

,

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


Adreßkonversion

Problem: Inverse Tabellen sind langsamDurchsuchen der gesamten Tabelle

Lösung: Assoziativer Tabellencache TLB

Antwortß

Assoziativ-

speicher

Abfragewort

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

Translation Lookaside Buffer TLB


Assoziativspeicher

Realisierung eines CAM

Anfrage

Hit


Virtueller Speicher: Unix

Linux:

32 Bit, 0-3GB in user mode

stack wächst nach unten, heap nach oben (malloc)

Kernel nur in kernel mode zugreifbar,abgebildet auf 0-1GB phys. Adr.

Memory-mapped devices(I/O map im kernel mode)

4GBI/O map

kernel3GB

• shared libs2GB

user stack

• u_area

• heap

• data1GB

user program

0 GB code


Virtueller Speicher: Windows NT

Version 5,5.1 (Win2000/XP): 32 Bit(nicht 64 Bit Windows XP - X64/Vista)

Virtual memory managerfür Seitenverwaltung 4KB-64KB Seiten

2-stufige Seitentabellenpage directory/ page table = PFD

Shared memory Sonderregelung3.Stufe: zentrale prototype page table

Kernel mode Adressierungdurch 30 Bit phys. Adresse, Start bei 0.

4 GBlocked

3 GB paged

2 GB kernel

user process0 (paged)



Verwaltung physikal. Seiten

Page Frame Database PFD: Pro frame ein Eintrag

Statusbits• Valid normal benutzt• Free frei• Zeroed frei+initialisiert (C2)• Standby noch verfügbar• Modified noch verfügbar + beschrieben• Badphys. fehlerhaft



Modified Standby

Free

In Use

Seitenpool

Zustandsübergängeder Seiten

C2-Sicherheit



Struktur zur Verwaltung der Zustände der Seiten

VM status bitsTabelleneintrag

PM statusPhys. Seiten


Shared Memory – wozu, wie

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



Shared memory Organisation

Erzeugen eines section-Objekts mit Attribute: max. Größe, Schutz, paged ?, Adreßbeginn = ?

Methoden:

Erzeugen, Öffnen, Ausweiten, Ausschnitt wählen, Status r/w



Problem: shared virtual memory pages

Page frameaddress

„normale“ Adressübersetzung

Prototype PTEaddress

Prozeß-unabhängi

ge Tafel



Verwaltung der Zustände der shared memory-Seiten


Thrashing


Virtueller Speicher

Seitenersetzung



Seitenersetzung

page- fault-Aktionen des Betriebssystem

Auswahl einer alten Seite

Lesen der gesuchten Seite vom Massenspeicher

Überschreiben (Ersetzen) der alten Seite mit der gesuchten Seite

Aktualisierung der Seiten-Tabelle mit der neuen Seitenadresse

Aufsetzen des Prozeß-PC auf die Adresse des page-fault auslösenden Maschinenbefehls

Übergabe der Kontrolle an den Benutzerprozeß

Erneutes Abarbeiten der Adressreferenz

Seitenauswahl – wie?


Ziel 1 2 3 1 4 1 3 2 3 RAM1 1 1 1 1 1 1 1 2 RAM2 - 2 2 2 4 4 4 4 RAM3 - - 3 3 3 3 3 3 3

t = 1 2 3 4 5 6 7 8 9

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: 1 2 3 1 4 1 3 2 3 4 ...

page fault-Interrupts


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


Problem: Referenzfolge i.A. nicht bekannt.Ansatz: Statistik notieren pro Seite

Bits R= referenced Reset durch Timer oder Ereignis M= modified

FIFO-Strategien: Ersetze die älteste Seitenur älteste Seite ersetzen: Problem mit Hauptseite

Beispiel: 1 2 3 1 4 1 3 2 3 4 ...



Der clock-Algorithmus

Markierung im Ringpuffer „älteste Seite“ kreist und zeigt auf

auszulagernde Seite

Überspringen einer Seite bei R = 1 (Second-Chance-Algorithmus)

Älteste Seite

Neue Seite



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 wenigste 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 (LFU)Ersetze die Seite mit geringster Benutzungsfrequenz bzw. -dauer in einerZeitspanne, z.B. Existenzzeit des Prozesses

Problem: 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ß



Die LRU-Strategie (Least Recently Used)Seite mit kleinster Benutzungswahrscheinlichkeit (längste Zeitspanne seit letzter Benutzung) zuerst ersetzenBeispiel: 1 2 3 1 4 1 3 2 3 4 ...

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


Arbeitsmenge (working set) eines Prozesses

Minimale Seitenzahl pro Prozessfenster (Denning 1980)

Beispiel: Variable A,B,C,D sind auf verschiedenen SeitenMOVE A,BMOVE C,D

Denning Working set = 5, unabhängig von evtl. zusätzlichen Seiten

Mittlere Seitenzahl pro Prozess

Methoden: demand paging: Einlagern von benötigten Seiten prepaging: Vorheriges Einlagern des working set

Prozessfenster

Seitenmengen: Das working set

Voraussetzung: Lokalitätsprinzip!


Seitenreferenzen: Lokalitätsprinzip

Benutzte Seiten

Aus

führ

ungs

zeitp

unkt

e

Einzelseiten sind zeitlich konstant!



Die Working Set-StrategieSeite außerhalb des working set-Fensters zuerst ersetzenFenster > SpeichergrößeBeispiel: 1 2 3 1 4 1 3 2 3 4 ...

„ ‚

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


Frage

Bei der working set-Strategie liegt eine Definition für

„working set“ zugrunde. Welche?

a) Minimale Seitenzahl pro Prozessfenster (Denning)

b) Mittlere Seitenzahl pro Prozess

Speicherverwaltung


Modellierung und Analyse

Optimale SeitenlängeHauptspeichergröße k gegeben. Opt.Seitengröße sopt ~ k ?

Sei einstufige Seitentabelle mit k/s Einträgen pro Prozeß ex.

Datenlänge ist aus ]0,s] mittl. Verschnitt s/2

mittl. Speicherverlust V(s) = (s/2 + k/s)

größ. Seiten kleinere Tabellen, aber mehr Verschnittklein. Seiten größere Tabellen, aber weniger Verschnitt

V s

sopt( )

01

202

k

sopt

1

2 2k

sopt

2k

Ableitung von Verlust V(s) wird null

sopt=

Optimum: (kurze Rechnung)



Weitere Kriterien für optimale Seitengröße:

geringe zusätzl. Speicheranforderungen von stack oder heap: große Seiten haben hohen Verschnitt

die Zeit, um eine Seite auf den Massenspeicher zu schieben: kleinere Seiten haben rel. höh. I/O overhead

der Speicherverschnitt bei s > mittl. Dateigröße (1 KB ??)=> nicht zu große Seiten! (aber: heutige mittl. Dateigröße?)

Also: Kleine Seitengröße, große Transfermengen => I/O Clustermengen bilden, read ahead nutzen


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


Optimale Seitenzahl pro Prozeß ?

Beispiel FIFO 4 vs. 5 Seiten für Referenzfolge

Beladys Anomalie: Mehr Ersetzungen trotz mehr Seiten!



Beispiel LRU 4 Seiten vs. 5 Seiten

Stack-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 RAM

RAM 1 2 3 4 0 0 1 6 0 1 2 3 1 2 3 4 0 0 1 6 0 1 2 3 RAM

RAM 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 DISK

DISK 2 2 2 3 4 4 4 2 2 2 3 4 4 4 DISK

a) 4 RAM-Seiten b) 5 RAM-Seiten

LRU-Prioliste: Letzte genutzte Seite an den Anfang

LRU-Ersetzungsliste mittels Stack-Liste implementierbar unabhängig von der RAM/DISK-Grenze

Keine Anomalie für alle Stack-Algorithmen (LRU, LFU) beweisbar

Gen

utzt

vor

Zei

tein

heite

n


Thrashing


Virtueller Speicher

Seitenersetzung



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 mit k < m Seiten

Keine Verzögerung: tS > tw > tS tW

Prozeß 1

Prozeß 2

Prozeß 3

tW tSProzeß 1

Prozeß 2

Prozeß 3

thrashing: tS < tw

>


Modellmenge M2(ausgelagerte Seiten)

Modellmenge M (Working set)

Analyse von thrashing

Modellierung Anordnung der Seiten nach Referenzhäufigkeit.

Referenzwahrscheinlichkeit pi der Seite i:

1

pi

pc

p1

p2

1 iM m Seitenindex i

p(i) beobachtet

Mittl. p(i)



Rechnung Seitenaustauschgrad = Funktion (Speicherangebot )

1() = 2() =



Visualisierung Abhängigkeit Seitenaustauschgrad vom Speicherangebot

Reduzierungvon M1 im Modell

Reduzierung vonM1+M2 im Modell

r2

r1

alle Seitengleich wahrscheinlich

r

1

rT

beobachtet 1 rel. Speicherangebot s

Sei

tena

usta

usch

grad

sT



RechnungNormalbetrieb vs. thrashing

Beispiele rel. Bearbeitungsdauer G(n)

Fälle W > T

W < T



Systemverhalten bei rT<rW also s T >sW

(A) Linearer Bereich(B) Thrashing - Bereich

i/o zu langsamBeispielrechnung

Nichtlineare Auslastung bei geringem Seitenwechsel

201816141210

86420

0 1 2 3 4 n 0 5 n

G C

G D

G E

12 10 8 6 4 2 0

0 1 2 3 4 n0 5 6 n Prozeßzahl

GA

Ges

amtb

earb

eitu

ngsd

auer

GB

Systemverhalten bei rT>rW also s T <sW

(C) Linearer Bereich(D) Thrashing - Bereich

(E) Starkes Thrashing working set zu grossBeispielrechnung Nichtlineare Auslastung bei hohem Seitenwechsel


Anti-Thrashing Strategien

Speicherangebot muß genügen für working set bei gegebenem Verhältnis w= Seitenverweilzeit tS

Seitenwechseldauer tT

Page Fault Frequency-Modell PFFWenn 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ßnahmen lokaler 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



Das Nutzungsgradmodell

L(n,t) = w1CPU + w2PPU Nutzungsgrad

Adaptive Regelung der Auslastungen Messe L(n,t) und entscheide:

Abfallen von L(.) aktiviere ProzesseAnsteigen von L(.) deaktiviere Prozesse

CPU PPU



Lazy evaluation Vermeide unnötigen Seitentausch

Copy On WriteSeitenkopie erst durchführen, wenn darauf geschrieben wird

Page Out PoolAuszulagernde Seiten zwischen-speichern (standby)

Globale vs. lokale Strategien Initiale Speicheraufteilung je nach Prozessgröße, lokale Seitenersetzungsstrategie.

Strategien (LRU, ...) nicht isoliert pro Prozess, sondern global

für alle Seiten aller Prozesse (z.B. PFF gleich für alle Prozesse).

Nachteil: Als „nicht gerecht“ empfunden


Seitenpool

Windows NT: page out pool

Modified Standby

Free

In Use

Zustandsübergängeder Seiten


Andere Seitenprobleme

Probleme

Aufsetzen: Page faults und InstruktionsgrenzenBei Seitenfehler: Wiederholung des Befehls. Aber wo fing er an? Rekonstruktionszeit nötig bei Microcode.

Verstreute Optimierungsmethoden: Paging DemonKapselung als idle-Prozeß, z.B. für page out pool

Verbotene Auslagerung: I/O Pages und Shared Pages DMA

für ausgelagerte Prozesse: Fehler!Gemeinsame Bibliotheken, shared memory: Probleme beim Auslagern!


Unix: Seitenersetzungsstrategien

HP-UX: Swapping vs. Paging

Swapping: schneller Zugriff, z.B. für Prozeßauslagerungz.B. extra swap disk, swap section einer Platte, swap directory im Dateisystem

swapper demonfreierSpeicher < desfree:swapper demon desaktiviert Prozesse + sweep out, bis Min. erreicht.Min,Max für Hysterese gegen „Seitenflattern“

Hintergrundprozesse Pageout demon

desfree < freierSpeicher < 25% des Anwenderspeichers:periodischer reset des R-Bits, t warten, Auslagern der Seiten mit R=0


Windows NT: Seitenersetzungsstrategien

FIFO-Seitenersetzung im NormalfallKeine globale Seitenabstimmung der Prozesse, da

lokales Seitenmanagement pro Prozeß subjektiv gerechter Wenig aufwendig Auslagerung häufig benutzter Seiten gemildert durch page out pool

Automatic Copy on write unnötiges Kopieren verhindern Neue Prozesse (POSIX): copy on write für Daten-Seiten verhindert

Kopieren von Elternseiten für Kinder (z.B. Code+Daten)

Dynamic Link Library DLL nur bei write für Daten kopiert, sonst nicht.

Automatic workset trimming zu wenig Speicher da Alle Prozesse mit aktueller Seitenzahl (working set) >min verkleinern Bei Seitenfehlern wird working set „geclustert“ vergrößert (größere

effektive Seitenlänge!)


Thrashing


Virtueller Speicher

Seitenersetzung



CPU/MMU

SegmentRegisterDaten B

Code B

DatenBlock 1

DatenBlock 2

Daten A

Code A

Stack

ES

Extended-Daten

Segmentverwaltung

Problem Speicherfragmentierung ?Segmentregister: Seitentabelle Segmenttabelle

Beispiel: Intel 80286

Speicher

CSCode DS

Daten

SSStack


Segmentierung

Segmente 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


Segementverwaltung

Lokale und globale Seitentabellen INTEL 80486 Pro Prozeß: Local Description Table LDT Alle 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


Cache

Beispiel: AMD Opteron 64 Bit, L1 und L2 Cache


Cache

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


Cache

Konsistenzproblem

Alte Daten Neue Daten

Lösungen CPU schreibt zurück write through Cache schreibt zurück write back Aktualisieren copy back mittels snooper bei M=1

Beispiel: Intel MESI Statuswort pro Cachezelle,parallele Cache-Validierung durch alle snooper

Adresse

Read

Daten Write

Prozessor CACHESpeicherDRAM

Ein-/Ausgabe-

einheiten

DMA


Speicherschutz

Virt.Speicher: keine Adressiermöglichkeit des Nachbarn

Zugriffsrechte bei jeder Seite bzw. Segment (UNIX, NT)

VM Manager (Windows NT)

Execute onlyGemeinsame Bibliotheken

Guard PageBei Benutzung Signalerzeugung guard page exception

No Accessbei nichtex. oder gesperrten Seiten: Debuggingsignal

Copy on WriteSpeicherschutz: Bei Zugriff nur Schreiben auf Kopie


Speicherschutz

CPU-Sicherheitsstufen kernel mode vs. user modez.B. Intel 80386: real mode virtual mode

Real modedirekter phys. Speicherzugriff, keine MMU

Virtual mode nicht rücksetzbar

Stufe 3: User

Stufe 2: shared libs

Stufe 1: system calls

Stufe 0: Kernel („Ring0-Mode“)

Zugriff und Sprünge nur auf Seiten mit größerer/gleicher Statuszahl,

kontrollierter Aufruf von kleinerem Status.

Documents

Modul: B-BS Betriebssysteme SS 2011 Prof. Dr. Rüdiger Brause Adaptive Systemarchitektur Institut für Informatik Fachbereich Informatik und Mathematik