Párhuzamos programozás

Párhuzamos programozás


A jegyzet használata

A jegyzet használata | Tartalomjegyzék | Tárgymutató

Vissza

1

A jegyzet használata Mozgás a jegyzetben A jegyzetben való mozgáshoz a Windows és az Acrobat Reader megszokott elemeit és módszereit használhatjuk. Minden lap felső és alsó sorában egy navigációs sor található, itt a megfelelő fülre kattintva ugorhatunk a használati útmutatóra, a tartalomjegyzékre és a tárgymutatóra. A és a nyilakkal az előző és a következő oldalra léphetünk át, míg a Vissza mező az utoljára megnézett oldalra visz vissza bennünket.

A könyvjelző, a tartalomjegyzék és a tárgymutató használata Pozícionálás a könyvjelzőablak segítségével A bal oldali könyvjelző ablakban tartalomjegyzékfa látható, amelynek bejegyzéseire kattintva az adott fejezet/alfejezet első oldalára jutunk. Éppen aktuális pozíciónkat a tartalomjegyzékfában kiemelt bejegyzés mutatja.

Ugrás megadott helyre a tartalomjegyzék segítségével Kattintsunk a tartalomjegyzék megfelelő pontjára, ezzel az adott fejezet/ alfejezet első oldalára jutunk.

A tárgymutató használata, keresés a szövegben Válasszuk ki a megfelelő betűt a tárgymutató lap tetején, majd miután megtaláltuk a keresett bejegyzést, kattintsunk a hozzá tartozó oldalszámok közül a megfelelőre. A további előfordulások megtekintéséhez használjuk a Vissza mezőt. A dokumentumban való kereséshez használjuk megszokott módon a Szerkesztés menü keresés pontját. Az Acrobat Reader az adott pozíciótól kezdve keres a szövegben.


Vissza

1


Párhuzamos programozás A jegyzet használata | Tartalomjegyzék | Tárgymutató

Tartalomjegyzék Vissza

2

Tartalomjegyzék A jegyzet használata ........................................................................ 1 Szekvenciális és párhuzamos algoritmusok ..................................... 5 Az algoritmusok hatékonyságának mérése ............................................. 5 Egy párhuzamos gépmodell .................................................................. 7 Rendezések és rekurzió ......................................................................... 8 A gyorsrendezés .............................................................................. 8 Rekurzív algoritmusok párhuzamosítása ....................................... 12 Dinamikus programozás ..................................................................... 13 Mohó algoritmusok ............................................................................ 13 Párhuzamos technikák, párhuzamos algoritmusok .............................. 14 A Gauss-elimináció ....................................................................... 15 Polinom-faktorizáció .................................................................... 17 PRAM-algoritmusok .......................................................................... 21 Párhuzamos hardverarchitektúrák ................................................ A párhuzamos architektúrák fejlődésének története ............................ A párhuzamos architektúrák osztályozási lehetőségei ........................... Csoportosítás az összekapcsolás jellege szerint ............................... Csoportosítás a processzorok felépítése szerint .............................. Csoportosítás a memóriamodulok felépítése szerint ...................... A Flynn-féle osztályozás ...................................................................... Az SISD gépcsalád ........................................................................ A pipeline-technika és a vektorgépek ............................................ Az SIMD-tömbprocesszor gépcsalád ............................................. Az MIMD gépcsalád .................................................................... Az MPP gépcsalád és a CRAY T3E szuperszámítógép ................... A processzorok közötti lehetséges hálózatok ........................................

24 24 26 28 28 29 29 30 31 33 38 41 42

A párhuzamos programozás fogalma ............................................ A szekvenciális programozás jellemzői ................................................. Elszakadunk a szekvenciális programozástól… .................................... Részben rendezettség a párhuzamos programozásban ..........................

45 45 47 50


Vissza

2



3

A párhuzamos programozás motivációja ............................................. Egy beágyazott rendszer szimulációja szekvenciális környezetben .. Problémák a párhuzamos programozásban ........................................ A helyfoglalási probléma ............................................................... A Pascal-FC alapjai .............................................................................

52 54 58 58 62

Folyamatreprezentáció és életciklus .............................................. Folyamatmodellek párhuzamos programozási nyelvekben ................... A Pascal-FC nyelv folyamatmodellje ................................................... Folyamatállapotok és -átmenetek ........................................................ A folyamatok menedzselése és a futtatórendszer .................................. Programfuttatás a Pascal-FC-ben ................................................. A folyamatok ütemezése ..................................................................... Ütemezés valós idejű rendszerekben .............................................. Időkezelés a Pascal-FC nyelvben .........................................................

63 63 67 70 72 74 75 77 79

Folyamatok kölcsönhatása ............................................................ 83 Szinkronizációs problémák megoldása hagyományos nyelvi eszközökkel ........................................................................................ 84 A termelő-fogyasztó probléma ...................................................... 84 A díszkert probléma ...................................................................... 86 Az író-olvasó probléma ................................................................. 96 Összefoglalás ................................................................................. 96 Párhuzamos programok helyessége ..................................................... 97 Biztonságosság .............................................................................. 97 Elevenség ...................................................................................... 97 A deadlock (holtpont) ................................................................... 98 A holtpont legyőzése ..................................................................... 99 Az étkező filozófusok problémája ............................................... 103 A csatornamodell ........................................................................ Folyamatok közötti kommunikáció üzenetváltással ........................... Szinkronizáció ............................................................................ Elnevezés .................................................................................... Kommunikáció csatorna segítségével ...........................................


Vissza

107 107 107 108 109

3



A Pascal-FC csatornamodellje ........................................................... Egy prímszámgenerátor .............................................................. Szinkronizációs csatornák ........................................................... A szelektív várakozás ......................................................................... Nem-determinisztikusság és párhuzamosság ................................ Szelektív várakozás a Pascal-FC-ben ............................................ Az őrfeltételes select .................................................................... A terminate alternatíva ............................................................... Az else alternatíva ....................................................................... A timeout alternatíva .................................................................. Prioritásos select ......................................................................... A select alternatívák együttes használata ...................................... Alkalmazás: az étkező filozófusok problémája .............................. Az occam nyelvi csatornamodell ....................................................... Gyakorló feladatok a fejezethez .........................................................

4

109 111 113 113 114 116 118 120 124 125 125 127 127 130 132

Irodalomjegyzék ......................................................................... 133 Név- és tárgymutató .................................................................... 134


Vissza

4



Szekvenciális és párhuzamos algoritmusok


Vissza

5

Szekvenciális és párhuzamos algoritmusok Az algoritmusok hatékonyságának mérése Az algoritmus olyan pontosan definiált számítási eljárás, amely egy meghatározott feladatot elvégezve bemeneti (input) adatokból kimeneti (output) adatokat állít elő. Egy algoritmust a feldolgozandó elemek függvényében a lépésszámmal (és így végeredményben a futási idővel) jellemezhetünk. Ez a költségfüggvény elméletileg minden algoritmus esetében meghatározható. Az algoritmusok programnyelvtől független megadásához és elemzéséhez elméleti gépmodelleket használunk, amelyek egy processzort és írható-olvasható memóriát tartalmaznak. A processzor lépésenként (szekvenciálisan) végrehajtja az algoritmust, eközben használhatja a memóriát. Az algoritmust a gép számára valamely általános algoritmus-leíró nyelvben adjuk meg. Ilyen modellek például a Turing-gép és a RAM-gép (randomaccess machine). A Turing-gép a gépi számítások legrégibb és legismertebb modellje. Turing angol matematikus még 1936-ban vezette be. Egy korlátos központi részből és egy végtelen tárból áll. Előnye, hogy bármely számítás elvégezhető rajta, amelyet akár előtte, akár utána bármilyen más gépmodellen el tudtak végezni. Lényeges hátránya ugyanakkor, hogy a távoli memóriablokkokat csak szekvenciálisan lehet elérni. Mivel erősen eltér a valós gépektől, így főleg elméleti vizsgálatokra alkalmas. A RAM-gép a memória bármely részét egy lépésben el tudja érni, ezért inkább tekinthető a valódi számítógépek leegyszerűsített modelljének, mint a Turing-gép. Ezen gép memóriája szintén korlátlan, és minden memóriarekeszben tetszőlegesen nagy egész szám tárolható. Ezeknél a modelleknél a műveletek költségét a szükséges memória-hozzáférések száma határozza meg.


Vissza

5




Vissza

6

Definíció: Azt mondjuk, hogy az f(n) függvény eleme az Ordó(g(n)) halmaznak, ha van olyan c konstans és n0 küszöbérték úgy, hogy valamely n>n0-ra mindig 0 ≤ f(n) ≤ c*g(n). Sok esetben az „f(n) eleme Ordó(g(n))” helyett az „f(n) = Ordó(g(n))” vagy az „f(n) Ordó(g(n))”-es írásmódot is használjuk. Rövidítés: O(g(n)). c*g(n) f(n)

n0 f(n)=O(g(n))

Az Ordó(g(n)) f egy felső korlátja, amely lehet éles, illetve nem éles. A tovább már nem finomítható korlátot éles korlátnak nevezzük. Például n2 = Ordó(n2) éles korlát, n2 = Ordó(n3) nem éles felső korlát. A továbbiakban az Ordó jelölést külön említés nélkül éles korlátként használjuk. Adjunk meg olyan függvényeket, amelyekre teljesül, hogy f(n) = Ordó(n2) illetve f(n) = Ordó(n3) (nem éles korlát, éles korlát). (1) Sok klasszikus probléma, illetve algoritmus esetében már régóta ismert, hogy a megoldások költségfüggvénye milyen Ordó(g(n)) függvényosztályba tartozik. Ugyanazon probléma esetén azokat a megoldásokat tartjuk hatékonynak, amelyek szintén ilyen költségűek.


Vissza

6




Vissza

7

Vizsgáljuk meg, hogy milyen éles korlátot tudunk adni a következő klasszikus algoritmusok műveletigényére (n elemű tömböket használunk). Foglalkozzunk külön a legrosszabb, a legjobb és az átlagos esettel: Szekvenciális keresés, logaritmikus keresés; buborékos rendezés, kiválasztásos rendezés, beszúrásos rendezés, gyorsrendezés. (3)

Egy párhuzamos gépmodell Bár már az 1940-es években készült első számítógépek is rendelkeztek bizonyos párhuzamosítási lehetőséggel (pipeline technika, lásd később), az igazi többprocesszoros számítógépek csak 1-2 évtizede kezdtek elterjedni. Ezzel megnőtt az érdeklődés a párhuzamos algoritmusok iránt is, amelyekben egyidejűleg több művelet is végrehajtásra kerülhet. Ma már sok olyan probléma megoldására is léteznek párhuzamos algoritmusok, amelyeket azelőtt közönséges, szekvenciális algoritmussal oldottunk meg. A párhuzamos algoritmusok megadására és jellemzésére használt elméleti modell a párhuzamos véletlen hozzáférésű gép (PRAM-gép, paralell random-access machine). A PRAM-modellben a processzorok az osztott memóriához csatlakoznak. Az osztott memóriában bármely szót minden processzor egységnyi idő alatt ér el. A PRAM-gép processzorai egymással párhuzamosan dolgozni képes RAM-gépeknek tekinthetők. P(0) P(1) P(2)

OSZTOTT MEMÓRIA

P(n)

A PRAM-modellben az algoritmus hatékonyságát a párhuzamos memóriahozzáférések számával mérjük. Ez a közönséges RAM-modellnél használt azon feltételezés közvetlen általánosítása, miszerint a memória-hozzáférések száma (aszimptotikusan) jó közelítést ad a futási időre.


Vissza

7


Szekvenciális és párhuzamos algoritmusok Vissza

8

A valóságban a processzorok számának növekedésével nő az elérésük ideje is. Egy párhuzamos algoritmus futási ideje az algoritmust végrehajtó proceszszorok számától is függ. Ezért amikor egy PRAM-algoritmust vizsgálunk, a feladat bonyolultsága mellett a processzorok számát is figyelembe kell vennünk, ellentétben a szekvenciális algoritmusokkal. Egy algoritmus futási ideje és az általa használt processzorok száma között általában szoros kapcsolat áll fenn, amennyiben az egyik paraméter csak a másik kárára javítható. PRAM-gépekre írt egyes algoritmusokkal a fejezet végén még részletesen foglalkozunk.

Rendezések és rekurzió A klasszikus rendezések – buborékos, kiválasztásos, beszúrásos – Ordó(n2)es algoritmusok, hiszen a megoldáshoz két egymásba ágyazott ciklust használunk fel. Az Ordóban „elbújtatott” konstansok eredményezhetnek ugyan jelentős sebességkülönbséget egyes algoritmusok (például a hagyományos és a javított buborékos rendezés) között, de a különbség csak konstansszoros. A rendezések elemzésekor az időtényező mellett még más szempontokat is figyelembe szoktunk venni, például azt, hogy az algoritmus helyben rendez-e. Ezen utóbbi tulajdonság megléte azt jelenti, hogy az adattömbön túl csak konstans számú adat elhelyezése szükséges más tárterületen. Ez alapján például egy Ordó(n3)-os rendezés nem hatékony.

A gyorsrendezés Az Ordó(n2)-es algoritmusoknál ismerünk hatékonyabb rendező eljárásokat is. A legjobb általánosan is használható módszer a gyorsrendezés, amelyet C. A. Hoare mutatott be 1961-ben. Az algoritmus rekurzív, a teljes sorozat rendezését visszavezeti két félsorozat, majd négy negyedsorozat, … rendezésére. A rendező eljárás meghív egy felosztó rutint, amely egy ún. „könyökelem” kiválasztása után átcserélgeti az eredeti tömb elemeit úgy, hogy a tömb felső részében ne maradjon a könyökelemnél kisebb, alsó részében pedig nála nagyobb elem.


Vissza

8



9

Az algoritmus pszeudokódja: gyorsrendezés(A, p, r) ha p < r akkor q := feloszt(A, p, r) gyorsrendezés(A, p, q) gyorsrendezés(A, q+1, r) elágazás vége eljárás vége feloszt(A, p, r) x := A[p] i := p - 1 j := r + 1 ciklus amíg i < j # while ciklus, bennmaradási feltétel ciklus # repeat-until ciklus j := j - 1 amíg A[j] <= x # kilépési feltétel ciklus i := i + 1 amíg A[i] >= x ha i < j akkor csere(A[i], A[j]) ciklus vége return(j) eljárás vége

A jegyzetben többször használjuk ezt a Pascal-szerű pszeudokódot algoritmusok leírására. A gyorsrendezés hatékonyságát alapvetően az határozza meg, hogy a felosztó eljárás hogyan vágja szét az „A” tömböt kisebb részekre, illetve, hogy milyen stratégia szerint választjuk ki a „q” könyökelemet. A legszerencsésebb esetben a felezés után a részsorozatok elemszáma megegyezik, és ez a tulajdonság a rekurzió során végig megmarad.


Vissza

9




Vissza

10

n

n n/2

n/2 n/4

n/4

lg n

n n/4

n/4

n

n/8

n/8

n/8

n/8

n/8

n/8

n/8

n/8

n

1

1

1

1

1

1

1

1

n

Jelöljük „T(n)”-nel „n” elem rendezésének költségét. Ekkor T(n) = 2*T(n/2) + Ordó(n), ahol Ordó(n) a szétválogatás költsége (feloszt eljárás), „T(n/2)” pedig az „n/2” elem rendezésének költsége. A képletet kifejtve T(n) = 2*T(n/2) + O(n) = 4*T(n/4) + 2*O(n) = … = = n*T(1) + lg n*O(n) = O(n*lg n). A képlet kiszámolható rekurzívan, kifejtve illetve az ún. Mester-tétel (lásd Algoritmusok könyv [AL]) alkalmazásával. Ugyanez a tétel használható a jegyzetben található többi rekurzív képlet kiszámítására is. A technikai részletekkel a jegyzetben nem foglalkozunk. A legrosszabb felosztás esetén az egyik félsorozat elemszáma mindig egy. Ekkor T(n) = T(n − 1) + O(n) = T(n − 2) + 2*O(n) = … = n*O(n) = O(n2).


Vissza

10




Vissza

n 1

n n

n–1 1

n

11

n–2

n–1 n–3

1

n–2

1

2 1

3 1

2

A gyorsrendezés gyakorlati alkalmazhatóságát erősen korlátozná, ha egy véletlen számtömb esetén sokszor kapnánk a legrosszabb esetet. Szerencsére – mint a következőkben láthatjuk – ez nem így van. A gyorsrendezés átlagos futási ideje sokkal közelebb áll a legjobb, mint a legrosszabb futási időhöz. Vegyük például azt az esetet, amikor a felosztás mindig 9:1 arányban történik. Ekkor T(n) = T(9n/10) + T(n/10) + O(n) = … = O(n*lg n) Ugyanezt kapnánk 99 az 1-hez felosztásnál is, mert minden állandó arányú felosztáskor a rekurziós fa mélysége Ordó(lg n), és a költség minden szinten Ordó(n). A futási idő tehát Ordó(n*lg n) bármilyen állandó arányú felosztáskor. Ezeket a felosztásokat ezért kiegyensúlyozott felosztásoknak is nevezzük. A gyakorlati tapasztalatok azt mutatják, hogy általános tömb esetében a rossz felosztások viszonylag ritkán fordulnak elő, általában valamilyen kiegyensúlyozott felosztást kapunk. További igazolás nélkül megemlítjük, hogy a gyorsrendezés futási teljesítménye „n” elem összes permutációit tekintve csak néhány esetben éri el vagy közelíti meg a legrosszabb esetet. Tovább javítható a rendezés várható hatékonysága a könyökelem véletlen kiválasztásával, illetve az elemek véletlen átrendezésével az algoritmus alkalmazása előtt. Összefoglalva a fenti elemzést: a gyorsrendezés futási ideje átlagos esetben (gyakorlatilag szinte mindig) Ordó(n*lg n).


Vissza

11




Vissza

12

Elemezzük, hogyan viselkedik a fenti algoritmus teljesen rendezett és fordítva rendezett tömb esetén. (2) Természetesen felmerül a kérdés, hogy vannak-e Ordó(n*lg n)-nél jobb rendező algoritmusok. Ezzel kapcsolatban fontos tétel, hogy elemek összehasonlításán alapuló rendezés költsége átlagos esetben nem lehet kisebb Ordó(n*lg n)-nél. Nem összehasonlításos rendezések azonban lehetnek gyorsabbak. Ismerünk ilyeneket, bár használhatóságuk korlátozott, mert speciális tulajdonságokat követelnek meg az input adatoktól (például azok csak adott intervallumba eső egész számok lehetnek). Ezért, noha átlagos végrehajtási idejük csak Ordó(n), mégsem használhatók általánosan. A gyorsrendezés az egyik leghatékonyabb általánosan használható rendező eljárás.

Rekurzív algoritmusok párhuzamosítása A klasszikus rendező algoritmusok nem párhuzamosíthatók kézenfekvően, a gyorsrendezés esetén azonban több processzor használatával rövidebb futási időt érhetünk el az egymástól független lépések egyidejű végrehajtásával. Két processzorral rendezhetjük például az első rekurziós lépés után kapott két félsorozatot, majd négy processzorral a második lépés utáni négy negyedsorozatot, és így tovább. Végeredményben, ha van „n” illetve „n/2” darab processzorunk, akkor a teljes időigény csak O(n) + O(n/2) + O(n/4) + … + O(1) = O(n), figyelemben tartva azt, hogy a teljes műveletigény továbbra is T(n) = O(n*lg n). Természetesen ez az eredmény elméleti jellegű, mert nem foglalkoztunk azzal, hogy mily módon lehet a részfeladatokat az egyes proceszszoroknak kiosztani, és az eredményt tőlük begyűjteni. Ez a gyakorlatban a teljes végrehajtás lelassulását eredményezi. Hasonló párhuzamosítási lehetőség adódik bármely olyan rekurzív algoritmusnál, ahol egymástól független részfeladatokat kell végrehajtani. A gyorsrendezéshez hasonlóan az összefésülő rendezés is rekurzív rendező eljárás. Végezzük el a fenti elemzést ezen algoritmus esetében is. (3)


Vissza

12



13

Dinamikus programozás A dinamikus programozás a rekurzióhoz hasonlóan az eredeti feladatot részproblémákra osztással oldja meg, de a részproblémák most nem (teljesen) függetlenek egymástól, sőt egyes részproblémák megoldása ismétlődően előfordulhat. Emiatt a már megoldott részfeladatok eredményét táblázatban tároljuk, és amennyiben újból szükség van rájuk, visszakeressük a megoldást. Erről a táblázatos megadásról nevezték el magát a módszert is. A dinamikus programozást optimalizálási problémák megoldásához használjuk, ilyenkor a feladatra található egy vagy több optimális megoldás, és nekünk egyet elő kell állítani, illetve az értékét meg kell határozni. Az előállítás lépései a következők: 1. 2. 3. 4.

Jellemezzük az optimális megoldás szerkezetét. Rekurzívan definiáljuk az optimális megoldás értékét. Kiszámítjuk az értéket alulról felfelé. Megszerkesztünk egy optimális megoldást (amennyiben ez is szükséges).

Részletesen kidolgozott feladatokat az Algoritmusok című könyvben találhatunk (pl. mátrixszorzat optimális zárójelezése). A rekurzióhoz hasonlóan a dinamikus programozással megoldható feladatok esetében is gyorsulást eredményezhet a párhuzamos megoldás. Nagyon lényeges azonban a processzorok közötti jó kommunikáció, hiszen szükséges, hogy a már kiszámított részeredmények a többi processzor számára is hozzáférhetőek legyenek.

Mohó algoritmusok Hasonlóan a dinamikus programozáshoz, a mohó stratégiát is optimalizálási problémák megoldásához használjuk – van több optimális megoldás, egyet előállítunk. A mohó stratégia kevesebb lépéssel dolgozik, mint a dinamikus programozás. Mindig az adott lépésben optimálisnak látszó választást teszi, feltételezve, hogy a lokális optimum globális optimumhoz vezet. Mivel ez a feltételezés sok problémára nem teljesül, ezért a mohó stratégia nem alkalmazható minden esetben.


Vissza

13



14

Azok a problémák oldhatóak meg a mohó stratégiával, amelyekre teljesül a következő két feltétel: a) mohó választási tulajdonság (lokális optimumot választunk, az aktuális választás függhet a korábbi, de nem függhet a későbbi választásoktól); b) optimális részproblémák tulajdonság (optimális megoldás építhető a részproblémák optimális megoldásából). Klasszikus mohó stratégiával megoldható feladat például a pénzkifizetési probléma „normál” pénzrendszer esetén, illetve a Huffman-kód előállítása karaktersorozat optimális kódolására. „Normális” pénzrendszer esetén adott pénzösszeget úgy tudunk a legkevesebb bankjeggyel és/vagy érmével kifizetni, ha mindig a lehető legnagyobb címletet választjuk. Adjunk meg olyan pénzrendszert (például új bankjegyek bevezetésével), amelyben ez a feladat nem oldható meg optimálisan a mohó stratégiával. Megoldható-e mohó stratégiával az ún. hátizsák probléma: Adott több, különböző súlyú és értékű tárgy. Pakoljunk bele minél nagyobb értéket egy adott kapacitású hátizsákba. Változik-e a stratégia, ha a tárgyak törhetők? A mohó stratégia szekvenciális jellege miatt nem párhuzamosítható, ezért nem foglalkozunk vele részletesebben.

Párhuzamos technikák, párhuzamos algoritmusok A párhuzamos számítások lehetősége az algoritmusok szervezésében sokkal nagyobb szabadságot biztosít, mint a szekvenciális megközelítés. Ezt az alábbi hasonlattal szemléltethetjük: •

a szekvenciális algoritmus egydimenziós konstrukció, euklideszi térben; • a párhuzamos algoritmus több (változó)-dimenziós konstrukció, változó térben. Jelenleg még elsősorban szekvenciális gépeken dolgozunk, ezért a párhuzamos algoritmusok főként a szekvenciális algoritmusokban amúgy is megle-


Vissza

14



15

vő párhuzamosítási lehetőségeket használják. A párhuzamosítás alapvetően négyféle módon képzelhető el: a) triviális párhuzamosítási lehetőségek (nem feltétlenül triviális klasszikus algoritmusokban, pl. Gauss-elimináció); b) klasszikus algoritmusok alkalmas részeinek vagy egészének párhuzamos végrehajtással való felgyorsítása (pl. mátrix-vektor szorzás, aritmetikai kifejezések párhuzamos kiértékelése); c) új elemek beépítése klasszikus algoritmusokba egyes részfeladatok párhuzamos megoldására (pl. aritmetikai kifejezések párhuzamos kiértékelése); d) teljesen új elveken alapuló párhuzamos algoritmusok kifejlesztése. Teljesen új elveken alapuló párhuzamos algoritmusokat egyszerűbb esetektől eltekintve nehéz kifejleszteni, és a közeljövőben nem várható, hogy ilyenek tömegesen megjelennek. De előfordulhat, hogy néhány évtized múlva ez lesz a számítástechnika fő fejlődési területe. Az előző alfejezetekben megnéztük, hogy milyen párhuzamosítási lehetőségek vannak a rekurzív illetve a dinamikus programozással megoldható algoritmusokban. Most néhány fontos matematikai probléma megoldásának párhuzamos felgyorsítását tekintjük át, a fenti a)–c) pontok módszerei szerint. Később – ezen fejezet utolsó alfejezetében – bemutatunk néhány d) ponthoz tartozó egyszerűbb példát is.

A Gauss-elimináció A Gauss-elimináció a lineáris egyenletrendszerek megoldására használt klasszikus módszerek egyike. Általános esetben kezdetben adott „n” darab ismeretlen és „m” darab egyenlet a következő elrendezésben: a11*x1 + a12*x2 + … + a1n*xn = b1 a21*x1 + a22*x2 + … + a2n*xn = b2 a31*x1 + a32*x2 + … + a3n*xn = b3 . . . am1*x1 + am2*x2 + … + amn*xn = bm


Vissza

15




Vissza

16

A megoldás során az ismeretlenek fokozatos eliminálásával a teljes együtthatómátrixból felső háromszög mátrixot hozunk létre, amelyből aztán a megoldások leolvashatók, illetve visszahelyettesítéssel meghatározhatók. Az elimináció során megengedett műveletek a következők: • valamely sort egy nem nulla konstanssal megszorozhatunk; • valamely sorból kivonhatjuk egy másik sor konstansszorosát; • (ha szükséges) átjelölhetjük a még nem eliminált ismeretleneket. 1. lépés: ai1-et „lenullázzuk” i < 1-re, azaz az i. sorból kivonjuk az 1. sor ai1/a11-szeresét: a11*x1 + a12*x2 + … + a1n*xn = b1 (a21 − a21/a11*a11)*x1 + (a22 − a21/a11*a12)*x2 + … + (a2n − a21/a11*a1n)*xn = = b2 − a21/a11*b1

.

.

.

(am1 − am1/a11*a11)*x1 + (am2 − am1/a11*a12)*x2 + … + (amn − am1/a11*a1n)*xn = = bm − a21/a11*b1 Ezzel az első sort követő minden sorban az első oszlop lenullázódik. A következő lépés során a második sort követő minden sor második oszlopa is lenullázódik stb. Az elimináció végén „jó esetben” az első sorban „n” tag összege fog szerepelni, a másodikban „n-1”, …, az utolsóban pedig csak egy ismeretlen lesz. A „jó eset” akkor fordul elő, ha a rendszeren belül ugyanannyi független egyenlet található, mint ahány ismeretlen. Egyéb esetben lehet, hogy nem kapunk megoldást (ellentmondásos egyenletrendszer), illetve végtelen megoldás is lehet (egy vagy több ismeretlen értéke szabadon megválasztható). Ezen esetek pontos meghatározásával most nem foglalkozunk, ez bármely egyetemi/főiskolai lineáris algebrai kurzus anyagában szerepel. A lépésszám és a műveletigény négyzetes mátrixra hagyományosan Ordó(n3). Ha van n darab processzorunk, és ki tudjuk köztük osztani a részfeladatokat úgy, hogy párhuzamosan dolgozzanak (például 1-1 sort egymástól függetlenül számoljanak végig), akkor a lépésszám Ordó(n2) lesz (ugyanakkor a műveletigény továbbra is Ordó(n3) marad). Tovább gyorsítható az eljárás n2 processzorral, ekkor minden mátrixelemhez rendelünk egy processzort, és az azzal dolgozik. Így a lépésszám Ordó(n) lesz. Megjegyzendő,


