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

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
  • $\mu =\lim \limits _{n\rightarrow \infty }{{\sqrt[{n}]{(}}2)-1=\ln(2)\approx 0.693147}$

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:

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.