TinyGALS és galsC
Bevezetés
A beágyazott hálózati rendszereket - mint amilyenek a vezeték nélküli szenzorhálózatok is - gyakran esemény-vezérelt programozási modellekben tervezik, így lehetővé válik reaktív, energiatakarékos rendszerek készítése. A többfeladatos beágyazott rendszerek programozásában a legnehezebb feladatot a párhuzamos folyamatok hatékony kezelése illetve a globális állapotok konzisztenciájának megőrzése jelenti. Ebben a leírásban bemutatunk egy ún. globálisan-aszinkron-lokálisan-szinkron (TinyGALS) programozási modellt, amelyet kifejezetten ilyen rendszerek készítéséhez terveztek. A modellben a szoftver komponensek modulokba szerveződnek és egy-egy modulon belül lokálisan szinkron módon kommunikálnak egymással. A rendszerben a modulok közötti kommunikáció aszinkron módon történik, ezáltal jól elkülöníthetőek a vezérlési szálak, ill. az egyes modulok feladatai jobban átláthatóak. Egy speciális, illeszkedő modellt (TinyGUYS) használunk a globális változók hatékony kezelésére. A TinyGALS modell úgy lett kitalálva, hogy a lelkét képező üzenetküldési mechanizmusok automatikusan generálhatóak a magas szintű specifikációkból. Ez azt jelenti, hogy hatékony, könnyen programozható nyelvek készíthetők hozzá, amelyekben a programozó a feladatra koncentrálhat anélkül, hogy a modell részleteiben elveszne. A cikk végén röviden bemutatjuk a TinyGALS modell egy implementációját: A galsC programozási nyelvet.
A TinyGALS programozási modell
A következőkben röviden ismertetjük a TinyGALS által használt alapfogalmakat, mint komponens, modul, rendszer, majd a modellben definiált, modulok közötti kommunikációról ejtünk szót, ennek kapcsán felvetjük az osztott állapotok hatékony kezelésének problémáját, és röviden bemutatjuk a problémát megoldó TinyGUYS modellt is. A programozási modellről [6][4] cikkekben olvashatunk részletesebben.
Komponensek
A komponensek jelentik a TinyGALS programok legkisebb építőköveit. Minden TinyGALS komponens egy rendezett hármas: C =< VC;XC; IC >, ahol a VC a saját változók halmaza; XC a külső változók halmaza; IC pedig az ezekkel a változókkal operáló metódusok halmaza. Az IC halmaz tovább bontható két diszjunkt részre: ACCEPTC tartalmazza azokat a metódusokat, amelyeket a C komponens szolgáltat más komponensek részére; USESC pedig a C komponens által használt - többnyire más komponensek által szolgáltatott - metódusokat tartalmazza. A komponensek tehát az objektum-orientált programozási nyelvek objektumaihoz hasonlítanak azzal a különbséggel, hogy a komponenseknek explicit módon kell megadniuk az általuk használt külső változókat és metódusokat. Szintaktikailag egy komponens definíció két részből áll. először a komponens interfészét deklaráljuk, majd következik az implementáció. A komponens egy impulzus frekvenciáját csökkenti a felére. A komponens interfésze két metódust szolgáltat (ACCEPTS) és egyet használ (USES). Az active egy belső változó. A komponens minden második fire() hívás hatására meghívja a fireOut()-ot ugyanazokkal a paraméterekkel, amelyekkel a fire()-t hívták. Vegyük észre, hogy komponens csak a fireOut() szignatúráját határozza meg, arról nem mond semmit, hogy mely másik komponensnek kell implementálnia azt. A CALL COMMAND kulcsszóval jelöljük, hogy a fireOut() hívása szinkron módon történik.
Modulok
A modulok egy vagy több TinyGALS komponensből állnak és a következő rendezett hatossal definiálhatjuk őket: M = < COMPONENTSM; INITM;INPORTSM;OUTPORTSM; PARAMETERSM; LINKSM >, ahol COMPONENTSM a modult alkotó komponensek halmaza; INITM a COMPONENTSM-ben szereplő komponensek metódusainak egy listája; INPORTSM és OUTPORTSM a modul bemeneti és kimeneti port-jainak halmazai; PARAMETERSM a komponensek külső változóit tartalmazó halmaz; LINKSM pedig a komponensek egymás közötti, ill. a komponensek és a modul be- és kimeneteinek kapcsolatait írja le. A kapcsolatot szinkron metódus hívások jelentik. Amint egy komponens külső metódust hív a CALL COMMAND segítségével, a vezérlés azonnal átadódik a hívott komponens megfelelő metódusára, vagy a modul megfelelő kimeneti port-jára. (Ez utóbbi jelentéséről később lesz még szó.) A következő példában egy A nevű modult definiáltunk, amely két komponenst tartalmaz, ACOMP1-et és ACOMP2-t. Az ACOMP1 komponens az init() és a fire() metódusokat szolgáltatja és a fireOut() metódust használja. Az ACOMP2 az exec()-et szolgáltatja és az output()-ot használja. A modul definíciójának végén lévő kapcsolatokat leíró rész mutatja, hogy amint input érkezik az A in portra az ACOMP1 komponens fire() metódusa kerÜl meghívásra. Hasonlóan az ACOMP1 fireOut() hívása az ACOMP2 exec() hívását jelenti, az ACOMP2 output() hívása pedig egy eseményt fog generálni az A out portra. Ezek a szinkron hívások mind azonnal kerÜlnek végrehajtásra.
A modul reprezentációja:
COMPONENT DownSample
ACCEPTS {
void init(void);
void fire(int in);
};
USES {
void fireOut(int out);
};
void init() {
_active = true;
}
void fire(int in) {
if (_active) {
CALL_COMMAND(fireOut)(in);
_active = false;
}
else {
_active = true;
}
}
A rendszer
A TinyGALS modell legfelső szintjén modulok alkotják a programot. A modell a programot rendszernek nevezi, eszerint minden rendszer a következő rendezett ötös: S = < MODULESS;GLOBALSS; V AR MAPSS;CONNECTIONSS;STARTS >, ahol MODULESS a rendszer moduljainak halmaza; GLOBALSS a globális változók halmaza; V AR MAPSS olyan leképezés, amely minden (globális változó, modul) pároshoz egy nevet rendel, vagyis megmondja, hogy a globális változót milyen paraméter-néven lehet elérni az adott modulban. A globális változók a modul szintjén tehát a modul paramétereiként jelennek meg; CONNECTIONSS a modulok port-jainak egymáshoz való kapcsolatát írja le; STARTS pedig egy egyedi input port neve a rendszerben. Ezzel a port-tal csak egyetlen modul rendelkezhet, a rendszer e port aktiválásával indítható. Habár a modulokon belüli kapcsolatok esetén csak egyetlen hívó és egyetlen hívott fél szerepelhet, a modulok közötti kapcsolatoknál szerepelhet több bemeneti és/vagy kimeneti port is.
include components {
ACOMP1;
ACOMP2;
};
init {
ACOMP1:init;
};
ports in {
A_in;
};
ports out {
A_out;
};
ACOMP1:fireOut ACOMP2:exec
ACOMP2:output A_out
A_in ACOMP1:fire
A modul A out kimeneti port-ja a B in és C in portokhoz van kötve. Mindkét utóbbi port-hoz tartozó FIFO sor mérete 10 egység. Az A out által létrehozott Összes token tehát meg lesz duplázva és egyaránt aktiválja a B in és a C in port-okat. A definíció utolsó sora jelzi, hogy a rendszer az A in port aktiválásával indítható.
Kommunikáció
A portok közötti kommunikáció FIFO sorok használatával valósul meg. Ami- kor egy komponens olyan metódust hív amely a modul kimeneti port-jára van kötve, a hívás paraméterei egy úgynevezett token-né konvertálódnak. Ezután a kimeneti port-hoz kapcsolódó minden bemeneti port FIFO sorába bemásolódik egy példány ebből a token-ből. Később a TinyGALS futtató környezet Ütemezője fogja kivenni a token-eket a FIFO sorokból, majd kicsomagolja belőlük a hívás paramétereit, végül végrehajtja az adott bemeneti port-hoz kapcsolt metódus hívását. A FIFO sorok tehát szétválasztják a végrehajtási szálakat; a kimeneti port-hoz kapcsolódó metódus hívása azonnal visszatér, így a hívó komponens folytathatja munkáját.
// Az S rendszer definíciója
include modules {
A;
B;
C;
}
A_out -> B_in 10
A_out -> C_in 10
@START A_in
A TinyGALS szemantikája nem definiálja pontosan, hogy mikor fog aktiválódni a bemeneti port, vagyis mikor hajtódik végre ténylegesen a modulok közötti aszinkron hívás. A legegyszerűbb implementáció a tokenek létrehozási sorrendjével azonos sorrendben aktiválja a bemeneti port-okat. Elképzelhetők azonban kifinomultabb megoldások is, amelyek figyelembe vesznek időzítési problémákat és az energiatakarékosság elvét is. A modulok közötti aszinkron kommunikáció lehetséges tényleges adat átvitele nélkül is. Ilyenkor egy Üres Üzenet közlekedik a modulok között, vagyis az aszinkron hívásnak nincsenek paraméterei, az csak valamilyen egyszerű jelzésre, kvázi szinkronizációra szolgál(A TinyOS, TinyGALS kÖrnyezetekben sosem beszélhetÜnk valódi szinkronizációról, hiszen valódi párhuzamosság sem létezik bennük. A TinyGALS modell Ütemezője legfelső szinten - az aktuális taszk végrehajtása után - bármelyik input port-ot kiválaszthatja aktiválásra, ezért a modellben az egyes modulokat Önálló, párhuzamosan működő egységekként fogjuk fel).
TinyGUYS
A TinyGALS programozási modell előnye, hogy az üzenetküldési mechanizmus következtében a modulok erősen szétválnak, így egymástól függetlenül fejleszthetők. Ez a mechanizmus azonban nem hatékony, ha globális változóink vannak, amelyeket gyakran módosítunk. Ilyenkor a programozónak kell gondoskodnia a rendszer állapotának konzisztenciájáról, amelyet többnyire őrváltozókkal valósítanak meg (Gondolhatunk szemaforra, de általánosabb - a kölcsönös kizárás melletti hozzáférést biztosító - nyelvi konstrukcióra is). Mivel a TinyGALS Ütemezőjének szemantikája nem köti meg, hogy milyen sorrendben választja ki az aktiválásra váró port-okat, gyakran választhat olyan modulokat, amelyek az őrváltozóra várakoznak. Ilyenkor az overhead jelentősen megnő, a rendszer hatékonysága leromlik. A TinyGUYS (Guarded Yet Synchronous) mechanizmus segítségével úgy tarthatjuk meg a konzisztenciát, hogy közben nem romlik a rendszer hatékonysága. A TinyGUYS mechanizmusban a globális változóink "őrzöttek". A modulok szinkron módon olvashatják a globális változókat késleltetés nélkül. A változók írása aszinkron módon történik abban az értelemben, hogy minden írási művelet eredménye egy pufferbe kerül. Ebből a pufferből másolja át az Ütemező az értéket a globális változóba az ún. biztonságos állapotokban. Ez tehát azt jelenti, hogy az az érték lesz a globális változó új értéke, amelyet utoljára írtak a pufferbe a globális változó értékének frissítése előtt. Biztonságos állapot például amikor egy modul befejezte taszkjainak futtatását és az Ütemezőnek újabb aktiválásra váró port-ot kell választania. Ezeknek az állapotoknak a tárgyalásával itt most nem foglalkozunk, részletes leírás található róluk [5]-ben. E cikkben található a módszer elméleti helyességének bizonyítása is. A TinyGUYS változók a modulok szintjén paraméterekre képződnek le, a paraméterek a komponensek szintjén pedig külső változók lesznek. A komponenseken belül a külső változókra - amelyek tehát a leképezések fordítása után TinyGUYS változók lesznek - speciális kulcsszavakkal hivatkozhatunk, ezek a PARAM GET ill. a PARAM PUT.
A galsC programozási nyelv
Ebben a fejezetben áttekintjük a galsC programozási nyelv [1] elemeit. Elsősorban a szintaktikus egységekre fogunk koncentrálni és megadjuk a TinyGALS modellel való kapcsolatot. A szemantikát a modell tartalmazza. A galsC és nesC programozási nyelvek mind C-szerű nyelvek, mert bár kiterjesztésnek tekinthetők, mindkettő tartalmaz megszorításokat is az eredeti C nyelvhez képest (Például a nesC függvények definíciójában a formális paraméterek megadására a C++ konvenciót követi és nem engedi meg a klasszikus C formát). Ezekkel a C-szerű nyelvi elemekkel most nem foglalkozunk, mert nem tartoznak szorosan tárgyhoz. A TinyGALS beágyazott hálózati rendszerekhez készített programozási modelljével és annak galsC implementációjával foglalkozunk (A TinyGALS programozási modell szempontjából tulajdonképpen a C-n kívül más alapnyelvet is választhattak volna. A választás oka a C fordítók által készített program hatékonysága és "gépközelisége"). Fontos még megjegyezni, hogy a galsC némileg eltér a modelltől és a TinyGUYS mechanizmushoz is a modelltől némileg eltérő implementációt ad.
TinyGUYS változók definíciója és használata:
// Rendszer definíció
include modules {
A;
B;
};
globals {
statevar;
};
statevar <=> A_param;
statevar <=> B_param;
...
// Az A modul definíciója
include components {
A1;
};
parameters {
int A_param;
};
...
// Az A1 komponens implementációja
...
void fire() {
...
int a;
a=PARAM_GET(A_param);
a++;
PARAM_PUT(A_param)(a);
...
}
Nyelvi konstrukciók
Háromféle alapkonstrukció létezik galsC-ben: komponens, aktor, és alkalmazás. A komponensek a legkisebb építőkövek és nesC nyelven írjuk őket. Interfészeket szolgáltatnak és használnak. Az interfészek speciális metódusok gyűjteményei. Az interfész szolgáltatója implementációt ad az interfészben szereplő parancsok- hoz és az implementációban használja az interfész eseményeit, míg az interfész használója az eseményekhez ad implementációt és a parancsokat használja. Egy komponens kétféle lehet: modul vagy konfiguráció. A modulok tartalmazzák a tényleges kódot, a konfigurációk pedig a rendszer komponenseit sorolják fel és azok interfészeit kapcsolják Össze. Ez utóbbit hívják kötésnek (wiring). A következő példában a TimerC konfigurációt láthatjuk, amely beágyazza a TimerM modult. Az interfész metódusok implementációját a TimerM tartalmazza.
// TimerC.nc
configuration TimerC {
provides interface Timer[uint8_t id];
provides interface StdControl;
} implementation {
components TimerM, ClockC, ...;
TimerM.Clock -> ClockC; ...
StdControl = TimerM.StdControl;
Timer = TimerM.Timer;
}
// TimerM.nc
module TimerM {
provides interface Timer[uint8_t id];
provides interface StdControl;
uses interface Clock;
...
} implementation {
// Az interfészek implementációja...
}
A galsC nyelvben aktoroknak hívják a TinyGALS modell moduljait. Az aktorokat már kizárólag galsC-ben implementáljuk. Egy aktor interfésze bemeneti és kimeneti portok, illetve paraméterek halmazából áll. A paraméterek globális változók amelyek egyaránt írhatóak és olvashatóak. Az aktor komponensek és azok kapcsolatainak listáját tartalmazza. Egy komponens interfész metódusát a következő elemekhez kapcsolhatjuk: (1) egy másik komponens interfész metódusához, (2) port-hoz, (3) paraméterhez, vagy (4) ezek kombinációjához. A kapcsolatok szemantikájáról részletesen lásd [5]. Ezenkívül minden aktor tartalmazhat egy ún. actorControl szakaszt, amely valamely komponenseinek StdControl interfészeit (Az StdControl interfész a nesC legfontosabb interfésze. Három parancsot tartalmaz, ezek az init(), a start() és a stop().) exportálja a galsC alkalmazás szintjére, hogy ott meghívhatóak legyenek a rendszer inicializálásakor. (Így lehet például a hardver komponenseket is inicializálni.) A galsC programot végül egy alkalmazás fájl írásával hozzuk létre. Ebben paraméterek, aktorok, és utóbbiak kapcsolatai szerepelnek. A kapcsolatok összeköthetnek alkalmazás-paramétereket (globális változókat) aktor paraméterekkel (aktorokra lokális változókkal), vagy aktorok kimeneti port-jait más aktorok bemeneti port-jaival (Elvileg lehetséges egy aktor kimeneti port-ját ugyanannak az aktornak egy bemeneti port-jára kötni). Utóbbi esetben megadható a port-hoz tartozó FIFO sor mérete is.
A SenseTag példa alkalmazás:
A SenseActor aktor és a SenseTag alkalmazás:
// SenseActor.gc
actor SenseActor {
port {
in trigger;
out output;
} parameter {
uint16_t count;
} implementation {
components SenseToInt, Photo;
SenseToInt.ADC -> Photo;
SenseToInt.ADCControl -> Photo;
trigger -> SenseToInt.trigger;
(SenseToInt.IntOutput.output, count) -> output;
actorControl {
SenseToInt.StdControl;
}
}
}
// SenseTag.gc
application SenseTag {
parameter {
uint16_t count = 0;
} implementation {
actor TimerActor, SenseActor, ...;
count = TimerActor.count;
count = SenseActor.count;
TimerActor.trigger =[64]=> SenseActor.trigger;
SenseActor.output => ...;
appstart {
SenseActor.trigger();
}
}
}
A galsC és a nesC kapcsolata
A nesC programozási nyelv a TinyOS operációs rendszer [2][3] programozási nyelve. Azonban a nesC által implementált programozási modellt is szokás TinyOS-nak, vagy TinyOS programozási modellnek nevezni. Ebben a modellben komponensekkel dolgozunk, amelyek kétfélék lehetnek: modulok, vagy konfigurációk. A modulok tartalmazzák a tényleges kódot, a konfigurációk pedig a komponensek egymással való kapcsolatait írják le. A kapcsolatok interfészek segítségével valósulnak meg. Egy-egy interfészben parancsokat és eseményeket (valójában parancs-kezelő és esemény-kezelő rutinokat) deklarálunk. Az interfészt szolgáltató komponens ad implementációt a parancsokhoz, és hívja az eseményeket, míg az interfészt használó komponens az eseményekhez ad implementációt, és a parancsokat hívja. Így tehát az interfészek kétirányúak. A TinyOS végrehajtási modelljében taszkok és hardvermegszakítás-kezelők szerepelnek. Mindkettőt a modulok belsejében definiálhatjuk. A taszkok indításuk sorrendjében futnak le egymás után és nem preemptálják egymást, vagyis nincs időszeletelés, így a taszkok között párhuzamossági problémák sem merülnek fel. Hardvermegszakítások megszakíthatják a taszkok futását és egy- mást is, ezért a TinyOS atomi szakaszok bevezetésével lehetővé teszi, hogy kölcsönös kizárást programozzunk ezekbe az aszinkron programrészekbe. A TinyGALS programozási modell független a TinyOS modelltől, azonban a galsC nyelv készítői fontosnak tartották, hogy a nesC komponensek felhasználhatóak legyenek a galsC programokban. Így a galsC a nesC kiterjesztésének tekinthető nyelvi szinten. Ezért a nesC és a galsC komponensei ugyanazok. A galsC nyelvi specifikációja nem mond semmit arról, hogy a komponensek hogyan épülnek fel, csak annyit köt meg, hogy azoknak metódusokat kell szolgáltatniuk és használniuk. A TinyGALS végrehajtási modellje eltér ugyan a TinyOS végrehajtási modelljétől, de ez nem okoz problémát, a TinyOS programok futnak a TinyGALS Ütemezőjével is.
Hivatkozások
[1] galsc home page. Web Page. http://galsc.sourceforge.net/
[2] Tinyos home page. Web Page. http://www.tinyos.net/
[3] Tinyos tutorial. Web Page. http://www.tinyos.net/tinyos-1.x/doc/tutorial/index.html
[4] Elaine Cheong. Design and implementation of tinygals: A programming model for event-driven embedded systems. Master's report, technical memorandum no. ucb/erl m03/14, University of California, Berkeley, CA, 94720, USA, May 23 2003. http://ptolemy.eecs.berkeley.edu/papers/03/TinyGALSreport
[5] Elaine Cheong and Jie Liu. galsc: A language for event-driven embedded systems. In Proceedings of Design, Automation and Test in Europe (DATE)
[6] Jie Liu Elaine Cheong, Judy Liebman and Feng Zhao. Tinygals: A programming model for event-driven embedded systems. In Proceedings of the 18th Annual ACM Symposium on Applied Computing (SAC'03), Melbourne, FL, Mar. 9-12 2003. http://ptolemy.eecs.berkeley.edu/papers/03/TinyGALS