KURZUS: Számítógépes folyamatirányítás

MODUL: A számítógép

3.3. lecke: Kiemelkedő jelentőségű programozástechnikai elemek 1.

Cél: A lecke célja, hogy a tananyag felhasználója

  • megismerje a zsák (stack) fogalmát és használatát;
  • megismerje a sor (queue) fogalmát és használatát;
  • megismerje a szubrutin, a szubrutinhívás és a szubrutinból való visszatérés fogalmát, valamint a főprogram és a szubrutin viszonyát;
  • megismerje az automatikus szubrutinkezelés mechanizmusát;
  • megismerje az automatikus szubrutinkezelés és a stack kapcsolatát.

Követelmények: Ön akkor sajátította el megfelelően a tananyagot, ha

  • meg tudja fogalmazni, mit értünk a stack fogalmán, el tudja mondani a stack kezelésének mechanizmusát, tud példát mondani a stack alkalmazására;
  • meg tudja fogalmazni, mit értünk sor fogalmán, el tudja mondani a sor kezelésének mechanizmusát, tud példát mondani a sor alkalmazására;
  • el tudja mondani a szubrutin fogalmát, a főprogramhoz való viszonyát, tud példát mondani a szubrutin alkalmazására;
  • részletesen elemezni tudja a szubrutinkezelés mechanizmusát, a hívás - visszatérés folyamatát, be tudja mutatni a szubrutinkezelés és a stack kapcsolatát.

Időszükséglet: 1.5 óra

Kulcsfogalmak:

  • zsák (stack, LIFO),
  • stack-pointer,
  • sor (queue, FIFO),
  • szubrutin,
  • főprogram,
  • szubrutinhívás,
  • utasításszámláló (PC),
  • visszatérés (a szubrutinból).

Mindenek előtt, elnézést kérek a semmitmondó és nyögvenyelős címért. Sokat gondolkoztam rajta, nem találtam jobbat. De ez a kisebb baj. A nagyobb az, hogy ráadásul az érintett témák kiválogatása, minősítése és "összehozása" több mint vitatható, talán még átgondolatlannak, légbőlkapottnak, sőt, szakszerűtlennek is nevezhető. Ám ha a számítógépes folyamatirányítás sajátos igényeire és szempontjaira utalok, erős kohézió lép működésbe, amely szinte varázsütésre összekötözi a széthullani készülő kazlat, és még az is kiderülhet, hogy az egymástól távol eső témák együvé kerülése szükségszerű. A cím viszont ettől még rossz marad...

Korábbi tanulmányai során (vagy valahol másutt) bizonyára hallott már a stack-ről és a szubrutinról. Idézze fel a hallottakat és csak ezután kezdjen bele a szöveg olvasásába!

1. Fontos adatstruktúrák

A lecke áttanulmányozása után:

  • fogalmazza meg, mit értünk sor fogalmán, mondja el a sor kezelésének mechanizmusát, és keressen példát a sor alkalmazására;
  • fogalmazza meg a szubrutin fogalmát, a főprogramhoz való viszonyát, és keressen példát a szubrutin alkalmazására;
  • részletesen elemezze a szubrutinkezelés mechanizmusát, a hívás - visszatérés folyamatát, mutassa be a szubrutinkezelés és a stack kapcsolatát.

Két fontos adatstruktúráról kell szólnunk: a zsákról és a sorról.

A) A zsák (stack, LIFO) olyan soros elérésű adatstruktúra, melybe azonos hosszúságú adatelemek (rendszerint gépi szavak) írhatók be és amelyből az adatok a beírási sorrenddel ellentétes irányban olvashatók ki (vagyis a legutoljára beírt adat olvasható ki legelőször). Erre utal a LIFO (Last In First Out) elnevezés. A stack egy olyan falhoz hasonlítható, amelyet téglák egymásra rakásával emelünk és mindig a legfelső tégla levételével bontunk le. A stack aktuális tetejére (az éppen hozzáférhető elemre) egy dinamikus mutató, a stack-pointer (SP) mutat. Az újabb processzorok (sőt, a már nem is olyan újak is) szinte kivétel nélkül hardveresen támogatják a stack-kezelést, ami azt jelenti, hogy van olyan gépi utasításuk, amely lehetővé teszi a beírást (PUSH) és a kiolvasást (POP) anélkül, hogy a programozónak ismernie kéne a stack pillanatnyi helyzetét. Az ilyen processzorokban a stack-pointer egy speciális regiszter, melynek kezdeti értékét a programozó állítja be, a processzor pedig íráskor, illetve olvasáskor automatikusan aktualizálja. Maga a stack a memória tetszőleges területe és mérete potenciálisan korlátlan. Minthogy a stack egyébként közönséges memória, semmi sem akadályozza meg, hogy egy akármilyen, memóriára hivatkozó utasítással - lényegében illegálisan - mélyebb rétegeihez is hozzáférjünk. Ezt azonban igen körültekintően szabad csak megtenni, mert - finoman fogalmazva - súlyos mellékhatások léphetnek fel. Egyébként is, ha valaki stacket akar használni, azt kezelje szabályosan.

