OS V15 Virtuelle Speicher - inf.fu-berlin.de · Als das Konzept des virtuellen Speichers von Fortheringham vorgeschlagen worden ist. 4. M. Esponda-Argüero Virtueller Speicher Die

M. Esponda-Argüero

Virtueller Speicher

WS 2011/2012

1

M. Esponda-Argüero

Virtuelle Speicher

Bis jetzt sind wir davon ausgegangen, dass Prozesse komplett im Hauptspeicher gelagert werden.

Speicherreferenzen sind nur logische Adressen, die dynamisch in physikalische Adressen umgewandelt werden.

Prozesse werden in Teile (Seiten oder Segmente) zerlegt und nach verschiedenen Strategien im Speicher geladen.

2

M. Esponda-Argüero

Virtueller Speicher

Gesetzt:

Der physikalische Speicher ist nie groß genug!

Früher weil der Speicher zu teuer war.

Jetzt weil ständig neue Multimedia-Anwendungen

entwickelt werden, die noch größer sind.

Seit den 50er Jahren müssen Programme ausgeführt werden, die nicht in den physikalischen Hauptspeicher passten.

3

M. Esponda-Argüero

Virtueller SpeicherErste Lösung:

- Algorithmen, um den Speicherverbrauch zu reduzieren.

- Programmierer müssten selber die Programme teilen (Overlays) und genauere Anweisungen für das Ein- und Auslagern angeben.

Zweite Lösung:

Die Verwaltung der Overlays wurde vom Betriebssystem übernommen, aber der Programmierer musste trotzdem das Programm teilen.

Durchbruch im Jahr 1961

Als das Konzept des virtuellen Speichers von Fortheringham vorgeschlagen worden ist.

4

M. Esponda-Argüero

Virtueller Speicher

Die reale Hauptspeichergröße wird mit Hilfe eines Bereichs auf der Festplatte

erweitert.

Aus Sicht des Benutzers haben die Programme viel mehr Hauptspeicher zur

Verfügung, als tatsächlich vorhanden.

Programm 3

Hauptspeicher

Programm 2Virtuelle Speicherräume

Programm 1

5

M. Esponda-Argüero

Virtueller Speicher

ProzessSpeicher-VerwaltungMMU+BS

virtuelleAdresse

physischeAdresse

Hauptspeicher

Hintergrundspeicher

Festplatten-Adresse

Prozess

Bei Rechnern mit virtuellem Speicher

geht die Adresse nicht direkt an den

Hauptspeicher, sondern an die MMU

Memory Managment Unit, die die

virtuelle Adresse auf die

physikalische Adresse abbildet.

Der Adressraum wird in Hauptspeicher und Hintergrundspeicher aufgeteilt.

Die Programme generieren nur virtuelle Adressen.

6

M. Esponda-Argüero

Virtueller Speicher

Die Technik des virtuellen Speichers befreit den Benutzer von Speichereinschränkungen.

Die Implementierung eines virtuellen Speichers ist kompliziert

- Hardware und Software werden kompliziert

Vorteile

Nachteile

Bei unvorsichtiger Anwendung kann die Ausführung der Programme stark verlangsamt werden.

Prozesse können gemeinsame Programmteile benutzen.

Prozesse können effizienter erzeugt werden.

- mehrere kleinere Prozesse können laufen

- weniger I/O-Operationen beim Swapping

7

M. Esponda-Argüero

Virtueller Speicher

Es gibt zwei grundlegende Implementierungsmöglichkeiten für virtuelle Speichersysteme.

Demand Segmentation

Demand Paging Es werden im Hauptspeicher nur die Seiten

geladen, die gerade gebraucht werden.

Es werden im Hauptspeicher nur die Segmente geladen, die gerade gebraucht werden.

- weniger I/O-Operationen

- weniger Speicherverbrauch

- mehrere Prozesse

- schnellere Antwortseiten

Einlagern nach Anforderung

8

M. Esponda-Argüero

Valid-Invalid Bit

9

Jeder Seitentabellen-Eintrag hat einen invalid-valid-Bit v ⇒ ist im Hauptspeicher und im Prozess-Adressraum i ⇒ ist nicht im Hauptspeicher oder nicht im Prozess-Adressraum

