Cours Prog Parra Seance 5-23-24

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 262

PROGRAMMATION PARALLÈLE ET

INTERFACE HOMME-MACHINE

Cycle Ingénieur SICOM, S8, FST, Fès

Pr. Mohammed Talibi Alaoui


AU:2021/2022
PROGRAMMATION PARALLÈLE

Pr. M. Alaoui Talibi 2


SOMMAIRE :
 Introduction au parallélisme
 Classification des architectures parallèles.
 Programmation parallèle impérative :
✓ Notionsde base
✓ Programmation par variables partagées
 Stratégiesde conception d'algorithmes parallèles.
 Exemples de langages.
 Mesures de performance.
 Programmation parallèle avec mémoire distribuée
et MPI.

Pr. M. Alaoui Talibi 3


INTRODUCTION AU PARALLÉLISME

Pr. M. Alaoui Talibi 4


PRÉSENTATION GÉNÉRALE :

 MOTIVATIONS

Pr. M. Alaoui Talibi 5


MOTIVATIONS MATÉRIELLES
 Loi de Moore :

Pr. M. Alaoui Talibi 6


LOI DE MOORE :
 La loi de Moore concerne l’évolution de la
puissance des ordinateurs.

 Selon cette loi :


Le nombre de transistors, c’est-à-dire l’élément
principal qui compose les processeurs des
ordinateurs, double tous les deux ans.

Et parallèlement double également la puissance


des appareils.

Pr. M. Alaoui Talibi 7


LOI DE MOORE :
 Moore fixa ensuite le cycle non plus sur 2 ans mais dix-
huit mois.

 Donc selon Moore :

Tous les 18 mois, il y a doublement du nombre de


transistors, rendant les ordinateurs rapidement
obsolètes.

Vous l’avez compris, cette loi porte le nom de celui


qui l’a énoncée en 1965, le cofondateur de la société
Intel, Gordon Moore.

Pr. M. Alaoui Talibi 8


LOI DE MOORE :

 Et Moore avait raison.

 Pourpreuve en 2014, les premières puces gravées


en 14 nanomètres (nm) – environ 5.000 fois plus fin
qu’un cheveu – sont arrivées avec un an de retard.

 Et
celles de 10 nanomètres n’étaient pas prêtes
avant 2017.

Pr. M. Alaoui Talibi 9


LOI DE MOORE :
 Les 7 nanomètres pas avant 2020.

 Orcomme l’avait dit Moore, à cette taille, certains


éléments du transistor ne sont désormais
constitués que de quelques atomes.

Nous touchons aux limites de la physique.

Pr. M. Alaoui Talibi 10


MOTIVATIONS :
 Lerecours au parallélisme pour accélérer des calculs
n’est pas une idée récente.

 Cependant, les contraintes matérielles imposèrent


l’utilisation d’un unique processeur.

 L’évolutiontechnologique des années 80 a permis de


réduire les couts de production des divers composants
d’un calculateur,

 Enmême temps qu’elle en augmentait les performances


à la fois en temps de calcul, en volume et en fiabilité.
Pr. M. Alaoui Talibi 11
MOTIVATIONS :

 Leralentissement du gain en vitesse des circuits


électroniques ( entre 1976 et 1986 ) a conduit à la
recherche de nouvelles techniques pour gagner de la
puissance soit :

- au niveau algorithmique

- soit au niveau architectural

Pr. M. Alaoui Talibi 12


MOTIVATIONS :
 Leconcept de parallélisme rompt avec l’approche
classique qui consiste à diminuer le temps de calcul
en effectuant plus vite chaque opération.

 Encalcul parallèle, le gain de temps provient de la


réalisation simultanée de plusieurs opérations.

 L’algorithmique
parallèle consiste à réduire la
complexité de certains problèmes parallèles.

Pr. M. Alaoui Talibi 13


MOTIVATIONS :
 De plus, le niveau technologique atteint est tel
qu’il est maintenant possible de construire des
architectures multiprocesseurs et de les utiliser
efficacement :

Avec quelques processeurs pour des systèmes


généraux ( plusieurs dizaines )
OU
Beaucoup plus pour des systèmes spécialisées (
quelques milliers )

Pr. M. Alaoui Talibi 14


MOTIVATIONS :

 Afin
d’atteindre cette objectif, les diverses
architectures parallèles ont poussé les algorithmiciens
à imposer de nouvelles contraintes à leurs modèles
pour les rendre plus proche de la réalité.

 Face aux demandes toujours croissantes en


puissance de calcul, le domaine du parallélisme
s’est considérablement développé depuis 1985.

Pr. M. Alaoui Talibi 15


MOTIVATIONS :
 La parallélisation d’une méthode requiert plusieurs
phases :

Tout d’abord, il est commode :

✓ de partir de diverses écritures de la méthode sous


forme algorithmique.
✓ puis d’en faire une étude théorique de complexité
pour bien saisir le parallélisme intrinséque.
✓ Après avoir choisi la (les) bonne version, on peut
examiner son implémentation, càd
Pr. M. Alaoui Talibi 16
MOTIVATIONS :
 Lafaçon d’exécuter les instructions sur une machine
cible.

Cela pose en particulier les problèmes :

- de placement d’instructions,
- de circulation des données,
- d’utilisation efficace des communications, ..

Pr. M. Alaoui Talibi 17


MOTIVATIONS :
 Pourparalléliser un algorithme, on commence par
partitionner le problème en sous-taches.

 Restealors à affecter les taches aux processeurs,


en respectant les contraintes de précédence ainsi
que les contraintes matérielles liées à l’architecture
de la machine.

 Ces dernières permettent de sélectionner, parmi


toutes les versions parallèles obtenues, celle qui
est la plus efficace pour l’ordinateur utilisé.
Pr. M. Alaoui Talibi 18
MOTIVATIONS :

 En général, ces contraintes sont de deux types :

✓ Accès limité aux données

✓ Et problèmes de synchronisation des processeurs.

Pr. M. Alaoui Talibi 19


DU SÉQUENTIEL AU PARALLÈLE :

 Aujourd’hui, on divise l’évolution de l’informatique


en cinq générations déterminées par :

✓ un niveau technologique,
✓ par un mode d’exploitation et de traitements,
✓ par les langages utilisées
✓ et par les objets traités.

Pr. M. Alaoui Talibi 20


Du séquentiel au parallèle :

Pr. M. Alaoui Talibi 21


PREMIÈRE GÉNÉRATION (1938 - 1953):

1938 : premier ordinateur électronique analogique


1964 : premier ordinateur électronique digital
ENIAC.
1950 :
 premier ordinateur avec programme enregistré
 Technologie mécanique ou électromécanique
 UAL séquentielle
 Langage binaire

Pr. M. Alaoui Talibi 22


DEUXIÈME GÉNÉRATION (1954 - 1963):

 1954 : premier ordinateur à transistors TRADIC ( 800


transistors)

 Mémoire magnétique
 UAL évoluée
 Langage assembleur, puis fortran et Algol.
 Exécution par batch d’un seul programme

Pr. M. Alaoui Talibi 23


TROISIÈME GÉNÉRATION (1964 - 1973):

 Utilisationdes circuits intégrés


 Compilateurs intelligents de langages de haut niveau.
 Multiprogrammation
 Processeurs vectoriels
 Temps partagé et multiprogrammation
 Machines virtuelles
 Du traitement des données au traitement l’information.

Pr. M. Alaoui Talibi 24


QUATRIÈME GÉNÉRATION (1974 -
PRÉSENT):

 Circuit à haute intégration (LSI)


 Mémoire de grande taille
 Langages permettant le traitement vectoriel
 UAL parallèle et pipeline
 Plusieurs processeurs
 Du traitement de l’information au traitement des
connaissances (systèmes experts).

Pr. M. Alaoui Talibi 25


PRÉSENT ET FUTUR PROCHE

 Circuits spécialisés à très haute intégration (VLSI)

 Multiprocesseurs parallèles

 Parallélisme massif

 Du traitement des connaissances au traitement de


l’intelligence.

Pr. M. Alaoui Talibi 26


TRAITEMENT PARALLÈLE
 Au plus haut niveau, le traitement parallèle permet
l’exécution simultanée de plusieurs programmes
indépendants.

 Il utilise la multiprogrammation, le temps partagée


et le multitraitement: Mode de fonctionnement d'un ordinateur selon
lequel plusieurs processeurs ayant accès à des mémoires communes
peuvent opérer en parallèle sur des programmes différents.(Anglais:
multiprocessing).

 Il s’emploie dans des systèmes de grande taille


(mainframe) et se traite au niveau du système
d’exploitation.

Pr. M. Alaoui Talibi 27


TRAITEMENT PARALLÈLE

 L’introduction
du parallélisme à l’intérieur d’un
programme peut se faire au niveau des procédures.

 Ilnécessite la décomposition du programme en


taches, la recherche des relations de dépendance
entre ces taches et la programmation en parallèle
des taches indépendantes.

Pr. M. Alaoui Talibi 28


TRAITEMENT PARALLÈLE

 Il peut se traiter au niveau du système d’exploitation :

✓ parallélisation automatique de programmes,


✓ compilateurs intelligents

 ou au niveau algorithmique.

Pr. M. Alaoui Talibi 29


TRAITEMENT PARALLÈLE

 Le traitement parallèle d’instructions indépendantes


utilise la technique de vectorisation.

 Ilse traite au niveau du système (vectoriseur), du


langage de programmation (Fortran vectoriel) ou au
niveau algorithmique.

Pr. M. Alaoui Talibi 30


TRAITEMENT PARALLÈLE
 Latechnique du pipeline permet l’introduction du
parallélisme au niveau d’une instruction. Il s’agit de
décomposer une instruction en plusieurs étapes
successives et de faire exécuter, en même temps,
des étapes différentes de plusieurs instructions.

 Ce
type de parallélisme est traité au niveau du
matériel.

 Lesgrands ordinateurs font appel maintenant tous


à ces techniques.
Pr. M. Alaoui Talibi 31
Le parallélisme dans les
monoprocesseurs

Pr. M. Alaoui Talibi 32


LE PARALLÉLISME DANS LES
MONOPROCESSEURS
 Les architectures monoprocesseurs ont en général
une structure de base commune :

✓ Une mémoire principale


✓ Un processeur centralisé
✓ Un ensemble de communications

Les relations entre ces 3 unités peuvent être réalisées


de manières diverses, par exemple par l’intermédiaire
d’un bus commun (VAX -11/780) par exemple.
Pr. M. Alaoui Talibi 33
LE PARALLÉLISME DANS LES
MONOPROCESSEURS

 L’introduction du parallélisme peut se faire de


plusieurs façons :

✓ UAL parallèle : Plusieurs unités fonctionnelles


✓ par exemple Fonctionnement simultané des trois
unités
✓ Multiprogrammation et temps partagé

Pr. M. Alaoui Talibi 34


LE PARALLÉLISME DANS LES
MONOPROCESSEURS
Exemple :
Les diverses fonctions d’une UAL sont distribuées à des
unités indépendantes opérant en parallèle.

Les CDC 6600 possède 10 unités fonctionnelles (addition,


soustraction, décalage,..) dans son UAL.

L’IBM 360/91 a deux unités arithmétiques parallèles :


l’une pour les opérations en virgule fixe,
l’autre pour les opérations en virgule flottante,
divisée en deux unités fonctionnelles (additions et
multiplications).
Pr. M. Alaoui Talibi 35
LE PARALLÉLISME DANS LES
MONOPROCESSEURS

 LesUAL possèdent maintenant des additionneurs


parallèles à anticipation de retenue et de multiplieurs
intégrés.

 Leur traitement est pipeline

Pr. M. Alaoui Talibi 36


LE PARALLÉLISME DANS LES
MULTIPROCESSEURS

 L’utilisation
des multiprocesseurs conduit à une
programmation effective de divers processeurs.

 Un ordinateur est donc parallèle dés qu’il dispose


de plus d’un processeur pour effectuer le
traitement d’un seul programme.

 Le Cray 2 possède 4 processeurs très puissants.

Pr. M. Alaoui Talibi 37


LES PROBLÈMES POSÉS PAR LA
MULTIPLICATION DES PROCESSEURS

 Problème d’optimisation :

Une très grande partie des programmes actuels


n’utilise pas la puissance des multi-cœurs.

Limite théorique : loi d’Amdahl

Pr. M. Alaoui Talibi 38


LOI D’AMDAHL :

Soit f la fraction intrinsèquement séquentielle (non


parallèlisable) de l’algorithme à paralléliser.

Alors l’accèleration maximale sur p processeurs de


l’algorithme parallèle correspondant est :

S(n,p)≤1/(f+(1-f)/p)

Pr. M. Alaoui Talibi 39


LOI D’AMDAHL :

 Exemple :

20% d’un algorithme n’est pas parallélisable.


L’accéleration est donc limité à 5.

50% d’un algorithme n’est pas parallélisable.


