beágy zh

Országok listájaHungaryBudapesti Műszaki és Gazdaságtudományi EgyetemVillamosmérnöki és Informatikai KarMérnök informatikusBeágyazott Információs Rendszerekbeágy zh

(10)

Beágy. ZH tutorial

ELMÉLET

Periodikus i T periódusid_vel: a task i T időnként áll elő a kérésével.

Sporadikus i T (spor) periódusidővel: van egy minimális i T periódusideje, ennél jelentkezhet ritkábban, de gyakrabban nem.

Aperiodikus taskra nincs alsó korlát, bármikor előállhat a kérésével.

A sporadikus és az aperiodikus taskok között az a különbség, hogy az utóbbinál nincs alsó korlát a task aktiválás közötti időre, míg a sporadikusnál van ilyen. Mi periodikusakkal fogunk foglalkozni.

______________________________________________________________________________

Prioritás inverzió akkor léphet fel, ha a taskok szokványos szemaforokat használnak közös adatok védelmére.

Példa:

H: High priority task ­ fut, de elakad, mert S1-re vár ­ismét fut

M: Medium priority task ­ fut ­ ismét fut és lefut

L: Low priority task ­ fut, közben lock S1 ­ ismét fut, közben unlock S1

Példa: - memória foglalás/felszabadítás: a malloc( ), free( ) m_veletek bels_ szemaforokat használnak. A fenti eset ilyen memória m_veletek esetén is el_fordulhat! Ráadásul a C++ fordító automatikusan generálhat ilyen helyzetet konstsruktorok és destruktorok esetén.

- NASA Jet Propulsion Laboratory (JPL) Mars szondájával 1997.

A megoldást “prioritás öröklés” (priority inheritance) algoritmus adta. Lényege, hogy egy alacsonyabb prioritású task megörökli a magasabb prioritású task prioritását arra az időre, amíg késlelteti
______________________________________________________________________________

mintavételezés, lekérdezés
Mintavételezés és lekérdezés közötti különbség az, hogy a lekérdezéstnél a mintavétet egy memóriával rendelkező célegység végzi, így az adatgyűjtő szg. hibája esetén sem vész el a mintavét. Ha a gép elszáll, az adat benne van a memóriában, így nincs gond (a memória független a géptől).

Adja meg a referencia óra, a helyes óra és a pontos óra definícióját. (2 pont)

Referencia óra: a teljesen pontos óra. Ha a k-jelű óra teljesen pontos, akkor C_k (t) = t; "t

Helyes óra: a k-jelű óra helyes (correct) t₀-ban, ha C_k (t₀) = t₀

Sorolja fel a PAR protokoll-család négy alapelvét (2 pont)! Mekkora a worst-case kommunikációs idő PAR protokoll alkalmazásakor, ha az ismétlések száma 2, a sikeres átvitel worst-case időigénye 100 msec, a time-out pedig 200 msec értékre van beállítva? (2 pont). Mennyi a hibadetektálás késleltetése (2 pont)? Mekkora az akció késleltetési idő, ha a kommunikáció minimális ideje 20 msec (2 pont)? Először tételezze fel, hogy nincsen globális óra. Mi a helyzet, ha van globális óra (1 pont)?

Megoldás: 1. A kommunikációt az adóoldali kliens kezdeményezi.

2. A vevő jogosult késleltetni az adót a kétirányú kommunikációs rendszerek keresztül.

3. A kommunikációs hibát az adó detektálja, nem a vevő. A vevő nem kap információt arról, hogy mikor történt a hiba.

4. A hiba javítására időredundanciát használnak, amely növeli a protokoll késleltetést.

dmax: 2*sikertelen + 1*sikeres: 2*200+1*100=500 msec

hibadetektálás késleltetése: 1*timeout+2*timeout: 600 msec

akció késletetés: 2*dmax-dmin: 980 msec (nincs globális óra)

dmax: 500 msec (van globális óra)

Megjegyzés: ismétlések száma = kísérletek száma – 1.

8. Foglalja össze a Globális Helymeghatározó Rendszer (GPS) muködési

elvét és adja meg a számíás alapösszefüggéseit (4 pont)!

---------------------------------------------------------------------------------

6. Mutassa be a non-blocking write protocol (NBW) rendeltetését (2 pont)

és muködését pszeudokód megadásával (2 pont)!

FELADATOK

Hiányzik :
- ütemezés : RM,EDF,IPCP (ZH 06.04.02 B / 06.05.10/ 07.04.02 )

