Beágyazott információs rendszerek ellenőrző kérdések 2006

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.

-- JankeDavid - 2006.06.30.

Még 2012-ben aktuális a kérdések nagy része (talán az összes).

-- Tsiga - 2012.06.11.

Megj.: egyelőre egy nap alatt fogalmazott + összevágott anyag. Formázásra és kiegészítésre szorul. Esetleg több részbe lehet vágni, de remélem nyersanyagnak vagy SOS tanulási résznek jó.

1.

Milyen rendszereket nevezünk beágyazott rendszereknek?

Definíció: Beágyazott rendszernek nevezik az olyan processzoralapú, programvezérlésű elektronikus eszközt, illetve az ilyen eszközökből alkotott rendszert, amely a befogadó fizikai/kémiai/biológiai környezetét autonóm módon képes érzékelők segítségével megfigyelni és beavatkozók segítségével befolyásolni.

Példák:

• (készenléti) pacemaker,
• „libabőrös” szárnyfelület,
• „brake-by-wire”.

Eszközök:

• járművek,
• háztartási gépek,
• vagyonvédelmi rendszerek,
• automatikus gyártósorok,
• (orvosi) diagnosztikai eszközök,
• folyamat-felügyeleti rendszerek,
• szórakoztató elektronika.

2.

Mit nevezünk relativisztikus hatásnak?

Ha két csomópont egymást követő e1 és e2 eseményéről tájékoztatást adunk egy _A_ és egy _B_ kliensnek, akkor elképzelhető, hogy az üzenetek megérkezési sorrendje el fog térni az események eredeti időbeni sorrendjétől.

Mit mond ki a lehetetlenségi tétel?

Ha a kommunikáció nem 100%-ig biztos, akkor lehetetlen a 100%-os megegyezés.

Véges meghibásodási csatornáról nem lehet hibátlan kommunikációt feltételezni.

Mutassa be a két hadsereg problémáját!

Lásd bir_eloadas.pdf.

Mutassa be a bizánci generálisok problémáját!

Adott _n_ generális és van közöttük _k_ db hazudós. Mindenki elmondja mindenkinek, hogy mennyi katonája van, kivéve a hazudósokat, ők mindenkinek mást állítanak magukról.
Négy szomszédos hegyen sorban táborozik ezer, kétezer, háromezer és négyezer katona, míg köztük a völgyben táborozik 5000 ellenséges katona. A hegylakók szeretnék szövettségben megtámadni a völgybelieket, de nem mindegyikük mond igazat, mert azt hazudja, hogy több katonája van a ténylegesnél. Az adatok alapján látszik, hogy a hegyiek csak összefogással győzhetik le a völgybelieket. Mit tehet ilyenkor egy király, ha sorba kérdezve barátait, mindenki bíztatja, hogy jön a harcba, de van akinek a szavában nem bízhat...A fáma szerint a nagy Bizánc hasonló okok miatt vesztett el egy fontos csatát, mert nem jött meg a beígért segítség... Jelen esetben tehát adat érvényességgel van a baj, nem a kommunikációval. Cél, hogy a hibás órát ki tudjuk zárni a döntésekből.

Adjon algoritmust a bizánci generálisok problémájának megoldására!

Mindenki körbeküldi a saját maga által gyűjtött vektort. Feltételezzük, hogy a csatorna nem manipulálható, csak egyes értékek rosszak. Így a hamis értékek kiszűrhetők, feltéve hogy $n\geq 3k+1$.

Minimálisan hány jól működő csomópont képes kiszűrni egy bizánci hibás csomópontot?

Az előző képlet alapján 4db.

• De abból 3 a jól működő, ami kiszűri az egy hibásat. Kicsit becsapós a kérdés :-)

Mutasson be olyan feladatokat, ill. problémákat, amelyek megállapodást eredményező algoritmusokat igényelnek?

• idő szinkronizáció,
• elosztott állapot konzisztenciája,
• elosztott kölcsönös kizárás,
• elosztott tranzakciós megállapodás,
• elosztott választás,
• elosztott befejezés.

3.

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

• (a) $t_{erv}=t_{kuld}+d_{max}+2g$ ahol g az óra felbontása,
• (b) $t_{erv}=t_{kuld}+2d_{max}-d_{min}+g_{l}$ ahol $g_{l}$ a lokális óra felbontása ha az nem elhanyagolható.

+tartályos-visszacsatolásos példa (előadáson volt).

4

Hasonlítsa össze a kemény valós idejű rendszereket (Hard Real-Time: HRT) és a puha valós idejű rendszereket (Soft Real-Time: SRT)!

	HRT	SRT
válaszidő	~ms	~s
viselkedés csúcsterhelés esetén	időkorláton belül válaszol	elviseljük a lassúságot
az ütem vezérlése	mindig szinkronban a környezet állapotával	aszinkron (visszacsatolás)
biztonság	kritikus	biztonságkritikus, hibafeloldás nem fontos
adatfile-ok mérete	kicsi	nagy
redundancia típusa	erőforrás redundancia	visszagörgetés
adatintegritás	rövid idejű	hosszú idejű
hibadetektálás	autonóm	felhasználó által segített

A hibás állapot kezelésének milyen stratégiáit ismeri?

Fail-safe, fail-operational.

1. katasztrófa megakadályozás bénítással (fail-safe). Pl. vonatok jelzőlámpa rendszere: minden lámpa piros.
2. katasztrófa elhárítás extra eszközökkel (fail-operational). Pl. repülőgép esetén: muszáj valahogy leszállni, nem kapcsolhatjuk ki az egész rendszert, ezért továbbra is működésben marad a rendszer csak csökkentett üzem módban, a „luxus” erőforrásokat kikapcsoljuk (hibás részeket kikapcsoljuk).

