Thèse de Doctorat

DEPARTEMENT D'INFORMATIQUE
THESE
Présentée par
D J E B B AR E s m a I n s a f
Pour obtenir
LE DIPLOME DE DOCTORAT EN SCIENCES
Filière: Informatique
Spécialité: Systèmes Informatiques Répartis
OPTIMISATION D’ORDONNANCEMENT ET D’ALLOCATION

DE RESSOURCES DANS LES CLOUD COMPUTING
Soutenue le : 05 / 12 / 2016
Devant les membres du jury :
Directeur de thèse : BELALEM Ghalem Professeur, Université d’Oran 1, Ahmed Ben Bella
Président : HAFFAF Hafid Professeur, Université d’Oran 1, Ahmed Ben Bella

Examinateurs : AMINE Abdelmalek Professeur, Université Tahar Moulay de Saida
EL BERRICHI Zakaria Professeur, Université Djillali Liabes, Sidi Bel-Abbes
FARAOUN Mohamed Kamel Professeur, Université Djillali Liabes, Sidi Bel-Abbes
GUEZOURI Mustapha Professeur, Université d'Oran1, Ahmed Ben Bella
i
Les savants des temps passés et des nations révolues n’ont cessé de composer des
livres. Ils l’ont fait pour léguer leur savoir à ceux qui les suivent.
Ainsi demeurera vive la quête de la vérité.
Al-Khwarizmi
ii
Dédicaces
À ma famille et mes parents

À mon frère, mes sœurs et ma nièce Anfel
À mes amies et mes collègues
À tous ceux qui m’ont encouragé et aidé
iii
Remerciements
e remercie Allah de m’avoir donner le courage et la volonté ainsi que la conscience

J et la patience d’avoir pu terminer ma thèse de Doctorat.
Je tiens à exprimer mes vifs remerciements à mon encadreur Mr Pr. Belalem

Ghalem pour m’avoir donner l’opportunité de réaliser ce sujet sous sa direction, la
confiance faite ainsi que ses conseils fructueux, et son temps consacré tout au long
du travail.
Je tiens à remercier Mr Pr. Haffaf Hafid d’avoir accepté d’être notre président de
jury ainsi qu’aux membres Mr Pr. El Berrichi Zakaria, Mr Pr. Amine AbdelMalek,
Mr Pr. Faraoun Mohamed Kamel et Mr Pr. Guezouri Mustapha qui nous honorent
de leurs présences en tant qu’examinateurs.
Ces remerciements seraient incomplets, si je n’en adressais pas à l’ensemble des

membres du laboratoire d’informatique de l’université d’Oran1 LIO.
Enfin, un merci particulier à tous ce qui m’ont soutenu de près ou de loin par
leurs soutiens et encouragements.
Résumé
Le Cloud computing est une technologie de calcul et de stockage naissante qui se

consolide rapidement comme une grande étape dans le développement et le déploie-
ment d’un nombre croissant des applications réparties. L’ordonnancement de tâches
et d’allocation de ressources dans les systèmes de type Cloud computing suscite une
attention croissante avec l’augmentation de la popularité de Cloud. Dans les travaux
de cette thèse, nous proposons trois stratégies d’ordonnancement et d’allocation de
ressources, la première stratégie d’ordonnancement est basée sur la réplication des
données pour les workflows scientifiques, la seconde stratégie d’ordonnancement se
focalise sur le groupement de tâches et la dernière stratégie d’ordonnancement de
tâches et d’allocation de ressources est destinée aux Big data. Nos propositions
permettent de réduire le temps de réponse moyen des tâches, de diminuer le dépla-
cement des données pour les applications scientifiques, et de réduire le coût global
d’utilisation de ressources.
Mots clés : Cloud computing, ordonnancement des tâches, allocation des res-
sources, workflows, groupement de tâches, Big data.
Abstract
Cloud computing is an emerging computing and storage technology that is ra-

pidly consolidating as a great step in the development and deployment of an increa-
sing number of distributed applications. The task scheduling and resource allocation
in Cloud computing systems are receiving increasing attention with the rise in the
popularity of Cloud. In this work, we propose three strategies of scheduling and
resource allocation, the first scheduling strategy based on the replication of data
for scientific workflows, the second scheduling strategy is based on the grouping of
tasks and the latest strategy of task scheduling and resource allocation is intended
for the big data. Our strategies reduce the average response time of tasks, minimize
data movement for scientific applications, and reduce the overall cost of resource
usage.
Keywords : Cloud computing, tasks scheduling, ressource allocation, work-
flows, tasks grouping, Big data.
TABLE DES MATIÈRES
1 Introduction 4
1.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Problématique et motivation . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Organisation de la thèse . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Cloud computing 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Les concepts du Cloud computing . . . . . . . . . . . . . . . . . . . . 10
2.2.1 La virtualisation . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 La grille informatique . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 L’informatique utilitaire (Utility computing) . . . . . . . . . 14
2.3 Les technologies connexes liées au Cloud computing . . . . . . . . . 14
2.4 Les principales caractéristiques des Clouds . . . . . . . . . . . . . . . 14
2.5 Modèles de déploiement . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.6 Modèles de service . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6.1 SaaS (Software as a Service) . . . . . . . . . . . . . . . . . . 18
2.6.2 IaaS (Infrasture as a Service) . . . . . . . . . . . . . . . . . . 19
2.6.3 PaaS (Platform as a Service) . . . . . . . . . . . . . . . . . . 19
2.7 Aborder un projet de migration vers le Cloud . . . . . . . . . . . . . 20
2.8 Avantages du Cloud computing . . . . . . . . . . . . . . . . . . . . . 21
2.8.1 Avantages au niveau de la stratégie . . . . . . . . . . . . . . . 21
2.8.2 Avantages au niveau des fonctions et des processus métier . . 22
2.8.3 Avantages opérationnels . . . . . . . . . . . . . . . . . . . . . 23
2.9 Sécurité dans les Cloud computing . . . . . . . . . . . . . . . . . . . 24
2.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Problème d’ordonnancement et d’allocation de ressources 27

TABLE DES MATIÈRES vi
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Ordonnancement : Concepts et définitions . . . . . . . . . . . . . . . 28
3.3 Les problèmes d’ordonnancement en ligne et hors ligne . . . . . . . . 30
3.4 Les critères d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 L’ordonnancement et la virtualisation dans le Cloud computing . . . 33
3.6 Les principaux algorithmes d’ordonnancement . . . . . . . . . . . . . 35
3.7 Les algorithmes d’ordonnancement pour les applications scientifiques 38
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 Stratégies d’ordonnancement et d’allocation de ressources pour les

Clouds scientifiques 44
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Stratégie d’ordonnancement basée sur la réplication de données . . . 45
4.2.1 Étape de construction . . . . . . . . . . . . . . . . . . . . . . 47
4.2.2 Étape d’exécution . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.3 Service de gestion de réplication dynamique . . . . . . . . . . 60
4.3 Stratégie d’ordonnancement basée sur le groupement de tâches . . . 63
4.3.1 Etape de construction . . . . . . . . . . . . . . . . . . . . . . 64
4.3.2 Étape d’ordonnancement . . . . . . . . . . . . . . . . . . . . 66
4.4 Stratégies d’ordonnancement et d’allocation de ressources pour les
Big Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4.1 La première variante OADTV . . . . . . . . . . . . . . . . . . 67
4.4.2 La deuxième variante OAAMV . . . . . . . . . . . . . . . . . 69
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Expérimentation et évaluation 75
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Langage et environnements de travail . . . . . . . . . . . . . . . . . . 76
5.2.1 Langage de programmation Java . . . . . . . . . . . . . . . . 76
5.2.2 Environnements de développement . . . . . . . . . . . . . . . 76
5.3 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . 79
TABLE DES MATIÈRES vii
5.3.1 Résultats expérimentaux 1 : Stratégie d’ordonnancement ba-

sée sur la réplication de données . . . . . . . . . . . . . . . . 79
sée sur le groupement de tâches . . . . . . . . . . . . . . . . . 88
5.3.3 Résultats expérimentaux 3 : Stratégies d’ordonnancement et
d’allocation de ressources pour les Big Data . . . . . . . . . . 92
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6 Conclusion générale 99
Bibliographie 102
A Simulateurs de Cloud computing 111

A.1 Simulateur CloudSim [12] . . . . . . . . . . . . . . . . . . . . . . . . 111
A.2 EMUSIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
A.3 Simulateur GreenCloud . . . . . . . . . . . . . . . . . . . . . . . . . 113
A.4 Simulateur GroudSim . . . . . . . . . . . . . . . . . . . . . . . . . . 114
A.5 iCanCloud [60] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
B Simulateur CloudSim : Développement et expérimentation 116

B.1 Architecture détailléé de CloudSim . . . . . . . . . . . . . . . . . . . 116
B.2 Modélisation du Cloud . . . . . . . . . . . . . . . . . . . . . . . . . . 117
B.3 Politiques d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . 119
B.3.1 Étape pour définir la politique SPACE SHARED . . . . . . . 119
B.3.2 Étape pour définir la politique TIME SHARED . . . . . . . . 120
Table des figures
2.1 L’environnement de Cloud computing [66] . . . . . . . . . . . . . . . 11

2.2 La virtualisation dans les environnements de Cloud [31] . . . . . . . 13
2.3 L’évolution vers le Cloud computing dans l’hébergement d’applica-
tions logicielles [75] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Les modèles de déploiement dans le Cloud computing . . . . . . . . 17
2.5 Les modèles de services dans le Cloud computing [32] . . . . . . . . 17
3.1 Le résultat d’exécution des tâches selon Min-min . . . . . . . . . . . 36

3.2 Le résultat d’exécution des tâches selon Max-min . . . . . . . . . . . 37
3.3 L’exécution de plusieurs workflows sur plusieurs Clouds [22] . . . . . 39
4.1 Vue globale de la stratégie utilisée . . . . . . . . . . . . . . . . . . . 46

4.2 Diagramme d’activité de la phase de mise en place et clusterisation
de la matrice de dépendance . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Diagramme d’activité pour le partitionnement de la matrice de dé-
pendance clusterisée . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4 Diagramme d’activité de la phase de partitionnement et distribution
des datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5 Diagramme d’activité de la phase d’ordonnancement et exécution des
tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.6 Diagramme d’activité pour la gestion des datasets générés avec l’al-
gorithme des K-means . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.7 Diagramme d’activité pour la phase de la réplication dynamique . . 63
4.8 Exemple de construction de la matrice de dépendance T M . . . . . 64
4.9 Exemple d’application de l’algorithme BEA sur la matrice de dépen-
dance T M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.10 Exemple de découpage de la matrice de dépendance clusterisée . . . 65
4.11 Exemple d’affectation et d’ordonnancement des tâches dans l’en-
semble des Datacenters . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Table des figures ix
4.12 Affectation et ordonnancement des tâches . . . . . . . . . . . . . . . 66

4.13 La première variante OADTV d’ordonnancement et d’allocation de
ressources dans les Cloud computing . . . . . . . . . . . . . . . . . . 68
4.14 La deuxième variante OAAMV d’ordonnancement et d’allocation de
ressources dans les Cloud computing . . . . . . . . . . . . . . . . . . 70
4.15 Le résultat d’exécution des tâches . . . . . . . . . . . . . . . . . . . . 73
5.1 Les principales classes de CloudSim [56] . . . . . . . . . . . . . . . . 79

5.2 Création d’un nouveau workflow . . . . . . . . . . . . . . . . . . . . 80
5.3 Déploiement de la matrice de dépendance . . . . . . . . . . . . . . . 81
5.4 Clusterisation de la matrice de dépendance . . . . . . . . . . . . . . 81
5.5 Partitionnement et distribution des données . . . . . . . . . . . . . . 82
5.6 Gestion des données générées . . . . . . . . . . . . . . . . . . . . . . 82
5.7 Le temps de réponse moyen . . . . . . . . . . . . . . . . . . . . . . . 84
5.8 Le gain obtenu pour le temps de réponse . . . . . . . . . . . . . . . . 84
5.9 Le nombre de déplacement des données . . . . . . . . . . . . . . . . 85
5.10 Le gain obtenu pour le déplacement des données . . . . . . . . . . . 86
5.11 Le coût de la réplication . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.12 Le gain obtenu pour le coût de la réplication . . . . . . . . . . . . . 87
5.13 Le coût global engendré . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.14 Le temps de réponse moyen . . . . . . . . . . . . . . . . . . . . . . . 90
5.15 Le temps de réponse moyen pour des tâches>=100 . . . . . . . . . . 90
5.16 Le coût de traitement moyen des Cloudlets . . . . . . . . . . . . . . 91
5.17 Le coût de traitement moyen pour des tâches>=100 . . . . . . . . . 92
5.18 Le résultat de temps de réponse dans l’exécution des tâches . . . . . 94
5.20 Le résultat de temps de réponse pour l’exécution des tâches . . . . . 95
5.22 Le temps de réponse moyen des Cloudlets . . . . . . . . . . . . . . . 97
5.23 Le coût moyen d’utilisation de ressources . . . . . . . . . . . . . . . 97
A.1 Organisation interne EMUSIM . . . . . . . . . . . . . . . . . . . . . 113

Table des figures x
A.2 Architecture GreenCloud . . . . . . . . . . . . . . . . . . . . . . . . 114

A.3 Architecture iCanCloud [60] . . . . . . . . . . . . . . . . . . . . . . . 115
B.1 Architecture de Cloudsim [12] . . . . . . . . . . . . . . . . . . . . . . 117

B.2 Effets des politiques d’ordonnancements sur l’exécution des tâches :
(a) Space-shared for VMs and Tasks, (b) Space-share for VMs and
Time-shared for tasks, (c) Time-shared for VMs, Space-shared for
tasks, and (d) Time-shared for both VMs and Tasks . . . . . . . . . 121
Liste des tableaux
3.1 Le temps d’exécution des tâches (Algorithme Min-min) . . . . . . . 36

3.2 Comparaison entre les algorithmes d’ordonnancement des workflows 41
4.1 Valeurs de λini par rapport aux types d’applications . . . . . . . . . 52
5.1 Les paramètres de simulation pour le temps de réponse . . . . . . . . 83

5.2 Les paramètres de simulation pour le nombre de déplacements . . . 85
5.3 Résultat de simulation de la première stratégie (OADTV) . . . . . . 93
5.4 Résultat de simulation de la deuxième stratégie (OAAMV) . . . . . 95
Glossaire
QoS : Quality of Service

NIST : National Institute of Standards and Technology
API : Application Programming Interface
IT : Information Technology, Internet Technology
CPU : Central Processor Unit
VPN : Virtual Private Network
SaaS : Software as a Service
PaaS : Platform as a Service
IaaS : Infrastructure as a Service
ROI : Return On Investment
DSI : Direction du système d’information
CSC : Conseil Service Collectivités
WAN : Wide Area Network
ISACA : Information Systems Audit and Control Association
CSA : Cloud Security Alliance
FAI : Fournisseur d’Accès à Internet
OTP : One Time Password (mot de passe à usage unique)
FCFS : First Come First Served
SJF : Short Job First
SLA : Service Level Agreement
HPC : High Performance Computer
UML : Unified Modeling Langage
FCFS : First Come First Served
FIFO : First In First Out
RR : Round Robin
DAG : Directed Acyclic Graph (graphe orienté acyclique)
Liste des travaux
1. Publications
Esma Insaf Djebbar, Ghalem Belalem and Merien Benadda. Task scheduling
strategy based on data replication in scientific Cloud workflows. Multiagent
and Grid Systems : An International Journal, vol. 12, no. 1, pages 55-67, 2016.
2. Conférences
Esma Insaf Djebbar and Ghalem Belalem. Optimization of Tasks Schedu-

ling by an Efficacy Data Placement and Replication in Cloud Computing.
In Algorithms and Architectures for Parallel Processing - 13th International Confe-
rence, ICA3PP 2013, Vietri sul Mare, Italy, December 18-20, 2013, Proceedings,
Part II, LNCS 8286, pages 22-29, 2013.
Esma Insaf Djebbar and Ghalem Belalem. Tasks Scheduling and Resource
Allocation for high Data Management in Scientific Cloud computing en-
vironment. The International Conference on Mobile, Secure and Programmable
Networking (MSPN’2016), Paris, France, LNCS 10026, June 1-3, 2016.
Esma Insaf Djebbar and Ghalem Belalem. An effective Task Scheduling

Strategy in multiple Data centers in Cloud Scientific Workflow. The 39th
International ICT Convention on Information and Communication Technology,
Electronics and Microelectronics (MIPRO 2016), Rijeka, Croatia, IEEE, pages 214-
217, May 30-June 3, 2016.
Liste des tableaux 3
3. Encadrements
Mokhtari Houari, Mederrek Ali et Aissa Berroudja Youssouf. Un algorithme

d’ordonnancement des tâches dans les Cloud computing, École Normale Su-
périeure d’Enseignement Technologique d’Oran, Licence d’enseignement secondaire
en Informatique, 2015.
Boudjenah Khadidja, Chermak Saâdia et Drief Merièm Programmation pa-
rallèle des tâches dans les Cloud computing, École Normale Supérieure d’En-
seignement Technologique d’Oran, Licence d’enseignement secondaire en Informa-
tique, 2016.
Chapitre 1
Introduction
Sommaire
1.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Problématique et motivation . . . . . . . . . . . . . . . . . . 5
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Organisation de la thèse . . . . . . . . . . . . . . . . . . . . . 8
1.1 Contexte
e Cloud computing ou informatique en nuage est une infrastructure dans la-

L quelle la puissance de calcul et le stockage sont gérés par des serveurs distants
auxquels les usagers se connectent via une liaison Internet sécurisée. L’ordinateur de
bureau ou portable, le téléphone mobile, la tablette tactile et autres objets connec-
tés deviennent des points d’accès pour exécuter des applications ou consulter des
données qui sont hébergées sur les serveurs. Le Cloud se caractérise également par
sa souplesse qui permet aux fournisseurs d’adapter automatiquement la capacité de
stockage et la puissance de calcul aux besoins des utilisateurs.
Le Cloud computing devient rapidement le standard de facto pour l’hébergement
et le fonctionnement des applications et des services logiciels à grande échelle sur
Internet. Beaucoup d’entreprises, d’individus et même des secteurs gouvernemen-
taux se tournent vers l’environnement de Cloud en raison de plusieurs avantages que
ce nouveau paradigme offre, y compris la réduction des coûts, l’évolutivité rapide,
la facilité de développement, le stockage illimité, et l’accessibilité omniprésente. En
utilisant le paradigme du Cloud, les consommateurs de Cloud peuvent être en me-
1.2. Problématique et motivation 5
sure de se concentrer davantage sur la fonctionnalité de l’application de base. Cloud

computing n’est pas une nouvelle technologie, mais une combinaison de technologies
existantes telles que le Web et la virtualisation. Par conséquent, toute vulnérabilité
dans l’une de ces technologies sous-jacentes peut être exploitée comme une attaque
de sécurité dans le Cloud.
La technologie de Cloud computing représente un nouveau paradigme pour la
fourniture de ressources informatiques. Ce paradigme facilite l’accès aux ressources
via le réseau pour réduire les coûts associés à la gestion des ressources matérielles
et logicielles. Il représente le rêve de longue date d’envisager l’informatique comme
un service où l’économie de principe à l’échelle aider à réduire efficacement le coût
des ressources informatiques. Le Cloud computing simplifie le temps d’approvi-
sionnement des processus de matériel, l’achat de matériel et le déploiement de la
consommation des logiciels. Par conséquent, il promet un certain nombre d’avan-
tages pour le déploiement d’applications de données intensives, telles que l’élasticité
des ressources, le modèle de coût de « pay-per-use », le faible temps sur le marché,
et la perception des ressources illimitées et l’évolutivité infinie. Par conséquent, il
devient possible, au moins théoriquement, d’obtenir un débit continu illimité en
ajoutant des moyens de calcul si la charge de travail augmente.
1.2 Problématique et motivation
Les systèmes de Cloud computing sont entrain de devenir une plate forme incon-
tournable pour les applications scientifiques. Ils permettent de faire l’allocation des
ressources informatiques. Lorsque ces ressources sont insuffisantes pour satisfaire
les demandes, des mécanismes d’ordonnancement sont nécessaires. Les problèmes
d’optimisation de tâches et d’allocation de ressources dans un contexte hétérogène
comme le Cloud sont des problèmes difficiles. Ce problème devient encore plus diffi-
cile lorsque les critères à prendre en considération pour l’optimisation sont multiples.
Les approches d’ordonnancement et d’allocation existantes sont souvent très corré-
lées, qui ne prennent en compte que quelques critères en même temps, et quelles
sont, le plus souvent, adaptées à des applications de données de taille moyenne et
1.2. Problématique et motivation 6
par conséquence ne passent pas à l’échelle.

La théorie d’ordonnancement de tâches et d’allocation de ressources dans les
systèmes de Cloud computing suscite une attention croissante avec l’augmentation
de la popularité de Cloud. En général, l’ordonnancement de tâches est le processus
d’affectation des tâches aux ressources disponibles sur la base des caractéristiques et
des conditions des tâches. C’est un aspect important dans le fonctionnement efficace
du Cloud, car de divers paramètres de tâches doivent être pris en considération pour
un ordonnancement approprié. Les ressources disponibles devraient être utilisées
efficacement sans affecter les paramètres de service du Cloud.
Les ressources cibles dans un environnement de Cloud peuvent être choisies selon
diverses algorithmes. La sélection des ressources peut être aléatoire, Round Robin,
ou gourmande (en capacité de traitement de la ressource et en temps d’attente) ou
par tous les autres moyens. La sélection des tâches peut être basée sur FCFS (First
Come First served), SJF (Short Job First), priorité, ou en groupement brute de
tâches. L’algorithme d’ordonnancement choisit la tâche à exécuter et la ressource
correspondante où on exécutera la tâche. Car chaque stratégie de sélection a un
certain bienfait et pourrait être effectuée dans cette direction pour extraire les points
avantageux de ces algorithmes et pour aboutir à une meilleure solution qui essaye
de réduire au minimum les inconvénients de l’algorithme résultant.
Les algorithmes existants sont bénéfiques aux utilisateurs ou aux fournisseurs
de service de Cloud, mais pas à tous les deux en même temps. Chacun a leurs
propres avantages et inconvénients. Comme l’ordonnancement gourmant ou basé sur
la priorité sont salutaires à l’utilisateur et l’ordonnancement basé sur un groupement
de tâches brutes est concerné par une meilleure utilisation des ressources disponibles
[10]. Mais l’ordonnancement basé sur la priorité peut mener au long temps d’attente
pour des tâches avec des basses priorités. L’ordonnancement gourmand du point de
vue d’utilisateurs mène au gaspillage des ressources, tandis que l’ordonnancement
gourmant de point de vue des fournisseurs de services peut mener à la déception
pour l’utilisateur sur les paramètres de qualité de service (QoS). De même, le groupe
de tâches peut avoir l’inconvénient du temps considérable d’accomplissement des
tâches dûs à la formation des groupes. Ainsi nous pouvons remarquer que quelques
1.3. Contributions 7
stratégies d’ordonnancement sont polarisées aux utilisateurs, tandis que d’autres

