Speicherverwaltung — Änderungen 2400 → 2405

Zeile 1: Zeile 1:
−
Memory Managment ist ein wichtiger Teil des Betriebssystem, um genau zu sein ist es ein Grundbestandteil eines Betriebssystem.
+
Die '''Speicherverwaltung''' (= '''Memory Management''') ist ein wichtiger Teil des [[Betriebssystem | Betriebssystems]]. Um genau zu sein ist es ein Grundbestandteil eines Betriebssystems und meistens sogar vollständig im [[Kernel]] enthalten.
  
 
== Einleitung ==
 
== Einleitung ==
−
Zuerst ist es wichtig zu wissen, was ein Memorymanager eigentlich machen soll. Generell ist der Memorymanager zuständig nachfragenden Prozessen freien Speicher zuzuteilen. Dafür muss natürlich gespeichert werden, welche Speicherbereiche belegt, bzw frei sind. Auch wichtig ist zu unterscheiden zwischen physikalischen Memorymanager und virtuellen Memorymanager. Der physikalische Memorymanager sucht freie Stellen im physikalischen Speicher. Der Virtuelle im virtuellen Speicher. Der physikalische Memorymanager liegt aber eine Schicht über dem virtuellen Memorymanager.
+
Generell ist die Speicherverwaltung dafür zuständig nachfragenden Prozessen freien Speicher zuzuteilen bzw. freizugebenden Speicher wieder zurückzunehmen. Dazu muss natürlich gespeichert werden, welche Speicherbereiche belegt bzw. frei sind. Es ist wichtig zu verstehen, dass die Speicherverwaltung normalerweise auf 2 Ebenen aufgeteilt wird: Zum einen die [[Speicherverwaltung#physische Speicherverwaltung | physische Speicherverwaltung]] und darauf aufbauend die [[Speicherverwaltung#virtuelle Speicherverwaltung | virtuelle Speicherverwaltung]].
  
−
== physikalischer Memorymanager ==
+
== physische Speicherverwaltung ==
−
Der physikalische Memorymanager muss Speicher allozieren und freigeben können. Dafür muss er immer bescheit wissen welcher Speicher schon belegt ist. Dafür gibt es zwei Möglichkeiten. Der physikalischer Memorymanager sollte aber immer so gestaltet sein, dass sich der Rest des OS keine Sorgen über Speicher machen muss.
+
Die '''physische Speicherverwaltung''' bildet die unterste Ebene und ermöglicht das Allozieren und Freigeben von physischen Speicherbereichen. Meist sind diese Speicherbereiche gleich groß und richten sich nach der Seitengröße der jeweiligen Architektur. Intern speichert die physische Speicherverwaltung welche Speicherbereiche im physischen Speicher frei sind. Dies könnte folgendermaßen implementiert werden:
  
−
=== Bitmap-Methode ===
+
=== Bitmap ===
−
Bei der Bitmap-Methode wird, wie der Name schon sagt, eine Bitmap verwendet. Jedes Bit gibt an ob eine Page frei ist oder nicht. Bei 4GB RAM benötigt man dafür eine 1kB große Bitmap. Um eine freie Page zu finden muss man einfach die Bitmap durchgehen und nachschauen wo die erste leere Page ist.
+
Dabei wird eine Bitmap der Größe ''Speichergröße / (Größe einer Speicherseite * 8)'' erstellt. Das x-te Bit dieser Bitmap gibt an ob die x-te Speicherseite (bzw. die Speicherseite an Adresse ''Größe einer Speicherseite * x'') frei oder belegt ist. Bei 4GB RAM benötigt man dafür eine 128kB große Bitmap.<br>
 +
==== Allokation & Freigabe von Speicherseiten ====
 +
Um eine Speicherseite zu allozieren wird die Bitmap solange durchsucht, bis man ein Bit mit dem Wert 0 gefunden hat. Dieses Bit setzt man dann auf 1, um anzuzeigen, dass diese Speicherseite ab jetzt belegt ist. Dann errechnet man anhand der Position dieses Bits in der Bitmap die Adresse der Speicherseite. Anschließend kann man die Adresse an die aufrufende Funktion zurückgeben.<br>
 +
Zum Freigeben einer Speicherseite muss nur die Bitposition aus der physischen Adresse berechnet werden und anschließend das Bit an der errechneten Position auf 0 gesetzt werden.
 +
==== Implementationsvorschläge ====
 +
* Wenn man sich die Bitposition der zuletzt allozierten/freigegebenen Speicherseite merkt, kann man zumindest im Normalfall das Allozieren von Speicherseiten beschleunigen.
 +
* Wenn man beim Allozieren gleich 32 bzw 64 Bit mit dem Wert 0xFFFFFFFF bzw. 0xFFFFFFFFFFFFFFFF vergleicht, kann man mit einem Vergleich gleich 32 bzw. 64 Speicherseiten ausschließen.
 +
==== Eigenschaften ====
 +
+ Das Allozieren physisch kontinuierlicher Speicherseiten ist möglich. (lineare Komplexität)<br>
 +
o Die Bitmap ist relativ klein.<br>
 +
o Das Freigeben einer Speicherseite ist in konstanter Zeit möglich. (konstante Komplexität)<br>
 +
- Zum Allozieren einer Speicherseite muss im schlechtesten Fall die gesamte Bitmap durchsucht werden. (lineare Komplexität)<br>
  
−
Vorteile:
+
=== Stack ===
−
* Bitmap verbraucht nur 1kB
+
Die Adressen der Speicherseiten werden hierbei auf einen Stack gelegt.
−
* Einfache Verwaltung von verschiedenen Speichertypen
+
==== Allokation & Freigabe von Speicherseiten ====
−
* Es können auch aneinanderhängende Pages gesucht werden
+
Zum Allozieren einer Speicherseite wird einfach die Adresse, die ganz oben auf dem Stack liegt, genommen. Anschließend wird der Zeiger auf das Stackende angepasst.<br>
−
Nachteile:
+
Das Freigeben einer Speicherseite exakt umgekehrt zur Allokation.
−
* Es muss jedes mal (theoretisch) die ganze Bitmap durchgeschaut werden
+
==== Implementationsvorschlag ====
−
 
+
Der Speicher, der für den Stack benutzt wird, wird aus den Speicherseiten, die auf den Stack gelegt werden sollen, erstellt. Dies kann folgendermaßen implementiert werden: Beim Start des Kernels ist der Stack erstmal leer. Desweiteren ist nur ein virtueller und kein physikalischer Speicherbereich für den Stack reserviert. Anschließend geht man die freien Speicherbereiche durch und legt jede freie Speicherseite auf den Stack. Da der Stack bei der ersten Speicherseite noch keinen Speicherbereich hat, nimmt man einfach diese Seite und blendet in den virtuellen Adressraum an der Adresse des Stacks ein. Anschließend können die Adressen einiger Speicherseiten auf den Stack gelegt werden, solange bis wieder kein Speicher vorhanden ist. Dann wird einfach die nächste Speicherseite, die auf den Stack gelegt werden soll, in den virtuellen Adressraum ein. Das kann man beim Freigeben natürlich analog implementieren und Speicherseiten, die in den virtuellen Adressraum engeblendet waren, wieder freigeben, falls dieser Speicherbereich nicht mehr vom Stack selbst benötigt wird. Somit verbraucht der Stack im Prinzip "keinen" Speicher.
−
=== Stack-Methode ===
+
==== Eigenschaften ====
−
Bei der Stack-Methode werden alle Adressen von freien Pages auf einen Stack gelegt. Wenn jetzt eine Page benötigt wird, muss man nur eine Adresse vom Stack nehmen. Umgekehrt, um eine Page freizugeben muss nur dessen Adresse wieder auf den Stack gelegt werden. Bei 4GB RAM benötigt man einen Stack von 4MB.
+
+ Das Allozieren einer Speicherseite ist in konstanter Zeit möglich. (konstante Komplexität)<br>
−
 
+
+ Der Stack verbraucht keinen Speicher.<br>
−
Vorteile:
+
o Das Freigeben einer Speicherseite ist in konstanter Zeit möglich. (konstante Komplexität)<br>
−
* Schneller Zugriff
+
- Das Allozieren physisch kontinuierlicher Speicherseiten ist unmöglich.<br>
−
Nachteile:
 
−
* Es werden 4MB für den Stack benötigt
 
−
* Es können keine aneinanderhängende Pages gesucht werden
 
−
* Man kann nur mit Umständen z.B zwischen RAM über und unter 16MB trennen (Hier empfielt sich die benutzung zweier Stacks)
 
  
 
=== Fazit ===
 
=== Fazit ===
−
Die Bitmap-Methode sieht zwar auf den ersten Blick viel besser aus, aber den Geschwindigkeitsunterschied zur Stack-Methode sollte man nicht unterschätzen.
+
Zusammenfassend lässt sich festhalten, dass eine Kombination aus den oben erklärten Datenstrukturen das Beste sein wird. Die Bitmap hat den Vorteil, dass man physisch kontinuierlichen Speicher allozieren kann. Dies benötigt man vor allem für [[DMA]]. Das heißt es macht Sinn bei der [[x86]]- bzw. [[x86-64]]-Architektur die unteren 1/16MB mit einer Bitmap zu verwalten. Der Stack hingegen hat einen unschlagbaren Geschwindigkeits- und Speichervorteil und kann für den Rest des Speichers verwendet werden.
  
−
== virtueller Memorymanager ==
+
== virtuelle Speicherverwaltung ==
−
Der virtuelle Memorymanager ist dafür zuständig die einzelnen Speicherbereiche der Prozesse zu organisieren. Das wird im Grunde so gemacht: Jeder Prozess bekommt beim Erzeugen mindestens ein Pagedirectory und ein Pagetable. Pagedirectory und Pagetable sind jeweils 4kB größ, die Pages können mithilfe des physikalischen Memorymanagers leicht und dynamisch angefordert werden. Wann immer man ein neues Pagedirectory oder Pagetable braucht, muss man einfach nur eine physikalische Page vom physikalischen Memorymanager anfordern. Natürlich braucht der Prozess auch noch Speicher den er benutzen kann, dieser wird auch mithilfe des physikalischen Memorymanagers angefordert werden und dann leicht in die Pagetables eingetragen werden. Beim Prozesswechsel muss man nur noch CR3 mit dem richtigen Pagedir laden. Man sollte natürlich auf keinen Fall vergessen den Kernel in jeden der Pagedirectories/Pagetables der Prozesse einzutragen.
+
Die '''virtuelle Speicherverwaltung''' befindet sich eine Schicht über der [[Speicherverwaltung#physischen Speicherverwaltung | physischen Speicherverwaltung]] und ist für die Organisation der Speicherbereiche im virtuellen Adressraum eines Prozesses zuständig. Dies bedeutet auch, dass sie das Ein- und Ausblenden von physischen Speicherseiten in den virtuellen Adressraum eines Prozesses übernimmt.<br>
 +
Das wird im Grunde so gemacht: Jeder Prozess bekommt beim Erzeugen mindestens ein Pagedirectory und ein Pagetable. Pagedirectory und Pagetable sind jeweils 4kB groß, die Pages können mithilfe der physischen Speicherverwaltung leicht und dynamisch angefordert werden. Wann immer man ein neues Pagedirectory oder Pagetable braucht, muss man einfach nur eine physische Speicherseite von der physischen Speicherverwaltung anfordern. Natürlich braucht der Prozess auch noch Speicher den er benutzen kann, dieser wird auch mithilfe der physischen Speicherverwaltung angefordert und kann dann leicht in die Pagetables eingetragen werden. Beim Prozesswechsel muss man nur noch CR3 mit dem richtigen Pagedir laden. Man sollte natürlich auf keinen Fall vergessen den Kernel in jeden der Pagedirectories/Pagetables der Prozesse einzutragen.
  
 
[[Category:Tutorials]]
 
[[Category:Tutorials]]