-„REFERENCIA BROADCASTING” (ZH 06.04.02 B / 06.05.10/ 07.04.02 )

6. Egy lineáris, diszkrét idejű, dinamikus rendszer (A=diag[1,-1], C=[1,1]) megfigyelésére alkalmas eljárást tervezünk. (A: állapotátmenet mátrix, C: megfigyelési mátrix, diag[.,.] olyan mátrix, amelynek csak a főátlóban van nullától különböző eleme). Adja meg az eljárás blokkvázlatát (2 pont)! Hogyan kell megválasztani az eljárás szabad paramétereit, ha véges beállási időt szeretnénk (3 pont)?

Megoldás:

Fel kellett rajzolni a rendszert, valamint a rendszert megfigyelő elrendezés blokkvázlatát a megfelelő egyenletek társaságában (lásd pl. előadás). Keresett az A-GC mátrix G eleme azzal, hogy (A-GC)*(A-GC)=0. Ehhez G1=0.5, ill. G2=-0.5 tartozik, ahol G1 és G2 a G vector komponensei.

--------------------------------------------------------------------------------------------------------------

Egy v(t) változó értékét megfigyeltük a t0 és a t0+Δt idöpontban. v(t0) = 5, v(t0+Δt) = 4

Adjon becslést a v(t) változó értékére a t0+5Δt időpontban!

Megoldás:

(v(t0 + Δt) - v(t)) /Δt = (4-5) /Δt

v(t0 + 5Δt) = v(t0) + (v(t0+Δt) - v(t))/Δt * 5Δt = 5 + (4-5) /Δt * 5 Δt = 0

--------------------------------------------------------------------------------------------------------------

Mit nevezünk akció késleltetési időnek, és hogyan számítjuk ha van globális óra, ha nincs globális óra? (3 pont)

Akció késleltetési idő: (action delay) amíg érvényessé nem válik az üzenet (ezt mindig ki kell

várni). Számítása:

van globális óra: t_érvényes = t_küld + d_max + 2g, ahol g az óra felbontása,

nincs globális óra: t_érvényes = t_küld + 2d_max - d_min + gl , ahol gl a lokális óra felbontása.

Látható, hogy a második esetben dmax - dmin idővel többet kell várni, mert valójában a küldés ideje nem ismert, míg az első esetben a küldés időpontja az üzenet részeként elküldhető.

--------------------------------------------------------------------------------------------------------------

6. Iteratív eljárás segítségével mutassa be az alábbi körülmények között működő 3-as task worst-case válaszidejét (5 pont)

Megoldás:

Task 3 worst-case válaszideje:

A táblázatot addig kell kitölteni, amíg R_iⁿ = R_iⁿ⁺¹ teljesül. R₃=3₃=14, tehát mindig teljesül a határidő.

(FELSŐEGÉSZ!!!)

--------------------------------------------------------------------------------------------------------------

Egy beágyazott rendszer négy csomópont közül az egyik bizánci viselkedésű („hazudós”). Jó lenne az órákat szinkronizálni. A nem „hazudós” csomópontok milyen algoritmussal tudják eldönteni, hogy melyik csomópont óra-információját kell figyelmen kívül hagyni (4 pont)? (Részletezze az algoritmust! A feladat megoldása során feltételezheti, hogy a kommunikációs csatornák hibátlanok, és mindenki mindenkivel „beszél”.)

Megoldás: 1. lépés: mindenki mindenkivel beszél. T.f.h. a csomópontokat 1,2,3,4 azonosítja. Legyen a 3-as hibás. A kapott információk: 1. csomópont: (C1,C2,x,C4), 2. csomópont: (C1,C2,y,C4), 3. csomópont: (C1,C2,C3,C4), 4. csomópont: (C1,C2,z,C4). 2. lépés: mindenki körbeküldi a vektort:

1. csomópont megkapja: 2.-tól: C1,C2,y,C4

3.-tól: a,b,c,d

4.-től: C1,C2,z,C4

2. csomópont megkapja: 1.-tól: C1,C2,x,C4

3.-tól: e,f,g,h

4.-től: C1,C2,z,C4

1. csomópont megkapja: 1.-tól: C1,C2,x,C4

2.-tól: C1,C2,y,C4

3.-től: i,j,k,l

A nem hazug csomópontok következtetése, hogy [C1,C2, ismeretlen/hibás, C4], tehát mindhárman megegyezhetnek pl. abban, hogy az óráikat C1, C2 és C4 átlagára állítják

