Folien

Zwei Möglichkeiten die TLB zu aktualisieren
Die MMU kümmert sich um alles (Hardware-Lösung)
•
sucht die p-Entry
•
wenn diese nicht da ist, behandelt direkt das TLB-miss
•
zum Schluss wird die neue p-Entry (virt.→phys. mapping) in der in
das TLB eingetragen.
Die TLB wird direkt vom Betriebssystem verwaltet (Software-Lösung)
•
ein TLB-miss verursacht ein Trap und wird vom Betriebssystem
behandelt.
•
Das Betriebssystem sucht und ladet die neue p-Entry ins TLB.
M. Esponda-Argüero
49
Was passiert, wenn ein Prozess gestartet wird?
Prozess (p) = n Seiten
if at least n frames in VM available
allocate n frames for p
load one page of p in main memory
put the entry on the page table of p
...
else
???????
Es gibt meistens eine Seitentabelle pro Prozess
M. Esponda-Argüero
50
Speicherschutz
valid-invalid bit
Mit Hilfe eines Bits pro Frame wird Speicherschutz gewährleistet.
valid =
gültiger Speicherzugriff, weil die Adresse im ProzessAdressraum ist.
invalid = die Adresse ist nicht im Prozess-Adressraum.
Seitengröße = 2048
00000
Seite 0
Valid-invalidBit
0
Seite 0
1
Seite 0
2
Seite 1
Seite 2
0 1
v
3
1 2
v
4
Seite 2
2 3
v
5
Seite 3
Seite 3
3 5
v
6
Seite 4
4 6
v
.
Seite 1
10232
FrameNummer
Seite 4
5
0 i
.
6
0 i
.
7
0 i
.
.
.
Seitentabelle
address-space identifiers (ASIDs)
M. Esponda-Argüero
Verwendung gemeinsamer Seiten (pages)
- Besonders gut geeignet für Timesharing-Systeme
- Seiten von gemeinsamen Programmen wie z.B.
- Windows-System
- Datenbank-Systeme,
- IPC
- Texteditoren
- Übersetzer, usw.
- müssen immer im gleichen Speicherbereich stehen
- Privater Programmkode und Daten
- kann in beliebigem Speicherbereich stehen
M. Esponda-Argüero
52
Verwendung gemeinsamer Seiten (pages)
Editor 1
Editor 2
Editor 3
Daten 1
.
.
.
Seitentabelle
von P1
3
4
6
1
Editor 2
Editor 3
Daten 3
.
.
.
Editor 2
Editor 3
Daten 2
3
4
6
Seitentabelle
von P2
Prozess P2
1
Daten 1
2
Daten 3
3
Editor 1
4
Editor 2
5
3
4
6
7
Seitentabelle
von P3
2
Prozess P3
Editor 1
.
.
.
Prozess P1
Editor 1
0
6
Editor 3
7
Daten 2
8
9
10
11
12
physikalischer
Speicher
M. Esponda-Argüero
Verwendung gemeinsamer Seiten (pages)
Stapel
Stapel
gemeinsame
Bibliotheken
gemeinsame
Bibliotheken
⇒
gemeinsame
⇒
Bibliotheken
Heap
Heap
Data
Data
Code
Code
Seiten von gemeinsamen Bibliotheken
M. Esponda-Argüero
54
Struktur von Seitentabellen
Programme werden ständig größer und entsprechend die
Seitentabellen auch.
Die meisten modernen Rechner stellen einen sehr großen
logischen Adressraum zur Verfügung ( 2 32 bis 2 64 ).
Wie viele Seiten?
2 32 ⇒
4GB
= 1, 048, 576 Seiten
4KB
Es gibt drei Lösungen:
- Die Seitentabellen selber werden in Seiten (pages) geteilt
- Hashtabellen werden verwendet
- invertierte Seitentabellen (inverted page table)
M. Esponda-Argüero
55
Hierarchische Seitentabellen
Moderne Rechner arbeiten mit einem Adressraum zwischen
232 und 264
Beispiel
Mit einem Adressraum =
Seitengröße =
Tabellengröße =
232
4 KB = 212
220 Einträge
Wenn ein Tabelleneintrag = PTE = 4 Bytes
Seitentabelle = 4 MB
100 Prozesse = 400 MB nur für die Seitentabellen!
zu groß!
M. Esponda-Argüero
56
Hierarchische Seitentabellen
Die Seitentabellen selber werden in Seiten geteilt.
Seitentabelle
Seite der
Seitentabelle
Seitentabelle
Speicher
Bildquelle: Silverschatz, Galvin und Gagne
Hierarchische Seitentabellen
Seitentabellen
0
1
2
..
.
page table #
3
page frame #
4
5
6
Seitentabelle der
Seitentabelle
..
.
7
physikalischer
Adresse
frame #
d
frame # + d
8
9
10
11
12
p1
p2
d
physikalischer
Speicher
logische Adresse
M. Esponda-Argüero
58
Beispiel einer zweistufigen Seitenhierarchie