Am Anfang werden alle invalid-valid-Bit auf i gesetzt.

vvvvi

ii

….

Frame #

Seitentabelle

valid-invalid Bit

Während der Adressübersetzung wird ein Seitenfehler verursacht, wenn der valid-invalid-Bit auf i gesetzt ist.

M. Esponda-Argüero

Demand Paging

10

Die Seiten eines Prozesses werden erst geladen, wenn sie zum ersten Mal gebraucht werden.

Frames

valid-invalid-Bit

Logische Speicher

A

B

C

D

E

F

G

H

0

1

2

3

4

5

6

7

Seiten

Hauptspeicher

12345678910111213141516

A

B

D

F

12345678910111213141516

A

B

D

F

Festplattenspeicher

A

B

C

D

E

F

G

H

Seitentabelle

01234567

vvivivii

311

7

5

Die virtuelle Seite 10 wird als Index für die Seitentabelle verwendet

Das Innenleben einer MMU mit 16x4K-Seiten

0000000101101010

virtuelle Seite

CPU

Seitentabelle

12345678910111213141516

0000001000000000000000000110011101000101001100000000001100000000

0100001111100100

valid-invalid-Bit

0101

0000000101100101Offset

Offset

physikalischer Speicher

M. Esponda-Argüero

ohne TLB!

Schritte für die Behandlung von Seitenfehlern

load Adresse

TLB

Festplattenspeicher

A

B

C

D

E

F

G

H


itrap

A

Fehlender Frame wird

kopiertCPU

Der load- Befehl wird fortgesetzt

Die Seite ist im Hintergrundspeicher

v

setzt die Seitentabelle

auf valid

Betriebssystem

M. Esponda-Argüero

page frame

M. Esponda-Argüero

Schritte für die Behandlung von Seitenfehlern1. Es wird zuerst in einer internen Tabelle (gespeichert mit der PCB)

kontrolliert, ob die Referenz gültig ist.

2. Wenn die Referenz nicht gültig ist, wird der Prozess beendet.

Wenn sie gültig ist, aber noch nicht im physikalischen Speicher ist, muss die Seite aus dem Hintergrundspeicher gelesen werden.

1. Ein leerer Frame wird im Hauptspeicher gesucht.

2. Eine I/O-Festplattenoperation wird gestartet und die neue Seite wird im Hauptspeicher kopiert.

3. Wenn die Seite kopiert worden ist, wird in der internen Tabelle des Prozesses sowie in der Seitentabelle die neue Seite als verfügbar markiert.

4. Der Prozess wird an der Stelle wieder gestartet, wo er von dem trap unterbrochen wurde.

13

M. Esponda-Argüero

Seitenfehler-Overhead

14

Beispiel:Speicherzugriff = 200 ns.

durchschnittliche Behandlungszeit = 8 Millisekunden

Wahrscheinlichkeit des Auftretens = p

EAT = (1− p) ⋅ (200ns) + p ⋅ (8ms)

= (1− p) ⋅200 + 8.000.000p

= 200 + 7.999.800p

ns.

Wenn p =1

1000 ⇒ EAT = 8200 ns.

(Effective Access Time)

40% langsamer!

Seitenersetzung

A

B

D

E

F

G

H

Logische Speicher

von Prozess 2

0

1

2

3

Seiten

0

1

2

3

Logische Speicher

von Prozess 1

Seitentabelle von Prozess 1

Frames

valid-invalid-Bit

0123

vviv

310

8

Physikalischer Speicher

0123456789101112131415


0123

vivv

1

56

C H

D

B

E

A

G

Festplattenspeicher

C

F

M. Esponda-Argüero

Seitenfehler

A

B

D

E

F

G

H

Logische Speicher

von Prozess 2

0

1

2

3

Seiten

0

1

2

3

Logische Speicher

von Prozess 1


Frames

valid-invalid-Bit

0123

vviv

310

8

Physikalischer Speicher

0123456789101112131415


0123

vivv

1

56

C H

D

B

E

A

G

Festplattenspeicher

C

F

M. Esponda-Argüero

F

vvvv

11256

M. Esponda-Argüero

Grundlegende Schritte einer Seitenersetzung

17

• Seite im Hintergrundspeicher finden

• Freiplatz (für die Seite im Hauptspeicher) finden