Vissza

16




Vissza

17

hogy a gyakorlatban a processzorok közötti kommunikációra fordított idő a fenti elméleti határokhoz képest jelentősen lelassítaná a feladat megoldását. Gyorsítható-e a végrehajtási idő újabb processzorok rendszerbe állításával? (1,5) A probléma részeredményei tovább már nem függetleníthetők egymástól, tehát ha ennél több processzort használunk, akkor már nem érthető el sebességnövekedés. Néhány fontos gyakorlati problémával nem foglalkoztunk, amelyek szintén komoly lassulást okozhatnak a megoldás során. Ilyen például az eliminációra sajátosan jellemező ún. együttható-növekedési probléma: az egymás utáni lépésekben egyre több jegyű számokkal (gyakran egyre hoszszabb törtekkel) kell dolgozni. Ennek részbeni kivédésére javasolhatnánk a közelítő számításokat, de ez sem oldja meg a gondot: eleve elveszítjük a pontos megoldás lehetőségét, ráadásul a közelítések hibái a lépések során összegződnek, így rossz esetben nem is kapunk megoldást a számolás végén! Csak ügyes egyszerűsítések alkalmazásával háríthatók el a fenti problémák általános esetben.

Polinom-faktorizáció A polinomok szorzattá alakítása általános esetben bonyolult probléma. Példa ♦ Bontsuk fel A(x, y) = y2 + 2xy − 3y + x2 − 3x − 4-et ??? Erre a feladatra első közelítésben nem látszik használható megoldási módszer. Az alfejezetben feltételezzük, hogy az olvasó tisztában van a többváltozós polinomokkal kapcsolatos fontosabb fogalmakkal. A szakszerű megalapozáshoz a következő ismeretek, definíciók szükségesek (csak felsorolásszerűen bemutatva): Z: egész számok gyűrűje (+-ra és *-ra); Q: racionális számok testje (+-ra és *-ra); Z[x]: polinomgyűrű; Z[x, y]: értelmezhető mint Z[x][y] vagy Z[y][x] polinomgyűrű; Z[x, y, z]: rekurzívan értelmezhető a fentiek szerint; Zp[x] = Z[x] mod p test, ha p prím.


Vissza

17




Vissza

18

A fenti tartományokban van egyértelmű faktorizáció és egyértelműen létezik a legnagyobb közös osztó is. A következő ötletet használjuk: a) Az eredeti problémát redukáljuk egy sokkal egyszerűbben kezelhető tartományba, és ott oldjuk meg. Ez az egyszerűsítés lehet például a következő: Z[x, y, z, …, w] → Z[x] → Zp[x]. b) Ezután megoldjuk a problémát Zp[x]-ben, ahol egy polinom már viszonylag egyszerűen szorzattá alakítható. c) Utolsó lépésben a kapott megoldást visszaképezzük az eredeti tartományba: Zp[x] → Z[x] → Z[x, y, z, …, w] Példa folytatása ♦ A(x, y) Z[x]-ben x2 − 3x − 4 lesz, Z3[x]-ben pedig x – 1. Ez a polinom már egyszerűen szorzattá alakítható, a felbontások: Z3[x]-ben (x + 1)(x − 1); Z[x]-ben pedig (x + 1)(x − 4). Ez a részeredmény már csak abban tér el az eredeti felbontástól, hogy az y-os tagok hiányoznak. Ez visszaképezéssel megkapható. A teljes megoldás Z[x, y]-ban: A(x, y) = (x + 1 + y)(x − 4 + y). A megoldandó részfeladatok elemzése a) Egyszerűsítés. Ez könnyen végrehajtható rész, adott esetben párhuzamosítható is. b) A probléma megoldása Zp[x]-ben vagy Z[x]-ben. Bár a polinom szorzattá alakítása nyilván sokkal egyszerűbb probléma valamely redukált tartományban, intuitív módon (mint a fenti egyszerű példában) általában még most sem lehet célhoz érni. A szorzattá alakító algoritmusok túlnyomó többsége a legnagyobb közös osztó (lnko) meghatározásán alapul. Egy lehetséges ötlet a következő: lnko(p, p’) az eredeti polinom egy valódi osztója, ahol p’ a derivált polinom.


Vissza

18




Vissza

19

Példa ♦ Legyen p = A*B2*C3, ahol A, B és C tovább már nem bontható faktorok. Ekkor p’ = A’*B2*C3 + A*2*B*B’*C3 + A*B2*3*C2*C’ (de például Z3[x]-ben csak p’ = A’*B2*C3 + A*2*B*B’*C3, ez egyszerűbb), és lnko(p, p’) = B*C2 , ez egy valódi osztó. Mikor nem használható ez az ötlet?

(2)

Más felbontó eljárások is ismeretesek. Bonyolult (magas fokú) polinom esetén célszerű lehet (egyszerre) több eljárást is kipróbálni, hogy hamarabb célhoz érjünk. Mivel lényegében az összes felbontó eljárás használ lnko számításokat, ezért szükségünk van ezek hatékony kivitelezésére. Erre az euklideszi algoritmust használjuk, amely Zp[x]-ben és Z[x]-ben egyaránt végrehajtható. Az euklideszi algoritmus a maradékos osztás ismételt alkalmazásával határozza meg lnko(a, b)-t. a = b*q + r, ahol |r| < |b|

(1.1)

ahol a képletben szereplő |…| norma a polinom foka. Állítás ♦ lnko(a, b) = lnko(b, r) Ezután választhatjuk:

(ennek igazolása nyilvánvaló)

új a := b; új b := r;

majd újra végrehajtjuk az (1.1) lépést. Az utolsó nem 0 maradék az lnko. c) A megoldás visszaképezése az eredeti többváltozós polinomgyűrűbe. Megjegyezzük, hogy ez a legnehezebb lépés, itt csak a legfontosabb ötleteket tekintjük át. Nyilvánvaló, hogy egy Zp[x] vagy Z[x]-beli kép sokkal kevesebb információt hordoz, mint ami az eredeti felbontás előállításához kell, ezért további adatokra van szükségünk a feladat megoldásához. Két megközelítés használható: (i) sok Zp[x]-beli képet állítunk elő (több különböző p-re), vagy több Z[x]-belit; (ii) csak egy képet használunk, de van még valami plusz információnk.


Vissza

19




Vissza

20

(i) eset 1. Példa ♦ Tudjuk a Z[x, y]-beli u polinomról hogy u(x, 0) = −9x − 21, u(x, 1) = −3x + 20, u(x, 2) = 5x − 36. Ez alapján polinom interpolációval u(x, y) = (−9x − 21) + (6x + 41)(y − 0) + x(y − 0)(y − 1) = = xy2 + 5xy + 41y − 9x − 21 2. Példa ♦ Tudjuk valamely u számról, hogy u = 2 (mod 5) és u = 3 (mod 7). Mennyi u valójában? Nyilván 5x + 2 alakú (lehet: 2, 7, 12, 17, 22, 27, 32, …) és 7x + 3 alakú (lehet: 3, 10, 17, 24, 31, 38, 45, 52, …) egyszerre, így lehet 17, 52, …, de mod 35 egyértelmű a megoldás. A példák alapján láthatjuk, és általánosan is igazolható, hogy • Z[x, y] → Z[x] invertálható polinom interpolációval (y foka + 1 kép kell); • Z[x] → Zp[x] invertálható kínai maradék algoritmussal. Gondot jelent azonban, hogy összességében nagyon sok kép kell (végeredményben exponenciális), és nem jól párhuzamosítható a folyamat. (ii) eset A szükséges plusz információ lehet például a következő: és

F(v, u) = a(x, y, w, …, z) − v*u;

(két faktorra vágtuk a-t)

u(x, y, w, …, z) = u0(x); (Zp[x]-ben) v(x, y, w, …, z) = v0(x). (Zp[x]-ben)

(1.2) (1.3) (1.4)

Ezután u0(x)-et és v0(x)-et felemeljük fokozatosan Z[x]-be, Z[x, y]-ba, Z[x, y, w]-be, …, Z[x, y, w, …, z]-be úgy, hogy (1.2)–(1.4) érvényes maradjon.


Vissza

20



21

A faktorok felemelése egymástól lényegében független (egy szinten belül), így a módszer jól párhuzamosítható. Még többet nyerhetünk egy teljes felbontással: F(u1, u2, …, un) = a(x, y, w, …, z) − u1*u2*…*un – ahol (1.2)–(1.4) megfelelői érvényesek – majd ennek a felemelésével. Az (i) és az (ii) esetekben használható részletes algoritmusok (pontos elméleti igazolással együtt) megtalálhatók a [CA] könyvben. Írjunk olyan programot, amely szorzattá alakít egy általános többváltozós polinomot (reális fokkorláttal). Ajánlott irodalom: [CA]. (5) Összefoglalva, a polinomok szorzattá alakítása bonyolult, komoly számításigényű probléma. Mivel ezen számítások jelentős része párhuzamosan is végrehajtható, többprocesszoros gépen a végrehajtás jelentős felgyorsulását érhetjük el.

PRAM-algoritmusok Ebben az alfejezetben néhány egyszerűbb párhuzamos algoritmust mutatunk be, amelyeket PRAM-gépekre dolgoztak ki. Az alapvető számítástechnikai algoritmusok közül sok tömbökön, listákon, fákon és gráfokon dolgozó szekvenciális algoritmus felgyorsítható a PRAM-modell segítségével. A PRAM-modellben a lehetséges algoritmustípusok a következő módon csoportosíthatók: (i) EREW: kizárásos olvasás és írás (exclusive read and exclusive write) (ii) CREW: egyidejű olvasás és kizárásos írás (concurrent read and exclusive write) (iii) ERCW: kizárásos olvasás és egyidejű írás (exclusive read and concurrent write) (iv) CRCW: egyidejű olvasás és írás (concurrent read and concurrent write) változat: P-CRCW ill. P-ERCW (prioritásos modell). A prioritásos modellben egyidejű írás esetén valamilyen stratégia szerint ki kell választani a „győztest” (vagy győzteseket), aki(k)nek az akarata érvényesül. Erre a következő módszereket használhatjuk:


Vissza

21




• • • •

Vissza

22

a legkisebb sorszámú dönt; a közös akarat érvényesül (csak akkor van eredmény, ha ugyanazt írják); véletlenszerűen választunk; adott képlet alapján döntünk (pl. összeadjuk az eredményeket vagy azok átlagát, maximumát vesszük).

A modellek közül az EREW és CRCW a leggyakoribb. Példa ♦ Határozzuk meg n darab processzorral, hogy két n hosszú 0-1 sorozat közül melyik a nagyobb! P-CRCW modellben elég O(1) lépés: a processzorok egyidejűleg sorszámot írnak, hogy melyik sorozat a nagyobb, a legkisebb helyen levő eltérés dönt. Igazoljuk, hogy EREW modellben elég O(log n) lépés.

(2,5)

A példában és a feladatban láthattuk, hogy a modellek közötti erőforrás- és időkülönbség nem „túl nagy”. Ez általánosan is igazolható: Állítás ♦ Ha egy probléma megoldható P-CRCW modellben p proceszszorral t idő alatt, akkor megoldható EREW modellben O(p2) processzorral O(t*(log p)2) idő alatt. Példa ♦ Határozzuk meg egy lista elemeinek a lista végétől való távolságát! Nem párhuzamos megoldás esetén O(n) lépés szükséges, minden elem a következőtől megkapja a partner távolságadatát, a sajátja ennél eggyel nagyobb lesz. A párhuzamos megoldásnál n darab processzort használunk, minden elemhez pontosan egyet rendelünk. Az algoritmus vázlata: (i) (minden i processzor párhuzamosan dolgozik) ha köv[i] = NIL akkor d[i] := 0 különben d[i] := 1 (ii) ciklus (minden i processzor párhuzamosan dolgozik) ha köv[i] <> NIL akkor d[i] := d[i] + d[köv[i]] köv[i] := köv[köv[i]] % mutatóugrás amíg van olyan objektum, amelyre köv[i] <> NIL % bennmaradási feltétel


Vissza

22




Vissza

23

A következő kis táblázat az algoritmus működését mutatja be. A lista elemei rendre 3, 4, 6, 1, 0 és 5. Az utánuk elhelyezkedő számjegy (kezdetben 1) az elemhez tartozó mutató távolsága, a nyíl utáni pedig azon elem, amelyre a mutató az adott lépésben mutat. 3 31→ 32→6 34→0 35→N

4 41→ 42→1 44→5 44→N

6 61→ 62→0 63→N 6

1 11→ 12→5 12→N 1

0 01→ 01→N 0 0

5 50→N 5 5 5

Az algoritmus végrehajtásához tökéletes szinkronizáció szükséges a processzorok között, a mutatóugrás sorában együtt kell végrehajtaniuk a jobb oldalt, majd utána a balt. A mutatóugrás az a hatékony technika, amellyel el tudjuk érni a megoldás felgyorsulását a szekvenciális megközelítéshez képest. Ugyanakkor ezzel a lista eredeti szerkezete sérül. Ha a feladat befejezése után is szükség van a kezdeti állapotra, akkor másolatot kell készítenünk a mutatókról az algoritmus végrehajtása előtt. Melyik modellben készült ez a megoldás?

(1,5)

EREW modellben, mert minden olvasás és írás kizárólagos. Mennyi a szükséges lépésszám?

(1,5)

O(log n) lépés kell (ii)-ben. Készítsünk (P-)CRCW modellben jobb megoldást!


(5)

Vissza

23



Párhuzamos hardverarchitektúrák Vissza

24

Párhuzamos hardverarchitektúrák Az 1980-as évektől kezdve a párhuzamos számítások már lényegesen befolyásolják a tudomány fejlődését és a gazdasági életet. Ekkorra a gépek sebessége a kezdetiekhez képest már többezerszeresére nőtt, és a további gyors fejlődést elsősorban a processzorok számának növelésével lehetett biztosítani. A számítógépek teljesítményének növelését napjainkban elsősorban a különböző tudományterületeken végzett bonyolult számítások szükségessége indukálja (fontosabb példák: kémia és biokémia, anyagtudomány, elemi részek fizikája, csillagászat, meteorológia és szimulációs vizsgálatok a legkülönbözőbb területeken).

A párhuzamos architektúrák fejlődésének története A párhuzamos számolás gondolata már régen felvetődött, szinte mindenki írt erről, aki a számítások automatizálásával foglalkozott. Az egyik első komoly feljegyzés Lady Lovelace Byrontól származik 1842-ből. Lényegében ezt a gondolatmenetet fejlesztette tovább Turing 1950-ben. Kezdeti szintű párhuzamosítás a pipeline-technika (lásd később) használata, ez már Neumann Jánosnál is megfigyelhető az EDSAC1 (1949) és UNIVAC (1951) gépekben. Ezt a módszert később a Cray és Cyber típusú gépeknél azzal bővítettek ki, hogy logikailag különböző processzorokat különböző feladatokra osztottak ki. A finomabb lehetőségek használata, azaz a job-, algoritmus- és utasításszintű párhuzamosítás viszonylag új, hiszen csak az 1980-as évektől terjednek el rohamosan a többprocesszoros rendszerek. A párhuzamos architektúrák fejlődését végigkísérte a technika fejlődése. Az áramkörök fő elemei kezdetben az elektroncsövek voltak, ezeket követték később a tranzisztorok, majd az integrált áramkörök. Első lépésként kifejlesztették a nagy sűrűségű integrált áramköröket (LSI – large scale integrated circuits), majd a nagyon nagy sűrűségű és az ultra nagy sűrűségű integrált áramköröket (VLSI – very large scale integrated circuits, ULSI – ultra large scale integrated circuits). Úgy tűnik, hogy a további miniatürizálás


Vissza

24



25

lehetősége már korlátozott, az ohmos ellenállás következtében keletkező hő elvezetésével kapcsolatos nehézségek miatt. Az adattárolás fejlődésével csökkent az elérési idő. A korábbi, a proceszszorhoz képest lassú mágneses tároló helyett például az ULSI integrált áramkörben már elektronikus úton valósítják meg az adattárolást. Ezzel lehetővé vált, hogy nagyszámú processzor közvetlen kapcsolatban legyen a memóriabankkal. Megjelentek a processzorok közötti új, sokkal hatékonyabb kapcsolatok (például a hiperkocka). Ezzel a Neumann által tervezett egyprocesszoros rendszert egy valódi sokprocesszoros konstrukció váltotta fel. Összefoglalóan mondhatjuk, hogy eleinte a futásidő csökkentésére egyre nagyobb sebességű processzorokat használtak, majd egy idő után több hagyományos processzort kapcsoltak össze egyetlen számítógépben.

A csúcsteljesítményű számítógépek fejlődése 1949-től napjainkig Az y tengelyen a számítógép műveletvégző sebességét mérjük: FLOPS – lebegőpontos művelet per másodperc (ez függ a feladattól is).


Vissza

25



26

A processzorok számának a növelése természetesen sok egyéb problémát is felvet, ezekkel később részletesen foglalkozunk. Ideális esetben a rendszer teljesítménye a CPU-k számának a növelésével arányosan nő, ekkor a rendszert skálázhatónak nevezzük. Ha ezt nem is tudjuk mindig garantálni, a teljesítménynövekedés legyen legalább arányos a szükséges anyagi ráfordítással, különben az elkészült rendszer gazdaságtalan és így eladhatatlan lesz. Az elmúlt években megjelentek az új gépekre írt valódi párhuzamos algoritmusok, amelyekkel bonyolultságuk ellenére jelentős teljesítménynövekedést lehet elérni.

A párhuzamos architektúrák osztályozási lehetőségei A párhuzamos hardverarchitektúrák csoportosítására egyértelmű terminológia nem alakult ki, többféle lehetőséget is kidolgoztak. Leginkább a Flynnféle osztályozást használják (lásd következő alfejezet), de más csoportosítások is elterjedtek. Ezeket mutatjuk be a következőkben. 1. egyprocesszoros rendszerek 2. többprocesszoros rendszerek az összekapcsolás jellege szerint a) • szorosan kapcsolt (tightly-coupled) • lazán csatolt (loosely-coupled or distributed) b) • processzor farm • processzor cube a processzorok felépítése szerint • szó szervezésű (ez a hagyományos) • bit szervezésű a memóriamodulok felépítése szerint • integrált (integrated) • (meg)osztott (shared)


Vissza

26



27

Fontos megjegyezni, hogy a különböző csoportok között sok esetben akár szoros kapcsolat is teremthető, például a Flynn-féle osztályozásban szereplő multiszámítógépek sokszor lazán csatolt rendszerek. Az egy- és többprocesszoros rendszerek összehasonlító elemzésével a jegyzetben később még több helyen is foglalkozunk. Most néhány olyan előnyt vizsgálunk meg, amelyet a többprocesszoros rendszerek hardverszinten nyújtanak a hagyományos rendszerekhez képest. a) Teljesítménynövekedés Egyprocesszoros rendszerek esetében csak az alkatrészek sebességének fokozásával érhető el teljesítménynövekedés, de ennek felső határt szab az elektromágneses hullámok véges terjedési sebessége és a hődisszipáció. A teljesítmény növelésének másik lehetősége, hogy a rendszerben egyidejűleg működő aktív elemek számát növeljük. Ennek egy lehetséges módja a beépített processzorok számának növelése és olyan programozási technika alkalmazása, amely biztosítja ezek egyidejű, párhuzamos működését. Fontos megjegyezni, hogy a teljesítmény és a processzorok száma között nincs egyenes arányos kapcsolat, aminek fő oka a hardver és szoftver téren egyaránt jelentkező hozzáférési verseny. Lényeges szempont az ár/teljesítmény arány is, amely nagyban függ a teljes rendszer szervezésétől és kiépítésétől. A mikroprocesszorok és a hozzájuk tartozó kiegészítő elemkészlet viszonylagos olcsósága következtében a központi egység ára legalább egy nagyságrenddel kisebb a teljes rendszer áránál, így a processzorok árának növelése ilyen szempontból nem jelent drasztikus árnövekedést. b) Modularitás, bővíthetőség, flexibilitás A modularitás annak a mértéke, hogy a rendszerelemek mennyire kompaktak és izoláltak. A mikroprocesszoros rendszerekre alapvetően jellemző a nagyfokú modularitás, függetlenül attól, hogy kiépítésükben egy vagy több processzor szerepel-e. A bővíthetőség szempontjából a többprocesszoros rendszer kedvezőbb, hiszen a beépített processzormodulok száma is változtatható. A flexibilitás azt méri, hogy a rendszerkonfiguráció milyen rugalmassággal igazítható különböző alkalmazásokhoz. A többprocesszoros rendszerek mind a real-time, mind az újratervezés alatti flexibilitás tekintetében megelőzik az egyprocesszoros rendszereket.


Vissza

27


Párhuzamos hardverarchitektúrák


Vissza

28

c) Megbízhatóság Többprocesszoros rendszer esetén a rendszer redundanciája fokozható tartalék processzorok alkalmazásával. Különösen a dinamikus taszkkiosztást megvalósító rendszerekben érhető el nagy biztonság.

Csoportosítás az összekapcsolás jellege szerint Szorosan kapcsolt (tightly-coupled) ♦ Az ilyen rendszerekben egy buszra több CPU csatlakozik, erre vannak felfűzve az input eszközök és a közös memória is. Minden processzor használhatja a buszrendszert, és egyes processzoroknak lehet saját memóriája is (ezt a többiek nem „látják”). Lazán csatolt (loosely-coupled or distributed) ♦ Ez a rendszer szétszórt csomópontokból épül fel, ezek akár nagy földrajzi távolságban is lehetnek egymástól. A csomópontok egy- vagy többprocesszorosok lehetnek. A csomópontok nem használnak közös memóriát, irányított hálózaton keresztül kommunikálnak egymással. Processzor farm ♦ Kevés számú processzorból álló konstrukció, amelyben minden egység minikomputer teljesítményű. Szükség esetén minden processzor önállóan is használható. A kommunikáció vagy egy buszrendszer segítségével elérhető osztott memórián keresztül, vagy pedig egy irányított hálózaton keresztül történik. Ezek a gépek olyan esetekben használhatók elsősorban, amikor az eredeti feladatot több, közel azonos nehézségű részproblémára tudjuk bontani. Példa: Alliant FX gépcsalád. Processzor cube ♦ Ebben a rendszerben sok processzor található, különböző teljesítménnyel (az egyszerű bit szervezésűtől kezdve egészen a minikomputerig), amelyek irányított hálózattal csatlakoznak egymáshoz. A processzorok önállóan nem használhatók. Jelenleg az ilyen rendszerek 128–216 darab processzorból állnak. A rendszer működtetéséhez vezérlő egység és okos menedzserprogram szükséges: a nehéz feladatokat a nagyteljesítményű processzorok kapják, a könnyűeket pedig a kisteljesítményűek. Példa: transputer.

Csoportosítás a processzorok felépítése szerint Szó szervezésű ♦ Ez a hagyományos, általánosan elterjedt szervezési mód. Bit szervezésű ♦ Egy szó tartalmát ilyenkor memóriából bitenként egymástól függetlenül lehet kiolvasni. Minden processzorelem csak az adat egy


Vissza

28




Vissza

29

bitjén végez műveletet, az adatot a saját memóriájából veszi. Ebből a szervezésből előnyök és hátrányok egyaránt adódnak. Például a hagyományos aritmetikai műveletek végrehajtása valamelyest lelassul és bonyolultabb a társzervezés, ugyanakkor egyes speciális adatokkal gyorsabban tudunk dolgozni, ha nem kell őket „mesterséges” szavakba pakolni és változó hoszszúságú aritmetika is megvalósítható. A logikai műveletek ilyen rendszerben különösen egyszerűvé válnak. Az első bit szervezésű gépcsalád az IBM 701 volt (1953).

Csoportosítás a memóriamodulok felépítése szerint Integrált (integrated) ♦ Nincs más memória a rendszerben, csak ami a processzorhoz tartozik, és ez csak a processzoron belül lokálisan címezhető. Példa: transputer. (Meg)osztott (shared) ♦ A rendszerben van központi memória is, amely bármely processzorból címezhető, függetlenül attól, hogy az adott proceszszornak van-e lokális memóriája. Példa: Alliant FX gépcsalád.

A Flynn-féle osztályozás Az általános célú párhuzamos rendszerek legsikeresebb, napjainkban is széles körben elfogadott osztályozása M. J. Flynn nevéhez fűződik (1972), aki az adatok kezelése (hány adattal hány műveletet végzünk egy időben) alapján a következő kategóriákat állította fel:

Egy adat – Single data Több adat – Multiple data

Egy utasítás – Single instruction

Több utasítás – Multiple instruction

SISD (Neumann-féle)

MISD

SIMD

MIMD

Az MISD kategória üres, hiszen nehezen képzelhető el, hogy egyszerre több utasítás dolgozik ugyanazon az adatrészen. Egyes szakemberek azonban a pipeline (csővezeték, lásd később) technikát használó egyes gépeket ebbe a kategóriába sorolják. Flynn osztályozását később kiterjesztették az egyes kategóriák további megosztásával. Bevezették az SIMD csoporton belül a vektor- illetve a


Vissza

29




Vissza

30

tömbprocesszorokat, az MIMD-n belül pedig a multiprocesszorokat (van közös memória) és a multiszámítógépeket (nincs közös memória, csak saját). Ezekkel a csoportokkal a következő alfejezetekben részletesen is foglalkozunk.

Az SISD gépcsalád Az SISD csoportba a klasszikus, szekvenciális Neumann-elvű gépek tartoznak. Az elsőt még az 1940-es évek elején-közepén gyártották, ekkor még elektroncsövek felhasználásával. Ezek a gépek több évtizeden keresztül nagyon népszerűek voltak (és még napjainkban is azok), ennek okai: egyszerű elvek, viszonylag egyszerű felépítés és gazdaságos gyártás. Ennek ellenére ma már kevés a teljesen tisztán Neumann-elvű gép, mert az operációs rendszerek fejlődése egyfajta virtuális párhuzamosságot eredményezett. A Neumann-elv az elektronikus számítógéppel kapcsolatos követelményeket fogalmazza meg: 1. mik legyenek a számítógép fő részei, melyek a velük szembeni kívánalmak; 2. a tárolt program elve; 3. az automatikus, emberi beavatkozás nélküli működés követelménye. 1. A számítógép fő funkcionális részei a következők: • • • •

vezérlőegység (control unit); aritmetikai és logikai egység (ALU); tár (memory), ami címezhető és újraírható tárolóelemekkel rendelkezik; be/kimeneti egységek.

1. Mindezen egységek teljesen elektronikusak legyenek és bináris számrendszert használjanak. Az ALU képes legyen elvégezni az alapvető logikai és aritmetikai műveleteket (néhány elemi matematikai és logikai művelet segítségével elvileg bármely számítási feladat elvégezhető). 2. Tárolt program elvű legyen a számítógép, azaz a program és az adatok ugyanabban a tárban tárolódjanak, ebből következően a programokat tartalmazó rekeszek is újraírhatók. A tárból kiolvasott utasítások alapján a vezérlőegység határozza meg a működést emberi beavatkozás nélkül.


Vissza

30



31

