Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | porsche-gehringer |
View: | 146 times |
Download: | 1 times |
RW-Systemarchitektur Kap. 81
Kapitel 8Speicherverwaltung
RW-Systemarchitektur Kap. 82
Ü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
RW-Systemarchitektur Kap. 83
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
RW-Systemarchitektur Kap. 84
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
RW-Systemarchitektur Kap. 85
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
RW-Systemarchitektur Kap. 86
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
RW-Systemarchitektur Kap. 87
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
RW-Systemarchitektur Kap. 88
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.
RW-Systemarchitektur Kap. 89
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“)
RW-Systemarchitektur Kap. 810
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
RW-Systemarchitektur Kap. 811
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
RW-Systemarchitektur Kap. 812
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
RW-Systemarchitektur Kap. 813
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
RW-Systemarchitektur Kap. 814
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
RW-Systemarchitektur Kap. 815
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!
RW-Systemarchitektur Kap. 816
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)
RW-Systemarchitektur Kap. 817
Dynamische Partitionierung (2)
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
RW-Systemarchitektur Kap. 818
Dynamische Partitionierung (3)
• 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
RW-Systemarchitektur Kap. 819
Dynamische Partitionierung (4)
• 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
RW-Systemarchitektur Kap. 820
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
RW-Systemarchitektur Kap. 821
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
RW-Systemarchitektur Kap. 822
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
RW-Systemarchitektur Kap. 823
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
RW-Systemarchitektur Kap. 825
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:
RW-Systemarchitektur Kap. 826
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
RW-Systemarchitektur Kap. 827
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
RW-Systemarchitektur Kap. 828
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
RW-Systemarchitektur Kap. 829
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
RW-Systemarchitektur Kap. 830
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
RW-Systemarchitektur Kap. 831
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
RW-Systemarchitektur Kap. 832
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“
RW-Systemarchitektur Kap. 833
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
RW-Systemarchitektur Kap. 834
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“
RW-Systemarchitektur Kap. 835
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“
RW-Systemarchitektur Kap. 836
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.
.
RW-Systemarchitektur Kap. 837
Buddy-System (5)
1 GB
Freie Blöcke:
1 GB: 0512 MB: 1256 MB: 2128 MB: 0 64 MB: 0
Bei Freigabe D:
„Buddies“
RW-Systemarchitektur Kap. 838
Buddy-System (5)
1 GB
Freie Blöcke:
1 GB: 0512 MB: 2256 MB: 0128 MB: 0 64 MB: 0
Bei Freigabe D:
„Buddies“
RW-Systemarchitektur Kap. 839
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.
RW-Systemarchitektur Kap. 840
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
RW-Systemarchitektur Kap. 841
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)
• …
RW-Systemarchitektur Kap. 842
Verlagerung (3)
Prozesskontrollblock
Programm
Daten
Stapel
Prozessabbild im Hauptspeicher
Basisregister
Grenzregister
Addierer
Vergleicher
Relative Adresse
Absolute Adresse
Unterbrechung an Betriebssystem
RW-Systemarchitektur Kap. 843
8.2.3 Seitenadressierung (Paging)
• Seitenadressierung
• Seitenaustauschverfahren mit virtuellem Speicher
• Erfinder:– Fritz-Rudolf Güntsch, Dissertation 1957– Fotheringham, 1961 in ATLAS Computer, Univ. Manchester
RW-Systemarchitektur Kap. 844
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
RW-Systemarchitektur Kap. 845
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!
RW-Systemarchitektur Kap. 846
Seitenadressierung (3)
• 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
RW-Systemarchitektur Kap. 847
Seitenadressierung (4)
• 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.– …
RW-Systemarchitektur Kap. 848
Seitenadressierung (5)
• 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
RW-Systemarchitektur Kap. 849
Seitenadressierung (6)
0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0
6-Bit-Seitennummer 10-Bit-Offset
0
1
2
3
1001001010010011
Seitentabelle des Prozesses
1101100111111010
……
……
Speicherzelle Nr. 478 (= <0111011110>) innerhalb des Seitenrahmens.
Seitenrahmen Nr. 147 (=<10010011>)
) Reale Adresse:
10010011|0111011110
RW-Systemarchitektur Kap. 850
Seitenadressierung (7)
• 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.)
RW-Systemarchitektur Kap. 851
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.
RW-Systemarchitektur Kap. 852
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
RW-Systemarchitektur Kap. 853
Lokalität
• Bsp.:
RW-Systemarchitektur Kap. 854
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“)
RW-Systemarchitektur Kap. 855
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
22-Bit-Seitennummer 10-Bit-Offset
RW-Systemarchitektur Kap. 856
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
22-Bit-Seitennummer 10-Bit-Offset
P M Weitere Bits Seitenrahmennummer
RW-Systemarchitektur Kap. 857
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
RW-Systemarchitektur Kap. 858
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
…
…
…
…
…
…
…
…
…
RW-Systemarchitektur Kap. 859
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
RW-Systemarchitektur Kap. 860
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
RW-Systemarchitektur Kap. 861
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
RW-Systemarchitektur Kap. 862
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
RW-Systemarchitektur Kap. 863
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
virtuellerAdressraum Prozess 2
Seitentabelle von Prozess 1
RahmenSeite
0
1
2
3
4
5
6
7
P
0
0
1
0
0
0
0
0
1
2
…
…
…
…
…
…
…
…
…
RW-Systemarchitektur Kap. 864
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
Seite 7
Seite 6
Seite 5
Seite 4
Seite 3
Seite 2
Seite 1
Seite 0
virtuellerAdressraum Prozess 2
1
2
2
1
4
6
2
2
Prozess Seite
3
2
1
0
Rahmen
Abbildung Seitenrahmennummer ) (Prozessnummer, Seitennummer)
RW-Systemarchitektur Kap. 865
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“
RW-Systemarchitektur Kap. 866
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
RW-Systemarchitektur Kap. 867
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)
RW-Systemarchitektur Kap. 868
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.
RW-Systemarchitektur Kap. 872
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
RW-Systemarchitektur Kap. 873
Translation Lookaside Buffer (TLB)
• 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!
RW-Systemarchitektur Kap. 874
Translation Lookaside Buffer (TLB)
5 502
Virtuelle Adresse
Adressumsetzungspuffer
Seitennr. Offset
5
19
128
1
90
…
37
…
Seitennr.Seitentabellen-
einträge
37 502
Reale AdresseRahmennr. Offset
RW-Systemarchitektur Kap. 875
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
RW-Systemarchitektur Kap. 876
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
RW-Systemarchitektur Kap. 877
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)
RW-Systemarchitektur Kap. 878
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.
RW-Systemarchitektur Kap. 879
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
RW-Systemarchitektur Kap. 880
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
RW-Systemarchitektur Kap. 881
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
RW-Systemarchitektur Kap. 882
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).
RW-Systemarchitektur Kap. 883
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
RW-Systemarchitektur Kap. 884
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.
RW-Systemarchitektur Kap. 885
• 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
RW-Systemarchitektur Kap. 886
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.