✴ Wenn es einen Freiplatz gibt, wird er verwendet

✴ Wenn es keinen gibt, wird ein Ersetzungsalgorithmus benutzt

✴ Die Opferseite wird im Hintergrundspeicher zurück geschrieben

• Die neue Seite wird im Hauptspeicher kopiert

• Die Seitentabelle wird aktualisiert

• Den Prozess wird erneut gestartet

Wenn ein Seitenfehler auftritt:

M. Esponda-Argüero 18

Um den doppelten Aufwand des Hin- und Zurückkopierens zu vermeiden, wird ein zusätzliches Bit verwendet.

modify bit (dirty bit) Nur wenn eine Seite verändert worden ist, wird auf die Festplatte zurückkopiert

die Seite wird ausgelagert

1i0

Opfer13

wird auf invalid gesetzt

2

die gefragte Seite wird geladen

3

V13

ein neuer Eintrag wird in die Tabelle geschrieben

4


Seitentabelle

Grundlegende Schritte einer Seitenersetzung

TLBs – Translation Lookaside Buffers

Valid Modified Protection Virtual page Page frame

1 1 110 140 13

1 0 101 750 20

1 0 100 440 13

1 0 101 22 12

1 1 111 340 99

1 1 110 120 85

1 0 101 110 65

1 0 110 625 99

R W X

M. Esponda-Argüero

Zwei wichtige Fragen sollen möglichst gut gelöst werden.

Wie viele Seiten soll ein Prozess von seinem gesamten

Adressraum im Speicher haben?

Mit welcher Strategie sollen alte gegen neue Seiten

ausgetauscht werden?

20

frame-allocation-Algorithmus

page-replacement-Algorithmus

M. Esponda-Argüero

Ersetzungsalgorithmen

1) FIFO-Strategie

Was ist der Optimale Ersetzungsalgorithmus?

Ersetzt die Seite, die am längsten nicht gebraucht wird.

2) LRU-Strategie Least Recently Used

3) Clock-Algorithmus

21

Beispiele:

M. Esponda-Argüero

Wie können die Algorithmen verglichen werden?

22

reference strings

am besten mit echte Zugriffssequenzen, die mit Hilfe von trace-Funktionen erzeugt und gespeichert werden können.

Beispiel:

0100, 0432, 0101, 0612, 0102, 0103, 0110, 0611, ...

1, 4, 1, 6, 1, 6, ...

1 Seite = 100 Bytes

M. Esponda-Argüero

Seitenfehler vs. Frame-Anzahl

23

Grafikquelle: Silverschatz, Galvin, Gagne

M. Esponda-Argüero

FIFO-Ersetzungsalgorithmus

24

- Das Betriebssystem verwaltet eine Liste von allen Seiten im Speicher. Am Kopf der Liste steht die älteste Seite und am Ende die, die zuletzt eingelagert wurde.

- Bei einem Seitenfehler wird die Seite am Kopf der Liste entfernt und die neue Seite wird an das Ende angehängt.

Nachteil:

Seiten werden ausgelagert, obwohl sie häufig benutzt werden.

Seitenanforderungenneue Seiten

älteste Seiten

0 10

210

3210

3210

0432

0 1 2 3 0 1 4 0

F F F F F F

4321

3210

M. Esponda-Argüero

FIFO-Seitenersetzungsstrategie

Vorteile:

Geht davon aus, dass Seiten, die als letztes geladen werden öfter verwendet werden.

Sehr einfach zu implementieren.

Probleme:

Daten, die während der gesamten Ausführung des Programms benötigt werden, werden ständig ein- und ausgelagert.

Die FIFO-Seitenersetzung wird selten verwendet.

25

Modellierung der FIFO-Seitenersetzungsstrategien Belady‘s Anomaly

Am Anfang gibt es keine Seite

0 10

210

321

032

103

410

410

410

241

324

324

neue Seiten

älteste Seiten

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

F F F F F F F F F 9 Fehler

0 10

210

3210

3210

0432

1043

2104

3210

4321

neue Seiten

älteste Seiten

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

F F F F F F F F F F10 Fehler

4321

3210

M. Esponda-Argüero

M. Esponda-Argüero

Optimaler Algorithmus

27

Ersetzt die Seite, die am längsten nicht verwendet wird.

