Ring stabel
I informatikk er en anropsstabel (bokstavelig oversatt fra engelsk som "call stack") et minneområde i et program, organisert i form av en stabel , der informasjon om de aktive underrutinene i et gitt øyeblikk er lagret ( de aktive subrutinene er de som har blitt påkalt, men hvis utførelse ikke er fullført). Det kan oversettes som en stabel med funksjonsanrop (eller funksjonskall ) eller en stabel med metodeanrop ( eller metodekall ) avhengig av typen subrutine som er involvert.
Denne typen stack blir også ofte referert til som en utførelsesstack , kontrollstack , funksjonsstack eller runtimestack , eller, når det ikke er mulighet for forvirring, bare en stack .
Settet med informasjon som er spesifikk for en subrutine i en anropsstabel kalles en ramme .
Operasjon
Grunnen til at du må ta i bruk en anropsstabel er å holde styr på hvor hver aktive subrutine skal returnere kontroll når den er ferdig utført. Hvis for eksempel en DrawSquare (draw a square) subrutine kaller DrawLine (draw a line) subrutinen fra fire forskjellige punkter, må DrawLine-koden kunne vite hvor den skal returnere etter utførelse. Denne oppgaven utføres vanligvis av koden for hvert anrop i DrawSquare ved å sette inn instruksjonsadressen etter en bestemt "returadresse" i anropsstakken.
Siden anropsstakken er organisert som en stabel, legger den anropende funksjonen returadressen på toppen av stabelen og den anropte subrutinen, når den avsluttes, tar returadressen av stabelen og overfører kontrollen til den adressen. Hvis en oppringt subrutine kaller en annen subrutine, vil den legge returadressen over anropsstakken, og så videre blir informasjonen stablet og fjernet som forventet av programmet . Hvis all ledig plass til samtalestakken brukes, oppstår en feil som kalles stabeloverflyt . Å legge til en subrutine til anropsstakken kalles vikling ; å fjerne den kalles avvikling.
Det er vanligvis bare én anropsstabel knyttet til et kjørende program (eller mer presist med hver oppgave eller tråd i en prosess), men ytterligere stabler kan opprettes for å håndtere signaler eller for samarbeidende multitasking . Siden det bare er én i denne viktige sammenhengen, refererer vi ganske enkelt til stabelen (implisitt "av oppgaven").
I programmeringsspråk på høyt nivå er anropsstabelspesifikasjonene skjult for programmereren . Sistnevnte har bare tilgang til listen over funksjoner og ikke til minnet som er okkupert av stabelen, og heller ikke til den interne strukturen som er vedtatt. Mange monteringsspråk krever derimot at programmerere er involvert i stackhåndtering. Detaljene til stabelen i et programmeringsspråk avhenger også av kompilatoren, operativsystemet og instruksjonene som er tilgjengelige.
Hensikten med anropsstakken
Hovedformålet med anropsstakken er:
- lagre returadresser - Når en subrutine kalles, må adressen til returinstruksjonen lagres et sted. Å bruke en stabel til å lagre returadresser har store fordeler fremfor alternativer. En av dem er at hver oppgave har sin egen stabel og derfor kan subrutiner være "reentrant" og kan derfor være aktive samtidig for forskjellige oppgaver som gjør forskjellige ting. En annen fordel er at rekursjon støttes automatisk. Når en funksjon kaller seg rekursivt, må det registreres en returadresse for hver funksjonsaktivering slik at den kan brukes til retur fra hver funksjonsaktivering. Denne funksjonen er automatisk med en stabel.
En anropsstabel kan ha flere formål, avhengig av språket, operativsystemet og maskinmiljøet. Mellom disse:
- lagre lokale data - En subrutine trenger ofte minneplass for å registrere verdiene til lokale variabler, variabler som bare brukes i den aktive subrutinen og som ikke må inneholde verdier etter retur (til den anropende funksjonen). Det er ofte praktisk å tildele plass for denne bruken for å bare flytte til toppen av stabelen nok til å ha plass. Det er veldig raskt sammenlignet med for eksempel heap- allokering . Hver forskjellig aktivering av en subrutine har sin egen separate stabelplass for lokale data.
- overføring av parametere - Subrutiner krever ofte at parameterverdier leveres av koden som kaller dem, og det er ikke uvanlig at det er plass til disse parameterne i anropsstakken. Vanligvis hvis det bare er noen få små parametere, kan prosessorregistrene brukes til å sende verdier, men hvis det er flere parametere som skal administreres på denne måten, kreves minneplass. Anropsstakken fungerer best som et sted for disse parameterne, spesielt siden hvert subrutineanrop, som vil ha forskjellige parameterverdier, vil ha en egen plass i anropsstakken for disse verdiene.
- evalueringsstabel - Operander for aritmetiske og logiske operasjoner legges ofte inn i registeret og brukes der. Men i noen situasjoner kan operandene stables til en vilkårlig dybde, noe som betyr at noe mer enn registeret må brukes. Stabelen med disse operandene, lik RPN-type datamaskiner, kalles evalueringsstabelen og kan ta opp plass på anropsstakken.
- gjeldende instanspeker - Noen objektorienterte språk (som C ++ ) lagrer denne pekeren som et argument for funksjoner i anropsstakken når en metode påkalles. Denne pekeren peker på forekomsten av objektet som den påkalte metoden er assosiert med. Det er en vesentlig del av utførelseskonteksten til objektorienterte språk, siden det gir tilgang til dataene som eies av det gjeldende objektet. Denne pekeren er koblet til lag som brukes i lagdelt objektorientert programmering (typer av stabelstrukturer) i kjøretidsanropsstakken.
- Subroutine Container Environment - Noen programmeringsspråk (som Pascal og Ada ) støtter nestede subrutiner , slik at en intern rutine får tilgang til konteksten til containerrutinen sin, det vil si parametere og lokale variabler i miljøet til den eksterne rutinen. Slike språk tillater vanligvis rutiner å foreta rekursive anrop (funksjonen kaller seg selv), noe som resulterer i flere anropsstabler for rutineanrop til interne rutiner, som hver peker til det samme miljøet som den eksterne rutinen. Denne typen samtaleramme er også kjent som en skjerm .
