5 Speicherverwaltung 5.1 Belegungsverfahren Aufgabenstellung

Transcrição

© H.-U. Hei§, Uni Paderborn
5.1 Belegungsverfahren
5 Speicherverwaltung
AktivitŠt
Aktive Komponente
Aufgabenstellung
temp.Zuordnung
Prozess
Prozess
Prozess
Prozess
Prozessor
Zugriff
Zugriff
Speicher
aktiv
frei
passiv
temp.Zuordnung
Datum
Datum
Datum
Speicher
logisch
Inhalt
physikalisc
BehŠlter
belegt
¥
Auswahl der StŸcke
¥
Effizienz der Algorithmen
¥
Speicherausnutzung
¥
Spezielle Randbedingungen
Einsatzbereich: (realer) Hauptspeicher und (teilweise) Plattenspeicher
5-1
5-2
Struktur einer Speicherverwaltung
Belegen
(allocate)
Gestaltungsparameter einer Speicherverwaltung
Konkrete Speicherverwaltungsverfahren unterscheiden sich bezŸglich der folgenden
Aspekte:
Freigeben
(release)
¥
Reihenfolge der Operationen
¥
Grš§e der StŸcke
¥
Belegungsdarstellung
¥
Verschnitt
¥
Auswahlstrategie (bei den freien StŸcken)
¥
Wiedereingliederung
Speicherverwaltung
feste Schnittstelle
unabhängige Algorithmen
Frei
(free)
Belegtsetzen
(set_occupied)
Freisetzen
(set_free)
Verwaltungsdaten
5-3
5-4
Grš§e der StŸcke
Reihenfolge der Operationen
¥
Konstante Einheiten
Belegungen und Freigaben
NUM = 1
¥
in gleicher Reihenfolge
¥
(Schlangenverfahren, FIFO = First In First Out))
Vielfache gleicher Grundeinheiten
NUM = k(Grundeinheit)
¥
¥
(Grundeinheit)
Bestimmte Portionsgrš§en
in umgekehrter Reihenfolge
NUM = k1, k2, k3,...
(Stapelverfahren, LIFO = Last In First Out)
¥
¥
in beliebiger Reihenfolge
Beliebige Grš§en
NUM = x
(allgemeiner Fall)
5-5
5-6
Belegungsdarstellung
Wie ?
¥
¥
Tabellendarstellung (meist Freispeichertabelle)
als Vektor
als Tabelle
Wo?
¥
¥
abgesetzt
integriert
¥
abgesetzte Belegungsdarstellung
Belegungsinformation wird in Tabellen gehalten.
Sortierung je nach Bedarf nach Adresse und/oder LŠnge
Vektordarstellung
¥
abgesetzt
0 1 2 3 4
8
10
14
17
20
11110100011110010000
¥
Sortiert nach Adresse
integriert
1
1
1
1
0
1
0
0
0
1
1
1
1
0
0
1
0
0
0
Beispiel
Hauptspeicher
128 Mbyte (227 Byte)
Grundeinheit
512 Byte
(29 Byte)
Ergibt
262144 Komponenten (218)
Belegungsdarstellung gespeichert in
8192 Worten zu je 32 Bit
5-7
0
Adresse
0
4
14
20
Sortiert nach LŠnge
Länge
Länge
3
4
3
13
3
3
4
13
5-8
Adresse
14
0
4
20
Tabellendarstellung
Verschnitt (fragmentation)
¥
¥ Meistens wird Speicher in Vielfachen von festen Elementargrš§en vergeben.
Anforderungen werden daher auf das nŠchste Vielfache gerundet.
Dadurch entsteht Speicherplatz, der als belegt gekennzeichnet ist, aber nicht benutzt
wird.
Man nennt solchen Speicherplatz internen Verschnitt fint (internal fragmentation)
¥ Durch die Dynamik des Belegens und Freigebens kann es vorkommen, dass eine
Anforderung zwar von der Gesamtmenge des freien Speichers erfŸllbar wŠre, durch die
ZerstŸckelung jedoch kein hinreichend gro§es StŸck gefunden werden kann.
Dadurch entsteht Speicherplatz, der frei, aber (momentan) nicht belegbar ist.
Er wird als externer Verschnitt fext (external fragmentation) bezeichnet
integrierte Belegungsdarstellung
Die SpeicherstŸcke identifizieren sich selbst, geben ihre LŠnge an und enthalten einen
Zeiger auf das nŠchste Listenelement
FreistŸcke sortiert nach Adresse
0
3 4
3
8
10
14
4
17
20
3
13
FreistŸcke sortiert nach LŠnge
0
3 4
3
8
10
14
4
17
20
3
13
frei, aber nicht belegbar (externer Verschnitt)
belegt, aber nicht benutzt (interner Verschnitt)
belegt und benutzt
belegt
5-9
5-10
Auswahlstrategie
Auswahlstrategie
¥
¥
Erstes passendes StŸck (First-Fit)
0
3
3 4
4
8
10
14
17
3
20
25
27
13
1
6
NŠchstes passendes StŸck (Next-Fit, Rotating First-Fit)
0
3
Die (nach Adressen sortierte) Liste wird von vorne durchlaufen.
Das erste hinreichend gro§e freie StŸck wird genommen.
8
10
4
14
17
3
20
25
27
13
1
6
Stelle der letzten Belegung
Liste wird zyklisch durchlaufen.
Suche beginnt an der Stelle, wo die letzte Belegung stattgefunden hat.
Eigenschaften:
¥
¥
¥
3 4
Geringer Suchaufwand
ZerstŸckelung des Speichers (externer Verschnitt)
Konzentration der belegten StŸcke am Anfang
und dadurch Erhšhung des Suchaufwands
5-11
Eigenschaften
¥
Wie First-Fit, vermeidet aber den Nachteil der Konzentration
der Belegungen am Anfang.
Dadurch etwas kŸrzere Suchzeiten.
5-12
Auswahlstrategie
Auswahlstrategie
¥
¥
Am besten passendes StŸck (Best-Fit)
NŠchstliegendes passendes StŸck (Nearest-Fit)
0
3
0
3
3 4
8
10
4
14
17
3
20
25
27
13
1
6
3 4
8
4
10
14
17
3
20
25
27
13
1
6
Stelle der gewünschten Belegung
Das kleinste hinreichend gro§e StŸck wird genommen
¥
Eine ãWunschadresseÒ fŸr das angeforderte StŸck wird Ÿbergeben.
Der Algorithmus beginnt dann eine First-Fit-Suche von der angegebenen Adresse an.
Eigenschaften
¥
¥
¥
Bei Sortierung nach Adresse muss die gesamte FreistŸckliste durchsucht werden.
Es empfiehlt sich daher Sortierung nach Grš§e.
Im Prinzip bessere Speicherausnutzung, da kleinere Anforderungen auch durch
kleinere freie Bereiche erfŸllt werden und nicht gro§e StŸcke ãangeknabbertÒ
werden.
Neigt allerdings dazu, sehr kleine freie StŸcke zu erzeugen, mit denen man gar
nichts mehr anfangen kann.
Beim Plattenspeicher hatten wir gesehen, dass es vorteilhaft ist, Armbewegungen zu
minimieren.
Kennt man die Zugriffsreihenfolge oder ZugriffshŠufigkeit, so kann man durch die Belegung
die Armbewegung beeinflussen.
¥
¥
Dateikataloge kšnnen auf die mittleren Zylinder gelegt werden.
Bei der Erweiterung sequentieller Dateien sollten die neuen Blšcke in der NŠhe der
bisher belegten liegen.
5-13
5-14
Wiedereingliederung
¥
Beispiele fŸr konkrete Verfahren
ãSchlangenverfahrenÒ (Ringpuffer)
sofort bei Freigabe:
belegt
Freigabe
frei
belegt
¥
frei
frei
belegt
belegt
verzšgert zusammengefasst
belegt
belegt
belegt
belegt
5-15
¥
¥
¥
¥
¥
Belegungsanfang
Belegungsende
Freigeben
Belegen
Belegen und Freigeben in gleicher Reihenfolge
Gleich lange StŸcke
Kein Suchen
Kein externer Verschnitt
Automatische sofortige Wiedereingliederung
5-16
Vektorverfahren
Stapelverfahren (Keller, Stack)
1111010001111001000011100000011110110000
Suchen
Belegen
:= 1
Stapelanfang
Stapelende
Belegen
Freigeben
¥
¥
¥
¥
¥
Freigeben
:= 0
Belegen und Freigeben in umgekehrter Reihenfolge (LIFO)
Beliebig lange StŸcke
Kein Suchen
Wenig externer Verschnitt
¥
Belegen und Freigeben in beliebiger Reihenfolge
¥
StŸckgrš§e = k x Grundeinheit
¥
Suche nach erstem (passenden) StŸck
¥
Interner und externer Verschnitt
¥
5-17
5-18
Ein Tabellenverfahren
Randkennzeichnungsverfahren
(Randkennzeichnungsverfahren, boundary tag system)
Nach Freigabe
freigeworden
Kennzeichnung der StŸcke
Verkettung nach Grš§e
¥
f L1
f L1 f L2
f L2 f L3
f L3
freies StŸck
belegt
frei
belegt
Nach Wiedereingliederung
Zeiger vorwärts
Zeiger rückwärts
Länge
„frei“
¥
Länge
„frei“
fL
f L
belegtes StŸck
belegt
Länge
Länge
„belegt“
„belegt“
5-19
5-20
Randkennzeichnungsverfahren
Weitere Optimierungsmšglichkeiten
Verwaltungsaufwand durch kleine ReststŸcke
Eigenschaften
¥
¥
Operationen in beliebiger Reihenfolge
¥
Vergabe in beliebig langen StŸcken
¥
Belegungsdarstellung und StŸckverwaltung integriert.
Doppelt verkettete Liste sortiert nach Grš§e
¥
Suchstrategie Best-Fit,
¥
Externer Verschnitt
¥
Explizit durchgefŸhrte sofortige Wiedereingliederung
Ausnutzen der LŠngenfelder zum PrŸfen der Nachbarn
Sortiertes EinfŸgen in verkette Liste
Kleine ReststŸcke der Anforderung zuschlagen
(Umwandlung von externem in internen Verschnitt)
belegt
¥
angefordert
belegt
frei
Kleine ReststŸcke nicht in FreistŸckliste aufnehmen,
aber bei Freigaben mit freigewordenem Nachbarn vereinigen.
zu klein
5-21
5-22
Weitere Optimierungsmšglichkeiten
Suchaufwand reduzieren
Suchaufwand bei beliebiger Reihenfolge von Belegen und Freigeben O(n)
Beispiel: Zugriff Ÿber BinŠrbaum
Suchaufwand reduzieren
4
Beispiel: Vorkonfektionierte StŸcke
1
5
Statistisch hŠufig auftretende Anforderungsgrš§en bereithalten (ãKonfektionswareÒ)
1
2
3
2
4
4
5-23
2
5
1 1
5
5-24
1
1
4
5
Speicherauslastung
Halbierungsverfahren (Buddy-System)
Speicherauslastung: η = 1 - fext
Simulation mit 32K-Einheiten, kein interner Verschnitt
Anforderungen gleichverteilt mit Mittelwert A und Standardabweichung σA
Belegungszeiten gleichverteilt aus Intervall (5,15)
η
η
Speicher besteht aus 2kmax Einheiten
95%
Kleinere StŸcke entstehen durch (fortgesetzte) Halbierung grš§erer StŸcke
Gemeinsam entstandene kleinere StŸcke werden bei Freigabe wieder zu grš§eren StŸcken
vereinigt
90%
A=1024
90%
σA=256
Best-Fit
89%
First-Fit
88%
85%
Best-Fit
First-Fit
87%
80%
86%
512
1024
2048
A
4096
64
128
256
512
σA
Ergebnis: Der externe Verschnitt steigt mit der Grš§e und der Streuung der Anforderungen.
Charakteristik
¥
Belegen und Freigeben in beliebiger Reihenfolge
¥
Vergabe in StŸckgrš§en 20, 21, 22, .. , 2k
¥
Darstellung abgesetzt
¥
Wenig Suchen
¥
Interner und externer Verschnitt
¥
Explizit durchgefŸhrte Wiedereingliederung
5-25
5-26
Beispiel Buddy-System
2M
4M
Datenstrukturen beim Buddysystem
16M
8M
32M
(abgesetzte FreistŸckverwaltung)
20
Anforderung:
3M
Anforderung:
800K
Anforderung:
12M
22
Freigabe:
12M
23
Anforderung:
3,5M
Freigabe:
3M
Freigabe:
800K
Freigabe:
3,5M
21
2
2n
Ein Array von Listenkšpfen, die auf StŸcke gleicher Grš§e zeigen
5-27
5-28
Ablauf Anforderung
¥
Aufrunden auf nŠchste Zweierpotenz
¥
Zugriff auf erstes freies StŸck der Liste
¥
Falls Liste leer (rekursiv):
-
Buddy-Verfahren: Interner Verschnitt
Anforderungsgrš§e a:
1 2 3 4 5 6 7 8
Grš§e des belegten StŸcks b(a): 1 2 4 4 8 8 8 8
Zugriff auf Liste der nŠchsten Grš§e
StŸck entfernen
StŸck halbieren
Hintere HŠlfte in entsprechende Liste einhŠngen
pa
b(a)
die Wahrscheinlichkeit, dass eine Anforderung die Grš§e a besitzt,
die Grš§e des resultierenden belegten StŸcks,
Def.:
Der interne Verschnitt fint ist das VerhŠltnis der Erwartungswerte der Anzahl
ungenutzter Einheiten zur Anzahl belegter Einheiten:
Ablauf Freigabe
¥
¥
¥
9 10 ...
16 16 ...
amax
∑ ( b( a ) − a )
Buddy bestimmen
Falls Buddy belegt, freigewordenes StŸck in die Liste einhŠngen
Falls Buddy frei:
Vereinigung mit Buddy
Vorgang iterieren, bis Buddy belegt oder bei der maximalen Grš§e angekommen
fint =
pa
a=1
amax
∑ pa b(a)
a=1
Mit Sb : =
amax
∑ pa b(a)
und Sa : =
a=1
amax
∑ pa a
als Erwartungswerte der Belegungsgrš§e b bzw. der
a=1
Anforderungsgrš§e a ergibt sich der interne Verschnitt als fint = 1 − Sa / Sb
5-29
5-30
Um den internen Verschnittzu berechnen, benštigen wir Annahmen Ÿber die Verteilung der
Anforderungen.
Der Einfachheit halber nehmen wir an,
die Grš§en der Anforderungen seien gleichverteilt Ÿber das Intervall [1, 2n],
d.h. jede Grš§e aus diesem Intervall habe die gleiche Wahrscheinlichkeit pa = 2 −n .
Wir erhalten dann approximativ eine mittlere Anforderungsgrš§e
n n
1 2
1 2 (2 + 1)
1
= 2 n−1 + ≈ 2 n−1
n ∑i = n
2
2 i=1 2
2
Durch die Aufrundung auf die nŠchste Zweierpotenz sieht die korrespondierende
Rechnung fŸr die zugeteilten StŸcke folgenderma§en aus:
Sb =
2
mal
1
= n (1 + 1⋅ 2 + 2 ⋅ 4 + 4 ⋅8+K+2 n−12 n )
2
=
n−1
1
2 2n −1
1
2i 