6 Seitenfehler

1

2

3

4

Wie können wir das wissen?nur als Massstab für Simulationen von anderen Algorithmen verwendet

1, 2, 3, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Beispiel:

1

2

3

5

M. Esponda-Argüero

Least Recently Used (LRU)

28

• Eine Seite, die von den letzten Befehlen benutzt wurde, wird wahrscheinlich auch für die nächsten gebraucht.

• Seiten, die schon lange nicht benutzt worden sind, werden ausgelagert.

• Eine verkettete Liste von allen Seiten im Speicher ist nötig• mit der zuletzt benutzten Seite am Anfang• und der am längsten nicht benutzten Seite am Ende• die Liste muss nach jedem Speicherzugriff aktualisiert werden!!!

(O(n))• Alternativ kann ein Zähler pro Antrag in der Seitentabelle benutzt

werden.• Beim Seitenfehler wird die Seite mit dem niedrigsten Zähler-Stand

gewählt.

Referenzliste: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

5243

- Implementierung mit Zähler (Zeitstempel)

- Jeder Seitenantrag hat einen Zähler; jedes Mal, wenn eine

Seite durch diesen Antrag referenziert wird, muss die aktuelle

Zeit in dem Zähler kopiert werden.

- Wenn eine Seite ersetzt werden soll, muss mit Hilfe der

Seitenzähler die Seite gesucht werden, die am längsten nicht

benutzt worden ist.

Least Recently Used (LRU)

1234

1254älteste

1253

älteste

1243

älteste

M. Esponda-Argüero


Sequenz der Referenzen

Seiten

7

7

0

7

0

1

2

0

1

2

0

3

4

0

3

4

0

2

4

3

2

0

3

2

1

3

2

1

0

2

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

1

0

7

2

0

1

2

0

3

0

3

2

0

3

2

LRU

LRU-Algorithmus


Ein Stapel, mit einer doppelt verketteten Liste, kann verwendet werden.

Die zuletzt referenzierte Seite wird an die Spitze des Stapels platziert.

Die Suche der LRU-Seite kann in konstanter Zeit O(1) realisiert werden.

LRU

Sequenz der Referenzen3 5 5 5 2 6 0 1 4 4 4 6

1

0

6

2

5

3

4

1

0

6

2

5Die Aktualisierung der Stapel muss nach jedem Speicherzugriff gemacht werden!!

6

4

1

0

2

5

LRU-Algorithmus

Aber? LRU

Head

LRU-Algorithmus mit HardwareEine Matrix aus nxn Bits wird verwendet, wo n die Anzahl der Seiten ist.Wenn ein Zugriff auf Seite k stattfindet, setzt die Hardware alle Bits der Zeile k auf 1 und alle Bits der Spalte k auf 0.

0 0 0 0 0

1 0 1 1 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 1 2 3 4

0

1

2

3

4

Seitenzugriffe 1 2 3 1 0 4 2 1 3

0 0 0 0 0

1 0 0 1 1

1 1 0 1 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

1 0 0 0 1

1 1 0 0 1

1 1 1 0 1

0 0 0 0 0

0 0 0 0 0

1 0 1 1 1

1 0 0 0 1

1 0 1 0 1

0 0 0 0 0

0 1 1 1 1

0 0 1 1 1

0 0 0 0 1

0 0 1 0 1

0 0 0 0 0

Die Zeile mit dem niedrigsten Binärwert ist am längsten nicht benutzt worden.

0 1 1 1 0

0 0 1 1 0

0 0 0 0 0

0 0 1 0 0

1 1 1 1 0

0 1 0 1 0

0 0 0 1 0

1 1 0 1 1

0 0 0 0 0

1 1 0 1 0

0 0 0 1 0

1 0 1 1 1

1 0 0 1 1

0 0 0 0 0

1 0 0 1 0

0 0 0 0 0

1 0 1 0 1

1 0 0 0 1

1 1 1 0 1

1 0 0 0 0

M. Esponda-Argüero

Der Second-Chance-Algorithmus

33

Das R-Bit der ältesten Seite wird geprüft.

Wenn es nicht gesetzt ist, ist die Seite nicht nur alt sondern auch unbenutzt und wird ersetzt.