Milyen vezérlési módokat ismer?

• Eseményvezérelt (event triggered),
• idő-vezérelt (time triggered).

Hasonlítsa össze a két módszert!

• esemény vezérelt (event triggered): aszinkron módon érkező megszakítások kiszolgálása, ill. ebből adódóan dinamikus ütemezés szükséges.
• idő vezérelt (time triggered): minden kommunikáció, ill. feldolgozás központi időzítéshez (órához) szinkronizált módon történik.

5

Mi az ütemezés célja?

A taszk végrehajtási határidő betartásának biztosítása.

Mikor nevezünk egy taszkot periodikusnak, sporadikusnak és mikor aperiodikusnak?

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

Milyen állapotai lehetnek a taszkoknak az ütemezés szempontjából?

• fut,
• futásra kész,
• blokkolt,
• interferálnak vele.

Mit értünk az alatt, hogy egy ütemezhetőségi teszt egzakt, szükséges, ill. elégséges?

Az ütemezhetőségi teszt az a teszt, amely meghatározza, hogy egy futásra kész taszk ütemezhető-e oly módon, hogy közben egyik taszk sem kési le a határidőt.

• Egzakt, ha kimutat egy létező és alkalmas ütemezést.
• Szükséges, ha a rendszer nem ütemezhető a feltételek nem teljesülése esetén.
• Elégséges, ha a rendszer ütemezhető a feltételek teljesülése esetén.

Hogyan határozzuk meg a processzor kihasználtsági tényezőt?

$\mu =\sum _{k}{\frac {C_{k}}{T_{k}}}$

6

Milyen előnyei és milyen hátrányai vannak az egyszerű, periodikus ütemezésnek?

• Egyszerű,
• rugalmatlan,
• az interruptkiszolgálás korlátozott ideig lehetséges.

Mi a prioritás alapú ütemezés lényege?

A rugalmasság, egy-egy taszknak pontosan meghatározhatjuk, a processzorhoz való hozzáférésének idejét. Viszont worst-case viselkedés nem adható meg minden esetben.

A nagyobb prioritású taszk fut le először.

Mi a Rate Monotonic algoritmus lényege?

A statikus prioritás hozzárendelés úgy történik, hogy a legkisebb periódusú taszk kapja a legnagyobb prioritást.

Statikus taszk prioritásokon nyugvó dinamikus preemptív algoritmus, amely a taszkokat illetően az alábbiakat tételezi fel:

• Az összes kemény határidővel rendelkező taszk periodikus.
• Minden taszk független egymástól: nincsen precedencia, vagy kölcsönös kizárási kényszer.
• A határidő minden taszk esetében a periódus idővel egyezik.
• Minden taszk $C_{i}$ kiszámítási ideje előre ismert és konstans.
• Az átkapcsolási idők (context switching) elhanyagolhatók.
• A kihasználási/hasznosítási tényező teljesül (n az ütemezett taszkok száma), hogy

$\mu =\sum _{k}{\frac {C_{k}}{T_{k}}}\leq n(2^{{\frac {1}{n}}-1})\rightarrow _{n\rightarrow \inf }\ln 2$

Milyen feltételek teljesülése esetén mondhatjuk, hogy ezt alkalmazva a taszkok ütemezhetőek lesznek?

Ha az ütemezéshez a szükséges és az elégséges feltételek is teljesülnek, akkor biztos hogy a rendszer ütemezhető. Ebből evidens ha már a szükséges teszt elbukik akkor, akkor biztosan nem ütemezhető.
A szükséges feltétel: $\mu =\sum {\frac {C_{i}}{T_{i}}}\leq N$ ahol $\mu$ a kihasználtségi tényező, $C_{i}$ az i-dik task végrehajtási ideje, $T_{i}$ az i-dik task periódus ideje, N pedig a rendelkezésre álló processzorok száma.

Mi a különbség statikus és dinamikus prioritás között?

A statikus ütemező az ütemezési döntéseket fordítási időben hozza meg. Egy diszpécser táblázatot generál, amely alapján a program végrehajtásra kerül. A dinamikus (vagy online) ütemező az ütemezésre vonatkozó döntéseket futás közben hozza meg.

Mi az Earliest Deadline First, ill. Least Laxity algoritmus lényege?

• EDF: Mindig az a taszk fut, amelyiknek a legkorábbi a határideje.
• LL: Mindig az a taszk fut, amelynek a legkisebb a tartalék ideje (L = D - C(hátralevő)).

Milyen feltételek teljesülése esetén mondhatjuk, hogy ezeket alkalmazva a taszkok ütemezhetőek lesznek?

• EDF:

$\mu <1$

Hogyan történik a prioritás alapú rendszerek analízise?

Deadline Monotonic Analysis: DMA

Milyen feltételezésekkel élünk a DMA alkalmazásakor?