n 1 + 2 ∑ 2  = n 1 + 2 2
 2 
2 −1 
2 
i=0
=
1 2 2n+1 + 1 2 n+1
≈
3
2n
3
n
Sa =

1
n
n
+K+2

1
4
2
4
3
n  1 + 2 + 4 + 4 + 8 + 8 + 8 + 8+K+2
2 
n−1

(
Daraus ergibt sich ein VerhŠltnis Sa Sb = 2 n−1 13 2 n+1 ) = 3 4 ,
d.h. die zugeteilten StŸcke sind im Mittel um ein Drittel grš§er als angefordert,
die belegten StŸcke sind im Mittel nur zu 3/4 genutzt,
und der interne Verschnitt betrŠgt fint = 25%.
5-31
5-32
Buddy-Verfahren
5.2 Speicherbereinigung (Garbage Collection)
¥
Schnelle Operationen (O(1))
¥
Stellt sich auf das Anforderungsprofil ein
¥
Nach Einschwingen nur wenig Teilungs- und VereinigungsvorgŠnge
¥
Relativ hoher interner Verschnitt
Problem:
Dynamische Speicherverwaltungsoperationen (C: malloc, free) erfordern disziplinierte
Benutzung durch den Programmierer
Nicht mehr benštigter Speicher sollte zurŸckgegeben werden
Beim Aufbau verzeigerter Datenstrukturen (Listen, BŠume) kann es vorkommen, dass
• Teile der Datenstruktur nicht mehr erreichbar sind (Lšschen oder Umsetzen einer
Referenz)
• Objekte gelšscht werden, auf die noch Referenzen existieren
25% int. Verschnitt
Anforderung gleichverteilt:
Minimum
Mittelwert
Maximum
5-33
5-34
Beispiel (Java)
UngŸltig gewordene Referenzen (dangling references)
class Node
{ Node (String s, Node n)
{ data = s; next = n;}
String data; Node next;
}
Node list = new Node ("A", null)
Wird ein Objekt freigegeben, auf das noch eine Referenz existiert, und anschlie§end der
Speicherplatz dieses Objekts neu vergeben, so kšnnen unvorhersehbare Fehler auftreten
list
Nach weiteren EinfŸgeoperationen kšnnte die folgende Liste entstehen:
list
"A"
"A"
"B"
"B"
"C"
"C"
Mit list.next = null sind die beiden hinteren Objekte nicht mehr erreichbar:
list
"A"
"B"
"C"
5-35
5-36
Modell
Wurzeln und Lebendigkeit
Wir nehmen an, der Speicherbereich eines Programms besteht aus drei Teilbereichen
Objekte des statischen Speichers oder Stacks, die solche Referenzen enthalten, hei§en
Wurzeln (roots).
• Statischer Speicher:
fest zugeordnet, nicht dynamisch belegbar (globale Variable)
• Stack:
Dynamischer Speicher zur Verwaltung lokaler Daten in Prozeduren.
WŠchst beim Prozeduraufruf und schrumpft bei der RŸckkehr (LIFO-Prinzip)
• Heap:
Dynamischer Speicher zur Aufnahme dynamisch angelegter Objekte
Speicherobjekte im Heap kšnnen nur erreicht werden Ÿber Referenzen oder Ketten von
Referenzen, die ihren Ursprung im statischen Speicher oder im Stack haben.
Ein Speicherobjekt des Heaps hei§t lebendig (live),
1. wenn es eine Wurzel gibt, die eine Referenz auf es besitzt oder
2. wenn es ein lebendiges Objekt gibt, das eine Referenz auf es besitzt
Referenzierung bildet eine Relation auf der Menge der Speicherobjekte, die
"zeigt-auf"-Relation oder "→"-Relation: O → P, gdw O eine Referenz auf P enthŠlt.
Die Menge der lebendigen Objekte ist dann die transitive referenzielle HŸlle der
Wurzelobjekte, d.h. die kleinste Menge live mit der folgenden Eigenschaft
live = {O ∈Objects (∃r ∈ roots : r → O) ∨ (∃P ∈live : P → O)}
Objekte des Heaps, die nicht lebendig sind, hei§en Abfall (garbage)
Es ist Aufgabe der Speicherbereinigung (Garbage Collection), solche Abfallobjekte zu
finden, ggf. ihren Inhalt zu lšschen und ihren Platz zur Wiederverwendung zur VerfŸgung
zu stellen.
5-37
5-38
5.2.1 ReferenzzŠhler (reference counter)
Der Heap sei ein StŸck zusammenhŠngender Speicher (Folge von Speicherzellen)
Die Speicherverwaltung fŸr den Heap unterhŠlt eine Freispeicherliste (free_list), in der freie
Speicherobjekte als verkettete Liste verwaltet werden.
Operationen fŸr ReferenzzŠhler-Verfahren
Beispielformulierung in Java-Šhnlicher Notation
class GC {
class MemObj {
MemObj next;
int rc = 0;
...
}
Jedes Speicherobjekt, ob frei oder belegt, enthŠlt ein Feld RC (reference counter)
MemObj free_list;
Freie Speicherobjekte haben einen RC-Wert von 0
MemObj allocate() {
// Entnahme eines freien Speicherobjekts
MemObj newMemObj = free_list;
free_list = free_list.next;
return newMemObj;
}
MemObj new() {
// Belegung eines neuen Speicherobjekts
if (free_list == null)
throw new Error("memory exhausted");
newMemObj = allocate();
newMemObj.rc = 1;
return newMemObj;
}
Bei der Anforderung eines Speicherobjekts (z.B. durch "new") wird der RC des Objekts auf
1 gesetzt.
Bei jeder Erzeugung einer weiteren Referenz auf das Speicherobjekt wird sein
ReferenzzŠhler inkrementiert, bei jeder Lšschung einer Referenz dekrementiert.
Wird der ReferenzzŠhler eines Objekts zu 0, so existiert keine Referenz mehr darauf und
es kann in die Freispeicherliste zurŸck
5-39
5-40
vor update(R.right, null)
Fortsetzung
private void free(o) { // Rueckgabe in die Freiliste
o.next = free_list;
free_list = o;
}
void delete(MemObj o) { // Loescht eine Referenz
o.rc = o.rc-1;
if (o.rc == 0) {
// Achtung: das folgende ist kein Java :-)
for _all p in children(o)_
delete(p);
free(o);
}
}
void update(MemObj o, MemObj p) { // Modifikation von Referenzen
delete(o); // Ersetzt das 1. Argument durch das 2.
p.rc = p.rc+1;
o = p;
}
freelist
n
R
2
T
S
1
U
1
Rekursion:
delete(R.right)
V
1
freelist
n
R
2
T
S
}
1
V
5-41
5-42
0
S
freelist
1
V
1
nach Abschluss aller Rekursionen
in update(R.right, null)
T
1
n
0
S
Zyklische Datenstrukturen
Ausgangspunkt
0
U
R
1
Weiter in Rekursion:
delete(S.left)
R n
1
0
0
U
T
0
0
freelist
U
0
R
Nach Lšschen eines Zeigers
R
n
n
S
2
S
1
T
2
T
2
U
1
U
1
Das ReferenzzŠhlerverfahren ist nicht in der Lage, bei Zyklen in der Datenstruktur die
Unerreichbarkeit zu erkennen, da die ReferenzzŠhler nicht zu Null werden.
Dies ist ein schwerwiegender Nachteil, weswegen das Verfahren in seiner reinen Form nur
eingesetzt werden kann, wenn feststeht, dass keine zyklischen Strukturen auftreten.
V
0
5-43
5-44
5.2.2 Mark-Sweep
Zwei Phasen
Im Gegensatz zum ReferenzzŠhler-Verfahren, wird das Mark-Sweep-Verfahren nur dann
aktiv, wenn kein freier Speicher mehr zur VerfŸgung steht.
void mark_sweep() {
for (R in Roots) mark(R);
sweep();
if (free_list == Null)
}
MemObj new () {
if (free_list == null)
throw new Error("memory exhausted");
newMemObj = allocate();
newMemObj.rc = 1;
return newMemObj;
}
// Phase 1
// Phase 2
Das Verfahren besteht aus zwei Phasen:
Phase 1 (Mark):
Beginnend bei den Wurzeln der Datenstruktur wird der komplette Graph abgelaufen
und jedes Objekt markiert (z.B. Tiefensuche). Die markierten Objekte sind die
lebendigen.
Nach Aufruf durchlŠuft es den Speicher, erkennt die nicht erreichbaren Objekte und gibt
deren Platz frei.
Anschlie§end kann der normale Betrieb weiterlaufen, bis wiederum aller Speicher
aufgebraucht ist.
Phase 2 (Sweep):
In der Sweepphase wird der Speicher linear durchlaufen und alle Objekte, die nicht
markiert sind, in die Freispeicherliste zurŸckgegeben.
Der Nachteil von Mark-Sweep besteht darin, dass der Programmlauf wŠhrend der GCPhasen zum Halten kommt, das Programm also fŸr einige Zeit nicht reagiert.
5-45
5-46
Fromspace
5.2.3 Kopierverfahren
Beim Kopierverfahren wird der Heap in zwei Teile geteilt, einen fŸr die aktuellen
Datenobjekte und einen, in dem sich ŸberflŸssig gewordenene befinden.
Fromspace
R
___
R
T
S
T
Bei Aufruf der Garbage Collection wechseln die beiden TeilrŠume ihre Funktion.
Der bislang aktive Teilraum (ãFromspace) wird wie bei Mark-Sweep entlang der
Verzeigerung durchlaufen.
U
U
Jedes erreichte Speicherobjekt wird in den anderern Teilraum (ãTospaceÒ) kopiert, wobei
man sich von der alten Kopie mittels eines Zeigers die Lage der neuen Kopie merkt, um
Mehrfachreferenzen korrekt behandeln zu kšnnen.
Nachteil: Doppelter Speicherraum
Vorteil: Kompaktere Speicherung (bessere LokalitŠt der Zugriffe)
5-47
Tospace
S
5-48
Tospace
Fromspace
Fromspace
R
5.3 Speicherhierachie und LokalitŠt
R
T
S
T
Verarbeitung
S
U
schneller, teurer,
kleiner
U
Register
Cache
Hauptspeicher
R
T
S
U
Magnetplatte
langsamer,
billiger, größer
Tospace
5-49
Tospace
Archiv (CD-ROM, Band,...)
5-50
Prinzipielle Arbeitsweise der Speicherhierarchie
LokalitŠtsprinzip (Principle of locality)
Beim (ersten) Zugriff auf ein Datenelement werden entlang der Speicherhierarchie Kopien
angelegt, d.h. das Datenlement ãwandertÒ nach ãobenÒ
Schicht 1
Kopie
Die Speicherhierarchie basiert auf dem LokalitŠtsprinzip:
Ein Prozess greift in einem kleinen Zeitraum ∆t nur auf einen kleinen Teil ∆A ⊂ A seines
Adressraums A zu.
Zugriff
Schicht n-1
Kopie
Schicht n
Original
Nach der Modifikation des Datenelements werden €nderungen (schrittweise, verzšgert)
nach unten propagiert.
Schicht 1
Kopie
Modifikation
Schicht n-1
RŠumliche LokalitŠt:Wird auf eine Adresse a zugegriffen, so ist ein Zugriff auf eine
Adresse in der NŠhe von a sehr wahrscheinlich.
Spezialfall: sequentieller Zugriff.
Zeitliche LokalitŠt: Wird auf eine Adresse a zugegriffen, so ist es sehr wahrscheinlich,
dass in KŸrze wieder auf a zugegriffen wird.
Warum ?
¥
Meist werden die Anweisungen sequentiell ausgefŸhrt (rŠumliche, sequentielle Lokal.)
¥
Programme verbringen die meiste Zeit in irgendwelchen Schleifen (zeitliche LokalitŠt)
¥
Manche Teile eines Programms werden nur in AusnahmefŠllen angesprungen.
¥
Viele Felder sind nur teilweise belegt.
¥
90/10-Regel: Ein Prozess verbringt 90% seiner Zeit in 10% seines Adressraums
Kopie
Schicht n
Original
5-51
Konsequenz:
¥
In jedem kleinen Zeitintervall wird nur ein kleiner Teil des Adressraums benštigt.
Jeweils nicht benštigte Teile kšnnen auf billigeren, langsameren Medien abgelegt sein.
5-52
Gestaltungsaspekte einer Speicherhierarchie
_Caching vs. Virtualisierung
Ziel:
Die gerade benštigten Daten und Programme sollen mšglichst weit oben in der
Speicherhierarchie verfŸgbar sein
transparent
Schicht k-1
Caching
Schicht k
Problem: Die KapazitŠten werden nach oben hin sehr knapp
sichtbar
Virtualisierung
Fragen:
¥ Woher wei§ man, auf welche Daten als nŠchstes zugegriffen wird ?
Kenntnis des Programmverhaltens
¥ Wer ist fŸr den Datentransport zustŠndig ?
Benutzer/Programmierer, †bersetzer, Betriebssystem, Hardware
¥ In welchen Einheiten werden die Daten transportiert ?
Bytes, Speicherworte, Blšcke, Dateien
¥ LŠuft der vertikale Datentransport automatisch ab oder muss man sich explizit darum
kŸmmern?
¥ Wird der Zugriff auf die aktuelle Schicht beschleunigt (Caching) oder die KapazitŠt der
aktuellen Schicht erweitert (Virtualisierung)
Schicht k+1
transparent
• Der Programmierer oder Nutzer einer Speicherhierarchie sieht in der Regel nicht alle
Schichten, sondern einige sind ihm verborgen, bzw. sind transparent fŸr ihn.
• Er hat den Eindruck, es gebe nur die Schicht k, auf die sich seine Zugriffe beziehen.
• Sieht der Benutzer Schicht k, greift aber de facto auf Schicht k-1 zu, so spricht man von
Caching.
• Sieht der Benutzer Schicht k, obwohl die addressierten Daten tatsŠchlich auf Schicht k+1
liegen, so spricht man Virtualisierung
• Durch Caching werden die Datenzugriffe schneller, durch Virtualisierung wird die
KapazitŠt grš§er.
5-53
5-54
FlŸchtiger / Permanenter Speicher
ZustŠndigkeiten bei AusfŸhrung
Zuständigkeit
Prozessorregister
Transfereinheit
Wort (z.B. 8 Byte)
Hardware
Cache
Hardware
Cache-Line (z.B. 64 Byte)
Bedingt durch die auf den jeweiligen Ebenen eingesetzten Speichermedien sind die oberen
Schichten flŸchtig, d.h. ihr Inhalt geht bei Stromabschaltung
Daher werden die oberen Schichten fŸr die Speicherung temporŠrer Objekte
(Programmvariable) verwendet, wŠhrend die unteren fŸr permanente Objekte (Dateien)
verwendet werden
Hauptspeicher
Betriebssystem
Prozessorregister
Plattenblock (z.B. 4KByte)
Magnetplatte
Betriebssystem, Benutzer
Cache
Datei (variabel)
Magnetband
WŠhrend der Laufzeit eines Programms wird der Transport der Daten und Befehle
zwischen Hauptspeicher, Cache und Prozessor von der Hardware direkt erledigt.
Zugriffe auf die Platte sind Aufgabe des Betriebssystems.
Aus- und Einlagern von Dateien auf/vom Archivspeicher wird entweder explizit vom
Benutzer angesto§en oder automatisch vom Betriebssystem (Dateisystem) durchgefŸhrt.
5-55
flüchtiger Speicher
temporäre Daten
(Programmvariablen)
nichtflüchtiger Speicher
permanente Daten
(Dateien)
Hauptspeicher
Magnetplatte
Magnetband
5-56
FlŸchtiger / Permanenter Speicher
Caching im World Wide Web
Caching und Virtualisierung haben dazu gefŸhrt, dass die historische Verwendung des
Hauptspeichers ( nur fŸr Programmadressraum) und des Plattenspeichers (nur Dateien)
aufgeweicht wurde.
Auch das Zugriffsverhalten im WWW zeigt LokalitŠt.
Es lohnt sich daher, Webseiten in einem Cache zwischenzuspeichern, um dadurch den
Zugriff zu beschleunigen und den Netzverkehr zu entlasten
Webclient
flüchtiger Speicher
temporäre Daten
(Programmvariablen)
Datei-Cache
Programm AR
Virtualisierung
Caching
nichtflüchtiger Speicher
permanente Daten
(Dateien)
Dateien
Paging area
Hauptspeicher
Webclient
Webclient
Webcache
Intranet
Magnetplatte
Internet
WebServer
5-57
WebServer
WebServer
5-58
Verzweigende Speicherhierarchien
Ebene der Verarbeitung
und Modifikation
5.4 Registerzuteilung
Zur VerknŸpfung von Werten mŸssen diese erst in Register des Prozessors geladen
werden
Auch Zwischenergebnisse komplexer arithmetischer AusdrŸcke mŸssen in Registern
zwischengespeichert werden:
Hšhere Programmiersprache
y := 3;
x := (a+b) * (c+d)
Speicherhierarchien kšnnen auch verzweigen.
Verzweigungen nach ãuntenÒ sind dabei unkritisch.
Verzweigungen nach ãobenÒ fŸhren dazu, dass auf derselben Ebene mehrere Kopien
existieren, die auf oberster Ebene unabhŠngig voneinander modifiziert werden kšnnen.
Dies fŸhrt zu einem Konsistenzproblem (Cache-KohŠrenz)
5-59
z := x+y
Maschinencode (Assembler)
load r1, 3
store r1,y
load r2, a
add r2, b
load r3, c
add r3,d
mult r2, r3
add r1, r2
store r1, z
Da Zugriffe auf den Speicher ãteuerÒ sind, wird versucht, Werte, die noch benštigt werden,
in Registern zu halten. (Z.B. ist y noch in R1 verfŸgbar)
5-60
Grundblšcke
Registerzuteilung innerhalb der Grundblšcke
Man wŸnscht sich daher so viele Register, dass man einen schon mal geladenen Wert bis
zur letzten Verwendung in einem Register halten kann.
Falls nicht genŸgend Register zur VerfŸgung stehen, muss man Werte aus Registern in
den Speicher auslagern und bei erneutem Gebrauch wieder einlagern (Spill-Code)
b
c
d
e
f
g
a+b
c :=
d := 5
Da der Compiler die Befehlsfolge selbst erzeugt, kennt er auch die nŠchsten benštigten
Daten, sofern nicht bedingte, d.h. von Werten abhŠngige SprŸnge auftreten (if..then..else)
d *a
max.
Schnitt
e :=
Teile eines Programms, die frei sind von solchen Verzweigungen, also aus
deterministischem Code bestehen hei§en Grundblšcke
Innerhalb der Grundblšcke kann der Compiler versuchen,
die Nutzung der Register zu optimieren.
a
a =: 3
b := 8
e+d
f :=
c+a
if a < b then
begin
t:= a;
a:= b;
b:= t;
end
else
a:= a-b;
g :=
b+g
f :=
R1 R2
R1 (R2)
(R1) (R2)
R3
R3
R3
5-61
R4
R4
R2
R5
R2
R1
R4
R4
R1
R1
R1
R2
5 Register
4 Register
3 Register
5-62
Registerzuteilung innerhalb der Grundblšcke
5.5 Streuende Adressierung im Hauptspeicher
1
Lebensdauern der Werte bestimmen
Der Programmadressraum wird in kleinere StŸcke zerlegt, die unabhŠngig voneinander im
Speicher abgelegt werden.
2
Maximalen Schnitt bestimmen (Registerbedarf des Blocks)
3
Register der Reihe nach zuordnen
bei Registermangel:
Register freimachen (Wert auslagern, spilling)
Kriterium fŸr Auslagerung:
Werte, die schon im Speicher stehen (kein Auslagern, einfach Ÿberschreiben)
Werte, die am lŠngsten nicht mehr benštigt werden
¥
¥
Bessere Ausnutzung von LŸcken (geringerer externer Verschnitt)
Hšherer Aufwand beim Adressieren
Man spricht von dynamischer Adressumsetzung:
Die Adressen im Programm (logische Adressen) werden durch eine spezielle
Einrichtung des Prozessors (Speicherabbildungseinheit, Memory Management Unit
(MMU)) in physikalische Adressen umgesetzt.
Programmadreßraum
Speicher
MMU
5-63
5-64
StŸckelung in gleichlange Teile:
StŸckelung in gleich lange Teile (Seiten, pages)
¥
kein externer, aber interner Verschnitt
Da es nun eine variable und gro§e Anzahl von Basisadressen geben kann, kšnnen wir sie
nicht alle im Prozessor halten.
¥
Die Teile des Adressraums hei§en Seiten (pages)
¥
Die korrespondierenden Einheiten des Speicher hei§en Seitenrahmen oder Kacheln
(page frames)
Sie werden in einer Seitentabelle zusammengefasst und im Hauptspeicher abgelegt.
Die Adressen bestehen aus zwei Teilen, der Seitennummer und einer Relativadresse
innerhalb der Seite (offset, displacement)
Speicher
Programmadreßraum
Im Prozessor befindet sich nur noch die Basisadresse der Seitentabelle in einem Register
Seitentabelle
Tabellenbasisadresse
Speicher
+
Seite
Byte
K
5-65
5-66
Seitengrš§e
Seitengrš§e
Wie gro§ sollte eine Seite sein ?
¥
kleine Seiten
+ geringer Verschnitt
lange Seitentabellen
¥
+
gro§e Seiten
hoher Verschnitt
kurze Seitentabellen
Wie gro§ sollte eine Seite sein ?
Beispiel
Sei
p
s
LŠnge des Programmadressraums
SeitenlŠnge
Dann gilt:
¥
interner Verschnitt:
¥
LŠnge der Seitentabelle
Relativer Gesamtverlust
v=
Daraus folgt
s/2
 p
 s 
