Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /mnt/tanenbaum/sd4/projets/AlgoTR/_includes/path.php on line 15

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /mnt/tanenbaum/sd4/projets/AlgoTR/_includes/path.php on line 15

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /mnt/tanenbaum/sd4/projets/AlgoTR/_includes/path.php on line 15

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /mnt/tanenbaum/sd4/projets/AlgoTR/_includes/path.php on line 15

U-EDF: An Unfair but Optimal Multiprocessor Scheduling Algorithm fo Sporadic Tasks

G. Nelissen, V. Berten, V. Nélis, J. Goossens, D. Milojevic

Damien.

Version 1 : tâches périodiques

Version 2 : tâches sporadiques

 

Résumé :

U-EDF est une généralisation de EDF pour ordonnancer des tâches sporadiques de façon globale en multiprocesseur. Contrairement aux autres généralisations de EDF (G-EDF), cet algorithme est optimal : il ordonnance correctement tout systèmes de tâches faisables avec pour tout i Ui<=1 et U <= m.

Cet algorithme est le deuxième, après RUN à proposer un algorithme optimal qui ne respecte ni la condition P-Fair, ni la condition DP-Fair. Cependant, RUN se limite à l'ordonnancement de tâche périodique, tandis que U-EDF permet de traiter le cas des tâches sporadiques.

L'idée de U-EDF est d'utiliser la règle d'EDF pour placer les tâches sur les processeurs en chargant au maximum le premier avant de commencer à assigner des tâches aux second (en faisant attention a ne pas autoriser de sections parallèles d'une même tâche), etc. En ce sens, les auteurs parlent d'une extension horyzontale de EDF à oposer aux extentions d'EDF non optimales dites "verticales" car elles utilisent la règle ASAP, et donc répartissent la charge sur l'ensemble des processeurs.

Toutefois, U-EDF reste un algorithme online globale, car ce partitionnement n'est qu'un placement des jobs et non des tâches, et de plus il est recalculé à chaque nouvelle activation dans le système. Les résultats de travaux précédant des mêmes auteurs peuvent également être appliqué pour diminuer le nombre de migrations induites par ce partitionnement. 

Tel que décrit jusqu'à présent, l'algorithme ne gère que les tâches périodiques. Pour garantir le respect des échéances des tâches sporadiques, l'algorithme de placement réserve de la place pour le job J+1 dès qu'il a placé le job J d'une tâche. La place réservé est une fraction du temps processeur proportionnelle à la charge de la tâche, et possède la priorité maximale.

Limitations :

L'algorithme se limite aux tâches avec échéances implicites (Di=Ti). N'ayant pas eu le temps de lire la preuve de l'optimalité, je ne sais pas si c'est un problème de preuve ou si l'optimalité ne tient pas. (ou si c'est un problème ouvert).