RW-SystemarchitekturKap. 8 1 Kapitel 8 Speicherverwaltung

RW-Systemarchitektur Kap. 81

Kapitel 8Speicherverwaltung


Überblick Betriebssysteme6 Einführung

7 Prozesse, Fäden (threads), Scheduling

8. Speicherverwaltung

8.1 Anforderungen an die Speicherverwaltung

8.2 Grundlegende Methoden der Speicherverwaltung8.2.1 Partitionierung

8.2.2 Verlagerung

8.2.3 Seitenadressierung und Seitenaustausch

8.2.4 Segmentierung

8.2.5 Seiten und Segmente

9. Dateisysteme

10. Ein- und Ausgabe

Nebenläufigkeit und wechselseitiger Ausschluss – Inhalt der Vorlesung „Nebenläufige Programmierung“

Deadlocks - dito


8 Speicherverwaltung

• Speicherverwaltung: – Aufteilung des verfügbaren Hauptspeichers zwischen

• Betriebssystem• verschiedenen Prozessen

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

• Hardwareaspekte (virtueller Speicher):– kurz in Kapitel 4 behandelt

• Jetzt:– Betriebssystemaspekte– Ausführliche Behandlung des Zusammenspiels Hardware /

Betriebssystem


Speicher• Funktion – Aufbewahrung für Programme und Daten

• Organisation – meist eine “Hierarchie”

CPU-Register

Speicher

Befehle/Adressen/./Operanden Programm 1-8 Bytes

BlöckeCache Controller

8-128 Bytes

oben

unten

schnell,klein

langsam,groß

Cache

Festplatte

Seiten Betriebssystem512-4K bytes

Band

Dateien Bnutzer/Operator

Mbytes

Inhalte/StrukturBesitzer/Verwalter

Größe


8.1 Anforderungen an die Speicherverwaltung

Anforderungen an die Speicherverwaltung von der Betriebssystemseite

• Bereitstellung von Speicher für Betriebssystem und Prozesse

• Ziel wg. Mehrprogrammbetrieb (Multiprogramming): Möglichst viele Prozesse im Speicher vorhanden

Anforderungen nach Lister/Eager: Fundamentals of Operating Systems 1. Verlagerbarkeit (relocatability)

2. Schutz (protection)

3. Gemeinsame Nutzung (sharing)

4. Logische Organisation

5. Physikalische Organisation


Verlagerung (relocation)

• Motivation: – Mehrere Prozesse gleichzeitig im System– Auslagern und Wiedereinlagern ganzer Prozesse aus dem

Hauptspeicher ermöglichen– Ort der Einlagerung zum Zeitpunkt der Programmentwicklung /

Programmübersetzung unbekannt!– Bindung an alten Ort beim Wiedereinlagern sehr ungünstig!

) Problem: Speicherreferenzen innerhalb des Programms:– Absolute Sprungbefehle– Datenzugriffsbefehle


Verlagerung (relocation)

• Übersetzung der Speicherreferenzen im Programmcode in physikalische Speicheradressen durch

– Prozessorhardware– Betriebssystemsoftware

• Ausnahme: Paging mit virtuellem Speicher (einfacher Fall ohne dynamisch gebundene Module)

Prozesskontrollblock

Programm

Daten

Beginn Prozesskontrollinformationen

Einsprungstelle ins Programm

Zunehmende Adresswerte

Programmende

Sprung-befehl

Referenz auf Daten


Schutz (Protection)

• Schutz von Prozessen gegen beabsichtigte oder unbeabsichtigte Störungen durch andere Prozesse Überprüfung aller Speicherzugriffe

• Schwierigkeit: Effektive Adresse (berechnet aus Registerinhalten und Offsets z.B. d(An, Ix) ) nicht zur Übersetzungszeit eines Programms überprüfbar.

• Grund:– effektive Adressen werden erst zur Ausführungszeit berechnet– (dynamische) Verlagerung

) Dynamische Überprüfung nötig,

• braucht Hardwareunterstützung,

• wird zusammen mit Verlagerung gelöst.


Gemeinsame Nutzung (Sharing)

• Gemeinsame Nutzung = kontrollierter Zugriff mehrerer Prozesse auf gemeinsam genutzte Bereiche des Speichers

• Anwendungsbeispiele:–Ausführung des gleichen Programms durch eine Reihe von Prozessen )

