3.2.5.2 Les messages utilisés
Dans cet algorithme, on utilise cinq types de
messages:
- Demande (Jeton, i) : envoyé par le site i
vers sa racine lors de la demande de la SC. - Libération (Jeton) :
envoyé par le site i vers sa racine après la
libération de sa SC.
- Accord (Jeton) : envoyé par une racine à
un site demandeur pour lui permettre d'utiliser la ressource critique
demandée.
- Requête (Jeton, i) : envoyé par une racine
i pour demander un jeton supplémentaire d'un
voisin.
- Aide (Jeton, i) : Réponse favorable à une
requête d'un voisin.
3.2.5.3 Les procédures de l'algorithme
Procédure 1: Demander la Section
Critique
1 Début
2
3
Etati ?-Demandeur;
Envoyer Demande (Jeton, i) à
Racinei;
4 Fin
Cette procédure est utilisée lorsqu'un site
simple appartenant à un arbre donné, désire d'entrer en
section critique.
Procédure 2: Réception de Accord
(Jeton)
1 Début
2
3
Etati ?-En SC;
< Entrer en Section Critique>
4 Fin
Lorsqu'un site de l'arbre a déjà
envoyé une demande d'entrer en section critique, il va
recevoir un message de type Accord si sa racine
possède au moins un jeton libre, lors de la réception de ce
message, le site va mettre son état EN SC, et entre à la section
critique.
Finsi
Procédure 3: Libérer la Section
Critique
1 Début
Etati ?-Dehors;
Envoyer Libération (Jeton) à
Racinei;
4 Fin
Cette procédure est utilisée si un site
veut libérer la section critique.
Procédure 4: Réception de Libération
(Jeton)
1 Début
|
2
|
Si Longueuri > 0
alors
|
|
3
|
Jeton Reçu ();
|
|
4
|
Sinon
|
|
5
|
Jetons_libresi ?-
Jetons_libresi + 1;
|
|
6
|
Finsi
|
7 Fin
lorsque la racine reçoit une libération
du jeton, elle va voir si sa file d'attente elle est vide, si c'est le cas elle
va incrémenter son compteur de jetons libres, sinon elle va appeler la
procédure Jeton_Reçu().
Procédure 5: Réception de Demande (Jeton,
j)
1 Début
Si Jetons_libresi > 0
alors
Envoyer Accord (Jeton) à j;
Jetons_libresi ?-
Jetons_libresi - 1;
2
3
Sinon
Si Jetons_presentsi = Longueuri
alors
Envoyer Requête (Jeton, i) à
voisin_droiti;
Finsi
Demandeursi ?- Demandeursi + {j};
Longueuri ?- Longueuri + 1;
2
3
4
5
6
7
8
9
10
11
12 Fin
Le site racine qui reçoit une demande d'un site
dans l'arbre, il va accorder cette demande en envoyant un jeton, s'il
détient des jetons libres. Dans le cas contraire, on a deux situations :
si le nombre de jetons utilisés dans l'arbre permet de satisfaire les
requêtes reçues au bout d'un temps fini, la racine va attendre la
libération d'un jeton, si non, le site racine va demander un jeton
supplémentaire d'un voisin dans l'anneau par l'envoi d'un message de
type Requête, dans les deux cas, la demande sera ajoutée à
la file d'attente.
Procédure 6: Réception de Requête
(Jeton, j)
1 Début
Si Jetons_libresi > 0
alors
Utiliser le plus court chemin (j);
Jetons_libresi +-
Jetons_libresi - 1;
Jetons_presentsi +- Jetons_presentsi -
1;
Sinon
Si Jetons_presentsi >
Longueuri alors
Demandeursi +- Demandeursi + {j};
Longueuri +- Longueuri + 1;
Sinon
Envoyer Requête (Jeton, j) à
voisin_droiti;
Finsi
Finsi
14 Fin
Lorsqu'un site racine reçoit une requête
d'un voisin, et il détient des jetons libres, il envoie un jeton vers le
voisin demandeur via le plus court chemin pour minimiser le nombre de messages
échangés. Si ce site ne détient pas des jetons libres,
mais le nombre de jetons dans l'arbre est suffisant pour satisfaire toutes les
requêtes au bout d'un temps fini, alors, la requête sera
ajoutée à la file d'attente. Si non, le site va simplement
propager la requête vers son voisin droit.
Procédure 7: Utiliser le plus court chemin(x :
noeud)
1 Début
Distance +- i - x;
Si Distance < 0
alors
Si Distance ~ -K / 2
alors
Envoyer Aide (Jeton, j) à
voisin_droiti;
2
3
4
5
6
7
8
9
10
11
12
13
Sinon
Envoyer Aide (Jeton, j) à
voisin_gauchei;
Finsi
Sinon
Si Distance > K /
2 alors
Envoyer Aide (Jeton, j) à
voisin_droiti;
Sinon
Envoyer Aide (Jeton, j) à
voisin_gauchei;
Finsi
Finsi
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 Fin
Cette procédure représente la
stratégie qui nous permet d'améliorer la complexité en
nombre de messages, cette procédure est utilisée pour envoyer le
jeton via le plus court chemin, le site racine qui va répondre
favorablement à la requête de son voisin, doit
calculer
la distance, qui est le nombre d'arêtes qui les
séparent, si cette distance est inférieure à
K/2, le jeton sera donc envoyé vers le voisin gauche
(retour en arrière), si non, le jeton sera envoyé vers le voisin
droit.
2
3
4
5
6
7
8
9
10
11
12
13
14
Procédure 8: Réception de Aide (Jeton,
j)
1 Début
|
2
|
Si i =6 j
alors
|
|
3
|
Utiliser le plus court chemin (j);
|
|
4
|
Sinon
|
|
5
|
|
Si Longueuri > 0
alors
|
|
6
|
|
|
Jetons_presentsi +-
Jetons_presentsi + 1;
|
|
7
|
|
|
Jeton Reçu ();
|
|
8
|
|
Sinon
|
|
9
|
|
|
Jetons_libresi +-
Jetons_libresi + 1;
|
|
10
|
|
|
Jetons_presentsi +-
Jetons_presentsi + 1;
|
|
11
|
|
Finsi
|
|
12
|
Finsi
|
|
13 Fin
|
Après l'envoi d'un jeton vers un voisin, le
jeton peut passer par plusieurs sites avant d'atteindre sa destination, ces
sites peuvent être aussi des sites demandeurs, pour cela, on doit
garantir que chaque jeton doit être utilisé par son demandeur. Le
message Aide désigne l'identité du demandeur, le site qui
reçoit ce message va comparer son identité avec celle de
demandeur qui se trouve dans le message, dans le cas où les
identités sont différentes, le site doit propager le jeton vers
le voisin adéquat en utilisant le plus court chemin.
Procédure 9: Jeton Reçu ()
1 Début
Q +-
la_tete_de_la_file_d'attente;
Supprimer la tête de la file d'attente; Longueuri +-
Longueuri - 1;
Si Q = Site_Racine
alors
Utiliser le plus court chemin (Q);
Jetons_presentsi +- Jetons_presentsi -
1;
Finsi
Si Q = Site_Simple
alors
Envoyer Accord (Jeton) à Q;
Finsi
Si Q = i
alors
Etati +-En SC;
< Entrer en Section Critique>
Finsi
15
16 Fin
Lorsqu'un site racine reçoit un jeton à
partir d'un voisin ou d'un site de l'arbre, il doit mettre à jour ses
variables locales. Si la file d'attente des sites demandeurs n'est pas vide, on
doit donc satisfaire la plus ancienne requête dans cette file en
appliquant la procédure Jeton_Reçu.
- 1er cas : la tête de la file est un
site racine, le site doit donc envoyer le jeton vers le site demandeur et doit
encore mettre à jour les deux variables : Jetons libres et Jetons
présents.
- 2ème cas : la tête de la file
d'attente est un site régulier dans l'arbre, la racine va envoyer le
jeton et mettre à jour la variable Jetons_libres.
- 3ème cas : le site demandeur est
la racine elle-même, cette situation nous amène à
décrire le comportement d'un site racine lorsqu'il désire entrer
en SC, donc il passe directement en SC.
2
3
4
5
6
7
8
9
10
11
Procédure 10: Demande de la Section Critique par
une racine
1 Début
Si Jetons_libresi > 0
alors
Jetons_libresi ?-
Jetons_libresi - 1; Etati ?-En
SC;
< Entrer en Section Critique>
Sinon
Si Jetons_presentsi = Longueuri
alors
Envoyer Requête (Jeton, i) à
voisin_droiti; Finsi
Demandeursi ?- Demandeursi + {i};
Longueuri ?- Longueuri + 1;
Finsi
12
13 Fin
Lorsqu'une racine veut entrer en SC.
Finsi
Procédure 11: Libération de la Section
Critique par une racine
1 Début
Etati +-Dehors;
Si Longueuri > 0
alors
Q +-
la_tete_de_la_file_d'attente;
Supprimer la tête de la file d'attente;
Longueuri +- Longueuri -
1;
Si Q = Site_Racine
alors
Utiliser le plus court chemin (Q);
Jetons_presentsi +-
Jetons_presentsi - 1;
Finsi
Si Q = Site_Simple
alors
Envoyer Accord (Jeton) à Q;
Finsi
Sinon
Jetons_libresi +-
Jetons_libresi + 1;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 Fin
Si un site racine veut libérer la SC. 3.2.6 Preuve
de l'algorithme
| 
