Erläutern Sie das Konzept eines Stapelrahmens auf den Punkt gebracht

200

Es scheint, dass ich auf die Idee des Aufrufstapels im Design von Programmiersprachen komme . Aber ich kann keine anständige Erklärung dafür finden (wahrscheinlich suche ich einfach nicht hart genug), was ein Stapelrahmen ist.

Deshalb möchte ich jemanden bitten, es mir in wenigen Worten zu erklären.

Ikostia
quelle

Antworten:

195

Ein Stapelrahmen ist ein Datenrahmen, der auf den Stapel verschoben wird. Im Fall eines Aufrufstapels würde ein Stapelrahmen einen Funktionsaufruf und seine Argumentdaten darstellen.

Wenn ich mich richtig erinnere, wird zuerst die Funktionsrückgabeadresse auf den Stapel verschoben, dann die Argumente und der Platz für lokale Variablen. Zusammen bilden sie den "Rahmen", obwohl dies wahrscheinlich architekturabhängig ist. Der Prozessor weiß, wie viele Bytes sich in jedem Frame befinden, und bewegt den Stapelzeiger entsprechend, wenn Frames vom Stapel verschoben und entfernt werden.

BEARBEITEN:

Es gibt einen großen Unterschied zwischen übergeordneten Call-Stacks und dem Call-Stack des Prozessors.

Wenn wir über den Aufrufstapel eines Prozessors sprechen, sprechen wir über das Arbeiten mit Adressen und Werten auf Byte- / Wortebene im Assembly- oder Maschinencode. Es gibt "Aufrufstapel", wenn es um übergeordnete Sprachen geht, aber sie sind ein Debugging- / Laufzeit-Tool, das von der Laufzeitumgebung verwaltet wird, damit Sie protokollieren können, was mit Ihrem Programm schief gelaufen ist (auf hoher Ebene). Auf dieser Ebene sind häufig Zeilennummern sowie Methoden- und Klassennamen bekannt. Bis der Prozessor den Code erhält, hat er absolut kein Konzept für diese Dinge.

Tony R.
quelle
6
"Der Prozessor weiß, wie viele Bytes sich in jedem Frame befinden, und bewegt den Stapelzeiger entsprechend, wenn Frames vom Stapel verschoben und entfernt werden." - Ich bezweifle, dass der Prozessor etwas über Stack weiß, weil WIR es durch Subbing (Zuweisung), Pushing und Popping manipulieren. Und so werden hier Konventionen aufgerufen, die erklären, wie wir den Stapel verwenden sollen.
Victor Polevoy
78

Wenn Sie Stack sehr gut verstehen, werden Sie verstehen, wie Speicher im Programm funktioniert, und wenn Sie verstehen, wie Speicher im Programm funktioniert, werden Sie verstehen, wie Funktionsspeicher im Programm gespeichert sind, und wenn Sie verstehen, wie Funktionsspeicher im Programm funktionieren, werden Sie verstehen, wie rekursive Funktionen funktionieren und wenn Sie verstehen, wie die rekursive Funktion funktioniert. Sie werden verstehen, wie der Compiler funktioniert. Wenn Sie verstehen, wie der Compiler funktioniert, funktioniert Ihr Verstand als Compiler und Sie können jedes Programm sehr einfach debuggen

Lassen Sie mich erklären, wie Stack funktioniert:

Zuerst müssen Sie wissen, wie Funktionen im Stapel dargestellt werden:

Heap speichert dynamisch zugewiesene Werte.
Der Stapel speichert automatische Zuordnungs- und Löschwerte.

Geben Sie hier die Bildbeschreibung ein

Lassen Sie uns mit Beispiel verstehen:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(4)

Verstehen Sie nun Teile dieses Programms:

Geben Sie hier die Bildbeschreibung ein

Nun wollen wir sehen, was Stapel ist und was Stapelteile sind:

Geben Sie hier die Bildbeschreibung ein

Zuordnung des Stapels:

Denken Sie an eines: Wenn die Rückgabebedingung einer Funktion erfüllt ist, unabhängig davon, ob sie die lokalen Variablen geladen hat oder nicht, kehrt sie sofort mit ihrem Stapelrahmen vom Stapel zurück. Dies bedeutet, dass die Basisbedingung nicht darauf wartet, lokale Variablen zu laden, die sich im Teil "else" des Programms befinden, wenn eine rekursive Funktion die Basisbedingung erfüllt und wir eine Rückgabe nach der Basisbedingung setzen. Der aktuelle Frame wird sofort vom Stapel zurückgegeben, woraufhin sich der nächste Frame im Aktivierungsdatensatz befindet.

Sehen Sie dies in der Praxis:

Geben Sie hier die Bildbeschreibung ein

Freigabe des Blocks:

Immer wenn eine Funktion auf eine return-Anweisung stößt, wird der aktuelle Frame vom Stapel gelöscht.

Bei der Rückkehr vom Stapel werden die Werte in umgekehrter Reihenfolge zurückgegeben, in der sie ursprünglich im Stapel zugewiesen wurden.

Geben Sie hier die Bildbeschreibung ein

Aaditya Ura
quelle
3
Der Stapel wächst nach unten und der Haufen nach oben. Sie haben sie in Ihrem Diagramm umgekehrt. RICHTIGES DIAGRAMM HIER
Rafael
@ Rafael Entschuldigung für die Verwirrung, ich sprach über die Richtung des Wachstums Ich sprach nicht über die Richtung des Stapelwachstums. Es gibt Unterschiede zwischen der Wachstumsrichtung und der Richtung des Stapelwachstums. Siehe hier stackoverflow.com/questions/1677415/…
Aaditya Ura
2
Rafael hat recht. Auch das erste Bild ist falsch. Ersetzen Sie es durch etwas anderes (suchen Sie in Google Bilder nach "Heap Stack").
Nikos
Wenn ich das richtig verstehe, gibt es in Ihrem dritten Diagramm 3 Stapelrahmen, weil hello()rekursiv aufgerufen wurde, hello()was dann (wieder) rekursiv aufgerufen wurde hello(), und der globale Rahmen ist die ursprüngliche Funktion, die den ersten aufgerufen hat hello()?
Andy J
1
Wohin führen uns die Links? Aus Sicherheitsgründen sollten diese Links so schnell wie möglich entfernt werden.
Shivanshu
45

Ein kurzer Abschluss. Vielleicht hat jemand eine bessere Erklärung.

Ein Aufrufstapel besteht aus 1 oder mehreren mehreren Stapelrahmen. Jeder Stapelrahmen entspricht einem Aufruf einer Funktion oder Prozedur, die noch nicht mit einer Rückgabe beendet wurde.

Um einen Stapelrahmen zu verwenden, behält ein Thread zwei Zeiger bei, von denen einer als Stapelzeiger (SP) und der andere als Rahmenzeiger (FP) bezeichnet wird. SP zeigt immer auf die "Oberseite" des Stapels und FP zeigt immer auf die "Oberseite" des Rahmens. Zusätzlich verwaltet der Thread einen Programmzähler (PC), der auf den nächsten auszuführenden Befehl zeigt.

Auf dem Stapel werden folgende Daten gespeichert: lokale Variablen und Provisorien, tatsächliche Parameter der aktuellen Anweisung (Prozedur, Funktion usw.)

Es gibt verschiedene Aufrufkonventionen bezüglich der Reinigung des Stapels.

ervinbosenbacher
quelle
7
Vergessen Sie nicht, dass die Absenderadresse des Unterprogramms auf dem Stapel steht.
Tony R
4
Frame Pointer ist auch Base Pointer in x86-Begriffen
Peterchaula
1
Ich möchte betonen, dass ein Frame-Zeiger auf den Anfang des Stack-Frames für die aktuell aktive Prozedur-Inkarnation zeigt.
Server Khalilov
13

"Ein Aufrufstapel besteht aus Stapelrahmen ..." -  Wikipedia

