1. fejezet - Programozási modellek

Tartalom

Szekvenciális programozás
Párhuzamos programozás
Szálak kommunikációja

A programozási modellek többek között a különböző teljesítményfokozó lehetőségek kiaknázásáról szólnak. A számítástechnika történetének kezdetén a processzor alacsony számítási kapacitást képviselt. A kapacitás mértéke a FLOPS[1] (floating point operations per second - lebegőpontos műveletek száma másodpercenként), melynek segítségével jellemezhetjük a műveletvégző sebességet.

Az első általános célú teljesen elektronikus számítógép az ENIAC volt, melyet 1946-ban helyeztek üzembe, és a hidrogénbombához szükséges számításokat futtatták rajta. Egy másodperc alatt képes volt 5000 összeadást, 357 szorzást vagy 38 osztást elvégezni.

A Cray Jaguar szuperszámítógép 2009-ben az 1,75 petaFLOPS[2] számítási sebességével az egyik legjelentősebb számítási erőt képviseli. Az IBM 2011-re ígéri a 20 petaFLOPS sebességű Sequoia projektjének befejezését. A jóslatok szerint 2019-re elérjük az 1 exaFLOPS sebességet is. Csak egy apróság – a 2 hetes időjárásjelentés kiszámításához szükséges 1 zettaFLOPS sebességet ez még mindig nem éri el (ennek jósolt időpontja 2030 körülre van becsülve).

A másik lehetséges mérőszáma a processzoroknak az IPS (instructions per second - műveletek száma másodpercenként). Ez persze nem teljesen egyezik a lebegőpontos műveletek számával, de durva nagyságrendi becslésnek megfelel. Az IPS többszöröse a MIPS (millió művelet másodpercenként). Az AMD Athlon FX-57 (debütált 2005-ben) processzor 12 000 MIPS sebességű volt 2,8 GHz órajel mellett. Ezen évtől kezdve a processzorgyártók inkább a többmagos processzorok fejlesztésében gondolkodtak, ez tehát az egyik utolsó ilyen mérőszám, amely még a hagyományos egymagos processzorokat jellemezte.

Egy másik szemléletmódot adott Michael J. Flynn ([flynn]) 1966-ban. Véleménye szerint a számítógép-architektúrákat négy nagy csoportra oszthatjuk:

Szekvenciális programozás

A Neumann-elvek egyike kimondja, hogy a számítógépek műveletvégző rendszere szekvenciális sorrendben kell, hogy feldolgozza a programok utasításait. Az utasításokat a belső memóriában kell tárolni számkódok formájában, csakúgy, mint az adatokat. A processzor egységben egy program counter[3] (PC) egység tartja nyilván, hogy a memória mely pontján található a következő végrehajtandó utasítás. Annak végrehajtása után ezen PC egységben lévő szám módosításával (növelésével) léphetünk a következő utasításra.

Ezen modell szerint a programunk indítása a PC megfelelő beállításával értelmezhető. A programunk legelső végrehajtandó utasításának memóriabeli helyét a PC-be betöltve a processzor el tudja kezdeni az utasítás végrehajtását, a továbbiakban a PC-t megfelelően módosítva önállóan (beavatkozás nélkül) tud működni, a tőle telhető legnagyobb sebességgel végrehajtva a soron következő utasítást, majd lépni a következőre.

Ezt a módszert a mai egymagos processzorok a végletekig optimalizálták. A pipeline technikával, a cache memóriával a következő utasítások végrehajtását próbálják a lehető legjobban előkészíteni, hogy a processzor minél gyorsabban végezhessen azzal. A feltételes elágazásokat egy speciális jósló áramkör elemzi, próbálja megsejteni, melyik ágon folytatódik tovább a program futása. Az órajel végső határokig emelésével és ezen rendkívül fejlett technikákkal az egymagos processzorok teljesítménye hihetetlen magasságokba emelkedett.

De úgy tűnik, ez a határ már nehezen bővíthető. A programozóknak azonban ez a legegyszerűbb, legkevesebb problémát magában foglaló modell, ezért létjogosultsága nem kérdőjelezhető meg. Az algoritmusok és adatszerkezetek tárgy keretein belül megismert módszerek is ezen modellen alapulnak, a hatékonysági jellemzők (legkisebb, átlagos, legnagyobb futási idő, memóriaszükséglet stb.) erre vannak kiszámítva.

