41
Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/10 1

Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Embed Size (px)

Citation preview

Page 1: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Systeme 1

Kapitel 8Speicherverwaltung

WS 2009/10 1

Page 2: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

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 2

Page 3: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Prozesse

WS 2009/10 3

Prozesstabelle

Hauptspeicher

CPU

Page 4: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Speicher• Die ersten Computer wurden als Einheit entwickelt.– Speicher, CPU, etc. wurden aufeinander abgestimmt

entwickelt.– Keine großen Geschwindigkeitsunterschiede zwischen den

Komponenten.• Später standardisiertes Design– Erlaubte getrennte und spezialisierte Entwicklung

einzelner Subsysteme.– Manche Subsysteme konnten schneller und besser

optimiert werden als andere.Engpässe („Flaschenhals“) entstanden.

• insbesondere zwischen CPU und Speicher

WS 2009/10 4

Page 5: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Speicherhierarchie

WS 2009/10 5

Registers

Cache

Memory

Disk

Tape

Instr./Operands

Blocks

Pages

Files

Upper Level

Lower Level

faster

larger

Page 6: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Anforderungen an das Betriebssystem

• Grundlegende Anforderungen an Speicherverwaltung:– Bereitstellung von Speicher für Betriebssystem und Prozesse– Ziel aus Betriebssystemsicht:

• Möglichst viele Prozesse im Speicher vorhanden. Multiprogramming!

• 5 Anforderungen nach Lister / Eager: 1. Relokation2. Schutz3. Gemeinsame Nutzung4. Logische Organisation5. Physikalische Organisation

WS 2009/10 6

Page 7: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Relokation• Relokation = „Verlagerbarkeit“• Motivation:

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

Hauptspeicher soll ermöglicht werden.– 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

WS 2009/10 7

Page 8: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Relokation

• Übersetzung der Speicherreferenzen im Programmcode in tatsächliche physikalische Speicheradressen durch– Prozessorhardware– Betriebssystemsoftware

WS 2009/10 8

Prozesskontrollblock

Programm

Daten

Beginn Prozesskontrollinformationen

Sprung-befehl

Referenzauf Daten

ZunehmendeAdresswerte

Einsprungstelle ins Programm

Programmende

Page 9: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Schutz• Schutz von Prozessen gegen beabsichtigte oder

unbeabsichtigte Störungen durch andere Prozesse– Folge: Überprüfung aller Speicherzugriffe notwendig– Schwierigkeit: Nicht zur Übersetzungszeit eines

Programms überprüfbar, da:• Dynamisch berechnete Adressen• Relokation

Dynamische Überprüfung nötig• Hardwareunterstützung nötig• In Zusammenhang mit Relokation gelöst.

• Nicht in ausschließlich Software lösbar– Betriebssystem benötigt für effektiven Schutz

Hardwareunterstützung.

WS 2009/10 9

Page 10: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Exkurs: User-/ Kernel-Modell

• Ein sogenannter Prozessor-Ring schränkt nutzbare Prozessor-Befehle und Speicherbereiche ein.

• z.B. x86 Prozessoren haben 4 Ringe• Meist werden nur 2 genutzt:– Ring 0 (Kernel-Mode)– Ring 3 (User-Mode)

• Kontrollierter Wechsel– durch Betriebssystem (später mehr!)

WS 2009/10 10

Page 11: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Gemeinsame Nutzung• 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“)

WS 2009/10 11

Page 12: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

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.

WS 2009/10 12

Page 13: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

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 Multiprogramming– Deshalb: Verwaltung durch das Betriebssystem

WS 2009/10 13

Page 14: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

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 14

Page 15: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

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

WS 2009/10 15

Page 16: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Statische Partitionierung

• Einteilung des Speichers in feste Anzahl von Partitionen• 2 Varianten:

WS 2009/10 16

Betriebssystem8 Mbyte

8 Mbyte

8 Mbyte

8 Mbyte

8 Mbyte

