Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
ETAT DE L’ART SUR LES ALGORITHMES D’ORDONNANCEMENTS
Le Cloud Computing est en train de devenir la plateforme de nouvelle génération qui faciliterait la rémunération de l’utilisateur lorsque vous utilisez le mode selon les exigences.
Le principal objectif du cloud est de fournir un accès efficace aux ressources distantes et géographiquement distribuées à l’aide de la virtualisation dans l’infrastructure en tant que service (IaaS).
Nous avons besoin de différents types de machines virtuelles (VMs) conformément aux exigences et le fournisseur de Cloud fournit ces services conformément au Service Levels Agreement (SLA) pour garantir la qualité de service (QoS).
Pour gérer un grand nombre de demandes de machines virtuelles, les fournisseurs de cloud nécessitent un algorithme d’ordonnancement de ressources efficaces.
Dans cette partie nous allons faire une étude détaillée des différents concepts d’ordonnancements et d’allocations de ressources suivi d’une étude comparative des algorithmes d’ordonnancements en fonction des critères d’optimisations.
Définitions et concept de base
La gestion des ressources est un processus clé dans le Cloud Computing pour les fournisseurs de services cloud. L’allocation des ressources fait partie du processus de gestion des ressources et son objectif principal est d’équilibrer la charge des ressources.
Dans la littérature il existe différent concept tel que : allocations de ressources, ordonnancement statique et dynamique qui sont étudiées pour mieux appréhender les algorithmes d’ordonnancements.
❖ L’allocation de ressources : consiste à attribuer les ressources disponibles aux applications nécessaires via Internet. Elle permet une répartition des ressources disponibles entre les utilisateurs de cloud et les applications d’une manière économique et efficace.
❖ L’ordonnancement : est l’action d’assigner des ressources (des machines virtuelles) au traitement des tâches ou des demandes et doit tenir compte des caractéristiques des tâches tel que : ressources nécessaires, heure de début et de fin, priorité, lien entre les tâches, etc. Elle peut être statique ou dynamique.
❖ Ordonnancement statique : L’ordonnancement est qualifié de statique lorsque chaque tâche (demandes entrantes) demeure sur le même nœud de calcul (ou serveur) du début à la fin de son traitement. Le placement initial des tâches tient compte de la demande en ressources formulée par les utilisateurs, et non pas des besoins réels en ressources de ces tâches [5].
❖ Ordonnancement dynamique : L’ordonnancement est qualifié de dynamique lorsque les tâches peuvent être migrées d’un nœud de calcul à un autre durant leur traitement, ce qui se fait en tenant compte de leurs besoins réels en ressources [5]. L’ordonnancement vise à remplir un ou plusieurs objectifs. Certains objectifs touchent
à la rapidité de traitement des tâches, d’autres sont liés à la répartition équitable des ressources entre les tâches. D’autres encore sont relatifs à l’utilisation optimale des ressources, par exemple l’équilibrage de la charge de travail entre les ressources, ou au contraire sa consolidation sur un nombre restreint de ressources afin de maximiser l’utilisation de ces dernières.
L’objectif principal du fournisseur de cloud est de fournir une utilisation maximale des ressources et d’augmenter les bénéfices en réduisant la consommation d’énergie et les coûts d’exploitation. Alors qu’on sait que la cible des utilisateurs de cloud est le temps de réponse minimum et l’amélioration du débit total [3].
La tâche intéressante dans le cloud consiste à allouer les ressources à l’aide de l’intervalle de temps minimal avec une utilisation efficace des ressources existantes. Grâce aux techniques d’ordonnancement, les ressources sont allouées dans le centre de données cloud. De nombreux utilisateurs peuvent simultanément faire la demande de service dans un environnement cloud. Par conséquent, pour améliorer les performances du système et réduire les coûts, une technique efficace d’allocation des ressources et d’ordonnancement des machines virtuelles est nécessaire. L’allocation de ressources est un élément important dans le cloud, si celle-ci n’est pas gérée avec précision cela affaiblira les services du cloud d’où la nécessité d’adopter des stratégies ou algorithmes d’ordonnancements.
Algorithmes d’ordonnancements
Les algorithmes d‘ordonnancement jouent un rôle important lorsque l’objectif est de planifier ou d’ordonner efficacement les tâches afin de réduire le temps de réponse et améliorer l’utilisation des ressources.
Une stratégie d’allocation des ressources (RAS) dans le cloud peut être défini comme un mécanisme qui vise à garantir que les ressources physiques et ou virtuels sont correctement assignés aux utilisateurs de cloud. Elle consiste à intégrer les activités des fournisseurs de cloud pour utiliser et allouer des ressources rares dans la limite de l’environnement cloud afin de répondre aux besoins de l’application cloud [3].
Il nécessite le type et la quantité de ressources nécessaires à chaque application pour effectuer le travail. L’ordre et l’heure de l’affectation des ressources constituent également une entrée pour un RAS optimal [3].
Algorithmes d’ordonnancements statiques
Les algorithmes statiques conviennent aux systèmes avec de faibles variations de charge. Il permet d’attribuer des ressources fixes à l’utilisateur ou à l’application cloud.
Dans l’algorithme statique, le trafic est réparti également entre les serveurs. Cet algorithme nécessite une connaissance préalable des ressources du système dont les performances des processeurs sont déterminées au début de l’exécution, donc la décision de décalage de la charge ne dépend pas de l’état actuel du système [6].
Cependant, les algorithmes d’équilibrage de charge statique ont un inconvénient parce que les tâches ne sont attribuées au processeur ou aux machines qu’après leur création et que les tâches ne peuvent pas être transférées pendant son exécution vers une autre machine pour l’équilibrage de charge [7].
Algorithmes d’ordonnancements dynamiques
Dans l’algorithme dynamique, le serveur le plus léger de l’ensemble du réseau ou du système est recherché et préféré pour équilibrer une charge. Pour cette communication en temps réel, le réseau est nécessaire, ce qui peut augmenter le trafic dans le système. Ici, l’état actuel du système est utilisé pour prendre des décisions pour gérer la charge [8]. Les algorithmes dynamiques répondent à l’état actuel du système en prenant des décisions de transfert de charge. Étant donné que l’état actuel du système est utilisé pour prendre des décisions d’équilibrage de charge dynamique, les processus peuvent passer d’une machine surutilisée à une machine sous-utilisée en temps réel de façon dynamique [7]. L’inconvénient de l’allocation dynamique est lorsque des ressources nécessaires sont demandées à la volée et qu’elles pourraient ne pas être accessibles. Ainsi, le fournisseur de services doit allouer les ressources de différents centres de données cloud.
Domaine d’utilisation
L’ordonnancements dans le cloud Computing est classé au niveau de l’utilisateur et au niveau du système [9]. Au niveau de l’utilisateur, l’ordonnancement traite les problèmes soulevés par la prestation de services entre les fournisseurs et les clients. La programmation au niveau système gère la gestion des ressources dans les centres de données. Le Datacenter se compose de plusieurs machines physiques, des millions de tâches des utilisateurs sont reçues, l’attribution de ces tâches aux machines physiques se fait au niveau des centres de données. Cette affectation d’ordonnancement joue un rôle significatif sur les performances du Datacenter. En plus de l’utilisation du système, d’autres exigences comme la qualité de services (QoS), le Service Levels Agreement (SLA), le partage de ressources, la tolérance aux pannes, la fiabilité, la satisfaction en temps réel, etc. devraient être pris en considération. L’allocation de ressources en fonction du modèle économique de marché est efficace dans un environnement de Cloud Computing où les ressources sont virtualisées et livrés à l’utilisateur en tant que service [10].
Etude comparative des algorithmes d’ordonnancements de VMs
Avec les stratégies d‘ordonnancement ou d’allocation de ressources, on choisit la tâche à exécuter et la machine adéquate pour cette tâche, en améliorant certains objectifs (minimiser le temps d‘exécution, minimiser le temps d‘attente ou le temps de réponse, respecter le délai, etc…), chaque stratégie a ses avantages [4].
L‘objectif de suivre un algorithme d‘ordonnancement pour un problème précis c‘est d‘améliorer et optimiser certains critères. On ne peut pas dire qu‘il y a un critère d‘optimisation universel, mais le choix de critères d‘optimisations est très important dans la qualité de travail, parmi les critères d‘optimisations les plus utilisé dans le cloud on distingue :
❖ MakeSpan (MS) : c‘est le temps de terminaison de la dernière tâche, correspond au temps passé par le système pour terminer tout son travail (le temps global pour exécuter toutes les demandes) [4]. Il est utilisé pour estimer le temps d’exécution maximal, en évaluant l’heure de fin de la dernière tâche, lorsque toutes les tâches sont planifiées. Si la durée de la tâche spécifique n’est pas minimisée, la demande ne sera pas terminée à temps [11]. Elle est déterminée par l’équation 2.1 :
Où FnhTime indique l’heure de fin de la n’ième tâche.
❖ Flow time (Fi) : Dans le cloud les ressources sont limitées et quand les machines virtuelles sont toutes occupées les tâches attendent dans une file d‘attente [4]. Le problème dans ce cas c‘est le temps d‘attente, c‘est pour ça qu‘on peut considérer le temps d‘attente moyen Flow time (Fi) comme un critère d‘optimisation et des algorithmes sont utilisés pour le minimiser.
Le temps d’attente moyen Fi est donné par l’équation 2.2 :
Où i est le temps d′arrivé et Ai est la fin de l′exécution job
Mais l‘inconvénient c‘est que la minimisation du temps d‘attente moyen implique l‘augmentation du temps d‘attente des petits jobs et cette optimisation conduit à des résultats indésirables.
❖ Le Débit (Throughput) : c‘est mieux d‘utiliser le débit comme critère d‘optimisation (nombre de tâches alloués par unité de temps) [4] comme indiqué dans l’équation 2.3 :
Où ExeTime représente le temps d’exécution de la ième tâche.
Dans le Cloud Computing, le débit signifie que certaines tâches sont terminées avec succès dans un certain laps de temps. Un débit minimal est requis pour l’ordonnancement des tâches.
❖ Deadline : qui correspond aux nombres de tâches (demandes) terminées avec succès avant le délai.
❖ Reponse Time (RT) : représente le temps nécessaire à partir du moment où une demande a été soumise jusqu’à ce qu’une réponse soit produite par les algorithmes d’équilibrage de charge dans le cloud Computing et cette métrique doit être réduite [12] comme mentionné dans l’équation 2.4 : Les algorithmes d’ordonnancements sont classés en fonction de l’état actuel de la machine virtuelle. Ils ont pour objectif principal de planifier ou d’ordonner des tâches sur des machines virtuelle. Ils ont pour objectif principal de planifier ou d’ordonner des tâches sur des machines virtuelles (VMs) en fonction du temps d’exécution.
La figure 2 montre une taxonomie des algorithmes d’ordonnancements de tâche et d’allocation des ressources évoqués actuellement dans le contexte du cloud.
En fonction du débit (throughput)
En juin 2017, Sharon Justine et Deepa S. Kumar publient un article qui vise à évaluer trois algorithmes d’ordonnancement de machines virtuelles (VM), à savoir : Premier arrivé, premier servi (FCFS), algorithme de Round Robin (RR) et algorithme génétique (GA) utilisant CloudSim et le calcul du débit est fait pour les algorithmes mentionnés ci-dessus et en essayant de trouver le débit maximal entre c’est dernier. Dans ce projet, les trois algorithmes d’ordonnancement de VM sont implémentés et le calcul du débit maximal est effectué, le meilleur algorithme est trouvé sur la base du débit [14].
CloudSim est une bibliothèque pour la simulation de scénarios cloud. Il fournit des classes essentielles pour décrire les centres de données, les ressources de calcul, les machines virtuelles, les applications, les utilisateurs et les politiques de gestion de diverses parties du système telles que l’ordonnancement et l’approvisionnement.
Le débit est le nombre de tâches qui terminent leur exécution avec succès par unité de temps. Il est largement appliqué aux systèmes allant de divers aspects des systèmes informatiques et de réseau aux organisations. Le calcul du débit pour l’ordonnancement de la machine virtuelle est calculé à l’aide de l’équation 2.5 :
Un algorithme avec un débit maximal est considéré comme le meilleur algorithme. Pour l’analyse d’algorithme comme First-Come First-Served, Round Robin et de l’algorithme génétique, le débit calculé est :
Les algorithmes d’ordonnancement de VMs tel que FCFS, RR, GA sont mise en œuvre dans un environnement de simulation en nuage à l’aide de l’outil de simulation CloudSim. Le calcul de débit est effectué pour chaque algorithme et l’algorithme génétique (GA) possède la valeur de débit plus élevée (soit 1,5) [14].
Ainsi, l’objectif de l’algorithme génétique (GA) est réduit le temps programmé de la VM mais difficile à implémenter et le coût de migration devient un véritable problème.
En fonction du MakeSpan et du Reponse Time
L’objectif de cette étude est de montrer quel est l’algorithme d’ordonnancement (FCFS, SJF, MSJF) de VMs qui est plus efficace pour améliorer le temps de réponse (Reponse Time) et le MakeSpan.
En 2016, Mokhtar A. Alworafi, Atyaf Dhari et Asma A. Al-Hashmi [15] publie un article qui vise à améliorer l’algorithme d’ordonnancement du premier travail le plus court (SJF) dans le cloud Computing. Dans l’ordonnancement des tâches, les paramètres les plus importants sont la durée de vie de la tâche (MakeSpan) et le temps de réponse (RT).
L’un des algorithmes proposés est SJF. La tâche dans cet algorithme a le temps d’exécution le plus bas, que son processus ayant la plus petite rafale CPU obtient une priorité élevée et s’exécute au premier par le CPU. Les tâches restantes attendent l’exécution pendant ce temps, et enfin la tâche qui a le temps d’exécution le plus élevé sera exécutée à la fin. Le critère de l’algorithme SJF (Short Job First) est qu’il traite d’abord la plus petite tâche.
L’algorithme proposée MSJF (Modified Short Job First) a deux fonctions, l’une calcule la moyenne de la longueur des tâches et l’autre est l’équilibrage de charge entre les machines virtuelles. L’un des avantages importants de MSJF est d’envoyer les tâches les plus longues à la machine la plus rapide. Ils ont comparé le résultat de leur algorithme proposé MSJF avec SJF et FCFS. Les performances de MSJF sont meilleures par rapport à SJF et FCFS pour minimiser (réduire) le temps d’achèvement de la dernière tâche ou temps total (MakeSpan) et minimiser le temps de réponse (Reponse Time) moyen en maximisant l’utilisation des ressources. Et comparer les résultats de l’algorithme MSJF obtenu avec les algorithmes SJF et FCFS [15].
L’algorithme proposée par Mokhtar A. Alworafi, Atyaf Dahri (MSJF), si la tâche a le temps d’exécution le plus élevé, le courtier enverra la tâche à la machine virtuelle à haute configuration pour exécuter cette tâche, et si la tâche a le temps d’exécution le plus bas, le courtier l’enverra au virtuel à faible configuration machine à exécuter. Les paramètres suivants sont utilisés dans MSJF : MakeSpan [15] et le temps de réponse.
Nous avons utilisé la boîte à outils CloudSim pour simuler l’environnement de communication et l’environnement de ressources hétérogène.
Jia Ru et Jacky Keung ont proposé un algorithme d’ordonnancement avec un groupe de tâches, conscient de la priorité et du SJF pour réduire le MakeSpan et le temps d’attente, en maximisant l’utilisation des ressources. Ils ont comparé les algorithmes de planification existants avec l’algorithme de planification de regroupement. Les résultats de l’expérience ont montré que le temps d’attente et le temps de traitement dans la technique proposée diminuaient significativement (plus de 30%) [16].
E. Iniya Nehru et al ont proposé un algorithme basé sur les priorités, ils ont vérifié chaque tâche selon différents algorithmes et calculé leur temps d’attente. La moyenne du temps d’attente par rapport à l’algorithme de programmation First Come First Serve (FCFS) est plus faible. Cela signifie que l’algorithme de planification du premier travail le plus court (SJF) est plus efficace que l’algorithme du premier arrivé premier servi (FCFS) [14].
Afin d’obtenir le meilleur résultat de la planification des tâches pour prendre moins de temps d’exécution et réduire la durée de vie (MakeSpan). L’idée principale de la tâche la plus courte modifiée en premier est de trier les tâches dans un ordre croissant en fonction de la durée des tâches et de calculer la moyenne de toutes les tâches. Ensuite, pour toutes les tâches, l’algorithme vérifie chaque longueur de tâche, si elle est inférieure à la moyenne de la longueur des tâches et le nombre de tâches dans VM1 inférieur au nombre de tâches dans VM2, alors la tâche sera envoyée à VM1, sinon à VM2.
Nous avons utilisé deux algorithmes, les algorithmes SJF et FCFS pour évaluer notre algorithme proposé MSJF. Pour chaque algorithme, nous avons utilisé la même configuration.
En fonction du Deadline
L’objectif de cette étude est de montrer quel est l‘algorithme d‘ordonnancement qui respecte le délai (Dead-line) d’une manière efficace.
En septembre 2018, Kebir Fatima Zohra, utilise trois (3) Datacenters identiques composé chacun d‘un Host(serveur) avec une seule VMs. Chaque machine virtuelle a une :
✓ Vitesse de 1000 MIPS.
✓ Bandwidth (BW) disponible de 1Gb/ s (1000 Mb/ s).
✓ Capacité de stockage de 10000 MB.
✓ Mémoire vive (RAM) de 512 Mb.
Nous traitons 200 Cloudlet(tâches) sur les trois datacenters utilisant trois Algorithmes d‘ordonnancement : First Come First Served (FCFS), Round-Robin et Short Job First. Pour chaque Cloudlet on donne une date limite générée au hasard où la valeur minimale est 0 et la valeur maximale est 100.
Si on prend en considération le nombre des tâches terminées avec succès avant le délai (critère :« Deadline »), l‘algorithme d‘ordonnancement Short Job First est plus efficace pour terminer les tâches avant l’arrivée de l’échéance que l’algorithme d’ordonnancement FCFS, et FCFS est meilleur que l‘algorithme d‘ordonnancement Round-Robin [4]. Nous comparons le nombre de tâches accomplies par chaque algorithme. Dans la figure 6, nous pouvons voir les résultats de l’expérience.
Sur l’axe des abscisses, il indique le nombre des tâches et l’axe des y indique le nombre de tâches terminées avec succès avant que l’échéance ne soit atteinte.
En examinant la figure, nous pouvons dire que l’algorithme Short Job First est le plus efficace parmi ces algorithmes pour respecter le « Deadline ». En augmentant le nombre des tâches nous pouvons remarquer une plus grande différence et conclure que Short Job First est meilleur que FCFS et FCFS est meilleur que Round Robin.
En fonction du MakeSpan
Le but de cette étude comparative est de montrer quel est l‘algorithme d‘ordonnancement Qui réalise le « MakeSpan » minimal.
Dans cet article, deux algorithmes basés sur l’heuristique : Min-Min et Max-Min ont été décrits par Neha Sharma, Dr. Sanjay Tyagi, Swati Atri, simulés sur CloudSim puis une analyse basée sur la comparaison a été effectuée en prenant en compte le paramètre MakeSpan [17].
L’algorithme Min-Min est un algorithme simple mais il donne le résultat rapide lorsque la taille de la tâche dans la méta-tâche est petite par rapport à une tâche de grande taille.
L’objectif principal de l’algorithme Max-Min est de réduire le temps d’attente des travaux de grande taille [18]. Dans cet algorithme, les tâches de petite taille sont exécutées simultanément avec des tâches de grande taille, réduisant ainsi la durée de vie et offrant une meilleure utilisation des ressources.
La simulation des deux algorithmes a été effectuée en utilisant CloudSim comme outil de simulation.
Après avoir implémenté les algorithmes Min-Min et Max-Min avec 50 Cloudlet et 2 machines virtuelles, leur MakeSpan a été calculé. La valeur de MakeSpan pour les deux algorithmes a été calculée après avoir exécuté le code 20 fois, puis leur moyenne est calculée, comme indiqué ci-dessous, en tant que valeur finale. Les résultats finaux ont été montrés à l’aide du graphique à barres de la figure 7 [17] :
Le graphique à barres ci-dessous montre que le Max-Min donne le meilleur MakeSpan par rapport à l’algorithme de Min-Min. Dans cet article, une analyse comparative basée sur la simulation de deux algorithmes d’ordonnancements de taches les plus utilisés (Max-Min et Min-Min) a été effectué. Il semble que le Max-Min surpasse le Min-Min lorsque le nombre de taches de grande taille est supérieur à la tâche de courte durée.
Les algorithmes FCFS, SJF, RR, GA ont été pour les critères du débit et du temps de réponse et celle de Min-Min et Max pour le critère du MakeSpan (cycle de vie de la tâche). L’algorithme Génétique présente le meilleur résultat pour le débit(throughput) mais reste insuffisant et difficile à implémenter. L’algorithme Max-Min surpasse Min-Min lorsque le nombre de demandes entrantes (tâches) de grande taille est supérieur à la tâche de courte durée. Mais lorsque les tâches de courte durée sont plus nombreuses que les tâches de longue durée, Min-Min peut être le meilleur.
Ces algorithmes sont étudiés sur la base des critères de performances tel que MakeSpan et Débit, Deadline et Reponse Time mais ne fournissent aucune connaissance sur les types de services offert, les types de ressources (routeurs, ou type de VMs) réservés ainsi qu’à la durée d’allocations (nombre de jours que la ressource sera allouée à l’utilisateur). Ce tableau montre que les concepteurs évaluent chaque algorithme d’ordonnancement en fonction d’un critère d’optimisation. Nous venons ainsi de faire une analyse comparative des algorithmes étudies dans le chapitre précédent sur la base des critères d’optimisation. Chaque algorithme est implémenté sur la base d’un critère mais ces derniers ne peuvent pas être mapper par rapport à notre contexte ce qui nous a permis de proposer un algorithme d’ordonnancement ou d’allocation en se basant sur le type de services, types de ressources ainsi qu’à la durée d’exécution de la demande de l’utilisateur. Cet algorithme sera détaillé et implémenter dans le chapitre suivant.
PROPOSITION D’UN ALGORITHME D’ORDONNANCEMENT DE VMs
Les points faibles relevés pour les autres algorithmes sont, pour l’algorithme Round Robin l’utilisation excessives de ressources, Min-Min et Max-Min échouent à utiliser efficacement les ressources, ce qui entraine un problème de déséquilibre de charge, l’algorithme FCFS planifie les tâches en fonction de leur ordre de soumission. Si une tâche soumise doit occuper un grand nombre de ressources informatique et que sa durée est longue, les tâches de courte durée doivent attendre longtemps et cela affecte donc négativement l’expérience utilisateur.
À l’avenir, il existe un large éventail d’amélioration où un algorithme peut être développé qui peut mieux fonctionner et donner un moyen efficace d’ordonnancé la tâche en utilisant les avantages des algorithmes mentionnés et en surmontant simultanément leurs inconvénients. L’état de l’art sur les algorithmes d’ordonnancements de VMs nous a permis de faire une étude comparative sur les stratégies existantes en fonction des critères d’optimisations.
Ce pendant l’existant ne s’applique pas par rapport à notre contexte, mais nous a permis de proposer un algorithme d’ordonnancement de VMs permettant de gérer le type de services, de demandes, le type de ressources ainsi que la durée d’allocation (nombre de jours que la ressource sera alloué à l’utilisateur).
Ainsi la mise en place de notre proposition va se dérouler en cinq étapes :
❖ Définition du modèle de système proposé ;
❖ Définition du principe de fonctionnement du modèle ;
❖ Définition du l’architecture proposée ;
❖ Implémentation de notre algorithme d’ordonnancement de VMs ;
❖ Tests et validation ;
Modèle de système proposé
Le modèle proposé s’articule autour de quatre sections principales : La première section représente les utilisateurs finaux, la deuxième est le système de gestion de contrôle ou Control Management System (CMS), la troisième section représente le système d’information (Information System) et la quatrième représente notre centre de donnée (le Datacenter). Les principaux composants sont illustrés dans la figure 8 :
Le Datacenter
Le Datacenter ou centre de donnée permettra de gérer plusieurs machines hôtes ou machines centrales. La machine hôte (soit un hyperviseur ou un serveur Dynamips/Dynagen, etc.,) est l’un des composants les plus importants. Chaque hôte peut avoir sa propre configuration et ses propres ressources tel que le processeur (CPU), la RAM (en Go) et le stockage (en Go).
L’autre composant est la machine virtuelle. Il est possible de créer un nombre illimité de machines virtuelles sur la machine hôte avec différentes capacités de calcul en fonction de la capacité de l’hôte. Chaque machine virtuelle a également sa propre configuration et ses propres ressources.
Le Datacenter est responsable de l’allocation de ressources aux utilisateurs et de la gestion de l’ordonnancement en fonction des ressources disponibles.
Le Control Management System
Le Control Management System (CMS) ou système de contrôle centrale est un autre composant qui fonctionne comme intermédiaire entre les utilisateurs et le Datacenter.
Le CMS est constitué d’un classificateur de tâches qui empile ces tâches dans une file d’attente. Les tâches représentent les demandes entrantes soumissent par les utilisateurs. Chaque tâche a sa propre spécification : le type de services demandé, le nombre d’élément de traitement, ainsi sa durée de bail (le nombre de jours que la ressource sera allouée).
Le Système d’information
Le Système d’Information permet de renseigner l’état actuel du système en termes de disponibilité de ressources avant de faire une allocation. Il est représenté par trois fonctions au niveau de notre algorithme d’ordonnancement de VMs :
Fonction verifier_disponibilté : cette fonction prend en paramètre les machines centrales (machines hôte) de notre Datacenter. D’abord les caractéristiques des machines hôtes seront initial à zéro dans un tableau, puis une récupération des ressources occupé des machines centrales sera faite en se basant sur chaque type de ressources.
Par exemple si le type de serveur est un hyperviseur ou un serveur dynamips, le système d’information regarde si les ressources (de l’hyperviseur ou du serveur dynamips) sont égale à la somme des caractéristiques demandés en enlevant les ressources réservées. S’il existe une ressource non disponible pour l’exécution de toutes ces requêtes, la fonction suivante sera vérifiée.
Fonction verifier_possibilité_execution_demandes : cette fonction prend en paramètre la disponibilité des machines centrales ainsi qu’une estimation des demandes. Elle retourne dans une tableau associatif la disponibilité des ressources tant que les caractéristiques de la machines hôtes sont plus grand que celles des demandes estimées. Fonction evaluer_demandes : cette fonction est la dernière étape de la vérification de la disponibilité des ressources dans notre Datacenter et nous permet d’évaluer les demandes des utilisateurs. Elle prend en paramètres l’ensemble des demandés en se basant sur le type de services. Par exemple lorsque les demandes sont des services réseaux, elle vérifie si la disponibilité des caractéristiques de la machine hôte concernée est plus grande que celles des demandes estimées. Le résultat sera retourné dans un tableau associatif. Ces trois fonctions nous permettre de connaitre la disponibilité des ressources sur le datacenter.
Les utilisateurs
Le La plateforme présente une interface graphique pour la soumission des tâches des utilisateurs. Les tâches sont classées en trois types : routeurs, VMs de type LXC et VMs de type KVM.
Tâche de types routeurs (en orange) : cette tâche est destinée aux utilisateurs qui souhaite réserver le nombre de routeurs voulu. Ils pourront concevoir des topologies et de les configurer à travers une interface graphique.
Tâche de types LXC (en vert) : cette tâche destinée aux utilisateurs qui souhaite tester des services réseau.
Tâche de type KVM (en rouge) : destinée aux utilisateurs qui souhaite réservée autres services ou autres systèmes d’exploitation comme des clients Linux (Desktop ou Serveur) ou des clients Windows, etc.
Les tâches sont remplis et maintenus par le système de gestion de contrôle (CMS) pour être ordonnancée lorsque les ressources sont libres. Bien que la ressource informatique désigne le cœur, la mémoire le stockage et la bande passante, nous considérons le cœur et la mémoire comme une capacité de ressource.
Les utilisateurs soumettent les tâches au CMS de manière dynamique, qui sont stockées dans une file d’attente de tâches. Le statut est à l’état submitted (1).
Il reçoit les demandes entrantes de l’utilisateur et envoie les demandes au classificateur de type de tâche pour l’identifier. Le statut est à l’état waiting (2).
Le classificateur de type de tâche dans le CMS permet de classer les demandes entrantes en trois types de ressources différents. : routeurs, machines virtuelles de type LXC et de type KVM. Pour identifier le type de ressource correspondante, une demande est décrite comme suit :
✓ Type routeurs = <Nombre de routeur, type de routeur, durée de bail>
✓ VM de type LXC = <Nom du service, durée de bail>
✓ VM de type KVM = <Nom du VM, Nombre de CPU, Nombre de RAM, Taille du
Disque, durée de bail>
Généralement, une demande se compose du type de service, des caractéristiques et l’horodatage qui contient la date et l’heure (durée de bail).
Étant donné qu’il s’agit d’exigences distinctes pour chaque type de tâches, les caractéristiques de la demande peuvent être utilisé pour identifier le type de tâches soumis et la tâche sera en attente d’allocation. Le statut est à l’état ready (2). Le CMS doit se réfère et utiliser les informations sur les ressources disponibles du DC grâce au système d’informations. Le statut est à l’état verified (3).
|
Table des matières
Liste des Figures
Liste des Tableaux
Liste des Acronymes
CHAPITRE I : PRESENTATION ET CONTEXTE
I.1. Introduction
I.2. Contexte
I.3. Problématique
I.4. Objectifs
CHAPITRE II : ETAT DE L’ART SUR LES ALGORITHMES D’ORDONNANCEMENTS
II.1. Définitions et concept de base
II.2. Algorithmes d’ordonnancements
II. 2.1. Algorithmes d’ordonnancements statiques
II. 2.2. Algorithmes d’ordonnancements dynamiques
II. 2.3. Domaine d’utilisation
II.3. Etude comparative des algorithmes d’ordonnancements de VMs
II. 3.1. En fonction du débit (throughput)
II. 3.2. En fonction du MakeSpan et du Reponse Time
II. 3.3. En fonction du Deadline
II. 3.4. En fonction du MakeSpan
CHAPITRE III : PROPOSITION D’UN ALGORITHME D’ORDONNANCEMENT DE VMs
III.1. Modèle de système proposé
III.1.1. Le Datacenter
III.1.2. Le Control Management System
III.1.3. Le Système d’information
III.1.4. Les utilisateurs
III.2. Principe et fonctionnement de notre modèle
III.3. Architecture proposée
III.4. Maquette de test
III.5. Implémentation
III.5.1. Mise en place de Proxmox Virtual Environnement
III.5.2. Mise en place de Dynamips/Dynagen
III.5.3. Conception de l’outils d’administration
III.5.4. Intégration
III.5.5. Tests et Validation
CONCLUSION GENERALE ET PERSPECTIVES
BIBLIOGRAPHIE
WEBOGRAPHIE
Télécharger le rapport complet