B) A sor (queue, FIFO) olyan soros elérésű adatstruktúra, melybe azonos hosszúságú adatelemek írhatók be és amelyből az adatok a beírási sorrenddel megegyező irányban olvashatók ki (vagyis a legkorábban beírt adat olvasható ki legelőször). Erre utal a FIFO (First In First Out) elnevezés. A sor egy olyan falhoz hasonlítható, amelyet téglák egymásra rakásával emelünk és mindig a legalsó tégla kihúzásával bontunk le (remélve, hogy nem omlik össze). De inkább hasonlítható egy alagúthoz, melybe először a mozdony lép be és a végén is először a mozdony jön ki. A FIFO két pointerrel és egy, a méretét korlátozó ütközővel kezelhető (mindegyik egy-egy címet tartalmaz). Az un. beíró pointer a legutóbb beírt (legújabb) elemre, az un. kiolvasó pointer pedig az aktuálisan kiolvasott elemre mutat (1. ábra).

FIFO
1. ábra

Ha a kiolvasó pointer eléri a beíró pointert az azt jelenti, hogy a FIFO kiürült; ilyenkor mindkettő a FIFO elejére ugrik. Üres FIFO-ból nem lehet olvasni. Ha a beíró pointer eléri az ütközőt, további beírás nem lehetséges. A felütközés nem jelenti azt, hogy a sor tele van, csak azt, hogy tovább nem nyújtható. Látható, hogy a FIFO kezelése meglehetősen bonyolult, talán ez az oka annak, hogy a processzorok utasítás-szinten nem valósítják meg, így azt programmal kell megoldani.

Mindkét adatsruktúra rendkívül fontos. A stack a szubrutinhívásnál, a megszakításkezelésnél, és a real-time monitor task-átkapcsolási műveleteinél, a sor pedig a processzor és a perifériák működésének aszinkronitását kiegyenlítő adatpufferek kialakításánál kap főszerepet.

2. A szubrutinok

A programokban gyakran előfordulnak viszonylag önálló, jól körülhatárolható funkciójú, többször ismétlődő utasítás-sorozatok. Ezeket ki lehet emelni a programtörzsből, elegendő egy példányban, külön elhelyezni a memóriában, a programokból pedig szükség esetén, adott ponton csak hivatkozni kell rájuk. Az ilyen programrészeket szubrutinnak, a rájuk való hivatkozást (aktivizálásukat) pedig szubrutinhívásnak nevezzük. A szubrutin helyfoglalás szempontjából nem, csak időben ékelődik a hívó programba, az un. főprogramba (2. ábra).

Egyszintű szubrutinhívás
2. ábra

Híváskor a szubrutint el kell látni az aktuális adatokkal (bemenő paraméterek), ezeket a szubrutin feldolgozza, előállítja az eredményeket (kimenő paraméterek), melyeket visszatéréskor átad a főprogramnak. Máskor, más helyen, más adatokkal ugyanez a folyamat ismétlődik.

A szubrutinhívás formailag egy vezérlésátadás a szubrutin elejére (kezdőcímére, belépési pontjára). Ez megoldható lenne egy közönséges ugró utasítással (JUMP). A szubrutin végén vissza kell térni a hívó programba, ám nem mindig ugyanarra a helyre, hanem mindig máshová: a mindenkori hívás helyét követő első utasításra. Erre már nem alkalmas az egyszerű ugró utasítás, mert annak immediate operandusa van, ami nem változtatható. A 2. ábra mutatja, hogy az A helyről való híváskor (A+1)-re, míg a B helyről való híváskor (B+1)-re kell az R pontról visszatérni. Ugró utasítás címrészeként nem adható meg egyszer (A+1), egyszer meg (B+1). A szubrutinnak (pontosabban: a processzornak) valahogyan tudnia kellene a mindig más visszatérési címet. A híváskor ez a cím már ismert, hiszen az a főprogram soron következő utasításának a címe és az utasításszámlálóban (PC) pontosan ez van. Viszont a PC tartalma a híváskor meg fog változni, mert a szubrutin kezdőcíme fog beleíródni (éppen ez jelenti a hívást). Ha tehát a hívással egyidejűleg a processzor valahová elmentheti a PC eredeti tartalmát, majd a szubrutin végén, az R ponton azt előveheti, továbbá, ha van egy olyan utasítás, amely ugrás-jellegű, de nem rögzített operandusú, akkor a visszatérés meg van oldva.

