volume de stockage important sur C.On veut implémenter un système de messagerie.
Un usager doit pouvoir émettre ou retirer des messages de n'importe quelle station.
Plusieurs implémentations possibles.
Tous les courriers sont stockés sur C (station centrale).
1 usager = 1 boîte aux lettres sur C.
volume de stockage important sur C.
disponibilité du service = disponibilité de C.
1 opération = 1 transfert d'informations.
Retrait d'un message sur station de rattachement = opération locale.
Dep\^ot ou retrait sur une autre station échange d'informations.
dictionnaire Usager/Station-de-rattachement.
Disponibilité du système accrue.
Panne d'une station = empêche la réception des messages pour les usagers de cette station.
Volume de stockage global réparti sur l'ensemble des stations.
Une copie du répertoire sur chaque machine (attention à la mise-à-jour).
On ajoute des stations relais.
Une station est reliée à une station relai et une seule.
Le relai stocke les messages des stations qui lui sont rattachées.
Tout usager dépend donc d'un seul relai.
Un message passe forcement par un relai.
Seuls les relais possèdent un dictionnaire.
Panne d'un relai pénalise un ensemble d'usagers.
Moins de répertoires à mettre à jour.
Avantage : si une fraction importante du nombre de messages est échangée entre les utilisateurs d'un même relai.
Un station peut être un simple terminal.
En résumé : on préfère définir un système réparti par les services qu'il offre :
Comment faire pour savoir qu'un evènement e de P_1 s'est déroulé avant (ou après) un evènement e' de P_1 ?
Il n'existe pas d'horloge commune (ou temps global).
À un instant donné, quel est l'état du système ?
Il faut que les processus échangent des messages.
1. Parking avec un accès unique, surveillé par un seul gardien : connaissance partielle de la situation
refus d'entrer alors qu'une voiture est en route vers la sortie.
2. Plusieurs accès avec un gardien à chaque accès : chaque gardien connaît avec retard les actions des autres gardiens
2 voitures sont autorisées à rentrer alors qu'il y a 1 seule place libre.
les gardiens doivent coopérer.
Ordre local des évènements :
A1 
A2 A3 A4 A5
B1 B2 B3 B4
Échanges de messages :
A2 B2 et B3 A4
Transitivité :
A1 A2 B2 B3 B4
B1 B2 B3 A4 A5
A1 A2 B2 B3 A4 A5
Exemples d'évènements incomparables :
B1 et A1, A2, A3
A3 et B2, B3, B4
NP = nombre de productions et NC = nombre de consommations.
C peut consommer ssi NP-NC > 0.
P peut produire ssi NP-NC < N.
Implémentation :
Primitives :
- 2 variables entières NP et NC initialisées à 0.
|
|
On doit pouvoir avoir un ordre total strict.
Par exemple : allocation de ressources.
En centralisé : les requêtes et avis de libération sont ordonnés dans une file manipulée en Exclusion-Mutuelle, puis traitées en séquence.
En réparti :
Les trois gardiens diffusent les messages suivants :
| Ordre d'envoi | Séquence 1 (msg, valeur) | Séquence 2 (msg, valeur) | Séquence 3 (msg, valeur) | Séquence 4 (msg, valeur) |
|---|---|---|---|---|
| init | -, 100 | -, 100 | -, 100 | -, 100 |
| 1 | M1, 120 | M1, 120 | M3, 90 | M2, 90 |
| 2 | M3, 108 | M2, 110 | M1, 110 | M3, 81 |
| 3 | M2, 98 | M3, 99 | M2, 100 | M1, 101 |
| final | -, 98 | -, 99 | -, 100 | -, 101 |
Cette estampille est la valeur instantannée, sur le site d'émission, d'une horloge logique locale à ce site.
Les horloges des différents sites sont recalées grâce à un dialogue.
Construction d'un ordre total strict [Lamport 78] :
Chaque site s est munie d'un compteur à valeurs entières H_s, appelé horloge logique.
H_s est incrémenté entre deux évènements successifs.
Un site e qui émet un message le marque d'une estampille E égale à la valeur courante de H_e.
À la réception du message, le site récepteur r met-à-jour H_r ainsi :
si H_r < E alors H_r := E+1 finsi
L'évènement << réception du message >> est daté par H_r.
On a une relation d'ordre total
Soient a et b deux évènements des sites (resp.) i et j alors :
a b 
H_i(a) < H_j(b)
Pour avoir un ordre total et strict
On associe le numéro du site à l'estampille.
a b (H_i(a) < H_j(b)) ou (H_i(a) < H_j(b) et i < j)
On veut répartir l'algorithme ( i.e. pas de site central).
une file par site.
Chaque site reçoit les requêtes et avis de libération de tous les autres sites.
On veut un ordre total strict (estampillage par horloge logique + numéro de site).
Pour qu'un site puisse prendre sa décision, il doit avoir reçu un message de chaque autre site (pas de message en transit).
Les envois de messages :
H_init est la même pour tous les sites.
Si un site reçoit (REQ, H_i, i) ou (REL, H_i, i), ce message remplace M_i.
Si un site reçoit (ACQ, H_i, i), ce message remplace M_i sauf si M_i est un (REQ, H_i, i).
Le site i peut rentrer en SC si sa requête (REQ, H_i, i) précède tous les autres messages de la file d'attente.
Retour au sommaire.