Code nur einmal im Speicher–Benutzung gemeinsamer Module (z.B. dynamisch gelinkte Bibliotheken)–Kooperation von Prozessen über gemeinsam genutzten Datenspeicher

(„shared memory“)


Logische Organisation

• Hauptspeicher ist lineares Feld von Bytes (Wörtern)

• Dagegen: Logischer Aufbau großer Programme:– Sammlung verschiedener Module– Unabhängig übersetzt; Referenzen erst zur

Laufzeit aufgelöst– Verschiedene Module mit verschiedenem

Schutz (z. B. nur lesen / ausführen)– Gemeinsame Nutzung von Modulen durch

verschiedene Prozesse• Z.B. auch dynamisch gebundene

Bibliotheken

• Betriebssystem muss mit Modulen umgehen können.

Programm A

Programm BCode Daten

schreib-geschützt


Physikalische Organisation

• Hier betrachtet:– 2 Ebenen:

• Hauptspeicher (schnell, teuer, flüchtig)• Hintergrundspeicher (langsam, billig, nicht

flüchtig)

• Grundproblem: Organisation des Informationsflusses zwischen Haupt- und Sekundärspeicher – Prinzipiell möglich: in Verantwortung des

Programmierers

– Aufwändig, erschwert durch Mehrprogrammbetrieb (multiprogramming)

– Deshalb: Verwaltung durch das Betriebssystem

Hauptspeicher

Sekundärspeicher - Festplatte


8.2 Grundlegende Methoden der Speicherverwaltung• Partitionierung

– Für Speicheraufteilung zwischen verschiedenen Prozessen eher veraltetes Konzept

– Betriebssysteminterne Nutzung von Partitionierung

• Paging– Aufteilung des Adressraums in Seiten und virtuelle Adressen– Kombiniert mit Seitenaustausch

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


8.2.1 Partitionierung

• Partitionierung:– Aufteilung des Speichers in Bereiche mit festen Grenzen– Fester, zusammenhängender Teil des Hauptspeichers für

Betriebssystem– Pro Prozess ein zusammenhängender Teil des Speichers

• Verschiedene Varianten:– Statische Partitionierung– Dynamische Partitionierung– Buddy-Verfahren

• Probleme: Speicherverschnitt/Fragmentierung– interne Fragmentierung – innerhalb der zugeteilten Speicherbereiche– externe Fragmentierung – außerhalb der zugeteilten Speicherbereiche


Statische Partitionierung (1)

• Einteilung des Speichers in feste Anzahl von Partitionen

• 2 Varianten: Alle Partitionen mit gleicher Länge Partitionen mit unterschiedlicher Länge

Betriebssystem8 Mbyte

8 Mbyte

8 Mbyte

8 Mbyte

8 Mbyte

8 Mbyte

8 Mbyte

Betriebssystem8 Mbyte

2 Mbyte

4 Mbyte

8 Mbyte

12 Mbyte

16 Mbyte

2 Mbyte


Statische Partitionierung (2)

• Probleme:– Programm zu groß für Partition ) Programmerstellung mit Overlays

nötig (aufwändig und fehleranfällig!)– Interne Fragmentierung: Platzverschwendung, wenn Programm

kleiner als Größe der zugeordneten Partition– Fest vorgegebene Anzahl von Prozessen im Speicher

• Bei Laden von Prozessen in den Speicher: evtl. Auslagern von anderen Prozessen

• Zuweisung von Partitionen an Prozesse:– Bei Bereichen mit gleicher Länge: trivial– Bei Bereichen mit variabler Länge: Kleinste verfügbare Partition die

gerade noch ausreicht?• Wenn Speicherbedarf nicht feststellbar, dann helfen nur Overlays oder

virtueller Speicher!


Dynamische Partitionierung (1)

• Einteilung des Speichers in Partitionen – variabler Länge und – variabler Anzahl

• Prozesse erhalten exakt passende Speicherbereiche

• Ein- und Auslagern führt zu externer Fragmentierung!(vgl. auch Kapitel Dateisysteme)



BS, 8 MB BS, 8 MB

56 MB

Prozess120 MB

36 MB

BS, 8 MB

Prozess120 MB

22 MB

Prozess 214 MB

Prozess 318 MB

BS, 8 MB

Prozess120 MB

4 MB

Prozess 214 MB

Prozess 318 MB

BS, 8 MB

Prozess120 MB

4 MB

Prozess 318 MB

BS, 8 MB