aux fournisseurs de services. Il y a une condition naissante à équilibrer ceci et qui
polarise pour former une solution d’ordonnancement.
Les nouvelles stratégies proposées doivent surmonter les problèmes posés par des
propriétés de réseau et des exigences d’utilisateur. Les nouvelles stratégies peuvent
employer certains concepts d’ordonnancement conventionnels pour les fusionner
avec quelques stratégies de réseau pour fournir la solution pour un meilleur et plus
efficace ordonnancement de tâches.
1.3 Contributions
Dans les travaux de cette thèse, nous proposons trois stratégies d’ordonnan-
cements, la première stratégie d’ordonnancement est basée sur la réplication des
données pour les workflows scientifiques, la seconde stratégie d’ordonnancement est
basée sur le groupement de tâches et la dernière stratégie d’ordonnancement de
tâches et d’allocation de ressources est destinée aux Big data. La première stratégie
comporte trois phases, nommées respectivement, l’étape de construction, l’étape
d’exécution et l’étape de réplication. La deuxième stratégie est basée sur le groupe-
ment de tâches, contient à son tour deux phases, nommées respectivement l’étape
de construction et l’étape d’ordonnancement. La troisième stratégie contient deux
sous stratégies, la première basée sur des paramètres d’optimisation de Cloud, tels
que la vitesse d’exécution des machines virtuelles et la longueur des tâches. La se-
conde est basée sur un arbre de construction des machines virtuelles. Ces travaux
visent, dans un premier temps, à réduire le temps de réponse et le temps d’attente
dans l’exécution des tâches. Ils visent, également, à minimiser le nombre de dépla-
cements de données entre les datacenters, ainsi que le coût engendré de l’utilisation
de ressources dans la technologie Cloud.
1.4. Organisation de la thèse 8
1.4 Organisation de la thèse
Le reste de la thèse est organisé comme suit : Dans le chapitre 2, nous présentons
les notions de base des concepts que nous jugeons nécessaires à la compréhension
du contenu de cette thèse. Nous présentons d’abord les concepts du Cloud com-
puting, ensuite, nous présentons les notions fondamentales, leurs interprétations,
ainsi que les services offerts par ce nouveau concept. Enfin, nous terminons ce cha-
pitre par une discussion sur les menaces majeures à la sécurité des données et à
celles des applications en Cloud. Dans le troisième chapitre, les concepts liés à l’or-
donnancement et l’allocation de ressources dans le Cloud computing sont abordés,
ainsi que quelques travaux réalisés dans ces domaines. Le quatrième chapitre est
destiné à la conception de nos contributions en prenant en compte la gestion de
l’ordonnancement des tâches et l’allocation de ressources. Le cinquième chapitre
s’appesantit, en premier lieu à la concrétisation de la conception présentée en cha-
pitre 4, et en second lieu à l’affichage de quelques résultats d’expérimentation et
leurs interprétations. Le chapitre 6 synthétise cette thèse par une conclusion qui
discute les contributions réalisées dans le cadre de nos travaux de thèse, ainsi que
des perspectives des travaux futurs envisagées.
Chapitre 2
Cloud computing
Sommaire
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Les concepts du Cloud computing . . . . . . . . . . . . . . . 10
2.2.1 La virtualisation . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 La grille informatique . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 L’informatique utilitaire (Utility computing) . . . . . . . . . . 14
2.3 Les technologies connexes liées au Cloud computing . . . . 14
2.4 Les principales caractéristiques des Clouds . . . . . . . . . . 14
2.5 Modèles de déploiement . . . . . . . . . . . . . . . . . . . . . 16
2.6 Modèles de service . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6.1 SaaS (Software as a Service) . . . . . . . . . . . . . . . . . . . 18
2.6.2 IaaS (Infrasture as a Service) . . . . . . . . . . . . . . . . . . . 19
2.6.3 PaaS (Platform as a Service) . . . . . . . . . . . . . . . . . . . 19
2.7 Aborder un projet de migration vers le Cloud . . . . . . . . 20
2.8 Avantages du Cloud computing . . . . . . . . . . . . . . . . . 21
2.8.1 Avantages au niveau de la stratégie . . . . . . . . . . . . . . . . 21
2.8.2 Avantages au niveau des fonctions et des processus métier . . . 22
2.8.3 Avantages opérationnels . . . . . . . . . . . . . . . . . . . . . . 23
2.9 Sécurité dans les Cloud computing . . . . . . . . . . . . . . . 24
2.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1 Introduction
’informatique dans le nuage est plus connue sous sa forme anglo-saxonne :

L « Cloud Computing », mais il existe de nombreux synonymes francophones
2.2. Les concepts du Cloud computing 10
tels que : « informatique dans les nuages », « infonuagique » (Québec) ou encore

« informatique dématérialisée ». C’est un domaine qui regroupe les technologies
de distribution, à la demande et via Internet, de services informatiques logiciels
et matériels. L’idée principale de ces technologies est de distribuer des ressources
informatiques comme un service d’utilité publique, conformément à ce qui avait été
imaginé par les pionniers de l’informatique moderne, il y a plus de 40 ans [25]. Ce
principe de distribution publique de ressources informatiques anime également la
communauté de la grille informatique, si bien qu’il est parfois difficile de distinguer
la frontière entre « Grille » et « Informatique dans le nuage ». Cette difficulté est
d’autant plus réelle que l’informatique dans les nuages, est un concept jeune, dont
les premières implantations datent de 2006, et dont le développement s’est accéléré
durant ces dernières années.
Dans ce chapitre, nous allons présenter globalement l’historique du « Cloud
computing » et l’origine de ce terme, suivi d’une définition explicite de ce dernier qui
sera basée sur une analyse des définitions proposées par le monde académique. Nous
décrivons aussi la virtualisation qui est une partie essentielle dans « l’informatique
en nuages », sans oublier les services de Cloud, les types de Cloud et ses acteurs
ainsi que les avantages, les inconvénients, les objectifs principaux et les domaines
d’utilisation du Cloud computing.
2.2 Les concepts du Cloud computing
Il y a une certaine confusion dans même l’esprit d’analyse des praticiens expé-
rimentés sur ce que constitue le Cloud computing et ce qui est le partage en temps
ou tout simplement une grande collection de serveurs distants. Cette confusion est
aggravée par un grand nombre de fournisseurs de services qui prétendent donner le
meilleur et le moins cher pour le calcul dans le nuage sans élucider comment cela
est différent de la génération de l’informatique [11, 64]. Puisque nous croyons que le
Cloud computing est plus qu’un mot à la mode, nous reproduisons ici la définition
du Cloud computing par le NIST réputé [46]. Selon l’Institut national des normes
et de la technologie, Cloud computing est un modèle pour permettre un accès pra-
tique à la demande du réseau à un ensemble partagé de ressources informatiques

configurables (par exemple, les réseaux, les serveurs, le stockage, les applications
et les services) qui peuvent être provisionnés rapidement et libérés avec un effort
de gestion minimale ou par l’interaction de fournisseur de services (Figure 2.1). Ce
modèle favorise l’accessibilité et est composé de cinq caractéristiques essentielles
[46] :
Figure 2.1 – L’environnement de Cloud computing [66]
1. La demande libre des services
2. Un accès en diffusion via le réseau
3. La mise en commun des ressources
4. L’élasticité rapide
5. Un service mesuré
Trois modèles de services (SaaS, PaaS et IaaS) et, quatre modèles de déploiement
(privé, public, communautaire et hybride). Les technologies clés comprennent :
1. Des réseaux rapides,
2. Des ordinateurs bon marché,

3. La virtualisation pour du matériel de base.
Les principaux obstacles à la plus large adoption du Cloud sont :

– La sécurité, l’interopérabilité et la portabilité.
Nous résumons en termes simples et courts, le Cloud computing est une grande
puissance évolutive et personnalisée de calcul disponible par loyer/ par heure et
accessible à distance. Il peut aider à faire plus de calcul à une fraction de coût.
2.2.1 La virtualisation
La virtualisation est une technologie qui isole et fait abstraction des ressources
de bas niveau et fournit des ressources virtualisées pour des applications de haut
niveau. Dans le contexte de virtualisation matérielle, le détail de matériel physique
peut être résumé dans la distance basée sur le noyau de la machine virtuelle avec
le support des hyperviseurs tels que Linux [49, 50]. Un serveur virtualisé géré par
l’hyperviseur est communément appelé une machine virtuelle. En général, plusieurs
machines virtuelles peuvent être extraites dans une seule machine physique. Avec
des grappes de machines physiques, les hyperviseurs sont capables d’extraire et de
la mise en commun des ressources, ainsi que l’affectation dynamique ou l’affectation
des ressources aux machines virtuelles à la demande. Par conséquent, la virtualisa-
tion constitue la base du Cloud computing. Les fournisseurs peuvent personnaliser
la plate-forme pour répondre aux besoins des clients, soit par des applications expo-
sant en cours d’exécution au sein de machines virtuelles des services, ou de fournir
un accès direct aux machines virtuelles permettant ainsi aux clients de créer des
services avec leurs propres applications. En outre, le Cloud computing est non seule-
ment basé sur la virtualisation de ressources, mais aussi sur la répartition intelligente
des ressources pour la gestion des demandes concurrentes de ressources des clients.
La Figure 2.2 illustre une exploitation de la technologie de virtualisation dans les
environnements de Cloud computing.
L’informatique autonome ou encore le Computing autonome vise à construire
des systèmes informatiques capables à l’autogestion, ce qui signifie être capable de
fonctionner dans des conditions générales définies et règlementaires sans interven-
Figure 2.2 – La virtualisation dans les environnements de Cloud [31]
tion humaine. Le but de l’informatique autonome est de surmonter la complexité

croissante et rapide de la gestion du système informatique, tout en étant en mesure
de continuer à augmenter l’interconnectivité et l’intégration sans relâche. Bien que
le Cloud computing présente certaines similitudes avec l’automatique de calcul de
la façon dont il inter-connexe et intègre la distribution des centres de données à
travers les continents. Son objectif est de réduire le coût des ressources plutôt que
de réduire la complexité du système.
2.2.2 La grille informatique
Grid computing est un paradigme de calcul distribué qui coordonne en réseau

les ressources pour atteindre un objectif commun de calcul. Le développement de
la grille informatique a été tirée par les applications scientifiques qui nécessite ha-
bituellement un calcul intensif, mais les applications nécessitant le transfert et la
manipulation d’une quantité massive de données a également été en mesure de tirer
parti des grilles. Le Cloud computing semble être similaire à la grille informatique
dans la façon dont il a également employé les ressources distribuées pour atteindre
les objectifs au niveau de l’application. Cependant, le Cloud computing prend un
2.3. Les technologies connexes liées au Cloud computing 14
peu plus loin en mettant à profit les technologies de virtualisation pour atteindre
le partage à la demande des ressources et le provisionnement dynamique des res-
sources.
2.2.3 L’informatique utilitaire (Utility computing)
L’informatique utilitaire représente le modèle d’affaires des ressources d’em-

ballage en tant que services comptés similaires à ceux fournis par les entreprises
traditionnelles d’utilité publique. En particulier, il permet aux ressources d’appro-
visionnement sur les clients à la demande et à la charge basé sur l’utilisation plutôt
que sur un taux forfaitaire. Le principal avantage de l’informatique utilitaire est
l’économie. Le Cloud computing peut être perçu comme une réalisation de l’infor-
matique utilitaire. Avec un approvisionnement à la demande des ressources et de la
tarification fondée sur l’utilité, les clients sont en mesure de recevoir davantage de
ressources pour gérer les pics inattendus et ne payer que pour les ressources dont ils
avaient besoin ; Pendant ce temps, les fournisseurs de services peuvent maximiser
l’utilisation des ressources et minimiser leurs coûts d’exploitation.
2.3 Les technologies connexes liées au Cloud computing
Le Cloud computing a évolué sur des décennies de recherche dans différentes

technologies, dont il a hérité des caractéristiques et des fonctionnalités telles que
les environnements virtualisés, le computing autonome, la grille informatique, et le
calcul distribué. La Figure 2.3 illustre l’évolution vers le Cloud computing dans l’hé-
bergement des applications logicielles [75]. En fait, le Cloud computing est souvent
comparé aux technologies connexes, dont chacun partage certains aspects avec le
Cloud computing.
2.4 Les principales caractéristiques des Clouds
Le modèle Cloud Computing se différencie par les cinq caractéristiques essen-

tielles suivantes :
2.4. Les principales caractéristiques des Clouds 15
Figure 2.3 – L’évolution vers le Cloud computing dans l’hébergement d’applica-

tions logicielles [75]
1. Accès réseau universel : Un environnement de type Cloud Computing

est accessible via le réseau, quel que soit le périphérique (PC, Mac, tablette,
SmartPhone, ...).
2. Mise en commun (Pooling) de ressources : Dans un environnement de

type Cloud Computing, on ne pense pas en nombre de serveurs, taille de
disques, nombre de processeurs..., mais en puissance de calcul, capacité totale
de stockage, bande passante disponible.
3. Elasticité : Grâce au Cloud, il est possible de disposer de plus de ressources

très rapidement pour soutenir une forte demande (par exemple pour garantir
une bonne expérience d’achat sur une plateforme web d’e-commerce durant
les fêtes de fin d’années). Inversement, au-delà de la provision de ressources,
il est possible avec le Cloud de diminuer les ressources utilisées (par exemple
en cas de baisse d’activité sur cette même plateforme web d’e-commerce) si
celles-ci sont supérieures à ce qui est nécessaire.
4. Libre-service (Self-Service) : Dans un environnement de type Cloud Com-

puting, il est possible à un utilisateur de consommer les services ou les res-
2.5. Modèles de déploiement 16
sources sans pour autant nécessiter une demande d’interventions auprès du

fournisseur : équipe IT ou fournisseur externe (par exemple, un développeur
qui souhaite tester son application sur une machine virtuelle représentative
d’un poste standardisé de son entreprise peut, au travers d’un portail web,
provisionner ou utiliser une machine).
5. Service mesurable ou facturable : Dans un environnement de type Cloud

Computing, le fournisseur de la solution est capable de mesurer de façon pré-
cise la consommation des différentes ressources (CPU, stockage, bande pas-
sante, ...) ; cette mesure lui permet de facturer à l’usage le client [7].
2.5 Modèles de déploiement
Il existe 4 modèles de déploiement du Cloud computing (voir Figure 2.4) :
1. Le Cloud privé qui peut se déployer sous deux formes distinctes :
Cloud privé interne : hébergé par l’entreprise elle-même, parfois partagé

ou mutualisé en mode privatif avec les filiales.
Cloud privé externe : hébergé chez un tiers, il est entièrement dédié à l’en-
treprise et accessible via des réseaux sécurisés de type VPN (Réseau
virtuel privé).
2. Le Cloud public est accessible par Internet et géré par un prestataire externe.
Il est ouvert au public ou à de grands groupes industriels. Cette infrastructure
est possédée par une organisation qui vend des services Cloud.
3. Le Cloud hybride ou mixte associe l’utilisation, pour une même entreprise,

d’un Cloud privé et d’un Cloud public. Ces infrastructures sont liées entre
elles par la même technologie qui autorise la portabilité des applications et
des données.
4. Le Cloud communautaire est dédié à une communauté professionnelle spéci-

fique incluant partenaires, sous-traitants, etc, pour travailler de manière colla-
borative sur un même projet ou Cloud gouvernemental dédié aux institutions
étatiques.
2.6. Modèles de service 17
Figure 2.4 – Les modèles de déploiement dans le Cloud computing
2.6 Modèles de service
Il existe trois types de services dans les Cloud computing : IaaS (Infrastructure
as a Service), PaaS (Plateform as a Service) et SaaS (Software as a Service), comme
il est montré dans la Figure 2.5.
Figure 2.5 – Les modèles de services dans le Cloud computing [32]
Fondamentalement, l’infrastructure en tant que service permet d’embaucher un ser-

veur virtuel, puis l’utiliser par le biais d’un navigateur. Il est comme une machine
distante qui vous permet de faire l’installation de logiciel et l’élargissement du ma-

