Kapitel 6 - Speichermanagment
|
Inhalt
|
- 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
|
|
|
|
|
|
|
Home 
