Chapitre IV :
Coordination
Syst mes R partis
Amine DHRAIEF
1 re ann e Master
Contexte : Le temps
Depuis 1967, la seconde nest plus d finit par rapport
lann 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 latome 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 lhorloge du satellite
et lhorloge du
r cepteur peut avoir un
impact d sastreux sur la
navigation mondiale
Un d calage dune
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 ny a pas dhorloge 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 lauthenticit 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 quun
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, lobjectif est de g rer les
interactions et les d pendances entre les activit s dun
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 lhorloge
19/12/2019
Syst mes R partis
18
La synchronisation de lhorloge
Dans un syst me centralis , le temps nest 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 lhorloge
Imaginons un instant les cons quences de labsence dune 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 na 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 lhorloge
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 lhorloge
Maintenant, imaginez ce qui pourrait arriver dans un syst me
distribu dans lequel il ny 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
Advertisement
essayant de comprendre ce qui ne va pas avec le code.
Syst mes R partis
22
La synchronisation de lhorloge
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 lexemple de make).
19/12/2019
Syst mes R partis
29
Horloge physique
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 dheure 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 106 ), 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 dun 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 lhorloge
Algorithmes de synchronisation d'horloge
19/12/2019
Syst mes R partis
32
Algorithmes de synchronisation
d'horloge
Si une machine est quip e dun r cepteur UTC,
lobjectif 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 dun ordinateur est d riv e de
lhorloge mat rielle de cet ordinateur.
Lhorloge 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
dhorloges
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) | d
19/12/2019
Syst mes R partis
36
Objectif des algorithmes de synchronisation
dhorloges
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 dexactitude
(accuracy), dans le but de la maintenir inf rieur
une valeur :
t,
p: | Cp(t) - t | d
19/12/2019
Syst mes R partis
37
Objectif des algorithmes de synchronisation
dhorloges
L'id e m me de la synchronisation
d'horloge est que nous gardons des
horloges pr cises (precise) ou exacte
(accurate)
Advertisement
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
dhorloges
Un ensemble d'horloges qui sont exactes dans une
limite , seront pr cis dans une limite = 2 .
|C p(t )t|d
|C q(t )t|d
|C p(t )C q(t )|d2 =
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
dhorloges
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 nest 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 lordre
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
dhorloges
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 loscillateur de
lhorloge mat rielle linstant t et F sa fr quence
id ale (constante), une horloge mat rielle est
conforme ses sp cifications si :
t ,1 d
F (t )
F
d1+
19/12/2019
Syst mes R partis
41
Objectif des algorithmes de synchronisation
dhorloges
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 d
19/12/2019
dCp(t )
dt
Syst mes R partis
d1+
42
Objectif des algorithmes de synchronisation
dhorloges
19/12/2019
Syst mes R partis
43
Objectif des algorithmes de synchronisation
dhorloges
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:146158, 1989.) est de laisser les clients contacter un
serveur de temps.
Ce dernier peut fournir avec pr cision lheure actuelle, en
l quipant dun r cepteur UTC ou dune horloge atomique.
Le probl me, bien s r, est que lorsquun 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 lheure de
larriv 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 2T 1CT 4T 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 BHd lai de propagation de B A
=d clagae de A par rapport B
T 2=T 1+ +
T 4=T 3+
(T 4T 2)=(T 3T 1)2
= (T 2T 1)+(T 3T 4)
2
19/12/2019
Syst mes R partis
49
=d lai de propagation de A BHd lai de propagation de B A
=d clagae de A par rapport B
T 2=T 1+ +
T 4=T 3+
(T 4T 2)=(T 3T 1)2
= (T 2T 1)+(T 3T 4)
2
19/12/2019
Syst mes R partis
50
Network Time Protocol (NTP)
Si lhorloge 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 lhorloge 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 lheure.
Lors du ralentissement, la routine dinterruption najoute 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 BHd 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 2T 1)+(T 4T 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)
Lapplication sym trique de NTP devrait en principe permettre galement
Advertisement
B dajuster son horloge sur celle de A.
Toutefois, si lhorloge de B est r put e tre plus pr cise, un tel ajustement
serait alors ridicule.
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 sajustera A.
19/12/2019
Syst mes R partis
55
Network Time Protocol (NTP)
19/12/2019
Syst mes R partis
56
Lalgorithme 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
Lalgorithme de Berkley
Sur la base des r ponses,
il calcule une dur e moyenne
et demande toutes les autres machines davancer leurs horloges vers
la nouvelle heure
ou de ralentir leur horloge jusqu ce quune r duction sp cifi e soit
atteinte.
Cette m thode convient aux syst mes dans lesquels aucune
machine nest quip e dun r cepteur UTC.
Lheure du d mon de temps doit tre d finie manuellement par
lop rateur p riodiquement.
19/12/2019
Syst mes R partis
58
Lalgorithme de Berkley
19/12/2019
Syst mes R partis
59
Lalgorithme de Berkley
Notez que dans de nombreux cas, il suffit que toutes les machines
saccordent 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, lhorloge du d mon de temps ne serait jamais
calibr e manuellement, aucun dommage nest caus si aucun des
autres nSuds ne communique avec des ordinateurs externes.
Tout le monde sera simplement daccord sur une heure actuelle, sans
que cette valeur nait 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 nSud d'un syst me distribu s'accorde sur
une heure actuelle.
Nous pouvons aller plus loin. Pour ex cuter make, il suffit que deux
nSuds 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 dune 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 dune variable,...)
mission dun message destination dun autre processus
R ception dun 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 ny 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
dun processus Si
Si
Si
Op rations qui modifient l tat dun processus :
Calcul local
Envoie dun message
R ception dun 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
Advertisement
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 loccurrence dune seule action
Un v nement modifie l tat dun processus.
Lordre 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
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 limportant nest g n ralement pas que tous
les processus saccordent sur lheure exacte, mais plut t sur lordre
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 lalgorithme 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 messag...