tériel. La plate-forme en tant que service fournit une plate-forme à l’utilisateur sans
se soucier de la gestion du matériel, mais tout simplement le contrôle de logiciel.
Le logiciel en tant que service signifie essentiellement que le logiciel est loué par le
consommateur, mais est hébergé et entièrement géré par le prestataire.
– Exemples de machines virtuelles IaaS : Windows Azure (https ://azure.microsoft.com/en-
us/), Amazon Web Services EC2 (http ://aws.amazon.com/ec2/), et Google
Compute Engine(https ://cloud.google.com/products/compute-engine/).
– Des exemples de PaaS sont Google App Engine (https ://developers.google.com/appengine),
la plate-forme Salesforce (http ://www.salesforce.com/platform/), et Amazon
AWS Elastic Beanstalk (http ://aws.amazon.com/elasticbeanstalk/)
– Des exemples de SaaS sont Gmail (messagerie) et Salesforce (CRM).
2.6.1 SaaS (Software as a Service)
Les clients de ce modèle sont aussi bien des utilisateurs personnels que des entre-
prises. Ce modèle de service correspond à celui que nous rencontrons communément
dans le Cloud public. Il dérive du monde des ASP (Application Service Provider)
qui se sont développés initialement dans le monde du Web. Pour beaucoup de per-
sonnes et d’utilisateurs [8], le Cloud se résume uniquement à cet aspect ! Ce modèle
représente l’accès à un service applicatif et à ses fonctionnalités associées. Tenons
comme exemples : Les réseaux sociaux, la messagerie personnelle, les applications
bureautiques et l’impression photo. Pour un public de masse, le fournisseur propose
des niveaux de service générique peu ou pas personnalisables. Ceci lui permet de
proposer des prix attractifs d’entrée de gamme. Une politique de prix d’entrée de
gamme, des niveaux de service quelques fois flous ou des clients en manque de ma-
turité peuvent poser des soucis de contractualisation et d’engagement. Ce point est
crucial pour les enjeux du Cloud.
2.6.2 IaaS (Infrasture as a Service)
Généralement, l’utilisateur final ne se voit pas offrir ce genre de service. Ce

modèle sert de base pour construire ou rénover des solutions informatiques. Ce type
de service se démocratie toutefois dans le Cloud public. Pour déployer un service
applicatif, les architectures de systèmes d’information considèrent un certain nombre
de couches :
– Le réseau ;
– Le stockage ;
– L’infrastructure physique (ou virtuelle) communément appelé un serveur ;
– L’hyperviseur pour l’infrastructure dite virtuelle ;
– Le système d’exploitation du serveur physique ou de la machine/ serveur
virtuelle ;
– Le middleware ;
– L’applicatif lui même.
L’entreprise proposant ce type de service peut devenir, de fait, un fournisseur de
serveurs. Ces serveurs autrefois physiques sont devenus de nos jours virtuels par
le fait des technologies de virtualisation employées. La Direction du Système d’In-
formation (DSI) d’une organisation peut devenir un fournisseur de serveurs pour
ses clients en lieu et place des anciens fournisseurs de serveurs physiques que sont
les constructeurs. Le fournisseur/hébergeur peut devenir un fournisseur de serveur
pour les DSI [8].
2.6.3 PaaS (Platform as a Service)
La population cliente de ce type de service est composé de développement qui

vont pouvoir concevoir un service de type SaaS par exemple. Ce type de service se
rencontre aussi bien en Cloud public qu’en Cloud privé. Le modèle PaaS de Cloud
Computing ajoute, à la couche IaaS, la couche Middleware constituée de serveurs
d’application, de serveur de présentation (serveurs web), de systèmes de bases de
données et d’environnements de programmation. Prenons comme exemples : le dé-
ploiement d’un blog sur Internet, le développement Interne d’une solution n-tiers,
2.7. Aborder un projet de migration vers le Cloud 20
....
2.7 Aborder un projet de migration vers le Cloud
Les quatres points ci-dessous sont à prendre en considération avec les avantages
et les inconvénients de la situation actuelle sans Cloud jusqu’à la situation vers le
Cloud [7].
L’élasticié : L’agilité est définit comme la capacité d’une entreprise à ressentir les
changements dans son environnement et à s’y adapter de manière efficiente. Si
on s’en réfère à cette définition, l’avantage le plus fréquemment cité des archi-
tectures Cloud est, sans surprise, l’élasticité. Puisque cette notion fait partie
de la définition même du Cloud Computing. Par exemple, l’un des avantages
les plus évidents d’une solution SaaS comme Salesforce est l’élasticité qu’elle
permet. Il est possible très simplement d’augmenter le nombre d’utilisateurs
ou de fonctionnalités. Mais l’élasticité se ressent aussi très clairement sur la
couche IaaS.
La réactivité : L’élasticité, c’est bien, à condition que les modifications d’ampli-

tude à la hausse ou à la baisse soient rapides. Le gain en réactivité peut être
considérable par rapport aux solutions précédentes. Prenons comme exemple
le cas d’Intel : le simple passage en Cloud de son infrastructure a permis de
réduire de trois semaines à trois heures le temps nécessaire pour allouer des
ressources à un utilisateur en faisant la demande. Dans l’exemple d’Intel, le
gain en réactivité peut être considérable, par rapport aux solutions précé-
dentes sans Cloud.
La flexibilité : Quand on associe élasticité et réactivité, on obtient une souplesse

d’utilisation sans égale. Le Cloud remet les choses dans le bon sens : l’entre-
prise n’a plus besoin de se contorsionner pour faire évoluer son organisation
sans mettre en péril son service informatique ; c’est ce dernier qui se plie à
ses impératifs. La flexibilité dans l’organisation du travail est permise par le
fait aussi que l’entreprise peut être moins liée aux contraintes traditionnelles
de calcul de retour sur investissement (ROI) et de validation préalable. C’est
2.8. Avantages du Cloud computing 21
particulièrement vrai pour le SaaS. L’entreprise peut se permettre d’expéri-

menter, de passer au Cloud petit à petit car l’investissement et l’engagement
restent modéré. Contrairement à un projet informatique traditionnel, le ROI,
est calculé avant le démarrage. Le succès du projet se mesure au fil du temps,
dans la progression des usages [7].
L’ubiquité : Il y’a quelques années, un constructeur informatique vantait ses so-

lutions de mobilité avec le slogan : « travailler partout pour ne pas travailler
tout le temps ». Aujourd’hui, cette promesse est devenue une réalité grâce à
la dissociation totale entre la couche des usages et celle de la technique [7].
2.8 Avantages du Cloud computing
2.8.1 Avantages au niveau de la stratégie
Au niveau de la stratégie, de nombreuses entreprises s’appuient sur le Cloud

pour alimenter de nouvelles stratégies commerciales et chercher des sources concur-
rentielles. L’optimisation des ressources et les économies d’échelle augmentent en
théorie les marges. L’impact du Cloud sur la stratégie se manifeste notamment par
la création de nouveaux « business models », qui affectent tout l’écosystème de
l’entreprise. L’enjeu consiste à disposer des bonnes informations au bon moment
pour prendre les bonnes décisions. Cela passe par la mise en relation, le partage et
la combinaison de l’ensemble des actifs stratégiques de l’organisation. Pour l’heure,
les DSI sont limitées par les capacités techniques des solutions de Cloud, notamment
en termes de sécurité des informations et de portabilité des données. Néanmoins, la
direction générale s’interroge sur l’ensemble des opportunités stratégiques que les
solutions de Cloud pourraient apporter à l’entreprise. Comme souvent, ce sont les
solutions à usage personnel qui permettent au marché de se façonner et de s’orienter.
Par exemple, les solutions de webmail, comme Gmail de Google ou la messagerie
d’Apple, ont ouvert des perspectives très intéressantes pour les entreprises. Autre
exemple autour de la musique en ligne, l’offre iCloud d’Apple propose une fonction
appelée « iTunes Match », qui permet de stocker l’ensemble de sa musique et de ses
vidéos dans les nuages, et d’y accéder à partir de n’importe quelle plate-forme. Pour
que ces services voient le jour et soient appréciés du marché professionnel, il faut
donc qu’ils s’inscrivent dans une démarche de standardisation, d’élasticité et d’ubi-
quité (autrement dit qu’ils soient accessibles à partir de tout type de plate-forme :
PC, tablettes, smartphones, ...). L’analyse des données (notamment à très grande
échelle, voir le Big data) constitue également un domaine dans lequel les solutions
de Cloud sont très innovantes. Ainsi, Tetrapak [30], un fournisseur d’emballages et
de briques alimentaires, analyse des banques de données en provenance d’eBay pour
détecter les tendances de consommation. C’est également l’esprit de la solution Web
Content Management d’Adobe, classée comme leader par le Gartner [30] dans ce
domaine éponyme, qui propose tout un ensemble d’outils d’analyse marketing sur la
fréquentation d’un site web, pour mieux identifier et modéliser les comportements
des visiteurs et des acheteurs.
2.8.2 Avantages au niveau des fonctions et des processus métier
Au niveau des processus et des fonctions métier, les entreprises cherchent avant
tout la performance, le partage des ressources (afin d’accéder à des services aux-
quels elles ne pouvaient pas prétendre auparavant), une collaboration plus étroite,
davantage d’intégration, ainsi qu’une meilleure coordination interprocessus. Or les
solutions de Cloud computing favorisent la coordination des processus et des fonc-
tions du métier. D’ailleurs, certains des plus grands succès du Cloud computing
concernent à ce jour des solutions de collaboration, qui permettent aux groupes
et aux communautés de travailler ensemble de manière innovante. On peut citer
l’exemple des entreprises qui ouvrent leurs systèmes à leur clientèle en proposant
des services de calendriers en ligne : le client d’une banque peut ainsi fixer un rendez-
vous avec son conseiller clientèle en fonction des plages disponibles. Les solutions
de Social Business Software, ou de collaboration pour l’ensemble des acteurs de
l’entreprise, offrent également des perspectives intéressantes. Le cabinet de conseil
des services collectives (CSC) a déployé, par exemple, ce genre de solution pour
ses 90 000 collaborateurs. Lors de la première expérience qui a duré 20 semaines,
plus de 25 000 personnes se sont inscrites à cette solution de collaboration Cloud,
appelée C3 et éditée par Jive [30]. Ils ont créé plus de 2 100 groupes et géré jusqu’à
150 000 activités par mois. Ces résultats encourageants ont convaincu l’entreprise
d’adopter la solution C3 de façon permanente. Autre exemple, Expensify [30] est
une solution de Cloud SaaS qui permet de gérer les dépenses et les tickets de caisse
de toute une entreprise. Ce service est accessible depuis tous les types de plates-
formes (tablettes, smartphones, client léger, etc.) [30]. Grâce au Cloud computing,
les entreprises pourront désormais s’inscrire dans une démarche de standardisation
des applications, des formats de données, des plates-formes de développement et
d’exploitation, ce qui contribuera à la mise en œuvre de processus métier efficaces.
Ceux-ci favoriseront le partage d’information, l’accès universel depuis tout type de
plate-forme (notamment les tablettes et les smartphones) et la collaboration.
2.8.3 Avantages opérationnels
Les principaux avantages opérationnels qu’offre une solution de Cloud compu-

ting concernent la baisse des coûts de production des services informatiques, grâce
à la disponibilité et l’élasticité des ressources informatiques, ainsi qu’à des systèmes
de facturation portant sur la consommation réelle de services, par opposition aux
systèmes de forfaits (pour lequel le client paie, même s’il ne consomme rien). Les
DSI estiment qu’ils pourraient réaliser des économies de 10 à 50 % sur ces coûts
de production. Il s’agit en outre de commercialiser plus rapidement de nouvelles
applications et d’accélérer leur mise à jour. Les petites et moyennes entreprises, de
même que les startups, ont très vite adopté les solutions de Cloud computing. Elles
ont rapidement compris les avantages qu’elles pouvaient en tirer en termes d’éco-
nomies d’échelle et d’agilité : le Cloud leur offre l’accès à des prestations en libre
service et le partage d’équipements et de ressources, ce qui leur permet d’utiliser des
services réservés jusqu’à présent aux grandes entreprises. Les grandes entreprises,
elles, sont toujours plus réticentes dès qu’il s’agit d’adopter des nouvelles techno-
logies. Mais elles commencent à entrevoir l’avantage concurrentiel qu’elles peuvent
tirer des solutions de Cloud, notamment en termes de performance, d’efficacité et
d’efficience. Les entreprises industrielles traditionnelles s’appuient sur des modèles
scientifiques de l’organisation du travail. Ces modèles sont optimaux lorsqu’il s’agit
de faire fonctionner des machines ensemble. Or, les sociétés de services reposent sur
2.9. Sécurité dans les Cloud computing 24
la production de prestations par les hommes et pour les hommes [30]. Nous rappe-
lons que Taylor considérait l’être humain comme le prolongement de la machine. Il
s’agit donc de remettre l’homme au centre de la production de services et de prendre
en compte les dimensions sociales, psychologiques et culturelles des entreprises [30].
2.9 Sécurité dans les Cloud computing
Les avantages du Cloud computing sont aujourd’hui une évidence. Les plus no-
tables sont : la réduction des coûts de maintenance de l’infrastructure informatique,
la réduction de la consommation énergétique, la disposition rapide d’une plateforme
prête à l’emploi pour le déploiement des applications, la disposition d’une solution
de sauvegarde simple et accessible à tous, même aux non-informaticiens. Cependant,
devant toutes les possibilités offertes par ce nouveau concept de l’informatique, il
demeure des réticences dans son adoption. Ces réticences sont liées, pour la plupart,
au facteur de sécurité, qui reste encore un véritable challenge [56].
Le Cloud computing est une approche informatique qui consiste à exploiter
via Internet (ou tout autre réseau WAN) des ressources système et applicatives
(serveurs, stockage, outils de collaboration et d’administration, etc.). Ces ressources
distantes sont dites en Cloud. Plusieurs études menées par des spécialistes tels
que ISACA (Information Systems Audit and Control Association) et CSA (Cloud
Security Alliance) ont permis d’identifier douze points qui constituent les menaces
majeures à la sécurité des données et à celles des applications en Cloud [56]. Ce
sont notamment :
1. L’existence de brèches de sécurité tant sur l’une des couches logiques du Da-
tacenter que celles issues d’erreurs humaines ;
2. La fragilité dans la gestion des accès et des identités, bien que certains four-
nisseurs renforcent les interfaces d’authentification avec d’autres moyens tels
que les certificats, les smartcards, la technologie OTP et bien d’autres ;
3. L’utilisation d’API non sécurisées pour l’intégration des applications avec les
services Cloud ;
2.9. Sécurité dans les Cloud computing 25
4. L’exploit de vulnérabilités des systèmes d’exploitation sur les serveurs du

Cloud et même sur les applications hébergées ;
5. Le piratage de compte, qui est un vieux type d’attaque informatique, vient

avec une forte recrudescence depuis l’avènement d’Internet et encore celui du
Cloud computing ;
6. Une action malveillante initiée en interne dans les effectifs du fournisseur. Une
personne malveillante dans l’équipe de gestion du Datacenter peut facilement
nuire à la confidentialité et l’intégrité des environnements hébergés ;
7. Les menaces persistantes avancées (APT : Advanced Persistent Threats) qui

consistent en une forme d’attaque où le Hacker réussit à installer d’une façon
ou d’une autre un dispositif dans le réseau interne de l’organisation, à partir
duquel il peut extirper des données importantes ou confidentielles. C’est une
forme d’attaque difficile à détecter pour un fournisseur de services Cloud ;
8. La perte de données qui peut être causée par une attaque informatique (lo-
gique) du Datacenter, une attaque physique (incendie ou bombardement),
une catastrophe naturelle, ou même simplement à un facteur humain chez le
fournisseur de services, par exemple en cas de faillite de la société ;
9. Les insuffisances dans les stratégies internes d’adoption ou de passage au

Cloud. Les entreprises ou les organisations ne prennent pas souvent en compte
tous les facteurs de sécurité liés à leur fonctionnement avant de souscrire à
un service Cloud. Certaines négligences, tant au niveau du développement
d’application qu’au niveau de l’utilisation basique, leur sont parfois fatales ;
10. Utilisation frauduleuse des technologies Cloud en vue de cacher l’identité et

de perpétrer des attaques à grande échelle. Généralement, il s’agit de comptes
créés pendant les périodes d’évaluation (la plupart des fournisseurs d’accès
à Internet (FAI) proposent 30 jours d’essai gratuits) ou des accès achetés
frauduleusement ;
11. Le déni de service qui est une attaque qui consiste à rendre indisponible un
service par une consommation abusive des ressources telles que les processeurs,
la mémoire ou le réseau. L’idée, pour le pirate, c’est de réussir à surcharger les
2.10. Conclusion 26
ressources du Datacenter en vue d’empêcher d’autres utilisateurs de profiter

des services ;
12. Les failles liées à l’hétérogénéité des technologies imbriquées dans l’architec-
ture interne du Cloud, et l’architecture externe d’interfaçage avec les utilisa-
teurs.
2.10 Conclusion
Le développement du Cloud Computing passera certainement par son adoption

au sein des entreprises, pour qui les offres commencent à être nombreuses. La renta-
bilité étant l’objectif numéro 1, ces entreprises sont susceptibles de payer beaucoup
plus que les particuliers, et sont les cibles principales du Cloud, les offres gravitant
autour d’applications et d’environnements métier. Reste la question de la sécurité
et de la confidentialité des données stockées, qui sont potentiellement exposées à
des négligences.
Arriver à répondre de manière rapide et efficace aux demandes croissantes des
utilisateurs, les entreprises ou les fournisseurs de Clouds doivent améliorer constam-
ment les algorithmes d’exécution des tâches et améliorer la qualité de services. La
théorie d’ordonnancement de tâches et d’allocation de ressources dans les systèmes
de Cloud computing suscite une attention croissante avec l’augmentation de la po-
pularité de Cloud. Pour cela, le chapitre suivant entamera le problème d’ordonnan-
cement et d’allocation de ressources dans le Cloud computing.
Chapitre 3
Problème d’ordonnancement et
d’allocation de ressources
Sommaire
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Ordonnancement : Concepts et définitions . . . . . . . . . . 28
3.3 Les problèmes d’ordonnancement en ligne et hors ligne . . 30
3.4 Les critères d’optimisation . . . . . . . . . . . . . . . . . . . . 31
3.5 L’ordonnancement et la virtualisation dans le Cloud com-
puting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6 Les principaux algorithmes d’ordonnancement . . . . . . . . 35
3.7 Les algorithmes d’ordonnancement pour les applications
scientifiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1 Introduction
’informatique dans le nuage ou le Cloud computing est un nouveau modèle de

L prestation de service informatique utilisant de nombreuses technologies exis-
tantes. Comme toute nouvelle technologie, elle a besoin cependant de nombreuses
améliorations, et de la mise en place de normes précises pour éviter les risques.
L’ordonnancement des tâches et l’allocation de ressources sont souvent considérés
comme des vrais challenges pour les gestionnaires dans ce type de technologies. C’est
ainsi que de nombreux travaux ont été consacrés à la recherche des solutions pour
remédier à ces problèmes. Nous essayerons dans cette partie de présenter quelques
3.2. Ordonnancement : Concepts et définitions 28
notions et travaux de recherches qui ont proposé des solutions ou des améliorations
dans ce contexte.
3.2 Ordonnancement : Concepts et définitions
Le problème d’ordonnancement consiste à organiser dans le temps la réalisation

de tâches, compte tenu de contraintes temporelles (contraintes de délai, contraintes
d’enchaı̂nement, ...) et de contraintes portant sur l’utilisation et la disponibilité des
ressources requises [54, 63].
Ordonnancement : Un problème d’ordonnancement consiste à ordonner dans le

temps un ensemble de tâches contribuant à la réalisation d’un même projet.
L’objectif est de minimiser la durée de réalisation du projet compte tenu des
contraintes d’antériorité reliant les différentes tâches. De plus, on détermine
les calendriers de réalisation de chacune de ces tâches ainsi que les marges de
manœuvre associées.
Allocation de ressources : L’allocation de ressources est le processus de division

et de répartition d’une quantité limitée des ressources disponibles à des usages
alternatifs concurrents, satisfaisant des besoins illimités. Étant donné que la
pénurie est endémique dans le monde (désirs et besoins illimités, mais des res-
sources limitées), tous les besoins ne peuvent être satisfaits par les ressources
disponibles. Des choix doivent être faits. Ces choix et ces décisions sont le
processus d’allocation des ressources.
Dans le Cloud Computing, l’allocation de ressources est le processus d’attri-
bution des ressources disponibles pour les applications de Cloud Computing
sur Internet. L’allocation des ressources qui n’est pas gérée avec précision em-
pêche le bon fonctionnement des services. L’approvisionnement de ressources
résout ce problème en permettant aux fournisseurs de services de gérer les
ressources pour chaque application.
Les tâches : Une tâche ou un job est une entité élémentaire localisée dans le temps,
par une date de début et une date de fin, et dont la réalisation nécessite une
3.2. Ordonnancement : Concepts et définitions 29
durée préalablement définie. Elle est constituée d’un ensemble d’opérations

qui requiert, pour son exécution, certaines ressources et qu’il est nécessaire de
programmer de façon à optimiser un certain objectif.
Les ressources : La ressource est un moyen technique ou humain destiné à être

utilisé pour la réalisation d’une tâche et disponible en quantité limitée, sa
capacité. Plusieurs types de ressources sont à distinguer. Une ressource est
renouvelable si après avoir été allouée à une ou plusieurs tâches, elle est à nou-
veau disponible en même quantité (les hommes, les machines, l’équipement
en général) ; la quantité de ressource utilisable à chaque instant est limitée.
Dans le cas contraire, elle est consommable (matières premières, budget) ; la
consommation globale (ou cumul) au cours du temps est limitée. Une ressource
est doublement contrainte lorsque son utilisation instantanée et sa consom-
mation globale sont toutes deux limitées (l’argent en est un bon exemple).
Qu’elle soit renouvelable ou consommable, la disponibilité d’une ressource
peut varier au cours du temps. Sa courbe de disponibilité est en général connue
a priori, sauf dans les cas où elle dépend du placement de certaines tâches gé-
nératrices. On distingue par ailleurs principalement dans le cas de ressources
renouvelables, les ressources disjonctives qui ne peuvent exécuter qu’une tâche
à la fois (machine-outil, robot manipulateur) et les ressources cumulatives qui
peuvent être utilisées par plusieurs tâches simultanément mais en nombre li-
mité (équipe d’ouvriers, poste de travail).
Les contraintes : Les contraintes expriment des restrictions sur les valeurs que
peuvent prendre simultanément les variables de décision. On distingue :
– Des contraintes temporelles concernent les contraintes de temps alloué, is-
sues généralement d’impératifs de gestion et relatives aux dates limites des
tâches (délais de livraisons, disponibilité des approvisionnements) ou à la
durée totale d’un projet et les contraintes de cohérence technologique, ou
contraintes de gammes, qui décrivent des relations d’ordre relatif entre les
différentes tâches.
– Des contraintes de ressources décrivent les contraintes d’utilisation de res-
3.3. Les problèmes d’ordonnancement en ligne et hors ligne 30
sources qui expriment la nature et la quantité des moyens utilisés par

les tâches, ainsi que les caractéristiques d’utilisation de ces moyens et les
contraintes de disponibilité des ressources qui précisent la nature et la
quantité des moyens disponibles au cours du temps. Toutes ces contraintes
peuvent être formalisées sur la base des distances entre débuts de tâches ou
potentiels.
L’équilibrage de charge (Load Balancing) : L’équilibrage de charge est une

technique relativement nouvelle qui facilite l’exécution des tâches entre des
ressources en fournissant un débit maximal avec un temps de réponse minimal
[55]. Divisant le trafic entre les serveurs, les données peuvent être envoyées et
reçues sans retard majeur. Différents types d’algorithmes sont disponibles qui
aide le partage de charges entre les serveurs disponibles. Un exemple d’équi-
librage de charge peut être lié à l’accès aux sites Web. Sans équilibrage de
charge, les utilisateurs pourraient subir des retards, délais d’attente et des
éventuelles réponses du système longues. Des solutions d’équilibrage de charge
s’appliquent habituellement sur des serveurs redondants qui permettent une
meilleure répartition du trafic de communication de sorte que la disponibilité
des sites web est définitivement tranchée [9].
3.3 Les problèmes d’ordonnancement en ligne et hors

ligne
Le but de l’ordonnancement des tâches est de trouver un plan d’exécution op-

timal des tâches qui prend en considération leurs contraintes : les ressources, le
budget, la date de fin, la performance, etc. En général, un problème contraint se
compose de : tâches, ressources, conditions contraintes et une ou plusieurs fonc-
tions objectifs. Il existe beaucoup d’algorithmes d’ordonnancement dans le Cloud
computing. Les problèmes d’ordonnancement peuvent être classés en deux grandes
catégories :
3.4. Les critères d’optimisation 31
1. Les problèmes d’ordonnancement en ligne (online) [69, 24] pour lesquels la

date d’arrivée (release date) des jobs n’est pas connue à l’avance ;
2. Les problèmes d’ordonnancement hors ligne (offline) pour lesquels les dates
d’arrivées des jobs (généralement ils sont tous prêts à t = 0 et toutes leurs
caractéristiques sont connues avant l’ordonnancement. Ces problèmes ont été
très largement étudiés pour les jobs séquentiels [53] et pour les jobs parallèles
[20, 23].
Les problèmes d’ordonnancement online sont généralement plus difficiles que

les problèmes offline, puisque nous ne connaissons qu’une partie des données du
problème. En effet, les décisions prises pour le placement ou l’exécution de tâches
ne tiennent pas compte des données manquantes car on ne peut pas prévoir l’avenir
[62].
Le processus d’ordonnancement se composent de tout ou partie des étapes sui-
vantes : task prioritizing, resource provisioning/ allocation et enfin scheduling/mapping
[61].
– La phase task prioritizing : établit l’ordre des tâches de départ leurs pro-
priétés et leurs contraintes. Après cette phase, on a une liste ordonnée.
– La phase resource provisioning/allocation : réserve ou alloue un en-
semble de ressources, c’est-à-dire qu’elle calcule le nombre de machines vir-
tuelles pour l’ordonnancement des tâches.
– La phase scheduling/mapping : sélectionne les ressources parmi celles
précédemment allouer qui permettent d’exécuter les tâches selon l’ordre pré-
défini. Ou elle fait l’ordonnancement de chaque tâche à des ressources qui lui
sont optimales.
3.4 Les critères d’optimisation
Les ressources dans un environnement de Cloud peuvent être choisies par di-
verses manières. La sélection des ressources peut être aléatoires, Round Robin, ou
gourmande en fonction de la capacité de traitement de ressource et de temps d’at-
tente ou par tous les autres moyens. La sélection des tâches peut être basée sur
3.4. Les critères d’optimisation 32
FCFS (First Come First Served), SJF (Short Job First), priorité, ou en groupant
un ensemble de tâches. L’algorithme d’ordonnancement choisit la tâche à exécu-
ter et la ressource correspondante où sera exécutée la tâche. Car chaque stratégie
de sélection a certain bienfaits et pourrait être effectuée dans cette direction pour
extraire les points avantageux de ces algorithmes et pour aboutir à une meilleure
solution qui essaye de réduire au minimum les inconvénients de l’algorithme utilisé.
Quand nous concevons un algorithme d’ordonnancement pour un problème par-
ticulier, nous cherchons à optimiser certains critères. Comme nous allons le voir,
ce critère dépend du problème à traiter et il n’existe pas pour tous les problèmes
d’ordonnancement un critère d’optimisation universel. Néanmoins, nous pouvons
donner quelques critères d’optimisation fréquemment utilisés. Pour les problèmes
hors ligne d’ordonnancement d’une collection de jobs ou d’un graphe de tâches
dont les propriétés sont connues à l’avance, un critère d’optimisation souvent utilisé
est la date de terminaison du dernier job ou de la dernière tâche du graphe. Il s’agit
du temps de complétion maximal ou makespan noté Cmax . Il correspond au temps
passé par le système à réaliser tout son travail.
Dans un cluster, les ressources de calcul ne sont pas illimitées, si bien que, quand
les processeurs sont tous occupés, les jobs de certains utilisateurs sont mis dans une
file d’attente. Á cause de cette file d’attente, un critère d’optimisation est alors
le temps d’attente moyen (flow time noté Fi ) qu’il faut minimiser. Il s’agit de la
moyenne des temps Fi écoulés entre l’arrivée du job i dans le cluster (à la date
ai ) et la fin de son exécution (à la date Ci ) : Fi = Ci - ai . Dans [5], Bender et al.
préconise plutôt de minimiser la fonction max Fi . En effet, minimiser une moyenne
des temps d’attente a tendance à allonger les temps d’attente des petits jobs.
Dans le contexte des problèmes d’ordonnancement de jobs pour les clusters, les
travaux de Bender et al. [5] aborde un critère d’optimisation fréquemment utilisé :
le stretch. Le stretch Si reflète le ralentissement engendré par l’exécution en concur-
Fi
rence avec d’autres jobs dans le cluster : Si = avec Fi le temps d’exécution totale
Ci
du job i et Ci le temps de calcul du job i s’il s’exécutait tout seul sur le cluster. Le
calcul du stretch moyen correspond à la moyenne arithmétique de l’ensemble des
1 P
stretchs Si : Si . Pour des raisons de risque de famine, les auteurs proposent
N i
3.5. L’ordonnancement et la virtualisation dans le Cloud computing 33
de minimiser le max stretch qui est le maximum des Si : maxi Si .

Pour l’ordonnancement d’un graphe de tâches exécuté un grand nombre de fois,
il est judicieux d’utiliser le débit comme critère d’optimisation, notamment pour
l’ordonnancement de flux d’une même application. Avec le débit, nous considérons
une fraction de tâche réalisée par unité de temps. Nous définissons la période comme
étant le temps moyen séparant deux exécutions terminées de deux instances d’une
application consécutives. Ainsi, il n’y a pas de critère d’optimisation universel. Ce-
pendant le choix du critère d’optimisation a une grande importance. Comme nous
venons de le voir à travers la minimisation du temps d’attente moyen des Fi , cette
optimisation conduit à des effets indésirables. Il est alors judicieux de remplacer ce
critère par le maximum des temps d’attente.
3.5 L’ordonnancement et la virtualisation dans le Cloud

computing
L’ordonnancement dans le Cloud computing est classé au niveau de l’utilisateur

et au niveau du système [59]. Au niveau de l’utilisateur, la planification traite les
problèmes soulevés par la prestation de services entre les fournisseurs et les clients.
La programmation au niveau système gère la gestion des ressources dans les centres
de données. Le Datacenter se compose de plusieurs machines physiques. Des millions
de tâches des utilisateurs sont reçues ; l’attribution de ces tâches aux machines phy-
siques se fait au niveau des centres de données. Cette affectation d’ordonnancement
joue un rôle significatif sur les performances du Datacenter. En plus de l’utilisa-
tion du système, d’autres exigences comme la qualité de service, le SLA (Service
Level Agreement), le partage des ressources, la tolérance aux pannes, la fiabilité, la
satisfaction en temps réel, etc. devraient être pris en considération.
Les ordonnanceurs basés sur le modèle du marché et sur les enchères sont ap-
propriés pour réguler l’offre et la demande des ressources sur le nuage. L’alloca-
tion des ressources en fonction du modèle économique de marché est efficace dans
un environnement de Cloud computing où les ressources sont virtualisées et livrés
à l’utilisateur en tant que service. Une suite d’algorithmes d’ordonnancement de
3.5. L’ordonnancement et la virtualisation dans le Cloud computing 34
tâches axées sur la base du modèle de marché pour les environnements distribués
hétérogènes est proposée dans le travail [74].
Le développement d’un modèle de tarification en utilisant le partage du proces-
seur dans les Clouds, l’application de ce modèle de tarification aux services compo-
sites avec dépendance et le développement de deux ensembles de planification et de
profit conduit aux algorithmes proposés dans [37].
Le service d’approvisionnement en Cloud est basé sur les accords au niveau de
service. SLA représente un contrat signé entre le client et le fournisseur de services
en précisant les termes de l’accord, y compris les exigences non fonctionnelles du
service spécifié comme la qualité de service (QoS), des obligations et des sanctions
en cas de violation de l’accord. Il existe donc un besoin de stratégies de planification
tenant compte de multiples paramètres SLA et d’allocation efficace des ressources.
Une nouvelle heuristique d’ordonnancement tenant en compte de multiples para-
mètres SLA pour le déploiement d’applications dans le Cloud est présenté dans
[36]. L’algorithme d’ordonnancement qui permet le réapprovisionnement des res-
sources dans le Cloud en cas de défaillance est introduit dans [1]. L’objectif du
modèle est de fournir une entente équitable pour les utilisateurs et les consomma-
teurs, une meilleure qualité de service, ainsi que la génération de coût optimal. Un
schéma d’ordonnancement du nuage présenté en [13] utilise SLA avec moniteur de
confiance pour fournir une planification plus rapide à la demande de l’utilisateur
avec un traitement sécurisé. Une nouvelle approche pour l’heuristique d’ordonnan-
cement des requêtes sur chaque serveur, dans chacun des centres de données répartis
géographiquement, à l’échelle mondiale pour un meilleur équilibrage de charge du
système de Cloud computing est proposé dans [6].
Sur la base de la fonction de files d’attente et de modèle de coûts, et compte tenu
des objectifs des utilisateurs et des fournisseurs de services de Cloud computing, le
travail [39] propose un algorithme pour obtenir la valeur optimiste approximative
de service pour chaque emploi dans le modèle de file d’attente prioritaire de préemp-
tion correspondant. Cette approche garantit les exigences de QoS des utilisateurs,
ainsi que le maximum de profits pour les fournisseurs de services de Cloud com-
puting. Pour faire face à la fluctuation dynamique des demandes de ressources,
3.6. Les principaux algorithmes d’ordonnancement 35
l’allocation des ressources axée sur le marché a été proposée et mise en œuvre par
l’infrastructure publique en tant que service (IaaS) des fournisseurs comme Amazon
EC2. Dans cet environnement, les ressources en nuage sont offertes dans différents
types de machines virtuelles (VM) et le fournisseur de Cloud exécute un modèle de
marché à base d’enchères pour chaque type de VM avec l’objectif d’atteindre un
maximum de revenus au fil du temps. Une étude de cas du fournisseur de Cloud
unique et la meilleure façon de la demande de la clientèle en termes de l’offre et de
prix, afin de maximiser les revenus des fournisseurs et les satisfactions des clients
tout en réduisant le coût de l’énergie est proposée dans [73]. Un autre mécanisme
à base d’enchères pour le provisionnement et l’allocation dynamique de VM qui
tient compte de la demande des utilisateurs pour les machines virtuelles lorsqu’ils
prennent des décisions de provisionnement de VM est proposé dans [72].
3.6 Les principaux algorithmes d’ordonnancement
Nous présentons dans ce qui suit, les principaux algorithmes d’ordonnancement

et d’allocation de ressources cités dans la littératures [26, 33, 29, 34] :
Algorithme Min-min : L’algorithme commence par calculer le temps d’exé-
cution minimale pour toutes les tâches puis la valeur minimale entre ces temps
minimum est choisie ; qui représente le temps minimum d’exécution parmi toutes
les tâches sur les ressources. Ensuite, en fonction de ce temps minimum, la tâche
est ordonnancée sur la machine correspondante. Puis le temps d’exécution pour
toutes les autres tâches sont mises à jour sur cette machine en ajoutant le temps
d’exécution de la tâche assignée à des temps d’exécution des autres tâches sur cette
machine/ressource et la tâche assignée est supprimée de la liste des tâches. Ensuite,
la même procédure est répétée jusqu’à ce que toutes les tâches soient assignées sur
les ressources [29].
Un exemple d’application de l’algorithme pour 6 tâches et 4 machines virtuelles,
les temps d’exécution (en milliseconde secondes) de toutes les tâches sur toutes les
machines sont présentés sur le tableau 3.1 suivant :
M0 M1 M2 M3
T0 160 400 80 200
T1 40 100 20 50
T2 100 250 50 125
T3 20 50 10 25
T4 140 350 70 175
T5 80 200 40 100
Table 3.1 – Le temps d’exécution des tâches (Algorithme Min-min)
Le résultat d’exécution des tâches selon l’algorithme Min-min est donné dans la
Figure 3.1 suivante :
Figure 3.1 – Le résultat d’exécution des tâches selon Min-min
Algorithme Max-min : L’algorithme Max-min suit le même principe que

l’algorithme Min-min à l’exception des propriétés suivantes : Après avoir calculer
les temps d’exécution minimum, la valeur maximale est sélectionnée, qui est la
durée maximale parmi toutes les tâches sur les ressources. Ensuite, en fonction de
ce temps maximum, la tâche est ordonnancée sur la machine correspondante. Puis le
temps d’exécution pour toutes les autres tâches sont mises à jour sur cette machine
en ajoutant le temps d’exécution de la tâche assignée à des temps d’exécution des
autres tâches sur la machine qui a acquise la tâche sélectionnée et la tâche assignée
est supprimée de la liste des tâches. La même procédure est répétée jusqu’à ce que
toutes les tâches soient assignées sur les ressources [34].
Le résultat d’exécution des tâches selon l’algorithme Min-max est donné dans
la Figure 3.2 suivante en utilisant les mêmes paramètres du tableau 3.1 :
Figure 3.2 – Le résultat d’exécution des tâches selon Max-min
Algorithme Round Robin : Cet algorithme suit une stratégie simple qui
consiste à distribuer de manière équitable les tâches sur les machines virtuelles dis-
ponibles, c’est-à-dire que le nombre de tâches pour chaque machine virtuelle est le
même. Cet algorithme est implémenté dans le simulateur CloudSim [12].
Algorithme FIFO/FCFS : L’algorithme FIFO (First In First Out) ou FCFS

(First Come First Served) est l’un des algorithmes les plus simple qu’il soit. L’idée
est d’ajouter chaque tâche et ressource disponible dans une file et d’exécuter chaque
tâche et ressource par ordre d’arrivée. Cet algorithme est implémenté dans le simu-
lateur CloudSim [12].
Shortest Job First (SJF)/Plus court d’abord : L’algorithme SJF ressemble

au FIFO, mais au lieu d’exécuter dans l’ordre d’arrivée, on choisit d’exécuter celui
qui sera le plus court. Mais le problème est de déterminer le temps d’exécution
d’une tâche avant de l’exécuter et pour cela il faut se baser sur une estimation.
3.7. Les algorithmes d’ordonnancement pour les applications
scientifiques 38
Earliest Deadline First scheduling (EDF) : Dans le même ordre d’idée,

on peut aussi choisir d’exécuter en premier la tâche qui nécessite d’être fini le plus
rapidement. Cet algorithme est utilisé pour les systèmes temps réel. C’est un ordon-
nancement préemptif avec priorité dynamique : la tâche la plus prioritaire est celle
dont la date de fin est la plus proche, c’est à dire que plus le travail doit être réalisé
rapidement, plus elle est prioritaire. Cependant, il est assez complexe à le mettre
en œuvre et il se comporte mal en cas de surcharge du système, c’est la raison pour
laquelle il est peu utilisé.
3.7 Les algorithmes d’ordonnancement pour les appli-

cations scientifiques
Cette section présente une série de travaux qui traitent différentes stratégies
d’ordonnancement des workflows dans les grilles et les Clouds afin d’identifier les
caractéristiques et les possibilités dans les environnements mentionnés pour l’ordon-
nancement des tâches et des ressources.
La Figure 3.3 décrit l’exécution de plusieurs workflows sur plusieurs Clouds.
Tout d’abord, le client envoie son job à la couche Broker [22] où l’algorithme d’or-
donnancement est installé. On suppose que tous les jobs sont formés par des DAGs
(Directed Acyclic Graph), chaque tâche est représentée par un cercle. Après, l’al-
gorithme prioritise les tâches et réserve des ressources dans le cloud privé et public.
Ensuite, il choisit pour chaque tâche la ressource adéquate pour l’exécuter. Enfin,
le résultat de calcul du job est renvoyé à l’utilisateur [61]. La résolution de l’ordon-
nancement des tâches, spécialement dans un système distribué et hétérogène, est de
complexité NP-hard. En général, des algorithmes courants utilisent des heuristiques
pour trouver une solution qui est quasi-optimal [22]. Le Tableau 3.2 présente les al-
gorithmes d’ordonnancement de workflows pour les environnements Clouds pour
optimiser l’utilisation de coût et de performance.
scientifiques 39
Figure 3.3 – L’exécution de plusieurs workflows sur plusieurs Clouds [22]
Le Tableau 3.2 se compose de 6 colonnes où chaque ligne présente un algorithme

avec son nom, une description, sa stratégie, ses caractéristiques, ses avantages et
ses inconvénients, etc. Pour la deuxième colonne, nous présentons brièvement l’al-
gorithme et son idée. Après, nous présentons les paramètres qu’il optimise. La pre-
mière, c’est makespan, il présente le temps complet d’exécution du workflow de la
première tâche à la dernière tâche. L’algorithme doit trouver la valeur minimale.
Ensuite, c’est le coût minimal à payer quand on utilise les services. Les autres sont :
la fidélité, la sécurité, le taux de réussite, le taux de vitesse, etc. La colonne outil
présente le simulateur ou l’environnement de déploiement de l’algorithme. Enfin, les
2 dernières colonnes présentent les avantages et les inconvénients des algorithmes
d’ordonnancement.
scientifiques 40
Algorithme Résumé Paramètres Outil Avantages Inconvénients
L’algorithme a une
pré-étape pour
Un algorithme
découvrir et
d’ordonnancement
réordonner les
CTC pour
tâches échouées. Il
l’exécution de
exploite l’effet
workflow dans le
Compromised Cloud computing. interactif entre le Il ne considère pas
coût et le deadline simultanément les
time-cost Il est centré sur des Makespan,
qui agit sur la deux contraintes
scheduling contraintes d’une coût SwinDeWC
performance du dans le workflow
algorithm relation interactive monétaire
workflow. De plus, pour minimiser la
(CTC) [41] entre le temps et le
il permet à performance totale
coût comme un
l’utilisateur de
compromis qui est
redéfinir leurs
basé sur des
deadline et leurs
caractéristiques du
coûts dans chaque
Cloud
cycle de
l’ordonnancement
L’article propose
une nouvelle
approche pour L’espace d’état
l’ordonnancement pour faire des
du workflow dans tâches est grande
Il s’adapte
le Cloud en incluant
automatiquement
Learning computing, c’est l’utilisation ou
au changement
l’architecture non-utilisation des
architec- Makespan, d’environnement
d’apprentissage qui ressources selon le
ture for coût Cloudsim des ressources par
utilise un processus temps. Il ne
scheduling monétaire l’apprentissage. De
de décision pour considère pas les
(LA) [3] plus, il garantit
diriger types de VMs. Il
l’exécution réussie
optimalement le répète l’évaluation
du workflow
processus de la fonction
d’exécution du fitness
workflow selon
l’état de
l’environnement
scientifiques 41
Deadline
and budget
distribu-
Cet algorithme
tion based
minimise le coût Il ne fait pas avec un
cost-time
d’exécution tout en Il garantit que toutes réordonnancement
Makespan,
optimiza- répondant au délai les tâches sont faites quand une tâche
coût Java
tion pour l’obtention des par leurs contraintes n’est pas terminée.
monétaire
résultats et analyse correspondantes De plus, il est
scheduling
le comportement de statique
algorithm
l’algorithme
(DBD-
CTO)
[65]
La stratégie peut
faire
Multiple
l’ordonnancement Il s’accorde avec les
QoS pour multiple multiples workflows
constrai- workflows qui sont et le
ned démarrés tous en multiple-objectifs

Taux de Il ne fait pas un
même temps et les optimal en
scheduling réussite, ré-ordonnancement
exigences de QoS CloudSim même-temps. De
strategy of coût, temps, quand une tâche
sont prises en plus, il considère la
makespan n’est pas terminée
multiple compte. Il considère performance totale
workflows 4 facteurs qui par 3 contraintes.

affectent grandement Une tâche est
(MQMW)
le makespan, le coût toujours terminée
[68]
et le taux de réussite
du workflow
SSWE fait Il groupe des

Il considère les
l’ordonnancement ressources qui sont
changements
d’un workflow de même capacité de
Scheduling élastiques des
élastique sur le calcul dans un
Scientific ressources quand le
Cloud computing Le temps cluster. Il ne
workflow s’exécute.
Workflows pour optimiser le d’exécution, CloudSim considère pas
De plus, les
Elastically temps d’exécution capacité d’autres
ressources peuvent
du workflow et met à caractéristiques de
SSWE [40] être assignées
échelle élastique des VMs comme : le
seulement quand
ressource lors de prix, le stockage, la
elles sont nécessaire
l’exécution bande passante, etc.
Table 3.2 – Comparaison entre les algorithmes d’ordonnancement des workflows

scientifiques 42
Dans [44], les auteurs présentent une stratégie d’ordonnancement des tâches dy-
namique qui traite la relation entre l’utilisateur et la ressource. Dans cette approche,
les ressources ne sont pas considérées individuellement, mais regroupées. L’ordon-
nanceur, dans cette approche, sélectionne les sites, et cette sélection est faite par
une stratégie opportuniste. Il vise à répartir les tâches du flux de travail à travers
des sites de la grille en fonction de leurs performances.
Le travail [67] présente une étude de programmation des applications de work-
flow sur les grilles basé sur un modèle d’ordonnancement bi-critères. Il utilise le
Constraint Algorithme dynamique (DCA) comme une solution au problème d’op-
timisation avec deux critères indépendants (exécution et coût). L’algorithme choi-
sit un critère primaire et l’utilisateur établit un pourcentage de variation pour le
deuxième critère. Cependant, cette approche ne tient pas compte des exigences de
qualité de service, ne différenciant pas la qualité des ressources et des services. Il
n’utilise pas le regroupement des tâches pour réduire la consommation de bande
passante. Dans [70], le travail présente un algorithme d’ordonnancement basé sur le
coût des flux de travail pour les applications en temps réel. Le but de l’algorithme
est de développer un programme qui minimise le coût et répond aux contraintes
de temps imposées par l’utilisateur. Le flux de travail est divisé en sous-ensembles
de tâches pour l’établissement d’un seul flux. Les tâches qui ne forment pas un
seul flux sont séparés et chacune d’entre elles fonctionne comme un sous-ensemble
indépendant.
Le thème de la réplication des tâches a été largement explorée dans le contexte
des systèmes de grille sans aborder la question du coût et de l’utilisation des res-
sources. Des récentes recherches sont portés sur des algorithmes qui sont conscients
de la complexité des environnements de Cloud lors de leur utilisation pour ordon-
nancer des applications de workflow. Reynolds [52] a proposé l’utilisation de Cloud
pour compléter les ressources de la grille. Cependant, les ressources de Cloud sont
déployés dans le but de répliquer les tâches lentes pour augmenter les chances d’un
achèvement rapide du flux de travail. La méthode proposée n’est pas optimisée soit
pour le budget et pour le temps d’exécution ; par contre, elle fonctionne dans des
meilleures conditions lorsque les tâches en retard sont détectées. Xu et al. [68] et
3.8. Conclusion 43
Mao et Humphrey [42] ont proposé des algorithmes pour l’ordonnancement de plu-
sieurs flux de travail dans les Clouds. Rahman et al. [51] ont proposé un algorithme
pour les Clouds hybrides, où au moins une partie des ressources peut être utilisée
sans coût et avec un niveau plus élevé de contrôle de performance.
3.8 Conclusion
La théorie d’ordonnancement de tâches et d’allocation de ressources dans les

systèmes de Cloud computing suscite une attention croissante avec l’augmentation
de la popularité de Cloud. En général, l’ordonnancement de tâches est le processus
d’affectation des tâches aux ressources disponibles sur la base des caractéristiques
et des conditions des tâches. C’est un aspect important dans le fonctionnement effi-
cace du Cloud, car de divers paramètres de tâches doivent être pris en considération
pour un ordonnancement approprié. Les ressources disponibles devraient être utili-
sées efficacement sans affecter les paramètres de service du Cloud. Dans le cadre de
ce travail, nous proposons trois stratégies d’ordonnancement et d’allocation de res-
sources. Le chapitre suivant permet de décrire nos contributions, leurs démarches,
ses différentes phases, et les algorithmes nécessaires ainsi que les différentes étapes
formalisées à l’aide du langage UML (Unified Modeling Langage).
Chapitre 4
Stratégies d’ordonnancement et
d’allocation de ressources pour
les Clouds scientifiques
Sommaire
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Stratégie d’ordonnancement basée sur la réplication de don-
nées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.1 Étape de construction . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.2 Étape d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.3 Service de gestion de réplication dynamique . . . . . . . . . . . 60
4.3 Stratégie d’ordonnancement basée sur le groupement de
tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1 Etape de construction . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.2 Étape d’ordonnancement . . . . . . . . . . . . . . . . . . . . . 66
4.4 Stratégies d’ordonnancement et d’allocation de ressources
pour les Big Data . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4.1 La première variante OADTV . . . . . . . . . . . . . . . . . . . 67
4.4.2 La deuxième variante OAAMV . . . . . . . . . . . . . . . . . . 69
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.1. Introduction 45
4.1 Introduction
ans les chapitres précédents, nous avons présenté les notions de base du Cloud
D Computing, et nous avons exploré et comparé certaines stratégies d’ordon-
nancement de tâches et d’allocation de ressources. Notre objectif principal est
de proposer et d’implémenter des stratégies d’ordonnancement et d’allocation de
ressources de données scientifiques afin d’améliorer certaines métriques de perfor-
mances tels que le temps de réponse, le temps d’attente, le nombre de déplacements
des données et le coût total engendré. Le présent chapitre permet de décrire nos
trois contributions, d’expliquer leurs démarches, de détailler leurs différentes phases,
et de décrire les algorithmes nécessaires, ainsi que les diagrammes du langage UML
(Unified Modeling Langage) pour modéliser les démarches de l’ensemble des diffé-
rentes étapes.
4.2 Stratégie d’ordonnancement basée sur la réplica-

tion de données
Dans cette section, nous décrivons notre première contribution à savoir une
stratégie pour l’ordonnancement des tâches et l’allocation de ressources, destinée
aux applications de workflows scientifiques distribuées. Cette stratégie est établie
à partir d’une matrice de clusterisation (classification) basée sur l’algorithme des
K-means [48].
La Figure 4.1 donne une vue globale sur les principales étapes de la stratégie, et
qui est réalisée à partir d’une simple instance de workflow (prise comme exemple).
4.2. Stratégie d’ordonnancement basée sur la réplication de données 46
Figure 4.1 – Vue globale de la stratégie utilisée
L’approche utilisée [71] comprend deux étapes importantes. Chacune d’elles

contient un ensemble d’opérations à effectuer. En plus de ces deux étapes, nous
avons étendu la stratégie avec un service de réplication qui constituera la troisième
phase de ce travail [15, 18]. Ces trois étapes se résument comme suit :
1. Étape de construction : Représente la première partie de la stratégie, dans

laquelle les opérations suivantes doivent être réalisées :
– Construction de la matrice de dépendances ;

– Établissement de la matrice de dépendances clusterisée ;
– Partitionnement et déplacement des données vers leurs nouveaux emplace-
ments ;
– Obtention du paramètre K, pour l’algorithme des K-means.
2. Étape d’exécution : Représente la deuxième partie de la stratégie, dans

laquelle les opérations suivantes doivent être effectuées :
– Ordonnancement et exécution des tâches ;

– Traitement des données générées en appliquant l’algorithme des K-means ;
3. Étape de réplication : Représente l’extension ajoutée à la stratégie utilisée.

Elle comprend un service de réplication dynamique des données.
4.2.1 Étape de construction
Durant la phase de construction, un modèle de matrice sera utilisé pour représen-

ter les données existantes. Un pré-classement de ces données sera, ensuite, effectué
en appliquant des transformations à cette matrice et en distribuant les données sur
différents datacenters. Cette distribution représentera les partitions initiales pour
l’algorithme des K-means, qui sera utilisé durant l’étape d’exécution.
L’étape de construction se constitue, à son tour, de deux étapes :
– Mise en place et clusterisation de la matrice de dépendance ;
– Partitionnement et distribution des datasets.
4.2.1.1 Mise en place et clusterisation de la matrice de dépendance
Dans les Clouds exécutant des workflows scientifiques, de nombreuses instances

vont être exécutées simultanément. Certaines tâches utiliseront un nombre impor-
tant de données et produiront, ainsi, plusieurs autres données en sortie.
Dans le but d’exécuter une tâche, toutes les données requises doivent être situées
dans le même datacenter et cela peut nécessiter certains mouvements des données
aussi appelées datasets.
En outre, si deux datasets sont toujours utilisés ensemble par de nombreuses
tâches, ils doivent être stockés ensemble dans le but de réduire la fréquence du
mouvement de données.
De ce fait, de nombreux algorithmes et opérations doivent être effectués, la
démarche se présente comme suit :
1. Calcul des dépendances :

Deux ensembles sont à considérer, l’ensemble de datasets noté par D et l’en-
semble de tâches noté par T . Chaque dataset di ∈ D possède deux attributs
notés : hTi , si i où Ti ⊂ T est l’ensemble de tâches qui utiliseront le dataset di ,
si étant la taille de di . Deux datasets di et dj sont dits dépendants s’il existe
des tâches qui utiliserons à la fois di et dj . La quantité de cette dépendance
est égale au nombre de tâches communes entre di et dj (voir Formule 4.1) :
\
dependencyij = Count(Ti Tj ) (4.1)
2. Construction de la matrice de dépendance DM :

Chaque élément de la matrice DM, noté DMi,j = dependencyij . Pour les élé-
ments de la diagonale, chaque valeur DMi,i représentera le nombre de tâches
qui vont utiliser le dataset di . DM est une matrice symétrique de dimension
n × n où n est le nombre total des datasets existants.
3. Élaboration de la matrice de dépendance clusterisée :

Le Bond Energy Algorithm (BEA) [43] sera appliqué sur la matrice DM dans
le but de regrouper les valeurs similaires ensembles, c’est-à-dire que les grandes
valeurs ensembles et les petites valeurs ensembles.
Deux mesures, BEC et BEL sont définies pour cet algorithme. La permutation
est faite de telle sorte que ces mesures (voir les Formules 4.2 et 4.3) soient
maximisées :
n
X
BEC i, j = DMi,j × DMi,j+1 (4.2)
i=1
n
X
BEL i, j = DMi,j × DMi+1,j (4.3)
j=1
Algorithme du BEA : Le Bond Energy Algorithm [43] a été proposé en 1972

et a été largement utilisé dans les systèmes de bases de données distribués. C’est un
algorithme de permutation qui peut regrouper, ensemble, les objets similaires dans
la matrice en calculant des énergies (d’où son nom) et en permutant les lignes et
les colonnes.
Après de nombreuses itérations, le résultat de l’application de cet algorithme
donnera une matrice de dépendance clusterisée notée CM . La Figure 4.2 résume, à
travers un diagramme d’activité, cette phase de mise en place et clusterisation de
la matrice de dépendance.
Figure 4.2 – Diagramme d’activité de la phase de mise en place et clusterisation

de la matrice de dépendance
4.2.1.2 Partitionner et distribuer les datasets
Au cours de cette partie, deux opérations importantes seront effectuées. Ces

dernières sont le partitionnement et la distribution des datasets.
A. Etape de Partitionnement :
L’ensemble des datacenters est noté DC dans lequel chaque datacenter dcj possède
une capacité de stockage notée csj . Un algorithme de partitionnement binaire (voir
Algorithme 1) sera appliqué sur la matrice CM dans le but d’obtenir le meilleur
partitionnement binaire possible. Une mesure P M (voir Formule 4.4) est définie
pour cet algorithme.
p X
X p n
X n
X p
X n
X
PM = CMij × CMij − ( CMij )2 (4.4)
i=1 j=1 i=p+1 j=p+1 i=1 j=p+1
Cette mesure signifie que les datasets dans chaque partition auront des dépen-
dances plus élevées qu’avec les datasets qui se trouvent dans les autres partitions.
Algorithme de partitionnement binaire : Cet algorithme a été mis en place
afin de partitionner, dans un premier temps, la matrice CM en deux parties (ou deux
sous-matrices). Le principe de cet algorithme est définit comme suit :
Étant donné un ensemble D de datasets, l’algorithme essaye, à chaque itération,
de former deux groupes différents à partir des datasets existants, dans le but de
trouver la meilleure combinaison possible. L’opération s’effectue en variant la valeur
de p et en choisissant la valeur maximum de P M . Choisir une valeur max pour P M
signifie que les datasets se trouvant dans le même groupe ont une dépendance plus
élevée que s’ils étaient regroupés autrement.
Algorithme 1 Algorithme de partitionnement binaire

Input : CM : Matrice de dépendance clusterisée.
Output : CMT et CMB : Deux matrices clusterisées représentant les 2 partions de
CM .
Description :
1: pour p := 1, p ≤ n − 1, p + + faire
2: Calculer P M (formule 4.4)
3: pour tout P Ms obtenues faire
4: Choisir p/ sa valeur P M = M AX
5: Prendre p point de coupure et Partitionner CM en CMT et CMB
6: retour CM P ;
Après de nombreuses opérations, le résultat de l’application de cet algorithme

donnera deux matrices clusterisées notées CMT et CMB . La matrice CMT repré-
sente la première partition de CM , elle contient le sous-ensemble de datasets DT /
DT = {d1 , d2 , ..., dp }. DT est de taille dsT / dsT = pi=1 si . La matrice CMB repré-
P
sente la deuxième partition de CM , elle contient le sous-ensemble de datasets DB /

Pn
DB = {dp+1 , dp+2 , ..., dn }. DB est de taille dsB / dsB = i=p+1 si . P étant le point
de coupure.
La Figure 4.3 montre un diagramme d’activité décrivant l’algorithme de parti-
tionnement de la matrice de dépendance clusterisée.
Figure 4.3 – Diagramme d’activité pour le partitionnement de la matrice de dé-

pendance clusterisée
B. Étape de distribution :
Dans cette partie, nous devons distribuer les datasets sur les datacenters. Un para-
mètre noté λini est introduit pour chaque datacenter dcj ∈ DC. Il désigne l’usage
initial (en %) de la capacité de stockage du datacenter, c’est-à-dire, que la taille ini-
tiale des datasets qui vont se trouver dans dcj ne pourra pas dépasser csj ∗ λini . La
valeur de λini dépendra du type d’application en cours d’exécution [71]. De ce fait,
nous avons établi une liste d’applications avec les valeurs de λini correspondantes
(Voir Tableau 4.1) :
Type d’application Valeur de λini
Bio-informatique 50%
Astronomie 40%
Physique nucléaire 20%
Sismologie 60%
Sciences de la santé 30%
Table 4.1 – Valeurs de λini par rapport aux types d’applications
Un algorithme de distribution (voir Algorithme 2) sera appliqué sur la matrice

CM .
Algorithme de distribution : Cet algorithme a été conçu dans le but d’af-
fecter les datasets existants aux datacenters disponibles, en suivant certaines condi-
tions. Le principe de cet algorithme est :
Étant donné un ensemble DC de datacenters, l’algorithme calcule pour chacun
d’eux, sa capacité de stockage initiale (Ligne 2 de l’Algorithme 2). Ensuite, il vérifie
si les datacenters disponibles pourront héberger tous les datasets existants (Ligne 3
de l’Algorithme 2). Si la condition précédente est satisfaite, l’algorithme partitionne,
d’abord, la matrice CM (Ligne 4 de l’Algorithme 2) et ensuite, refait l’opération (si
nécessaire) avec les sous-matrices M CT et M CB jusqu’à trouver un datacenter dci
d’une capacité de stockage (parmi celles disponibles) qui puisse héberger la partition
en question. (En cas de non satisfaction de la condition, la distribution ne pourra
pas s’effectuer). Une fois le datacenter dci trouvé, la distribution des datasets est
effectuée (Lignes 12 et 20 de l’Algorithmes 2), ainsi que l’affectation de l’identifiant
du datacenter à l’ensemble K.
Des appels récursifs de l’algorithme de distribution sont exécutés, jusqu’à la
distribution de la dernière partition.
La Figure 4.4 montre un diagramme d’activité décrivant la phase de partition-
nement et distribution des datasets.
Algorithme 2 Algorithme de distribution des datasets

Input : CM : Matrice de dépendance clusterisée.
DC : Ensemble de datacenters.
Output : K : Ensemble de datacenters avec les datasets initiaux.
Description :
1: pour each dcj ∈ DC faire

2: i csj = csj ∗ λini
Pn Pm
3: si i=1 si < j=1 (csj ∗ λini ) alors
4: Partitionner CM (Algorithme 1)
5: si dsT < maxm
j=1 csj alors
6: Trouver dci ∈ DC
7: si csi = minm
j=1 (csj > dsT ) alors
8: Distribuer CMT dans dci

9: Mettre dci dans K
10: i csj = i csj − dsT
11: sinon
12: Partitionner et Distribuer CMT (Algorithme 1, 2)
13: si dsB < maxm
j=1 alors
14: Trouver dci ∈ DC

15: si csi = minm
j=1 (csj > dsB ) alors
16: Distribuer CMB dans dci

17: Mettre dci dans K
18: i csj = i csj − dsB
19: sinon
20: Partitionner et Distribuer CMB (Algorithme 1, 2)
21: La distribution ne peut pas être effectuée //Taille des datasets > Capa-
cité des DC
22: retour K ;
Figure 4.4 – Diagramme d’activité de la phase de partitionnement et distribution

des datasets
Le résultat obtenu, de la phase de partitionnement et distribution, est l’ensemble

de datacenters sur lesquels nous avons effectué une distribution. Cet ensemble noté
K représente le paramètre d’entrée pour l’algorithme du K-means qui s’effectuera
dans l’étape d’exécution. Avec ce troisième algorithme, l’étape de construction
s’achève pour donner naissance à l’étape d’exécution.
4.2.2 Étape d’exécution
Durant la phase d’exécution, l’algorithme des K-means [48] sera utilisé afin
de classifier, dynamiquement, les datasets générés en affectant chacun deux à l’un
des K datacenters obtenus durant l’étape de construction. Comme pour l’étape de
construction, cette étape, contient, elle aussi, deux phases importantes :
– Ordonancement et exécution des tâches ;
– Préallocation des datasets générés par un algorithme de classification.
4.2.2.1 Ordonnancement et exécution des tâches
Avant de se préoccuper des datasets qui vont être générés, il faudrait, d’abord
exécuter les tâches existantes. Étant donné que le déplacement de datasets d’un
datacenter vers un autre est plus coûteux que l’ordonnancement des tâches vers ce
datacenter. Un algorithme d’ordonnancement des tâches est utilisé (Algorithme 3).
Dans cet algorithme, la technique employée se base sur le placement des datasets,
c’est-à-dire, les tâches prêtes sont ordonnancées vers le datacenter qui contient la
majorité des datasets requis. Une tâche est dite prête si tous les datasets requis
appartiennent à l’ensemble des datasets existants. Une fois les tâches exécutées, de
nouveaux datasets sont générés.
La Figure 4.5 montre un diagramme d’activité décrivant l’ordonnancement et
l’exécution des tâches.
Algorithme 3 Algorithme d’ordonnancement

Input : T : Ensemble de tâches.
Output : Toutes les tâches ordonnancées vers le datacenter approprié.
Description :
pour chaque ti ∈ T faire

si les datasets requis par ti sont disponibles alors
Ordonnancer ti vers dcj pour s’exécuter
si dcj possède la majorité des datasets requis par ti alors
Mettre état ti = prêt
sinon
état ti = non prêt
si état ti = prêt alors
Exécuter ti
Figure 4.5 – Diagramme d’activité de la phase d’ordonnancement et exécution des

tâches
4.2.2.2 Pré-allocation des datasets générés par un algorithme de classi-

fication
Une fois générés, les nouveaux datasets seront classifiés à l’aide de l’algorithme
des K-means [48], en suivant la démarche suivante :
A. Choix du Datacenter destinataire
Étant donné du un nouveau dataset généré et Tu l’ensemble des tâches qui
utiliseront du . Le calcul de la dépendance entre du et les K datacenters se
procède comme suit :
1. En premier lieu, le calcul des dépendances entre du et tous les datasets

existants est effectué. Aussi, une colonne et une ligne seront ajoutées à
la matrice de dépendance DM , où :
\
DMui = dependencyui = Count(Tu Ti ) i = 1, 2, .., n (4.5)
2. En second lieu, le calcul des dépendances entre du et les K datacenters

est effectué, où :
X
dc depuj = dependencyum j = 1, 2, .., K (4.6)
dm ∈dcj
Une fois, les K dépendances calculées, le datacenter avec la plus grande valeur
de dépendance est sélectionné (la dépendance entre deux datasets représente
le nombre de tâches qui les exécutent ensemble, plus elle est élevée dans un
datacenter donné plus le dataset généré est dépendant et doit se trouver avec
les datasets de ce datacenter). Ce dernier est noté dch , où :
dc depuh = maxK
j=1 (dc depuj ) (4.7)
dch est le datacenter dans lequel le dataset du va être stocké. Une vérification
de la capacité de stockage disponible pour ce datacenter est effectuée avant le
déplacement de du .
B. Vérification de l’espace de stockage
Un paramètre noté λmax est introduit pour chacun des K datacenters. Il
désigne l’usage maximal (en %) de la capacité de stockage du datacenter, c’est-
à-dire, un seuil indiquant quand est-ce qu’un datacenter devient surchargé.
La valeur de λmax dépendra de la charge de travail globale du système. De ce

fait, nous supposons que tous les datacenters ont une charge plus au moins
égale. Par conséquent, la valeur de λmax sera la même pour tous, ainsi : λmax
= 90 % ([71]).
De ce fait, les datasets générés ne peuvent utiliser qu’un taux limité de la

capacité de stockage d’un datacenter dci , noté par csiU T , tel que :
csiU T = csi ∗ (λmax − λini ) (4.8)
Enfin, le dataset généré du sera déplacé au datacenter dch sélectionné si la

formule 4.9 est vérifiée :
csh ∗ λ + su < csh ∗ λmax (4.9)
où su est la taille de du est λ est le pourcentage de l’usage en cours de la

capacité de stockage de dch .
Les démarches ci-dessus représentent les opérations élémentaires qu’utilisera

l’algorithme des K-means pour la classification des datasets générés.
Algorithme des K-means
L’algorithme des K-means, ou K-moyennes a été proposé en 1967 [48]. Il figure

parmi les techniques de classification non supervisée (clustering) les plus uti-
lisées pour résoudre les problèmes de classification. Son principe se constitue
des étapes suivantes :
i) Placer K points d’entrée : C’est K points représenteront les groupes
initiaux, sur la base desquels la classification s’effectuera. Dans notre tra-
vail, ces points d’entrée sont les K datacenters résultant de la phase de
construction.
ii) Calculer des distances avec les K points : Dans notre stratégie, ce
sont les dépendances qui sont calculées (voir formules 4.5 et 4.6).
iii) Choisir le point le plus proche : Dans notre cas, la notion de proche
est exprimée en terme de plus grande valeur de dépendance avec l’un des
K datacenters (voir Formule 4.7).
iv) Classifier : Une fois le datacenter approprié trouvé et après une véri-
fication de la capacité de stockage disponible (voir Formules 4.8 et 4.9) ;
l’affectation des datasets est effectuée.
La Figure 4.6 montre un diagramme d’activité décrivant la gestion des datasets

générés avec l’algorithme des K-means.
Figure 4.6 – Diagramme d’activité pour la gestion des datasets générés avec l’al-
gorithme des K-means
Remarques :
1. Vu que λmax représente le pourcentage de l’espace de stockage total d’un data-

center, chaque datacenter aura toujours un certain espace disponible (100% −
λmax ) pour faciliter le mouvement des datasets durant la re-distribution.
2. Dans le cas où λmax est mis à 100%, un espace de stockage additionnel et
temporaire peut être requis pour servir comme buffer, avant l’accomplisse-
ment du processus d’ajustement. Cependant, cette situation ne se produit
que rarement dans le système et ce pour les causes suivantes :
(a) La taille totale des datasets dans le système est plus petite que celle de
la capacité de stockage disponible dans tous les datacenters, car nous
sommes sûr que les datacenters peuvent héberger tous les datasets du
système ;
(b) Pour chaque datacenter, nous réservons certain espace de stockage pour
les datasets générés pendant l’exécution (cs ∗ (λmax − λini )), cet espace
de stockage n’est pas toujours très utilisé, parce que nous supprimons les
datasets obsolètes, dynamiquement.
Dans le but d’améliorer et d’augmenter les performances de l’approche utilisée,

nous proposons de l’étendre par un service de gestion de réplication dynamique.
4.2.3 Service de gestion de réplication dynamique
Durant l’étape d’exécution, chacune des tâches va être ordonnancée vers le data-
center qui possède la majorité des datasets requis. Avec cette approche, nous allons
essayer de répliquer certains datasets dans le but de minimiser leurs déplacements
d’un datacenter vers un autre et par conséquent réduire le temps de réponse des
requêtes des utilisateurs. Pour ce faire nous avons élaboré un algorithme pour la
réplication des datasets.
Afin de répliquer certains datasets importants, les plus fréquemment utilisés, un
algorithme a été mis en place. Son principe peut être décrit comme suit :
1. Étant donné un ensemble T des tâches s’exécutant dans un datacenter donné,

nous calculons la majorité absolue pour cet ensemble. Cette majorité repré-
sente le seuil à partir duquel la réplication s’effectuera (Ligne 1 de l’Algo-
rithme 4). Ainsi, dans chaque datacenter, le seuil dépendra du nombre de
tâches s’exécutant dans ce datacenter (voir les Formules 4.10 et 4.11). Si :
N b tches = pair =⇒ Seuil = (N b tche \ 2) + 1 (4.10)
N b tches = impair =⇒ Seuil = (N b tche + 1) \ 2 (4.11)
2. Pour chaque tâche nous marquerons les datasets qui ne sont pas disponibles
dans le datacenter destinataire, c’est-à-dire, que chaque datacenter contiendra
sa propre liste de marquage qui sera établie en fonction des datasets non dispo-
nibles en local et qui doivent être déplacés (Lignes 2 jusqu’à 4 de l’Algorithme
4).
3. Si la majorité des tâches requièrent le déplacement du même dataset, ce der-

nier va être répliqué, afin d’éviter son déplacement pour chaque tâche (Lignes
6 et 7 de l’Algorithme 4).
4. La réplication doit s’effectuer au niveau du datacenter destinataire sur lequel

les tâches, qui requièrent le dataset marqué, s’exécuteront.
5. Dans le cas où il y a plusieurs datasets marqués pour lesquels le marquage

a atteint le seuil, la réplication s’effectuera pour l’ensemble de ces datasets
marqués. Une fois les datasets en question répliqués, l’exécution des tâches
commence.
Algorithme 4 Algorithme de réplication

Input : T : Ensemble de tâches.
K : Ensemble de datacenters résultant de l’étape de construction.
Output : Datasets répliqués.
Description :
Calculer le Seuil
pour chaque dcj ∈ K faire
si dj est requis par ti mais dj ∈
/ dci alors
Marquer dj
si Nombre de marquage >= Seuil alors
répliquer dj
pour chaque dcj ∈ K faire
Mettre à jour csj
Exécuter ti
La Figure 4.7 expose un diagramme d’activité décrivant le service proposé pour

les réplications dynamiques.
4.3. Stratégie d’ordonnancement basée sur le groupement de tâches 63
Figure 4.7 – Diagramme d’activité pour la phase de la réplication dynamique
4.3 Stratégie d’ordonnancement basée sur le groupe-

ment de tâches
Dans cette section, nous décrivons notre deuxième contribution à savoir une
stratégie pour l’ordonnancement des tâches et l’allocation de ressources, destinée
aux applications de workflows scientifiques distribuées. La stratégie d’ordonnance-
ment est basée sur le groupement de tâches [17] qui se compose de deux grandes
étapes :
– Etape de construction ;
– Etape d’ordonnancement.
4.3.1 Etape de construction
Nous construisons dans cette étape la matrice de dépendance, c’est une matrice
symétrique carrée (tâches/tâches), chaque case de sa diagonale représente le nombre
de données dans le Cloud, et le reste des éléments représente les dépendances entre
les tâches. Cette dépendance est calculée par la Formule suivante (voir formule
4.12) :
\
T Mij = dependencyij = Count(Di Dj ) (4.12)
Le résultat de l’application de la Formule 4.12 sur l’ensemble des données et des

tâches dans le Cloud donnera une matrice de dépendance notée T M . La Figure 4.8
donne un exemple sur cette matrice de dépendance :
Figure 4.8 – Exemple de construction de la matrice de dépendance T M
Une fois la matrice de dépendance établie. Nous appliquons l’algorithme BEA

(Bound Energy Algorithm) [43] sur la matrice T M . C’est un algorithme qui consiste
à regrouper les valeurs identiques de la matrice, ensemble, en permutant l’ensemble
des lignes et des colonnes. Deux mesures, BEC et BEL sont définies pour cet algo-
rithme. La permutation est faite de telle sorte que ces mesures (voir les Formules
4.13 et 4.14) soient maximisées :
n
X
0
BEC i, j = T Mi,j × T Mi,j+1 (4.13)
i=1
n
X
0
BEL i, j = T Mi,j × T Mi+1,j (4.14)
j=1
La Figure 4.9 donne un exemple de l’application de l’algorithme BEA sur la

matrice de dépendance de l’exemple 4.8 :
Figure 4.9 – Exemple d’application de l’algorithme BEA sur la matrice de dépen-

dance T M
Après l’application de l’algorithme BEA sur la matrice de dépendance. Nous

obtenons une matrice de dépendance clusterisée. Cette matrice est ensuite découpée
en sous matrices en définissant un point de coupure. Le nombre de sous matrices
dépend du nombre de datacenters dans le Cloud. La Figure 4.10 montre un exemple
de découpage de la matrice en deux sous matrices :
Figure 4.10 – Exemple de découpage de la matrice de dépendance clusterisée

4.3.2 Étape d’ordonnancement
Une fois le découpage de la matrice réalisé, nous obtenons un ensemble de sous

matrices. L’ensemble de groupe de tâches de chaque sous matrice est affecté au
datacenter correspondant. La figure 4.11 donne un exemple d’affectation et d’or-
donnancement des tâches dans le datacenter correspondant :
Figure 4.11 – Exemple d’affectation et d’ordonnancement des tâches dans l’en-

semble des Datacenters
La Figure 4.12 montre un diagramme d’activité décrivant la phase d’affectation

et d’ordonnancement des tâches dans l’ensemble des Datacenters et l’Algorithme 5)
décrit la phase d’ordonnancement des tâches vers les datacenters.
Figure 4.12 – Affectation et ordonnancement des tâches

4.4. Stratégies d’ordonnancement et d’allocation de ressources pour les
Big Data 67

Input :
T : Ensemble de tâches.
Output : Toutes les tâches ordonnancées vers le datacenter approprié.
Description :

si les datasets requis par ti sont disponibles alors
Ordonnancer ti vers dcj pour s’exécuter
si dcj possède la majorité des datasets requis par ti alors
Mettre état ti = prêt
sinon
état ti = non prêt
Exécuter ti
4.4 Stratégies d’ordonnancement et d’allocation de res-

sources pour les Big Data
Dans cette section, nous décrivons notre troisième contribution à savoir deux
sous-stratégies pour l’ordonnancement des tâches et l’allocation de ressources, des-
tinée aux environnements de Cloud computing. Deux variantes d’ordonnancement
des tâches et d’allocation des ressources [16] sont présentées :
4.4.1 La première variante OADTV
Nous proposons une stratégie d’ordonnancement des tâches et l’allocation des

ressources en fonction de la date limite, la taille des cloudlets et la vitesse d’exécution
de la machine virtuelle (variante OADTV). Notre proposition est différente de celle
présentée en [27] car nous ajoutons dans l’algorithme, dans la deuxième étape,
Big Data 68
la division du nombre de cloudlets par le nombre de machines virtuelles afin de

minimiser le temps d’exécution moyen de toutes les tâches. Les grandes lignes de la
stratégie sont les suivantes, et le diagramme d’activité correspondant est représenté
dans la Figure 4.13 :
Figure 4.13 – La première variante OADTV d’ordonnancement et d’allocation de

ressources dans les Cloud computing
Notre première variante d’ordonnancement est composée de trois étapes :
Étape 1 : Trier les cloudlets (tâches) en fonction de la date limite des instructions
et de leurs longueurs (taille) dans l’ordre croissant ;
Étape 2 : Trier les machines virtuelles en fonction de la vitesse d’exécution dans

l’ordre croissant ;
Big Data 69
Étape 3 : Attribuer pour chaque VM un vecteur de tâches, le nombre de cases

est égal à M qui est le nombre de tâches (nombre de cloudlets) divisé par N
(nombre de VM) ; de sorte que le premier groupe des premières tâches sont
exécutées par la première machine virtuelle, la seconde sont exécutées par la
deuxième machine virtuelle,...
Un algorithme d’ordonnancement des tâches est utilisé (Algorithme 6) :

Input :
T : Ensemble de tâches (Cloudlets).
V M : Ensemble de machines virtuelles.
Output : Toutes les tâches ordonnancées vers les machines virtuelles appropriées.
Description :

Trier ti en fonction de la date limite et la longueur
pour chaque vmi ∈ V M faire
Trier vmi en fonction de la vitesse d’exécution
Attribuer à chaque vmi un vecteur contenant la liste des ti à exécuter
pour chaque vmj ∈ V M faire
Exécuter ti dans vmj
Mettre à jour la liste des ti et vmj
4.4.2 La deuxième variante OAAMV
La deuxième stratégie d’ordonnancement des tâches et d’allocation des res-

sources utilise une structure d’arbre de données appelée Arbre de machines virtuelles
(AMV) pour l’exécution efficace des tâches. Notre algorithme est une amélioration
du travail [45], et il offre un meilleur équilibrage de charge. Un arbre de machines
Big Data 70
virtuelles (AMV) est un arbre binaire avec N nœuds. Chaque nœud représente une
machine virtuelle contenant un identifiant Id et une vitesse d’exécution exprimée en
M IP S de la machine virtuelle. N représente le nombre total de machines virtuelles
spécifiques de calcul dans le Cloud. La propriété spéciale de AMV est que la valeur
de nœud (MIPS) au niveau L est supérieure ou égale à la valeur de nœud au niveau
L + 1 où L >= 0. Chaque nœud contient zéro, un ou deux nœuds enfants. Un nœud
sans nœud enfant est appelé un nœud feuille et le nœud avec des nœuds enfants est
désigné en tant que nœud interne.
Considérons 5 machines virtuelles spécifiques de calcul représentées par leur Id
et M IP S V = {{0, 250}, {1, 1000}, {2, 250}, {3, 500}, {4, 250}}. La Figure 4.14 ci-
dessous montre le AMV. Le AMV est construit sur la base de l’ordre prioritaire des
machines virtuelles de gauche à droite, de telle sorte que la machine virtuelle avec
la plus haute M IP S devient la racine de l’arbre.
Figure 4.14 – La deuxième variante OAAMV d’ordonnancement et d’allocation de

ressources dans les Cloud computing
Dans la Figure 4.14 ; l’arbre AMV a un nœud racine représentant la machine

virtuelle avec Id = 1 et M IP S = 1000. Le nœud racine a deux enfants. Le nœud
enfant de gauche représente la machine virtuelle avec Id = 3 et M IP S = 500. Le
nœud enfant droit représente la machine virtuelle avec Id = 0 et M IP S = 250. De
même, le nœud qui représente la machine virtuelle avec Id = 3 et M IP S = 500
a 2 enf ants. L’enfant gauche de ce nœud représente les machines virtuelles avec
Big Data 71
Id = 2 et M IP S = 250, l’enfant droit représente la machine virtuelle avec Id = 4

et M IP S = 250.
Nous présentons ici une stratégie d’ordonnancement et d’allocation de ressources
basée sur un groupe de tâches dans le Cloud. Soient T COU N T le nombre to-
tal de tâches soumises et L COU N T le nombre total de nœuds feuilles en AMV.
Le nombre total de groupes G COU N T pour les tâches présentées sont calculées
comme suit : G COU N T = L COU N T . Si AMV est construit avec 5 machines
virtuelles, le nombre total des groupes est le nombre de niveau (il est égal à 3 dans
notre exemple). Le nombre de tâches de chaque groupe G est calculé comme suit,
G = Nombre de niveaux. Chaque groupe contient le nombre maximum de tâches en
MIPS, qui ne doit pas dépasser une valeur qui est calculée par la Formule 4.15, et
chaque groupe de tâches est assigné pour chaque niveau, le premier dans le niveau
supérieur (racine), le deuxième groupe dans le second et le dernier groupe dans le
troisième niveau.
X X X
lengthof tasks ∈ G COU N T <= lengthof tasks∗(V M M ipsinlevel)÷ M ipsof V M s
(4.15)
Un algorithme d’ordonnancement des tâches est utilisé (Algorithme 7) :
Big Data 72

Input : T : Ensemble de tâches (Cloudlets).
V M : Ensemble de machines virtuelles.
L COU N T : Le nombre total de nœuds feuilles en AMV.
G COU N T : Le nombre total de groupes G COU N T
Output : Toutes les tâches ordonnancées vers les machines virtuelles appropriées.
Description :
pour chaque vmi ∈ V M faire

Trier vmi en fonction de la vitesse d’exécution Mips
Attribuer chaque vmi comme racine à l’arbre AMV
G COU N T = L COU N T
Trier ti en fonction de la longueur Mips
pour chaque vmj ∈ G COU N T faire
P
Attribuer ti à vmj tel que lengthof tasks ∈ G COU N T <=
P P
lengthof tasks ∗ (V M M ipsinlevel) ÷ M ipsof V M s
pour chaque vmj ∈ V M faire
Exécuter ti dans vmj
Mettre à jour la liste des ti et vmj
Prenons l’exemple de 12 tâches représentées par leurs Id et leurs longueurs

(MIPS) tel que :
G = {{0, 20000}, {1, 20000}, {2, 20000}, {3, 10000}, {4, 10000}, {5, 20000}, {6, 10000},
{7, 20000}, {8, 10000}, {9, 10000}, {10, 20000}, {11, 10000}}.
Après le découpage et le regroupement de tâches, chaque groupe contient les
tâches suivantes :
Big Data 73
G1 = {{0, 20000}, {1, 20000}, {2, 20000}, {5, 20000}}

G2 = {{7, 20000}, {10, 20000}, {3, 10000}, {4, 10000}}
G3 = {{6, 10000}, {8, 10000}, {9, 10000}, {11, 10000}}
Une fois les regroupements des tâches sont effectuées, les machines virtuelles
appropriées sont sélectionnées pour l’exécution. Les tâches de chaque groupe sont
sélectionnées séquentiellement et soumises à la machine virtuelle correspondante.
L’ordre est le suivant : La première tâche du groupe G1 est exécutée par la machine
virtuelle représentée par le nœud racine de l’arbre AMV. La deuxième tâche sera
exécutée par son enfant, la troisième tâche sera exécutée par le petit-enfant et
ainsi de suite. Une fois qu’elle atteint la machine virtuelle représentée par le nœud
feuille, la tâche suivante sera soumise à nouveau au nœud racine et ainsi de suite.
La même procédure est répétée pour toutes les tâches de chaque groupe. La Figure
4.15 ci-dessous montre l’arbre AMV pour 5 machines virtuelles et le nombre total
de groupes formés pour les 12 tâches soumises.
Figure 4.15 – Le résultat d’exécution des tâches
Ici, le nombre total de tâches soumises sera rassemblé en 3 groupes à savoir

G1, G2 et G3 respectivement. Les tâches avec Id = 0, 2, 5, 7 seront dans le groupe
G1, les tâches avec Id = 10, 1, 3, 4 seront dans le groupe G2 et les tâches avec
Id = 6, 8, 9, 11 seront dans le groupe G3 respectivement.
4.5. Conclusion 74
4.5 Conclusion
Au cours de ce chapitre, nous avons essayé de décrire nos trois contributions pour
l’ordonnancement et l’allocation de ressources, nous avons présenté les différentes
étapes à suivre pour l’utilisation de nos trois stratégies. Nous avons étendue la
première stratégie par un service de réplication dynamique, la seconde stratégie
d’ordonnancement est basée sur le groupement de tâches et la dernière stratégie
d’ordonnancement de tâches et d’allocation de ressources est destinée pour les Big
data. Du point de vue technique, nous avons utilisé un ensemble d’algorithmes, de
formules et de diagrammes UML pour faciliter la compréhension et la lecture du
chapitre, d’une part, et d’autre part pour donner un schéma conceptuel général du
travail réalisé.
Dans le chapitre suivant, nous nous intéressons à la concrétisation des stratégies
proposées et cela par l’implémentation de nos stratégies présentées et les différentes
interprétations des résultats obtenus par la simulation.
Chapitre 5
Expérimentation et évaluation
Sommaire
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Langage et environnements de travail . . . . . . . . . . . . . 76
5.2.1 Langage de programmation Java . . . . . . . . . . . . . . . . . 76
5.2.2 Environnements de développement . . . . . . . . . . . . . . . . 76
5.3 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . 79
5.3.1 Résultats expérimentaux 1 : Stratégie d’ordonnancement basée
sur la réplication de données . . . . . . . . . . . . . . . . . . . 79
5.3.2 Résultats expérimentaux 2 : Stratégie d’ordonnancement basée
sur le groupement de tâches . . . . . . . . . . . . . . . . . . . . 88
d’allocation de ressources pour les Big Data . . . . . . . . . . . 92
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.1 Introduction
e chapitre est consacré à la phase d’implémentation des stratégies d’ordon-

C nancement et d’allocation de ressources proposées. Il permettra d’évaluer et
de valider nos stratégies proposées dans l’environnement de Cloud computing par
rapport aux objectifs tracés dans le cahier des charges initial. Pour cela, nous avons
réalisés plusieurs simulations soit en utilisant notre simulateur développé en Java,
soit en utilisant le simulateur CloudSim [12], dans le but d’effectuer des séries d’ex-
périmentations dont les résultats et les interprétations font l’objet de ce chapitre.
5.2. Langage et environnements de travail 76
5.2 Langage et environnements de travail
Nous avons utilisé le langage de programmation Java, les environnements de

développement Eclipse et Netbeans, et le simulateur CloudSim.
5.2.1 Langage de programmation Java
Le langage Java est un langage de programmation informatique orienté objet

[14, 21, 58]. Java a la particularité principale d’être portable, c’est à dire, que les
logiciels écrits avec ce dernier sont très facilement réutilisable sur plusieurs systèmes
d’exploitation tels qu’UNIX, Microsoft Windows, Mac OS ou Linux avec peu ou pas
de modifications. C’est la plate-forme qui garantit la portabilité des applications
développées en Java.
Le langage reprend en grande partie la syntaxe du langage C++, très utilisé par
les informaticiens. Néanmoins, Java a été épuré des concepts du C++ et à la fois
les plus déroutants, tels que l’héritage multiple remplacé par l’implémentation des
interfaces. Les concepteurs ont privilégié l’approche orientée objet de sorte qu’en
Java, tout est objet à l’exception des types primitifs (nombres entiers, nombres à
virgule flottante, ...).
Java est un langage de développement créé par Sun puis racheté par Oracle en
2010 qui a réussi à obtenir une très grande notoriété en seulement quelques années
grâce à ces qualités. Aujourd’hui Java est largement utilisé notamment en entreprise
et pour les applications pour appareils mobiles. Java représente la synthèse des bons
côtés de plusieurs langages de programmation (notamment C++ et Small Talk).
5.2.2 Environnements de développement
Eclipse
Eclipse est un environnement de développement intégré (Integrated Develop-
ment Environment) dont le but est de fournir une plate-forme modulaire pour per-
mettre de réaliser des développements informatiques.
I.B.M. est à l’origine du développement d’Eclipse qui est d’ailleurs toujours le
cœur de son outil Websphere Studio Workbench (WSW), lui-même à la base de la
famille des derniers outils de développement en Java d’I.B.M. Tout le code d’Eclipse
a été donné à la communauté par I.B.M afin de poursuivre son développement [19].
Eclipse utilise énormément le concept de modules nommés «Plug-Ins» dans
son architecture. D’ailleurs, hormis le noyau de la plate-forme nommé «Runtime»,
tout le reste de la plate-forme est développé sous la forme de Plug-Ins. Ce concept
permet de fournir un mécanisme pour l’extension de la plate-forme et ainsi fournir
la possibilité à des tiers de développer des fonctionnalités qui ne sont pas fournies en
standard par Eclipse. Eclipse possède de nombreux points forts qui sont à l’origine
de son énorme succès dont les principaux sont :
– Une plate-forme ouverte pour le développement d’applications et extensible
grâce à un mécanisme de Plug-Ins.
– Plusieurs versions d’un même Plug-In peuvent cohabiter sur une même plate-
forme ;
– Un support multi langages grâce à des Plug-Ins dédiés : Cobol, C, PHP, ...
– Support de plusieurs plateformes : Windows, Linux, Mac OS X, ...
– Les nombreuses fonctionnalités de développement proposées par le JDT.
– Le gestionnaire de mise à jour permet de télécharger de nouveaux Plug-ins ou
nouvelles versions d’un Plug-in déjà installées à partir de sites Web dédiés.
NetBeans
NetBeans est un projet open source ayant un succès et une base d’utilisateur très
large, une communauté en croisance constante, et près 100 partenaires mondiaux et
des centaines de milliers d’utilisateur à travers le monde. Sun Microsystems a fondé
le projet open source NetBeans en Juin 2000 et continue d’être le sponsor principal
du projet [2].
Aujourd’hui, deux projets existent : L’EDI NetBeans et la Plateforme NetBeans.
L’EDI NetBeans est un environnement de développement, un outil pour les pro-
grammeurs pour écrire, compiler, déboguer et déployer des programmes. Il est écrit
en Java mais peut supporter n’importe quel langage de programmation. Il y a égale-
ment un grand nombre de modules pour étendre l’EDI NetBeans. L’EDI NetBeans
est un produit gratuit, sans aucune restriction quant à son usage.
Également disponible, La Plateforme NetBeans ; une fondation modulable et
extensible utilisée comme brique logicielle pour la création d’applications bureau-

tiques. Les partenaires privilégiés fournissent des modules à valeurs rajoutées qui
s’intègrent facilement à la Plateforme et peuvent être utilisés pour développer ses
propres outils et solutions. Les deux produits sont open source et gratuits pour un
usage commercial et non-commercial. Le code source est disponible pour réutilisa-
tion sous la Common Development and Distribution License (CDDL).
CloudSim
CloudSim est un Framework de simulation généralisé et extensible qui permet
la modélisation, la simulation et l’expérimentation des nouvelles infrastructures de
Cloud Computing et des services d’application associés. Nous avons utilisé pour la
réalisation de nos travaux de thèse la version du simulateur CloudSim 3.0.3.
Le simulateur ClouSim est composé de plusieurs classes (Figure 5.1). Parmi les
classes fondamentales qui forment les blocs constitutifs du simulateur CloudSim,
nous pouvons citer :
Datacenter : La classe Datacenter permet de modéliser le cœur de l’infrastruc-

ture du Cloud. elle encapsule un ensemble de machines physiques appelées
Hosts qui se caractérisent par leurs configurations (mémoire, CPU, stockage
et nombre de cœurs). Chaque Datacenter implémente un ensemble d’algo-
rithmes pour l’allocation de la bande passante, la mémoire et le stockage aux
différents hosts et machines virtuelles du Cloud.
Cloudlet : La classe Cloudlet modélise les applications. Elle a un nombre d’ins-

tructions et de données connu à exécuter et à transférer. A noter que cette
classe est étendue par WorkflowSim en Task puis en Job pour modéliser les
relations de dépendances entre les tâches.
Datacenter Broker : Cette classe modélise le courtier (Broker), qui est respon-
sable de la médiation entre les utilisateurs et les prestataires de service selon
les conditions de QoS des utilisateurs et elle permet de déployer les tâches de
service à travers les Clouds. Le Broker agit au nom des utilisateurs, il identifie
les prestataires de service appropriés du Cloud par le service d’information
du Cloud CIS (Cloud Information Services) et négocie avec eux pour une
5.3. Résultats expérimentaux 79
allocation des ressources qui répond aux besoins de QoS des utilisateurs.
Machine virtuelle : Cette classe modélise une instance de la machine virtuelle

(VM), dont la gestion pendant son cycle de vie, est une responsabilité de la
machine (Host). Un Host peut simultanément instancier de multiples VMS et
assigner des cœurs à base des politiques prédéfinies de partage de processeur :
espace partagé ou temps partagé (voir Annexe B).
Figure 5.1 – Les principales classes de CloudSim [56]
5.3 Résultats expérimentaux

sée sur la réplication de données
5.3.1.1 Description du simulateur
Dans cette partie, nous allons nous intéresser à la démonstration du simulateur

réalisé, qui est écrit en Java et qui permet de tester à travers des exemples et des scé-
narios de simulation [4], la stratégie d’ordonnancement basée sur la réplication qui
est présenté dans le chapitre 4, en faisant référence à quelques interfaces graphiques.
5.3.1.2 Création d’un nouveau workflow et configuration des Datacen-

ters
La première chose à effectuer est le déploiement d’un nouveau workflow sur le

système. L’utilisateur introduit certaines informations concernant le workflow. Il
s’agit du nombre de sous-ensembles de tâches (les tâches sont regroupées en lots) ;
du nombre de tâches, du nombre de données ; des datacenters requis, du nombre de
données générées (voir Figure 5.2).
Figure 5.2 – Création d’un nouveau workflow
Toutes les informations sont mises, initialement à 10. Cependant l’utilisateur

peut les modifier en introduisant de nouvelles valeurs. Aussi, l’utilisateur doit choi-
sir le type d’application parmi celles disponibles, c’est-à-dire, à quel domaine son
workflow appartient, pour que le système puisse déterminer le pourcentage initial
de la capacité de stockage autorisée pour héberger les données (il faut laisser un
espace libre pour stocker ; ensuite les données générées).
Du moment où le nombre de datacenters requis est spécifié, l’utilisateur peut
passer à leurs configurations en introduisant, à chaque fois le nombre d’hôtes, de
machines virtuelles, de processeurs, la bande passante, son coût d’utilisation, la
capacité de stockage et son coût d’utilisation.
5.3.1.3 Déploiement et clusterisation de la matrice de dépendance
A l’issue de l’étape de saisie, toutes les configurations concernant le Cloud et

le workflow, sont effectuées. Ainsi, les calculs concernant la stratégie peuvent com-
mencer. Ces derniers commencent par l’élaboration de la matrice de dépendance.
La Figure 5.3 suivante montre la création de la matrice de dépendance :
Figure 5.3 – Déploiement de la matrice de dépendance
Après l’étape de construction de la matrice de dépendance, on passe à l’étape

de clusterisation de la matrice de dépendance avec l’algorithme BEA. La Figure 5.4
montre le résultat obtenu :
Figure 5.4 – Clusterisation de la matrice de dépendance

5.3.1.4 Partitionnement et distribution
La troisième étape de la stratégie est le partitionnement et la distribution des

données sur les datacenters. Un journal décrivant la traçabilité du partitionnement
des données a été mis en place (voir Figure 5.5).
Figure 5.5 – Partitionnement et distribution des données
5.3.1.5 Gestion des données générées
Après avoir effectué la simulation, c’est à dire que les tâches se sont exécutées, de
nouvelles données sont générées. Leur classification est effectuée grâce à l’algorithme
des K-means (voir Figure 5.6).
Figure 5.6 – Gestion des données générées

5.3.1.6 Expérimentations
Dans cette partie, nous allons effectuer plusieurs séries de simulations sur trois
types d’approches :
(i) Approche FCFS (First Come First Served) : Représente la première

approche dans laquelle les données et les tâches sont affectées, aléatoirement,
avec une file d’attente FIFO (First In First Out), aux différents datacenters.
(ii) Approche de placement des données : Représente la deuxième approche

dans laquelle la stratégie de placement de données est utilisée.
(iii) Approche de réplication : Représente la troisième approche dans laquelle

la réplication des données est effectuée.
Expérience 1 : Temps de réponse

Dans cette première série d’expériences, nous avons mesuré le temps de réponse.
Ce dernier est calculé en fonction de l’emplacement des données, c’est-à-dire, inclure
la latence ou le temps d’attente pour les données qui ne se trouvent pas en local.
Pour cela nous avons lancé la simulation avec les trois approches. Les simulations
ont été réalisés avec les paramètres décrits dans le tableau 5.1 :
Paramètres Valeurs
Nombre de données 100
Taille des données 3000 Go
Nombre des datacenters 20
Capacité de stockage 30000 Go
Nombre de hosts 10
Nombre de VMs 1
Bande passante 10 Go/s
Table 5.1 – Les paramètres de simulation pour le temps de réponse
Le résultat des simulations est donné dans la Figure 5.7 :

Temps de réponse moyen

3200000
3000000
2800000
2600000
Temps de réponse moyen (ms)
2400000
2200000
2000000
1800000
1600000
1400000
1200000
1000000
800000
600000
400000
200000
0
200 400 600 800 1000
Nombre de tâches
Stratégie FCFS Stratégie de placement Stratégie de réplication
Figure 5.7 – Le temps de réponse moyen
Le gain obtenu est donné dans la Figure 5.8 :
Le gain pour le temps de réponse

110
100
90
Le gain pour le temps de réponse (ms)
80
70
60
50
40
30
20
10
0
200 400 600 800 1000
Nombre de tâches
Gain/ Stratégie de placement Gain/ Stratégie de réplication
Figure 5.8 – Le gain obtenu pour le temps de réponse

Expérience 2 : Nombre de déplacements

Dans cette deuxième série d’expériences, nous avons mesuré le nombre de dé-
placements. Pour cela nous avons lancé la simulation avec les trois approches. Les
simulations ont été réalisé savec les paramètres décrits dans le tableau 5.2.
Paramètres Valeurs
Nombre de tâches 100
Taille des données 3000 Go
Nombre des datacenters 20
Capacité de stockage 30000 Go
Nombre de hosts 10
Nombre de VMs 1
Bande passante 10 Go/s
Table 5.2 – Les paramètres de simulation pour le nombre de déplacements
Le résultat des simulations est donné dans la Figure 5.9 :
Nombre de déplacement des données

110
100
90
80
70
Données
60
50
40
30
20
10
0
D0 D1 D2 D3 D4 D5 D6 D7 D8 D9
Nombre de déplacement
Figure 5.9 – Le nombre de déplacement des données

Le gain obtenu pour le nombre de déplacement

120
Le gain pour le nombre de déplacement (%)

100
80
60
40
20
-20
-40
1
0
9
4
D
D
D
D
Données
Figure 5.10 – Le gain obtenu pour le déplacement des données
Expérience 3 : Coût de la réplication

Dans cette troisième série d’expériences, nous avons mesuré le coût de la ré-
plication. Pour cela nous avons lancé la simulation avec les trois approches. Les
résultats de simulation ont été réalisés avec les mêmes paramètres de simulation en
faisant varier le nombre de datacenters et le nombre de tâches comme montre la
figure 5.11 :
Le coût de la réplication pour le temps de réponse

2000000
1800000
1600000
Temps réponse moyen (ms)
1400000
1200000
1000000
800000
600000
400000
200000
0
es
es
es
es
es
ch
ch
ch
ch
ch
tâ
tâ
tâ
tâ
tâ
0
0
0
0
50
60
30
40
20
C
C
C
C
D
D
D
D
10
12
6
8
4
Figure 5.11 – Le coût de la réplication

Le gain pour le coût de la réplication
Gain pour le coût de la réplication (%)

100
80
60
40
20
es
es
es
es
es
ch
ch
ch
ch
ch
tâ
tâ
tâ
tâ
tâ
0
0
0
0
50
60
30
40
20
C
C
C
C
D
D
D
D
10
12
6
8
4
Figure 5.12 – Le gain obtenu pour le coût de la réplication
Expérience 4 : Coût global engendré

Dans cette série d’expériences, nous avons calculé le coût global engendré. Ce
dernier est calculé en fonction du coût de la bande passante et du coût de stockage
(car ce sont les deux facteurs pertinents dans notre travail). Pour cela nous avons
lancé la simulation avec les trois approches cités auparavant. Les simulations ont
été réalisés avec les mêmes paramètres de simulations avec 600 tâches. La Figure
5.13 ci-dessus montre le résultats de simulation :
Figure 5.13 – Le coût global engendré

Synthèse des résultats obtenus :

Nous avons réalisé plusieurs simulations en faisant varier plusieurs critères d’éva-
luation du système comme : Le temps de réponse moyen d’exécution des tâches, le
nombre de déplacement des données, le coût de réplication et le coût global d’utili-
sation de ressources.
Après avoir fait plusieurs essais de simulation, nous avons pu extraire les re-
marques suivantes :
– Les premiers graphes (Figures5.7 et 5.8) concernant le temps de réponse
moyen des requêtes montrent que le temps de réponse diminue d’une façon
remarquable en utilisant la stratégie de réplication puisque les données sont
répliquées avant l’exécution des tâches.
– Dans les graphes des (Figures 5.9 et 5.10), nous remarquons que le nombre
de déplacement de données entre les centres de données a réduit considéra-
blement puisque nous avons complété l’approche par un service de réplication
dynamique intelligente de données.
– Les graphes des Figures (5.11, 5.12 et 5.13) montrent l’effet de l’utilisation
du service de réplication dans la réduction du temps de réponse des tâches
puisque les données seront trouvées sur des machines virtuelles plus proches,
ce qui minimise en plus le temps de réponse des requêtes en augmentant le
coût de la réplication et par conséquent le coût d’utilisation des ressources.

sée sur le groupement de tâches
Dans cette partie, les expériences sont réalisées dans un environnement de Cloud
fourni par le simulateur CloudSim (voir Annexe B)
5.3.2.1 Mesures de performances
Nous présentons les mesures de performances sur lesquelles nous sommes ap-
puyées pour interpréter les résultats obtenus par les simulations puis comparer
entre les différentes approches. Les deux principales mesures de performances sont
le temps de réponse et le budget (coût financier). Ce sont des mesures classiques

pour tester l’efficacité des algorithmes d’ordonnancement et de gestion de ressources.
Le Temps de réponse : Ti étant la date de fin du job i Le temps de réponse est

calculé à partir du Makespan Makespan = max Ti
Il représente tout simplement la date fin du dernier job, parmi tous les jobs
exécutés.
Le budget : Nous avons proposé quelques formules pour calculer le budget. Pour
calculer le coût de traitement des cloudlets qui est égal à la somme du coût
de traitement et de transfert des fichiers d’entrées et de sorties, est donnée
comme suite :
P rocessingCost = (ActuelT imeCP U ×CostP erSec)+InputDataT ransf er+
OutputT ansf erCost
Où le coût total de transfert du fichier d’entrée est comme suit :

InputDataT ransf er = CostP erBW × GetCloudletF ilesize
Et le coût total de transfert du fichier de sortie est égal à l’équation :

OutputT ansf erCost = CostP erBW × GetCloudletOutputsize.
5.3.2.2 Scénarios et résultats
Dans cette partie, nous allons effectuer plusieurs séries de simulations sur les
trois approches :
(i) La politique d’ordonnancement Space Shared (Espace partagé) :

Cette politique suit la même procédure que l’algorithme du premier arrivé,
premier servi.
(ii) La politique d’ordonnancement Time Shared (Temps partagé) : Le

principe de l’algorithme d’ordonnancement Round-Robin (RR) est utilisé dans
cette politique.
(iii) La politique d’ordonnancement Time Shared Clustering : Cette poli-

tique suit la même procédure que la stratégie d’ordonnancement basée sur le
groupement de tâche présenté dans le chapitre 4.
– Résultat 1 (Le temps de réponse moyen) :

Dans cette première simulation, nous avons calculé le temps de réponse moyen
par les techniques TimeShared et TimeShared Clustering (stratégie 2 proposée en
chapitre 4). Pour un nombre de Cloudlets (tâches) différents «20, 40, 60, 80, 100,
200, 300, 400, 500» avec une longueur correspondante aux données de Cloudlets. Les
Figures 5.14 et 5.15 montrent le résultat d’exécution du temps de réponse moyen.
Le temps de réponse moyen

850
800
750
700
650
600
550
500
Temps (s)
450
400
350
300
250
200
150
100
50
0
20 40 60 80 100
Nombre de cloudlets
Time Shared Time Shared Clustering
Figure 5.14 – Le temps de réponse moyen
Le temps de réponse moyen

6000
5500
5000
4500
4000
3500
Temps (s)
3000
2500
2000
1500
1000
500
0
100 200 300 400 500
Nombre de cloudlets
Time Shared Time Shared Clustering
Figure 5.15 – Le temps de réponse moyen pour des tâches>=100

D’après ces résultats, nous remarquons que le temps de réponse moyen en Time-
Shared augmente à chaque fois qu’on augmente le nombre de Cloudlets car plusieurs
Cloudlets sont traitées à la fois, alors l’exécution prend beaucoup de temps pour
traiter toutes les Cloudlets, par conséquent le temps de réponse moyen augmente à
chaque fois. Par contre en TimeShared Clustering le temps de réponse moyen est
très faible car les Cloudlets sont répartis sur les différents Datacenters. L’allure de
la courbe en TimeShared Clustering est presque linéaire avec une pente faible par
rapport à la courbe TimeShared.
– Le coût de traitement moyen des Cloudlets :
Dans cette série de simulation, nous avons calculé le coût de traitement moyen des
Cloudlets avec les deux algorithmes (TimeShared et TimeShared Clustering).
Les Figures 5.16 et 5.17 montrent l’impact du nombre de cloudlets sur le coût
de traitement, sur des histogrammes, les principales exécutions réalisées sur
ce scénario.
Le coût de traitement moyen des cloudlets

14000
12086
12000
10000
7719
Coût ($)
8000
6000
4140
4000
2026
2000 1288 1550
672 972
585 358
0
0
20
60
80
40
10
Cloudlets
Timeshared TimeShared Clustering
Figure 5.16 – Le coût de traitement moyen des Cloudlets


350000
300000
250000
Coût ($)
200000
150000
100000
50000
0
0
0
0
10
20
30
50
40
Cloudlets
Timeshared TimeShared Clustering
Figure 5.17 – Le coût de traitement moyen pour des tâches>=100
L’objective de cette série de simulation est d’étudier l’impact de notre stra-

tégie sur le coût de traitement moyen des Cloudlets. D’après ces résultats, nous
remarquons que le coût de traitement moyen dans l’algorithme TimeShared est très
élevé par rapport à la stratégie TimeShared Clustering car l’utilisation de CPU
est moins importante qu’en TimeShared. Les différentes partitions contiennent les
mêmes données donc l’utilisation de CPU est amoindri.

d’allocation de ressources pour les Big Data
Les expériences sont réalisées dans un environnement de Cloud fourni par le

simulateur CloudSim (voir Annexe B).
5.3.3.1 Paramètres de simulation
La vitesse de chaque élément de traitement est exprimé en MIPS (millions d’ins-

tructions par seconde) et la longueur de chaque Cloudlet (tâche) est exprimée par
le nombre d’instructions à exécuter. L’environnement de simulation se compose de
deux datacenters avec deux hôtes ayant deux éléments de calcul chacun. Chaque
élément de calcul a une puissance de calcul varié (selon le paramètre MIPS). Les
algorithmes sont testés en faisant varier le nombre de cloudlets entre 10 et 50 par
un pas de 20, et en changeant aussi la longueur des cloudlets. En outre, le nombre
de machines virtuelles utilisées pour exécuter les cloudlets, sont modifiées en consé-
quence.
5.3.3.2 Scénarios et résultats
Dans cette partie, nous allons effectuer des simulations en comparant les deux
sous-stratégies proposées avec les deux politiques d’ordonnancements implémentées
dans le simulateur CloudSim :
1. La politique d’ordonnancement Space Shared (Espace partagé) :

Cette politique suit la même procédure que l’algorithme du premier arrivé,
premier servi.
2. La politique d’ordonnancement Time Shared (Temps partagé) : Le

concept de l’algorithme d’ordonnancement Round-Robin (RR) est utilisé dans
la présente politique.
Le temps de réponse global pour exécuter les cloudlets est utilisé comme indi-
cateur pour évaluer les performances de la première sous-stratégie (OADTV). Les
résultats sont présentés dans le tableau 5.3 et la Figure 5.18 :
Première straté-
Time Shared(s) Space Shared(s)
gie proposée(s)
Temps de réponse
734,92 840,75 646,63
10 Cloudlets
Temps de réponse
3185,15 2204,34 2032,39
30 Cloudlets
Temps de réponse
8959 3776,8 3548,35
50 Cloudlets
Table 5.3 – Résultat de simulation de la première stratégie (OADTV)

Le temps de réponse total

10000
9000
8000
7000
6000
Temps (s)
5000
4000
3000
2000
1000
0
10 30 50
Nombre de cloudlets
Time Shared Space Shared Stratégie proposée
Figure 5.18 – Le résultat de temps de réponse dans l’exécution des tâches
La Figure 5.19 ci-dessous montre le gain obtenu :
Le gain obtenu pour le temps de réponse

6500
6000
5500
5000
4500
4000
Gains (s)
3500
3000
2500
2000
1500
1000
500
0
s
s
et
et
et
dl
dl
dl
u
u
lo
lo
lo
C
C
10
30
50
Gain/ Time Shared Gain/ Space Shared
Il a été constaté que, pour un petit nombre de tâches, les trois algorithmes
présentent des performances plus ou moins similaires. Mais, comme le montre le
tableau 5.3 et la figure 5.19. Lorsque le nombre de tâches augmente, la première

stratégie proposée présente une meilleure performance par rapport à la politique de
l’espace partagé et la politique du temps partagé, puisque les tâches les plus longues
sont affectées aux machine virtuelles les plus puissantes et les plus rapides.
Pour la deuxième sous-stratégie (OAAMV), les expériences sont menées sur un
environnement de Cloud avec les mêmes paramètres de simulation. Le temps de
réponse global pour exécuter les cloudlets est utilisé comme indicateur pour évaluer
les performances de la première stratégie. Les résultats sont présentés dans le tableau
5.4 et la Figure 5.20 :
Deuxième straté-
Time Shared(s)
gie proposée(s)
Temps de réponse
1334,94 980
10 Cloudlets
Temps de réponse
11475,05 8819,98
30 Cloudlets
Temps de réponse
31875,7 24959,88
50 Cloudlets
Table 5.4 – Résultat de simulation de la deuxième stratégie (OAAMV)
Le temps de réponse des cloudlets

40000
35000
Temps de réponse (s)
30000
25000
20000
15000
10000
5000
0
s
s
et
et
et
dl
dl
dl
ou
ou
ou
cl
cl
cl
10
30
50
Cloudlets
Timeshared Stratégie2 propsée
Figure 5.20 – Le résultat de temps de réponse pour l’exécution des tâches

La Figure 5.21 ci-dessous montre le gain obtenu :
Le gain obtenu/ TimeShared pour le temps de réponse

8000
7000
6000
5000
Gain (s)
4000
3000
2000
1000
0
s
s
et
et
et
dl
dl
dl
ou
ou
ou
cl
cl
cl
10
30
50
Cloudlets
Nous pouvons remarqué que, pour un petit nombre de tâches, tous les deux
algorithmes présentent des performances plus ou moins similaires puisque les lon-
gueurs des cloudlets sont petites. Mais, comme le montre le tableau 5.4 et les Figures
5.20 et 5.21. Lorsque le nombre de tâches augmente, la seconde stratégie présente
une meilleure performance par rapport à la politique de temps partagé, puisque les
tâches sont affectées équitablement sur l’ensemble des machines virtuelles. Les deux
sous-stratégies peuvent fournir un meilleur temps de réponse, temps d’attente, et
un meilleur équilibrage de charge.
Dans cette dernière partie, nous allons effectuer des simulations en comparant
l’hybridation des deux sous-stratégies proposées avec la politique d’ordonnancement
Time Shared, implémentée sous le simulateur CloudSim. Les algorithmes sont testés
en faisant varier le nombre de cloudlets entre 100 à 700 par pas de 100, en changeant
la longueur des cloudlets. En outre, le nombre de machines virtuelles utilisées pour
exécuter les cloudlets, sont modifiées en conséquence. Le temps de réponse pour
exécuter les cloudlets et le coût global d’utilisation de ressources sont utilisés comme
des indicateurs pour évaluer les performances de la stratégie. Les résultats sont
présentés dans les Figures 5.22 et 5.23 :
Le temps de réponse des cloudlets

450
400
350
Temps de réponse (s)
300
250
200
150
100
50
0
0
0
0
10
20
30
50
60
70
40
Cloudlets
Timeshared Stratégie propsée
Figure 5.22 – Le temps de réponse moyen des Cloudlets

1600
1400
1200
1000
Coût ($)
800
600
400
200
0
0
0
0
10
20
30
50
60
70
40
Cloudlets
TimeShared Stratégie proposée
Figure 5.23 – Le coût moyen d’utilisation de ressources
Les graphes des Figures 5.22 et 5.23 montrent l’effet de l’équilibrage de charge
dans l’exécution des tâches entre les différentes machines virtuelles dans la réduction
du temps de réponse des tâches puisque les tâches seront exécutées sur les différentes
5.4. Conclusion 98
machines virtuelles équitablement ce qui minimise en plus le temps de réponse des

tâches en augmentant les cloudlets et par conséquent le coût de traitement moyen
des cloudlets pour les Big data.
5.4 Conclusion
Dans ce chapitre, nous avons simulé nos trois stratégies proposées sous le simu-
lateur réalisé en Java et sous le simulateur CloudSim pour étudier leurs comporte-
ments. Nous avons comparé les résultats obtenu avec des approches existantes tel
que la stratégie d’ordonnancement FCFS (First Come First Served) et RR (Round
Robin) et les stratégies déjà implémentées sous le simulateurs CloudSim, à savoir
(Space Shared et Time Shared). Comme métriques de performance, nous avons uti-
lisé le temps de réponse, le nombre de déplacement des données et le coût de la
réplication pour les workflows scientifiques, et le coût global engendré.
En résumé, les résultats de simulation des stratégies d’ordonnancement et d’al-
location de ressources proposées ont donné un comportement positif et les résultats
obtenus sont très encourageant qui répondent aux objectifs tracés dans le cahier de
charge initial.
Chapitre 6
Conclusion générale
e Cloud computing ou informatique en nuage est une infrastructure dans la-

L quelle la puissance de calcul et le stockage sont gérés par des serveurs distants
auxquels les usagers se connectent via une liaison Internet sécurisée. L’ordinateur de
bureau ou portable, le téléphone mobile, la tablette tactile et autres objets connec-
tés deviennent des points d’accès pour exécuter des applications ou consulter des
données qui sont hébergées sur les serveurs. Le Cloud se caractérise également par
sa souplesse qui permet aux fournisseurs d’adapter automatiquement la capacité de
stockage et la puissance de calcul aux besoins des utilisateurs.
Le Cloud computing est la prochaine génération dans l’informatique. Probable-
ment les gens peuvent avoir tout ce qu’ils ont besoin sur le Cloud. Le Cloud est la
prochaine étape normale dans l’évolution des services sur la demande et des produits
de technologie de l’information. Le Cloud est une technologie de calcul naissante
qui se consolide rapidement comme prochaine grande étape dans le développement
et le déploiement d’un nombre croissant des applications réparties. Le Cloud a été
émergé pour des variétés d’entreprises d’Internet, beaucoup de cadres de calcul pour
la mémoire énorme de données et les besoins de calcul fortement parallèles.
La théorie de l’ordonnancement est une branche de la recherche opérationnelle
qui s’intéresse au calcul de dates d’exécution optimales de tâches. Pour cela, il est
très souvent nécessaire d’affecter en même temps les ressources nécessaires à l’exé-
cution de ces tâches. Un problème d’ordonnancement peut être considéré comme
un sous-problème de planification dans lequel il s’agit de décider de l’exécution
opérationnelle des tâches planifiées.
Dans la résolution d’un problème d’ordonnancement, deux grands types de stra-
tégies peuvent être utilisées, visant respectivement l’optimalité des solutions, ou plus
100
simplement leur admissibilité. L’approche par optimisation suppose que les solutions
candidates à un problème puissent être ordonnées de manière rationnelle selon un
ou plusieurs critères d’évaluation numériques, construits sur la base d’indicateurs
de performances. On cherchera donc à minimiser ou maximiser de tels critères liés
au temps ou aux ressources.
L’ordonnancement de tâches et d’allocation de ressources dans les systèmes de
Cloud computing suscite une attention croissante avec l’augmentation de la popu-
larité de Cloud. En général, l’ordonnancement de tâches est le processus d’affec-
tation des tâches aux ressources disponibles sur la base des caractéristiques et des
conditions des tâches. C’est un aspect important dans le fonctionnement efficace du
Cloud, car de divers paramètres de tâches doivent être pris en considération pour
un ordonnancement approprié. Les ressources disponibles devraient être utilisées
efficacement sans affecter les paramètres de service du Cloud.
Pour optimiser l’ordonnancement et l’allocation de ressources dans les Cloud
computing, nous avons proposé dans cette thèse trois stratégies d’ordonnancement,
la première stratégie d’ordonnancement est basée sur la réplications des données
pour les workflows scientifiques, la seconde stratégie d’ordonnancement est basée
sur le groupement de tâches et la dernière stratégie d’ordonnancement de tâches
et d’allocation de ressources pour les Big data. La première stratégie comporte
trois phases, nommée respectivement, l’étape de construction, l’étape d’exécution
et l’étape de réplication. La deuxième stratégie basée sur le groupement de tâche,
contient à son tour deux phases, nommée respectivement l’étape de construction
et l’étape d’ordonnancement. La troisième stratégie contient deux sous stratégies,
la première basée sur des paramètres d’optimisation de Cloud, tel que la vitesse
d’exécution des machines virtuelles et la longueur des tâches. La seconde est basée
sur un arbre de construction de machines virtuelles.
Dans ce travail, nous avons simulé les trois stratégies proposées sous un simula-
teur réalisé en Java et sous le simulateur Cloudsim pour étudier leurs comportements
et nous avons comparé les résultats obtenus avec des approches existantes telque la
stratégie d’ordonnancement FCFS (First Come First Served) et RR (Round Robin)
et des stratégies déjà implémentées sous le simulateurs Cloudsim, à savoir (Space
101
Shared et Time Shared). Comme métriques de performance, nous avons utilisé le

temps de réponse, le nombre de déplacement des données et le coût de la réplication
pour les workflows scientifiques, et le coût global engendré.
Nos stratégies d’ordonnancement proposées permettent de réduire le temps de
réponse moyen d’exécution des tâches, de diminuer le déplacement des données
pour les applications scientifiques dans le cas de la stratégie 1, d’avoir un meilleur
équilibrage de charge dans le cas de la stratégie 3, et de réduire le coût global
d’utilisation de ressources dans les stratégies 1 et 2 proposées.
En résumé, Les résultats de simulation obtenus pour nos stratégies d’ordonnan-
cement et d’allocation de ressources proposées sont satisfaisants, très encourageant,
et répondent aux objectifs tracés dans le cahier de charge.
Afin d’étendre notre travail de recherche, nous envisageons plusieurs perspec-
tives. Nous voulons augmenter les capacités de la première stratégie proposée en
permettant la réplication des ensembles de données pour l’ordonnancement des
tâches dans les environnements de Clouds multiples (fédération de Clouds). Nous
proposons également d’intégrer la première stratégie proposée dans le simulateur
Cloudsim et de prendre en considérations d’autres paramètres comme la taille des
données et le coût de la réplication comme facteurs essentiels dans la deuxième
stratégie. Nous proposons aussi d’étudier comment la stratégie de réplication peut
être utilisée lorsque le provisionnement et le processus d’ordonnancement est ef-
fectué sur des flux de données multiples dont les tâches ont différentes priorités.
Nous prévoyons également de réaliser la mise en œuvre de nos stratégies dans la
planification et l’ordonnancement des tâches sur des cas réel d’une compagnie pé-
trolière Sonatrach-Algérie contenant des données chimiques industrielles réparties
sur plusieurs clusters dans un objectif d’améliorer efficacement le système de cette
compagnie.
Bibliographie
[1] Ravin Ahuja, Asok De, and Goldie Gabrani. Sla based scheduler for cloud
for storage and computational services. In ICCSA Workshops, pages 258–262.
IEEE Computer Society, 2011. (Cité en page 34.)
[2] Oracle Corporation and/or its affiliates. Bienvenue à netbeans. https ://net-
beans.org/, (Consulté Mai 2014). (Cité en page 77.)
[3] Enda Barrett, Enda Howley, and Jim Duggan. A learning architecture for
scheduling workflow applications in the cloud. In Proceedings of the 9th IEEE
European Conference on Web Services, ECOWS’11, pages 83–90, 2011. (Cité
en page 40.)
[4] Meriem Benadda. Stratégie de placement de données dans le cloud computing.

Master en informatique, Université d’Oran, Faculté des sciences, Département
d’informatique, 2012. (Cité en page 79.)
[5] Michael Bender, Soumen Chakrabarti, and S. Muthukrishnan. Flow and stretch
metrics for scheduling continuous job streams. In Proceedings of the 9th Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 270–279, 1998. (Cité
en page 32.)
[6] Keerthana Boloor, Rada Chirkova, Timo J. Salo, and YannisViniotis. Heuristic-
based request scheduling subject to a percentile response time sla in a dis-
tributed cloud. In GLOBAL COMMUNICATIONS CONFERENCE (IEEE
GLOBECOM 2010), pages 1–6, 2010. (Cité en page 34.)
[7] Sylvain Caicoya and Jean-Georges Saury. CLOUD COMPUTING : Maı̂trisez

les enjeux et solutions de l’informatique dans les nuages. Micro Application,
2011. (Cité en pages 16, 20 et 21.)
[8] Jean-Louis Caire and Willy Munch. Objectif Cloud : Une démarche pratique
orientée services. Eni Datapro, 2014. (Cité en pages 18 et 19.)
[9] Zenon Chaczko, Venkatesh Mahadevan, Shahrzad Aslanzadeh, and Christopher

Mcdermid. ”availability and load balancing in cloud computing. In Internatio-
Bibliographie 103
nal Conference on Computer and Software Modeling, IPCSIT’11, 2011. (Cité

en page 30.)
[10] Amit Nathani Sanjay Chaudharya and Gaurav Somanib. Policy based resource
allocation in iaas cloud. Future Generation Computer Systems, 28(7) :94–103,
2012. (Cité en page 6.)
[11] Shruti Chhabra and V. S. Dixit. Cloud computing : State of the art and
security issues. SIGSOFT Softw. Eng. Notes, 40(2) :1–11, April 2015. (Cité en
page 10.)
[12] The Cloud Computing and Distributed Systems (CLOUDS Laboratory) Uni-
versity of Melbourne. Cloudsim. http ://www.cloudbus.org/cloudsim/,
(Consulté Mars 2015). (Cité en pages vii, x, 37, 75, 111, 112 et 117.)
[13] D. Daniel and S.P.Jeno Lovesum. A novel approach for scheduling service re-
quest in cloud with trust monitor. In International Conference on Signal Pro-
cessing, Communication, Computing and Networking Technologies (ICSCCN),
[14] Claude Delannoy. Programmer en Java. Eyrolles, 2007. (Cité en page 76.)
[15] Esma Insaf Djebbar and Ghalem Belalem. Optimization of tasks scheduling
by an efficacy data placement and replication in cloud computing. In Algo-
rithms and Architectures for Parallel Processing - 13th International Confe-
rence, ICA3PP 2013, LNCS 8286, Vietri sul Mare, Italy, December 18-20,
2013, Proceedings, Part II, pages 22–29, 2013. (Cité en page 46.)
[16] Esma Insaf Djebbar and Ghalem Belalem. Tasks scheduling and resource allo-
cation for high data management in scientific cloud computing environment. In
he International Conference on Mobile, Secure and Programmable Networking
(MSPN’2016), LNCS 10026, Paris, France, June 1-3, 2016. (Cité en page 67.)
[17] Esma Insaf Djebbar and Ghalem Belalem. An effective task scheduling strategy
in multiple data centers in cloud scientific workflow. In MIPRO Proceedings,
The 39th International ICT Convention on Information and Communication
Technology, Electronics and Microelectronics (MIPRO 2016), IEEE, Rijeka,
Croatia, pages 214–217, May 30-June 3, 2016. (Cité en page 63.)
Bibliographie 104
[18] Esma Insaf Djebbar, Ghalem Belalem, and Merien Benadda. Task scheduling
strategy based on data replication in scientific cloud workflows. Multiagent and
Grid Systems : An International Journal of Cloud Computing, 12(1) :55–67,
[19] Jean Michel Doudoux. Java et eclipse.

http ://www.jmdoudoux.fr/accueil.html, (Consulté Juin 2016). (Cité en
page 77.)
[20] Pierre-François Dutot, Lionel Eyraud, Grégory Mounié, and Denis Trystram.
Bi-criteria algorithm for scheduling jobs on cluster platforms. In Proceedings
of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and
Architectures, SPAA ’04, pages 125–132, New York, NY, USA, 2004. ACM.
(Cité en page 31.)
[21] Bruce Eckel. Thinking in Java (4th Edition). Prentice Hall PTR, Upper Saddle
River, NJ, USA, 2005. (Cité en page 76.)
[22] Hamid Mohammadi Fard, Radu Prodan, and Thoma Fahringers. A truthful
dynamic workflow scheduling mechanism for commercial multicloud environ-
ments. IEEE Trans. Parallel Distrib. Syst., 24(6) :1203–1212, 2013. (Cité en
pages viii, 38 et 39.)
[23] D.G. Feitelson. A survey of scheduling in multiprogrammed parallel systems.

