| Zeile 30: | Zeile 30: | ||
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 physischer 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. | 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 physischer 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 | + | Das kann man beim Freigeben natürlich analog implementieren und Speicherseiten, die in den virtuellen Adressraum eingeblendet waren, wieder freigeben, falls dieser Speicherbereich nicht mehr vom Stack selbst benötigt wird. Somit verbraucht der Stack im Prinzip "keinen" Speicher. |
=== Eigenschaften === | === Eigenschaften === | ||
| Zeile 37: | Zeile 37: | ||
o Das Freigeben einer Speicherseite ist in konstanter Zeit möglich. (konstante Komplexität)<br> | o Das Freigeben einer Speicherseite ist in konstanter Zeit möglich. (konstante Komplexität)<br> | ||
- Das Allozieren physisch kontinuierlicher Speicherseiten ist unmöglich.<br> | - Das Allozieren physisch kontinuierlicher Speicherseiten ist unmöglich.<br> | ||
| + | |||
| + | == verkette Liste == | ||
| + | |||
| + | Die Elemente der Liste sind dabei (freie, physisch zusammenhängende) Speicherbereiche, d.h. Zeiger auf den Beginn des Speicherbereichs und Länge des Speicherbereichs. Diese Liste benötigt allerdings ein malloc/free, um Speicher für die Listenelemente zu allozieren, d.h. diese Art der Speicherverwaltung kann nur für einen Teil des Speichers genutzt werden. | ||
| + | |||
| + | === Allokation & Freigabe von Speicherseiten === | ||
| + | Zum Allozieren von Speicherseiten wird die Liste solange durchsucht bis ein ausreichend großer Speicherbereich gefunden ist. Falls der zu allozierende Speicherbereich exakt so groß wie der gefundene ist wird das Listenelemente entfernt, andernfalls die Größe angepasst. Beim Freigeben wird - falls dies möglich ist - zuerst versucht der freizugebende Speicherplatz in eines der vorhandenen Listenelemente einzubauen, was natürlich nur geht, wenn das freizugebende physisch genau davor bzw. genau dahinter liegt. Andernfalls wird ein neues Listenelement erzeugt und passend initialisiert. | ||
| + | |||
| + | === Eigenschaften === | ||
| + | + Das Allozieren von physisch kontinuierlichen Speicherseiten ist möglich.<br> | ||
| + | - Das Allozieren eines (physisch kontinuierlichen) Speicherbereichs oder einer Speicherseite ist in linearer Zeit möglich.<br> | ||
| + | - Freigeben eines Speicherbereichs oder einer Speicherseite ist in linearer Zeit möglich.<br> | ||
| + | - Es wird ein darunterliegendes malloc/free benötigt.<br> | ||
| + | |||
| + | Das sieht natürlich für die verkettete Liste erstmal schlecht aus, aber nach Erfahrung von [[Benutzer:Bluecode | Bluecode]] eignet sie sich perfekt zum Verwalten eines Speicherbereichs für Allokationen von physisch kontinuierlichem Speicher, da solche Allokationen sehr selten und deswegen die Liste nicht sonderlich groß ist. Der Rest des Speichers könnte den über einen wie oben beschriebenen Stack verwaltet werden. | ||
== Buddy == | == Buddy == | ||