Prozess120 MB

4 MB

P. 4, 8 MB

Prozess 318 MB

BS, 8 MB

4 MB

P. 4, 8 MB

20 MB

Prozess 318 MB

BS, 8 MB

4 MB

P. 4, 8 MB

Prozess 214 MB

6 MB 6 MB 6 MB

6 MB



• Defragmentierung erforderlich!– Aufwändig– Speicherverdichtung nur erfolgreich, wenn dynamische Verlagerung

möglich (Speicherreferenzen werden nicht ungütig!)

• Speicherzuteilungsalgorithmen:– Best Fit:

• Suche kleinsten Block, der ausreicht

– First Fit: • Suche beginnend mit Speicheranfang bis ausreichender Block gefunden

– Next Fit: • Suche beginnend mit der Stelle der letzten Blockzuweisung



• Analyse von Speicherzuteilungsalgorithmen:– Im Schnitt ist First Fit am besten!– Next Fit:

• Etwas schlechter

• Typischer Effekt: Schnelle Fragmentierung des größten freien Speicherblocks am Ende des Speichers

– Best Fit:• Am schlechtesten

• Produziert schnell eine Reihe von sehr kleinen Fragmenten, die ohne Defragmentierung nie mehr benutzt werden können

• Zudem: langsames Verfahren


Buddy-System (1)

• Nachteil statische Partitionierung:– Beschränkte Anzahl nicht-ausgelagerter Prozesse– Interne Fragmentierung

• Nachteil dynamische Partitionierung:– Defragmentierung nötig wegen externer Fragmentierung

• Buddy-System (Halbierungsverfahren): – Kompromiss zwischen statischer und dynamischer Partitionierung– Eigenschaften:

• Anzahl nicht-ausgelagerter Prozesse dynamisch

• Interne Fragmentierung beschränkt

• Keine explizite Defragmentierung


Buddy-System (2)

Prinzip: – Verwalte Speicherblöcke der Größe 2K, L · K · U,

ausgerichtet an nx 2K-Grenzen• 2L = Größe des kleinsten zuteilbaren Blocks• 2U = Größe des größten zuteilbaren Blocks (z.B. Gesamtgröße des

Speichers)

– Zu Beginn:• Es existiert genau ein Block der Größe 2U.• Anforderung eines Blocks der Größe s:

– Bei 2U-1 < s · 2U: Weise gesamten Speicher zu– Sonst: Teile auf in 2 Blöcke der Größe 2U-1

– Bei 2U-2 < s · 2U-1: Weise einen der beiden Blöcke zu– Sonst: Wähle einen der beiden Blöcke aus und teile– …– Fahre fort bis zu Block der Größe 2K mit 2K-1 < s · 2K

• Bei resultierendem Block ist der „Verschnitt“ kleiner als die halbe Blockgröße


Buddy-System (3)

– Verwalte f.a. L · K · U Listen mit freien Blöcken der Größe 2K

– Allgemeiner Fall: Anforderung eines Blocks der Größe 2i-1 < s · 2i:

• Vergebe Block aus Liste i, wenn vorhanden

• Sonst: Wähle Block aus nächst größerer nichtleerer Liste

• Teile rekursiv auf, bis ein Block der Größe 2i vorhanden

– Wenn nach Freigabe eines Blocks der Größe 2K der entsprechende Partnerblock der Größe 2K ebenfalls frei war:

• Verschmelze die Blöcke zu einem Block der Größe 2K+1

• Mache rekursiv mit Verschmelzen weiter


Buddy-System (4)

• Beispiel: – Speicher der Größe 1 GB– Folge von Anforderungen und Freigaben:

• A fordert 100 MB an.

• B fordert 240 MB an.

• C fordert 64 MB an.

• D fordert 256 MB an.

• Freigabe B

• Freigabe A

• E fordert 75 MB an.

• Freigabe C

• Freigabe E

• Freigabe D

1 GB


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 1256 MB: 1128 MB: 1 64 MB: 0

Es folgt Anforderung B: 240 MB, d.h. Block der Größe 256 MB.

A:128MB

Nach Anforderung A: 100 MB, d.h. Block der Größe 128 MB:


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 1256 MB: 0128 MB: 1 64 MB: 0

Nach Anforderung B: 240 MB, d.h. Block der Größe 256 MB.

Es folgt Anforderung C: 64 MB, d.h. Block der Größe 64 MB.

