Beágyazott rendszerek vizsga 20050203

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

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

A feladatlap.

%TOC{depth="2"}%

1. feladat

Három taszk ütemezését kell megoldanunk prioritásos rendszerben. A T1 taszk alacsony (L), a T2 taszk középső (M), és a T3 taszk pedig magas (H) prioritáson fut. T1 végrehajtási ideje 4 sec, T2-é 3 sec, T3-é pedig 2 sec. A T3 végrehajtására vonatkozó igény 5sec-nál gyakrabban nem merül fel. A rendszerben van globális óra. Amikor ez 100 sec-ot mutat, akkor futni kezd a T1 taszk. 101 sec-nál lefoglalja azt az erőforrást, amelyet a T3 taszk is használ. Prioritás felső-határ protokollt használunk. 102 sec-nál futásra kész állapotba kerül a T3. 104 sec-nál TI elengedi a szemafort. T3 futási ideje 2 sec.

• 1.1. Mekkora a T2 worst-case blokkolási ideje? (2 pont)
• 1.2. Mekkora a T2 worst-case válaszideje? (2 pont)

100nál kezd futni T1, 101nél lefoglalja S szemafort, aminek H a felsőhatár prioritása. Fut L statikus prioritással 102-ig, ahol is T3 futni akar, és szemafort akar foglalni. Ekkor T1 örökli a prioritását, majd H dinamikus prioritással fut. 104nél elengedi, befejezi futását, T3 kezd futni. 106-nál elengedi a szemafort (2 a futási ideje) , 106-tól 109ig fut T2 (3 a futási ideje).

T2 worst case blokkolási ideje 3, mert 101 és 104 között blokkolódik, ugyanis ekkor használja T1 a szemafort. Worst case válaszidő: mivel nem volt megadva a futási kérés ideje, ezért nem lehet pontosan megmondani.

Szerintem: A szöveg szerint T1 100 és 101 között fut => a magasabb prio T2 csak ez után lehetett futásra kész. 102-től már T3 és T1 is magas prioritáson vannak, és a szöveg (számomra) azt sejteti, hogy 104-nál tud elkezdeni futni, és 2 secig fut. Tehát 102-től 106-ig van H prio taszk. ==> T2 WC blokkolása 4 sec, WC válaszidő a blokkolás+futás = 7 sec. -- SzaMa - 2006.05.26.

Szerintem: a blokkolási idő az, amíg egy alacsonyabb statikus prioritású taszk akadályozza a futást, valamint a válaszidő az I+C+B=R azaz interferencia+blokkolás+futás, tehát az eredeti jó!!! -- Denny - 2006.06.17.

Ennek megfelelően a megoldás: 1.1 Ha T2 futásra kész a T1 futásának első másodpercében, akkor T2 megkapja a vezérlést T1-től, és nem lép fel blokkolás. Az 1. sec után T2 már nem futhat, hiszen T1 ekkor birtokolja a semafort, és H a prioritása. T1 a szemafort 3 sec után engedi el, ezalatt senki sem szakíthatja meg, a rendszerben nincs T1-en kívül olyan taszk, aminek a statikus prioritása kisebb T2-nél, tehát a T2 blokkolási ideje 3 sec. 1.2 WC válaszidő = Blokkolasi idő + Interferencia + Futasi idő Blokkolási idő = 3 (ld. 1.1 feladat) Interferencia = 2 (T3 max ennyi időre elveheti a vezérlést T2-től. Mivel C3=2, C2=3 és T3 nem jelentkezik 5 sec-nál sűrűbben, ezert max egyszer szakítja meg T3 a T2-t) Futasi idő: C2 = 3 WC válaszidő = 3 + 2 + 3 = 8 -- Sales - 2006.06.19.

