Memory Stack und Heap

[Rolf B]

Hallo hmm,

der Unterschied zwischen Stack und Heap liegt im Aufgabenbereich. Daraus resultieren unterschiedliche Techniken, sie zu verwalten, und daraus resultieren alle weiteren Unterschiede im Verhalten.

Der STACK ist eine Struktur, die von einem Ausgangspunkt "abwärts", d.h. zu fallenden Adressen hin, wächst. Die meisten Prozessoren setzen voraus, dass es ihn gibt, brauchen ihn zum Betrieb und unterstützen ihn mit entsprechenden Instruktionen. Von den Anwendungen wird erwartet, dass sie den Stack auf eine bestimmte Art und Weise verwenden - WELCHE das ist, schreibt das Betriebssystem vor (Microsoft nennt das das ABI - Application Binary Interface).

Der Prozessor verwendet den Stack automatisch bei Prozeduraufrufen (CALL Instruktion) und bei Interrupts. Er legt dann die Adresse des Befehls, der bei Rückkehr als nächstes auszuführen ist, auf den Stack (genauer gesagt: schreibt sie dorthin, wohin ein spezielles Prozessorregister namens Stackpointer zeigt und zieht die Anzahl von Bytes, die die Adresse benötigt, vom Stackpointer ab) und macht dann in der Prozedur oder im Interrupt-Handler weiter. Bei Interrupts wird noch etwas mehr auf den Stack geschrieben, das sind aber Details. Und, ja, es ist auch jetzt nur die halbe Wahrheit, aber wenn ich jetzt über Call Gates und Wechsel User/Supervisormode referiere, platzt Dir der Kopf, ich müsste mich erstmal wieder einlesen und es ist dann auch sehr prozessorspezifisch. Endet eine Prozedur, wird die oben genannte Anzahl von Bytes auf den Stackpointer wieder aufaddiert, der Befehlszähler von dort geladen und dann geht's dort weiter, wohin der Befehlszähler gerade zeigt.

Außer für die Rückkehradresse wird der Stack auch für die Übergabe von Parametern verwendet. Hier wird es kompliziert, denn es gibt abzählbar viele Regelsätze (calling conventions), welcher Parameter in welcher Form und in welcher Reihenfolge auf dem Stack zu landen hat - oder vielleicht doch in einem Register. In einigen Betriebssystemen (z.B. Windows 64-bit) ist die Calling Convention Teil des ABI, in anderen ist sie eher Verhandlungssache. Wie sie genau aussieht, ist letztlich egal, solange jede Prozedur mit der Calling Convention aufgerufen wird, für die sie compiliert ist.

Zur Calling Convention gehört auch, welche Prozessorregister eine Prozedur unverändert hinterlassen muss. Wenn man solche Register nutzen will, muss man sie beim Einstieg in die Prozedur sichern und am Ende wiederherstellen. Wo? Genau: Auf dem Stack. Dafür gibt's im Prozessor die Befehle PUSH und POP.

Viertens können Prozeduren lokale Variablen verwenden, wenn die Register nicht ausreichen. Wenn eine Prozedur weiß, dass sie 48 Bytes extra braucht, zieht sie einfach 48 vom Stackpointer ab und nutzt den freien Raum. Bevor sie zurückkehrt, müssen die 48 natürlich wieder aufaddiert werden. DAS sind die auto-Variablen, die Du in C++ bekommst, wenn Du in einer Funktion oder Methode einfach ein 'int x' hinschreibst. Manche Prozessoren haben noch einen Zusatzstackpointer (den Base Pointer), den man verwendet, um sich einfach zu merken, wo Stack Pointer am Beginn der Prozedur stand. Das einleitende Mantra lautet dann

       PUSH BP
       MOV  BP,SP
       SUB  SP, 48
       ; Prozedurbefehle
       MOV  SP, BP
       POP  BP
       RET

und weil JEDE Prozedur es braucht, um den korrekten Stack-Frame aufzubauen, haben z.B. die Intel-Prozessoren dafür eigene Befehle (ENTER und LEAVE) definiert.

Wenn deine C++ Funktion in diese 48 Bytes ein Objekt hineinlegt, ist es Sache des C++ Compilers, am Ende der Funktion noch Code zu generieren, der den Destruktor dieses Objekts aufruft.