--------------------------------------------------------------------------------------------------------------

Egy valós idejű mennyiség számítógépbeli képének pontossági intervalluma 2 msec. Azt szeretnénk, hogy a felhasználás helyén erről a mennyiségről mindig legyen kellően pontos képünk. Milyen gyakran kell frissíteni ezt a képet, ha az információ továbbítás a felhasználás helyére a legkedvezőtlenebb esetben 1.8 msec időt vesz igénybe (2 pont)? Mikor fázis-érzékeny egy periodikusan frissített valós idejű kép (1 pont)?

Megoldás: (RAJZ!) A frissítés gyakorisága < 0.2 msec kell legyen. A fázis-érzékeny RT kép jellemzője: (WCETüzenettovábbítás

--------------------------------------------------------------------------------------------------------------

Egy komplex technológiai folyamat állapotváltozóit 480 érzékelovel Folyamatosan mérjük. A jeleket önállóan kommunikáló mikroprocesszoros egységek fogadják és dolgozzák fel. 12 ilyen egység van, mindegyik 34 érzékelot szolgál ki. Ha a mért jelek átlépnek egy határértéket, akkor a

diszpécserszámítógépet 100 msec-on belül értesíeni kell. Az ilyenkor küldendo üzenet minden állapotváltozó esetében 1 byte hosszúságú, a kommunikációs overhead 42 bit. A kommunikációs csatorna sávszélessége 100 kbit/s. Vizsgálja m, hogy eseményvezérelt muködési módot választva

hány állapotváltozó határérték-túllépését tudja a rendszer idoben jelezni a diszpécserközpontnak (3 pont)! Vizsgálja meg, hogy idovezérelt muködési módot választva milyen mértéku terhelést jelent a kommunikációs csatornán az az eset, amikor valamennyi állapotváltozó átlépi a

határértéket (3 pont)! (lehet elírtam a számokat)

Megoldás:

Eseményvezérelt esetben egy határérték-túllépés 8 bit adat és 42 bit kommunikációs overhead azaz 50 bit továbbításából áll. Itt nincs csomópontonkénti optimalizáció, tehát 100000/50 = 200/0.1s, azaz 200 üzenet érhet be határidő alatt. Ez kisebb mint 480, tehát nem jó az eseményvezérelt módszer erre a rendszerre. Az idővezérelt esetnél az üzeneteket "csokorba" lehet fogni, tehát 40*8+42 bit = 362 bit. Ebből 27.6 fér rá a csatornára 0.1 s alatt és mivel 12 csomópont van, így a csatorna átlagos terheltsége: 43%

--------------------------------------------------------------------------------------------------------------

Egy master-slave rendszerű óraszinkronizáció során a master óra 200 sec-os állásakor átküldjük az óra állását a slave-nek, aki ezt a saját órájának 202 sec-os állásakor kapja meg. Ezt követően a slave óra 203 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 masternek, aki ezt órájának 204 sec-os állásakor veszi. Egyéb információnk nincsen. Mekkora értékű óra-korrekciós tényezőt fog a master meghatározni a slave számára (2 pont)? Ezzel növelni, vagy csökkenteni kell a slave értékét (1 pont)? Hogyan módosul a fenti korrekciós érték, ha többlet információként ismerjük, hogy a master-slave irányú kommunikáció 200 msec, a slave-master irányú kommunikáció pedig 100 msec időt vesz igénybe (2 pont)? Mekkora a slave óra driftje a master órához képest, ha a t=0 időpontban a master és a slave óra egyaránt helyes (2 pont)? Hogyan jellemezhető a master és a slave együttfutása (1 pont)?

Megoldás: Az előadáson megismert algoritmus szerint a szükséges korrekció: [(202-200)-(204-203)]/2=0.5 sec, ezzel kell csökkenteni a slave értékét (alkalmas stratégiával). A kommunikációs idők ismeretében a korrekció – (200-100)/2 msec értékkel módosul, azaz 0.45 sec lesz. (Figyeljük meg, hogy a kommunikációs idők ismeretében az órák granularitása mennyire nem jó!) A drift, ill. A drift mértéke az eltelt (átlagos) idő, és a korrekció ismeretében becsülhető legjobban (1+) 0.5/202, ill. (1+) 0.45/202. Az együttfutás mértéke a szinkronizáció előtti eltéréssel,tehát 0.5, ill. 0.45 sec-mal jellemezhető.

Hozzászólások