Systemes Distribués [PDF]

Zitiervorschau

Systèmes Distribués

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 Communication de groupes – Protocoles de diffusion – Appels de procédures – Mémoire Distribuée- Modèles de Cohérence

Table des matières : Introduction Partie I : Communication de groupe Partie II : Protocoles de diffusion Partie III : Appel de procédures Partie IV : Mémoire partagée

Systèmes Distribués

Conclusion

2|Page

Boulekhmir Abdessamed

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

.

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.

Systèmes Distribué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.).

3|Page

Boulekhmir Abdessamed

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

I- Communication de groupes : 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.

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.

4|Page

Boulekhmir Abdessamed

Systèmes Distribués

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.

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

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:

II- Les protocoles de diffusion : 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.

5|Page

Boulekhmir Abdessamed

Systèmes Distribués

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

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

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. 15h10

16h01

I.1.2- Ordre consistant:

Remarque : L’ordre absolu est un ordre consistant + l’ordre de réception doit être le même que celui de l’émission.

6|Page

Boulekhmir Abdessamed

Systèmes Distribués

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

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

Afin d’avoir cet ordre deux solutions sont proposées : Solution 1 : many-to-one puis one-to-many (Centraliser)

Donner des numéros de séquences aux messages

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.

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.

7|Page

Boulekhmir Abdessamed

Systèmes Distribué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.

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

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

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



8|Page

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. Boulekhmir Abdessamed

Systèmes Distribués

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 :

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

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

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.

9|Page

Boulekhmir Abdessamed

Systèmes Distribués

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 :

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

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 : 



Systèmes Distribués



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.

10 | P a g e

Boulekhmir Abdessamed

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

III- REMOTE PROCEDURE CALL “RPC”: 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 les paramètres dans la pile. 2. Lorsque la procédure read a terminé son traitement, elle :

il place

• 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 : Systèmes Distribués

• Par valeur. • Par référence. • Par Copy / restore.

11 | P a g e

Boulekhmir Abdessamed

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

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 donnée n’est demandée au noyau.

ne sont pas stockés dans les registres et aucune

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.

Systèmes Distribués

• Lorsque la procédure a terminé son traitement, elle renseigne la pile et rend la main à la souche (voir schéma suivant).

12 | P a g e

Boulekhmir Abdessamed

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

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.

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) ;

13 | P a g e

Boulekhmir Abdessamed

Systèmes Distribués

Le lien dynamique

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

• 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.

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.

14 | P a g e

Boulekhmir Abdessamed

Systèmes Distribués

Le client est en panne :

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

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 Systèmes Distribués

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.).

15 | P a g e

Boulekhmir Abdessamed

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

• 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

Systèmes Distribués

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

16 | P a g e

Boulekhmir Abdessamed

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

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.

Systèmes Distribués

Ce chemin critique démarre quand le client appelle la souche client et se termine lorsque le résultat est renvoyé par le serveur.

17 | P a g e

Boulekhmir Abdessamed

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

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.

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.

18 | P a g e

Boulekhmir Abdessamed

Systèmes Distribués

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

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

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.

Systèmes Distribués

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

19 | P a g e

Boulekhmir Abdessamed

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

IV- Mémoire partagé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 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).

20 | P a g e

Boulekhmir Abdessamed

Systèmes Distribués

• Cohérence séquentielle.

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

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.

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) ;

21 | P a g e

Boulekhmir Abdessamed

Systèmes Distribués

IV.1.1.2 La cohérence séquentielle

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

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.

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.

22 | P a g e

Boulekhmir Abdessamed

Systèmes Distribués

R = temps de lecture.

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

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.

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.

23 | P a g e

Boulekhmir Abdessamed

Systèmes Distribués

3.1.1.5 La cohérence processeur

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

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

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.

24 | P a g e

Boulekhmir Abdessamed

Systèmes Distribués

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

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

• 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

Systèmes Distribués

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.

25 | P a g e

Boulekhmir Abdessamed

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

.

Systèmes Distribués

Conclusion

26 | P a g e

Boulekhmir Abdessamed