3. Van egy utasításkészlet (instruction set), amelynek utasításait a vezérlő képes felismerni és az ALU-val elvégeztetni. Az utasításhalmaz egy alhalmaza a tár (rendszerint egymás utáni) címezhető celláiban van. A vezérlőegység egy mutatója jelöli ki a soron következő végrehajtható utasítást (instruction). Ezt a vezérlőegység értelmezi. Az utasításokban kódolva vannak/lehetnek az adatok, vagy az adatok tárbeli címei. Ezeket a vezérlőegység a tárból előveszi, az ALU pedig elvégzi rajtuk az operációkat. A tárolási helyek címezhetők, az ott tárolt értékek megváltoztathatók. Egy instrukció végrehajtása után a vezérlőegység mutatója automatikusan – emberi beavatkozás nélkül – a soron következő instrukcióra mutat, a vezérlőegység veszi ezt az instrukciót és így tovább. Megjegyzendő, hogy Neumann még nem használta a CPU (Central Processing Unit) kifejezést, hiszen ez akkoriban még nem létezett. A három pont együtt azt is kimondja, hogy a számítógép lényegében a hardver és a szoftver együttese, hiszen működését nemcsak a hardver szabja meg.

A pipeline-technika és a vektorgépek Már a korai SISD-gépeknél is alkalmaztak egy korlátozott szintű párhuzamos módszert, az ún. pipeline (csővezeték) technikát. Ez a módszer akkor alkalmazható, ha a CPU néhány – különböző funkciókért felelős – része egymással párhuzamosan tud működni. Az ilyen processzort vektorproceszszornak, a vektorprocesszoros számítógépet pedig vektorgépnek nevezzük. Később ezt a technikát többprocesszoros vektorgépeken (SIMD kategória) is sikerrel alkalmazták. A módszer lényege a következő: Egy gépi utasítás végrehajtása általában több fázisra bontható (utasítás felhozása, dekódolása, hozzá tartozó akciók végrehajtása). A számítógépek többsége ezeket a fázisokat sorosan hajtja végre. A működés azonban nagymértékben felgyorsítható, ha ezeket a fázisokat átlapoltan, több utasításon párhuzamosan hajtja végre a számítógép. Ez – a fenti példánál maradva – azt jelenti, hogy az n-edik utasításhoz tartozó akciók végrehajtásával egyidejűleg folyik az (n+1)-edik utasítás dekódolása, és az (n+2)-edik utasítás felhozása. Tehát assembler szinten korlátozott párhuzamosításról van szó. Az elérhető sebességnövekedés k fázis esetén k-szoros, ha a feltöltés és a végső kiürülés ideje a teljes működési időhöz képest elhanyagolható.


Vissza

31




Vissza

32

Példa ♦ n hosszú vektorok összeadása. Kissé leegyszerűsítve mondhatjuk, hogy az a és b számok összeadása 3 lépésben történik meg (a valóságban bonyolultabb): 1. a elérése; 2. b elérése és hozzáadása a-hoz; 3. az a + b eredmény outputja. A következő táblázat az egyes ütemezési periódusokban elvégzett műveleteket mutatja: ütemezési periódus 1 2 3 adatbevitel a1 a2 a3 adatbevitel b1 b2 és összeadás a1+b1 a2+b2 kimenet a1+b1

4 a4 b3 a3+b3 a2+b2

... ... ... … …

n an bn−1 an−1+bn−1 an−2+bn−2

n+1 – bn an+bn an−1+bn−1

n+2 – – – an+bn

A legsikeresebb vektorgépek a vektor-szuperszámítógépek, közülük a Cray-1 az 1970-es évek közepétől a végéig földgolyónk leghatékonyabb számítógépe volt. Felépítésének elveit (kissé aktualizálva) sok modern szuperszámítógép is követi. A vektorgépek egyetlen hátránya az, hogy nem minden feladatnál lehet kihasználni a vektor jellegű feldolgozás előnyeit. A későbbi Cray (C90, T90, T3D, T3E) szériák szintén a szuperszámítógépek élmezőnyébe tartoztak/tartoznak. A legújabb gépek már nem az SIMD, hanem az MIMD csoporthoz sorolhatók. A legfontosabb vektorgépek adatai: • Cray-1 (1976) és 1S központi tár: (0,5–4)*106 64 bites szó (8 MB) 1 processzor, órajel 12,5 ns (80 MHz) 12 pipeline 3/3/3/3, +, −, *, / • Cray X-MP 1, 2, 4 processzor, bennük (0,5–8)*106 64 bites szó órajel 9,5 ns 8 db vektorregiszter, innen kapják az adatokat a pipeline egységek a pipeline egységeket láncolják, így pl. gyorsabban számolható (a + b)*c


Vissza

32




Vissza

33

lebegőpontos pipeline vektorregiszter Központi tár

vektorregiszter

+

* vektorregiszter

/

A Cray-gépek processzorának a szerkezete További nevezetesebb vektorgépek még: Star 100 (1971, 4 processzor), Cyber 205 (1980, 1, 2, 4 processzor), Fujitsu VP-200 (1982, 1), Cray-2 (1985, 4), Eta 10 (1987, 2, 4, 6, 8), Cray-3 (1988, 16) A vektorgépek fejlesztése utáni következő lépést a RISC processzorok megjelenése jelentette, amelyekben az utasításonkénti fix hosszúsági végrehajtási idő nagyon megkönnyítette az elemi utasítások párhuzamos végrehajtását. Ezt a módszert manapság már majdnem minden mikroprocesszorban alkalmazzák. A processzorokban többszörözött feldolgozó egységek vannak, amelyek az elemi utasítások szintjén párhuzamosítják a szekvenciálisan írott programokat (amennyiben ez lehetséges).

Az SIMD-tömbprocesszor gépcsalád Az SIMD-gépek másik fő csoportját a tömbprocesszorok alkotják. Az első ilyen gépet (ILLIAC IV) az 1970-es évek elején mutatták be, tömegesebben mintegy 10 évvel később terjedtek el. Egyes modern SIMD-gépeket napjainkban tudományos számításoknál alkalmaznak. Ezen gépeknél a központi vezérlőegység (MCU – master control unit) minden processzor számára ugyanazt az utasítássorozatot adja (broadcast technika, üzenetszórás). Ezeket az utasításokat minden processzor egyidőben hajtja végre. Minden processzornak van saját memóriája, néhány rendszerben globális memória is található. A processzorok felépítése a kivételesen egyszerűtől a nagyon bonyolultig terjedhet. A processzorokat összekötő hálózat az adatforgalom lebonyolítására szolgál.


Vissza

33




Vissza

34

Az SIMD-gépek vázlatos felépítése (tömbprocesszor) A tömbprocesszorok felépítésük jellege miatt csak meghatározott területeken alkalmazhatók, itt azonban igen hatékonyak lehetnek. A képfeldolgozás során például gyakran adódnak olyan helyzetek, amikor sok (akár kisképességű) processzor hatékonyabb megoldást tud adni, mint egy vagy néhány nagyobb képességű. Adjunk megoldási vázlatot tömbprocesszor alkalmazásával a következő problémára: Körvonal rajzolása körlemezből kis képességű processzorokkal O(1) lépésben. (2) Néhány sikeres tömbprocesszoros gépcsalád: • Distributed array processors, DAP-család; • Connection Machine, CM-család; • MP-1 gépcsalád. A DAP-gépekben 4096 processzor található, 64×64-es rácsszerkezetbe rendezve. A gépcsalád elvét az 1970-es évek elején dolgozták ki. Megvalósítások: • ICL – Nagy Britannia • AMT Active Memory Technology Inc. – USA


Vissza

34



35

A DAP-gépek processzorainak összekapcsolása A processzorok közvetlen kapcsolatban vannak a legközelebbi szomszéddal. Minden (elemi) processzornak 1 bites saját memóriája van. A teljes aritmetika szoftverrel megvalósított. A CM-gépek 65535 (216) processzort tartalmaznak (inking Machine Corp.). Az első gépet 1983–84-ben tervezték. Elemi processzorai szintén 1 bitesek. A működési jellemzőit lebegőpontos gyorsítókkal (accelerators) növeli, bár elemi processzorai lényegesen lassabbak a DAP-gépek proceszszorainál. Processzorainak összekapcsolására a hiperkocka-kapcsolást alkalmazták.


Vissza

35



36

A hiperkocka-kapcsolás 0-5 dimenziós esetben.


Vissza

36



37

A fenti ábrák négy- és ötdimenziós esetben csupán „közelítést” adnak a kockáról, bemutatva a logikai kapcsolatokat a csúcsok között. Természetesen az ábráról az is leolvasható, hogy hány éle és hány lapja van az adott dimenziós kockának, illetve hogy mely csúcsok között vezetnek élek. Ugyanakkor magát a négy- vagy ötdimenziós kockát nem tudjuk pontosan elképzelni. Adjunk általános szabályt az n-dimenziós hiperkocka-kapcsolásra. Segítség: használjunk n-dimenziós koordináta-rendszert a csúcsok azonosítására. Például (0, 0), (0, 1), (1, 0), (1, 1) csúcsok. (2) Készítsünk háromdimenziós modellt a négy- és ötdimenziós kockáról. (4) Készítsünk négydimenziós modellt a négydimenziós kockáról.

(5)

Jelenleg a hiperkocka-kapcsolás az egyik legnépszerűbb összekötési mód, ugyanis a csomópontok számának növelése • nem növeli aránytalanul a közvetlen kapcsolatok számát, így nem nő túlzottan a hálózat bonyolultsága; • az alternatív utak számát viszont jelentősen növeli, ezzel a kommunikáció sebessége felgyorsul, biztonsága megnő. MP-1 gépcsaládban 16384 (214) processzort kapcsoltak össze (MasPar Computer Corporation – USA). A gépcsaládon belül öt modellt fejlesztettek ki. Elemi processzorait x-hálós rendszerben kapcsolták össze, ekkor minden processzor a 8 hozzá legközelebb lévővel áll közvetlen kapcsolatban.


Vissza

37



38

Az MP-1 gépcsalád elemi processzorainak összekapcsolása

Az MIMD gépcsalád Az igazi forradalmi változást az MIMD-gépek jelentik a Neumann-elvű gépekkel szemben. Ezen gépek processzorai a többitől függetlenül is képesek dolgozni, és sokszor ekvivalens teljesítményűek. Az ilyen felépítésnek nagy előnye, hogy a munka jó szervezése mellett minden processzor teljesítménye jól kihasználható, míg az SIMD-gépeknél a processzorok kihasználtsága attól is függ, hogy az aktuális utasítást hány adaton kell végrehajtani. Mivel az MIMD-gépekben a processzorok egymással is kommunikálhatnak, ezért a kommunikációs hálózat megtervezésének nagy jelentősége van. A proceszszorok összekötésére a legfejlettebb módszereket alkalmazzák, sok esetben a hiperkocka-kapcsolást. A processzorok száma ezen rendszerekben jelenleg még kisebb, mint az SIMD-gépeknél.


Vissza

38




Vissza

39

Az MIMD-gépek vázlatos felépítése Az MIMD-gépeket klasszikusan két csoportra bonthatjuk: • a rendszerben csak osztott (shared) memória van (multiprocesszorok); • a processzoroknak csak saját (distributed) memóriája van (multiszámítógépek). A multiprocesszorokra jellemző az osztott (közös) változók használata, míg a multiszámítógépek a közös memória hiánya miatt üzenetváltásos kommunikációs modellt alkalmaznak, ez a szoftver így bonyolultabb. A multiprocesszorok ugyanakkor sok processzorral nem működtethetők hatékonyan a közös memória elérésével kapcsolatos nehézségek miatt. Amennyiben például 100 processzor ugyanazon változót akarja írni/olvasni, ez szinte feloldhatatlan „memóriaversenyt” eredményez. Felépítésük jellege miatt tehát a nagyobb méretű multiprocesszorokat nehéz megtervezni és megépíteni, ugyanakkor viszonylag könnyű programozni, míg a multiszámítógépek esetében ez fordítva van. Ezért a két filozófiát sokszor együtt is alkalmazzák „hibrid” rendszerek előállítására. Ez megvalósítható például úgy, hogy a multiszámítógép hadver vagy szoftver úton (Linda- és Orca-rendszerek) szimulálja a közös memóriát. Így előfordul az is, hogy egy multiszámítógépes rendszer szimulálja az osztottváltozós modellt, míg egy multiprocesszoros rendszer az üzenetváltásos modellt. Osztott memóriás gépek: • Alliant FX gépcsalád (processzor farm, 8db processzor); • TC 2000 – Motorola 8800 RISC Chips processzorok; • BBN butterfly (256 processzor, pillangós kapcsolás, lásd később).


Vissza

39




Vissza

40

Saját memóriás gép: • Transputer – Inmos cég (keverő hálózat, lásd később). A transputer egy elosztott programozású szoftvermodell hardver-megvalósításaként jött létre a nyolcvanas évek közepén. Önmagában egy általános célú, nagyteljesítményű (10 MIPS), 32 bites RISC-elvű processzor, memóriával, input-output lehetőséggel és szükség szerint egy dupla pontosságú lebegőpontos műveletvégző társprocesszorral (1,5 MFLOPS) kiegészítve. Típustól függően 2-4 kbyte gyors SRAM-ot tartalmaz. Elsődlegesen arra készült, hogy az occam nyelven írt programok hatékony végrehajtó processzora legyen. A tervezők (Inmos) úgy alakították ki a belső architektúrát, hogy rendkívül hatékonyan tud több szekvenciális folyamatot átlapoltan végrehajtani. Ezt úgy érték el, hogy kevés belső regisztert tartalmaz, és a folyamatváltás csak a végrehajtás jól definiált pontjain történhet, így a folyamatváltás ideje minimális, egy egyéb utasítás végrehajtási idejének mintegy másfélszerese. A transputer emellett a párhuzamos működésű számítógépek egy lehetséges építőeleme (MIMD-architektúra). A transputer-elemekből általános és célszámítógépek építhetők a megoldandó feladat függvényében, a legjobban megfelelő architektúrát állítva össze. Négy csatlakozója segítségével igen sokféle topológiát lehet kialakítani, ilyenek például a csővezeték (pipeline), a gyűrű (ring), a háló (mesh), a fa (tree) és a kocka (cube, max. négydimenziós). A multiprocesszor és multiszámítógép kategóriák még további csoportokra is bonthatók (például SMP, MPP, SPP, UMA, COMA, NUMA, COW), azonban ezen a szinten az osztályozásra a szakirodalomban már nem alakult ki közelítőleg egységes rendszer (egyes szerzők más-más felosztást tartanak fontosnak). Mivel a fenti kategóriák részletes ismertetése meghaladná ezen jegyzet lehetőségeit és célját, ezért a továbbiakban csak egy gépcsaládot és egy konkrét példát nézünk meg. A téma iránt részletesebben érdeklődők ezekről a csoportokról további információt a [TA] könyvben találhatnak.


Vissza

40




Vissza

41

Az MPP gépcsalád és a CRAY T3E szuperszámítógép Az MPP (Massively parallel processors, erősen párhuzamos processzorok) gépcsalád (lényegében üzenetátadásos multiszámítógépek) hatalmas, többmillió dolláros szuperszámítógépeket tartalmaz, amelyek a legsikeresebb SIMD-szuperszámítógépek mai utódai. Napjaink legnagyobb számításigényű feladatainál használják őket (például éghajlat-modellezés). Felépítésükben kevés rögzített szabályt alkalmaznak, általánosan a következőt mondhatjuk: az MPP-rendszerek lényegében önálló memóriával rendelkező processzorokból álló nagyszámítógépek, ahol a kapcsolat felépítésére speciális hardverelemeket használnak. Ez a kivitel az adatátvitelt nagyon meggyorsítja. Egyszerű esetben akár a sín topológia is alkalmazható. A gépek többsége hagyományos CPU-kat használ processzorként. Ilyenek lehetnek például: Intel Pentium, Sun UltraSPARC és DEC Alpha. Egyes MPP-rendszerekben a közös memóriát is szimulálják. A CPU-k nagy száma és az óriási adatforgalom miatt a rendszerekben időnként hibák is előfordulnak, ezeket speciális hardver- és szoftverelemekkel figyelik és javítják.

Az MPP-rendszerek vázlatos felépítése A Cray T3E gépcsalád tagjai (T3E, T3E-900, T3E-1200) valamennyien erősen párhuzamos számítógépek, a processzorok száma 2048-ig terjedhet. Az 1200-as széria DEC Alpha processzorokból épül fel (300-600 MHz), a teljes rendszer memóriája maximum 4 TB. A gyors kommunikáció érdekében processzorait háromdimenzióban két irányú kommunikációra alkalmas tóruszok kapcsolják össze. A processzorok távoli memóriához is hozzáférhetnek, a nem saját memória elérésének ideje maximum hatszorosa a saját memória elérésének. A rendszerbeli hibák kiküszöbölésére segédcsomópontokat alkal-


Vissza

41



42

maznak, ezek egyszerűen „kiváltják” az aktuálisan hibás csomópont szerepét. A teljes rendszert egy speciális UNIX operációs rendszer működteti.

A processzorok közötti lehetséges hálózatok A korábbiakban már volt szó arról, hogy a sokprocesszoros rendszerek felépítéséhez elengedhetetlenül szükséges a processzorok közötti hatékony kapcsolatok kialakítása. Ideális esetben minden processzor minden memóriaegységgel közvetlen kapcsolatban van, de ezt csak viszonylag kis számú elem esetén tudjuk hatékonyan megvalósítani. Ilyenkor ugyanis az összekötő hálózat bonyolultsága a processzorok számának a négyzetével nő, ez például 1000 elem esetén kb. 500 000 összeköttetést jelentene. A gyakorlatban három különböző típusú rendszer használatos: • hálózat ♦ A processzorok valamilyen hálózat segítségével vannak egymással kapcsolatban. Ez direkt összeköttetést jelent valamely környezetükkel, míg a távolabbi elemeket hosszabb úton érik el. • busz ♦ A processzorok egy buszrendszeren keresztül kommunikálnak egymással. Egyszerű esetben ez csak a sín topológia. • kapcsoló berendezés ♦ A processzorok és a memóriák két tengelyre vannak felfűzve mátrixszerű összeköttetésben (például: x tengely memóriák, y tengely processzorok), és minden processzor minden memóriát elérhet. példa: HEP – Heterogenius Element Processor, 1978 – 4 processzor + memória, 1984 – 16 processzor + memória. Az utóbbi évek tapasztalatai alapján a legígéretesebb összeköttetési módszer a hálózatos. Az ideális összeköttetés kiválasztásához több szempontot kell mérlegelni, közülük néhány: • Mennyi egy adott csomópont kapcsolatainak a száma (az ún. terhelhetőségi szám)? • Hiba esetén mekkora a lehetséges alternatív utak száma (hibatűrő-képesség)? • Mekkora a két legtávolabbi csomópont közötti távolság (a hálózat átmérője)? • Mekkora a hálózat áteresztőképessége?


Vissza

42



43

A fenti szempontok mérlegelésével a hálózati topológiák tervezéséhez gráfelméleti ismeretek is szükségesek. A leggyakoribb hálózattípusok a következők: • lineáris és ciklikus ♦ Olyan esetekben hatékony, amikor egy processzor korábbi processzorok által előállított adattal dolgozik tovább. Egyszerű példák: Fibonacci-szerű sorozatok előállítása, összeadás-szorzás kombináció. A lineáris hálózatot visszakapcsolva ciklikus hálózatot kapunk. • keverő hálózat ♦ n = 2k darab csomópontot tartalmaz, a csúcsokat 0tól sorszámozzuk. Összeköttetések: 2i. csúcs ↔ 2i + 1. csúcs, i. csúcs → 2i. csúcs (mod n – 1), ahol az utolsó csúcsból önmagába megy él. Ezen összeköttetés következtében bármely processzorból bármely másikba viszonylag rövid úton eljuttatható információ, miközben az élek száma nem túl nagy. A hálózat onnan kapta a nevét, hogy egy pakli kártyát ily módon néhány lépés alatt tökéletesen megkeverhetünk, k lépés után pedig visszaáll a kezdő állapot. Ezt a kapcsolást például a transputereknél alkalmazzák, de más MIMD-gépeknél is jól használható. • fa hálózat ♦ Az egyik legegyszerűbb típusú gráf, hierarchia megvalósítására használják. Elsősorban a következő feladattípusoknál célszerű használni: rendezés, visszakeresés, algebrai kifejezések kiértékelése. Egyes feladatoknál teljes bináris fa helyett hiányos változatok is használhatók. • síkbeli háló ♦ Ebben az elrendezésben az n2 processzor mindegyike 4 szomszéddal áll kapcsolatban. Sokszor visszahurkoltan is használják (utolsó sor vissza az elsőhöz). Ilyen struktúra például mátrix-vektor szorzatok kiszámítására használható hatékonyan. • piramis háló ♦ A bináris fa struktúra térbeli megfelelője, gúlaszerű szerkezettel. • pillangó hálózat ♦ (k + 1)*2k darab csomópontot tartalmaz k + 1 sorban. Nevét onnan kapta, hogy az elrendezés kiterjesztett pillangószárnyhoz hasonlít. Az összekötés szabálya: az (i, j) csúcsot az (i + 1, j) és a (i + 1, j’) csúccsal kötjük össze, ahol j’-t a j szám i-edik bitjének a negálásával kapjuk. • hiperkocka hálózat ♦ A hálózatot úgy készítjük el, hogy n dimenziós koordináta-rendszerben koordinátázzuk a csúcsokat (például (0, 0), (1, 0), (0, 1), (1, 1)). Azon csúcsok vannak összekötve, amelyek sorszáma csak 1 bitben különbözik. A kapcsolással már részletesen foglalkoztunk


Vissza

43




Vissza

44

az SIMD gépcsaládnál. Az MIMD-gépeknél is nagyon népszerű ez az összeköttetési forma, jelenleg n≤10 használatos. • hiperkockába kapcsolt ciklikus hálózatok ♦ A hiperkocka-hálózat változata, ahol a csomópontok maguk is kis ciklikus hálózatot alkotnak. Hány lépés szükséges bináris fa struktúrájú hálózat esetén 2n proceszszorral ugyanannyi elem összeadásához? (1,5) Határozzuk meg a síkbeli hálózat átmérőjét n×n processzor használata esetén visszahurkolás nélkül, illetve visszahurkolással. (2) Rajzoljuk le a keverő hálózatot n = 8 esetben.

(2,5)

Rajzoljuk le a pillangó hálózatot k = 3 esetben.

(2)

Határozzuk meg az n-dimenziós hiperkocka-hálózat átmérőjét.

(2)

Készítsünk terveket, hogy a felsoroltakon kívül még milyen jellegű párhuzamosítható feladatokat lehet hatékonyan megoldani a fenti hálózatokkal. (2,5–5) Készítsünk új hálózatterveket egyes párhuzamos feladatok optimális megoldására. (4–5)


Vissza

44



A párhuzamos programozás fogalma


Vissza

45

A párhuzamos programozás fogalma A szekvenciális programozás jellemzői A napjainkban is széles körben használt egyprocesszoros számítógépek a Neumann-elvet követik, amely szerint a processzor egyszerre csak egy utasítást hajt végre, és a végrehajtási sorrend előre meghatározott: mindig meg tudjuk mondani, hogy mi volt az előző utasítás és mi lesz a következő. Egy magas szintű programnyelven írt program valamely egyszerű részlete – egyelőre elágazások és ciklusok nélkül – a következő utasítássorozattal reprezentálható: P; Q; R

Ebben a szemléltető példában P, Q és R egyes utasítások (például értékadások) vagy utasításcsoportok lehetnek. A program minden futtatására teljesül, hogy a P rész végrehajtása megelőzi Q végrehajtását, és Q végrehajtása megelőzi R végrehajtását (jelölés: P → Q → R). Azt a jellemzőt, ami minden futtatásra teljesül, a program tulajdonságának nevezzük. Gépi szinten minden utasításcsoport, ami P-ben, Q-ban, illetve R-ben van, felírható elemi utasítások sorozataként. Így minden futtatásra az is teljesül, hogy p1 → p2 → p3 → … → pm → q1 → q2 → … → qn, tehát elemi szinten sem lehet átfedés az utasítások részei között. Igaz továbbá, hogy az elemi utasításokra fennáll a teljes rendezettség, azaz két elemi utasítás sorrendje minden futtatásra ugyanaz: előre meg tudjuk mondani, hogy x → y vagy y → x teljesül minden esetben. Első megközelítésben azt gondolhatjuk, hogy ez a logikai rendszer sérül abban az esetben, ha a programban ciklusok és elágazások is megengedettek.


Vissza

45


A párhuzamos programozás fogalma Vissza

46

Elágazások beépítése Az elágazások ugyan különböző végeredményt adhatnak különböző végrehajtások esetén, de azonos input adatokkal mindig ugyanazt az eredményt kell produkálniuk. Minden konkrét futtatáskor az elágazásnak csak egy ága él, tehát egy végrehajtás során az elágazás tökéletesen beépíthető az eddigi logikába. Ciklusok beépítése A ciklusok feladata egy bizonyos részfeladat egymás után többszöri (előre meghatározott, vagy nem meghatározott számú) lefuttatása. Az ismétlődő részeket kifejtjük egymás után sorba, így megint egy olyan utasításlistát kapunk, amelyben az utasítások szigorúan követik egymást a fenti rendszer szerint. Minden futtatásra igaz lesz, hogy a P ciklus i-edik végrehajtása mindig megelőzi Q ciklus i-edik végrehajtását, továbbá az is teljesül, hogy a Q ciklus i-edik végrehajtása mindig megelőzi a P ciklus i + 1-edik végrehajtását. Tehát minden futtatásra igaz, hogy Pi → Qi, és Qi → P(i+1). Hasonlóan beépíthetők a rendszerbe az eljárás- illetve függvényhívások is, ezzel pedig a stuktúrált programtervezésben használatos összes szerkezeti elemet beépítettük. Nem foglalkoztunk a nemstrukturált programokban előforduló egyéb szerkezetekkel (például goto-szerű műveletek). Ennek oka az, hogy elméletileg igazolható, hogy minden nemstrukturált program átírható az eredetivel ekvivalens struktúrálttá, azaz a nemstrukturált elemek egy tetszőleges programból a helyes működés fenntartásával kiküszöbölhetők (BőhmJacobini tétel). Összefoglalóan, a Neumann-elveknek megfelelően a következőket mondhatjuk: • egy szekvenciális programban a szövegbeli elhelyezkedés meghatározza a végrehajtási sorrendet; • az utasítások között nem lehet átfedés elemi szinten sem, tehát egy szekvenciális program utasításai teljesen rendezettek; • a szekvenciális program determinisztikus, azonos bemenő adatokra mindig azonos az utasítások végrehajtási sorrendje és az eredmény is.


Vissza

46



47

Fontos megjegyezni, hogy ezek a megállapítások bármely mai és régebbi, magas- és alacsonyszintű szekvenciális programozási környezetben érvényesek. A fentiek alapján a szekvenciális program végrehajtása egy egyenesen szemléltethető, mint a következő ábrán láthatjuk:

Az a kijelentés, hogy egy szekvenciális program azonos adatokra azonos eredményt szolgáltat, hardver okok miatt néha kismértékben sérülhet. Adjunk meg ilyen példákat. (2) Eltérés figyelhető meg a számok tárolása kapcsán például a 16 bites, illetve 32 bites rendszerekben. Lebegőpontos adatok kerekítése is eltérhet architektúráktól függően, ez az eltérés azonban nagyon kicsi. Az előző fejezetben szerepelt a pipeline-technika, amely szerint a processzor egyes részei képesek egymással párhuzamosan működni. Nem sérti-e ez a Neumann-elvet? (2,5) A programkészítő szempontjából nem (és ez a döntő), hiszen ő továbbra is meghatározott utasítássorrend szerint készíti a programot elemi szinten is, a hagyományos Neumann-elvű tervezést követve. A részegységek működését külön-külön tekintve szintén nem, hiszen egy részegységen belül fix végrehajtási sorrend van meghatározva. Összgépi szempontból viszont kis mértékben sérül az elv.

