Temps Logique

 Introduction aux systèmes distribués
 Le temps logique dans les systèmes

distribués
 Exclusion mutuelle et exclusion mutuelle du

groupe
 Interblocage
1
 Le temps logique dans les systèmes distribués
Introduction
✓ Un Système distribué 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.
✓ Système = ensemble de processus (1 par site) + canaux de

communication
✓ Processus = séquence d’événements locaux + mémoire locale + horloge
locale
✓ Evénement = changement d’état du processus (événement interne), ou
émission d’un message, ou réception d’un message
2
Introduction (1)
✓ Une horloge locale unique permet de dater chacun des événements. Tous
les événements ont des dates différentes. Mais, dans les systèmes
distribués., 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
événements est parfois primordial
Exemples:
✓ Un message ne peut pas avoir une date de réception antérieure à sa date
d’émission.
✓ Deux sites modifient une donnée partagée. Quelle est la modification la
plus récente?
3
Introduction (2)
Il est donc nécessaire de définir des méthodes qui permettent d’assurer une
relation causale entre les différents événements. Pour cela, il faut définir un
temps global cohérent et « identique » (ou presque) pour tous les processus:
➢ Soit synchroniser au mieux les horloges physiques locales avec une
horloge de référence ou entre elles
➢ Soit créer un temps logique
4
Temps logique
➢ Ordonner les évènements dans un système distribué;
➢ Chaque processeur maintient une horloge locale;
➢ Pas de point central pour fournir le temps ;
➢ Ne donne pas le temps d’un évènement, elle s’intéresse à
préciser les évènements qui se sont déroulés avant ou après
5
Temps logique: Relation de causalité
➢ Il y a une dépendance causale entre 2 événements si un

événement doit avoir lieu avant l'autre
➢ La notation: e → e’ signifie « l’évènement e a eu lieu avant
l’évènement e’ »
➢ Si A → B, alors une des trois conditions suivantes doit être
vérifiée pour A et B
6
1. A et B ont lieu sur le même site et A s’est produit avant B
2. A est l’émission d’un message et B sa réception
3. Il existe un événement C tel que A → C et C → B
7
Temps logique: Relation de concurrence
➢ Deux évènements E1 et E2 sont concurrents si et seulement si ils n’ont
pas de relation de précédence, ce qui se note E1E2
L’évènement E1 et E2 peuvent se dérouler dans n’importe quel ordre, c’est-
à-dire E1E2  (E1→E2)  (E2→E1).
➢ Une relation de concurrence est aussi appelée relation de parallélisme. Le
parallélisme logique ne signifie pas que les 2 événements se déroulent
simultanément mais qu'ils peuvent se dérouler dans n'importe quel ordre.
8
Temps logique: Relation de concurrence
➢ Ordonnancement des événements
o Les dépendances causales définissent des ordres partiels pour l’
ensemble d'événements
➢ But d'une horloge logique
o Créer un ordre total global sur tous les événements de tous les
processus
➢ Horloge logique
o Fonction H(e) : associe une date à chaque événement
o Respect des dépendances causales

9
Temps logique:Relation de causalité

chronogramme
10
Répondez aux questions suivantes en se basant sur le chronogramme ci-

dessus
Existe t–il un ordre causal entre a et b ?
Existe t–il un ordre causal entre a et i ?
Existe t–il un ordre causal entre a et o ?
Existe t–il un ordre causal entre c et n ?
11
Deux évènements liés par la relation de causalité appartiennent à un
chemin causal. Par exemple, a et o appartiennent au chemin causal
a, b, c, d, e, o
De manière plus générale, si on considère pour un évènement donné,
l'ensemble de tous ses prédécesseurs, on obtient l'ensemble de tous
les évènements qui en sont la cause [potentielle].
12
Temps logique
Horloges logiques (Algorithme de Lamport, 1978)
On s'intéresse ici à construire un ordre total qui soit cohérent avec la relation
de causalité. Pour cela, on associe à chaque évènement une estampille telle
que si on compare les estampilles de 2 évènements, 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 évènement E est notée d(E).
✓ Pour chaque évènement E ne correspondant pas à l'envoi ou à la
réception d'un message, le site Si incrémente l'horloge locale Hi de 1 et
date cet évènement par d(E) = Hi.
13
Temps logique
✓ Lors de l'émission d'un message M par Si, on incrémente l'horloge locale
Hi de 1, on estampille M par (Hi, i) et on date l‘émission par d(E) = Hi.
✓ Lors de la réception d'un message estampillé (Hj, j) par Si, Si recale son
horloge locale de la manière suivante:
▪ Si Hi < Hj, alors Hi = Hj + 1

