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

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 11.

1. Mire ad választ az egzakt, a szükséges és az elégséges ütemezhetőségi teszt? (2 pont) Adjon meg szükséges ütemezhetőségi tesztet periodikus taszkok esetére! (1 pont) Ha a "rate monotonic" ütemezési algoritmust használjuk, hogyan fogalmazható meg elégséges ütemezhetőségi teszt? (2 pont) Ugyanezzel az algoritmussal mikor érhető el 100%-os processzor kihasználtsági tényező? (1 pont)

• Szükséges: ha teszt szerint nem lehet, akkor biztosan nem lehet (de ha a teszt szerint lehet, az még nem biztosíték arra, hogy lehet). Elégséges: ha a teszt szerint lehet, akkor biztosan lehet (de ha a teszt szerint nem lehet, az még nem biztosíték arra, hogy nem lehet). Egzakt: egyszerre szükséges és elégséges (vagyis akkor és csak akkor ütemezhető, ha a teszt szerint az).
• Általában véve szükséges, hogy az átlagos processzor-kihasználtság ne haladja meg a processzorok számát. Periodikus taszkoknál ez Értelmezés sikertelen (formai hiba): {\displaystyle \sum_i \frac{C_i}{T_i} = \mu < P } alakba írható, ahol $C_{i}$ az i-edik taszk futási ideje egy periódusban, $T_{i}$ a taszk periódusideje, P a processzorok száma.
• Rate monotonicnál n taszk és 1 processzor esetén elégséges, ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \sum_i \frac{C_i}{T_i} = \mu < n(2^{1/n}-1) } . Ez nagy n esetén kb. ln(2) kihasználtságot garantál. Ha a legkisebb periódusidőnek az egész többszöröse a többi, akkor teljes kihasználtságot garantál.

2. Ismertessen egy master-slave óra-szinkronizációs algoritmust! (2 pont) Mekkora a kommunikációs igénye ezeknek az algoritmusoknak? (1 pont)

• Az elosztott Berkeley Unix-ban alkalmazott TEMPO algoritmus: legyen a mastertől a slave felé az üzenetküldési idő x, vissza y, és mutasson a slave órája z-vel többet a kelleténél. A master minden slave-nek küld egy lekérést a saját aktuális időbélyegével. A slave-ek kiszámolják a saját aktuális (a kérés érkezése pillanatában érvényes) idejük, és a kapott időbélyeg különbségét; ez a=x+z lesz. Ezt visszaküldik, csatolva a válasz küldésekor érvényes időbélyegüket. A master a saját, válasz megkapásakor érvényes idejének, és a slave válasz küldésekor érvényes idejének képezi a különségét; ez b=y-z lesz. A slave órájának sietése a két értékből és a kommunikációs idők különbségéből kifejezhető: z=(a-b)/2-(x-y)/2. Ha ismertek a kommunikációs idők, vagy feltehetjük, hogy közel egyenlő a két irányba, akkor z számítható, ezt a master visszaküldi a slave-nek, aki ennyivel állítja vissza az óráját. Ha z számítását p üzenetváltás átlagolt a-ja és b-je alapján végezzük, akkor a zaj hatását csökkenthetjük. Így n slave esetén n(2p+1) üzenet kell.

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

• A véges beálláshoz (k lépésben) az kell, hogy a megfigyelőt jellemző G mátrixra $(A-GC)^{k}=0$ teljesüljön. Mivel itt C négyzetes és invertálható, ezért $G=AC^{-1}$ megfelelő. A konkrét esetben G=diag[1, -1] adódik.

4. Mi a különbség a sporadikus és az aperiodikus taszkok között? (1 pont)

• A sporadikusnál van egy nemnulla időtartam; két "aktiválás" közt legalább ennyi időnek kell eltelnie. Az aperiodikusnál nincs ilyen alsó határ, tetszőleges gyakorisággal jöhetnek a kérések.

5. Mit nevezünk akció késleltetésnek? (2 pont) Adja meg az akció késleltetés értékét, ha az átlagos üzenet-továbbítási idő 1 msec, a jitter 0.4 msec! (2 pont) (Gondoljon arra is, hogy az akciókésleltetési idő eltérő attól függően, hogy a globális idő ismert vagy ismeretlen!)

