Speicherverwaltung Adressbindung

Speicherverwaltung
Warum?
–
Wodurch?
–
Mehrere Prozesse gleichzeitig im Speicher (bessere
Ausnutzung, höhere Bequemlichkeit).
Speicherverwaltungskomponente im OS (Memory
Manager).
Speichersparvarianten:
–
SS 2007
Dynamic Loading; Dynamic Linking; Overlays.
VO Betriebssysteme
60
Adressbindung
Bindung: Zuordnung eines Programmelements
(Symbol: Variable, Funktion, ...) zu einer
Speicheradresse.
Adressierung kann absolut oder relativ sein.
Zeitpunkt der Bindung:
–
Compile Time: absolute.
–
Load Time: relocatable.
–
Execution Time: durch HW.
SS 2007
VO Betriebssysteme
61
Adressen
Adressraum: physikalisch (Speicher),
logisch/virtuell (CPU):
–
Gleich für Compile Time und Load Time Bindung.
–
Verschieden für Execution Time Bindung: benötigt MMU.
Einfache MMU: Base/Relocation Register (+Limit).
Limit R.
CPU
logisch
<
ja
nein
Relocation R.
+
physikalisch
MMU
Hauptspeicher
Fehler
SS 2007
VO Betriebssysteme
62
Speicherpartitionierung
Einfache MMU ermöglicht Zuteilung eines
zusammenhängenden Speicherbereichs (Partition).
–
Single Partition: Ganzer Hauptspeicher steht einem Job
zur Verfügung. MMU schützt OS.
–
Fixed Partitions: Hauptspeicher aufgeteilt in (verschieden
große) Partitionen. Job-Queue gemeinsam oder pro
Partition.
–
Variable Partitions: Partitionsgröße und -anzahl nicht fix.
Anzahl der Partitionen bestimmt den Grad des
Multiprogrammings (Degree of Multiprogramming).
SS 2007
VO Betriebssysteme
63
Vergabeverwaltung
Notwendig bei variabler Partitionsgröße.
Verwaltung belegter und freier
Speicherbereiche durch:
–
Bitmaps: Ein Bit pro Speicherblock zeigt Belegung an.
–
Free Lists: Verkettete Liste freier Speicherbereiche.
Vergabestrategien:
–
First Fit; Next Fit; Best Fit; Worst Fit; Quick Fit.
–
Erzeugen „Löcher“ im Speicher.
Fragmentierung: Extern / Intern.
SS 2007
VO Betriebssysteme
64
Swapping
Ist die Aus- bzw. Einlagerung von Partitionen, d.h.
zusammenhängender Speicherbereiche.
Notwendig, wenn mehr Speicher gebraucht wird als
vorhanden ist.
Benötigt Massenspeicher (z.B. Festplatte).
Nur möglich bei Jobs die nicht ausgeführt werden. (Auch
kein Datentransfer möglich).
Vorgang ist sehr zeitaufwändig.
Fragmentierung von Haupt- und Massenspeicher möglich.
Wird praktisch nicht verwendet (nur im Notfall).
SS 2007
VO Betriebssysteme
65
Weiterentwicklung - I
Ein Prozess darf sich über mehrere Partitionen
erstrecken, die verstreut im Speicher liegen können.
Zugeordneter Hauptspeicher eines Prozesses braucht
nicht zusammenhängend zu sein.
Externe Fragmentierung verschwindet.
Voraussetzung zur Umsetzung: Aufteilung des
Speichers in gleich große Blöcke.
–
Hauptspeicher (physikalische Adresse): Frame (Rahmen)
–
Prozessabbild (logische Adresse): Page (Seite)
–
Auslagerungsspeicher (Massenspeicher)
SS 2007
VO Betriebssysteme
66
Anwendung
page 3
page 1
page 0
Prozessabbild
(logische
Adressen)
SS 2007
5
X
7
3
4
1
Page
Table
page 1
4
page 2
3
2
page 0
1
Frame Nummer
page 2
Zuordnung von Pages
zu Frames erfolgt über
Seitentabelle (Page
Table).
Zur Ausführung
werden Pages in
Frames geladen.
Prozessabbild kann
größer als verfügbarer
Hauptspeicher sein.
6
page 4
page 3
7
0
Hauptspeicher
(physikalische
Adressen)
VO Betriebssysteme
67
Umsetzung
logisch
CPU
p
physikalisch
d
f
d
Seitennummer Seiten-Offset
Adresse:
p
d
m bit
m–n
n
Hauptspeicher
Aufteilen von (virtuellen)
Adressen in Seitennummer
und Seiten-Offset:
Seitengröße:
512 Byte – 16MB
(in Adressbits).
f
Typisch: 4kB.
Page Table
SS 2007
VO Betriebssysteme
68
Paging
Paging ist die Verwaltung des Speichers in
Speicherseiten in Verbindung mit HWUnterstützung zur Adressumsetzung.
Ermöglicht:
–
Aus- bzw. Einlagerung von Pages.
–
Virtuellen Speicher.
Benötigt:
–
Unterstützung durch die Hardware: MMU.
–
Eine Page Table pro Prozess.
–
Eine Frame Table zur Hauptspeicherverwaltung.
SS 2007
VO Betriebssysteme
69
Seiten-Attribute
Größe (hat Einfluss auf):
–
Interne Fragmentierung (~ ½ Seite).
–
Page Table Umfang und Verwaltungs-Overhead.
–
Effizienz der Auslagerung.
Gültigkeit und Zugriff:
–
Ist Seite als Frame im Hauptspeicher vorhanden?
–
Wurde darauf zugegriffen? / Wurden Daten verändert?
Rechte:
–
SS 2007
Beschränkung der Manipulationsmöglichkeiten.
VO Betriebssysteme
70
Probleme und Lösungen
Geschwindigkeit der Adressumsetzung:
–
Translation Look-Aside Buffer (TLB): Schneller
assoziativer Cache verbessert die Geschwindigkeit
der Umsetzung. Hohe Trefferrate ist sehr wichtig.
–
Muss bei jedem Kontextwechsel geleert werden.
Größe der Page Table:
–
Multilevel Page Tables: zwei- oder mehrstufige
Unterteilung der Seitennummer erlaubt Teile der
Page Table wegzulassen.
Top-Level Second-Level
p1
p2
SS 2007
VO Betriebssysteme
Offset
d
71
Paging – Spezielles
Invertierte Page Table:
–
Eine Tabelle verwaltet für jeden Frame des
Hauptspeichers einen Eintrag über Prozess und Seite.
–
Zugriff durch Suchen in dieser Tabelle (langsam).
Gemeinsame Seiten (Shared Pages):
–
Pages verschiedener Prozesse zeigen auf den selben
Frame im Hauptspeicher.
–
Macht gemeinsamen Datenbereich möglich.
–
Spart Platz bei mehrmaliger Ausführung des gleichen
Programms.
SS 2007
VO Betriebssysteme
72
Weiterentwicklung - II
Ein Prozess darf sich über mehrere Partitionen
erstrecken. Diese bilden unabhängige Adressräume.
Funktionale Einheiten eines Prozesses erhalten jeweils
eigene Partitionen geeigneter Größe (= Segmente).
Interne Fragmentierung verschwindet.
Voraussetzung zur Umsetzung:
–
Ergänzen jedes Speicherzugriffs um eine
Partitionsidentifikation.
–
Abbilden der unabhängigen Partitionen in einen
gemeinsamen Hauptspeicher.
SS 2007
VO Betriebssysteme
73
Segmentierung
Segmentierung ist die Verwaltung des
Speichers in Segmenten.
Umsetzung:
–
Adressen bestehen aus Segmentnummer und Offset
(zweidimensionale Adressierung).
–
MMU verwendet mehrere Base-/Limit-Register
(= Segment Table). Auswahl über Segmentnummer.
Erlaubt separaten Schutz sowie gemeinsame
Nutzung der „Komponenten“.
Führt zu externer Fragmentierung.
SS 2007
VO Betriebssysteme
74
Segmentierung mit Paging
Kombination aus Segmentierung und Paging.
Segmenttabellen-Eintrag verweist auf Page
Table für dieses Segment.
Bei großen Segmenttabellen auch Paging
dieser Tabellen möglich (MULTICS).
Effiziente Umsetzung benötigt Translation
Look-Aside Buffers.
Prominenter Vertreter: Intel i80386.
SS 2007
VO Betriebssysteme
75
Virtueller Speicher
Trennung von logischem und physikalischem
Speicher.
Erlaubt die Ausführung von Programmen die
nicht zur Gänze im Hauptspeicher sind.
Vorteile:
–
Prozess kann größer als der Hauptspeicher sein.
–
Mehr Prozesse können gleichzeitig ausgeführt werden.
–
Aus-/Einlagerung geht schneller (weniger Daten).
Demand Paging (oder Demand Segmentation).
SS 2007
VO Betriebssysteme
76
Demand Paging
Pager: Lagert nur benötigte Seiten ein und nicht
den ganzen Prozess (= Lazy Swapper).
Gültigkeit einer Seite muss markiert werden:
–
Seite im Speicher: valid => Memory Resident.
–
Seite nicht im Speicher: invalid => Page Fault.
Demand Paging: Einlagerung einer Speicherseite
wenn diese benötigt (= referenziert) wird.
Zugriffslokalität (Locality of Reference):
Aufeinander folgende Zugriffe liegen meist nahe
beisammen.
SS 2007
VO Betriebssysteme
77
Seitenersetzung
Virtueller Speicher und Multiprogramming
führen zu Überbuchung des Hauptspeichers.
Sind keine freien Frames verfügbar, müssen
belegte ausgelagert werden, um Platz zu
schaffen (Page Replacement):
–
Veränderte Seiten (dirty): Auslagerung notwendig.
–
Nicht veränderte Seiten: Überschreiben möglich.
Frame Allocation entscheidet, wieviele Seiten
einem Prozess zugeteilt werden.
SS 2007
VO Betriebssysteme
78
Optimaler Algorithmus
„Ersetze die Seite, die am längsten nicht
gebraucht wird.“
Hat die gerinste Page Fault Rate.
Nicht anfällig für Belady's Anomaly: Anzahl der
Page-Faults kann sich erhöhen, wenn mehr
Frames zur Verfügung stehen.
Nicht praktisch einsetzbar (niemand kennt die
Zukunft) aber zur Bewertung anderer
Algorithmen verwendet.
SS 2007
VO Betriebssysteme
79
Verwendete Algorithmen
FIFO Algorithmus:
–
Ersetzen der ältesten Seite.
–
Implementierung: Queue aller Seiten; neue Seite wird
angefügt; älteste Seite steht vorne.
–
Einfach, aber schlechte Performance.
LRU (Least Recently Used) Algorithmus:
–
Ersetzen der am längsten nicht verwendeten Seite.
–
Wie optimaler Algo., aber „schaut“ in die Vergangenheit.
–
Guter Algorithmus, aber schwer zu implementieren:
(i) mittels Zähler, (ii) mittels Stack.
SS 2007
VO Betriebssysteme
80
Näherungsweises LRU (1)
Benötigt Reference Bit: HW setzt ein Bit wenn
eine Seite angesprochen wird.
Second-Chance (Clock) Algorithmus:
–
Wie FIFO, aber prüft Reference Bit vor dem Ersetzen und
reiht referenzierte Seiten nochmals ein (Bit löschen).
–
Implementiert als zirkuläre Queue.
Enhanced Second-Chance Algorithmus:
–
Benötigt zusätzlich Modify Bit (HW).
–
Ergibt vier Klassen: (i) !ref., !mod.; (ii) !ref., mod.;
(iii) ref., !mod.; (iiii) ref., mod.
SS 2007
VO Betriebssysteme
81
Näherungsweises LRU (2)
Additional-Reference-Bits Algorithmus:
–
Reference Bit wird in regelmäßigen Intervallen in
einem Schieberegister an höchster Stelle
aufgezeichnet.
–
Register zeigt Information zu n Zeitpunkten in der
Vergangenheit.
–
Schieben des Registers führt zu Alterung der
Information.
–
Seite mit dem niedrigsten Registerwert wird ersetzt.
Pool freier Frames verbessert Reaktionszeit.
SS 2007
VO Betriebssysteme
82
Frame Allocation
Jeder Prozess benötigt minimale Anzahl Frames
(vorgegeben durch ISA).
Aufteilen des Hauptspeichers auf Prozesse:
–
Gleichmäßig (equal).
–
Anteilig (proportional) nach der Prozessgröße.
–
Gewichtung der Prozesspriorität.
Frame-Zuteilung:
–
Global: alle Frames des Systems werden einbezogen.
–
Local: nur prozesseigene Frames werden beachtet.
SS 2007
VO Betriebssysteme
83
Thrashing
Thrashing: andauerndes, schnelles Auftreten
von Seitenfehlern, weil der Prozess mehr Seiten
aktiv verwendet als ihm zur Verfügung stehen.
–
Bearbeitungsleistung bricht ein.
–
CPU-Auslastung sinkt stark.
–
Es sind zu viele Prozesse im System aktiv.
Lokalitätsmenge von Seiten: gemeinsam aktiv
genutzte Seiten.
Lokalitätsmodell der Prozessausführung:
Prozess wandert zwischen Lokalitätsmengen.
SS 2007
VO Betriebssysteme
84
Working-Set Modell
Working Set: Seiten, die in den letzten X
Zugriffen verwendet wurden (X = WS Window).
Summe aller Working Sets ergibt benötigte
Hauptspeicher-Frames. Thrashing tritt auf,
wenn dieser Speicher nicht vorhanden ist.
Alternative: Seitenfehler-Rate (Page Fault
Frequency PFF) pro Prozess:
–
Hoch: Prozess bekommt mehr Frames.
–
Niedrig: Prozess muss Frames abgeben.
SS 2007
VO Betriebssysteme
85
WSClock Algorithmus
Seitenersetzung basierend auf Working-Set
Modell.
Frames werden in zirkulärer Liste verwaltet und
haben R-Bit (Referenced) und Zeitstempel.
In Seiten mit gesetztem R-Bit wird der
Zeitstempel aktualisiert (R-Bit löschen).
Aus den Seiten ohne R-Bit wird die erste mit
ausreichendem Alter oder sonst die älteste
ausgewählt.
SS 2007
VO Betriebssysteme
86
Vermischtes zu Paging (1)
Swapping: kann notwendig werden, wenn es zu
Thrashing kommt.
Prepaging: Seiten werden vorsorglich
eingelagert (z.B. Programmstart).
Page Size: abhängig von der HW Architektur.
Inverted Page Table: Demand Paging benötigt
zusätzlich „normale“ Page Tables.
Shared Pages: ein Frame gehört mehreren
Prozessen: Kommunikation; Platz sparen.
SS 2007
VO Betriebssysteme
87
Vermischtes zu Paging (2)
I/O Interlock: Frames, die an I/O beteiligt sind
(DMA), müssen im Speicher gesperrt werden.
Real-Time Prozessing: benötigt Möglichkeit
Frames vor Paging zu sperren.
Paging Daemon: Lagert veränderte Seiten
periodisch aus => Paging findet Clean Pages.
Demand Segmentation: einfache Architekturen
unterstützen oft kein Demand Paging.
SS 2007
VO Betriebssysteme
88