eredeti oldal címe

Dinamikus tárkezelés, adatstruktúrák

 

 

A téma bevezetéseként ismételjük át, hogy eddig milyen változókkal ismerkedtünk meg. Elsőként a globális változókkal, amelyet a program deklarációs részében irtunk le, s amelyeket a teljes programba, bárhol használhattunk. Aztán megismerkedtünk az eljárásokkal és függvényekkel. Ezeknek a belsejében is deklarálhattunk változókat, ezek voltak a lokális változók. A lokális változókat csak a deklarálás helyén, vagy az alatta lévő szinteken lehetett használni. Az ugyanazon szinten lévő rutinok nem látták egymás változóit, sőt a főprogram sem. Definiáltunk továbbá konstansokat és tipizált konstansokat. A Max értékek konstansok, a menüpontok nevei tipizált konstansok voltak. Az eddig megismert változókat és konstansokat statikusoknak nevezzük azért, mert fordításkor a helyük létrejön és a program futásának a végéig változatlanul meg is marad.

 

Nézzük ezután, hogyan helyezkednek el a pascal program esetén a memóriában a kódok és az adatok. Kezdetben, a 4.0 verzióig a turbo pascal *.comtárgyprogramokat készített, melynek rögzített betöltési helye volt a memóriában és mérete maximálisan egy lap, azaz 64 Kb lehetett. Ehhez kapcsolódott az adatszegmens maximum 64 Kb-tal és az Ovelay terület (azaz átlapolási terület az Overlay-be fordított Unit-ok részére, – mindig az aktuálisan szükséges kódot töltötte a rendszer a lemezről a RAM-ba). A kimarad memóriaterületen volt a Stack (a verem). Ezeket a korlátokat manapság jelentősen átléphetjük az új típusú memória kiosztás és kezelés révén. Első fontos dolog, hogy a Turbo Pascal 7.0 már nem *.com hanem *.exe állományokat készít, melyet a hagyományos memória bármely üres helyére betölthet, nincs rögzített helye. Méretére nincs korlátozás, hacsak az nem, hogy a szövegszerkesztő maximálisan 64 Kb-os szöveget tud kezelni. Ezen viszont az tud segíteni, hogy saját Unit-okat írhatunk, melynek darabszáma nincs korlátozva. Így az összeszerkesztett exe állomány akár több-száz Kb is lehet. Itt említenénk meg, hogy a pascal rendszer két IDE-t tartalmaz a DOS-os környezetre. Ezek: a Turbo és a Tpx. A Turbo úgy dolgozik, hogy a fordítást alapértelmezésben a RAM-ba készíti és a segédállományokat is itt hozza létre. Nagyméretű programok esetén ez akadály lehet, hiszen DOS-ban csak maximum 10 lap (640 Kb) áll rendelkezésre, s ha mindent a memóriában oldunk meg, hamar elfogyhat a standard memória. A Tpx viszont a fordítást mindig lemezre végzi és az ideiglenes állományait is itt hozza létre. Ezzel tehát nagyobb programokat lehet irni. Ezért használtuk eleve ezt a fejlesztéseink alkalmával. A mai rendszerben a memória kiosztása a következő (az alacsony címtől kezdve a magasak felé haladva):

–         *.exe állomány,

–         Unit-ok,

–         tipizált konstansok (nem tartoznak az adatszegmenshez),

–         globális (statikus) változók – maximum 64 Kb -,

–         Stack – maximum 64 Kb -,

–         Overlay – ha van,

–         Heap – a memória tetejéig.

 

Vizsgáljuk meg egy kicsit jobban a Stack-et, miért szükséges és hogyan működik. A program futása közben gyakran előfordul, hogy a programnak alprogramhoz kell fordulnia, amely gyakorlatilag egy objekt helyre való ugrást jelent. Az alprogram végrehajtása után – alapértelmezésben – a programot a hívás helye utáni memóriacímen kell folytatni. A gép úgy tud visszatalálni, hogy minden alprogramhíváskor lementi a hívás helyét a memóriába. Természetesen alprogramból újraalprogramba ugorhatunk, így az eredeti helytől már két ugrásra vagyunk. A visszajutás először a legutóbbi, aztán az eggyel korábbi cím ismerete alapján lehetséges. Az adatokat tehát úgy kell feljegyezni, hogy amit később irtunk le, arra hamarabb van szükség, amit legkorábban, arra pedig legutoljára. Ennek az adattárolásnak az angol neve: LIFO (Last Input, First Output), magyarul: amit utoljára behelyezünk, azt vesszük ki elsőnek. Ez úgy működik, mint egy verem (Stack), ami a verem alján van, azt csak akkor tudjuk kivenni a veremből, ha már mindent, amit utána tettünk bele, már kivettünk. Azt, hogy a verem véges méretű, könnyen leellenőrizhetjük a következő kis programmal.

 

Program Verem;

Procedure Ide;

Ide;

End;

Begin

Ide;

End.

 

Ez a program gyakorlatilag semmit nem tesz, csak azt, hogy egy rekurzív eljárást hív meg, (amely természetesen most nincs megfelelően kidolgozva, majd a későbbiekben látunk rekurzív hívásra értelmes és hasznos megoldásokat is). Mivel állandóan önmagát kell meghívnia, mindig menti a visszalépési címet, amely olyan gyorsan történik, hogy a program azonnal leáll Stack Overflow – verem túlcsordulás hibaüzenettel. Ha már itt tartunk, említsünk meg a másik nevezetes adattárolást és a hozzá kapcsolódó hardware megoldást. Ez pedig a FIFO (First Input, First Output), magyarul: amit először behelyezünk, azt vehetjük ki elsőnek. Ez egy csőhöz hasonlítható, amelybe torlódnak az adatok (mint például a hurkatöltőben a töltelék). Pl. (szemléletesen) a baloldalon kerülnek be a csőbe az adatok, és jobb oldalon kerülnek ki a csőből. A számítógépeink mindegyike rendelkezik ilyen elven működő tárral: ez CACHE memória. Ezt a memóriát a processzor és az operatív tár közé helyezik. Működési alapelve azon alapszik, hogy ha a processzornak adatra van szüksége a memóriából, akkor nagyon valószínű, hogy nem csak egy-két Byte-ra, hanem a memória közeli területéről többre is. Így nem csak a kívánt adatok indulnak el a gyorsító tárba, hanem több is, akár 512 kb -is, a CACHE méretétől függően. A CACHE -t ugyanis a processzor sokkal gyorsabban el tudja érni, mint a RAM-ot. Ezáltal a gép működése felgyorsul.