BeagyRendVizsga20060607

1. feladat

1. Mire ad választ az egzakt, a szükséges és az elégséges ütemezhetőségi teszt (3 pont)?
   1. Egzakt: Mutat egy ütemezést is.
   2. Ha a szükséges teszt nem teljesül, akkor nem lehet ütemezni.
   3. Ha az elégséges teszt teljesül, akkor biztosan lehet ütemezni.
2. Adjon meg szükséges ütemezhetőségi tesztet periodikus taszkok esetére (1 pont)?

• • <=Kihasználtásgi tényező processzorok száma

1. Ha a "rate monotonic" ütemezési algoritmust használjuk, hogyan fogalmazható meg elégséges ütemezhetőségi teszt (2 pont)?

• • Kihasználtsági tényező $<=n(2^{1/n}-1)$ nem bizti, de jobbat nem találtunk

1. Ugyanezzel az algoritmussal mikor érhető el 100%-os processzor kihasználtsági tényező?

• • Ha a periódusok a legkisebb periódus egész számú többszörösei.

2. feladat

• 2.1 Ismertesse pszeudo-kód segítségével az "Intervallumok metszése" algoritmust (3 pont) Ne feledkezzen meg az egyes konstansok és változók tartalmának, ill. fogalmának definiálásáról!

Legalább minden $\tau$ időközönként

do

• $\forall j\not =i$ REQUEST$[C_{j}(t),E_{j}(t)]$;
• $\forall j\not =i$ RECIEVE$[C_{j}(t),E_{j}(t)]$;
• $\forall j\not =i{\mathcal {L}}_{j}(t)\rightarrow [C_{j}(t)-E_{j}(t)]$;
• $\forall j\not =i{\mathcal {R}}_{j}(t)\rightarrow [C_{j}(t)+E_{j}(t)]+(1+\delta _{i})\mu _{j}^{i}$;
• ${\mathcal {L}}=\max \limits _{\forall j}{\mathcal {L}}_{j}(t)$
• ${\mathcal {R}}=\min \limits _{\forall j}{\mathcal {R}}_{j}(t)$
• $\alpha ={\mathcal {L}}$
• $\beta ={\mathcal {R}}$

• if ($\alpha <\beta$)
  • then
    • $\varepsilon _{i}={\frac {1}{2}}[\beta -\alpha ]$
    • $C_{i}(t)={\frac {1}{2}}[\alpha +\beta ]$
    • $\varrho _{i}={\frac {1}{2}}[\beta -\alpha ]$
  • else
    • ignore them all

endo

• 2.2 Mekkora a kommunikációs igénye ezeknek az algoritmusoknak (1 pont)?
  • 2*(n-1)*n (mert mindenki (n csomópont) küld n-1 üzenetet, majd arra jön n-1 válasz), tehát O(n²)

3. feladat

Egy lineáris, diszkrét idejű, dinamikus rendszer (A=diag[1‚-1] C=[0.1‚ O.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. feladat

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

• Minden task legyen ütemezhető az átlagos érkezési és végrehajtási idők figyelembevételével.
• Minden HRT taszk legyen ütemezhető a worstcase érkezési és worstcase végrehajtási idővel.

Megoldások:

• Szerverrel: HRT taszkok futnak az ő időszeletükben, a többi a maradékban.
• Kettős prioritással: A HRT addig van alacsony prioritáson, amíg nem közeledik a határideje, majd magas prioritásra vált és lefut.

5. feladat

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

• Mintavételezésnél egy külső hardver eszköz írja az érzékelő adatát az ő memóriájába, amely értéket a belső memóriába másolunk. (Ez a memória a számítógép befolyásolási tartományán kívül helyezkedik el).
• Polling-nál a közvetlenül a fő memóriába írjuk az érzekelő értékét. Így hiba esetén a az érték elveszhet.
• 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.

6. feladat

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

• Definiálja a használt és szolgáltatott interfészeket és implementálja a szolgáltatott kommandokat és a felhasznált eseményeket.

7. feladat

• 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)?
  • HW esemény megszakíthat Task-ot, másik Task nem.
• Mi a fő oka a primitív taszk megvalósításnak (1 pont)?
  • Nem kell kontextus váltás és szinkronizációs primitív.
• Mikor kell mindenképpen taszkokat használnunk és mik az un. splitáphase műveletek? (1 pont)
  • Közös erőforrásokat használó kódnál, mert így megoldható a kizárás. (???)
  • Split-phase: 1. fázisa kérés (command), a 2. fázisa egy válasz, eredmény (event)

8. feladat

• 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)?

9. feladat

• Ismertesse a gradiens alapú routing (GBR) működését (2 pont)!
  • 3 fázis: Kérés, gradiens számítás, adatszolgáltatás
• Milyen alkalmazásokban használható eredményesen? (1 pont)
  • Sok-egy kommunikáció (pl adatgyűjtés)
• Hogyan lehet az algoritmust módosítani, hogy figyelembe vegye a csomópontok energiatartalékát? (1 pont)
  • A kevés energiájú node megnöveli a saját gradiensét, így a kommunikáció elkerüli.

10. feladat

• Ismertesse a tranziens hardver hibák utáni helyreállítás tanult technikáit!
• Adja meg egy rövid indoklással, hogy melyik esetén szükséges leginkább a pontos hibadetektálás (2 pont)?

11. feladat

Hasonlítsa össze a funkcionális és strukturális modul tesztelési módszert a következő szempontok szerint:

• Mi a célja a tesztelésnek (1 pont)?
• Milyen információt használunk fel a tesztek tervezése során (1 pont)?
• Hogyan mérhető (mérhető-e) a tesztelés alapossága (1 pont)?

12. feladat

Egy forróvíztároló hőmérsékletét kétféle érzékelővel mérik. Az egyes érzékelők p1 illetve p2 valószínűséggel hajlamosak a meghibásodásra, ekkor az irreális +200C hőmérsékletet mutatják. Ezt vezérlőegység egy hihetőségvizsgálat lefuttatásával ellenőrzi. A p1 hibavalószínűségű érzékelő az elsődleges, a másikhoz csak ennek hibája esetén fordul a vezérlő A hihetőségvizsgálat hibás érzékelő esetén mindig jelzi a hibát, de egy belső programozói hiba miatt pe valószínűséggel hibátlan érzékelő esetén is hibát jelez.

• Rajzolja fel a hőmérsékletméréshez tartozó eseményfát! A kiindulás az elsődleges érzékelő beolvasása, a bekövetkező események pedig az egyes érzékelők illetve a hihetőségvizsgálat hibája a fenti működésnek megfelelően (2 pont).
• Jelölje be azokat a forgatókönyveket, ahol nem sikeres a hőmérsékletmérés, és becsülje meg ezek valószínűségét a fenti paraméterek felhasználásával (3 pont)!

-- WiKing - 2006.06.08. -- MatthewLakat - 2006.06.08. -- habib - 2008.06.04.