Itt értelmezhető először a szál (thread) fogalma, mely azonban itt nem hangsúlyos fogalom. A szál fogalmának megértéséhez képzeljünk el egy vékony zsinórt, melyre gyöngyöket fűzünk fel. A gyöngyök a programunk utasításait szimbolizálják, a szálra fűzés pedig a processzor feldolgozási módszerét jellemzi. A processzor feladata a program futtatása, vagyis az utasítások végrehajtása. A szálra fűzés miatt egy időben csak egy utasítást tud leválasztani, feldolgozni (a következőt), majd ezután tud a következőre lépni. A processzor végez egy program futtatásával, ha a szál utolsó utasítását is végrehajtotta.

Ezen modellhez tartozó algoritmusleírási módszerek közé tartozik a folyamatábra, a struktorgramm, a leíró nyelv. Az imperatív programozási nyelvek mindegyike ezt a modellt támogatja. A C, C++, Pascal, Delphi, Java, C# és egyéb nyelvek alapértelmezett futási modellje a szekvenciális modell.

A modernebb programozási nyelvek támogatást tartalmaznak a többszálú (párhuzamos) modellű programok fejlesztéséhez, és némelyikük az elosztott modellre jellemző kommunikációs problémák kezeléséhez is. De ezek jellemzően technikai támogatások, vagyis függvényeket, eljárásokat (OOP környezetben osztályokat) jelentenek. Ezek mellett a programozóknak nagyon is ismerni kell a modellek működését, a felmerülő problémákat, azok szokásos megoldási módját ugyanúgy, mint ahogy a szekvenciális modellben programozóktól elvárjuk a szekvenciális algoritmusok ismeretét.

Párhuzamos programozás

A párhuzamos programozás során a programunk hagyományos szekvenciális programként indul el, az utasításai felfűzhetők egy szálra, mint a gyöngyök. Egy speciális függvényhívással azonban a programban megjelöl egy másik belépési pontot, majd utasítja a processzort, hogy kezdjen neki ezen szál végrehajtásának is.

Az egymagos processzor természetesen erre fizikailag képtelen. Egy időben csak egy utasítással képes foglalkozni. A két szál párhuzamos futtatását úgy tudja megvalósítani, ha adott pontokon az egyik szál feldolgozását megszakítva átlép a másik szál feldolgozására, majd újra vissza az elsőre. Az adott pontok meghatározása külön probléma, de a prioritások segítségével ez egyszerűen megérthető: a szálakhoz prioritásokat rendelhetünk, melyek azok fontosságát jelölik. A magasabb prioritású szál futását fontosabbnak jelöljük, így a vezérlés erre a szálra gyakrabban kerül[4]. Az egyiknek tehát több időszelet jut, mint a másiknak. Az idő lejártával a processzor befagyasztja az aktuális szál végrehajtását, majd áttér a másikra. Az 1.1. ábra bemutatja, hogyan értelmezhető ez az adott szál szemszögéből.

1.1. ábra. Szálváltások

Jelen ponton már fontos tisztázni két fogalom pontos jelentését. A processz vagy folyamat egy olyan környezetet takar, amely egy program indítása során keletkezik, és a program futásának időtartama alatt végig létezik, annak teljes életciklusát végigkísérve. Egy ilyen processz nemcsak a futó kódot tartalmazza, hanem annak leírását is, hogy a kódot milyen felhasználó nevében, milyen jogosultsággal indítottuk el. Az operációs rendszer a program indulásakor memóriát is foglal nemcsak a kódnak, de az adatoknak is, amelyeket szintén a processzhez rendel hozzá. Ennek következtében az allokált memória akkor törlődhet csak, amikor maga a processz befejeződik, vagyis a teljes program leáll.

A szál (thread) a processz egyik építőeleme. A szál a kód egy szeletének utasítássorozata (1.2. ábra), amelynek állapota lehet futó (running), leállt (finished) vagy várakozó (standby). Egyéb adminisztratív, rövid ideig jellemző állapotok is léteznek (pl. futáskész [ready]), de ezek most számunkra nem annyira érdekesek.

1.2. ábra. Processz

Az alkalmazás indításakor az operációs rendszer létrehozza a processzt, majd betölti a kódot, létrehoz egy szálat, a szál kezdőpontját a Main függvény kezdőpontjára állítja[5], és a szálat indítja (running state).

