Beágyazott információs rendszerek - Ütemezési algoritmusok

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.

tanszéki weblap - bejelentkezéssel! illetve tanszéki weblap - bejelentkezéssel!
Beadási határidő: 2006.3.24. 12:00:00

Az idő- és prioritásalapú ütemezéseket egész jól összefoglalja ez a cikk (embedded.com). (Ezt hivatkozza a Wikipédia is.)

Rate Monotonic (RM) algoritmus

Definició és feltételek

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

Független taskok dinamikus ütemezése Periodikus, független hard real-time taskok ütemezésének klasszikus algoritmusa egy processzoros rendszerben: a rate monotonic algoritmus (a leggyakoribb először) (1973-ban publikálták). Ez egy statikus task prioritásokon nyugvó dinamikus preemptív algoritmus, amely a taskokat illetően az alábbiakat tételezi fel:

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

μ =

Ezen a helyen volt linkelve a ln2.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

A statikus prioritás hozzárendelés úgy történik, hogy a legkisebb periódusú task kapja a legnagyobb prioritást. Ha a task periódusok a legkisebb periódus egészszámú többszörösei, akkor egy processzoros rendszerben elérhető a μ=1 elvi maximum.

forrás: mit.bme.hu

Worst-case válaszideje

$R_{i}=C_{i}+\sum _{k\in hp_{i}}\left\lceil {\frac {R_{i}}{T_{k}}}\right\rceil C_{k}$ Az összes olyan taskra kell szummázni, amelynek magasabb a prioritása ($hp$:higher priority). Tehát egy task worst-case válaszideje egyenlő a számítási idejével, plusz az interferencia idővel, amikor magasabb prioritású taskok futnak.

Earliest Deadline First (EDF) algoritmus

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

Definíció és feltételek

Earliest Deadline First algoritmus (EDF)(Legkorábbi határidejű először). Ez egy idővezérelt módszer. A prioritás hozzárendelés dinamikus, nincsen szükség statikus prioritásra: a legnagyobb prioritást mindig az a task kapja, amelyiknek a határideje a legkorábbi. Az algoritmus preemptív. Ismerni kell a T ismétlődési időt, a C számítási időt és a D határidőt. Az ütemező futási időben ellenőrzi a kéréseket: ez az ún. elfogadási teszt (admission test). A scheduler figyeli az idő múlását és kizárja azt a taskot, amely nem fejezi be a futását az ígért határidőn belül. Ezt alkalmazzák a Real-Time Java implementációban. Lásd: http://www.rtj.org.

Priority Ceiling Protocol (PCP)

• Ha egy task futási időben le akar foglalni egy szemfort, akkor a prioritásának szigorúan nagyobbnak kell lennie, mint az összes olyan szemafor plafonprioritása, amelyet jelenleg más taskok foglalnak (hacsak nem az adott task foglalja a legmagasabb plafonprioritású szemafort).
• Ha a fenti feltétel nem teljesül, a task blokkolódik.
• Ha egy task blokkolódik egy szemafor miatt, akkor az a task, amely a szemafort foglalja (és ezzel várakoztatja az előbbi taskot) örökli az előbbi task prioritását (amely a szemafor miatt blokkolódott).
• Egy taskot teljes futása alatt legfeljebb egyszer blokkolhat valamely, nála alacsonyabb prioritású task.
• Holtpont nem fordulhat elő.

Szerintem ez így nem jó! !(ha más is egyetért javítsa ki) A PCP-ben az örökölt prioritás az éppen az adott szemaforra várakozó processek prioritásának maximuma, és nem a plafonprioritás, ezért lehet holtpont!! (2 szemafor- az alsó lefoglalja az egyiket(A), a felső megszakítja, lefoglalja a másikat(B), majd az egyiket akarja(A), de azt a másik foglalja, ezért annak megnő a prioritása, és az folytatódik, ami le akarná foglalni a másik(B) szemafort, de ekkor holtpont van, mert azt a felső tartja lefoglalva az első szemafort meg az alsó, és mind a kettő vár)
from Priority Scheduling by Dr. S. Felix Wu - Computer Science Department - University of California, Davis

lásd még: http://en.wikipedia.org/wiki/Priority_ceiling_protocol
Ez félrevezető, mert a PCP-ről szól, de az IPCP leírása

Worst-case válaszidő

$R_{i}=B_{i}+C_{i}+\sum _{k\in hp_{i}}\left\lceil {\frac {R_{i}}{T_{k}}}\right\rceil C_{k}$ ahol $B_{i}=\max _{\forall k\in lp_{i},\forall s\in lock\,s_{k,i}}(t_{k,s})$ az $i$ task blokkolási ideje,

$lp_{i}$: lower priority $i$,

$t_{k,s}$: az az idő, ameddig $k$ task foglalja $s$ szemafort,

$lock\,s_{k,i}$: azok a $k$ task által foglalt szemaforok, melyek plafonprioritása nagyobb vagy egyenlő az $i$ task prioritásánál.

Tehát egy task worst-case válaszideje egyenlő a blokkolási idejének, a számítási idejének és az interferencia idejének összegével.

Immediate Priority Ceiling Protocol (IPCP)

• Minden tasknak van statikus (alap) prioritása (talán a deadline monotonic módszer alapján).
• Minden erőforráshoz egy statikus plafonérték tartozik, amely az erőforrást használó taskok prioritásának maximuma.
• A taskoknak van dinamikus (aktív) prioritása, amely a saját statikus prioritásuk és az általuk foglalt erőforrások plafonértékeinek maximuma.
• Következésképpen egy task csak futtatásának legelején fog blokkolódni.
• Ha a task már fut, akkor minden számára szükséges erőforrásnak szabadnak kell lennie. Ha nem lenne, akkor valamely tasknak vele egyenlő vagy nála nagyobb prioritása lenne, és a task futtatását el kellene halasztani.

from Priority Scheduling by Dr. S. Felix Wu - Computer Science Department - University of California, Davis

Megjegyzés:

Kockás lap az ütemező feladatokhoz

Kérjük, hogy az ütemezéseket - az időpontok és időtartamok pontos megadásával - grafikusan adják meg. Javasoljuk léptékezést támogató papír, pl. kockás papír használatát.

-- adamo - 2006.02.24. -- Kornai Tamas- 2006.03.18 -- toma - 2006.06.28.