Wie werden Variablen im Programmstapel gespeichert und daraus abgerufen?

Entschuldigung im Voraus für die Naivität dieser Frage. Ich bin ein 50 Jahre alter Künstler, der zum ersten Mal versucht, Computer wirklich richtig zu verstehen. Also geht es los.

Ich habe versucht zu verstehen, wie Datentypen und Variablen von einem Compiler behandelt werden (im Allgemeinen weiß ich, dass es eine Menge gibt). Ich vermisse etwas in meinem Verständnis der Beziehung zwischen dem Speicher im "Stapel" und den Werttypen und dem Speicher im "Heap" und den Referenztypen (die Anführungszeichen sollen bedeuten, dass ich verstehe, dass diese Begriffe Abstraktionen sind und nicht in einem so vereinfachten Kontext wie dem, in dem ich diese Frage formuliere, zu wörtlich genommen zu werden). Mein simpler Gedanke ist jedenfalls, dass Typen wie Boolesche Werte und Ganzzahlen auf dem Stapel abgelegt werden, weil sie dies können, weil sie im Hinblick auf den Speicherplatz als Entitäten bekannt sind und ihr Gültigkeitsbereich leicht entsprechend gesteuert werden kann.

Was ich aber nicht verstehe, ist, wie Variablen auf dem Stack von einer Anwendung gelesen werden - wenn ich sie deklariere und xals Ganzzahl zuordne x = 3, wird Speicher auf dem Stack reserviert und der Wert von 3dort und dann in gespeichert die gleiche Funktion , die ich erklären und assign ywie, sagen wir 4, und dann folgt , dass ich dann verwenden x, in einem anderen Ausdruck (sagen wir z = 5 + x) , wie kann das Programm lesen , xum zu bewerten , zwenn es unten istyauf dem Stapel? Mir fehlt eindeutig etwas. Geht es bei der Position auf dem Stapel nur um die Lebensdauer / den Gültigkeitsbereich der Variablen und darum, dass das Programm jederzeit auf den gesamten Stapel zugreifen kann? Wenn ja, bedeutet dies, dass es einen anderen Index gibt, der nur die Adressen der Variablen auf dem Stapel enthält, damit die Werte abgerufen werden können? Aber dann dachte ich, der springende Punkt des Stapels sei, dass die Werte am selben Ort wie die variable Adresse gespeichert werden. Meiner Meinung nach scheint es, dass wir, wenn es diesen anderen Index gibt, über etwas mehr wie einen Haufen sprechen? Ich bin eindeutig sehr verwirrt und hoffe nur, dass es eine einfache Antwort auf meine vereinfachte Frage gibt.

Vielen Dank für das Lesen so weit.

Das Speichern lokaler Variablen auf einem Stack ist ein Implementierungsdetail - im Grunde genommen eine Optimierung. Sie können sich das so vorstellen. Bei der Eingabe einer Funktion wird Speicherplatz für alle lokalen Variablen zugewiesen. Sie können dann auf alle Variablen zugreifen, da Sie deren Position irgendwie kennen (dies ist Teil des Zuweisungsprozesses). Beim Verlassen einer Funktion wird der Speicherplatz freigegeben.

Der Stack ist eine Möglichkeit, diesen Prozess zu implementieren - Sie können sich ihn als eine Art "schnellen Heap" vorstellen, der eine begrenzte Größe hat und daher nur für kleine Variablen geeignet ist. Als zusätzliche Optimierung werden alle lokalen Variablen in einem Block gespeichert. Da jede lokale Variable eine bekannte Größe hat, kennen Sie den Versatz jeder Variablen im Block und greifen auf diese zu. Dies steht im Gegensatz zu Variablen, die auf dem Heap zugeordnet sind und deren Adressen selbst in anderen Variablen gespeichert sind.

$k$

Lassen Sie mich abschließend erwähnen, dass in der Praxis einige der lokalen Variablen in Registern gespeichert sind. Dies liegt daran, dass der Zugriff auf Register schneller ist als der Zugriff auf den Stapel. Dies ist eine weitere Möglichkeit, ein Leerzeichen für lokale Variablen zu implementieren. Wir wissen wieder genau, wo eine Variable gespeichert ist (diesmal nicht über Offset, sondern über den Namen eines Registers), und diese Art der Speicherung ist nur für kleine Daten geeignet.

