Párhuzamos programozás (Párhuzamos és osztott rendszerek) v.08

Párhuzamos programozás (Párhuzamos és osztott rendszerek) v.08 Schrettner Lajos ([email protected]) 2007. január 3.

Tartalomjegyzék 1. Bevezetés 1.1. Párhuzamos számítógéprendszerek . . . . . . 1.1.1. Hardver . . . . . . . . . . . . . . . . . . 1.1.2. Szoftver . . . . . . . . . . . . . . . . . . 1.1.3. Hardver és szoftver . . . . . . . . . . . . 1.2. A párhuzamos programozás jellemz˝oi . . . . . 1.2.1. Folyamatok muködése ˝ . . . . . . . . . . 1.2.2. Folyamatinterakciók . . . . . . . . . . . 1.2.3. Párhuzamos programok hatékonysága 1.2.4. „Törvények” . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

4 4 4 5 6 6 7 8 9 9

2. Osztott memóriás programozás 2.1. Üzenetek kezelése . . . . . . . . . . . . . . . . . 2.1.1. Címzés . . . . . . . . . . . . . . . . . . . 2.1.2. Szinkron és aszinkron kommunikáció . 2.1.3. Kommunikáció több folyamattal . . . . 2.2. O CCAM . . . . . . . . . . . . . . . . . . . . . . . 2.2.1. Csatornák, protokollok . . . . . . . . . . 2.2.2. Párhuzamos konstrukciók . . . . . . . . PAR . . . . . . . . . . . . . . . . . . . . . Többszörös értékadás . . . . . . . . . . ALT . . . . . . . . . . . . . . . . . . . . . 2.2.3. Cs˝ovezetékek . . . . . . . . . . . . . . . Rendezés . . . . . . . . . . . . . . . . . . Struktúraütközés . . . . . . . . . . . . . Aszinkron kommunikáció . . . . . . . . 2.2.4. További példák . . . . . . . . . . . . . . Hatékonyabb aszinkron kommunikáció 2.3. PVM . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Áttekintés . . . . . . . . . . . . . . . . . 2.3.2. Megvalósítás, használat . . . . . . . . . 2.3.3. Programszerkezet . . . . . . . . . . . . . 2.3.4. Taszkkezelés . . . . . . . . . . . . . . . . 2.3.5. Kommunikáció . . . . . . . . . . . . . . Üzenetküldés . . . . . . . . . . . . . . . Üzenetfogadás . . . . . . . . . . . . . . 2.3.6. Szinkron kommunikáció . . . . . . . . . 2.3.7. Cs˝ovezetékes rendezés . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

11 11 11 12 12 13 13 15 15 18 18 20 20 22 24 24 24 26 26 26 26 27 28 28 29 30 31

2

Taszk szerkezet kialakítása Feldolgozás . . . . . . . . . 2.3.8. Processzor farm . . . . . . . 2.4. MPI . . . . . . . . . . . . . . . . . . 2.5. Grid . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

31 31 32 32 32

3. Közös memóriás programozás 3.1. Szemafor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Szemafor definíciója . . . . . . . . . . . . . . . . . . Kölcsönös kizárás szemaforral . . . . . . . . . . . . Szinkronizáció szemaforral . . . . . . . . . . . . . . 3.1.2. Szemafor implementációja . . . . . . . . . . . . . . . 3.2. Monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1. Termel˝o-fogyasztó probléma (Produ er- onsumer) . Termel˝o-fogyasztó probléma megoldása monitorral 3.3. J AVA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1. Párhuzamosság J AVA-ban . . . . . . . . . . . . . . . Szálak . . . . . . . . . . . . . . . . . . . . . . . . . . Szálinterakció (J AVA 1.4 verzióig) . . . . . . . . . . . J AVA 1.5 verzió b˝ovítései . . . . . . . . . . . . . . . . 3.3.2. Olvasók-írók probléma (Readers-Writers) . . . . . . 3.3.3. Étkez˝o filozófusok (Dining philosophers) . . . . . . . 3.3.4. Alvó borbély probléma (Sleeping barber) . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

33 33 33 34 34 35 36 36 38 38 38 38 40 42 44 46 49

3

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

1. fejezet

Bevezetés 1.1. Párhuzamos számítógéprendszerek Egy rendszer egységes egészet alkotó komponensekb˝ol áll, amelyek egymással kapcsolatban, kölcsönhatásban vannak. Most számítógéprendszerekr˝ol van szó, ezeken belül párhuzamosság szempontjából vizsgáljuk a hardver és szoftver alrendszereket. A párhuzamosság azt jelenti, hogy egyid˝oben több komponens muködik. ˝ Az osztott (distributed ) jelz˝o a párhuzamos speciális esete, amikor a rendszer komponensei térben elkülönülten helyezkednek el. Gyakran használt jelz˝o még a konkurrens ( on urrent ), ami gyakran azt hangsúlyozza, hogy a rendszer komponensei vetélkednek egymással az er˝oforrásokért. A párhuzamosságnak két el˝onye van a szekvenciális programozással összehasonlítva: • gyorsabb, hatékonyabb programvégrehajtás megfelel˝o hardver esetén (hardver szempont) • természetesebb kifejezésmód lehet˝osége a nagyobb számú elemi muvelet ˝ segítségével (szoftver szempont) A második lehet˝oségr˝ol gyakran megfeledkeznek, pedig legalább ugyanolyan fontos, mint az els˝o. A több elemi muvelet ˝ abból adódik, hogy a párhuzamos nyelvek általában tartalmaznak egy szekvenciális nyelvet részhalmazként. Ismeretes, hogy a programozási nyelvek egyik f˝o feladata, hogy segítsenek áthidalni a probléma megfogalmazása (specifikáció) és a megoldás (program) közötti koncepcionális szakadékot. Minél több független épít˝oelemet, konstrukciót használhatunk munkánk során, annál könnyebbnek ígérkezik ez a feladat.

1.1.1.

Hardver

A párhuzamos hardver rendszerek sokféleképpen rendszerezhet˝ok, az egyik máig is használt a Flynnféle, amelyben a komponensek a processzor, memória és a vezérl˝o (controller). A processzor(ok) a vezérl˝ot˝ol kapják a végrehajtandó utasítássorozatot (instruction stream), a memóriá(k)ból pedig a feldolgozandó adatokat (data stream). Négy f˝o csoportot különböztetünk meg aszerint, hogy hány utasításfolyam (Instruction stream), illetve adatfolyam (Data stream) különíthet˝o el a rendszerben. Mindkét fajta folyam egyszeres (Single), vagy többszörös (Multiple) lehet. • SISD (Single Instruction stream, Single Data stream) • SIMD (Single Instruction stream, Multiple Data stream) • MISD (Multiple Instruction stream, Single Data stream) 4

• MIMD (Multiple Instruction stream, Multiple Data stream) A SISD elrendezés a hagyományos Neumann-féle szekvenciális számítógépnek felel meg. A SIMD és MISD csoportokhoz speciális célú számítógépek tartoznak. Legfontosabb csoport a MIMD, melyben két alosztályt különböztetünk meg aszerint, hogy a processzorok közötti adatcsere egy közös memórián keresztül (shared memory MIMD , SM-MIMD ), vagy üzenetküldéses kommunikációval (distributed memory MIMD , DM-MIMD ) valósul-e meg. A MIMD csoportba sorolhatók a manapság elterjedten használt párhuzamos számítógépek. SMMIMD gép például egy többprocesszoros PC, vagy az ilyen felépítésu, ˝ nagyobb teljesítményu˝ szerverek, munkaállomások. DM-MIMD gépekre példa a közelmúltból a transzputer alapú rendszerek, melyek fejl˝odése és terjedése azonban a kezdeti sikerek után megállt. A lokális hálózatok és az internet terjedésével párhuzamos számítógépet legegyszerubben ˝ hálózatba kapcsolt számítógépekb˝ol építhetünk. Úgy is lehet fogalmazni, hogy a hálózatba kötött számítógépek egy párhuzamos számítógépet alkotnak, ehhez azonban egy megfelel˝o szoftver rétegre van szükség. Párhuzamos számítégépeket azért építünk, mert nagy számítási kapacitásra van szükségünk. Ebb˝ol következ˝oen az a párhuzamos architektúra a jobb, amelynek teljesítménye újabb komponensek hozzáadásával igény szerint növelhet˝o. Ha a MIMD gépeket tekintjük, akkor azt láthatjuk, hogy közös memória esetén a teljesítmény újabb processzorok hozzáadásával növelhet˝o, de csak egy bizonyos határig, mert a memóriahozzáférés során hamar szuk ˝ keresztmetszet alakul ki. Tipikusan maximum néhányszor 10 processzor helyezhet˝o el egymás mellett ilyen módon. Osztott memória esetén a rendszert egy olyan gráfnak képzelhetjük el, amelynek csúcspontjaiban autonóm feldolgozóegységek (pro essing element , PE ) helyezkednek el, az élek pedig a közvetlenül összekötött feldolgozóegységeket között találhatók. Egy ilyen gráfot könnyen b˝ovíthetünk új feldolgozóegységek beillesztésével, a változás csak azokat a csúcspontokat érinti, amelyekhez közvetlenül hozzákapcsoljuk az újat. Az el˝oz˝oek miatt tehát megállapíthatjuk, hogy a DM-MIMD architektúra el˝onyösebb, mert könnyebben b˝ovíthet˝o.

1.1.2.

Szoftver

A párhuzamos szoftver rendszerek, vagy más néven programozási modellek rendkívül sokfélék, most csak a legfontosabbak említése lehetséges. Ezek komponensei a folyamat (pro ess ) és a memória, amely itt magasabb szintu, ˝ mint a hardvernél, változók együtteseként tekintünk rá. A folyamat helyett használatos a végrehajtási szál (thread ), illetve a feladat (task ) elnevezés is. Minden folyamat futását a programja vezérli. Ezt a két fogalmat fontos megkülönböztetnünk, mert míg a program(szöveg) statikus, addig a folyamat a program futása közben létez˝o dinamikus objektum. A szekvenciális és a párhuzamos programot az különbözteti meg egymástól, hogy egy, vagy több végrehajtási szál található-e benne. A folyamatok használhatják a szokásos szekvenciális nyelveknél megismert utasításokat, ideértve természetesen a változók értékének kiolvasását és új érték beírását (értékadás). Ezen felül egy adott modell tartalmaz a párhuzamos számítások vezérléshez szükséges konstrukciókat, ilyenek például a folyamatok kezeléséhez és az azok közötti adatátadáshoz használt utasítások. Fontos megérteni, hogy a programozási modell egy absztrakt képz˝odmény. Nem mindig els˝odleges szempont a hatékony implementálhatóság, vagyis egy adott hardver architektúrára való leképezhet˝oség. Ennél sokkal fontosabb, hogy a modell megfelel˝o keretet biztosítson a problémamegoldáshoz, olyan eszközkészletet adjon a programtervez˝o kezébe, amelynek segítségével könnyen, hatékonyan meg tudja oldani a feladatokat. Ezek természetesen szubjektív szempontok, egyéni képességekt˝ol és el˝oélett˝ol függ˝oek. A két legfontosabb programozási modell történetesen nagyon közel áll a korábban ismertetett két hardver modellhez (SM és DM-MIMD), azok szoftver megfelel˝oinek tekinthet˝ok. A hasonlóság ellenére fontos mindig tisztáznunk, hogy hardverr˝ol vagy szoftverr˝ol beszélünk-e éppen. A közös memóriás párhuzamos programozási modell folyamatokból és egy közös memóriából áll. A közös memória azt jelenti, hogy a folyamatok ugyanazokat a változókat használhatják, akár egyid˝oben is megkísérelhetik o˝ ket olvasni/írni. Utóbbi szituáció kezelése jelenti a legnagyobb kihívást ebben a modellben. Az osztott 5

memóriás párhuzamos programozási modell folyamatainak olyan változói vannak, amelyeket azok kizárólagosan használhatnak, itt tehát az egyideju˝ hozzáférés ki van zárva. A folyamatok együttmuködése ˝ üzenetküldéssel (message passing ) valósul meg, ennek különböz˝o formái kés˝obb kerülnek ismertetésre. A folyamatok kezelése mellett tehát szükség van olyan utasításokra, amelyek az üzenetek kezelését lehet˝ové teszik. A két párhuzamos programozási modellt összehasonlítva elmondhatjuk, hogy a közös memória kezelését általában könnyebbnek tekintik, mint az üzenetküldéses problémamegoldást. Ennek egyik oka lehet, hogy a szekvenciális modellhez képest a közös memória „csak” a párhuzamos folyamatokat tartalmazza új elemként, míg az osztott memóriás az üzenetküldést is. Az osztott memóriás modell támogatói azzal érvelnek, hogy a folyamatok interakciója közös memória esetén is odafigyelést, speciális konstrukciókat igényel, s˝ot, ezek kevésbé elegánsak, mint az üzenetküldés. Mindezeket az érveket összegezhetjük azzal, hogy mindkét modellnek van létjogosultsága, a modellek hardverre történ˝o leképezési lehet˝oségeit azonban érdemes még megvizsgálni.

1.1.3.

Hardver és szoftver

Általánosságban elmondhatjuk, hogy a hardver és a szoftver rendszer független egymástól, vagyis bármely hardveren bármely programozási modell implementálható. Fontos megérteni, hogy ez azt is jelenti, hogy a párhuzamos programozás során felmerül˝o nehézségek, megoldandó problémák csak a modellt˝ol függnek, hardver paramétereket csak hatékonysági szempontokból szükséges figyelembe vennünk, ezt viszont – ahogy szekvenciális programozás esetében is – legjobb a programfejlesztés utolsó fázisára hagyni. A gyakorlatban a hatékonysági szempontokat nyilván alaposan mérlegeljük, miel˝ott a megvalósításról döntünk. Minden esetben a folyamatok egyenként vagy valamilyen módon csoportosítva a processzorokra kerülnek, különbség a memória használatában van. Az egymásnak megfelel˝o hardver és szoftver modellek könnyen összeilleszthet˝ok, természetes módon a változók a megfelel˝o memóriamodulokba kerülnek, muködés ˝ közben semmilyen nehézség nem lép fel. „Keresztben” már nem ennyire egyértelmu˝ a helyzet, ekkor az a könnyebb eset, amikor közös memóriás hardverre képezzük le az osztott memóriás programozási modellt, hiszen a közös memóriából könnyu˝ „osztott”-at csinálni úgy, hogy minden folyamat kap egy külön részt. A közös memóriás modell leképezése osztott fizikai memóriára nehéz. Nem adódik egyértelmu˝ megoldás, hiszen elkerülhetetlen, hogy az adatokat „szétterítsük” a memóriamodulok között, ekkor viszont a folyamatok számára nem feltétlenül tudjuk biztosítani, hogy az elérni kívánt adatok a feldolgozóegység memóriájában legyenek. A más feldolgozóegységekben tárolt adatok elérése nem lehetetlen, de sokkal több id˝ot vesz igénybe, mert az üzenetküldés a mai technológia mellett egy nagyságrenddel nagyobb id˝oigényu˝ muvelet, ˝ mint a közvetlen memóriaelérés. Az egységes elérés logikailag tehát megoldható, az elérési id˝oket pedig különféle technikákkal próbálták meg csökkenteni (adatok többszörözése, speciális gyorsítótárak alkalmazása), de a lokális és a távoli elérés közötti különbségek nem tüntethet˝ok el. Az utóbbi megoldást alkalmazó rendszereket NUMA (Non-Uniform Memory Access) számítógépeknek nevezzük. Azért fektettek ezek kutatásába nagy energiát, mert az osztott hardver és a közös memóriás szoftver elvileg ötvözné mindkét oldal el˝onyeit, könnyen b˝ovíthet˝o és könnyen programozható rendszert alkotva. Sokan az osztott programozási modellt eleve el˝onyben részesítve az osztott hardver/osztott szoftver megoldást tartják a legjobbnak. Nem lehet egyértelmuen ˝ egyik vagy másik modellt jobbnak nevezni, ezért mindkett˝ot érdemes tanulmányozni.

1.2. A párhuzamos programozás jellemzoi ˝ A legegyszerubben ˝ úgy kerülhetünk párhuzamos programozási környezetbe, ha veszünk egy hagyományos szekvenciális programozási nyelvet és kiegészítjük párhuzamos konstrukciókkal a folyamatkezelés és interakció kezeléséhez. Ennek a megközelítésnek vannak azonban hátrányai, ugyanis a ki6

egészítések nem feltétlenül illeszkednek hézagmentesen az alapnyelvbe, s˝ot legtöbbször csak egy eljárásgyujteményt ˝ kapunk, amelynek elemei a programokból hívhatók. Pontosan ez a helyzet, ha pl. a C nyelvet tekintjük kiegészítve bizonyos Linux (Unix) rendszerhívásokkal. Ezzel a módszerrel akár közös memóriás, akár osztott memóriás modellben is programozhatunk. Másik példa a PVM (Parallel Virtual Machine) rendszer, amellyel a C (vagy Fortran) nyelvb˝ol kiindulva hozhatunk létre lokális hálózaton hardver és szoftver szempontból is osztott memóriás párhuzamos számítógépet. Elegánsabb megközelítés, ha egy programozási nyelvet eleve a párhuzamosság figyelembevételével terveznek, ekkor egységes jelölésrendszert használhatunk szekvenciális és párhuzamos program fejlesztésekor egyaránt, illetve az el˝oz˝o esettel ellentétben a fordítóprogram támogatást adhat a programhibák kiszuréséhez. ˝ Jó példa jól megtervezett párhuzamos nyelvre az O CCAM, amely az osztott memóriás modellt támogatja. A J AVA-t szintén sorolhatjuk a párhuzamosságot nyelvi szinten támogató nyelvek közé, noha a szükséges elemek csak az osztályhierarchiában mint adattagok és metódusok jelennek meg, de a virtuális gépnek ezeket alacsonyabb szinten támogatnia kell. Egy probléma párhuzamos programmal való megoldásakor az egymástól (részben) független részfeladatok azonosítása a legnehezebb. A részfeladatokra bontás (más néven dekompozíció) kétféle lehet: Funkcionális dekompozíció során az algoritmust bontjuk olyan részekre, amelyek egymással párhuzamosan futtathatók. Az egyes adatelemek a teljes feldolgozásáig szükség szerint több folyamathoz is eljutnak. Adat dekompozíció során a feldolgozandó adatokat particionáljuk és az egyes részeket párhuzamosan dolgozzuk fel. A páhuzamosan futó folyamatok ilyenkor rendszerint ugyanazt az algoritmust valósítják meg, minden adatelemet csak egy (tetsz˝oleges) folyamathoz kell eljuttatni.