Ansonsten wird das R-Bit zurück gesetzt, die Seite am Ende der Liste angehängt und die nächst älteste Seite geprüft.

• Variante der FIFO-Strategie

• Ein Referenced-Bit (R-Bit) wird verwendet, um zu

signalisieren, dass eine Seite wieder verwendet

worden ist.

M. Esponda-Argüero


34

1 0 0 0 1 1 R-Bit

Erste geladene Seite

Zuletzt geladene Seite

A B C D E F

B wird ersetztA wird wie eine neu geladene Seite behandelt

Die neue Seite wird geladen

0 3 5 6 7 9

Ladezeiten

0 0 0 1 1 0

B C D E F A

3 5 6 7 9 11

0 0 1 1 0 0

neue Seite

C D E F A 5 6 7 9 11 12

M. Esponda-Argüero


35

nächstes Opfer

Bild aus Silverschatz, Galvin und Gagne

Zirkuläre Warteschlange

Referenzbits Referenzbits

M. Esponda-Argüero

Der Clock-Algorithmus

36

1

1

00

0

1

0

0

11

1

0

AB

C

D

E

FG

H

I

J

K

L Sobald ein Seitenfehler auftritt, wird

die Seite referenziert, auf die der

Pfeil zeigt. Die Folgeaktion hängt

vom R Bit ab:

Wenn R=0: Die Seite wird ersetzt

Wenn R=1: Lösche R und wandere

mit dem Pfeil eine Position weiter.


1

1

00

0

1

0

0

11

1

0

A neue Seite

C

D

E

FG

H

I

J

K




vom R Bit ab:






0

1

00

0

1

0

0

11

1

0

A neue Seite

C

D

E

FG

H

I

J

K




vom R Bit ab:






0

0

00

0

1

0

0

11

1

0

A neue Seite

C

D

E

FG

H

I

J

K




vom R Bit ab:






0

0

00

0

1

0

0

11

0

A neue Seite

C

D

GH

I

J

K

L

neue Seite

1

F

Sobald ein Seitenfehler auftritt, wird



vom R Bit ab:





M. Esponda-Argüero

NFU-AlgorithmusNot Frequently Used

• Jede Seite besitzt einen Zähler.

• Nach jeder Zeitunterbrechung wird das R-Bit der Seiten an den jeweiligen Zählern addiert.

• Bei Seitenfehlern wird die Seite mit dem niedrigsten Zählerstand ersetzt.

Probleme

Seiten, die am Anfang sehr oft benutzt worden sind, bleiben im Speicher, obwohl diese nicht mehr gebraucht werden.

41

M. Esponda-Argüero

Aging-Algorithmus

Alle Seitenzähler werden zuerst ein Bit nach rechts verschoben und dann wird das R-Bit zum höchstwertigen Bit des Zählers addiert.

Eine Seite, auf die in den letzten Intervallen nicht zugegriffen wurde, hat Nullen an den ersten Bitstellen des Zählers und damit einen niedrigeren Zählerwert als der Zähler der Seiten, auf die zugegriffen worden ist.

Problem

Das Aufzeichnen vergangener Zugriffe ist durch die Anzahl der Bits begrenzt.

Zwischen zwei Zählern voller Nullen ist es nicht mehr möglich zu wissen, welche Seite zuletzt benutzt worden ist.

42

Aging-Algorithmus

Seitenzähler11100000

10000000

01100000

10100000

00100000

01100000

11110000

01000000

10110000

01010000

10010000

10110000

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

t1 t

2t3

t4

t5

R- Bits der Seiten 0 bis 5

10000000

00000000

10000000

10000000

10000000

10000000

0

1

2

3

4

5

Seitet1

11000000

00000000

11000000

01000000

01000000

11000000

t2

11111000

00100000

11011000

00101000

01001000

01011000

t1

t5

M. Esponda-Argüero

M. Esponda-Argüero

Working-Set

44

Die Menge von Seiten, die ein Prozess zu einem bestimmten Zeitpunkt benutzt, wird Working-Set oder Arbeitsbereich genannt.

Working-Set = Δ

Reihenfolge der Seitenzugriffe:

WS(P1)={1,2,3,5,6}

. . . 3 3 5 6 3 3 3 3 2 1 8 . . . 7 7 7 9 7 7 9 9 7