• A taszkok halmaza rögzített és ismert a prioritás hozzárendelés.
• Minden taszk tetszőleges időpontban futásra kész állapotba kerülhet, de ismételten futásra kész csak valamely minimális idő elteltével lehetséges.
• Valahányszor egy taszk futásra kész csak egy korlátozott mértékű processzor időt kap.
• Egy taszk önkényesen nem függesztheti fel önmagát végrehajtása közben (egy tetszőleges eseményre várás végrehajtás közben nem megengedett).
• A taszk határidő nem lehet hosszabb, mint a taszk ismétlődése (periódusa), azaz a taszknak be kell fejeződnie mielőtt újra futnia kellene.
• Minden taszknak egyedi prioritása van.
• Egy adott taszkot sosem késleltethet egy alacsonyabb prioritású taszk: amint a taszk futásra-kész állapotba kerül az Operációs Rendszer átkapcsol, hogy futtassa ezt a taszkot. Végrehajtás során a taszkot sohasem késleltetjük alacsonyabb prioritású taszk végrehajtásával. Ez kizárja az interruptok tiltását és az adatcserét szemaforok segítségével.
• Az Operációs Rendszer az ütemezést és a taszk átkapcsolást nulla idő alatt hajtja végre.

7

Mit jelent az, hogy a taszkok nem függetlenek?

A taszkok közös erőforrásokat használnak, amelyek egyszerre történő használata ellen szemaforokat használnak.

Mit nevezünk prioritás inverziónak?

Akkor léphet fel, ha a taszkok szokványos szemaforokat használnak közös adatok védelmére. Egy magasabb prioritású taszk esetleg olyan szemafort igényel, amelyet már alacsonyabb prioritású foglal. Ekkor tulajdonképpen őt mindig figyelmen kívül hagyják az ütemezésből, amíg fel nem szabadul az igényelt szemafor. Tehát a szemaforra váró magas prioritású taszk legalacsonyabb prioritású lesz.

Hogyan akadályozza meg a prioritás öröklés algoritmus (Priority Inheritance Protocol: PIP) a prioritás inverziót?

Egy alacsonyabb prioritású taszk átmenetileg magasabb prioritású lesz arra az időre, amíg késlelteti a magasabb prioritású taszkot.

Hogyan jöhet létre deadlock a prioritás öröklés alkalmazása esetén?

Ha pl. egy alacsonyabb prioritású taszk olyan szemafort fog, amelyre egy magasabbnak szüksége lesz és fordítva, de a lefoglalások sorrendje fordított.

1. L lefoglalja az S1 szemafort és fut tovább,
2. H megszakítja L-t, lefoglalja az S2 szemafort, és fut tovább,
3. H-nak szüksége van S1-re, ezért L magas prioritásúvá válik,
4. L fut, de szüksége lenne S2-re...

Mi a prioritás felső-határ (Priority Ceiling Protocol: PCP) lényege?

Többszörös blokkolódást elkerülendő van egy szabály, amely nem enged kritikus szakaszba lépni, ha van olyan &#147;tilos&#148; szemafor, amely blokkolhatná a kritikus szakaszban tartózkodót.

• Minden szemaforhoz rendelődik egy prioritás felső határ, amely annak a legmagasabb prioritású taszknak a prioritása, amely tilosra állíthatja (lefoglalhatja).
• Ekkor egy taszk csak akkor léphet kritikus szakaszba, ha prioritása nagyobb, mint akármelyik más taszkok által lefoglalt szemafor felső prioritása.
• Ebből következik, hogy ha egy taszk belép egy kritikus szakaszba, akkor nem blokkolható alacsonyabb prioritású taszk által amíg a taszk be nem fejeződik.

FONTOS: a kritikus szakaszba lépésnél vizsgálódunk.

Milyen szabályt kell betartani, ha egy taszk több szemafort is kezel?

A szemaforok lefoglalási és feloldási sorrendje konzekvens legyen (+S1, +S2, -S2, -S1 és nem +S1, +S2, -S1, -S2)

Mi a pillanatnyi öröklés algoritmus (Instant Inheritance Algorithm, Immediate Priority Ceiling Protocol: IPCP, ill. Immediate Ceiling Priority) lényege?

• Amikor egy taszk lefoglal egy erőforrást, akkor az ütemező azonnal felemeli a taszk prioritását. (Ahelyett, hogy csak akkor, amikor blokkol egy magasabb prioritású taszkot.)
• Következmény: A taszk csak a végrehajtás legelején blokkolódik.

Mit nevezünk blokkolási időnek és hogyan számítjuk?

Blokkolási idő az az idő, amíg egy taszkot egy alacsonyabb prioritású taszk feltart. $B_{i}$ blokkolás idő, ha $l_{p_{i}}$ azon taszkok halmaza, amelyek prioritása kisebb, mint $i$, $t_{k,s}$ az az idő, amíg $k$ taszk tartja az $s$ szemafort és ${\mbox{lock}}s_{k,i}$ az i taszk prioritásánál nagyobb vagy egyenlő plafon prioritású szemaforok azon halmaza, amelyeket a k taszk lockolt, akkor $B_{i}=\max(t_{k,s})$, ahol a maximumot minden $k\in l_{p_{i}}$ és minden $s\in {\mbox{lock}}s_{k,i}$ szerint keressük

8

Fix prioritású rendszerben, nulla kezdőfázis esetén, milyen időtartamra kell elvégezni az ütemezhetőségi vizsgálatot?

RM esetén a worst-case az, amikor mindenki egyszerre kér procit. A vizsgálatot így csak a legritkábban kérő, a legalacsonyabb prioritású taszk válaszidejére (?) kell elvégezni.

EDF algoritmus esetén, amikor nem feltétlenül a nulla kezdőfázis eredményezi a legkedvezőtlenebb esetet, milyen időtartamra kell elvégezni az ütemezhetőségi vizsgálatot?

Hiperperiódusra, a taszkok periódusidejének legkisebb közös többszörösére.

9

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

