Nederlands
Menu

Wat is Stack (stapelgeheugen)?

Last-in-first-out-datastructuur (LIFO) waarin het laatst toegevoegde element als eerste wordt verwijderd. Een element toevoegen heet push en een element verwijderen pop. Stacks worden gebruikt om retouradressen en lokale variabelen bij functieaanroepen te beheren (de call stack), om expressies in omgekeerde Poolse notatie te evalueren en voor diepte-eerst zoeken.

Japanse benaming: スタック

“Stack (stapelgeheugen)” komt voor in 33 oefenvragen uit 8 onderwerpen, bijv. Linker, loader en uitvoerbare formaten, Instructieset en assembly, Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Stack (stapelgeheugen)

Bij functies die geen andere functies aanroepen (bladfuncties, leaf functions) hoeft ra vaak niet op de stack te worden opgeslagen. Wat is de juiste reden?

  1. ABladfuncties gebruiken geen ret-instructie
  2. BDe CPU plaatst het terugkeeradres van een bladfunctie automatisch op de stack
  3. COmdat ze geen andere functies aanroepen, wordt ra niet overschreven en blijft het terugkeeradres behouden
Antwoord en toelichting tonen

Antwoord: C. Omdat ze geen andere functies aanroepen, wordt ra niet overschreven en blijft het terugkeeradres behouden

ra wordt bij elke jal die een functie aanroept overschreven, dus een functie die andere functies aanroept moet zijn eigen terugkeeradres eerst op de stack opslaan. Een bladfunctie gebruikt geen jal, dus ra blijft intact en kan zonder opslaan met ret terugkeren. Als ook geen callee-saved-registers worden gebruikt, hoeft zelfs geen stackframe te worden gemaakt. De call-instructie van x86 plaatst het terugkeeradres altijd op de stack, wat hier een verschil met RISC-V is.

Wat gebeurt er als men bij het schrijven van een recursieve functie die zichzelf aanroept in RISC-V vergeet ra op de stack op te slaan?

  1. Ara wordt door de binnenste aanroep overschreven en de buitenste functie kan niet meer correct naar de juiste aanroeper terugkeren
  2. BDe CPU slaat ra automatisch op, dus er treedt geen probleem op
  3. CHet rekenresultaat wordt verdubbeld, ongeacht de recursiediepte
Antwoord en toelichting tonen

Antwoord: A. ra wordt door de binnenste aanroep overschreven en de buitenste functie kan niet meer correct naar de juiste aanroeper terugkeren

De jal van een recursieve aanroep overschrijft ra met „de instructie na de aanroep binnen de functie zelf”. Als dat niet is opgeslagen, keert de buitenste functie bij ret niet terug naar de oorspronkelijke aanroeper maar in zichzelf, waardoor dezelfde plaats herhaaldelijk wordt doorlopen of een storing optreedt. Daarom is afgesproken dat een functie die andere functies aanroept in de prologue ra op de stack opslaat en in de epiloog terugzet.

“Stack (stapelgeheugen)” in de toelichting

Vragen met “Stack (stapelgeheugen)” (33)

  1. Bij functies die geen andere functies aanroepen (bladfuncties, leaf functions) hoeft ra vaak niet op de stack te worden opgeslagen. Wat is de juiste reden?
  2. Wat gebeurt er als men bij het schrijven van een recursieve functie die zichzelf aanroept in RISC-V vergeet ra op de stack op te slaan?
  3. Welk voordeel is juist van de indeling waarin heap en stack van een proces in tegengestelde richting groeien met ertussen een breed vrij gebied?
  4. Wat gebeurt er in het algemeen op Linux en dergelijke als recursie te diep wordt en de bovengrens van de stack wordt overschreden?
  5. Op een lege stack worden achtereenvolgens push 1, push 2, pop, push 3, push 4, pop, pop uitgevoerd. In welke volgorde komen de waarden die pop verwijdert eruit?
  6. De expressie „3 4 + 2 * 5 −” in omgekeerde Poolse notatie (postfixnotatie) wordt geëvalueerd door elk getal op een stack te leggen en bij elke operator twee waarden eraf te halen, het resultaat te berekenen en dat weer op de stack te leggen. Wat is het resultaat? De linkeroperand van een operator is de waarde die het eerst op de stack is gelegd.
  7. Een stack wordt voorgesteld door de integer-array st met 5 elementen en de variabele top van het type integer. Alle elementen van st zijn aanvankelijk 0, en top begint bij 0. push(v) telt 1 op bij top en voert dan st[top] ← v uit; pop() geeft de waarde van st[top] terug en trekt dan 1 af van top (de elementen van st veranderen niet). Wat zijn top en st nadat het volgende programma is uitgevoerd?
  8. Wat bevat de programmateller (program counter, PC) van de CPU?
  9. Welk geheugengebied wordt gewoonlijk gebruikt om bij het aanroepen van een subroutine (functie) tijdelijk onder meer het terugkeeradres op te slaan?
  10. Welke werking van de RISC-V-instructie „lw t0, 8(sp)” is juist?
  11. Wat is het belangrijkste doel van het vastleggen van een aanroepconventie (calling convention)?
  12. Welke registers worden in de standaard RISC-V-aanroepconventie gebruikt om gehele-getalargumenten en retourwaarden door te geven?
  13. Waar worden in de standaard RISC-V-aanroepconventie het 9e en 10e argument doorgegeven bij het aanroepen van een functie met 10 gehele-getalargumenten?
  14. Wat betekent het dat s0 tot s11 in de RISC-V-aanroepconventie „callee-saved”-registers zijn?
  15. Wat is het juiste doel van het uitvoeren van „addi sp, sp, -16” aan het begin van een RISC-V-functie?

Vergelijkingen met deze term

Verwante termen

Variabele Recursie Heap Aanroepconventie (calling convention) Array Argument Stackframe Wachtrij (queue) Stackpointer Retourwaarde (return value)

Naar de woordenlijst