L’accéleration est donc limité à 2.

Pr. M. Alaoui Talibi 40


LOI D’AMDAHL :

 En pratique, le (sur)cout dû au parallélisme est dû


aux parties séquentielles, mais aussi aux aspects
suivants :

✓ Démarrage et terminaison des taches


✓ Synchronisation
✓ Communications
✓ Surcouts logiciels dus aux compilateurs,
bibliothèques, outils, systèmes d’exploitation…

Pr. M. Alaoui Talibi 41


Pr. M. Alaoui Talibi 42
LE PARALLÉLISME DANS LES
MULTIPROCESSEURS

 Comment construire et analyser des algorithmes et


des programmes pour des machines si différentes.

 Peut-on concevoir une méthode de programmation


identique ?

 Existe-ildes outils de parallélisation automatique et


quels sont leur principes ?

Pr. M. Alaoui Talibi 43


LE PARALLÉLISME DANS LES
MULTIPROCESSEURS
 Certains
problèmes sont ils intrinsèquement
séquentiels ?

 Leparallélisme massif a-t-il un avenir et peut-il


être utilisé efficacement?

Voila quelques unes des questions auxquelles nous


nous proposons d’apporter des Réponses.

Pr. M. Alaoui Talibi 44


Paradigmes de base de la
programmation concurrente

Pr. M. Alaoui Talibi 45


PROGRAMMATION CONCURRENTE :
 Permettre d'effectuer plusieurs traitements, spécifiés
distinctement les uns des autres,« en même temps ».

 En général, dans la spécification d'un traitement,


beaucoup de temps est passé à « attendre ».

✓ Idée : exploiter ces temps d'attente pour réaliser


d'autres traitements, en exécutant en concurrence
plusieurs traitements.

Pr. M. Alaoui Talibi 46


PROGRAMMATION CONCURRENTE :

 Laprogrammation concurrente permet à des


processus multiples, de pouvoir partager des
ressources (structures de données, ressources
matériels, CPU, mémoire, dispositifs I/O).

Pr. M. Alaoui Talibi 47


PROGRAMMATION CONCURRENTE :
 Utilisation des temps d’attente de saisie :

Pr. M. Alaoui Talibi 48


PROGRAMMATION CONCURRENTE :
 Programme concurrent :

programme qui contient plusieurs processus (ou


threads) qui coopèrent.
✓ coopération Communication, échange
d’information

 Deux principales façons de communiquer :


✓ par l’intermédiaire de variables partagées.
✓ par l’échange de messages et de signaux (par ex.
canaux de communications).
Pr. M. Alaoui Talibi 49
PROGRAMMATION CONCURRENTE :
 Note: on considère un thread comme étant un
processus léger (lightweight process)

Pr. M. Alaoui Talibi 50


PROGRAMMATION CONCURRENTE :
 Processus vs thread :

✓ Processus :

- Un processus représente un programme en cours


d’exécution.

– Un processus possède un espace mémoire privé,


indépendant de celui des autres processus.

– Parce qu’ils ne partagent aucun espace mémoire


commun, deux processus qui veulent collaborer doivent le
faire en utilisant un mécanisme d’échange de messages .

Pr. M. Alaoui Talibi 51


PROGRAMMATION CONCURRENTE :

– Le contexte d’un processus est lourd : code,


registres.

- Créer et activer un processus est donc (très!)


coûteux!

Pr. M. Alaoui Talibi 52


PROGRAMMATION CONCURRENTE :
 Thread :
– Un thread représente une fonction en cours
d’exécution.

– Un processus peut contenir un ou plusieurs threads.

- Ces threads partagent alors la mémoire ainsi que


diverses autres ressources.

- Parce qu’ils partagent un même espace mémoire,


deux threads qui veulent collaborer peuvent le
faire par l’intermédiaire de variables partagées.
Pr. M. Alaoui Talibi 53
PROGRAMMATION CONCURRENTE :

- Le contexte d’un thread est léger.

- Créer et activer un thread est donc moins coûteux


que dans le cas d’un processus!

Pr. M. Alaoui Talibi 54


PROGRAMMATION CONCURRENTE :
 Interaction entre processus : communication

La communication est un échange de données entre processus,

• Soit par messages explicites.

Deux manières d'envoyer un message :

Synchrone : permet autant la synchronisation que la


communication.

Le Processus Emetteur doit attendre que son message soit reçu;


Et il est possible qu'un processus Récepteur doive attendre qu'un
message soit envoyé.

Pr. M. Alaoui Talibi 55


PROGRAMMATION CONCURRENTE :
Asynchrone :

L'émetteur poursuit son exécution après l'envoi du


message.

• soit à travers des variables partagées (visibles à


chaque processus; convient aux systèmes à mémoire
commune);

• ou bien par RPC (Remote Procedure Call).

Pr. M. Alaoui Talibi 56


PROGRAMMATION CONCURRENTE :

 RPC (remote procedure call) est :

✓ Un protocole réseau

✓ Ce protocole est utilisé dans le modèle client-serveur

✓ Pour assurer la communication entre le client, le serveur et


d’éventuels intermédiaires.

✓ Permettant de faire des appels de procédures sur


un ordinateur distant à l'aide d'un serveur d’applications.

Pr. M. Alaoui Talibi 57


PROGRAMMATION CONCURRENTE :
 Interaction entre processus : Synchronisation

La synchronisation, implique l'échange d'information de


contrôle entre processus.

Exemples :

Un processus dépend des données produites par un autre;


Si les données ne sont pas disponibles, le processus doit
attendre jusqu'à ce qu'elles soient disponibles.

Un processus peut changer son état à "Blocked"(Wait(Pi)),


et peut signaler aux Processus "Blocked" qu'ils peuvent
continuer (signal(Pi)).
Pr. M. Alaoui Talibi 58
PROGRAMMATION CONCURRENTE :
 Entrelacement
de threads : C'est un dispositif technique
commode pour étudier l'exécution concurrente de
processus.

 Définition:
Un entrelacement de deux séquences s et t est une
séquence U construite à partir des événements de s
et de t, de telle sorte que les événements de s
préservent leur ordre dans U ainsi que ceux de t.

Pr. M. Alaoui Talibi 59


PROGRAMMATION CONCURRENTE :

 Exemple :

Si a et z sont des événements concurrents,


On considère le cas ou a se produit avant z ou bien
z se produit avant a, mais on ignore le cas ou a et z
se produisent en même temps.

Pr. M. Alaoui Talibi 60


PROGRAMMATION CONCURRENTE :
 Concurrence comme entrelacement : Exemple
Soient deux Processus :

A:a;b
Z:x;y;z

L'exécution concurrente de A et Z, peut être étudiée en considérant les


entrelacements possibles (10):
 a b x y z
 a x b y z
 .....
 x y za b

L'entrelacement préserve l'ordre relatif dans le thread:

a doit se produire avant b, mais x y z étant dans un autre thread peuvent se produire
dans n'importe quel ordre relativement à a et b. Il en est de même pour x, y et z...

Pr. M. Alaoui Talibi 61


Une autre façon de classifier
les paradigmes de
programmation parallèle

Pr. M. Alaoui Talibi 62


UN AUTRE PARADIGME :
 Une autre classification intéressante des modèles
de programmation parallèle, qui peut aussi aider à
mieux comprendre certaines notions importantes
de conception d’algorithmes parallèles, est celui
qui distingue entre :

✓ parallélisme de données,
✓ parallélisme de contrôle
✓ et parallélisme de flux.

Pr. M. Alaoui Talibi 63


PARALLÉLISME DE DONNÉES :

 Correspond à l’application d’une même opération


sur tous les éléments d’une collection des données
homogènes, (de même type).

 Onparle dans ce cas de structures des données


régulières.

 Paropposition aux structures de données


dynamiques basées sur l’utilisation des pointeurs (
et donnant lieu à des arbres ou des graphes : donc
des structures de formes non régulières ).
Pr. M. Alaoui Talibi 64
PARALLÉLISME DE DONNÉES :

 L’ensemble du travail effectué consiste en une


série de phases de calcul.

 Chaque phase est une application d’une opération


sur une collection.

 Et
ou les différentes phases peuvent évidemment
manipuler des collections différentes.

Pr. M. Alaoui Talibi 65


PARALLÉLISME DE DONNÉES :

 La forme la plus simple de parallélisme de données


survient lorsque les calculs sur les différents
éléments sont complètement indépendants les uns
des autres.

L’ordre d’exécution n’a aucune importance et, donc,


que tous les calculs peuvent se faire en parallèle.

Pr. M. Alaoui Talibi 66


PAR EXEMPLE :
 Soit
l’opération consistant à multiplier chacun des
éléments d’une collection par l’entier 2.

 L’applicationd’une telle opération sur les éléments


d’un tableau d’entiers a pour obtenir un tableau b
pourrait alors s’écrire comme suit :

int a[n], b[n]


pour i varie de 1 … n
b[n]=2*a[n]

Pr. M. Alaoui Talibi 67


PARALLÉLISME DE DONNÉES :

Ici, c’est le compilateur qui s’occupe de générer le


code qui permettra l’exécution en parallèle des
diverses multiplications et affectations.

C’est aussi le compilateur qui s’occupera de


distribuer les données entre les processeurs, en
fonction des directives spécifiés par le programmeur.

Pr. M. Alaoui Talibi 68


PARALLÉLISME DE DONNÉES :

 Lafigure suivante illustre les deux principaux


types de décomposition et distribution d’un
tableau à deux dimensions 8*8 sur 4 processeurs, à
savoir distribution par bloc ou distribution
cyclique (ou des combinaisons entre les deux
modes).

Pr. M. Alaoui Talibi 69


DIFFÉRENTS TYPES DE DISTRIBUTIONS DE DONNÉES POUR UN
TABLEAU 8*8 SUR 4 PROCESSEURS. LES DONNÉES POUR LE
PROCESSEUR N°1 SONT EN GRIS

Pr. M. Alaoui Talibi 70


PARALLÉLISME DE CONTRÔLE :
 Consiste :

✓ à décomposer le travail à effectuer en


différentes taches,

✓ à identifier celles qui peuvent s’exécuter en


parallèle,

✓ puis finalement à ordonner, à l’aide de


structures de contrôle appropriés, l’exécution
de ces diverses taches.

Pr. M. Alaoui Talibi 71


PARALLÉLISME DE FLUX :

 Correspond au principe du travail à la chaine.

 Uneséquence d’opérations doit être appliquées en


cascade à une série de données similaires.

 Lesopérations à réaliser sont associées à des


éléments de calculs chainées de façon à ce que
l’entrée d’une opération soit la sortie de
l’opération précédente.
Pr. M. Alaoui Talibi 72
PARALLÉLISME DE FLUX :

 Leparallélisme de flux n’est donc rien d’autre


qu’un fonctionnement en mode pipeline des
éléments du calcul.

Pr. M. Alaoui Talibi 73


Systèmes parallèles et
distribués

Pr. M. Alaoui Talibi 74


PARALLÉLISME ET CONCURRENCE :

 Définition :

✓ On dit que deux processus s'exécutent en parallèle


lorsqu'ils s'exécutent sur des CPU différents.

✓ Ils sont concurrents lorsqu'ils concourent pour


l'obtention d'une même ressource CPU.

Leur exécution est alors entrelacée. Chacun


dispose à son tour d'un quantum de temps calcul.
Pr. M. Alaoui Talibi 75
SYSTÈMES PARALLÈLES :
 Découper un gros problème en de nombreux petits
problèmes :

- Super calculateurs pour le calcul scientifique


- Stations multiprocesseurs
- Grilles :
✓ SETI@Home
✓ folding@home
✓ défi cryptographiques (distributed.net)
✓ ....

Pr. M. Alaoui Talibi 76


PARALLÉLISME À DIFFÉRENTS NIVEAUX :

A l’intérieur du processeur :

✓ instructions en parallèle (pipeline)


✓ multi-cœurs

 Multi-processeurs

Pr. M. Alaoui Talibi 77


Le parallélisme au
sein du processeur :

Pr. M. Alaoui Talibi 78


LE PARALLÉLISME AU SEIN DU
PROCESSEUR :
 L’exécutiond’une instruction (multiplication par ex.)
nécessite plusieurs cycles d’horloge).

⇒ On exécute en parallèle les instructions indépenda-


ntes pour gagner du temps.

 Un processeur possède plusieurs Unités Arithmétique


et Logiques.

 Les
instructions peuvent être réarrangées afin
d’améliorer le rendement (out of order execution).
Pr. M. Alaoui Talibi 79
MULTI-CŒUR :

 Cœur :
Unité exécutant les instructions dans un processeur
Multi-cœur : plusieurs unités exécutant des
instructions en parallèle.

 Multi-cœur(tous sur un même circuit) ≠multi-


processeur (circuits différents).

Pr. M. Alaoui Talibi 80


PROCESSEUR MULTI-CŒUR :

 Une très grande partie des processeurs actuels sont