Elszakadunk a szekvenciális programozástól… Most tegyük fel, hogy sok processzor áll a rendelkezésünkre. A szekvenciális megközelítés ekkor nem minden esetben hatásos, illetve szükségszerű. Például tekintsük a következő egyszerű programrészletet: X:=0; Y:=0; Z:=0

(* P *) (* Q *) (* R *)


Vissza

47



48

Ez esetben nem kell betartani a P → Q → R sorrendet, hiszen az értékadások egymástól függetlenek, így tetszőleges sorrendben végrehajthatók. A három programrész futhat azonos időben akár három különböző processzoron. Ha sorrendiséget állapítanánk meg közöttük, az túlspecifikálás lenne, azaz olyan megkötés, amely az algoritmus logikájából nem következik. Ugyanakkor ez a megközelítés nem alkalmazható teljesen szabadon minden esetben. Vannak olyan programrészek is, ahol fontos rögzíteni a végrehajtás sorrendjét, még akkor is, ha több processzor áll a rendelkezésünkre. Ezek a részek akár értékadások is lehetnek, ha például az egyik változó értékéből következik egy másik változó értéke: X:=10; Y:=X*2;

(* P *) (* Q *)

Általánosan tehát egy programban bizonyos esetekben megengedjük a párhuzamos végrehajtást, máshol pedig rögzítenünk kell a végrehajtási sorrendet az algoritmus logikája szerint. Lényeges, hogy ezt a rögzítést csak ott végezzük el, ahol feltétlenül szükséges. A párhuzamos végrehajtás lehetőségének jelölésére egy új nyelvi struktúrát vezetünk be: cobegin … coend, ahol a „co” a concurrent (párhuzamos) szó rövidítése. A cobegin … coend részben megengedett (de nem kötelező) a párhuzamos végrehajtás. Teljesen hasonlóan, egyes párhuzamos programozási nyelvekben használatos még a parbegin … parend struktúra is (a paralel szóból). Egy egyszerű párhuzamos programrészlet lehet a következő: J; K; cobegin P; Q; R coend; L; M

//concurrent begin //itt nincs sorrendi megkötés, a végrehajtás //lehet párhuzamos


Vissza

48




Vissza

49

A programrészlet minden futtatására igaz, hogy J → K → (cobegin … coend) → L → M, míg a cobegin … coend struktúrán belül megengedett a párhuzamos végrehajtás. A programozási nyelvektől elszakadva ezt jelölhetjük a következő módon: P || Q || R, ahol || a párhuzamossági operátor. Ez az operátor mindig többoperandusú, csak legalább két operandus esetén van értelme használni. A párhuzamossági operátor jellemzői: • Kommutatív, azaz felcserélhető, tehát ha P || Q, akkor Q || P. • Asszociatív, azaz átcsoportosítható, tehát ha (P || Q) || R, akkor P || (Q || R). • Tranzitív, tehát ha P || Q és Q || R, akkor P || R. Érdemes megjegyezni, hogy az operátor bizonyos fontos műveleti tulajdonságokkal nem rendelkezik, például nem reflexív, így nem ekvivalencia-reláció. Vizsgáljuk meg, hogy a fenti → operátor milyen tulajdonságokkal rendelkezik. (1) A cobegin … coend struktúra természetesen bonyolultabb módon is használható, mint a fenti egyszerű példában. Kézenfekvő, hogy több ilyen szerkezet is elhelyezkedhet egy párhuzamos programban, sőt egyes párhuzamos nyelvek megengedik ezen struktúrák egymásba ágyazását is. Az ezzel kapcsolatos nehézségekkel később részletesen foglalkozunk. A gyakorlatban nem mindig áll több processzor a rendelkezésünkre, vagy nem annyi van belőlük, ahány programrészletet párhuzamosan szeretnénk futtatni, ráadásul ez programrészenként változhat. Tehát általánosan nem tudunk egy-egy processzort hozzárendelni minden párhuzamosan futtatandó programrészlethez – ezeket a részeket a továbbiakban folyamatoknak (más elnevezések: taszk, néha processzus, az angol task illetve process szavakból) nevezzük. A hordozhatóságot és az univerzális működést úgy kell biztosítanunk, hogy a cobegin … coend struktúrának legyen értelme akárhány, akár egyprocesszoros rendszerben is. Így P || Q számunkra általánosan azt jelenti, hogy van olyan futtatás, amelyre igaz, hogy not (P → Q) and not (Q → P).


Vissza

49



50

Egyprocesszoros rendszerben tehát megengedett az átfedés, de az nem kötelező, míg többprocesszoros rendszerben megengedett a párhuzamos végrehajtás, de ez sem kötelező. Ideális esetben megvalósul a teljes a párhuzamos végrehajtás. A folyamatok számára fizikai processzorok helyett logikai processzorokat vezetünk be. A logikai processzor fizikailag egy szekvenciális processzornak tekinthető, de a logikai-fizikai megfeleltetéssel mi nem foglalkozunk, ez implementációs kérdés. Elméleti szinten hozzárendeljük az egyes folyamatokat egy-egy logikai processzorhoz, és rábízzuk a programozási nyelv készítőire, hogy ezt hogyan osztják be a fizikai processzorok között. Ha csak egy folyamat van, akkor a leggyorsabb fizikai processzort célszerű hozzárendelni, míg egyprocesszoros rendszerben értelemszerűen valamely időosztásos módszerrel dolgozhatunk. A logikai processzorok tulajdonságairól a fentiek miatt általánosan csak keveset tudunk mondani, hiszen megvalósításuk nagyon változatos lehet. • Sebességükre egymáshoz képest nincs megkötés, hiszen a konkrét fizikai processzorok sebességét sem ismerjük. Ráadásul lehetnek „peches” folyamatok, amelyek belátható időn belül nem kerülhetnek végrehajtásra, és az éhezés állapota lép fel. • Hasonló indokok miatt csak nagyon laza kapcsolat van logikai proceszszorok futási ideje és a valós idő között. Egyprocesszoros rendszerben például időosztásos megoldást szoktak alkalmazni, és így nehezen mondható meg, hogy egy folyamat mikor fejezi be a futását, hiszen ez az ütemezőtől is függ. Néha szükséges a kapcsolatok szorítása (valós idejű rendszerek esetében), erre vannak megfelelő eszközeink (időkezelés, lásd később).

Részben rendezettség a párhuzamos programozásban Mit tudunk mondani ezek után egy cobegin … coend közötti programrész végrehajtásáról? cobegin P; Q; R coend;


Vissza

50



51

Elvileg bármilyen P, Q, R sorrend megengedhető, tehát 6 különböző eset fordulhat elő, ha a lehetséges átfedésektől eltekintünk: Q -> R -> P R -> Q -> P P -> Q -> R ...

Általános esetben a végrehajtás csak egy folyamaton belül szekvenciális, de a folyamatok között lehet átfedés. Így P egy elemi utasítása és Q egy elemi utasítása futhat egymással párhuzamosan is. Tehát minden futtatásra igaz, hogy i<j esetén pi → pj, azaz P maga determinisztikus, ugyanakkor not (minden futtatásra: pi → qj) and not (minden futtatásra: qj → pi). Így a párhuzamos program végrehajtási sorrendje egyes részeken rögzített, más helyeken nem, azaz végeredményben a program csak részben rendezett. Azonban nem korlátozzuk magunkat önként, csak akkor mondunk le a végrehajtási sorrend szabadságáról, ha szükséges. A párhuzamos program lehetséges végrehajtásait egy bonyolult nagy fával szemléltethetjük, amelynek egyes ágait levágjuk, és a struktúra annál bonyolultabb, minél több proceszszor áll a rendelkezésünkre. Egy cobegin … coend közötti programrészben két folyamat helyezkedik el (a és b), mindkettő három elemi utasítást tartalmaz. Hányféle végrehajtási sorrend lehetséges egyprocesszoros környezetben? a: a1, a2, a3 b: b1, b2, b3 cobegin A; B coend;


Vissza

51




Vissza

52

A teljes megoldás egy részletét az ábrán láthatjuk, de nemcsak rajzos úton kaphatjuk meg a lehetőségek számát. Az elméletileg lehetséges 6!-féle sorrendből ki kell zárni azokat, amikor az a1 → a2 → a3 és a b1 → b2 → b3 végrehajtás sérülne (ismétléses permutáció). Így a megoldás: 6! / (3! * 3!) = 20. Hogyan változik a helyzet, ha kétprocesszoros környezetben dolgozunk? Segítség: itt három lehetőség megengedett az első szinten: a1, a1 || b1 és b1. Az elemzés hasonlóan folytatható lefelé haladva. (3) Összefoglalva az eddigieket, a párhuzamos programban • a szövegbeli elhelyezkedés nem határozza meg a műveleti sorrendet; • a műveletek átfedhetik egymást; • különböző rendezettség tapasztalható különböző futtatások esetén, tehát a párhuzamos program nemdeterminisztikus. Mindez a párhuzamos nyelv programozója számára meglepő következményekkel jár. A legfurcsább ezek közül talán az, hogy egy párhuzamos program azonos input adatokkal általában különböző eredményt ad (egyszerű példa: betűkiíratás [lásd később CHAOUT.PFC]). Párhuzamos környezetben a hibák sokkal veszélyesebbé válnak azáltal, hogy nehéz őket felderíteni. Egy nagy végrehajtási fa esetében gyakran előfordulhat, hogy egy-két „pici” hibás ág bennmarad a programban. Nyilván nagyon kicsi az esélye, hogy a program oda ténylegesen be is fog futni, de gyakorlati teszteléssel ez nem zárható ki: akár 1000 hibátlan végrehajtás után is bekövetkezhet egy hibás. Ilyenkor tehát a hibák elméleti előfordulását kell megakadályozni.

A párhuzamos programozás motivációja Természetesen adódik a kérdés, hogyha párhuzamos környezetben ilyen „nehéz az életünk”, akkor miért akarunk mégis párhuzamosan programozni? A következőkben néhány fontos indokot mutatunk be (ilyeneket nyilván mindenki önállóan is fel tudna sorolni).


Vissza

52



53

1. Van több processzorunk, és szeretnénk őket egyidejűleg használni a végrehajtás felgyorsítására. A folyamatokat szétosztjuk a processzorok között (független problémák). Egyszerű példa: ki kell számolnunk egy tömb elemeinek összegét és négyzetösszegét. cobegin total := sum(data) (*ezt odaadjuk a lassabb processzornak, a másikat a gyorsabbnak*) totatsqr := sumsqr(data) coend

2. Célunk a processzor teljesítőképességének jobb kihasználása. Egy program önmagában általában nem tudja optimálisan kihasználni a processzort. Például a futtatás során vannak olyan pontok, amikor input-output műveleteket kell végrehajtani. Mivel az input-output eszközök elérése a processzor műveletvégző-képességéhez képest lassú, így a processzor sokszor várakozni kényszerül. Mindenképpen hasznos, ha a várakozás alatt átkapcsoljuk egy másik feladat megoldására, azaz lényegében a processzorhoz egyidőben több feladatot is rendelünk. A feladatoknak időnként várakozniuk kell a végrehajtásra, tehát az egyes feladatok végrehajtási ideje megnőhet, de a rendszer összteljesítménye javul. Ugyanezen elven alapul a multiprogramozás is, amely a kisszámítógépek megjelenéséhez köthető. Ezek a gépek valójában nem olyan kicsik, és egy felhasználó nem tudta/tudja kihasználni a gép nyújtotta lehetőségeket. Ezért a számítógépet terminálokon keresztül több felhasználó használta egyszerre. Időnként előfordult, hogy a felhasználónak várakoznia kellett egy program végrehajtására, de általában ez nem jelentett fennakadást. Operációs rendszerekben is alkalmazzák az időosztásos technikát a párhuzamos programfuttatás szimulálására, például Windows környezetben is. Látszólag több program fut a gépen egy időben, de igazi párhuzamos végrehajtás nyilván nem lehetséges, hiszen csak egy processzorunk van. A valóságban a programok időszeleteket kapnak és időosztásos megoldással működnek. Amennyiben a rendszer terheltsége maximális,


Vissza

53



54

előfordulhat a drasztikus teljesítményzuhanás, esetleg az operációs rendszer összeomlása is. 3. A teljes rendezettség logikailag nem megfelelő modell egyes problémák esetében. A végrehajtási sorrendet sok esetben külső események is befolyásolhatják, azaz a probléma lehet alapjában véve nemdeterminisztikus és párhuzamos. Ilyen feladatokra igen nehézkes lenne szekvenciális megoldást adni. Például a közlekedési lámpának érzékenynek kell lennie az éppen várakozó járművekre és gyalogosokra. Ilyen problémákkal még sokat foglalkozunk, például a következő alfejezetben is. Mindez nem azt jelenti, hogy párhuzamos gépeket használva elméletileg több problémát tudunk megoldani. Bizonyítható, hogy a PRAM-gépmodellben pontosan ugyanazon problémák oldhatóak meg véges idő alatt, mint egy Turing-gépen. A végrehajtási időben és a megoldás bonyolultságában azonban igen jelentős különbségek lehetnek.

Egy beágyazott rendszer szimulációja szekvenciális környezetben A beágyazott rendszer egy kis számítógép, amely egy nagyobb, bonyolultabb valós idejű rendszer működését segíti. Ilyen például repülőgépeknél a robotpilótát kiszolgáló több kisebb részegység (magasságmérő, szélerősség, stb. leolvasása és feldolgozása), továbbá gépjárműveknél a vezetőt kiszolgáló egyes automatikák. Mostani egyszerű példánkban tegyük fel, hogy csak egy processzorunk van, és ezen szeretnénk 3+1 taszkot periodikusan működtetni (A, B, C és D, de a negyedik taszkot egyelőre nem vizsgáljuk). Szekvenciális megoldással próbálkozunk, majd rámutatunk, hogy esetünkben ez nem szerencsés. Első megközelítés: repeat DEAL_WITH_A; DEAL_WITH_B; DEAL_WITH_C; forever


Vissza

54




Vissza

55

Ez a megközelítés több problémát is felvet. Ezek ugyan valóban periodikus folyamatok, de lehetnek gondok az időzítéssel. Például, ha az A folyamat a benzinszint kijelzését végzi, míg a B folyamat a kormány állását ellenőrzi, akkor látható, hogy az előbbit elég akár félpercenként frissíteni, ám az utóbbit ennél jóval gyakrabban, akár századmásodpercenként is szükséges. Tehát az iménti megközelítést finomítani kell. Semmiképpen nem fogadhatjuk el azt a „megoldást”, hogy nem hajtunk végre egy tevékenységet idejében, mert ez nem biztonságos. A következő lehetőség az, hogy beállítjuk a végrehajtási ciklus idejét a szükséges legrövidebb időre, és mindig megnézünk mindent, tehát például minden századmásodpercben megnézzük a benzinszintet és a kormányt is. Ebben az esetben pazaroljuk ugyan az erőforrásokat, de rosszabb esetben az is előfordulhat, hogy a feladat végrehajthatatlan lesz, nem tud a megszabott időn belül lefutni. Tegyük fel például, hogy az egyes műveleteket az alábbi kis táblázatnak megfelelően kell bizonyos időközönként végrehajtani, és futási idejük a következő: Taszk A B C

Időköz 20 40 80

Futási idő 4 10 40

Az időegység nem meghatározott (lehet például századmásodperc). Ezeket a feltételeket csak úgy tudnánk teljesíteni, ha a teljes ciklus 20 időegységenként lefutna. Ez B szempontjából nyilván pazarlás lenne, C végrehajtására pedig már nem jutna idő, mert 20 időegység múlva újra az A taszk kezdődne. A futási időt azonban egy-egy taszk esetén széttördelhetjük. Tegyük fel, hogy egy periódusra 80 egységnyi idő jut. Ekkor: A-nak kell 4×4=16 (mivel 80/20=4, azaz négyszer hajtódik végre a 80 egység alatt), B-nek kell 2×10=20, C-nek kell 1×40=40. Ezzel összesen 76 időegységet foglalnak le a folyamatok. Lehetséges megoldás, ha a C folyamat futását felosztjuk, és ha szükséges, megtesszük ugyanezt a B-vel is.


Vissza

55




Felhaszn. idő 0 4 14 20 24 40 44 54 60 64 76 80

Taszk (-rész) A B C-1 A C-2 A B C-3 A C-4 nyereség

Vissza

56

Időigény 4 10 6 4 16 4 10 6 4 12 4

Tényleges megvalósítás: repeat DEAL_WITH_A; DEAL_WITH_B; DEAL_WITH_C_1; DEAL_WITH_A; DEAL_WITH_C_2; DEAL_WITH_A; DEAL_WITH_B; DEAL_WITH_C_3; DEAL_WITH_A; DEAL_WITH_C_4; (* 4 egységig alvás *) forever

Ez a megvalósítás ugyan működik, de az ütemezést nekünk kell biztosítani, és így a kódot nehéz fenntartani, mert idő- és hardverfüggő (például egy másik gépen nem ugyanannyi a ciklusidő). Nem foglalkoztunk még a D folyamattal. Legyen ez egy aperiodikus (periódushoz nem kötött) taszk, például a biztonsági övek rögzítése. Az ilyen feladatokat ritkán, de akkor gyorsan kell végrehajtani, és maguk a feladatok rövid ideig tartanak. Külső esemény váltja ki ezt a hatást (például


Vissza

56



57

erős fékezés), és utána a normál működést folytatni kell, nem engedhetjük meg a rendszer összeomlását (a legtöbb erős fékezés semmilyen káros következménnyel nem jár az autóra nézve). Ugyanakkor ezek az események nem fordulhatnak elő túl gyorsan egymás után: a fékezés után az autó megáll, az újbóli felgyorsuláshoz idő kell. A feladat tehát – jellege miatt – egy ideje nagy részét alvással töltő folyamattal reprezentálható, amely szükség esetén ébresztést (alarm) igényel. Ekkor várakozás nélkül, gyorsan végre kell hajtani, befejezéskor pedig küld egy jelet (clear) a vezérlőnek, hogy folytatható a normális működés. Esetünkben feltehetjük, hogy az ébresztés 1 időegység alatt történik, a taszk végrehajtása 2 időegységet igényel, és a clear jelet szintén 1 időegység alatt küldi el. Megkötjük, hogy 80 időegységenként csak egy ilyen eset fordulhat elő, így pont beleférünk a rendelkezésre álló 80 időegységbe (76+4). Mivel azonban nem tudjuk, hogy a feladatot mikor kell végrehajtani, egy hagyományos szekvenciális megoldásban minden 1-2 időegységben vizsgálni kellene D-t, ez a megközelítés tehát biztosan nem alkalmazható (megszakításokkal persze még így is boldogulnánk). Végeredményben tehát a szekvenciális megoldással kudarcot vallottunk ugyan, de látjuk, hogy párhuzamosan viszonylag egyszerűen meg fogjuk tudni oldani ezt a problémát (lásd később). A leendő párhuzamos megoldástól elvárjuk a következőket: • a folyamatok párhuzamosan futnak A-tól D-ig; • D-t kivéve ciklikusak; • a periodikus folyamatok időbeli megkötést igényelnek (prioritások hozzárendelése); • az aperiodikus folyamatok ébresztést igényelnek, máskülönben alszanak. Ez a példa valós idejű rendszert szimulál, ezért a logikai processzorok futási idejét kapcsolatba kellett hozni a valós idővel.


Vissza

57



58

Problémák a párhuzamos programozásban Az eddigiekben a párhuzamos végrehajtással kapcsolatban feltettük, hogy: • egy folyamathoz egy logikai processzor tartozik; • egy folyamaton belül megköveteljük a szekvenciális végrehajtást; • különböző folyamatok elemi részeinek végrehajtási sorrendje egymás között nem meghatározott. Kis gondolkodás után láthatjuk, hogy az utolsó feltevés általánosan nem lehet érvényes: sok esetben logikai hibához vezet az, ha az elemi részek között minden futtatási sorrend megengedett. Általában azt mondhatjuk, vannak logikailag megengedhető és nem megengedhető futtatási sorrendek. A hibás futtatási ágak megkeresését és kizárását folyamatszinkronizációnak nevezzük. A párhuzamos programban a folyamatoknak általában kommunikálniuk kell egymással a működés során, a közös cél elérése érdekében. A kommunikáció és szinkronizáció megvalósítása a legfontosabb tevékenységek közé tartozik a párhuzamos programozásban, mi is kiemelten foglalkozunk velük. A következő példa rávilágít arra, hogy milyen nehézségekkel szembesülünk és milyen megfontolásokat teszünk a hibás futtatási ágak kizárása közben.

A helyfoglalási probléma Ebben a feladatban egy jegykiadó iroda működését szimuláljuk. Egy központi számítógép nyilvántartja az adatokat a pillanatnyi helyzetnek megfelelően, az ügyfelek az igényeket n darab – egymástól akár nagy távolságra elhelyezkedő – terminálon jelenthetik be. Első megközelítés: cobegin HANDLER1; HANDLER2; ... HANDLERn coend


Vissza

58




Vissza

59

Egy handler (kezelő) eljárás vázlata a következő: repeat ülésrend megjelenítése; read(CLIENT_CHOICE); SEAT[CLIENT_CHOICE] := RESERVED; jegy kiadása forever

Azonnal látható, hogy ez a megoldási kísérlet megengedi az egyidejű jegykiadást, sőt akár egy már kiadott hely újbóli kiadását, szándékosan vagy véletlen mulasztás miatt. A következőkben ezt a fogyatékosságot javítjuk. 2. megközelítés (csak a handler eljárás): repeat if SOLD_OUT then begin kijelzés; várakozás további utasításra end else begin SUCCESS := false; repeat ülésrend megjelenítése; read(CLIENT_CHOICE); if SEAT[CLIENT_CHOICE] = FREE then begin SEAT[CLIENT_CHOICE] := RESERVED; SUCCESS := true; jegy kiadása end else hibaüzenet until SUCCESS end forever

Az ellenőrzés következtében itt már véletlen vagy szándékos kezelői hiba miatt nem lehet gond, de más okok miatt mégis történhet egyidejű jegyki-


Vissza

59



60

adás. Képzeljük el például, hogy két távoli terminálon közel azonos időben akarnak ugyanoda helyet foglaltatni: • • • •

Handler1: ellenőrzi SEAT[K]-t, és annak állapota FREE Handler2: ellenőrzi SEAT[K]-t, és annak állapota FREE Handler1: beállítja SEAT[K] értékét RESERVED-re Handler2: beállítja SEAT[K] értékét RESERVED-re

A probléma oka az, hogy a számítógép az if-then-else szerkezetet kisebb részekre bontva kezeli, mi viszont a megoldási kísérletben ezt figyelmen kívül hagytuk. Az iménti részfeladat gépi kódú vázlata a következő: SEAT[CLIENT_CHOICE] betöltése a CPU regiszterbe CPU regiszter vizsgálata ugrás L1-re ha RESERVED SEAT[CLIENT_CHOICE] átállítása RESERVED-re SUCCESS átállítása TRUE-ra jegykiadás kódja ugrás L2-re L1: hibaüzenet kódja L2: az if szerkezetet követő rész kódja

Ezek az elemi utasítások a gép szempontjából oszthatatlan részek, ún. atomi akciók. Egy ilyen művelet végrehajtása során a vezérlő nem veheti el a futási jogot egy folyamattól, csak előtte vagy utána. A megoldás során tehát azt kell biztosítanunk, hogy az adott ülőhely vizsgálata és annak foglaltra állítása közben a vezérlő ne adhassa át a futási jogot egy másik folyamat ugyanilyen programrészletének. Ezzel egy mesterséges atomi akciót hozunk létre. A programrészletben ezt < és > jelekkel jelöltük. Így kizárjuk a rossz végrehajtási sorrendeket. Gépi kódú vázlat: < SEAT[CLIENT_CHOICE] betöltése a CPU regiszterbe CPU regiszter vizsgálata ugrás L1-re ha RESERVED SEAT[CLIENT_CHOICE] átállítása RESERVED-re > SUCCESS átállítása TRUE-ra jegykiadás kódja ugrás L2-re


Vissza

60




Vissza

61

L1: hibaüzenet kódja L2: az if szerkezetet követő rész kódja

Azt a programrészletet, amely egy külső folyamat számára (mesterséges) atomi akcióként jelenik meg, kritikus szakasznak (critical section) nevezzük. Mivel két vagy több folyamat kritikus szakaszainak egyidejű vagy átlapolt futtatása hibás eredményre vezetne, ezért a kritikus szakaszok csak kölcsönös kizárással (mutual exclusion) hajthatók végre. A kritikus szakaszok végrehajtása még így sem teljesen rendezett, mert lefutásuk sorrendjére nincs megkötés. Minden futtatásra igaz tehát, hogy (CSiP -> CSjQ) vagy (CSjQ -> CSiP). Ugyanakkor kritikus szakaszok és nemkritikus szakaszok futtathatók párhuzamosan. A kritikus szakaszok határait (a fenti példában < és >) a program írása során nekünk kell beállítani valamely megfelelő nyelvi eszközzel. Erre szolgálnak majd a párhuzamos programozási nyelv szinkronizációs elemei. Nem megfelelő beállítások esetén a kölcsönös kizárás sérülhet, és ez súlyos programhibákhoz vezethet. A szinkronizációra és a kritikus szakaszok létrehozására meglesznek a megfelelő eszközeink (pl. szemaforok, lásd később), sőt látni fogjuk, hogy ez a védelem akár a hagyományos programozás elemeivel is megoldható. Általánosan érvényes, hogy a kritikus szakasz definiálásakor csak minimális korlátozást alkalmazunk, csak annyira korlátozzuk a szabadságunkat, amennyire ténylegesen szükséges. A cél az, hogy kizárjuk az összes logikailag hibás végrehajtási sorrendet, de a jó végrehajtási sorrendek közül az ütemező továbbra is teljesen szabadon választhasson. Így a kritikus szakaszt a lehető legrövidebbre tervezzük, ha felesleges részeket is belevennénk, azzal már romlana a hatékonyság. Emiatt a fenti példában a SUCCESS := TRUE beállítás már nem a kritikus szakasz belsejében szerepelt. A helyfoglalási probléma megoldására azt is kitalálhattuk volna, hogy a programozási nyelvben az if-then-else szerkezetet általánosan úgy írjuk meg, hogy annak megfelelő részei mindig csak kölcsönös kizárással legyenek végrehajthatók. Miért nem jó ez a megközelítés? (1,5)


Vissza

61




Vissza

62

Ezt a korlátozást nem alkalmazhatjuk általánosan minden if-then-else szerkezetre, mert sok probléma esetén ilyen korlátozásra egyáltalán nincs szükség. Egy ilyen programozási nyelv tehát túlspecifikált lenne.

A Pascal-FC alapjai A jegyzetben nagyrészt a Pascal-FC párhuzamos programozási nyelvet használjuk a példák bemutatására. Ezt a nyelvet részben egyszerűsége, részben pedig a szükséges kevés előismeret miatt választottuk. Egyszerűsége ellenére – mint látni fogjuk – alkalmas a párhuzamos programozás megfelelő tanulmányozására. Nagy előnye még, hogy szabadon másolható, viszonylag jó a futási teljesítménye és kevés helyet foglal. A Pascal-FC alapjául szolgáló Pascal-S nyelvet („ős-Pascal”) Nicholaus Wirth professzor fejlesztette ki, ez tulajdonképpen a mai Pascal egy részhalmaza. A nyelvből kimaradtak a következő funkciók: • • • • • •

fájlkezelés (de van standard I/O); WITH utasítás (de rekordok vannak); halmazok (van bitset – valós idejű alkalmazásokra); intervallumszűkítés; dinamikus tárolás, pointerek, new és dispose; packed azonosító, string típusú változó (konstans van).