A:128MB B:256MB


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 1256 MB: 0128 MB: 0 64 MB: 1

Nach Anforderung C: 64 MB, d.h. Block der Größe 64 MB.

Es folgt Anforderung D: 256 MB, d.h. Block der Größe 256 MB.

A:128MB B:256MBC:64MB


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 0256 MB: 1128 MB: 0 64 MB: 1

Nach Anforderung D: 256 MB, d.h. Block der Größe 256 MB.

Es folgt Freigabe B.

A:128MB B:256MBC:64MB D:256MB


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 0256 MB: 2128 MB: 0 64 MB: 1

Nach Freigabe B:

Es folgt Freigabe A.

A:128MB C:64MB D:256MB


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 0256 MB: 2128 MB: 1 64 MB: 1

Nach Freigabe A:

Es folgt Anforderung E: 75 MB, d.h. Block der Größe 128 MB.

.

C:64MB D:256MB


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 0256 MB: 2128 MB: 0 64 MB: 1

Nach Anforderung E: 75 MB, d.h. Block der Größe 128 MB:

Es folgt Freigabe C.

.

C:64MB D:256MBE:128MB


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 0256 MB: 2128 MB: 0 64 MB: 2

Bei Freigabe C:

D:256MBE:128MB

„Buddies“


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 0256 MB: 2128 MB: 1 64 MB: 0

Nach Freigabe C:

Es folgt Freigabe E.

.

D:256MBE:128MB


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 0256 MB: 2128 MB: 2 64 MB: 0

Bei Freigabe E:

D:256MB

„Buddies“


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 0256 MB: 3128 MB: 0 64 MB: 0

Bei Freigabe E:

D:256MB

„Buddies“


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 1256 MB: 1128 MB: 0 64 MB: 0

Nach Freigabe E:

D:256MB

Es folgt Freigabe D.

.


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 1256 MB: 2128 MB: 0 64 MB: 0

Bei Freigabe D:

„Buddies“


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 0512 MB: 2256 MB: 0128 MB: 0 64 MB: 0

Bei Freigabe D:

„Buddies“


Buddy-System (5)

1 GB

Freie Blöcke:

1 GB: 1512 MB: 0256 MB: 0128 MB: 0 64 MB: 0

Nach Freigabe D:

Gesamter Speicher wieder als 1 Block verfügbar.


8.2.2 Verlagerung (1)

• Nach Aus- und Wiedereinlagern von Prozessen liegen Programmcode bzw. Daten an anderer Stelle.

• Absolute Sprungbefehle und Datenzugriffsbefehle sollen weiterhin funktionieren.

• Unterscheidung:– Logische Adresse: Bezug auf eine Speicherstelle unabhängig von der

aktuellen Zuteilung von Daten im Speicher– Relative Adresse:

• Spezialfall einer logischen Adresse• Adresse relativ zu einem bekannten Punkt (meist Programmanfang)

ausgedrückt

– Physikalische bzw. absolute Adresse: konkrete Stelle im Hauptspeicher


Verlagerung (2)

• Berechnung von absoluten Adressen aus relativen Adressen durch Hardware.

• Beim Einlagern eines Prozesses:– Adresse des Programmanfangs in Basisregister.– Zusätzlich: Zur Realisierung von Speicherschutz enthält Grenzregister

die höchste erlaubte Speicheradresse – eine Schtzmaßnahme gegen „Pufferüberlauf“ (buffer overflow)

• …


Verlagerung (3)

Prozesskontrollblock

Programm

Daten

Stapel

Prozessabbild im Hauptspeicher

Basisregister

Grenzregister

Addierer

Vergleicher

Relative Adresse

Absolute Adresse

Unterbrechung an Betriebssystem


8.2.3 Seitenadressierung (Paging)

• Seitenadressierung

• Seitenaustauschverfahren mit virtuellem Speicher

• Erfinder:– Fritz-Rudolf Güntsch, Dissertation 1957– Fotheringham, 1961 in ATLAS Computer, Univ. Manchester