multi-cœurs (généralement de 2 à 8 cœurs).

 Encore plus de cœurs dans l’avenir :

✓ Prototype tera-scale (80 cœurs) d’Intel.

✓ Processeurs multi-cœurs pour les appareils mobiles


(smartphones, tablettes).

Pr. M. Alaoui Talibi 81


Le parallélisme multiprocesseurs :

Pr. M. Alaoui Talibi 82


LE PARALLÉLISME MULTIPROCESSEURS :

 Un concept ancien :

✓ premier ordinateur multi-processeur en 1962,

✓ premier ordinateur multi-processeur parallèle en


1969.

 Similaire au multi-cœur à l’exception de la


mémoire cache qui n’est pas partagée.

Pr. M. Alaoui Talibi 83


QUELQUES EXEMPLES DE
MULTIPROCESSEURS :

 Supercalculateurs :
- Le plus puissant : Computer K
- 88,128 processeurs 8-cœurs (2GHz)

- Le deuxième : Tianhe-1A
- 14 336 processeurs
- 7 168 processeurs graphiques

Pr. M. Alaoui Talibi 84


Les systèmes distribués :

Pr. M. Alaoui Talibi 85


INTÉRÊT DES SYSTÈMES DISTRIBUÉS :

 Ensemble de processeurs autonomes.

 Qui ne se partagent pas de mémoire primaire.

 Maisqui coopèrent par envoi de messages à travers


un réseau de communication.

Pr. M. Alaoui Talibi 86


INTÉRÊT DES SYSTÈMES DISTRIBUÉS :
 Mise en commun d'un grand nombre de ressources à
faible coûts :
– Bon rapport performance / prix.
– Puissance globale virtuellement illimitée.
- Supérieure à celle des gros calculateurs

 Disponibilité et flexibilité :

– Un élément peut tomber en panne sans bloquer tout


le système.
– Flexibilité : Distribution de la charge permet d’exécuter
un travail sur la machine la plus disponible.
Pr. M. Alaoui Talibi 87
INTÉRÊT (2) :
 Distribution naturelle de certaines applications :
- distribution géographique d’agences bancaires.

 Partage de ressources coûteuses entre plusieurs


utilisateurs/machines.
– Accès à distance à une ressource indisponible en
local.
– Accès aux mêmes ressources depuis tous les endroits
du système.

Pr. M. Alaoui Talibi 88


INCONVÉNIENTS DES SYSTÈMES
DISTRIBUÉS :

 Problèmes inhérents aux communications


– Si pas de mémoire partagée, communications explicites
(moins de communications).
– Lenteur, saturation, perte de messages.

 Partage et distribution de données impose mécanismes


complexes :
– Synchronisation.
– Sécurité.

Pr. M. Alaoui Talibi 89


LE PLUS GRAND SYSTÈME DISTRIBUÉ
ACTUEL :

Internet :

Contient de nombreux sous-systèmes selon le


protocole considéré :

– Web (http)

– peer-to-peer : permet à plusieurs ordinateurs


de communiquer entre eux via un réseau.

Pr. M. Alaoui Talibi 90


SUPER-CALCULATEUR ?
Seti@home !
– Les machines de tout le monde :

 Puissance virtuellement illimitée


- N Gflop/s par machine, des millions des
machines.

 Calculsindépendants
 Modèle plus distribué que parallèle

Pr. M. Alaoui Talibi 91


SUPER-CALCULATEURS
 Cray Jaguar à ORNL :

- 20 000 noeuds à six-core


Assemblés par réseau Cray spécifique

- Presqu'un Cluster, mais réseau trop spécifique

- Plus d'1 PetaFlop/s

Pr. M. Alaoui Talibi 92


SUPER-CALCULATEURS :
 Tianhe en Chine :

- 7000 nœuds à 2 processeurs et 2 GPUs.


- Un cluster avec des accélérateurs.
- 2 Petaflop/s.

Pr. M. Alaoui Talibi 93


DIFFÉRENCES ENTRE SYSTÈMES
PARALLÈLES ET DISTRIBUÉS

 Architecture matérielle et/ou logicielle


- Un système parallèle peut être distribué
Si assemblage de machines à mémoires
indépendantes
- ou non
Si une seule grosse machine parallèle.

Application cible
– Applications parallèles dans les systèmes
parallèles :
Communication, synchronisation, … entre les différentes

Pr. M. Alaoui Talibi 94


PROGRAMMATION PARALLÈLE
IMPÉRATIVE

Pr. M. Alaoui Talibi 2018-2019 95


PROGRAMMATION PAR VARIABLES
PARTAGÉES : EXCLUSION
MUTUELLE VS SYNCHRONISATION
DE CONDITION

Pr. M. Alaoui Talibi 2018-2019 96


PLAN :

 Introduction
 Processus
 Appels système
 Ordonnancement des processus
 Communication et synchronisation des
processus : l’exclusion mutuelle.

Pr. M. Alaoui Talibi 2018-2019 97


PROCESSUS :
 Lesordinateurs mono processeur actuels sont capables
d’exécuter plusieurs programmes « simultanément ».

 Multiprogrammation, multi-tâches ou encore pseudo-


parallélisme.
 En réalité ce n’est pas vrai, une machine mono processeur ne
peut exécuter qu’une seule tâche à un instant donné.

 Le processeur est affecté, périodiquement, à chaque programme


en cours d’exécution pour une durée infiniment petite ➔ donne
l’impression d’exécuter tous les programmes en même temps.

Pr. M. Alaoui Talibi 2018-2019 98


PROCESSUS :

 Un processus est un programme en exécution qui a


son propre environnement

 Espace d’adressage
 Code (instructions du programme)
 Pile
 Compteur ordinal
 Registres
 Variables
 …
 Un programme peut être exécuté par plusieurs processus.

Pr. M. Alaoui Talibi 2018-2019 99


PROCESSUS :

Les systèmes d’exploitation ont besoin de savoir que tous

les processus nécessaires existent bel et bien.

Par exemple le contrôleur d’un four à micro-ondes : il

peut être envisageable que tous les processus susceptibles

d’intervenir soient actifs pendant le fonctionnement du

système.

Pr. M. Alaoui Talibi 2018-2019 100


PROCESSUS :

En général, les systèmes d’exploitation ont besoin de


disposer d’une méthode pour créer et arrêter les
processus, selon le cas, au cours de leur activité.

Pr. M. Alaoui Talibi 2018-2019 101


PROCESSUS :
 Création des processus
 Quatre événements sont à l’origine de la création d’un
processus.
 Initialisation du système.
 Exécution d’un appel système de création de processus par un
processus en cours d’exécution.
 Requête utilisateur sollicitant la création d’un nouveau
processus.
 Initiation d’un travail en traitement par lot.

Pr. M. Alaoui Talibi 2018-2019 102


PROCESSUS :

 Sous UNIX, la commande ps sert à afficher la liste


des processus en cours d’exécution.

 Sous windows 95/98/Me, le fait de taper Ctrl+Alt+Del


une seule fois permet de voir les processus en cours.

 Sous Windows 2000/XP, c’est le gestionnaire des


taches qui intervient.

Pr. M. Alaoui Talibi 2018-2019 103


PROCESSUS :
Création des processus :
 La création d’un processus se traduit toujours par
un :
appel système déclenché à partir de :
 Processus utilisateur OU
 Processus système, OU
 Processus gestionnaire de traitements par lots.

Cet appel demande au système d’exploitation de créer un


nouveau processus et indique, directement ou indirectement,
quel programme y exécuter.

 Sous Unix : fork() crée un clone du processus appelant


 Sous Win32 : Create_Process.

Pr. M. Alaoui Talibi 2018-2019 104


PROCESSUS :

 Dans les deux cas, une fois qu’un processus a été


crée, le parent et le fils disposent désormais de leur
propre espace d’adressage.

 S’il arrive que l’un des processus modifie un mot dans


son espace d’adressage, le changement n’est pas
visible par l’autre processus.

Pr. M. Alaoui Talibi 2018-2019 105


PROCESSUS :

Fin d’un processus :

 Une fois qu’un processus a été créé, il commence à


s’exécuter, quelle que soit sa tache.

 Mais tôt ou tard, le nouveau processus s’arrete pour


diverses raisons :

Pr. M. Alaoui Talibi 2018-2019 106


PROCESSUS
 Fin d’un processus
 Arrêt normal (volontaire)
 Exécution de toutes les instructions du programme correspondant.
 Arrêt à cause d’une erreur fatale
 Erreur imprévisible (division par 0)
 Par exemple, saisir la commande cc foo.c

Pour compiler le programme foo.c et que le fichier correspondant


n’existe pas, le compilateur s’arrete.

Pr. M. Alaoui Talibi 2018-2019 107


PROCESSUS :
▪ Arrêt à cause d’une erreur provoquée par le processus :

Souvent due à un bogue du programme.

Par exemple, les erreurs peuvent provenir de l’exécution :

- d’une instruction illégale,

- D’une référence mémoire inexistante

- d’une division par 0

Pr. M. Alaoui Talibi 2018-2019 108


PROCESSUS :

▪ Le quatrième motif d’ arrêt d’un processus :

Intervient lorsqu’il exécute un appel système indiquant

au SE d’ Arrêter un ou plusieurs autres processus.

Sous UNIX, cet appel est kill.

Pr. M. Alaoui Talibi 2018-2019 109


PROCESSUS
 Hiérarchie des processus
 Chaque processus a un et un seul processus parent
 Sous Unix le processus « init » est le seul qui n’a pas de
parent.
 C’est le processus qui initialise le système.

 Un processus peut avoir des processus fils 0,1,2


ou plus.
 Sous Unix, il est possible d’envoyer des signaux à toute
une arborescence de processus
 Demande d’arrêt par exemple
 Le principe de l’hiérarchie n’existe pas sous Windows
 Tous les processus sont égaux

Pr. M. Alaoui Talibi 2018-2019 110


PROCESSUS :
 Etats des processus
 Un processus peut être dans l’un des trois états
 Elu : En cours d’exécution
 C’est lui qui détient la CPU
 Prêt
 A toutes les ressources nécessaires et attend son tour pour la
CPU.
 Bloqué
 Attend une ressource ou un événement
 Ne peut pas être candidat pour obtenir la CPU avant qu’il soit
débloqué

Pr. M. Alaoui Talibi 2018-2019 111


PROCESSUS :
 La transition 1 : rend le processus
bloqué en attente d’une ressource ou
d’un événement.

 La transition 2 : reprend la CPU au


processus et la donne à un autre
processus. Elu
1: réquisition
Notre processus doit attendre son tour. d’une ressource 2: réquisition
de la CPU
3: attribution
 La transition 3 : donne (redonne) la CPU de la CPU
à notre processus.
Bloqué
 La transition 4 : débloque le processus Prêt
ce qui le rend candidat pour obtenir la 4: acquisition
de toutes les ressources
CPU.

 Un processus prêt ne peut pas devenir


bloqué sans passer par l’état « élu ».

 Un processus bloqué ne peut pas


prendre la CPU sans passer par l’état «
prêt ». Pr. M. Alaoui Talibi 2018-2019 112
PROCESSUS
 Appels systèmes :
 Définissent l’interface entre le SE et les programmes
utilisateurs
 Sorte de bibliothèque de fonctions.
 Environ 100 appels systèmes dans la norme UNIX.
 Analogie avec l’appel de fonctions en langage C.
 Les tâches correspondant aux appels systèmes sont
exécutées en mode noyau.
 Services offerts à travers les appels systèmes :
 Gestion des processus
 Gestion de la mémoire
 Gestions des fichiers
 Gestion des E/S

Pr. M. Alaoui Talibi 2018-2019 113


PROCESSUS
Principaux appels système de gestion des processus de

la norme UNIX :

Appel système description


pid = fork() Crée un processus enfant identique au parent

pid = waitpid(pid, &stat, Attend la terminaison d'un fils


options)

exit (statut) Termine l'exécution du processus et renvoie le


statut

Pr. M. Alaoui Talibi 2018-2019 114


PROCESSUS :
 Appels système de gestion des processus
 fork
 Crée une copie conforme du processus appelant
 Même code
 Mêmes descripteurs de fichiers
 …
 Sauf la valeur retournée par fork
 Nulle dans le nouveau processus (fils)
 PID du fils dans le processus père
 Les deux processus évolueront, en général, différemment.
 Le seul moyen de créer les processus.

Pr. M. Alaoui Talibi 2018-2019 115


ORDONNANCEMENT DES PROCESSUS :

Pr. M. Alaoui Talibi 2018-2019 116


ORDONNANCEMENT DES PROCESSUS :

Lorsqu’un ordinateur est multiprogrammé, il possède


fréquemment plusieurs processus en concurrence pour
l’obtention de temps processeur.

Cette situation se produit chaque fois que deux


processus ou plus sont en état prêt en même temps.