A Pascal-FC természetesen sok új párhuzamos elemet tartalmaz, ezeket a későbbiekben tárgyaljuk. Ugyanakkor néhány nempárhuzamos plusz elemmel is bővítették ezt a nyelvet az alap Pascalhoz képest: • • •

repeat ... forever ciklus (tulajdonképpen repeat ... until false); null utasítás (üres tevékenység); random függvény (random(n) véletlen egész számot ad 0 és |n| között).

A programozási nyelv egyéb jellegzetességei: • kisbetű/nagybetű érzéketlenség, kivéve string és char; • a deklarációs sorrend nem megkötött (const, type, var, … – mi azért a példákban megtartjuk a hagyományos sorrendet).


Vissza

62



Folyamatreprezentáció és életciklus


Vissza

63

Folyamatreprezentáció és életciklus Folyamatmodellek párhuzamos programozási nyelvekben A párhuzamos programozási nyelvek tervezése meglehetősen bonyolult tevékenység. A tervezőknek sokféle szempontot kell mérlegelni, ahol egyegy tulajdonság gyakran csak egy másik kárára javítható. A következőkben áttekintjük a folyamatmodell legfontosabb jellemezőit, a választható lehetőségeket. 1. Struktúra A folyamatok struktúrája a következő lehet: a) statikus (a folyamatok száma futtatás előtt ismert); b) dinamikus (folyamatok dinamikusan létrehozhatók, csak futás közben derül ki a számuk); c) félstatikus („köztes verzió”, a folyamatok száma futás közben dől el, de egy maximális számot a definíciós részben előre meg kell adni). 2. Szint Itt a folyamathierarchia lehetőségei közül választhatunk: a) A folyamatok hierarchikusan egymásba ágyazhatók. Példa: Ada nyelv. b) Nincs egymásba ágyazás („lapos” folyamatstruktúra – egyszerűbb nyelvekben). Példa: Concurrent Pascal. Megjegyezzük, hogy annak ellenére, hogy ezen nyelvekben nem megengedett az egymásba ágyazás, mégis van egy speciális szülő-gyerek viszony, hiszen a főprogram az összes többi folyamat szülője. Ennek következménye például az a fontos, de nyilvánvaló tulajdonság, hogy amíg folyamat fut, addig a főprogram nem fejezheti be a futását. 3. Inicializálás Ha van ilyen lehetőség a nyelvben, akkor megengedett a nyelvi adatátadás a folyamatnak létrehozás közben. Ennek hiányában a szükséges kezdőér-


Vissza

63


Folyamatreprezentáció és életciklus Vissza

64

tékadásokat folyamatok közötti kommunikációval kell megoldani. Ez a lehetőség egy nyelvbe viszonylag egyszerűen beépíthető, ezért a legtöbb párhuzamos programozási nyelv tartalmazza. 4. Terminálás A párhuzamos nyelvek tervezői a következő lehetőségek közül választhatnak: a) sikeres befejezés (SUCCESS akció bekövetkezte); b) hibás befejezés (programhiba miatt, FAILURE akció bekövetkezte); c) belülről kikényszerített terminálás, „öngyilkosság” (belső FAILURE akció, suicide); d) más folyamatok által kikényszerített kilépés (külső FAILURE akció, abort); e) terminálás, mert nincs többé szükség rá; f ) sohasem terminál valamilyen hiba miatt; g) sohasem terminál szándékos végtelen ciklus miatt (repeat … forever ciklusnál). Nyilvánvaló, hogy a lehetőségek közül néhányat a „legszerényebb” képességű párhuzamos nyelveknek is tartalmazniuk kell, és nyelvi szintű kezelésük is viszonylag egyszerű – például a) és b) tulajdonságok. Egyes fajták megengedése viszont problémákat is felvet, és a nyelv tervezési bonyolultságát jelentősen megnöveli. Például a más folyamatok által kikényszerített kilépés veszélyes lehet, mert ha az őrfolyamat meghibásodik, akkor a helyesen működő folyamatokat is kiirthatja. Az e) pontnál nehéz lehet annak felismerése, hogy megengedhetjük-e már az adott folyamat terminálását. Különösen igaz ez akkor, ha a folyamatok egymásba is ágyazhatók – ha a szülő- és a gyerekfolyamatok is terminálni szeretnének, vagy a gyerekek már terminálnak, akkor egyszerre az egész struktúra terminálhat. Ilyen problémák bonyolult módon például az Ada nyelvben adódhatnak, de „lapos” folyamatstruktúra esetén is szülője a főprogram a folyamatoknak. 5. A folyamatok lehetséges nyelvi reprezentációi A következő lehetőségeink vannak (mindegyik megvalósítására vannak példák konkrét nyelvekben).


Vissza

64



65

I. A folyamatokat nem névvel azonosítjuk ♦ Ilyenkor szükséges párhuzamos végrehajtási utasítás, tehát cobegin ... coend (egyes nyelvekben parbegin ... parend) vagy más hasonló struktúra között felsoroljuk a párhuzamosan futtatandó nyelvi elemeket. Ha ezek az elemek bonyolultak, akkor eljárásokat kell használni. A párhuzamos struktúra működése ugyanaz, mint korábban, tehát a párhuzamosság csak lehetőség, nem kényszer. „Lapos” és egymásba ágyazott folyamatstruktúra egyaránt elképzelhető. Példa (egy ilyen nyelvbeli programrészlet): cobegin S1; begin s2; cobegin s3; s4 coend s5; end; s6; coend

A folyamatok végrehajtását ebben a példában a következő precedencia gráf szemlélteti:


Vissza

65



66

II. Van explicit folyamatazonosítás ♦ Ekkor a folyamatokat névvel azonosítjuk. Példa: var P1, P2: ProcType;

Ilyenkor lehet, de nem feltétlenül szükséges külön párhuzamos futtatási utasítás. II./a) Nincs párhuzamos futtatási utasítás ♦ Ekkor a hatáskör határozza meg a párhuzamosságot, hiszen a nyelvben nincs cobegin ... coend-szerű struktúra. Ilyen rendszert valósítottak meg például az Ada nyelvben. Példa (egy Ada programrészlet Pascal-szerű szintakszisban): procedure PROC; process P; begin ... end; process Q; begin ... end; begin (* itt PROC, P és Q párhuzamosan fut, ehhez nem kell más külön jelzés *) end; (* PROC *)

II./b) Van párhuzamos futtatási utasítás ♦ Ilyen reprezentációt valósít meg a Pascal-FC nyelv, ezzel később foglalkozunk. Az alfejezetben megismert lehetőségek után tekintsük át összefoglalóan, hogy mitől jó egy párhuzamos nyelv. Általánosan mondhatjuk, hogy akkor, ha: • gazdag, rugalmas eszköztárral rendelkezik (ez be van építve a nyelvbe); • jó a futási teljesítménye.


Vissza

66




Vissza

67

Sok nyelv ezek közül inkább csak az egyik pontban erős, hiszen a gazdag eszköztár a több ellenőrzés miatt rontja a futási teljesítményt. Az Ada nyelv tervezői ugyanakkor – igen nagy erőforrásigénnyel – elérték, hogy az addig létező összes jó struktúra beépítésével is jó a nyelv futási teljesítménye. A PascalFC – mint látni fogjuk – kissé „szegényes” eszköztárral és kis erőforrásigénnyel jó futási teljesítményt nyújt. Egy adott nyelvben csak egyféle típusú folyamatmodell valósítható meg.

A Pascal-FC nyelv folyamatmodellje A Pascal-FC nyelv folyamatmodellje a II./b) típusba tartozik, azaz a folyamatokat névvel azonosítjuk, és van párhuzamos végrehajtási utasítás. A struktúra félstatikus és „lapos”, tehát nincs egymásba ágyazás. A terminálás lehetőségei közül nincs benne a nyelvben a suicide és az abort, a többi viszont megvan. Így – noha a Pascal-FC nem a legrugalmasabb nyelvi modellt használja – az elméletileg lehetséges eszköztárból csak néhány fontosabb elem maradt ki. A legszembetűnőbb az általános esethez képest a folyamatok egymásba ágyazásának a hiánya, ennek beépítése azonban igen jelentős mértékben megnövelné a nyelv tervezési és futási bonyolultságát, és rontaná a teljesítményt. A Pascal-FC nyelvben minden folyamatot előre kell deklarálni, a párhuzamos futtatás csak folyamatokra érvényes. Csak egy darab cobegin … coend struktúra megengedett. Példa (egy egyszerű Pascal-FC programrészlet): program SCHEMA; process type EXAMPLE(I: integer); begin ... end; var P, Q: EXAMPLE; ...


Vissza

67



68

begin (* szekvenciális programrészlet a konkurrens rész előtt *) cobegin P(19); (* input paraméter *) Q(48) coend; (* szekvenciális részlet a konkurens folyamatok terminálása után *) end.

A cobegin ... coend struktúra csak akkor fejezi be a futását, ha minden belső folyamat befejezte. Több azonos típusú folyamat esetén használhatunk ciklust (for, while és repeat típus) a cobegin ... coend belsejében. Példa: program SIMPLE; process type PTYPE(I: integer); begin ... end; var COUNT: integer; P: array[1..3] of PTYPE; begin cobegin for COUNT := 1 to 3 do P[COUNT](COUNT) coend end.

vagy (ekvivalens módon átírva): var P1, P2, P3: PTYPE; begin cobegin P1(1); P2(2); P3(3) coend end.


Vissza

68



69

Bár a ciklusműködés alapvetően szekvenciális, a cobegin ... coend struktúra belsejében az is párhuzamosan megy végbe, hiszen a || operátor tulajdonságai miatt a P1, P2 és P3 folyamatok futtatási sorrendje itt nem megkötött. Erről a futtatórendszer gondoskodik. Ha csak egy adott típusú folyamatot akarunk használni, akkor megengedett az úgynevezett anonymous folyamattípus (mint a tömböknél). Példa: process P; var ... begin ... end;

Megfigyelhető, hogy a process kulcsszó mögül hiányzik a „type” kulcsszó. A fenti kódrészlet ekvivalens a következővel: process type PT; var ... begin ... end; var P: PT;

A nyelvben van inicializálás, és a var változóval a folyamat terminálás után küldhet vissza adatokat a főprogramnak. Ezt egyfajta párhuzamos „függvényhívásra” alkalmazhatjuk. Példa: process type BACK(var i: integer);


Vissza

69



70

Folyamatállapotok és -átmenetek Bár a Pascal-FC nyelv folyamatmodellje az egyszerűbbek közé tartozik, így is sokféle állapoton haladhat át egy adott folyamat az élete során. Eddigi ismereteink alapján a következő életciklust rajzolhatjuk fel:

Az állapotok közül a created (létrehozott) a folyamat deklarációja után, az executable (futtatható) a cobegin … coend struktúra belsejében, de a terminálás előtt következik be. A terminated (terminált) állapot a folyamat futásának befejezése után, de a cobegin … coend struktúra lezárása előtt él, míg destroyed (szétrombolt) állapotba a folyamat a coend után kerül. A program futásának befejezése után következik be újra a non-existing (nem létező) állapot. A végrehajtható állapotot részletesebben is elemezzük, ez implementációs kérdéseket is felvet. Mivel nem feltétlenül ugyanannyi fizikai proceszszorunk van, mint amennyi folyamat, ezért a cobegin … coend struktúra belsejében, a terminálás előtt • egy adott folyamat nem biztos, hogy fut, ezért futtatható állapotban van; • vannak futó (running) folyamatok és futásra kész (ready) folyamatok, utóbbiak közül választ az ütemező, ha felszabadul egy fizikai proceszszor.


Vissza

70




Vissza

71

Egyprocesszoros rendszerben például mindig csak egy éppen futó folyamat lehet, a többi a készenléti állapotban várakozik. Az executable állapot részeit tekintve nyilvánvaló, hogy egy folyamat a created állapotból először mindig a ready-be kerül át (az executable állapoton belül), és mindig a running-ból kerül át a terminated állapotba. Kissé nehezebb a válasz a következő kérdésre: vajon mikor történhet ready ↔ running átmenet? Ready → running átmenet akkor következik be, ha felszabadult egy processzor, és az adott folyamat kapta meg a futási jogot. Running → ready átmenet akkor történik, ha időosztással dolgozik a processzor, és lejárt az adott folyamat időkerete (például többfelhasználós környezetben); illetve ha az éppen futónál fontosabb taszk indul (emlékeztető: beágyazott rendszer példa). A beágyazott rendszer példában láttuk, hogy egyes taszkok időnként nem futtatható (non-executable) állapotban is lehetnek. Az ilyen állapotokat a továbbiakban blokkolt állapotnak nevezzük. A blokkolt folyamat tehát már túljutott a created állapoton, de még nem terminált, és valamely esemény bekövetkeztére várakozik. Ennek alapvetően két oka lehet: • a folyamat most nem akar futni (nincs dolga); • a folyamat valamely erőforrásra vár.


Vissza

71



72

Lényeges különbség van egy blokkolt és egy processzor hiányában nem futó folyamat között, hiszen újabb processzorok rendszerbe állításával az előbbi nem kerül automatikusan futó állapotba (példa: a biztonsági öv rögzítését végző taszk). A folyamat életciklusát a blokkolt állapottal kiegészítve a következő ábrát kapjuk:

Az executable állapot részeit tekintve végiggondolhatjuk, hogy csak running → blocked → ready átmenet lehetséges, tehát például a blokkolt állapotból a folyamat először mindig a készenléti állapotba kerül vissza.

A folyamatok menedzselése és a futtatórendszer Eddigi tapasztalataink alapján már láthatjuk, hogy egy párhuzamos program futtatása közel sem olyan egyszerű, mint egy szekvenciálisé. A folyamatokat „szét kell osztani” a rendelkezésre álló processzorok között, gondoskodni kell létrehozásukról és terminálásuk ellenőrzéséről. Ezeket a


Vissza

72




Vissza

73

tevékenységeket egy futtatórendszer (Run Time Support System – RTSS) látja el, amelyet általában a compiler (fordító) generál a programot reprezentáló object kóddal együtt. Az RTSS hasonló, mint egy többfelhasználós operációs rendszer ütemezője, logikailag a hardver és az alkalmazási szoftver között helyezkedik el. Az RTSS nyomon követi az összes folyamatot a párhuzamos program futása alatt. Mivel egy folyamat az életciklusa alatt többször is elhagyhatja a CPU-t (és visszajöhet, hogy onnan folytassa a futásását, ahol abbahagyta), ezért a regiszterek tartalmát ilyenkor tárolni kell valami egyedi helyen, ahol az más folyamatokhoz tartozó adatokkal nem keveredhet össze. A tárolásra egy folyamatleíró blokk (process descriptor vagy process control block) szolgál, amelyet rekordként képzelhetünk el. Egy tipikus folyamatleíró blokk a következő mezőket tartalmazza: • ID: a folyamat egyedi azonosítója; • status: a folyamat aktuális állapota (lásd diagram); • volatile environment: mentőterület a folyamathoz tartozó CPU-regiszterek, utasításszámláló és a verempointer értékei számára; • links: az RTSS által használt pointerek, amelyek más leírásokra mutatnak. Az RTSS megvalósítására kétféle stratégia képzelhető el: • A fordítóprogram generálja a teljes futtatórendszert. Az RTSS a felhasználói program kódjával összeszerkesztve, egyetlen programként kerül végrehajtásra az operációs rendszer egyetlen vezérlési folyamataként. • A folyamatok menedzselését és ütemezésüket az operációs rendszer végzi, a fordítóprogram csak a megfelelő szolgáltatáskérő hívási sorozatot generálja. Minden folyamat az operációs rendszer külön vezérlési folyamata. A második megoldás a hatékonyabb, ha a nyelv és az operációs rendszer párhuzamossági modellje kompatíbilis. Az elsőt ugyanakkor egyszerűbb megvalósítani, és csak ez lehetséges, ha maga az operációs rendszer nem párhuzamos. Komoly hátrány ilyen esetben például az, hogy I/O hívásoknál nemcsak a hívó folyamat, hanem az egész program blokkolt állapotba kerülhet (a Pascal-FC ebbe a csoportba tartozik, de szintén ide sorolható az egyébként professzionális Ada nyelv néhány változata is).


Vissza

73




Vissza

74

Példaprogram: HELLO.PFC (01) Elemezzük a fenti problémát a HELLO.PFC példaprogram futtatásával. Hogyan jelenik meg a felhasználó számára, hogy a program blokkolt állapotba kerül? Hogyan működhetne ez a program a második csoportba tartozó RTSS alatt? (1,5)

Programfuttatás a Pascal-FC-ben Attól függően, hogy fair vagy nem fair ütemezőt használunk (lásd következő rész), a programok futtatása Pascal-FC-ben a következőképpen történik: pfc.bat pfc.bat

programnév.pfc -uf programnév.pfc

(* fair ütemező *) (* nem fair ütemező *)

A Pascal-FC az újabb Windows típusú operációs rendszerekkel ellentétben nem támogatja a hosszú fájlnevek használatát. Ügyeljünk ezért arra, hogy programjaink nevét ennek megfelelően adjuk meg. A Pascal-FC részei a következők: pfccomp.exe pfc.bat pint.exe, ufpint.exe

(* fordító *) (* batch fájl a fordításra *) (* fair és nem fair ütemező *)

Egy program forráskódjából a fordító a következő fájlokat állítja elő: listfile, objfile és pmdfile.

(* az utóbbival később foglalkozunk *)

A Pascal-FC-ben a programok futtatása több lépésben zajlik. Először a fordító ellenőrzi és értelmezi a forrásprogramot, erről a lépésről a lisfile-ban kapunk információt. Ezután a programot lefordítja, ekkor keletkezik a már gépi kódú objfile. Végül a rendszer a gépi kódú programot lefuttatja, külön futtatható kódot (exe fájl) azonban nem készít. Újbóli futtatáshoz meg kell ismételnünk a fenti folyamatot. Ha a fordító szintaktikai vagy szemantikai hibát talál a forrásprogramban, akkor a futtatásra már (értelemszerűen) nem kerül sor. Ilyenkor a hibát a compiler a listfile-ban jelzi.


Vissza

74



75

A listfile részlete a CHAOUT.PFC (02) program futtatása után: Compiler listing 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

0 0 0 0 0 0 6 8 8 8 8 9 14 19 24 25

program CharOutput; process type betu(valt: char); var i: integer; begin for i := 1 to 10 do write(valt) end; var a, b, c: betu; begin cobegin a(’a’); b(’b’); c(’c’); coend; end.

A program sorait a fordító sorszámozza, emellett jelzi a futtatható utasítások számát az adott sor végrehajtása után (pc – program counter). Megfigyelhető, hogy a deklarációk sosem növelik ezt a számot, a parancsok és a kifejezések pedig ilyen szempontból változatos eredményt szolgáltatnak.

A folyamatok ütemezése Az RTSS feladatai közé tartozik a logikai processzorok fizikai megvalósítása. Mivel általában több folyamat van, mint processzor, ezért a futni akaró folyamatok valamilyen várakozási sorba kerülnek, és az RTSS közülük választ egyet, ha felszabadult egy processzor. Erre sok különböző stratégia is elképzelhető, de alapvetően két szélsőséges választási módszer lehetséges: • befejezésig dolgozhat a kiválasztott folyamat (nem fair stratégia); • időosztás, minden folyamat egyenlően részesedik a processzoridőből (fair stratégia). Az első módszer kevés átkapcsolást igényel a folyamatok között, ezért elsősorban akkor használjuk, ha az átkapcsolás drága művelet, illetve sok időt


Vissza

75




Vissza

76

vesz igénybe (valós idejű rendszereknél). A második stratégia akkor használatos, ha garantálni kell a folyamatok fair kiszolgálását (bizonyos időközönként mindegyik taszk „szóhoz jusson”, és közel azonos ideig dolgozhassanak egy-egy alkalommal – többfelhasználós operációs rendszereknél). Ezen két szélsőség között természetesen sok „köztes” változat is elképzelhető. Bármilyen ütemezőt is használunk azonban, a párhuzamos program helyessége és más funkcionális tulajdonságai (például terminálása) nem függhetnek az ütemezőtől, azaz egy párhuzamos programot akkor tekintünk helyesnek, ha bármilyen ütemezés esetén lefut, és megfelelő output adatokat ad. Mindez a teszteléses hibakeresést nagyon nehézzé teszi, ugyanis előfordulhat, hogy bizonyos jellegű hibák egyes ütemezések esetén egyáltalán nem, vagy csak nagyon ritkán jelentkeznek, más ütemezéssel pedig azonnal kiugranak. A helyesen működő párhuzamos program tényleges futási eredménye és teljesítménye azonban függhet az ütemezőtől, és – mint látni fogjuk – általában erősen függ is. A Pascal-FC nyelvbe két ütemezőt építettek be: • Korrekt (fair) ütemező – Ben Ari ötlete alapján (1982) • Nem korrekt (unfair) ütemező – Geoff Davies (1990) A fair ütemező véletlenszerűen választ egy folyamatot, amely véletlen ideig futhat. Ezután az ütemező újra választ az előzőek szerint (nyilván az előző folyamat is választható). Ezt a stratégiát alkalmazva egy egyszerű párhuzamos programnak is rengeteg különböző legális végrehajtása lehetséges, hiszen a véletlen is komoly szerepet kap a futtatás során. Mindez a program teljes gyakorlati tesztelését lényegében lehetetlenné teszi. A fair ütemező ténylegesen fair működéséhez igen jó véletlenszám-generátor szükséges. Ilyet természetesen beépítettek a Pascal-FC-be is. A nem fair ütemezésnél a következő elvek érvényesülnek: • az ütemező kezdetben a szövegbeli elhelyezkedés alapján rangsorolja a folyamatokat; • a kiválasztott folyamat addig dolgozik, ameddig akar, nem vehetik el tőle a futási jogot; • ha felszabadul egy processzor, a sorban következő folyamat indulhat.


Vissza

76




Vissza

77

Nagyon lényeges, bár egyáltalán nem nyilvánvaló, hogy a szekvenciális futtatás a látszólagos hasonlóság ellenére is különbözik a nem fair ütemezővel történő párhuzamos programfuttatástól. Több processzor esetén ez azonnal látszik, egyprocesszoros környezetben pedig lehetséges, hogy egy folyamat terminálás előtt lemond a futási jogáról (sleep utasítás, lásd később). Jósoljuk meg, hogy milyen eredmény várható a következő programoktól a kétféle ütemezés esetén, majd ellenőrizzük a sejtésünket! Meddig fog futni a PIG.PFC program a fair és a nem fair ütemezővel? (1,5) Példaprogram: CHAOUT.PFC (02), PIG.PFC (03) Módosítsuk a PIG.PFC programot úgy, hogy továbbra is használja mind a 3 folyamatot, de a) nem fair ütemezővel csak A betűket írjon ki; b) kiírja nem fair ütemezővel is az összes A és B betűt!

(1)

Elméleti szinten tervezzünk egy harmadik, „köztes” ütemezőt a Pascal-FC-hez, és gondoljuk végig, hogy milyen jellegű feladatoknál lehet hasznos ennek az alkalmazása (azaz mikor vezet lényeges különbségre a fair, a nem fair és a „köztes” ütemező használata)! (3–5) Készítsük el ezt az ütemezőt a Pascal-FC-hez, és teszteljük működését! (5)

Ütemezés valós idejű rendszerekben Most már rendelkezünk annyi ismerettel, hogy párhuzamos környezetben is áttekintsük a beágyazott rendszer szimulációját. A párhuzamos megoldás vázlata: program BEAGYAZOTT; process A; begin repeat ACTION_A; (* alvás, amíg a következő iteráció nem esedékes *) forever end;


Vissza

77



78

process B; begin repeat ACTION_B; (* alvás, amíg a következő iteráció nem esedékes *) forever end; process C; begin repeat ACTION_C; (* alvás, amíg a következő iteráció nem esedékes *) forever end; process D; begin repeat (* alvás, amíg nincs ébresztés, ekkor teljes végrehajtás *) forever end; begin cobegin A; B; C; D coend end.

El akarjuk érni, hogy az ütemező magától is úgy válassza ki a folyamatokat egyprocesszoros rendszerben, ahogyan azt korábban megterveztük. Prioritást rendelünk a folyamatokhoz a következők szerint: D > A > B > C. Az ütemező ekkor a következő stratégiát követi: mindig biztosítani kell azt, hogy az éppen futó folyamat prioritása a legnagyobb legyen a most futtatható folyamatok között. Ennek az a következménye, hogy ha felébred egy, az éppen futónál magasabb prioritású folyamat, akkor az ütemező elveszi a futási jogot és a processzort a futó folyamattól. Ezen ütemezési stratégia használatával a fenti program ugyanazzal az időbeosztással dolgozik (amennyiben a D taszkot


Vissza

78



79

nem kell végrehajtani), mint amit korábban terveztünk szekvenciális végrehajtás esetén. Lényeges különbség azonban, hogy ez alkalommal az ütemező dönt így, és mindezt nem a programozónak kell garantálni. Igazoljuk, hogy a D taszk végrehajtása esetén is tartani tudja az ütemező a határidőket. (1,5) A megoldás során feltettük, hogy a folyamatok közti átkapcsolás nem igényel időt. Ez a valóságban nem igaz, bár sok esetben ez az idő valóban elhanyagolható a végrehajtás idejéhez képest. Azonban, ha a végrehajtás már önmagában is „feszített”, akkor az átkapcsolások komoly problémát okozhatnak. Már ezen egyszerű példa alapján is látjuk, hogy általánosan nehéz lehet a következő kérdések megválaszolása: • Lehet-e ütemezni a folyamatokat a megadott határidők szerint? • Hogyan érjük el a folyamatok prioritását? Ezen kérdésekkel részletesen nem foglalkozunk, mert a jegyzet fő témája nem a valós idejű programozás. Megjegyezzük ugyanakkor, hogy a PascalFC nyelvben is lehet prioritást rendelni a folyamatokhoz a priority eljárással. Keressünk általános megoldást a fenti kérdésekre (elméleti szinten)! (3–5) Gyűjtsünk tapasztalatokat a priority eljárás használatáról!

(2–3)

Időkezelés a Pascal-FC nyelvben A valós idejű rendszerekben sokszor fontos, hogy a logikai processzorok futási idejét összhangba hozzuk a valós idővel (ennek szükségességét az autós példában már láthattuk). Erre a különböző nyelvekben időkezelő elemeket használnak. Két ilyen elemet a Pascal-FC-be is beépítettek: • egy standard clock függvény; • egy standard sleep eljárás.


Vissza

79



80

A clock függvény a rendszer belső (általában másodperc alapú) órája által mért aktuális értéket adja vissza, míg a sleep eljárás blokkolt állapotba helyezi a hívó eljárást a paraméterként megadott időre (azaz a folyamat önként felfüggeszti működését és elmegy aludni). Ezzel a két eszközzel bizonyos mértékig szabályozhatjuk a végrehajtási időt, mint azt a következő példa is mutatja: process x; const period = ...; var start, now: integer; begin repeat start := clock; action_x; now := clock; sleep(period - (now - start)) forever end;

Mennyi ideig fog tartani a példában a ciklus végrehajtása? Első közelítésben azt gondolhatjuk, hogy pontosan period ideig, és utána azonnal újbóli végrehajtás következik. Ez azonban csak közelítő kontrol, mert a megfelelő idő letelte után még nem biztos, hogy fut a folyamat, hiszen csak ready állapotba kerül vissza. Az ütemezőt semmi sem kényszeríti arra, hogy azonnal ezt a folyamatot válassza (a priority eljárás használatával ezt is megtehetnénk). Így a ciklus várhatóan egy periódus időnél valamivel nagyobb idő alatt fog lefutni. Ha nem valós idejű rendszer szimulációja a cél, akkor a sleep eljárás használata elvileg nem is szükséges. Egyes esetekben azonban mégis hasznos lehet, hiszen nem fair ütemező esetén így elérhetjük, hogy más folyamatok is szóhoz jussanak. A sleep eljárást hívó folyamatot ugyanis az ütemező az adott időre kikapcsolja. Az eljárás 0 paraméterrel is használható. Írjuk át a PIG folyamatot úgy, hogy kevésbé önző módon viselkedjen, engedje szóhoz jutni a többi folyamatot nem fair ütemezéssel is. (1)


