Beágyazott információs rendszerek - Vizsga 2008.06.18

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Beágyazott információs rendszerek vizsga, 2008. június 18.

1. Mutassa be az akciókésleltetés szükségességét (2 pont) és az akció késleltetési idő számításának módját, ha a globális idő ismert (1 pont), valamint ha a globális idő nem ismert (1 pont)!

2. Ismertesse pszeudo-kód segítségével a "maximális hiba minimalizálása" és az "intervallumok metszése" algoritmusokat! (2 pont) Ne feledkezzen meg az egyes konstansok és változók tartalmának ill. fogalmának definiálásáról! Mekkora a kommunikációs igénye ezeknek az algoritmusoknak? (1 pont)

• _Megjegyzés: inkább szövegesen írtam le, pszeudokódot lásd bir1_2005.pdf 18. oldalán._
• Mindkét algoritmus azt igényli, hogy a csomópontok a saját idejük, $C_{i}$ ismerete mellett meg tudják becsülni a saját aktuális hibájukat, $E_{i}$-t is. A hiba jelentése: az óra nem biztos, hogy helyes, azaz $C_{i}(t)=t$ nem teljesül, de az óra állása legfeljebb egy adott értékkel tér el a valódi időtől: $C_{i}(t)-E_{i}(t)\leq t\leq C_{i}(t)+E_{i}(t)$. A hiba becsléséhez felhasználja a legutóbbi szinkronizáció óta eltelt időt ($\rho _{i}$), az óra specifikációjában szereplő drift ütemet ($\delta _{i}$), és az utolsó szinkronizációnál megmaradt hibát ($\varepsilon _{i}$). Ezek alapján $E_{i}(t)=\varepsilon _{i}+(C_{i}(t)-\rho _{i})\delta _{i}$, mivel a legutóbbi egyeztetéskor maradt hibára legfeljebb az eltelt idő drift-szerese "rakódhatott rá". Ha kérés érkezik egy másik node-tól, mindkét algoritmus ugyanúgy az aktuális időbélyeggel és becsült hibával válaszol. A kérésekre kapott válaszok felhasználása különbözik:
• Maximális hiba minimalizálása: a csomópont $\tau$ időközönként egyszer mindenki mástól lekéri az időbélyegét és a hibáját. Majd ezeket sorra veszi, és megvizsgálja, hogy a saját órájával és hibájával konzisztens-e (vagyis a két [C-E; C+E] intervallumnak van-e metszete), és ha igen, akkor csökkenthető-e az aktuális hibája, ha átveszi a másikét. Ha mindkettő igen, akkor átveszi a másik órájának értékét, az új hibát pedig így számítja: $E_{i}(t)\;\Leftarrow \;E_{j}(t)+(1+\delta _{j})\mu _{j}^{i}$. Ehhez felhasználja, hogy az üzenetküldés ideje legfeljebb $\mu _{j}^{i}$ hibát jelent, és ez alatt a drift miatt $\delta _{j}\mu _{j}^{i}$ plusz bizonytalanság keletkezik az időbélyegekben. Ez sorban (pl. érkezés szerinti sorrendben) elvégzi az összes kapott idő-hiba párral, mindegyiknél újra frissítve, ha érdemes. Végül feljegyzi $\rho _{i}=C_{i}(t)$ és $\varepsilon _{i}=E_{i}(t)$ új értékeit.
• Intervallumok metszése: ugyanúgy $\tau$ időnként mindenkit lekérdez. Az összes kapott idő-hiba párból kiszámítja a következő intervallumot: $[C_{j}(t)-E_{j}(t);\;C_{j}(t)+E_{j}(t)+(1+\delta _{j})\mu _{j}^{i}]$, amihez azt is felhasználta, hogy az üzenetkésleltetés csak az "egyik irányba" okozhat hibát. Majd az összes ilyen intervallumnak képzi a metszetét (az alsó határok közül a legnagyobbat, a felsők közül a legkisebbet választja ki). Ha van metszetintervallum, annak középpontja lesz az új óraérték, és a hosszának a fele az új hiba. Ha nincs, semmit nem változtat az adatain.
• Az algoritmusok $\tau$ időnként 2n(n-1) üzenetet igényelnek, ha n csomópont van (minden csomópont-pár közt egy lekérés-válasz az egyik irányba, és egy a másik irányba, páronként 4 üzenet).

3. Egy lineáris, diszkrét idejű, dinamikus rendszer (A=diag[1, -1], C=[0.1, 0.1]) megfigyelésére alkalmas eljárást tervezünk (A: állapotátmenet mátrix, C: megfigyelési mátrix). Hogyan kell megválasztani az eljárás szabad paramétereit, ha véges beállási időt szeretnénk? (3 pont)