S’il y’a un seul processeur, un choix doit être fait quand


au prochain processus.

Pr. M. Alaoui Talibi 2018-2019 117


ORDONNANCEMENT DES PROCESSUS :

▪ La partie du système d’exploitation qui effectue ce


choix se nomme l’ordonnanceur (sheduler).

▪ L’algorithme qu’il emploie s’appelle algorithme


d’ordonnancement (sheduling algorithm).

Pr. M. Alaoui Talibi 2018-2019 118


ORDONNANCEMENT DES PROCESSUS :
 L’ordonnanceur peut jouer un rôle prépondérant pour
améliorer les performances du système d’exploitation
 Exemple :
 Etant donnés deux processus P1 et P2
 P1 : processus de rafraichissement de l’écran
 P2 : processus d’envoi de courrier électronique
 Retarder P1 (i.e. ralentir le rafraichissement de l’écran) ➔
l’utilisateur perçoit ce petit retard comme une dégradation du
service.
 Par contre un petit retard de l’envoi du courrier électronique ne
sera pas senti par l’utilisateur.
 L’ordonnanceur doit, normalement favoriser le processus P1.

Pr. M. Alaoui Talibi 2018-2019 119


ORDONNANCEMENT DES PROCESSUS :
 Quand ordonnancer ?
Un large éventail de situations nécessitent de
l’ordonnancement.

- lorsqu’un nouveau processus est créé, il faut décider


s’il faut exécuter d’abord le processus parent ou le
processus fils. Etant donné que les deux sont en état
prêt.

- lorsqu’un processus se termine, un autre processus


doit être choisi dans le jeu des processus prêts.
Pr. M. Alaoui Talibi 2018-2019 120
ORDONNANCEMENT DES PROCESSUS :
- lorsqu’un processus bloque sur des E/S un autre
processus, un autre processus doit être sélectionné
pour être exécuté.

- lorsqu'une interruption d’E/S se produit, il faut


également prendre une décision d’ordonnancement.

Si l’horloge matérielle fournit des interruptions


périodiques à une fréquence de 50 ou 60 Hz, par
exemple, une décision d’ordonnancement peut être
prise à chaque kéme interruption.
Pr. M. Alaoui Talibi 2018-2019 121
ORDONNANCEMENT DES PROCESSUS :
On peut classer les algorithmes d’ordonnancement en
deux catégories selon leur manière de réagir aux
interruptions de l’horloge :

- Un algorithme non préemptif : sélectionne un


processus, puis le laisse s’exécuter jusqu’à ce qu’il
bloque ou qu’il libère volontairement le processeur.
Même s’il s’exécute pendant des heures.

- Par contre un algorithme préemptif, sélectionne un


processus et le laisse s’exécuter pendant un délai
déterminé. Si le processus est toujours en cours à
l’issue de ce délai : il est suspendu.
Pr. M. Alaoui Talibi 2018-2019 122
ORDONNANCEMENT DES PROCESSUS :

 Efficacité de l’utilisation du processeur


 Le basculement du processeur d’un processus à un autre
est relativement coûteux

 Basculement en mode noyau


 Sauvegarder l’état du processus en cours
 Charger l’environnement du processus suivant
 Démarrer le processus

 ➔ éviter les basculements très nombreux

Pr. M. Alaoui Talibi 2018-2019 123


ORDONNANCEMENT DES PROCESSUS :

 Plusieurs algorithmes d’ordonnancement :


 Ordonnancement de type tourniquet (round robin)

 Ordonnancement par priorités

 Ordonnancement garanti

 Ordonnancement par tirage au sort

 …

Pr. M. Alaoui Talibi 2018-2019 124


ORDONNANCEMENT DES PROCESSUS :

 Ordonnancement de type tourniquet (round robin)

 Le plus ancien et le plus utilisé


 Tous les processus à ordonnancer sont au même pied
d’égalité.
 Le processeur est attribué, à tour de rôle, à chacun des
processus en lice pour une durée donnée (quantum)
 Un processus, qui n’a pas terminé son exécution au bout
de son quantum, se met de nouveau dans la file
d’attente.

Pr. M. Alaoui Talibi 2018-2019 125


ORDONNANCEMENT DES PROCESSUS :

 Le choix du quantum est très déterminant pour les


performances du système.

 Un quantum très petit provoquerait des basculements très


fréquents ➔ dégradation des performances

 Un quantum très grand ➔ temps d’attente est important pour les


processus prêts ➔ atteinte à l’interactivité

Pr. M. Alaoui Talibi 2018-2019 126


ORDONNANCEMENT DES PROCESSUS :
 Ordonnancement par priorités
 En réalité, les processus ne sont pas de même niveau
d’importance
 Les processus système sont le pivot du système et par la
suite doivent être les plus prioritaires.
 Un processus d’envoi de courrier n’est pas sensible à un petit
retard.
 Un processus de traitement de texte peut être sensible au
retard d’affichage des caractères saisis au clavier.

 ➔ il est important de définir des priorités entre les


processus

Pr. M. Alaoui Talibi 2018-2019 127


ORDONNANCEMENT DES PROCESSUS :

 Ordonnancement par priorités


 Principe :
 Attribution d’une priorité à chaque processus
 Parmi les processus prêts, l’ordonnanceur choisit celui qui
a la plus grande priorité

 La priorité peut être :


 Statique : ne change pas le long de l’exécution ➔ un
processus de priorité supérieure est toujours prioritaire
par rapport à un autre de prioritaire moindre.

Pr. M. Alaoui Talibi 2018-2019 128


ORDONNANCEMENT DES PROCESSUS :

 Dynamique
 Le niveau de priorité du processus qui détient la CPU
baisse dans le temps jusqu’à ce qu’un autre processus
devient plus prioritaire et lui prend la CPU.

 De même le processus prêt se voit augmenter le niveau


de priorité au fil du temps ce qui lui donne la chance
d’avoir la CPU.

Pr. M. Alaoui Talibi 2018-2019 129


ORDONNANCEMENT DES PROCESSUS :
 Ordonnancement par priorités

 Catégories de priorités
 Le système définit plusieurs catégories de priorités
 Regrouper les processus par catégorie
 Les processus de la même catégorie ont le même niveau de
priorité.
 L’ordonnancement adopté entre ces processus est celui de
type Tourniquet.
 Les processus de la catégorie de priorité supérieure sont
toujours prioritaires par rapport aux autres processus des
autres catégories.

Pr. M. Alaoui Talibi 2018-2019 130


ORDONNANCEMENT DES PROCESSUS :
 Ordonnancement par priorités :
 Files d’attente multiples
 Définition de plusieurs catégories de priorités
 Le quantum du processeur n’est pas le même pour toutes les
catégories. La catégorie de niveau de priorité inférieure a un
quantum relativement grand que celui de la catégorie de priorité
supérieure.
 Récompenser le retard des processus de priorité inférieure par une
durée de détention de la CPU supérieure.
 Le processus qui termine sa durée et lâche le processeur passe à la
catégorie inférieure.
 les processus interactifs commencent dans la catégorie
supérieure.
 Une interaction (clique, retour chariot) remet le processus dans
la catégorie supérieure.

Pr. M. Alaoui Talibi 2018-2019 131


ORDONNANCEMENT DES PROCESSUS :
 Ordonnancement garanti
 Le principe de cet ordonnancement est que les
processus doivent avoir, globalement, le même cumul
des durées de détention du processeur.
 Le système maintient, pour chaque processus, un taux
correspondant à la durée effective d’utilisation de la
CPU par rapport à son quota.

Le processus qui a le taux le plus petit (qui a moins


utilisé la CPU) sera le plus prioritaire.
 Exemple
Un processus de taux ½ (a utilisé la moitié de son quota) est
prioritaire par rapport au processus de taux 1,2 (a dépassé
son quota de 20%).
Pr. M. Alaoui Talibi 2018-2019 132
ORDONNANCEMENT DES PROCESSUS :
 Ordonnancement par tirage au sort :

 L’idée de base consiste à donner aux processus des «


billets de loterie » pour différentes ressources du
système et notamment pour le temps processeur.
 L’ordonnanceur effectue, à chaque fois, un tirage au
sort et le processus possédant le billet tiré aura le CPU.
 Possibilité d’instaurer une discrimination positive :
 Pour favoriser certains processus, il suffit de leur attribuer
plus de billets que les autres
 Le processus qui a plus de billets a beaucoup de chance qu’un
de ses billets soit tiré.

Pr. M. Alaoui Talibi 2018-2019 133


ORDONNANCEMENT DES PROCESSUS :

 Des processus coopératifs peuvent s’échanger leurs


billets
 Un processus bloqué, en attente d’un autre processus,
préférerait donner ses billets à ce dernier.
 ➔ le processus bloquant aura, donc, plus de chance
d’être sélectionné.
 Notre processus pourra récupérer ses billets et éventuellement
ceux de l’autre processus.

Pr. M. Alaoui Talibi 2018-2019 134


COMMUNICATION ET SYNCHRONISATION DES
PROCESSUS :

 Comment un processus passe des informations à un


autre processus ?

 Comment éviter des conflits entre des processus


concurrents qui s’engagent dans des activités
critiques ?

 Comment synchroniser les processus dépendants ?

Pr. M. Alaoui Talibi 2018-2019 135


COMMUNICATION ET SYNCHRONISATION DES
PROCESSUS : L’EXCLUSION MUTUELLE

 Les conditions de concurrence


 La section critique
 L’exclusion mutuelle avec attente active
 Le sommeil et l’activation
 Les sémaphores
 Les moniteurs
 L’échange de message
 Les barrières
Pr. M. Alaoui Talibi 2018-2019 136
CONDITIONS DE CONCURRENCE
 Exemple : spooler d’impression
 Principe
 Un processus qui veut imprimer un fichier, entre son nom dans
un répertoire spécial : répertoire du spooler
 Le démon d’impression (spooler) inspecte périodiquement son
répertoire, s’il y a un fichier il l’imprime et le supprime du
répertoire.
 Le répertoire du spooler possède un grand nombre d’entrées
numérotées : 0, 1 ,2 … chacune pouvant accueillir un nom de
fichier.
 Le spooler utilise deux variables partagées : out et in
 Out : pointe vers le prochain fichier à imprimer
 In : pointe vers la prochaine entrée libre du répertoire
 Les variables out et in peuvent être stockées dans un fichier
de deux mots, disponible pour tous les processus.

Pr. M. Alaoui Talibi 2018-2019 137


CONDITIONS DE CONCURRENCE
 Problème : deux processus A et B
tentent d’imprimer en même temps
 Le processus A lit la valeur de in, et en stocke
out in
la valeur, 7, dans une variable locale appelée
4 7
next_free_slot.
 A ce moment là, une interruption se 4 Linux.pdf
Processus A
produit. La CPU jugeant que le processus 5 Prog.c
A a bénéficié de suffisamment du temps 6 Script.sh
d’exécution, bascule vers le processus B. Processus
7
B
 Celui-çi lit la valeur de in et récupère
également un 7. il stocke cette valeur dans
sa variable locale appelée aussi next_free_slot.
 A ce point, les 2 processus pensent que la
prochaine entrée disponible est la 7.
Pr. M. Alaoui Talibi 2018-2019 138
CONDITIONS DE CONCURRENCE
Le processus B continue de s’exécuter. Il stocke son
nom de fichier dans l’entrée 7 et actualise in qui
prend la valeur 8.

Finalement, le processus A s’exécute à nouveau,


reprenant les choses où il les avait laissées. Il
examine next_free_lost, y trouve un 7, et écrit son
nom de fichier dans le connecteur 7, écrasant le nom
que le processus B venait juste d’y placer. Ensuite, il
calcule next_free_lost+1, ce qui donne 8, et
positionne in à 8.

Pr. M. Alaoui Talibi 2018-2019 139


CONDITIONS DE CONCURRENCE
Problème : deux processus A et B tentent
d’imprimer en même temps

 Le processus B ne recevra jamais de sortie.


L’utilisateur B va attendre longtemps une impression
qui ne viendra jamais.

 De telles situations, ou deux processus ou plus


lisent ou écrivent des données partagées et ou le
résultat final dépend de quel élément s’exécute à
un instant donné : sont nommées conditions de
concurrence.

Pr. M. Alaoui Talibi 2018-2019 140


SECTION CRITIQUE :
 Appelée aussi région critique, c’est l’ensemble
d’instructions d’un processus (par exemple :
accès à la mémoire ou fichiers partagés)
susceptibles de provoquer les conditions de
concurrence avec d’autres processus.
 Pour éviter les conditions de concurrence il faut
éviter que les processus concernés ne se trouvent
en même temps dans la section critique.

L’Exclusion mutuelle

Pr. M. Alaoui Talibi 2018-2019 141


SECTION CRITIQUE :
 L’exclusion mutuelle est une méthode qui permet de
s’assurer que si un processus utilise une variable
ou un fichier partagé, les autres processus seront
exclus de la même activité.

