Un S.R. est organisé comme un ensemble de processus qui s'exécutent sur des sites reliés par un système de communication et qui communiquent en échangeant des messages. Sur chaque site, il est possible de définir un état local, qui est modifié par l'exécution des processus du site.
On appelle évennement un changement local d'état sur un site, ou bien l'envoi ou la réception d'un message par un processus.
Une horloge locale unique permet de dater chacun des évennements. On suppose que tous les évennements ont des dates différentes. Mais, dans les systèmes répartis, bien que chaque site dispose d'une horloge locale, il n'existe pas d'horloge réelle globale, alors que l'ordre dans lequel surviennent les évennements est parfois primordial.
Exemples :Il est donc nécessaire de définir des méthodes qui permettent d'assurer une relation causale entre les différents évennements. On va pour cela créer des horloges logiques ou physiques.
Cette relation n'est mise en oeuvre que sur les évennements. Il y a deux contraintes séquentielles fondamentales :
Une relation d'ordre entre les évennements vérifiant ces contraintes a été définie par Lamport.
Soit A et B deux évennements. On dit que A précède B et on note A --> B si et seulement si l'une des trois conditions suivantes est vraie :
e1.1 e1.2 e1.3
(1) --------x------------------x-----------x----
\ / /
e2.1 \ e2.2 / e2.3 /
(2) --x---------------------x----x--------------
\ / /
\ / /
(3) ------x-------x-----x-----x------x----------
e3.1 e3.2 e3.3 e3.4 e3.5
Deux évennements liés par la relation de causalité appartiennent à un chemin causal. Par exemple, e11 et e34 appartiennent au chemin causal e1.1, e3.2, e3.3, e3.4.
De manière plus générale, si on considère pour un évennement donné l'ensemble de tous ses prédecesseurs, on obtient l'ensemble de tous les évennements qui en sont la cause [potentielle].
La relation de causalité entre évennements crée donc un ordre partiel sur ces évennements. Deux évennements A et B sont dits concurents (ou causalement indépendants) et notés A||B si aucun des deux ne précède causalement l'autre, et ne peut donc influer sur lui. Par exemple, e2.1||e1.1.
On s'intéresse ici à construire un ordre total qui soit cohérent avec la relation de causalité. Pour cela, on associe à chaque évennement une estampille telle que si on compare les estampilles de 2 évennements, l'estampille de la cause est inférieure à celle de l'effet.
Sur Chaque site Si, on trouve une variable entière Hi, dite horloge locale, initialisée à 0. La date locale d'un évennement E est notée d(E).
La date globale d(E) d'un évennement E est alors (d(E), i) où i est le numéro du site où a lieu l'évennement et d(E) sa date locale.
(1,1) (3,1) (6,1)
S1 ------------x--x-------------------x------
\/ /
(1,2) /\ (3,2) (5,2) /
S2 ------x-----x--x--------x-------x---------
\ (2,2) (4,2)
(2,3) \ (3,3) (4,3)
S3 ---------x--------x-------------x---------
On a une relation d'ordre total notée ==>. (d(E1), i1) ==> (d(E2), i2) si et seulement si l'une des deux conditions suivantes est vraie:
Ce système d'estampillage est très interessant lorsque le problème à résoudre nécessite un ordre total sur les évennements respectant les relations de causalité qui les lient. C'est le cas par exemple de l'exclusion mutuelle.
Propriété :Si H est la valeur d'horloge associée à un évennement A, alors il y a exactement H - 1 évennements qui précèdent causalement A sur le plus long chemin causal se terminant par A. En d'autres termes, il s'agit là du nombre maximum d'évennements qui peuvent avoir lieu avant que A se produise.
La relation ==> ordonne bien les évennements mais elle perd la relation de causalité, c'est à dire l'information selon laquelle deux évennements sont indépendants. Pour remédier à ce problème, on peut utiliser l'algorithme des horloges vectorielles.
Considérons un observateur extérieur au système qui en percevrait tous les évennements et qui compterait pour chaque site le nombre d'évennements qui ont eu lieu depuis le début.
----*-----*-----------*---
-------*--------*---------
-------------*------------
1 1 2 2 2 3
1 1 1 1 2 2
0 0 0 1 1 1
Le but est d'offrir à chaque site une vue semblable.
Sur chaque site Si, on définit une horloge vectorielle comme un vecteur Vi[1..n] initialisé à 0.
(1) -----------x---+-----------------------------
/0 /1 2\
V / 0 / 1 1 \
1 \ 0 / 0 0 \
\0 / 0 0 \
/ \
(2) -----+---------------x-----x---*-----x---*---
/0 0\ 2 /2 2 /2 2
V / 0 1 \ 2 / 3 4 / 5 6
2 \ 0 0 \ 0 / 2 2 / 2 2
\0 0 \ 0 / 0 0 / 2 2
\ / /
(3) -----------x---------+-----------------------
/0 0\ 0 /
V / 0 1 \ 1 /
3 \ 0 1 \ 2 /
\0 0 \ 0 /
\ /
(4) -----------------x-------+-------------------
/0 0 0
V / 0 1 1
4 \ 0 0 0
\0 1 2
Pour deux horloges vectorielles V1 et V2, on a :
On garde donc la précédence causale, car E1 <-- E2 si et seulement si V1 >= V2.
Le but est ici de fournir un mutex réparti. On va pour cela utiliser utiliser l'algorithme de Ricart et Agravala (1981). On pose les hypothèses suivantes:
La réalisation se fait en trois étapes :
Dans cet exemple, les machines 1 et 2 ont besoin d'entrer en section critique. Les conventions de représentation sont les suivantes :
0 2 3 4 5
3 -----------x-+--x-------+--------------------------------
/ \/ \
Req,1,2 / /\ Ack,3,3 \ Ack,5,3
0 1/ 2/ \4 \ 5 9
2 -------+----x----x--------------+--------------x=====----
\ / \ \ /
Req,1,2 \/ Req,1,1 \ \ Ack,5,2 / Ack,8,1
0 1/\2 (vers 2 et 3) \6 \7 8/
1 --------+--x--------------------x---x======+-------------
Le but est de permettre une diffusion fiable avec ordre causal.
ATTENTION : ICI, ON ESTAMPILLE UNIQUEMENT LES EMISSIONS
On procède en 4 étapes :
Par rapport aux horloges logiques, les systèmes synchrones sont caractérisés par l'approche duale, c'est à dire qu'il existe une horloge globale qui fait avancer le système. Il existe un dispositif qui produit une séquence de signaux ou pulsations, et le système obéit aux règles suivantes :
Question : Etant donné un système réparti asynchrone, comment avoir des horloges synchrones?
Hypothèses : On suppose qu'à chaque pulsation, un site peut envoyer au maximum un message à chacun de ses voisins. Le réseau physique étant asynchrone, les messages ont des temps de transit différents.
On considère sur chaque système Si une variable n-puli, cette variable servant à régler le synchronisme. On a un message envoyé par n-puli.
Le problème à régler est le suivant : si Si, lors de la pulsation p n'a pas reçu de message de son voisin Sj, il ne peut conclure qu'entre deux scénari :
Or le site Si ne peut considérer la pulsation p finie que si il a reçu tous les messages envoyés à cette même pulsation.
Dans le cas où tous les voisins de Si lui envoient un message à chaque pulsation, il est très simple de savoir quand la pulsation se termine. On va donc généraliser ce cas. Chaque processeur ou machine enverra soit un message, soit une trame appellée trame contrôle si il n'a pas besoin de communiquer.
Une horloge physique hp est un dispositif permettant de bâtir une métrique du temps. Elle permet d'associer à un évennement E une date hp(e). Une telle horloge est un compteur d'évennements périodiques qui est caractérisé par une certaine granularité (espace de temps entre deux tics horloge).
On suppose qu'une horloge physique est asociée à chaque site Si du système réparti. Ces horloges, de par le dispositif avec lequel elles sont construites, peuvent avoir une certaine dérive par rapport au temps de référence, notée p. Si l'on considère les horloges physiques de deux sites, la dérive maximale est de 2 * p.
Etant donné un système réparti, il est possible d'avoir différentes valeurs du temps à un instant t. Le but est de constituer un référentiel de temps physique qui soit global et unique dans le S.R., ce qui permet d'associer à tout évennement une date d'occurence qui ait une signification dans tout le Système. Cela peut servir à dater des e-mails, aussi bien que gérer correctement la compilation distribuée, ou autres...
On va donc construire sur chaque site Si une horloge Ci, avec l'aide d'horloges physiques qui vont permettre de dater les évennements. Si on note Ci(t) la valeur de Ci à l'instant t, les 3 propriétés suivantes doivent tj être respectées :
Le but de cet algorithme consiste à calculer périodiquement une fonction d'ajustement. On aura Ci(t) = hpi(t) + A(t)
Afin de calculer A(t), les sites voisins se communiquent la valeur de leur horloge Ci au moins tous les per unités de temps. Lors d'une resynchronisation pour un site, on a Ci(t) = L alors que sa valeur devrait être T. On calcule alors A(t) de façon à ce que sur la prochaine période de resynchronisation, la différence T - L soit absorbée par Ci(l).
Suivant le réseau de communication établi, il existe différents protocoles mis en oeuvre pour la resynchronisation.
Prenons l'exemple d'un système réparti dont on connait les délais maximum (d) et minimum (dmin) sur les canaux entre tout couple de sites voisins. La quantité d - dmin correspond au jiger du réseau.
Tous les messages sont estampillés avec la valeur actuelle de Ci, et chaque site envoie un message vers chacun de ses voisins au plus tard toutes les per unités de temps. A la réception d'un message (M, Tm) où Tm est la date d'émission, le récepteur Si effectue les actions suivantes :
Pour p = 10-5, diamètre = 1, dmin = 14 ms, d = 25 ms et per = 60 s, on obtient E = 12,2 ms.
Il n'y a qu'un protocole qui soit dans le domaine public : NTP
Soit E un ensemble d'éléments constituant une applicaiton répartie. Une coupure est un sous-ensemble fini C de E tel que pour a et b appartenant à E, si a appartient à C et b précède localement a, alors b appartient à E.
Une coupure est la photographie instantanée d'un système, obtenue en prenant un évennement par site et tous les évennements du site qui le précèdent. C'est un sous-ensemble de l'histoire de l'application qui contient toute l'histoire qui le précède. Cela permet de définir un passé et un futur.
La frontière F d'une coupure C est l'ensemble des évennements les plus récents de la coupure, un sur chaque site.
Un évennement a appartient à F si et seulement si a appartient à C et qu'il n'existe aucun évennement b appartenant à C tel que a --> b.
Une coupure cohérente est une coupure qui respecte la causalité (un message ne peut pas venir du futur). C'est une coupure fermée par la relation de dépendance causale suivante : Si a appartient à C et b --> a, alors b appartient à C.
On dit que l'état global est cohérent si la coupure associée est cohérente.
|
|
|