Was ist der Stack und der Heap und wo befinden sie sich?

Question

• Was sind der Stack und der Heap?
• Wo befinden sie sich physisch im Speicher eines Computers?
• In welchem Maße werden sie vom Betriebssystem oder der Laufzeitumgebung der Sprache kontrolliert?
• Was ist ihr Geltungsbereich?
• Was bestimmt ihre Größen?
• Was macht einen schneller?

Answer 1

Andere Antworten vermeiden es einfach zu erklären, was statische Zuweisung bedeutet. Daher werde ich im Folgenden die drei Hauptformen der Zuweisung erklären und wie sie sich normalerweise auf den Heap, den Stack und das Datensegment beziehen. Ich werde auch einige Beispiele in C/C++ und Python zeigen, um das Verständnis zu erleichtern.

"Statische" (AKA statisch zugewiesene) Variablen werden nicht auf dem Stack zugewiesen. Nehmen Sie das nicht an - viele Leute tun das nur, weil "statisch" so ähnlich wie "Stack" klingt. Tatsächlich existieren sie weder auf dem Stack noch auf dem Heap. Sie sind Teil dessen, was man den Datensegment .

Im Allgemeinen ist es jedoch besser, die " scope " und " Lebensdauer " statt "Stack" und "Heap".

Der Geltungsbereich bezieht sich darauf, welche Teile des Codes auf eine Variable zugreifen können. Im Allgemeinen denken wir an lokaler Geltungsbereich (kann nur von der aktuellen Funktion aufgerufen werden) gegenüber globale Reichweite (auf die überall zugegriffen werden kann), obwohl der Umfang viel komplexer werden kann.

Die Lebensdauer bezieht sich darauf, wann eine Variable während der Programmausführung zugewiesen und freigegeben wird. Normalerweise denken wir an statische Zuordnung (die Variable bleibt während der gesamten Dauer des Programms erhalten und ist daher nützlich, um dieselben Informationen über mehrere Funktionsaufrufe hinweg zu speichern) versus automatische Zuweisung (Variable bleibt nur während eines einzigen Funktionsaufrufs bestehen und ist daher nützlich, um Informationen zu speichern, die nur während der Funktion verwendet werden und nach Beendigung gelöscht werden können) versus dynamische Zuteilung (Variablen, deren Dauer zur Laufzeit definiert wird, anstatt zur Kompilierzeit wie bei statischen oder automatischen Variablen).

Obwohl die meisten Compiler und Interpreter dieses Verhalten in Bezug auf die Verwendung von Stacks, Heaps usw. ähnlich umsetzen, kann ein Compiler diese Konventionen manchmal brechen, solange das Verhalten korrekt ist. So kann beispielsweise eine lokale Variable aus Optimierungsgründen nur in einem Register vorhanden sein oder ganz entfernt werden, obwohl die meisten lokalen Variablen auf dem Stack liegen. Wie bereits in einigen Kommentaren erwähnt wurde, steht es Ihnen frei, einen Compiler zu implementieren, der weder einen Stack noch einen Heap verwendet, sondern andere Speichermechanismen (was nur selten geschieht, da Stacks und Heaps dafür hervorragend geeignet sind).

Zur Veranschaulichung werde ich einen einfachen kommentierten C-Code zur Verfügung stellen. Am besten lernen Sie, indem Sie ein Programm mit einem Debugger ausführen und das Verhalten beobachten. Wenn Sie lieber Python lesen, springen Sie zum Ende der Antwort :)

// Statically allocated in the data segment when the program/DLL is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in the code
int someGlobalVariable;

// Statically allocated in the data segment when the program is first loaded
// Deallocated when the program/DLL exits
// scope - can be accessed from anywhere in this particular code file
static int someStaticVariable;