▪ Sinon Hi = Hi + 1
On a ensuite d(E) = Hi.
La date globale d(E) d'un évènement E est alors (d(E), i) où i est
le numéro du site où a lieu l‘ évènement et d(E) sa date locale.
14
Temps logique
Ce système d'estampillage est très intéressant lorsque le problème à
résoudre nécessite un ordre total sur les évènements respectant les relations
de causalité qui les lient. C'est le cas par exemple de l'exclusion mutuelle.
Si H est la valeur d'horloge associée à un évènement A, alors il y a
exactement H - 1 évènements 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‘ évènements qui peuvent avoir lieu avant que A se produise.
L’horloge de lamport respecte la dépendance causale e → e’ h(e)h(e’)
Mais non sa réciproque h(e)(he’) n’implique pas forcement que e→e’
15
1. Donner les horloges de Lamport des évènements représentés ci-

dessus
2. e11 et e31 sont-ils causalement ordonnés?
3. Idem pour e13 et e34?
4. Quel rapport avec leurs estampilles?
16
17
Trois principaux avantages :

❑ Première datation répartie introduite en informatique
❑ Économiques : la datation est réalisée par un seul nombre et
non par un vecteur
❑ Causalité des messages est respectée par remise à l'heure
du récepteur
18
Limitations de l’algorithme
E1‐> E2 implique H(E1) < H(E2) est une condition faible, car on
ne peut rien affirmer si H(E1) < H(E2)
❑ soit les évènements E1 et E2 sont concurrents
❑ soit les évènements E1 et E2 sont ordonnés
Les estampilles ne sont pas “denses” => Horloge de Lamport
respecte les dépendances causales mais avec e et e' tel que
H(e) < H(e') on ne peut rien dire sur la dépendance entre e et e'
19

Cette technique permet donc d'associer à chaque événement une date
(estampille logique) correspondant à la valeur de l'horloge de son site
modifiée selon les règles que nous venons de définir. On peut observer que :
▪ l'ordre des événements qui est ainsi défini n'est pas un ordre strict :
plusieurs événements peuvent porter la même valeur. C'est le cas (parmi
d'autres) sur notre exemple des événements e34 et e13 appartenant
respectivement à S3 et S1 qui ont chacun 6 comme date. Il est facile de
rendre cet ordre strict en modifiant légèrement le système de datation : la
date d'un événement sur un site est obtenue en adjoignant à la valeur de
l'horloge scalaire de ce site l'identification du site (par exemple un entier
attribué artificiellement ou une adresse IP ou physique)
20
Horloges vectorielles (Fidge et Mattern, 1988)
L'objectif est ici d'obtenir une caractérisation simple de la relation de
causalité au moyen d'une horloge logique, donc de faire en sorte que la
propriété : si e → f, alors h(e) → h(f) admette une réciproque. Il est bien
évident que la relation d'ordre sur les horloges ne peut pas être totale comme
celle sur les entiers. On définit donc une fonction H qui associe à tout
événement e un vecteur de nombres entiers indicé par l'ensemble des sites
de la manière suivante :
21
✓ Chaque site i possède un vecteur H(i) à n composantes (n étant le
nombre de sites du réseau), initialisé à (0,0, ..., 0)
✓ Sur le site i, avant chaque événement interne ou envoi de message, la i-
ème composante de ce vecteur est incrémentée.
✓ Tout message émis par i transporte la valeur du vecteur H(i)
✓ Lors de la réception par i d'un message daté par le vecteur H, on recale
les horloges par H(i)[k] = Max (H(i)[k], H[k] ) , pour tout k allant de 1 à n, et
de plus la ième composante H(i)[i] est incrémentée.
22
Dépendance et indépendance causales
Horloge de Mattern assure les propriétés suivantes, avec e et e' deux
événements et V(e) et V(e') leurs datations.
❑ V(e) < V(e') ⇒ e → e’.

✓ Si deux dates sont ordonnées, on a forcément dépendance causale
entre les événements datés.
❑ V(e) || V(e') ⇒e || e'.

✓ Si il n’y a aucun ordre entre les 2 dates, les 2 événements sont
indépendants causalement (les 2 événements sont en parallèle).
23

Exemple 1
24
Coupure et état global cohérent dans un système réparti
❑ Etat global
État du système à un instant donné, défini à partir de coupures.
▪ Buts de la recherche d’états globaux : trouver des états cohérents à partir
desquels on peut reprendre un calcul distribué en cas de plantage du système.
❑ Coupure : photographie à un instant donné de l’état du système. Un état est
associé à une coupure.
▪ Définit les événements appartenant au passé et au futur par rapport à
l’instant de la coupure.
25
❑ Coupure
▪ Coupure = les événements appartenant au passé par rapport à l’instant de la
coupure.
❑ Calcul distribué = ensemble E d’événements.
❑ Coupure C est un sous-ensemble fini de E tel que :
❑ Si un événement d’un processus appartient à la coupure, alors tous les
événements locaux le précédant y appartiennent également.
26
❑ Exemple coupure
27
▪ Frontière
La frontière F d'une coupure C est l'ensemble des évènements les plus récents de la
coupure, un sur chaque site.
Un évènement a appartient à F si et seulement si a appartient à C et qu'il n'existe
aucun évènement b appartenant à C tel que a → b.
▪ Coupure/ état cohérent
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.
28
Exemple
On considère les deux coupures C1 et C2 dans la figure ci-dessous. Les

coupures C1 et C2 sont-elles cohérentes?
29
Dépendance causale entre messages
On considère que send(m) et receive(m) correspondent à l'émission et la

réception d'un message m et que les messages doivent respecter la
dépendance causale.
Définitions:
Les communications sont ordonnées causalement (Causal Ordered), si, pour
tout message m et m', on a :
send(m) → send(m') ⇒ receive (m) → receive (m')
30
Exemple 2
La réception sur P2 respecte t-il la dépendance causale des messages?
31
Exemple2
Y a t-il la dépendance causale des messages?
32
Horloges matricielles
❑ n processus : matrice M de (n x n) pour dater chaque événement.
❑ Sur processus Pi :
Ligne i : informations sur événements de Pi :
❑ Mi [ i , i ] : nombre d’événements réalisés par Pi.
❑ Mi [ i , j ] : nombre de messages envoyés par Pi à Pj (avec j ≠ i).
Ligne j (avec j ≠ i) :
❑ Mi [ j , j ] : nombre d’événements que l’on connaît sur Pj.

❑ Mi [ j , k ] : nombre de messages que l’on sait que Pj a envoyé à Pk (avec
j ≠k)
33
❑ Avec 3 processus (sur le processus P2):
34
✓ lorsqu'un événement local se produit sur le site Si , HMi [i,i] est
incrémenté;
✓ lorsqu'un message est expédié à partir du site Si vers le site Sj , HMi [i,i]
et HMi [i, j] sont incrémentés;
✓ lorsqu'un message m en provenance du site Sj est reçu sur le site Si il
faut s'assurer que tous les messages envoyés antérieurement au site Si y
sont effectivement arrivés. Cela suppose donc que Si ait reçu d'une part
tous les messages précédents de Sj et d'autre part tous ceux envoyés
plutôt causalement depuis d'autres sites. Cela correspond aux conditions
suivantes:
▪ HMm[j,i] = HMi[j,i] + 1 (ordre FIFO sur le canal (j,i))
35
▪ pour tout k # i et j , HMm[k,i] = HMi[k,i] (tous les messages des sites
différents de Sj ont été reçus)
- Si toutes ces conditions sont vérifiées, le message est délivrable et
l'horloge du site Sj est mise à jour:
▪ HMi[i,i]++ (incrémentation);
▪ HMi[j,i]++ (incrémentation);
▪ pour tout k # i et j et pour tout l # i , HMi[k,l] = max(HMi[k,l], EMm[k,l])
36
P1
P2
P3
37
38

Temps Logique

Transféré par

Droits d'auteur :

Formats disponibles

Temps Logique

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Temps Logique

Transféré par

Droits d'auteur :

Formats disponibles

 Introduction aux systèmes distribués

 Le temps logique dans les systèmes

 Exclusion mutuelle et exclusion mutuelle du

✓ Système = ensemble de processus (1 par site) + canaux de

➢ Soit synchroniser au mieux les horloges physiques locales avec une

horloge de référence ou entre elles

➢ Soit créer un temps logique

➢ Ordonner les évènements dans un système distribué;

➢ Chaque processeur maintient une horloge locale;

➢ Pas de point central pour fournir le temps ;

➢ Ne donne pas le temps d’un évènement, elle s’intéresse à

préciser les évènements qui se sont déroulés avant ou après

Temps logique: Relation de causalité

➢ Il y a une dépendance causale entre 2 événements si un

Temps logique: Relation de causalité

1. A et B ont lieu sur le même site et A s’est produit avant B

2. A est l’émission d’un message et B sa réception

3. Il existe un événement C tel que A → C et C → B

Temps logique: Relation de concurrence

➢ Deux évènements E1 et E2 sont concurrents si et seulement si ils n’ont

pas de relation de précédence, ce qui se note E1E2

L’évènement E1 et E2 peuvent se dérouler dans n’importe quel ordre, c’est-

à-dire E1E2  (E1→E2)  (E2→E1).

➢ Une relation de concurrence est aussi appelée relation de parallélisme. Le

parallélisme logique ne signifie pas que les 2 événements se déroulent

simultanément mais qu'ils peuvent se dérouler dans n'importe quel ordre.

Temps logique: Relation de concurrence

➢ Ordonnancement des événements

o Les dépendances causales définissent des ordres partiels pour l’

➢ But d'une horloge logique

o Fonction H(e) : associe une date à chaque événement

o Respect des dépendances causales

Temps logique:Relation de causalité

Temps logique: Relation de causalité

Répondez aux questions suivantes en se basant sur le chronogramme ci-

Existe t–il un ordre causal entre a et b ?

Existe t–il un ordre causal entre a et i ?

Existe t–il un ordre causal entre a et o ?

Existe t–il un ordre causal entre c et n ?

Temps logique: Relation de causalité

Deux évènements liés par la relation de causalité appartiennent à un

chemin causal. Par exemple, a et o appartiennent au chemin causal

De manière plus générale, si on considère pour un évènement donné,

l'ensemble de tous ses prédécesseurs, on obtient l'ensemble de tous

les évènements qui en sont la cause [potentielle].

▪ Si Hi < Hj, alors Hi = Hj + 1

Horloges logiques (Algorithme de Lamport, 1978)

1. Donner les horloges de Lamport des évènements représentés ci-

Horloges logiques (Algorithme de Lamport, 1978)

Horloges logiques (Algorithme de Lamport, 1978)

Trois principaux avantages :

Horloges logiques (Algorithme de Lamport, 1978)

Horloges logiques (Algorithme de Lamport, 1978)

Horloges vectorielles (Fidge et Mattern, 1988)

L'objectif est ici d'obtenir une caractérisation simple de la relation de

causalité au moyen d'une horloge logique, donc de faire en sorte que la

propriété : si e → f, alors h(e) → h(f) admette une réciproque. Il est bien

événement e un vecteur de nombres entiers indicé par l'ensemble des sites

Horloges vectorielles (Fidge et Mattern, 1988)