1.4 L'EXcLusioN MuTuELLE DANs LEs RtsEAuX AD HOC
Pour mieux comprendre ce problème dans les
environnements mobiles, nous allons d'abord l'expliquer dans un contexte
réparti.
1.4.1 L'exclusion mutuelle en réparti
1.4.1.1 La notion de l'exclusion mutuelle
L'utilisation simultanée d'une ressource
critique par plusieurs sites va certainement provoquer des situations
incohérentes. Afin d'éviter cette incohérence, un seul
processus au plus peut exécuter sa section critique à la fois, en
d'autres termes, les sections critiques doivent être
exécutées en exclusion mutuelle.
Pour rendre exclusif l'accès à une
section critique, les sites désirant l'exécuter doivent
exécuter un protocole d'acquisition avant la SC, ce dernier ne permet
qu'à un seul site de passer à la SC, à la fin de la SC, le
processus exécute le protocole de libération pour informer les
sites qui peuvent être en attente que la SC est
libre.[All07]. La forme générale d'un processus
utilisant une ressource critique est :
Protocole d'acquisition
< Section Critique>
Protocole de libération
1.4.1.2 Les états d'un processus
Un processus Pi appartenant au système
réparti est doté d'une variable locale Etati qui
désigne son état, tel que :
Etati = {Dehors, Demandeur,
Dedans}.
La figure 1.10 suivante
illustre les transitions d'un processus entre les trois
états.
Figure 1.10 - Les
états d'un processus.[Ray92]
1.4.1.3 Notions de base
1. Ressource critique C'est une ressource
partagée qui ne doit être accessible que par un seul site à
la fois.
2. Section critique
Une partie du code du processus manipulant une
ressource critique. Un seul processus au plus doit être en section
critique afin de garantir une utilisation correcte de la
ressource.[Ray92]
1.4.1.4 Propriétés d'un algorithme
d'exclusion mutuelle
Une solution n'est considérée correcte que
si elle respecte les propriétés suivantes : -
Propriété de sûreté (safety) : à
tout instant, un seul site au plus exécute la SC.
- Propriété de vivacité
(liveness) : tout site demandeur de la ressource critique doit pouvoir
l'acquérir au bout d'un temps fini.
Un algorithme qui assure ces deux
propriétés assure également l'absence de deux
problèmes, l'interblocage et la famine:
- Interblocage (Deadlock) : est une situation du
système oü il y a plusieurs sites à l'état Demandeur
et aucun ne peut accéder à la SC.
- Famine (Starvation) : aura lieu si un site qui
se trouve à l'état Demandeur ne passe jamais à
l'état Dedans.
1.4.1.5 Les classes de solutions d'exclusion
mutuelle
Les solutions réparties peuvent être
classées en deux grandes familles selon le type de messages
utilisé, les algorithmes fondés sur les permissions et ceux
fondés sur l'utilisation du jeton.[Ray92]
Figure 1.11 - Les
catégories des solutions d'exclusion mutuelle. 1.4.1.5.a
Algorithmes utilisant des permissions
Les algorithmes basés sur les permissions
utilisent le protocole suivant : Pour qu'un site i puisse
exécuter sa section critique, il doit d'abord demander la permission
à un ensemble Ri de sites et ne peut exécuter sa section
critique que s'il a reçu un nombre suffisant de permissions des autres
sites. Ce nombre est géré par ses variables locales. Ce
mécanisme assure l'exclusion
mutuelle.[All07]
1.4.1.5.b Algorithmes utilisant des jetons
Un jeton est un message particulier qui circule entre
les sites du système réparti, le site détenant le jeton
peut exécuter sa SC. L'algorithme de Lelann[Lan77],
était le 1er algorithme
utilisant un jeton. Et plusieurs autres solutions ont résolu le
problème, tels que l'algorithme de Ricart et Agrawala
[RA81], Suzuki et Kasami [SK85], Naimi et
Trehel[NT87], et plusieurs autres.
| 