Seitenadressierung (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


Seitenadressierung (2)

• Beispiel:

Rahmen-nummer

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Hauptspeicher

0

1

2

3

4

5

6

7

8

9

Hauptspeicher

0

1

2

3

4

5

6

7

8

9

Hauptspeicher

0

1

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.0

A.1

A.2

A.3

A.0

A.1

A.2

A.3

A.0

A.1

A.2

A.3

B.0

B.1

B.2

B.0

B.1

B.2

C.0

C.1

C.2

C.3

Prozess D mit 6 Seiten soll jetzt geladen werden!



• Beispiel:

Rahmen-nummer

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Hauptspeicher

0

1

2

3

4

5

6

7

8

9

Hauptspeicher

Prozess D geladen

10

11

12

13

14

A.0

A.1

A.2

A.3

A.0

A.1

A.2

A.3

C.0

C.1

C.2

C.3

C.0

C.1

C.2

C.3

Prozess B ausgelagert

D.0

D.1

D.2

D.3

D.4

Datenstrukturen zum aktuellen Zeitpunkt:

0

1

2

3

0

1

2

3

Seitentabelle Prozess A

0

1

2

-

-

-

Seitentabelle Prozess B

0

1

2

3

7

8

9

10

Seitentabelle Prozess C

0

1

2

3

4

5

6

11

Seitentabelle Prozess D

4 12

13

14

Liste der freien Rahmen



• 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.– …



• Bsp.: 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:

…

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

6-Bit-Seitennummer 10-Bit-Offset



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


0

1

2

3

1001001010010011

Seitentabelle des Prozesses

1101100111111010

……

……

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

Seitenrahmen Nr. 147 (=<10010011>)

) Reale Adresse:

10010011|0111011110



• 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.)


Seitenadressierung mit virtuellem Speicher (1)• Grundidee:

– Nur Teile der Daten von Prozessen im Hauptspeicher halten.– Programmausführung auf Code und Daten im Speicher.– Bei Zugriff auf ausgelagerte Speicherbereiche muss nachgeladen werden.

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

• Vorteile:– Mehr aktive Prozesse im Speicher () Pseudoparallelismus!)– Tatsächlicher Speicherplatzbedarf eines Prozesses muss nicht von vornherein

feststehen.– Adressraum eines Prozesses kann 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.


Lokalität

• Kann das überhaupt effizient funktionieren?– Antwort: ja!– 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


Lokalität

• Bsp.:


Lokalität

• Seitenaustauschverfahren 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“)


Technische Realisierung

• Technische Realisierung von Seitenaustauschverfahren mit virtuellem Speicher:– Die Daten des Prozesses befinden sich im Hintergrundspeicher

(Festplatte), bei nicht komplett ausgelagerten Prozessen zusätzlich noch Teile im Speicher

– Trennung der logischen Adressen in Seitennummer und Offset, z.B.:

– Im Gegensatz zu nur Seitenadressierung:• Logische Adressen überdecken kompletten virtuellen Adressraum,

z.B. 32-Bit- / 64-Bit-Adressen

– Pro Prozess eine Seitentabelle zur Übersetzung Seitennummer ) Seitenrahmen

0 0 … 0 1 0 1 1 1 0 0 1 1 1 0



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)

0 0 … 0 1 0 1 1 1 0 0 1 1 1 0


P M Weitere Bits Seitenrahmennummer


Adressumsetzung

Seitennr. Offset

Virtuelle Adresse

Seitentabellen-zeiger

Register

Seitentabelle

+Rahmennr.

Sei

tenn

umm

er

Rahmennr. Offset

……

Programm Paging-Verfahren Hauptspeicher

Seiten-rahmen

Off

set

Reale Adresse


Seitentabelle

Seite 7

Seite 6

Seite 5

Seite 4

Seite 3

Seite 2

Seite 1

Seite 0

virtuellerAdressraum

Seitenrahmen 3

Seitenrahmen 2

Seitenrahmen 1

Seitenrahmen 0

Hauptspeicher

Seitentabelle des Prozesses im Hauptspeicher

Rahmennr.Seitennr.0

1

2

3

4

5

6

7

P

0

0

1

0

1

0

0

0

0

3

…

…

…

…

…

…

…

…

…


Seitenfehler

Zugriff auf eine nicht im Hauptspeicher befindliche Seite:– 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: Verdrängen eines belegten Seitenrahmens

» Aktualisierung der Seitentabelle• Danach: Laufendes Programm wird wieder fortgesetzt


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


Seitenfehler

Seite 7

Seite 6

Seite 5

Seite 4

Seite 3

Seite 2

Seite 1

Seite 0

virtuellerAdressraum

Seitenrahmen 3

Seitenrahmen 2

Seitenrahmen 1

Seitenrahmen 0

