Systeme 1 Kapitel 8.1 Speicherverwaltung - Paging WS 2009/101

Systeme 1

Kapitel 8.1Speicherverwaltung - Paging

WS 2009/10 1

• Zwischenklausur:– Jetzt am Samstag (19.12.2009)– Ort: Technische Fakultät– Zeit: 10 Uhr s.t.– Dauer: 45 Minuten– Räume: 101-026/036– Hilfsmittel: Außer Stifte KEINE! (Blätter werden gestellt)

• Vorlesungsbeginn– 08.01.2010

WS 2009/10 2

Letzte Vorlesung• Speicherhierarchie• Anforderungen an das Betriebssystem– Relokation– Schutz– Gemeinsame Nutzung– Logische Organisation– Physikalische Organisation

• Grundlegende Methoden der Speicherverwaltung– Partitionierung– Paging– Segmentierung

WS 2009/10 3

Letzte Vorlesung

• Partitionierung– Statische Partitionierung

• Partitionen mit gleicher Länge• Partitionen mit unterschiedlicher Länge

– Dynamische Partitionierung• Defragmentierung erforderlich• Speicherzuteilungsalgorithmen:

Best Fit, First Fit, Next Fit– Buddy-System

• Kompromiss zwischen statischer und dynamischer Partitionierung

WS 2009/10 4

Speicherverwaltung• Speicherverwaltung:

– Aufteilung des verfügbaren Hauptspeichers zwischen• Betriebssystem• verschiedenen Prozessen

• Speicherverwaltung erfordert enges Zusammenspiel von– Hardware und – Betriebssystem.

• Zur Erinnerung:– Zu jedem Prozess gehört ein Adressraum:

• zugeordneter Arbeitsspeicher mit minimalen und maximalen Adressen

• Enthält – Ausführbares Programm, Programmdaten und Kellerspeicher

(“Stack”)

WS 2009/10 5

Grundlegende Methoden der Speicherverwaltung• Partitionierung– Für Speicheraufteilung zwischen verschiedenen

Prozessen eher veraltetes Konzept– Betriebssysteminterne Nutzung von Partitionierung

• Paging– Einfaches Paging– Kombiniert mit Konzept des virtuellen Speichers

• Segmentierung– Einfache Segmentierung– Kombiniert mit Konzept des virtuellen Speichers

WS 2009/10 6

Einfaches Paging• Wie bisher (im Gegensatz zu virtuellem Speicherkonzept): Prozesse

sind entweder ganz im Speicher oder komplett ausgelagert.• Im Gegensatz zu Partitionierung werden Prozessen nicht

notwendigerweise zusammenhängende Speicherbereiche zugeordnet.

• Hauptspeicher aufgeteilt in viele gleichgroße Seitenrahmen.• Speicher eines Prozesses aufgeteilt in Seiten derselben Größe.• Zuordnung von Seiten zu Seitenrahmen beim Laden von Prozessen

– Logische Adressen der Form „Seitennummer, Offset“– Pro Prozess eine „Seitentabelle“ – Seitentabelle übersetzt Seitennummern in Nummern von

Seitenrahmen im physikalischen Speicher• Interne Fragmentierung nur bei letzter Seite eines Prozesses

WS 2009/10 7

Einfaches Paging: Beispiel

WS 2009/10 8

Rahmen-nummer

01

2

3

4

5

6

7

8

9

10

11

12

13

14

Hauptspeicher

01

2

3

4

5

6

7

8

9

Hauptspeicher

01

2

3

4

5

6

7

8

9

Hauptspeicher

01

2

3

4

5

6

7

8

9

Hauptspeicher

Prozess A geladen

Prozess B geladen

Prozess C geladen

10

11

12

13

14

10

11

12

13

14

10

11

12

13

14

A.0A.1A.2A.3

A.0A.1A.2A.3

A.0A.1A.2A.3

B.0B.1B.2

B.0B.1B.2C.0C.1C.2C.3

Prozess D mit 6 Seiten soll jetzt geladen werden!

Einfaches Paging: Beispiel

WS 2009/10 9

Rahmen-nummer

01

2

3

4

5

6

7

8

9

10

11

12

13

14

Hauptspeicher

01

2

3

4

5

6

7

8

9

Hauptspeicher

Prozess D geladen

10

11

12

13

14

A.0A.1A.2A.3

A.0A.1A.2A.3

C.0C.1C.2C.3

C.0C.1C.2C.3

Prozess B ausgelagert

D.0D.1D.2

D.3D.4

Datenstrukturen zum aktuellen Zeitpunkt:

01

2

3

0123

Seitentabelle Prozess A

01

2

---

Seitentabelle Prozess B

