Tervezési algoritmus a legközelebbi befejezési dátumhoz

A legközelebbi határidő ( EDF ) ütemezési algoritmusa egy dinamikus ütemezési algoritmus. Valós idejű operációs rendszerekben használják a folyamatok prioritási sorba helyezésére . Ütemezési esemény bekövetkezésekor (egy feladat befejeződött, új feladat jelent meg stb.), a sorban megkeresi a határidőhöz legközelebb eső folyamatot. Ennek a folyamatnak a következő futtatása lesz ütemezve.

A legközelebbi befejezési ütemezés optimális az egyprocesszoros preemptív rendszerek számára a következő értelemben: ha garantálható, hogy a független feladatok halmaza, amelyek mindegyikét jellemez egy érkezési idő, egy teljesítési feltétel és egy befejezési határidő, a határidőig garantálható. befejezéséhez, akkor az EDF algoritmus is képes lesz erre.

A periódusaikkal megegyező határidővel rendelkező időszakos folyamatok ütemezésekor a befejezéshez legközelebb eső ütemezési algoritmus a teljes terhelést használja. Ezért ennek az algoritmusnak az ütemezési tesztje a következő lesz [1] :

ahol  a folyamatok legrosszabb végrehajtási ideje, és  az érkezési dátumok közötti megfelelő időszak (feltételezve, hogy megegyezik a megfelelő határidőkkel).

Vagyis a legközelebbi befejezési dátumig történő hozzárendelés biztosítja az összes határidő betartását, mindaddig, amíg a teljes CPU-használat nem haladja meg a 100%-ot. A rögzített prioritások használatához képest a legközelebbi befejezési dátumra történő ütemezés biztosítja, hogy minden határidőt betartsanak, ha nagyobb a munkaterhelés.

Ha azonban a rendszer túlterhelt, akkor a folyamatok halmaza, amelyeknél a határidő kimarad, nagyon kiszámíthatatlan lesz (ez a túlterhelés pontos időzítésétől és idejétől függ.) Ez a valós idejű rendszertervezők számára észrevehető hátrány. . Ezen túlmenően az algoritmus nehezen implementálható hardverben, és nehézségekbe ütközik a határidők különböző tartományokban történő megjelenítése (a határidőket nem lehet pontosabban hozzárendelni, mint az ütemezéshez használt órajeleket). Ha moduláris aritmetikát használunk a jövőbeli határidők kiszámításához , a jövőbeli határidőket tároló mezőknek legalább a „leghosszabb várható végrehajtási idő időtartamának kétszerese” + „most” értéket kell tartalmazniuk. Ezért a valós idejű ipari számítógépes rendszerekben nem általános a legközelebbi befejezési dátumra történő ütemezés .

Ehelyett a legtöbb valós idejű számítógépes rendszer fix prioritású ütemezést használ. Rögzített prioritás mellett könnyebben biztosítható, hogy túlterheltség esetén az alacsony prioritású folyamatok lekéssék a határidőket, miközben a magas prioritású folyamatok továbbra is időben befejeződjenek.

Sok kutatást végeztek a rövid távú befejezés tervezésével kapcsolatban ; Ezzel az algoritmussal ki lehet számítani a folyamatok legrosszabb válaszidejét, a kötegelt folyamatokon kívül más típusú folyamatokkal is dolgozhatunk, és szervereket használhatunk a torlódások kezelésére.

Lásd még

• TERVEZETT HATÁRIDŐ  - a feladatütemező megvalósítása a legközelebbi befejezési időre a Linux kernelben

Jegyzetek

1. ↑ Jia Xu, David Parnas. Ütemezési folyamatok kiadási időkkel, határidőkkel, elsőbbséggel és kizárási viszonyokkal.IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 16 NO. 1990. március 3

Irodalom

• Pierre G. Jansen, Sape J. Mullender, Paul JM Havinga, Hans Scholten. Könnyű EDF ütemezés határidős örökléssel
• Stankovic, JA Valós idejű rendszerekre vonatkozó határidők ütemezése: Edf és kapcsolódó algoritmusok. - Springer USA, 1998. - 273 p. — ISBN 9780792382690 .
• Leung, JYT Kézikönyv az ütemezésről: Algoritmusok, modellek és teljesítményelemzés. - CRC Press, 2004. - 1224 p. — ISBN 9780203489802 .