Hauptspeicher

Seitentabelle des Prozesses im Hauptspeicher

Rahmennr.Seitennr.0

1

2

3

4

5

6

7

P

0

0

1

0

1

0

0

0

0

3

…

…

…

…

…

…

…

…

…

Festplatten-Adresse

A

D

B

X

Y

C

E

F


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

auf die 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ückgeschreiben 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


Verdrängung

Seite 7

Seite 6

Seite 5

Seite 4

Seite 3

Seite 2

Seite 1

Seite 0

virtuellerAdressraum Prozess 1

Seitenrahmen 3

Seitenrahmen 2

Seitenrahmen 1

Seitenrahmen 0

Hauptspeicher

Seitentabelle von Prozess 1

RahmenSeite

0

1

2

3

4

5

6

7

P

0

0

1

0

1

0

0

0

0

3

…

…

…

…

…

…

…

…

…

Seite 7

Seite 6

Seite 5

Seite 4

Seite 3

Seite 2

Seite 1

Seite 0


Seitentabelle von Prozess 1

RahmenSeite

0

1

2

3

4

5

6

7

P

0

0

1

0

0

0

0

0

1

2

…

…

…

…

…

…

…

…

…


Verdrängung

Seite 7

Seite 6

Seite 5

Seite 4

Seite 3

Seite 2

Seite 1

Seite 0


Seitenrahmen 3

Seitenrahmen 2

Seitenrahmen 1

Seitenrahmen 0

Hauptspeicher

Seite 7

Seite 6

Seite 5

Seite 4

Seite 3

Seite 2

Seite 1

Seite 0


1

2

2

1

4

6

2

2

Prozess Seite

3

2

1

0

Rahmen

Abbildung Seitenrahmennummer ) (Prozessnummer, Seitennummer)


Größe von Seitentabellen

• Problem: Größe der Seitentabelle

• Bsp.:– 32-Bit-Adressraum– 20 Bit Seitennummer, 12 Bit Offset

) 220 Seiten der Größe 212 Byte– Seitentabelle mit 220 Zeilen ) 4 MB für Seitentabelle bei 4 Byte pro

Zeile, d.h. 210 Seiten– Für jeden Prozess!– Noch schlimmer bei 64-Bit-Adressraum …

• Abhilfe:– Zweistufige Seitentabellen– „Invertierte Seitentabellen“


Zweistufige Seitentabellen

• „Hierarchische Seitentabelle“ (vgl. Pentium)

• Idee: Speichere auch Seitentabelle im virtuellen Speicher

• Im Beispiel:– 220 Seiten mit jeweils 212 Byte, pro Eintrag 4 Byte ) 222 Byte für

Seitentabelle, d.h. 210 Seiten für Seitentabelle benötigt– Führe „Hauptseite“ (212 Byte) ein, die immer im Speicher liegt.– Hauptseite enthält 210 Verweise auf Seiten der

„Benutzerseitentabelle“, indiziert mit ersten 10 Bit der Adresse– Wenn gesuchte Seite der Benutzerseitentabelle nicht im Speicher:

Lade in einen freien Seitenrahmen– Benutze 10 mittlere Bit, um in „Untertabelle“ den gesuchten

Seitenrahmen zu finden (evtl. Nachladen von Festplatte)– Restliche 12 Bit wie üblich als Offset innerhalb des Seitenrahmens


Adressumsetzung

10 Bit 12 Bit

Virtuelle Adresse

Hauptseiten-tabellenzeiger

Register

Hauptseitentabelle (210 Einträge)

+

Rahmennr. Offset

……

Programm Paging-Verfahren Hauptspeicher

Seiten-rahmen

Reale Adresse

+

10 Bit

Untertabelle (210 Einträge)


Invertierte Seitentabellen

• Siehe Power PC, IBM AS/400• Beobachtung:

– Sei n die Zahl der Seiten im virtuellen Adressraum, m die Zahl der einem Prozess zugeordneten Seitenrahmen. Dann ist üblicherweise n >> m.

) Seitentabellen sind meist nur sehr dünn besetzt

– Seitentabelle zur Abbildung Seitennummer ! Seitenrahmennummer verschwendet Speicherplatz.

• Allgemeines Problem:– Gegeben Schlüssel k1, …, km 2 {0, …, n-1} oder allgemein k1, …, km 2 U mit |U|

= n.

– Gesucht ist eine Methode, die jedem Schlüssel ki einen Wert vi zuordnet.