1. szabály: Minden taszk ütemezhető kell legyen átlagos végrehajtási és érkezési idő feltételezésével.
2. szabály: Minden hard real-time taszk ütemezhető kell legyen valamennyi (szoft is) taszk esetén WCET és WCAT (Worst Case Arrival Time) feltételezésével.

Mit nevezünk tranziens túlterhelésnek?

Google nulla találat...

10

Miért célszerű szervereket alkalmazni aperiodikus szoft real-time taszkok ütemezésénél?

A szerverek a legmagasabb prioritáson futnak adott periodicitással és számítás igénnyel. Periodicitását és számítási igényét úgy választjuk, hogy a hard real-time taszkok még ütemezhető legyenek.

11

Hogyan működik a kettős prioritású ütemezés?

Három prioritási sávot alkalmazunk: magas (H), közepes (M), alacsony (L). Eleinte a hard real-time taszkok L szinten futnak, az aperiodikusak pedig az M szinten. Ahogy közeledik a (hard) határidő a hard real-time taszkok átkerülnek a H szintre, és így betarthatók a határidők, de amíg csak lehet, az aperiodikus kéréseket szinte azonnal kiszolgáljuk.

Mikor kell áttérni L szintről H szintre?

D-R időben.

12

Hogyan alkalmazható a DMA módszer a CAN buszos kommunikáció válaszidő analízisére?

A rekurzív összefüggést a várakozási időre (Q) írjuk fel. A képletben a számítási idő helyére az üzenetváltási idő kerül. A CAN buszos kommunikáció prioritásos, de nem preemptív, ezért felléphet blokkolódás, amit az alacsonyabb prioritású frame-ek okozhatnak. A vizsgált prioritási szinten a válaszidőt a várakozási idő és az üzenettovábbítási idő összege adja.

13

Hogyan vehetjük figyelembe a hibatűrés érdekében futtatott kódrészek futási idejét a taszkok válaszidő számításánál?

Egyetlen hibát feltételezve megkeressük az azonos, vagy magasabb prioritású szinten futó hibakezelő handlerek futási idő igényének maximumát, és ezt hozzáadjuk a válaszidőhöz. F számú hiba esetén a hozzáadott érték F-fel szorzódik. Ha ismerjük a hibák fellépése közötti időt (inter arrival time), akkor a hozzáadandó számítási idők szorzótényezőjét úgy határozzuk meg, hogy a válaszidő és a hibák fellépése közötti idő hányadosának felső-egészét képezzük, az így kapott számot szorozzuk a szükségessé váló extra számítási idővel, majd az így képezett szorzatok maximumát képezzük.

14

Hogyan vesszük figyelembe az operációs rendszer által okozott overhead-et?

Taszk bekapcsolási, ill. kikapcsolási idő, ütemezés időigénye: „tick scheduler”.

15

Hogyan értékeli a memória menedzsment technikákat a válaszidő kézbentarthatósága szempontjából?

• Statikus allokáció:
  • sok hibaforrás kizárva, viszont rekurzió és újrahívhatóság sem használható.
• Stack használat:
  • sok program esetében fordítási időben nem mondható meg a szükséges stack méret. Tesztelés szükséges. Ehhez adott mintával fel kell tölteni a stack területet, majd a teszt futtatás után rákeresni, hogy a program meddig használta. Ez az ún. watermark meghatározás. Ökölszabály: a stack méretét 50%-kal nagyobbra kell választani, mint a tesztelések során tapasztalt legnagyobb (worst case) igény.
• Heap használat:
  • Nagy a programozó felelőssége, zárványok alakulhatnak ki, fragmentation, nőhet a memóriafoglalás ideje, ami a válaszidőt is növeli.

Milyen memória foglalási, ill. felszabadítási technikákat ismer?

• Foglalás:
  • first fit (gyors),
  • best fit (kimerítő keresés).
• Felszabadítás:
  • A felszabadított tartomány címe a Free List elejére teendő, ezáltal a végrehajtási idő rögzített hosszúságú lesz.
  • A felszabadított tartományokat cím szerinti sorrendbe állítani - a végrehajtási idő ilyenkor a lista hosszával változik. Rendezett listákban a felszabadított blokkok gyorsabban összevonhatók - ami segít a feldarabolódás elkerülésében.

Miért kritikus beágyazott rendszerekben a memória töredezés, ill. a memória „zárvány” kialakulása?

Mert sokáig futnak a beágyazott rendszerek újraindítás nélkül, és így elpocsékoljuk a memóriát, mert ezeket később nem tudják újra felhasználni (újraindításig). Vagy kifogyhat a memóriából, ha nagyon széttöredezik, mert nem lesz egy darabban akkora, amekkorára szüksége van a HRT taszkunknak...

Milyen stratégiák tűnnek jó kompromisszumnak multitasking környezetben?

Minden taszknak saját stack-je kell legyen, heap lehet saját, vagy nem saját, függetlenül attól, hogy statikus, partíció jellegű, vagy általános allokációs módszert használtunk.

Mire kell ügyelni átvett könyvtárak esetében?

• Memóriát a könyvtári programnak kell foglalnia.
• Memóriát felszabadítani az alkalmazás tud.
• A könyvtári programhoz is rendelhetünk statikus memóriát, de ilyenkor nem lesz újrahívható, bár ez sokszor kell.
• Mindezekre a könyvtár írójának kellene gondolnia: esetleg saját könyvtári rutinok felkínálása a memória felszabadítására (ún. Pluggable memory management).

16

Milyen eszközökkel tudunk időt viszonylag pontosan mérni?

• Időmérés elektronikus számlálóval
• Kettős nóniuszos időmérés

