Kiskoza, 2014. április 22., 10:33-n

2014-04-22T10:33:53Z

← Régebbi változat		A lap 2014. április 22., 12:33-kori változata
1. sor:		1. sor:
	~~{{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.)		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.)
24. sor:		16. sor:
	* Az átkapcsolási idők (context switching) elhanyagolhatók.		* 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		* A kihasználási/hasznosítási tényező teljesül (n az ütemezett taskok száma), hogy
	~~μ~~ = {{~~InLineImageLink\|Infoalap\|BeagyRendHaziUtem\|ln2~~.~~png}~~}		** <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.		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.
84. sor:		76. sor:

	==Megjegyzés:==		==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.		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~~]]		[[Kategória:Mérnök informatikus]]
			[[Kategória:Autonóm intelligens rendszerek szakirány]]

Kiskoza: Kiskoza átnevezte a(z) Ütemezési algoritmusok lapot Beágyazott információs rendszerek - Ütemezési algoritmusok lapra átirányítás nélkül

2014-04-22T10:24:05Z

Kiskoza átnevezte a(z) Ütemezési algoritmusok lapot Beágyazott információs rendszerek - Ütemezési algoritmusok lapra átirányítás nélkül

← Régebbi változat		A lap 2014. április 22., 12:24-kori változata
(Nincs különbség)

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|BeagyRendHaziUtem}} TOC [http://portal.mit.bme.hu/?l=oktatas/hf/vimm3244&p=homework&h=1 tanszéki weblap - bejelentkezéssel!] illetve …”

2012-10-21T19:53:27Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|BeagyRendHaziUtem}} __TOC__ [http://portal.mit.bme.hu/?l=oktatas/hf/vimm3244&p=homework&h=1 tanszéki weblap - bejelentkezéssel!] illetve …”

Új lap

{{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!]
 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
μ = {{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 μ=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ő.

 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 [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
 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 [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]]

Beágyazott információs rendszerek - Ütemezési algoritmusok - Laptörténet

Kiskoza, 2014. április 22., 10:33-n

Kiskoza: Kiskoza átnevezte a(z) Ütemezési algoritmusok lapot Beágyazott információs rendszerek - Ütemezési algoritmusok lapra átirányítás nélkül

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|BeagyRendHaziUtem}} __TOC__ [http://portal.mit.bme.hu/?l=oktatas/hf/vimm3244&p=homework&h=1 tanszéki weblap - bejelentkezéssel!] illetve …”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|BeagyRendHaziUtem}} TOC [http://portal.mit.bme.hu/?l=oktatas/hf/vimm3244&p=homework&h=1 tanszéki weblap - bejelentkezéssel!] illetve …”