La partie du programme à partir de laquelle on accède à


la mémoire partagée se nomme région critique, ou
section critique.

Si l’on pouvait empêcher que deux processus se trouvent


simultanément dans leurs sections critiques, on éviterait les
conditions de concurrence.

Pr. M. Alaoui Talibi 2018-2019 142


SECTION CRITIQUE
 Quatre conditions sont nécessaires pour éviter les
conditions de concurrence tout en assurant la
coopération et l’utilisation adéquate des ressources
partagées :
 Deux processus ne doivent pas se trouver simultanément
dans leurs sections critiques (exclusion mutuelle)
 Il ne faut pas faire de suppositions quant à la vitesse ou le
nombre de processeur mis en œuvre.
 Aucun processus s’exécutant à l’extérieur de la section
critique ne doit bloquer d’autres processus.
 Aucun processus ne doit attendre indéfiniment pour
pouvoir entrer dans sa section critique.

Le comportement que nous voulons mettre en œuvre est celui


illustré à la figure suivante.
Pr. M. Alaoui Talibi 2018-2019 143
SECTION CRITIQUE
A entre dans sa A quitte sa
section critique section critique

Processus A

B tente B entre dans B quitte sa


d’entrer dans sa section section
sa section critique critique
critique
Processus B

B est
T T2 bloqué T3 T4
1
temps

2018-2019 144
L’EXCLUSION MUTUELLE

 Plusieurs manières d’assurer l’exclusion mutuelle

 L’exclusion mutuelle avec attente active

 Le sommeil et l’activation

 Les sémaphores

 …

Pr. M. Alaoui Talibi 2018-2019 145


L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Leprincipe est que lorsqu’un processus se trouve


dans sa section critique, les autres processus ne
peuvent pas y entrer, mais restent actifs et
attendent que le processus en cours termine la
région critique.

 Plusieurs techniques sont utilisées


 Désactivation des interruptions
 Variables de verrou
 Alternance stricte
 Solution de Peterson
 Instruction TSL
Pr. M. Alaoui Talibi 2018-2019 146
L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Désactivation des interruptions :

 Le processus qui entre dans sa section critique, désactive les interruptions


 ➔ Dans ce cas, l’horloge aussi ne pourrait pas envoyer les interruptions, ce qui
implique que le processeur ne pourrait pas basculer vers un autre processus.
 Le processus en cours est sûr maintenant qu’aucun processus concurrent (ou
autre) ne pourra entrer dans la section critique.
 Les autres processus n’ont même pas la possibilité d’avoir le processeur tant que les
interruptions sont désactivées.
 Le processus en cours doit réactiver les interruptions à la fin de la section critique.
 Attention!!
 Donner aux processus utilisateurs de bloquer les interruptions n’est pas une bonne idée
 Un processus (utilisateur) qui termine sa section critique et oublie de réactiver les
interruptions.
 Un processus (utilisateur) qui, volontairement, ne réactive pas les interruptions pour
s’emparer (l’utiliser tout seul) exclusivement du processeur.
 La désactivation des interruptions peut être intéressante pour les processus en
mode noyau (qui n’impose pas des restrictions sur les instructions exécutées).

Pr. M. Alaoui Talibi 2018-2019 147


L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :
 Variables verrou : Solution logicielle
 Le processus qui veut exécuter sa section critique, teste une variable
verrou ( ou lock) partagée dont la valeur initiale est 0.
 Si cette variable est à 0, alors il la remet à 1 et entre dans la section critique

 Si le verrou est déjà à 1, ce qui signifie qu’un autre processus se trouve dans la

section critique ➔ le processus doit attendre que le verrou passe à 0


 Le processus remet le verrou à 0 quand il termine la section critique
 Problème :
 La variable verrou est partagée ➔ pour y accéder, les conditions de concurrence

peuvent se produire
 Un processus qui a testé le verrou et le trouve à 0, perd le processeur avant

de remettre le verrou à 1 (un autre processus s’exécute et le fait à sa place).


 Un deuxième processus teste aussi le verrou (toujours à 0) et le remet à 1
ensuite, il entre dans sa section critique.
 Lorsque le premier processus reprend son exécution, il remet le verrou à 1(il est

déjà à 1) et commence sa section critique.

Résultat : les deux processus se trouvent en même temps dans la section


critique!!
Pr. M. Alaoui Talibi 2018-2019 148
L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Alternance stricte
 Deux processus alternent strictement leur entrées dans la
section critique
 Entre deux exécutions de la section critique par l’un des
processus, il est impératif que l’autre processus exécute aussi la
section critique.
 Pratique pour représenter le modèle basique de producteur /
consommateur.
 Principe
 Les deux processus inspectent une variable « turn »
 Le processus 1 entre dans sa section critique si turn est à 0.
Sinon, il entre dans une phase d’attente active.
 A l’inverse du processus 1, le processus 2 entre dans sa section
critique si turn est à 1. Sinon il entre dans une phase d’attente.
 Chacun des deux processus alterne la variable turn à la fin de sa
section critique.
 Le processus 1 : 0➔1
 Le processus 2 : 1➔0
Pr. M. Alaoui Talibi 2018-2019 149
L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Alternance stricte
 Code d’entrée dans la section critique des deux
processus

Processus 1 Processus 2

Pr. M. Alaoui Talibi 2018-2019 150


RAPPEL : ÉVITER LES CONDITIONS
DE CONCURRENCE :
 Quatre conditions sont nécessaires pour éviter les
conditions de concurrence tout en assurant la
coopération et l’utilisation adéquate des
ressources partagées :
1. Deux processus ne doivent pas se trouver
simultanément dans leurs sections critiques (exclusion
mutuelle).
2. Pas de suppositions sur la vitesse ou le nombre de
processeur mis en œuvre.
3. Aucun processus s’exécutant à l’extérieur de la section
critique ne doit bloquer d’autres processus
4. Aucun processus ne doit attendre indéfiniment pour
pouvoir entrer dans sa section critique.

Pr. M. Alaoui Talibi 2018-2019 151


L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Alternance stricte
 Problème :

 La démarche proposée entre en conflit avec la troisième


condition :

Le processus 1 peut être bloqué par un processus, hors de sa


section critique.

Par exemple, le processus 1 ne serait pas autorisé à imprimer


un autre fichier, car le processus 2 serait occupé à une autre
tache.

Pr. M. Alaoui Talibi 2018-2019 152


L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Solution de Peterson
 Combine l’alternance stricte et la variable verrou

 Un processus peut enchaîner deux (ou plusieurs)


exécutions de la section critique, alors que
l’autre processus n’en a pas exécuté une.

 L’algorithme de Peterson, est composé de deux


procédures développées en C ANSI.

Pr. M. Alaoui Talibi 2018-2019 153


L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Code de la solution de Peterson :


#define n 2 /*nb de processus*/
int turn; /* à qui le tour */
int interested[n]; /* toute valeur initialement 0 (FALSE)*/
void enter_region (int process) /* Le processus est 0 ou 1*/
{
int other; /* nb des autres processus */
other = 1 – process; /* l’opposé du processus */
interested[process] = TRUE; /* montre que vous êtes intéressés */
turn = process; /* définit l’indicateur */
while(turn == process && interested[other] == TRUE); /* instruction null */
}

void leave_region(int process) /* processus : qui quitte */


{
inerested[process] = FALSE; /* indique départ de la section critique */
}

Pr. M. Alaoui Talibi 2018-2019 154


L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Avantd’utiliser les variables partagées, chaque


processus appelle enter_region avec son propre
numéro de processus, 0 ou 1.

 Cet appel le met en attente, jusqu’à ce qu’il entre

 Unefois qu’il a fini avec les variables partagées, le


processus appelle leave_region pour autoriser un
autre processus à entrer.

Pr. M. Alaoui Talibi 2018-2019 155


L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :
 Voyons comment fonctionne cette solution :
 1er cas :
 Aucun des processus ne se trouve dans sa section
critique.
 Le processus 0 appelle enter_region.
 Il montre son intérêt en positionnant turn à 0.
 Si le processus 1 est désintéressé, enter_region
retourne immédiatement.
 Si le processus 1 appelle maintenant enter_region,
il attend jusqu’à ce que interested[0] passe à FALSE.
 Ceci ne se produit que si le processus 0 appelle
leave_region.
Pr. M. Alaoui Talibi 2018-2019 156
L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 2éme cas :

 Les 2 processus appellent enter_region simultanément.


 Ils vont stocker tous les 2 leur numero de processus dans
turn.
 Supposons que le processus 1 soit stocké en dernier : turn
est à 1.
 Lorsque les 2 processus arrivent, le processus 0 entre en
section critique.
 Le processus 1 n’entre pas en section critique tant que le
processus 0 n’a pas quitté la sienne.

Pr. M. Alaoui Talibi 2018-2019 157


L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Instruction TSL :

Etudions maintenant une proposition qui sollicite un


peu d’aide de la part du matériel. De nombreux
ordinateurs, et notamment ceux qui ont été conçus
pour accueillir plusieurs processeurs, prennent en
charge l’instruction :

TSL RX, LOCK

Pr. M. Alaoui Talibi 2018-2019 158


 Elle fonctionne de la manière suivante :

Elle lit le contenu du mot mémoire lock dans le


registre RX, puis stocke une valeur différente de 0 à
l’adresse mémoire lock.

Les opérations qui consistent à lire le mot et à y


stocker une valeur sont absolument indivisibles :
aucun autre processeur ne peut accéder à la
mémoire tant que l’instruction n’est pas terminée.

Le processeur exécutant l’instruction TSL verrouille


le bus mémoire pour interdire aux autres processeurs
d’accéder à la mémoire tant qu’il n’a pas terminé.
Pr. M. Alaoui Talibi 2018-2019 159
 DONC, pour exploiter l’instruction TSL, on fait
appel à une variable partagée, lock, afin de
coordonner l’accès à la mémoire partagée.

Lorsque lock est à 0, n’importe quel processus peut


la positionner à 1 via l’instruction TSL, puis lire ou
écrire dans la mémoire partagée. Cela fait, le
processus repositionne lock à 0 à l’aide d’une
instruction move ordinaire.

Mais comment utiliser cette instruction pour


empêcher deux processus d’entrer simultanément
dans leurs sections critiques ?
Pr. M. Alaoui Talibi 2018-2019 160
La solution est illustré dans les sous-programmes
suivants :

Enter_region :
TSL REGISTER, LOCK |copie lock dans le registre et
|la positionne à 1
CMP REGISTER, #0
JNE enter_region
RET

leave_region :
MOV LOCK, #0
RET
Pr. M. Alaoui Talibi 2018-2019 161
L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE :

 Limitations
 Toutes les solutions de cette catégorie obligent le
processus en attente d’entrer dans sa section critique
à rester actif.
 Le processus s’installe dans une petite boucle en
attendant l’ouverture.

 ➔ Cette approche est très consommatrice du temps


processeur.
 Le processus consomme, inutilement, sa part du
processeur.

Pr. M. Alaoui Talibi 2018-2019 162


SOMMEIL ET ACTIVATION :
 Principe :
 Le processus, en attente d’entrer dans sa section critique,
ne doit pas rester actif.
 N’a pas besoin d’avoir la CPU
 ➔ Le processus en attente doit se bloquer (s’endormir)
en attendant que le processus en cours le débloque (le
réveille).
 Deux primitives sont utilisées : sleep et wakeup
 Un processus qui n’est pas autorisé à entrer dans la section
critique se bloque (est suspendu de la liste de l’ordonnanceur
) en appelant la primitive sleep.
 A la fin de la section critique, le processus vérifie si un processus
est bloqué, si c’est le cas il le réveille avec la primitive wakeup.
Pr. M. Alaoui Talibi 2018-2019 163
SOMMEIL ET ACTIVATION :
 Producteur/consommateur
 Deux processus se partagent un tampon (buffer) de taille
fixe. Le premier (producteur) écrit des informations dans le
tampon et le deuxième (consommateur) y récupère les
informations.
 Le producteur se bloque quand le tampon devient plein.
 Le consommateur se bloque quand le tampon se vide.
 Principe :
 N étant la taille fixe du tampon
 Les deux processus se partagent une variable « count »
correspondant au nombre d’éléments dans le tampon
 Consommateur
 Si count = 0 ➔ le consommateur entre en sommeil
 Si count = N-1 ➔ le consommateur réveille le producteur
 Producteur
 Si count = N ➔ le producteur entre en sommeil
 Si count = N-1 ➔ le producteur réveille le consommateur

Pr. M. Alaoui Talibi 2018-2019 164


SOMMEIL ET ACTIVATION :
 Producteur/consommateur
 Problème de conditions de concurrence (qu’on risque
de rencontrer)

 Le consommateur lit la valeur de count qui est à 0 et avant de


se mettre en sommeil on lui retire la CPU.
 Le producteur insère un élément dans le tampon et