Vissza

80



81

Írjuk át a betűkiírató programot úgy, hogy 5 darab A betű kiíratása után B-ket is kiírasson. (1,5) Mérjük le a fenti ciklus végrehajtási idejét úgy, hogy betűkiírató folyamatokat is elindítunk mellette fair és nem fair ütemezővel! (2) Végül érdemes kiegészíteni a folyamatéletciklus-ábrát úgy, hogy megkülönböztesse a kétféle blokkolt állapotot: • delayed (alvás, késleltetés) – időkezelő nyelvi elem miatt, az idő letelte után kijön a blokkolt állapotból; • suspended (nincs erőforrás) – folyamat szinkronizációs vagy kommunikációs elem miatt került blokkolt állapotba, csak más folyamat tevékenysége hatására jöhet ki onnan.

A következő programrészlet egymásba ágyazott cobegin … coend struktúrát tartalmaz. Átírható-e úgy, hogy pontosan ugyanazt hajtsa végre csak egy darab cobegin … coend struktúrával (melyik a legjobb megoldás)? (3)


Vissza

81



82

Vissza

82

cobegin begin A := kezdőérték_1 cobegin (* A-t használó részek *) coend end; begin B := kezdőérték_2 cobegin (* B-t használó részek *) coend end; coend




Folyamatok kölcsönhatása Vissza

83

Folyamatok kölcsönhatása Egy párhuzamos program folyamatait kölcsönhatásuk szerint vizsgálva a következő módon csoportosíthatjuk: • • •

függetlenek; versengők; együttműködők.

Eddigi (viszonylag szerény) tapasztalataink alapján úgy gondolhatjuk, hogy a folyamatok leggyakrabban függetlenek (mint amikor egy korábbi példánkban egy tömb elemeinek összegét és négyzetösszegét kellett kiszámolni). Ez azonban általánosan nem így van, az igazság az, hogy a csak független folyamatokat futtató párhuzamos programok viszonylag ritkák, és programozói szempontból nem is túl érdekesek. A legtöbb esetben a folyamatok versenyeznek egymással az erőforrásokért (például memória, háttértár elérése). Ugyanakkor a párhuzamos program lefutása közös cél, a folyamatok mind efelé tartanak, így közben segítik is egymás futását (például információ átadásával – folyamatok közti kommunikáció). A program futásának egyes szakaszaiban a versengés, máskor az együttműködés a fontosabb. Ha egyes folyamatok jelentős „versenyhátrányt” szenvednek el (éhezés, lásd később), akkor a közös cél is sérül, ezért az operációs rendszer feladatai közé tartozik a versengés menedzselése (folyamatszinkronizáció), továbbá a programozónak is gondolnia kell arra, hogy hogyan tud kivédeni ilyen káros helyzeteket. Együttműködő objektumok elemzésénél hasznos az objektumorientált megközelítés. Eszerint egy párhuzamos programban lehetnek aktív, passzív és semleges objektumok. a) Az aktív objektumok akciókat hajtanak végre, ők biztosítják a program futásának előrehaladását. b) A passzív objektumok csak akkor dolgoznak, ha azt egy aktív objektum kéri, ők szabályozzák a hozzáférést egyes erőforrásokhoz. Nem kezdeményeznek akciót.


Vissza

83



84

c) Semleges objektumok viszonylag ritkán fordulnak elő. Ezek olyan nem aktív objektumok, amelyek számára megengedett, hogy hozzáférést nyissanak (később látunk ilyen példákat). Ezeket az objektumokat a párhuzamos programozási nyelvekben a következő módon reprezentálhatjuk: a) folyamat; b) folyamat vagy új nyelvi elem; c) egy változó vagy valamilyen modul. A passzív objektumok nyelvi reprezentációja nem véglegesen megoldott kérdés, a két lehetőség mindegyike előnyökkel és hátrányokkal is jár. Folyamatreprezentáció esetén a nyelv egyszerű marad, de a folyamatok nagy száma lerontja a futási időt a sok váltás miatt. Új nyelvi elem esetén a működés hatékonyabb, de a megvalósítás kevésbé rugalmas, a nyelv bonyolultabb lesz. Ha a folyamatreprezentációt választjuk, akkor az ún. üzenetváltásos modellt tudjuk felépíteni (csatornamodell, távoli felhívás), míg új nyelvi elemként a szemaforokat illetve a monitorokat tudjuk a nyelvbe beilleszteni. Ezekkel a lehetőségekkel később foglalkozunk.

Szinkronizációs problémák megoldása hagyományos nyelvi eszközökkel Ebben a fejezetben azt mutatjuk be, hogy milyen nehézségekkel szembesülünk akkor, ha egy modern programnyelv hagyományos eszközeivel akarjuk biztonságosan megoldani a folyamatok közötti kommunikáció és szinkronizáció problémáit.

A termelő-fogyasztó probléma A legegyszerűbb szinkronizációs feladat a termelő-fogyasztó probléma. Ilyenkor egy folyamat egyszerűen elküldi az általa előállított értéket egy másik folyamatnak. Példaprogram: TERMFOGY.PFC (04) program termelfogyaszt; var value: integer;


Vissza

84



85

process sender; var message: integer; begin message := 29; value := message; end; process receiver; var data: integer; begin data := value; writeln(data); end; begin cobegin sender; receiver; coend end.

Ez a program fair ütemezővel nem működik megfelelően (néha jó eredményt ír ki, néha rosszat – a válaszok: 29 illetve 0). A hiba oka nyilván az, hogy a receiver folyamat néha hamarabb ír ki, mielőtt értéket kapott volna. A megoldáshoz feltételszinkronizáció szükséges, minden futtatásra biztosítanunk kell, hogy produce → consume (termelés → fogyasztás). A termelő-fogyasztó probléma ebben a legegyszerűbb esetben mindössze egy logikai változó használatával megoldható. A termelő beállít egy flag nevű változót, ha már elvégezte a tevékenységét, a fogyasztót pedig megvárakoztatjuk addig, amíg nem történt termelés: while not flag do sleep(0);

Ezt a technikát „foglalva várakozásnak” (busy waiting) nevezzük, hiszen a várakozás alatt a folyamat egyfolytában dolgozik. Emiatt az ilyen megoldások bonyolultabb esetekben általában nem hatékonyak. Példaprogram: TERMFOGY2.PFC (05)


Vissza

85


Folyamatok kölcsönhatása


Vissza

86

Általánosabban, ha többszöri lefutást is megengedünk, producei → consumei és consumei → producei+1 kell, hogy teljesüljön minden futtatásra. Ez így még mindig nem életszerű, mert a termelő és a fogyasztó aktivitása lehet erősen különböző egy adott időpillanatban. Például egy pékségnél általában hajnalban vagy reggel sütik a kenyeret, ugyanakkor az napközben fogy el. Az általános megoldás puffert használ, és így még minden futtatásra a consumei → producei + pufferméret feltételt is biztosítanunk kell. Ezen általános feladat megoldása sem túl nehéz hagyományos eszközökkel. Oldjuk meg a termelő-fogyasztó problémát a) ciklikusan, puffer nélkül; b) ciklikusan, puffer alkalmazásával.

(2,5) (3)

A díszkert probléma Ez a feladat a kölcsönös kizárás problémáját mutatja be. Példánkban egy nagy botanikus kertbe a látogatók két forgóajtós rendszerű bejáraton léphetnek be. Egy ajtón egyszerre nyilván csak egy ember tud bemenni, de egy időben mindkét kapun is érkezhetnek látogatók. Írjunk egy olyan programot, amely szimulálja a beléptető rendszert, azaz számoljuk meg a belépőket (egyprocesszoros rendszerben)! A pontos hardver-szoftver megvalósítással részletesen nem foglalkozunk. Nem párhuzamos megoldással is kísérletezhetünk, ekkor a forgóajtók eljárások lesznek. Egy közös változó (count) jegyzi az összes belépő számát. Bár a közös változó helyes eredményt ad, ez a „megoldás” mégsem fogadható el, hiszen csak szekvenciális beléptetést valósít meg. Nem köthetjük ki, hogy először mindenki az első ajtón megy be, majd utána mindenki, aki addig a második ajtónál várakozott. Példaprogram: GARDENS0.PFC (06)


Vissza

86




Vissza

87

Ez a probléma tehát tipikusan párhuzamos megközelítést igényel: a forgóajtók párhuzamosan működnek, és a belépők sorrendje előre nem jósolható meg. A párhuzamos megoldástól a következőket várjuk el: • mindegyik forgóajtó egy külön folyamat, ezek egymással párhuzamosan futnak; • egy közös globális változó (count) számolja a látogatókat; • egy terminálkezelő folyamat ad információt a vezetésnek (ezzel nem foglalkozunk). Első párhuzamos megoldási kísérletünk a következő: Példaprogram: GARDENS1.PFC (07) program gardens1; var count: integer;

(* első megoldási kísérlet *)

process turnstile1; var loop: integer; begin for loop := 1 to 20 do count := count + 1 end; (* turnstile1 *) process turnstile2; var loop: integer; begin for loop := 1 to 20 do count := count + 1 end; (* turnstile2 *) begin count := 0; cobegin turnstile1; turnstile2 coend; writeln(’Total admitted: ’,count) end.


Vissza

87



88

A program nem fair ütemezést használva belépteti mind a 40 embert, de fair ütemezéssel ez alatt van a beléptetés, többszöri végrehajtás után például a következő válaszokat kaphatjuk: 33, 25, 31, 22, 18, 30, 26, 27, 19, 23.

Láthatjuk, hogy még 20-nál kevesebb belépő is előfordulhat! Miért vesztünk belépőket? Ennek oka nyilván a folyamatok nem megengedett kölcsönhatása (többszörös értékadás). A GARDENS1 programot úgy is megírhattuk volna, hogy egy turnstile folyamattípus két változóját használja, ezzel a kód valamivel rövidebb lesz. Ez az átírás azonban a fenti probléma szempontjából irreleváns. A részletes elemzéshez meg kell vizsgálnunk az értékadó utasítást. Egy ilyen utasítást gépi szinten 3 lépésre lehet lebontani: kiolvasás, megnövelés, viszszatöltés. x := x + 1 gépi megvalósítása tehát: 1. x értékének regiszterbe töltése; 2. a regiszter értékének növelése; 3. a regiszter értékének visszaírása x címére. Értékvesztés például a következő módon történhet: 1. 2. 3. 4. 5. 6.

P berakja x értékét egy regiszterbe; Q berakja x értékét egy regiszterbe; P növeli a regiszter értékét; Q növeli a regiszter értékét; P tárolja a regiszter értékét x címén; Q tárolja a regiszter értékét x címén.

Végeredményben a két közel azonos időben megnövelt érték egyike jelenik csak meg a változó címén. Értékvesztés nyilván még sok más végrehajtási sorrend esetében is előfordulhat. Hány különböző végrehajtás lehetséges összesen a fenti 6 utasításra? Hány esetben vesztünk belépőt ezek közül? (2)


Vissza

88



89

Egyik korábbi feladatunk alapján az összes lehetséges futtatások száma ilyen esetben 20. Csak akkor nem vesztünk értéket, ha az egyik folyamat már teljesen befejezi a tevékenységét, mire a másik belekezd. Ez két eset, a PPPQQQ vagy a QQQPPP lefutás. A többi 18 eset mind rossz eset. Hogyan veszíthetünk el két értéket?

(2)

Egy lehetséges ilyen végrehajtás a következő: 1. P berakja x régi értékét egy regiszterbe; 2. Q berakja x régi értékét egy regiszterbe; 3. Q növeli a regiszter értékét; 4. Q tárolja a regiszter értékét x címén; 5. Q berakja x új értékét egy regiszterbe; 6. Q növeli a regiszter értékét; 7. Q tárolja a regiszter értékét x címén; 8. P növeli a regiszter értékét; 9. P tárolja a regiszter értékét x címén. Az utolsó lépésben P „tönkreteszi” Q teljes közbülső munkáját azzal, hogy egy jóval korábbi értéket ír be a közös változóba. Elméletileg mennyi lehet a legkisebb érték, amit a belépők számára kaphatunk? (2,5) Hogyan befolyásolná a hiba előfordulását, ha valamelyik folyamat végrehajtás közben lemondana a futási jogáról? (2) A hiba oka alapvetően az, hogy x-et semleges objektumként kezeltük, pedig passzívként kellett volna, a hozzáférést kellett volna szabályozni. A megoldáshoz a folyamatok működését úgy kell összehangolni, hogy a többszörös értékadás ne fordulhasson elő. Ez a kölcsönös kizárás esete, amivel már találkoztunk a helyfoglalási problémánál. Fontos látni azt is, hogy a hiba előfordulása elsősorban az ütemezőtől függ, nem fair ütemezővel sosem találnánk meg a hibát. Fair ütemezővel ellenben ez gyakran kiugrik, és elképzelhető olyan „köztes” ütemező is, amivel a program csak néha veszítene belépőket. Dijkstra 1965-ben bemutatta, hogy az általa bevezetett új nyelvi eszközzel, a szemaforral meg lehet oldani a kölcsönös kizárást. Ezután sokan


Vissza

89



90

próbálkoztak olyan megoldással, amely csak hagyományos nyelvi eszközöket használ, de jó ideig nem tudott ilyet mutatni senki. A kortársak jelentős része azon a véleményen volt, hogy ez nem is lehetséges. Később többen is eljutottak a – nem túl egyszerű – megoldáshoz. Az egyik legelegánsabb algoritmus Peterson nevéhez fűződik (1981). A következőkben megmutatjuk, hogy hogyan lehet eljutni ehhez az algoritmushoz. A vizsgálat során feltesszük, hogy • az egyidejű olvasások nem interferálnak, nem rontják el egymás hatását; • az egyidejű írások közül csak az egyik jelenhet meg tisztán, nem keveredhetnek; • egyidejű írás-olvasás esetén az olvasó tisztán a régi vagy az új értékeket látja. Ezek a feltételek elfogadhatóak egyprocesszoros rendszer és egyszerű adattípusok esetén. A megoldástól első közelítésben elvárjuk, hogy a kritikus szakaszban lévő folyamatok száma legfeljebb egy lehet, hiszen ha már kettő van ott, akkor belépőt vesztünk. A folyamatok kritikus szakaszt és nemkritikus szakaszt egyaránt tartalmaznak. Bár egyszerű példánkban ez nem teljesül, általában a kritikus szakasz jóval rövidebb, mint a nemkritikus szakasz, így a veszélyes átfedések viszonylag ritkán fordulnak elő. A megoldás vázlata a következő: process P; begin repeat entry protocol (* kritikus szakaszba lépés előtt *) kritikus szakasz exit protocol (* kilépés *) nem kritikus szakasz forever end;

Igazán lényeges most az entry és az exit protokoll, ezeket kell megírni hagyományos nyelvi eszközök használatával. Feltesszük még, hogy a kritikus szakaszban a program nem követ el hibát.


Vissza

90



91

Ez utóbbi feltevés a gyakorlatban nem mindig alkalmazható, ez azonban már a hibatoleráns rendszerek témakörébe vinne át bennünket, amivel a jegyzetben nem foglalkozunk. Második megoldási kísérlet Mindkét folyamatnak van egy saját logikai változója (flag1 és flag2), ezzel jelzik belépési szándékukat, és belépéskor megvizsgálják egymás változóit. Amennyiben a másik folyamat is be akar lépni a kritikus szakaszba, akkor az első várakozik, amíg a másik kilép. Megoldási vázlat: process P1; begin repeat flag1 := true; while flag2 do null; kritikus szakasz flag1 := false; nem kritikus szakasz forever end; process P2; begin repeat flag2 := true; while flag1 do null; kritikus szakasz flag2 := false; nem kritikus szakasz forever end;

Példaprogram (megvalósítás): GARDENS2.PFC (08) A program fair ütemezővel általában néhány lépés után „lefagy”. A probléma oka az, hogy ha közel azonos időben mindkét folyamat be akar lépni, mindkettő végtelen ciklusba kerülhet, például a következő módon: 1. P1 beállítja flag1-et (true lesz) 2. P2 beállítja flag2-et (true lesz)


Vissza

91


3. 4. 5. 6.


92

P2 megvizsgálja flag1-et (true, ezért belép a várakozóciklusba) P2 belép a busy waiting-be P1 megvizsgálja flag2-t (true, ezért belép a várakozóciklusba) P1 belép a busy waiting-be

Végeredményben feloldhatatlan várakozás keletkezik, de úgy, hogy közben minden folyamat lázasan dolgozik, előrehaladás mégsem várható. Az ilyen helyzeteket livelocknak nevezzük (lásd később is). A jó megoldáshoz tehát újabb követelményt kell támasztani: ha mindkét folyamat be akar lépni a kritikus szakaszba, előbb-utóbb dönteni kell közöttük, hogy elkerüljük a végtelen várakozást. Harmadik megoldási kísérlet Úgy gondolhatjuk, hogy eredményre vezet, ha megcseréljük a várakozó ciklust és a flagek beállítását. process P1; begin repeat while flag2 do null; flag1 := true; kritikus szakasz flag1 := false; nem kritikus szakasz forever end; process P2; begin repeat while flag1 do null; flag2 := true; kritikus szakasz flag2 := false; nem kritikus szakasz forever end;

Példaprogram (megvalósítás): GARDENS3.PFC (09)


Vissza

92



93

A program nem működik jól, néhány belépőt elvesztünk. A veszteség oka nyilván ugyanaz, mint kezdetben, a folyamatok mégis bejutnak egyszerre a kritikus szakaszba. Észrevehető ugyanakkor, hogy a veszteség kevesebb, mint a protokoll nélküli változatnál. Egy lehetséges értékvesztés: 1. 2. 3. 4. 5. 6. 7.

P1 és P2 a nemkritikus szakaszban vannak (flag1 = flag2 = false) P1 megvizsgálja flag2-t (false) P2 megvizsgálja flag1-t (false) P1 átállítja flag2-t (true) P2 átállítja flag1-t (true) P1 belép a kritikus szakaszba P2 belép a kritikus szakaszba (elvesztettünk egy belépőt) Mi az oka annak, hogy kevesebb belépőt vesztünk, mint az első megoldási kísérletnél (gardens1)? Próbáljunk több indokot megadni! (2) A javulásnak alapvetően két oka van: 1. Van ellenőrzés, ami néha működik. 2. Kevesebb a veszélyes ütközés, mert a folyamatok összhosszához képest rövidebb a kritikus szakasz (az első esetben a néhány soros programnak majdnem a fele kritikus volt).

Negyedik megoldási kísérlet Most egy olyan megoldással próbálkozunk, hogy a folyamatok csak egy változót használnak közösen (turn), ez reprezentálja a belépési jogot. Ha a másik folyamatnál van a jog, akkor az adott folyamat várakozásra kényszerül a belépésnél. Amikor egy folyamat befejezte a futását a kritikus szakaszban, átadja a jogot a másiknak. process P1; begin repeat while turn = 2 do null; kritikus szakasz turn := 2; nem kritikus szakasz forever end;


Vissza

93



94

process P2; begin repeat while turn = 1 do null; kritikus szakasz turn := 1; nem kritikus szakasz forever end;

Példaprogram (megvalósítás): GARDENS4.PFC (10) Ez a belépési védelem kizárja azt, hogy belépőt veszítsünk. Ugyanakkor van egy komoly probléma, ami a futtatás során azonnal látszik: a program csak felváltva léptet be a turn változó miatt. Tehát, ha valaki belép az egyik kapun, akkor az a kapu addig blokkolódik, amíg a másikon is be nem jön valaki. Ez a feltétel a gyakorlatban nyilván elfogadhatatlan, és eltérő számú belépő esetén végtelen várakozáshoz (livelockhoz) vezet. A jó megoldástól tehát még azt is elvárjuk, hogy ha egy folyamat be akar lépni a kritikus szakaszba, a másik pedig már többet nem akar, akkor az első folyamat tetszőlegesen (várakozás nélkül) beléphessen. A Peterson-féle megoldás A jó megoldás (Peterson, 1981) egyszerre használja a flageket és a turn változót is. A flag a belépési szándékot jelzi, míg a turn a jogot. Így az előző kísérlethez hasonlóan belépőt biztosan nem vesztünk el. Csak akkor kell egy folyamatnak várakoznia, ha a másik is be akar lépni, és a jog is nála van. A folyamat tehát akkor is beléphet, ha elvileg nincs nála a jog, de a másik nem akar belépni. Ezzel kizárjuk az előző kísérlet hibáját. process P1; begin repeat flag1 := true; turn := 2; while flag2 and (turn = 2) do null; kritikus szakasz flag1 := false; nem kritikus szakasz forever end;


Vissza

94



95

process P2; begin repeat flag2 := true; turn := 1; while flag1 and (turn = 1) do null; kritikus szakasz flag2 := false; nem kritikus szakasz forever end;

Példaprogram (megvalósítás): GARDENPE.PFC (11) A Peterson-féle megoldás fair kiszolgálást biztosít abban az értelemben, hogy ütközés utáni újabb ütközéskor most a korábbi vesztes lesz a nyertes. Ugyanakkor a beléptetés nem teljesen determinisztikus, azaz nem mindig felváltva lépnek be az emberek a kapukon. Egy hasonló megoldást Dekker is bemutatott. Ez a program szintén turn változót használ, verseny esetén az egyik folyamat visszalép. Ez a megoldás kicsit kevésbé determinisztikus, többször lépnek be egymás után az emberek ugyanazon a kapun. Példaprogram: GARDENDE.PFC (12) Fejlesszük tovább a Peterson vagy Dekker-féle megoldást három vagy több forgókapura (újabb flag változókkal illetve a turn felhasználásával). (3-4) További forgókapuk: a Bakery-algoritmus Sikeres megoldásunkon felbuzdulva a díszkert vezetősége újabb forgókapukat akar felszerelni. Ehhez a kölcsönös kizárás problémájának általánosabb megoldása szükséges. Lamport 1974-ben közzétett egy olyan algoritmust, amely általánosan megoldja ezt a problémát, bár – mint látni fogjuk – kissé nehézkes, nem teljesen fair, és ráadásul jóval bonyolultabb, mint a Peterson illetve Dekker-féle megoldások. A megoldás egy pékséget szimulál. Egy frissen belépő folyamat sorszámot „húz”, ez határozza meg majd a hozzáférési jogot. A párhuzamos működés miatt azonos sorszám kiadása is előfordulhat. Ilyen esetek feloldására


Vissza

95




Vissza

96

az inicializáláskor minden folyamat még egy indexet is kap, ez dönti el, hogy sorszámütközés esetén melyik folyamat az erősebb. A program nem teljesen fair, mert az inicializáláskor kapott nagyobb prioritás végig meg is marad. A folyamatok számát az nprocs konstans határozza meg, ennek értéke megváltoztatható. A program kicsit lassú a sok busy waiting miatt, de legalább jól működik. Példaprogram: LAMPORT.PFC (13) Elemezzük a Bakery-algoritmus működését! Válaszoljunk a következő kérdésekre: 1. Melyik sorszámot kapja az aktuálisan belépő folyamat? 2. Mire szolgál a favoured függvény? 3. Mire szolgál a choosing tömb?

(2)

Az író-olvasó probléma A kölcsönös kizárásnál még általánosabb az úgynevezett író-olvasó probléma. Az olvasás és írás műveletek itt nem elemi tevékenységek. Az írók kölcsönös kizárással dolgoznak, az olvasók futhatnak egymással párhuzamosan, és amikor egy író ír, akkor olvasó nem olvashat. Tehát nincs szükség minden esetben a kölcsönös kizárásra. Egy lehetséges fontos alkalmazás az adatbáziskezelés. Ilyenkor nagyobb területen zajlik a munka, több író is dolgozhat egyidőben, ha különböző területet használnak. Az író-olvasó probléma általános megoldásával később foglalkozunk, hagyományos nyelvi eszközös megoldással nem kísérletezünk.

Összefoglalás Összegezve tapasztalatainkat a szinkronizációs problémák hagyományos nyelvi eszközökkel történő megoldásáról, mindenképpen érdemes új nyelvi elemeket bevezetni, mert: • A busy waiting-et használó protokollok tervezése és megértése nehéz, különösen az általános esetben. • A busy waiting nem elég hatékony és nem biztosít fair kiszolgálást, emellett sokszor túl determinisztikussá teszi a programot. • A programtesztek gyakran nem mutatják ki azon ritka eseteket, amikor sérül a kölcsönös kizárás vagy livelock áll elő.


Vissza

96



97

• Ezeknek a programoknak a helyességigazolása rendkívül időigényes, gyakorlatilag szinte kivitelezhetetlen. • Egy rossz taszk tönkreteheti a közös változót, és vele az egész programot. A bevezetendő új nyelvi elemeket a következő fejezetekben tárgyaljuk.

Párhuzamos programok helyessége A kölcsönös kizárás és a feltételszinkronizáció tanulmányozása közben fontos tapasztalatokat szereztünk a párhuzamos programok helyességével kapcsolatban. Általánosan azt mondhatjuk, hogy a helyesen működő párhuzamos programnak bizonyos tulajdonságokat teljesítenie kell (a tulajdonság olyan jellemző, amely minden futtatásra érvényes). Egy helyesen működő párhuzamos program biztonságos és eleven (Owicki és Lamport 1982). Egy párhuzamos program • biztonságos, ha nem történik semmi „rossz” a program futtatása során; • eleven, ha a futtatás során végül (véges időn belül) történik valami „jó”.

Biztonságosság Eddigi tapasztalataink alapján legalább két tulajdonság ilyenkor biztosan teljesül: • a kölcsönös kizárás nem sérül; • a folyamatok szinkronizációja biztosított (termelő-fogyasztó probléma, teli és üres puffer kezelése). További követelmény a deadlock-mentesség, a deadlock meghatározásával, feloldásával és elkerülésével a következő alfejezetben foglalkozunk részletesen. Deadlock esetén a folyamatok blokkolt állapotban várakoznak olyan eseményre, amely sohasem következik be.

Elevenség Ennek teljesüléséhez szükséges a biztonságosság igazolása is, de ez még önmagában nem elég. A díszkert probléma második megoldási kísérletében már tapasztaltuk az elevenség sérülését. Egy eleven programnál szükséges a livelock-mentesség, hiszen livelock esetén a folyamatok haszontalanul futtatnak utasításokat, mert nem történik semmi előrehaladás. A livelock


Vissza

97




Vissza

98

logikai meghatározása nehezebb, mint a deadlocké, mert bonyolultabb párhuzamos programok esetében előfordulhat, hogy egyes utasítások sokszor ismétlődnek, de végül mégis lesz előrehaladás (pl. Bakery-algoritmus). Az elevenség más módon is sérülhet. Ilyen hiba a meghatározatlan elhalasztás vagy éhezés (néhány folyamatra). Ekkor az egész program képes dolgozni és előrehaladni, de néhány folyamat mindig veszít a többiekkel szemben, például a különböző prioritások miatt. Ezen folyamatok „éhezése” általában a főprogram hatékonyságát is rontja. A livelockkal ellentétben ilyen helyzeteken segítenek a plusz erőforrások, ezekkel az éhezés feloldható.

