3.2.3 Principe de fonctionnement
Pour assurer la K-exclusion mutuelle, nous utilisons
autant de jetons que de ressources disponibles, initialement, chaque racine
détient un jeton libre et les racines peuvent échanger les jetons
entre elles, une racine peut détenir jusqu'à K jetons libres
à la fois.
Lorsqu'un site demandeur désire entrer en SC,
il envoie une requête vers la racine de son arbre, cette racine va
satisfaire la requête par l'envoi d'un jeton si elle détient des
jetons libres, dans le cas contraire, la requête sera sauvegardée,
et la racine va demander un jeton supplémentaire à ses voisins
via l'anneau.
Si la racine qui reçoit la demande d'un voisin
détient des jetons libres, elle va répondre favorablement
à cette demande par l'envoi d'un jeton, sinon elle va propager cette
demande vers un autre voisin.
La réception d'un jeton par une racine permet
de servir la première requête en attente, le site demandeur qui
reçoit un jeton passe donc à la SC, et il envoie le jeton
à sa racine après la libération de la SC.
Afin d'éviter l'échange coûteux
des jetons entre les racines, nous utilisons une méthode judicieuse qui
permet d'envoyer les jetons via le plus court chemin entre le site envoyeur et
le site récepteur, cette méthode permet donc de minimiser le
nombre de messages échangés pour chaque entrée en
SC.
3.2.4 Hypothèses
Pour assurer le bon fonctionnement de notre algorithme,
on suppose que :
- Le nombre N des noeuds et le K des racines sont
connus.
- Le réseau physique est un réseau
complet.
- Les sites du système ne tombent pas en
panne.
- Les canaux de communication sont fiables, et il n'y a
pas de perte de messages.
3.2.5 Description de l'algorithme
Dans cette partie nous allons décrire les
variables et les messages utilisés, et on va détailler les
procédures de notre algorithme.
3.2.5.1 Variables locales
Cet algorithme possède deux types de noeud, les
sites racines et les sites simples. - Au niveau d'un Site i
simple:
Etati : Désigne l'état du site,
cet état appartient à {Dehors, Demandeur, En SC}, qui est
initialisé à Dehors.
Racinei : L'identité de la racine d'arbre
contenant ce site. - Au niveau d'une Racine i :
Etati : Désigne l'état du site,
cet état appartient à {Dehors, Demandeur, En SC}, et qui est
initialisé à Dehors.
Racinei : au début est initialisée
à Nil.
voisin_droiti : l'identité du
voisin droit dans l'anneau. voisin_gauchei :
l'identité du voisin gauche dans l'anneau.
Jetons_libresi : un entier qui donne le
nombre de jetons libres détenus par la racine, qui est initialisé
à 1.
Jetons_presentsi : un entier qui donne
le nombre de jetons qui se trouvent dans l'arbre, qui est initialisé
à 1.
Demandeursi : une file d'attente pour stocker
les requêtes, initialement vide.
Longueuri : la longueur de la file d'attente, et
puisque la file d'attente est vide initialement, donc il est initialisé
à 0.
Distance : une variable permettant de calculer la
distance entre deux sites dans l'anneau, qui est initialisé à
0.
| 
