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

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

[math]R_i=C_i+\sum_{k\in hp_i} \left\lceil\frac{R_i} {T_k}\right\rceil C_k[/math] Az összes olyan taskra kell szummázni, amelynek magasabb a prioritása ([math]hp[/math]: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ő

[math]R_i=B_i+C_i+\sum_{k\in hp_i} \left\lceil\frac{R_i} {T_k}\right\rceil C_k[/math] ahol [math]B_i=\max_{\forall k\in lp_i, \forall s\in lock\, s_{k,i}}(t_{k,s})[/math] az [math]i[/math] task blokkolási ideje,

[math]lp_i[/math]: lower priority [math]i[/math],

[math]t_{k,s}[/math]: az az idő, ameddig [math]k[/math] task foglalja [math]s[/math] szemafort,

[math]lock\, s_{k,i}[/math]: azok a [math]k[/math] task által foglalt szemaforok, melyek plafonprioritása nagyobb vagy egyenlő az [math]i[/math] 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.