01

2

3

789

10

Seitentabelle Prozess C

01

2

3

456

11

Seitentabelle Prozess D

4 12

1314

Liste der freien Rahmen

Einfaches Paging• Berechnung von physikalischen Adressen aus

logischen Adressen:• Voraussetzung: Länge der Seiten ist eine

Zweierpotenz.• Logische Adresse besteht aus Seitennummer und

Offset.• Absolute Adresse wird durch Hardware auf

Grundlage der Seitentabelle des Prozesses berechnet.

• …

WS 2009/10 10

Einfaches Paging

• Beispiel: logische Adresse der Länge 16 Bit

• Der Prozess kann somit bis zu 26 verschiedene Seiten haben, die über die Seitentabelle des Prozesses auf Seitenrahmen im Hauptspeicher abgebildet werden.

• Jede Seite besteht aus 210 = 1024 Bytes.• Berechnung der physikalischen Adresse:

WS 2009/10 11

000001 0111011110

6-Bit-Seitennummer 10-Bit-Offset

Einfaches Paging

WS 2009/10 12

000001 0111011110


10010010100100111101100111111010

Seitentabelledes Prozesses

0123

= 1

……

……

Speicherzelle Nr. 478(=<0111011110>)Innerhalb des Seitenrahmens.

=> Reale Adresse:10010011 0111011110

= 478

Seitenrahmen Nr. 147(=<10010011>)

Einfaches Paging

• Entfernen eines Prozesses aus dem Speicher:– Lagere Prozess auf Hintergrundspeicher aus (z.B.

Festplatte).– Über Seitentabelle kann man feststellen, welche

Seitenrahmen dem Prozess gehören.– Füge diese Rahmen zur Liste der freien Rahmen

hinzu.– (Keine zusätzlichen Datenstrukturen des

Betriebssystems benötigt.)

WS 2009/10 13

Paging mit virtuellem Speicher• Grundidee:

– Wenn man im Zusammenhang mit Auslagern sowieso mit Hintergrundspeicher arbeitet, dann hat man auch die Möglichkeit, nur Teile der Daten von Prozessen ein- bzw. auszulagern.

– Das Programm kann momentan weiter ausgeführt werden, wenn die aktuell benötigten Informationen (Code und Daten) im Speicher sind.

– Wird auf Informationen zugegriffen, die ausgelagert (auf der Festplatte) sind, so müssen diese nachgeladen werden.

• Bezeichnungen:– Hauptspeicher = realer Speicher– Hauptspeicher + Hintergrundspeicher = virtueller Speicher

WS 2009/10 14

Paging mit virtuellem Speicher• Vorteile:– Mehr aktive Prozesse im Speicher

(=> Pseudoparallelismus!)– Tatsächlicher Speicherplatzbedarf eines Prozesses muss

nicht von vornherein feststehen.– Adressraum eines Prozesses kann jetzt größer sein als

verfügbarer Hauptspeicher.• Nachteil:– Bei Zugriff auf Code/Daten, die nicht im Hauptspeicher

vorhanden sind, muss das Betriebssystem die entsprechenden Seiten nachladen.

– Dabei müssen evtl. andere Seiten ausgelagert werden, um Platz zu schaffen.

WS 2009/10 15

Lokalität

• Kann das überhaupt effizient funktionieren?– Antwort: meistens!– Grund: Räumliche und zeitliche Lokalität von

Programmen, d.h. Abarbeitung während kürzerer Zeit bewegt sich häufig in engen Adressbereichen.• Abarbeitung von Schleifen• In zeitlich engem Abstand Zugriff auf gleiche Daten • Zugriffe auf benachbarte Daten

Aufgabe des Programmierers

WS 2009/10 16

Lokalität: Beispiel

• Matrix mit N x N Elementen.• Arbeitsspeicher „1-dimensional“, daher:– Ordne jede Zeile nacheinander im Speicher an.– Zugriff auf Element (i ,j) (i-te Spalte in Zeile j):• j * N + i

WS 2009/10 17

i

j


• Zugriffsmuster Beispiel 1: Initalisiere alle Elemente– Variante 1

Für N = 300 auf einer aktuellen Intel CPU (IA32): ~ 0.048 s

WS 2009/10 18

i

j

// jede Zeilefor(j = 0; j < N; j++){ // jede Spalte for(i = 0; i < N; i++) { pos = j * N + i; element[pos] = 0; }}


• Zugriffsmuster Beispiel 1: Initalisiere alle Elemente– Variante 2: Vertausche Zeilenindex mit Spaltenindex

Für N = 300 auf einer aktuellen Intel CPU (IA32): ~ 0.160 s

WS 2009/10 19

j

i

