2.2.4.2 Les messages utilisés
Dans cet algorithme, on utilise trois types de
messages:
- Information (Jeton, i) : envoyé par le site
i vers les voisins immédiats pour les informer qu'il est un
père.
- Requête (Jeton, i) : envoyé par le site
i vers le père lors de la demande de la Section
critique.
- Accord (Jeton) : envoyé par un père
à un site demandeur pour lui permettre d'utiliser la ressource critique
demandée.
2.2.4.3 Initialisation des variables
Initialisation : des variables
Demandeuri : Variable
booléenne.
Jetoni : Variable booléenne.
Perei : Variable qui peut prendre
{1,2,. . .,N} U NIL U 0
Suivanti : Variable qui peut prendre
{1,2,. . .,N} U NIL
Début
Demandeuri +- Faux; Jetoni +-
Faux;
Suivanti +- NIL;
Perei +- 0;
Si Je suis un père Alors
Perei
+- NIL;
Jetoni +- Vrai;
Finsi
Fin
2.2.4.4 Les procédures de l'algorithme
Procédure N°1 : Informer tous les voisins
immédiat (Initialement)
1 Début
2 Envoyer Information (Jeton, i) à tous les
voisins immédiat;
3 Fin
Cette procédure est utilisée lorsqu'un site
père désire informer ses voisins immédiats qu'il
détient un jeton (père).
2
3
4
Procédure N°2 : Demander la Section Critique
1 Début
|
2
|
Demandeuri ?- Vrai;
|
|
|
3
|
Si Perei =6 NIL Alors
/* Si je possède un père
|
*/
|
|
4
|
Envoyer Requête (Jeton, i) à
Perei;
|
|
|
5
|
Sinon
|
|
|
6
|
|
Si Perei = Ø Alors
/* Si je ne possède pas de père
|
*/
|
|
7
|
|
Envoyer Requête (Jeton, i) à un voisin
immédiat;
|
|
|
8
|
|
Finsi
|
|
|
9
|
Finsi
|
|
|
10
|
Perei ?- NIL;
|
|
|
11
|
Attendre (Jeton = Vrai);
|
|
|
12
|
< Entrer en Section Critique>
|
|
|
13 Fin
|
|
Quand un noeud désire entrer en SC, il met sa
variable Demandeuri à Vrai, s' il possède
déjà un jeton (Jetoni = Vrai) il entre
directement en SC, Sinon il doit attendre la réception d'un jeton
auprès de son père.
Procédure N°3 : Réception de
Information (Jeton,j)
1 Début
Si Perei = Ø Alors
/* Si je ne possède pas un père */
Perei ?- j;
Finsi
5 Fin
Lors de la réception d'un message de type
Information par un site, il doit mettre à jour sa variable Perei
dans le cas ou ce site ne possède pas de père.
Procédure N°4 : Libérer la Section
Critique 1 Début
|
2
|
Demandeuri ?- Faux;
|
|
|
|
|
|
|
|
3
|
Si Suivanti =6 NIL
Alors /* S'il
|
y
|
a une
|
demande
|
en
|
attente
|
*/
|
|
4
|
|
Envoyer Accord (Jeton) à
Suivanti;
|
|
|
|
|
|
|
|
5
|
|
Jetoni ?- Faux;
|
|
|
|
|
|
|
|
6
|
|
Suivanti ?- NIL;
|
|
|
|
|
|
|
|
7
|
Finsi
|
|
|
|
|
|
|
8 Fin
Si un site veut libérer la section critique, il
met à jour sa variable Demandeuri à Faux et il consulte
s'il possède déjà un noeud suivant auquel il retransmettra
le jeton.
Procédure N°5 : Réception de Accord
(Jeton)
1 Début
2 Jetoni +- Vrai;
3 Fin
Lorsqu'un site a déjà envoyé une
demande d'entrer en section critique à son père, il va recevoir
un message de type Accord, lors de la réception de ce message, le site
va mettre à jour sa variable Jetoni à Vrai et entre
à la SC.
Procédure N°6 : Réception de
Requête (Jeton, j)
1 Début
|
2
|
Si Perei = NIL Alors
/* Si je suis un père */
|
|
3
|
|
Si Demandeuri = Vrai
Alors /* Si je suis déjà demandeur */
|
|
4
|
|
Suivanti +- j;
|
|
5
|
|
Sinon /* Si je n'ai pas fait une demande */
|
|
6
|
|
|
Jetoni +- Faux;
|
|
7
|
|
|
Envoyer Accord (Jeton) à j;
|
|
8
|
|
Finsi
|
|
9
|
Sinon
|
|
10
|
|
Si Perei =6 Ø
Alors /* Si je possède un père */
|
|
11
|
|
Envoyer Requête (Jeton, j) à
Perei;
|
|
12
|
|
Sinon /* Si je ne possède pas un
père */
|
|
13
|
|
Envoyer Requête (Jeton, j) à un voisin
immédiat;
|
|
14
|
|
Finsi
|
|
15
|
Finsi
|
|
16
|
Perei +- j;
|
|
17 Fin
|
Lorsqu'un site père reçoit une
requête, et il n'est pas demandeur, donc il détient un jeton, il
va satisfaire la requête et envoie ce jeton vers le site demandeur, si le
site père est un demandeur ou en SC, il met à jour sa variable
Suivanti et après sa sortie de la SC, il envoie le jeton vers
son suivant. Si le site qui reçoit la requête est un site
possédant un père, la requête sera propagée dans
l'arbre des pères jusqu'à l'arrivée à la racine.
Sinon le site va simplement propager cette requête à un voisin
immédiat.
Remarque
L'étude théorique de notre algorithme nous
a permis de constater le problème suivant :
Lorsqu'un site qui ne possède pas un
père désire entrer en SC, il va envoyer une requête vers un
voisin immédiat (voir Procédure Demander la SC), ce voisin va
propager cette requête à un autre voisin s'il ne possède
aucun père et ainsi de suite jusqu'à l'arrivée à un
arbre donné et satisfaire la requête, cependant ce chemin peut
être long et pénalisant en terme du temps d'attente, alors qu'il
peut exister un autre chemin plus court permettant de satisfaire la
requête et minimiser ainsi le temps d'attente.
Solution proposée
Dans le cas où un site veut libérer la
SC, il va vérifier s'il possède déjà une
requête en attente, sinon il ne fait rien, alors qu'il peut diffuser un
message Information afin d'informer le plus possible de voisins qui ne
possèdent pas de père, et cela va leur permettre lorsqu'ils
veulent entrer en SC, d'envoyer directement leurs requêtes à ce
père et ne pas l'envoyer à un voisin immédiat qui peut ne
pas avoir de père et tomber dans la problématique
précédente.
| 
