3.2 L'ALGORiTHME
3.2.1 Objectif de l'algorithme
Les sites dans un système réparti
communiquent entre eux par des échanges de messages seulement, c'est
pourquoi cet échange à une grande influence sur la performance du
système, en effet la performance d'un algorithme dépends de ces
messages échangés, alors on doit essayer de minimiser le nombre
de messages échangés afin d'assurer un degré acceptable de
performance.
Dans le problème de la K-exclusion mutuelle,
les N sites du système partagent K exemplaires de la même
ressource, généralement la complexité des solutions de ce
problème est exprimée en fonction de N, cela va rendre la
complexité très élevé et qui influe
négativement sur la performance du système, d'une autre part, la
valeur de K est largement inférieur à N, donc on a essayé
de proposer un algorithme dont la complexité est exprimé en
fonction de K, cela va certainement influencer positivement sur la performance
du système.
3.2.2 Structure logique utilisée
Afin de minimiser la complexité de notre
algorithme, nous avons créé une nouvelle structure logique
permettant d'assurer la K-exclusion mutuelle par l'échange de minimum de
messages.
Cette structure logique consiste à diviser les
sites en K groupes, chaque groupe à un site appelé Racine
qui joue le rôle d'un coordinateur, tous les sites d'un groupe
adressent leur requêtes à cette racine, chaque racine
détient initialement un jeton, et toutes les racines sont reliées
entre elles par un anneau bidirectionnel qui permet l'échange des jetons
entre les différents sites.
La création de cette structure passe par deux
étapes :
- 1er étape : créer des
arbres statiques tels que, pour 1 < i < K, le
site i est la racine d'un arbre noté
Arbrei, et pour le reste des sites : K+1,
K+2, . . ., N, chaque site doit appartenir
à un arbre selon son identité en utilisant la fonction suivante
:
si i = 1 mod k, ce site
E Arbre1 si i 2
mod k, ce site E Arbre2 si
i 3 mod k, ce site E Arbre3 . . .
si i k-1 mod k, ce site E
Arbrek_1 si i 0 mod k,
ce site E Arbrek
On obtient K arbres statiques ayant les
caractéristiques suivantes :
1. V i / 1 < i <
k, le site i est la racine de Arbrei.
2. Vi/iEArbrei,ijmod
k.
3. V i,j < k, Arbrei fl
Arbrej = 0.
- 2ème étape : consiste
à connecter les arbres entre eux, pour cela, seules les K
racines seront reliées entre elles par un anneau
bidirectionnel tel que, pour un site i, le voisin
gauche de ce site est le site i-1, et le voisin droit
est le site i+1. (Pour les sites 1 et
K, nous avons : voisin gauche du site 1 est
le site K, et voisin droit du site K est le site
1).
- Exemple : On suppose qu'on a un système
composé de 17 sites et 4 ressources,
on a donc 4 arbres : Arbre1,
Arbre2, Arbre3 et Arbre4, oil les racines respectives
sont les sites 1,
2, 3 et 4, les autres sites vont
constituer les arbres selon leurs identités, on obtient
les arbres suivants :
|
Arbre1 =
|
{1,
|
5,
|
9, 13, 17}
|
|
Arbre2 =
|
{2,
|
6,
|
10,
|
14}
|
|
Arbre3 =
|
{3,
|
7,
|
11,
|
15}
|
|
Arbre4 =
|
{4,
|
8,
|
12,
|
16}
|
Ces arbres sont illustrés dans la figure
3.1 ci dessous :
Figure 3.1 - La
structure des arbres statiques.
Afin d'obtenir la structure logique final de notre
algorithme suivant la figure 3.2
:
Figure 3.2 - La
structure logique finale.
| 
