Chapitre IV :
Coordination
Systèmes Répartis
Amine DHRAIEF 1ère année Master
Contexte : Le temps
● Depuis 1967, la seconde n’est plus définit par rapport à l’année (1/86400ème partie du jour solaire moyen) mais par rapport à une propriété de la matière
– « La seconde est la durée de 9 192 631 770 périodes de la
radiation correspondant à la transition entre les deux niveaux hyperfins de l’état fondamental de l’atome de césium 133 »
● Les horloges ne sont pas forcément synchronisées.
– Peut poser de grave problèmes pour la localisation GPS par
exemple
19/12/2019
Systèmes Répartis
2
Contexte : Le temps exemple : trilatération GPS
● Nom / tdépart ● Localisation
d= Distance(satellite → homme) ? d=vitesse * temps de parcours = c * (tarrviée - tdépart) =
19/12/2019
Systèmes Répartis
Terre
3
Contexte : Le temps exemple : trilatération GPS
d
19/12/2019
Systèmes Répartis
4
Contexte : Le temps exemple : trilatération GPS
19/12/2019
Systèmes Répartis
5
Contexte : Le temps exemple : trilatération GPS
19/12/2019
Systèmes Répartis
6
Contexte : Le temps exemple : trilatération GPS
19/12/2019
Systèmes Répartis
7
Contexte : Le temps exemple : trilatération GPS
19/12/2019
Terre
Systèmes Répartis
8
Contexte : Le temps exemple : trilatération GPS
19/12/2019
Terre
Systèmes Répartis
9
Contexte : Le temps exemple : trilatération GPS
19/12/2019
Terre
Systèmes Répartis
10
Localisation OK !
Contexte : Le temps exemple : trilatération GPS
La navigation aérienne utilise largement le GPS
19/12/2019
Systèmes Répartis
11
Contexte : Le temps exemple : trilatération GPS
● Erreur de synchronisation entre l’horloge du satellite et l’horloge du récepteur peut avoir un impact désastreux sur la navigation mondiale
– Un décalage d’une
milliseconde (0,001 s), une erreur de 300 km se ressentira au niveau de la position.
1er juillet 2002 Collision d'Überlingen
19/12/2019
Systèmes Répartis
12
Et dans Internet … ????
Qui est le premier ? Client#1 10:10 Client#2 10:15
Serveur
Client #1
Client #2
19/12/2019
Systèmes Répartis
13
Problématique ?
● Le temps est très important dans les
systèmes répartis. On veut savoir avec précision quand un évènement est arrivé.
● Il n’y a pas d’horloge globale pour mesurer le temps à travers les systèmes répartis, étant donné le délai pour envoyer par réseau une lecture de temps.
19/12/2019
Systèmes Répartis
14
Problématique ?
● Algorithmes de synchronisation servent à
– maintenir la cohérence des données réparties,
– éliminer les mises à jour redondantes,
– vérifier l’authenticité des requêtes envoyées au
serveur,
– coordonner certaines opérations,
– tracer l'exécution du système..
19/12/2019
Systèmes Répartis
15
Objectifs
● Dans ce cours, nous nous concentrons sur la
façon dont les processus peuvent synchroniser et coordonner leurs actions.
– Par exemple, il est important que plusieurs processus
n'accèdent pas simultanément à une ressource partagée, telle qu'un fichier, mais coopèrent pour s'accorder mutuellement un accès exclusif.
– Un autre exemple : plusieurs processus peuvent
parfois devoir s'accorder sur l'ordre des événements, par exemple si le message m1 du processus P a été envoyé avant ou après le message m2 du processus Q.
19/12/2019
Systèmes Répartis
16
La synchronisation et la coordination
● La synchronisation et la coordination sont deux phénomènes
étroitement liés.
– Lors de la synchronisation de processus, nous nous assurons qu’un
processus en attend un autre pour terminer son opération.
– En ce qui concerne la synchronisation des données, le problème
consiste à s'assurer que deux ensembles de données sont identiques.
● En matière de coordination, l’objectif est de gérer les
interactions et les dépendances entre les activités d’un système distribué.
– De ce point de vue, on pourrait affirmer que la coordination englobe la
synchronisation.
19/12/2019
Systèmes Répartis
17
La synchronisation de l’horloge
19/12/2019
Systèmes Répartis
18
La synchronisation de l’horloge
● Dans un système centralisé, le temps n’est pas
ambiguë
– Lorsqu'un processus veut connaître l'heure, il appelle
simplement le système d'exploitation.
– Si le processus A demande l'heure, puis un peu plus
tard, B demande l'heure, la valeur obtenue par B sera supérieure (ou éventuellement égale à) à la valeur A.
– Ce ne sera certainement pas inférieur.
– Dans un système distribué, parvenir à un accord dans
les délais est une tâche difficile à réaliser.
19/12/2019
Systèmes Répartis
19
La synchronisation de l’horloge
● Imaginons un instant les conséquences de l’absence d’une horloge
globale sur le programme Unix, par exemple.
● Normalement, sous Unix, les programmes volumineux sont divisés en plusieurs fichiers source, de sorte qu'une modification apportée à un fichier source ne nécessite la recompilation d'un seul fichier, pas tous les fichiers.
● Si un programme contient 100 fichiers, on n’a pas à tout recompiler car
un fichier a été modifié
→ cela augmente considérablement la vitesse à laquelle les programmeurs peuvent travaille
19/12/2019
Systèmes Répartis
20
La synchronisation de l’horloge
● Lorsque le programmeur a fini de modifier tous les fichiers source, il
exécute make, qui examine l'heure à laquelle tous les fichiers source et objet ont été modifiés.
● Si le fichier source input.c a été modifié à l'heure 21 :51 et que le
fichier objet correspondant input.o a été modifié à l'heure 21 :50, make sait que input.c a été modifié depuis la création de input.o et que input.c doit donc être recompilé.
● D'autre part, si output.c a été modifié à l'heure 21:44 et que output.o a
été modifié à l'heure 21 :45, aucune compilation n'est nécessaire.
● Ainsi, make parcourt tous les fichiers source pour déterminer ceux qui doivent être recompilés et appelle le compilateur pour les recompiler.
19/12/2019
Systèmes Répartis
21
La synchronisation de l’horloge
● Maintenant, imaginez ce qui pourrait arriver dans un système distribué dans lequel il n’y a pas un consensus/accord sur un temps global.
● Supposons que output.o ait l'heure 21 :44 et que peu après,
output.c soit modifié mais que l'heure 21 :43 lui soit affectée, car l'horloge de sa machine est légèrement en retard.
● make n'appelle pas le compilateur.
– Le programme binaire exécutable résultant contiendra alors un
mélange de fichiers objets des anciennes sources et des nouvelles sources.
– Cela plantera probablement et le programmeur deviendra fou en
19/12/2019
essayant de comprendre ce qui ne va pas avec le code.
Systèmes Répartis
22
La synchronisation de l’horloge
1- output.o ait l'heure 21 :44 2- peu après, output.c soit modifié mais que l'heure 21 :43 lui soit affectée, car l'horloge de sa machine est légèrement en retard.
19/12/2019
Systèmes Répartis
23
Est-il possible de synchroniser toutes les horloges dans un système distribué?
La réponse est très compliqué.
19/12/2019
Systèmes Répartis
24
Horloge physique
● Presque tous les ordinateurs ont un circuit permettant de garder une trace du
temps. Malgré l'utilisation répandue du mot «horloge» pour désigner ces dispositifs, ils ne sont pas réellement des horloges au sens habituel.
– Un Timer/Une minuterie est peut-être un meilleur mot.
– Une minuterie d'ordinateur est généralement un cristal de quartz usiné avec précision.
– Lorsqu'ils sont maintenus sous tension, les cristaux de quartz oscillent à une
fréquence bien définie qui dépend du type de cristal, de la manière dont il est coupé et de l'intensité de la tension.
– Deux registres sont associés à chaque cristal, un compteur et une mémoire
– Chaque oscillation du cristal décrémente le compteur d'une unité.
– Lorsque le compteur atteint zéro, une interruption est générée et le compteur est
rechargé à partir du registre mémoire.
– De cette manière, il est possible de programmer une minuterie pour générer une
interruption 60 fois par seconde ou à toute autre fréquence souhaitée.
– Chaque interruption est appelée un tic d'horloge.
19/12/2019
Systèmes Répartis
25
Horloge physique
● Lorsque le système est démarré, il demande
généralement à l'utilisateur de saisir la date et l'heure, qui sont ensuite converties en nombre de tics après une date de début connue et stockées en mémoire.
– La plupart des ordinateurs ont une mémoire RAM
CMOS spéciale sauvegardée sur batterie, de sorte que la date et l'heure ne doivent pas être entrées lors des démarrages suivants.
– À chaque heure d'horloge, la procédure de service
d'interruption ajoute un à l'heure enregistrée dans la mémoire.
– De cette façon, l'horloge (logicielle) est tenue à jour.
19/12/2019
Systèmes Répartis
26
Horloge physique
● Avec un seul ordinateur et une seule horloge, peu importe si cette horloge est légèrement décalée.
– Étant donné que tous les processus de la machine
utilisent la même horloge, ils resteront cohérents en interne.
– Par exemple, si le fichier input.c a l'heure 21 : 51 et le
fichier input.o l'heure 21 : 50, make recompilera le fichier source, même si l'horloge est décalée de 2s et que les heures vraies sont 21 :53 et 21 : 52, respectivement.
– Tout ce qui compte vraiment, ce sont les temps
relatifs.
19/12/2019
Systèmes Répartis
27
Horloge physique
● Dès que plusieurs processeurs sont
introduits, chacun avec sa propre horloge, la situation change radicalement.
● Bien que la fréquence à laquelle un oscillateur à cristal fonctionne soit généralement relativement stable, il est impossible de garantir que les cristaux de différents ordinateurs fonctionnent exactement à la même fréquence.
19/12/2019
Systèmes Répartis
28
Horloge physique
● En pratique, quand un système a (n) ordinateurs, tous les (n)
cristaux fonctionneront à des vitesses légèrement différentes, ce qui entraînera une désynchronisation progressive des horloges (logicielles) et la lecture de valeurs différentes.
● Cette différence de temps est appelée décalage/dérive
d'horloge. En raison de ce décalage d'horloge, les programmes qui s'attendent à ce que le temps associé à un fichier, à un objet, à un processus ou à un message soient corrects et indépendants de la machine sur laquelle il a été généré (c'est-à-dire quelle horloge il a utilisée) peuvent échouer (comme dans l’exemple de make).
19/12/2019
Systèmes Répartis
29
Horloge physique
Publicité
● La base pour garder l'heure globale est appelée Universal Coordinated Time mais elle est
abrégée en UTC.
– UTC est la base de tout chronométrage civil moderne et est une norme mondiale.
– Pour fournir l'heure UTC aux personnes qui ont besoin d'une heure précise, une quarantaine de stations de radio à ondes courtes du monde entier diffusent une impulsion courte au début de chaque seconde UTC.
– La précision de ces stations est d'environ ± 1 ms, mais en raison de fluctuations atmosphériques
aléatoires pouvant affecter la longueur du trajet du signal, en pratique, la précision ne dépasse pas ± 10 ms.
● Plusieurs satellites de la Terre offrent également un service UTC. Le satellite géostationnaire peut fournir le temps UTC avec précision à 0,5 ms, et certains autres satellites obtiennent même de meilleurs résultats.
– En combinant les réceptions de plusieurs satellites, il est possible de construire des serveurs d’heure au
sol offrant une précision de 50 nsec.
● Les récepteurs UTC sont disponibles dans le commerce et de nombreux ordinateurs en sont
équipés.
19/12/2019
Systèmes Répartis
30
Horloge physique pour résumer...
● Horloge d'ordinateur: cristal au quartz qui vibre à une
fréquence précise (e.g. à plus ou moins 10−6 ), avec une interruption après un certain nombre d'oscillations, ce qui génère un tic.
● L'horloge est obtenue par un calcul d'un temps initial (heure lue mémorisé avec une pile): temps lu au démarrage+ nombre de tics depuis ce temps initial * durée d’un tic.
● Les cristaux diffèrent d'un ordinateur à l'autre, ce qui cause une
désynchronisation entre les systèmes multi-ordinateurs, appelée dérive/décalage des horloges (clock skew).
19/12/2019
Systèmes Répartis
31
La synchronisation de l’horloge Algorithmes de synchronisation d'horloge
19/12/2019
Systèmes Répartis
32
Algorithmes de synchronisation d'horloge
● Si une machine est équipée d’un récepteur UTC,
l’objectif est de garder toutes les autres machines synchronisées.
● Si aucune machine ne dispose de récepteurs UTC,
chaque machine garde une trace de son propre temps et le but est de synchroniser ces machines.
● De nombreux algorithmes ont été proposés pour
effectuer cette synchronisation.
19/12/2019
Systèmes Répartis
33
Horloge physique
● Toutes les horloges sont basées sur un oscillateur
harmonique
– Un objet qui résonne à une certaine fréquence et dont on peut
ensuite déduire le temps.
– Les horloges atomiques sont basées sur les transitions de
l'atome de césium 133.
● Les horloges matérielles de la plupart des ordinateurs utilisent un oscillateur à cristal (le quartz), également capable de produire une fréquence très élevée et stable, bien que moins stable que celle des horloges atomiques.
19/12/2019
Systèmes Répartis
34
Horloge physique
● Une horloge logicielle d’un ordinateur est dérivée de
l’horloge matérielle de cet ordinateur.
● L’horloge matérielle provoque une interruption f fois par
seconde.
– Lorsque cette minuterie est désactivée, le gestionnaire
d'interruptions ajoute 1 à un compteur qui enregistre le nombre de tics (interruptions) depuis une certaine heure convenue dans le passé.
– Ce compteur agit comme une horloge logicielle C, résonnant
à la fréquence F.
19/12/2019
Systèmes Répartis
35
Objectif des algorithmes de synchronisation d’horloges
● Si l'heure UTC est t, on note Cp(t) la valeur de
l'horloge logicielle sur la machine p.
● Les algorithmes de synchronisation d'horloge ont pour objectif de conserver l'écart entre les horloges respectives de deux machines quelconques d'un système distribué, dans une limite spécifiée, appelée précision (precision) π:
→ ∀t, p, q: | Cp(t) - Cq(t) | ≤ π
∀
19/12/2019
Systèmes Répartis
36
Objectif des algorithmes de synchronisation d’horloges
● Notez que la précision fait référence à la
déviation des horloges uniquement entre les machines faisant partie d'un système distribué.
● Quand on considère un point de référence externe, comme UTC, on parle d’exactitude (accuracy), dans le but de la maintenir inférieur à une valeur α:
→
∀ t,
∀
p: | Cp(t) - t | ≤ α
19/12/2019
Systèmes Répartis
37
Objectif des algorithmes de synchronisation d’horloges
● L'idée même de la synchronisation
d'horloge est que nous gardons des horloges précises (precise) ou exacte (accurate)
– précises (precise), appelées synchronisation
interne
– exacte (accurate), appelées synchronisation
externe.
19/12/2019
Systèmes Répartis
38
Objectif des algorithmes de synchronisation d’horloges
● Un ensemble d'horloges qui sont exactes dans une
limite α , seront précis dans une limite π = 2α.
|C p(t )−t|≤α |C q(t )−t|≤α |C p(t )−C q(t )|≤2∗α=π
● Cependant, être précis ne nous permet pas de
conclure sur l'exactitude des horloges.
19/12/2019
Systèmes Répartis
39
Objectif des algorithmes de synchronisation d’horloges
● Dans un monde parfait, nous aurions Cp(t) = t pour tout p et tout t, et
donc α = π = 0.
● Malheureusement, les horloges matérielles, et donc aussi les horloges
logicielles, sont soumises à une dérive d'horloge:
– en raison de leur fréquence qui n’est pas parfaite et affecté par des sources externes (telles que la température), les horloges de différentes machines commencent à afficher progressivement des valeurs différentes pour le temps.
→ C'est ce que l'on appelle le taux de dérive d'horloge: la différence par unité de temps d'une horloge de référence parfaite.
● Une horloge matérielle typique à quartz a un taux de dérive de l’ordre de 10-6 secondes par seconde, ou environ 31,5 secondes par an. Il existe des horloges de matériel informatique dont les taux de dérive sont beaucoup plus faibles.
19/12/2019
Systèmes Répartis
40
Objectif des algorithmes de synchronisation d’horloges
● Les spécifications d'une horloge matérielle incluent
son taux de dérive d'horloge maximal ρ.
● Si F (t) indique la fréquence réelle de l’oscillateur de l’horloge matérielle à l’instant t et F sa fréquence idéale (constante), une horloge matérielle est conforme à ses spécifications si :
∀ t ,1−ρ≤
F (t ) F
≤1+ρ
19/12/2019
Systèmes Répartis
41
Objectif des algorithmes de synchronisation d’horloges
● En utilisant des interruptions matérielles, nous couplons
directement une horloge logicielle à une horloge matérielle, et donc également à son taux de dérive. En particulier, nous avons :
Cp(t )=
1 F
t
∗∫
0
F (t )dt ⇒
d Cp(t) dt
=
F (t ) t
● ce qui nous amène à notre objectif ultime, à savoir garder la dérive de l'horloge logicielle à taux également inférieur à ρ
∀ t : 1−ρ≤
19/12/2019
dCp(t ) dt
Systèmes Répartis
≤1+ρ
42
Objectif des algorithmes de synchronisation d’horloges
19/12/2019
Systèmes Répartis
43
Objectif des algorithmes de synchronisation d’horloges
● Si deux horloges s'écartent de UTC dans la direction
opposée, à un moment ∆t après leur synchronisation, elles peuvent être éloignées de 2ρ * ∆t.
● Si les concepteurs de système veulent garantir une précision
π, c'est-à-dire qu'aucune horloge ne diffère de plus de π secondes, les horloges doivent être resynchronisées (au moyen d'un logiciel) au moins toutes les π / (2ρ) secondes.
● Les différents algorithmes diffèrent par la manière dont cette
resynchronisation est effectuée.
19/12/2019
Systèmes Répartis
44
Network Time Protocol (NTP)
● Une approche courante dans de nombreux protocoles et
proposée à l'origine par Cristian en 1989 (Cristian F. Probabilistic Clock Synchronization. Distributed Computing, 3:146–158, 1989.) est de laisser les clients contacter un serveur de temps.
● Ce dernier peut fournir avec précision l’heure actuelle, en l’équipant d’un récepteur UTC ou d’une horloge atomique.
● Le problème, bien sûr, est que lorsqu’un client contacte un
serveur de temps, les retards de messages auront dépassé la date indiquée. L'astuce consiste à trouver une bonne estimation de ces retards.
19/12/2019
Systèmes Répartis
45
Network Time Protocol (NTP)
● Considérez la situation présenté par la figure ci-dessous
● Dans ce cas, A enverra une requête à B, horodatée avec la valeur T1. B, à son tour, enregistrera l'heure de réception T2 (extraite de sa propre horloge locale), et retournera une réponse horodatée avec la valeur T3, en y insérant la valeur précédemment enregistrée T2. Enfin, A enregistre l’heure de l’arrivée de la réponse, T4.
19/12/2019
Systèmes Répartis
46
19/12/2019
Systèmes Répartis
47
Network Time Protocol (NTP)
● Supposons que les délais de propagation de A à B soient à peu près identiques à ceux de B à A, ce qui signifie que :
δT requête=T 2−T 1≃T 4−T 3=δT reponse
19/12/2019
Systèmes Répartis
48
Network Time Protocol (NTP)
● Dans ce cas, A peut estimer son décalage
par rapport à B comme suit:
δ=délai de propagation de A → B≈délai de propagation de B → A θ=déclagae de A par rapport à B T 2=T 1+δ+θ T 4=T 3+δ−θ (T 4−T 2)=(T 3−T 1)−2∗θ θ= (T 2−T 1)+(T 3−T 4)
2
19/12/2019
Systèmes Répartis
49
δ=délai de propagation de A →B≈délai de propagation de B → A θ=déclagae de A par rapport à B T 2=T 1+δ+θ T 4=T 3+δ−θ (T 4−T 2)=(T 3−T 1)−2∗θ θ= (T 2−T 1)+(T 3−T 4)
2
19/12/2019
Systèmes Répartis
50
Network Time Protocol (NTP)
● Si l’horloge de A est rapide, θ <0, ce qui signifie que A devrait, en principe, reculer son horloge.
● Ceci n'est pas autorisé car cela pourrait
entraîner de graves problèmes, tels qu'un fichier objet compilé juste après le changement d'horloge ayant une heure antérieure à celle de la source qui a été modifiée juste avant le changement d'horloge.
19/12/2019
Systèmes Répartis
51
Network Time Protocol (NTP)
● Un changement dans l’horloge de A doit être introduit
progressivement.
● Supposons que le minuteur soit configuré pour générer 100
interruptions par seconde.
● Normalement, chaque interruption ajoute 10 ms à l’heure.
– Lors du ralentissement, la routine d’interruption n’ajoute que 9 ms à
chaque fois que la correction est effectuée.
– De la même manière, l'horloge peut être avancée progressivement en ajoutant 11 ms à chaque interruption au lieu de la faire avancer d'un coup.
19/12/2019
Systèmes Répartis
52
Network Time Protocol (NTP)
● Dans le cas du protocole NTP (Network Time Protocol), ce
protocole est configuré par paires entre les serveurs.
● En d'autres termes, B sondera également A pour son heure
actuelle.
● Le décalage θ est calculé comme précédemment, ainsi que
l'estimation δ pour le délai
δ=délai de propagation de A → B≈délai de propagation de B → A θ=déclagae de A par rapport à B T 2=T 1+δ+θ T 4=T 3+δ−θ (T 2+T 4)=(T 1+T 3)+2∗δ
19/12/2019
δ=
(T 2−T 1)+(T 4−T 3) 2
Systèmes Répartis
53
Network Time Protocol (NTP)
● Les paires de valeurs (θ, δ) sont mises en mémoire tampon, prenant finalement la valeur minimale trouvée pour δ comme meilleure estimation du délai entre les deux serveurs, puis la valeur associée θ comme estimation la plus fiable du décalage.
19/12/2019
Systèmes Répartis
54
Network Time Protocol (NTP)
● L’application symétrique de NTP devrait en principe permettre également
à B d’ajuster son horloge sur celle de A.
● Toutefois, si l’horloge de B est réputée être plus précise, un tel ajustement
serait alors ridicule.
Publicité
● Pour résoudre ce problème, NTP divise les serveurs en strates.
– Un serveur avec une horloge de référence, telle qu'un récepteur UTC ou une
horloge atomique, est connu pour être un serveur de strate-1 (on dit que l'horloge elle-même fonctionne à la strate 0).
– Lorsque A contacte B, il ajuste uniquement son heure si son propre niveau de
strate est supérieur à celui de B.
– En outre, après la synchronisation, le niveau de strate de A devient supérieur à
celui de B.
– En d'autres termes, si B est une strate -k serveur, alors A deviendra une strate- (k +
1) serveur si son niveau de strate d'origine était déjà supérieur à k.
– En raison de la symétrie du NTP, si le niveau de la strate de A était inférieur à celui
de B, B s’ajustera à A.
19/12/2019
Systèmes Répartis
55
Network Time Protocol (NTP)
19/12/2019
Systèmes Répartis
56
L’algorithme de Berkley
● Dans de nombreux algorithmes de synchronisation d'horloge, le serveur de temps est passif. D'autres machines lui demandent périodiquement l'heure. Tout ce qu'il fait est de répondre à leurs questions.
● Dans le système Unix de Berkley, l'approche
exactement opposée est adoptée.
● Ici, le serveur de temps (en fait, un démon de temps) est actif, interrogeant chaque machine de temps à autre pour lui demander quelle heure il est là.
19/12/2019
Systèmes Répartis
57
L’algorithme de Berkley
● Sur la base des réponses,
– il calcule une durée moyenne
– et demande à toutes les autres machines d’avancer leurs horloges vers
la nouvelle heure
– ou de ralentir leur horloge jusqu’à ce qu’une réduction spécifiée soit
atteinte.
● Cette méthode convient aux systèmes dans lesquels aucune
machine n’est équipée d’un récepteur UTC.
● L’heure du démon de temps doit être définie manuellement par
l’opérateur périodiquement.
19/12/2019
Systèmes Répartis
58
L’algorithme de Berkley
19/12/2019
Systèmes Répartis
59
L’algorithme de Berkley
● Notez que dans de nombreux cas, il suffit que toutes les machines
s’accordent sur le même temps.
– Il n'est pas essentiel que cette heure soit également en accord avec le temps
réel annoncé à la radio toutes les heures.
● Si, dans notre exemple, l’horloge du démon de temps ne serait jamais
calibrée manuellement, aucun dommage n’est causé si aucun des autres nœuds ne communique avec des ordinateurs externes.
● Tout le monde sera simplement d’accord sur une heure actuelle, sans
que cette valeur n’ait aucun rapport avec la réalité.
● L'algorithme de Berkeley est donc typiquement un algorithme de
synchronisation d'horloge interne.
19/12/2019
Systèmes Répartis
60
Les horloges logiques
19/12/2019
Systèmes Répartis
61
Les horloges logiques
● La synchronisation de l'horloge est naturellement liée à l'heure, bien qu'il ne soit peut-être pas nécessaire de disposer du temps réel: il peut suffire que chaque nœud d'un système distribué s'accorde sur une heure actuelle.
● Nous pouvons aller plus loin. Pour exécuter make, il suffit que deux nœuds s'accordent sur le fait que input.o est obsolète avec une nouvelle version de input.c, par exemple.
● Dans ce cas, il est important de garder une trace des événements de chacun (telle que la production d’une nouvelle version de input.c). Pour ces algorithmes, il est classique de parler d'horloges comme des horloges logiques
19/12/2019
Systèmes Répartis
62
Les horloges logiques Processus et systèmes répartis
● Modèle du système réparti :
– Collection de N processus Pi où i = 1, 2, 3, ..., N. – Chaque processus Pi exécute une séquence ordonnée 0 , ei
d’éventements notés: ei
2 , …
1 , ei
– On dit que ei – ei
1 intervient avant ei
2
e⇒ e i
1 < ei
2
1 , ei
2 , … sont des éventements locaux à Pi
● Les événement peuvent prendre trois formes
– Calcul locaux (mise à jours d’une variable,...)
– Émission d’un message à destination d’un autre processus
– Réception d’un message émis par un autre processus
19/12/2019
Systèmes Répartis
63
Les horloges logiques Processus et systèmes répartis
● Les processus sont indépendants ;
– Il n’y a pas de mémoire partagée entre les processus.
● Si: état du processus Pi.
– L’état = valeurs des variables, des ressources ou des
objets locaux utilisés par le processus.
● La communication entre les processus ne se fait
que par transmission de messages.
19/12/2019
Systèmes Répartis
64
Les horloges logiques Processus et systèmes répartis ● Processus Pi : Ensemble des actions (send, receive, calcul local) pouvant modifier l’état d’un processus Si
Si
S’i
Opérations qui modifient l’état d’un processus :
– Calcul local – Envoie d’un message – Réception d’un message
19/12/2019
Systèmes Répartis
65
Les horloges logiques Processus et systèmes répartis
1
e1
2
e1
3
e1
4
e1
1
e2
2
e2
3
e2
P1 P1
P2
P3
19/12/2019
Systèmes Répartis
66
1
e3
2
e3
Les horloges logiques Processus et systèmes répartis
1
e1
2
e1
3
e1
4
e1
1
e2
2
e2
3
e2
P1 P1
P2
P3
Des événement locaux
1
e3
2
e3
19/12/2019
Systèmes Répartis
67
Les horloges logiques Processus et systèmes répartis
1
e1
2
e1
3
e1
4
e1
1
e2
2
e2
3
e2
P1 P1
P2
P3
Des réceptions de messages
1
e3
2
e3
19/12/2019
Systèmes Répartis
68
Les horloges logiques Processus et systèmes répartis
1
e1
2
e1
3
e1
4
e1
1
e2
2
e2
3
e2
P1 P1
P2
P3
Des émissions de messages
1
e3
2
e3
19/12/2019
Systèmes Répartis
69
Les horloges logiques Évènements dans un système réparti ● Un évènement est l’occurrence d’une seule action
– Un évènement modifie l’état d’un processus.
● L’ordre total unique des évènements est noté : →
– e → e’ si et seulement si l’événement e est survenu avant e’
dans Pi
● Historique de Pi est une série d’évènements survenus
dans Pi et ordonnés par la relation → – History(Pi) = hi = < e0
i , ... >
i , e1
i , e2
19/12/2019
Systèmes Répartis
70
La causalité
● Définition Larousse : « Lien qui unit la cause à l'effet. »
● Définition CNRTL : « Rapport de la cause à son effet.
Principe de causalité en vertu duquel tout phénomène a une cause. »
● Wikipédia : « En physique, le principe de causalité
affirme que si un phénomène (nommé cause) produit un autre phénomène (nommé effet), alors la cause précède l'effet (ordre temporel) »
19/12/2019
Publicité
Systèmes Répartis
71
Les horloges logiques
● Dans un article phare publié en 1978 (voir ci-dessous), Lamport a
montré que, bien que la synchronisation d'horloge soit possible, elle ne doit pas nécessairement être absolue.
● Si deux processus n'interagissent pas, il n'est pas nécessaire que
leurs horloges soient synchronisées car le manque de synchronisation ne serait pas observable et ne pourrait donc pas causer de problèmes.
● En outre, il a souligné que l’important n’est généralement pas que tous les processus s’accordent sur l’heure exacte, mais plutôt sur l’ordre dans lequel les événements se produisent.
– Dans l'exemple de création, ce qui compte est de savoir si input.c est plus ancien ou
plus récent que input.o, et non leurs temps de création absolus respectifs.
Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565. DOI=http://dx.doi.org/10.1145/359545.359563
19/12/2019
Systèmes Répartis
72
Les horloges logiques de Lamport
● Pour synchroniser les horloges logiques, Lamport a défini une relation
appelée se produit-avant (happens before).
● L'expression a → b est lue «l'événement a se produit avant l'événement b» et signifie que tous les processus conviennent que le premier événement a se produit, puis l'événement b se produit. La relation se produit-avant peut être observée directement dans deux situations:
– 1. Si a et b sont des événements du même processus et que a se produit avant b,
alors a → b est vrai.
– 2. Si a est l'événement d'un message envoyé par un processus et b est l'événement de la réception du message par un autre processus, alors a → b est également vrai. Un message ne peut pas être reçu avant son envoi, ni même en même temps
19/12/2019
Systèmes Répartis
73
Les horloges logiques de Lamport
● produit-avant (happens before) est une relation transitive, donc si a → b et b → c, alors a → c.
● Si deux événements, x et y, se produisent dans des
processus différents qui n'échangent pas de messages (même indirectement via des tiers), alors x → y n'est ni vrai ni fausse
– Ces événements sont dits concurrent, ce qui signifie
simplement que rien ne peut être dit (ou n'a pas besoin d'être dit) sur le moment où les événements se sont produits ou quel événement est survenu en premier.
19/12/2019
Systèmes Répartis
74
Les horloges logiques de Lamport
a et b sont locaux à un même processus & a se produit avant b
a → b
∃ un message m / a : émission(m) & b : réception(m)
∃ un évnement c / a → c & c → b
19/12/2019
Systèmes Répartis
75
Les horloges logiques de Lamport
P1 P1
P2
P3
1
e1
e1
2 e1
3
4
e1
e2
1 e2
2
3
e2
1
e3
2
e3
e1
1 → e1
2
e2
1 → e2
2
e2
2 → e1
2
e1
3→ e3
1
e2
1 → e1
2
19/12/2019
Systèmes Répartis
76
Les horloges logiques de Lamport
● Ce dont nous avons besoin, c'est d'un
moyen de mesurer une notion de temps telle que, pour chaque événement, nous pouvons lui attribuer une valeur de temps C (a) sur laquelle tous les processus s'accordent.
● Ces valeurs de temps doivent avoir la
propriété que si a → b, alors C (a) < C (b).
19/12/2019
Systèmes Répartis
77
Les horloges logiques de Lamport
● Pour reformuler les conditions énoncées précédemment, si a et b
sont deux événements dans le même processus et a se produit avant b, alors C (a) < C (b).
● De même, si a est l'envoi d'un message par un processus et que b est la réception de ce message par un autre processus, alors C (a) et C (b) doivent être attribués de manière à ce que tout le monde s'accorde sur les valeurs de C (a) et C (b) avec C (a) <C (b).
● De plus, le temps d'horloge, C, doit toujours avancer (augmenter),
jamais reculer (diminuer).
– Des corrections au temps peuvent être apportées en ajoutant une valeur
positive, jamais en soustrayant une.
19/12/2019
Systèmes Répartis
78
Les horloges logiques de Lamport
● Examinons maintenant l’algorithme proposé par Lamport pour
attribuer des heures aux événements.
● Considérons les trois processus P1, P2 et P3.
● Les processus s'exécutent sur différentes machines, chacune
avec sa propre horloge.
19/12/2019
Systèmes Répartis
79
Les horloges logiques de Lamport
● Nous supposons qu'une horloge est implémentée en tant que compteur logiciel: le compteur est incrémenté d'une valeur spécifique toutes les T unités de temps.
● Cependant, la valeur par laquelle une horloge est incrémentée diffère selon le
processus.
● L'horloge du processus P 1 est incrémentée de 6 unités, 8 unités du processus P
2 et 10 unités du processus P 3, respectivement.
19/12/2019
Systèmes Répartis
80
Les horloges logiques de Lamport
● A l'instant 6, le processus P1 envoie le message m1 au processus P2.
– L'horloge du processus P2 lit 16 à son arrivée.
● Si le message porte l'heure de début, le processus P2 en conclura qu'il lui a fallu
10 tics pour effectuer le trajet.
– Cette valeur est certainement possible.
● Selon ce raisonnement, le message m2 de P2 à P3 prend 16 tics, encore une
valeur plausible.
19/12/2019
Systèmes Répartis
81
Les horloges logiques de Lamport
● Considérons maintenant le message m3. Il quitte le
processus P3 à 60 et arrive à P2 à 56.
● De même, le message m4 de P2 à P1 part de 64 et arrive à 54.
● Ces valeurs sont clairement impossibles.
19/12/2019
Systèmes Répartis
82
Les horloges logiques de Lamport
● La solution de Lamport découle directement de la relation se produit-avant.
– Comme m3 est parti à 60, il doit arriver à 61 ou plus tard.
● Lorsqu'un message arrive et que l'horloge du destinataire indique une valeur antérieure à l'heure d'envoi du message, le destinataire avance rapidement son horloge à une heure de plus que l'heure d'envoi.
– Dans la figure ci-dessous, nous voyons que m3 arrive maintenant à 61. De même,
m4 arrive à 70.
19/12/2019
Systèmes Répartis
83
Les horloges logiques de Lamport
19/12/2019
Systèmes Répartis
84
Les horloges logiques de Lamport récapitulons
● Idée :
– Chaque événement (e) se voit associer une
horloge C(e)
– e → é
⇒ e
C(e) < C(é)
– Afin de permettre aux processus d’estampiller les événements qu’ils exécutent, Lamporte propose l’algorithme suivant :
19/12/2019
Systèmes Répartis
85
Les horloges logiques de Lamport
● Initialement : chaque Processus Pi a une
horloge Ci initialisé à 0
–
∀ i, Pi , CPi ←0
● Lorsqu’un événement local (e) à Pi se produit
– Pi incrément son horloge Cpi ← Cpi + 1 – Utilise cette horloge pour estampiller l’événement
C(e) ← Cpi
19/12/2019
Systèmes Répartis
86
Les horloges logiques de Lamport
● Émission d’un message m par Pi
– Pi incrémente son horloge : Cpi ← Cpi + 1 – Utilise cette horloge pour estampiller l’événement C(e) ← Cpi – Ajoute dans le message l’estampille ts(m) ← C(e)
● Réception d’un message m ayant l’estampille ts(m) (m, ts(m))
– Mets à jours son horloge Cpi = max( Cpi , ts(m)) +1 – Utilise cette horloge pour estampiller l’événement C(e) ← Cpi
19/12/2019
Systèmes Répartis
87
Exemple des horloges de Lamport
P1 P1
P2
P3
1
e1
2
e1
1
e2
2
e2
1
e3
3
e2
2
e3
19/12/2019
Systèmes Répartis
88
Exemple des horloges de Lamport
3=max(0,2) +1 3 e1 1
0
4 e1
2
0
0
m(2)
1
2
1
e2
2
e2
m(4)
1
1
e3
3
3
e2
5
2
e3
P1 P1
P2
P3
19/12/2019
Systèmes Répartis
89
Les horloges logiques de Lamport une deuxième versio