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.)
Tartalomjegyzék
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.
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.
