Modul: B-BS, BS1, M-SIW-S1A, M-SIW-S1B, M-WR-IDSA, M-WR-IDSB Betriebssysteme WS 2015 Prof. Dr. Rüdiger Brause Adaptive Systemarchitektur Institut für

Modul: B-BS, BS1, M-SIW-S1A, M-SIW-S1B, M-WR-IDSA, M-WR-IDSB

BetriebssystemeWS 2015

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 SpeicherSeitenersetzung

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


SpeicherorganisationZuordnung 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

SpeicherorganisationZuordnung 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: BelegungsstrategienFirstFitNimm 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.Schnelles Verschmelzen mit jeweils dem Partnerstück bei gleichem Adressenanfang: 0xxx + 1xxx Xxxx

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

Speicherorganisation; Buddy-System

Beispiel

Speicherverwaltung

1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

x x x

0 x x

Anforderung: 3 Einheiten

Zugeteilt: 4 = 22 Einheiten 0xx


Speicherorganisation; Buddy-System

Beispiel

Speicherverwaltung

1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

1 x x

0 x x

Anforderung: 3 Einheiten

Zugeteilt: 4 = 22 Einheiten 0xx

Freigabe: 0xx - Stück

Verschmelzen: 0xx mit 1xx- Buddy zu Xxx - Stück

Unbenutzt: 1xx - Stückx x x


4kB

16kB

Buddy-System: Beispiel

Anforderungsreihenfolge 80KiB, 8KiB, 9KiB, 3KiB, 50KiB

Aufbau einer Baumstruktur für 256 KiB Speicher

Speicherverwaltung

256KiB

128KiB

64KiB

32KiB 32KiB

9+7KiB

3+1KiB 4KiB

16KiB

8KiB 8KiB

128kB

64kB64KiB =50+14KiB

128KiB =80KiB+48KiB


SpeicherorganisationBewertung der Belegungsstrategien

FirstFit > NextFit, WorstFit, BestFit

ex. Kenntnisse über Speicheranforderungen: QuickFit

Leistungsfähigkeit der buddy-Systeme:

mittl. Anforderung = ?tats. Belegung

Überschlagsrechnung !


SpeicherorganisationBewertung 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!)


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 VerschnittInterner 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 - 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 ProgrammiermodellFragmente sollen zusammenhängend erscheinenBei Speicheranforderung werden nur inaktive Programmteile ausgelagert

Implementierung durch Memory Management Unit MMU

Virtueller Speicher

Beliebig langer, Fragmentierter,

durchgehender virt. Speicher endlicher,

physikalischer Speicher

¥...

10000

...

90008FFF

...

80007FFF

...0000

13000

...

C000

B8FF...

A900

A783

...2784


Grundmodell virtueller AdreßkonversionVirtuelle 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ßkonversionProblem: virt. Adreßraum >> phys.Adreßraum

Riesige Seitentabellen! Seitentabelle bei Seitengröße = offset = 12 Bit 4KiB 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 KiB Tabelle, aber auch bei 50KiB-Prozeß!

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


AdreßkonversionMulti-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

Linux: 10 Bit 10 Bit 12 Bit-Seite

Linux: 1 MiB Tabellen, 1 KiB Tabelle jeweils 4iKB 4GiB Speicher


Adreßkonversion: 3-Level TabellenSPARC-Architektur (SUN)

00

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-TabellenMC 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 Seitentabellen, geordnet nach reell. Seiten

Nimm 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ßkonversionProblem: Inverse Tabellen sind langsam

Durchsuchen 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: UnixLinux:

32 Bit, 0-3GiB 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)

4GiB I/O map

kernel3GiB

• shared libs2GiB

user stack

• u_area• heap

• data1GiB

user program

0 GiB 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 4KiB-64KiB Seiten2-stufige Seitentabellenpage directory/ page table = PFDShared memory Sonderregelung3.Stufe: zentrale prototype page table

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

4 GiBlocked

3 GiB paged

2 GiB 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


Virtueller Speicher: Windows NTStruktur 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


