Algoritm de planificare EDF

Cel mai devreme termen limită ( EDF ), în italiană înainte de cel mai apropiat termen , este un algoritm de planificare tipic sistemelor de operare în timp real . După cum sugerează și numele, programatorul selectează ca următor proces pentru a-l executa pe cel cu cea mai mică distanță de la termenul limită. EDF este un algoritm de prioritate dinamic , deoarece prioritatea atribuită proceselor se poate modifica la fiecare execuție a planificatorului și valoarea acestuia depinde numai de caracteristicile lor temporale (ora sosirii, termenul limită etc.) ^[1] .

Complexitatea algoritmului este în mod tradițional $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ ^[2] , chiar dacă în literatura științifică este posibil să se găsească algoritmi care amortizează complexitatea a $O(n\log n)$ ${\ displaystyle O (n \ log n)}$ $O (n \ log n)$ ^[3] .

Caracteristicile algoritmului

Definiția formală a algoritmului de planificare EDF poate fi scrisă ca ^[1] :

La fiecare moment t , jobul j este ales pentru a fi programat dacă expirarea acestuia este cea mai apropiată de timpul t .

Presupunând că fiecare proces $t$ ${\ displaystyle t}$ $t$ pregătiți-vă la intervale de timp $T_{t}$ ${\ displaystyle T_ {t}}$ $T_ {t}$ și că expirarea corespunde perioadei ( expirare implicită ), atunci este posibil să se calculeze analitic utilizarea sistemului ca:

U=\sum _{t=1}^{n}{\frac {C_{t}}{T_{t}}}

{\ displaystyle U = \ sum _ {t = 1} ^ {n} {\ frac {C_ {t}} {T_ {t}}}}

{\ displaystyle U = \ sum _ {t = 1} ^ {n} {\ frac {C_ {t}} {T_ {t}}}}

unde este $C_{t}$ ${\ displaystyle C_ {t}}$ $CT}$ este cel mai rău timp de rulare. De sine $U\leq 1$ ${\ displaystyle U \ leq 1}$ ${\ displaystyle U \ leq 1}$ , programul este admisibil.

Optimitatea EDF

EDF este un algoritm optim pe sistemele uniprocesor preventive : dacă nu există un program valid în EDF, nu va exista niciun alt algoritm care să îl poată găsi. ^[4]

Exemplu

Luați în considerare următoarele procese (presupuneți un termen implicit , adică echivalent cu perioada):

Proces	Timpul de execuție	Perioadă
P1	1	8
P2	2	5
P3	4	10

Planificatorul la momentul 0 va verifica distanța expirărilor proceselor, în acest caz prioritatea atribuită proceselor este $P2>P1>P3$ ${\ displaystyle P2> P1> P3}$ ${\ displaystyle P2> P1> P3}$ :

Un posibil program al exemplului, presupunând absența preempțiunii

Notă

^ ^a ^b Sanjoy Baruah, Programarea sarcinilor în timp real: algoritmi și complexitate , Universitatea din Carolina de Nord la Chapel Hill.
^ Michael O'Boyle, Software încorporat - Lectura 6: Programare ( PDF ), la inf.ed.ac.uk. Adus la 23 noiembrie 2016 .
^ Jagbeer Singh, Un algoritm de reducere a complexității în timp a primului algoritm de planificare pentru primele termene în sistem în timp real , 2010.
^ Arezou Mohammadi, Selim G. Akl, Scheduling Algorithms for Real-Time Systems ( PDF ), School of Computing, Queen's University, 2005.

[barauh-1] Sanjoy Baruah, Programarea sarcinilor în timp real: algoritmi și complexitate , Universitatea din Carolina de Nord la Chapel Hill.

[2] Michael O'Boyle, Software încorporat - Lectura 6: Programare ( PDF ), la inf.ed.ac.uk. Adus la 23 noiembrie 2016 .

[3] Jagbeer Singh, Un algoritm de reducere a complexității în timp a primului algoritm de planificare pentru primele termene în sistem în timp real , 2010.

[4] Arezou Mohammadi, Selim G. Akl, Scheduling Algorithms for Real-Time Systems ( PDF ), School of Computing, Queen's University, 2005.

[1]

[2]

[3]

[4]