International Business Machines Corporation, 1994. (Cité en page 31.)
[24] D.G. Feitelson and 1.W. Mu’alem. On the definition of ”on-line” in job sche-
duling problems. Tech. rep., SIGACT News, 2000. (Cité en page 31.)
[25] Ian T. Foster, Yong Zhao, Ioan Raicu, and Shiyong Lu. Cloud computing and
grid computing 360-degree compared. CoRR, abs/0901.0131, 2009. (Cité en
page 10.)
[26] Yuji Ge and Guiyi Wei. Ga-based ta,sk scheduler for the cloud computing
systems. In Proceedings of the IEEE International Conference on Web Infor-
mation Systems and Mining, pages 181–186, 2010. (Cité en page 35.)
Bibliographie 105
[27] Shamsollah Ghanbaria and Mohamed Othman. A priority based job scheduling
algorithm in cloud computing. Procedia Engineering, 50 :778–785, 2012. (Cité
en page 67.)
[28] Jens Gustedt, Emmanuel Jeannot, and Martin Quinson. Experimental vali-
dation in large-scale systems : a survey of methodologies. Parallel Processing
Letters, 19(3) :399–418, 2009. RR-6859. (Cité en page 113.)
[29] M. Hemamalini. Review on grid task scheduling in distributed heterogeneous