– Die Zuordnung soll speicher- und laufzeiteffizient sein.


Translation Lookaside Buffer (TLB)

Seitennr. Offset

Virtuelle Adresse

Seitentabelle

Rahmennr. Offset…

…

Seiten-rahmen

Off

set

Reale Adresse

TLB

TLB-Fehlschlag

……

{

}

}

Seitenfehler

TLB-Treffer

Seite laden

Hauptspeicher Sekundärspeicher



• Der TLB ist ein Hardware-Cache.

• Meist realisiert als assoziativer Speicher:– Einträge der Form (Seitennummer, Seitentabelleneintrag)– Angefragte Seitennummer wird durch Hardware parallel mit allen

Einträgen in TLB verglichen.– Ausgabe:

• Vorhanden, Seitentabelleneintrag

• Nicht vorhanden

– Bei Eintrag: Verdrängungsstrategien notwendig …– Teuerste Realisierungsmöglichkeit eines Caches!



5 502

Virtuelle Adresse

Adressumsetzungspuffer

Seitennr. Offset

5

19

128

1

90

…

37

…

Seitennr.Seitentabellen-

einträge

37 502

Reale AdresseRahmennr. Offset


TLB und Caches

• Zusätzlich noch Caches für Programme und Daten:– Caches für Programme und Daten

sind TLB / MMU nachgeschaltet.– Verwenden physikalische

Adressen.

MMU

virtuelle Adresse

physikalische Adresse

Cache

Hauptspeicher


Virtuelle Cache-Adressierung

• Alternative: Cache mit der virtuellen Adresse adressieren.

• Vorteil: – Adressumsetzung und

Cachezugriff parallel

• Nachteil:– Verschiedene Prozesse benutzen gleiche virtuelle

Adresse für verschiedene reale Adressen.) Daten- / Programmcache bei Prozesswechsel ungültig– Abhilfe bei Single-Prozessor-Umgebungen:

• Trage zusätzlich zur virtuellen Adresse auch PID (process identifier)-Tag ein

• Schwierig in Zusammenhang mit Konsistenz von Caches bei Multiprozessoren

) Meist physikalische Cache-Adressierung verwendet.

MMU

virtuelle Adresse

physikalische Adresse

Cache

Hauptspeicher


Seitengröße

• Wahl der Seitengröße sehr wichtig für Systemleistung• Kleine Seiten:

– Wenig „Verschnitt“ (interne Fragmentierung)

• Große Seiten:– Kleinere Seitentabellen, weniger Verwaltungsaufwand

• „Moderne“ Probleme:– Objektorientierte Techniken mit vielen kleinen, verstreuten Programm-

und Datenmodulen ) Schwächung der Lokalität – Multithreading-Anwendungen wirken Lokalität entgegen.

• In Realität: Seitengrößen um 4 Kbyte, teilweise auch variierbar (z.B. Pentium bis 4 Mbyte)


8.2.4 Segmentierung

• Im Gegensatz zu Partitionierung werden Prozessen nicht notwendigerweise zusammenhängende Speicherbereiche zugeordnet.

• Speicher eines Prozesses aufgeteilt in Segmente, deren Größe im Gegensatz zu den Seiten beim Paging verschieden sein kann.

• Keine interne Fragmentierung, aber externe Fragmentierung (wie bei dynamischer Partitionierung.

• Segmentierung ist für Programmierer / Übersetzer sichtbar.• Aufteilung in Codesegmente, Datensegmente, …

• Einfache Segmentierung: Prozesse sind entweder ganz im Speicher oder komplett ausgelagert.


Segmentierung

• Logische Adresse besteht aus Segmentadresse und Offset.• Berechnung der realen Adresse durch Addition von

– Basisadresse des Segments

– Offset

• Segmenttabelle enthält pro Segment– Basisadresse des Segments (Startadresse im Speicher)

– Segmentlänge


Segmentierung

• Bsp.: logische Adresse mit 16 Bit

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

4-Bit-Segmentnummer 12-Bit-Offset

001011101110 0000010000000000

011110011110 0010010000100000

000110010100 0011010100000000

0

1

2

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

+

16-Bit physikalische Adresse

Länge Basis

Prozesssegmenttabelle


Segmentierung

• Segmentierung mit virtuellem Speicher– Nicht alle Segmente eines nicht komplett ausgelagerten Prozesses

müssen im Speicher vorhanden sein.– Restliche Segmente auf Festplatte– Segmenttabelleneintrag:

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

• Schutz und gemeinsame Nutzung auf Segmentbasis einfach zu regeln

• Größe der Segmente unterschiedlich und dynamisch festlegbar• Bei Segmentvergrößerung:

– Allokieren von nachfolgendem Speicher oder– Verschiebung in einen größeren freien Bereich oder– Auslagerung

P M Weitere Bits Länge Basis


8.2.5 Seiten und Segmente

• Vorteile Paging: – Für den Nutzer transparent– Feste Seitengrößen ) leistungsfähige Speicherverwaltungsalgorithmen