Hogyan függ az időmérés pontossága az alkalmazott elektronikus számláló tartalmától, ill. az óragenerátor frekvencia pontosságától?

A számlálóba az újratöltéskor kerülő értékkel lehet befolyásolni a macrotick-ek pontosságát.

Hogyan mérünk kis időtartamokat?

Kettős nóniuszos időméréssel. Ekkor a mérendő idő kezdetén és végén indítunk egy-egy $T_{0}(1+\delta )$ periódusidejű, kvarcpontosságú órát, és nézzük, hogy a szabadon futó $T_{0}$ periódusidejű órával a felfutó él egybeesést. Ekkor az $N_{1}T_{0}(1+\delta )+N_{0}T_{0}=T_{x}+N_{2}T_{0}(1+\delta )$ képletből $T_{x}$ nagy pontossággal kiszámolható.

Milyen nehézségek lépnek fel akkor, ha időtartamot különböző órák által biztosított időbélyegek alapján mérünk? Mekkora lehet ilyenkor az időmérés pontossága?

Az órák egymáshoz képest csúszhatnak és előfordul, hogy az egyik macrotick korábban következik be a másiknál. Az időintervallum mérésének pontossága: $(d_{m}-2g)<d_{v}<(d_{m}+2g)$ Ahol $d_{m}$ a mért érték, és $d_{v}$ pedig az intervallum tényleges értéke (valóságos)

17

Hogyan épül fel egy fizikai óra?

Egy oszcillátorból és egy tölthető számlálóból. Az oszcillátor triggereli (microtick) a lefelé számlálást, majd 0-nál a számlálóba az egy macroticknyi microtickek száma töltődik.

Mit nevezünk mikro-, és mit makro óraütésnek?

• mikrotick: ~ az oszcillátor 1 ütése
• makrotick: ~ x db mikrotick

Mi a referencia óra, a helyes óra és a pontos óra definíciója?

• Referencia óra: értéke a nemzetközi szabvány szerinti idő, $\forall t:C_{i}(t)=t$
• Helyes óra: $C_{i}(t_{0})=t$
• Pontos óra: ${\frac {\partial C_{i}(t)}{\partial t}}=1$

Hogyan értelmezzük az óra driftet (a drift mértékét), mit nevezünk ofszetnek, együttfutásnak, ill. pontosságnak?

• Drift: ${\frac {C_{k}(t_{i+1})-C_{k}(t_{i})}{t_{i+1}-t_{i}}}$
• Offset: $|C_{j}(t_{i})-C_{i}(t_{i})|$
• Együttfutás: $\Pi (t_{i})=\max |C_{j}(t_{i})-C_{i}(t_{i})|=\max |ofszet_{i}^{jk}|$ ahol a maximum az összes órapár között vizsgálandó
• Pontosság: offset(k,referencia)

Mit nevezünk belső, és mit külső szinkronizációnak?

• belső: az együttfutás csökkentése, vagyis az órák idejének közelebb hozása,
• külső: a referenciaórához órához képesti eltérés csökkentése.

18

Milyen idő etalonokat ismer?

• Nemzetközi atomidő (TAI)
• Univerzális idő (UTC)
• Network Time Protocol (NTP)

Milyen pontosságú az UTC rádió által szolgáltatott idő?

1msec az adó oldalon, és a légköri ingadozások következtében 10msec a vevőnél.

19

Milyen órarendszereket ismer?

• Központi órarendszerek
• Központilag felügyelt órarendszerek
• Elosztott órarendszerek

Mutasson (további) példát az órák szinkron működésének fontosságára!

Pl. UNIX make program: nagy programok forrásai fel vannak osztva részekre (pl 100 file). Csak azokat kell újrafordítani, amelyekhez tartozó forrás megváltozott. Ha input.c (timestamp 2151), és input.o (timestamp 2150), akkor újra kell fordítani. De ha az editor és a compiler különböző gépen fut, akkor az időbélyegek értelmezésével baj lehet, ha az órák nincsenek szinkronban. Ha output.c (timestamp 2143), és output.o (timestamp 2144), de az editort futtató gép órája késik két időegységet, akkor baj van.

20

Hogyan működik a Cristian algoritmus?

Kliens T0-ban kér a Timer servertől, aki I interrupt kiszolgálási idő múlva megküldi a C(UTC) értéket, amit a kliens az Ő órája szerint T1-ben kap meg. Probléma1: C(UTC)<T1. Órát vissza nem léptetünk! Fokozatosan kell bevezetni, azaz átmenetileg le kell lassítani az órát, amíg el nem érjük a C(UTC+eltelt idő)-t. Probléma2: terjedési idő: ennek becslése (T1-T0)/2, vagy (T-T0-I)/2. Finomítás: több mérés: adott küszöb felettieket eldobjuk. Átlagolhatunk, vagy vehetjük a legkisebbet, hiszen akkor lehetett a legkevesebb a kommunikáció körüli nehézség.

21

Mekkora a kommunikációs igénye ezeknek az algoritmusoknak?

Minden központilag óra rendszernek (mint pl. az itt felsorolt Tempo-algoritmus, vagy bármely Master-Slave típusú algoritmus) igen nagy a kommunikációs igénye a sűrű adatcsere miatt. Ebben biztosan jobb egy sima Központi órarendszer, pl. GPS.

22

Mekkora a kommunikációs igénye ezeknek az algoritmusoknak?

a kommunikációs igény viszonylag nagy, különösen akkor, ha alattomos hibák (pl. „bizánci” hibák) esetén is a robusztusság követelmény.