1.2.1.

Folyamatok muködése ˝

Ahhoz, hogy párhuzamos programot írjunk, az egyik legalapvet˝obb muvelet ˝ a folyamatlétrehozás. Létrehozás után a folyamatok általában azonnal aktívak lesznek, de van olyan rendszer is, amikor külön kell elindítani o˝ ket. A létrehozó és a létrehozott folyamat(ok) között rendszerint alá-fölérendeltségi viszony van, amit a rendszer nyilván is tart. Szekvenciális programnál a kezeletlen futás ideju˝ hibák (pl. nullával osztás) azonnali leállást okoznak. Párhuzamos programnál ezt nem is mindig lehet megtenni, hiszen egy hiba közvetlenül csak egy folyamatot érint, a többi ett˝ol függetlenül folytatódhat legalábbis addig amíg szüksége nem lesz olyan adatokra, amit a hibás folyamat szolgáltatott volna. Egy párhuzamos program általában egyetlen folyamat elindításával kezd˝odik, amely aztán tetszés szerint létrehoz újabbakat. Futási id˝on azt az id˝ointervallumot értjük, ami az indulásától az utolsó folyamatának befejez˝odéséig tart. Beszélhetünk a programok szemcsézettségér˝ol (granularity ), amely azt fejezi ki, hogy mennyire intenzív a folyamatok létrehozása/megszüntetése a futás során. Ha a program viszonylag kevés, de a program futási idejéhez képest hosszú életu˝ folyamatból áll, akkor ezt durva szemcsézettségnek ( oarse granularity ) nevezzük. A másik véglet, amikor sok rövid életu˝ folyamatunk van, ezt finom szemcsézettségnek (ne granularity ) nevezzük. A két véglet között közepes szemcsézettség (medium granularity ) is elképzelhet˝o. Az általunk vizsgált két modellben a folyamatok aszinkron módon muködnek, ˝ ami azt jelenti, hogy egymástól függetlenül futnak, nem tudjuk el˝ore megmondani, hogy egy lefutásnál két folyamat utasításai egymáshoz képest id˝oben milyen sorrendben hajtódnak végre. Két aszinkron folyamat együttes futását vizsgálva azok (gépi kódú) utasításainak bármely összefésül˝odése (interleaving ) el˝ofordulhat (beleértve az egyidejuséget ˝ is). Vannak szituációk, amikor szükséges, hogy a folyamatok egymáshoz viszonyított el˝orehaladása szabályozottabb legyen, vagyis bizonyos összefésül˝odéseket ki akarunk zárni. Ezeket az eseteket nevezzük folyamtinterakciónak, melyeknek sok fajtája lehetséges, de szokás három alapvet˝ot kiemelni (ezek képez(het)ik alapját a többinek): kölcsönös kizárás (mutual ex lusion), szinkronizáció és holtpont (deadlo k ). Az els˝o kett˝o szükséges bizonyos feladatok megoldásához, míg a holtpont egy nemkívánatos mellékhatás, amely programhibának tekintend˝o. 7

Közös jellemz˝oje a folyamatinterakcióknak, hogy a folyamatok várakozásra kényszeríthetik egymást, ha az utasítások nem kívánt összefésül˝odése csak így akadályozható meg. A várakozás megvalósítása kétféle módszerrel történhet: Aktív várakozás (busy waiting) A folyamat egy ciklusban újra és újra vizsgálja azt a feltételt, aminek teljesülése esetén továbbléphet. Ha csak lehet kerülni kell ezt a módszert, mert feleslegesen leköti a (egy) processzort. Tipikusan az operációs rendszer, vagy futtató környezet legalsóbb szintjein használják. Passzív várakozás A folyamat egy várakozási sorba kerülve blokkolódik, így nem használ fel er˝oforrásokat feleslegesen. A várakozási sorról levéve a folyamat újra futtatható állapotba kerül. Értelemszeruen ˝ ezt a megoldást kell el˝onyben részesíteni, ha csak lehetséges.

1.2.2.

Folyamatinterakciók

A kölcsönös kizárás szükségessége csak közös memória esetén lép fel, akkor, ha egy vagy több folyamat kezel egy közös er˝oforrást. (Er˝oforrás bármi lehet, amire a folyamatoknak szükségük lehet feladatuk elvégzéséhez, de mi mindig (összetett) változót használunk erre a célra. Az er˝oforrások általában korlátozott számban állnak rendelkezésre és egyszerre nem használhatja o˝ ket akármennyi folyamat, leggyakrabban egyszerre legfeljebb egy.) Egy adott R er˝oforrást kezel˝o programrészt a folyamat (R er˝oforrásra vonatkozó) kritikus szakaszának (szekciójának) nevezzük. Ugyanerre az er˝oforrásra vonatkoztatva a kölcsönös kizárás azt jelenti, hogy bármely id˝opillanatban legfeljebb egy folyamat tartózkodhat kritikus szekcióban. Ugyanezt a követelményt más kifejezéssel úgy is mondhatjuk, hogy a kritikus szakasz legyen atomi. Ez arra utal, hogy ha egy kritikus szakasz egyszer elkezd˝odött, akkor annak le kell futnia teljes egészében anélkül, hogy más folyamat kritikus szakaszbeli utasításai közbeékel˝odnének. A szinkronizációban két (fajta) folyamat vesz részt, küld˝o és fogadó. Mindkett˝oben kijelölünk egy szinkronizációs pontot azzal a követelménnyel, hogy a fogadó nem haladhat át a szinkronizációs pontján addig, amíg a küld˝o el nem érte a sajátját. Ezt a követelményt amiatt szoktuk megfogalmazni, mert a fogadónak szüksége van a küld˝o által el˝oállított adatokra, addig nem tudja folytatni a futását, amíg azokat meg nem kapta. Futás közben két eset lehetséges; vagy a fogadó folyamat ér el˝obb a szinkronizációs pontjához, vagy a küld˝o (a sajátjához). Az els˝o esetben a fogadó folyamat várakozásra kényszerül, be kell várnia amíg a küld˝o a saját szinkronizációs pontjához ér. Második esetben különböz˝o modellek különböz˝o viselkedést írnak el˝o. Az küld˝o bevárhatja a fogadót (ekkor viselkedésük szimmetrikus), vagy mindkét folyamat várakozás nélkül haladhat át a kijelölt ponton (ekkor a viselkedés asszimetrikus, hiszen csak a fogadó folyamat kerülhet várakozó helyzetbe). A holtpont egy nem kívánatos állapot, amely nem megfelel˝oen megtervezett folyamatinterakció során alakulhat ki. Lényege, hogy kett˝o vagy több folyamat között körkörös függés alakul ki, egyik sem tud haladni, amíg a sorban el˝otte lév˝o nem lép. Mivel a függés körkörös, saját erejéb˝ol egyik sem tud kiszabadulni a holtpontból. A holtpont elkerülése nagy körültekintést igényel és csak gondos tervezéssel lehetséges, mert az aszinkron folyamatok, illetve egyes esetekben bizonyos nyelvi elemek a párhuzamos programok futását nemdeterminisztikussá tehetik. Ez azt jelenti, hogy ugyanarra az inputra a program nem mindig ugyanazt az outputot adja. A nemdeterminisztikusság nem feltétlenül hátrány, vannak esetek amikor megengedhet˝o, s˝ot kívánatos, tehát kezelését el kell sajátítani. A holtponthoz hasonló nemkívánatos jelenség az ún. éhezés (starvation), amikor ugyan nem alakul ki holtpont, de egy vagy több folyamat soha nem kapja meg a szükséges er˝oforrásokat, így nem tudja elvégezni feladatát. Az éhezésmentesség is nehéz probléma, nyelvi eszközökkel sokszor nem is biztosítható, csak alacsonyabb szinten a futtató környezet, vagyis az implementáció adhat garanciákat. 8

1.2.3.

Párhuzamos programok hatékonysága

Amikor a sebesség, a hatékonyság növelése érdekében írunk párhuzamos programot, akkor természetesen szeretnénk valamilyen módon jellemezni programunk teljesítményét. Erre a célra szolgál két mér˝oszám, a gyorsulás (speedup) és a hatékonyság (efficiency). Fontos megjegyezni, hogy a programok viselkedését nagyon sok tényez˝o befolyásolja, ezek mindegyikének figyelembe vétele szinte lehetetlen. Emiatt a gyorsulás és a hatékonyság is inkább csak nagy vonalakban jellemzi, semmint abszolút értelemben min˝osíti a programokat. A gyorsulás (speedup) S(n) = T(1)/ T(n) képlettel definiált, ahol T(1) a program futási ideje 1 processzoron, míg T(n) ugyanaz n processzoron. Megjegyzend˝o, hogy „a program futási ideje” kifejezés további értelmezést igényel. Vagy egy konkrét inputra vonatkozik, vagy S(n) függ egy további rejtett változótól, az input méretét˝ol. Gyakoribb az els˝o értelmezés, amikoris egy (esetleg néhány) kiválasztott adathalmazon (inputon) vizsgálják a program viselkedését változó számú processzoron. A T(1) id˝o vonatkozhat a párhuzamos program 1 processzoron történt futtatásakor kapott értékre, de használhatunk tetsz˝oleges szekvenciális programot is összehasonlítási alapként. Könnyen belátható, hogy ha van egy egységnyi feldolgozandó munkánk, akkor párhuzamosítással abban az esetben járunk a legjobban, ha annyi pontosan egyenl˝o részre osztjuk a munkát, ahány processzorunk van. Ekkor n processzor esetén a párhuzamos futási id˝o pontosan n-ed része a szekvenciálisnak, vagyis S(n) = n. Ha bármelyik részmunka az optimálisnál rövidebb, akkor szükségképpen lesz annál hosszabb is, ezáltal a futási id˝o megnövekszik és a gyorsulás n-nél kisebb lesz. A munka egyenl˝o részekre való elosztásának követelménye úgy is megfogalmazható, hogy próbáljuk meg a program teljes futási ideje alatt a processzorokat „hasznos” munkával ellátni, vagyis folyamatosan terhelve tartani. Ez a terheléselosztás (load balan ing ), amely történhet statikusan és dinamikusan is. Az els˝o esetben a részfeladatok processzorokhoz rendelése már a program tervezése során megtörténik. Ez csak akkor alkalmazható, ha a részfeladatok számítási igénye el˝ore meghatározható. Gyakoribb eset, hogy a tényleges számítási igény csak futás közben derül ki, ekkor a terheléselosztási döntéseket a program futása közben kell meghozni. E dinamikus módszer esetén a terheléselosztás többletmunkát jelent ugyan, de a rendszer rugalmas. Egy gyakran használt dinamikus terheléselosztási rendszer a processzor farm. Ebben egy farmer folyamat felel˝os a feladat részfeladatokra bontásáért, a részfeladatok kiosztásáért, a részeredmények begyujtéséért, ˝ majd a végeredmény meghatározásáért. A részfeladatokat egyforma dolgozó (worker ) folyamatok dolgozzák fel. Amint valamelyik dolgozó szabaddá válik, a farmer azonnal kioszt neki egy részfeladatot, így biztosítva a folyamatos leterheltséget. A megfelel˝o muködéshez ˝ biztosítani kell, hogy jóval (általában egy nagyságrenddel) több részfeladat legyen, mint munkás. A processzor farm egyben az adatpárhuzamosság tipikus példája is. Nem mindig kifizet˝od˝o újabb processzorok „bevetése” még akkor sem, ha azokkal további sebességnövekedést lehetne elérni. A hatékonyság (efficiency) E(n) = S(n)/n egy 0 és 1 közé es˝o szám, amely azt próbálja meg kifejezni, hogy mennyire tudja a program kihasználni a rendelkezésre álló processzorokat.

1.2.4.

„Törvények”

A párhuzamos számítógépek megjelenésekor (1960-as évek) komoly viták folytak ezek használhatóságáról. Az el˝oterjeszt˝ojér˝ol Amdahl törvényének elnevezett összefüggés azt sugallja, hogy b˝oven elegend˝oek a szekvenciális számítógépek által nyújtott lehet˝oségek. A levezetés abból a jogos el˝ofeltevésb˝ol indul ki, hogy minden programnak vannak csak szekvenciálisan végrehajtható részei, ezek nem részesülnek a több processzor nyújtotta el˝onyökb˝ol, mert amíg egy közülük dolgozik, a többi tétlenül várakozik. Legyen egy adott inputra szekvenciális programunk futási ideje ts , amelynek egy bizonyos része ( f ts , ahol 0 < f < 1) csak szekvenciálisan hajtható végre. Tételezzük fel, hogy a maradék rész ((1 − f )ts ) teljesen ideális módon párhuzamosítható, vagyis n processzor esetén a párhuzamos futási id˝o 9

t p = f ts + (1 − f )ts /n lesz. Ekkor a gyorsulást az S(n) =

n ts = ... = tp 1 + (n − 1) f

képlet adja meg. Ha ábrázoljuk a gyorsulást a processzorok számának függvényében, akkor azt látjuk, hogy már kis f értékek (0.1-0.2) is súlyos korlátot jelentenek. Például f = 0.05 esetén a maximális gyorsulás 20 a processzorok számától függetlenül. A fenti eszmefuttatás ellenére a gyakorlatban jelent˝os gyorsulásokat értek el, ami arra mutat, hogy a választott megközelítés nem teljesen szerencsés. Valóban, Amdahl törvénye csak azt mondja, hogy ha van egy rögzített méretu˝ feladatunk, akkor egyre több processzort „rádobva” az elérhet˝o gyorsulás korlátozott. A valós alkalmazási körülményeket jobban leíró érveléssel állt el˝o Gustafson 1988-ban, o˝ kiindulási alapnak azt választotta, hogy a felhasználók bizonyos id˝ot hajlandók áldozni a program futtatására. Akkora méretu˝ feladatot választanak, ami még kivárható id˝on belül megoldható, vagyis a párhuzamos futási id˝ot kell adottnak tekinteni, nem a probléma méretét. További gyakorlati szempontból megalapozott el˝ofeltevés, hogy a program csak szekvenciálisan végrehajtható részének aránya nem növekszik a feladat méretével együtt. A párhuzamos futási id˝ot állandónak tekintve a gyorsulás S(n) =

f t p + n(1 − f )t p = ... = f (1 − n) + n f t p + (1 − f )t p

Most azt látjuk, hogy a processzorok számának növekedésével arányosan a gyorsulás is növekszik, ami sokkal kedvez˝obb, mint a radikálisan csökken˝o görbe az el˝oz˝o esetben.

10

2. fejezet

Osztott memóriás programozás Az osztott memóriás programozási modell f˝o jellemz˝oje, hogy minden folyamatnak saját változókészlete van, egymás változóit a folyamatok nem érhetik el. Közös változók hiányában viszont nyilván lennie kell valamilyen eszköznek arra, hogy a folyamatok egymással adatokat tudjanak cserélni. Adatátadásra üzenetküldést használhatnak, ezt a mechanizmust vizsgáljuk meg el˝oször közelebbr˝ol.

2.1. Üzenetek kezelése Az általunk vizsgált modellekben az üzenetek kezelése két utasítás beépítésével valósítható meg. A küldés egy send( hova, mit) jellegu˝ utasítással, amelynek két paramétere egyrészt (esetleg közvetetten) a fogadó folyamato(ka)t, másrészt az elküldend˝o adatokat azonosítja. A fogadáshoz egy re eive( honnan, mibe) jellegu˝ utasítás használható, itt az els˝o paraméter a fogadni kívánt üzenet feladóját határozza meg, vagy egyéb módon szukítheti ˝ a szóba jöhet˝o üzenetek körét. A második paraméter egy változó, amelybe eltároljuk a beérkez˝o adatokat. A kommunikációs mechanizmusokat többféle szempont szerint csoportosíthatjuk. Az egyik a címzés módja, vagyis ahogy a kommunikáló folyamatok megtalálják egymást: lehet közvetlen vagy közvetett. Másik szempont lehet az adatátadás lefolyása, különös tekintettel arra, hogy a küld˝o bevárja-e a fogadót, ha el˝obbi hamarabb érkezik a send utasításhoz. A kommunikációs utasítások tárgyalása során érdekes lehet még az adatátviteli hibák kezelése. Érdemes megfigyelni, hogy az üzenetküldés egy tipikus szinkronizációs esemény két folyamat között, a szinkronizáció leírásánál használt „küld˝o” és „fogadó” szavak is ezt az értelmezést hangsúlyozták. A szinkronizációs pontok a send és a re eive utasítások.

2.1.1.

Címzés

