´ ´ BABES¸-BOLYAI TUDOMANYEGYETEM, KOLOZSVAR ´ MATEMATIKA ES INFORMATIKA KAR ¨ ¨ LORAND ´ ´ EOTV OS TUDOMANYEGYETEM, BUDAPEST INFORMATIKAI KAR
Oper´ aci´ os rendszerek funkcion´ alis modellez´ ese A doktori ´ertekez´es t´ezisei
´ PALI G´ abor J´ anos Doktori hallgat´o
Horia F. POP (UBB) KOZSIK Tam´ as (ELTE) Doktori t´emavezet˝ok
¨ ¨ LORAND ´ ´ EOTV OS TUDOMANYEGYETEM INFORMATIKA DOKTORI ISKOLA Doktori program: Az informatika alapjai ´es m´odszertana ´ Andr´as, DSc. Iskolavezet˝o: BENCZUR Programvezet˝o: DEMETROVICS J´anos, DSc.
2012
Bevezet´ es A sz´am´ıt´og´epek szerves r´eszei mindennapjainknak, mindegyik¨ uk k´et fontos alkot´or´eszb˝ol tev˝odik ¨ossze: ez a hardver ´es a szoftver. Ezek sz´etv´alaszt´od´asa egy olyan evol´ uci´o eredm´enye, amelynek sor´an a m´ern¨ok¨ok k´enytelenek voltak bel´atni, hogy a technol´ogiai fejl˝od´est u ´gy tudj´ak felgyors´ıtani, ha programozhat´o alacsonyszint˝ u fel¨ ulettel rendelkez˝o hardvereszk¨oz¨oket gy´artanak, amelyekre azt´an tov´abbi virtu´alis, szoftveres r´etegek ´ep´ıthet˝oek. Ennek eredm´enyek´eppen manaps´ag szinte m´ar lehetetlen olyan g´epet tal´alni, amely legal´abb egy ilyen r´eteget ne tartalmazna, ´es ezt a r´eteget szokt´ak ´altal´aban ,,oper´aci´os rendszernek” nevezni. A sz´am´ıt´og´epek ´elet¨ unkben bet¨olt¨ott szerep´enek v´altoz´as´aval az oper´aci´os rendszerek is v´altoztak. Az u ´j ´evezred bek¨osz¨ont´evel a processzorok lassan el´ert´ek u ¨zemeltet´esi frekvenci´ajuk fels˝o hat´arait, ez´ert tervez˝oik azok sk´al´az´as´anak egy u ´jabb dimenzi´oj´at nyitott´ak meg, ´es egyre t¨obb magot, feldolgoz´o egys´eget kezdtek ´ep´ıteni bel´ej¨ uk. Ezzel egyid˝oben viszont tov´abbra is megmaradt az egyszer˝ u de megb´ızhat´o ig´enye. Ennek ment´en nyilv´anval´o, hogy az el˝oz˝o ´evtizedekben kialakult szoftverfejleszt´esi m´odszereket valamilyen m´odon igaz´ıtani kell tudnunk ezekhez az ig´enyekhez, nem kev´es kih´ıv´ast jelentve ezzel a szoftverfejleszt˝ok sz´am´ara. Annak ellen´ere, hogy folyamatosan u ´jabb ¨otletekkel ´es megk¨ozel´ıt´esekkel halmozz´ak el, az oper´aci´os rendszerek fejleszt´ese tov´abbra is az 1970-es ´evekben, a UNIX ´es a C programoz´asi nyelv ment´en lefektetett alapokra t´amaszkodik javar´eszt. Az u ´jelv˝ u oper´aci´os rendszerek terjed´es´eben komoly akad´alyt jelent ugyanis azok t´amogatotts´ag´anak hi´anya. Megfelel˝o hardvert´amogat´as (vagy legal´abb azok megfelel˝o dokument´aci´oja) n´elk¨ ul egy oper´aci´os rendszer l´enyeg´eben eleve kudarcra van ´ıt´elve. Azonban akadnak az iparnak olyan szegmensei, ahol a v´allalatok ´es a szoftverfejleszt˝ok m´ar t´ ul szeretn´enek l´epni a C nyelv ´es annak lesz´armazottainak alkalmaz´as´an, ´es ez´ert kitart´oan keresik tov´abb azokat a megold´asokat, amelyek az alacsonyszint˝ u rendszerek fejleszt´es´eben nagyobb g´epes´ıthet˝os´eget ´ıg´ernek. Emellett a hardverek fejl˝od´es´enek ir´anya ´es u ¨teme is egyre ink´abb egy magasabb szint˝ u gondolkod´asra k´eszteti a programoz´okat, ahol egy hardverhez tartoz´o ford´ıt´oprogram seg´ıti ˝oket munk´ajuk min´el hat´ekonyabb elv´egz´es´eben. Itt ´altal´aban figyelembe kell venn¨ unk a kapcsol´od´o szakter¨ ulet elv´ar´asait is, aminek kihaszn´al´as´aval a rendszerek szerkeszt´ese sor´an t¨obb szemantikai inform´aci´ot tudunk kinyerni a megfelel˝o magasabb szint˝ u specifik´aci´okb´ol. ´Igy ¨osszes´eg´eben azt´an kevesebb emberi beavatkoz´assal jobb c´elnyelvi programok k´esz´ıthet˝oek. Az ´ertekez´es az al´abbi m´odokon t¨orekszik v´alaszokat adni ezekre a k´erd´esekre: – Bevezetj¨ uk a Flow-t, a minimalista tapaszt´onyelvet, amellyel k¨ ul¨onb¨oz˝o be´agyazott szakter¨ ulet-specifikus programoz´asi nyelveken ´ırt programokat tudunk szervezni ´es ¨osszekapcsolni. A Flow c´elja, hogy a Haskell tiszt´an funkcion´alis programoz´asi nyelvet egy olyan specifik´aci´os eszk¨ozz´e alak´ıtsa, amely kell˝oen t¨om¨or ´amde m´egis k´epes kifejezni bonyolult alkalmaz´asokat szakter¨ ulet-specifikus nyelvek kompoz´ıci´ojak´ent. – Bemutatunk egy adatfolyamgr´afokra ´ep¨ ul˝o magasszint˝ u sz´am´ıt´asi modellt, amely ¨osszetettebb alkalmaz´asokat k´epes platformf¨ uggetlen m´odon le´ırni. A modell jellegzetess´egeib˝ol fakad´oan r´aad´asul az ´ıgy meval´os´ıtott rendszer szemantik´aja egyszer˝ uen ´es tiszt´an megadhat´o, felt´etelezve, hogy maguk az alkot´or´eszek is tiszta sz´am´ıt´asokkal kifejezhet˝oek. Ugyanez a modell lehet˝ov´e teszi azt is, hogy a rendszer m˝ uk¨od´ese magasszint˝ u ´es deklarat´ıv m´odon legyen vez´erelhet˝o.
1
– A Flow nyelven meg´ırt rendszerek fut´as´at seg´ıtend˝o, le´ırjuk a a nyelvhez tartoz´o, szint´en minimalista futtat´o rendszer fel´ep´ıt´es´et ´es megval´os´ıt´as´anak r´eszleteit. A futtat´o rendszer szorosan k¨oveti a nyelvhez tartoz´o sz´am´ıt´asi modellt ´es az a c´elja, hogy a modell sz´am´ara fontos alapvet˝o absztrakci´ok minden platformon el´erhet˝oek legyenek. Enn´elfogva c´elunk a kidolgoz´as sor´an az volt, hogy ezen absztrakci´ok sz´am´at a lehet˝o legjobban cs¨okkents¨ uk. Ez term´eszetesen sz´amos el˝onnyel j´ar: a futtat´o rendszert a k´es˝obbiekben k¨onnyebb m´as k¨ornyezetekbe is ´at¨ ultetni, illetve k¨onnyebb mag´anak a futtat´o rendszernek is megfogalmazni a form´alis szemantik´aj´at.
Kapcsol´ od´ o munka El˝orevet´ıtve dolgozatunk v´egk¨ovetkeztet´eseit, r¨oviden u ´gy ¨osszegezhetn´enk a funkcion´alis nyelvek eszk¨ozeinek alkalmazhat´os´ag´at az oper´aci´os rendszerek ter¨ ulet´en, hogy ez nagyon is lehets´eges. A t´argyal´asban ehelyett ink´abb arra ´erdemes helyezni a hangs´ ulyt, hogy mindez milyen kompromisszumok ´ar´an ´erhet˝o el a hat´ekonys´ag ´es a karbantarthat´os´ag hat´armezsgy´ej´en u ¨gyesen egyens´ ulyozva. P´eld´aul a Mirage [9] egy olyan ´ıg´eretes kutat´asi projekt term´eke, amely els˝osorban a napjainkban n´epszer˝ u felh˝oszolg´altat´asok (“cloud computing”) egyszer˝ ubb l´etrehoz´as´at t˝ uzte ki c´elj´aul, ´es amely erre a feladatra egy k¨ ul¨on specializ´alt szoftverk´eszletet alkalmaz. A Mirage egy exokerneles, u ´n. ,,vertik´alis oper´aci´os rendszer”. A hardverre vonatkoz´o r´eszletekt˝ol egy hypervisor, mint amilyen mondjuk a Xen vagy a Hyper-V, seg´ıts´eg´evel vonatkoztat el, ´es a magasszint˝ u nyelven elk´esz´ıtett szoftverkomponenseket az ´ıgy l´etrehozott virtu´alis hardverre igaz´ıtja. ´Igy a Mirage k´epes a hypervisorok nagyon alacsony szint˝ u fel¨ ulet´et magasszint˝ u absztrakci´okra cser´elni. A Mirage magasszint˝ u nyelvk´ent egy m´asik (noha nem tiszt´an) funkcion´alis nyelvet, az OCamlt v´alasztotta, mivel a kutat´oknak m´ar kor´abban is voltak vele pozit´ıv tapasztalataik nagyteljes´ıtm´eny˝ u rendszerek fejleszt´es´eben. R´aad´asul, mag´at az OCaml ford´ıt´ot nem is kellett m´odos´ıtaniuk, elegend˝o volt csup´an a futtat´o rendszert hozz´aigaz´ıtani az alatta lev˝o oper´aci´os rendszer ig´enyeihez.
A dolgozat v´ azlata A digit´alis jelfeldolgoz´o (Digital Signal Processing, DSP) algoritmusokat ´altal´aban egy absztrakt, platformf¨ uggetlen m´odon tervezik meg, amelyet azt´an k´epzett C programoz´ok megval´os´ıtanak meg adott DSP processzorokon. A terv ´es ´es konkr´et implement´aci´o k¨ozt viszont el´eg nagy a szakad´ek, az eredm´eny¨ ul keletkez˝o C programok ak´ar processzoronk´ent elt´erhetnek. Emiatt a fejleszt´es sor´an az u ´jabb hardverre val´o ´att´er´eskor szinte minden alkalommal u ´jra kell ´ırni az eg´eszet. Ez´ert abban b´ızunk, hogy egy megfelel˝o magasszint˝ u be´agyazott nyelv (DSL) ´es adott platformra felk´esz´ıthet˝o ford´ıt´oprogramj´anak seg´ıts´eg´evel az algoritmusok implement´aci´oja jelent˝osen meg tudja k¨onny´ıteni ezt a folyamatot. Ehhez a Feldspar (Functional Embedded Language for Digital Signal Processing and Parallelism) [7] javasoljuk, amely ISO C99 k´odra esetleg az LLVM k¨oztes reprezent´aci´oj´ara tud k´odot gener´alni. A DSP-k sz´ant szoftverek ´altal´aban el´egg´e hardverf¨ ugg˝oek, ´ıgy az u ´jabb processzorokra val´o ´att´er´es gyakran u ´jratervez´est is jelent. A Feldspar ez´ert lehet˝ov´e teszi, hogy algoritmusokat specifik´aci´o szintj´en ´ırjuk le, amit a megfelel˝o absztrakci´ok ´es tran2
szform´aci´ok k¨ozrem˝ uk¨od´es´evel olyan C k´odd´a alak´ıthat´oak, amelyek k¨ozel azonos szinten vagy esetleg jobban teljes´ıtenek, mint a k´ezzel ´ırt v´altozataik. A Feldspar ford´ıt´o modul´aris ´es ez´altal k¨onnyen b˝ov´ıthet˝o, p´eld´aul a k¨ovetkez˝o gener´aci´os hardverek fel´ep´ıt´es´ere vonatkoz´o inform´aci´okkal. Ennek k¨osz¨onhet˝oen a hardverrel kapcsolatos tud´as a ford´ıt´oprogramba vihet˝o ´at ´es ´ıgy automatikusan hat´ekony, hardverf¨ ugg˝o k´od ´all´ıthat´o el˝o. Az ´ertekez´esben ezt a Feldspar nyelvet haszn´aljuk a Flow nyelvvel egy¨ utt a p´eld´ak bemutat´asa sor´an. Valamint seg´ıts´eg´evel megmutatjuk, hogy mik´ent lehet modern eszk¨oz¨okkel a Haskell tiszt´an funkcion´alis programoz´asi nyelven m´as programoz´asi nyelveket hat´ekonyan kifejezni, m´asn´even be´agyazni. Ezek a technik´ak ugyanis a Flow kialak´ıt´as´aban ´es megval´os´ıt´as´aban is fontos szerepet j´atszottak. Az ¨osszetettebb szoftverrendszerek, mint amilyenek maguk az oper´aci´os rendszerek is, ´altal´aban sz´amos, a legjobb teljes´ıtm´enyre hangolt rutint tartalmaznak, amelyeket azt´an valamilyen fels˝obb r´etegekb˝ol kapcsoljuk ¨ossze ´es vez´erelj¨ uk. A rendszer n¨oveked´es´evel azonban annak megb´ızhat´o m˝ uk¨od´ese, m´as platformokra t¨ort´en˝o ´at¨ ultethet˝os´ege ´es karbantarthat´os´aga egyre ink´abb fontosabb´a v´alik. Ezt azonban ellen˝orz¨ott keretek k¨oz´e tudjuk szor´ıtani, ha elvonatkoztatunk a platformf¨ ugg˝o r´eszletekt˝ol ´es az alkot´or´eszeket, valamint azok kapcsolat´at egy magasabb szinten modellezz¨ uk. A funkcion´alis programoz´asb´ol k¨olcs¨onz¨ott nyelvbe´agyaz´as technik´aj´anak seg´ıts´eg´evel tal´an kaphattunk egy olyan v´alaszt, amely seg´ıt egy ilyen megold´as megval´os´ıt´as´aban. Ilyenkor p´eld´aul az egyes alkot´or´eszeket egy nekik megfelel˝o szakter¨ ulet-specifikus nyelven ´ırjuk le, amelyet azt´an egy alacsonyabb szint˝ u nyelvre ford´ıtunk le. Arra viszont m´eg nincs eszk¨oz¨ unk, hogy mik´ent kapcsoljuk ezeket ¨ossze egy nagyobb, ¨osszef¨ ugg˝o rendszerbe. Erre c´elra az ´ertekez´esben a Flow nyelvet vezetj¨ uk be konkr´et p´eld´akon ´es alkalmaz´asokon kereszt¨ ul. Tov´abb´a megfogalmazza azokat a fontosabb elemeket – a feladatokat, csatorn´akat ´es a feladatok v´egrehajt´as´at –, amelyek v´eg¨ ul egy sz´am´ıt´asi modell kialak´ıt´as´ahoz vezetnek. Itt a hangs´ uly legink´abb a megk¨ozel´ıt´es alkalmazhat´os´ag´an van, vagyis mik´ent tudunk alkalmazni vele egy¨ utt tetsz˝oleges, Haskellbe ´agyazott nyelveket nagyobb, szakter¨ ulet-specifikus feladatok megold´as´ara. A be´agyazott szakter¨ ulet-specifikus nyelvek sz´am´ara ´ıgy kialak´ıtott koordin´aci´os nyelvi keretrendszer megtervez´ese ´es megval´os´ıt´asa sor´an r¨oviden ´erintj¨ uk specializ´alt feladatgr´afok v´egrehajt´as´anak k´erd´esk¨or´et is. Ilyenkor ugyanis l´enyeg´eben DSL programokat szervez¨ unk adatfolyamgr´afokba, amelyekhez munkafolyamatokat (v´egrehajt´o egys´egeket) alak´ıtunk ki, ´es ezek fut´as k¨ozben dinamikusan v´egrehajtj´ak a feladatokat. A munkafolyamatok sz´am´at az adott hardverben tal´alhat´o feldolgoz´o egys´egek sz´am´ahoz igaz´ıtjuk, ´ıgy cs¨okkenteni tudjuk a futtat´ast t´amogat´o k¨ornyezettel kapcsolatos elv´ar´asainkat, lehet˝ov´e t´eve a leford´ıtott gr´afok futtat´as´at ak´ar k¨ozvetlen¨ ul mag´an a hardvereszk¨oz¨on is. Az ´ıgy keletkezett rendszerek teljes´ıtm´eny´enek vizsg´alata sor´an azonban arra a k¨ovetkeztet´esre jutottunk, hogy a gr´afok futtat´as´anak na´ıv u ¨temez´ese nem elegend˝o ahhoz, hogy t¨obb munkafolyamat eset´en is fenntarthat´o legyen a hat´ekonys´ag, mivel eddig nem vett¨ uk figyelembe feladatok k¨ozti adatf¨ ugg˝os´egeket. Ennek orvosl´as´ara a feladatokat ez´ert oszt´alyozhat´ov´a tessz¨ uk, noha ennek automatiz´al´asa nem felt´etlen¨ ul egyszer˝ u feladat. Ez´ert kidolgoztunk egy m´asik olyan szakter¨ ulet-specifikus funkcion´alis nyelvet, amellyel adatfolyamgr´afok u ¨temez´es´ere vonatkoz´oan tudunk t¨obblettud´ast bevinni a rendszerbe. Ezt nevezz¨ uk az ´ertekez´esben ,,deklarat´ıv u ¨temez´esnek”. A deklarat´ıv u ¨temez´es r´ev´en olyan szakter¨ ulet-specifikus u ¨temez´esi megszor´ıt´asokat tudunk megfogalmazni, amelyek r´ev´en el tudunk vonatkoztatni az alacsonyabb szint˝ uu ¨temez´esi r´eszletekt˝ol ´es helyette a megfelel˝o protokoll megval´os´ıt´as´ara koncentr´alni. A t´em´aban v´egzett kutat´asaink azt mu3
tatt´ak, hogy ezt a fogalmat m´ar alkalmazz´ak mind az adatb´azisok ´es a felh˝oszolg´altat´asok eset´eben, ´ıgy k´ezenfekv˝onek tal´altuk eset¨ unkben is felhaszn´alni. V´egezet¨ ul a dolgozat megpr´ob´alja kiakn´azni a Flow nyelvben rejl˝o lehet˝os´egeket ´es olyan kiterjeszt´eseket javasol az eddigi modellhez, amelyekkel bizonyos tulajdons´agok ment´en tudjuk finomhangolni a keletkez˝o rendszer ¨osszteljes´ıtm´eny´et. Mindezt r´aad´asul u ´gy, hogy az alkalmaz´asunkat egy magasabb szinten fogalmazzuk meg ´es a r´eszleteket a megfelel˝o ford´ıt´oprogramokra b´ızzuk. Az ´ertekez´es az al´abbi fejezetekb˝ol ´all. Az els˝o fejezetben ´attekintj¨ uk a kutat´asi ter¨ uletet, ´es a kapcsol´od´o munk´ak ´attekint´es´evel egyid˝oben r¨oviden megfogalmazzuk a megoldand´o probl´em´akat. Ezek megold´as´at a r´ak¨ovetkez˝o fejezetekben fejtj¨ uk ki l´ep´esr˝ol l´ep´esre. A m´asodik fejezetben bevezetj¨ uk mindazon alkalmazott technik´akat, amelyek ismerete felt´etlen¨ ul n´elk¨ ul¨ozhetetlen a munk´ank meg´ert´es´ehez. Itt a Haskell nev˝ u tiszt´an funkcion´alis programoz´asi nyelvet haszn´aljuk fel arra, hogy defini´aljunk egy m´asik programoz´asi nyelvet. Ezt nyelvbe´agyaz´asnak (language embedding) nevezik. A fejlett t´ıpusrendszer ´es a puszt´an f¨ uggv´enyekkel val´o programoz´asban rejl˝o rugalmass´ag a Haskellt nagyon is alkalmass´a teszi arra, hogy u ´j programoz´asi nyelvek protot´ıpusait alkossuk meg benne. Ennek l´ep´eseit, valamint a nyelvebe´agyaz´as alapfogalmait a Feldspar megval´os´ıt´as´anak r´eszleteinek t´argyal´as´aval mutatjuk be. Mag´anak a Haskellnek egyes r´eszeit (p´eld´aul mon´adokat) is ugyanezen a m´odon val´os´ıtj´ak meg, ami miatt ez ebben a k¨ornyezetben egy teljesen szokv´anyos gondolkod´ast k¨ovet. A harmadik fejezetben a Flow ker¨ ul bemutat´asra. Itt az a c´elunk, meg tudjuk tartani a Feldspar eset´en m´ar az el˝oz˝o fejezetben megtapasztalt kompozicion´alit´ast, mik¨ozben az eg´eszet egy olyan magasabb szintre emelj¨ uk, ahol a programokat ak´ar elt´er˝o DSLekben is meg´ırhatjuk. A Flow m´asik szerepe azt megmutatni, hogy egy nagyobb rendszer jellemz˝o alkot´or´eszei mik´ent foghat´oak meg absztrakt st´ılusban. Emellett m´eg egy absztrakt g´ep szemantik´aj´anak megad´as´an kereszt¨ ul mutatjuk be, mik´ent lehet futtatni az ´ıgy megszerkesztett programokat. A negyedik fejezetben a Flow nyelven k´esz´ıtett rendszerek hat´ekonys´ag´at vizsg´aljuk. Ennek sor´an t¨obbek k¨ozt olyan k´erd´eseket dolgozunk fel, amelyek azzal foglalkoznak, hogy mik´ent tudjuk u ¨temezni az egyes programok fut´as´at a rendelkez´es¨ unkre ´all´o er˝oforr´asok (processzorok ´es mem´oria) min´el jobb kioszt´as´aval. Elemz´eseink r´ev´en egy olyan k´odgener´al´asi strat´egi´at ´es egy hozz´a tartoz´o kis m´eret˝ u futtat´o rendszert ismertet¨ unk, amely k¨ozvet´ıt´es´evel ellens´ ulyozhat´oak a funkcion´alis nyelvi megval´os´ıt´ashoz ´altal´aban k¨ot˝od˝o korl´atoz´asok. R´aad´ask´ent bevezetj¨ unk egy programozhat´o u ¨temez´esi s´em´at, amely v´eg¨ ul seg´ıt a kor´abban bemutatott absztrakt g´ep p´arhuzamos szemantik´aj´anak kialak´ıt´as´aban. Az ¨ot¨odik fejezetben egy nagyobb rendszer megval´os´ıt´as´an kereszt¨ ul folytat´odik a Flow alkalmazhat´os´ag´anak vizsg´alata ´es demonstr´al´asa. De ezen k´ıv¨ ul m´eg az is a c´elunk ezzel, hogy modellezz¨ uk az oper´aci´os rendszerek egy bizonyos oszt´aly´at. Az itt bemutatotthoz hasonl´o rendszerek ugyanis gyakran el˝ofordulnak be´agyazott rendszerek eset´en, ahol az oper´aci´os rendszernek az a feladata, hogy a hardvert egy konkr´et alkalmaz´as, p´eld´aul digit´alis jelfeldolgoz´ashoz kapcsol´od´oan programozza fel ´es m˝ uk¨odtesse. Ez´ert itt visszany´ ulunk a m´asodik fejezetben bemutatott Feldspar nyelvhez, hogy annak egy lehets´eges b˝ov´ıt´es´evel kiterjessz¨ uk annak m˝ uk¨od´es´et egy komplett rendszerr´e. A hatodik fejezetben ¨osszehasonl´ıtjuk eredm´enyeinket a szakter¨ uleten fellelhet˝o m´as egy´eb megold´asokkal, k¨ ul¨on¨os tekintettel a saj´at megk¨ozel´ıt´es¨ unkben rejl˝o elt´er´esekre. Vagyis milyen el˝ony¨okkel ´es h´atr´anyokkal j´arnak az ´altalunk adott v´alaszok a t¨obbi hasonl´o munka viszonylat´aban. 4
V´egezet¨ ul, a hetedik fejezet z´arja az ´ertekez´est a t´emara vonatkoz´o k¨ovetkeztet´eseink ¨osszegz´es´evel.
K¨ ovetkeztet´ esek A digit´alis jelfeldolgoz´as az ipar egyik jelent˝os szakter¨ ulete, ´es a sok- ´es t¨obbmagos processzorok megjelen´es´evel folyamatosan keresi azokat az u ´j technol´ogi´akat, amelyek lehet˝ov´e teszik a kapcsol´od´o szoftverek gyors, megb´ızhat´o ´es fenntarthat´o fejleszt´es´et. ´ A Flow nyelvet is ilyen elv´ar´asok ment´en dolgoztuk ki. Ugy gondoljuk viszont, a Flow nyelv nem csak digit´alis jelfeldolgoz´o rendszerek ´ep´ıt´es´ere lehet alkalmas, hanem hordoz mag´aban annyi rugalmass´agot, hogy ig´eny szerint m´as ter¨ uleteken is alkalmaz´asra tal´aljon, ak´ar egyszerre t¨obben eset´en. Ennek kapcs´an a Flow a maga kev´es elv´ar´as´aval nagy szabads´agot ny´ ujt a kapcsolhat´o DSL-ek tervez˝oi sz´am´ara, ez´altal jobban testreszabhat´ov´a t´eve az egyes szakter¨ uletek eset´eben. A ter¨ uleten v´egzett tapasztalataink ´es kutat´asaink alapj´an az al´abbi k¨ovetkeztet´eseket tudjuk levonni. T´ ezis. A probl´em´ak szakter¨ ulet-specifikusan val´o megfogalmaz´asa jobban seg´ıti a ford´ıt´ oprogramot abban, hogy hozz´ajuk hat´ekonyabb k´odot tudjuk el˝o´all´ıtani. Amikor egy programot alkot´o szerkezetek t´ uls´agosan alacsonyszint˝ uek, akkor a ford´ıt´oprogramnak nagyon intelligensnek kell lennie ahhoz, hogy felfedezze a forr´asprogramokban az ´altaluk elrejtett absztrakci´okat. Ugyanekkor a programok helyess´eg´evel kapcsolatban is nehezebb ´ervelni, nehezebb megmondani, hogy a program megfelel-e a specifik´aci´onak. A szakter¨ ulet-specifikus nyelvek azonban t¨obbnyire magasszint˝ u szerkezeteket tartalmaznak, amelyek seg´ıtik a programoz´ot egy j´ol meghat´arozott, a szakter¨ uletet le´ır´o absztrakt modell k¨ovet´es´eben. Ennek sor´an a programoz´o j´oval t¨obb mindent fel tud fedni a sz´and´ekaib´ol, ´ıgy a ford´ıt´onak is t¨obb es´elye van l´atni a megoldand´o feladatot. Szerencs´es esetben, a nyelv defin´ıci´oja egybeesik a form´alis specifik´aci´oval, vagyis a programok maguk is specifik´aci´okk´a v´alnak. A Feldspar eset´eben ezek matematikai k´epleteket jelentenek, amelyeket a neki megfelel˝o programok sz´am´ıtanak ki, ahogy ezt bemutatja a [1, 2]. T´ ezis. A probl´em´ak szakter¨ ulet-specifikus megfogalmaz´asa seg´ıti a programoz´ot abban, hogy kevesebb hib´at v´etsen ´es hogy mentes¨ ulj¨on a sablonos programr´eszek meg´ır´as´at´ol. A rendszer ´atszervez´ese k¨onnyebben megoldhat´o. A ford´ıt´as szemsz¨og´eb˝ol a deklarat´ıv megk¨ozel´ıt´es l´enyeg´eben ahhoz j´arul hozz´a, hogy a specifik´aci´ora mint egy tud´asb´azisra tekints¨ unk, ahol a ford´ıt´onak van valamennyi szabads´aga a ford´ıt´as sor´an, mivel t¨obbet ´es magasabb szinten tud a sz´obanforg´o rendszerr˝ol. A deklarat´ıv n´ez˝opont mag´at a programoz´ot is arra sarkallja, hogy ne legyen t´ uls´agosan hanyag a megold´as r´eszeleteit illet˝oen. Ehelyett a szisztematikus r´eszek kiemelhet˝oek, a program pedig t¨om¨orr´e tehet˝o, amelyet azt´an k´es˝obb egyszer˝ u meg´erteni ´es m´odos´ıtani. Ezt a [6] ´ırja le. T´ ezis. A kompozicionalit´as az oper´aci´os rendszerek eset´en is megval´os´ıthat´o ´es kifizet˝od˝ o. Az oper´aci´os rendszerek ´es a hozz´ajuk hasonl´o programok eset´en a kompozicionalit´as
5
bevezet´es egy er˝oteljes fejleszt´esi m´odszertanhoz vezet. Ennek sor´an a rendszert t¨obb r´eteg kompoz´ıci´ojak´ent adjuk meg. Ha ezt m´eg vegy´ıtj¨ uk a deklarat´ıv megk¨ozel´ıt´essel, a r´etegek kompon´al´asa (vagy ¨osszef´es¨ ul´ese) ak´ar a k¨oztes adatszerkezetek elt˝ untet´es´evel is j´arhat, vagyis ezen a m´odon specializ´alt programokk´a tudjuk ¨osszeolvasztani az egy´ekb´ent ´ ´altal´anos alkot´or´eszeket. Ugy gondoljuk, a [4]-ben bemutatott Flow nyelv j´o p´eld´at ad arra, hogy mik´ent lehet megalkotni egy olyan absztrakt eszk¨ozt, amely kieg´esz´ıt˝o r´etegk´ent lehet˝ov´e teszi m´ar meglev˝o komponensek ¨osszekapcsol´as´at k¨ ul¨onb¨oz˝o k¨ornyezetekben. T´ ezis. A szakter¨ ulet ´altal defini´alt korl´atozott szemantika egy kisebb m´eret˝ u, specializ´alt futtat´asi k¨ornyezetet k´ıv´an meg, amely komolyabb kih´ıv´asok n´elk¨ ul valamennyi architekt´ ur´an kialak´ıthat´o. Az ´ertekez´esben az ¨osszekapcsolt programok adatfolyamgr´afk´ent val´o ´abr´azol´as´anak ´es futtat´as´anak teremtj¨ uk meg az alapjait ´es szemantik´aj´at. Ez a modell viszont csak n´eh´any egyszer˝ u absztrakci´oval dolgozik: feladatok, feladatcsoportok, u ¨zenetsorok ´es munkafolyamatok. Az ´ertekez´es r´eszek´ent ehhez megadunk egy konkr´et programoz´asi fel¨ uletet (API-t) is, amelyet C nyelven ´es egy POSIX kompatibilis rendszer mellett meg ´ v´elj¨ lehet val´os´ıtani. Ugy uk, ez a szint lentebb is vihet˝o, egesz´en ak´ar k¨ozvetlen¨ ul a hardverig, noha a be´agyazott rendszerek gy´art´oi (p´eld´aul a Tilera) gyakran m´ar eleve ilyen k¨ornyezetet adnak eszk¨ozeikhez. Az eredm´enyeket a [6] tartalmazza. ¨ Osszes´ eg´eben teh´at a fenti ´eszrev´eteleink arra engednek k¨ovetkeztetni, hogy a funkcion´alis nyelvek ´altal el´erhet˝o ford´ıt´asi technol´ogi´ak olyan el˝ony¨okkel j´arnak az oper´aci´os rendszerek fejleszt´ese eset´en, amelyek r´ev´en modellek alapj´an tudunk automatikusan ´es megb´ızhat´o m´odon k´odot gener´alni.
K¨ osz¨ onetnyilv´ an´ıt´ as Ez´ uton is szeretn´enk megk¨osz¨onni az Ericsson Software Research, az, Ericsson Business ¨ Network Units, az SSF (Sv´edorsz´ag), a Magyar Nemzeti Fejleszt´esi Ugyn¨ oks´eg (KMOP2008-1.1.2), a Programul Operat¸ional Sectional Dezvoltarea Resurselor Umane 2007– 2013 (POSDRU/6/1.5/S/3-2008, Rom´ania) anyagi t´amogat´as´at. Tov´abb´a szeretn´enk k¨osz¨onetet mondani a Feldspar fejleszt´ese k¨or¨ ul szorgoskod´o tagoknak ´es hallgat´oknak, E¨otv¨os Lor´and Tudom´anyegyetem Programoz´asi Nyelvek ´es Ford´ıt´oprogramok Tansz´ek´en, a Chalmers M˝ uszaki Egyetem Sz´am´ıt´og´eptudom´anyi ´es M´ern¨oki Tansz´ek´en, valamint a Babe¸s-Bolyai Tudom´anyegyetem Sz´am´ıt´og´eptudom´anyi Tansz´ek´en dolgoz´o mindazon koll´eg´aknak ´es hallgat´oknak, akik v´elemeny¨ ukkel ´es munk´ajukkal az ´evek sor´an valamilyen m´odon hozz´aj´arultak ennek az ´ertekez´esnek a fejl˝od´es´ehez. Tov´abb´a, nagyon h´al´asnak ´erezz¨ uk magunkat, hogy a FreeBSD Projekt akt´ıv tagjak´ent gy˝ ujthett¨ uk a t´em´ahoz k¨ot˝od˝o tapasztalatokat, ´es ahol az ´evek sor´an a Glasgow Haskell Compiler, valamint hozz´a tartoz´oan megannyi Haskell Cabal csomag portj´anak karbantart´ojak´ent lehet˝os´eg¨ unk ny´ılt egyszerre r´al´at´ast kapni napjaink oper´aci´os rendszereinek, illetve funkcion´alis programoz´asi nyelveinek szervez´es´ere, bels˝o m˝ uk¨od´es´ere ´es k´epess´egeire. Hasonl´oan fontosnak ´erezt¨ uk a lehet˝os´eget, hogy sok-sok f´el´even kereszt¨ ul az E¨otv¨os Lor´and Tudom´anyegyetemen tan´ıthattunk Haskellt kezd˝ok ´es halad´ok sz´am´ara egyar´ant.
6
Hivatkoz´ asok [1] G. D´evai, Z. Gera, Z. Horv´ath, G. P´ali, M. Tejfel. Feldspar – A Functional Embedded Language for DSP, 8th International Conference on Applied Informatics (ICAI2010), Eger, Hungary, January 27–30, 2010, Vol. 2, pp. 149–156. [2] G. D´evai, M. Tejfel, Z. Gera, G. P´ali, Gy. Nagy, Z. Horv´ath, E. Axelsson, M. Sheeran, A. Vajda, B. Lyckegard, A. Persson. Efficient Code Generation from the High-Level Domain-Specific Language Feldspar for DSPs, Proc. ODES-8: 8th Workshop on Optimizations for DSP and Embedded Systems, assoc. with IEEE/ACM International Symposium on Code Generation on Optimization (CGO), Toronto, Canada, April 25, 2010, pp. 12–20. [3] G. P´ali, Z. Gili´an, Z. Horv´ath, A. Persson. Describing Digital Signal Processing Systems in a Functional Reactive Style. Volume of Extended Abstracts of the 7th Conference of PhD Students in Computer Science (CSCS2010), Szeged, Hungary, June 29 – July 2, 2010, p. 58. [4] G. P´ali. Extending Little Languages into Big Systems. To appear in Horv´ath Z., Zs´ok V. (Eds.): Central European Functional Programming School. Fourth Summer School, CEFP 2011. Revised Selected Lectures. Lecture Notes in Computer Science, (ISSN 0302-9743), Vol. 7241, pp. 499–516. [5] G. P´ali. Declarative Scheduling of Dataflow Networks. Volume of Abstracts of the 9th Joint Conference on Mathematics and Computer Science (MaCS2012), Si´ofok, Hungary, February 9–12, 2012, p. 78. [6] G. P´ali. Declarative Scheduling of Dataflow Networks, Annales Universitatis Scientarium Budapestinensis de Rolando E¨otv¨os Nominatae, Sectio Computatorica, Vol. 37(2012), pp. 311–338. [7] E. Axelsson, G. D´evai, Z. Horv´ath et al. Feldspar: A Domain-Specific Language for Digital Signal Processing Algorithms, Proc. 8th ACM/IEEE International Conf. on Formal Methods and Models for Codesign, MemoCode, IEEE Computer Society, 2010. [8] C. Elliott, S. Finne, O. de Moor. Compiling Embedded Languages, Proc. Semantics, Applications and Implementation of Program Generation (SAIG 2000), 2000. [9] A. Madhavapeddy, R. Mortier, R. Sohan, T. Gazagnaire, S. Hand, T. Deegan, D. McAuley, J. Crowcroft. Turning Down the LAMP: Software Specialization for the Cloud, Proc. of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud), Boston, Massachusetts, 2010. 7