Ein Stapelrahmen ist eine Sache, die Sie auf den Stapel legen. Dies sind Datenstrukturen, die Informationen zu aufzurufenden Unterprogrammen enthalten.

Waleed Khan
quelle
Entschuldigung, ich habe keine Ahnung, wie ich das im Wiki verpasst habe. Vielen Dank. Verstehe ich richtig, dass in dynamischen Sprachen die Größe des Frames kein konstanter Wert ist, da die Einheimischen der Funktion nicht genau bekannt sind?
Ikostia
Die Größe und Art eines Rahmens hängt stark von der Architektur der Maschine ab. Tatsächlich ist das Paradigma eines Aufrufstapels architekturspezifisch. Soweit ich weiß, ist es immer variabel, da verschiedene Funktionsaufrufe unterschiedliche Mengen an Argumentdaten enthalten.
Tony R
Beachten Sie, dass die Größe des Stapelrahmens dem Prozessor bekannt sein muss , wenn er bearbeitet wird. In diesem Fall ist die Größe der Daten bereits festgelegt. Dynamische Sprachen werden wie statische Sprachen zu Maschinencode kompiliert, jedoch häufig just-in-time, damit der Compiler die Dynamik beibehalten und der Prozessor mit "bekannten" Frame-Größen arbeiten kann. Verwechseln Sie keine höheren Sprachen mit Maschinencode / Assembly, wo dieses Zeug tatsächlich passiert.
Tony R
Nun, aber dynamische Sprachen haben auch ihre Call-Stacks, nicht wahr? Ich meine, wenn beispielsweise Python eine Prozedur ausführen möchte, werden die Daten zu dieser Prozedur in der Struktur eines Python-Interpreters gespeichert. Stimmt das? Ich meine also, dass der Aufrufstapel nicht nur auf einer niedrigen Ebene vorhanden ist.
Ikostia
Nachdem ich ein bisschen von diesem Wikipedia-Artikel gelesen habe, stehe ich korrigiert da (ein bisschen). Die Größe des Stapelrahmens kann zum Zeitpunkt der Kompilierung unbekannt bleiben . Wenn der Prozessor jedoch mit Stack + Frame-Zeigern arbeitet, muss er die Größen kennen. Die Größe kann variabel sein, aber der Prozessor kennt die Größe, wollte ich sagen.
Tony R
5

Programmierer haben möglicherweise Fragen zu Stapelrahmen nicht in einem weiten Sinne (dass es sich um eine einzelne Entität im Stapel handelt, die nur einen Funktionsaufruf bedient und die Rücksprungadresse, Argumente und lokalen Variablen beibehält), sondern im engeren Sinne - wenn der Begriff stack framesin erwähnt wird Kontext der Compileroptionen.

Ob der Autor der Frage es gemeint hat oder nicht, aber das Konzept eines Stapelrahmens unter dem Aspekt der Compileroptionen ist ein sehr wichtiges Thema, das in den anderen Antworten hier nicht behandelt wird.

Der Microsoft Visual Studio 2015 C / C ++ - Compiler verfügt beispielsweise über die folgende Option stack frames:

  • / Oy (Frame-Pointer-Auslassung)

GCC haben Folgendes:

  • -fomit-frame-pointer (Bewahren Sie den Frame-Zeiger nicht in einem Register für Funktionen auf, die keinen benötigen. Dadurch werden die Anweisungen zum Speichern, Einrichten und Wiederherstellen von Frame-Zeigern vermieden. Außerdem wird in vielen Funktionen ein zusätzliches Register verfügbar )

Intel C ++ Compiler haben Folgendes:

  • -fomit-frame-pointer (Bestimmt, ob EBP bei Optimierungen als Allzweckregister verwendet wird)

welches den folgenden Alias ​​hat:

  • / Oy

Delphi verfügt über die folgende Befehlszeilenoption:

  • - $ W + (Stapelrahmen generieren)