Das Vorhandensein yauf dem Stapel verhindert nicht den physischen xZugriff, was, wie Sie bereits betont haben, Computerstapel von anderen Stapeln unterscheidet.

Beim Kompilieren eines Programms werden auch die Positionen von Variablen im Stapel (im Rahmen einer Funktion) vorgegeben. Wenn in Ihrem Beispiel der Stapel xein y"darüber" enthält, weiß das Programm im Voraus, dass xsich innerhalb der Funktion 1 Element unter dem oberen Rand des Stapels befindet. Da die Computerhardware explizit um 1 Element unterhalb des Stapels bitten kann, kann der Computer erhalten x, obwohl yauch vorhanden.

Geht es bei der Position auf dem Stapel nur um die Lebensdauer / den Gültigkeitsbereich der Variablen und darum, dass das Programm jederzeit auf den gesamten Stapel zugreifen kann?

Ja. Wenn Sie eine Funktion verlassen, zurück , um den Stapelzeiger bewegt sich in seine vorherige Position, effektiv zu löschen xund y, aber technisch werden sie noch da sein , bis der Speicher für etwas anderes verwendet wird. Wenn Ihre Funktion eine andere Funktion aufruft xund yweiterhin vorhanden ist und absichtlich zu weit unten im Stapel abgerufen werden kann.

Um ein konkretes Beispiel dafür zu geben, wie ein Compiler den Stack verwaltet und wie auf Werte im Stack zugegriffen wird, sehen wir uns visuelle Darstellungen sowie Code an, der GCCin einer Linux-Umgebung mit i386 als Zielarchitektur generiert wurde .

1. Rahmen stapeln