Szerintem: Az a baj ezzel a feladattal, hogy túl sok minden nem specifikus. De az pl. biztos, hogy T1 prioritása csak akkor lesz H, amikor T3 használni szeretné a szemafort. Ergo T1 elkezd futni 100-nál, T3 102-nél jelzi, hogy ő is szeretne, és amennyiben nem rögtön szeretné használni az erőforrást, meg is szakíthatja T1-et és elveszi a processzort. Amennyiben azonban azt feltételezzük, hogy 102-nél, amikor T3 elkezd futni, azonnal igényli az erőforrást, ez esetben itt tényleg blokkolódik T3, és T2 is, ha egyáltalán futásra kész eddigre, mert ugye ezt sem tudjuk, hogy T2 mikor akar futni. Ha T3 előtt szeretne futni, megkapná a procit, de ezt az esetet most hanyagoljuk el, mert ugye worst case időket számolunk, tehát azt nézzük, hogy maximum mennyi ideig akadályozza őt a másik kettő. Szóval akárhogy is, a 106. secre T2 is megkezdheti a futását. 102-től blokkolódhat, és max 2 secig, mivel ennyi ideig használja T1 az erőforrást. Ha T3 miatt nem tud futni, az interferencia. Azon gondolkodtam még el, hogy vajon mit jelent a "A T3 végrehajtására vonatkozó igény 5 sec-nál gyakrabban nem merül fel" mondat. Ha ez T3 periódusideje, akkor 107-nél újra jelentkezhet, így 109-kor tud T2 folytatódni és 111-re lefutni. Javítsatok ki, ha tévedek. -- Szilvi - 2008.05.20.

2. feladat

Egy master-slave rendszeru óraszinkronizáció során a master óra 100.0 sec-os állásakor átküldjük az óra állását a slave-nek, aki ezt a saját órájának 100.1 sec-os állásakor kapja meg. Ezt követoen a slave óra 103.0 sec-os állásakor a slave megküldi az órák előzőekben regisztrált értékeinek különbségét és a saját óra aktuális állását a mastemek, aki ezt órájának 103.1 sec-os állásakor veszi.

2.1 feladat

Mekkora értéku óra-korrekciós tényezot fog a master meghatározni a slave számára ha a master-slave irányú 0.1 sec, a slave-master irányú pedig 0.3 sec idot vesz igénybe (2 pont)?

2.2

Ezzel növelni, vagy csökkenteni kell a slave értékét (1 pont)?

A jegyzetem szerint Δ = (d1-d2)/2 - (μ1-μ2)/2, ahol d az óraállások közti különbség, μ a vándorlás ideje, a számok az első és második adást jelölik. Tehát Δ=0-(-0,2)/2 = 0,1. És ezt le kell vonni a slave órájából. (T) tévedés joga fenntartva -- SzaMa - 2006.05.25.

2.3.

Végrehajtható-e ez a korrekció? Válaszát indokolja (1 pont)!

Órát nem állítunk vissza, kivéve ha biztos nem okoz galibát, de inkább lassítunk...

2.4.

Mekkora a slave óra driftjének mértéke a master órához képest, ha a t=O idopontban a master és a slave óra egyaránt helyes (1 pont)?

~0,1/100

• Nekem úgy tűnik, hogy a T=100-ban (vagyis a Tmaster=100 -ban) is tökéletesen együtt futnak, és nem tudom, honnan jött ki neked az a 0.1/100.
• Az volt órán, hogy az üzenet megérkezésének időpontja nem teljesen biztos, mert ugye ez egy perifériára érkezik, nem szinkronban a csomópont "működési ciklusával". Ezért szerintem csak látszat, hogy együtt futnak, a második üzenet időviszonyaiból sejthető, hogy a slave siet. Tehát egy a 0,1 egy becslés, ami a 100 és 103 között valamikor érvényes hibát becsli. Volt is órán, hogy sok szinkronizációból lehet jó valószínűséggel jó eredményt adni.

2.5.

Hogyan jellemezheto a master és a slave együttfutása (1 pont)?

Az eltérés maximuma = 0,1

3. feladat

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

1. A softosok érekében: átlagos végrehajtási és válaszidő mellett minden task ütemezhető legyen
2. A hard érdekében: minden HRT taszk ütemezhető legyen minden worst case végrehajtási és válaszidő mellett

4. feladat

Miért célszeru szervereket alkalmazni aperiodikus szoft real-time taszkok ütemezésénél (1 pont)? Milyen prioritás mellett, milyen periodicitással és számítási idovel futtatjuk ezeket a a szervereket (1 pont)?

A szerver folyamatnak van egy C kapacitása. Ha fut c időt, akkor ennyit csökken C. A kapacitás az idő folyamán újratöltődik. Az újratöltődésre kétfajta algoritmus is lehet:

• Defferable Server: Ts időnként visszaállítja a fix kezdőértékre C-t.
• Sporadic Server: (ha c ideig fut, akkor C=C-c) a futás vége után Ts idővel C=C+c

A szerver taszkok a sávszélességet megőrzik (hisz adott időn belül C időt futhatnak). Így tekinthetünk mindenkit (a servereket is) HRT-nek az ütemezéskor.

