Ugrás a tartalomhoz

earliest deadline first

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

earliest deadline first (tsz. earliest deadline firsts)

  1. (informatika) Az Earliest Deadline First (EDF) egy preemptív ütemezési algoritmus, amelyet általában valós idejű rendszerekben alkalmaznak. A célja, hogy a legközelebbi határidővel rendelkező (vagyis a legkorábban esedékes) folyamatokat ütemezze elsőként, biztosítva, hogy azok időben befejeződjenek. Ez egy dinamikus ütemezési algoritmus, amely folyamatosan újraértékeli a folyamatok állapotát a futtatás során.

Működési elv:

  1. Folyamatok határidői: Minden folyamat rendelkezik egy határidővel (deadline), amely meghatározza, hogy a folyamatnak milyen időpontig kell befejeződnie.
  2. Folyamatos újrasorolás: Mivel az EDF preemptív, az algoritmus folyamatosan újraszámolja, hogy melyik folyamatnak van a legközelebbi határideje. A legközelebbi határidővel rendelkező folyamatot választja ki, hogy futtassa.
  3. Preemptív ütemezés: Ha egy új folyamat érkezik, amelynek hamarabb van a határideje, mint a jelenleg futó folyamatnak, akkor a rendszer megszakítja az aktuálisan futó folyamatot, és az új folyamatot futtatja.
  4. Folyamatok végrehajtása: Az algoritmus biztosítja, hogy minden folyamat időben befejeződjön, amennyiben a rendszer rendelkezik elegendő erőforrással.

Előnyök:

  1. Optimalitás: Az EDF az optimális ütemezési algoritmus a valós idejű rendszerek számára, ha a folyamatok CPU időt igényelnek, és azok befejezésének határideje van. Az EDF garantálja, hogy ha a rendszer képes a folyamatok végrehajtására a rendelkezésre álló idő alatt, akkor minden folyamat teljesíteni fogja a határidőt.
  2. Egyszerűség: Az algoritmus egyszerű és könnyen implementálható, mivel csupán a határidők folyamatos ellenőrzésére és a legközelebbi határidő kiválasztására épít.
  3. Dinamizmus: Mivel a folyamatokat a futásuk alatt folyamatosan újrasorolják, az EDF rugalmasan alkalmazkodik a változó környezethez, például új folyamatok érkezésekor.

Hátrányok:

  1. Preemptív jelleg: Mivel preemptív, előfordulhat, hogy a gyakori kontextusváltások miatt megnövekszik a rendszer overheadje, különösen, ha sok folyamat van a rendszerben.
  2. Nem garantálja az energiahatékonyságot: Mivel a határidők azonnali végrehajtást igényelnek, nem mindig optimalizálja az energiafelhasználást, különösen mobil eszközök vagy beágyazott rendszerek esetében.
  3. Starvation: Bár az EDF biztosítja, hogy a legközelebbi határidővel rendelkező folyamatokat futtassuk, előfordulhat, hogy egyes folyamatok gyakran nem kerülnek sorra, ha azok hosszú futási időt igényelnek, és mindig újabb, hamarabb esedékes folyamatok jönnek.

Példa:

Tegyük fel, hogy van három folyamatunk, amelyek a következő határidőkkel és futási időkkel rendelkeznek:

Folyamat Futási idő (S) Határidő (D)
A 4 5
B 3 3
C 2 6
  1. A rendszer először a B folyamatot választja, mivel ennek van a legközelebbi határidője (3).
  2. Miután B befejeződött, a következő folyamat a A, mivel annak a következő legkorábbi határideje van (5).
  3. A C folyamat végül a legvégén kerül végrehajtásra, mivel a legnagyobb határidővel rendelkezik (6).

Sorrend: B -> A -> C

Összegzés:

Az Earliest Deadline First (EDF) egy optimális és rugalmas ütemezési algoritmus a valós idejű rendszerek számára, amely biztosítja, hogy a legközelebbi határidővel rendelkező folyamatok kerüljenek először végrehajtásra. Bár előnye az optimális teljesítmény, hátrányai közé tartozik a magas kontextusváltási overhead és a nem garantált energiahatékonyság. Az EDF ideális olyan rendszerekben, ahol a feladatok határidővel rendelkeznek, és a cél az, hogy minden folyamat befejeződjön időben, amennyiben a rendszer erőforrásai lehetővé teszik.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=earliest_deadline_first&oldid=3491328”