environment. International Journal of Computer Applications, 40(2) :24–30,
[30] Romain Hennion, Hubert Tournier, and Eric Bourgeois. Cloud computing : Dé-
cider, Concevoir, Piloter, Améliorer. Groupe Eyrolles, 2012. (Cité en pages 22,
23 et 24.)
[31] http ://www.hebergeurcloud.com. Hébérgeur cloud.

http ://www.hebergeurcloud.com/les-technologies-du-cloud-computing/,
(Consulté Mars 2015). (Cité en pages viii et 13.)
[32] Le Cloud Kesako. Cloud-serveur. http ://www.cloud-serveur.fr/fr/le-

cloud/cloud-kesako, (Consulté Mars 2016). (Cité en pages viii et 17.)
[33] Mansouri Khalil. L’ordonnancement des tâches dans le cloud computing par
une approche d’optimisation parallèle. Master en informatique, Université Mo-
hamed Khider, Biskra, 2013. (Cité en page 35.)
[34] Pardeep Kumar and Amandeep Verma. Scheduling using improved genetic
algorithm in cloud computing for independent tasks. In Proceedings of the In-
ternational Conference on Advances in Computing, Communications and In-
formatics, ICACCI ’12, pages 137–142, New York, NY, USA, 2012. ACM. (Cité
en pages 35 et 37.)
[35] Parveen Kumar and Anjandeep Kaur Rai. An overview and survey of va-
rious cloud simulation tools. Journal of Global Research in Computer Science,
5(1) :24–26, January 2014. (Cité en page 112.)
Bibliographie 106
[36] Shyamlal Kumawat and Deepak Tomar. Sla aware trust model for cloud service
deployment. International Journal of Computer Applications, 90(10) :10–15,
March 2014. (Cité en page 34.)
[37] Young Choon Lee, Chen Wang, Albert Y. Zomaya, and Bing Bing Zhou. Profit-
driven service request scheduling in clouds. In Proceedings of the 2010 10th
IEEE/ACM International Conference on Cluster, Cloud and Grid Computing,
CCGRID ’10, pages 15–24, Washington, DC, USA, 2010. (Cité en page 34.)
[38] Jiayin Li, Meikang Qiu, Zhong Ming, Gang Quan, Xiao Qin, and Zonghua Gu.
Online optimization for scheduling preemptable tasks on iaas cloud systems.
J. Parallel Distrib. Comput., 72(5) :666–677, 2012. (Cité en pages 119 et 120.)
[39] Luqun Li. An optimistic differentiated service job scheduling system for cloud
computing service users and providers. In the third International Conference
on Multimedia and Ubiquitous Engineering, MUE 2009, Qingdao, China, June
4-6, 2009, pages 295–299, 2009. (Cité en page 34.)
[40] Cui Lin and Shiyong Lu. Scheduling scientific workflows elastically for cloud
computing. In Ling Liu and Manish Parashar, editors, IEEE CLOUD, pages
746–747. IEEE, 2011. (Cité en page 41.)
[41] Ke Liu, Hai Jin, Jinjun Chen, Xiao Liu, Dong Yuan, and Yun Yang.
A compromised-time-cost scheduling algorithm in swindew-c for instance-
intensive cost-constrained workflows on a cloud computing platform. Inter-
national Journal of High Performance Computing Applications, 24(4), 2010.
(Cité en page 40.)
[42] Ming Mao and Marty Humphrey. Auto-scaling to minimize cost and meet appli-
cation deadlines in cloud workflows. In Proceedings of International Conference
for High Performance Computing, Networking, Storage and Analysis, SC ’11,
pages 1–49, New York, NY, USA, 2011. ACM. (Cité en page 43.)
[43] Wiliam T. McCormick, Paul J. Sehweitzer, and Thomas W. White. Problem

