Ordonnancement Deux-Agents avec Augmentation de Ressources
Vincent Fagnon  1@  , Denis Trystram  1@  , Giorgio Lucarelli  2@  , Clement Mommessin  3@  
1 : Laboratoire d'Informatique de Grenoble
Centre National de la Recherche Scientifique : UMR5217, Université Grenoble Alpes, Institut polytechnique de Grenoble - Grenoble Institute of Technology
2 : Laboratoire de Conception, Optimisation et Modélisation des Systèmes
Université de Lorraine : EA7306
3 : University of Leeds

La diversité des éléments numériques qui composent les systèmes informatiques d'aujourd'hui crée de nouveaux problèmes dans la perspective de gérer efficacement l'exécution des tâches. Et la plupart des données produites par les capteurs de l'Internet des Objets n'ont d'intérêt que pour leur environnement local et ont une durée de vie courte.
Dans ce travail, nous ciblons un système informatique composé de plusieurs unités de calcul et connecté à certains capteurs. Lorsqu'aucune donnée n'est analysée sur ce système, les unités de calcul disponibles peuvent être utilisées par d'autres calculs utiles, de la même manière qu'avec le volonteer computing.

Nous considérons un modèle qui comprend deux agents, chacun avec son propre ensemble de tâches et avec son propre objectif. Les tâches du premier ($\mathcal{L}$) sont online, peuvent être préemptées et l'objectif est de minimiser leur Flowtime moyen. Les tâches du second ($\mathcal{G}$) sont off-line, ne peuvent pas être préemptées, et doivent être exécutées avant une échéance commune.

En raison de fortes bornes inférieures sur le ratio concurrentiel du problème, nous utilisons la notion d'augmentation de ressources pour proposer un algorithme avec une garantie. Même dans le cas de l'augmentation de la vitesse et de la rejection, nous donnons une borne inférieure générale pour le problème qui dépend du ratio des charges de travail $\mathcal{G}$ sur les charges de travail $\mathcal{L}$ (ratio noté $\mathcal{W}$). Ensuite, nous proposons un algorithme ($1+\epsilon_s$)-speed et $O(\frac{W}{\epsilon_r \cdot \epsilon_s})$-compétitif dont nous faisons l'analyse à l'aide de la technique Dual-Fitting (où $\epsilon_s$ et $\epsilon_r$ sont les paramètres de l'augmentation des ressources (respectivement pour la vitesse et la rejection)).


Personnes connectées : 2 Vie privée
Chargement...