e-gradiva				Sistemi	Motorola	Omrežja
						SERŠ Maribor

Sklad

Ena od najpomembnejših podatkovnih struktur, ki se uporablja v mnogih programih, je sklad (angl. stack, pushdown stack). Sklad lahko realiziramo programsko ali aparaturno in zanimivo je, da so se CPE z aparaturno realizacijo sklada razširile šele po letu 1970. Ker predstavlja aparaturno realiziran sklad zelo dobro rešitev za nekatere pomembne probleme, si ga oglejmo nekoliko podrobneje.

Sklad je seznam podatkovnih elementov, običajno velikosti pomnilniških besed ali njihovih mnogokratnikov, z omejitvijo, da se elementi lahko dodajajo ali odvzemajo samo na enem koncu seznama. Ta konec se imenuje vrh sklada, drugi konec pa je dno sklada. Ime sklad prihaja iz podobnosti z na primer skladom drv, ki deluje na podoben način. Delovanje sklada lahko opišemo tudi kot "zadnji noter - prvi ven" in ga označujemo z LIFO (angl. Last In – First Out). Očitno postane zadnji element, ki smo ga postavili na sklad, prvi, ki ga vzamemo s sklada, ko se jemanje s sklada prične.

Potisni na sklad 25

Postavljanje elementa na sklad se običajno označuje z besedo "push", jemanje s sklada pas "pull" ali s "pop". Od tod seje tudi pri nas razširil žargon, v katerem govorimo o "potiskanju" elementov v sklad in o "vlečenju" elementov s sklada.

Prostor za shranjevanje elementov sklada je lahko glavni pomnilnik ali pa poseben pomnilnik v CPE. Druga rešitev je hitrejša, vendar se manj uporablja, ker je tak sklad po velikosti nujno. majhen. Pri skladu v pomnilniku pravimo. da računalnik "ima sklad", če ima ukaze za postavljanje in jemanje elementov iz sklada. V tem primeru je v CPE običajno poseben register, ki mu pravimo skladovni kazalec (angl. Stack Pointer) in ki vedno kaže na vrh sklada.

Sklad je lahko narejen tako, da se ob vstavljanju elementov širi proti nižjim ali proti višjim naslovom. Obe možnosti sta seveda enako dobri, čeprav je zanimivo, da danes večina računalnikov s skladom uporablja širjenje proti nižjim naslovom. V tem primeru se po vsaki vstavitvi v sklad vsebina skladovnega kazalca zmanjša, po vsakem jemanju iz sklada pa poveča. Primer tako delujočega sklada prikazuje slika .

Računalniki s skladom imajo v CPE vgrajeno logiko, ki običajno omogoča uporabljati sklad na naslednje tri načine:

1. Z ukazi tipov kot sta PUSH in PULL omogoča programerju, da v skladu s potrebami začasno shranjuje podatke v sklad in jih potem jemlje iz sklada.
2. Z ukazi za klic podprogramov, ki avtomatsko shranijo vsebino PC v sklad. Za vrnitev iz podprograma uporabi programer ukaz, ki vrne shranjeno vrednost iz sklada nazaj v PC.
3. Za shranjevanje registrov pri preklapljanju stanja CPE (npr. pri prekinitvah). Običajno se avtomatsko shrani PC, nekateri računalniki pa shranijo še druge registre. Za obnovitev prejšnjega stanja uporabi programer ukaz, ki vrne shranjene registre nazaj v CPE.

Vse naštete operacije lahko realiziramo tudi drugače, brez sklada. Vendar pa nobena od teh drugačnih realizacij, izjema so večkratni nabori registrov, ne reši problema rekurzivnih programov in vgnezdenih prekinitev (prekinitev med izvajanjem prekinitvenega servisnega programa) tako dobro kot ravno sklad. Ta namreč na preprost način zagotavlja, da sta vedno izpolnjena naslednja dva pogoja:

1. podatki se ob vsakem shranjevanju shranijo na drugo mesto - nevarnosti, da bi novi podatki uničili prejšnje, ni.
2. dostop do podatkov je preprost in hiter.

Reševanje rekurzivnih programov (to so tisti, ki kličejo sami sebe), prekinitev in podprogramov so tipični primeri uporabe sklada. Skladovni računalniki pa sklad uporabljajo kot čisto običajen način delovanja.