decomposition and data reorganization by a clustering technique, volume 20,
chapter 1, pages 993–1009. Operations Research, 1972. (Cité en pages 48
et 64.)
Bibliographie 107
[44] Luiz Meyer, Marta Mattoso, Doug Scheftner, Mike Wilde, Jens Voeckler, and
Ian Foster. (Cité en page 42.)
[45] Ioannis A. Moschakis and Helen D. Karatza. Performance and cost evaluation
of gang scheduling in a cloud computing system with job migrations and star-
vation handling. In Proceedings of the 16th IEEE Symposium on Computers
and Communications, ISCC 2011, Kerkyra, Corfu, Greece, June 28 - July 1,
2011, pages 418–423, 2011. (Cité en page 69.)
[46] A. Ohri. R for Cloud Computing : An Approach for Data Scientists. Springer,
New York Heidelberg Dordrecht London, 2014. (Cité en pages 10 et 11.)
[47] Simon Ostermann, Kassian Plankensteiner, Radu Prodan, and Thomas Fah-
ringer. GroudSim : An Event-based Simulation Framework for Computational
Grids and Clouds. In CoreGRID/ERCIM Workshop on Grids and Clouds, Is-
chia, Naples, Italy, Aug 2010. Springer Computer Science Editorial. (Cité en
page 114.)
[48] Dan Pelleg and Andrew W. Moore. X-means : Extending k-means with efficient
estimation of the number of clusters. In Proceedings of the Seventeenth Interna-
tional Conference on Machine Learning, ICML ’00, pages 727–734, San Fran-
cisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. (Cité en pages 45,
55, 57 et 58.)
[49] Linux Project. Linux, the linux foundationt. http ://www.Linux.com/,