// jede Spaltefor(j = 0; j < N; j++){ // jede Zeile for(i = 0; i < N; i++) { pos = i * N + j; element[pos] = 0; }}


• Zugriffsmuster Beispiel 2: Matrixmultiplikation– Variante 1:

WS 2009/10 20

for (i = 0; i < N; ++i){ for (j = 0; j < N; ++j) { for (k = 0; k < N; ++k) { res[i][j] += ma[i][k] * mb[k][j]; } }}

1

0)1()1(2211)(

N

kjNNijijikjikij babababaAB


• Zugriffsmuster Beispiel 2: Matrixmultiplikation– Variante 2: Transponiere Matrix

WS 2009/10 21

// transponiere Matrix B in temporäre Matrixfor (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) { tmp[i][j] = mb[j][i]; }}for (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) { for (k = 0; k < N; ++k) { res[i][j] += ma[i][k] * tmp[j][k]; } }}

1

0)1()1(2211)(

N

k

TNjNi

Tji

Tji

Tjkikij babababaAB


• Zugriffsmuster Beispiel 2: Matrixmultiplikation– Test mit N = 1000 (Intel Core Duo 2666 Mhz)

• Variante 1: 16.765.297.870 CPU Zyklen• Variante 2: 3.922.373.010 CPU Zyklen• Relativer Gewinn: >70% !!!

– Analyse:• Variante 2 benötigt zusätzlichen Speicher für die transponierte Matrix.

Zudem müssen N*N Elemente kopiert werden. • Dennoch: Die 1000 nicht-sequentiellen Zugriffe (Matrix B) in Variante 1

sind wesentlich teurer. In Variante 2 kann über beide Matrizen sequentiell iteriert werden.

– Anmerkung: In diesem Beispiel wirken Cache-Effekte. Die Datenmenge ist zu klein, um in den Hintergrundspeicher ausgelagert zu werden. Dennoch ähnlicher Effekt, da Cache-Speicher um ein Vielfaches schneller als Hauptspeicher.

WS 2009/10 22

Lokalität

• Paging mit virtuellem Speicher ist nur dann effizient, wenn Lokalität gegeben.

• Falls nicht:– Ständiges Aus- und Einlagern von Seiten zwischen

Hauptspeicher und Festplatte– Bezeichnung: Seitenflattern („thrashing“)

WS 2009/10 23

Technische Realisierung• Technische Realisierung von Paging mit virtuellem Speicher:

– Die Daten des Prozesses befinden sich im Hintergrundspeicher (Festplatte), bei nicht komplett ausgelagerten Prozessen zusätzlich noch Teile im Speicher.

– Wie bei einfachem Paging: Trennung der logischen Adressen in Seitennummer und Offset, z.B.:

– Im Gegensatz zu einfachem Paging:• Logische Adressen überdecken kompletten virtuellen Adressraum, z.B.

32-Bit- / 64-Bit-Adressen.– Pro Prozess eine Seitentabelle zur Übersetzung

Seitennummer => Seitenrahmen

WS 2009/10 24

00 ... 01 0111001110


22-Bit-Seitennummer

Technische Realisierung• Logische Adresse:

– Seitentabelleneintrag:

• Present-Bit P: „Seite ist im Hauptspeicher“• Modify-Bit M: „Seite wurde verändert“• Weitere Bits für Schutzrechte und gemeinsame Nutzung

– Seitentabelle liegt im Hauptspeicher.– Umsetzung der virtuellen Adressen in reale Adressen mit

Hardwareunterstützung (Memory Managment Unit (MMU) des Prozessors)

WS 2009/10 25

00 ... 01 0111001110

10-Bit-Offset

P M Weitere Bits Seitenrahmennummer

Adressumsetzung

WS 2009/10 26

Seiten-rahmen

……

Rahmennr. Offset

Reale Adresse

Seitentabelle

Seitentabellen-zeiger

Register

Virtuelle Adresse

Seitennr. Offset

Rahmennr.

Programm Paging-Verfahren Hauptspeicher

Seitentabelle

WS 2009/10 27

Seite 0

Seite 1

Seite 2

Seite 3

Seite 4

Seite 5

Seite 6

Seite 7

Seitenrahmen 0

Seitenrahmen 1

Seitenrahmen 2

Seitenrahmen 3

Seitennr. P … Rahmennr.

0 0 …

1 0 …

2 1 … 0

3 0 …

4 1 … 3

5 0 …

6 0 …

7 0 …

virtueller Adressraum

Hauptspeicher

Seitentabelle des Prozesses im Hauptspeicher

Seitenfehler• Was passiert beim Zugriff auf eine Seite, die sich nicht im

Hauptspeicher befindet?– Hardware (MMU) stellt anhand des present bits fest, dass angefragte

Seite nicht im Hauptspeicher ist (=> „Seitenfehler“ bzw. „page fault“).– Auslösen einer Unterbrechung („Interrupt“) durch die Hardware– Behandlung des Interrupts:

• Laufendes Programm wird unterbrochen, Sichern des aktuellen Programmzustandes durch Hardware (Stand des Programmzählers!)

• Routine zur Interruptbehandlung wird aufgerufen.– Feststellen des Grundes der Unterbrechung (hier: page fault)– Behandlung abhängig vom Grund der Unterbrechung, hier:

» Betriebssystem lädt die entsprechende Seite von der Festplatte in einen freien Seitenrahmen.

» Wenn kein Seitenrahmen frei: Vorheriges Verdrängen eines belegten Seitenrahmens

» Aktualisierung der Seitentabelle• Danach: Laufendes Programm wird wieder fortgesetzt.WS 2009/10 28

Seitenfehler

• Welche Informationen benötigt das Betriebssystem zum Einlagern von Seiten (d.h. während der Behandlung einer Unterbrechung wegen eines page faults)?– Abbildung Seitennummer --> Festplattenadresse,

um die gesuchte Seite auf der Festplatte zu finden– Liste freier Seitenrahmen

WS 2009/10 29

Seitenfehler

WS 2009/10 30

Seite 0

Seite 1

Seite 2

Seite 3

Seite 4

Seite 5

Seite 6

Seite 7

Seitenrahmen 0

Seitenrahmen 1

Seitenrahmen 2

Seitenrahmen 3

Seitennr. P … Rahmennr.

0 0 …

1 0 …

2 1 … 0

3 0 …

4 1 … 3

5 0 …

6 0 …

7 0 …


Hauptspeicher

Seitentabelle des Prozesses im Hauptspeicher

Festplatten-Adresse

A

D

B

X

Y

C

E

F

Verdrängung• Wenn kein freier Seitenrahmen vorhanden: Verdrängen von

Seitenrahmen Festplatte.

• Je nach Betriebssystem:– Alle Seitenrahmen sind Kandidaten für Verdrängung oder– Nur Seitenrahmen des eigenen Prozesses

• Entscheidung unter diesen Kandidaten gemäß Verdrängungsstrategie (Ziel: gute Ausnutzung von Lokalität)

• Ist das Modify-Bit M gesetzt, dann muss Seite im entsprechenden Rahmen auf Festplatte zurückgeschrieben werden.

• Nach Verdrängen eines Seitenrahmens muss die Seitentabelle des zugehörigen Prozesses aktualisiert werden.

• Da Seitentabellen meist nur dünn besetzt:– Suchen des verdrängten Seitenrahmens in Seitentabelle des Prozesses

ineffizient– Abbildung Seitenrahmennummer --> (Prozessnummer, Seitennummer)

hilfreich

WS 2009/10 31

Verdrängung

WS 2009/10 32

Seite 0

Seite 1

Seite 2

Seite 3

Seite 4

Seite 5

Seite 6

Seite 7

Seitenrahmen 0

Seitenrahmen 1

Seitenrahmen 2

Seitenrahmen 3

Hauptspeicher

Seitentabelle von Prozess 1

Seite P … Rahmen

0 0 …

1 0 …

2 1 … 1

3 0 …

4 1 …

5 0 …

6 0 … 2

7 0 …

Seite P … Rahmen

0 0 …

1 0 …

2 1 … 0

3 0 …

4 1 … 3

5 0 …

6 0 …

7 0 …

Seitentabelle von Prozess 2

Seite 0

Seite 1

Seite 2

Seite 3

Seite 4

Seite 5

Seite 6

Seite 7


Prozess 2Seite 6 vonProzess 2 soll Aus-gelagert werden=> P = 0

Seitenrahmen 2 sollfreigeräumt werden.


Prozess 1

Verdrängung

WS 2009/10 33

Seite 0

Seite 1

Seite 2

Seite 3

Seite 4

Seite 5

Seite 6

Seite 7

Seitenrahmen 0

Seitenrahmen 1

Seitenrahmen 2

Seitenrahmen 3

Hauptspeicher

Rahmen Prozess Seite

0 1 2

1 2 2

2 2 6

3 1 4

Abbildung Seitenrahmennummer -> (Prozessnummer, Seitennummer)

Seite 0

Seite 1

Seite 2

Seite 3

Seite 4

Seite 5

Seite 6

Seite 7

Frohe Weihnachten

WS 2009/10 34

Documents

Systeme 1 Kapitel 8.1 Speicherverwaltung - Paging WS 2009/101