P1

Δ

P2

Δ

WS(P2)={7,9}

M. Esponda-Argüero

Working-setEinlagern bei Bedarf

Lokalität der Referenzen

Die Seiten eines Prozesses können erst bei Anforderung gelagert werden.

Probleme

Zu viele Seitenfehler bis der Prozess alle Seiten, die er braucht, im Speicher hat.

Prozesse neigen dazu, ihre Seitenzugriffe innerhalb zeitlich begrenzter Ausführungsphasen auf einen relativ kleinen Teil ihrer Seiten zu reduzieren.

45

Lokalität der Referenzen

Bildquelle: Silverschatz, Galvin und Gagne

M. Esponda-Argüero

Working-Set-Modell

Eine reine Form des Wieder-Einlagerns bei Bedarf würde dazu führen, dass jeder Prozess viele Seitenfehler erzeugen könnte, bevor er seinen Arbeitsbereich wieder vollständig geladen hat.

Viele Betriebssysteme benutzen die Lokalitätseigenschaft der Prozesse und merken sich deshalb den Arbeitsbereich eines Prozesses und sorgen dafür, dass er wieder geladen wird.

Dieser Ansatz wird Working-Set-Modell genannt und soll dafür sorgen, dass die Seitenfehlerrate reduziert wird.

47

M. Esponda-Argüero

Working-Set

48

Arbeitsbereich

Sei

tenfe

hle

r-Rat

e

Zeit

1

0

Wieder-Einlagern bei Bedarf

M. Esponda-Argüero

Working-Set

Lokalität der Referenzen.

Wenn Δ zu klein ist, können viele Prozesse im Speicher arbeiten,

aber die Lokalitäten werden nicht komplett.

Wenn Δ zu groß ist, werden mehrere Lokalitäten gleichzeitig

umfasst.

Wenn Δ ohne Grenzen wächst, ist irgendwann das ganze

Programm da.

- niedrige CPU Auslastung- zu wenig Programme können gleichzeitig arbeiten.- sehr großer Zeitaufwand beim swapping.

Das Problem des Seiten-Flatterns (Thrashing) entsteht

49


Ein Prozess ist nur mit dem Ein- und Auslagern von Seiten beschäftigt.

Seitenflattern

Wenn ein Prozess nicht genug Seiten hat, wird die Seiten-Fehlerrate zu hoch.

Anzahl von Prozessen

CPU

-Ausl

astu

ng

Thrashing

Thrashing


Angenommen, es gibt eine etablierte Fehlerrate.• Wenn die aktuelle Rate zu klein ist, darf der Prozess Seiten

verlieren.• Wenn sie zu hoch ist, sollen zusätzliche Seiten geladen werden.

Seitenfehlerrate-Schema

WS-Algorithmus

R-Bit1280 1

1620 0

2810 1

2010 0

Letzter Zugriff

Seitentabelle

Die Seite wurde im letzten Intervall benutzt.

Alle Seiten und entsprechende R-Bits werden durchsucht. wenn R=1

die Zeit des letzten Zugriffs wird mit der aktuellen virtuellen Zeit ersetzt.

wenn R=0 und (virtuelle Zeit - letzter Zugriff) > Δ Seite ersetzen. wenn alle Seiten im Arbeitsbereich liegen und es gab Seiten mit R=0 die Seite mit dem höchsten Alter wird ausgelagert. wenn im letzten Intervall auf alle Seiten zugegriffen würde (R=1 in alle Seiten) eine willkürlich gewählte Seite wird ausgelagert.

Δ Zeitintervall, um den Working-Set Fenstern eines Prozesses festzulegen.

M. Esponda-Argüero

M. Esponda-Argüero

WS-AlgorithmusProbleme

Die ganze Seitentabelle muss jedesmal durchsucht werden.

Verbesserung

WSClock-Algorithmus von Carr und Hennessey 1981

• Eine ringförmige Liste mit Seiteninformation wird verwendet.

• Am Anfang ist die Liste leer.

• Neu geladene Seiten werden in der Liste eingefügt.

53

WSClock-Algorithmus• Bei einem Seitenfehler werden die Seiten ab einem Uhrzeiger-Position

untersucht.• Wenn das R-Bit gesetzt ist, wird dieser auf 0 gesetzt, Die Zeitstempel