(Consulté Janvier 2014). (Cité en page 12.)
[50] Xen Project. A linux foundation collaborative project : Xen.

http ://www.xenproject.org/, (Consulté Janvier 2016). (Cité en page 12.)
[51] Mustafizur Rahman, Xiaorong Li, and Henry Novianus Palit. Hybrid heuristic
for scheduling data analytics workflow applications in hybrid cloud environ-
ment. In IPDPS Workshops, pages 966–974. IEEE, 2011. (Cité en page 43.)
[52] Christopher J. Reynolds, Stephen C. Winter, Gábor Terstyánszky, Tamás Kiss,

Pamela Greenwell, Sandor Acs, and Péter Kacsuk. Scientific workflow makes-
pan reduction through cloud augmented desktop grids. In Costas Lambri-
Bibliographie 108
noudakis, Panagiotis Rizomiliotis, and Tomasz Wiktor Wlodarczyk, editors,

CloudCom, pages 18–23. IEEE Computer Society, 2011. (Cité en page 42.)
[53] Michael R.Garey and David S.Johnson . Computers and Intractability : A

Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York,
NY, USA, 1979. (Cité en page 31.)
[54] J. R. Rodrigues, L. Z. Zhou, L. M. Mendes, K. L. Lin, and J. L. Lloret. Distri-

buted media-aware flow scheduling in cloud computing environment. Computer
Communications, 35(1) :1819–1827, September 2012. (Cité en page 28.)
[55] Robert Shimonski. Windows 2000 & Windows Server 2003 Clustering and
Load Balancing. (Cité en page 30.)
[56] Guillaume Sigui. Cloud computing, quels sont les risques de sécurité majeurs
du cloud computing ? http ://www.developpez.com/, (Consulté Mars 2014).
(Cité en pages ix, 24 et 79.)
[57] The Green Cloud Simulator. Greencloud. https ://greencloud.gforge.uni.lu/,

Université du Luxemburg, (Consulté Mars 2015). (Cité en page 113.)
[58] Anne Tasso. Le livre de Java : premier langage. Collection noire. Eyrolles,
Paris, 2010. (Cité en page 76.)
[59] Fei Teng. Resource allocation and schelduling models for cloud computing. Phd
thesis, Ecole Centrale Paris, October 2011. (Cité en page 33.)
[60] Michael Tighe, Gastón Keller, Michael Bauer, and Hanan Lutfiyya. Dcsim : A
data centre simulation tool for evaluating dynamic virtualized resource mana-
gement. In 8th International Conference on Network and Service Management,
CNSM 2012, Las Vegas, NV, USA, October 22-26, 2012, pages 385–392, 2012.
(Cité en pages vii, x, 114 et 115.)
[61] DAO Van Toan. Workflows scientifiques sur plusieurs clouds. Master en in-
formatique, Institut de la francophonie pour l’informatique, Laboratoire de
l’informatique du parallélisme (LIP), 2013. (Cité en pages 31 et 38.)
[62] Lamiel Toch. Contributions aux techniques d’ordonnancement sur plates-