Virtueller Speicher: Windows NTVerwaltung der Zustände der shared memory-Seiten


Thrashing





Seitenersetzung

page- fault-Aktionen des BetriebssystemAuswahl einer alten SeiteLesen der gesuchten Seite vom MassenspeicherÜberschreiben (Ersetzen) der alten Seite mit der gesuchten SeiteAktualisierung der Seiten-Tabelle mit der neuen SeitenadresseAufsetzen 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 SeitenersetzungProblem: 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

Problem: Referenzfolge i.A. nicht bekannt.


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

Strategien zur Seitenersetzung

FIFO-Strategie: Ersetze die älteste Seite

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


Strategien zur SeitenersetzungProblem: Wenn älteste Seite ersetzt, immer zuerst die Hauptseite.Ansatz: Statistik notieren pro Seite

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

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

Der clock-Algorithmus Markierung im Ringpuffer „älteste Seite“

kreist, und zeigt auf auszulagernde Seite. (Effiziente Implementierung

von second chance)

Älteste Seite

Neue Seite


Strategien zur SeitenersetzungDie LRU-Strategie (Least Recently Used)Seite mit geringster Benutzung (größter Zeitdauer seit letztem Benutzen) 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

Messen durch Shift des R-Bits in einer Zahl pro Seite: 8 Bit-Zahl ~ Aktualität pro Seite


Strategien zur SeitenersetzungDie NRU-Strategie (Not Recently Used)Ersetze die Seite mit geringster Nutzung in einem gemeinsamen Zeitraum, etwa der Existenzzeit des Prozesses oder periodischer Resetzeit.

Mit einer Prioritätsliste gibt es bessere Statistik-Ausnutzung:0) R = 0, M = 0 wenigste Nutzung zuerst ersetzen. Clock-Alg!1) R = 0, M = 1 beschriebene Seite2) R = 1, M = 0 genutzte Seite3) R = 1, M = 1 genutzte beschriebene Seiten zuletzt

Ersetze Seite mit kleinster Nummer (2R+M)Problem: Geringe Differenzierung (Viele Seiten mit

gleichem Status), nur 4 Benutzungsfrequenzen


Strategien zur Seitenersetzung

Not Frequently Used (NFU), Least Frequently Used (LFU)

Ersetze die Seite mit geringster Benutzungsanzahl bzw. -dauer in einer Zeitspanne. Dies entspricht der NRU, aber mit mehr möglichen Zuständen, also einem feiner abgestuften Verhalten.

Problem: früher aktuelle Seiten dominieren zu lange, „träges“ Verhalten.

Alterungsprozeß einführen!

z.B. Linux: Einen Zähler pro Seite, bei jeder Referenz hochzählen,

Dekrementieren (altern) durch Hintergrundprozeß


Die 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 für working set: demand paging: Einlagern von benötigten Seiten prepaging: Vorheriges Einlagern des working set

Prozessfenster

Seitenmengen: Das working set


Strategien zur SeitenersetzungDie 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

Voraussetzung: Lokalitätsprinzip!


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


Seitenreferenzen: LokalitätsprinzipBenutzte Seiten

Aus

führ

ungs

zeitp

unkt

e

Einzelseiten sind zeitlich konstant!


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

Modellierung und AnalyseOptimale Seitenzahl pro Prozeß ?Beispiel FIFO 4 vs. 5 Seiten für Referenzfolge

Beladys Anomalie: Mehr Ersetzungen trotz mehr Seiten!


Modellierung und AnalyseBeispiel 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


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 ssopt( )

012

02

ksopt

12 2

ksopt

2k

Ableitung von Verlust V(s) wird null

sopt=

Optimum: (kurze Rechnung)


Modellierung und Analyse

Weitere Kriterien für optimale Seitengröße:

geringe zusätzl. Speicheranforderungen von stack oder heap: große Seiten haben hohen Verschnittdie 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


Thrashing





Thrashing Beobachtung: Bei sehr vielen Prozessen läuft plötzlich das