23

Hogyan befolyásolja a szinkronizációs üzenet jittere az elérhető együttfutás értéket?

Bizonyítható, hogy $N$ óra esetén, ha $e$ értékű jittert (latency jittert) tételezünk fel a kommunikációban, akkor teljesen pontos órák esetén sem érhető el jobb együttfutás, mint $\Pi =e(1-{\frac {1}{N}})$

Hogyan adható meg az együttfutás elvileg legjobb értéke N óra szinkronizációja esetén?

(Gondolom az előző képlet kell ide)

24

Mit nevezünk real-time változónak, megfigyelésnek, real-time objektumnak, real-time változó képének, időbeni pontosságnak?

• RT változó: állapotváltozó; vannak statikus és időben változó, dinamikus attribútumai.
• Megfigyelés: a RT változó értékei adott időpontokban.
  • Megfigyelés = <név, megfigyelési idő, érték>
• RT objektum: Egy RT objektum az elosztott rendszer csomópontján belül egy olyan tároló, amely egy RT változót, vagy annak képét tartalmazza.
• RT változó képe: a RT változó megfeleltetése a számítógépes programban, amelynek értelmezzük az időbeni és az amplitúdó szerinti pontosságát, valamint az időbeni érvényességét. Egy RT változó képe aktuális állapot, ill. esemény megfigyelés, vagy állapot becslés.
• Időbeni pontosság: az az intervallum, amelyhez tartozóan a bekövetkező amplitúdó-hiba még elviselhető a vezérelt rendszer szempontjából

Mikor nevezünk egy periodikusan frissített real-time képet parametrikusnak/fázis érzéketlennek, és mikor fázis-érzékenynek?

• parametrikus: $d_{pontossag}>(d_{frissites}+WCET_{uzenettovabbitas})$
• fázisrzékeny: $WCET_{uzenettovabbitas}<d_{pontossag}<(d_{frissites}+WCET_{uzenettovabbitas})$

Mi az állandóság követelménye, mit nevezünk akció késletetésnek?

• Állandóság (Permanence): jelentése: megmarad/stabilizálódik/érvényessé válik állapota. Egy üzenet akkor válik állandóvá/megmaradóvá/érvényessé, amikor a vevő csomópont tudja, hogy minden, a jelen üzenet küldési ideje előtt elküldött üzenet már meg kellett érkezzen, vagy sosem fog megérkezni.
• Akció késleltetési idő: (action delay) amíg érvényessé nem válik az üzenet (ezt mindig ki kell várni).

Hogyan számítjuk az akció késleltetési időt?

• Ha van globális óra: $t_{erv}=t_{kuld}+d_{max}+2g$ ahol g az óra felbontása
• Ha nincs globális óra: $t_{erv}=t_{kuld}+2d_{max}-d_{min}+g_{l}$ ahol $g_{l}$ a lokális óra felbontása; látható, hogy itt $(d_{max}-d_{min})$ idővel kell többet várni, mert valójában az üzenet küldés ideje nem ismert

Mi a különbség az állapot-megfigyelés és az esemény-megfigyelés között?

* Állapot megfigyelések: minden megfigyelés önállóan értelmezhető értéket ad. Jellegzetesen periodikus mintavételezéssel végezzük. * Esemény megfigyelések: az esemény adott időpontban bekövetkező állapotváltozás. Mivel maga a megfigyelés is egy esemény, ezért nem lehetséges egy esemény közvetlen megfigyelése az irányított objektumban, csak annak következményeit tudjuk megfigyelni.

Mit jelent ebben a kontextusban az idempotencia?

A hibatűrés célú többszöri ismétlések nem eredményeznek többszörös üzenetet: nem mindegy, hogy érték-változást, vagy magát az értéket küldjük.

• Idempotencia: Ha ugyanaz az üzenet – tipikusan hibatűrési céllal – többször is megérkezik ugyanarra a csomópontra, akkor ezt az üzenethalmazt idempotensnek nevezzük, ha a a többszöri azonos üzenet hatása ugyanaz, mint az egyszerié.

25

Mi a „replikátum determinizmusa” követelmény tartalma?

(A replikátumnak ugyanaz a kívülről látható RAM állapota, és az outputja, legfeljebb egy „d” időbeni eltérés van közöttük. A nem-determinizmus okai lehetnek: (1) különböző bemenetek, (2) időbeni eltérések a kiszámításoknál, különböző értékek olvasása, (3) megszakításos ütemezés, (4) nem-determinisztikus nyelvi tulajdonságok (pl. SELECT az ADA-ban), stb.)

26

Miért mondjuk, hogy az időnek kettős szerepe lehet?

Mert egyrészt adat (időbélyeg), másrészt vezérlés kötődik hozzá.

Hogyan csoportosítjuk az adatokat?

• nyers adat, ami jön a hardverről
• mért adat: feldolgozott adat dimenzióval
• megegyezett adat: ellenőrzött RT kép, pl. redundáns szenzornak köszönhetően.

Mikor beszélünk szintaktikus megegyezésről?

Ha a környezetet nem vizsgáljuk, csak pl. egyszerűen csak átlagot képezünk, mint a hibatűrő átlagolás algoritmusnál, ahol a bizánci hiba elleni védekezéshez négy nyers adatot igényel.

Mikor beszélünk szemantikus megegyezésről?

Ha az egyezésről a vizsgált/mért (technológiai) folyamat modelljén keresztül győződünk meg. Pl. analitikus redundancia módszere: pl. gyorsulást gyorsulás mérővel is mérünk, de ugyanazt a gyorsulást sebességmérő két időben közeleső értékének különbségéből is megbecsüljük.

