2.2.2 Le principe de fonctionnement
Pour assurer la K-exclusion mutuelle, nous utilisons
autant de jetons que de ressources disponibles. Initialement, chaque site
père détient un jeton, et doit informer ces voisins
immédiats pour leur permettre de lui adresser leurs requêtes, et
dans le but de former les K-arbres.
Lorsqu'un site désire entrer en SC, il envoie
une requête vers son père, et il devient un père à
son tour, le site qui reçoit cette requête répond par le
jeton s'il le détient, si non, il va propager la requête vers son
Père, et met à jour ses variables et pointe vers le nouveau
père (demandeur), et ainsi de suite jusqu'à ce que la
requête atteint la racine de l'arborescence, en effet, une nouvelle
arborescence est créée par le passage de cette requête, la
nouvelle racine est le dernier site demandeur.
Si un site est en SC et reçoit une
requête, il met à jour ses variables et pointe vers le nouveau
demandeur, après sa sortie de la SC, il envoie le jeton vers son
suivant, cet envoi ne modifie pas la structure de l'arborescence.
Dans le cas où un site en dehors des arbres
logiques créés, veut entrer en SC, il va envoyer sa requête
vers un voisin immédiat. .Si le site qui reçoit cette
requête n'a pas de père, il va propager cette demande à un
autre voisin immédiat différent du précédent, cette
propagation peut atteindre un site père ou un site possédant un
père, et donc la demande va alors transiter dans l'arbre des
pères jusqu'à arriver à la racine, et par
conséquent la racine ainsi que tous les sites parcourus pointent vers le
nouveau demandeur et la requête sera satisfaite directement ou au bout
d'un temps fini, cette requête permet au nouveau demandeur ainsi que tous
les sites parcourus et qui ne possèdent pas de père de joindre ce
nouvel arbre.
La figure 2.3 montre
l'évolution d'une arborescence selon des requêtes
émises.
Figure 2.3 - Les
états d'arborescence après chaque requête.
2.2.3 Hypothèses
Pour assurer le bon fonctionnement de notre algorithme,
on suppose que :
- Le nombre N des noeuds et le K des pères sont
connus initialement. - Chaque noeud connaît ses voisins
immédiats.
- Les canaux de communication sont fiables, et il n'y a
pas de perte de messages. - Les sites du système ne tombent pas en
panne.
- Le réseau n'est pas
partitionné.
2.2.4 Description de l'algorithme
Dans cette partie nous allons décrire les
variables locales et les messages utilisés, et on va détailler
les procédures de notre algorithme, quelques explications sont
associées aux procédures pour faciliter la compréhension
du code.
2.2.4.1 Les variables locales
Chaque noeud i dans le système maintient
les variables locales suivantes :
- Perei : est l'identité du père
qui possède le jeton tel que :
Si (Perei = NIL) :
i est un père.
Si (Perei = 0) : i est
un noeud qui ne possède pas de père
Si (Perei ? {1 ... N}) : i
est un noeud possédant un père.
- Demandeuri : une variable booléenne
initialisée à Faux, indiquant si i a demandé une
ressource critique ou non.
- Jetoni : une variable booléenne
indiquant si i possède un jeton ou non, elle est
initialisée à Faux au niveau des sites simple et à Vrai au
niveau des sites père.
- Suivanti : une variable indiquant
l'identité du site auquel le jeton sera transmis à la sortie de
la SC.
| 
