L’ORDONNANCEMENT DES PLATES-FORMES SUR GRILLE ET CLOUD

 Ordonnancement équitable des ressources

Notion d’équité

Le libre accès à des ressources limitées entraîne inévitablement une utilisation inefficace qui pénalise l’ensemble des participants. En effet, chaque individu cherche à maximiser son intérêt personnel et aura tendance à s’approprier de manière excessive les ressources au détriment des autres [46]. Une solution pour faire face à ce problème consiste à organiser la gestion de ces ressources. Cette gestion doit proposer des mécanismes de régulation afin de garantir une part équitable aux différents utilisateurs. L’équité est un important facteur d’évaluation dans tous les problèmes d’allocation, de distribution ou de partage de ressources entre utilisateurs ; ceci inclut entre autres les systèmes distribués comme les grilles de calcul. Ainsi, un ordonnancement équitable envers les utilisateurs encourage leur participation, alors qu’un ordonnancement inéquitable provoque l’abandon de la participation. De plus, des méthodes capables de justifier les choix effectués et de montrer que le traitement est équitable, permettent de régler les conflits. Il n’y a de problèmes d’équité que lorsque les demandes excèdent les ressources disponibles. Dans ce cas de figure, la mise en place d’une politique d’allocation des ressources est nécessaire pour départager les utilisateurs. Ces politiques d’allocations de ressources doivent obéir à certaines règles, ce qui permet de les automatiser, de les évaluer et de les vérifier. Lorsque les ressources ne sont pas suffisantes pour l’ensemble des utilisateurs et qu’un conflit survient, la politique d’allocation fait alors office de médiateur [47] et répartit les ressources entre les utilisateurs. La grille de calcul permet le partage de ressources de calcul et/ou de stockage. Dans un tel environnement apparaît le problème de distribuer les ressources à la fois de façon efficace et équitable. Un des principes importants est que la grille doit respecter la liberté des fournisseurs. Les sites ont la liberté d’attribuer leurs ressources comme ils le souhaitent à des 58 groupes particuliers, en revanche une fois l’attribution décidée, on doit respecter le principe d’équité entre individus égaux en droits. En conséquence, il existe dans une grille plusieurs niveaux d’ordonnancement : – au niveau central, les utilisateurs soumettent leurs tâches à un système de gestion de charge (en anglais “Workload Management System (WMS)”) dont le rôle est de répartir les tâches sur les sites [10]. Un site est passif devant l’envoi des tâches et ne participe pas directement à la sélection par un WMS : les sites publient de l’information sur l’état de leurs clusters et le WMS gère la sélection des sites pour chacune des tâches. L’utilisateur peut spécifier certaines contraintes à respecter pour la sélection du site dans son JDL [48] – au niveau de chaque site de la grille, le système de batch est chargé de la gestion de l’envoi des tâches depuis une machine frontale, le “Computing Element (CE)”, sur l’ensemble des machines de calcul, les “Worker Nodes (WN)”. Le système de batch ne décide pas du placement ; c’est le rôle de l’ordonnanceur. Couramment utilisé sur les clusters intégrés dans la grille, l’ordonnanceur MAUI [49] fonctionne sur le principe d’une file d’attente triée selon la priorité des tâches. L’administrateur peut spécifier des pondérations selon les groupes, les utilisateurs, le temps d’attente. Il est aussi possible d’attribuer une priorité supplémentaire à une tâche, par exemple lorsque son groupe ou son utilisateur a consommé un temps de calcul inférieur à son quota de temps pendant une période. Nous reviendrons dans ce chapitre sur cette fonctionnalité, appelée “Fair Share”. – Eventuellement, un troisième niveau d’ordonnancement est celui de la plate-forme. Il s’agit de définir une politique pour créer les jobs pilotes et définir un ordre de traitement par ces jobs pilotes des tâches soumises par les utilisateurs de la plateforme. L’ordonnancement va permettre d’organiser la file d’attente des utilisateurs si ceux-ci partagent les agents (DIRAC) ou gérer la création des agents par utilisateur quand les agents sont privés (HTCaaS) 

