Habitat netopirjev. Netopirji
Pri obvladovanju programiranja se prej ali slej pojavi vprašanje: " Kaj je sklad?".
Mislim, da je najbolj očiten način za razlago tega program v zbirnem jeziku (ne skrbite), ki preprosto doda podatke v sklad.
Stack je podatkovna struktura, ki je del vse programabilne tehnologije. Najpogosteje se načelo delovanja sklada primerja s kupom plošč: če želite vzeti drugo z vrha, morate odstraniti zgornjo. Sklad se pogosto imenuje trgovina - po analogiji s trgovino v strelno orožje(streljanje se bo začelo z zadnjim napolnjenim nabojem).
Zakaj je vse to potrebno?
Skoraj ne morete napisati programa, ki ne uporablja funkcij (podprogramov). Ko je funkcija poklicana, se naslov prekopira na sklad, da se vrne po koncu izvajanja tega podprograma. Na koncu njegovega izvajanja se naslov vrne iz sklada v programski števec in program nadaljuje z izvajanjem od točke za funkcijo.
Tudi registri, ki se uporabljajo v tem podprogramu, morajo biti postavljeni na sklad (v jezikih visoki ravni prevajalnik to naredi).
Vse našteto je značilno za tako imenovani strojni sklad. Upam, da se zavedate, da je ta struktura podatkov (LIFO - zadnji vstop, prvi ven) uporabna ne le pri delu na nizki ravni. Pogosto obstaja potreba po shranjevanju podatkov v tem vrstnem redu (na primer dobro znani algoritem za razčlenjevanje aritmetičnih izrazov temelji na delu s skladom), nato programerji implementirajo programski sklad.
Kako to deluje?
dajmo poglejmo delo s skladom na primeru krmilnikov družine MSP430. Izbral sem jih samo zato, ker sem slučajno imel nameščeno okolje za delo z njimi.
V MSP430 sklad temelji na preddekrementalni zasnovi. Tisti. Preden zapišete podatke v sklad, zmanjša naslov vrha sklada (zgornji krožnik). Obstajajo tudi postdekrementalni/postinkrementalni (odštevanje/dodajanje vrha sklada se pojavi po zapisu podatkov) in predinkrementalni (pred pisanjem se naslov vrha poveča).
Če sklad povečuje svoj naslov med zapisovanjem podatkov, pravimo, da raste navzgor; če se zmanjšuje, se reče, da raste navzdol.
Register SP je odgovoren za shranjevanje naslova vrha sklada.
Kot lahko vidite, je privzeti naslov vozlišča 0x0A00.
Razmislite o tem programu:
POTISNI #0123h ; Postavitev 0123h na vrh sklada (TOS); kopiranje podatkov iz pomnilnika MOV.W &0x0A00, R5 MOV.W &0x09FE, R6 ; napišite še dve številki PUSH #9250h PUSH #0000h ; pop podatke iz sklada POP R8 POP R9 POP R10
Kaj počne ta program?
Z ukazom PUSH potisnemo podatek 0123h na sklad. Zdi se, da bi s tem ukazom zapisali 0123h v pomnilnik na naslov 0x0A00, vendar se spomnimo, da je naš sklad preddekrementalen. Zato se najprej naslov zmanjša za 2 (0x0A00 - 2 = 0x09FE) in podatki se zapišejo v celico s prejetim naslovom.
Takole je prvotno izgledal spomin:
Po izvedbi ukaza PUSH (spremembe so označene rdeče):
Podatki so torej zabeleženi.
Ali je to res, preverimo z izvedbo dveh ukazov za prenos (mov). Najprej bomo prejeli podatke iz celice 0x0A00 in jih zapisali v register R5, nato pa podatke iz celice 0x09FE zapisali v register R6.
Po tem bodo registri vsebovali naslednje podatke:
Pri izvajanju ukazov POP se vrh sklada z vsakim ukazom poveča za 2, podatki v registrih R8-10 pa bodo 0x0000, 0x9250 oziroma 0x0123.
Ko je dodanih več podatkov, bo pomnilnik (ki še vedno vsebuje podatke, izstreljene iz sklada) napolnjen z novimi vrednostmi.
Delo s skladom lahko ponazorite tako (od leve proti desni):
Sprva je bil naslov sklada 0x0A00, vanj je bil shranjen 0000. Ko je bil izveden PUSH, je spodnja celica (z naslovom 0x09FE) postala vrh sklada in vanjo so bili zapisani podatki. Z vsakim naslednjim ukazom se vrh nahaja nižje v pomnilniku.
Pri izvajanju ukaza POP se slika obrne.
Veselim se vaših vprašanj v komentarjih.
Stack je programski pojav in naravna rešitev. Stack je takoj prišel v računalniški posel in postal tako »domači«, kot da se je tam vse začelo.
Brez sklada procesor ne deluje, ni rekurzije in ni mogoče organizirati učinkovitih klicev funkcij. Vsak algoritem lahko deluje brez čakalne vrste, seznama, zbirke, niza ali sistema organiziranih objektov, vendar nič ne deluje brez pomnilnika in sklada, vključno z vsem zgoraj naštetim.
Na zori začetkov: procesor, pomnilnik in sklad
Idealni pomnilnik omogoča naslavljanje neposredno na vrednost - to sta strojna in jezikovna raven visoka stopnja. V prvem primeru procesor zaporedno ponavlja pomnilniške naslove in izvaja navodila. V drugem primeru programer manipulira z nizi. Obe epizodi vsebujeta:
- naslov = vrednost;
- indeks = vrednost.
Naslov je lahko absoluten in relativen, indeks je lahko digitalen in asociativen. Naslov in indeks lahko vsebujeta drugačen naslov kot vrednost, vendar so to podrobnosti posrednega naslavljanja. Brez pomnilnika procesor ne more delovati, brez kopice ukazov in podatkov pa je kot čoln brez vesla.
Kup krožnikov je tradicionalna zgodba o bistvu sklada: konceptu sklada in prevodu v splošni zavesti. Krožnika ne morete vzeti od spodaj, lahko ga vzamete samo od zgoraj in potem bodo vsi krožniki nedotaknjeni.
Karkoli pride zadnje na kup, gre najprej. Popolna rešitev. V bistvu stack kot prevod enega dejanja v drugega preoblikuje idejo algoritma kot zaporedja operacij.
Bistvo in koncept sklada
Procesor in pomnilnik - glavni strukturni elementi računalnik. Procesor izvaja navodila, manipulira s pomnilniškimi naslovi ter pridobiva in spreminja vrednosti na teh naslovih. V programskem jeziku se vse to pretvori v spremenljivke in njihove vrednosti. Bistvo sklada in koncept LIFO (last in first out) ostaja nespremenjen.
Akronim LIFO se ne uporablja več tako pogosto kot nekoč. Verjetno zato, ker so bili seznami preoblikovani v objekte in se po potrebi uporabljajo čakalne vrste prvi v prvi ven (FIFO). Dinamika podatkovnih tipov je izgubila pomen v kontekstu opisovanja spremenljivk, ampak je dobila pomen v času izvajanja izrazov: vrsta podatka je določena v trenutku njegove uporabe in do tega trenutka lahko opisujete karkoli in kakorkoli želite.
Torej, stack - kaj je to? Zdaj veste, da je to neprimerno vprašanje. Navsezadnje brez sklada ni sodobnega programiranja. Vsak klic funkcije pomeni posredovanje parametrov in povratnega naslova. Funkcija lahko pokliče drugo funkcijo - to je ponovno posredovanje parametrov in povratnega naslova. Nastavitev mehanizma za klicanje vrednosti brez sklada je dodatno delo, čeprav je dosegljiva rešitev zagotovo mogoča.
Mnogi se sprašujejo: "Stack - kaj je to?" V kontekstu klica funkcije je sestavljen iz treh dejanj:
- shranjevanje povratnega naslova;
- shranjevanje vseh prenesenih spremenljivk ali naslovov nanje;
- klic funkcije.
Ko klicana funkcija zaključi svojo nalogo, bo preprosto vrnila nadzor na povratni naslov. Funkcija lahko kliče poljubno število drugih funkcij, saj je omejitev le velikost sklada.
Lastnosti sklada
Sklad ni abstraktna podatkovna vrsta, ampak pravi mehanizem. Na ravni procesorja je to »motor«, ki izpopolnjuje in dopolnjuje delo glavnega procesorskega cikla. Tako kot bitna aritmetika tudi sklad zajema preprosta in očitna pravila delovanja. Je zanesljiv in varen.
Značilni lastnosti sklada sta njegova velikost in dolžina njegovih elementov. Na procesorski ravni je vse odvisno od bitne kapacitete, naslavljanja pomnilnika in fizike dostopa do njega. Zanimiva funkcija in tradicija: sklad raste navzdol, to je proti zmanjševanju pomnilniških naslovov, programski in podatkovni pomnilnik pa navzgor. To je običajno, vendar ni obvezno. Tu je pomemben pomen - prišel je zadnji in odšel prvi. To presenetljivo preprosto pravilo vam omogoča sestavljanje zanimivih algoritmov, predvsem v jezikih visoke ravni. Zdaj se ne boste vprašali, kaj je kup?
Brezhibno delovanje strojne opreme je že zelo dolgo norma, vendar na samem vrhu informacijska tehnologija Zamisel o skladu pridobiva nove in obetavne aplikacije.
V bistvu ni pomembno, kakšen je sklad na ravni procesorja. Je naravni del računalniške arhitekture. Toda pri programiranju je sklad odvisen od specifične aplikacije in sposobnosti programerja.
Nizi, zbirke, seznami, čakalne vrste ... Stack!
Ljudje pogosto postavljajo vprašanje: "Stack - kaj je to?" "Programiranje" in "sistematizacija" - zanimivi koncepti: Nista sinonima, sta pa tako tesno povezana. Programiranje je zelo hitro šlo tako daleč, da se zdijo doseženi vrhovi idealni. Najverjetneje temu ni tako. Ampak očitno nekaj drugega.
Ideja sklada se ni udomačila le na ravni različnih programskih jezikov, ampak tudi na ravni njihovih zasnov in zmožnosti ustvarjanja podatkovnih vrst. Vsaka matrika ima push in pop, koncepta "prvega in zadnjega elementa matrike" pa sta postala tradicionalna. Prej so obstajali samo elementi niza, danes pa obstajajo:
- elementi niza;
- prvi element matrike;
- zadnji element niza.
Operacija umeščanja elementa v matriko premakne kazalec in pridobitev elementa z začetka ali konca matrike naredi razliko. V bistvu je to isti sklad, vendar uporabljen za druge vrste podatkov.
Posebej je treba omeniti, da priljubljeni programski jeziki nimajo konstrukcije sklada. Toda njegovo idejo razvijalcu posredujejo v celoti.
(angleško last in - first out, "last in - first out").
Najpogosteje se načelo delovanja sklada primerja s kupom plošč: če želite vzeti drugo z vrha, morate odstraniti zgornjo.
V nekaterih jezikih (na primer Lisp, Python) lahko kateri koli seznam imenujemo sklad, saj so zanje na voljo pop in push operacije. V C++ ima standardna knjižnica razred z implementirano strukturo in metodami. itd.
Sklad programske opreme
Organizacija v spominu
Pogosto je sklad implementiran kot enosmerni seznam (vsak element na seznamu vsebuje poleg informacij, shranjenih v skladu, še kazalec na naslednji element sklada).
Toda sklad se pogosto nahaja tudi v enodimenzionalni matriki z urejenimi naslovi. Ta organizacija skladov je primerna, če informacijski element zaseda določeno število besed v pomnilniku, na primer 1 besedo. To odpravlja potrebo po shranjevanju eksplicitnega kazalca na naslednji element sklada v elementu sklada, kar prihrani pomnilnik. V tem primeru je kazalec sklada ( Kazalec sklada, - SP) je običajno register procesorja in kaže na naslov glave sklada.
Na primer, predpostavimo, da se glava sklada nahaja na nižjem naslovu, naslednji elementi pa se nahajajo na naraščajočih naslovih. Vsakič, ko je beseda potisnjena na sklad, se SP najprej zmanjša za 1, nato pa se naslov iz SP zapiše v pomnilnik. Vsakič, ko se beseda odstrani iz sklada, najprej prebere trenutni naslov iz SP in nato poveča vsebino SP za 1.
Pri organiziranju sklada kot enosmernega seznama je vrednost spremenljivke sklada kazalec na njegov vrh - naslov vrha. Če je sklad prazen, je vrednost kazalca NULL.
Primer implementacije sklada v C:
struct stack (char * data; struct stack * next;);
Stack Operations
V skladu so možne tri operacije: dodajanje elementa (imenovano tudi potiskanje), odstranjevanje elementa (pop) in branje elementa glave (peek).
Ko se doda potiskanje (potisk). nov element, ki označuje element, ki je bil prej glava. Novi element zdaj postane glavni element.
Pri brisanju elementa (pop) se prvi odstrani, glavni pa postane tisti, na katerega je imel ta objekt kazalec (naslednji element). V tem primeru se vrne vrednost odstranjenega elementa.
void push (STACK * ps, int x) // Dodajanje novega elementa v sklad( if ( ps -> size == STACKSIZE ) // Ali je sklad prepoln?( fputs ( "Napaka: stack overflow \n ", stderr); abort (); ) else ( ps -> items [ ps -> size ++ ] = x ; ) ) int pop ( STACK * ps ) // Odstrani iz sklada( če ( ps -> velikost == 0 ) // Ali je sklad prazen?( fputs ( "Napaka: stack underflow \n ", stderr); abort (); ) else ( return ps -> items [ -- ps -> size ]; ) )
Področje uporabe
Programski pogled sklada se uporablja za prečkanje podatkovnih struktur, kot je drevo ali graf. Pri uporabi rekurzivnih funkcij bo uporabljen tudi sklad, vendar v strojni obliki. Poleg teh namenov se sklad uporablja za organizacijo skladovnega stroja, ki izvaja izračune v obratnem poljskem zapisu.
Klicni sklad se uporablja za sledenje povratnim točkam iz podprogramov.
Zamisel o skladu se uporablja v stroju za sklad med programskimi jeziki, ki temeljijo na skladu.
Uporaba sklada poenostavi in pohitri delo programa, saj se na enem naslovu dostopa do več podatkov.
Sklad strojne opreme
Pred uporabo sklada ga je treba inicializirati, tako da registri SS:ESP kažejo na naslov glave sklada v območju fizičnega RAM-a, zahtevano število pomnilniških celic pa mora biti rezervirano za shranjevanje podatkov na sklad (očitno sklada v ROM-u seveda ni mogoče organizirati). Aplikacijski programi praviloma od operacijskega sistema prejmejo sklad, pripravljen za uporabo. V načinu zaščitenega procesorja segment stanja opravila vsebuje štiri izbirnike segmentov sklada (za različne ravni privilegiji), vendar se hkrati uporablja samo en sklad.
Opombe
- Turingov stroj: Uvod (nedefinirano) . Pridobljeno dne 12. februar 2013.
Najpogosteje se načelo delovanja sklada primerja s kupom plošč: če želite vzeti drugo z vrha, morate odstraniti zgornjo.
V nekaterih jezikih (na primer Lisp, Python) lahko kateri koli seznam imenujemo sklad, saj so zanje na voljo pop in push operacije. V C++ ima standardna knjižnica razred z implementirano strukturo in metodami. itd.
Enciklopedični YouTube
1 / 3
Informatika. Podatkovne strukture: sklad. Spletni učni center Foxford
#9. Sklad / 1. Sestavljalnik in postopki / Programiranje iz nič
Osnove podatkovnih omrežij. Model OSI in protokolni sklad TCP IP. Osnove Etherneta.
Podnapisi
Sklad programske opreme
Organizacija v spominu
Pogosto je sklad implementiran kot enosmerni seznam (vsak element na seznamu vsebuje poleg informacij, shranjenih v skladu, še kazalec na naslednji element sklada).
Toda sklad se pogosto nahaja tudi v enodimenzionalni matriki z urejenimi naslovi. Ta organizacija sklada je primerna, če element informacije zaseda določeno število besed v pomnilniku, na primer 1 besedo. To odpravlja potrebo po shranjevanju eksplicitnega kazalca na naslednji element sklada v elementu sklada, kar prihrani pomnilnik. V tem primeru je kazalec sklada ( Kazalec sklada, - SP) je običajno register procesorja in kaže na naslov glave sklada.
Na primer, predpostavimo, da se glava sklada nahaja na nižjem naslovu, naslednji elementi pa se nahajajo na naraščajočih naslovih. Vsakič, ko je beseda potisnjena na sklad, se SP najprej zmanjša za 1, nato pa se naslov iz SP zapiše v pomnilnik. Vsakič, ko se beseda odstrani iz sklada, najprej prebere trenutni naslov iz SP in nato poveča vsebino SP za 1.
Pri organiziranju sklada kot enosmernega seznama je vrednost spremenljivke sklada kazalec na njegov vrh - naslov vrha. Če je sklad prazen, je vrednost kazalca NULL.
Primer implementacije sklada v C:
struct stack (char * data; struct stack * next;);
Stack Operations
V skladu so možne tri operacije: dodajanje elementa (imenovano tudi potiskanje), odstranjevanje elementa (pop) in branje elementa glave (peek).
Pri potisku (push) se doda nov element, ki kaže na element, ki je bil prej glava. Novi element zdaj postane glavni element.
Pri brisanju elementa (pop) se prvi odstrani, glavni pa postane tisti, na katerega je imel ta objekt kazalec (naslednji element). V tem primeru se vrne vrednost odstranjenega elementa.
void push (STACK * ps, int x) // Dodajanje novega elementa v sklad( if ( ps -> size == STACKSIZE ) // Ali je sklad prepoln?( fputs ( "Napaka: stack overflow \n ", stderr); abort (); ) else ( ps -> items [ ps -> size ++ ] = x ; ) ) int pop ( STACK * ps ) // Odstrani iz sklada( če ( ps -> velikost == 0 ) // Ali je sklad prazen?( fputs ( "Napaka: stack underflow \n ", stderr); abort (); ) else ( return ps -> items [ -- ps -> size ]; ) )
Področje uporabe
Programski pogled sklada se uporablja za prečkanje podatkovnih struktur, kot je drevo ali graf. Pri uporabi rekurzivnih funkcij bo uporabljen tudi sklad, vendar v strojni obliki. Poleg teh namenov se sklad uporablja za organiziranje
Podobni procesi se zgodijo med strojno prekinitvijo (procesor X86 med strojno prekinitvijo samodejno shrani register zastavic na sklad). Poleg tega prevajalniki lokalne spremenljivke postopka postavijo v sklad (če ima procesor dostop do naključne lokacije sklada).
Pred uporabo sklada ga je treba inicializirati, tako da registri SS:ESP kažejo na naslov glave sklada v območju fizičnega RAM-a, zahtevano število pomnilniških celic pa mora biti rezervirano za shranjevanje podatkov na sklad (očitno sklada v ROM-u seveda ni mogoče organizirati). Aplikacijski programi praviloma od operacijskega sistema prejmejo sklad, pripravljen za uporabo. V načinu zaščitenega procesorja vsebuje segment stanja opravila štiri izbirnike segmentov sklada (za različne ravni privilegijev), vendar se hkrati uporablja samo en sklad.
Pomnilnik, ki ga uporabljajo programi, je sestavljen iz več delov − segmenti:
segment kode(ali "besedilni segment"), kjer se nahaja prevedeni program. Segment kode je običajno samo za branje;
segment bss(ali "neinicializiran podatkovni segment"), kjer so shranjene globalne in ničelne inicializirane vrednosti;
podatkovni segment(ali "inicializiran podatkovni segment"), kjer so shranjene inicializirane globalne in statične spremenljivke;
Zapoučevanje(kupa), od koder so dodeljene dinamične spremenljivke;
klicni sklad, kjer so shranjene lokalne spremenljivke in druge informacije, povezane s funkcijami.
V tej vadnici si bomo ogledali samo kup in sklad, saj se tam dogaja vsa zabava.
Kup
Segment kopice(ali preprosto " kup") spremlja pomnilnik, uporabljen za dinamično dodeljevanje. Malo smo že govorili o kupu v.
Ko v C++ uporabite operator new za dodelitev dinamičnega pomnilnika, je ta pomnilnik dodeljen v lastnem segmentu kopice aplikacije.
int *ptr = novo int; // ptr dodeli 4 bajte iz kopice int *array = new int; // polje dodeli 40 bajtov iz kopice
Novi operater posreduje naslov dodeljenega pomnilnika in ga nato lahko shrani v . Zdaj nam ni treba skrbeti za mehanizem za shranjevanje in dodeljevanje prostega pomnilnika. Vendar je vredno vedeti, da zaporedne pomnilniške zahteve ne povzročijo vedno dodelitve zaporednih pomnilniških naslovov!
int *ptr1 = novo int; int *ptr2 = novo int; // ptr1 in ptr2 ne smeta imeti zaporednih naslovov
Ko je dinamično dodeljena spremenljivka izbrisana, se pomnilnik vrne nazaj v kopico in ga je nato mogoče znova dodeliti (na podlagi poznejših zahtev). Ne pozabite, da brisanje kazalca ne izbriše spremenljivke, ampak preprosto povzroči, da se pomnilnik na tem naslovu vrne nazaj v operacijski sistem.
Kopica ima svoje prednosti in slabosti:
Dodeljevanje pomnilnika na kupu je sorazmerno počasno.
Dodeljeni pomnilnik ostane dodeljen, dokler ni osvobojen (pazite na uhajanje pomnilnika) ali dokler se aplikacija ne prekine (takrat mora operacijski sistem ponovno zahtevati pomnilnik).
Do dinamično dodeljenega pomnilnika lahko dostopate samo prek kazalca. Dereferenciranje kazalca je počasnejše od neposrednega dostopa do spremenljivke.
Ker je kopica velik rezervoar pomnilnika, se uporablja za dodeljevanje velikih ali razredov.
Sklad klicev
Sklad klicev(ali preprosto " kup") ima veliko več zanimiva vloga. Klicni sklad sledi vsem aktivnim funkcijam (tistim, ki so bile poklicane, vendar še niso dokončane) od začetka programa do trenutne točke izvajanja in obravnava dodelitev vseh funkcijskih parametrov in lokalnih spremenljivk.
Klicni sklad je implementiran kot podatkovna struktura Stack. Preden torej govorimo o tem, kako deluje sklad klicev, moramo razumeti, kaj je "sklad" kot podatkovna struktura.
Struktura podatkov sklada
Struktura podatkov je mehanizem v programiranju za organiziranje podatkov, tako da jih je mogoče učinkovito uporabljati. Videli ste že več vrst podatkovnih struktur, kot so polja in strukture. Zagotavljajo mehanizme za učinkovito shranjevanje in dostop do podatkov. Obstaja veliko več dodatnih podatkovnih struktur, ki se pogosto uporabljajo v programiranju, od katerih so nekatere implementirane v standardni knjižnici C++, in Stack je ena izmed njih.
Razmislite o kupu krožnikov na mizi. Ker je vsak krožnik težak in so zloženi (drug na drugega), lahko naredite samo eno od naslednjih treh stvari:
Poglejte površino zgornje plošče.
Vzemite zgornji krožnik iz kupa (tako razkrijete naslednjega, ki je spodaj - če sploh obstaja).
Postavite nov krožnik na vrh kupa (skrijte najvišji krožnik spodaj, če je bil).
V računalniškem programiranju je sklad vsebniku podobna podatkovna struktura, ki vsebuje več spremenljivk (podobno kot polje). Medtem ko vam matrika omogoča dostop in spreminjanje elementov v poljubnem vrstnem redu (imenovano " naključni dostop«), potem je sklad bolj omejen. Operacije, ki jih je mogoče izvesti na skladu, ustrezajo trem zgoraj naštetim. Na skladu lahko:
Poglejte zgornji element v skladu (uporabite funkcijo vrh() oz pokukati() ).
Izvlecite zgornji element svežnja (uporabite funkcijo pop() ).
Dodajte nov element na vrh sklada (uporabite funkcijo potiskati() ).
Stack je struktura podobna LIFO(Last In, First Out - zadnji pride, prvi odide). Zadnji element, potisnjen na vrh sklada, bo prvi izstopil iz sklada. Če postavite nov krožnik na vrh drugih krožnikov, bo to prvi, ki ga boste vzeli. Ko se elementi potisnejo na sklad, se sklad poveča; ko se elementi odstranijo iz sklada, se sklad skrči.
Na primer, razmislite o kratkem zaporedju, ki prikazuje, kako deluje dodajanje in odstranjevanje v skladu:
Kup: prazen
Potisnite 1
Sklad: 1
Potisnite 2
Sklad: 1 2
Potisnite 3
Sklad: 1 2 3
Potisnite 4
Sklad: 1 2 3 4
Pop
Sklad: 1 2 3
Pop
Sklad: 1 2
Pop
Sklad: 1
Kup krožnikov je precej dobra analogija za to, kako deluje kup, vendar obstaja boljša analogija. Na primer, razmislite o več nabiralnikih, ki se nahajajo drug nad drugim. Vsak nabiralnik lahko vsebuje le en predmet in vsi nabiralniki so na začetku prazni. Poleg tega je vsak nabiralnik prikovan na nabiralnik pod njim, tako da števila nabiralnikov ni mogoče spreminjati. Če ne moremo spremeniti števila nabiralnikov, kako potem doseči vedenje, podobno skladu?
Najprej z nalepko označimo, kje je najnižji prazen nabiralnik. Na začetku bo to prvi nabiralnik, ki je v nadstropju. Ko dodamo predmet v naš kup nabiralnikov, bomo ta predmet postavili v nabiralnik, na katerem bo nalepka (tj. prvi prazen nabiralnik na tleh), nato pa nalepko premaknili en nabiralnik višje. Ko izločimo predmet iz sklada, premaknemo nalepko za en nabiralnik navzdol in odstranimo predmet iz nabiralnika. Vse pod oznako je na kupu. Vse, kar je v škatli z nalepko in zgoraj, ni v skladu.
Segment sklada klicev
Segment sklada klicev vsebuje pomnilnik, ki se uporablja za sklad klicev. Ko se aplikacija zažene, je funkcija main() potisnjena na sklad klicev operacijski sistem. Nato se program začne z izvajanjem.
Ko program naleti na klic funkcije, je funkcija potisnjena na sklad klicev. Ko funkcija zaključi izvajanje, se odstrani iz sklada klicev. Na ta način lahko z ogledom funkcij, dodanih v sklad, vidimo vse funkcije, ki so bile priklicane do trenutne točke izvajanja.
Analogija našega nabiralnika je v resnici način delovanja sklada klicev. Klicni sklad ima fiksno število pomnilniških naslovov (fiksna velikost). Nabiralniki so pomnilniški naslovi, "predmeti", ki jih dodamo in prikažemo na kupu, pa se kličejo okvirji(ali drugače " osebje") sklad. Okvir sklada spremlja vse podatke, povezane z enim klicem funkcije. "Nalepka" je register (majhen del pomnilnika v CPE), ki je kazalec sklada. Kazalec sklada spremlja, kje se nahaja vrh sklada klicev.
Edina razlika med dejanskim skladom klicev in našim hipotetičnim skladom nabiralnika je v tem, da ko odstranimo element iz sklada klicev, nam ni treba izprazniti pomnilnika (tj. izstreliti celotne vsebine nabiralnika). Lahko pustimo ta spomin za naslednji element, ki ga bo prepisal. Ker bo kazalec sklada pod tem pomnilniškim naslovom, potem, kot že vemo, ta pomnilniška lokacija ne bo na skladu.
Sklad klicev v praksi
Oglejmo si podrobneje, kako deluje sklad klicev. Spodaj je zaporedje korakov, izvedenih ob klicu funkcije:
Program naleti na klic funkcije.
Okvir sklada je ustvarjen in postavljen na sklad, sestavljen je iz:
Naslov ukaza, ki se nahaja za klicem funkcije (tako imenovani " povratni naslov"). Tako si procesor zapomni, kam naj se vrne po izvedbi funkcije.
Argumenti funkcije.
Pomnilnik za lokalne spremenljivke.
Shranjene kopije vseh registrov, spremenjenih s funkcijo, ki jih bo treba obnoviti, ko funkcija zaključi svoje izvajanje.
Procesor se premakne na začetno točko funkcije.
Navodila znotraj funkcije se začnejo izvajati.
Ko je funkcija končana, se izvedejo naslednji koraki:
Registri se obnovijo iz sklada klicev.
Okvir sklada se odstrani iz sklada. Sprosti se pomnilnik vseh lokalnih spremenljivk in argumentov.
Vrnjena vrednost je obdelana.
CPE nadaljuje z izvajanjem kode (na podlagi povratnega naslova).
Povratne vrednosti je mogoče obdelati na različne načine, odvisno od arhitekture računalnika. Nekatere arhitekture menijo, da je vrnjena vrednost del okvira sklada. Drugi uporabljajo registre procesorja.
Poznavanje vseh podrobnosti delovanja sklada klicev ni tako pomembno. Vendar razumevanje, da so funkcije dodane v sklad, ko so priklicane in odstranjene iz sklada, ko so priklicane, daje osnove, potrebne za razumevanje rekurzije, kot tudi nekatere druge koncepte, ki so uporabni v .
Primer sklada klicev
Razmislite o naslednjem delčku kode:
Klicni sklad tega programa izgleda takole:
boo() (vključno s parametrom b)
glavni ()
Stack Overflow
Sklad ima omejeno velikost in zato lahko vsebuje le omejeno količino informacij. V sistemu Windows je privzeta velikost sklada 1 MB. V nekaterih drugih sistemih Unix lahko ta velikost doseže 8 MB. Če poskuša program potisniti preveč informacij na sklad, bo povzročil prelivanje sklada. Stack Overflow(stack overflow) se zgodi, ko pride do zahteve po pomnilniku, ko je ves pomnilnik sklada že dodeljen - v tem primeru se bodo vse zahteve za dodelitev začele pretakati (prelivati) v druge odseke pomnilnika.
Prelivanje sklada je tudi rezultat dodajanja veliko število tudi spremenljivke na skladu in/ali ustvarjanje velika količina ugnezdene klice funkcij (na primer, kjer funkcija A pokliče funkcijo B, ta nato pokliče funkcijo C, ki pokliče funkcijo D itd. itd.). Prelivanje sklada običajno povzroči zrušitev programa.
Na primer:
int main() (int stack; return 0; )
int main() int sklad [100000000]; vrni 0; |
Ta program poskuša v sklad klicev dodati ogromno matriko. Ker velikost sklada ni dovolj za obdelavo takšne matrike, gre njen dodatek v druge dele pomnilnika, ki jih program ne more uporabiti. Zato dobimo neuspeh.
Tu je še en program, ki bo povzročil prekoračitev sklada, vendar iz drugega razloga:
void boo() (boo(); ) int main() (boo(); return 0; )