D.h. der Stack wächst und schrumpft mit der Call-Hierarchie deines Programms und ist immer lückenlos. Das Betriebssystem kann bei entsprechendem Prozessor-Support den Stack so anlegen, dass es vor dem Speicher, der für den Stack reserviert ist, eine schreibgeschützte Schutzseite platziert. Wird der Stack dann zu groß, gibt es einen Fault und das Betriebssystem kann das Programm abbrechen. Ohne diese Schutzseite würde der Stack unkontrolliert weiter wachsen und kann fremde Speicherbereiche überschreiben. Die Folge ist ein Absturz, entweder vom Programm, oder vom ganzen Computer. Es ist bei den heutigen großen Adressräumen der Prozessoren auch möglich, z.B. 16MB Adressen für den Stack zu reservieren und die unteren 15MB mit Schutzseiten zu füllen. Nur das oberste MB bekommt real Speicher zugewiesen, den Rest gibt's nur in den Speichermanagement-Tabellen des Prozessors. Läuft der Stack über, wird 1MB Schutzseiten in echten Speicher umgewandelt, und das Betriebssystem kehrt aus dem Fault-Interrupt zurück als wäre nichts gewesen. Es hat nur einen Moment Zeit gekostet.

Der HEAP ist eine Struktur, die rein in Software realisiert ist und die dem Prozessor egal ist. Ein Programm ordert beim Start einen Eimer Speicher beim Betriebssystem befüllt ihn nach Gutdünken. Es ist auch Sache des Programms, dafür zu sorgen, dass seine Zugriffe nicht aus dem Eimer hinausschwappen, bei Speichermangel einen weiteren Eimer zu bestellen (-> Heap hat variable Größe) und ganz allgemein die Übersicht über die Brocken zu behalten, die im Eimer schwimmen. Was auf den Heap draufkommt, bestimmt dein Programm. Und es muss auch explizit dafür sorgen, dass es wieder heruntergenommen wird - sonst bleibt der Datenbrocken da liegen. Es gibt im Heap auch keine Regel, in welcher Reihenfolge der Speicher darin zu belegen ist. Das steuert die Speicherverwaltung in der Laufzeitumgebung der Programmiersprache. In einer Sprache wie C++ schreibst Du

int* pi = new int[1000];

und bekommst dann zweierlei: einen Pointer auf dem Stack, und 1000*sizeof(int) Bytes auf dem Heap. Nun muss die Laufzeitumgebung von C++ sich zwei Dinge merken: (1) da sind 1000*sizeof(int) Bytes, die auf dem Heap für irgendwen reserviert sind und (2) mein freier Platz auf dem Heap beginnt anderswo. Nr 1 ist deshalb wichtig, weil irgendwann mal jemand delete[] pi ausführen sollte. Der Speichermanager muss dann wissen, wieviel da eigentlich freizugeben ist. Aber nun wird's knifflig, denn zwischen dem new und delete können durchaus weitere Speicherbereiche vom Heap abgerufen worden sein. Da hast Du nun einen Stapel voller Speicherbrocken und irgendwer zieht den untersten heraus. C++ kann nun nicht einfach wie beim Händestapel-Spiel alles herunterfallen lassen, weil ja jede Menge Pointer herumfliegen, die in die allocierten Heap-Bereiche hineinzeigen und dann falsch wären. Sowas können nur Sprachen mit komplexerer Speicherverwaltung (Java, PHP, Javascript, C#), wo der Compiler nicht nur weiß, was auf dem Heap liegt, sondern auch alle Pointer kennt, die darauf zeigen. Die können dann mal eben aufräumen und die Pointer zurechtfummeln (Garbage Collection), aber in C++ kann der Speichermanager nur sagen: Okay, da sind jetzt 1000*sizeof(int) Bytes verwaist. Trag ich mal in meine Liste freier Speicherbereiche ein. Wenn mich nochmal einer nach einem Speicherbrocken fragt, der da irgendwie rein passt, dann kriegt er ihn halt. Und wenn nur 800*sizeof(int) bestellt werden, also gut, dann legen wir das da rein und hoffen drauf, dass nachher nochmal einer 170*sizeof(int) Bytes bestellt.

Was hier entsteht, nennt man interne Fragmentierung^[1]. Den Heap optimal zu fragmentieren, ist die hohe Kunst der Laufzeitumgebung. Das ist der Grund, weshalb der Stack schneller ist als der Heap, und warum ein langlaufendes C++ Programm speziell designed werden muss, um nicht schleichend immer mehr Speicher zu belegen.

So, ich hoffe, ich konnte ein paar Infos vermitteln, ohne Dich zu sehr in Verwirrung zu stürzen 😀

Rolf

---

1. Externe Fragmentierung gibt's auch, die betrifft die Verwaltung der (unterschiedlich großen) Eimer selbst und ist Sache des Betriebssystems ↩︎