0.
Un séquenceur S délivre une valeur entière 0.
Fonction ticket(S).
Deux propriétés :
P1 : si a et b deux opérations ticket(S) alors a > b ou b > a.
P2 : si a est une exécution de t = ticket(S) alors t est le nombre d'opérations ticket(S) qui ont précédé a.
P1 est l'EM sur ticket(S) et P2 est l'absence de trous.
Privilège = valeur courante du séquenceur.
Quand site i possède le privilège, il peut faire ticket(S).
Séquenceur circulant.
Séquenceur sur une voie à diffusion.
Méthode simple = chaque site communique avec 2 sites voisins.
Un numéro unique est attribué à chaque site.
Chaque site i a un voisin successeur suiv(i) et un prédécesseur pred(i).
anneau virtuel.
|
suiv[i]=i+1 mod N
pred[i]=i-1 mod N |
Le privilège tourne toujours dans le même sens.
En cas de panne d'un site reconstruction
de l'anneau reconfiguration (mise
à jour des variables suiv et pred).
Site défaillant remis en route
réinsertion.
Soit K (K > 1).
Sur chaque site i, P_i assure la circulation du privilège.
Chaque P_i a une variable S[i] (0 
S[i]
K-1).
S[i] peut être modifiée par P_i et lue par P_suiv(i).
P_i possède le privilège quand :
S[i]  S[i-1] pour i 0
S[0] = S[N-1] pour i = 0 |
Lorsque P_i possède le privilège il doit l'abandonner au bout d'un temps fini :
|
S[i] := S[i-1] pour i 0
S[0] := S[0] + 1 mod K pour i = 0 |
Équité = chaque processus reçoit le privilège à tour de rôle.
Exemple avec N=3, K=2 et S=000.
Évolution du système = 000 - 1 00 - 11 0 - 111 - 0 11 - 00 1
P_0
1- aucun nouveau front est créé.
2- disparition d'un front regénération
par P_0.
Processus P_0.
impossible de regénérer le front.
Le processus qui joue le rôle de P_0 est le seul tel que pred[i] > i.
Chaque processus est programmé pour jouer le rôle de P_0.
si (pred[i] > i) alors << Comportement selon P_0 >> sinon << Comportement selon P_i >> |
2- réinitialiser S[i].
Il faut que j (j = suiv(i)) n'autorise pas la lecture de S[j] pendant la SC.
si (j < i) alors S[i] := S[j]-1 mod K sinon S[i] := S[j] |
Le privilège = 1 jeton qui circule sur l'anneau.
Le jeton porte la valeur v.
Avant la transmission du jeton :
|
S[j]:=v pour j 0
v := v+1 mod K; S[j]:=v pour j = 0 |
À chaque passage du jeton sur j, une horloge de garde est armée.
Si l'horloge se déclenche, j consulte S[i] (i = pred(j)).
|
si (j > i) et (S[j]
S[i])
ou si (j < i) et (S[j] = S[i]) Alors le jeton est considéré comme perdu. |
j le regénère avec S[i] et réarme son horloge.
1 message envoyé par i est diffusé à tous les sites (y compris i).
Tous les communicateurs classent les messages dans le même ordre.
ordonnancement global.
Chaque site i a un compteur local cpt_i.
Pour se réinsérer, i envoie une requête de réinsertion à j.
j renvoie un message de synchronisation.
Quand le message apparaît dans la file de sortie :
Retour au sommaire.