Nos, a processzornak van olyan utasítása, amely ugrás előtt automatikusan elmenti a PC tartalmát. Ez a szubrutinhívó utasítás, a CALL, amely egy közönséges ugrásnak és az említett PC-mentési műveletnek az egyesítése. És van olyan utasítás is, a RETURN (röviden: RET), amely a szubrutin végén az elmentett PC-tartalmat veszi elő és azt tekinti ugrási címnek. A RET tehát szintén egy ugrás, de olyan, melynek implicit operandusa van. Már csak az a kérdés, hogy a CALL hová menti el, és a RET honnan veszi elő a visszatérés helyét meghatározó PC-tartalmat.

A korai processzorok idején még nem ismerték az automatikusan kezelt stacket. A processzorban kialakítottak egy regisztert (un. csatoló regiszter), ebbe mentette el a CALL a PC-t és a RET innen vette elő. Ám a szoftveresek szerettek volna szubrutinból is hívni szubrutint (több szintes, egymásba ágyazott szubrutinhívás, 3. ábra).

Kétszintű szubrutinhívás
3. ábra

Ehhez nem elég egy csatoló regiszter, mert az a 2. szintű szubrutin hívásakor felülíródik az 1. szintű szubrutin PC-értékével. Így a 2. szintről az 1. szintre való visszatérés még biztosított, de az 1. szintről a főprogramba már nem. Akkor kell még egy csatoló regiszter, de akkor kell egy jelzőbit is, melynek 0-értéke jelzi, hogy a főprogramból (0. szint) történt a hívás és az első csatolóregisztert kell használni, 1-értéke pedig azt, hogy az 1. szintről történt a hívás, tehát a második csatolóregisztert kell használni (mert az első már foglalt). A 2. szintről való visszatéréskor a második regiszter tartalma felhasználódik, a jelzőbit pedig 1-ről 0-ra vált, jelezve, hogy most már a 0. szintre kell visszatérni, vagyis az első csatolóregiszter tartalmát kell címnek tekinteni. A jelzőbit tehát egy dinamikus pointer, amely az éppen használandó csatolóregiszterre mutat. Vegyük észre, hogy ez az együttes már egy 2-hosszúságú stack egy egybites pointerrel.

A mai processzorokban már nincsenek csatolóregiszterek, van viszont hasonlóan működő, automatikusan kezelt, memóriába ágyazott stack. A CALL utasítás a stack aktuális tetejére menti a PC-t, a RET pedig onnan veszi elő. Magasabb szintű híváskor az előző cím fölé íródik az újabb és így tovább. Ily módon akárhány szintes, egymásba ágyazott hívás-lánc megvalósítható, mert - a stack lényegéből adódóan - visszatéréskor az egymásra rétegzett címek éppen fordított sorrendben használódnak fel, így a visszatérés Ariadné-fonala sehol sem szakad el.

Lépjen ki a tananyagból!  Gondolja át a lecke tartalmát, rekonstruálja a szerkezetét! Vegyen elő egy lapot és írja le a lecke vázlatát! Ne sajnálja az erre fordított időt! Ha gondosan megcsinálja, már majdnem tudja is az anyagot.

Önellenőrző kérdések

1. Mondja el a stack fogalmát, szemléltesse a "téglafal"-hasonlattal és mondjon példát használatára!

2. Mondja el a sor fogalmát, szemléltesse az "alagút"-hasonlattal és mondjon példát használatára.

3. Igaz-e, hogy szubrutinhívás csak olyan gépen valósítható meg, melyben van stack, vagy valamilyen, legalább egy cím tárolására alkalmas automatikusan kezelt LIFO-jellegű tároló?
Igen
Nem

4. Rajzolja fel egy két-szintes szubrutinhívás sémáját és részletesen kövesse végig a vezérlésátadások mechanizmusát!

5. Gondolkodtató kérdések - nem kötelező anyag.
Meghívhatja-e egy szubrutin saját magát? Mi lesz ennek a következménye? Lehet-e ennek egyáltalán értelme? Értelemtől függetlenül, mi történik ilyenkor? Hogyan lehetne megállítani a végtelen rekurziót és elindítani a visszatérési folyamatot?