Kapitel 6 - Speichermanagment
- Freispeicherverwaltung durch Bitmaps, Listen und Buddy
- Mehrdimensionale Adressräume durch Segmentierung
- virtueller Speicher durch Paging
- Zusammenwirken von Segmentierung und Paging
- Adressumrechnung am Beispiel
|
Übersicht zur Freispeicherverwaltung
Es gibt drei grundlegende Ansätze zur Verwaltung des freien Speichers. Diese werden
im folgendem Text erläutert.
Was sind Bitmaps?
Bitmaps teilen den Hauptspeicher in gleich große Einheiten und assoziieren zu
jedem Eintrag ein Bit in der Bitmap. Ist der Eintrag 0, so ist der Speicherbereich
noch frei. Bei Nutzung eines Speicherbereiches wird in dem assoziierenden
Bitmapplatz eine eins platziert. Umso kleiner die zusammengefassten Einheiten
werden, umso größer wird die Bitmap. Der größte Nachteil von Bitmaps ist das Suchen
von freien Speicherbereichen, was eine aufwendige Operation darstellt.
Welche Möglichkeiten der Suche in Freispeicherlisten gibt es?
Bei dieser Variante werden Listen für Löcher und belegte Segmente durch
Prozesse geführt.
First Fit
Der erste freie Block der groß genug ist wird ausgewählt, egal wieviel Speicher
dadurch verschwendet wird (interne Fragmentierung).
Next Fit
Suche beginnt nicht vom Anfang der Liste, sondern vom zuletzt verwendeten
Listenelement.
Best Fit
Es wird der optimale Platz in Bezug auf Speicherausnutzung gesucht. Dadurch das
immer Blöcke mit der geringsten Speicherplatzverschwendung gesucht werden, werden
die freien Blöcke irgendwann zu klein.
Quick Fit
Es gibt mehrere Listen für verschiedene Blockgrößen.
Wie funktionieren Buddy Listen?
Listen haben den Nachteil, daß benachbarte freie oder belegte Speicherbereiche
sich nicht zusammenlegen lassen. Abhilfe schafft hier das Buddy-System. Die Idee
beruht darauf, dass mehrere Listen geführt werden, welche aber nur Blockgrößen von
2^n zulassen. Zweierpotenz deshalb, weil ein Rechner Binärzahlen zur Adressierung
benutzt.
Beispiel:
Die maximale Blockgröße beträgt 64 Mbytes und die minimale Blockgröße 4 Kbyte. D.h.
226 - 212, also müssen Listen für N=12 bis N=26 verwaltet werden. Somit wären für
diese Blockgrößenwahl mit dem Buddysystem 15 Listen notwendig.
Anfragen werden nun immer zur nächsthöhren Zweierpotenz aufgerundet. D.h. wird eine
Anfrage an einen 75 Kbyte Block gestellt, muss ein 128 Kbyte großer Slot verwendet
werden. Anfangs gibt es eine Liste für in unserem Beispiel 64 Mbyte Speicher. Der
Buddymanager würde die Liste rekursiv so oft teilen, bis ein 128 Kbyte großer Block
in eine der anderen Listen frei ist.
Falls die angeforderten Blockgrößen aussschliesslich Zweierpotenzen wären, würde es
zu keiner Internen Fragmentierung kommen können. Da dies aber nie der Fall ist,
wird viel Speicher durch interne Fragmentierung verschwendet.
Zusammenfassung Freispeicherverwaltung
Bitmaps unterteilen den Speicher in Allokationseinheiten. Für
jede Einheit gibt es ein Bit im Bitmap. Verknüpfte Listen bieten Suchmöglichkeiten
mit First Fit, Best Fit oder Quick Fit. Quick Fit setzt mehrere Listen bestimmter
Lochgößen voraus. Das Buddy System verwaltet n Listen von 1,2, 4, 8 bis zur Größe
des Speichers. D.h. ein 1 MByte großer Speicher benötigt 21 Listen und hat Initial
nur einen einzigen Eintrag in der letzten Liste, der das 1 MByte große Loch
beschreibt. Alle anderen Listen sind leer. Speicher wird nun immer in Abhängigkeit
von einer Potenz von 2 vergeben, der gerade noch groß genug ist, um die Daten
aufzunehmen. Dies wird einfach implementiert, in dem der Große block einfach
solange geteilt wird, bis der Datenblock in den Freispeicherblock passt. Das
Buddysystem ist zwar schnell, aber impliziert eine starke interne
Fragmentation, da ja immer auf Zweierpotenzen gerundet werden muss.
- einfache verkettete Listen mit Best-,Next- oder First-Fit Suche
- Bitmap-System welches Speicher in gleichgroße Einheiten teilt
- Buddy-Listen nach dem binären System
Merktabelle: Methoden zur Freispeicherverwaltung
Wie arbeitet Segmentierung (mehrdimensionale Adressräume)?
Eindimensionale Adressierung hat den Nachteil, daß Programme mit verschieden
dynamisch wachsenden Programmteilen nur schlecht realisierbar sind. Code, Stack und
Daten würden hintereinander im Speicher liegen. Benötigt ein Programm aber extrem
viele Variablen, würde der Compiler mit der Fehlermeldung abbrechen, daß es nicht
genug Speicher gäbe. Um nun mehrere Stack, Daten und Codebereiche getrennt
voneinander adressieren zu können, ohne daß die verschiedenen Teile in Konflikt
geraten, wurden die Segmente eingeführt.
Segmentierte Speicherung wird oft als das Prinzip der gestreuten
Speicherung benannt. Gestreut deshalb, weil die einzelnen Seiten nicht
nacheinander im Speicher liegen müssen, sondern dort eingefügt werden, wo Platz
ist. Anders als z.B. bei Kontinuierlicher Allokation, wo viel Speicher durch
externe Fragmentierung verlorengeht, tritt bei Segmentation dieses Problem nicht
auf. Dafür aber interne Fragmentierung...
Wie werden Segmenten adressiert?
Um mit Segmenten arbeiten zu können, sind zweiteilige Adressen notwendig,
bestehend aus Segment und Offset. Die
Segmentation muss also dem Programmierer bewusst sein, da ein Segment nur eine
logische Einheit darstellt. Besonders einfach gestaltet sich das übersetzen von
Prozeduren. Angenommen jede Prozedur hat ihr eigenes Codesegment, benötigt man nur
die Segmentnummer, um die Funktion aufzurufen, da der Eintrittspunkt bei der
logischen Adresse 0 dieses Segmentes ist.
Wird nun eine Prozedur neu kompiliert, müssen die restlichen Prozeduren nicht neu
kompiliert werden, da der Eintrittspunkt immer noch der gleiche ist. Und zwar 0.
Die Segmentnummern werden eh dynamisch vergeben.
Was versteht man unter gemeinsam genutzten Segmenten?
Durch Segmentierung wird es sehr einfach, verschiedene Codesegmente gemeinsam
zu nutzen. So genannte Shared Libraries sind in jedem modernen
Betriebssystem notwendig, denn sie stellen für viele Programme Frameworks oder
API's bereit, deren Funktionalität sich jedes Programm bedienen kann, soweit es die
dafür notwendigen Zugriffsrechte hat. Ob ein Segment ausführbar ist oder nicht,
wird über die Schutzart des Segmentes definiert.
Wie funktioniert das Prinzip des virtuellen Speichers durch Paging?
Um mehr Speicher bereitzustellen werden statt echter physikalischer Adressen
virtuelle benutzt, welche durch die MMU in reale Adressen bei Benutzung umgewandelt
werden. Durch das Paging können Seiten aus- oder eingelagert (nach einem Page
Fault) werden. Eine Page Table referenziert virtuelle auf
physikalische Adressen. Swapping ist in Reinform sehr langsam. Sinnvollerweise
werden Segmente in Seiten geteilt, welche durch Paging ein oder ausgelagert werden.
(Protected Mode) Die MMU kann, muss aber nicht auf der CPU liegen. Jede
Seitentabelleneintrag hat ein Present/Absent Bit, welches Auskunft darüber gibt, ob
eine Seite sich im Speicher befindet oder nicht. Des Weiteren vermerkt eine Art
Dirty Bit, ob eine Seite im Speicher geändert wurde, um
entscheiden zu können, ob ein zurück schreiben notwendig wird.
Die momentan verwendeten Seiten eines Programmablaufes wird Working
Set genannt. Demand Paging bedeutet, dass Seiten erst dann abgefordert
werden, wenn sie benötigt werden.
Eine virtuelle Adresse besteht aus Seitenummer und Offset. Bei
einem Contextswitch wird nach der entsprechenden Seitennummer in der Page Table
gesucht und die zugehörige physikalische Adresse errechnet. Es wird meist ein
n-stufiges Paging angewandt, um die Suche mach den Seiten zu beschleunigen (Unix) .
Bei i386 gibt es ein so genanntes Seitenverzeichnis (DIR) mit 1024
Zeilen, welche wiederum je auf eine Seitentabelle verweisen. Somit enthält eine
lineare Adresse beim Intel DIR,PAGE und OFFSET Teil. (mehrstufiges Paging)
Beim Swapping werden statt Seiten ganze Prozesse ausgelagert.
- Demand Paging und Caching basieren auf den gleichen Prinzip
- Sie arbeiten nur auf verschiedenen Ebenen
- Cache-Misses werden von der Hardware geregelt, Page Faults vom Betriebssystem
Merktabelle: Virtual Memory und Caching
Was ist der Translation Lookaside Buffer?
Um die Zeit der Adressumrechnung zu vermindern, wird in der MMU ein
Assoziativspeicher mit meist nicht mehr als 32 Einträgen
verwaltet. Die Einträge enthalten die zuletzt verwendeten virtuellen Seiten mit der
dazugehörigen Seitenrahmennummer im Speicher. Gleichzeitig wird dort vermerkt,
welche Art von Lese/Schreibzugriff erlaubt ist und ob die Seite verändert wurde.
Kommt eine Anforderung auf eine nicht im TLB vorhandene Seite, wird ein Eintrag aus
dem TLB mit der neu dekodierten Adresse überschrieben, so daß bei der nächsten
Anfrage die Adressumrechnung entfallen kann.
- TLB's werden verwendet, wenn Seitentabelle auf Grund eines zu großen Adressraumes nicht möglich ist
- TLB bildet zuletzt genutzten (64 bei UltraSparc) virtuellen Seitennummern auf physikalische Seitenrahmen ab
- häufig benutzte Seiten werden in einem Cache (Translation Storage Buffer) verwaltet
- Dieser Cache bildet Seiten direkt ab und wird bei TLB-Miss zuerst untersucht
- befindet sich die Seite nicht im Cache, muss sie in der Translation Table gesucht werden
Merktabelle: Translation Lookaside Buffer
Was sind invertierte Page Tables?
Eine Seitentabelle enthält hier einen Eintrag für jeden Seitenrahmen des
physikalischen Speichers. Der Eintrag enthält Informationen über den besitzenden
Prozess und die virtuelle Seite. So entspricht die Anzahl der Einträge der Anzahl
der Seitenrahmen im Speicher. Die Tabelle verwaltet nur, welche Seite, von welchem
Prozess in den Seitenrahmen des Arbeitsspeicher geladen wurden.
Was sind Paging Dämons?
Paging arbeitet nur effizient, wenn jederzeit genügend Seitenrahmen im
Speicher frei sind, um diese bei einem Page Fault neuen Seiten belegen zu können.
Doch wie wird sichergestellt, daß der Speicher komplett ausgefüllt werden muss und
somit bei einem Page Fault erst eine Seite ausgelagert werden muss? Viele
Betriebssysteme haben dafür einen speziellen Dienst vorgesehen. Der Paging Dämon
wird in zyklischen Abständen aktiviert. Dieser schaut nun nach ob genügend
Frames im Speicher zur Verfügung stehen. Ist dies nicht der Fall,
werden so viele Seiten wie notwendig mit einem der
Seitenersetzungsalgorithmen aus dem Speicher entfernt und auf die
Platte zurückgeschrieben.
Erklären Sie das Zusammenspiel von Segmentierung und Paging?
Um beide Vorteile (Mehrdimensionalität und virtuellen Speicher) nutzen zu
können, werden in fast allen modernen Betriebssystemen beide Techniken angewandt.
Dabei wird das Paging transparent, also für den Programmierer
nicht sichtbar, hinter die Segmentierung geschalten. Auf dieser Basis bauen sich
auch die Adressen dieser Maschinen auf. Es gibt verschiedene Implementationen von
Segmentierung und Paging. Aber letztendlich haben sie eines gemeinsam. Die logische
Adresse besteht aus
- die Segmentnummer zur Auswahl des richtigen Segmentdeskriptors und
- den Offset zur Adressierung innerhalb des Segmentes.
Die Implementierungen unterscheiden sich nun in der Verwaltung der
Deskriptoren und der Art und Weise wie die aus Segment + Offset
entstandene virtuelle Adresse über die Page Table auf den realen Speicher
projiziert bzw. umgerechnet wird.
Was passiert wenn Sie ein Programm starten?
- Der Virtual Memory Manager verwaltet den virtuellen Speicher.
- Bei Programmstart richtet das BS für den Prozess eine Seitentabelle ein.
- Eine definierte Anzahl Rahmen werden dem Prozess als Arbeitsmenge zugeteilt.
- Seiten aus dem Read-Only Bereich der EXE werden direkt geladen und brauchen
nicht zurückgeschrieben werden.
- Read-Write Bereiche werden zuerst direkt aus der EXE geladen und im Speicher
hinterlegt.
- Bei einem Schreib-Bezug wird sie als private Kopie in die Auslagerungsdatei
geschrieben. So können mehrere Prozesse die selbe EXE im benutzen. (Copy On
Write)
Der VMM von Windows verwaltet mehrere Listen für:
- freie Seiten, welche mit 0 initialisiert wurden (zerofilled)
- uninitialisierte freie Seiten, die noch alten Inhalt haben
- wartende Seiten, die Prozess zugewiesen waren und nicht modifiziert
wurden(standby pages)
- wartende, aber modifizierte Seiten (modified pages)
- belegte Seiten, welchen einem Prozess zugewiesen / referenziert sind (valid
pages)
- unbenutzbare Seiten, durch z.B. Hardwarefehler (unusable pages)
Wie arbeitet die Adressumrechnung der Multics?
- mit Segmentnummer wird Segmentdeskriptor festgestellt
- es wird geprüft, ob die Pagetable des Segmentes im Speicher ist
- ist sie nicht im Speicher tritt ein Segmentfehler auf und es erfolgt ein Trap
- ist sie im Speicher wird der Pagetableeintrag für die angefragte Seite
überprüft
- falls Seite nicht im Speicher entsteht Page Fault
- ist Seite im Speicher wird die physikalische Adresse des Seitenursprungs aus
dem Pagetableeintrag entnommen
- Der Offset wird zur gewonnenen Adresse hinzuaddiert und die physikalische
Adresse ist berechnet.
(nach Tanenbaum)
Meist wird ein Assoziativspeicher verwendet, um die letzten paar Umrechnungen ohne
Verzögerung ausgeben zu können. Ein TLB enthält zwei Vergleichsfelder für
Segmentnummer und korrespondierende virtuelle Seite und einige zusätzliche
Attribute, wie Schutzattribute, Age oder Referenziert-Bits.
Wie funktioniert die Adressumrechnung beim P2?
Intel Prozessoren besitzen ab dem i386 eine LDT (local
descriptor table) und eine GDT (global descriptor table). Die
Local Descriptor Tables enthalten die programmeigenen Segmente, wie Stack-, Code-
und Datensegment der verschiedenen Benutzerprogramme. Die Global Descriptor Table
enthält dagegen die Systemsegmente samt deren des Betriebssystems , welche erst
geladen werden muss. Wird ein Segmentselektor in ein Segmentregister geladen, wird
der entsprechende Bezeichner aus der LDT oder GDT geholt und in MMU Registern
gespeichert. Ob L- oder GDT kann dem Selektor entnommen werden, da dort ein Bit für
diese Auswahl reserviert ist. Der Deskriptor besteht nun aus der Basisadresse des
Segmentes, der Größe des Segmentes und verschiedenen Privilegbits. Es wird nun eine
virtuelle Adresse über Segmenteselektor + Offset gebildet. Bei deaktiviertem Paging
ist nun diese Adresse die lineare physikalische. Ist aber Paging aktiv wird die
Adresse als virtuell interpretiert und über die Seitentabelle auf den realen
Speicher abgebildet.
Was haben Deskriptoren mit Sicherheit und Segmentverwaltung zu tun?
Jeder Deskriptor in einer Deskriptortabelle ist mehrere Byte breit und enthält
Beschreibungsinformationen für ein Segment aus dem linearen Adressraum. Neben der
Segment-Basisadresse (BASE) enthält er das LIMIT, das die Segmentgröße angibt.
Dabei wird durch ein Granularitätsbit festgelegt, ob das LIMIT direkt als Länge
interpretiert wird (Segmentgrößen bis 1 MB) oder mit dem Wert 4096 multipliziert
wird und damit Segmentgrößen bis 4 GB unterstützt. Der Descriptor-Privilege-Level
gibt an, mit welcher Berechtigungsstufe der Zugriff auf das Segment erfolgen muss:
- Level 0: Betriebssystem
- Level 1, 2: Betriebssystemdienste, Treiber, Systemsoftware
- Level 3: Anwendungssoftware
Weitere Informationen im Deskriptor zeigen an, ob auf das Segment lesend,
schreibend oder ausführend zugegriffen werden darf und ob es sich um ein System-
oder Anwendungssegment handelt. Ein Present-Bit gibt an, ob das Segment sich
derzeit überhaupt im Hauptspeicher befindet.
Zusammenfassung von Freispeicherverwaltung, Segmentierung und Paging
Segmentierung wird genutzt, um statt einen linearen Adressraum (wie beim
virtuellen Speicher), mehrere virtuelle Adressräume nutzen zu können. Segmentierung
wurde entworfen, um dynamisch wachsende Tabellen besser Handhaben zu können. Somit
ist schafft Segmentierung einen mehrdimensionalen Adressraum.
Unter Swapping versteht man das komplette Ein- und Auslagern von Prozessen. Das
Swapping des segmentierten Speichers ist vergleichbar mit dem Demand-Paging des
virtuellen Speichers. Nur das Segmente unterschiedlich groß sein können. Aus diesem
Grund tritt hier das Problem der externen Fragmentierung auf.
Um die externe Fragmentierung zu minimieren, werden die Löcher als verkettete Liste
im Speicher gehalten. Falls ein Segment geladen werden soll, sucht z.B. Best Fit,
dass nächst größere Loch unter allen, wo das Segment passen würde. First Fit nimmt
das Nächste Loch, welches für das Segment groß genug wäre.
Neben dem Swapping kann auch Paging zum Auslagern von Segmenten benutzt werden.
Hierbei sind die auszulagernden Blöcke gleich groß, da die Segmente in gleich große
Seiten eingeteilt werden. Zur Auslagerung wird das bekannte Demand Paging benutzt.
Meist wird eine Kombination aus Segmentierung und Paging angewandt, bei der die
Adresse aus zwei Teilen besteht. (Segmentnummer und Offset innerhalb des Segments).
Segmente werden also in Seiten unterteilt. Zur Leistungsverbesserung werden die
zuletzt verwendeten Segment-Seiten- Kombinationen in einem Assoziativspeicher (TLB)
gehalten. Im Gegensatz zum Paging ist es beim reinen Swapping nicht möglich,
Prozesse auszuführen, die alleine schon nicht in den Hauptspeicher passen.
Bitmaps unterteilen den Speicher in Allokationseinheiten. Für jede Einheit gibt es
ein Bit im Bitmap. Verknüpfte Listen bieten Suchmöglichkeiten mit First Fit, Best
Fit oder Quick Fit. Quick Fit setzt mehrere Listen bestimmter Lochgößen voraus. Das
Buddy System verwaltet n Listen von 1,2, 4, 8 bis zur Größe des Speichers. D.h. ein
1 MByte großer Speicher benötigt 21 Listen und hat Initial nur einen einzigen
Eintrag in der letzten Liste, der das 1 MByte große Loch beschreibt. Alle anderen
Listen sind leer. Speicher wird nun immer in Abhängigkeit von einer Potenz von 2
vergeben, der gerade noch groß genug ist, um die Daten aufzunehmen. Dies wird
einfach implementiert, in dem der Große block einfach solange geteilt wird, bis der
Datenblock in den Freispeicherblock passt. Das Buddysystem ist zwar schnell, aber
impliziert eine starke interne Fragmentation, da ja immer auf Zweierpotenzen
gerundet werden muss.
|
|
|
|
|
|
Kapitel 1
|
Einleitung
|
|
Ebenen- oder Schichtenmodell, Aufgaben...
|
|
Kapitel 2
|
Modelle
|
|
Schichtenmodell, Betriebsmittel, Instanzen...
|
|
Kapitel 3
|
Aktivitäten
|
|
Token, Multitasking, Prozesse,Timesharing...
|
|
Kapitel 4
|
Kritischer Abschnitt
|
|
Gegenseitiger Ausschluss,Peterson,Semaphore...
|
|
Kapitel 5
|
Scheduling
|
|
Prozessorzuteilung, Prioritätsscheduling, RR...
|
|
Kapitel 6
|
Speichermanagment
|
|
Freispeicherverwaltung, Segmentierung, Paging...
|
|
Kapitel 7
|
Seitenersetzung
|
|
NRU, FiFo, Second Chance, LRU, NFU, Aging...
|
|
Kapitel 8
|
Deadlocks
|
|
Bedingungen, Erkennung und Auflösung...
|
|
Kapitel 9
|
Dateisysteme
|
|
Freispeicherverwaltung, Festplattenscheduling...
|
|
|
|
|
|
|
|
Quellen:
|
Andrew S. Tanenbaum
Computerarchitektur
|
Andrew S. Tanenbaum
Moderne Betriebssysteme
|
Petterson
Computer Architectur & Design
|
Christian Märtin
Rechnerarchitekturen
|
Kalfa
Skript und Vorlesung
|
Word Wide Web
Verschiedenste Seiten
|
|
|
|
|