(T) ez nagyon homályos, remélem nem írtam hülyeséget -- SzaMa - 2006.05.25.

Erre itt van egy másik válasz:

Szerver megoldás: a HRT taszkok futnak a saját időszeletükben, a többiek a maradék időben Kettős prioritású szerver: az aperiodikusokkal kezd, de ha jön a periodikus taszk és közel van a határidő, akkor átvált rá (azaz a periodikus taszkokhoz L prioritást rendel, amit H-ra növel, ha közel van a periodikus taszk határideje)

Sajnos nekem is homályos, de beírtam, hátha a kettőből össze lehet hozni egy jót:) -- zséder - 2006.05.25.

5. feladat

Hogyan muködik a kettos prioritású ütemezés (1 pont)? Mikor kell áttérni az alacsonyabb szintrol a magasabb szintre (1 pont)?

H, M, L prioritási osztályaink vannak. A HRT taszk az utolsó pillanatig (D-R) L prioritáson van, majd hopp, felugrik H prioritásra, és mindenkit megszakíva lefut. :) A köztes időben az aperiodikus taszkok M prioritással futnak.

http://hat.sch.bme.hu/jegyzetek/szama/beagy/06.jnt

6. feladat

Mit nevezünk szinkron ill. aszinkron kódterületnek a TinyOS rendszerben (2 pont)? Milyen szabályok vonatkoznak a statikus erőforrások (pl. változók) elérésére (1 pont)?

Szinkron kód: a kódnak azon része (fv-ek, commandok, taszkok, eventek), melyek csak taszkokból érhetők el.

aszinkron kód: a kódnak azon része, mely elérhető IT kezelőből is.

Közös erőforrások védelme:
1. Elérés csak szinkron kódból.
2. Atomikus utasítások használata.
(SensorNet-2.pdf 23. oldal)

7. feladat

Milyen mezokbol áll és közelítoleg milyen méretu egy TinyOS rádió üzenet (1 pont)? Mi lehet az oka a viszonylag kicsi méretnek (1 pont)?

A jegyzetben a 18. dia egy üzenetet mutat, bár ez konkrétan a Mica rendszeré. 36 byte, amiből 29 adat, a többi címzés, hossz, időzítés, hibajavítás, és piggyback ACK.

Azért kicsi, mert kevés adatot kell küldeni általában, és energiatakarékosan akarjuk megtenni. Így az ütközésnek is kisebb az esélye, annak a megelőzésével sem foglalkozunk, így még rövidebb az üzenet.

8. feladat

Ismertesse a DSR (Dynamic Source Routing) protokoll útvonal felépítési algoritmusát (2 pont)! Hogyan gondoskodik a protokoll a rádiós hálózatokban gyakran jelentkezo aszimmetrikus csatornákról (1 pont)?

On-demand útvonalkijelölési protokoll, ami routing táblák helyett a következő megoldást alkalmazza: Az útvonalak megismerése útvonalfelderítő csomagokkal történik, az így kalkulált útvonalakat a csomópontok cachelik. A csomagok címzési része tertalmazza az összes csomópont címét, amin a csomag keresztül fog haladni, ez komoly overheadet jelenthet.

http://en.wikipedia.org/wiki/Dynamic_Source_Routing

"Semmitöbbetnemtokelmondani. Kéremkapcsojjaki"

9. feladat

Ismertesse egy általános állapotátmenet végrehajtását a Statechart modellezési nyelvben! Milyen akciók milyen sorrendben hajtódnak végre (2 pont)?

Ez alapján a kérdés másképp: hogyan történik egy komplex (különböző hierarchiaszinten elhelyezkedő állapotok közötti) állapotváltás végrehajtása?

Válasz:

A legközelebbi közös szülőig végre kell hajtani az összes kilépési akciót, utána következik az átmenethez rendelt akció, végül a szülőtől a végállapotig a belépési akciók. Figyelembe kell venni az emlékező állapotokat is.

10. feladat

Milyen speciális végrehajtó elemek (actor-ok) jellemzik a folytonos ideju számítási modellt a Ptolemy környezetben (2 pont)?

• Integrátor
• Esemény generátorok (pl. nullátmenetérzékelő)
• Jelgenerátorok (pl. nulladrendű tartó)

11. feladat