incrémente count qui passe à 1. Dans ce cas, il tente de
réveiller le consommateur qui ne s’est pas encore endormi.

 Cette tentative sera ignorée


 Le consommateur reprend la CPU et, croyant que la valeur de
count est 0, se met en sommeil ➔ il y restera à jamais.

Pr. M. Alaoui Talibi 2018-2019 165


LES SÉMAPHORES :

 Telleétait la situation, en 1965, lorsque E. W.


Dijkstra suggéra d’utiliser un nouveau type de
variable entière qui devait permettre de
décompter le nombre de wakeup enregistrés pour
un usage ultérieur.

 Danssa proposition, il appelait ce nouveau type de


variable un sémaphore.

Pr. M. Alaoui Talibi 2018-2019 166


LES SÉMAPHORES :
 Unsémaphore est une variable entière spéciale sur
laquelle on peut exécuter deux opérations : down
et up
 L’opération down teste si le sémaphore est supérieur à
0. Dans ce cas, elle le décrémente et le processus peut
entrer dans la section critique. Si le sémaphore est nul
alors, le processus entre en sommeil.
 L’opération up incrémente le sémaphore.
 Si un processus se trouve en sommeil sur ce sémaphore, alors
il sera réveillé.
 Les opérations de test, de modification du sémaphore
et de mise en sommeil sont indivisibles
➔ ceci permet d’éviter les conditions de concurrence.
Pr. M. Alaoui Talibi 2018-2019 167
LES SÉMAPHORES :
 Résolution du problème du producteur / consommateur
avec les sémaphores :
 Deux processus se partageant un tampon de taille fixe. Le
premier écrit dans le tampon et l’autre y consomme.

 Trois sémaphores sont utilisés dans la solution


 Full : pour compter le nombre d’emplacements pleins dans tampon

 Empty : le nombre d’emplacements vides

 Mutex : pour assurer l’exclusion mutuelle lors de l’accès au tampon


(afin de s’assurer que le producteur et le consommateur n’accèdent
pas simultanément au tampon).

Pr. M. Alaoui Talibi 2018-2019 168


LES SÉMAPHORES :

 Dans la figure suivante, le sémaphore mutex est


employé pour l’exclusion mutuelle. Il est conçu
afin de garantir qu’un seul processus à la fois
accédera en lecture et en écriture au tampon et
aux variables associées.

 Cetteexclusion mutuelle est indispensable pour


éviter tout désordre.

Pr. M. Alaoui Talibi 2018-2019 169


LES SÉMAPHORES :
 Solution du Producteur/consommateur

#define n 100 /* nb d’emplacements dans le tampon */


Typedef int semaphore ; /* les semaphores sont un type de variable int */
semaphore mutex = 1; /* contrôle l’acces à la section critique */
semaphore empty = n; /* compte les emplacements vides dans le tampon */
semaphore full = 0; /* compte les emplacements pleins */
void producer()
{
int item;
while (TRUE) /* TRUE est la constante 1 */
{
item = produce_item(); /* génère qlq chose à placer dans le tampon */
down(&empty); /* décrèmente le décompte des emplacements vides */
down(&mutex); /* entre en section critique */
insert_item(item); /* place un nouvel élément dans le tampon */
up(&mutex); /* quitte la section critique */
up(&full); /* incrémente le décompte des emplacements pleins */
}
}
Pr. M. Alaoui Talibi 2018-2019 170
LES SÉMAPHORES :
void consumer()
{
int item;
while (TRUE) /* boucle sans fin */
{
down(&full); /* décrémente le décompte des emplacements pleins */

down(&mutex); /* entre en section critique */


item = remove_item(); /* prélève un élément dans le tampon */
up(&mutex); /* quitte la section critique */
up(&empty); /* incrémente la décompte des emplacements vides */
consomme_item(item); /* fait quelque chose avec l’élément */
}
}

Pr. M. Alaoui Talibi 2018-2019 171


LES SÉMAPHORES :
 les sémaphores servent également à faire de la
synchronisation.

Les sémaphores full et empty sont nécessaires pour garantir


que certaines séquences d’événements se produisent ou ne
se produisent pas.

 Dans ce cas de figure, ils font en sorte que le producteur


cesse de s’exécuter lorsque le tampon est plein, et que le
consommateur cesse de s’exécuter quand il est vide.

 Il s’agit d’un usage différent de celui de l’exclusion


mutuelle.

Pr. M. Alaoui Talibi 2018-2019 172


LES MUTEX :
 Version simplifiée des sémaphores
 Prend en charge particulièrement l’exclusion mutuelle
 Un mutex peut prendre deux valeurs
 1 : déverrouillé
 0 : verrouillé
 Deux fonctions pour la gestion des mutex
 Mutex_lock : invoquée pour pouvoir entrer en section
critique
 Si le mutex est à 1 alors, il passe à 0 et le processus pourrait
entrer en section critique.
 Si le mutex est à 0 alors le processus se bloquerait jusqu’à ce que
le mutex sera débloqué par un autre processus (celui qui exécute
sa section critique)
 Mutex_unlock : remet le mutex à 1 à la fin de la section
critique, et réveille éventuellement un processus bloqué.
Pr. M. Alaoui Talibi 2018-2019 173
LES SÉMAPHORES : RISQUE D’ERREUR
 L’usage des sémaphores est relativement complexe et la moindre erreur peut avoir
des conséquences fatales sur le fonctionnement global des processus.
 Exemple : producteur/consommateur
 Que se passe-t-il si, par erreur, l’ordre des deux instructions down dans le producteur a été
inversé?

void producer() void consumer()


{ {
int item; int item;
while (TRUE) while (TRUE)
{ {
item = produce_item(); down(&full);
down(&mutex); down(&mutex);
down(&empty); item = remove_item();
insert_item(item); up(&mutex);
up(&mutex); up(&empty);
up(&full); consomme_item(item);
} }
} }

Pr. M. Alaoui Talibi 2018-2019 174


LES SÉMAPHORES : RISQUE
D’ERREUR
 Exemple : producteur/consommateur (suite)

 Si mutex = 1 et empty = 0 ➔ le producteur va pouvoir


réaliser l’opération down(mutex) ce qui signifie que
le mutex passe à 0. Par contre il se bloquera après
l’opération down(empty).
 Le consommateur sera bloqué sur down(mutex) parce
que le producteur n’a pas encore fait l’opération
up(mutex).
 Le consommateur ne pourra jamais incrémenter la
valeur de empty et le producteur ne pourra jamais
incrémenter la valeur de mutex
Pr. M. Alaoui Talibi 175
LES SÉMAPHORES : RISQUE D’ERREUR

 ➔ interblocage

 ➔ utilisation des primitives de synchronisation de haut


niveau fournies par un langage de programmation :

Moniteurs

Pr. M. Alaoui Talibi 2018-2019 176


LES SÉMAPHORES : RISQUE D’ERREUR
 Mettre à la disposition des utilisateurs un moyen de
définir et de spécifier une partie du code
nécessitant l’exclusion mutuelle sans se soucier de
la gestion «complexe » de sémaphores.
 Minimiser le risque d’erreur lors de la gestion des
sémaphores.

➔ utilisation des primitives de synchronisation de


haut niveau fournies par un langage de
programmation : Moniteurs.

Pr. M. Alaoui Talibi 2018-2019 177


LES MONITEURS :
 Un moniteur est un module spécial regroupant des
fonctions, des variables et des structures de
données.
 Les processus peuvent appeler les fonctions du
moniteur, mais ils ne peuvent pas accéder
directement à ses structures internes.
 A un instant donné, un seul processus peut être
actif dans le moniteur.
 Le programmeur n’a pas à se soucier de la
manière d’assurer l’exclusion mutuelle :
 Normalement c’est le compilateur qui s’en charge
Pr. M. Alaoui Talibi 2018-2019 178
ECHANGE DE MESSAGE :
 Comment synchroniser deux processus qui
s’exécutent sur deux ordinateurs distincts reliés
par internet ?
 Pas de mémoire partagée pour conserver un
sémaphore.
 Les moniteurs eux aussi se basent sur les sémaphores.
 Les autres techniques vues précédemment nécessitent
une zone mémoire partagée.

➔ L’échange de message

Pr. M. Alaoui Talibi 2018-2019 179


ECHANGE DE MESSAGE :
 Lesprocessus distants peuvent se synchroniser en
échangeant des messages avec deux primitives send
et receive (en général présentes sous forme d’appel
système).

 send(destination, &message)
 Envoie un message vers une destination
 receive(source, &message)
 Reçoit un message d’une source donnée.
 En l’absence du message, le récepteur peut se bloquer jusqu’à
ce que celui-ci arrive.

Pr. M. Alaoui Talibi 2018-2019 180


ECHANGE DE MESSAGE
 Problème de perte de messages
 Utiliser la technique d’acquittement et de duplication
de messages.
 Pour chaque message reçu, on doit envoyer un accusé de
réception.
 Si l’émetteur ne reçoit pas l’accusé de réception, il déduit
que son message est perdu ➔ il réémette le message
 Que se passe-t-il si le message est arrivé mais son
accusé de réception est perdu?
 Le message sera réémis et risque d’être pris en compte deux
fois.
 ➔ numéroter les messages
 Si un message arrive deux fois, le récepteur peut se rendre
compte qu’il s’agit d’un doublon et l’ignorer.

Pr. M. Alaoui Talibi 2018-2019 181


BARRIÈRES :
 Moyen de synchroniser un groupe de processus au
début de chaque « phase »

 Tous les processus doivent arriver à un seuil


(barrière) avant que chacun d’eux ne puisse
poursuivre son exécution
 Point de rencontre

 Attendre le dernier

Pr. M. Alaoui Talibi 2018-2019 182


BARRIÈRES :

A A A

B B B
barrière

barrière

barrière
C C C

D D D

temps
Les processus A, B, C et D doivent tous atteindre la
barrière avant que le groupe puisse poursuivre la suite
de l’exécution

Pr. M. Alaoui Talibi 2018-2019 183


Classification des
Architectures parallèles

Pr. M. Alaoui Talibi 184


OBJECTIFS :
 Dans ce chapitre, nous passons en revue les divers
concepts sous-jacents aux architectures parallèles.
 La distinction entre les architectures synchrones et
asynchrones conduit à une classification qui va :

✓ Des pipelines,
✓ Des processeurs vectoriels,
✓ Des machines SIMD,

✓ Aux machines MIMD à mémoire partagée et

✓ Aux réseaux de processeurs.


Pr. M. Alaoui Talibi 185
OBJECTIFS :

 Nous définissons deux modèles théoriques importants


pour les études de complexité algorithmique :

✓ Les PRAM
✓ Et les circuits booléens et arithmétique

 Nous présentons enfin, les mesures de performances


des ordinateurs parallèles.

Pr. M. Alaoui Talibi 186


DES CLASSES D’ORDINATEURS
PARALLÈLES :

1. Présentation informelle des ordinateurs parallèles:

La notion de parallélismes recouvre de nombreux


concepts, allant :

- de la manipulation des bits


à
- Un niveau plus grossier (découpage d’un programme
en procédures complexes indépendantes ).

Pr. M. Alaoui Talibi 187


DES CLASSES D’ORDINATEURS
PARALLÈLES :

 Plusieursclassifications ont été proposées dans la


littérature. La plus populaire celle de Flynn.

 Elles
est basée sur le type d’organisation des flots
de données et des flots d’instructions.

Pr. M. Alaoui Talibi 188


CLASSIFICATION DE FLYNN :

 Cependant, cette classification, ne permet pas de


tenir compte de beaucoup de facteurs tels que :

- Le mode de fonctionnement des processeurs,

- L’organisation de la mémoire ou encore

- La granularité des processeurs (taille des éléments


logiques de base des processeurs).

Pr. M. Alaoui Talibi 189


CLASSIFICATION DE FLYNN :
 On peut dégager trois grandes classes de machines
parallèles :

✓ Les machines généralistes à mémoire partagée.

✓ Les réseaux de processeurs asynchrones à mémoire


Distribuée.

✓ Les machines distribuées synchrones massivement


parallèles (machines généralistes ou spécialisées).

Pr. M. Alaoui Talibi 190


2. LES PRINCIPES FORMES DE PARALLÉLISME :

Problèmes :

 L’augmentation du nombre des processeurs modifie


énormément la structure de base de l’ordinateur.

 Les problèmes d’accès mémoire deviennent cruciaux


pour pouvoir acheminer des données au rythme du
traitement des processeurs.

 De même, les problèmes de communication entre


processeurs sont importants.

Pr. M. Alaoui Talibi 191


2. LES PRINCIPES FORMES DE PARALLÉLISME :
 Denombreuses solutions ont été proposées à ces
problèmes et plusieurs architectures ont vu le jour.

 La plus simple, et la plus utilisée est celle de Flynn.

 Celle-ci,
a pour critère de sélection :
le mode de contrôle des suites d’opérations
élémentaires effectuées par les différents processeurs.

 Leprocessus essentiel dans un ordinateur est


