Wo sind mehrere Stapel und Haufen im virtuellen Speicher?

Question

Ich schreibe einen Kernel und brauche (und möchte) mehrere Stapel und Haufen in den virtuellen Speicher, aber ich kann nicht herausfinden, wie man sie effizient platziert. Wie machen normale Programme das?

Wie (oder wo) werden Stacks und Heaps in den begrenzten virtuellen Speicher eines 32-Bit-Systems platziert, sodass sie so viel Platz wie möglich haben?

Wenn zum Beispiel ein triviales Programm in den Speicher geladen wird, kann das Layout der Adressraum wie folgt aussehen:

[ Code Data BSS Heap-> ... <-Stack ] 

In diesem Fall wird der Haufen so groß wachsen können als virtuelle Speicher ermöglicht (zB bis zum Stack), und ich glaube, so funktioniert der Heap für die meisten Programme. Es gibt keine vordefinierte obere Grenze.

Viele Programme haben gemeinsam genutzte Bibliotheken, die sich irgendwo im virtuellen Adressraum befinden. Dann gibt es Multi-Thread-Programme, die mehrere Stapel haben, einen für jeden Thread. Und .NET-Programme haben multiple heaps, die alle in der Lage sein müssen, auf die eine oder andere Weise zu wachsen.

Ich sehe einfach nicht, wie dies einigermaßen effizient getan wird, ohne ein vordefiniertes Limit für die Größe aller Haufen und Stapel.

Answer 1

Einfach gesagt, da Ihre Systemressourcen immer begrenzt sind, können Sie nicht grenzenlos gehen.

Die Speicherverwaltung besteht immer aus mehreren Schichten, die jeweils eine genau definierte Verantwortung haben. Aus der Perspektive des Programms ist der Manager auf Anwendungsebene sichtbar, der normalerweise nur mit einem eigenen zugewiesenen Einzelheap befasst ist. Eine Ebene darüber könnte sich mit dem Erstellen der mehreren Heaps, falls erforderlich, aus einem globalen Heap und dem Zuweisen von Unterprogrammen (jeweils mit einem eigenen Speichermanager) befassen. Darüber hinaus könnte der Standard malloc()/free() verwendet werden und über das Betriebssystem, das sich mit Seiten und der tatsächlichen Speicherzuweisung pro Prozess beschäftigt (es geht im Grunde nicht nur um mehrere Heaps, sondern sogar um User-Level-Heaps im Allgemeinen).

Speicherverwaltung ist kostspielig und das Einfangen in den Kernel. Die Kombination der beiden könnte schwerwiegende Leistungseinbußen zur Folge haben. Aus Gründen der Performance (und aus anderen Gründen, die derzeit nicht im Bereich liegen) wird die tatsächliche Heap-Verwaltung aus Sicht der Anwendung tatsächlich im Benutzerbereich (der C-Laufzeitbibliothek) implementiert).

Wenn eine Shared (DLL) -Bibliothek geladen wird, wenn sie beim Programmstart geladen wird, wird sie höchstwahrscheinlich in CODE/DATA/etc geladen, so dass keine Heap-Fragmentierung auftritt. Auf der anderen Seite, wenn es zur Laufzeit geladen wird, gibt es so gut wie keine andere Möglichkeit als die Verwendung von Heap-Speicherplatz. Statische Bibliotheken werden natürlich einfach in die Abschnitte CODE/DATA/BSS/etc eingebunden.

Am Ende des Tages müssen Sie Heaps und Stacks Beschränkungen auferlegen, damit sie nicht überlaufen, aber Sie können andere zuweisen. Wenn man über diese Grenze hinaus wachsen muss, können Sie entweder mit Fehler

• die Anwendung beenden
• der Speichermanager die Größe zuteilen/haben/für diesen Stapel/Haufen den Speicherblock bewegen und höchstwahrscheinlich den Haufen defragmentieren (seine eigene Ebene) danach; deshalb funktioniert free() normalerweise schlecht.

eine ziemlich große, 1 KB Stack-Frame jeder call als Durchschnitt auf Anbetracht (kann passieren, wenn der Anwendungsentwickler unerfahren ist) Stapel ein 10MB würde für 10.240 verschachtelte call -s ausreichend sein. Übrigens, es gibt so ziemlich keinen Bedarf für mehr als einen Stack und Heap pro Thread.

Answer 2

Ich nehme an, Sie haben die Grundlagen in Ihrem Kernel getan, eine Trap-Handler für Seitenfehler, die eine virtuelle Speicherseite zu RAM zuordnen können. Auf der nächsthöheren Ebene benötigen Sie einen Adressraummanager für den virtuellen Speicher, von dem der Usermode-Code Adressraum anfordern kann. Wählen Sie eine Segmentgranularität, die eine übermäßige Fragmentierung verhindert, 64 KB (16 Seiten) sind eine gute Zahl. Erlaube Usermode-Code, Speicherplatz und Commit-Speicherplatz zu reservieren. Ein einfaches Bitmap von 4 GB/64 KB = 64 KB x 2 Bits, um den Status des Segments zu verfolgen, erledigt die Arbeit. Der Seitenfehler-Trap-Handler muss auch diese Bitmap konsultieren, um zu wissen, ob die Seitenanforderung gültig ist oder nicht.

Ein Stack ist eine VM-Zuweisung mit fester Größe, normalerweise 1 Megabyte. Ein Thread benötigt normalerweise nur eine Handvoll Seiten davon, abhängig von der Verschachtelungsebene der Funktion, also reservieren Sie die 1MB und binden Sie nur die obersten paar Seiten ein. Wenn der Thread tiefer nistet, wird ein Seitenfehler ausgelöst und der Kernel kann die zusätzliche Seite einfach dem RAM zuordnen, damit der Thread fortfahren kann. Sie sollten die unteren paar Seiten als besonders markieren, wenn die Thread-Seite Fehler aufweist, geben Sie den Namen dieser Website an.

Der wichtigste Job des Heap-Managers ist die Vermeidung von Fragmentierung. Der beste Weg, dies zu tun, ist eine Lookaside-Liste zu erstellen, die Heap-Anfragen nach Größe partitioniert. Alles weniger als 8 Bytes stammt aus der ersten Liste von Segmenten. 8 bis 16 von der zweiten, 16 bis 32 von der dritten, und so weiter. Erhöhen der Größe des Buckets, wenn Sie nach oben gehen. Sie müssen mit den Eimergrößen spielen, um das beste Gleichgewicht zu erhalten. Sehr große Zuordnungen stammen direkt vom VM-Adressmanager.

Wenn Sie zum ersten Mal einen Eintrag in die Lookaside-Liste eingeben, weisen Sie ein neues VM-Segment zu. Sie unterteilen das Segment in kleinere Blöcke mit einer verketteten Liste. Wenn eine solche Zuweisung freigegeben wird, fügen Sie den Block der Liste der freien Blöcke hinzu. Alle Blöcke haben unabhängig von der Programmanforderung die gleiche Größe, so dass keine Fragmentierung auftritt. Wenn das Segment vollständig verwendet wird und keine freien Blöcke verfügbar sind, weisen Sie ein neues Segment zu. Wenn ein Segment nur freie Blöcke enthält, können Sie es an den VM-Manager zurückgeben.

Mit diesem Schema können Sie beliebig viele Stapel und Stapel erstellen.