Politiques d’ordonnancement

Nous n’allons présenter dans ce paragraphe que les algorithmes d’ordonnancement les plus connus et les plus couramment utilisés, notamment sur la grille. Traditionnellement, les ordonnanceurs sont conçus pour affecter les ressources de façon uniforme aux processus (dans l’idéal, tous les processus s’exécuteraient en même temps et à la même vitesse). Cependant, ce type d’ordonnancement a tendance à favoriser les utilisateurs qui lancent beaucoup de processus en allouant le CPU proportionnellement au nombre de processus et risque d’étouffer les utilisateurs avec peu de tâches. A l’inverse, un ordonnanceur qui privilégie l’équilibre entre les utilisateurs peut pénaliser les très gros consommateurs de ressources, ce qui pose problème quand ceux-ci travaillent pour la collectivité. C’est ainsi le cas pour les expériences au LHC où la production de données simulées est centralisée afin d’être plus efficace. Satisfaire tous les utilisateurs est donc la quadrature du cercle et les politiques d’ordonnancement décrites ci-dessous vont finalement privilégier une catégorie d’utilisateurs.

First In First Out (FIFO)

L’ordonnancement est fait dans l’ordre d’arrivée en gérant une file unique des processus sans priorité ni préemption: chaque processus s’exécute jusqu’à son terme ; le processus élu est celui qui est en tête de liste, le premier arrivé. Cet algorithme est facile à implanter, mais il est loin d’optimiser le temps de traitement moyen et il n’est pas très équitable. La plate-forme WISDOM [28], développée par le Laboratoire de Physique Corpusculaire (LPC) Clermont-Ferrand, France, pour les projets WISDOM-I (2005) et WISDOM-II (2006) utilisait une politique d’ordonnancement FIFO. 

Round robin

Il s’agit d’un algorithme ancien, simple et fiable. Les jobs sont servis tour à tour : dans le cas avec préemption des jobs, chaque job est exécuté dans une tranche de temps constante (quantum). A la fin du quantum, si le job n’est pas encore terminé, il est remis dans la file d’attente et laisse ainsi la machine au job suivant. Sans préemption des jobs, l’ordonnanceur sélectionne tour à tour un job d’un utilisateur différent dans la file d’attente. 60 La plate-forme DIRAC [43] utilise la politique d’ordonnancement Round Robin sans préemption.

Ordonnancement équitable ou « fairshare scheduling »

Cette méthode d’ordonnancement a pour objectif que chaque utilisateur obtienne une part équitable plutôt que chaque processus [50]. Chaque utilisateur a un pourcentage du temps de calcul qu’il divise entre ses tâches. Il est aussi possible d’attribuer une priorité supplémentaire à une tâche, par exemple lorsque son groupe ou son utilisateur a consommé un temps de calcul inférieur à son quota de temps pendant une période. Une variable baptisée FS est calculée pour chaque utilisateur. Quand un processeur est libre, c’est l’utilisateur avec le plus petit FS qui peut utiliser le processeur. FS est calculé avec la formule suivante (2.1) : (2.1) Avec : – le paramètre « Max_depth », nombre d’intervalles enregistrés dans la table de l’histoire. – le paramètre « Decay_rate » est le nombre de tâches d’utilisateur j qui sont exécutées dans l’intervalle i – la durée de chaque intervalle est fixée par le le paramètre « Duration » Considérons par exemple deux utilisateurs avec un historique d’utilisation de ressources. Pour un choix de paramètres (Duration = 1h, Max_depth = 5, Decay_rate=0.85), on obtient le tableau 3-1 et des valeurs FS qui attribuent la priorité à l’utilisateur 1 pour le prochain processeur disponible.