26
Systèmes Distribués Communication de groupes Protocoles de diffusion Appels de procédures Mémoire Distribuée- Modèles de Cohérence Boulekhmir Abdessamed Systèmes Distribués

Systemes Distribués

Embed Size (px)

Citation preview

Page 1: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

ist

rib

s

Page 2: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

2 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

T a b l e d e s m a t i è r e s :

Introduction

Partie I : Communication de groupe

Partie II : Protocoles de diffusion

Partie III : Appel de procédures

Partie IV : Mémoire partagée

Conclusion

Page 3: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

3 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Introduction .

Qu’est ce qu’un système distribué ?

Un système informatique distribué est une collection de postes ou calculateurs

autonomes qui sont connectés à l'aide d'un réseau de communication. Chaque poste

exécute des composantes, par exemple des séquences de calculs, issues du découpage d'un

projet de calcul global, et utilise un intergiciel, qui s'occupe d'activer les composantes et de

coordonner leurs activités de telle sorte qu'un utilisateur perçoive le système comme un

unique système intégré.

Une propriété importante des systèmes distribués est que la distribution est

généralement cachée pour l’utilisateur et les programmeurs de l’application. Il préfère voir

l'ensemble comme un seul et unique système et ainsi cacher la complexité de la distribution

le plus possible et augmenter la transparence du système distribué. Cela permet de

développer le plus possible les applications de la même façon que les systèmes centralisés.

Un système distribué est généralement séparable en plusieurs composantes

entièrement autonomes. Il n’existe pas de composante maître qui gère les autres et chacune

est donc responsable de son propre fonctionnement. Cela permet, entre autres, d’avoir une

hétérogénéité dans la technologie utilisée pour chaque composante, ils peuvent être écrits

dans différents langages de programmation (Java, Cobol, C++, etc.) et s'exécuter sur

différents systèmes d'exploitation (Mac OS X, Linux, Windows, etc.). L’autonomie des

composantes fait que les systèmes sont exécutés simultanément (programmation

concurrente). De plus, contrairement au système centralisé, les systèmes distribués

possèdent plusieurs points de défaillances (problème de composantes, réseau, trafics, etc.).

Page 4: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

4 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

I - C o m m u n i c a t i o n d e g r o u p e s :

I.1- Qu’est ce qu’un groupe :

Un groupe est un ensemble de processus formant une entité unique. Un message

envoyé à ce groupe sera reçu par tous les membres du groupe au même moment.

Un groupe est un ensemble de processus qui travaille ensemble.

Un groupe comporte des processus qui agissent ensemble pour les besoins du

système ou de l'utilisateur.

I.2- Communication inter-groupe :

I.1.1- Communication one-to-many:

Est une méthode de diffusion de l'information d'un émetteur (source unique) vers un

groupe (plusieurs supports/medias). On l’appelle aussi diffusion multipoint, multicast

ou bien encore diffusion de groupe.

Ainsi c’est un moyen de d’envoyer un message à plusieurs destinataires, sans pour

autant surcharger le réseau. Dans un réseau qui supporte le multicast, le message

envoyé à plusieurs membres du réseau n’est envoyé qu’une seule fois. Cela est

beaucoup moins consommateur en bande passante. Cette méthode est employée

dans le domaine de la vidéo en demande, qui nécessite beaucoup de bande passante.

Les utilisateurs s’inscrivent à un groupe et reçoivent le flux en multicast.

I.1.2- Communication many-to-one:

Many-to-one est une méthode de diffusion de l'information de plusieurs émetteurs

vers une seule destination.

Page 5: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

5 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

On distingue deux types de réception :

Réception sélective : le serveur reçoit le message envoyé par un client bien

précis.

Réception non sélective : le serveur ne peut sélectionnait l’émetteur des

messages.

I.1.3- Communication many-to-many:

Dans ce type de communication, on a plusieurs sources qui communiquent avec

plusieurs destinations.

I I - L e s p r o t o c o l e s d e d i f f u s i o n :

I.1- La synchronisation dans les systèmes répartis :

Nous avons vu comment les processus communiquent dans un système réparti.

La communication entre processus est importante, mais il faut voir aussi :

Comment ils coopèrent.

Comment ils se synchronisent les uns les autres.

Page 6: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

6 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Dans un système centralisé, les problèmes de synchronisation sont résolus par des