Közvetlen címzés esetén szükség van arra, hogy a folyamatok létrehozáskor egyértelmu˝ folyamat azonosítót kapjanak a rendszerben. Üzenet küldésekor és fogadásakor a folyamatazonosítót használjuk a hova és honnan paraméterek helyén. Ehhez természetesen szükség van arra is, hogy egy folyamat ismerje azon folyamatok azonosítóját, amelyekkel kommunikálni akar. Egy tipikus párhuzamos alkalmazásnak van egy kezdeti inicializációs része, amikor a kezdeti folyamatokat létrehozzuk és amelynek direkt címzés esetén része a folyamatazonosítók „terítése” is. Közvetlen címzést használ például a PVM rendszer. Közvetett címzés esetén nincs szükség folyamatazonosítókra, ehelyett a folyamatok mellett megjelenik egy új fels˝o szintu˝ komponens, a csatorna. Ahhoz hogy két folyamat kommunikálni tudjon, szükség van egy csatornára, amelyen keresztül az adatok átkerülnek a küld˝ot˝ol a fogadóhoz. A folyamatoknak 11

egymást nem kell ismerniük, csak a kijelölt csatorna egyik végét „látják”, a csatornát nevezik meg a send és a re eive utasításokban. A közvetett címzés el˝onye, hogy a könnyebb a folyamatokat „fekete dobozként” használni, el˝ore definiált folyamatokat csatornákkal a megfelel˝o módon összekötve építhetünk párhuzamos alkalmazásokat. Ugyanez természetesen elérhet˝o közvetlen címzéssel is, de egyrészt ott ez külön odafigyelést igényel, másrészt a rendszer konfigurálása fordítási id˝o helyett futási id˝oben történik. Csatornákat használ például az O CCAM nyelv.

2.1.2.

Szinkron és aszinkron kommunikáció

A szinkronizáció leírásánál láttuk, hogy a küld˝o folyamat viselkedése konkrét modellt˝ol függ˝oen kétféle lehet. Az egyik esetben bevárja a fogadót, annak megérkezésekor megtörténik az adatátvitel (ha szükséges), majd mindkét folyamat tovább folytatja futását. Ezt a viselkedést szinkron kommmunikációnak, vagy randevúnak is nevezik. A másik lehet˝oség, hogy a küld˝o folyamat nem várja be a fogadót, hanem folytatja futását. Ekkor azonban a rendszerben lehetnek már elküldött, de még nem fogadott üzenetek, így ezek tárolásáról gondoskodni kell. A tárolás módja azonban függ a címzést˝ol. Közvetlen címzés esetén minden folyamathoz egy úgynevezett postafiókot rendelnek, amelyben az üzenetek átmenetileg tárolódnak. Ebben az esetben a re eive utasítás tulajdonképpen a postafiókból olvas be egy üzenetet. Közvetett címzés (csatorna) esetén az úton lév˝o üzeneteket a csatorna tárolja, emiatt ekkor pufferelt csatornáról is szokás beszélni. Az elküldött, de még nem fogadott üzenetek száma elméletileg akár tetsz˝olegesen nagy is lehet, gyakorlatban azonban valamilyen korlátot kell szabnunk. A korlátot elérve a küld˝ot várakozásra kényszeríthetjük, vagy esetleg a fölös üzenetet megsemmisíthetjük. Ez elfogadható lehet ha az alkalmazást amúgyis fel kell készíteni adatátviteli hibákból ered˝o üzenetvesztésre. További el˝onye, hogy ilyenkor nehezebben alakul ki holtpont, mert a küld˝o nem „ragad be”. Leginkább ízlés kérdése, hogy egy programozási modellbe szinkron vagy aszinkron kommunikációt építünk-e be alapmuveletként. ˝ A szinkron kommunikáció egyszerubb ˝ implementációt kíván, de szükségtelen várakozásra kényszerítheti a küld˝ot. Az aszinkron verzió (nagyrészt) kiküszöböli a várakozást, de bonyolultabb definiálni és megvalósítani. Szerencsére a kétfajta módszer egyforma er˝osségu, ˝ mindkét fajta alapmuveletet ˝ felhasználva definiálható a másik. Ha szinkron muveletünk ˝ van, akkor definiálhatunk egy olyan puffer folyamatot, amely üzenetek átmeneti tárolására van „kiképezve”. Ezt két másik folyamat közé helyezve az eredeti folyamatok úgy érzik, mintha aszinkron módon kommunikálnának, mivel a küld˝o üzenetei el˝oször a pufferbe kerülnek függetlenül attól, hogy a fogadó mikor lesz képes azokat beolvasni. Ha aszinkron muveletünk ˝ van, akkor ezek segítségével definiálhatunk új, már szinkron módon muköd˝ ˝ o utasításokat úgy, hogy küldés után várakozunk egy nyugta (acknowledgement) üzenetre, amit az üzenet beolvasása után indítunk vissza a küld˝onek.

2.1.3.

Kommunikáció több folyamattal

Leggyakrabban a kommunikációban két fél vesz részt, küld˝o és fogadó. El˝ofordulnak azonban olyan konstrukciók is, amelyek lehet˝ové teszik, hogy több folyamat legyen érintett. Egyik fajtája a többszerepl˝os kommunikációnak az üzenetszórás (broadcast), amikor ugyanazt az üzenetet több címzettnek küldjük el. Ha nem is feltétlenül ugyanolyan hatékonyan, de ez természetesen egy ciklussal megvalósítható akkor is, ha éppen alapmuveletként ˝ nem áll rendelkezésre. Az osztott memóriás modellekben akár a re eive utasítás speciális paraméterezésével, vagy külön utasítással elérhet˝o, hogy egy folyamat több beérkez˝o üzenetre felkészülve várakozzon. Ebben az állapotban a megengedett üzenetek közül bármelyik beérkezésekor a folyamat arra azonnal reagálni tud. Ez a módszer a „gyors várakozás”, amit azért nevezhetünk így, mert ez a módszer sokkal rugalmasabb (és ezáltal gyorsabb lehet), mintha a potenciálisan beérkez˝o üzenetekre egy önkényes feldolgozási sorrendet írnánk el˝o. 12

2.2.

O CCAM

Az O CCAM nyelvet párhuzamos nyelvnek tervezték, ezért egységes jelölésmóddal és hatékony fordítási ideju˝ ellen˝orzésekkel teszi könnyebbé a programozó munkáját. Szinkron csatornakommunikációt használ. Az O CCAM program elemei: változók, folyamatok, csatornák, id˝ozít˝ok. A hivatalos terminológia szerint utasítások nincsenek, csak folyamatok. Minden folyamatnak van egy életciklusa, definálásakor ezt kell megadni. Az életciklushoz az elidulás, az elvégzett tevékenység és a leállás tartozik. A leállás lehet sikeres vagy sikertelen (ekkor a folyamat megszakad). A sikertelen befejez˝odésre különösen nagy figyelmet kell fordítani, mert ez az oka az osztott renszereket leginkább fenyeget˝o és legnehezebben felderíthet˝o hibának, a holtpontnak. A nyelv tartalmaz egy szekvenciális részhalmazt, amely szintaxisától eltekintve a szokványos imperatív konstrukciókat tartalmazza: • értékadás (v := e) • üres „utasítás” (SKIP) • elemi holtpont (STOP) • szekvencilális kompozíció (SEQ) • szelekció (IF (replikált is), CASE) • ciklus (replikált SEQ, WHILE) Ezeket, valamint néhány további fogalmat ismertnek tételezünk fel: adattípusok, deklaráció, hatáskör, replikáció, eljárások, függvények, rövidítés (abbreviation).

2.2.1.

Csatornák, protokollok

Az O CCAM a kommunikációra indirekt címzést, tehát csatornákat használ. A csatornák tulajdonságai: • szinkron, vagyis a folyamatok bevárják egymást. • pont-pont kapcsolatot tesz lehet˝ové, vagyis mindkét oldalán legfeljebb 1 folyamat helyezkedhet el. • megbízható, vagyis kommunkiciós hiba nem fordulhat el˝o, üzenet nem jön létre, nem vész el és nem változik meg. • egyirányú. • típusos, rajta csak az el˝ore meghatározott típusú adatok küldhet˝ok át. Sok hasonlóság van a változók és a csatornák között, illetve a különbségek is azonos szempontok szerint vizsgálhatók. A változóknak és a csatornáknak is van típusuk (a csatornák típusát protokollnak (protocol) nevezzük), amely meghatározza a tárolható, illetve átvihet˝o adatok értékkészletét. Másik hasonlóság, hogy mindkét esetben két muveletet ˝ végezhetünk: kiolvasást és beírást (csatorna esetén fogadás és küldés, de lényegében ezek ugyanazok a muveletek). ˝ Különbség, hogy változók esetén a muveletet ˝ csak ugyanaz a folyamat hajthatja végre (osztott memória), csatornán értelemszeruen ˝ csak két különböz˝o folyamat. Változó esetén a kiolvasások és beírások száma és sorrendje tetsz˝oleges, csatorna esetén mindig egy beírás és egy küldés történik egyszerre. A kommunikálni szándékozó folyamatokat és a kommunikációhoz szükséges csatornát ugyanazon a szinten kell deklarálni: 13

CHAN INT : PAR

! 5 INT x:

? x