Eine logische Adresse mit 32 Bits wird wie folgt geteilt :
• 22 Bits für die Seitennummer
• 10 Bits für die Verschiebung (Page Offset)

Die Seitentabelle selber ist geteilt:
• 12 Bits Seitennummer in der Seitentabelle
• 10 Bits Seiten-Offset innerhalb der Seitentabelle

Eine logische Adresse sieht wie folgt aus:
page number
page offset
p1
p2
d
12
10
10
wo p1 der Index in der ersten Seitentabelle und p2 die
Verschiebung innerhalb der Seite der äußeren Seitentabelle ist.
M. Esponda-Argüero
59
Beispiel einer zweistufigen Seitenhierarchie
p1
p2
d
p1
+
p2
+
d
Seitentabelle der
Seitentabelle
Seitentabelle
M. Esponda-Argüero
60
CPU
p1
p2
d
Beispiel einer zweistufigen Seitenhierarchie
p1
+
TLB miss
p2
+
d
p1
p2
+
f
TLB hit
TLB
M. Esponda-Argüero
61
232
Eine gute Teilung ist:
4KB
Seitengroße
4KB
p1
p2
d
10
10
12
Beispiel einer dreistufigen Seitenhierarchie
ab 264
schlecht!
besser
noch zu groß!
M. Esponda-Argüero
62
Seitentabellen mit Hilfe von Hash-Funktionen
Werden oft verwendet mit Adressräumen größer als 32 Bits
Eine logische Seitennummer wird mit Hilfe einer Hash-Funktion in
der Seitentabelle abgebildet. An dieser Position der Tabelle hängt
eine verkettete Liste von Elementen, die zur selben Seitennummer
abgebildet werden.
Die logische Seitennummer wird dann mit den Elementen der Liste
verglichen. Wenn die Seitennummer in der Liste ist, wird die
entsprechende Frame-Nummer gewählt.
M. Esponda-Argüero
63
Seitentabellen mit Hilfe von Hash-Funktionen
logische Adresse
p
d
r
physikalische
Adresse
d
Hashtabelle
HashFunktion
q s
p r
physikalischer
Speicher
t
u
NULL
M. Esponda-Argüero
Inverted Page Table
Nur eine Seitentabelle existiert für das gesamte System.
Einen Speichereintrag für jede reale Speicherseite.
Die Prozess ID wird in die Tabelle gespeichert.
Es wird insgesamt weniger Speicherplatz für die
Prozesstabellen verbraucht, aber die Zeit zum Suchen in der
Tabelle wird größer.
Eine Hashtabelle wird verwendet, um die Suche zu
beschleunigen.
Beispiele:
64-Bit UltraSPARC und PowerPC
M. Esponda-Argüero
65
Invertierte Seitentabelle
Logische Adresse
CPU
pid
p
d
i
d
physikalische
Adresse
physikalischer
Speicher
Suche
i
pid
p
Seitentabelle
M. Esponda-Argüero
66
Invertierte Seitentabelle
Logische Adresse
CPU
pid
p
j
d
Verkettung
d
physikalische
Adresse
physikalischer
Speicher
HashFunktion
p
pid
j
Seitentabelle
M. Esponda-Argüero
67
Was ist die beste Seitengröße?
Kleine Seiten
kleine interne Fragmente,
aber große Seitentabellen
Große Seiten
Nehmen wir an:
große interne Fragmente,
aber kleine Seitentabellen
p = Länge des logischen Adressraums des Prozesses und
s
= Seitenlänge
Dann ist
p/s = Länge der Seitentabelle
s/2 = mittlere Größe des internen Fragments (nur in der letzten Seite)
Der relative Speicherverlust V ist
V = (p/s + s/2)/p
Daraus folgt durch Minimierung:
Optimale Seitengröße = 2 p
M. Esponda-Argüero
68
Page Table Entries (PTEs)
Mikroprozessor-Architektur abhängig
V
Valid-Bit
Befindet sich die Seite im Hauptspeicher?
M
Modify-Bit
Ist die Seite verändert worden?
R
Reference-Bit
Ist die Seite verwendet worden (read/written)
prot
Protection-Bits Ist die Seite lesbar, veränderbar oder ausführbar?
page frame number
Physikalische Adresse im Hauptspeicher (RAM)
M. Esponda-Argüero
69
Segmentierung
Segmentierung ist ein Speicherverwaltungsschema, das
die logische Sichtweise des Benutzers unterstützt.
Programme werden in logische Segmente geteilt.
Beispiel:
Hauptprogramm
Funktion
Methode
Objekte
lokale + globale Variablen
Datenstrukturen
Standard C-Bibliothek
usw.
M. Esponda-Argüero
70
Programm aus der Sichtweise eines Benutzers
Hauptprogramm
Stapel
Symboltabelle
Standard
Bibliothek
Funktion 1
Objekt 2
logischer Adressraum
M. Esponda-Argüero
71
Segmentierung aus einer logischen Benutzersichtweise
1
4
1
2
2
3
4
3
Benutzer-Adressraum
Physikalischer Adressraum
M. Esponda-Argüero
72
Segmentierung aus logischer Benutzersichtweise