A deadlock (holtpont) A folyamatok működésük során erőforrásokat használnak (nyomtató, memória, fájlok). Jó esetben a rendszernek biztosítani kell a folyamatok erőforrásigényének véges időn belüli kiszolgálását. Ezeket az eszközöket általában valami közös állományba helyezik, és egy erőforrás-kezelő menedzseli a beérkező igényeket. A folyamat először kéri, majd megkapja és használja az erőforrást, ezután pedig elengedi. Ha a kérés nem teljesíthető, azaz a rendszer nem rendelkezik szabad erőforrással, akkor a folyamatot az erőforráskezelő várakozásra kényszeríti. Az ilyen protokollok azonban holtponthoz vezethetnek. Példa Tekintsünk egy olyan rendszert, amely két folyamatból (P1, P2) és két erőforrásból (E1, E2) áll. Tegyük fel, hogy mindkét folyamat mindkét erőforrást használni szeretné, és az első folyamat már lekötötte az első erőforrást, a másik folyamat pedig a másodikat. Ha mindkét folyamat bejelenti igényét a másik folyamat erőforrására, mielőtt elengedné a sajátját, előáll a holtpontállapot, a folyamatok végtelen ideig várakozni fognak. Az ábrán a folyamatokat körökkel, az erőforrásokat négyzetekkel jelöltük, és a folyamatos nyíl jelzi a használatot, míg a szaggatott nyíl a kérést. P1

P2

E1

E2


Vissza

98




Vissza

99

Elő lehet-e idézni holtpontot a sleep utasítás használatával?

(1)

A példa alapján is látható, hogy a holtpont csak bizonyos feltételek együttes teljesülése esetén jöhet létre. A holtpont előfordulásának szükséges és elégséges feltételei (Coffman és mások, 1971.): 1. a folyamatok az erőforrásokat kölcsönös kizárással használják; 2. a folyamatok a már megszerzett erőforrásokat megtartják azon idő alatt is, amíg további erőforrásigényeik kielégítésére várnak; 3. a rendszer erőszakkal nem vehet el erőforrást egy folyamattól, ha az már azt lefoglalta; 4. az erőforrásokra várakozó folyamatok ciklikus lánca létezik. A 4. pont úgy szemléltethető, hogy a folyamatokat és az erőforrásokat reprezentáló gráfon körbe tudunk sétálni a folyamatos és szaggatott nyilakon haladva (lásd fenti példa).

A holtpont legyőzése A holtpont legyőzésére két különböző fő stratégia létezik: 1. Beépítünk a rendszerbe olyan komponenseket, amelyek észlelik a holtpont bekövetkeztét, és ezután végrehajtanak bizonyos tevékenységeket a megszüntetés érdekében (holtpont felismerés és megszüntetés). 2. Úgy építjük meg a rendszert, hogy holtpont sose következhessen be. a) Holtpont elkerülés – előre látja a közelgő holtpontot, megtagadja az odavezető igényeket. b) Holtpont megelőzés – úgy építjük fel a rendszert, hogy a holtpont bekövetkezése logikailag lehetetlen). Ezek a fő- és alstratégiák akár együtt is alkalmazhatók. Egyes rendszerek közülük azt választják, ami a legjobban illik az adott erőforráshoz. Holtpontfelismerés és -megszüntetés Ebben a stratégiában megengedjük a holtpont előfordulását, mert bízunk abban, hogy felismerjük és meg tudjuk szüntetni.


Vissza

99



100

A holtpont felismerése viszonylag könnyű feladat. Az erőforrásokat és az igényeket tároljuk, erre az irányított gráfok kiválóan alkalmasak (lásd a fenti példát). A holtpontot a gráfban kör jelzi, ennek előfordulását egy ellenőr folyamat figyeli. Ha a holtpont bekövetkezett, a megszüntetése történhet kézi módon (egy programozó hajtja végre) vagy automatikusan (program). Lehetséges megszüntetési stratégiák: • minden folyamatot kilövünk, ami a holtpontban részt vesz; • egyesével lőjük ki őket, amíg a holtpont meg nem szűnik; • erőforrásokat veszünk el egyesével a folyamatoktól, amíg kell. A megszüntetett („áldozat”) folyamatok erőforrásai felszabadulnak. Bármelyik módszert is választjuk azonban, minden esetben elveszik valamennyi számítás, és a rendszer egy korábbi (holtpontmentes) állapotba kerül vissza. Kézenfekvő, hogy ezután a már bejárt úton haladva a rendszer újra visszakerül a holtpontba. Elméletileg mennyire valószínű ez? (1,5) A párhuzamos program rengeteg különböző lefutását tekintve ennek valószínűsége nagyon kicsi. Persze lehet, hogy más lefutási ágak is holtpontot eredményeznek. Hogyan választjuk ki az „áldozatokat”? A folyamatok kiiktatásánál a következő szempontokat célszerű figyelembe venni: • prioritás (egyes folyamatok fontosabbak a többieknél); • mióta fut a folyamat (minél régebben, annál több munka veszik el); • mennyi idő kell még neki a befejezéshez (ha ezt tudjuk mérni, akkor nem érdemes olyan folyamatot kilőni, amelyik hamarosan befejezi a tevékenységét); • mennyi erőforrást igényel még a folyamat (például ha csak egy kell már neki, akkor ne irtsuk ki); • milyen erőforrásokat használ már a folyamat (egyes erőforrásokat könynyebb elvenni, mint másokat).


Vissza

100



101

A holtpont elkerülése Ezen stratégia szerint, ha olyan erőforrásigény érkezik, amely nem tűnik biztonságosnak, akkor azt visszautasítjuk. Azt gondolhatjuk, hogy mindig elég csak egy lépésre előrenézni, ez a megközelítés azonban túlzóan leegyszerűsíti a problémát. Vannak ugyanis olyan helyzetek, amikor a holtpont már vészesen közel van, de a következő lépésben még nem következik be. A holtpont elkerülésének legismertebb módszere a bankár algoritmus (Dijkstra). A módszer arra hasonlít, ahogy egy bank kezeli a betéteket és a kölcsönöket: • a bankár adott nagyságú tőkével rendelkezik, amit adott számú ügyfélnek kölcsönöz; • minden ügyfél előre közli maximális igényét; • a bankár egy ügyfél igényét akkor fogadja el, ha az nem haladja meg a tőkéjét; • a bankár egy ügyfélnek nyújtott kölcsön ideje alatt más tranzakciókat is lebonyolíthat; • egy ügyfélnek időnként várnia kell a kölcsönre, de a bankár garantálja a véges várakozási időt; • egy ügyfél összes tartozása sohasem haladhatja meg maximális igényét; • egy ügyfél a teljes kölcsönösszeg megkapása után véges időn belül visszafizeti teljes tartozását egy összegben. Példa Van 3 folyamat és 12 erőforrás. A folyamatok előre bejelentett maximális igénye a következő: folyamat A B C Összesen:

max. igény 4 6 8 18


Vissza

101




Vissza

102

Tegyük fel, hogy egy adott pillanatban a folyamatok a következő erőforrásokat használják: folyamat A B C szabad:

max. igény 4 6 8

lefoglalt 1 4 5 2

Kielégíthetők-e a következő kérések: a) B kér 2 erőforrást; b) A kér 1 erőforrást? Egy kérést biztonságosnak tekintünk, ha teljesítés esetén marad olyan út, amelyen a különböző folyamatok eljuthatnak a befejezésig, még akkor is, ha most bejelentik az összes igényüket (azaz a bankár véges időn belül minden kérést ki tud elégíteni). Egy kérés nem biztonságos, ha teljesítése után holtpont keletkezik, amennyiben a folyamatok egyszerre bejelentik összes igényüket. A bankár algoritmus sosem teljesít nem biztonságos kéréseket. a) folyamat A B C

max. igény 4 6 8

lefoglalt 1 6 5 szabad: 0

Ekkor B be tudja fejezni a tevékenységét, így véges idő múlva visszaadja erőforrásait. Ezután A és C maximális kérése is teljesíthető. b) folyamat A B C

max. igény 4 6 8

lefoglalt 2 4 5 szabad: 1


Vissza

102



103

Ha a folyamatok egyszerre bejelentik összes igényüket, akkor holtpontba jutunk. Lényeges ugyanakkor, hogy ez az állapot így még nem holtpont, és belőle a holtpont nem is biztos, hogy bekövetkezik. Lehet ugyanis, hogy a folyamatok nem jelentik be maximális igényüket. A bankár algoritmus azonban úgy látja, hogy a veszély túl nagy, hiszen a kérés nem biztonságos, ezért nem fogja teljesíteni. A holtpont megelőzése Mivel ismerjük a holtpont létrejöttének szükséges és elégséges feltételeit, ezért építhetünk olyan rendszert is, amelyben a feltételek közül legalább egy nem teljesül. Ekkor a holtpont bekövetkezése logikailag lehetetlen, ezért nem kell nyomon követnünk az erőforrásigényeket. A feltételek kizárása a következő módon történhet: 1. A kölcsönös kizárás egyes erőforrásoknál nem oldható fel, de szimulálhatjuk az elhagyását. Ilyen például a nyomtatás többfelhasználós operációs rendszerben, ahol a felhasználók közvetlenül elküldik az anyagot a nyomtatóra, és az operációs rendszer kezeli az egyidejű igényeket. 2. Az erőforrások megragadva tartása közbeni várakozás feloldható például úgy, hogy a folyamatok csak egyszerre kaphatják meg az összes erőforrást (max. igény). Ilyenkor biztosan el tudják végezni a munkájukat, és utána visszaadják az összes erőforrást. Ez a megoldás azonban a sokszor bekövetkező felesleges birtoklás miatt nem tökéletes. 3. Ilyenkor a rendszer bevonhat erőforrásokat a folyamatoktól. Ekkor azonban bizonyos munka elveszik. 4. A ciklikus lánc például a következő módon zárható ki: sorszámozzuk az erőforrásokat, és minden kisebb sorszámú is kell egy adott erőforrás felvételéhez. A módszer hátránya szintén az esetlegesen bekövetkező felesleges birtoklás. Találjunk ki más módszereket is a feltételek kizárása (elsősorban 4. pont)! Mérlegeljük az előnyöket és a hátrányokat. (2-5)

Az étkező filozófusok problémája Az étkező filozófusok problémáját általánosan használjuk annak a vizsgálatára, hogy mennyire hatékonyak a párhuzamos programozási nyelvek szinkronizációs eszközei.


Vissza

103



104

A feladat szerint a filozófusok visszavonultan élnek, és mindössze két fő tevékenységet folytatnak: gondolkodnak és esznek. A filozófus ideje nagy részét gondolkodással tölti. Amikor megéhezik, leül a helyére egy közös asztalhoz, ahol egy tányér és egy villa áll a rendelkezésére. Szed magának az asztal közepén lévő tál tésztából (a tészta nem fogy el), és enni kezd. Minden filozófusnak csak egy villája van, azonban az evéshez két villára van szüksége, így a szomszéd villáját is használnia kell. Ezért ha egyszerre két szomszédos filozófus akar enni, akkor versenyeznek a villákért, és az egyik várakozásra kényszerül. A filozófus az étkezés után leteszi a villákat, és visszamegy gondolkodni. A filozófus folyamatok tevékenységei a következő lánccal írhatók le: P = (think → pickup → pickup → eat → putdown → putdown → P) A feladat egy csomó problémát bemutat a párhuzamos programozás területéről: • kölcsönös kizárás – egy villát egyszerre csak egy filozófus használhat; • feltételszinkronizáció – a filozófus csak akkor ehet, ha mindkét villát megszerezte; • kommunikáció osztott változóval – a villák reprezentálhatók olyan változóval, amin a szomszéd filozófusok osztoznak; • üzenetalapú kommunikáció – a villák reprezentálhatók olyan változóval, amit egy filozófus elküld a másiknak; • busy-waiting – ha a filozófus nem kapta meg a villát, így is megvárakoztathatjuk; • blokkolt várakozás – ha a filozófus nem kapta meg a villát, akkor aludni küldjük; • livelock – a filozófusok felvették a bal villát, és busy-waiting ciklusban várakoznak a jobb villa felvételére, ami sosem teljesül (lásd következő programpélda); • deadlock – a filozófusok felvették a bal villát, és blokkolva várakoznak a jobb villa felvételére, ami sosem teljesül (lásd később); • éhezés – egy filozófust kiéheztethet a két szomszédja, ha „összeesküdnek” ellene úgy, hogy mindig foglalva tartják a bal vagy a jobb villáját. A mostani megoldási kísérletben a hagyományos programozás eszközeivel dolgozunk. A filozófusok folyamatok, a villák foglaltságát logikai változók


Vissza

104




Vissza

105

jelzik. A „megoldás” azonban nem tökéletes, mert livelock keletkezik, ha a filozófusok egyszerre felveszik a bal villájukat. Példaprogram: FILOZ0.PFC (14) program filozofusok; const filoszam = 5; var villak: array[1..filoszam] of boolean; i: integer; procedure felvesz(var villaasztalon: boolean; var felvettem: boolean); begin felvettem := false; if villaasztalon then begin villaasztalon := false; felvettem := true; end; end; procedure letesz(var villaasztalon: boolean); begin villaasztalon := true; end; process type filozofustipus(nev: integer); var i: integer; villa1, villa2: integer; megvanavilla: boolean; begin villa1 := nev; if nev = filoszam then villa2 := 1 else villa2 := nev+1; repeat sleep(random(1)); {gondolkodik} megvanavilla := false; repeat felvesz(villak[villa1], megvanavilla);


Vissza

105



106

until megvanavilla; {megragadjuk az egyik villat} megvanavilla := false; repeat felvesz(villak[villa2], megvanavilla); until megvanavilla; {megragadjuk a masik villat} sleep(random(1)); {eszik} letesz(villak[villa1]); {leteszi a villakat} letesz(villak[villa2]); forever; end; var filozofus: array[1..filoszam] of filozofustipus; begin for i := 1 to filoszam do villak[i] := true; {minden villa az asztalon} cobegin for i := 1 to filoszam do filozofus[i](i); coend; end.

A megoldás egy másik logikai hibát is tartalmaz, amit később kijavítunk majd: a villák felvételét (és a kiíratásokat) kölcsönös kizárással kell végrehajtani. Hogy ez most nem teljesül, azt onnan láthatjuk, hogy a kiírások egymásba csúsznak. Ezt jelenleg a Peterson- vagy a Dekker-féle megoldás segítségével tudnánk megvalósítani, de más új eszközök később hatékonyabbak lesznek. Elemezzük a program működését! Milyen sorszámú villákat vesz fel az utolsó filozófus? (1) Teszteljük, hogy átlagosan hány étkezés után kerül livelockba a program. Hogyan változik ez a szám, ha a gondolkodás és az evés idejét megváltoztatjuk? Előfordul-e éhezés a futás során? (1) Keressünk deadlock és livelock példákat a valós életben! Hogyan lehet őket feloldani? (1,5) Elemezzük a TWOSLOTS.PFC (15) programot, amely az író-olvasó problémát hivatott megoldani. Biztonságos és eleven ez a program? Ha nem, akkor javítsuk! (3)


Vissza

106



A csatornamodell Vissza

107

A csatornamodell Folyamatok közötti kommunikáció üzenetváltással Ha a közös változók használatát el akarjuk kerülni az esetleges hibák miatt (például count a díszkert problémánál), akkor a nyelvbe be kell építeni a folyamatok közötti direkt kommunikáció lehetőségét. Ezzel egy üzenetváltásos nyelvi modellt kapunk, amely lényegesen különbözik az eddigiektől. Az egyik folyamat üzenetet küld (SEND), a másik pedig vár rá (WAIT) és fogadja. A SEND és a WAIT műveleteket többféle módon is meg lehet valósítani, eszerint több különböző üzenetváltásos modell képzelhető el. Egy ilyen nyelv tervezőjének alapvetően két kérdést kell megfontolni: • Milyen szinkronizációs módszert használjunk (ha egyáltalán kell)? • Hogy nevezzük el a forrás- és a célfolyamatot?

Szinkronizáció Az üzenetküldés módja a következő lehet: • aszinkron; • szinkron (egyszerű randevú); • távoli felhívás (remote invocation, kiterjesztett randevú). Aszinkron stratégia esetén a küldő folyamat az üzenet elküldése után azonnal szabadon folytatja a működését, és nem vár arra, hogy a fogadó megkapta-e az üzenetet, ilyenkor tehát nincs szinkronizáció. A módszer jelentős hátránya, hogy a fogadó az üzenet vételekor nem a küldő aktuális állapotáról kap információt (hanem egy korábbiról), továbbá a küldő semmilyen visszajelzést nem kap arról, hogy egyáltalán célba ért-e az üzenete. Ez utóbbi csak úgy lehetséges, ha a fogadó üzenetet küld vissza. Példa: postai levél. Szinkron stratégia esetén a küldőt megvárakoztatjuk addig, míg a fogadó nincs „vevőkész” állapotban, illetve fordítva. Ezután létrejön a randevú, majd a küldés és fogadás után mindkét folyamat szabadon folytatja a tevékenységét. Példa: fax.


Vissza

107



108

Távoli felhívás (kiterjesztett randevú) esetén a „küldő” nemcsak küldhet, hanem fogadhat is üzenetet. A módszerrel a következő fejezetben foglalkozunk részletesen. Példa: telefonbeszélgetés.

Elnevezés A folyamatok azonosítására a következő – egymástól független – lehetőségek vannak: • közvetlen vagy közvetett; • szimmetrikus vagy aszimmetrikus. A legegyszerűbb esetben minden folyamatnak egyértelmű neve van, ekkor a műveletek a következők: SEND message TO ProcessName WAIT message FROM ProcessName

Aszimmetrikus esetben a fogadót csak maga az üzenet érdekli, az nem, hogy ki küldte: WAIT message

Kliens-szerver kapcsolatban a klienseknek meg kell nevezniük a szervert az üzenetben, de a szervernek nem kell tudnia feltétlenül, hogy egy üzenet honnan érkezett, hacsak nem akar választ küldeni. Ha az egyértelmű elnevezés nem használható, vagy nem megfelelő, akkor közvetítőt (postaláda – mailbox, csatorna – channel) kell alkalmaznunk. A közvetítőt a küldőnek és a fogadónak egyaránt meg kell neveznie. SEND message TO mailbox WAIT message FROM mailbox

Többféle postaláda is lehetséges, elképzelhető egy vagy több küldő, illetve egy vagy több fogadó, megengedhető továbbá csak egy- vagy mindkét irányú adatáramlás. Maga az üzenet is lehet egyszerű vagy bonyolult.


Vissza

108



109

Kommunikáció csatorna segítségével A szinkron üzenetváltás csatornamodelljét az occam nyelvben (INMOS, 1984) és a CSP szabványban (Hoare, 1985) vezették be. A folyamatok elnevezett csatornákon keresztül kommunikálnak. A műveletek szintaktikája a következő: ch ! e ch ? v

(* e értékét elküldi a ch csatornára *) (* v értékét veszi a ch csatornáról, végül: v := e *)

A végrehajtás szinkronizált, az előbb érkező folyamat várakozik. Ha mindkét folyamat készen áll a kommunikációra, akkor végrehajtódik a randevú. Egy csatornához csak egy küldő és egy fogadó tartozik, azaz egy-egy kommunikáció valósul meg.

A Pascal-FC csatornamodellje A Pascal-FC-ben a csatorna mint alaptípus létezik, a deklarációs szabályok a megszokottak, azaz a használat előtt kell őket definiálni. Egy csatornával egyszerre csak egy egyszerű adat küldhető el. A csatornák helyes használatát a compiler biztosítja. Paraméterként csak a var kulcsszóval szerepelhetnek. Szemléltető példák: var link: channel of integer; type packet = record (* ... *) end; var network: channel of packet; type IntChans = channel of integer; var ch1,ch2: IntChans;

A termelő-fogyasztó probléma igen egyszerűen megoldható csatornák segítségével, hiszen a szinkronizáció biztosított. Példaprogram: CSATI0.PFC (16)


Vissza

109



110

program csati0; var ch: channel of integer; process producer; var message: integer; begin repeat ch ! 17; forever; end; process consumer; var message: integer; begin repeat ch ? message; write(message); forever; end; begin cobegin producer; consumer; coend end.

Ez az egyszerű program végtelen ciklusban „termeli” és „fogyasztja” a megadott értéket. Írjunk programot, amelyben a termelő elküldi sorban az angol ábécé betűit a fogyasztónak! (1,5) CSATI1.PFC (17)


Vissza

110



111

Egy prímszámgenerátor A következőkben egy bonyolultabb programot mutatunk be, amely prímszámokat állít elő az eratoszthenészi szita módszerének felhasználásával. A termelő folyamat (numbers) előállítja a számokat 2-től kezdve, amelyek ezután szűrőkhöz (elements, filters) kerülnek. Minden szűrő a megkapott első számot elraktározza magában (ez lesz az ő értéke), és ezt továbbküldi egy kiírató (outproc) folyamatnak. A továbbiakban a szűrők a kapott számokat aszerint vizsgálják, hogy oszthatók-e az értékükkel. Ha igen, akkor eldobják, ha nem, akkor továbbküldik a következő szűrőnek. Előbb-utóbb lesznek olyan számok, amelyek az összes szűrőn átjutnak. Ezeket végül egy fogyasztó (consumer) fogyasztja el. Így például az első szűrő értéke 2 lesz, és ő a továbbiakban csak a páratlan számokat küldi tovább. A második szűrő a 3-as számot kapja meg először, és ő ezután a hárommal nem osztható páratlan számokat küldi tovább. Példaprogram: PRIM.PFC (18) A numbers, a consumer és az outproc folyamatok részletes listáját a jegyzetben nem közöljük, a példaprogramban megtekinthető. program prim; (* nem terminál *) const N = 10; type chan = channel of integer; chans = array[0..N] of chan; var pipeline: chans; output: chans; i: integer; process numbers(var out:chan); (* egészeket generál és elküldi *) ... process consumer(var into:chan); (* a szűrőkön átjutó egészeket elfogyasztja *) ... process outproc(var outs:chans); ...


(* kiírja a prímeket *)

Vissza

111



112

process type elements(var left, right, down: chan); var p, q: integer; begin left ? p; down ! p; repeat left ? q; if (q mod p <> 0) then right ! q; forever end; var filters: array[1..N] of elements; begin cobegin numbers(pipeline[0]); consumer(pipeline[N]); for i := 1 to N do filters[i](pipeline[i-1], pipeline[i], output[i]); outproc(output); coend end.

A megoldás nem tökéletes, mert a program nem terminál. A „leálló” prímszámgenerátor megírásához később tanuljuk meg a megfelelő eszközöket. Rajzoljuk le a megoldás vázlatát gráf reprezentációban úgy, hogy a folyamatokat téglalapok, a csatornákat irányított élek szimbolizálják! Összesen hány folyamatot és hány csatornát használtunk? Mennyi csatornát deklaráltunk összesen? (2) Hány prímszámot ír ki a program? Meddig lehetne még ugyanennyi szűrővel a prímeket előállítani? (1,5) A program N darab prímszámot ír ki, és elméletileg p2-ig tudja előállítani a prímeket, ahol p az utolsó szűrő értéke.


Vissza

112



113

Szinkronizációs csatornák Az üzenetváltásos randevú szinkronizációt és kommunikációt egyaránt megvalósít. Vannak azonban olyan esetek, amikor csak a folyamatok szinkronizálása a célunk, konkrét üzenetet nem akarunk elküldeni. Ilyenkor használható speciális csatornatípus a szinkronizációs csatorna, amelyre egy „any” értéket küldhetünk, és róla azt leolvashatjuk. Ez a csatorna érdemi üzenetküldésre nem használható. A szinkronizációs csatorna a Pascal-FCben a „channel of synchronous” kulcsszavakkal deklarálható. A következő példaprogramban egy „starter” folyamat megvárakoztatja a „worker” folyamatokat bizonyos ideig, ha ez az idő letelt, akkor a workerek indulhatnak. Példaprogram: STARTERS.PFC (19) Írjuk át a STARTERS.PFC programot úgy, hogy „normál” csatornával valósítjuk meg ugyanezt a szinkronizációt. (1)

A szelektív várakozás Bármilyen üzenetváltásos modellt is használunk, bizonyos elemeket gyakorlati igények miatt be kell építenünk a nyelvbe. Ilyen a szelektív várakozás lehetősége is. Ennek szükségességét most a díszkert probléma kapcsán mutatjuk be. Első megoldási kísérletünkben a forgóajtó folyamatok egy-egy csatornára írják az általuk beléptetett emberek számát (például: path1 ! 1), míg a számláló folyamat a belépők számát leolvassa, és növeli a count változó értékét. Az üzenetváltásos modell nagy előnye, hogy a kölcsönös kizárás most nem sérülhet, hiszen a csatornaműveletek szinkronizáltak, és a randevú egyegy típusú. Emiatt belépőt nem veszítünk el. Példaprogram: GARDEN3A.PFC (20) A számláló folyamat részlete: count := 0; for i := 1 to 20 do begin path1 ? temp; count := count + temp; path2 ? temp; count := count + temp end; writeln(’Total admitted: ’,count);


Vissza

113



114

Változat: GARDEN3B.PFC (21) – itt egy forgóajtó típusból hoztuk létre a forgóajtó folyamatokat, és a számláló folyamat egy ciklust használ a leolvasáshoz, de a lényeget tekintve a két megoldás ugyanaz. A fenti programrészlet elemzésével (illetve a kapukon belépők kiíratásával) láthatjuk, hogy ez a „megoldás” ugyanúgy hibás logikailag, mint a turn változót használó megoldási kísérlet az előző fejezetben: a program csak felváltva léptet be. Tehát ha valaki belép az egyik kapun, akkor az a kapu addig blokkolódik, amíg a másikon is be nem jön valaki. Ez a feltétel – mint korábban láttuk – a gyakorlatban elfogadhatatlan. A megoldáshoz a számláló folyamatnak életszerűen kellene kezelni a belépőket, hiszen előfordulhat, hogy ugyanazon a kapun egymás után többen is be akarnak lépni, míg a másikon egy darabig nem. Adódhatnak olyan helyzetek is, hogy azonos időben mindkét kapun van belépő, ilyenkor a számláló szabadon választhatna, hogy kit léptet be először, a másik vendég addig várakozik. Összefoglalóan mondhatjuk, hogy egy nem determinisztikus, szelektív várakozást megvalósító szerkezetet kell beépítenünk a nyelvbe. A GARDENCH (22) és a GARDENC2 (23) példaprogramok kiírják, hogy mely kapukon léptek be a látogatók. Bár a randevú mindkét programban ugyanolyan jellegű, az eredmény alapján úgy tűnik, mintha az első program nemdeterminisztikus módon, a második pedig felváltva léptetne be. Mi az oka a látszólag eltérő eredménynek? Hogyan lehet a hibás kiíratást megvalósító programot javítani? (2)

Nem-determinisztikusság és párhuzamosság Tudjuk, hogy egy párhuzamos program nemdeterminisztikus, hiszen viselkedése nem teljesen előre meghatározott az input függvényében. Ismételt végrehajtás esetén nem biztos, hogy ugyanaz lesz az eredmény, nem látható előre pontosan, hogy mi fog történi (emlékeztető: betűkiírató program). Hasonló nemdeterminisztikus viselkedés figyelhető meg a folyamatok párhuzamos végrehajtásánál: P || Q esetén a végrehajtás lehet teljesen párhuzamos vagy csak átlapolt, továbbá nem-fair ütemezés esetén még ez utóbbi sem megengedett.


Vissza

114


A csatornamodell


Vissza

115