Egyszeru˝ protokoll Csatorna típusának megadása CHAN <protokoll> alakban történik. A legegyszerubb ˝ esetben a <protokoll> megegyezik egy alap adattípussal (egyszeru˝ protokoll), ekkor az az adattípus szerepel a deklarációban, pl. CHAN INT, vagy CHAN [10℄BYTE. Küldéskor és fogadáskor mindig a protokollnak megfelel˝o típusú kifejezéseket, illetve változókat kell megadni. CHAN [3℄BOOL : PAR

! [ FALSE, TRUE, FALSE℄ [3℄BOOL bv:

? bv

Tömbök esetén lehet˝oség van arra, hogy az átküldött adatok mennyiségét ne rögzítsük el˝ore, ekkor küldéskor meg kell adni az elemek számát és magukat az elemeket is. Ezt a fajta protokollt számlálós tömbprotokollnak nevezzük, formája CHAN INT::[℄<elemi-típus> . Fogadáskor két változót adunk meg, egyikbe az elemek száma, másikba a tömbelemek kerülnek. Utóbbi természetesen egy tömbváltozó, amely balról jobbra kerül feltöltésre és elég nagynak kell lennie, hogy elférjenek benne a küldött elemek. CHAN INT::[℄BYTE : PAR VAL outmsg IS hello'':

! ( SIZE outmsg) :: outmsg INT inpsize: [100℄BYTE inpmsg:

? inpsize :: inpmsg

Névvel ellátott protokollok Bonyolultabb esetekben a protokollnak nevet adhatunk és a nevet használhatjuk a deklarációkban. A protokoll deklaráció egyik formája

PROTOCOL <protokoll-név> IS <protokoll-leírás> : Itt a <protokoll-leírás> lehet egy alap adattípus, de lehet adattípusok sorozata is, ekkor szekvenciális protokollról beszélünk. PROTOCOL PAIR IS BYTE; BYTE: CHAN PAIR : PAR

! 'x'; 'y' BYTE a, b:

? a; b

Ha két folyamat különböz˝o id˝opontokban különböz˝o típusú adatokat akar küldeni egymásnak, akkor az eddigiek alapján minden típushoz külön csatornát kell használniuk. A variant protokoll segítségével megoldható, hogy a kommunikáció ilyenkor is egy csatornán történjen. Ennek lényege, hogy 14

a különböz˝o lehet˝oségekhez egy-egy címkét rendelünk, ez a címke futás közben átküldésre kerül és a fogadó ez alapján megfelel˝oen tudja értelmezni a beérkez˝o adatokat. PROTOCOL WORK CASE init; pro ess; quit :

BOOL; BOOL INT::[℄BYTE; [ 2℄REAL64; INT

CHAN WORK w: PAR SEQ w ! init; TRUE; TRUE w ! pro ess; 3::"ab ";[ 1.0 (REAL64), 1.0 (REAL64)℄; 42 w ! quit BOOL going: SEQ going := TRUE WHILE going BOOL i1, i2: INT size, x: [ 2℄REAL64 rve : [ 100℄BYTE bve : w ? CASE init; i1; i2 SKIP pro ess; size::bve ; rve ; x SKIP quit going := FALSE

2.2.2.

Párhuzamos konstrukciók

Az O CCAM párhuzamosságot támogató folyamatai: • üzenet küldése (output) ( !

e)

• üzenet fogadása (input) ( ?

v)

• párhuzamos kompozíció (PAR, replikált is) • többszörös értékadás (v1 , ..., vn := e1 , ..., en ) • várakozás bejöv˝o csatornákon (ALT, replikált is) A kommunikációról volt szó az el˝oz˝oekben, most vegyük sorra a többit. PAR A PAR konstrukció szolgál párhuzamos folyamatok létrehozására. Szintaxisa a kulcsszó kivételével megegyezik a SEQ folyamatéval. PAR P1 P2 ... Pn

15

Ez az összetett folyamat úgy muködik, ˝ hogy a komponens folyamatokat egyszerre elindítja, majd befejez˝odik miután mindegyik komponens sikeresen befejez˝odött. Fontos, hogy N darab aktív folyamatunk van, a „szül˝o” folyamatnak nincs önálló élete a gyerekfolyamatok futása alatt, az legfeljebb csak a leszármazottak összeségeként értelmezhet˝o. A komponensek sikeres befejez˝odésének követelménye azt jelenti, hogy ha valamelyik komponens futása közben holtpontba jut, akkor ezzel megakadályozza az összetett PAR folyamat terminálását is. Ez jól mutatja a holtpontok veszélyességét, azt a tendenciát, hogy felbukkanásuk után egyre nagyobb programrészeket „fert˝oznek meg”, végül lebénítják az egész rendszert. A PAR replikált változata PAR i=ek FOR ev P( i)

formájú, ennek jelentését úgy kapjuk, hogy visszavezetjük a replikáció nélküli változatra. A fenti replikált forma megfelel a PAR P( ek ) P( ek +1) ... P( ek +ev -1)

folyamatnak, ennek megfelel˝oen alakul a muködése. ˝ Egy O CCAM program szintaktikusan egy (összetett) folyamat. Ugyanez a program futását egyetlen folyamatként kezdi, amely azonban több részfolyamatra válik szét, amikor PAR-hoz ér. A részfolyamatok programkódja is tartalmazhat PAR-t, ilyenkor ezek tovább bomlanak részfolyamatokra. Ha a program futása közben egy pillanatfelvételt készítünk, akkor egy fát láthatunk, amelynek csúcsa a kezdeti folyamat, bels˝o csúcsai olyan folyamatok, amelyek PAR végrehajtása közben vannak. Fontos, hogy csak a fa levelei jelölnek aktív folyamatot, a többi csúcs értelmezhet˝o úgy, mint a leszármazottak befejez˝odésére váró szül˝o folyamat. Fa helyett elképzelhetjük a folyamatokat bármilyen hierarchikus módon ábrázolva, például gyakran egymásba ágyazott buborékokként ábrázolják o˝ ket. Ha egy folyamat PAR-hoz ér, akkor a fában egy új szinten megjelennek a leszármazottai. Ha ezek mindegyike sikeresen befejez˝odött, akkor eltunnek ˝ a fából és a szül˝o folyamat újra aktívvá válik. Az O CCAM nyelv eddigi egyetlen osztott memóriás többprocesszoros megvalósítása arra adott lehet˝oséget, hogy a folyamat-hierarchia gyökér alatti szintjét a programozó leképezze a processzorokra. Ezután minden folyamat a szül˝o processzorán futott. Elvileg nincs kizárva, hogy egy gyerek folyamat ne a szül˝o folyamat processzorán fusson, a futás közbeni folyamat-áthelyezést folyamat migrációnak nevezzük. A migráció azonban technikailag nehéz, az esetek túlnyomó többségében sokkal egyszerubb ˝ a folyamatok helyett az adatokat mozgatni.

Közös változók használata A fentiek miatt az O CCAM megengedi, hogy változók több párhuzamos folyamat számára is láthatók legyenek és hozzá is férhessenek, ha ezzel nem szegik meg az osztott memória elvét. A modell megengedi azt, hogy ha egy folyamat több részre válik szét, akkor a részek örököljék az o˝ s memóriájának diszjunkt darabjait, tehát ha egy küls˝obb szinten deklarált változót csak egyetlen folyamat használ, az megengedett. INT x: PAR P1 -- x nem fordul el® ... Pi−1 -- x nem fordul el® x := x + 1

16

Pi+1 -- x nem fordul el® ... Pn -- x nem fordul el®

Tekintsük az alábbi összetett folyamatot: INT x: CHAN INT , d: PAR SEQ

! x d ! x P1 -- sak olvassa x-et INT x: SEQ

? x P2 -- sak olvassa x-et INT x: SEQ d ? x P3 -- sak olvassa x-et

Itt P1 az o˝ st˝ol „örökli” az x változót, amelynek értékét elküldi más folyamatoknak. Egyik folyamat sem változtatja meg a saját lokális változója értékét, mindannyian csak olvassák. Ebben az esetben megengedhet˝o, hogy az összes folyamat ugyanazt a változót használja, hiszen az INT x: PAR P1 -- sak olvassa x-et P2 -- sak olvassa x-et P3 -- sak olvassa x-et

programrészlet hatása minden körülmények között megkülönböztethetetlen az el˝oz˝ot˝ol, különbség csak a jelölésbeli könnyebbségben van, tehát ez is megengedhet˝o. Összegezve azt mondhatjuk, hogy küls˝oleg deklarált változót PAR-ban használni csak két esetben lehet: vagy csak egyetlen komponens használja a változót (akár olvasásra, akár írásra, vagy mindkett˝ore), vagy több folyamat is használja, de akkor mindegyik csak olvashat bel˝ole. Még másként megfogalmazva, ha valamelyik folyamat ír egy küls˝oleg deklarált változóba, akkor a változó csak abban a folyamatban fordulhat el˝o. A tömbök egy változónak számítanak, de a legtöbb esetben elérhet˝o, hogy komponenseiket külön változóként használhassuk. Ha az indexkifejezések értéke fordítási id˝oben megállapítható, akkor semmi egyéb teend˝onk nincs, például: [ 10℄INT v: PAR v[ 0℄ := 0 v[ 1℄ := 1 PAR i=3 FOR 8 v[ i℄ := 2

Változókat tartalmazó kifejezéseket is használhatunk, de akkor el˝oz˝oleg a tömböt fel kell osztanunk diszjunkt részekre az O CCAM rövidítés (abbreviation) konstrukciója segítségével. (A rövidítés is történhet változót tartalmazó kifejezéssel, ilyenkor a fordítóprogram egy kódrészletet generál a programba, amelyik futás közben ellen˝orzi, hogy diszjunktak-e a részek.) 17

[ 10℄INT v: w1 IS [ v FROM 0 FOR 5℄: w2 IS [ v FROM 5 FOR 5℄: CHAN INT , d: PAR INT i: SEQ

? i

? w1[ i℄ INT i: SEQ d ? i w2[ i℄ := 7

Többszörös értékadás A változók használatát rögzít˝o szabályoknak következménye van a többszörös értékadásra nézve, mert definíciójához szükségünk van a PAR-ra. A v1 , ..., vn := e1 , ..., en jelentése ugyanis T1 t1 : T2 t2 : ... Tn tn : SEQ PAR t1 := t2 := ... tn := PAR v1 := v2 := ... vn :=

e1 e2 en t1 t2 tn

Vagyis a többszörös értékadás két lépésben (SEQ) kerül végrehajtásra, mindkét lépésen belül a részlépések egymással párhuzamosan futnak. A ti átmenti változók egymástól és az összes többi változótól különböznek, Ti típusaik megegyeznek a vi változók típusaival. Többszörös értékadást alapul véve ugyanaz a változó párhuzamos folyamatokban az alábbi módokon jelenhet meg: • az els˝o lépésben a jobboldalon (például x, y := a, a), ekkor a változóból csak kiolvasás történik • a második lépésben a baloldalon (például x, x := 3, 5), ekkor a változóba csak beírás történik • a második lépésben a baloldalon (például i, x[i℄ := 7, 8), ekkor a változóból kiolvasás és abba beírás is történik A változók használatának szabályai szerint ezek közül csak az els˝o megengedett, a másik kett˝o nem. ALT Az ALT a legösszetettebb O CCAM folyamat, a korábbiakban említett „gyors várakozás”-t valósítja meg azáltal, hogy több bejöv˝o csatornát figyel és a legels˝o kommunikációs kísérletre reagál. A szintaxisa leginkább az IF-hez hasonlít. 18

ALT g1 g2

P1

P2 ... gn Pn

A replikált változatból ebben az esetben is formai átalakítással kapjuk a neki megfelel˝o normál formátumot. ALT i=ek FOR ev g( i) P( i)

A fenti replikált forma megfelel a ALT g( ek ) P( ek ) g( ek +1) P( ek +1) ... g( ek +ev -1) P( ek +ev -1)

alaknak. Fontos, hogy a replikáció nem az ALT ismétl˝odését jelenti, hanem csatornatömb figyelését teszi lehet˝ové. Ha az ALT-ot többször végre akarjuk hajtani, akkor minden esetben ciklusba kell tenni. A fentiekben gi az úgynevezett „˝or” (guard), ezek határozzák meg, hogy mely csatornákat figyeljük. (Amint azt látni fogjuk, speciális esetben el˝ofordulhat, hogy nincs csatorna megnevezve.) Az o˝ r általános alakja & < satorna> ? , ahol az els˝o rész az ’&’ jellel együtt elhagyható, ˝ ennek a hatása olyan, mintha a logikai kifejezés értéke TRUE lenne. Orként megadható még a TRUE & SKIP kifejezés is. Az ALT elindulásakor el˝oször kiértékeli a logikai kifejezéseket, a továbbiakban csak azokat az o˝ röket veszi figyelembe, amelyeknél TRUE volt az eredmény. A logikai kifejezésekkel tehát el tudjuk érni, hogy ha egy adott ALT folyamat többször lefut, akkor esetenként más legyen az „élesített”, aktív o˝ rök halmaza.Az aktív o˝ rök meghatározása után elkezd várakozni, amit akkor fejez be, ha legalább egy o˝ r engedélyezetté válik. Csatornát megnevez˝o o˝ r akkor kerül engedélyezett állapotba, ha a csatorna túlsó oldalán lév˝o folyamat a csatornán adatot akar küldeni, vagyis egy output (!) „utasítás”-hoz ért. Fontos, hogy ekkor még az adatátvitel nem történhetett meg, a potenciális küld˝o felek még várakoznak, közülük egynek lesz lehet˝osége a kommunikációra. A TRUE & SKIP formájú o˝ r mindig engedélyezett, tehát ha ez jelen van, akkor nincs várakozás. Engedélyezett o˝ r azonban lehet még több ilyenkor is, hiszen elképzelhet˝o, hogy az ALT indulásakor már voltak küldeni szándékozó folyamatok a figyelt csatornákon. Az engedélyezettség következménye az, hogy az adott ág kiválasztható, kijelölt lett az ALT befejez˝o fázisához. A befejez˝o fázisban az engedélyezett o˝ rök közül nemdeterminisztikus módon kiválasztásra kerül egy, csatornás o˝ r esetén megtörténik az adatátvitel, majd az o˝ rhöz tartozó folyamatot végrehajtva az ALT is befejez˝odik. A nemdeterminisztikusság azt jelenti, hogy a nyelv tervez˝oi szándékosan nem definiálták a kiválasztási kritériumokat. Elképzelhet˝o olyan implementáció is, amely azonos körülmények között kétszer különböz˝oképpen dönt, a programozónak erre tekintettel kell megírnia a programját. Az ALT holtpontba kerülhet, ha üres o˝ rhalmazt sikerül megadnunk, ha a figyelt csatornák túloldalán lév˝o folyamatok mind holtpontba kerültek, ha a kiválasztott csatornán protokollhiba történik, vagy ha a kiválasztott o˝ rhöz tartozó folyamat maga holtponba kerül. 19

Multiplexer Az ALT legtipikusabb alkalmazása az úgynevezett multiplexer folyamat megvalósítása. Ennek az a feladata, hogy több bemen˝o csatorna forgalmát egy kimen˝o csatornára irányítsa. Sokszor együtt alkalmazzák az úgynevezett demultiplexer folyamattal, ami egy bemen˝o csatornán érkez˝o adatokat oszt szét több kimen˝o csatornán. A két folyamat együttes alkalmazásával elérhet˝o, hogy egy fizikai csatornát több logikai csatornaként használjunk, ezt a technikát nevezik multiplexálásnak. PROTOCOL DATA IS : PROTOCOL MPLEX IS INT; : PROC multiplex( CHAN PROC mplex() WHILE TRUE ALT i= 0 FOR ( d: logi al.inp[ physi al ! : -- mplex

MPLEX physi al, [℄CHAN DATA logi al.inp, logi al.out) SIZE logi al.inp) i℄ ? d i; d

PROC demplex() WHILE TRUE INT i: d: SEQ physi al ? i; d logi al.out[ i℄ ! d : -- demplex PAR mplex() demplex() : -- multiplex

2.2.3.

Csovezetékek ˝

A funkcionális dekompozíció tipikus példája az úgynevezett cs˝ovezeték. Ennél egy láncban helyezzük el a folyamatokat, melyek egy feldolgozás munkafázisait végzik el a rajtuk áthaladó adatokon. Egyid˝oben több adatelem van feldolgozás alatt, mindegyik másik minkafázisban. Egy adatelemnek a teljes feldolgozáshoz végig kell járnia sorrendben az összes munkafázist. Sebességnövekedést úgy érünk el, ha sok feldolgozandó adatelemünk van, ezek összesített feldolgozási ideje lényegesen lecsökkenhet cs˝ovezeték alkalmazásával. Ideális esetben n fázis esetén n-szeres gyorsulásra számíthatunk akkor, ha a fázisok id˝oigénye megközelít˝oleg azonos, hiszen a leglassabb fázis határozza meg az adatok áramlási sebességét. Rendezés Az egyik legegyszerubb ˝ alkalmazása a cs˝ovezetékes rendezés, a cs˝ovezeték hossza ebben az esetben megegyezik a rendezend˝o elemek számával (N). Minden fázis ugyanazt a munkafolyamatot hajtja végre, a rajta áthaladó sorozat elemeinek sorrendjét megváltoztatja úgy, hogy a nagyobb elemek a sorozat vége felé helyezkedjenek el. PROC sortelement( CHAN INT inp, out) INT max, x: SEQ inp ? max SEQ i= 1 FOR N-1

20

SEQ inp ? x x, max := max2( x, max) out ! x out ! max : -- sortelement

A sortelement folyamat N számot olvas be az input csatornáján és ugyanannyit küld tovább a kimen˝o csatornáján. A már látott számok közül a legnagyobbat a max változóban tárolja. Minden újabb beérkez˝o számot összehasonlít az addigi legnagyobbal, a nagyobbikat tárolja, a kisebbiket továbbküldi. Miután az összes számot látta, a még a max-ban lév˝o legnagyobbat is elküldi. A felhasznált max2 segédfüggvény két egész számot fogad és nagyság szerinti sorrendben adja vissza o˝ ket, ennek definíciója INT, INT FUNCTION max2( VAL INT a, b) INT x, y: VALOF IF a > b x, y := b, a TRUE x, y := a, b RESULT x, y : -- max2

A rendez˝o eljárás N példányban párhuzamosan futtatja a fenti folyamatot és gondoskodik az összeköttetésekr˝ol. PROC pipesort( CHAN INT inp, out) [ N-1℄CHAN INT : PAR sortelement( inp, [ 0℄) PAR i= 1 FOR N-2 sortelement( [ i-1℄, [ i℄) sortelement( [ N-2℄, out) : -- pipesort

A fenti definíciókat felhasználva összeállíthatunk egy programot, amelyben a bemen˝o adatok kiosztása és az eredmény begyujtése ˝ is szerepel. PROC sorter( ...) VAL [℄INT v IS [ 3, 7, 2, 5, 8, 0, 9, 4, 1, 6℄: VAL N IS SIZE v: [ N℄INT w: PROC pipesort( CHAN INT inp, out) PROC sortelement( CHAN INT inp, out) INT, INT FUNCTION max2( VAL INT a, b) ... : -- max2 ... : -- sortelement ... : -- pipesort CHAN INT feed, extra t: PAR pipesort( feed, extra t) SEQ SEQ i= 0 FOR N feed ! v[ i℄

21

SEQ i= 0 FOR N extra t ? w[ i℄ : -- sorter

Struktúraütközés Tekintsük azt a feladatot, amelyben az input karaktereket tartalmazó inpSize hosszúságú rekordokból (az utolsó rekord lehet rövidebb) álló sorozat. A programnak meg kell vizsgálnia minden karaktert és el kell végeznie bizonyos transzformációkat. A transzformációk között lehet olyan is, amely a karakter törlését, vagy (több) másik karakterrel való helyettesítését írja el˝o. Például transzformációs szabály lehet, hogy töröljünk minden ’#’ és ’*’ jelet, cseréljünk minden nagybetut ˝ kisbeture ˝ és helyettesítsünk minden számjegyet a ’#’ jelek közé helyezett bináris megfelel˝ojével (pl. 5 helyett 101). Mindezek mellett az outputot outSize hosszúságú rekordokba rendezve kell kiírni. A feladat szekvenciális nyelven természetesen megoldható, de a program szerkezete nem tudja tükrözni az adatok szerkezetét, mert az inputot és az ouputot kezel˝o ciklusok nem ágyazhatók egymásba. O CCAM-ban folyamatokat és csatornákat felhasználva sokkal átláthatóbb, tisztább megoldáshoz juthatunk. A megoldás egy háromelemu˝ cs˝ovezetéket használ, amelynek tagjai a Reader, Transform és Writer folyamatok. Mindhárom folyamat ugyanazt a sémát alkalmazza a termináció biztosítására, a WHILE ciklus tesztje egy logikai változóból áll, amelyet a ciklusba való els˝o belépéskor TRUE-ra állítunk, majd a ciklustörzs végén az új helyzetnek megfelel˝oen beállítunk. BOOL going: SEQ going := TRUE WHILE going SEQ ... going := ...

A Reader feladata az input rekordok beolvasása és a karakterek egyenkénti eljuttatása a következ˝o fázishoz. PROC Reader( CHAN INP.RECORD inp, CHAN BYTE out) [ inpSize℄BYTE iv: INT inpCnt: BOOL going: SEQ going := TRUE WHILE going SEQ inp ? inpCnt; iv SEQ i= 0 FOR inpCnt out ! iv[ i℄ going := inpCnt = inpSize : -- Reader

A Transform az egyenként érkez˝o karakterek transzformációjáért felel˝os, egy bemen˝o karakterre a transzformációs szabályoknak megfelel˝oen nulla, egy, vagy több karaktert bocsáthat ki a következ˝o fázis felé. Ezt az xform() eljárás végzi, ami az alábbi példában csak továbbküldi a karaktert változtatás nélkül. Biztosítani kell, hogy az EOF karaktert is továbbítsa a legvégén. PROC Transform( CHAN BYTE inp, out) BYTE b:

22

PROC xform() out ! b : -- xform BOOL going: SEQ going := TRUE WHILE going SEQ inp ? b xform() going := b <> EOF : -- Transform

A Writer (és azon belül a olle t) folyamat feladata az egyenként beérkez˝o karakterekb˝ol kimen˝o rekordok összeállítása majd azok továbbküldése. PROC Writer( CHAN BYTE inp, CHAN OUT.RECORD out) PROC olle t( CHAN BYTE inp, [℄BYTE v, INT nt) BOOL going: SEQ going, nt := TRUE, 0 WHILE going SEQ inp ? v[ nt℄

nt, going := nt+1, ( v[ nt℄ <> EOF) AND ( nt+1 < ( SIZE v)) : -- olle t [ outSize℄BYTE ov: INT outCnt: BOOL going: SEQ going:= TRUE WHILE going SEQ

olle t( inp, ov, outCnt) out ! outCnt; ov going := outCnt = outSize : -- Writer

A fenti folyamatokat cs˝ovezetékbe rendezve kapjuk a feladatot megoldó programot. VAL INT inpSize IS 10: VAL INT outSize IS 7: PROTOCOL INP.RECORD IS INT; [ inpSize℄BYTE: PROTOCOL OUT.RECORD IS INT; [ outSize℄BYTE: PROC str oll( CHAN INP.RECORD inpre , CHAN OUT.RECORD outre ) PROC Reader( CHAN INP.RECORD inp, CHAN BYTE out) ... PROC Transform( CHAN BYTE inp, out) ... PROC Writer( CHAN BYTE inp, CHAN OUT.RECORD out) ... CHAN BYTE R2T, T2W: PAR Reader( inpre , R2T) Transform( R2T, T2W) Writer( T2W, outre ) : -- str oll

23

Aszinkron kommunikáció Ahogy korábban szóltunk róla, akár a szinkron, akár az aszinkron kommunikáció szerepel alapmuvelet˝ ként egy programozási modellben (nyelvben), lehet˝oség van a másik definiálására. Ennek megfelel˝oen O CCAM-ban is használhatunk aszinkron kommunikációt, ha arra van szükség. Erre azáltal nyílik lehet˝oség, hogy az aszinkron csatorna pufferel˝o képességét egy folyamattal valósítjuk meg és ezt a folyamatot az aszinkron módon kommunikálni szándékozó folyamatok közé helyezzük. A továbbiakban feltételezzük, hogy az P és Q folyamatok egész számokat akarnak küldeni egymásnak aszinkron csatornán. Egy üzenet tárolására képes aszinkron csatornához jutunk, ha köztes folyamatként az alábbit használjuk: PROC asyn ( CHAN INT inp, out) WHILE TRUE INT x: SEQ inp ? x out ! x : -- asyn

Ha ezt a folyamatot a P és Q közé helyezzük, akkor a P egy üzenetet el tud küldeni akkor is, ha a Q még éppen nem fogadóképes. Ezt a sémát egy cs˝ovezetékkel általánosíthatjuk. Ha többet sorban összekapcsolunk a fenti folyamatból, akkor tetsz˝oleges véges kapacitású aszinkron csatornát hozhatunk létre. PROC asyn N( CHAN INT inp, out) [ N-1℄CHAN INT : PAR asyn ( inp, [ 0℄) PAR i= 1 FOR N-2 asyn ( [ i-1℄, [ i℄) asyn ( [ N-2℄, out) : -- asyn N

2.2.4.

További példák

Hatékonyabb aszinkron kommunikáció A cs˝ovezetékkel megvalósított aszinkron kommunikáció helyesen muködik, ˝ de nem a leghatékonyabb megoldás még akkor sem, ha a folyamatindítás O CCAM-ban nem költséges muvelet. ˝ Felvet˝odik a kérdés, hogy nem lehetne-e az úton lév˝o üzeneteket egy tömbben tárolva kevesebb folymattal megoldani a feladatot. Természetesen meg lehet, két folyamat elég a megvalósításhoz. (A pufferbe való beírások és az abból történ˝o kiolvasások tetsz˝oleges sorrendben követhetik egymást, ezt egyetlen szekvenciális folyamattal nem lehet megoldani, mert ott el˝ore el kellene dönteni a sorrendet.) A két folyamat egyike (store) a pufferelést és ezzel a munka nagy részét oldja meg, a másik (prompter) szerepe az, hogy az adatok fogadása és továbbítása egymástól függetlenül történhessen, a környezet által megkívánt módon. A megoldás lényege, hogy a legrégebb óta várakozó üzenetet a prompter tárolja, készen arra, hogy továbbítsa az aszinkron csatornán fogadni kész folyamatnak. A két folyamat között mindkét irányban van kapcsolat, az adatáramlással megegyez˝o irányban egy adatcsatorna, visszafelé egy kérés-csatorna köti össze o˝ ket. A kérések adattartalma közömbös, csak a szinkronizáció miatt van szükség rájuk. Valamilyen protokollt azonban ekkor is meg kell adnunk, ilyenkor választhatjuk például a BOOL típust. Tehát mindkét folyamatnak van egy bejöv˝o és egy kimen˝o adatcsatornája, ezen kívül a prompter-nek van egy kimen˝o, a store-nak pedig egy bejöv˝o kérés-csatornája. A prompter folyamat az egyszerubb, ˝ három lépést ismétel egymás után: • jelez a store-nak, hogy kész fogadni a legrégebb óta várakozó üzenetet. 24

• beolvassa a kérés hatására érkez˝o üzenetet (várakozik, amíg megérkezik) • továbbítja a nála lév˝o üzenetet (várakozik, amíg át nem veszik t˝ole) PROC prompter( CHAN INT inp, out, CHAN BOOL req) WHILE TRUE INT v: SEQ req ! TRUE inp ? v out ! v : -- prompter

A prompter fenti kialakításával lehet˝oség nyílik arra, hogy a store egy olyan folyamat legyen, amely folyamatosan figyeli a bejöv˝o csatornáit és reagál a beérkez˝o üzenetekre. Ha adat (aszinkron üzenet) érkezik, akkor azt eltárolja a pufferben; ha kérés érkezik, akkor egy üzenetet továbbít a prompter felé. Az üzeneteket egy FIFO tárban tároljuk, ehhez szükségesek a buffer, ptr és ount változók. PROC store( CHAN INT inp, out, CHAN BOOL req) [ N℄INT buffer: INT ptr, ount: SEQ ptr, ount := 0, 0 WHILE TRUE BOOL r: INT v: ALT 0 < ount & req ? r SEQ v, ptr, ount := buffer[ ptr℄, ptr+1, ount-1 out ! v N > ount & inp ? v SEQ buffer[ ( ptr+ ount) REM N℄ := v

ount := ount+1 : -- store

Fontosak az ALT o˝ rökben alkalmazott logikai feltételek. A 0 < ount miatt nem fogadunk kérést akkor, ha nincs továbbítandó tárolt üzenet, hiszen ekkor nem tudnánk mit küldeni válaszul. Ha üres a puffer, akkor csak bejöv˝o üzenetet fogadunk el. Az N > ount a másik határesetet kezeli le, azt eredményezi, hogy tele puffer esetén újabb üzenetet fogadni nem, csak tároltat továbbítani lehet. Mindkét ˝ biztosított. feltétel nem lehet egyszerre hamis (nyilván N > 0), ezért a rendszer folyamatos muködése Érdemes még megfigyelni az ALT két ágában szerepl˝o értékadásokat. A korábban megismert szabályok miatt az els˝o ágban mindhárom elhelyezhet˝o egy többszörös értékadásban, míg a másodikban csak egyenként végezhet˝ok el a megadott sorrendben. A két részfolyamat összekapcsolása a megszokott módon történik. Mivel a prompter is tárol egy üzenetet, az összkapacitás eggyel nagyobb, mint a store-ban lév˝o tömb mérete. PROC xasyn ( CHAN INT inp, out) PROC prompter( CHAN INT inp, out, CHAN BOOL req) ... PROC store( CHAN INT inp, out, CHAN BOOL req) ... CHAN INT data: CHAN BOOL req: PAR prompter( data, out, req) store( inp, data, req) : -- xasyn

25

2.3.

PVM

2.3.1.

Áttekintés

A PVM (Parallel Virtual Machine) rendszert tanulságos összehasonlítani az O CCAM-mal, az osztott memóriás programozáson belül szinte minden szempontból vizsgálva más megközelítéssel találkozhatunk. Legel˝oször is a PVM nem egy önálló nyelv, hanem egy (kett˝o: C vagy F ORTRAN) alapnyelvre épített eljáráskönyvtár. Ennek következménye, hogy a fordítóprogramtól semmilyen segítséget nem várhatunk a párhuzamos programozási hibák kiküszöböléséhez, hiszen a párhuzamos konstrukciók is csak függvényhívások, azok szemantikájáról a fordítóprogramnak nincsen tudomása. A folyamatok a PVM terminológiában a taszk elnevezést kapták. Az elindított taszkok a szül˝o folyamattól és egymástól függetlenül, aszinkron módon futnak, de a rendszer nyilvántartja a szül˝o-gyerek kapcsolatokat. Együtt indított taszkok befejez˝odésekor nincs az O CCAM-hoz hasonló implicit szinkronizáció. Minden taszk egy egyedi taszkazonosítót (taszk ID, TID) kap, ami a rendszer által generált egész szám. Az üzenetküldés közvetlen, nincsenek csatornák, a küld˝o és a fogadó utasítások a taszkazonosítót használják címzésre. A kommunikáció aszinkron módon zajlik, tehát a küld˝o nem várja be a fogadót, hanem az üzenet feladása után folytatja a futását. Az üzenetek puffereléséhez minden taszkhoz tartozik egy „levelesláda” (mailbox ), ahol a beérkezett, de még fel nem dolgozott üzenetek tárolódnak. A PVM az adatátvitel hibamentességét nem garantálja, az ilyen jellegu˝ hibák felderítése és kezelése az alkalmazások feladata. Az üzenetekkel kapcsolatban viszont biztosított, hogy sorrendjük meg˝orz˝odik. Vagyis ha az A taszk egymás után két üzenetet küld a B taszknak, akkor a korábban elküldött üzenet fog el˝oször megérkezni a B taszkhoz és ilyen sorrendben tárolódnak el a mailboxban. A legtöbb alkalmazás ezt a garanciát ki is használja, enélkül nem muködnének ˝ helyesen. Lényegében az aszinkron kommunikációnak csak így van értelme, különben szinte mindig nyugták küldésére, vagyis szinkron kommunikáció használatára lennénk kényszerítve.

2.3.2.

Megvalósítás, használat

A PVM-et heterogén számítógépes környezetre tervezték, segítségével például egy lokális PC hálózatot használhatunk párhuzamos (virtuális) számítógépként. A virtuális gépet alkotó gépeket hosztoknak nevezzük. A heterogenitás azt jelenti, hogy a gépeknek nem kell azonos architektúrájúaknak lenniük és nem kell ugyanazt az operációs rendszert használniuk. A hardver és szoftver közötti különbségek elfedésér˝ol a PVM gondoskodik. Egy számítógép azáltal kerül be a PVM rendszerbe, hogy rajta elindítjuk a pvmd démont. Az adott gépen futó taszkok a lokális démonnal tartják a kapcsolatot, a démonok pedig egymással kommunikálva hozzák létre a virtuális gépet. A rendszer kipróbálásához egy gép is elég, s˝ot teszteléshez leginkább ez ajánlott. A továbbiakban L INUX/C környezetet feltételezünk. A PVM démon elindítása a pvm paranccsal történik, pontosabban ez egy konzol alkalmazást indít, amelynek számos olyan szolgáltatása van, amellyel a virtuális gép állapotát meg tudjuk változtatni illetve le tudjuk kérdezni. A konzolba való els˝o belépéskor elindul a démon, ezután a konzolt tetszés szerint bármikor leállíthatjuk/elindíthatjuk. A konzol parancsai között van olyan is, amely leállítja a démonokat, vagyis a virtuális gépet. (a help paranccsal segítséget kérhetünk)

2.3.3.

Programszerkezet

C nyelven úgy írhatunk PVM programokat, hogy minden taszk(fajtá)hoz egy külön futtatható állományt készítünk. A programok elejére el kell helyeznünk az #in lude pvm3.h direktívát, hogy a PVM függvényeket hívhassuk. A végrehajtható program létrehozásakor meg kell adni a PVM könyvtárt, hogy a hivatkozásokat a linker fel tudja oldani. Vagyis egy tipikus parancssor így néz ki (jelenleg a PVM 3. verziója a legújabb): 26



-o prog prog. -lpvm3

A taszkok szokványos L INUX folyamatként kezdik futásukat, majd belépnek a PVM rendszerbe, feladatukat elvégezve pedig kilépnek onnan. A PVM-b˝ol való kilépés nem jelenti a(z immár) folyamatok futásának végét, a befejez˝odés az operációs rendszernek megfelel˝o módon történik. Egy tipikus PVM program vázlata az alábbi: #in lude <stdlib.h> #in lude "pvm3.h" main() { int mytid; mytid= pvm_mytid(); ... // egyéb PVM hívások ... pvm_exit(); exit( EXIT_SUCCESS); }

Látható, hogy a PVM függvények mind pvm_xxx alakúak, melyek definíciói a fordításkor -lpvm3 kapcsolóval megadott könyvtárban vannak, ezekbe van elrejtve a lokális démonnal való kommunkáció.

2.3.4.

Taszkkezelés

A fenti programrészlet tartalmaz két taszkkezeléssel kapcsolatos függvényt, az alábbi táblázatban egy b˝ovebb listát láthatunk: • int pvm_mytid( void) Rendszerbe való belépés illetve saját taszk azonosító lekérdezése. A visszatérési érték a hívó taszk azonosítója. • int pvm_parent( void) Szül˝o taszk azonosítójának lekérdezése. A visszatérési érték a hívó taszk szül˝ojének azonosítója. • int pvm_exit( void) Kilépés a PVM rendszerb˝ol. A nem 0 visszatérési érték hibát jelez. • int pvm_kill( int tid) A megadott azonosítójú taszk (er˝oszakos) leállítása és megszüntetése. Saját magát nem szüntetheti meg ezzel a hívással egyetlen taszk sem. A nem 0 visszatérési érték hibát jelez. • int pvm_spawn( har* task, har** argv, int flag, har* where, int ntask, int* tids) Taszk(ok) indítása. A hívó taszk az újonnan indítottak szül˝oje lesz. A paraméterek jelentése:

har* task Az inditando taszk(ok) végrehajtható programjának elérési útja a filerendszerben.

har** argv Átadott parancssori argumentumok. int flag Különböz˝o opciókat határoz meg, többek között meghatározza a következ˝o where paraméter értelmezését. PvmTaskDefault esetén a rendszer maga választja ki az indítandó taszkok helyét.

har* where Ha flag értéke PvmTaskHost vagy PvmTaskAr h, akkor itt adhatjuk meg azt a hosztgépet, illetve architektúra típust amelyen a taszkok indulnak. 27

int ntask Ez a paraméter határozza meg, hogy hány példány induljon a taszkból. A függvény visszatérési értéke adja meg, hogy hány példány indult el valójában.

int* tids Ez egy ntask méretu˝ tömb els˝o elemére mutató pointer. Ide kerülnek az elindított taszkok azonosítói, hogy kés˝obb tudjunk rájuk hivatkozni.

2.3.5.

Kommunikáció

A PVM direkt címzést és aszinkron adatátvitelt alkalmaz. Minden taszkhoz tartozik három további objektum, amelyek a kommunikáció során jutnak szerephez. Ezek egyike a levelesláda (mailbox), amiben a beérkezett üzenetek feldolgozásig várakoznak. Ezen kívül a kommunikációhoz minden taszknak szüksége van pufferekre, amelyekbe küldés el˝ott elhelyezzük, illetve fogadáskor beolvassuk az adatokat. Két puffert (egy küld˝o- és egy fogadópuffert) készen kapunk a taszk indulásakor, de szükség esetén továbbiakat is létrehozhatunk a megfelel˝o PVM függvények segítségével. Akárhány pufferünk is van, azok közül mindig ki van jelölve egy aktív küld˝o puffer és egy aktív fogadó puffer. Küldéskor és fogadáskor ezeket már nem kell megnevezni, de a rendszer értelemszeruen ˝ ezeket használja, Az üzeneteket küldéskor el kell látni egy úgynevezett címkével (message tag, msgtag ), ami tulajdonképpen egy egész szám. A címke lehet˝oséget ad az alkalmazásnak, hogy az üzeneteket csoportokba sorolja. Fogadásakor a címzett válogathat a beérkezett üzenetek közül címke szerint (is), ami bizonyos esetekben hasznos lehet. Ennek segítségével például megoldhatjuk, hogy bizonyos üzeneteknek nagyobb priorotása legyen, vagy egyszeruen ˝ csak elkülöníthetjük egymástól a különböz˝o feldolgozási fázisokat. Üzenetküldés PVM-ben az üzenetküldés három lépésb˝ol áll, ezek: puffer inicializálás, becsomagolás, tényleges küldés. Az ide tartozó legfontosabb függvények: • int pvm_initsend( int en oding) El˝okészíti az aktív puffert az üzenet összeállítására (becsomagolására). Visszatérési értéke a puffer azonosítója. Az en oding paraméter lehetséges értékei:

PvmDataDefault Az adatokat ellátja típus információval. Ezáltal lehetséges heterogén hálózatok-

ban a különböz˝o architektúrájú gépek közötti kommunikáció, mert szükség esetén automatikus adatkonverzióra van lehet˝oség a fogadó oldalon.

PvmDataRaw Az adatok továbbításakor nincs konverzió, csak akkor használható, ha a fogadó hoszt architektúrája megegyezik a küld˝oével.

PvmDataInPla e Kombinálható az el˝oz˝o kett˝o valamelyikével. Becsomagoláskor csak pointerek

kerülnek tárolásra, az adatokat a tényleges küldéskor olvassa ki a rendszer. A kevesebb másolás miatt ez a módszer gyorsabb lehet, azonban figyeljünk arra, hogy az alkalmazás igényeit˝ol függ˝oen a pointerek által hivatkozott memóriaterületet nem írhatjuk felül a küldésig.

• int pvm_pk*( ...) Egy függvénycsalád szolgál a különböz˝o alaptípusok becsomagolására. Negatív visszatérési érték hibát jelez. • int pvm_send( int tid, int msgtag) Az aktív küldési pufferben található el˝okészített üzenetet a megadott címkével ellátva elküldi. Negatív visszatérési érték hibát jelez. 28

A fogadóra nem vár, azonnal visszatér, amint a lokális démon átvette az üzenetet. Utóbbi miatt szokás ezt az utasítást „blokkoló aszinkron küldésnek” (blo king asyn hronous send ) nevezni. Habár technikailag ez helyes, mégsem szerencsés, mert összemossa a logikai és az implementációs szinteket. Elvi szempontból a küldés aszinkron, hiszen ilyenkor csak a küld˝o és a fogadó taszk szerepe fontos. A küld˝o taszk és a démon kapcsolata egy implementációs részletkérdés, ami természetesen fontos lehet, de nem befolyásolja a programozási modellt, amiben dolgozunk. • int pvm_m ast( int* tids, int ntask, int msgtag) A tids tömbben megadott azonosítójú összes taszknak elküldi az üzenetet. Ezt a módszert üzenetszórásnak (multi ast ) nevezzük. Természetesen ugyanezt elérhetnénk úgy is, hogy egy ciklusban minden címzettnek egyenként elküldjük az üzenetet, de külön függvényként bizonyos architektúrákon hatékonyabban implementálható. Üzenetfogadás Az üzenetfogadás els˝o lépésben tulajdonképpen azt jelenti, hogy a levelesládából egy már beérkezett és ott eltárolt üzenetet kiveszünk feldolgozásra. A levelesláda az üzeneteket beérkezési sorrendben tárolja, de amint látni fogjuk nem csak abban a sorrendben dolgozhatjuk fel o˝ ket. • int pvm_re v( int tid, int msgtag) Ennek a függvénynek a meghívása azt eredményezi, hogy a taszk addig várakozik, amíg egy a feltételeknek megfelel˝o üzenet nem érkezik. A feltételeket a két paraméter jelöli ki, a tid a ˝ alkalmas. Mindkét esetben a nemnegatív küld˝o taszkok, a msgtag pedig a címkék közötti szurésre paraméter egy konkrét értéket jelöl ki, a -1 érték pedig azt jelenti, hogy az adott szempont szerint nem kívánunk válogatni. Mindig a legrégebben beérkezett, a feltételeknek eleget tev˝o üzenetet kapjuk meg az aktív fogadó pufferbe. Két nemnegatív érték esetén tehát egy konkrét taszk megadott címkéju˝ üzenetére vagyunk kíváncsiak. Ha legalább az egyik paraméter értéke -1, akkor az O CCAM ALT konstrukciójához hasonló muveletet ˝ végzünk, vagyis több lehetséges forrásból és/vagy több lehetséges típusú üzenet fogadására vagyunk felkészülve. A lehetséges várakozás miatt ezt a függvényt blokkoló fogadásnak (blocking receive) is nevezik. Visszatérési értéke az üzenetpuffer azonosítója. • int pvm_nre v( int tid, int msgtag) Muködése ˝ az el˝oz˝ohöz hasonló, azzal a különbséggel, hogy nem blokkol (non-blocking receive). Ha a mailboxban nincs megfelel˝o üzenet, akkor 0 értékkel azonnal visszatér. • int pvm_probe( int tid, int msgtag) Ez a függvény hasonlít az el˝oz˝ohöz, azzal a különbséggel, hogy ha talál is üzenetet, azt nem olvassa be. Így tehát csak arról kapunk információt, hogy van-e a levelesládában olyan üzenet, amely megfelel a feltételeknek. • int pvm_tre v( int tid, int msgtag, stru t timeval* timeout) Ugyanaz, mint a pvm_re v, de legfeljebb csak a harmadik paraméter által meghatározott ideig várakozik. A visszatérési értékb˝ol lehet megtudni, hogy üzenet érkezett, vagy at id˝okeret járt-e le. Ha 0 várakozási id˝ot adunk meg, akkor a pvm_nre v viselkedését kapjuk vissza, ha nagyon nagy értéket, akkor pedig lényegében a blokkoló fogadást valósítja meg. Ennek a függvénynek a segítségével készíthetünk hibatur˝ ˝ o alkalmazásokat, amennyiben az id˝okeret lejártával feltételezzük, hogy valamilyen hiba következett be és megfelel˝o intézkedéseket tehetünk az elhárítására. 29

• int pvm_bufinfo( int bufid, int* bytes, int* msgtag, int* tid) A fenti függvények hívása után nem mindig egyértelmu, ˝ hogy a megtalált üzenet melyik taszktól érkezett, illetve mi a címkéje. A hiányzó információ meghatározásában segít ez a függvény, illetve megtudhatjuk az üzenet teljes méretét bájtokban mérve. A megadott pointerek által meghatározott változókba helyezi el az adatokat, kivéve ha NULL-t adunk meg. Ez a függvény pvm_probe után is használható. • int pvm_upk*( ...) A kicsomagoló függvények a megfelel˝o pvm_pk* függvények párjai. Az adatokat a becsomagolás sorrendjében és a típusnak megfelel˝o kicsomagoló függvénnyel kell kicsomagolni.

2.3.6.

Szinkron kommunikáció

O CCAM-ban a kommunikációs primitívek szinkron üzenetküldést tettek lehet˝ové, de mint láttuk a korlátos aszinkron üzenetküldést is meg lehetett valósítani. PVM-ben a beépített kommunikációs utasítások aszinkron üzenetküldést tesznek lehet˝ové, de meg tudunk valósítani szinkron üzenetküldést is. Ennek technikája meglehet˝osen egyszeru, ˝ azon alapszik, hogy a fogadó visszaküld egy nyugtát, amit a küld˝o megvár. Így biztosítható, hogy a küld˝o az üzenet elküldését követ˝o utasításra csak azután térjen rá, miután a fogadó beolvasta az üzenetet. Az alábbi kódrészlet két függvénye úgy lett megtervezve, hogy a pvm_send és a pvm_re v helyett (párban) használva szinkron kommunikáció jöjjön létre a taszkok között. A SYNC_ACK egy olyan konstans, amelyet a nyugták azonosítására használunk, értéke különbözik a programban használt összes többi üzenetcímke értékét˝ol. A syn _send egyszerubb, ˝ mindössze a küldés és a nyugtafogadás szerepel benne. A syn _re v egy ˝ kicsit összetettebb, mert fel kell készíteni arra az esetre, amikor hívásakor a tid paraméter -1 értéku. Ekkor ugyanis szükség van a pvm_bufinfo hívásra, hogy a küld˝o taszkot azonosítani tudjuk. Figyeljük meg, hogy függvényeink a nyugta számára ugyanazokat az üzenetpuffereket használják, mint a „normál” üzenetek számára. Ez kényelmetlen, ha például a syn _send hívásakor egy félig feldolgozott üzenet van az aktív fogadó pufferben. Megoldható lenne, hogy saját puffert hozzunk létre a nyugtaüzenetnek mind a fogadó, mind a küld˝o taszkban, ezáltal a nyugtázás teljesen transzparens lenne az alkalmazás számára. #in lude "pvm3.h" #in lude <stdlib.h> #define SYNC_ACK

172

int syn _send( int tid, int msgtag) { int info= pvm_send( tid, msgtag); pvm_re v( tid, SYNC_ACK); }

return info;

int syn _re v( int tid, int msgtag) { int bufid= pvm_re v( tid, msgtag); if ( -1 == tid) pvm_bufinfo( bufid, NULL, NULL, &tid); pvm_initsend( PvmDataDefault); pvm_send( tid, SYNC_ACK); }

return bufid;

30

2.3.7.

Csovezetékes ˝ rendezés

Az egyik legegyszerubb ˝ párhuzamos folyamatszerkezet a cs˝ovezeték, amelynek alkalmazására O C CAM-ban már láttunk példát. A cs˝ ovezetékes rendezés PVM-ben is hasonlóan egyszeruen ˝ megvalósítható, az algoritmusban természetesen nincs különbség. A program két fajta taszkból áll, a pipemain. a szül˝o-vezérl˝o taszkot, míg a pipe omp. a cs˝ovezetéket felépít˝o elemek programkódját tartalmazza. Taszk szerkezet kialakítása Két figyelemre érdemes különbség azonban van a két megoldás között, mindkett˝o a használt rendszerek tulajdonságaiból adódik. Az els˝o különbség az, hogy míg O CCAM-ban a folyamatszerkezet a programban le van írva és a fordítóprogram ellen˝orzi, addig PVM-ben erre nincs lehet˝oség. Bármelyik taszk bármely másiknak küldhetne üzenetet (ha ismeri a tasz azonosítóját), a leggyakoribb azonban az, hogy minden taszk csak néhány „szomszédjával” tart kapcsolatot. Ezért a PVM programok elején szokás egy inicializációs rész elhelyezése, melynek során a taszkokat értesítjük arról, hogy kikkel fognak kommunikálni a kés˝obbiekben. A cs˝ovezetékes rendezés esetében ez az inicializáció azt jelenti, hogy minden taszkhoz el kell juttatni a cs˝ovezetékben rákövetkez˝o tag azonosítóját. A megel˝oz˝o tag azonosítójára nincs feltétlenül szükség, hiszen tudunk üzenetet fogadni ismeretlen küld˝ot˝ol is. Nem tartozik szorosan a szerkezethez, de a rendezend˝o sorozat hosszára minden taszknak szüksége van, ezért azt is el kell küldeni. pipemain. inicializáció: tids= ( int*) mallo ( N * sizeof ( int)); pvm_spawn( "pipe omp", NULL, PvmTaskDefault, "", N, tids); for ( i= 0; send_int( send_int( send_int( }

i < N; ++i) { tids[ i℄, INIT, 0 == i ? pvm_mytid() : tids[ i-1℄); tids[ i℄, INIT, N-1 == i ? pvm_mytid() : tids[ i+1℄); tids[ i℄, INIT, N);

pipe omp. inicializáció: prev= re v_int( -1, INIT); su

= re v_int( -1, INIT); N= re v_int( -1, INIT);

Feldolgozás A tulajdonképpeni rendezés algoritmusa ugyanaz, mint az O CCAM verzió esetén. A vezérl˝o taszk el˝oször elküldi a rendezend˝o sorozatot a cs˝ovezeték els˝o elemének, majd elkezdi fogadni a rendezett sorozatot a cs˝ovezeték utolsó elemét˝ol. A rendez˝o elemek, illetve a f˝o taszk együttmuködésében ˝ azonban elrejtve ott van a másik lényeges különbség az O CCAM verzióhoz képest, ez pedig az aszinkron kommunikáció. Itt a cs˝ovezeték fázisai mind saját ütemükben haladhatnak, nincsenek arra kényszerítve, hogy összehangoltan haladjanak el˝ore. Ebben az esetben a program helyes muködése ˝ azon múlik, hogy a PVM garantálja, hogy az elküldött üzenetek sorrendje nem változik meg. pipemain. feldolgozó rész: for ( i= 1; i <= N; ++i) send_int( tids[ 0℄, DATA, atoi( argv[ i℄)); for ( i= 1; i <= N; ++i) printf( "%d ", re v_int( tids[ N-1℄, DATA)); puts( "");

31

pipe omp. feldolgozás: max= re v_int( prev, DATA); for ( i= 1; i < N; ++i) { x= re v_int( prev, DATA); sort( &x, &max); send_int( su

, DATA, x); } send_int( su

, DATA, max);

2.3.8.

Processzor farm

2.4. MPI 2.5. Grid

32

3. fejezet

Közös memóriás programozás A közös memóriás programozási modell f˝o jellemz˝oje, hogy a folyamatok közösen használnak változókat. Nincs kizárva, hogy egyes folyamatoknak privát változóik legyenek, de a folyamatok közötti együttmuködés ˝ csak közös változókon keresztül valósulhat meg. A közös változók (er˝oforrások) kezelése során leginkább a kölcsönös kizárás megvalósítására kell odafigyelni.

3.1. Szemafor 3.1.1.

Szemafor definíciója

A szemafor (semaphore ) egy olyan objektum, amelynek segítségével megvalósítható a kölcsönös kizárás. Két privát adattagot tartalmaz, az egyik egy egész számot tárol, melyet a szemafor értékének nevezünk. A másik egy várakozósor, amely a folyamatok késleltetésekor kap szerepet. A szemafor létrehozásakor megadhatjuk a kezd˝oértékét (a várakozósor kezdetben mindig üres). Ha a tárolt érték csak 0 vagy 1 lehet, akkor a szemafort nevezhetjük bináris szemafornak (binary semaphore ). A nem bináris szemafort pedig szokás számláló szemafornak ( ounting semaphore ) is nevezni. Az inicializáláson túl a szemafornak két muvelete ˝ van, wait és signal. A szemafor osztály deklarációja C++ jellegu˝ szintaxissal így nézhetne ki:

lass Semaphore { int _value; Pro essQueue _queue; publi : Semaphore( int v) { _value= v; }; void wait() { if ( 0 == _value) _queue.add(); else --_value; }; void signal() { if ( NOT _queue.empty()) _queue.release(); else ++_value;

33

};

};

A Pro essQueue osztály add metódusa a végrehajtó folyamatot a várakozósorba helyezi. A release metódus egy folyamatot levesz a várakozósorról így az újra futtatható állapotba kerül. Mindkett˝o rendszerhívás, vagyis nem az aktuális folyamatok hajtják végre ezeket, hanem az operációs rendszer (futtató környezet). ˝ egy-egy Ha egy szemafort tekintünk, akkor azt vehetjük észre, hogy a wait és a signal muvelet kritikus szakasz a szemafor bels˝o változóira nézve. Mivel a muveleteket ˝ különböz˝o folyamatok el˝ore nem látható id˝opontokban hívhatják, a helyes muködéshez ˝ szükséges, hogy a kölcsönös kizárást a szemaformuveletekre ˝ nézve is biztosítsuk, vagy másként kifejezve a szemaformuveleteknek ˝ atominak kell lenniük. Egyel˝ore tegyük fel, hogy teljesíthet˝ok ezek a feltételek, és lássuk, hogyan kezelhet˝o a folyamatinterakció szemaforral. Kölcsönös kizárás szemaforral Ha van egy er˝oforrásunk és tetsz˝oleges számú folyamatunk, amelyek erre az er˝oforrásra nézve kritikus szekciókat tartalmaznak, akkor a kölcsönös kizárás megvalósításához az alábbi teend˝oket kell elvégeznünk. • Az er˝oforráshoz hozzárendelünk egy s bináris szemafort, melynek kezd˝oértékét 1-re állítjuk. • Minden folyamat minden kritikus szakaszát „zárójelbe tesszük”, vagyis – közvetlenül elé s.wait() muveletet ˝ helyezünk el. – közvetlenül utána s.signal() muveletet ˝ helyezünk el. A szemafor a létrehozásakor szabad, az els˝o kritikus szakaszba belépni kívánó folyamat tilosra állítja. Ha közben újabb folyamatok érkeznek, akkor azok a várakozósorba kerülnek. Ha kilépéskor van várakozó, akkor a kilép˝o és egy várakozó helyet cserél, közben a szemafor értéke mindvégig 0 marad. Ha kilépéskor nincs várakozó, akkor a szemafor szabadra állítódik. Szinkronizáció szemaforral A szemafort szinkronizációra is fel lehet használni. Ha van két folyamatunk, amelyekben ki van jelölve egy-egy szinkronizációs pont, akkor • A szinkronizációs eseményhez hozzárendelünk egy s szemafort, melynek kezd˝oértékét 0-ra állítjuk. • A küld˝o folyamatban a szinkronizációs pontban elhelyezünk egy s.signal() hívást. • A fogadó folyamatban a szinkronizációs pontban elhelyezünk egy s.wait() utasítást. A muködés ˝ nagyon egyszeru, ˝ ha a küld˝o érkezik el˝oször a szinkronizációs pontba, akkor szabadra állítja a szemafort, majd haladhat tovább. Ha a fogadó érkezik el˝oször a szinkronizációs pontba, akkor a szemafor várakozósorára kerül, ahonnan a másik folyamat fogja elengedni. 34

3.1.2.

Szemafor implementációja

A szemaformuveletek ˝ atomiságára vonatkozó követelmény egy kicsit furcsának tunhet, ˝ hiszen a szemafort eredetileg azért vezettük be, hogy a kölcsönös kizárást megvalósíthassuk. A látszólagos ellentmondást úgy tudjuk feloldani, hogy a szemaformuveleteknél ˝ a kölcsönös kizáráshoz nem beágyazott ˝ használjuk. szemafort, hanem a lo k és unlo k muveleteket Egy lo k/unlo k pár ugyanazt a funkciót tölti be, mint egy szemafor, vagyis kölcsönös kizárást lehet velük megvalósítani, de a folyamatok nem várakozósoron, hanem aktív várakozással egy rövid ciklusban pörögnek, amíg tovább nem haladhatnak. Ez csak akkor engedhet˝o meg, ha el˝ore tudjuk, hogy a várakozási id˝o nagyon rövid lesz. Esetünkben ez így is van, hiszen a wait és signal törzse csak néhány utasítást tartalmaz. A lo k és unlo k egy változón (memóriarekeszen) keresztül muködnek ˝ együtt. A 0 érték tiltja, az 1 engedélyezi a belépést a kritikus szakaszba. A lo k addig várakozik egy ciklusban, amíg a változóban ˝ 1-re állítja a változót. az 0 értéket látja, majd beállítja az 0-ra és visszatér. Az unlo k egyszeruen void lo k( int& lo kvar) { // hibás !!! while ( 0 == lo kvar) ; lo kvar= 0; } void unlo k( int& lo kvar) { lo kvar= 1; }

Figyelmes olvasóink észrevehetik, hogy a közösen használt változóra nézve a lo k és az unlo k muveletek ˝ kritikus szekciók. Kölcsönös kizárásra volna szükség, mert anélkül el˝ofordulhat, hogy két folyamat is 1 értéket olvas a while ciklus feltétel részében, még miel˝ott a másik 0-ra állíthatná a változót. Ezen a ponton a szoftver eszközökb˝ol kifogytunk, hardver támogatásra van szükség, mégpedig egy olyan utasításra, amely megszakíthatatlanul kiolvassa egy memóriarekesz tartalmát, majd beír oda egy másik értéket. Ilyen utasítások léteznek a modern processzorokon, az irodalomban test_and_set utasításnak nevezik ezeket. Ezt felhasználva a lo k helyes definíciója: void lo k( int& lo kvar) { while ( 0 == test_and_set( lo kvar, 0)) ; }

Itt tehát az történik, hogy kiolvassuk a változó értékét és egyben azonnal beállítjuk 0-ára. Ha 0 volt el˝oz˝oleg is, akkor valaki más zárolva tartja, tehát tovább kell folytatni a várakozást. Ha 1 volt, akkor szabaddá vált, de mi azonnal lezártuk, még miel˝ott bárki más szabadnak láthatta voltna. A Semaphore osztály pedig ezek alapján egy kicsit részletesebben így nézhet ki:

lass Semaphore { int _value; Pro essQueue _queue; int

_lo kvar;

publi : Semaphore( int v) { _value= v; _lo kvar= 1; }; void wait() { lo k( _lo kvar);

35

};

};

if ( 0 == _value) _queue.add_and_unlo k( _lo kvar); else { --_value; unlo k( _lo kvar); }

void signal() { lo k( _lo kvar); if ( NOT _queue.empty()) _queue.release_and_unlo k( _lo kvar); else { ++_value; unlo k( _lo kvar); } };

Kis komplikáció, hogy a várakozósorral végzett muveletek ˝ után azonnal a zárat is fel kell oldanunk, ezért szerepel add helyett add_and_unlo k, illetve release helyett release_and_unlo k. Utóbbi nem lenne feltétlenül szükséges, mert a release nem blokkol, de így egységesebb a sorkezelés.

3.2. Monitor A monitor egy másik, folyamatinterakciók szabályozására szolgáló eszköz. A monitort is tekinthetjük egy objektumnak, amelynek minden adattagja privát, vannak publikus metódusai és inicializáló eljárása (konstruktora). A monitort úgy kell elképzelni, mintha egy er˝oforrást zártunk volna a belsejébe (privát adattagok), az er˝oforrásra vonatkozó kritikus szekciókat pedig a publikus eljárások törzsében helyeztük volna el. Ekkor a fordítóprogramnak lehet˝osége van arra, hogy a monitoreljárások elején és végén olyan utasításokat helyezzen el, amelyek az er˝oforrás zárolását/feloldását automatikusan elvégzik. A zárolás történhet szemaforral, vagy más mechanizmus segítségével is.

3.2.1.

Termelo-fogyasztó ˝ probléma (Produ er- onsumer)

Ebben a szituációban két fajta folyamatunk van, termel˝o és fogyasztó. Mindekett˝ob˝ol tetsz˝oleges számú lehet, a termel˝ok folyamatosan el˝oállítanak valamilyen „termék”-eket (adatokat), amiket a fogyasztók feldolgoznak. A termékek az el˝oállítás és a feldolgozás közötti id˝oben egy pufferben tárolódnak. A pufferhez minden folyamatnak hozzá kell férnie muködése ˝ közben, ezért a hozzáférést szabályozni kell a helyes muködés ˝ érdekében. Egyrészt a kölcsönös kizárást kell biztosítani, másrészt azt, hogy üres pufferb˝ol ne próbáljanak kivenni a fogyasztók, illetve tele pufferbe ne próbáljanak új elemet betenni a termel˝ok. A rendszer komponenseinek szerkezete Java-szeru˝ jelöléssel az alábbi lehet monitor Queue { private ITEM[℄ private int

_queue; _front= 0, _used= 0;

publi Queue( int apa ity) { _queue= new ITEM[ apa ity℄; } private boolean empty() { return 0 == _used; } private boolean full() {

36

}

return _queue.length == _used;

private int offset( int val, int off) { return ( val+off) % _queue.length; } publi ITEM extra t() { ITEM x= _queue[ _front℄; _front= offset( _front, 1); --_used; }

}

return x;

publi void deposit( ITEM x) { _queue[ offset( _front, _used)℄= x; ++_used; }

publi void Produ er( Queue queue) { while ( going) { ITEM x= produ e(); queue.deposit( x); } } publi void Consumer( Queue queue) { while ( going) { ITEM x= queue.extra t();

onsume( x); } }

A kölcsönös kizárásról a monitor gondoskodik, de nem akadályozza meg, hogy üres pufferb˝ol kiséreljünk meg kivenni, vagy tele pufferbe betenni adatot. Ennek megakadályozására a folyamatoknak szinkronizálniuk kell, a monitoron belül ennek megvalósítása pedig úgynevezett feltételváltozó ( ondition variable ) segítségével történik. A feltételváltozó lényegében egy várakozási sor, amelyen a folyamatok egy bizonyos esemény bekövetkezésére, vagy másképpen fogalmazva egy bizonyos feltétel teljesülésére várakoznak. A feltételváltozóhoz két muvelet ˝ tartozik:

wait A hívó folyamat a várakozási sorra kerül. A monitor zárolását feloldja, így egy másik folyamatnak lehet˝osége van belépni.

signal Egy várakozó folyamat felélesztése, ha a sor nem üres. Ha üres, akkor hatástalan. A signal hívása esetén konfliktushelyzet áll el˝o, mert a hívó és az éppen felélesztett folyamat is igényt tart a monitorra, de nyilván csak egyikük tarthatja azt zárolva. Különböz˝o stratégiák lehetségesek: signal & wait El˝oször a felélesztett folyamat kapja meg a monitort, majd a signal-t hívó. Ez a monitor eredeti definíciója szerinti viselkedés. signal & continue A signal folytathatja futását, a felélesztett folyamat bekerül a monitorba belépni szándékozók sorába. signal & exit A signal csak a monitoreljárás utolsó utasítása lehet. Ezzel el lehet kerülni a konfliktust. 37

Termelo-fogyasztó ˝ probléma megoldása monitorral A szinkronizáláshoz felveszünk két feltételváltozót (_nonempty, _nonfull). Itt várakoznak a folyamatok, amíg a megfelel˝o feltétel nem teljesül. monitor Queue { private ITEM[℄ private int private Condition

_queue; _front= 0, _used= 0; _nonempty, _nonfull;

publi Queue( int apa ity) ... private boolean empty() ... private boolean full() ... private int offset( int val, int off) ... publi ITEM extra t() { if ( empty()) _nonempty. wait(); // ha üres, akkor várakozás ITEM x= _queue[ _front℄; _front= offset( _front, 1); --_used;

}

_nonfull. signal(); // biztosan nin s tele, hiszen most távolítottunk el egy elemet return x;

publi void deposit( ITEM x) { if ( full()) _nonfull. wait(); // ha tele van, akkor várakozás _queue[ offset( _front, _used)℄= x; ++_used;

}

3.3.

}

_nonempty. signal(); // biztosan nem üres, hiszem most helyeztünk el egy elemet

J AVA

A J AVA támogatja a párhuzamos programozást, mégpedig a monitor-koncepcióhoz hasonló formában.

3.3.1.

Párhuzamosság J AVA-ban

Szálak J AVA-ban egy szekvenciális végrehajtási egységet szálnak (thread ) nevezünk. Minden szál egyben egy objektum is, amely a Thread osztályból származó osztály egy példánya. A Thread osztály tartalmazza tehát azokat az adattagokat és metódusokat, amelyek a szálak kezeléséhez szükségesek. Ide kapcsolódik még a Runnable interfész, amely egyedül a run metódust definiálja. Minden szálnak implementálnia kell ezt a metódust, amely a szál által végrehajtandó programot tartalmazza. publi interfa e Runnable { void run(); }

A Thread osztály legfontosabb metódusai: 38

lass Thread implements Runnable { publi Thread( String name); publi Thread( Runnable target, String name);

}

publi

String getName();

// név lekérdezése

publi publi

int void

getPriority(); setPriority(int newPriority);

// prioritás lekérdezése // prioritás beállítása

publi

void

run();

// üres a törzse

publi publi publi

void void void

start(); join(); interrupt();

// a szál indítása // sak a run() befejez®dése után tér vissza // szál megszakítása

publi stati Thread urrentThread(); publi stati void sleep(long millis); publi stati void yield();

// aktuális szálat reprezentáló objektum // várakozás megadott ideig // lemondás a pro esszorról

A kétféle konstruktor kétfajta létrehozási módszert támogat. Lehet˝oségünk van közvetlenül a Thread osztályból származtatni, vagy saját osztályunk implementálhatja a Runnable interfészt. A szálat reprezentáló Thread objektumot minden helyzetben elérhetjük a urrentThread metódus segítségével. Mindkét módszer esetében egy szöveges azonosítót rendelhetünk a szálhoz, amelyet kés˝obb a getName metódussal kérdezhetünk le. Ennek nem kell egyedinek lennie, a rendszer nem ez alapján azonosítja a szálakat.

lass ExThread extends Thread { // Egyik módszer ExThread( String name) { super( name); }

}

publi void run() { ... }

lass ImThread implements Runnable { // Másik módszer

}

publi void run() { ... }

Az els˝o esetben az osztály közvetlenül példányosítható, a másodikban az osztály egy példányát átadva a Thread konstruktorának megintcsak egy önálló szálat reprezentáló objektumot kaphatunk. ExThread t1= new ExThread( "ExThread"); Thread t2= new Thread( new ImThread(), "ImThread");

A szál a létrehozása után még nem fut, el˝oször el kell indítani. Erre a start metódust használjuk, amelynek visszatérése után az indított és az indító szál egymástól függetlenül futnak. Egy szál mindig több, el˝ore definiált állapot egyikében lehet csak, ezek az állapotok a Thread osztályban vannak definiálva. NEW Létrehozás után, elindítás el˝ott. RUNNABLE A szál a J AVA virtuális gépben végrehajtás alatt van, a run metódusa még nem ért véget. Ez nem zárja ki, hogy processzorra várakozzon. 39

BLOCKED Zárolt monitor miatti várakozás. WAITING Másik szálra várakozás meghatározatlan ideig. TIMED_WAITING Másik szálra várakozás el˝ore meghatározott ideig (id˝ozített). TERMINATED A run metódus véget ért. A start hatására tehát az indított szál run metódusa kezd végrehajtódni. Nem biztos, hogy a gyerek szál el˝obb be fog fejez˝odni, mint a szül˝o. Ha meg akarjuk várni egy másik szál befejez˝odését, akkor a join metódusát kell meghívnunk. Vannak olyan metódusok, amelyek várakozást idézhetnek el˝o, pl. join, sleep. Ha várakozás közben egy szálat megszakítanak (interrupt), akkor a várakozás „nem rendesen” fejez˝odik be, hanem egy InterruptedEx eption kivétel jön létre. A várakozással járó metódusokat csak úgy hívhatjuk meg, hogy az esetleges kivétel kezelésér˝ol is gondoskodunk. publi lass ThreadDemo { publi stati void main(String[℄ args) { ExThread t1= new ExThread( "ExThread"); Thread t2= new Thread( new ImThread(), "ImThread"); t1.start(); t2.start(); ...

}

}

try { t1.join(); t2.join(); }

at h ( InterruptedEx eption e) { ... } ...

A sleep metódus a megadott ezredmásodpercig inaktívvá teszi a hívó szálat, az csak az id˝o lejárta után válik újra futtathatóvá. Minden szálhoz tartozik egy prioritási érték, amely befolyásolja, hogy melyik szál futhat, ha több futtatható szál van, mint rendelkezésre álló processzor. A prioritás MIN_PRIORITY és MAX_PRIORITY közötti egész szám lehet, NORM_PRIORITY az alapértelmezés szerinti érték. Az újonnan létrehozott szálak öröklik a szül˝o prioritását, míg a beállítást és a lekérdezést a setPriority és a getPriority metódusokkal végezhetjük. A J AVA virtuális gép mindig a futtatható legnagyobb prioritású szálak közül választ ütemezésnél, alacsonyabb prioritásúakra csak akkor kerülhet sor, ha a magasabb prioritásúak befejez˝odtek, vagy id˝olegesen várakozniuk kell. A yield metódus hívásával a szál lemondhat a processzorról és átadhatja azt egy másiknak. Szálinterakció (J AVA 1.4 verzióig) Mivel a monitor egy osztály jellegu˝ konstrukció, a J AVA tervez˝oi azt a megoldást választották, hogy bármelyik J AVA osztály monitorrá tehet˝o, illetve felruházható monitor jellegu˝ tulajdonságokkal. Vegyük sorra a monitor tulajdonságait, illetve azt, hogy egy adott jellemz˝o hogyan valósítható meg J AVA-ban. 40

Monitor privát adatok inicializáló eljárás monitor eljárások zár a monitoreljárásokhoz feltételváltozók

wait muvelet ˝

signal muvelet ˝

J AVA privát tagváltozók/konstansok konstruktor syn hronized blokk, syn hronized metódus (implicit) zár az Obje t osztályban egyetlen implicit feltételváltozó az Obje t osztályban Obje t osztály wait metódusa Obje t osztály notify, notifyAll metódusai

Az Obje t osztályban van egy zár, amelyet a syn hronized metódusok/blokkok automatikusan kezelnek, így kerül megvalósításra a kölcsönös kizárás. Fontos, hogy a syn hronized blokkok csak egymás között valósítják meg a kölcsönös kizárást. A wait metódus várakozásra kényszerítheti a hívó szálat, a várakozás pedig bizonyos körülmények között „eredménytelenül” fejez˝odhet be. Ez a gyakorlatban azt jelenti, hogy normál visszatérés helyett egy InterruptedEx eption kivétel keletkezik, ezért a wait hívását try blokkban kell elhelyezni. Az elnevezések szerencsétlenül keverednek mostantól, mert a J AVA arra használja a „szinkronizált” kulcsszót, amit mi eddig (és mindenki más a J AVA megjelenéséig) kölcsönös kizárásnak nevezett. Szinkronizációnak viszont azt neveztük, amikor egy folyamat bevár egy másikat. Továbbra is az eddigi értelemben használjuk a kölcsönös kizárás és a szinkronizáció kifejezéseket, és jegyezzük meg, hogy J AVA-ban a syn hronized kulcsszót kell (lehet) használni kölcsönös kizáráshoz. A syn hronized blokk szintaxisa: syn hronized ( objref ) { ... }

Ennek hatása, hogy az objref által azonosított objektumot zárolja a blokk végrehajtása alatt. Ez azt jelenti, hogy ha ezid˝o alatt egy másik szál próbálja zárolni ugyanazt az objektumot, akkor annak várakoznia kell, amíg a blokk végrehajtása befejez˝odik. Megcimkézhetünk egy metódust is a syn hronized kulcsszóval, ennek az a hatása, mintha a metódus törzsét helyeztük volna syn hronized blokkba az alábbi módon. publi void syn hronized f() { ... }

publi void f() { syn hronized ( this) { ... } }

A J AVA megoldása egy ponton korlátozottabb, mint az eredeti monitor koncepció, mivel csak egyetlen feltételváltozó használatára van lehet˝oség. Ezt szintén az Obje t osztály tartalmazza, és implicit módon a wait, notify és notifyAll metódusok hivatkoznak rá. J AVA-ban a notify és notifyAll a „signal & continue” stratégia szerint muködik, ˝ ezt figyelembe kell venni a monitoreljárások megírásakor. Az eredeti, „signal & wait” szerinti muködés ˝ lehet˝ové teszi, hogy a várakozást a if ( ond )

wait( ond_var );

programrészlettel valósítsuk meg. Ez azért lehetséges, mert amikor a jelz˝o folyamat a signal()-t hívja, akkor utána rögtön a felélesztett folyamat folytatja futását a wait() után. Ha azonban „signal & continue” van érvényben, akkor a felélesztett folyamat egyszeruen ˝ beáll a monitort zárolni szándékozó folyamatok közé. Ha egy másik várakozó folyamat kapja meg el˝obb a monitort, akkor érvénytelenítheti 41

a feltételt, ezért a wait() visszatérése után azt újra meg kell vizsgálni, és szükség esetén újra várakozni. Vagyis az if helyett while-ra van szükség. A termel˝o-fogyasztó probléma megoldásához használt tároló J AVA-ban az alábbiak szerint alakul:

lass Queue { private ITEM[℄ private int

_queue; _front= 0, _used= 0;

publi Queue( int apa ity) ... private boolean empty() ... private boolean full() ... private int offset( int val, int off) ... publi syn hronized ITEM extra t() { while ( empty()) try { wait(); // ha üres, akkor várakozás } at h ( InterruptedEx eption e) { ... } ITEM x= _queue[ _front℄; _front= offset( _front, 1); --_used;

}

notifyAll(); // mindenkit feléleszt, mert a termel®k és a fogyasztók együtt várakoznak return x;

publi syn hronized void deposit( ITEM x) { while ( full()) try { wait(); // ha tele van, akkor várakozás } at h ( InterruptedEx eption e) { ... } _queue[ offset( _front, _used)℄= x; ++_used;

}

}

notifyAll(); // mindenkit feléleszt, mert a termel®k és a fogyasztók együtt várakoznak

Figyeljük meg, hogy mind a termel˝ok, mind a fogyasztók ugyanazt az egyetlen feltételváltozót kénytelenek használni, ezért mindkét metódusban a notifyAll() hívásnak kell szerepelnie. Ez nem különösebben hatékony, hiszen a felélesztett folyamatok közül jó eséllyel egy kivételével mind visszakerül a várakozási sorra, de nincs jobb megoldás, mert az Obje t osztály csak egyetlen feltételváltozót tartalmaz. Szerencsére a J AVA 1.5-ös verziójának megjelenésével a helyzet sokat javult, mert bevezettek számos új osztályt a párhuzamos programozás támogatására. Egyebek mellett több feltételváltozó használatára is lehet˝oség van. J AVA 1.5 verzió bovítései ˝ Legfontosabb b˝ovítés a Lo k és a Condition interface, amelyek lehet˝ové teszik egynél több feltételváltozó használatát. A Lo k interface legfontosabb elemei: publi interfa e Lo k { void lo k(); void unlo k(); Condition newCondition(); ... }

42

A ReentrantLo k osztály implementálja a Lo k interfészt, ennek példányai segítségével ugyanazt a hatást tudjuk elérni, mint az Obje t osztály beépített zárjával. A feltételváltozóknak a kölcsönös kizárást megvalósító zárhoz kell kapcsolódniuk, mivel a feltételváltozó muveletek ˝ befolyásolják a zárolást is. Az Obje t osztály zárjához nem tudunk további feltételváltozókat rendelni, csak a Lo k interfészt megvalósító zárhoz, mégpedig a newCondition metódus segítségével. A Condition interface legfontosabb elemei: publi interfa e Condition { void await() // monitorban wait, Obje t-ben wait throws InterruptedEx eption; void signal(); // monitorban signal, Obje t-ben notify void signalAll(); // Obje t-ben notifyAll }

Egy több feltételváltozót használó J AVA osztály vázlata az alábbiak szerint alakulhat:

lass X { private final ReentrantLo k _lo k= new ReentrantLo k(); private final Condition _ ond1= _lo k.newCondition(); private final Condition _ ond2= _lo k.newCondition(); // ...

}

publi void m() { // NEM syn hronized _lo k.lo k(); try { // ... metódus törzse _ ond1.await(); // feltétel változó m¶veletek sak zárolt állapotban érvényesek // ... _ ond2.signal(); // ... } finally { // biztosan feloldjuk a zárolást _lo k.unlo k() } }

Az await által esetleg kiváltott InterruptedEx eption kezelésér˝ol gondoskodni kell. Az új osztályokkal most már megvalósíthatjuk a termel˝o-fogyasztó puffert ésszerubben. ˝

lass Queue { private ITEM[℄ private int

_queue; _front= 0, _used= 0;

private final ReentrantLo k _lo k= new ReentrantLo k(); private final Condition _nonempty= _lo k.newCondition(); private final Condition _nonfull= _lo k.newCondition(); publi Queue( int apa ity) ... private boolean empty() ... private boolean full() ... private int offset( int val, int off) ... publi ITEM extra t() { _lo k.lo k(); try { while ( empty()) _nonempty.await(); ITEM x= _queue[ _front℄; _front= offset( _front, 1);

43

--_used; _nonfull.signal();

}

}

}

at h ( InterruptedEx eption e) { // await miatt } finally { _lo k.unlo k(); } return x;

publi void deposit( ITEM x) { _lo k.lo k(); try { while ( full()) _nonfull.await(); _queue[ offset( _front, _used)℄= x; ++_used; _nonempty.signal(); }

at h ( InterruptedEx eption e) { // await miatt } finally { _lo k.unlo k(); } }

További új osztályok is bekerültek a J AVA 1.5 verzióba, ezekr˝ol kés˝obb lesz szó.

3.3.2.

Olvasók-írók probléma (Readers-Writers)

Az olvasók-írók „probléma” a kölcsönös kizárás általánosításának tekinthet˝o. Vannak folyamatok, amelyek egy közös er˝oforrást kezelnek, a kezel˝o kódrészletek a kritikus szakaszok. Megfigyelhetjük, hogy egyes kritikus szakaszok csak olvassák az er˝oforrást, míg mások megváltoztatják annak állapotát. Hatékonyabban muköd˝ ˝ o programot kaphatunk, ha az olvasásokat engedjük egyszerre végrehajtódni, hiszen ezzel nem veszélyeztetjük az er˝oforrás konzisztenciáját. Tehát a folyamatokat két csoportba osztjuk aszerint, hogy kritikus szakaszuk tartalmaz-e írási muve˝ letet, vagy nem. A kölcsönös kizárásnál szemafort használtunk, illetve ezzel összefüggésben a kritikus szakasz használatára egy belépési- és egy kilépési protokolt vezettünk be. Ez a megoldási séma most is megmarad, csak most két belépési- és két kilépési protokolt kell definiálnunk (külön az olvasóknak és az íróknak). Lesz tehát egy REntry, egy RExit, egy WEntry és egy WExit eljárásunk, amelyeket a megfelel˝o pontokon meg kell hívnunk. A folyamatok együttmuködésének ˝ biztosításához ezúttal (J AVA) monitort fogunk használni.

lass ReadersWriters { private final Lo k _lo k= new ReentrantLo k(); private final Condition _readable= _lo k.newCondition(); private final Condition _writable= _lo k.newCondition(); private int _numReaders= 0; private boolean _isWriting= false; publi void REntry() { _lo k.lo k(); try {

44

while ( _isWriting) _readable.await(); ++_numReaders;

}

at h ( InterruptedEx eption e) { } finally { _lo k.unlo k(); }

}

} publi void RExit() { _lo k.lo k(); try { if ( 0 == --_numReaders) _writable.signal(); } finally { _lo k.unlo k(); } } publi void WEntry() { _lo k.lo k(); try { while ( 0 < _numReaders || _isWriting) _writable.await(); _isWriting= true; }

at h ( InterruptedEx eption e) { } finally { _lo k.unlo k(); } } publi void WExit() { _lo k.lo k(); try { _isWriting= false; _readable.signalAll(); _writable.signal(); } finally { _lo k.unlo k(); } }

A probléma megoldásakor különböz˝o stratégiák közül választhatunk, részben aszerint, hogy el˝onyben részesítjük-e valamelyik folyamatcsoportot a másikkal szemben. Létezik az olvasókat el˝onyben részesít˝o (reader-preferen e ) és az írókat el˝onyben részesít˝o (writer-preferen e ) stratégia. Mindkett˝onek van el˝onye és hátránya is. Az olvasó-preferencia azt jelenti, hogy ha olvasó van kritikus szakaszban, akkor az újonnan érkez˝o olvasók „bemehetnek” mellé, még akkor is, ha van várakozó író. El˝onye, hogy így maximalizálhatjuk a párhuzamosságot. Az író-preferencia azt jelenti, hogy az olvasók nem mehetnek be a kritikus szakaszba, ha van várakozó író, valamint írót választunk következ˝o folyamatnak, amikor csak lehet. Emellett az szól, hogy az írási muveletek ˝ frissítik az adatokat, és valószínuleg ˝ az alkalmazás szempontjából jobb, ha ez minél el˝obb megtörténik, nem elavult adatokkal dolgozik. Mindkét módszer hátránya, hogy éhezéshez vezethet, az el˝onyben részesített folyamatok bármeddig késleltethetik a másik csoport tagjait. Az éhezést például (más módszer is lehetséges) ki lehet küszöbölni azzal, ha nem engedjük a folyamatok el˝ozését, érkezési sorrendben engedjük o˝ ket a kritikus 45

szakaszukba. A fenti J AVA program olvasó-preferenciát valósít meg. Író befejez˝odése után az összes várakozó olvasót és egy írót is feléleszt, mert nem tudhatjuk, hogy nem üres-e valamelyik sor. Ha mindkét soron van várakozó folyamat, akkor a signal-ok sorrendje ellenére el˝ofordulhat az is, hogy író lesz a következ˝o, aki bejut a kritikus szakaszba, de ez nem sérti az olvasó-preferencia követelményét. A J AVA 1.5-ös verziója tartalmaz beépített támogatást az olvasók-írók probléma megoldására. Ennek egyik része a ReadWriteLo k interface, amelynek két metódusa az olvasók, illetve az írók zárjához való hozzáférést teszi lehet˝ové. publi interfa e ReadWriteLo k { Lo k readLo k(); Lo k writeLo k(); }

A rendszer természetesen tartalmaz egy implementáló osztályt is, ez a ReentrantReadWriteLo k. Ezt használva a fenti ReadersWriters osztály jelent˝osen leegyszerusíthet˝ ˝ o (akár ki is küszöbölhet˝o).

lass ReadersWriters { private final ReadWriteLo k

}

_rwlo k= new ReentrantReadWriteLo k();

publi void REntry() { _rwlo k.readLo k().lo k(); } publi void RExit() { _rwlo k.readLo k().unlo k(); } publi void WEntry() { _rwlo k.writeLo k().lo k(); } publi void WExit() { _rwlo k.writeLo k().unlo k(); }

A ReadWriteLo k interface és a ReentrantReadWriteLo k osztály részletei a J AVA dokumentációban megtalálhatók.

3.3.3.

Étkezo˝ filozófusok (Dining

philosophers)

Öt filozófus (folyamat) két tevékenységet végez váltakozva: gondolkodnak és esznek. A két tevékenység közötti alapvet˝o különbség az, hogy a gondolkodást önállóan végzik (nincs szükségük küls˝o segítségre), míg az evéshez különböz˝o segédeszközöket vesznek igénybe. Egy asztal közepén egy tálban spagetti van, az asztal körül öt szék, az asztalon a székek között öt villa. Minden filozófusnak rögzített helye van, csak a saját székére ülhet le. Ahhoz, hogy enni tudjon, fel kell vennie a székér˝ol elérhet˝o mindkét villát, a sajátját is, és az egyik szomszédjáét is (mindig ugyanazt a kett˝ot). Megfigyelhetjük, hogy a villáknak két állapota van, szabad vagy foglalt. Ezen kívül minden villát egyszerre csak egy folyamat használhat, ezért legkézenfekv˝obb, ha a villákat bináris szemaforokkal reprezentáljuk. J AVA-ban monitorunk van, de ebb˝ol kiindulva szemafort is létrehozhatunk az olyan helyzetekre, amikor azt szeretnénk használni a programunkban. A bináris szemafor nem más, mint egy olyan monitor, amelynek egy boolean változó tárolja a foglaltsági állapotát, a folyamatok egy feltételváltozó várakozási során várakozhatnak, két muveletét ˝ pedig két monitoreljárás valósítja meg. Az alábbi programrészletben a muveleteket ˝ s_wait-nek és s_signal-nak nevezzük, hogy ne keveredjenek az Obje t wait és signal muveleteivel. ˝ 46

lass Sema { private boolean _free; publi Sema( boolean initval) { _free= initval; } publi syn hronized void s_wait() { while ( ! _free) try { wait(); }

at h ( InterruptedEx eption e) { } _free= false; }

}

publi syn hronized void s_signal() { _free= true; notify(); }

A J AVA 1.5-ös verziójától kezdve nem kell a fenti osztályt beilleszteni a programunkba valahányszor szemaforra van szükségünk, mert van beépített szemafor osztály is.

lass Semaphore { publi Semaphore( int initval); publi void a quire() throws InterruptedEx eption; publi void release(); ... }

// ini ializá ió kezd®értékkel // eredeti szemafor wait // eredeti szemafor signal

A wait és signal helyett megint új neveket kell megjegyeznünk, de a muveletek ˝ a szokásosak. A beépített Semaphore osztály felhasználásával a filozófus folyamatok viselkedését az alábbi kódrészlet írja le (a terminálással most nem foglalkozunk).

lass Philo extends Thread { private Semaphore _my_fork, _your_fork; publi Philo( String name, Semaphore my_fork, Semaphore your_fork) { super( name); _my_fork= my_fork; _your_fork= your_fork; } publi void run() { while ( ...) { ... // ideje enni valamit _my_fork.a quire(); _your_fork.a quire(); ...

}

}

}

// jóllaktam _my_fork.release(); _your_fork.release();

// gondolkodás // saját villa fel // szomszéd villája fel // evés // saját villa le // szomszéd villája le

47

A filozófusok rendszerét megvalósító program nem különösebben bonyolult. publi lass Diner { stati final int NofPhilos= 5; publi stati int neigbour( int i) { return ( i+1) % NofPhilos; } publi stati void main( String[℄ args) { Semaphore forks[℄= new Semaphore[ NofPhilos℄; Philo philos[℄= new Philo[ NofPhilos℄; for ( int i= 0; i < NofPhilos; ++i) forks[ i℄= new Semaphore( 1); for ( int i= 0; i < NofPhilos; ++i) { philos[ i℄= new Philo( "Philo" + i, fork[ i℄, fork[ neighbour( i)℄) philos[ i℄.start(); }

}

}

for ( int i= 0; i < NofPhilos; ++i) philos[ i℄.join();

Az étkez˝o filozófusokat azoknak a problémáknak az illusztrálására szokás bemutatni, amelyek a rendszer muködése ˝ során felléphetnek. Az egyik lehetséges probléma a holtpont. Ez úgy fordulhat el˝o, ha minden folyamat egyszerre "éhezik meg", és fel is veszik a saját villájukat. Ezután mindegyik megpróbál hozzájutni a szomszéd villájához, ami viszont már foglalt, így a rendszer nem tud tovább muködni. ˝ A holtpontot el lehet kerülni például úgy, ha megbontjuk a komponensek közötti szimmetriát, és az egyik filozófus fordított sorrendben veszi fel a villákat mint az összes többi. Ha ezt nem akarjuk, akkor kicsit nagyobb er˝ofeszítéssel alkalmazhatunk egy "biztonsági o˝ rt", vagyis bevezethetünk egy újabb komponenst, amelyiknek az a feladata, hogy egyszerre legfeljebb négy filozófust engedjen az asztalhoz. Ehhez egyrészt fel kell venni egy egész értéku˝ szemafort, másrészt át kell alakítani a filozófusokat, hogy kezeljék az új komponenst. Az o˝ r szemafor kezd˝oértékét 4-re kell állítani, ezzel olyan er˝oforráshoz jutunk, amelyb˝ol négy egységet lehet egyszerre kezelni, négy folyamat használhatja egyid˝oben.

lass Philo extends Thread { private Semaphore _my_fork, _your_fork, _guard; publi Philo( String name, Semaphore my_fork, Semaphore your_fork, Semaphore guard) { super( name); _my_fork= my_fork; _your_fork= your_fork; _guard= guard; } publi void run() { while ( ...) { ... // ideje enni valamit _guard.a quire(); _my_fork.a quire(); _your_fork.a quire();

// gondolkodás // asztalhoz // saját villa fel // szomszéd villája fel

48

...

}

}

}

// jóllaktam _my_fork.release(); _your_fork.release(); _guard.release();

// evés // saját villa le // szomszéd villája le // asztaltól

publi lass GuardedDiner { stati final int NofPhilos= 5; publi stati int neigbour( int i) ... publi stati void main( String[℄ args) { Semaphore forks[℄= new Semaphore[ NofPhilos℄; Philo philos[℄= new Philo[ NofPhilos℄; Semaphore guard= new Semaphore( NofPhilos-1); for ( int i= 0; i < NofPhilos; ++i) forks[ i℄= new Semaphore( 1); for ( int i= 1; i <= NofPhilos; ++i) { philos[ i℄= new Philo( "Philo" + i, fork[ i℄, fork[ neighbour( i)℄, guard) philos[ i℄.start(); }

}

3.3.4.

}

for ( int i= 1; i <= NofPhilos; ++i) philos[ i℄.join();

Alvó borbély probléma (Sleeping

barber)

Az alvó borbély probléma a részfolyamatok közötti kliens-szerver kapcsolatot modellezi. Egy kiszolgáló (szerver) folyamat kéréseket fogad kliens folyamatoktól, a kérés hatására valamilyen feldolgozást végez a kliens folyamatok érdekében, majd visszajuttatja az eredményt a kliensekhez. A kliens-szerver kapcsolatban a kliens az aktív, kezdeményez˝o fél, a szerver pedig a passzív fél. A kettejük lezajló adatáramlás kötött szabályok szerint, fázisokban történik. Kliens: Kérést küld a szerver felé. Megvárja, amíg a kérést a szerver feldolgozza és a választ visszaküldi. A kérés elküldése és a válasz megérkezése között nem kezdhet más tevékenységbe. Szerver: Várakozik, amíg kérés nem érkezik egy klienst˝ol. Feldolgozza a kérést és visszajuttatja az eredményt a kliensnek. Egyid˝oben csak egy klienssel foglalkozik, csak akkor vált másikra, amikor az el˝oz˝ot kiszolgálta. Az alvó borbély problémához tartozó „mese” úgy hangzik, hogy van egy borbélyüzlet egy borbéllyal (szerver). Az üzletben van egy borbélyszék, amelyben a kiszolgálás alatt álló ügyfél (kliens) ül, illetve néhány (akár tetsz˝oleges számú) másik szék, amelyben a kiszolgálásra várakozó ügyfelek ülnek. Ha nincs senki az üzletben, akkor a borbély alszik. Ha ügyfél érkezik, akkor felébreszti a borbélyt, leül a borbélyszékbe és megvárja, amíg levágják a haját (feldolgozzák a kérését). Ha a borbély készen van, akkor az ajtó kinyitásával jelez az ügyfélnek, hogy távozhat. A borbély megvárja, amíg az ügyfél becsukja maga mögött az ajtót (átveszi az eredményt), majd kezdi elölr˝ol a ciklusát. Közös memóriás környezetben az adatátadás pufferekben történik. Feltételezzük, hogy a szervernek van egy puffere, amelybe a kéréshez tartozó adatokat várja, és egy másik, amelybe az eredményt elhelyezi. A szervernek a feldolgozás végeztével még meg kell várnia, amíg a kliens kiüríti/feldolgozza az 49

eredménypuffert. A továbbiakban a pufferek kezelésével nem foglalkozunk, csak a folyamatok interakciójával, amelyet egy J AVA monitor segítségével adunk meg. Mindkét szerepl˝onek kétszer kell várakoznia, ezeket a várakozásokat négy feltételváltozó segítségével kényszerítjük ki. A borbélynak meg kell várnia, amíg ügyfél érkezik (_ hair_o

upied), illetve amíg a távozó ügyfél becsukja maga mögött az ajtót (_ ustomer_left). Az ügyfélnek meg kell várnia, amíg a borbély szabaddá válik (_barber_available), illetve amíg a feldolgozás befejez˝odik (_door_open). A monitor állapotának tárolására három boolean változót használunk (_barber, _ hair, _open). Egyébként a korábbiakban látott szokásos megoldásokat használjuk.

lass BarberShop { private boolean _barber= false; private boolean _ hair= false; private boolean _open= false; private private private private private

final final final final final

Lo k Condition Condition Condition Condition

// szabad? // székbe leült valaki? // ajtó nyitva?

_lo k= _barber_available= _ hair_o

upied= _door_open= _ ustomer_left=

new ReentrantLo k(); _lo k.newCondition(); _lo k.newCondition(); _lo k.newCondition(); _lo k.newCondition();

publi void get_hair ut() { _lo k.lo k(); try { while ( ! _barber) _barber_available.await(); _barber= false; ... // adatok feltöltése szerver pufferbe _ hair= true; _ hair_o

upied.signal(); while ( ! _open) _door_open.await(); ... // adatok kimásolása szerver pufferb®l _open= false; _ ustomer_left.signal();

}

}

at h ( InterruptedEx eption e) { } finally { _lo k.unlo k(); }

publi void get_next_ ustomer() { _lo k.lo k(); try { _barber= true; _barber_available.signal(); while ( ! _ hair) _ hair_o

upied.await(); _ hair= false; }

at h ( InterruptedEx eption e) { } finally { _lo k.unlo k(); } }

50

}

publi void finished_ ut() { _lo k.lo k(); try { _open= true; _door_open.signal(); while ( _open) _ ustomer_left.await(); }

at h ( InterruptedEx eption e) { } finally { _lo k.unlo k(); } }

A kliensek a get_hair ut eljárást hívják. Ennek visszatérése után rendelkezésükre áll az eredmény. A szerver egyetlen kliens kiszolgálásához két eljárást is meghív, el˝oször a get_next_ ustomer-t, aminek visszatérése után a kérés adatainak birtokában elkezdheti a feldolgozást. Miután elkészült, meghívja a finished_ ut eljárást, ennek visszatérése után készen áll a következ˝o ügyfél fogadására.

51

Irodalomjegyzék [1] O CCAM honlap

http://wotug.uk .a .uk/parallel/o

am/

[2] O CCAM 2.1 Reference Manual

http://www.wotug.org/o

am/do umentation/o 21refman.pdf

[3] PVM honlap

http://www. sm.ornl.gov/pvm/

[4] PVM könyv online

http://www.netlib.org/pvm3/book/pvm-book.html

[5] C.A.R.Hoare: Monitors: An Operating System Structuring Concept, Communications of the ACM, Vol. 17, No. 10. October 1974, pp. 549-557. Elérhet˝o online: http://www.a m.org/ lassi s/feb96/ [6] J AVA 1.5 dokumentáció

http://java.sun. om/j2se/1.5.0/do s/api/index.html

[7] S.Oaks, H.Wong: Java Threads, 3rd Edition, O’Reilly, 2004 ISBN 0-596-00782-5 [8] A.S.Tannenbaum, A.S.Woodhull: Operációs rendszerek, Panem-Prentice Hall, 1999 ISBN 963 545 189 X [9] B.Wilkinson, M.Allen: Parallel Programming, Prentice Hall, 1999 ISBN 0-13-671710-1 [10] G.A.Andrews: Foundations of Multithreaded, Parallel, and Distributed Programming, AddisonWesley, 2000 ISBN 0-201-35752-6

52