l’exécution d’une suite d’instructions sur un
ensemble de données. Pr. M. Alaoui Talibi 192
2. LES PRINCIPES FORMES DE PARALLÉLISME :

 En général, les ordinateurs peuvent être classifiées


selon la multiplicité des flots d’instructions et de
données disponibles matériellement.

 En conservant les initiales anglaises consacrées par


l’usage, on obtient essentiellement les architectures
suivantes :
- SIMD : un seul flot d’instructions, plusieurs flots de
données.(single instruction multiple data)
- SPMD : chaque processeur dispose du même
programme.(single program multiple data)
Pr. M. Alaoui Talibi 193
2. LES PRINCIPES FORMES DE PARALLÉLISME :
 MISD : plusieurs instructions successives traitent la
même donnée.
 MIMD : plusieurs flots d’instructions et de données.

 Un flot d’instructions est une suite d’instructions


issues d’une partie contrôle en direction d’un ou
plusieurs processeurs.

 Un flot de données est une suite de données venant


d’une zone mémoire en direction d’un processeur ou
venant d’un processeur en direction d’une zone
mémoire.
Pr. M. Alaoui Talibi 194
ARCHITECTURES SYNCHRONES :
 Principe de l’ordinateur séquentiel :
Les instructions sont exécutées séquentiellement
mais peuvent être pipelinées.

Figure.
Architecture
synchrone

Pr. M. Alaoui Talibi 195


 En microarchitecture,

Un pipeline (ou chaîne de traitement1),


est l'élément d'un processeur dans lequel
l'exécution des instructions est découpée
en plusieurs étapes.

Pr. M. Alaoui Talibi 196


ARCHITECTURES SYNCHRONES :
Architectures pipeline et vectorielle :
Le principe des architectures pipelines est le suivant :

 Ondivise l’opération à effectuer en étapes de


durées égales qui s’exécutent successivement.

 Lesentrées d’une étape sont constituées par les


sorties de l’étape précédente.

 Lepipeline est une unité matérielle qui reproduit


cette division.
Pr. M. Alaoui Talibi 197
ARCHITECTURES SYNCHRONES :
 Ilest donc composé d’étages séparés par des
registres nécessaires au stockage des données
intermédiaires.

 Au sens de la classification de Flynn, ces architectures


révèlent du mode MISD.

 Eneffet, une même donnée est traitée par un flot


multiple d’instructions élémentaires successives.

Pr. M. Alaoui Talibi 198


ARCHITECTURES SYNCHRONES :
Architecture vectoriel :
 Un vecteur est un ensemble ordonnée de n éléments.

 Chaque élément est un scalaire, nombre réel


flottant, entier, booléen ou caractère.

 Un processeur vectoriel est une unité permettant


de traiter des vecteurs.

 Ilest constitué de registres de stockage et d’une


ou plusieurs unités pipelines.

Pr. M. Alaoui Talibi 199


ARCHITECTURES SYNCHRONES :
Architecture SIMD :
 Plusieurs unités de traitement sont supervisées par
la même unité de contrôle.

 Toutes les unités de traitement reçoivent la même


instruction ( ou le même programme, auquel cas
on parle d’une structure SPMD ) diffusée par
l’unité de contrôle,

Mais opèrent sur des ensembles de données


distincts, provenant de flots de données distincts.
Pr. M. Alaoui Talibi 200
ARCHITECTURES SYNCHRONES :

Figure : Structure SIMD

Pr. M. Alaoui Talibi 201


ARCHITECTURES SYNCHRONES :
 Chaque unité de traitement exécutant la même
instruction au même instant, on obtient un
fonctionnement synchrone des processeurs.

 la mémoire partagée peut être subdivisée en


plusieurs modules.

 Dans ce cas, l’accès des unités de traitement aux


différents modules se fait par un réseau
d’interconnexion que nous étudierons après.

Pr. M. Alaoui Talibi 202


ARCHITECTURES SYNCHRONES :

 Un calculateur SIMD peut être considéré comme un


monoprocesseur exécutant des instructions sur des
tranches de plusieurs éléments.

 Ilest donc particulièrement bien adapté aux


traitements d’opérations vectorielles.

Pr. M. Alaoui Talibi 203


ARCHITECTURES SYNCHRONES :
 Par exemple, les ordinateurs :

- ILLIAC IV
- BSP
- STARAN
- MPP
- Et plus récemment les DAP de AMT

Par contre, OPSILA ou les hypercubes FPS de la série T sont


des machines SIMD/SPMD.

 Notons que la plupart des machines actuelles MIMD peuvent


s’utiliser en mode SPMD.

Pr. M. Alaoui Talibi 204


ARCHITECTURES ASYNCHRONES MIMD :
 Parallélisme partagé :

Les premiers ordinateurs parallèles à avoir


effectivement connu un succès industriel sont les
machines à mémoire partagée.

Considérons p processeurs vectoriels reliés à une grande


Mémoire commune.

Le fonctionnement des processeurs s’effectue en mode


MIMD.
Pr. M. Alaoui Talibi 205
ARCHITECTURES ASYNCHRONES MIMD :
 Càdchaque processeur peut évoluer indépendamment
des autres.

 Leséchanges d’informations entre les processeurs se


font par l’intermédiaire de la mémoire.

 Lesmachines appartenant à cette classe possèdent


un nombre relativement faible des processeurs (une
dizaine), mais chacun assez puissant.

 Ladiminution des temps d’exécution n’est pas le seul


but que les utilisateurs (constructeurs) recherchent.
Pr. M. Alaoui Talibi 206
ARCHITECTURES ASYNCHRONES MIMD :

 Ils voudraient aussi disposer de plus en plus de


mémoire pour pouvoir traiter des problèmes
toujours plus grands.

 Or, l’accès à des mémoires de grandes dimensions


est lent.

 Comme la vitesse de base des unités de traitement


augmente sans cesse, il faut organiser les mémoires
de telle sorte que l’accès soit rapide.

Pr. M. Alaoui Talibi 207


ARCHITECTURES ASYNCHRONES MIMD :

Figure. Structure MIMD


Pr. M. Alaoui Talibi 208
ARCHITECTURES ASYNCHRONES MIMD :
 La grande mémoire est divisée en modules distincts
possédant chacun son propre canal d’entrées-sorties
(les bancs mémoire).

 Ces bancs sont reliées aux processeurs par


l’intermédiaire de bus ou d’un réseau
d’interconnexion.

 la différence entre le SIMD et le MIMD, est que pour


le dernier, chaque processeur possède sa propre
unité de contrôle.
Pr. M. Alaoui Talibi 209
ARCHITECTURES ASYNCHRONES MIMD :

 Lesprocesseurs ont donc un fonctionnement


indépendant : en particulier asynchrone, et
exécutant des programmes différents.

Pr. M. Alaoui Talibi 210


ARCHITECTURES ASYNCHRONES MIMD :

 Architectures MIMD distribuées :

Les difficultés d’accès à la mémoire limitent le


nombre de processeurs :

au-delà de quelques dizaines


de processeurs, les performances du réseau
d’interconnexion se dégradent.

Pr. M. Alaoui Talibi 211


ARCHITECTURES ASYNCHRONES MIMD :
 Chaque processeur doit disposer d’une mémoire
locale à accès rapide et n’est connecté qu’a un
certain nombre de processeurs voisins.

 nous avons deux modèles :


1.
✓ Les processeurs travaillent en partageant des
données de la mémoire commune.
✓ Chaque processeur lit en mémoire les données dont
il a besoin, effectue son traitement, puis écris les
résultats en mémoire.
Pr. M. Alaoui Talibi 212
ARCHITECTURES ASYNCHRONES MIMD :
2.
✓ Les processeurs travaillent en échangeant des
messages.

✓ Chaque processeur lit sur un ou plusieurs canaux de


communications les données dont il a besoin en
provenance d’autres processeurs, effectue son
traitement, puis transfère les résultats en direction
des processeurs qui les demandent.

Pr. M. Alaoui Talibi 213


ARCHITECTURES À FLOTS DE DONNÉES
(DATA-FLOW):
 Cherchent à exploiter au maximum le parallélisme
d’un algorithme en s’affranchissant des contraintes
liées à l’ordre d’exécution des instructions.

 Le principe de base est d’autoriser l’exécution


d’une instruction dés que ses opérandes sont
disponibles.

 Le début d’une instruction ne dépend alors que de


la disponibilité des données et non pas de sa
position dans le programme.
Pr. M. Alaoui Talibi 214
ARCHITECTURES À FLOTS DE DONNÉES
(DATA-FLOW):
 Explication
: L’exécution du programme est liée
aux contraintes de dépendance entre données.

Pr. M. Alaoui Talibi 215


ARCHITECTURES À FLOTS DE DONNÉES
(DATA-FLOW):
 Elle comporte :
✓ Une unité mémoire contenant les opérandes et les
instructions non actives,

✓ Une unité de recherche des instructions actives

✓ Une file des instructions actives en attente d’exécution.

✓ Une unité de traitement avec plusieurs processeurs,

✓ Une unité de mise à jour dont le rôle est d’affecter


leurs valeurs aux opérandes à l’issue du traitement.
Pr. M. Alaoui Talibi 216
COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :

Pr. M. Alaoui Talibi 217


INTRODUCTION AUX MODÈLES :
 Présentation générale :

L’étude de la complexité algorithmique parallèle nécessite


que soit défini un modèle de calcul, que nous appelons un
modèle de machines, pour exécuter des algorithmes.

 Cependant, de nombreux modèles existent pour les


ordinateurs parallèles.

 Suivant le modèle utilisé, Il existe des notions différentes


de complexité algorithmique.

Pr. M. Alaoui Talibi 218


INTRODUCTION AUX MODÈLES :

 Dans ce paragraphe, nous allons étudier deux


d’entre eux :

✓ les PRAM, Parallel Random Access Machines,

✓ Et les circuits booléens et arithmétiques.

Pr. M. Alaoui Talibi 219


INTRODUCTION AUX MODÈLES :
 Thèse du calcul parallèle :

Se fonde sur l’idée intuitive d’une relation entre le


temps de calcul des machines parallèles et l’espace
de calcul (taille de la mémoire) des machines
séquentielles.

Tout problème qui peut être résolu sur un ordinateur


séquentiel (raisonnable) en utilisant un espace de
taille mémoire (polynomiale) peut être résolu en temps
Polynomial sur un ordinateur parallèle (raisonnable)
et vice versa.
Pr. M. Alaoui Talibi 220
INTRODUCTION AUX MODÈLES :
Définir des ordinateurs raisonnables, aussi bien séquentiel que
parallèle n‘est pas une tache simple.

Un consensus s’est établi entre théoriciens qui repose sur la


« thèse de l’invariance ».

 Thèse d’invariance :

Des machines raisonnables peuvent se simuler entre elles avec


au plus un accroissement polynomial en temps et une
multiplication constante de l’espace.

Pr. M. Alaoui Talibi 221


INTRODUCTION AUX MODÈLES :

 Le modèle PRAM :

Un Parallel Random Access Machine PRAM est un


ensemble de processeurs séquentiels indépendants,
des RAM, qui possèdent donc chacun une mémoire
privée (ou locale) et qui communiquent entre eux en
utilisant une mémoire globale qu’ils se partagent.

Pr. M. Alaoui Talibi 222


INTRODUCTION AUX MODÈLES :
 Opérations fondamentales :

Considérons une PRAM composée de :

p processeurs numérotées de P0 à Pp-1


m positions mémoires M0 à Mm-1

Chaque processeur peut effectuer des opérations


atomiques, en une unité de temps :
Lire(Mi)
Ecrire(Mi)
Calculer(f)
Pr. M. Alaoui Talibi 223
INTRODUCTION AUX MODÈLES :
 Toutes
ces opérations atomiques s’effectuent de
manière synchrone,

 Autrement dit, au même instant, tous les processeurs


lisent, écrivent et calculent.

 Extensions :

Le modèle PRAM doit être modifié pour prendre en


compte les accès mémoire dans le cas d’une mémoire
distribuée.
Pr. M. Alaoui Talibi 224
INTRODUCTION AUX MODÈLES :
 Définition:
Une DRAM ( Distributed RAM ) est un ensemble de p
processeurs Pi, de p zones mémoires Mi et d’une
famille de couples X=(i,j).

Nous noterons Xi l’ensemble des couples (i,.).

Le processeur Pi ne peut accéder qu’aux zones


mémoire Mj quel que soit j appartenant à Xi.

X est le réseau d’interconnexion de la DRAM.


Pr. M. Alaoui Talibi 225
INTRODUCTION AUX MODÈLES :

 Pour lire une donnée située dans une case mémoire


à laquelle il n’est pas directement connecté :

Un processeur doit donc obtenir l’aide d’autres


processeurs qui, en lisant et en écrivant, déplaceront
la donnée de la case mémoire initiale à une case
accessible par le processeur intéressé.

