Rapport De Stage
Dissertation : Rapport De Stage. Rechercher de 53 000+ Dissertation Gratuites et Mémoires………………………………………………………………….20
Conclusion ......................................................................................................... 24
Algorithmique
Distribué
2010
3
INTRODUCTION
Le but de ce projet est l’étude d’un algorithme d'exclusion mutuelle (EM), celui
d'Housni-Tréhel en précis.
Il s'agit d'un algorithme à "jeton sollicité" qui utilise une structure d'arbre inverse
pour la transmission des requêtes d'EM et dans lequel la file des processus en attente
d'EM est abritée par la racine.
Notre travail consistera donc à mettre en oeuvre cet algorithme. En premier lieu, nous
allons spécifier l'application en CSP de celui-ci. Ensuite, nous devons élaborer le code
java de cet algorithme. En effet le langage java possède différents modes de
communication entre processus nous citerons comme exemple les Sockets et les
Threads. Et pour finir, nous procéderons à une phase de test de notre algorithme
pour de savoir si celui-ci correspond bien à l'algorithme d'Housni-Tréhel.
Algorithmique
Distribué
2010
4
I. SPECIFICATION DE L’ALGORITHME:
Nous allons commencer d’abord par définir l’architecture de notre réseau et nous le
spécifierons en CSP. Ceci nous facilitera le passage au codage en langage java et nous
donnera aussi une vision globale et claire de ce que nous devons mettre en oeuvre.
1. LE RESEAU :
Notre réseau possède une topologie qui est fixe. En effet il s’agit d’un graphe
connexe sans cycles, les noeuds représentent les sites ou les processus et les arêtes
représentent les connexions pour la communication. La figure qui suit nous montre
de près la forme de notre réseau.
2. SON ARCHITECTURE :
Les noeuds représentent les sites. Chaque site est composé d'un contrôleur (C) qui
communique avec les autres contrôleurs, pour savoir s'il peut entrer en EM, et d'une
application (A) qui effectue une tache lorsqu'elle entre en EM.
Algorithmique
Distribué
2010
5
Pour pouvoir entrer en EM, chaque site envoie un message, qui est une requête, à son
père. Cette requête contient une file, qui est le chemin de la requête individuelle pour
parvenir jusqu'à la racine. Ce message est ensuite transmis jusqu'à la racine, et le
chemin évolue en fonction des sites rencontrés.
*Cas de figure pour le traitement d’une requête :
Si la racine n'est pas en EM, alors elle envoie le jeton à son fils, qui a demandé le jeton
en premier. Pour savoir quel est le fils qui lui a demandé en premier le jeton, nous
utilisons une pile FIFO, qui sera la file de requête. Donc, lorsqu'un message parvient
à la racine et que celle-ci est en EM, elle place la demande dans la file.
Lorsqu'un site reçoit le jeton, nous le plaçons automatiquement à la racine. Le jeton
sera donc envoyé au site demandeur de la manière suivante (sur la figure cidessous).
Les messages qui transitent sur le réseau sont :
*Entre deux contrôleurs de site différents
*Entre le contrôleur d'un site et son application.
Les messages qui transitent sur le réseau sont donc les suivants :
Algorithmique
Distribué
2010
6
3.CODE CSP
Comme nous l’avons précisé avant, il y a 2 types de message, ceux qui transitent
entre deux contrôleurs de sites différents, et ceux entre un contrôleur et son
application.
3.1 SPECIFICATION DU CONTROLEUR EN CSP:
Il y a 4 types de message qui arrivent pour le contrôleur. Nous allons donc avoir 4
traitements différents en fonction du type de message.
*Réception de Req () :
Comme nous l'avons montré précédemment le message Req (), provient d'un
contrôleur d'un autre site. Ce message ne peut provenir que de la part de l'un de ses
fils. Ce message se présente sous la forme "Req (M,]A1,A2…..M]) ", et contient donc
une file qu'il faudra modifier. Il nous informe qu'un processus (site) souhaite entrer
en section critique, ainsi que le chemin pour parvenir au site demandeur.
Lorsque nous recevons un message de ce type, nous pouvons effectuer plusieurs
types de traitements selon notre position dans l'arbre.
Algorithmique
Distribué
2010
7
*1er cas :
Nous sommes à la racine et nous sommes en section critique, nous allons inséré la
requête individuelle (M,] A1, A2…..M]) en queue de la file de requête.
*2ème cas :
Nous sommes à la racine et nous ne sommes pas en section critique, le message
Jeton()(M,]A1,A2…..M]) est envoyé au site A1. Et avant d'envoyer le jeton au site A1,
il convient de le spécifier comme la nouvelle racine de l'arbre.
*3ème cas :
Nous ne sommes pas positionner à la racine, et nous recevons le message
"Req(M,]A1,A2…..M]) " , nous transmettons le message "Req(M,]A0,A1,A2…..M]) "
à notre père, en supposant que nous sommes le site A0 pour pouvoir lui indiquer le
chemin pour parvenir au site demandeur.
*Réception de Jeton () :
Lors de la réception du message Jeton (), nous nous plaçons directement à la racine.
Le message Jeton () est envoyé avec la file de requête. Ici aussi, plusieurs traitements
seront effectués suivant le fait que nous désirons entrer en section critique ou non.
*1er cas :
Nous sommes le site C (nous sommes le site à l'origine de la demande et que nous
sommes en tête de la file de requête) alors nous allons entrer en section critique, et
nous allons envoyer un message Deb-sc (), à notre application.
*2ème cas :
Nous ne sommes pas le site C, alors nous passons juste pour intermédiaire pour la
requête en tête de file. Le message Jeton () et la file de requête modifiée sont transmis
au site A1. Celui-ci, devient donc la nouvelle racine.
Algorithmique
Distribué
2010
8
*Réception de Bes_sc () :
En recevant un besoin de section critique de la part de notre application, nous allons
effectuer un traitement qui dépendra du fait si nous sommes à la racine ou non.
*1er cas :
Nous sommes pas à la
...