formes parallèles ou distribuées. PhD thesis, Ecole doctorale sciences pour
l’ingénieur et microtechniques, Université de Franche comté. (Cité en page 31.)
Bibliographie 109
[63] C. T. Tsai and J. R. Rodrigues. Metaheuristic scheduling for cloud : A survey.

IEEE Systems, 8(1) :279–291, March 2014. (Cité en page 28.)
[64] Luis M. Vaquero, Luis Rodero-Merino, Juan Caceres, and Maik Lindner. A
break in the clouds : Towards a cloud definition. SIGCOMM Comput. Commun.
Rev., 39(1) :50–55, December 2008. (Cité en page 10.)
[65] Amandeep Verma and Sakshi Kaushal. Deadline and budget distribution based
cost-time optimization workflow scheduling algorithm for cloud. IJCA Procee-
dings on International Conference on Recent Advances and Future Trends in
Information Technology (iRAFIT 2012), iRAFIT(7) :1–4, April 2012. (Cité en
page 41.)
[66] Global Digital Vision. Cloud computing. http ://www.gdv.com.au/cloud-

computing.html, (Consulté Mars 2014). (Cité en pages viii et 11.)
[67] Marek Wieczorek, Stefan Podlipnig, Radu Prodan, and Thomas Fahringer. Bi-
criteria scheduling of scientific workflows for the grid. In CCGRID’08 : Pro-
ceedings of the 2008 Eighth IEEE International Symposium on Cluster Com-
puting and the Grid, pages 9-16, IEEE Computer Society, Washington, DC,
USA, 2008. (Cité en page 42.)
[68] Meng Xu, Li zhen Cui, Haiyang Wang, and Yanbing Bi. A multiple qos constrai-
ned scheduling strategy of multiple workflows for cloud computing. In ISPA,
pages 629–634. IEEE Computer Society, 2009. (Cité en pages 41 et 42.)
[69] Deshi Ye and Guochuan Zhang. On-line scheduling of parallel jobs in a list.
Journal of Scheduling, 10(6) :407–413, 2007. (Cité en page 31.)
[70] Jia Yu, Rajkumar Buyya, and Chen Khong Tham. Cost-based scheduling
of scientific workflow application on utility grids. In Proceedings of the First
International Conference on e-Science and Grid Computing, E-SCIENCE’05,
pages 140–147, Washington, DC, USA, 2005. IEEE Computer Society. (Cité
en page 42.)
[71] Dong Yuan, Yun Yang, Xiao Liu, and Jinjun Chen. A data placement stra-
tegy in scientific cloud workflows. Future Generation Computer Systems,
26(8) :1200–1214, 2010. (Cité en pages 46, 51 et 58.)
Bibliographie 110
[72] Sharrukh Zaman and Daniel Grosu. Combinatorial auction-based dynamic

VM provisioning and allocation in clouds. In the 3rd International Conference
on Cloud Computing Technology and Science, CloudCom 2011, Athens, Greece,
IEEE, November 29-December 1, 2011, pages 107–114, 2011. (Cité en page 35.)
[73] Qi Zhang, Quanyan Zhu, and Raouf Boutaba. Dynamic resource allocation for
spot markets in cloud computing environments. In the Fourth International
Conference on Utility and Cloud Computing (UCC’11), IEEE, 2011. (Cité en
page 35.)
[74] Han Zhao and Xiaolin Li. Auctionnet : Market oriented task scheduling in he-
terogeneous distributed environments. In the International Parallel and Dis-
tributed Processing Symposium (IPDPS), pages 1–4. IEEE, 2010. (Cité en
page 34.)
[75] Liang Zhao, Sherif Sakr, Anna Liu, and Athman Bouguettaya. Cloud Data
Management. Springer Editor, 2014. (Cité en pages viii, 14 et 15.)
Annexe A
Simulateurs de Cloud
computing
ans un système distribué, il existe des enjeux à résoudre tels que la gestion
D des ressources et l’ordonnancement des applications car, ces tâches sont com-
pliquées et il n’existe pas une solution optimale pour répondre à ces issues. D’autre
part, dans l’environnement d’un système distribué comme Cloud, il est difficile d’ef-
fectuer les différents scénarios avec différents nombres de ressources et d’utilisateurs
afin d’évaluer la performance des algorithmes de partage de charge, Broker, gestion
des ressources, etc. Lorsque on veut évaluer les scénarios de manière répétable et
contrôlable, cela est parfois impossible à cause de l’issue du coût et de la gestion.
Afin de résoudre cette issue, les chercheurs utilisent des simulateurs pour effectuer
leur scénarios avant de les effectuer au sein d’un système distribué réel. Plusieurs
simulateurs de Cloud Computing sont actuellement en développement. En voici une
liste non exhaustive, décrivant les caractéristiques de chacun d’entre eux.
A.1 Simulateur CloudSim [12]
CloudSim est un framework qui modélise et qui simule l’environnement du Cloud

computing et ses services, il a été réalisé en Java. Ce framework supporte la mo-
délisation et la simulation de l’environnement de Datacenter basé sur le Cloud, tel
que les interfaces de gestion dédiées aux VMs, la mémoire, le stockage et la bande
passante. La couche CloudSim gère l’instanciation et l’exécution des entités de base
(VM, hôtes, Datacenters, applications) au cours de la période de simulation. Dans
la couche la plus haute de la pile de simulation, on trouve le code de l’utilisateur qui
A.1. Simulateur CloudSim [12] 112
expose la configuration des fonctionnalités liées aux hôtes (ex : nombre de machines,
leurs spécifications), les politiques d’ordonnancement de Broker, les applications (
ex : nombre de tâches et leurs besoins), les VMs , et le nombre d’utilisateurs.
Il a été développé dans le laboratoire CLOUDS de science et de génie dans le
département Informatique de l’Université de Melbourne, en Australie. Il fournit des
classes de base pour décrire les centres de données, les machines virtuelles, les ap-
plications, les utilisateurs, les ressources informatiques et les politiques de gestion
des diverses parties du système (par exemple, l’ordonnancement et l’approvisionne-
ment). Ces composants peuvent être mis en place pour les utilisateurs pour évaluer
de nouvelles politiques, les algorithmes d’ordonnancement, la cartographie, etc. Le
Cloud est une boı̂te à outils de simulation complexe à l’aide duquel la plupart des
scénarios de Cloud peuvent être construites par une simple extension ou de rempla-
cement des classes et de codage du scénario souhaité.
CloudSim est une solution prête à l’emploi pour définir les paramètres et simu-
ler afin d’obtenir des résultats. Étant une bibliothèque, CloudSim exige d’écrire le
programme en Java à l’aide de ses composants pour composer le scénario souhaité
et de recueillir les résultats de l’analyse de la performance et de la sécurité des
applications de Cloud.
Tous les composants de CloudSim communiquent entre eux par envoi de mes-
sages. Dans l’architecture en couches au-dessus de CloudSim, la couche la plus
basse est principalement responsable de la communication entre les composants et
la seconde couche possède toutes les sous-couches en ce qui concerne les principaux
composants tels que les capteurs de nuages, les centres de données, etc. [35]. L’uti-
lisation de CloudSim permet de modéliser les centres de données, la répartition de
la machine virtuelle en utilisant un VMScheduler, la consommation d’énergie et le
comportement du réseau. D’autres outils de simulation qui étendent la puissance
de CloudSim sont : CloudSimEx, WorkflowSim, SimpleWorkflow, RealCloudSim,
CloudReports, CloudAuction, CloudMIG Xpress, CloudAnalyst [12].
A.2. EMUSIM 113
A.2 EMUSIM
EMUSIM (Integrated Emulation and Simulation) combine l’émulation et la si-

mulation [28] pour permettre à des modèles plus précis des artefacts de logiciels
(obtenus par profilage lors de l’émulation) à les utiliser lors des simulations. Ceci
est particulièrement utile lorsque le testeur n’a aucune idée sur la performance du
logiciel sous différents niveaux de concurrence et parallélisme, ce qui empêche l’uti-
lisation de la simulation.
Figure A.1 – Organisation interne EMUSIM
A.3 Simulateur GreenCloud
GreenCloud est un simulateur pour les centres de données de Cloud computing

développé pour la réduction de l’énergie en mettant l’accent sur les communications
en Cloud. Il propose une modélisation fine et détaillée de l’énergie consommée par
l’équipement informatique des centre de données, tels que les serveurs informatiques,
les commutateurs de réseau, et les liens de communication.
GreenCloud peut être utilisé pour développer de nouvelles solutions en matière
de suivi, d’allocation des ressources, d’ordonnacement, ainsi que d’optimisation des
protocoles de communication et des infrastructures de réseau (Figure A.2). Il est
libéré en vertu du Contrat de Licence Publique Générale et est une extension du
simulateur de réseau NS2 bien connu. GreenCloud a été élaboré dans le cadre des
projets Greenit et ECO-CLOUD [57].
A.4. Simulateur GroudSim 114
Figure A.2 – Architecture GreenCloud
A.4 Simulateur GroudSim
GroudSim est un simulateur basé sur des événements, il a été proposé par Oster-
mann et al. [47] pour des applications scientifiques sur les environnements de grille
et de Cloud basé sur un noyau discret d’évènement indépendant pour la simulation
évolutive. Il fournit un ensemble complet de fonctionnalités pour les scénarios de
simulation complexes à partir des exécutions d’emploi simples sur les ressources
informatiques louées à des coûts de calcul, et la charge des ressources. Les simu-
lations peuvent être paramétrées et sont facilement extensibles par des paquets de
distribution de probabilité pour les défaillances qui se produisent normalement dans
des environnements complexes. Il est principalement concentré sur le IaaS, mais il
est facilement extensible pour soutenir des modèles supplémentaires tels que PaaS,
DaaS (Data as a Service) et TaaS (Text as a Service).
A.5 iCanCloud [60]
iCanCloud est un autre outil de simulation des applications de hautes perfor-

mances sur des grands réseaux de stockage (Figure A.3). Ce simulateur est développé
sur Simcan (un outil de simulation pour analyser les architectures d’E/S à haute
performance). Dans ce simulateur, il n’y a pas besoin de modifier le code de simula-
tion pour tester différentes architectures. Il peut être effectué simplement en créant
A.5. iCanCloud [60] 115
un nouveau fichier de configuration.
Figure A.3 – Architecture iCanCloud [60]

Annexe B
Simulateur CloudSim :
Développement et
expérimentation
e framework Cloudsim modélise et simule l’environnement du Cloud computing

L et ses services, il a été réalisé en Java.
B.1 Architecture détailléé de CloudSim
La Figure B.1 illustre les différentes couches de la structure du CloudSim et

ses éléments architecturaux. Au niveau le plus bas est le moteur de simulation aux
évènements discrets SimJava, qui implémente les fonctionnalités de base requises
pour les cadres de simulation au niveau supérieur, telles que les files d’attente, le
traitement des événements, la création de composants du système (services, hôte,
Datacenter, Broker, les machines virtuelles), la communication entre les composants
et la gestion de l’horloge de simulation.
CloudSim supporte la modélisation et la simulation de l’environnement de Da-
tacenter basé sur Cloud, tel que les interfaces de gestion dédiées aux VMs, la mé-
moire, le stockage et la bande passante. La couche CloudSim gère l’instanciation
et l’exécution des entités de base (VM, hôtes, Datacenters, applications) au cours
de la période de simulation. Dans la couche plus haute de la pile de simulation, on
trouve le code de l’utilisateur qui expose la configuration des fonctionnalités liées
aux hôtes (ex : nombre de machines...), les politiques d’ordonnancement de Broker,
les applications ( ex : nombre de tâches...), les VMs, et le nombre d’utilisateurs.
B.2. Modélisation du Cloud 117
Figure B.1 – Architecture de Cloudsim [12]
B.2 Modélisation du Cloud
Dans cette partie, nous allons voir comment simuler une application distribuée
au sein d’un Cloud. Chaque Cloud est constitué des Datacenters. On trouve dans
chaque Datacenter, des hôtes et chaque hôte héberge les VMs. Pour faire la simu-
lation, il faut définir une classe qui contient la fonction Main(), dans laquelle, on
définit les paramètres de notre Cloud comme le nombre de Datacenter, des hôtes, et
les caractéristiques de chaque hôte et machine virtuelle comme la bande passante.
Dans cet exemple, la configuration de la VM est :
//—————–VM description—————–
int vmid = 0 ;//vm id
int mips = 250 ;//number of operations
long size = 10000 ; //image size (MB)
int ram = 512 ; //vm memory (MB)
long bw = 1000 ;//vm bandwidth
B.2. Modélisation du Cloud 118
int pesNumber = 1 ; //number of cpus

String vmm = ”Xen”; //VMM name
//create VMs
Vm vm1 = new Vm(vmid, brokerId, mips, pesNumber, ram, bw, size, vmm, new
CloudletSchedulerTimeShared()) ;
Et la configuration de l’hôte est :
//—————–create host—————–
List<Host> hostList = new ArrayList<Host>() ; List<Pe> peList = new Array-
List<Pe>() ; int mips = 1000 ;
peList.add(new Pe(0, new PeProvisionerSimple(mips))) ; // need to store Pe id and
MIPS Rating
int hostId=0 ;
int ram = 2048 ; //host memory (MB)
long storage = 1000000 ; //host storage
int bw = 10000 ;
hostList.add(new Host(hostId,new RamProvisionerSimple(ram),new BwProvisioner-
Simple(bw), storage, peList, new VmSchedulerSpaceShared(peList))) ;
Et finalement le Datacenter :
//—————–create Datacenter—————–
String arch = ”x86”;//system architecture
String os = ”Linux”;//operating system
String vmm = ”Xen”;
double time zone = 10.0 ;//time zone this resource located
double cost = 3.0 ;// the cost of using processing in this resource
double costPerMem = 0.05 ;//the cost of using memory in this resource
double costPerStorage = 0.001 ;//the cost of using storage in this resource
double costPerBw = 0.0 ;//the cost of using bw in this resource
LinkedList<Storage> storageList = new LinkedList<Storage>() ;//we are not ad-
ding SAN devices by now
DatacenterCharacteristics characteristics = new DatacenterCharacteristics
(arch, os, vmm, hostList, time zone, cost, costPerMem, costPerStorage, costPerBw) ;
B.3. Politiques d’ordonnancement 119
Datacenter datacenter = null ;

try {
datacenter = new Datacenter(name, characteristics, new VmAllocationPolicySimple(hostList),
storageList, 0) ;
} catch (Exception e) {
e.printStackTrace() ;
}
Dans CloudSim, il y a deux entités importantes : Broker et Cloudlet. Le Broker
gère la création de VMs, la soumission aux VMs et la destruction de VMs. Les
Cloudlets sont les tâches à exécuter sur les machines virtuelles. La dernière version
de CloudSim 3, nous permet de configurer et de changer les paramètres de réseau
entre les hôtes dans un datacenter, aussi entre les datacenters en utilisant des switchs
et des routeurs.
B.3 Politiques d’ordonnancement
Il existe deux politiques qui sont définies dans le simulateur CloudSim :

– La politique d’ordonnancement Space Shared (Espace partagé)
– La politique d’ordonnancement Time Shared (Temps partagé)
B.3.1 Étape pour définir la politique SPACE SHARED
Dans la politique d’ordonnancement Space Shared, l’ordonnanceur (Broker) pla-

nifie une tâche sur la machine virtuelle concernée à un instant donné et après son
achèvement, il lance une autre tâche sur la machine virtuelle. Cette même politique
est utilisée pour programmer les machines virtuelles sur l’hôte. Cette politique suit
la même procédure que l’algorithme du premier arrivé, premier servi (PAPS) [38].
Étape 1 : Les tâches acceptées sont disposées dans une file d’attente.
Étape 2 : La première tâche dans la file d’attente est lancée sur la machine vir-
tuelle donnée.
Étape 3 : Après la terminaison de la première tâche, la prochaine tâche dans la

file d’attente sera considérée.
Étape 4 : Si la file d’attente est vide, le Broker vérifie pour une éventuelle tâche.
Étape 5 : Répéter ensuite à partir de l’étape 1.
Étape 6 : Fin.
B.3.2 Étape pour définir la politique TIME SHARED
Dans la politique d’ordonnancement en temps partagé, l’ordonnanceur planifie

toutes les tâches sur la machine virtuelle en même temps. Il partage le temps entre
toutes les tâches et les planifie simultanément sur la machine virtuelle. Cette po-
litique est également utilisée pour ordonnancer la machine virtuelle sur l’hôte. Le
concept de l’algorithme d’ordonnancement Round-Robin (RR) [38] est utilisé dans
cette politique.
Étape 1 : Les tâches acceptées sont disposées dans une file d’attente.
Étape 2 : Planifier les tâches simultannément sur la machine virtuelle.
Étape 3 : Si la file d’attente est vide, vérifier pour une éventuelle tâche.
Étape 4 : Si une nouvelle tâche arrive, répéter à partir de l’étape 2.
Étape 5 : Fin.
CloudSim met en œuvre les politiques d’ordonnancement Space Shared et Time

Shared. La différence entre ces deux politiques et leurs effets sur les performances de
l’application est montrée dans la Figure B.2. Dans lequel, un hôte avec deux cœurs
de processeurs reçoit une demande pour l’hébergement de deux machines virtuelles,
et chacune nécessitant deux noyaux et exécute quatre unités de tâches : t1, t2, t3
et t4 à exécuter en VM1, tandis que t5, t6, t7 et t8 à exécuter dans VM2.
Figure B.2 – Effets des politiques d’ordonnancements sur l’exécution des tâches :
(a) Space-shared for VMs and Tasks, (b) Space-share for VMs and Time-shared for
tasks, (c) Time-shared for VMs, Space-shared for tasks, and (d) Time-shared for
both VMs and Tasks
Résumé
Le Cloud computing est une technologie de calcul et de stockage naissante qui se consolide rapidement
comme une grande étape dans le développement et le déploiement d'un nombre croissant des
applications réparties. L'ordonnancement de tâches et d'allocation de ressources dans les systèmes de
type Cloud computing suscite une attention croissante avec l'augmentation de la popularité de Cloud.
Dans les travaux de cette thèse, nous proposons trois stratégies d'ordonnancement et d'allocation de
ressources, la première stratégie d'ordonnancement est basée sur la réplication des données pour les
workflows scientifiques, la seconde stratégie d'ordonnancement se focalise sur le groupement de
tâches et la dernière stratégie d'ordonnancement de tâches et d'allocation de ressources est destinée
aux Big data. Nos propositions permettent de réduire le temps de réponse moyen des tâches, de
diminuer le déplacement des données pour les applications scientifiques, et de réduire le coût global
d'utilisation de ressources.
Mots clés: Cloud computing, ordonnancement des tâches, allocation des ressources,
workflows, groupement de tâches, Big data.
Abstract
Cloud computing is an emerging computing and storage technology that is rapidly consolidating as a
great step in the development and deployment of an increasing number of distributed applications.
The task scheduling and resource allocation in the systems based Cloud computing are receiving
increasing attention with the rise in popularity of Cloud. In the works of this thesis, we propose three
scheduling and resource allocation strategies, the first scheduling strategy is based on the replication
of data for scientific workflows, the second scheduling strategy focuses on the grouping of tasks and
the last strategy of task scheduling and resource allocation is intended for the big data. Our proposals
will reduce the average response time of tasks, decrease data movement for scientific applications, and
minimize the overall cost of resource use.
Keywords: Cloud computing, tasks scheduling, resource allocation, workflows, tasks

grouping, Big data.
‫ملخص‬
‫الحوسبة السحابية هي تكنولوجيا الحوسبة والتخزين الناشئة التي تعمل على التوطيد بسرعة كبيرة في تطوير ونشر عدد‬
‫ جدولة المهام وتخصيص الموارد في الحوسبة السحابية أنظمة تحظى باهتمام متزايد مع‬.‫متزايد من التطبيقات الموزعة‬
،‫ نقترح ثالث استراتيجيات للجدولة وتخصيص الموارد‬،‫ في عمل هذه األطروحة‬.‫ارتفاع الشعبية في الحوسبة السحابية‬
‫ استراتيجية الجدولة الثانية تركز على‬،‫استراتيجية الجدولة األولى تعمل على أساس تكرار البيانات لسير التطبيقات العلمية‬
‫ مقترحاتنا تعمل على‬.‫تجميع المهام و االستراتيجية األخيرة من جدولة المهام وتخصيص الموارد تختص بالبيانات الكبيرة‬
.‫ و تقليل التكلفة اإلجمالية الستخدام الموارد‬،‫ الحد من حركة البيانات للتطبيقات العلمية‬،‫تقليل متوسط زمن إ ستجابة المهام‬
‫ البيانات‬،‫ تجميع المهام‬،‫ التطبيقات العلمية‬،‫ تخصيص الموارد‬،‫ جدولة المهام‬،‫ الحوسبة السحابية‬:‫كلمات البحث‬
.‫الكبيرة‬

Thèse de Doctorat

Transféré par

Droits d'auteur :

Formats disponibles

Thèse de Doctorat

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Thèse de Doctorat

Transféré par

Droits d'auteur :

Formats disponibles

DEPARTEMENT D'INFORMATIQUE

LE DIPLOME DE DOCTORAT EN SCIENCES

Spécialité: Systèmes Informatiques Répartis

OPTIMISATION D’ORDONNANCEMENT ET D’ALLOCATION

Devant les membres du jury :

Président : HAFFAF Hafid Professeur, Université d’Oran 1, Ahmed Ben Bella

À ma famille et mes parents

e remercie Allah de m’avoir donner le courage et la volonté ainsi que la conscience

Je tiens à exprimer mes vifs remerciements à mon encadreur Mr Pr. Belalem

Ces remerciements seraient incomplets, si je n’en adressais pas à l’ensemble des

Le Cloud computing est une technologie de calcul et de stockage naissante qui se

Cloud computing is an emerging computing and storage technology that is ra-

3 Problème d’ordonnancement et d’allocation de ressources 27

4 Stratégies d’ordonnancement et d’allocation de ressources pour les

5.3.1 Résultats expérimentaux 1 : Stratégie d’ordonnancement ba-

A Simulateurs de Cloud computing 111

B Simulateur CloudSim : Développement et expérimentation 116

2.1 L’environnement de Cloud computing [66] . . . . . . . . . . . . . . . 11

3.1 Le résultat d’exécution des tâches selon Min-min . . . . . . . . . . . 36

4.1 Vue globale de la stratégie utilisée . . . . . . . . . . . . . . . . . . . 46

4.12 Affectation et ordonnancement des tâches . . . . . . . . . . . . . . . 66

5.1 Les principales classes de CloudSim [56] . . . . . . . . . . . . . . . . 79

A.1 Organisation interne EMUSIM . . . . . . . . . . . . . . . . . . . . . 113

A.2 Architecture GreenCloud . . . . . . . . . . . . . . . . . . . . . . . . 114

B.1 Architecture de Cloudsim [12] . . . . . . . . . . . . . . . . . . . . . . 117

3.1 Le temps d’exécution des tâches (Algorithme Min-min) . . . . . . . 36

4.1 Valeurs de λini par rapport aux types d’applications . . . . . . . . . 52

5.1 Les paramètres de simulation pour le temps de réponse . . . . . . . . 83

QoS : Quality of Service

Esma Insaf Djebbar and Ghalem Belalem. Optimization of Tasks Schedu-

Esma Insaf Djebbar and Ghalem Belalem. An effective Task Scheduling

Mokhtari Houari, Mederrek Ali et Aissa Berroudja Youssouf. Un algorithme

e Cloud computing ou informatique en nuage est une infrastructure dans la-

sure de se concentrer davantage sur la fonctionnalité de l’application de base. Cloud

1.2 Problématique et motivation

par conséquence ne passent pas à l’échelle.

stratégies d’ordonnancement sont polarisées aux utilisateurs, tandis que d’autres

1.4 Organisation de la thèse

’informatique dans le nuage est plus connue sous sa forme anglo-saxonne :

tels que : « informatique dans les nuages », « infonuagique » (Québec) ou encore

2.2 Les concepts du Cloud computing

tique à la demande du réseau à un ensemble partagé de ressources informatiques

Figure 2.1 – L’environnement de Cloud computing [66]

1. La demande libre des services

2. Un accès en diffusion via le réseau

3. La mise en commun des ressources

1. Des réseaux rapides,

2. Des ordinateurs bon marché,

3. La virtualisation pour du matériel de base.

Les principaux obstacles à la plus large adoption du Cloud sont :

Figure 2.2 – La virtualisation dans les environnements de Cloud [31]

tion humaine. Le but de l’informatique autonome est de surmonter la complexité

2.2.2 La grille informatique

Grid computing est un paradigme de calcul distribué qui coordonne en réseau

2.2.3 L’informatique utilitaire (Utility computing)

L’informatique utilitaire représente le modèle d’affaires des ressources d’em-

2.3 Les technologies connexes liées au Cloud computing

Le Cloud computing a évolué sur des décennies de recherche dans différentes

2.4 Les principales caractéristiques des Clouds

Le modèle Cloud Computing se différencie par les cinq caractéristiques essen-