Pr. M. Alaoui Talibi 226


PERFORMANCES :
 Le facteur d’accélération :

Considérons un algorithme qui s’exécute sur un


ordinateur parallèle comportant p processeurs
(identiques) en un temps tp, et soit t1 son temps
d’exécution séquentiel (sur un ordinateur avec un
seul processeur).
On définit le facteur d’accélération par le rapport :

Sp = t1/tp

Théorème : quel que soit p, 1 ≤ Sp ≤ p (A démontrer).


Pr. M. Alaoui Talibi 227
PERFORMANCES :
 Limitations du facteur d’accélération :

Divers auteurs ont essayé de préciser les bornes du


facteur d’accélération suivant l’architecture (à
chercher):

✓ Loi d’Amdahl
✓ Loi de Minsky
✓ Table de Stone

Pr. M. Alaoui Talibi 228


COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :

 Dansce chapitre, nous introduisons les principales


notions de complexité parallèle.

 Lemodèle utilisé est principalement le modèle PRAM


et ses dérivées.

 Nousétudions la complexité parallèle de plusieurs


algorithmes de base.

Pr. M. Alaoui Talibi 229


COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :
 Description des hypothèses :
✓ La structure de l’ordinateur est de type SIMD ou
MIMD avec une mémoire commune partagée.

✓ Nous supposerons que notre modèle peut admettre


un nombre illimité de processeurs.

✓ L’unité de base est le temps d’exécution d’une


opération arithmétique

✓ Nous négligeons les temps de communication entre


la mémoire et les processeurs.
Pr. M. Alaoui Talibi 230
COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :
 Objectifs de l’étude de la complexité parallèle :

✓ Il s’agira de trouver dans l’algorithme les opérations


susceptibles d’être exécutées simultanément.

✓ Considérons un problème donné : calcul du produit


scalaire de deux vecteurs de taille n.

✓ Une question classique : chercher la complexité


séquentielle de ce problème.

✓ Càd le temps de calcul minimum pour résoudre le


problème.
Pr. M. Alaoui Talibi 231
COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :

 On procède généralement en deux étapes :

✓ Recherche d’une borne inferieur.

✓ Ensuite, construction d’un algorithme séquentiel


dont le temps d’exécution est égal à cette borne.

Un tel algorithme est dit optimal

Pr. M. Alaoui Talibi 232


COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :

 Lesalgorithmes que nous étudierons s’exécutant


en un nombre fini d’opérations,

 2n-1 (nb d’opérations) pour le cas du produit scalaire,

 Cecirevient à supposer que le nombre de processeurs


est égal à ce nombre d’opérations.

Pr. M. Alaoui Talibi 233


COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :
 Evaluation d’une expression arithmétique :

Dans une première partie, nous étudions les relations


entre algorithmes d’évaluation d’une expression et
arbres binaires étiquetés.

Définition :
1. Une expression de taille n est un problème
possédant n données (variables ou atomes) et
fournissant un seul résultat, et dont toutes les
opérations sont binaires.
Pr. M. Alaoui Talibi 234
COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :
 L’expression est simple si chacune des variables
n’est utilisée qu’une seule fois comme opérande.

 E est une expression simple si E satisfait une des


conditions suivantes :

1. E = xi où xi est une variable


2. E = o G où G est une expression simple et où o
appartient {+,-}.
3. E = G o D où G et D sont des expressions simples
portant sur des ensembles de variables disjoints
et où o appartient à {+,-,*,/}.
Exemple.
Pr. M. Alaoui Talibi 235
COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :
 Nousdéfinissons maintenant les arbres binaires
étiquetés.

 Ladéfinition dépend d’un entier p qui représente


le nombre de processeurs.

 L’arbre
étiqueté conduit à un algorithme d’évaluation
avec p processeurs : chaque nœud représente une
opération et l’étiquette du nœud la date d’exécution
de cette opération.

Pr. M. Alaoui Talibi 236


COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :
 Définition :

Soit p un entier positif. Nous appelons A(p) l’ensemble des


arbres binaires étiquetés construits de la manière suivante :

1. l’arbre avec un seul nœud étiqueté 0 appartient à A(p) et


a une profondeur égale à 0.

2. Pour d≥0, un élément de A(p) de profondeur d+1 est


obtenu à partir d’un élément de A(p) de profondeur d en
ajoutant 1 à toutes les étiquettes et en remplaçant au plus
p de ses feuilles par l’arbre binaire à trois sommets dont
les feuilles sont étiquetées 0 et la racine 1.

Pr. M. Alaoui Talibi 237


COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :

 L’arbrebinaire à trois sommets dont les feuilles


sont étiquetées 0 et la racine 1 est appelé arbre de
base.

Exemple : prenons p=3;

Pr. M. Alaoui Talibi 238


COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :

 Relationsentre évaluation des expressions et arbres


binaires étiquetés :

Lemme :
1. Tout algorithme parallèle d’évaluation d’une
expression de taille n avec p processeurs peut être
représenté par un élément de A(p) admettant au
moins n feuilles.

Pr. M. Alaoui Talibi 239


COMPLEXITÉ DES ALGORITHMES
PARALLÈLES :

2. Toute expression simple de taille n peut être


représentée par un élément de A(p) possédant n feuilles.
Cet arbre détermine un algorithme parallèle d’évaluation
de l’expression avec p processeurs.

 Pour tout arbre de A(p), de profondeur d et possédant n


feuilles, il existe une expression simple de taille n et un
algorithme parallèle d’évaluation de cette expression,
représenté par cet arbre.
Exemple1
Exemple2

Pr. M. Alaoui Talibi 240


Stratégies de conception
d'algorithmes parallèles :

Pr. M. Alaoui Talibi 241


LA PROGRAMMATION PARALLÈLE
 Le but est de :
▪ résoudre plus rapidement un problème donné ;
▪ résoudre un problème plus gros pour une même
durée de calcul.

Elle concerne :

▪ le calcul scientifique en cherchant à modéliser


et à simuler des phénomènes naturels, et les grands
défis :

✓ Réchauffement climatique, un nouveau médicament...


Pr. M. Alaoui Talibi 242
LA PROGRAMMATION PARALLÈLE
✓ La cosmologie, l’imagerie médicale, la prédiction
des tremblements de terre, le climat.

Ces programmes sont exécutés sur des architectures


parallèles avec souvent autant de processus que de
processeurs.

Pr. M. Alaoui Talibi 243


LA PROGRAMMATION PARALLÈLE
 On distingue deux grandes classes de programmes
parallèle :

▪ Parallélisme de données : chaque processeur


réalise un même traitement sur une partie des
données ;

▪ Parallélisme de contrôle : chaque processeur


réalise un traitement différent.

Pr. M. Alaoui Talibi 244


CONCEPTION DES APPLICATIONS
CONCURRENTES :

 Les différents processus d'une même application


ont besoin :

▪ d'interagir entre eux,


▪ de communiquer,
▪ de se synchroniser,

et suivant leur localisation entre les différents


processeurs :

Pr. M. Alaoui Talibi 245


CONCEPTION DES APPLICATIONS
CONCURRENTES :

▪ En multi-programmation : utilisation de variable


partagée ;

▪ En distribué : échange de message

▪ En parallèle : soit l'un, soit l'autre, soit les deux en


fonction du matériel utilisé.

Pr. M. Alaoui Talibi 246


CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Parallélisme itératif :

▪ Il est utilisé lorsque le programme est décomposé en


différents processus souvent identiques,

▪ Chacun contenant une ou plusieurs boucles.

▪ Ces processus travaillent ensemble pour résoudre un


seul problème.

▪ Ils communiquent et se synchronisent par variables


partagées et envoi de messages.

Essentiellement : du calcul scientifique exécuté sur


plusieurs processeurs.
Pr. M. Alaoui Talibi 247
CONCEPTION DES APPLICATIONS
CONCURRENTES :

 Parallélisme de récursion :

Il peut être utilisé lorsque il existe une ou plusieurs


procédures récursives et que ces appels sont
indépendants entre eux.

Pr. M. Alaoui Talibi 248


CONCEPTION DES APPLICATIONS
CONCURRENTES :

La récursion est utilisée pour résoudre des problèmes


combinatoires : tri, ordonnancement (problème du
voyageur de commerce), jeu (échec).

Pr. M. Alaoui Talibi 249


CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Producteur/Consommateur :

Ce sont des processus communiquants qui sont


souvent organisés en pipeline à travers lequel les
données circulent.

Chaque processus est un filtre qui utilise la sortie


de son prédecesseur et produit la sortie pour son
successeur.

Cette forme de pipeline est utilisée au niveau de l'OS


pour un shell Unix, par exemple.
Pr. M. Alaoui Talibi 250
CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Client/Serveur : c'est le modèle dominant qui
s'applique du réseau local au réseau global.

Un client fait appel à un service et attend la réponse.

Un serveur attend une requête et travaille à la réception.

Un serveur peut être implémenté par :


➢ un seul processus gérant un client à la fois,
➢ ou bien comme un multi-programme (plusieurs
processus) pour traiter simultanément les requêtes de
plusieurs clients.
Pr. M. Alaoui Talibi 251
CONCEPTION DES APPLICATIONS
CONCURRENTES :

Lorsque client et serveur sont sur des machines


différentes :

il est nécessaire d'utiliser la notion de


rendez-vous et d'appel à distance.

Ce schéma peut être facilement automatisé, mais il


faut faire attention à son efficacité.

Pr. M. Alaoui Talibi 252


CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Modèle Map/Reduce :

Pr. M. Alaoui Talibi 253


CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Modèle Map/Reduce :

✓ Est un paradigme dédié pour exécuter un problème


large et complexe d’une manière distribuée.

✓ Les programmes adoptant ce modèle sont


automatiquement parallélisés et exécutés sur
des clusters (grappes) d’ordinateurs.
CONCEPTION DES APPLICATIONS
CONCURRENTES :
Fonctionnement de MapReduce :

Un programme MapReduce se compose des trois parties


suivantes :
 Le driver, qui s’exécute sur une machine client,
est responsable :
✓ d’initialiserle job
✓ puis de le soumettre pour exécution.
 Le mapper est responsable :
✓ de lire les données stockées sur disque
✓ et les traiter.
 Le reducer est responsable de :
✓ consolider les résultats issus du mapper
✓ puis de les écrire sur disque.
Pr. M. Alaoui Talibi 255
CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Unebonne compréhension de MapReduce implique
la maitrise du fonctionnement de Hadoop et HDFS.

Pour cela, ces deux notions sont obligatoires pour


mieux appréhender la suite.

 Fonctionnement de Hadoop
 Fonctionnement de HDFS

Pr. M. Alaoui Talibi 256


CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Hadoop :

➢ est une plateforme « framework » open source.

➢ destiné aux traitements distribués des données


massives de l’ordre de plusieurs pétaoctets.

➢ Elle permet de faciliter la création d’applications


distribuées.

➢ Est un environnement Big Data typique.


CONCEPTION DES APPLICATIONS
CONCURRENTES :
 L’écosystème Hadoop est un :

➢ produit de la fondation Apache basé pour sa


création sur le langage java.

➢ Hadoop se positionne aujourd’hui avec plus de


42000 nœuds chez Yahoo.

➢ Plusieurs fondations mondiales utilisent Hadoop tel


que : Ebay, Facebook, Amazon, Google, Microsoft,
LinkedIn, Twitter…
CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Avantages de Hadoop :

➢ Parallélisme des données:


un même traitement et calcul peut être effectué
sur toutes les données.

➢ Performance :
Hadoop délivre à travers le critère de parallélisme
un support de traitement de grands volumes de
données et d’énormes data sets.
CONCEPTION DES APPLICATIONS
CONCURRENTES :

 Avantages de Hadoop :

➢ Économie : les coûts lors de l’utilisation de


Hadoop sont mieux contrôlés grâce à l’utilisation
de matériel de calcul de type standard.
CONCEPTION DES APPLICATIONS
CONCURRENTES :
 Le fonctionnement de Hadoop repose sur :

➢ HDFS (Hadoop Distributed File System) :

▪ Est un système de fichiers distribués de Hadoop


▪ Destiné pour le stockage distribué des données.
▪ Ce composant est distribué,
▪ tolérant aux pannes,
▪ portable,
▪ et également extensible.
CONCEPTION DES APPLICATIONS
CONCURRENTES :
 L’interet de MapReduce est de simplifier la vie du
programmeur, en lui masquant le fonctionnement
interne de Hadoop (parallélisation , tolérance aux
pannes,…etc).

 Ainsi, le modèle de programmation permet au


développeur de ne s’intéresser qu’à la partie
algorithmique.

 Il transmet alors son programme MapReduce développé


dans un langage de programmation au framework
Hadoop pour l’exécution.

Pr. M. Alaoui Talibi 262

Vous aimerez peut-être aussi