sémaphores :

Régions critiques.

Exclusion mutuelle.

Dans les systèmes répartis, le fait qu’il n’y ait pas de mémoire partagé, les sémaphores

(variables partagées) ne peuvent pas exister.

I.1.2- Ordre stricte:

L’ordre de réception des messages doit être le même que celui d’émission.

! Problème de synchronisation des horloges.

La solution serait d’avoir une estampie.

Si on suppose que les horloges des processus sont synchronisées il suffit d’inclure la

date d’émission comme identifiant.

I.1.2- Ordre consistant:

Permet la réception des messages qui assurent la consistance des opérations.

Remarque : L’ordre absolu est un ordre consistant + l’ordre de réception doit être le

même que celui de l’émission.

15h10

16h01

Page 7: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

7 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Afin d’avoir cet ordre deux solutions sont proposées :

Solution 1 : many-to-one puis one-to-many (Centraliser)

Solution 2 : Protocole ABCAST (Décentraliser)

L'algorithme ABCAST décrit ici a été proposé par Birman (1987) pour permettre une

délivrance uniforme sur tous les sites (c'est-à-dire dans le même ordre sur tous les sites)

de tous les messages envoyés à un groupe (ouvert ou fermé). Il utilise un mécanisme

d'estampillage scalaire. Il s'agit d'un protocole de validation à deux phases.

Chaque membre du groupe dispose d'une horloge logique et gère une file d'attente des

messages diffusés au groupe et qu'il a reçus et sont en attente pour être délivrés.

1- L’émetteur affecte un numéro temporaire de séquence a son message qui est

supérieur a tout les numéros des messages précédents .

2- Ce Message va être reçu par un membre du groupe, Chaque membre du groupe

va proposer un numéro de séquence au message.

Fmax : Le Nombre de séquence max attribué dans le groupe

Pmax : C’est le nombre de séquence max attribué par le membre récepteur

I : Numéro d’identification du membre récepteur.

N : Taille du groupe

Max (Fmax, Pmax) + 1 + i/N

Le message est renvoyé a l’émetteur.

3- Quand l’émetteur reçoit les numéros de séquence proposés de touts les

membres, il sélectionne le plus grand et le retransmet dans un « Commit

Message ».

4- A la réception du commit message chaque membre attribue ce numéro au

message.

Donner des numéros de

séquences aux messages

Page 8: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

8 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Les messages avec ce « Commit Sequence Number » sont ordonnés dans une file et

délivrés au processus destinataire.

I.1.2- Ordre Causal:

Un protocole d’ordre causal est un protocole qui assure que les messages reçus sur un même

site sont délivrés en respectant les dépendances causales entre les événements d’émission

de ces messages.

Algorithme CBCAST :

Problème

Il s'agit ici de fournir un protocole de diffusion de messages à un groupe garantissant une délivrance des messages sur les différents dites respectant la relation de causalité entre les différentes diffusions. Dans l'exemple suivant, on considère un groupe contenant 4 composants et un ensemble de 4 diffusions de messages. Si les messages sont délivrés dès leur arrivée sur les sites, la relation de causalité entre les différentes diffusions est violée :

Les dépendances causales entre les différentes diffusions sont les suivantes :

la diffusion de m2 par le second site est postérieure à la réception de m1 par ce site (et donc la diffusion de m1): une délivrance causale suppose donc que m2 soit délivré après m1 sur tous les sites;

la diffusion de m4 par le troisième site suit la réception de m2 par ce site: une délivrance causale impose donc que m4 soit délivré après m2 sur tous les sites. Par ailleurs cette même diffusion suit celle de m3 par ce même site et donc, la délivrance de m3 devra donc précéder celle de m4.

Page 9: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

9 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Une diffusion causale suppose donc que sur chaque site les message soient délivrés dans un ordre correspondant à l'un des suivants (m3 peut être délivré dans l'une quelconque des positions vertes): m3 m1 m3 m2 m3 m4 L'ordre d'arrivée sur les différents sites est quant à lui le suivant (les messages en rouge violent l'ordre imposé pour une délivrance causale :

sur S1 : m1 m3 m2 m4 sur S2 : m1 m2 m4 m3 (m4 arrive trop tôt); sur S3 : m3 m1 m2 m4 sur S4 : m3 m4 m2 m1: d'une part m4 arrive trop tôt par rapport à m1 et m2 et,

d'autre part, m2 arrive trop tôt par rapport à m1.On peut noter au passage que le canal de communication entre S3 et S2 ne respecte pas la propriété FIFO (le message m4 y double le message m3).

Algorithme CBCAST

Dans l'algorithme décrit maintenant utilisable pour des diffusions dans des groupes fermés, une estampille vectorielle (de taille n égale au nombre de membres du groupe) est utilisée pour dater les diffusions :

A la réception d'un message, il est possible en comparant la valeur de l'horloge locale et l'estampille attribuée par le message de savoir si le site récepteur a reçu tous les messages qu'il est censé avoir reçus: pour que le message puisse être délivré, il faut que

a. l'ordre FIFO soit respecté sur le canal de l'émetteur; b. le site récepteur a reçu des autres sites autant de messages que le site émetteur en

avait reçus lors de la diffusion du message.

Page 10: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

10 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

En d'autres termes, un message est délivré si et seulement si :

La délivrance d'un message qui, lors de son arrivée sur un site, ne satisfait pas au moins l'une des conditions précédentes doit être différée sur ce site jusqu'à ce que les deux conditions soient effectivement satisfaites. La mise à jour de l'horloge locale est réalisée lors de la délivrance du message.

Exemple :

La figure suivante illustre l'utilisation de l'algorithme pour détecter les arrivées prématurées de messages et en différer la délivrance :

les anomalies y sont repérées en rouge (point A, B et C) ainsi que les valeurs courantes des horloges des sites qui y sont comparées avec les valeurs des estampilles (vertes) des messages arrivant correspondant aux horloges des sites émetteurs;

pour les arrivées de messages pouvant donner lieu à une délivrance du message, les valeurs courantes des horloges du site avant et après délivrance sont respectivement en bleu (en haut) et en vert (en bas);

les flèches bleues indiquent les instants ou les messages pourront être effectivement délivrés.

Page 11: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

11 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

I I I - R E M O T E P R O C E D U R E C A L L “ R P C ” :

Le modèle Client-Serveur est un modèle simple à utiliser pour la structuration des systèmes répartis. Mais ce modèle s’appuie sur des communications de type entrée/sortie (SEND / RECEIVE). Ce n’est pas le modèle plus efficace pour les systèmes répartis car son but est de rendre le comportement des systèmes répartis identique à celui des systèmes centralisés. III.1- Objectif de RPC:

Appel aux procédures distantes presque aussi facilement qu’un appel aux procédures locales. III.2- Fonctionnement d’un appel à procédure (machine unique):

Count = read ( fd, buf, nbytes) ;

• fd = entier.

• Buf = Tableau de caractères.

• Nbytes = entier.

1. Lorsque le programme principal appelle la procédure read il place

les paramètres dans la pile.

2. Lorsque la procédure read a terminé son traitement, elle :

• Place le résultat dans un registre.

• Efface l’adresse de retour.

• Rend la main à l’appelant.

3. L’appelant enlève les paramètres de la pile pour retourner à son état original. Les

paramètres peuvent être passés :

• Par valeur.

• Par référence.

• Par Copy / restore.

Page 12: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

12 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

III.3- Fonctionnement du RPC:

On veut que l’appel à une procédure distante se fasse comme si l’appel était local. Même si cela doit

être transparent pour l’utilisateur, il est nécessaire que le mécanisme RPC mette en place des

versions différentes pour l’appel d’une procédure selon qu’elle soit locale ou distante.

On va donc avoir une souche client (client stub) et une souche serveur (server stub).

Souche Client :

• La version cliente de la procédure est constituée d’une souche cliente (« client stub ») qui est

placée dans la librairie locale.

• L’appel se fait ensuite comme avec une procédure locale (la pile est gérée

localement) et l’exécution est prise en charge par le noyau.

• Par contre, les paramètres ne sont pas stockés dans les registres et aucune

donnée n’est demandée au noyau.

Les paramètres sont stockés dans un message construit par le noyau et envoyé au serveur distant qui

contient la partie serveur de la procédure.

• Le client attend ensuite que le serveur lui réponde.

Souche Serveur :

• La version serveur de la procédure est constituée d’une souche serveur et de la procédure.

• Lorsque le message parvient au serveur, le noyau passe le message à la souche correspondante

(qui est en attente de messages).

• La souche extrait les paramètres du message, renseigne la pile et appelle la procédure qui

pense être appelée par un client local.

• Lorsque la procédure a terminé son traitement, elle renseigne la pile et rend la main à la

souche (voir schéma suivant).

Page 13: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

13 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

La création des souches (stubs) est de la responsabilité du compilateur.

À la compilation les stubs sont créés et le compilateur peut s’aider d’un langage de définition

d’interfaces (IDL).

III.4- Le passage de paramètres:

Le passage de paramètres dans le cadre des RPCS n’est pas forcément quelque chose de Simple.

Dans les systèmes répartis, les machines peuvent être différentes. Des problèmes de conversion

peuvent apparaître.

La problématique va donc être de connaître le format du message et la plateforme cliente :

• Le premier octet (Byte) du message détermine le format utilisé par le client.

• Le serveur compare cet octet avec le sien : Si c’est le même aucune transformation n’est

nécessaire, sinon il effectue la transformation.

Passage de pointeurs en paramètres

Le pointeur (adresse) n’est connu que dans l’espace d’adressage du processus qui le crée.

Cette adresse n’est valide que dans la machine où s’exécute le processus.

La souche client qui récupère un pointeur, copie le contenu de la zone adressée dans le message. Au

retour elle place le résultat dans la zone.

III.5- Localisation du serveur:

La localisation d’un serveur peut se faire de différentes manières :

• Statique : Codée en dur l’adresse du serveur dans le client. En cas de changement de

l’adresse, le client doit être recompilé (les programmes qui Accèdent au serveur).

• Dynamique : lien dynamique (dynamic binding). Ce lien permet de faire dynamiquement

connaître les clients et les serveurs.

Le lien dynamique

La construction du lien dynamique s’effectue en plusieurs étapes. Définition de la spécification du

serveur qui servira à la génération des souches.

À l’initialisation, le serveur exporte son interface. Il l’envoie à un binder (relieur) pour signaler son

existence.

C’est la phase d’enregistrement. Le serveur envoie ses informations :

• nom ;

• version identifiant (unique sur 32 bits en principe) ;

Page 14: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

14 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

• handle (adresse IP, protocoles, etc.).

Lorsqu’un Client appelle une procédure pour la première fois :

• Il constate qu’il n’est pas relié à un serveur.

• Il envoie un message au relieur pour importer la version de la procédure qu’il désire invoquer.

• Le relieur lui renvoie l’identifiant unique (ID) et le handle.

Avantage :

• Cette méthode d’importation et exportation des interfaces est très flexible.

• Les serveurs peuvent s’enregistrer ou se dés enregistrer.

• Le client fournit le nom de la procédure et la version et il reçoit un ID unique et handle.

III.6- Les problèmes liés aux RPCs dans les systèmes répartis:

1. Le client ne peut pas localiser le serveur.

2. L’appel du client n’arrive pas au serveur.

3. La réponse du serveur n’arrive pas au client.

• Il faut dissocier la panne avant l’exécution de la requête ou après l’exécution.

Trois écoles pour résoudre ce problème :

1. Attendre que le serveur redémarre et relancer le traitement. « Au moins un traitement est réussi.

» (Peut-être plus).

2. Abandon du client et rapport de l’erreur. « Au plus un traitement est réussi. » (Peut-être aucun).

3. Ne rien dire au client (aucune garantie) Seuls avantages : Facile à gérer et à implémenter.

En règle générale, crash du serveur = crash du client.

Le client est en panne :

Lorsqu’un client tombe en panne alors qu’il a demandé un traitement à un serveur, on dit que

l’échange devient orphelin. Cela a pour effet de gaspiller du temps CPU, de bloquer des

ressources, lorsqu’il redémarre, il peut recevoir des messages antérieurs à la panne (problème

de confusion).

Quatre solutions peuvent être envisagées :

1. L’extermination : Le client enregistre les appels dans un log. Au redémarrage l’orphelin est détruit.

Beaucoup d’écritures disque à chaque RPC.

Page 15: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

15 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

2. La réincarnation : Le client tient compte du temps. Lorsqu’il redémarre, il annule les

échanges ente deux époques et reprend les échanges orphelins.

3. La réincarnation à l’amiable : Comme précédemment, avec en plus la vérification avec le

serveur concerné des échanges orphelins.

4. Expiration du délai : Un compteur de temps détermine quand un échange devient orphelin.

Les orphelins sont détruits.

Un temps T déterminé identique pour tous est donné à 1 RPC. Difficile de choisir un temps T (les

RPCs sont sur des réseaux différents).

III.7- Les protocoles RPC:

Pour le protocole RPC un certain nombre de choix sont à faire.

III.7.1- Avec ou sans connexion

Avec connexion

Avantage :

• Simple à utiliser.

• Pas d’ACK nécessaire.

• Pas de perte de paquets.

Désavantage :

• Trop difficile à mettre en place sur un WAN.

• Très pénalisant sur un LAN (performance pas bonne).

Note : Les systèmes répartis utilisent des protocoles sans connexion

III.7.1- Utilisation d’un protocole standard ou d’un protocole propriétaire

Protocole propriétaire = protocole conçu pour les RPCs.

Protocole standard (IP, TCP, UDP)

Avantage :

• Déjà construit.

• Implémentation effectuée et disponible.

• Utilisable par tous les systèmes (UNIX, Windows, etc.).

Page 16: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

16 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

• Supporter par la majorité des réseaux.

Désavantage :

• Protocoles peu performants.

• Conçus pour des connexions TCP.

Protocole propriétaires

Avantage :

• Evite les checksums.

• Longueur de paquets variables.

• Adapté au système (spécialisé).

Désavantage :

• Beaucoup de travail de développement.

• Difficile à faire adopter par les autres (nouveau protocole).

III.8- Accusé de réception :

Si une RPC doit être découpée en plusieurs petits paquets.

4Ko de données à envoyer

Choisir entre un accusé de réception par paquet. Attente accusé avant envoi suivant

Page 17: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

17 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Si un problème est rencontré sur un paquet le client le renvoie. Ou seul accusé de réception à la fin

de l’envoi. Envoi aussi vite qu’il peut.

Si un problème est rencontré sur un paquet le serveur le redemande.

III.9- Le chemin critique:

Le code de la RPC est crucial pour les performances du système. La séquence d’instructions

exécutées pour chaque RPC est appelée chemin critique.

C’est le temps nécessaire et rajouté par la RPC vs si le traitement était effectué en local.

Ce chemin critique démarre quand le client appelle la souche client et se termine lorsque le résultat

est renvoyé par le serveur.

Page 18: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

18 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Note : La question intéressante ensuite est : Quelle est la partie du chemin critique où L’on passe le

plus de temps. La réponse permet de savoir où l’effort d’optimisation doit être fait.

III.10- Gestion du temps (timer):

Tous les protocoles sont basés sur des échanges de messages sur les moyens de communication. Les

messages peuvent être perdus et créer de graves problèmes d’intégrité dans le système.

Un des moyens de pallier ce problème est la mise en place d’un timer (gestion du temps). Qui va

associer un horodatage à chacun des messages et définir une durée de vie (délai d’expiration). Si le

temps imparti pour la durée de vie d’un message est écoulé, le message sera renvoyé. Le nombre de

renvois est défini dans le protocole.

Deux méthodes peuvent être envisagées :

1. Mise en place d’une structure spécifique.

2. Insertion d’un champ dans la table des processus.

Mise en place d’une structure spécifique

Une structure va être construite :

• Spécification de l’expiration.

• Quelles sont les actions à prendre en cas d’expiration.

• La structure sera insérée dans une liste existante (qui contient d’autres structures).

La liste doit être surveillée.

La liste est triée par temps.

Lorsqu’un message est envoyé la liste est mise à jour.

Lorsqu’un accusé de réception ou une réponse revient, l’entrée est retirée de la table.

Note : Parce que la plupart du temps les timers n’ont pas le temps d’expirer, on perd beaucoup de

temps à insérer puis effacer les entrées non expirées. Donc une autre approche peut être envisagée.

Insertion d’un champ dans la table des processus.

L’idée est de rajouter une entrée « expiration » dans la table des processus. La mise à jour des timers

devient quelques instructions en langage machine. A intervalles réguliers (toutes les secondes) le

noyau parcourt la table et compare les timers avec le temps courant.

Page 19: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

19 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

III.11- Quelques problèmes liés aux RPCs:

a- Principe de transparence :

L’introduction d’un mécanisme RPC dans un système monoprocesseur ne doit pas :

• Générer un nouvel ensemble de règles qui empêche la construction d’objets qui était possible

avant.

• Impliquer l’utilisation obligatoire d’objets optionnels auparavant.

b- Problème des variables globales :

• Comment peut-on accéder à des variables globales à partir de procédures distantes ?

• Les accès doivent être construits. Le principe de transparence est donc violé.

c- Problème des paramètres variables :

Comment le passage de paramètres dont on ne connaît pas la taille à priori peut se faire ? (Par

exemple les tableaux en langage C).

Idée : On peut coder les longueurs en dur mais :

• Si taille des données < maxi : perte d’espace.

• Si taille des données > maxi : erreur.

Page 20: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

20 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

I V - M é m o i r e p a r t a g é e :

Introduction

En informatique, et dans le cadre de systèmes multiprocesseurs, chaque processeur à sa propre mémoire. Lorsque la mémoire est répartie ou distribuée les processeurs ou les applications de chaque nœud peuvent utiliser un réseau pour accéder aux données présentes sur un autre nœud. Ce réseau peut être interne à la machine et géré au niveau matériel (NUMA) ou externe à un nœud de calcul (Ferme de calcul), et partagé au niveau logiciel (MPI).

IV.1 La mémoire partagée et répartie : Distributed and Shared memory (DSM).

Implémentation facile:

• Une ou plusieurs copies de page en lecture seule possible.

• Une et une seule copie de page en écriture.

Par contre avoir une seule copie de page en écriture génère un goulet d’étranglement. Il est

impératif d’avoir plusieurs copies de page en lecture et en écriture dans le système. Cela peut

conduire à des problèmes d’incohérence.

IV.1.1 Les modèles de cohérence

Les modèles de cohérence sont des contrats basés sur des règles. Ils permettent de gérer plusieurs

copies de pages mémoire dans des mémoires dans systèmes répartis. L’objectif est d’éviter les

goulets d’étranglement associés à l’utilisation concurrente d’une page mémoire unique. Il existe

plusieurs modèles (ou règles) de cohérence :

• Cohérence stricte.

• Cohérence séquentielle.

• Cohérence causale.

• PRAM (Pipelined RAM).

• Cohérence processeurs (faible, relâchée, par entrée).

Ces règles de cohérence correspondent à un contrat entre la mémoire et les programmes à

exécuter dans le système et vont assurer la cohérence des données utilisées par les programmes,

pour les lire ou les modifier (c’est le souci des concepteurs et surtout des utilisateurs).

Page 21: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

21 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

IV.1.1.1 La cohérence stricte

La règle de la cohérence stricte est la suivante : Toute lecture d'une position de mémoire x retourne

la valeur stockée par l'écriture la plus récente.

La problématique

• x est stocké sur une machine B.

• Un processus sur une machine A lit x à un temps T1 (A envoie un message à B pour obtenir x).

• A un temps T2 (un peu plus tard) avec T2 > T1, un processus de B modifie x.

• Si T2 – T1 = 1 ou 2 nanosecondes, pour que A récupère x avant que B ne l’ait modifié,

l’information doit transiter à une vitesse supérieure à la vitesse de la lumière. Note : 10 fois

la vitesse de la lumière si les machines sont à trois mètres l’une de l’autre.

Incohérence : A et B n’ont pas la même valeur de x.

Mais est-ce raisonnable qu’un contrat de cohérence stricte soit passé entre les logiciels et la

mémoire ? Si des processus modifient lisent et écrivent en mémoire à des fréquences

approchant les nanosecondes cela est pratiquement (physiquement) impossible à honorer.

En conclusion, cette règle est la plus contraignante, elle tient compte d'un temps global absolu, ainsi

la détermination de la plus récente ne sera pas ambiguë. Elle implique que lorsque la mémoire est

basée sur la cohérence stricte :

• Tous les processus voient instantanément toutes les écritures qui y sont effectuées.

• Lorsqu’une lecture est effectuée, la dernière mise à jour et fournie. Peu importe lorsque la

prochaine écriture se produira.

IV.1.1.2 La cohérence séquentielle

La règle de la cohérence séquentielle est la suivante : Le résultat de toute exécution est identique à

une exécution séquentielle et ordonnée de tous les processus, et les opérations de chaque

processus apparaissent dans l'ordre d'exécution de son programme.

La problématique au travers d’un exemple

Soit trois processus effectuant chacun deux opérations atomiques :

• P1 : o a = 1 ; o print (b,c) ;

• P2 : o b = 1 ; o print (a,c) ;

• P3 : o c = 1 ; o print (a,b) ;

Page 22: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

22 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Les trois processus s’exécutent en parallèle sur trois processeurs différents et ont tous accès aux

variables a, b, c dans une mémoire répartie et partagée.

Avec six instructions indépendantes on peut avoir en théorie 6! (720) séquences d’instructions

différentes. Néanmoins, comme l’ordre d’exécution a=1 et avant print(b,c) doit être respecté,

cela ramène à 90 séquences possibles.

Prenons quatre séquences parmi ces 90 :

• Seq1 : a=1 ;print(b,c) ;b=1 ;print(a,c) ;c=1 ;print(a,c) ; o Res1=001011

• Seq2 : a=1 ;b=1 ;print (a,c) ;print(b,c) ;c=1 ;print(a,b) ; o Res2=101011

• Seq3 : b=1 ;c=1 ;print(a,b) ;print(a,c) ;a=1 ;print(b,c) ; o Res3=010111

• Seq4 : a=1 ;b=1 ;c=1 ;print(b,c) ;print(a,c) ;print(a,b) ; o bvRes4=111111

Nous trouvons quatre résultats différents en fonction de l’ordre de traitement des instructions.

Ici la notion de temps a disparu, seul l'ordre d'exécution compte. Pour pouvoir appliquer cette règle

de cohérence il faut s'assurer qu'avant le démarrage d'une opération mémoire les autres opérations

soient terminées.

Deux conditions doivent être respectées :

• La séquence d’exécution : exemple précédent.

• La cohérence mémoire : une lecture dans une localisation renvoie toujours la valeur

dernièrement mise à jour.

Note : Assez facile à programmer, mais gros problème de performance. Car si le nombre de

lectures augmente alors le nombre d’écritures diminue :

T = temps mini de transfert entre deux nœuds.

R = temps de lecture.

W = temps d’écriture.

R + W ≥ T

IV.1.1.3 La cohérence causale :

Cette règle est une version affaiblie de la règle de cohérence séquentielle, qui tient compte de

la relation causale potentielle ou pas entre les événements. La règle stipule :

Les écritures qui ont potentiellement une relation causale doivent être vus par tous les processus

dans le même ordre. Des écritures parallèles peuvent être vus dans un ordre différent sur

différentes machines.

Page 23: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

23 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Un exemple :

• Soit P1 qui écrit x.

• Soit P2 qui lit x et écrit y.

• Potentiellement l’écriture de y peut-être la cause de x.

En résumé :

• Si deux processus écrivent simultanément deux variables, il s’agit de processus concurrents qui

n’ont pas de relation causale.

• Si un processus lit une variable et ensuite en écrit une autre, alors il y a possibilité de

relation causale.

Exemple :

P1 ------ E(x)1 ---------------------------------------------------------------------

P2 --------------- L(x)1 ----- E(x)2 -----------------------------------------------

P3 ---------------------------------------- L(x)2-- L(x)1—KO : P3 demande à P2 puis à P1

P4 ---------------------------------------- L(x)1-- L(x)2—OK : P4 demande à P1 puis à P2

IV.1.1.4 La cohérence PRAM (Pipelined RAM)

La règle stipule : Les écritures causales, faites par un processus, sont vues par tous les processus dans

le même ordre, les écritures parallèles (concurrentes) peuvent être vus dans un ordre différent

par des processus différents.

3.1.1.5 La cohérence processeur

Note : Pratiquement identique à la cohérence PRAM. La cohérence PRAM et processeur sont les

mécanismes qui sont les plus performants. Elles sont moins restrictives pour les applications

partant du principe que les applications n’ont forcément à connaître tous les accès en écriture qui

sont effectués. Un moyen serait alors de rentrer les écritures en section critique (personne ne

peut accéder aux variables) et d’envoyer les modifications à tout le monde lorsque les mises à jour

sont effectuées.

Cela introduit la notion de variables de synchronisation pour les modèles de cohérence.

Trois modèles de cohérence sont définis pour la cohérence processeur :

1. La cohérence faible.

2. La cohérence relâchée.

Page 24: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

24 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

3. La cohérence en entrée.

IV.1.1.5.1 La cohérence faible

Cette règle comprend trois articles :

1. Les accès aux variables de synchronisation ont une séquence cohérente. Tout accès est

diffusé à tous les nœuds qui partagent la mémoire et aucun autre n'est possible.

2. L'accès à une variable de synchronisation n'est pas autorisé tant que toutes les écritures qui

précèdent ne sont pas exécutées. (On vide le pipeline).

3. L'accès aux données (écriture ou lecture) n'est pas autorisé tant que tous les accès aux

variables de synchronisation qui précèdent ne sont pas exécutés. (En effectuant une synchro avant

de lire la donnée, on est sûr d’avoir la bonne valeur).

Pour éviter la violation il faudrait retirer la lecture L(x)1 ce qui rendrait E(x)1 et E(x)2 concurrent et

non plus causal. Copyright (C) 1997-2007. JM Rodriguez. Tous droits réservés. Reproduction interdite

par tous moyens sauf à des fins de citation.

Une variable de synchronisation permet de synchroniser la mémoire. Lorsqu'une

synchronisation est exécutée, à la fin, les écritures sont transmises aux autres machines, et les

écritures d'une autre machine sont répercutées dans la machine.

La synchronisation permet d’envoyer toutes les écritures que l’on effectuées et de recevoir

celles des autres.

Exemple de séquences :

Autorisée

P1---- E(x)1 --- E(x)2 --- Synchro --------------------------------------

P2 -----------------------------------------L(x)1 --- L(x)2 --- Synchro

P3 -----------------------------------------L(x)2 --- L(x)1 --- Synchro

Non autorisée

P1---- E(x)1 --- E(x)2 --- Synchro --------------------------------------

P2 ----------------------------------------Synchro -- L(x)1— (Devrait lire la valeur 2)

IV.1.1.5.2 La cohérence faible

Cette amélioration de la cohérence faible permet à la mémoire de savoir quand elle entre ou quand

elle quitte une région critique. Deux opérations complètent le dispositif :

• Acquisition (Acq), indique à la mémoire qu'un entrée dans la région critique est en cours.

Page 25: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

25 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

• Libération (Rel), signale à la mémoire la sortie de la région critique. Voici une séquence valide.

P1- Acq(L) - E(x)1 - E(x)2 - Res (L) --------------------------------

P2 ---------------------------------------- Acq(L) --- L(x)2 --- Res (L) – Lecture garantie

P3 ---------------------------------------------------------------- L(x)1 – Lecture non garantie

La règle se définit ainsi :

1. Avant un accès à une variable partagée, toutes les acquisitions précédentes du processus ont

été exécutées complètement.

2. Avant qu'une libération soit autorisée il faut que toutes les écritures et lectures du processus

soient exécutées complètement.

3. Les opérations 'acquisition' et 'libération' doivent être cohérentes avec le processeur.

IV.1.1.5.3 La cohérence par entrée

La règle s'établit ainsi :

1. Un accès d'acquisition d'une variable de synchronisation n'est pas autorisé pendant le

déroulement d'un processus tant que les données protégées de ce dernier ne sont pas mises à jour.

2. Pour qu'un processus accède en mode exclusif à une variable de synchronisation, il faut s'assurer

qu'aucun autre processus ne soit en train de travailler, même en mode non-exclusif, avec cette

variable de synchronisation.

3. Lorsqu'un accès, en mode exclusif, à une variable de synchronisation est réalisé, tout processus

qui suit en mode non-exclusif et qui demande accès à la variable de synchronisation doit demander

au propriétaire de la région critique les données disponibles.

IV.1.1.6 Synthèse des règles de cohérence

Le premier tableau pour la cohérence sans synchronisation et le suivant pour la cohérence

avec synchronisation résument les caractéristiques majeures des différentes règles de cohérence.

Page 26: Systemes Distribués

S y s t è m e s D i s t r i b u é s

C o m m u n i c a t i o n d e g r o u p e s – P r o t o c o l e s d e d i f f u s i o n – A p p e l s d e

p r o c é d u r e s – M é m o i r e D i s t r i b u é e - M o d è l e s d e C o h é r e n c e

26 | P a g e B o u l e k h m i r A b d e s s a m e d

S

ys

me

s D

is

tr

ib

s

Conclusion .