8 Mbyte

8 Mbyte

Betriebssystem8 Mbyte2 Mbyte2 Mbyte4 Mbyte

8 Mbyte

12 Mbyte

16 Mbyte

Alle Partitionen mit gleicher Länge Partitionen mit unterschiedlicher Länge

Page 17: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Statische Partitionierung• Probleme:– Programm zu groß für Partition Programmerstellung durch Overlays nötig (aufwändig!)– Interne Fragmentierung: Platzverschwendung, wenn

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

• Bei Laden von Prozessen in 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!WS 2009/10 17

Page 18: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Dynamische Partitionierung

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

WS 2009/10 18

Page 19: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Dynamische Partitionierung

WS 2009/10 19

BS, 8MB

56 MB

BS, 8MB

36 MB

Prozess 120 MB

BS, 8MB

22MB

Prozess 120 MB

Prozess 214MB

BS, 8MB

4 MB

Prozess 120 MB

Prozess 214MB

Prozess 318 MB

BS, 8MB

4 MB

Prozess 120 MB

Prozess 318 MB

BS, 8MB

4 MB

Prozess 120 MB

6 MBProzess 3

18 MB

P. 4, 8MB

BS, 8MB

4 MB

Prozess 120 MB

6 MBProzess 3

18 MB

P. 4, 8MB

BS, 8MB

4 MB

Prozess 214 MB

6 MBProzess 3

18 MB

P. 4, 8MB6 MB

Page 20: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Dynamische Partitionierung• Defragmentierung erforderlich!

– Aufwändig– Speicherverdichtung nur erfolgreich, wenn dynamische

Relokation möglich (Speicherreferenzen werden nicht ungültig!)

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

WS 2009/10 20

Page 21: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Dynamische Partitionierung• 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

WS 2009/10 21

Page 22: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System• 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

WS 2009/10 22

Page 23: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System• Prinzip: – Verwalte Speicherblöcke der Größe 2K, L ≤ K ≤ U

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

WS 2009/10 23

Page 24: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System• 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ächstgröß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.

WS 2009/10 24

Page 25: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System• 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

Annahme:Obergrenze der Blockgröße: 1 GB, Untergrenze: 64 MBWS 2009/10 25

Page 26: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 26

1 GB

Freie Blöcke:

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

Zunächst verfügbar:

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

Page 27: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 27

1 GB

Freie Blöcke:

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

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

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

A: 128 MB

Page 28: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 28

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.

B: 256 MBA: 128 MB

Page 29: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 29

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.

B: 256 MBA: 128 MB C:64MB

Page 30: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 30

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.

B: 256 MBA: 128 MB C:64MB D: 256 MB

Page 31: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 31

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: 128 MB C:64MB D: 256 MB

Page 32: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 32

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: 256 MB

Page 33: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 33

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.

D: 256 MBE: 128 MB C:64MB

Page 34: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 34

1 GB

Freie Blöcke:

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

Bei Freigabe C:D: 256 MBE: 128 MB

„Buddies“

Page 35: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 35

1 GB

Freie Blöcke:

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

Nach Freigabe C:D: 256 MBE: 128 MB

Es folgt Freigabe E.

Page 36: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 36

1 GB

Freie Blöcke:

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

Bei Freigabe E:D: 256 MB

„Buddies“

Page 37: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 37

1 GB

Freie Blöcke:

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

Bei Freigabe E:D: 256 MB

„Buddies“

Page 38: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 38

1 GB

Freie Blöcke:

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

Nach Freigabe E:D: 256 MB

Es folgt Freigabe D.

Page 39: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 39

1 GB

Freie Blöcke:

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

Bei Freigabe D:

„Buddies“

Page 40: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 40

1 GB

Freie Blöcke:

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

Bei Freigabe D:

„Buddies“

Page 41: Systeme 1 Kapitel 8 Speicherverwaltung WS 2009/101

Buddy-System

WS 2009/10 41

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.