Beágyazott információs rendszerek - Ütemezési algoritmusok forrásának megtekintése

{{GlobalTemplate|Infoalap|BeagyRendHaziUtem}}


__TOC__

[http://portal.mit.bme.hu/?l=oktatas/hf/vimm3244&p=homework&h=1 tanszéki weblap - bejelentkezéssel!]
illetve
[http://portal.mit.bme.hu/?l=oktatas/hf/vimm3244&p=homework&h=3 tanszéki weblap - bejelentkezéssel!]
<br> Beadási határidő: '''2006.3.24. 12:00:00'''

Az idő- és prioritásalapú ütemezéseket egész jól összefoglalja [http://www.embedded.com/2000/0006/0006feat1.htm  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
	 &#956; = {{InLineImageLink|Infoalap|BeagyRendHaziUtem|ln2.png}}

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 &#956;=1 elvi maximum.

[http://portal.mit.bme.hu/oktatas/targyak/vimm3244/jegyzet/2005/bir1_2005.pdf 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ő.

<span style="color:red"> 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)
</span> <br>
from [http://www.cs.ucdavis.edu/~wu/ecs150/ecs150_W2006_L003.ppt Priority Scheduling] by
[http://www.cs.ucdavis.edu/~wu/ Dr. S. Felix Wu] -  Computer Science Department -  University of California, Davis

lásd még: http://en.wikipedia.org/wiki/Priority_ceiling_protocol
<br><span style="color:red"> Ez félrevezető, mert a PCP-ről szól, de az IPCP leírása</span> 
===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 [http://www.cs.ucdavis.edu/~wu/ecs150/ecs150_W2006_L003.ppt Priority Scheduling] by
[http://www.cs.ucdavis.edu/~wu/ Dr. S. Felix Wu] -  Computer Science Department -  University of California, Davis



==Megjegyzés:==

[http://info2.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=8746 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|adamo]] - 2006.02.24.
-- [[KornaiTamas|Kornai Tamas]]- 2006.03.18 
-- [[RebeliSzaboTamas|toma]] - 2006.06.28.


[[Category:Infoalap]]