Eine logische Adresse ist ein zweistelliges Tupel:
<Seitennummer, Offset>


Segmenttabelle – Jeder Segmenttabelleneintrag hat:
•
•
Base
= Start der physikalischen Adresse des Segments
im Speicher.
Grenze = Größe des Segments.

Segment Table Base Register (STBR) = Zeiger auf die
Segmenttabelle des Speichers.

Segment Table Length Register (STLR) =Anzahl der
Segmente, die im Programm verwendet werden.
Eine Segmentnummer s ist legal, wenn s < STLR
M. Esponda-Argüero
73
Speicherschutz
Jeder Segmenteintrag in der Tabelle hat:
validation bit = 0 ⇒ illegales Segment
read/write/execute Zugriffsrechte
Die Segmente haben Schutzbits.
Gemeinsame Codeverwendung auf Segment-Ebene.
Weil Segmente verschiedene Größen haben, ist
dynamische Speicherallokation ein Problem.
M. Esponda-Argüero
74
Hardwareunterstützung für Segmentierung
s
limit
base
physikalischer
Speicher
Segmenttabelle
CPU
s
d
<
ja
+
Speicherzugriff
nein
Ausnahmefehler (trap)
M. Esponda-Argüero
75
Hardwareunterstützung für Segmentierung
physikalischer Speicher
Hauptprogramm
0
Segment 0
Stapel
Objekt 2
Segment 2
Symboltabelle
Segment 1
Funktion 1
Standard
Bibliothe
k
1
2
3
4
5
6
limit base
2000 1000
500 4000
1500
6000
.
.
.
.
.
.
7
1000
Segment 0
3000
4000
4500
6000
Segmenttabelle
Segment 1
Segment 2
7500
logischer Adressraum
M. Esponda-Argüero
76
Das Intel-Pentium
Die Hardware-Architektur des Intel-Pentium-CPU unterstützt
pure Segmentierung oder Segmentierung kombiniert mit
Paging
Pentium Segmentierung
- Segmente können bis zum 4 GB groß sein.
- Ein Prozess kann maximal 16 Segmente haben.
- Der Speicherraum des Prozesses hat zwei Partitionen
- Erste Partition: private Segmente des Prozesses
- Zweite Partition: gemeinsame Segmente für alle Prozesse
- Information über die Partitionen:
- local descriptor table LDT (Tabelle der ersten Partition)
- global descriptor table GDT (Tabelle der zweiten Partition)
M. Esponda-Argüero
77
Pentium-Segmentierung
selector
segment number
13
g protection
offset
2
0 = das Segment ist in GDT
1 = das Segment ist in LDT
Von logischer in physikalische Adresse
CPU
logische
Adresse
segmentation
unit
lineare
Adresse
paging
unit
Physikalischer
Speicher
physikalische
Adresse
M. Esponda-Argüero
Pentium Paging-Architektur
Die Pentium-Architektur erlaubt zwei verschiedene Seitengrößen (4 KB
oder 4 MB).
Bei 4 KB-Seitengröße wird ein zweistufiges Seitenschema verwendet.
Seitennummer
Dir
Page
offset
10
10
12
Jeder Prozess hat ein Seitenverzeichnis, das aus
210 32-Bits-Einträgen besteht.
Jeder Eintrag in diesem Verzeichnis zeigt auf eine Seitentabelle,
die wiederum aus 210 32-Bits-Einträgen besteht.
M. Esponda-Argüero
79
Pentium Segment- und Paging-Architektur
logische Adresse
selector
offset
descriptor table
segment descriptor
+
lineare Adresse
Dir
Page
Offset
selektiertes
Wort
Dir
Page
Seitenverzeichnis
Seitentabelle
4 KB
page
Offset
Seitenrahmen
M. Esponda-Argüero
Pentium Segment- und Paging-Architektur
logische Adresse
selector
offset
descriptor table
segment descriptor
+
lineare Adresse
page directory
offset
selektiertes
Wort
4 MB
page
Dir
Seitenverzeichnis
Seitenrahmen
Offset
Linux in Pentium-Systemen
Linux hat eine minimale Segmentierung-Unterstützung.
Nur 6 Segmente
- kernel code
- kernel data
- user code
- user data
- task-state segment (TSS)
- default LDT segment
Dreistufige Seitentabelle in Linux
Globales Verzeichnis
Mittleres Verzeichnis
Seitentabelle
Offset
Dreistufige Seitenadressierung im Linux
a
+
a
+
+