A futó szál újabb szálakat hozhat létre, megjelölve az adott szálhoz tartozó kód indulási pontját. Ez legegyszerűbben úgy kivitelezhető, ha a szál létrehozásakor megnevezzük egy függvényünket, melynek belépési pontja lesz a szál kezdőpontja (ez gyakorlatilag megegyezik az operációs rendszer módszerével, ami a Main függvényünk belépési pontját veszi kiindulási pontnak).

Egy szál futása befejeződik, ha a szálhoz rendelt utasítássorozat véget ér, vagyis ha a szálhoz rendelt függvény befejezi a futását. Ez bekövetkezhet oly módon is, hogy a függvényben egy kivétel (exception) váltódik ki. A kezeletlen kivétel terminálja az adott szálat, de más szálakra a hatása nem terjed át[6]. Ez azt jelenti, hogy nem kell aggódnunk amiatt, hogy egy elindított szálban keletkező kivétel az indító szál leállítását is okozhatja. Másrészt azt is jelenti, hogy nem nagyon van módunk ahhoz az információhoz hozzájutni, hogy az általunk indított szálban kivétel keletkezett-e vagy sem.

Szálak kommunikációja

A szálak a processz belsejébe zárt építőelemek, így hozzáférnek a processz egy másik építőeleméhez: a processzhez tartozó, adatokat tároló memóriaterülethez. Ezen a memóriaterületen osztoznak egymással. Ez egyúttal a párhuzamos programozás előnye és hátránya is egyben.

A szálak között mindig szükséges némi kommunikáció, adatcsere. Ezt pontosan a közös memóriaterület segítségével lehet áthidalni – az egyik szál elhelyezi a küldeni kívánt adatokat egy előre megbeszélt memóriaterületre (változó), majd a másik szál egyszerűen kiolvassa onnan azt. A válaszát is hasonlóan tudja visszaküldeni – ő is elhelyezi egy közös változóban, majd az első szál onnan ki tudja azt olvasni (1.3. ábra).

1.3. ábra. A szálak a közös memórián osztoznak

Ez a módszer egyúttal két dolgot is jelent. Az egyik olvasata ezeknek a tényeknek az, hogy az indítás során a függvénynek paramétert nem feltétlenül egyszerű átadni, helyette szokásos az átadandó értékeket az indítás előtt elhelyezni a közös változókban. A másik olvasata szerint a függvény nem rendelkezik visszatérési értékkel (return), helyette a visszaadandó értéket szintén egy közös változóba helyezi el, majd leáll.

Természetesen a való életben ez egy kicsit bonyolultabb. Mindenképpen szükség van egyfajta mechanizmusra, amelynek segítségével a szálak el tudják dönteni, hogy az adott változóba a keresett érték elhelyezésre került-e már, vagy sem. Ez nem a függvény indulásakor kérdéses elsősorban, hiszen az értékeket már indítás előtt el kell helyezni. Sokkal fontosabb annak vizsgálata során, hogy a függvény által generált válaszérték már bekerült-e a változóba, vagy sem. Erre a szóban forgó változó egyedül ritkán alkalmas, mivel a változókban minden időpillanatban található valamilyen érték, így nehéz megkülönböztetni egymástól azt a szituációt, amikor a változóban valamilyen korábbi érték van még mindig, vagy már az új, generált érték.

Utóbbit technikailag megoldhatnánk annak vizsgálatával, hogy az adott szál milyen státuszban van. Ha még mindig futó státuszú, akkor a visszatérési értéket még nem állította elő. Ha befejezett státuszú, akkor már beírta a visszatérési értékét. Ne felejtsük el azonban, hogy egy szál akkor is kerülhet befejezett állapotba, ha a szál leállását egy kezeletlen kivétel váltotta ki (mely esetben a visszatérési érték nem került be a szóban forgó változóba)! Ezért ez a módszer önmagában ritkán használható.



[1] néha flop/s-nak írják, gyakran azt hiszik, hogy a szó végi s a többes szám jele, így a flop kifejezés is bekerült a köztudatba (hibásan)

[2] peta = , exa = , zetta =

[3] egyes irodalmak instruction pointer-nek is nevezik

[4] vagy a processzor több utasítást dolgoz fel a váltás előtt, mint egy alacsonyabb prioritású szálról

[5] valójában a kezdőpont ennél korábbi pont, a Main indulása előtt még egy előkészítő, inicializáló kód is le szokott futni, de jelen esetben annak szerepe érdektelen

[6] a .NET környezetben ez a Thread osztályra jellemző viselkedés, a .NET v4-ben bevezetett Task osztály esetén már ez nem feltétlenül igaz