27

Mi a lényeges különbség mintavételezés (sampling) és lekérdezés (polling) között?

(Mintavételezés esetén a memória az érzékelőnél, és nem a számítógépen belül. Így megóvjuk a rendszert attól, hogy több esemény érkezzen, mint a specifikációban rögzített („alul-áteresztő szűrő” hatás). Ez a memória a számítógép befolyásolási tartományán (sphere of control) kívül helyezkedik el). Lekérdezés esetén a memória a számítógépen belül van. Hiba esetén a mintavételezés robusztusabb: a számítógép leállása és újraindulása esetén a memóriatartalom elveszhet).

Milyen veszélyekkel jár a megszakítás?

(felépítése olyan mint a lekérdezésé: a számítógép befolyásolási tartományán kívüli eszköz befolyásolja a számítógépet; veszélyes, kevésbé robusztus, mint akár a lekérdezés; tranziens hibák (pl. nagyáramú fogyasztó be-kikapcsolása következtében) váratlan processzor terhelést okozhatnak, ami veszélyeztetheti a határidő betartását).

28

Milyen követelményeket állítunk a kommunikációval szemben elosztott, valós-idejű rendszerekben?

• A protokoll okozta késleltetés/bizonytalanság: (1) az adó CNI (Communication Network Interface) -> vevő CNI között legyen kicsi. (2) ingadozása (jitter) legyen jósolható és kicsi. (3) Az eloszott real-time rendszerek kommunikációs topológiája többszereplős, nem pont-pont kapcsolat. Minden vevő CNI-jébe rövid és ismert időn belül meg kell jelenjen az üzenet.
• A komponálhatóság támogatása: (1) a csomópontok időleges leválasztása (temporal firewall). (2) A csomópont host-jában implementált szerver csak akkor tud határidőket teljesíteni, ha a kliensek teljesítik kötelezettségeiket: nem terhelik túl a szervert túlságosan sok, vagy koordinálatlan kéréssel. A kommunikációs rendszernek szabályoznia kell az áramlást és segítenie a kliensnek, hogy teljesítse időszakos kötelezettségeit.
• Flexibilitás: A real-time kommunikációs rendszernek támogatnia kell a rendszer konfiguráció változtatásokat.
• Hibadetektálás: (1) Kommunikációs hibák: a kommunikációs rendszer jósolható és szolgáltatás-biztos kell legyen. (2) Csomópont hibák detektálása. (3) Teljes körű visszaigazolás: end-to-end protocol.
• Fizikai struktúra többszereplős (multicast): busz vagy gyűrű. Ha a hibatűrés aktív redundanciával valósul meg, akkor az egyes egységek szeparáltan kell elhelyezkedniük. Pl.: steer-by-wire (elektronikus kormányzás): az egyes egységeket a gépkocsi különböző részeibe szerelik.

Hogyan történhet a kommunikáció szinkronizálása?

kétvezetékes handshake, három vezetékes handshake, stb.

Hogyan működik a PAR protokoll?

(Pozitive Acknowledgement or Retransmission)

Adott egy adó, egy vevő, egy kommunikációs közeg, egy time-out érték és egy újrapróbálás számláló.

Kliens <--> Adó <-----------> Vevő <--> Kliens
Lépések:

1. Az adó beállítja a számlálóját 0-ra. Time outot indít, üzenetet küld.
   

A) -Ha jött visszaigazolás, értesíti a klienst.
B) -Ha nincs visszaigazolás és még nem telt be a számláló: újrapróbál. Ha betelt a számláló, hibát jelez.

1. A vevőhöz érkezett üzenet, ha még nem jött ugyanez, visszaigazol és értesíti a kliensét. Ha már jött, csak visszaigazol.

Tulajdonságai:

1. Az adó kezdeményezi a kommunikációt
2. A vevő jogosult késleltetni az adőt a kétiríányú kommunikációs rendszeren keresztül
3. A kommunikáció hibáját az adó detektálja, nem a vevő.
4. A hiba javítására idő-redundanciát használnak, ami növeli a protokoll késleltetést.

Miért nem ajánlható hard real-time rendszerekben?

Az átbocsátóképesség a terhelés növekedésével erősen nemlineárisan visszaesik. Torlódást okoz a PAR újrapróbáló mechanizmusa és az ütemező algoritmusok processzor ideje.

A fizikai réteg szintjén mit értünk aszinkron és mit szinkron rendszereknek

• aszinkron: csak az üzenet elején szinkronizál
• szinkron: maga az üzenet kódolás gondoskodik az üzenet alatti szinkronizálásról

29

Mit értünk implicit forgalomszabályozáson?

Globális időalap kell. Az adó csak meghatározott időpontokban ad, nincs handshake, a hibadetektálás a vevő dolga: tudja, hogy mikor kell/kellett volna üzenetnek érkeznie. A hibatűrős aktív redundanciával valósul meg: k fizikai üzenet kópia, ha legalább egy megérkezik, addig sikeres. A csatorna egyirányú, ami többszereplős esetben előnyös.
(Explicit forgalomszabályozás, ha a vevő minden üzenetet visszaigazol, jelezve ezzel, hogy kész új üzenetet fogadni. Pl: PAR protokoll)

Mi a kommunikáció idővezérelt megközelítésének a lényege?

(Lásd az „Idővezérelt rendszerek” c. anyagot is!)

Mi a busz őrzők (Bus guardian) szerepe?