4. Milyen szabályokat alkalmazunk, ha aperiodikus és sporadikus, hard real-time és soft real-time taszkokat egyaránt ütemeznünk kell? (2 pont)

• Az ütemezhetőséghez két feltételt kell teljesíteniük a taszkoknak: átlagos érkezési és végrehajtási idők esetén minden legyen ütemezhető, és a hard real-time taszkok bármilyen (legrosszabb) érkezési és végrehajtási (WCAT, WCET) idő esetén is. Ilyen esetben szerver-szerű megoldást érdemes alkalmazni: minden HRT feladat külön taszkot kap, és van egy közös, alacsony prioritású taszk az összes SRT-nek. Ennek egy változata, hogy 3 prioritást használunk: a középsőn vannak a HRT taszkok, az alacsonyon pedig az SRT-k. Ha valamelyik SRT-nek közeledik a határideje, azt áttesszük ideiglenesen magas prioritásra.

5. Mi a lényeges különbség mintavételezés (sampling) és lekérdezés (polling) között? (1 pont) Milyen veszélyekkel jár a megszakítás? (1 pont)

• Sampling esetén az eszköz mindig készen áll adatot szolgáltatni, és tetszőleges időpontban lekérdezhető. Polling: az eszköztől le kell kérdezni, hogy készen áll-e, illetve külön utasítani kell az adat beolvasás megkezdésére (pl. lassú A/D konverter). Ez folyamatosan terheli a processzort, amire egy megoldás, ha az eszköz interrupttal szól, ha készen van. Ennél problémás, hogy mindig kontextusmentésre van szükség, és biztosítani kell a kölcsönös kizárást az interrupt és a taszkok közt.

6. Ismertesse röviden a TinyOS modulok felépítését! Mit definiál és mit implementál a modul? (2 pont)

• A modulok definiálják az általuk használt és szolgáltatott interfészeket. Minden használt interfészhez implementálja az alulról jövő események kezelőjét, és minden szolgáltatott interfészhez implementálja az onnan kapható parancsok értelmezőjét.

7. Ismertesse a taszk-kezelés szabályait TinyOS operációs rendszerben! (1 pont) Ismertesse az ütemező működését! (1 pont) Történik-e kontextus váltás az ütemezőben? (1 pont) Mi a fő oka a primitív taszk-megvalósításnak? (1 pont) Mikor kell mindenképpen taszkokat használnunk, és mik az ún. split-phase műveletek? (1 pont)

• TinyOS esetéban nincs taszkok között preempció és blokkoló rendszerhívások, csak hardware IT szakíthatja meg őket. A taszkok létrehozáskor egy FIFO várakozási sorba kerülnek be, onnan veszi ki a legkorábbit az ütemező, és a befejeződéséig futtatja. Inkább késleltetett függvényhívásokként működnek tehát, mint szokásos taszkként.
• Ütemezésnél, mivel mindig befejeződik az előző feladat, mielőtt a következőre sor kerülne, nincs kontextus-váltás (kiürítés). Emiatt az ütemezés gyors és egyszerű, valamint szinkronizációra sincs szükség (taszkok között - a HW eseménykezelők és taszkok közti kizárás biztosítására szükség lehet).
• Mivel senki (taszk, parancsértelmező, stb.) nem függesztheti fel magát, amíg pl. bemenetre vár, ezért az ilyen műveleteket két fázisra szét kell bontani (split-phase): az első fázisban kiadjuk a parancsot, majd a kód többi részét a végrehajtás végét jelző esemény kezelőjében írjuk meg.

8. Ismertesse a Ptolemy rendszer folytonos idejű rendszerek modellezésére használt jelfolyam gráf alapú számítási modelljét (grafikus forma is)! (1 pont) Hogyan modellezi a valóságot, hogyan történik a szimuláció végrehajtása? (1 pont)

• A modellben az actor-ok kimenetei és bemenetei is folytonos idejű jelek, és a gráf egy differenciálegyenlet-rendszerként fogható fel. Speciális végrehajtó egységek ezek megvalósításához: integrátorok, nullátmenet érzékelők, jelgenerátorok. Minden egység párhuzamosan fut, közös órával, valós időben (ellentétben pl. a szekvenciális adatfolyam modellel), és a végrehajtás determinisztikus. A szimulációnál a folytonos jeleket lépcsős, diszkrét lépésekben változó jelekkel közelíti, és numerikus módszerekkel (Runge-Kutta) oldja meg a differenciálegyenletet.

9. Ismertesse a gradiens alapú routing (GBR) működését! (1 pont) Milyen alkalmazásokban használható eredményesen? (1 pont) Hogyan lehet az algoritmust módosítani, hogy figyelembe vegye a csomópontok energiatartalékát? (1 pont)