Gesamtsystem langsamer, stattdessen starke PlattenaktivitätErklärung: Wartezeiten kehren sich um CPU PPU

n Prozesse, jeder mit k < m Seiten

Keine Verzögerung: CPU-Zeit tS > tw Seitenwechselzeit > tS tW

Prozeß 1

Prozeß 2

Prozeß 3

tW tSProzeß 1

Prozeß 2

Prozeß 3

thrashing: tS < tw >


Anti-Thrashing StrategienSpeicherangebot muß genügen für working set bei gegebenem Verhältnis w= Seitenverweilzeit tS(gegebener Zeitscheibe und I/O DMA) 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


Anti-Thrashing Strategien

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


Anti-Thrashing Strategien

Lazy evaluation Vermeide unnötigen Seitentausch

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

Page Out PoolAuszulagernde Seiten zwischen-speichern (standby)

Lokale vs. globale 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 SeitenproblemeProbleme

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 demon freierSpeicher < desfree: swapper demon desaktiviert Prozesse + sweep out, bis desfree erreicht.System V: Min, Max-Markierungen für Hysterese gegen

Seitenoszillation (Seitenflattern)Linux: Auslagern der Seite, wenn 8 Bit-Seitenzähler null erreicht

Strategien der 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 POSIX: Neue Prozesse: copy on write für Daten-Seiten verhindert

Kopieren von Elternseiten für Kinder (z.B. Code+Daten) NT: 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





CPU/MMU

SegmentRegisterDaten B

Code B

DatenBlock 1

DatenBlock 2

Daten A

Code A

Stack

ES

Extended-Daten

SegmentverwaltungProblem Speicherfragmentierung ?Segmentregister: Seitentabelle Segmenttabelle

Beispiel: Intel 80286

Speicher

CSCode DS

Daten

SSStack


SegmentierungSegmente 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


Segmentverwaltung

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

Jedes Segment hat aber eine virtuelle Speicherverwaltung!


Cache-Hierarchie bei CPU

Beispiel: AMD Opteron 64 Bit, L1 und L2 Cache


Cache-Architektur

Schneller Speicherzugriff durch schnellen Hilfsspeicher (Cache) bei Lokalitätseigenschaft

Pipeline-burst-Cache (klein) Adresse

Daten

Prozessor SpeicherDRAMburst

CACHE

Befehls/Daten-Cache (groß)

Adresse Daten

Prozessor

Speicher DRAM

CACHE


Cache ProblemeKonsistenzproblem

Alte Daten Neue Daten

Lösungen CPU schreibt zurück write through (langsam) Cache schreibt zurück write back (HW nötig) Aktualisieren copy back mittels HW-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

Virtueller Speicher: keine Adressiermöglichkeit des Nachbarn

Memory curtaining: spezielle HW-geschützte Speicheradressen

Sealed Storage: HW-Kontext (HASH-Wert) geht in Kodierung ein

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

VM Manager (Windows NT) Execute onlyFür Code und gemeinsame Bibliotheken (NX-pool !)

Guard PageBei Benutzung Signalerzeugung guard page exception

No Accessbei nichtex. oder gesperrten Seiten: Debuggingsignal

Copy on WriteSpeicherschutz: Bei Zugriff nur Schreiben auf Kopie


Ring 3

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

Real modedirekter phys. Speicherzugriff, keine MMU

Virtual mode nicht rücksetzbarStufe 3: UserStufe 2: shared libsStufe 1: system callsStufe 0: Kernel („Ring 0-Mode“)

Zugriff und Sprünge nur auf Seiten mit größerer/gleicher Statuszahl,kontrollierter Aufruf von kleinerem Status.

Ring 2

Ring 1

Speicherverwaltung

Speicherschutz

Ring 0

Documents

Modul: B-BS, BS1, M-SIW-S1A, M-SIW-S1B, M-WR-IDSA, M-WR-IDSB Betriebssysteme WS 2015 Prof. Dr. Rüdiger Brause Adaptive Systemarchitektur Institut für