• Ha két csomópont közt kétféle úton is terjedhet információ, és az egyik irányból kapott adatok feldolgozásához szükség lehet a másik irányból kapottra, akkor azt be kell várni. Pl. ha egy vészjelző érzékeli, hogy az eszköz egy paramétere hirtelen megváltozott, akkor nem kezdhet azonnal szirénázni, mert kis késleltetéssel kaphat az operátortól jelzést, hogy "én változtattam a paramétereken, nem hiba történt". Ez akkor történhet meg, ha az operátor-vészjelző úton lassabban fut végig a hatás, mint az operátor-beavatkozó-eszköz-érzékelő-vészjelző úton.
• Ha a hálózatban $d_{max}$ és $d_{min}$ a maximális és minimális üzenetkésleltetés, akkor két eset van, attól függően, van-e globális óra:
  • Ha van, és a hibajelzéssel együtt a küldés időbélyegét is megkapjuk, akkor a küldés idejéhez képest még $d_{max}$-ot kell várnunk a szirénázással, mert legfeljebb ennyi idő alatt oda kell érnie a leállítójelnek is.
  • Ha nincs, akkor worstcase esetre tervezünk: a vészjel a lehető leggyorsabban ért ide, és leállítójel a lehető leglassabban, így $d_{max}-d_{min}$-t kell várnunk a megkapáshoz képest. Viszont, ettől függetlenül akármekkora lehet a vészjel tényleges kézbesítési ideje, legrosszabb esetben $d_{max}$, ekkor a küldés után $2d_{max}-d_{min}$ idővel szólalhat meg a sziréna.
• A konkrét esetben $jitter=d_{max}-d_{min}=0.4ms$ és $d_{atlag}=(d_{max}+d_{min})/2=1ms$, így $d_{max}=1.2ms$ és $d_{min}=0.8ms$. Globális óra esetén tehát 1.2ms-t kell várni, globális óra nélkül 1.6ms-t.

6. Mit nevezünk szinkron ill. aszinkron kódterületeknek? (1 pont) Milyen szabályok vonatkoznak a közös erőforrások (változók) elérésére? (1 pont)

• Szinkron kód az, amit csak szinkron módon (taszkból) érünk el, tehát amit biztosan nem fogunk újrahívni (mivel a TinyOS-ben nincs preempció, taszkot nem "szakítunk félbe" másik taszkkal, legfeljebb interrupttal.). Aszinkron kód az, amit nem csak taszkból érünk el, hanem legalább egy IT-kezelőből is.
• A TinyOS-ben nincsenek blokkoló rendszerhívások (pl. szemaforkezelés), ezért a közös erőforrásokat vagy csak szinkron kódból érjük el (és ekkor garantált, hogy másik, ugyanazt az erőforrást használó kód nem fog félbeszakítani), vagy egy speciális nyelvi elemmel (atomic{}) utasítjuk a rendszert, hogy a kezelés közben ne szakíthasson félbe senki. Ez utóbbinál az atomikus szakaszban kerülendőek a lassú, vagy kiszámíthatatlan válaszidejű műveletek (command, event).

7. Vázolja nagy vonalakban a TinyOS közeghozzáférési megoldását (CSMA)! (2 pont) Milyen mezőkből épül fel egy adatcsomag? (2 pont) Ön szerint mi az oka/előnye a viszonylag kis csomagméretnek? (1 pont)

• CSMA: adásnál megvizsgálja, szabad-e a csatorna. Ha igen, elkezd adni, ha nem, egy véletlen időt vár, mielőtt újra próbálkozna. Megjegyzés: a diasor alapján az első próbálkozás előtt is vár véletlen ideig, de ezt nem értem, miért.
• A csomagok mezői: célcím, csoport, üzenet típusa, üzenet tartalmának hossza, maga a hasznos adat (tartalom), a hasznos adat CRC-je. (A strength, ack, time mezők csak a struct TOS_Msg-ben vannak benne, a tényleges adásnál nem kerülnek átvitelre.)
• A kis méret (hasznos teher max. 29 byte, egy csomag max. 36 byte a SecDed kódolás előtt) teszi lehetővé a CSMA használatát, illetve értelmetlenné a fejlettebb megoldásokat (pl. RTS/CTS). Ugyanis azoknál a csatornafoglalás is kb. ugyanennyi lenne (és a vezérlőüzeneteknél még azok is kénytelenek CSMA-szerűen működni).

8. Ismertesse a gradiens alapú routing (GBR) működését! (2 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)

• A GBR első fázisában a központból elárasztással terjesztenek szét a node-ok egy üzenetet. Az alapján, hogy kitől kapta meg először, mindegyik node ki tudja számítani, merre a legérdemesebb a központnak szánt üzeneteket küldeni/továbbítani, illetve hogy hány ugrásnyi távolságra van a központtól. Ez alapján továbbítják az adatküldés fázisban az üzeneteket. A kétértelmű esetek (több node-tól kapta meg a kérést közel ugyanakkor) többféle módon fel lehet oldani (pl. véletlenszerűen).
• Akkor jó, ha sok pontból kell egy pontba adatot küldeni.
• Az első fázisban a node, ha kevés az energiája, "hazudhat" is, nagyobb távolságúnak állítva be magát, így kevesebben fogják rajta keresztül küldeni az adataikat.

9. Írja le, hogy hibrid monitorozás esetén hogyan történik a felműszerezés, a triggerelés és a regisztrálás! (2 pont) Adjon választ arra a kérdésre, hogy vannak-e előnyei a hibrid monitorozásnak a szoftver illetve hardver monitorozáshoz képest! (1 pont)