Wie Sie wissen, ist der Stapel ein Speicherort im Adressraum eines laufenden Prozesses, der von Funktionen oder Prozeduren in dem Sinne verwendet wird, dass auf dem Stapel Speicherplatz für lokal deklarierte Variablen sowie für an die Funktion übergebene Argumente reserviert ist ( Platz für Variablen, die außerhalb einer Funktion deklariert wurden (dh globale Variablen), wird in einer anderen Region im virtuellen Speicher zugewiesen. Der für alle Funktionsdaten zugewiesene Speicherplatz wird als Stapelrahmen bezeichnet . Hier ist eine visuelle Darstellung mehrerer Stapelrahmen (aus Computersystemen: Perspektive eines Programmierers ):

2. Stack-Frame-Management und variable Position

Damit Werte, die in den Stapel innerhalb eines bestimmten Stapelrahmens geschrieben werden, vom Compiler verwaltet und vom Programm gelesen werden können, muss es eine Methode zum Berechnen der Positionen dieser Werte und zum Abrufen ihrer Speicheradresse geben. Dabei helfen die in der CPU als Stapelzeiger und Basiszeiger bezeichneten Register.

Der Basiszeiger ebpenthält gemäß der Konvention die Speicheradresse des Bodens oder der Basis des Stapels. Die Positionen aller Werte innerhalb des Stapelrahmens können unter Verwendung der Adresse im Basiszeiger als Referenz berechnet werden. Dies ist in der obigen Abbildung dargestellt: %ebp + 4Ist die im Basiszeiger gespeicherte Speicheradresse beispielsweise plus 4.

3. Vom Compiler generierter Code

Was ich aber nicht bekomme, ist, wie Variablen auf dem Stapel von einer Anwendung gelesen werden. Wenn ich x als Ganzzahl deklariere und zuordne, z. B. x = 3, wird Speicher auf dem Stapel reserviert und dann der Wert 3 gespeichert dort und dann in der gleichen Funktion deklariere ich y als, sage 4, und folge dann, dass ich x in einem anderen Ausdruck verwende (sage z = 5 + x), wie kann das Programm x lesen, um z wann auszuwerten liegt es unter y auf dem stapel?

Verwenden wir ein einfaches Beispielprogramm in C, um zu sehen, wie dies funktioniert:

int main(void)
{
        int x = 3;
        int y = 4;
        int z = 5 + x;

        return 0;
}

Lassen Sie uns den von GCC erstellten Assembler-Text für diesen C-Quelltext untersuchen (der Übersichtlichkeit halber habe ich ihn ein wenig aufgeräumt):

main:
    pushl   %ebp              # save previous frame's base address on stack
    movl    %esp, %ebp        # use current address of stack pointer as new frame base address
    subl    $16, %esp         # allocate 16 bytes of space on stack for function data
    movl    $3, -12(%ebp)     # variable x at address %ebp - 12
    movl    $4, -8(%ebp)      # variable y at address %ebp - 8
    movl    -12(%ebp), %eax   # write x to register %eax
    addl    $5, %eax          # x + 5 = 9
    movl    %eax, -4(%ebp)    # write 9 to address %ebp - 4 - this is z
    movl    $0, %eax
    leave

Was wir beobachten ist , dass Variablen x, y und z an Adressen angeordnet %ebp - 12, %ebp -8und %ebp - 4ist. Mit anderen Worten, die Positionen der Variablen innerhalb des Stapelrahmens für main()werden unter Verwendung der im CPU-Register gespeicherten Speicheradresse berechnet %ebp.

4. Daten im Speicher außerhalb des Stapelzeigers liegen außerhalb des Bereichs

Mir fehlt eindeutig etwas. Geht es bei der Position auf dem Stapel nur um die Lebensdauer / den Gültigkeitsbereich der Variablen und darum, dass das Programm jederzeit auf den gesamten Stapel zugreifen kann? Wenn ja, bedeutet dies, dass es einen anderen Index gibt, der nur die Adressen der Variablen auf dem Stapel enthält, damit die Werte abgerufen werden können? Aber dann dachte ich, der springende Punkt des Stapels sei, dass die Werte am selben Ort wie die variable Adresse gespeichert werden.

Der Stack ist eine Region im virtuellen Speicher, deren Verwendung vom Compiler verwaltet wird. Der Compiler generiert Code so, dass auf Werte jenseits des Stapelzeigers (Werte jenseits des obersten Stapels) nie verwiesen wird. Wenn eine Funktion aufgerufen wird, ändert sich die Position des Stapelzeigers, um Platz auf dem Stapel zu schaffen, der sozusagen nicht "außerhalb der Grenzen" liegt.

Wenn Funktionen aufgerufen und zurückgegeben werden, wird der Stapelzeiger dekrementiert und inkrementiert. Auf den Stapel geschriebene Daten verschwinden nicht, wenn sie außerhalb des Gültigkeitsbereichs liegen. Der Compiler generiert jedoch keine Anweisungen, die auf diese Daten verweisen, da der Compiler die Adressen dieser Daten nicht mit %ebpoder berechnen kann %esp.

5. Zusammenfassung

Code, der direkt von der CPU ausgeführt werden kann, wird vom Compiler generiert. Der Compiler verwaltet den Stack, Stack-Frames für Funktionen und CPU-Register. Eine Strategie, die von GCC zum Verfolgen der Positionen von Variablen in Stapelrahmen in Code verwendet wird, der auf einer i386-Architektur ausgeführt werden soll, besteht darin, die Speicheradresse im Stapelrahmen-Basiszeiger %ebpals Referenz zu verwenden und Werte von Variablen in Positionen in den Stapelrahmen zu schreiben bei Offsets an die Adresse in %ebp.

Es gibt zwei spezielle Register: ESP (Stapelzeiger) und EBP (Basiszeiger). Wenn eine Prozedur aufgerufen wird, werden normalerweise die ersten beiden Operationen ausgeführt

push        ebp  
mov         ebp,esp 

Die erste Operation speichert den Wert des EBP im Stapel, und die zweite Operation lädt den Wert des Stapelzeigers in den Basiszeiger (um auf die lokalen Variablen zuzugreifen). EBP verweist also auf denselben Speicherort wie ESP.

Assembler übersetzt Variablennamen in EBP-Offsets. Zum Beispiel, wenn Sie zwei lokale Variablen x,yhaben und Sie haben so etwas

  x = 1;
  y = 2;
  return x + y;

dann kann es in so etwas wie übersetzt werden

   push        ebp  
   mov         ebp,esp
   mov  DWORD PTR [ ebp + 6],  1   ;x = 1
   mov  DWORD PTR [ ebp + 14], 2   ;y = 2
   mov  eax, [ ebp + 6 ]
   add  [ ebp + 14 ], eax          ; x + y 
   mov  eax, [ ebp + 14 ] 
   ...  

Die Offsetwerte 6 und 14 werden zur Kompilierungszeit berechnet.

So funktioniert es ungefähr. Einzelheiten finden Sie in einem Compiler-Buch.

Sie sind verwirrt, weil auf die im Stapel gespeicherten lokalen Variablen nicht mit der Zugriffsregel des Stapels zugegriffen wird: First In Last Out oder nur FILO .

Die Sache ist die, dass die FILO - Regel Funktionsaufruf Sequenzen und gilt Stapelrahmen , anstatt auf lokale Variablen.

Was ist ein Stapelrahmen?

Wenn Sie eine Funktion eingeben, wird ihr auf dem Stapel eine gewisse Menge an Speicher zugewiesen, die als Stapelrahmen bezeichnet wird. Lokale Variablen der Funktion werden im Stack-Frame gespeichert. Sie können sich vorstellen, dass die Größe des Stapelrahmens von Funktion zu Funktion unterschiedlich ist, da jede Funktion eine unterschiedliche Anzahl und Größe lokaler Variablen aufweist.

Wie lokale Variablen im Stack-Frame gespeichert werden, hat nichts mit FILO zu tun. (Auch die Reihenfolge der Darstellung Ihrer lokalen Variablen in Ihrem Quellcode gewährleistet nicht, dass lokale Variablen in dieser Reihenfolge gespeichert werden.) Wie Sie in Ihrer Frage richtig abgeleitet haben, gibt es einen anderen Index, der nur die Adressen der Variablen enthält auf dem Stapel, damit die Werte abgerufen werden können ". Die Adressen lokaler Variablen werden typischerweise mit einer Basisadresse wie der Grenzadresse des Stapelrahmens und Versatzwerten berechnet, die für jede lokale Variable spezifisch sind.

Wann erscheint dieses FILO-Verhalten?

Was passiert nun, wenn Sie eine andere Funktion aufrufen? Die Aufruffunktion muss einen eigenen Stapelrahmen haben, und dieser Stapelrahmen wird in den Stapel geschoben . Das heißt, der Stapelrahmen der Angerufenen-Funktion wird über den Stapelrahmen der Aufrufer-Funktion gelegt. Wenn diese Angerufene-Funktion eine andere Funktion aufruft, wird ihr Stapelrahmen wieder oben auf den Stapel gelegt.

Was passiert, wenn eine Funktion zurückkehrt? Wenn ein Angerufener Funktion kehrt in die CLIP - Funktion, die Stack - Frame des Angerufenen Funktion tauchte aus dem Stapel heraus, Raumnutzung für zukünftige befreien.

Also von Ihrer Frage:

Geht es bei der Position auf dem Stapel nur um die Lebensdauer / den Gültigkeitsbereich der Variablen und darum, dass das Programm jederzeit auf den gesamten Stapel zugreifen kann?

Sie sind hier ganz richtig, weil die lokalen Variablenwerte im Stapelrahmen nicht wirklich gelöscht werden, wenn die Funktion zurückkehrt. Der Wert bleibt nur dort, obwohl der Speicherort, an dem er gespeichert ist, nicht zum Stack-Frame einer Funktion gehört. Der Wert wird gelöscht, wenn eine andere Funktion ihren Stapelrahmen erhält, der den Speicherort enthält, und einen anderen Wert in diesen Speicherort überschreibt.

Was unterscheidet dann Stapel von Haufen?

Stack und Heap sind insofern identisch, als sie beide Namen sind, die auf Speicherplatz verweisen. Da wir mit seiner Adresse auf jeden Speicherort im Speicher zugreifen können, können Sie auf jeden Speicherort im Stapel oder im Heap zugreifen.

Der Unterschied ergibt sich aus dem Versprechen, dass das Computersystem darüber entscheidet, wie es sie verwenden wird. Wie Sie bereits sagten, dient der Heap als Referenztyp. Da die Werte in Heap keine Beziehung zu einem bestimmten Stack-Frame haben, ist der Gültigkeitsbereich des Werts an keine Funktion gebunden. Eine lokale Variable wird jedoch innerhalb einer Funktion scoped, und obwohl Sie können eine beliebigen lokalen Variable Wert zugreifen , die aus Stapelrahmen Stromfunktion befinden, wird das System versuchen , um sicherzustellen , dass diese Art von Verhalten nicht geschieht, unter Verwendung von Stapelrahmen. Dies gibt uns eine Art Illusion, dass die lokale Variable auf eine bestimmte Funktion beschränkt ist.

Es gibt viele Möglichkeiten, lokale Variablen durch ein Sprachlaufzeitsystem zu implementieren. Die Verwendung eines Stapels ist eine häufig verwendete, effiziente Lösung, die in vielen praktischen Fällen eingesetzt wird.

Intuitiv wird ein Stapelzeiger spzur Laufzeit herumgehalten (in einer festen Adresse oder in einem Register - es ist wirklich wichtig). Angenommen, jeder "Druck" erhöht den Stapelzeiger.

Zur Kompilierungszeit bestimmt der Compiler die Adresse jeder Variablen als sp - Kwobei Kes sich um eine Konstante handelt, die nur vom Umfang der Variablen abhängt (daher zur Kompilierungszeit berechnet werden kann).

Beachten Sie, dass wir das Wort "Stapel" hier in losem Sinne verwenden. Auf diesen Stack kann nicht nur über Push / Pop / Top zugegriffen werden, sondern auch über sp - K.

Betrachten Sie zum Beispiel diesen Pseudocode:

procedure f(int x, int y) {
  print(x,y);    // (1)
  if (...) {
    int z=x+y; // (2)
    print(x,y,z);  // (3)
  }
  print(x,y); // (4)
  return;
}

Beim Aufruf der Prozedur können Argumente x,yauf dem Stack übergeben werden. Nehmen Sie der Einfachheit halber an, dass die Konvention derjenige ist, den der Anrufer xzuerst drückt y.

Dann kann der Compiler bei Punkt (1) xbei sp - 2und ybei finden sp - 1.

Bei Punkt (2) wird eine neue Variable in den Geltungsbereich gebracht. Der Compiler generiert Code, der summiert x+y, dh, worauf durch sp - 2und hingewiesen wird sp - 1, und gibt das Ergebnis der Summe auf dem Stapel aus.

Bei Punkt (3) zwird gedruckt. Der Compiler weiß, dass es sich um die letzte Variable im Gültigkeitsbereich handelt sp - 1. Dies yhat sich seitdem nicht mehr spgeändert. Trotzdem yweiß der Compiler, dass er es in diesem Bereich unter finden kann sp - 2. Ähnlich xist es nun bei zu finden sp - 3.

Bei Punkt (4) verlassen wir den Gültigkeitsbereich. zwird geknallt und ywird erneut unter der Adresse sp - 1und xunter gefunden sp - 2.

Wenn wir zurückkehren, erscheint entweder foder der Anrufer x,yvom Stapel.

Also, Berechnung Kfür den Compiler ist eine Frage der Zählung , wie viele Variablen im Umfang sind, grob. In der realen Welt ist dies komplexer, da nicht alle Variablen die gleiche Größe haben, so dass die Berechnung von Ketwas komplexer ist. Manchmal enthält der Stapel auch die Rücksendeadresse für f, daher Kmuss auch diese "übersprungen" werden. Aber das sind technische Aspekte.

Beachten Sie, dass in einigen Programmiersprachen die Dinge noch komplexer werden können, wenn komplexere Funktionen behandelt werden müssen. Beispielsweise erfordern verschachtelte Prozeduren eine sehr sorgfältige Analyse, da Kjetzt viele Rücksprungadressen "übersprungen" werden müssen, insbesondere wenn die verschachtelte Prozedur rekursiv ist. Closures / Lambdas / anonyme Funktionen erfordern auch einige Sorgfalt im Umgang mit "erfassten" Variablen. Das obige Beispiel soll jedoch die Grundidee veranschaulichen.

Am einfachsten ist es, sich Variablen als feste Namen für Adressen im Speicher vorzustellen. In der Tat zeigen einige Assembler den Maschinencode auf diese Weise an ("Wert 5 in Adresse speichern i", wobei ies sich um einen Variablennamen handelt).

Einige dieser Adressen sind "absolut" wie globale Variablen, andere "relativ" wie lokale Variablen. Variablen (dh Adressen) in Funktionen beziehen sich auf eine bestimmte Stelle im "Stapel", die für jeden Funktionsaufruf unterschiedlich ist. Auf diese Weise kann derselbe Name auf verschiedene tatsächliche Objekte verweisen, und Zirkelaufrufe auf dieselbe Funktion sind unabhängige Aufrufe, die an einem unabhängigen Speicher arbeiten.

Datenelemente, die auf den Stapel gelegt werden können, werden auf den Stapel gelegt - Ja! Es ist ein Premium-Raum. Sobald wir xin den Stapel geschoben und dann yin den Stapel geschoben haben , können wir im Idealfall nicht darauf zugreifen, xbis yes da ist. Wir müssen auftauchen, yum Zugang zu haben x. Du hast sie richtig verstanden.

Der Stack besteht nicht aus Variablen, sondern aus frames

Wo Sie es falsch verstanden haben, geht es um den Stapel selbst. Auf dem Stapel werden nicht die Datenelemente direkt übertragen. Vielmehr wird auf den Stack etwas Aufgerufenes stack-framegeschoben. Dieser Stapelrahmen enthält die Datenelemente. Während Sie nicht auf die Bilder tief im Stapel zugreifen können, können Sie auf das oberste Bild und alle darin enthaltenen Datenelemente zugreifen.

Nehmen wir an, wir haben unsere Datenelemente in zwei Stapelrahmen frame-xund gebündelt frame-y. Wir haben sie nacheinander geschoben. Solange Sie darauf frame-ysitzen frame-x, können Sie im Idealfall nicht auf ein Datenelement im Inneren zugreifenframe-x . Nur frame-yist sichtbar. ABER wenn dies frame-ysichtbar ist, können Sie auf alle darin gebündelten Daten zugreifen. Der gesamte Rahmen ist sichtbar und zeigt alle darin enthaltenen Datenelemente an.

Ende der Antwort. Mehr (schimpfen) über diese Frames

Beim Übersetzen wird eine Liste aller Funktionen im Programm erstellt. Dann wird für jede Funktion eine Liste von stapelbaren Datenelementen erstellt. Dann wird für jede Funktion ein stack-frame-templategemacht. Diese Vorlage ist eine Datenstruktur, die alle ausgewählten Variablen, den Platz für die Eingabedaten der Funktion, die Ausgabedaten usw. enthält. Jetzt wird zur Laufzeit, wenn eine Funktion aufgerufen wird, eine Kopie davon templateauf den Stapel gelegt - zusammen mit allen Eingabe- und Zwischenvariablen . Wenn diese Funktion eine andere Funktion aufruft, wird eine neue Kopie dieser Funktion stack-frameauf den Stapel gelegt. Solange diese Funktion ausgeführt wird, bleiben die Datenelemente dieser Funktion erhalten. Sobald diese Funktion beendet ist, springt der Stapelrahmen heraus. JetztDieser Stack-Frame ist aktiv und diese Funktion kann auf alle seine Variablen zugreifen.

Beachten Sie, dass die Struktur und Zusammensetzung eines Stack-Frames von Programmiersprache zu Programmiersprache unterschiedlich ist. Selbst innerhalb einer Sprache kann es bei verschiedenen Implementierungen subtile Unterschiede geben.

Vielen Dank, dass Sie sich für CS entschieden haben. Ich bin jetzt ein Programmierer, der Tage Klavierunterricht nimmt :)