// "someArgument" is allocated on the stack each time MyFunction is called
// "someArgument" is deallocated when MyFunction returns
// scope - can be accessed only within MyFunction()
void MyFunction(int someArgument) {

    // Statically allocated in the data segment when the program is first loaded
    // Deallocated when the program/DLL exits
    // scope - can be accessed only within MyFunction()
    static int someLocalStaticVariable;

    // Allocated on the stack each time MyFunction is called
    // Deallocated when MyFunction returns
    // scope - can be accessed only within MyFunction()
    int someLocalVariable;

    // A *pointer* is allocated on the stack each time MyFunction is called
    // This pointer is deallocated when MyFunction returns
    // scope - the pointer can be accessed only within MyFunction()
    int* someDynamicVariable;

    // This line causes space for an integer to be allocated in the heap
    // when this line is executed. Note this is not at the beginning of
    // the call to MyFunction(), like the automatic variables
    // scope - only code within MyFunction() can access this space
    // *through this particular variable*.
    // However, if you pass the address somewhere else, that code
    // can access it too
    someDynamicVariable = new int;

    // This line deallocates the space for the integer in the heap.
    // If we did not write it, the memory would be "leaked".
    // Note a fundamental difference between the stack and heap
    // the heap must be managed. The stack is managed for us.
    delete someDynamicVariable;

    // In other cases, instead of deallocating this heap space you
    // might store the address somewhere more permanent to use later.
    // Some languages even take care of deallocation for you... but
    // always it needs to be taken care of at runtime by some mechanism.

    // When the function returns, someArgument, someLocalVariable
    // and the pointer someDynamicVariable are deallocated.
    // The space pointed to by someDynamicVariable was already
    // deallocated prior to returning.
    return;
}

// Note that someGlobalVariable, someStaticVariable and
// someLocalStaticVariable continue to exist, and are not
// deallocated until the program exits.

Ein besonders anschauliches Beispiel dafür, warum es wichtig ist, zwischen Lebensdauer und Geltungsbereich zu unterscheiden, ist die Tatsache, dass eine Variable einen lokalen Geltungsbereich, aber eine statische Lebensdauer haben kann - zum Beispiel "someLocalStaticVariable" im obigen Codebeispiel. Solche Variablen können unsere üblichen, aber informellen Benennungsgewohnheiten sehr verwirrend machen. Wenn wir zum Beispiel sagen " . " meinen wir normalerweise " lokal begrenzte, automatisch zugewiesene Variable "und wenn wir global sagen, meinen wir normalerweise " statisch zugewiesene Variable mit globalem Geltungsbereich ". Leider, wenn es um Dinge geht wie " statisch zugewiesene Variablen mit Dateispezifikation "Viele Leute sagen einfach ... " Was? ".

Einige der Syntaxentscheidungen in C/C++ verschärfen dieses Problem noch. So denken viele Leute, dass globale Variablen aufgrund der unten dargestellten Syntax nicht "statisch" sind.

int var1; // Has global scope and static allocation
static int var2; // Has file scope and static allocation

int main() {return 0;}

Beachten Sie, dass das Schlüsselwort "static" in der obigen Deklaration verhindert, dass var2 einen globalen Geltungsbereich hat. Dennoch hat das globale var1 eine statische Zuweisung. Das ist nicht intuitiv! Aus diesem Grund versuche ich, bei der Beschreibung des Geltungsbereichs nie das Wort "static" zu verwenden und stattdessen etwas wie "file" oder "file limited" zu sagen. Viele Leute verwenden jedoch den Ausdruck "static" oder "static scope", um eine Variable zu beschreiben, auf die nur von einer einzigen Codedatei aus zugegriffen werden kann. Im Zusammenhang mit der Lebensdauer bedeutet "statisch" immer bedeutet, dass die Variable beim Programmstart zugewiesen und beim Beenden des Programms wieder freigegeben wird.

Manche Leute halten diese Konzepte für C/C++-spezifisch. Das sind sie aber nicht. Das folgende Python-Beispiel veranschaulicht beispielsweise alle drei Arten der Zuweisung (in interpretierten Sprachen sind einige subtile Unterschiede möglich, auf die ich hier nicht eingehen werde).

from datetime import datetime

class Animal:
    _FavoriteFood = 'Undefined' # _FavoriteFood is statically allocated

    def PetAnimal(self):
        curTime = datetime.time(datetime.now()) # curTime is automatically allocatedion
        print("Thank you for petting me. But it's " + str(curTime) + ", you should feed me. My favorite food is " + self._FavoriteFood)

class Cat(Animal):
    _FavoriteFood = 'tuna' # Note since we override, Cat class has its own statically allocated _FavoriteFood variable, different from Animal's

class Dog(Animal):
    _FavoriteFood = 'steak' # Likewise, the Dog class gets its own static variable. Important to note - this one static variable is shared among all instances of Dog, hence it is not dynamic!

if __name__ == "__main__":
    whiskers = Cat() # Dynamically allocated
    fido = Dog() # Dynamically allocated
    rinTinTin = Dog() # Dynamically allocated

    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

    Dog._FavoriteFood = 'milkbones'
    whiskers.PetAnimal()
    fido.PetAnimal()
    rinTinTin.PetAnimal()