10. Írja le, milyen vizsgálatra alkalmas az ok-következmény analízis (1 pont) és jellemezze a következők megadásával:

• Hogyan épül fel az ok-következmény analízis diagramja? (1 pont)
• Milyen számszerű eredményt szolgáltathat az analízis? (1 pont)

• A diagram a hibafa és az eseményfa analízis kombinációja. Tulajdonképpen fogljuk az eseményfát, és minden eseményt kiegészítünk egy saját hibafával, ami megadja, hogy milyen feltételkombinációk esetén következhet be. Ha ismerjük az elemi események valószínűségeit, akkor - az ÉS- és VAGY-kapcsolatokon megfelelően kombinálva a valószínűségeket - az egyes események és végkimenetelek valószínűségét is meghatározhatjuk (feltével bizonyos események függetlenségét). Így a kiváltó okokkal együtt láthatóak a kockázatos eseménysorozatok.

11. Ismertesse, hogy tranziens hardver hibák esetén a szoftver úton megvalósított hibatűrés milyen lépések végrehajtását igényli! (2 pont) Részletezze a helyreállítás lehetséges technikáit, valamint ezek legfontosabb alkalmazhatósági előfeltételét! (2 pont)

• A 4 szükséges lépés: a hiba detektálása, a hiba hatásainak felmérése, a rendszer állapotának helyreállítása, és a hiba okának (ha lehetséges) megszüntetése.
• A helyreállítás lehetséges módszerei:
  • Kompenzáció: többletinformáció alapján kompenzáljuk a hiba hatását. Ehhez szükséges valamilyen redundancia (pl. másik algoritmus, ami járulékos adatokat számít).
  • Állapot-visszaállítás: egy régebbi érvényes állapotba állítjuk vissza a rendszert. El kell legyen mentve a régebbi állapot, vagy a közben történt műveletek "visszacsinálásához" szükséges információ. A hiba típusától függetlenül elvégezhető, de szükséges, hogy minden komponens állapota menthető és visszaállítható legyen.
  • Állapot-előreállítás: valamilyen ismert értelmes állapotba hozzuk a rendszert. Akkor alkalmazható, ha előre számítottunk az adott hibára, és magától a hibától is függhet a pontos módja.

12. Az alábbi C nyelvű függvény az alábbi táblázatban felírt paraméterek (bemeneti vektorok) beállításával tesztelik. A config paraméter értéke NORMAL vagy REPAIR, a status paraméter értéke OK vagy FAULTY, a move paraméter értéke pedig IN, OUT vagy STOP lehet.

int set_control(int config, int status, int move)
{
  int control;
  if ((config==NORMAL) && (status==OK)) {
	 control=0x00;
	 switch (move) {
		case IN:
		  control=0x0f; break;
		case OUT:
		  control=0xf0; break;
	 }
	 write_log(control);
  } else {
	 control=0xff;
  }
  return(control);
}

Teszt bemenetek	config	status	move
Teszt 1	NORMAL	OK	IN
Teszt 2	NORMAL	OK	OUT
Teszt 3	NORMAL	FAULTY	IN

• Adja meg, hogy hány független út bejárásával tesztelhető a kódrészlet! (1 pont)
• Határozza meg a fenti tesztek végrehajtása után az utasításfedettség, döntési ág fedettség, és útvonal fedettségi mértékeket! (2 pont)
• Ha szükséges, akkor egészítse ki úgy a teszt sorozatot, hogy az előbbi mértékek, valamint a feltétel kombináció fedettség is 100%-osak legyenek! (2 pont)

• A csomópontok (egybefüggő, elágazást, becsatlakozást nem tartalmazó kódrészletek, illetve külön az elágazások) száma 9 (belépési pont, IF, SWITCH, kilépési pont (return), write_log, control 4-féle értékadása). Az élek száma 10, tehát a program ciklomatikus komplexitása CK=E-N+2=3. Ennyi független úttal fedhető le az egész gráf (minden él és csomópont).
• Utasításfedettség: 100%, mivel mindegyik legalább egyszer végrehajtódik. Döntési ág fedettség: mind a két elágazásban mindkét ágat választjuk legalább egyszer, tehát ez is 100%. Útvonal fedettség: 3 független utat jártunk be, és ennyi a maximális szám is, tehát ez is 100%.
• A feltétel kombináció fedettséghez ki kell egészíteni a bemeneteket, mivel az IF-nél két változó kombinációját teszteljük, ami összesen 4-féle lehetne, de ebből csak 2 volt eredetileg tesztelve. Tehát még 2 tesztre van szükség:

Teszt bemenetek	config	status	move
Teszt 4	REPAIR	OK	IN
Teszt 5	REPAIR	FAULTY	IN

-- G - 2009.06.15.