Rietuvė
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
Rietuvė arba dėklas (angl. stack) – duomenų struktūra, veikianti pagal LIFO principą: „paskutinis į maišą, pirmas iš maišo“ (angl. last in first out).[1] Kitaip tariant, iš rietuvės visada paimamas paskutinis į jį padėtas elementas, po to – priešpaskutinis ir t. t. Tai primena plytas, kraunamas vienas ant kitų stulpu.
Rietuvė paremia dvi pagrindines operacijas – push (padėti) ir pop (pasiimti).
Daugelis procesorių (ypač – CISC architektūros) paremia rietuvės veikimą aparatiškai. Tokiuose procesoriuose būna vienas ar keli už rietuvę atsakingi registrai (Intel 8080 – SP, Intel x86 – SP ir ESP), rodantys į rietuvės pabaigą. Procesoriaus vykdoma Pop operacija automatiškai perkelia į nurodytą registrą paskutinį rietuvės elementą ir sumažina rietuvės registro reikšmę. Push operacija rietuvės registro reikšmę padidina, bei nurodyto registro reikšmę perkelia į rietuvę. Asembleriu tokia operacijų seka gali būti aprašyta maždaug taip:
PUSH AX ; ; Atitiktų žemiau komentaruose esančią seką:
; ADD SP, 2 ; (Keičiama rietuvės rodyklė, AX dydis baitais)
; MOV WORD PTR [SP], AX ; Registro reikšmė perkeliama į rietuvę
POP AX ; ; Atitiktų žemiau komentaruose esančią seką:
; MOV AX, WORD PTR [SP] ; Rietuvės viršūnė perkeliama į registrą
; SUB SP, 2 ; (Keičiama reituvės rodyklė, AX dydis baitais)
Sukompiliuotame Intel x86 procesoriui skirtos programos kode yra rietuvės segmentas, kuriame ir laikomi į rietuvę dedami elementai.
Jei kodas generuojamas kompiliatoriaus, kviečiamų funkcijų argumentai programiniame kode dažniausiai perduodami per rietuvę (asembleriu programuojantis žmogus parametrus dažniausiai perduoda registruose).
Lokalūs kintamieji taip pat dažnai saugomi rietuvėje.
Pirmieji masiškai gaminti mikroprocesoriai turėjo vidinę rietuvinę atmintį. Pavyzdžiui, Intel 4004 turėjo trijų lygių paprogramių rietuvę grįžimo adresui atsiminti, kuri Intel 4040 buvo padidinta iki aštuonių lygių. Vidinė rietuvė patogi itin paprastuose kompiuteriuose, kur išorinės operatyvinės atmintinės gali ir nebūti. Intel 8080 vis dar turėjo retai naudotą galimybę prijungti net iki 64 Kb talpos atskirai adresuojamą rietuvės atmintį. Daugelyje šiuolaikinių kompiuterių rietuvė yra pagrindinės atmintinės dalis.
Rietuvę gali būti realizuojama tiesinio sąrašo pagrindu arba panaudojant masyvus. Masyvo pagalba realizuota rietuvė veikia sparčiau ir nereikalauja papildomos atminties sąrašo duomenims laikyti. Ji imituoja aparatinę realizaciją, turėdama rietuvės rodyklę atitinkantį sveikojo tipo kintamąjį, rodantį į pirmą laisvą elementą virš rietuvės viršūnes. Reikšmės padėjimo operacija užrašoma kaip
rietuvė[sp] = reikšmė sp = sp + 1
Reikšmės paėmimo operacija užrašoma kaip
sp = sp - 1 reikšmė = rietuvė[sp]
čia rietuvė – rietuvės turinį saugantis masyvas, sp – rietuvės rodyklės kintamais (pradinė vetrė lygi nuliui).
Tokia rietuvė paprastai turi ribotą iš anksto žinomą talpą (masyvo ilgį), nebent jį viršijus visas turinys būtų automatiškai kopijuojamas į kitą (didesnį) masyvą.
Nuorodas naudojančio tiesinio sąrašo pagrindu galima sukurti tik kompiuterio atminties ribojamą dinamiškai augančią rietuvę, tačiau duomenų laikymas joje mažiau efektyvus.
Kviečiant įvairių programos vietų bendrai naudojamą paskirties kodo fragmentą (pavyzdžiui, simbolio išvedimo į ekraną paprogramį), taip pat aptarnaujant pertraukimus, svarbu neužmiršti šiuo metu vykdomos komandų sekos adreso, kad užbaigus paprogramį būtų galima grįžti atgal. Grįžimo adresas beveik visada išsaugomas rietuvėje. Dažnai pasitaiko, jog vykdomas paprogramis savo ruožtu kviečia kitas paprogramius. Tuomet įsiminimo operacija kartojama. Baigiant paprogramį, rietuvės viršūnėje visada bus reikalingas grįžimo adresas, nes jis buvo ten padėtas paskutinis.
Rietuvėje gali būti išsaugomas ne tik ankstesnis vykdymo adresas, bet ir įvairi kita su ankstensniu vykdymu susijusi informacija (registrų bei vėliavėlių reikšmės, kai kada ir informacija apie įvedimo ar išvedimo įrenginių būseną). Kviečiant vieną paprogramį iš kito, būsena gali būti išsaugota daugelį kartų. Rietuvė tinka, nes paskutinė išsaugota būsena turi būti atstatyta pirmoji.
Jei paprogramiui reikia atminties lokaliems kintamiesiems saugoti, jai taip pat patogu išskirti rietuvę, pradedant nuo dabartinės rietuvės rodyklės reikšmės (rodyklė pastumiama tiek, jog rodytų į laisvą sritį greta užimtos atminties ribos). Rietuvė tam patogi todėl, jog paskutinis pradėtas vykdyti paprogramis pirmasis ir pabaigiamas (taigi paskutinė išskirta lokialių kintamųjų sritis pirmoji ir atlaisvinama). Rietuvėje išskirtai atminties sričiai naudoti daugelis procesorių turi komandas ne tik rietuvės viršūnei, bet ir žinomu atstumu žemiau jos esantiems duomenims pasiekti.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