• A felműszerezés a szoftveres monitorozáshoz hasonlóan trigger utasítások beszúrásával történik, amik az "érdekes" eseményeknél (pl. szemaforműveletek, I/O-műveletek, stb.) loggolást, stb. is végeznek. A triggerelés értelemszerűen ezek végrehajtásával történik, viszont a hatásukat külön hardver regisztrálja (tehát pl. a loggolásnál az utasítás nem ír ténylegesen a tárolóra, csak olyan jelek megjelenését okozza a buszon, amit a rákapcsolt hardver észrevesz).
• A tisztán szoftveres megoldáshoz képest előnye, hogy sokkal kevésbé bolygatja meg (pl. végrehajtási idők tekintetében) az eszköz működését, a tisztán hardvereshez képest meg könnyebbé válik a magas szintű műveletek figyelése.

10. Hasonlítsa össze a felülről lefelé (top-down) illetve az alulról felfelé (bottom-up) történő integrációs tesztelési stratégiát a következők szerint:

• Mely esetben és miért nem szükséges teszt végrehajtót illetve teszt csonkot implementálni? (2 pont)
• Egy modul javításának milyen hatása van a többi modul újratesztelésére? (1 pont)

• A felülről lefelé tesztelésben mindig először a "keretet" (a hívó/használó modult) teszteljük, és amikor azzal készen vagyunk, akkor folytatjuk az alatta lévőkkel. Mivel egy modult csak akkor tesztelünk, ha a felette lévők már készek és teszteltek, ezért nincs szükség teszt végrehajtóra, viszont az alacsonyabb szintű modulok helyettesítésére kellenek teszt csonkok.
• Az alulról felfelé tesztelésben először a legkisebb, mások által használt modult teszteljük, és a magasabb szintű modulokra csak akkor kerül sor, ha az általuk használtakkal már készen vagyunk. Emiatt teszt csonkokra nincs szükség, de végrehajtó környezetre igen, a modult hívó, paramétereit meghatározó magasabb szintű modul helyettesítésére.
• Egy modul változtatása azokat érinti, amiknek a tesztelése az illető modulra támaszkodott. A felülről lefelé tesztelésben az alsóbb szintű modulok teszteléséhez használtuk fel a hierarchiában felette lévőket, ezért a változtatott modul által használtakat kell újra tesztelni. Az alulról felfelé tesztelésnél a modul az alatta lévőket már használta, tehát ezek változása esetén kell újra tesztelni. Avagy fordítva: egy modul változtatása a felette lévők tesztelését teszi szükségessé.

11. Egy lakás betörésjelző berendezés egy ajtónyitó érzékelő, egy padlóba épített nyomásérzékelő valamint egy analóg szűrővel kiegészített hangérzékelő segítségével tudja detektálni, ha a lakásba betörés történik. Ezeket a komponenseket egy mikrokontrolleren futó szavazó modul alkalmazásával az N-verziós progamozási séma szerint működtetik.

• Rajzolja fel a betörésjelző hibafáját a detektálatlan betörésre, mint rendszerszintű veszélyre nézve! (3 pont) (Az egyes rendszerkomponensek hibáit tekintsük függetleneknek.)
• Adja meg az egyszeres hibapontokat! (2 pont)
• Írja le, hogy a megadott komponensekkel történű hibatűrő működéshez alkalmazható-e a javító blokkok (recovery block) séma! (1 pont)

• Mottó: Az ipafai papnak hibafája van.
• A hibafát általában többféleképp is fel lehet rajzolni. Az egyik lehetőség: felül téglalapban van a detektálatlan betörés esemény. Ennek oka VAGY a szavazómodul hibája (rombuszban, tovább nem vizsgált esemény), VAGY a hibás szavazatok többsége (téglalap, közbenső esemény). Ez utóbbi akkor következik be, ha a három érzékelőből kettő hibás. Létezik a hibafa-diagramnak olyan kiterjesztése, ahol a "3-ból 2" külön jelölhető, de ez a jegyzetben nem szerepel, ezért simán ÉS és VAGY kapcsolatokkal megvalósítva: az ajtónyitó ÉS a nyomásérzékelő hibás, VAGY az ajtónyitó és a hangérzékelő, VAGY a nyomásérzékelő ÉS a hangérzékelő. Ezek körök a diagramon (elsődleges események).
• Egyszeres hibapont az, aminek a hibája önmagában is előidézheti a bajt. Itt a szavazómodul hibája ilyen.
• A recovery blocks séma alapelve: először az elsődleges modult futtatjuk, majd ellenőrizzük az eredményt. Ha nem felel meg az előzetes elvárásoknak (pl. adott határértékeken kívül van), akkor a modul eredményét hibásnak tekintjük, és elvetjük, majd futtatjuk helyette a másik, azonos feladatot ellátó modult. Ezt több lépcsőben is lehet ismételni, amíg valamelyik eredmény jónak nem bizonyul, vagy elfogynak a pótmodulok.
• Mivel itt nincs jó módunk ellenőrizni a modul eredményét, és eleve párhuzamos, nem soros működésre lettek tervezve, ezért a séma itt nem alkalmazható.

-- G - 2009.06.15.