Earliest deadline first

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Earliest Deadline First (EDF) je plánovací algoritmus používaný v operačních systémech reálného času, který na rozdíl od RMS nevyžaduje periodické úlohy a zpracování úloh probíhá na základě mezní doby platnosti procesu.

Základní vlastnosti[editovat | editovat zdroj]

Každý proces oznamuje při svém příchodu do fronty dobu platnosti (nejčastěji mezní termín splnění - deadline). Scheduler udržuje informace o všech spuštěných úlohách ve frontě seřazené podle deadline. Plánovač spouští úlohu s nejbližším časem deadline a kdykoliv se spustí úloha s bližším časem deadline, scheduler odstaví právě obsluhovanou úlohu a spouští novou - v tomto případě příchozí.

Rozdíl mezi EDF a RMS[editovat | editovat zdroj]

Při větším zatížení procesoru se ukáže, že algoritmus RMS selže, neboť jak dokázal roku 1973 Liu a Layland, rozvrhovatelný RTOS v případě použití RMS je ve chvíli, platí-li:

U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(\sqrt[n]{2} - 1)

Pro EDF ale platí:

U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1, kde

C_i je doba trvání události, T_i je perioda události. Je vidět, že využití CPU je při použití algoritmu EDF větší.