Ugyanakkor mindkét fenti esetben a folyamatok belső végrehajtása determinisztikus és szekvenciális volt. Nekünk most a díszkert probléma megoldásához a folyamat belsejében kell megengednünk a nemdeterminisztikus választás lehetőségét. A CSP szabvány a □ jelet használja a nemdeterminisztikus választás jelölésére. Eszerint P=X□Y a következőt jelenti: P úgy dolgozik, mint X, ha X feltételei teljesülnek, illetve Y-ként dolgozik, ha Y feltételei teljesülnek. Ha X és Y egyaránt lehetséges, akkor P szabadon (nemdeterminisztikusan) választhat X és Y végrehajtása között. A párhuzamos program helyes működése nem függhet a választási stratégiától, azaz a programnak bármilyen választás esetén is helyesnek kell lennie. Ugyanakkor egyes jellemzők (futási idő, output adatok) természetesen változhatnak a választás függvényében. Fontos látni, hogy a nemdeterminisztikusság nem ugyanaz, mint a fair vagy a véletlen választás. Lehet, hogy a nemdeterminisztikus stratégia véletlenszerűen választ, de az is elképzelhető, hogy mindig csak az egyik tevékenységet választja, vagy akár felváltva választja a tevékenységeket. Csupán annyit tudunk mondani, hogy programszinten a választás nem definiált, bármilyen lehetőség elképzelhető. A nemdeterminisztikusság ugyanakkor az említett hasonlóság ellenére a párhuzamosságtól is lényegesen különbözik. Az előbbi a folyamaton belüli választási struktúra tulajdonsága (amiből hiányzik az egyidejűség lehetősége), míg az utóbbi a folyamatok tulajdonsága. A □ operátor tulajdonságai a következők: • P □ (R □ S) = (P □ R) □ S = P □ R □ S • P□R=R□P

(asszociatív); (kommutatív).

Igaz továbbá az a kissé meglepő tulajdonság, hogyha nemdeterminisztikus választás lehetséges valamely tevékenység és az üres tevékenység (SKIP, null utasítás) között, akkor természetes a SKIP választása: P □ SKIP = SKIP.


Vissza

115



116

Szelektív várakozás a Pascal-FC-ben A Pascal-FC-ben a select konstrukció valósítja meg a nemdeterminisztikus, szelektív várakozást. Ez a konstrukció nagyon általános, tartalmazza az öszszes olyan hasznos lehetőséget, amelyet más nyelvekben megalkottak. A fenti P = X □ Y esetben a select szerkezet a következő: select csatorna1 ? érték1; or csatorna2 ? érték2 end;

A Pascal-FC a nemdeterminisztikus választást véletlenszerűen oldja meg, azaz ha egy időpillanatban mindkét csatornán lehetséges a kommunikáció, akkor „pénzfeldobással” dönti el, hogy ki lesz a győztes. A díszkert probléma megoldása egyszerű a select konstrukció ismeretében. Példaprogram: GARDENC3.PFC (24) A számláló (counter) folyamat két forgóajtóra a következő: process szamolo; var db, i: integer; tarolo: integer; begin db := 0; for i := 1 to 40 do begin select ut[1] ? tarolo; or ut[2] ? tarolo end; db := db+1; end; writeln(’Osszes belepo:’, db:2); end;

A példaprogram kiírja, hogy mely kapukon léptek be a látogatók. A futtatás során jól megfigyelhető a nemdeterminisztikusság.


Vissza

116



117

A select szerkezet általánosan tetszőleges számú ágat tartalmazhat, or kulcsszavakkal elválasztva. Az ágakban a csatorna műveletek mellett más utasítások is lehetnek. Így az előző példaprogram számláló eljárásába a következő részt is beírhattuk volna: select paths[1] count := or paths[2] count := end

? temp; count + temp; ? temp; count + temp

Ha az ágakban egy csatornatömb elemei közül kell választani, akkor a hoszszú kifejtést lehet rövidíteni. select chan[1] or chan[2] or chan[3] or chan[4] or another end

? V[1]; ? V[2]; ? V[3]; ? V[4]; ? T

A fenti szerkezet ekvivalens a következővel, ahol egy for ciklust használunk a replicate kulcsszóval (a nemdeterminisztikus választás szintén teljesül): select for i := 1 to 4 replicate chan[i] ? V[i]; or another ? T end

Megvalósítás a díszkert problémára (példaprogram): GARDENC4.PFC (25)


Vissza

117



118

A select szerkezet a Pascal-FC-ben a következő műveleteket/alternatívákat tartalmazhatja: • • • • •

üzenet olvasása; üzenet írása; timeout alternatíva; terminate alternatíva; else alternatíva.

Ha nincs randevúra kész select ág, illetve nincs választható alternatíva (például nincs belépő a díszkertbe), akkor a select szerkezetet futtató folyamat addig várakozik, amíg az ágak valamelyike nyitottá nem válik. Ha van else alternatíva, akkor a folyamat sosem lesz blokkolva, valamelyik ág azonnal végrehajtódik (lásd később).

Az őrfeltételes select Az eddigiek szerint a select minden ága választható a futtatáskor, ugyanakkor nem biztos, hogy mindig jó, ha minden lehetőséget megengedünk. Példa: buffer folyamat a termelő-fogyasztó probléma esetén. Első megoldási kísérlet: type intchan = channel of integer; process buffer(var put, get: intchan); var buff: array[0..31] of integer; top, base: integer; begin top := 0; base := 0; repeat select put ? buff[top]; top := (top + 1) mod 32; or get ! buff[base]; base := (base + 1) mod 32 end forever end;


Vissza

118



119

A fenti megoldásban az adatok tárolását ciklikus FIFO (first in first out) sorral valósítottuk meg. Ha termelés és a fogyasztás közel azonos időben történik, és egyszerre mindkét kommunikáció lehetséges, akkor nemdeterminisztikus választással határozza meg az ütemező a „győztes” folyamatot. Rövid átgondolás után láthatjuk, hogy ez a megoldási kísérlet nem teljesíti a következő biztonsági követelményeket: • nem lehet üres bufferból olvasni; • nem lehet teli bufferbe írni. A helyes megoldáshoz le kell zárnunk azokat az ágakat, amelyek az aktuális esetben logikailag nem hajthatók végre. Erre őrfeltételeket használunk. Az őrfeltétel egy logikai kifejezés, amely a select végrehajtása során (egyszer) kiértékelődik. Ha az eredmény TRUE, akkor a select ág nyílt, különben zárt. A zárt ágak közül a gép abban a végrehajtásban nem választhat. Az őrfeltétel nélküli select ág nyíltnak számít. Ha nincs nyílt ág, akkor a folyamat örökre blokkolt marad (hiába változnak közben a feltételek). Újabb kiértékelés csak a select újbóli végrehajtásakor történik. Az őrfeltétel általános alakja: when logikai_kif. =>

A javított buffer tehát a következő: process buffer(var put, get: intchan); var buff: array[0..31] of integer; top, base: integer; contents: integer; begin top := 0; base := 0; contents := 0; repeat select when contents < 32 => put ? buff[top]; top := (top + 1) mod 32; contents := contents + 1;


Vissza

119



120

or when contents > 0 => get ! buff[base]; base := (base + 1) mod 32; contents := contents - 1 end forever end;

A terminate alternatíva A buffer folyamattal kapcsolatban felmerül az a probléma, amelyet általánosan is meg kell oldani a párhuzamos program futása közben: mikor fejezze be egy folyamat a futását? Aktív folyamat esetén a válasz egyszerű: nyilván akkor, ha befejezte a tevékenységét (saját maga dönt). Passzív folyamatra a megoldás jóval nehezebb: ő akkor terminálhat, ha már nincs szüksége rá egyik aktív folyamatnak sem, és később sem lesz. Ezt úgy tudjuk mérni, hogy nyomon követjük a passzív folyamat használatát, és ha már az összes megfelelő aktív folyamat terminált, akkor fejezheti be a futását a passzív folyamat is. Bonyolult programstruktúra esetén ezen megoldás programozása nagyon bonyolult. Egy passzív folyamat esetleges túl korai terminálása deadlockhoz vezet, hiszen a már terminált passzív folyamatot használni kívánó aktív társ végtelen ideig várakozni kényszerül. Ezen probléma megoldására vezették be a terminate alternatívát a select konstrukción belül. A terminate alternatíva általános alakja: select in ? TetszőlegesVáltozó; or terminate end

A terminate alternatíva használatára a következő teljesül: Egy terminate alternatívás select utasítást futtató folyamat akkor és csak akkor fejezi be a futását, ha nincsenek el nem intézett hívások, és az összes folyamat, amely hívhatná a select utasítást már vagy terminált, vagy egy terminate alternatívás select utasításon várakozik.


Vissza

120



121

A Pascal-FC folyamatstruktúrája viszonylag egyszerű, ezért ha az ütemező nem talál futtatható folyamatot, akkor csak a következő három eset valamelyike következhet be: 1. minden folyamat terminált; 2. néhány folyamat várakozik csatorna műveleteken vagy sima select utasításokon; 3. minden nem terminált folyamat valamely select-terminate alternatíván várakozik. További teendők az egyes esetekben: 1. cobegin ... coend struktúra vége, esetleges további szekvenciális programrészek végrehajtása; 2. ez feloldhatatlan várakozás (deadlock) – a programot kívülről le kell állítani; 3. minden még várakozó folyamat terminálhat, esetleges további programrészek végrehajtása. Mivel a fenti 3. pont egy direkt suspended → terminated átmenetet valósít meg, a Pascal-FC-ben a terminate alternatíva bevezetése után ki kell bővítenünk a folyamatok állapotdiagramját (lásd 4. fejezet). A terminate alternatíva használatával a buffer folyamatot tökéletesíthetjük a következő módon: process buffer(var put, get: intchan); ... (* mint korábban *) contents := contents – 1; or (* új rész *) terminate end forever end;

Ha a termelő és a fogyasztó befejezte a futását, akkor a buffer folyamat is terminál, mert a futtatórendszer észreveszi, hogy nincs rá szükség a továbbiakban. Ez még akkor is így történik, ha esetleg maradt a bufferben adat


Vissza

121



122

(ez nyilván hiba, a fogyasztó túl hamar terminált), sőt ilyenkor ezzel az egyébként biztosan bekövetkező holtpontot is elkerüljük. A díszkert problémánál is segít a terminate alternatíva használata. Az eddigi megoldások kifogásolhatók olyan tekintetben, hogy a számláló (counter) folyamatnak előre meg kellett adni az összes leendő belépő számát („bűvös konstans”, lásd például GARDENC3.PFC). Terminate alternatíva nélkül ezt a logikai hibát csak nehézkesen tudjuk elkerülni. Egy lehetséges megvalósítás a következő: a forgóajtók az összes látogató beléptetése után egy szinkronizációs csatornán jelzik a befejezést a számlálónak, az pedig ennek megfelelően befejezi a tevékenységét, ha mindkét forgóajtótól megkapta a lezáró jelet (ekkor már tudja, hogy a továbbiakban nincs szükség rá). process type turnstile(name, num: integer); var loop: integer; begin for loop := 1 to num do paths[name] ! 1; closedown[name] ! any end; (* turnstile *) process counter; var count: integer; i, j, temp: integer; continue: array[1..2] of boolean; begin count := 0; continue[1] := true; continue[2] := true; while continue[1] or continue[2] do select paths[1] ? temp; count := count + temp; or paths[2] ? temp; count := count + temp;


Vissza

122



123

or

closedown[1] ? any; continue[1] := false;

or

closedown[2] ? any; continue[2] := false end; (* select *) writeln(’Total admitted: ’,count) end;

Terminate alternatíva használatával a megoldás jóval egyszerűbb: process counter; var count: integer; i, j, temp: integer; begin count := 0; repeat select paths[1] ? temp; or paths[2] ? temp; or terminate end; (* select *) count := count + temp forever; writeln(’Total admitted: ’,count) end;

Példaprogram (megvalósítás): GARDENC5.PFC (26) Bár első áttekintés után nem feltétlenül nyilvánvaló, de ez a megvalósítás még hibás. Sosem fogja kiírni az összes belépő számát! Ennek oka az, hogy a számláló eljárásból a terminate alternatíváról lépünk ki, így az utána elhelyezkedő kiíró utasítás már nem hajtódik végre. Ezen úgy tudunk javítani, ha a kiíratást áttesszük a főprogramba, ehhez pedig az kell, hogy a számláló folyamat paraméterként visszaadja a count változó értékét. Példaprogram (megvalósítás): GARDENC6.PFC (27)


Vissza

123



124

Az else alternatíva Előfordulnak olyan esetek, amikor az egyik folyamat nem akar meghatározatlanul sokat várni a csatornarandevúra egy megbízhatatlan partner miatt. Ilyenkor két lehetőség van a feloldásra: • ha a randevú nem lehetséges, akkor azonnali kilépés és más tevékenység (else); • valamennyi várakozás után ugyanez, ha közben nem jött létre a randevú (timeout). Egy else alternatívás select konstrukcióban a folyamat sosem lesz blokkolt állapotban. Az else alternatíva általános alakja: select in ? TetszőlegesVáltozó or out ! TetszőlegesÉrték else (* tetszőleges tevékenységek *) end

Az else alternatívát olyan esetekben célszerű használni, amikor a folyamat bármikor kaphat speciális input adatokat (amelyek hatására pl. befejezi a tevékenységét), de amennyiben nem érkezik ilyen adat, akkor saját akciót kell neki kezdeményeznie. Ezzel az eszközzel ki tudjuk javítani a korábbi (végtelen ideig futó) prímgenerátor programot a következő módon: ha már generáltuk az összes szükséges számot, akkor egy szinkronizációs csatornán leállítjuk a numbers folyamatot. Megoldás (részlet): type synchan = channel of synchronous; ... process numbers(var out: chan; var stopchan: synchan); var i: integer; stopnumbers: boolean;


Vissza

124



125

begin i := 2; stopnumbers := false; while not stopnumbers do select stopchan ? any; stopnumbers := true else out ! i; i := i + 1 end end;

Írjuk meg a leálló prímgenerátort a többi folyamat esetlegesen szükséges módosításával. Használjuk a terminate alternatívát is. (2,5)

A timeout alternatíva Ezt az alternatívát a valósidejű programozásban használjuk. Ilyenkor nem megengedhető a végtelen ideig tartó várakozás, ugyanakkor célszerű bizonyos időt hagyni a megelőző cselekvések előtt, hátha „befut” a késő folyamat. A timeout alternatíva általános alakja: select in ? TetszőlegesVáltozó or timeout 3; (* várakozás megadott másodpercig *) (* timeout esetén végrehajtandó tevékenységek *) end

Tipikus alkalmazás a nagyon lassú vagy hibásan működő folyamatok megfogása. Ha a megadott időtartamig nem történt randevú, akkor a timeout ágban megadott utasítások hajtódnak végre (pl. kiírjuk, hogy letelt a rendelkezésre álló idő). Példaprogram: TIMER.PFC (28)

Prioritásos select Bár a select konstrukciót logikailag úgy építettük fel, hogy a nemdeterminisztikus választást valósítsa meg, bizonyos esetekben szükséges lehet a selectben a determinisztikus választás is.


Vissza

125



126

Például tekintsük azt az ellenőr folyamatot, amely azt vizsgálja, hogy az input adatok beleesnek-e egy [−K, K] intervallumba, ahol K értéke szintén kívülről érkezik. A feladat jellegéből következik, hogy az esetlegesen érkező új K „fontosabb”, mint a többi input adat, hiszen ha továbbra is a régi K-val dolgozunk, akkor a válasz megbízhatatlan lesz. Az első megoldási kísérletben az ellenőr folyamat az első K értéket leolvasva lép be a repeat … forever ciklusba. Ha egyszerre érkezik új K és V input adat a csatornákon, a nemdeterminisztikusság miatt semmi sem garantálja, hogy K értéke jut át először, sőt rossz esetben akár több V-t is beolvashatunk, mire az új K is átér. Kchan ? K; (* első K *) repeat select Kchan ? K or inp ? V; if (V <= K) and (V >= -K) then out ! V end forever

Javít a helyzeten az else alternatíva használata. Kchan ? K; (* első K *) repeat select Kchan ? K else null end; select Kchan ? K; or inp ? V; if (V <= K) and (V >= -K) then out ! V end forever


Vissza

126



127

Ez a változat már csak legfeljebb egy „rossz” számot kér be, ugyanis a következő végrehajtáskor az első select biztosan megfogja az új K számot (ha nincs új K érték, akkor nem történik semmi). A jó megoldáshoz olyan select utasítás szükséges, amelyben előre lehet definiálni az ágak végrehajtását, ha közülük egynél több választható. Kchan ? K; (* első K *) repeat pri select Kchan ? K or inp ? V; if (V <= K) and (V >= -K) then out ! V end forever

Amennyiben a Pascal-FC prioritásos selectjében több lehetőség választható, akkor a kitüntetett ág lesz az első. Eszerint ha K és V érték egyszerre érkezik a csatornákra, akkor a K érték élvez előnyt, és csak utána következik a V.

A select alternatívák együttes használata A Pascal-FC selectjét úgy valósították meg, hogy ágaiban legalább egy csatornaműveletet mindig használni kell (input vagy output), de több ilyen művelet is használható. Az alternatívák esetleges együttes alkalmazását átgondolva belátható, hogy ez a szándék hiábavaló lenne. Ha van ugyanis else alternatíva, akkor a timeout sosem hajtódna végre. A terminate alternatíva alkalmazása pedig felteszi, hogy a folyamat késleltetett, így mellette sem az else, sem a timeout nem lehet értelmes. A Pascal-FC ezért tiltja az alternatívák együttes használatát.

Alkalmazás: az étkező filozófusok problémája Az étkező filozófusok probléma korábbi megoldási kísérletében a villák paszszív objektumok voltak, és csak kölcsönös kizárással lehetett őket használni. Ez livelockhoz vezetett. Most ezt a megoldási kísérletet „átfordítjuk” a csatornamodellbe. A villák is folyamatok lesznek, a filozófusok és a villák szinkronizációs csatornákon keresztül kommunikálnak egymással. Ha egy villára már nincs szükség, futását befejezi a terminate alternatíva segítségével.


Vissza

127



128

A folyamattípusok a következők: process type villatipus(hely: integer); begin repeat select balfel[hely] ? any; balle[hely] ? any; or jobbfel[hely] ? any; jobble[hely] ? any; or terminate end; forever; end; process type filozofustipus(nev: integer); var i: integer; villa1, villa2: integer; begin villa1 := nev; if nev = n then villa2 := 1 else villa2 := nev + 1; for i := 1 to 10 do begin sleep(random(2)); (* gondolkodik *) balfel[villa1] ! any; jobbfel[villa2] ! any; etkezik := i; writeln(i:2, nev:2); sleep(random(2)); (* eszik *) jobble[villa2] ! any; balle[villa1] ! any; end; end;

Példaprogram (megvalósítás): FILOCSAT.PFC (29) Mivel a programban szereplő logikai hibát nem javítottuk, a korábbi livelockból most deadlock keletkezik. Lényeges azonban hangsúlyozni, hogy deadlock nem következik be minden esetben, előfordulhat az is, hogy a program több futtatás során is látszólag jól működik.


Vissza

128



129

Gyűjtsünk gyakorlati tapasztalatokat a deadlock előfordulásának esélyéről úgy, hogy többször lefuttatjuk a programot különböző sleep értékekre! (1) A Pascal-FC a deadlockot csalhatatlanul észreveszi: ekkor minden még létező folyamat blokkolva várakozik valamely másik folyamatra (és nem a terminate alternatíván). Ha a deadlock ténylegesen bekövetkezett, a PascalFC a végtelen blokkolt várakozást leállítja, és kiírja, hogy a program futása deadlock következtében megszakadt. Esetünkben például a következő üzenetet kaphatjuk: Abnormal halt in process villa[1] with pc = 15 Reason: deadlock See pmdfile for post-mortem report

Ilyenkor a Pascal-FC a program állapotáról egy „halál utáni” leírást készít (post-mortem description), amelyet a pmdfile-ban helyez el. A pmdfile a folyamatok aktuális (blokkolt) állapotát mutatja az állapotdiagram szerint (suspended), továbbá információ ad arról, hogy a folyamat melyik utasításon várakozik, és mennyi most a pc (program counter) értéke. Végül kiírja a globális változók értékét is. A most keletkező pmdfile egy részlete: Pascal-FC post-mortem report on filozofuso - Interpreter Version P5.3 Abnormal halt in process villa[1] with pc = 15 Reason: deadlock ---------Main program Status: awaiting process termination ---------Process filozofus[1] Status: active pc = 67 Process suspended on: jobbfel[2] (channel)


Vissza

129


A csatornamodell


Vissza

130

---------Process villa[1] Status: active pc = 15 Process suspended on: balle[1] (channel) ---------Process filozofus[2] ... ========== Global variables etkezik = i =

8 4

Értelmezzük, hogy mit mutat a globális változók értéke!

(1)

Az occam nyelvi csatornamodell A csatornamodell alapjait eredetileg a CSP formalizmusban rögzítették, ez alapján fejlesztették ki az occam nyelvben, és innen került át a Pascal-FCbe. A csatornák használata az occamban nagyon hasonlít a Pascal-FC-beli használathoz, de van néhány fontos különbség. Az occam egy általános célú, gyakorlatias párhuzamos nyelv, folyamatmodellje bonyolultabb, mint a Pascal-FC nyelvé. Az occamban megengedett az egymásba ágyazott cobegin ... coend struktúrák használata (ott PAR-nak hívják), és a folyamatokat nem névvel azonosítjuk, bármely kód egy PAR belsejében önálló folyamatként fut (emlékeztető: ez a mi kategorizálásunk szerint az I. modell – lásd 64. oldal). Ugyanakkor az occam nyelv select konstrukciója „gyengébb”, mint a Pascal-FC-beli: • a szelektív várakozásban (ALT-nak hívják) nem lehet csatorna írás; • nincs terminate alternatíva. Ezeket a megkötéseket a gyakorlati megvalósítás nagy költségei miatt vezették be (az occam nyelvet a transputerekben is használják). Tekintsük


Vissza

130



131

például a következő nemszimmetrikus selectet (Pascal-FC szintaktikával bemutatva): var chan: channel of SomeType; ... select (* in process P *) chan ? variable; or ... end; ... select (* in process Q *) chan ! value; or ... end; ...

Itt szelektív várakozás lehetséges ugyanazon csatorna mindkét végén, valódi párhuzamos végrehajtás esetén. A gondot az okozza, hogy ha P és Q egyszerre ér oda a selecthez, akkor nehéz annak az eldöntése, hogy a select ágon lehetséges-e a kommunikáció. Bár ilyen protokollok léteznek, úgy találták, hogy alkalmazásuk túl időigényes lenne, ezért inkább a selectet korlátozták a fenti módon. Egyprocesszoros rendszerben ez a probléma nem merül fel, hiszen vagy P vagy Q érkezik először, és utána a második érkező dönt. Hasonló okok miatt hagyták el a terminate alternatívát is: sok párhuzamosan futó folyamat esetén (valódi párhuzamosság többprocesszoros rendszerben) egy adott pillanatban nehéz megállapítani, hogy a terminálás lehetséges-e. E lehetőség hiánya a programozó munkáját nehezíti: ha mégis szükséges a terminate alternatíva, akkor azt direktben kell programozni, és ez sok hibalehetőséget vet fel.


Vissza

131



132

Gyakorló feladatok a fejezethez Írjuk meg a leálló prímgenerátort terminate alternatíva nélkül.

(2,5)

Írjuk meg a buffer folyamatot az occam nyelvi modellben (nincs terminate alternatíva) (2) Készítsünk megoldást csatornamodellben a stabil házasság problémára. Eszerint van n férfi és n női folyamat. A férfiak pontozzák a nőket, és fordítva. Egy házasság nem stabil, ha egy férfi magasabbra pontoz egy nőt, mint a saját feleségét, és az a nő is magasabbra pontozza őt, mint a saját férjét. Hozzuk létre a folyamatokat, osszuk ki a pontokat (egy tömb minden folyamathoz), és döntsük el, hogy az adott pontozás mellett van-e instabil házasság. (3) Készítsünk megoldást csatorna modellben a kliens-szerver problémára. Egy szerverfolyamat lehetővé teszi a kliensek számára, hogy üzenetet (pl. egész szám) juttassanak el más kliensekhez. A „célcsoport” folyamatai számára nem kötjük meg, hogy milyen sorrendben veszik az üzenetet. (2,5)


Vissza

132



Irodalomjegyzék Vissza

133

Irodalomjegyzék [1] [2] [3] [4] [5] [6]

Alan Burns – Geoff Davies: Concurrent Programming. 1994, Addison-Wesley Publishing Company. omas H. Cormen – Charles E. Leiserson – Ronald L. Rivest: Algoritmusok. Budapest, 1998, Műszaki Könyvkiadó. Keith O. Geddes – Stephen R. Czapor – George Labahn: Algorithms for Computer Algebra. 1991, Kluwer Academic Publishers. Marton László – Fehérvári Arnold: Algoritmusok és adatstruktúrák. Győr, 2002, NOVADAT. Jagdish Modi: Paralell Algorithms. 1986, Oxford University Press. Andrew S. Tannenbaum: Számítógép-architektúrák. Budapest, 2001, Panem kiadó.


Vissza

133


Párhuzamos programozás A jegyzet használata | Tartalomjegyzék | Tárgymutató Vissza 134 ABCDEFGHIJKLMNOPQRSTUÜVWXYZ

Név- és tárgymutató A

F

Ada nyelv 63, 66, 67

fair ütemező 76 fa hálózat 43 folyamat 49 folyamatmodell 63, 70 futtatható állapot 70 futtatórendszer 72

B Bakery-algoritmus 95 bankár algoritmus 101 beágyazott rendszer 54 Ben Ari 76 bit szervezésű processzor 28 blokkolt állapot 71, 80, 81 buffer folyamat 118 busy waiting 85, 96

C CM-gép 35 cobegin … coend struktúra 48, 67 Cray-1 32 CRAY T3E 41

D DAP-gép 34 Davies 76 deadlock 97, 128 Dijkstra 89, 101 dinamikus programozás 13 díszkert probléma 86, 122

E éhezés 50, 98, 104 EREW modell 21 étkező filozófusok 103, 127 euklideszi algoritmus 19

G Gauss-elimináció 15 gyorsrendezés 8

H hálózat 42 hiperkocka-kapcsolás 35 hiperkocka hálózat 43 Hoare 109

I IBM 701 29 időosztásos módszer 50, 53 integrált memóriamodul 29 író-olvasó probléma 96

K keverő hálózat 43 kölcsönös kizárás 61, 113 kommunikáció 58 közös változó 87 kritikus szakasz 61, 90


Vissza

134

Párhuzamos programozás A jegyzet használata | Tartalomjegyzék | Tárgymutató Vissza 135 ABCDEFGHIJKLMNOPQRSTUÜVWXYZ

L Lady Lovelace Byron 24 Lamport 95 lazán csatolt rendszer 28 lisfile 74 livelock 92, 94, 97 logikai processzor 50

M MIMD gépcsalád 38 mohó algoritmus 13 MP-1 gépcsalád 37 MPP gépcsalád 41 multiprocesszor 39 multiprogramozás 53 multiszámítógép 39

N nemdeterminisztikusság 52 nemdeterminisztikus választás 115 nem fair ütemező 76 Neumann-elv 30, 46 Neumann János 24 null utasítás 62, 126

prioritás 57, 127 processzor cube 28 processzor farm 28

R rekurzió 8 repeat ... forever ciklus 62 részben rendezettség 51 RISC processzor 33

S SIMD gépcsalád 31 SISD gépcsalád 30 sleep eljárás 77, 80 szekvenciális program 46 szelektív várakozás 113 szemafor 89 szinkronizáció 58, 83 szorosan kapcsolt rendszer 28

T termelő-fogyasztó probléma 84, 109 tömbprocesszorok 33 transputer 40, 130

O

U

objfile 74 occam nyelv 109, 130 Ordó jelölés 6 osztottváltozós modell 39 osztott memóriamodul 29

üzenetváltásos modell 39, 84, 107

P

V valósidejű programozás 125 valós idejű rendszerek 50, 76, 79 vektorprocesszor 31

P-CRCW modell 21 párhuzamossági operátor 49 Peterson 90, 94 pillangó hálózat 43 pipeline-technika 31, 47 polinom-faktorizáció 17 PRAM-gép 7, 54


Vissza

135

Párhuzamos programozás

Recommend Documents