1  p s
+
p  s 2
sopt = 2 p
vopt = 2 / p
sopt
vopt
p=
50
10
20%
p=
5000
100
2%
p=
500000
1000
0.2%
WŠhlt man jeweils die optimale SeitenlŠnge, so nimmt der Speicherverlust mit
zunehmender Programmgršsse ab
5-67
5-68
StŸckelung in variabel lange Teile (Segmente, segments)
StŸckelung in variabel lange Teile (Segmente)
¥
kein interner Verschnitt
Da Segmente an beliebigen Adressen beginnen kšnnen, muss die Segmenttabelle volle
Adressen aufnehmen kšnnen.
¥
dafŸr externer Verschnitt
Die Relativadresse (Byte) innerhalb des Segments wird dann zur Segmentbasisadresse
addiert
Speicher
Programmadreßraum
belegt
frei
Speicher
Segmenttabelle
+
frei
Segment
Byte
+
5-69
5-70
GegenŸberstellung: Seiten- und Segmentumsetzung
Zweistufige Adressumsetzung
Jedes Segment besteht aus einer variablen Menge von Seiten
Seitenumsetzung
0000
0001
0010 1101
Segmenttabelle
+
0010 1011
K
Seitentabelle
11011011
+
Segmentumsetzung
0000
0001
0010 11010101
Speicher
K
Segment
0010 1011
+
5-71
Seite
Byte
11100000
5-72
Beschleunigung der Adressumsetzung
Zweistufige Adressumsetzung mit Assoziativregister
Problem:
Segmenttabelle
Segment- und Seitentabellen sind so gro§, dass sie im Hauptspeicher untergebracht
werden mŸssen.
+
Seitentabelle
Um eine effektive Hauptspeicheradresse zu bilden, muss zunŠchst die Seiten- und/oder
Segmentadresse beschafft werden.
+
FŸr jeden Zugriff (Befehl oder Daten) sind damit mindestens zwei Hauptspeicherzugriffe
erforderlich.
Dadurch reduziert sich die Verarbeitungsgeschwindigkeit etwa um den Faktor 2
TLB (Assoziativspeicher)
Segment
Seite
Speicher
Kachel
Um das zu verhindern, werden die aktuell benštigten Segment/Seitentabellen in einem
schnellen Registersatz gespeichert. (TLB = Translation Lookaside Buffer)
Der TLB ist ein Assoziativspeicher, d.h. eine Tabelle, bei der zu findende Eintrag simultan
in allen Zeilen der Tabelle gesucht wird.
K
Er wird als eine Art Cache fŸr Seiten-/Segmenttabellen verwendet.
Die Suche kann also in einem Schritt durchgefŸhrt werden.
Segment
Seite
Byte
5-73
5-74
Typische Eigenschaften eines TLB
Logische Seiten/Segment-Nr., Kachel-Nr. Verwaltungsbits
5.6 Virtueller Speicher
¥
Das Zerlegen der AdressrŠume, das Ein-und Auslagern der Teile kann (mit
technischer Hilfe) automatisiert werden.
¥
Die benštigten Teile werden erst auf Anforderung eingelagert (demand paging)
¥
Zeilenbreite : 4-8 Byte:
¥
Zeit fŸr Adressumsetzung
¥
FŸr den Benutzer / Programmierer sind diese VorgŠnge transparent
Erfolg (hit):
² 1 Prozesorzyklus
¥
Er hat den Eindruck, der Speicher sei in unbegrenzter Grš§e vorhanden.
Misserfolg (miss)
10 - 30 Prozessorzyklen
¥
Dieser unbegrenzte Speicher ist jedoch nur virtuell vorhanden
¥
Trefferrate:
99.0% - 99.99%
¥
TLB-Grš§e:
32 - 1024
Voraussetzungen fŸr effizienten Betrieb:
Zeilen (EintrŠge)
5-75
¥
Gestreute Adressierung (Seitentabellen)
Seiten sind die Einheiten der †berlagerung
¥
Automatisches Erkennen der Abwesenheit einer Seite
Zugriff auf nicht vorhandene Seite lšst Unterbrechung aus.
Einlagerung der Seite wird im Rahmen der Unterbrechungsbehandlung ausgelšst.
5-76
Beteiligte Komponenten (Datenstrukturen)
¥
Seitentabelle fŸr virtuellen Speicher
ZusŠtzlich zur physikalischen Adresse enthŠlt jeder Eintrag Informationen, ob
¥
die Seite im Hauptspeicher vorhanden ist:
PrŠsenzbit (presence bit, valid bit)
¥
auf die Seite zugegriffen wurde:
Referenzbit (reference bit)
¥
die Seite verŠndert wurde (Schreibzugriff)
Modifikationsbit (dirty bit)
Seitentabellen (page table)
Funktion:
Adresstransformation
Inhalt:
fŸr jede Seite:
¥
Nutzungs- und PrŠsenzinformation
¥
Physikalische Adresse (Kachelnummer)
Speicher (Kacheln)
Seiten
Seitentabelle
1 1 1
¥
¥
Kacheltabelle (page frame table, inverted page table)
1 0 0
0 0 0
Funktion:
Speicherverwaltung
Inhalt:
fŸr jede Kachel
¥
Zustand (frei / belegt)
¥
Besitzer
¥
belegende Seite
1 1 0
0 0 0
1 1 1
Modifikation
Ersatzspeicher (swap area)
Funktion:
Zugriff (Referenzierung)
Präsenz
Bereiche des Plattenspeichers zur Aufnahme ausgelagerter Seiten
5-77
5-78
Aufgaben bei der Verwaltung des virtuellen Speichers
Ersatzspeicher
initialisieren
Seitenfehler
Freigeben_VS
leere Kachel verfügbar ?
Seite präsent ?
N
belegte Kacheln
freigeben
J
Seitenfehler
Ja
Nein
Ausräumen
Ersatzspeicher
belegen
Zugriff
Ablauf bei Seitenfehler
Ersatzspeicher
freigeben
Kachel zum Räumen auswählen
Strategieproblem
Kachelinhalt (Seite) modifiziert ?
Nein
Ja
Seite auslagern auf Ersatzspeicher
Neue Seite einlagern von Ersatzspeicher
Einräumen
Belegen_VS
5-79
Eintrag Kacheltabelle
Eintrag Seitentabelle
5-80
Zeitaufwendig!
Umschalten!
5.7 Datei-Cache
Beispiel: Datei-Cache in Unix
¥
¥
Zur Verwaltung der Plattenblšcke im Hauptspeicher wird eine Hashtabelle verwendet.
Blšcke mit gleichem Hashwert werden in einer verketteten Liste gehalten.
¥
Blšcke, die gerade gefŸllt oder geleert werden, sind gesperrt
¥
Die nicht gesperrten Blšcke werden in der Reihenfolge des letzten Zugriffs (zusŠtzlich)
verkettet. Wird ein Block benštigt, so wird der am lŠngsten nicht mehr referenzierte
gerŠumt.
¥
¥
¥
¥
¥
¥
Da hŠufig Daten mehrfach zugegriffen werden, z.B. Indexblšcke (Block mit
Verwaltungsdaten, in welchen Plattenblšcken welche Teile der Datei abgelegt sind),
lohnt es sich, Plattenblšcke im Hauptspeicher zu puffern. (Platten-Cache, DateiCache)
Einige Betriebssysteme verwenden den gesamten sonst ungenutzten Hauptspeicher
als Plattencache (z.B. Linux)
(Auch moderne Plattencontroller haben hŠufig einen internen, transparenten Cache)
Bei jedem Zugriff auf einen Plattenblock wird daher zunŠchst im Puffer nachgesehen,
ob der Block schon vorhanden ist.
Als Auslagerungsstrategie bei Platzmangel kommen dieselben Algorithmen in Frage
wie beim virtuellen Speicher oder auf anderen Ebenen der Speicherhierarchie. (siehe
5.7)
Wenn ein modifizierter Plattenblock jedoch erst im Rahmen einer Auslagerung auf die
Platte geschrieben wird, besteht die Gefahr des Verlustes (bei Systemabsturz,
Stromausfall)
Wichtige Blšcke, von deren AktualitŠt die Konsistenz des Dateisystems abhŠngt
(Verzeichnisblšcke, Indexblšcke) sollten daher sofort gerettet werden.
Sequentieller Zugriff kann beim Puffern ausgenutzt werden: Read-Ahead und FreeBehind
Kopf der Freiliste
Hashtabelle
frei
gesperrt
5-81
5-82
Caching in verteilten Dateisystemen
Cache-Konsistenz
• Im lokalen Fall bedeutet Caching, da§ Teile der Datei, die auf einem Plattenspeicher
abgelegt ist,sich im Hauptspeicher befinden.
Greifen mehrere Clients lesend und schreibend auf dieselbe Datei zu, so fŸhrt das Caching
zu Konsistenzproblemen, weil Schreiboperationen sich zunŠchst nur auf die lokale Kopie
beziehen.
• Im verteilten Dateisystem mit Client-Server-Struktur wird der Server ebenfalls gro§e Teile
des Hauptspeichers als Pufferplatz verwenden, um Plattenzugriffe zu sparen.
• Bei entfernten Zugriffen sollten jedoch auch Datentransporte Ÿber das Netz minimiert
werden. Dazu kann man nun auf Seiten des Clients einen Puffer einsetzen.
• Der Puffer auf Client-Seite kann nun auf der Platte oder im Hauptspeicher realisiert sein.
Client
x1
Puffer
x2
Client
Client
lokale
Kopie
lokale
Kopie
lokale
Kopie
Server
Netz
x3
Client
lokales Netz
x0
Als Transfereinheiten verwendet man entweder Blšcke (z.B. NFS = Network File System)
oder ganze Dateien (z.B. AFS = Andrew File System)
FileServer
Original
5-83
5-84
Cache-Konsistenz
5.8 Auslagerungsstrategien
Zur Reduktion der Netzlast wurden folgende Ma§nahmen vorgeschlagen
Je grš§er der Unterschied der Zugriffszeiten zwischen zwei adjazenten Ebenen der
Speicherhierarchie, desto wichtiger ist die Trefferwahrscheinlichkeit, d.h. die
Wahrscheinlichkeit, mit der ein referenziertes Datenelement auf der jeweiligen Ebene
vorgefunden wird.
Write-Through
Der Puffer wird zum Lesen benutzt. Schreiboperationen werden sofort zum Server
weitergegeben, d.h. auf das Original angewendet.
Verzšgertes Schreiben
Schreiboperationen werden gesammelt und im BŸndel an den Server weitergeleitet.
Write-on-Close
DateiŠnderungen werden erst beim Schlie§en der Datei an den Server weitergeleitet.
In allen FŠllen kšnnen Inkonsistenzen auftreten. Es handelt sich um pragmatische
Kompromisse zwischen Konsistenzwahrung und Aufwandsminimierung,
Soll strenge Konsistenz erreicht werden, so muss auf Sperren oder Transaktionskonzepte
zurŸckgegriffen werden.
Ist das gewŸnschte Datenelement auf der jeweiligen Ebene nicht vorhanden, so liegt ein
Zugriffsfehler (z.B. cache miss, page fault) vor.
Ein Zugriff auf einer bestimmten Ebene ist also entweder ein Treffer oder ein Zugriffsfehler.
Ist auf einer Ebene ein Zugriffsfehler aufgetreten und ist kein Platz mehr zum Einlagern des
referenzierten Datenelements frei, so muss ein anderes Datenelement ausgelagert werden.
Wir werden in diesem Abschnitt Auslagerungsstrategien im Kontext und in der
Terminologie des virtuellen Speichers behandeln.
Alle Aussagen lassen sich aber mutatis mutandis auf andere Ebenen einer
Speicherhierarchie anwenden.
Das Cache-Konsistenzproblem tritt auch bei WWW-Browsern auf (Reload-Button)
5-85
5-86
Auswirkung der Trefferrate auf die Zugriffszeit
Eine kleine Rechnung:
Sei p pf die Wahrscheinlichkeit fŸr einen Seitenfehler (page fault), tm die
Speicherzugriffszeit und t pf die Zeit zur Behandlung eines Seitenfehlers.
Dann erhalten wir als effektive Speicherzugriffszeit im virtuellen Speicher
(
)
Auswahlstrategie
Die Seitenfehlerrate hŠngt natŸrlich stark davon ab, welche Seiten wir im Hauptspeicher
halten und welche wir auslagern.
Auswahlstrategie:
Wenn Seitenfehler und keine Kachel frei, welche soll dann geleert werden ?
teff := 1 − p pf ⋅ tm + p pf ⋅ t pf
Bei halbwegs realistischen Grš§en von z.B. tm = 20 nsec und t pf = 20 msec
(
)
teff = 1 − p pf ⋅ 20 + p pf ⋅ 20.000.000
Unterscheidung
Lokale Auswahlstrategie:
Es wird eine Kachel desjenigen Prozesses gerŠumt,
der den Seitenfehler verursacht hat
= 20 + 19.999.980 ⋅ p pf
Bei einer Seitenfehlerwahrscheinlichkeit von p pf = 0, 001 erhalten wir eine effektive
Zugriffszeit von 20 µsec, d.h. eine Verlangsamung um den Faktor 1000 !
Selbst bei einem Wert von p pf = 10 −6 verdoppelt sich die effektive Zugriffszeit.
Globale Auswahlstrategie:
Eine beliebige Kachel (auch fremder Prozesse) wird gerŠumt
Es ist daher ungeheuer wichtig, die Seitenfehlerzahl sehr gering zu halten
5-87
5-88
ZufŠllige Auswahlstrategie (RANDom)
Modellierung der Seitenzugriffe
Falls die Referenzfolge keinerlei statistische Eigenschaften hat,
d.h. wenn das LokalitŠtsprinzip nicht zutrifft, also die Zugriffe unabhŠngig voneinander und
gleichverteilt Ÿber den Adressraum stattfinden,
dann ist es letztlich gleichgŸltig, welche Seite ausgelagert wird.
Um die verschiedenen Auswahlalgorithmen vergleichen zu kšnnen,
legen wir sogenannte Seitenreferenzfolgen zugrunde
Sei ri die Nummer der Seite, auf die zum Zeitpunkt i zugegriffen wird.
Dies fŸhrt zur zufŠlligen Strategie (RAND)
Dann ist R = r1, r2 , r3 ,..., rn eine Seitenreferenzfolge.
Es gelte ri ≠ ri +1 ∀i , d.h. aufeinanderfolgende Referenzen auf dieselbe Seite werden in
der Referenzfolge zu einer Referenz zusammengefasst.
Beispiel:
Gegeben sei ein Speichergrš§e von 3 Kacheln und eine Referenzfolge
ZufŠllige Strategie: 7 Seitenfehler (ohne die Initialseitenfehler beim ersten Zugriff)
Bei lokaler Strategie erhalten wir fŸr jeden Prozess eine Referenzfolge. Die
Referenznummern beziehen sich auf den jeweiligen Adressraum.
Bei globaler Strategie entsteht die Referenzfolge als Mischung der Referenzfolgen der
Prozesse.
Der Seitennummer ist die Prozesskennung beizufŸgen, so dass eine Referenz aus einem
Paar (PID, Seitennummer) besteht.
Zeit
1
Referenz 0
Kachel 1 0
Kachel 2
Kachel 3
2
2
0
2
3
4
0
2
4
4
3
0
3
4
5
2
2
3
4
FŸr die nachfolgende Diskussion ergibt sich daraus kein Unterschied.
Die Zugriffe, die einen Seitenfehler verursachen, sind fett gedruckt
5-89
6
3
2
3
4
7
0
2
0
4
8
1
2
0
1
9
0
2
0
1
10
3
2
3
1
11
0
0
3
1
12
2
0
3
2
5-90
Optimale Auswahlstrategie (OPTimal)
Realisierbare Strategien
Die zufŠllige Strategie nutzt keinerlei Information der Referenzfolge.
Die optimale Strategie hat einen schwerwiegenden Nachteil:
Sie ist nicht realisierbar, da i.a. zu jedem Zeitpunkt nur die bisher stattgefundenen
Referenzen, nicht aber die zukŸnftigen bekannt sind.
(Die optimale Strategie dient daher nur als ãMesslatteÒ fŸr realisierbare Strategien)
Es stellt sich daher die Frage, ob es eine optimale Strategie gibt,
d.h. eine Strategie, die unter Ausnutzung der Referenzfolge die Seiten so auswŠhlt,
dass die Anzahl der Seitenfehler bei einer gegebenen Speichergrš§e minimiert wird.
Daher:
Versuchen, auf Grund der vergangenen Referenzen die zukŸnftigen Referenzen
vorherzusagen.
TatsŠchlich gibt es eine solche Strategie und sie lautet:
ãWŠhle (zum Auslagern) die Seite, die am lŠngsten nicht mehr benštigt werden wird.Ò
LokalitŠtsprinzip bedeutet:
Optimale Strategie: 3 Seitenfehler (ohne Initialseitenfehler)
Zeit
1
Referenz 0
Kachel 1 0
Kachel 2
Kachel 3
2
2
0
2
3
4
0
2
4
4
3
0
2
3
5
2
0
2
3
6
3
0
2
3
7
0
0
2
3
8
1
0
1
3
5-91
9
0
0
1
3
10
3
0
1
3
Das Zugriffsverhalten in der unmittelbaren Vergangenheit ist eine gute SchŠtzung fŸr das
Verhalten in der unmittelbaren Zukunft.
11
0
0
1
3
12
2
2
1
3
Auswahl basiert auf
¥
HŠufigkeit der Zugriffe auf eine Seite
¥
Zeitpunkte der Zugriffe
5-92
FIFO-Strategie
Realisierbare Strategien
FIFO-Strategie (first-in-first-out) 4 Seitenfehler
¥
FIFO
(First-In-First-Out)
Zeit
1
Referenz 0
Kachel 1 0
Kachel 2
Kachel 3
Ausgelagert wird die Seite, die am schon am lŠngsten im Speicher ist
¥
LFU
(Least Frequently Used)
Ausgelagert wird die Seite, die am wenigstens hŠufig referenziert wurde
¥
LRU
RNU
3
4
0
2
4
4
3
3
2
4
5
2
3
2
4
6
3
3
2
4
7
0
3
0
4
8
1
3
0
1
9
0
3
0
1
10
3
3
0
1
11
0
3
0
1
12
2
2
0
1
(Least Recently Used)
Ausgelagert wird die Seite, die am lŠngsten nicht mehr refenziert wurde
¥
2
2
0
2
Man erwartet von einem Seitentauschalgorithmus, dass er weniger Seitenfehler produziert,
wenn mehr Speicher zur VerfŸgung gestellt wird.
(Recently Not Used)
Ausgelagert wird eine Seite, die innerhalb eines vorgegebenen Zeitraums nicht mehr
referenziert wurde
Die Seitenfehlerrate sollte bei steigender Kachelanzahl monoton fallen.
Diese Eigenschaft trifft auf die FIFO-Strategie nicht zu.
5-93
5-94
LFU (Least Frequently Used)
Anomalie bei FIFO-Strategie
Bei 4 Kacheln: 7 Seitenfehler
Zeit
1
Referenz 0
Kachel 1 0
Kachel 2
Kachel 3
Kachel 4
2
1
0
1
3
2
0
1
2
4
3
0
1
2
3
5
4
4
1
2
3
6
0
4
0
2
3
7
1
4
0
1
3
8
5
4
0
1
5
9
6
6
0
1
5
10
0
6
0
1
5
11
1
6
0
1
5
12
2
6
2
1
5
13
3
6
2
3
5
14
5
6
2
3
5
15
6
6
2
3
5
5
4
0
1
2
3
4
6
0
0
1
2
3
4
7
1
0
1
2
3
4
8
5
5
1
2
3
4
9
6
5
6
2
3
4
10
0
5
6
0
3
4
11
1
5
6
0
1
4
12
2
5
6
0
1
2
13
3
3
6
0
1
2
14
5
3
5
0
1
2
15
6
3
5
6
1
2
Zeit
1
2
3
4
5
6
7
8
9
10
11
12
Referenzen
0
2
4
3
2
3
0
1
0
3
0
2
Kachel 0
0
0
2
0
2
4
3
2
4
3
2
4
3
2
4
3
2
0
3
2
1
3
2
0
3
2
0
3
2
0
3
2
0
1
–
–
–
–
1
–
1
–
–
1
–
1
–
1
Kachel 1
Kachel 2
Bei 5 Kacheln: 8 Seitenfehler
Zähler
Zeit
1
Referenz 0
Kachel 1 0
Kachel 2
Kachel 3
Kachel 4
Kachel 5
2
1
0
1
3
2
0
1
2
4
3
0
1
2
3
5-95
0
1
2
3
4
(1) (1) (1) 2 (2) 3 3 4 4
– – – – 1 (1) (1) (1) (1)
1 2 2 2 2 2 2 2 3
1 1 2 2 2 2 3 3 3
1 1 1 (1) (1) (1) (1) (1) (1)
Der LFU-Algorithmus unterhŠlt fŸr alle Seiten einen ZŠhler, der bei jedem Zugriff
inkrementiert wird.
Im vorliegenden Beispiel werden vier Seitenfehler verursacht.
5-96
LRU (Least Recently Used)
LRU bedeutet, dass die am lŠngsten nicht mehr referenzierte Seite ausgelagert wird.
Man kann dies leicht mit einem Stapel (stack) realisieren, bei dem die jŸngst zugegriffene
oben auf den Stapel gelegt wird.
Beispiel fŸr LRU-Strategie (4 Seitenfehler)
Andere Seiten ãrutschenÒ dadurch nach unten.
Bei k Kacheln sind die k obersten Seiten des Stapels im Speicher
Zeit
1
Referenz 0
Kachel 1 0
Kachel 2
Kachel 3
0
Stapel
Zugriff auf Seite 5 (im Stapel)
3
7
4
9
5
8
1
t=i
Zugriff auf Seite 6 (nicht im Stapel)
5
3
7
4
9
8
1
3
7
4
9
5
8
1
6
3
7
4
9
5
8
t = i+1
t=i
t = i+1
2
2
0
2
2
0
3
4
0
2
4
4
2
0
4
3
3
2
4
3
4
2
5
2
3
2
4
2
3
4
6
3
3
2
4
3
2
4
7
0
3
2
0
0
3
2
5-97
8
1
3
1
0
1
0
3
9
0
3
1
0
0
1
3
10
3
3
1
0
3
0
1
11
0
3
1
0
0
3
1
12
2
3
2
0
2
0
3
5-98
RNU (Recently Not Used)
Die LRU Strategie schaut also in die Vergangenheit und wŠhlt die Seite, deren letzter
Zugriff am weitesten zurŸckliegt.
RNU ist Šhnlich wie LRU, arbeitet jedoch mit einem festen ãZeitfensterÒ der LŠnge k, das
Ÿber die Referenzfolge geschoben wird.
Sie ist damit symmetrisch zur optimalen Strategie OPT, die in die Zukunft schaut und
diejenige Seite auswŠhlt, deren nŠchster Zugriff am weitesten vorausliegt.
FŸr eine Auslagerung in Frage kommen alle Seiten, die innerhalb des Fensters nicht
referenziert wurden.
rückwärts
vorwärts
Die Fenstergrš§e k ist so wŠhlen, dass Anzahl der RNU-Seiten klein, aber > 0
ri m ri-m+1 .... ri 1 ri ri+1 .... ri+m-1 ri+m
aktueller Zeitpunkt
Beispiel fŸr RNU-Strategie (4 Seitenfehler)
(fŸr Fenstergrš§e k=2)
-1
Sei R ein Referenzstring und R der zu R invertierte Referenzstring.
Dann gilt:
Die Seitenfehlerzahl, die entsteht, wenn LRU auf R angewendet wird, ist gleich der
Seitenfehlerzahl, die OPT angewendet auf R-1 erzeugt.
(... und umgekehrt)
5-99
Zeit
1
Referenz 0
Kachel 1 0
Kachel 2
Kachel 3
2
2
0
2
3
4
0
2
4
4
3
3
2
4
5
2
3
2
4
6
3
3
2
4
7
0
3
2
0
5-100
8
1
3
1
0
9
0
3
1
0
10
3
3
1
0
11
0
3
1
0
12
2
3
2
0
Anmerkungen zur Realisierung
AngenŠherte LRU/RNU-Strategie
Alle realisierbaren Strategien erfordern bei jedem Zugriff gewisse Datenoperationen
(z.B. Stack-Operationen, ZŠhlerinkrementierung,..)
Die Referenzindikatoren geben an, auf welche Seiten zugegriffen wurde, geben aber keine
Auskunft Ÿber den Zeitpunkt des letzten Zugriffs.
Sie vollstŠndig in Software durchzufŸhren ist zu aufwendig.
Da eine Seite nur bei Zugriff eingelagert wird, sind ohnehin alle Referenzindikatoren 1 und
daher nicht hilfreich bei der Auswahl.
Auch eine Hardware-UnterstŸtzung (erweiterte Funktion des TLB) wird i.a. aus
AufwandsgrŸnden nicht vorgesehen.
Die Referenzindikatoren mŸssen deshalb periodisch zurŸckgesetzt werden,
damit man erkennen kann, auf welche Seiten aktuell noch zugegriffen wird.
Man begnŸgt sich daher mit leichter realisierbaren AnnŠherungsverfahren.
Präsenzindikatoren
Von den diskutierten Verfahren zeigt LRU i.d.R. das beste Verhalten, d.h. LRU fŸhrt zur
geringsten Seitenfehlerrate.
Referenzindikatoren
0
0
1
1
1
-
Die in realen Betriebssystemen zu findenden Seitentauschstrategien sind daher leicht
realisierbare Varianten von LRU
2
1
1
3
0
Mit der Ÿblichen Hardware-UnterstŸtzung, d.h. der Aktualisierung von Referenzbits bei
jedem Zugriff auf eine Seite, lŠsst sich LRU bzw. RNU annŠhern.
4
1
5
0
–
Setzen bei
individueller
Referenz
-
–
0
-
–
Periodisch
gemeinsam löschen
5-101
5-102
„Second Chance“-Algorithmus (Clock-Algorithmus)
Second-Chance-Algorithmus (Clock-Algorithmus)
Referenzindikatoren
Der Clock-Algorithmus ist insofern geschickter, als er die Referenzindikatoren nicht alle auf
einmal zurŸcksetzt, sondern immer nur Teilmengen:
¥
Der Vektor der Referenzbits wird zyklisch durchlaufen.
¥
Bei der Suche nach einem Kandidaten wird die nŠchste Seite gewŠhlt, deren
Referenzbit 0 ist.
¥
Im Zuge dieser linearen Suche werden alle besuchten Referenzindikatoren
zurŸckgesetzt.
¥
¥
Auswahlzeiger
0
0
1
0
0
0
1
1
1
1
0
1
0
1
0
1
0
0
1
0
1
1
0
1
Sie haben - bis der Zeiger das nŠchste Mal vorbeikommt - eine weitere Chance,
referenziert zu werden
1
Ausgelagert wird also eine Seite, die seit dem letzten Durchlauf des Auswahlzeigers
nicht wieder referenziert wurde.
1
0
0
Vor Auswahl
5-103
0
Auswahlzeiger
0
1
Auswahlzeiger
1
1
1
0
1
Nach Auswahl
Nach weiteren Referenzen
5-104

5 Speicherverwaltung 5.1 Belegungsverfahren Aufgabenstellung

Transcrição

Documentos relacionados

Nun will der Lenz uns gruessen

Warndienst West 01-2015 - Landwirtschaftskammer Schleswig

Nordverbund Schulbegleitforschung

Adobe Photoshop PDF

Design zum anfassen! Besondere Produkte im

* PC-Shop Wiedervermarktung Lageplan

Wetterstation „Mindelheimer Hütte“

Gesundheitsfoerdernde_Soziale_Arbeit

Yaro Yanomama thã turu Yaro Yanomama thã turu Yaro Yanomama

Flyer IP kurdisch