aktualisiert und der Uhrzeiger sucht weiter.

• Wenn das R-Bit gleich 0 ist und das Alter der Seite größer als Δ• wenn die Seite nicht verändert wurde dirty-Bit ist gleich 0, wird sie ersetzt.• sonst wird auf der Seite vorgemerkt, den Inhalt auf die Platte

zu schreiben (um Prozess-Wechsel zu vermeiden) der Uhrzeiger geht einen Schritt weiter und sucht weiter nach einer nicht veränderten Seite.

Wenn der Uhrzeiger an den Anfang der Liste zurückkehrt und mindestens eine Seite vorgemerkt wurde, bewegt sich der Zeiger weiter bis die erste saubere Seite gefunden wird.Wenn der Uhrzeiger am Anfang der Liste zurückkehrt und keine Seite vorgemerkt wurde, gehören alle Seiten zu irgendeinem Arbeitsbereich und es wird eine beliebige Seite ausgelagert.

M. Esponda-Argüero

WSClock-Algorithmus

0600 0

0800 0 2010 1

2220 0 2200 0

2100 12000 0

1200 01200 0

1900 0

Virtuelle Zeit2300

R-Bit

Zeitpunkt des letzten Zugriffs

Δ = 1000

0 0D X

0 0D X

0 0D X

0 0D X

1 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

M. Esponda-Argüero

WSClock-Algorithmus

0600 0

0800 0 2300 0

2220 0 2200 0

2100 12000 0

1200 01200 0

1900 0

Virtuelle Zeit2300

Δ = 1000

0 0D X

0 0D X

0 0D X

0 0D X

1 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

M. Esponda-Argüero

WSClock-Algorithmus

0600 0

0800 0 2300 0

2220 0 2200 0

2100 12000 0

1200 01200 0

1900 0

Virtuelle Zeit2300

Δ = 1000

0 0D X

0 0D X

0 0D X

0 0D X

1 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

M. Esponda-Argüero

WSClock-Algorithmus

0600 0

0800 0 2300 0

2220 0 2200 0

2300 02000 0

1200 01200 0

1900 0

Virtuelle Zeit2300

Δ = 1000

0 0D X

0 0D X

0 0D X

0 0D X

1 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

M. Esponda-Argüero

WSClock-Algorithmus

0600 0

0800 0 2300 0

2220 0 2200 0

2300 02000 0

1200 0

1900 0

Virtuelle Zeit2300

Δ = 1000

wird markiert!

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

1200 01 1D X

M. Esponda-Argüero

WSClock-Algorithmus

0600 0

0800 0 2300 0

2220 0 2200 0

2300 02000 0

1200 0

1900 0

Virtuelle Zeit2300

Δ = 1000

wird markiert!

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

1200 01 1D X

M. Esponda-Argüero

WSClock-Algorithmus

0600 0

0800 0 2300 0

2220 0 2200 0

2300 02000 0

2300 0

1900 0

Virtuelle Zeit2300

Δ = 1000

wird markiert!

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

1200 01 1D X

Neue Seite!

M. Esponda-Argüero

WSClock-Algorithmus

0600 0

0800 0 2300 0

2220 0 2200 0

2300 02000 0

2300 0

1900 0

Virtuelle Zeit2300

Δ = 1000

wird markiert!

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

0 0D X

1200 01 1D X

Neue Seite!

M. Esponda-Argüero

M. Esponda-Argüero

Zusammenfassung der AlgorithmenAlgorithmus Kommentar

Optimale Ersetzung Optimale Ersetzung

NRU (Not Recently Used) Sehr primitiv

FIFO Wichtige Seiten können entfernt werden

Second Chance Verbesserung gegenüber FIFO

LRU (Least Recently Used) Exzellent, aber schwierig zu implementieren

NFU (Not Frequently Used) Grobe Annährung an LRU

Aging Effizienter Algorithmus, der fast LRU erreicht

Working Set Aufwändige Implementierung

WSClock Guter und effizienter Algorithmus

63

Documents

OS V15 Virtuelle Speicher - inf.fu-berlin.de · Als das Konzept des virtuellen Speichers von Fortheringham vorgeschlagen worden ist. 4. M. Esponda-Argüero Virtueller Speicher Die