Deutsch
Menü

Was ist Stack (Stapelspeicher)?

LIFO-Datenstruktur (Last In, First Out), bei der das zuletzt hinzugefügte Element zuerst entnommen wird. Das Hinzufügen eines Elements heißt push, das Entnehmen pop. Stacks dienen zur Verwaltung von Rücksprungadressen und lokalen Variablen bei Funktionsaufrufen (Call Stack), zur Auswertung von Ausdrücken in umgekehrter polnischer Notation und für die Tiefensuche.

Japanische Bezeichnung: スタック

„Stack (Stapelspeicher)“ kommt in 33 Übungsfragen aus 8 Themen vor, z. B. Linker, Loader und ausführbare Formate, Befehlssatz und Assembler, Datenstrukturen und Algorithmen.

Fachgebiet: Datenstrukturen und Algorithmen

Jetzt üben: Fragen zu Stack (Stapelspeicher)

Bei Funktionen, die keine anderen Funktionen aufrufen (Blattfunktionen, Leaf-Funktionen), muss ra oft nicht auf dem Stack gesichert werden. Welche Begründung ist richtig?

  1. AWeil Blattfunktionen den Befehl ret nicht verwenden
  2. BWeil die CPU die Rücksprungadresse einer Blattfunktion automatisch auf den Stack legt
  3. CWeil keine anderen Funktionen aufgerufen werden, ra nicht überschrieben wird und die Rücksprungadresse unverändert erhalten bleibt
Antwort und Erläuterung anzeigen

Antwort: C. Weil keine anderen Funktionen aufgerufen werden, ra nicht überschrieben wird und die Rücksprungadresse unverändert erhalten bleibt

ra wird bei jedem funktionsaufrufenden jal überschrieben, daher muss eine Funktion, die andere Funktionen aufruft, ihre Rücksprungadresse zu Beginn auf dem Stack sichern. Blattfunktionen verwenden kein jal, ra bleibt unverändert, und sie können ohne Sicherung ret ausführen. Verwenden sie zudem keine vom Aufgerufenen gesicherten Register, ist nicht einmal ein Stackframe nötig. Der Befehl call bei x86 legt die Rücksprungadresse stets auf den Stack, was hier ein Unterschied zu RISC-V ist.

Was geschieht bei RISC-V, wenn in einer sich selbst aufrufenden rekursiven Funktion vergessen wird, ra auf dem Stack zu sichern?

  1. Ara wird beim inneren Aufruf überschrieben, und die äußere Funktion kann nicht mehr korrekt zum richtigen Aufrufer zurückkehren
  2. BDie CPU sichert ra automatisch, daher entsteht kein Problem
  3. CUnabhängig von der Rekursionstiefe verdoppelt sich das Rechenergebnis
Antwort und Erläuterung anzeigen

Antwort: A. ra wird beim inneren Aufruf überschrieben, und die äußere Funktion kann nicht mehr korrekt zum richtigen Aufrufer zurückkehren

Das jal des rekursiven Aufrufs überschreibt ra mit „dem Befehl nach dem Aufruf in der Funktion selbst“. Ohne Sicherung kehrt die äußere Funktion bei ret nicht zum ursprünglichen Aufrufer, sondern in sich selbst zurück, wiederholt dieselbe Stelle oder arbeitet fehlerhaft. Daher gilt als Regel, dass eine Funktion, die andere Funktionen aufruft, ra im Prolog auf dem Stack sichert und im Epilog wiederherstellt.

„Stack (Stapelspeicher)“ in den Erläuterungen

Fragen mit „Stack (Stapelspeicher)“ (33)

  1. Bei Funktionen, die keine anderen Funktionen aufrufen (Blattfunktionen, Leaf-Funktionen), muss ra oft nicht auf dem Stack gesichert werden. Welche Begründung ist richtig?
  2. Was geschieht bei RISC-V, wenn in einer sich selbst aufrufenden rekursiven Funktion vergessen wird, ra auf dem Stack zu sichern?
  3. Welcher Vorteil ergibt sich daraus, Heap und Stack eines Prozesses mit einem großen freien Bereich dazwischen in entgegengesetzte Richtungen wachsen zu lassen?
  4. Was ist bei einem kleinen Mikrocontroller ohne MMU im Hinblick auf übermäßige Stack-Nutzung zu beachten?
  5. Auf einem leeren Stack werden nacheinander die Operationen push 1, push 2, pop, push 3, push 4, pop, pop ausgeführt. In welcher Reihenfolge werden die Werte durch pop entnommen?
  6. Der Ausdruck „3 4 + 2 * 5 −“ in umgekehrter polnischer Notation (Postfixnotation) wird ausgewertet, indem jede Zahl auf einen Stack gelegt wird und bei jedem Operator zwei Werte entnommen, verrechnet und das Ergebnis wieder abgelegt wird. Welches Ergebnis entsteht? Der linke Operand eines Operators ist der Wert, der früher abgelegt wurde.
  7. Ein Stack wird durch das ganzzahlige Array st mit 5 Elementen und die ganzzahlige Variable top dargestellt. Alle Elemente von st sind anfangs 0, und top beginnt bei 0. push(v) addiert 1 zu top und führt dann st[top] ← v aus; pop() gibt den Wert von st[top] zurück und subtrahiert dann 1 von top (die Elemente von st werden nicht verändert). Welche Werte haben top und st, nachdem das folgende Programm ausgeführt wurde?
  8. Was enthält der Programmzähler (PC) einer CPU?
  9. Welcher Bereich wird beim Aufruf einer Subroutine (Funktion) üblicherweise genutzt, um Rücksprungadresse usw. vorübergehend zu sichern?
  10. Welche Wirkung hat der RISC-V-Befehl „lw t0, 8(sp)“?
  11. Was ist der Hauptzweck der Festlegung einer Aufrufkonvention (Calling Convention)?
  12. Welche Register werden in der Standard-Aufrufkonvention von RISC-V zur Übergabe von Ganzzahlargumenten und Rückgabewerten verwendet?
  13. Wo werden das 9. und 10. Argument übergeben, wenn in der Standard-Aufrufkonvention von RISC-V eine Funktion mit 10 Ganzzahlargumenten aufgerufen wird?
  14. Was bedeutet es, dass s0 bis s11 in der RISC-V-Aufrufkonvention „vom Aufgerufenen gesichert“ (callee-saved) sind?
  15. Welchen Zweck hat die Ausführung von „addi sp, sp, -16“ am Anfang einer RISC-V-Funktion?

Vergleiche mit diesem Begriff

Verwandte Begriffe

Rekursion Rücksprungadresse Heap Variable Aufrufkonvention Argument Rückgabewert Stackpointer Zeiger (Pointer) ASLR

Zur Glossarübersicht