„Beágyazott információs rendszerek - Ütemezési algoritmusok” változatai közötti eltérés

A VIK Wikiből
Ugrás a navigációhoz Ugrás a kereséshez
a (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)
 
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
&#956; = {{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 &#956;=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 &#956;=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]]

A lap jelenlegi, 2014. április 22., 12:33-kori változata


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.