Figyelik a vezérlő busz-hozzáférési mintáit, és leállítják a vezérlő működését, ha a szabályos hozzáférési minták időzítése megsérül.

Hogyan épül fel a kommunikációs interfész (CNI)?

Ezt mondják az idővezérelt archtektúra legfontosabb részének, mert ez az egy elem hozzáférhető a hoszt felől. Kér része van: Státusz regiszterek és vezérlő regiszterek

Státusz regiszterek	Vezérlő regiszterek
Globális óra	Watchdog
SRU Idő	Timeout regiszter
MEDL	Módváltás kérés
Tagság	Ujrakonfigurálás kérés
Státusz információ	Külső idő korrekció

A státusz regisztereket a kommunikációs illesztő frissíti. Részei:

• globális rendszer idő
• SRU ablakot jelölő mező (megmutatja, melyik szereplő küldhet épp üzenetet)
• MEDL mutató (hol tartunk épp az MEDL táblában)
• csomópont tagság (minden csomópontnak 1 bit, akinél 1 az értéke, az jól működött az utolsó időrésében, akinél 0, az nem).
• Státusz regiszter - erről nem ír a doksi.

A vezérlő regisztereket a hoszt frissíti:

• Watchdog számláló (folyamatosan frissíti a hoszt, ha leáll a frissítéssel, az hibára utal)
• Timeout kérés regiszter - a beírt jövőbeli időpontban kap egy megszakítást a hoszt.
• Módváltás kérő bit
• Újrakonfigurációt kérő bit - pl átveszi valamelyik meghibásodott csomópont feladatait
• Külső idő korrekció az óra szinkronizációhoz

=Hogyan épül fel az üzenetleíró táblázat (MEDL)?

Node Time

Address

Direction

Length

Initialize bit

Mode change bit

azaz egy sorban az idő, memóriacím, irány, egy bit az inicilaizálást és egy bit a mód váltás jelzendő szerepel. A cím mező a hálózati illesztő memóriacímét tartalmazza, ahol az üzenet kezdődik. Irány: küldött vs fogadott üzenet. Van még üzenethossz, és a módváltást/inicializálást jelző 1-1 bit. Logikusan annyi sornak kéne lennie a táblázatban, ahány rés van egy klaszter ciklusban (utána újrakezdődik a küldők sorrendje a TDMA körökkel együtt). A táblázat statikus - a hoszt számítógép felöl nem hozzáférhető. Minden csomópontnak egyedi a rendszerben.

Hogyan valósul meg a szinkronizáció, ha a csomópont eseményvezérelt működésű (Non-Bocking Write: NBW protokoll)?

A CNI blokkolás nélkül írja a DPRAM tartalmát. Minden írás előtt és írás után inkrementál egy mezőt (CCF - Confurrency Control Field). Az olvasó olvasás előtt ellenőrzi a CCF tartalmát. Ha páratlan számon áll, írás van folyamatban, azonnal újrakezdi az olvasást. Ha páros számon áll, ellenőrzi olvasás végén is, ha változott szintén újrakezdi az olvasást. Mivel két írás között idő jelentősen nagyobb az irás idejénél így az újrapróbálkozások száma korlátos marad és végül kap egy konzisztens verziót az olvasó.

30

Mutassa be a programszervezés főbb alternatíváit!

(egyszerű ciklikus és tovább-fejlesztései, a megszakításokkal kiegészített ciklikus, az ütemezett függvényekkel szervezett program, a mikrokernel architektúra, ill. az operációs rendszere épített architektúra. Lásd a „Beágyazott rendszerek alapkomponensei II.: Software” c. anyagot is!)

31

Mutassa be a beágyazott real-time operációs rendszerek (BIR RTOS) főbb jellemzőit!

(Alapfogalmak, a BIR RTOS feladatai, összehasonlítás a desktop számítógépek operációs rendszereivel, taszkok állapota, a kernel működése, ütemezés, időzítési szolgáltatások, taszkok közötti kommunikáció (szemafor, queue, mailbox, pipe, events), biztonságkritikus operációs rendszerek. Lásd a „Beágyazott rendszerek alapkomponensei III.: RTOS” c. anyagot is!)

32

Mutassa be a valós idejű operációs rendszerrel együttműködő szoftver tervezésének szabályait/szempontjait!

• megszakítás-kezelő rutinok írásának szabályai
• taszkok írásának szabályai (ajánlott taszk felépítés)
• a kommunikáció egységbezárása
• a beágyazott szoftver rétegszerkezete

33

Milyen esetben konvergál a megfigyelő véges lépésben?

$\left[A-GC\right]^{N}=0$ahol $N$ az $A$ mátrix dimenziója. Ebben az esetben a konvergencia N lépéses.

Ismertesse az előadáson bemutatott robot targonca modellt

(mozgásegyenletek + állapotleírás + állapotátmenetek)!

34

Milyen idő-szinkronizációs technikákat használnak vezeték-nélküli hálózatokban?

Egyirányú, kétirányú, módosított kétirányú, referencia broadcasting.

( lásd részletesen: http://www.vs.inf.ethz.ch/publ/papers/wsn-time-book.pdf ).

---

Letölthető irodalom: The Concise Handbook of Real-Time Systems ( http://www.intel.com/education/highered/Embedded/Resources.htm )

Felhasznált irodalom: bir_eloadas.pdf

-- adamo - 2006.04.08. -- palacsint - 2006.06.30. -- Peti - 2007.04.01. -- Vajda - 2007.04.02. -- palacsint - 2008.05.28. -- habib - 2008.06.02.