# Output is:
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is steak
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is tuna
# Thank you for petting me. But it's 13:05:02.255000, you should feed me. My favorite food is milkbones
# Thank you for petting me. But it's 13:05:02.256000, you should feed me. My favorite food is milkbones

Answer 2

Die groben Züge wurden bereits recht gut beantwortet, also füge ich noch ein paar Details hinzu.

1. Stack und Heap müssen nicht singular sein. Eine häufige Situation, in der Sie mehr als einen Stack haben, ist, wenn Sie mehr als einen Thread in einem Prozess haben. In diesem Fall hat jeder Thread seinen eigenen Stack. Sie können auch mehr als einen Heap haben, zum Beispiel können einige DLL-Konfigurationen dazu führen, dass verschiedene DLLs aus verschiedenen Heaps allozieren, weshalb es im Allgemeinen keine gute Idee ist, Speicher freizugeben, der von einer anderen Bibliothek alloziert wurde.

2. In C können Sie von der variablen Längenallokation durch die Verwendung von alloca profitieren, das auf dem Stack alloziert, im Gegensatz zu alloc, das auf dem Heap alloziert. Dieser Speicher wird Ihren Rückgabewert nicht überdauern, ist aber nützlich für einen Zwischenspeicher.

3. Das Erstellen eines riesigen temporären Puffers auf Windows, den Sie nicht oft verwenden, ist nicht kostenlos. Dies liegt daran, dass der Compiler eine Stack-Sonde-Schleife generiert, die jedes Mal aufgerufen wird, wenn Ihre Funktion betreten wird, um sicherzustellen, dass der Stack existiert (weil Windows eine einzelne Schutzseite am Ende Ihres Stacks verwendet, um zu erkennen, wann der Stack vergrößert werden muss. Wenn Sie auf Speicher mehr als eine Seite neben dem Ende des Stacks zugreifen, wird der Prozess abstürzen). Beispiel:

   void meineFunktion() { char big[10000000]; // Tun Sie etwas, das nur die ersten 1K von big zu 99% der Zeit verwendet. }

Answer 3

Andere haben Ihre Frage direkt beantwortet, aber wenn Sie versuchen, den Stack und den Heap zu verstehen, denke ich, dass es hilfreich ist, das Speicherlayout eines traditionellen UNIX-Prozesses zu betrachten (ohne Threads und mmap()-basierte Allokatoren). Die Memory Management Glossary Webseite hat ein Diagramm dieses Speicherlayouts.

Der Stack und der Heap befinden sich traditionell an entgegengesetzten Enden des virtuellen Adressraums des Prozesses. Der Stack wächst automatisch beim Zugriff, bis zu einer vom Kernel festgelegten Größe (die mit setrlimit(RLIMIT_STACK, ...) angepasst werden kann). Der Heap wächst, wenn der Speicherallokator den brk() oder sbrk() Systemaufruf aufruft, um weitere Seiten des physischen Speichers in den virtuellen Adressraum des Prozesses abzubilden.

In Systemen ohne virtuellen Speicher, wie beispielsweise in einigen eingebetteten Systemen, gilt oft das gleiche grundlegende Layout, wobei jedoch der Stack und der Heap eine feste Größe haben. In anderen eingebetteten Systemen (wie solchen, die auf Microchip PIC-Mikrocontrollern basieren) ist der Programmstack ein separater Speicherblock, der nicht durch Datenbewegungsinstruktionen adressierbar ist und nur indirekt durch Programmflussinstruktionen (Aufruf, Rückkehr usw.) geändert oder gelesen werden kann. Andere Architekturen, wie z. B. Intel-Itanium-Prozessoren, haben mehrere Stacks. In diesem Sinne ist der Stack ein Element der CPU-Architektur.

Answer 4

Was ist ein Stapel?

Ein Stapel ist ein Haufen von Objekten, typischerweise einer, der ordentlich angeordnet ist.

Stapel in Rechnerarchitekturen sind Speicherbereiche, in denen Daten in einem Last-In-First-Out-Verfahren hinzugefügt oder entfernt werden.
In einer Multithread-Anwendung wird jeder Thread seinen eigenen Stapel haben.

Was ist ein Heap?

Ein Heap ist eine unordentliche Ansammlung von Dingen, die willkürlich aufgestapelt sind.

In Rechnerarchitekturen ist der Heap ein Bereich des dynamisch allokierten Speichers, der automatisch vom Betriebssystem oder der Speicherverwaltungsbibliothek verwaltet wird.
Speicher im Heap wird während der Programmausführung regelmäßig allokiert, deallokiert und vergrößert, was zu einem Problem namens Fragmentierung führen kann.
Fragmentierung tritt auf, wenn Speicherobjekte mit kleinen Zwischenräumen allokiert werden, die zu klein sind, um zusätzliche Speicherobjekte aufzunehmen.
Das Ergebnis ist ein Prozentsatz des Heap-Speichers, der nicht für weitere Speicherzuweisungen verwendet werden kann.

Beides zusammen

In einer Multithread-Anwendung wird jeder Thread seinen eigenen Stapel haben. Aber alle verschiedenen Threads teilen sich den Heap.
Weil die verschiedenen Threads den Heap in einer Multithread-Anwendung teilen, bedeutet dies auch, dass es eine Koordination zwischen den Threads geben muss, damit sie nicht gleichzeitig auf dasselbe Speicherstück im Heap zugreifen und es manipulieren.

Was ist schneller - der Stapel oder der Heap? Und warum?

Der Stapel ist viel schneller als der Heap.
Das liegt an der Art und Weise, wie Speicher auf dem Stapel allokiert wird.
Speicher auf dem Stapel zu allozieren ist so einfach wie das Verschieben des Stapelzeigers nach oben.

Für Anfänger in der Programmierung ist es wahrscheinlich eine gute Idee, den Stapel zu verwenden, da er einfacher ist.
Da der Stapel klein ist, sollte man ihn verwenden, wenn man genau weiß, wie viel Speicher man für seine Daten benötigt, oder wenn man weiß, dass die Größe seiner Daten sehr klein ist.
Es ist besser, den Heap zu verwenden, wenn man weiß, dass man viel Speicher für seine Daten benötigen wird, oder wenn man einfach nicht sicher ist, wie viel Speicher man benötigen wird (wie bei einem dynamischen Array).

Java-Speichermodell

Der Stapel ist der Speicherbereich, in dem lokale Variablen (einschließlich Methodenparameter) gespeichert sind. Wenn es um Objektvariablen geht, handelt es sich lediglich um Verweise (Zeiger) auf die tatsächlichen Objekte im Heap.
Jedes Mal, wenn ein Objekt instanziiert wird, wird ein Teil des Heap-Speichers reserviert, um die Daten (den Zustand) dieses Objekts zu speichern. Da Objekte andere Objekte enthalten können, können einige dieser Daten tatsächlich Verweise auf diese verschachtelten Objekte enthalten.

Answer 5

Der Stack ist ein Teil des Speichers, der über mehrere wichtige Assemblerbefehle manipuliert werden kann, wie z.B. 'pop' (entfernt und gibt einen Wert aus dem Stack zurück) und 'push' (schiebt einen Wert auf den Stack), aber auch call (ruft eine Unterfunktion auf - dies schiebt die Rückgabeadresse auf den Stack) und return (kehrt von einer Unterfunktion zurück - dies nimmt die Adresse vom Stack und springt dorthin). Es handelt sich um den Speicherbereich unterhalb des Stack-Zeigerregisters, der bei Bedarf festgelegt werden kann. Der Stack wird auch verwendet, um Argumente an Unterfunktionen zu übergeben und um die Werte in Registern vor dem Aufruf von Unterfunktionen zu speichern.

Der Heap ist ein Teil des Speichers, der einer Anwendung vom Betriebssystem zugewiesen wird, in der Regel über einen Systemaufruf wie malloc. Auf modernen Betriebssystemen handelt es sich bei diesem Speicher um eine Reihe von Seiten, auf die nur der aufrufende Prozess Zugriff hat.

Die Größe des Stacks wird zur Laufzeit festgelegt und wächst im Allgemeinen nicht nach dem Programmstart. In einem C-Programm muss der Stack groß genug sein, um jede innerhalb einer Funktion deklarierte Variable zu speichern. Der Heap wächst dynamisch bei Bedarf, aber letztendlich trifft das Betriebssystem die Entscheidung (oftmals wird der Heap um mehr als den von malloc angeforderten Wert vergrößert, damit zukünftige mallocs nicht zurück zum Kernel gehen müssen, um mehr Speicher zu erhalten. Dieses Verhalten ist oft anpassbar)

Weil der Stack vor dem Start des Programms zugewiesen wurde, müssen Sie nie malloc aufrufen, bevor Sie den Stack verwenden können, was ein kleiner Vorteil ist. In der Praxis ist es sehr schwer vorherzusagen, was in modernen Betriebssystemen mit virtuellen Speicherunterstützung schnell und was langsam sein wird, weil die Implementierung der Seiten und ihr Speicherort ein Implementierungsdetail sind.