• Vorteile Segmentierung:– Anpassung an dynamischen Speicherbedarf von Prozessen– Gemeinsame Nutzung und Schutz auf Grundlage „natürlicher

Organisationseinheiten“

) Kombination beider Verfahren:– Prozesse aufgeteilt in Segmente, pro Prozess eine Segmenttabelle– Segmente aufgeteilt in Seiten, pro Segment eine Seitentabelle

• Aufbau einer Adresse:– Für den Programmierer besteht Adresse aus Segmentnummer und

OffsetSegmentierung.– OffsetSegmentierung wird beim Paging interpretiert als (Seitennummer,

OffetPaging).


Segmentierung und Paging kombiniert -Adressumsetzung

Seg-mentnr

Off-set

Virtuelle Adresse

Segment-tabellenzeiger

Register

Segmenttabelle

+

Rahmennr. Offset

……

Programm Paging Hauptspeicher

Seiten-rahmen

Reale Adresse

+

Seiten-nr.

Seitentabelle

Segmentierung


Betriebssystemaufgaben bei Speicherverwaltung• Festlegung verschiedener Strategien:

– Abrufstrategie (Fetch Policy) - Wann wird eine Seite in den Hauptspeicher geladen?

• „Demand Paging“• „Prepaging“

– Speicherzuteilungsstrategie (Placement Policy): Wo im Speicher wird ein Prozessteil abgelegt?

• Nur wichtig bei Segmentierung / Partitionierung, nicht bei Paging• Z.B. Best-Fit, Next-Fit, First-Fit

– Austauschstrategie (Replacement Policy):Welche Seite soll ausgelagert werden, wenn alle Seitenrahmen belegt sind?

• Gesperrte Seiten sind ausgenommen!• Vielzahl von Verfahren, z.B.

– LRU (Least Recently Used) – FIFO (First In First Out)– Clock-Algorithmus

• Strategien arbeiten auf der Grundlage von Daten, die durch die Hardware gesammelt werden müssen.


• Festlegung verschiedener Strategien:– Strategie zur Verwaltung des „Resident Set“:

Welchem Prozess wird wie viel Platz im Hauptspeicher zugeteilt?• Feste oder variable Zuteilung von Speicher an Prozesse• Variable Zuteilung meist auf Grundlage der Seitenfehlerrate (mit

Hardwareunterstützung gemessen / abgeschätzt)• Lokale oder globale Austauschstrategie (nur Seiten des eigenen Prozesses

ausgelagert oder auch von anderen)

– Cleaning-Strategie:Wann lagert man eine geänderte Seite in den Sekundärspeicher aus?

• Demand Cleaning• Precleaning (Motivation: Schreiben mehrerer Seiten in Gruppen)

– Strategie zur Lastkontrolle:Wieviele Prozesse werden gleichzeitig zugelassen (teilweise im Speicher)

• Ab welcher Zahl von Prozessen beginnt man mit Suspendieren von Prozessen?• Welche Prozesse werden suspendiert?

Betriebssystemaufgaben bei Speicherverwaltung


Zusammenfassung

• Speicherverwaltungsstrategien sind extrem wichtig die Effizienz des Gesamtsystems.

• Moderne Betriebssysteme arbeiten mit virtuellem Speicher.

• Lokalität ist die Grundvoraussetzung für das effiziente Funktionieren virtueller Speicherkonzepte.– In der Praxis meist vorhanden.

• Paging unterteilt den Speicher in viele gleich große Teile.

• Segmentierung unterteilt in verschieden große Teile, deren Größe variabel ist.

• Es ist auch möglich, Paging und Segmentierung zu kombinieren.

Documents

RW-SystemarchitekturKap. 8 1 Kapitel 8 Speicherverwaltung