Ismertesse, beágyazott rendszerek monitorozása során hogyan valósítható meg a megfigyelni kívánt információkhoz való hozzáférés (1 pont)! Hogyan jellemezhetok ezek a technikák a beavatkozás és a rugalmasság szempontjából (1 pont)?

Szoftveres, hardveres, és kevert (hibrid). A tisztán hardveres okoz a legkisebb beavatkozást, de nehéz a triggerelés (nem minden infó olvasható ki a buszon keresztül pl). A szoftveressel absztrakt feltételeket is adhatunk, de az időzítési viszonyokba is belezavarhat, plusz hibát vihetünk be, egyéb gonosz dolgok. Ha a kettőt kombináljuk, az segíthet a bajokon: pl a kódba beleteszünk (szoftveres) triggereket, amik a buszon speciális üzenetet küldenek ki, és erre aktiválódik a monitorozó HW.

12. feladat

Adjon meg két olyan tanult technikát, ami hibaturést biztosít szoftver tervezési hibák esetén (1 pont)! Hasonlítsa össze ezeket az alábbi szempontok szerint (2 pont):

• hibadetektálás módja,
• legrosszabb esetben érvényes végrehajtási ido,
• hibakezelés módja,
• tolerálható hibák száma.

N-verziós programozás

N fejlesztő egymástól függetlenül megírja ugyanazt a kódot, ezek mindig egyszerre lefutnak, majd a kimeneteket egy szavazó kapja meg, és eldönti, hogy mi a jó válasz.

Javító blokkok

Ugyanúgy több variánsa van a kódnak, plusz van egy kód, ami a kimenetről eldönti, hogy elfogadható-e (hihető-e). Az első változat lefut. Ha nem elfogadható, akkor a második próbálkozhat.

Tulajdonság/típus	N-verziós programozás	Javító blokkok
Ellenőrzés	Szavazás, relatív	Elfogadhatóság, abszolút
Végrehajtás	Párhuzamos	Soros
Időigény	Leglassabb variáns (vagy time-out)	Hibák számától függő
Redundancia	Mindig	Csak hiba esetén
Tolerált hibák	[N/2-1]	N-1
Hibakezelés	Maszkolás	Helyreállítás

13. feladat

Adjon meg két általános stratégiát a modulokból való építkezés során végezheto inkrementális szoftver integrációs tesztelésre, és hasonlítsa össze ezeket az alábbi szempontok szerint (2 pont):

• teszt vezérlo (végrehajtó) szükségessége,
• teszt csonkok szükségessége,
• modul módosítás hatása az integrációs tesztelésre.

• Felülről lefelé
  • A main modulnál kezdjük, majd jönnek a meghívott modulok, majd az azok által meghívott modulok.
  • A meghívott modulok helyett értelemszerűen teszt csonkok kellenek, amiket meghívva azt az eredményt adják vissza, amit mi szeretnénk.
  • Ha egy modul változik, akkor az alatta lévőket újra kell tesztelni, mert ezeket a régi változattal teszteltük le.
  • Követelményorientált tesztelést tesz lehetőve.
• Alulról felfelé:
  • Pont fordítva
  • Vezérlők kellenek, amik utasításokat adnak a tesztelt modulnak (felsőbb szintű modult szimulálva)
  • Modósításnál a magasabb szintűeket kell újra tesztelni.
  • Korai integrációt biztosít

14. feladat

Rajzolja fel a javító blokkok technikájához tartozó eseményfát 2 variáns futtatása esetén! A kiindulás az elsődleges variáns indítása, a bekövetkező események pedig az egyes variánsok p1 és p2 valószínűségű, illetve az elfogadhatósági ellenőrzés pe valószínűségű hibája (2 pont)! Tételezzük fel, hogy a hibák függetlenek, valamint egy hibás variáns esetén az elfogadhatósági teszt mindig jelzi a hibát, jó variáns esetén viszont attól függően jelzi, hogy maga hibás-e. Jelölje be azokat a forgatókönyveket, ahol nem elérhető a variánsokkal megvalósított szolgáltatás, és becsülje meg ezek valószínűségét a fenti paraméterek felhasználásával! (3 pont)

Na, fél egykor a vizsga előtti napon nem rajzolgatok :) A jegyzet 8. oldalát tessék megnézni, az alapjánfog menni. BTW jópofa, hogy a kettővel korábbi kérdést megválazolják - úg látszik érdemes elolvasni a többi feladatot, ha megakadsz.

-- SzaMa - 2006.05.25.