In diesem speziellen Sinne ist aus Sicht des Compilers ein Stapelrahmen nur der Eingangs- und Ausgangscode für die Routine , der einen Anker auf den Stapel schiebt - der auch zum Debuggen und zur Ausnahmebehandlung verwendet werden kann. Debugging-Tools können die Stapeldaten scannen und diese Anker zum Zurückverfolgen verwenden, während sie sich call sitesim Stapel befinden, dh um die Namen der Funktionen in der Reihenfolge anzuzeigen, in der sie hierarchisch aufgerufen wurden. Für die Intel-Architektur ist es push ebp; mov ebp, espoder enterfür den Ein- und / mov esp, ebp; pop ebpoder leaveAusstieg.

Aus diesem Grund ist es für einen Programmierer sehr wichtig zu verstehen, in welchem ​​Stapelrahmen sich die Compileroptionen befinden, da der Compiler steuern kann, ob dieser Code generiert werden soll oder nicht.

In einigen Fällen kann der Compiler auf den Stapelrahmen (Eingangs- und Ausgangscode für die Routine) verzichten, und auf die Variablen wird direkt über den Stapelzeiger (SP / ESP / RSP) und nicht über den praktischen Basiszeiger (BP /) zugegriffen. ESP / RSP). Bedingungen für das Weglassen des Stapelrahmens, zum Beispiel:

  • Die Funktion ist eine Blattfunktion (dh eine Endentität, die keine anderen Funktionen aufruft).
  • Es gibt keine try / finally- oder try / Except- oder ähnliche Konstrukte, dh es werden keine Ausnahmen verwendet.
  • Es werden keine Routinen mit ausgehenden Parametern auf dem Stapel aufgerufen.
  • Die Funktion hat keine Parameter.
  • Die Funktion hat keinen Inline-Assemblycode.
  • etc...

Das Weglassen von Stapelrahmen (Eingabe- und Ausstiegscode für die Routine) kann den Code kleiner und schneller machen, kann jedoch auch die Fähigkeit der Debugger beeinträchtigen, die Daten im Stapel zurückzuverfolgen und dem Programmierer anzuzeigen. Dies sind die Compileroptionen, die bestimmen, unter welchen Bedingungen eine Funktion den Eingangs- und Ausgangscode haben soll, zum Beispiel: (a) immer, (b) nie, (c) bei Bedarf (Angabe der Bedingungen).

Maxim Masiutin
quelle
-1

Der Stapelrahmen ist die gepackte Information, die sich auf einen Funktionsaufruf bezieht. Diese Informationen enthalten im Allgemeinen Argumente, die an die Funktion übergeben werden, lokale Variablen und die Rückgabe beim Beenden. Aktivierungsdatensatz ist ein anderer Name für einen Stapelrahmen. Das Layout des Stapelrahmens wird im ABI vom Hersteller festgelegt, und jeder Compiler, der die ISA unterstützt, muss diesem Standard entsprechen. Das Layoutschema kann jedoch vom Compiler abhängig sein. Im Allgemeinen ist die Stapelrahmengröße nicht begrenzt, aber es gibt ein Konzept namens "rote / geschützte Zone", mit dem Systemaufrufe usw. ausgeführt werden können, ohne einen Stapelrahmen zu stören.

Es gibt immer einen SP, aber bei einigen ABIs (z. B. ARMs und PowerPCs) ist FP optional. Argumente, die auf den Stapel gelegt werden mussten, können nur mit dem SP ausgeglichen werden. Ob ein Stapelrahmen für einen Funktionsaufruf generiert wird oder nicht, hängt von der Art und Anzahl der Argumente, den lokalen Variablen und dem allgemeinen Zugriff auf lokale Variablen ab. Bei den meisten ISAs werden zunächst Register verwendet. Wenn mehr Argumente als Register zum Übergeben von Argumenten vorhanden sind, werden diese auf den Stapel gelegt (z. B. verfügt x86 ABI über 6 Register zum Übergeben ganzzahliger Argumente). Daher benötigen einige Funktionen manchmal keinen Stapelrahmen, um auf dem Stapel platziert zu werden, sondern nur die Rücksprungadresse wird auf den Stapel verschoben.

betrunkene Teekanne
quelle