2.1.3 Bref historique
Le problème de l'exclusion mutuelle
était très bien traité dans les systèmes
informatiques centralisés, plusieurs algorithmes et mécanismes
assurant l'exclusion mutuelle ont été proposés, on peut
citer par exemple les sémaphores de Dijkstra [Dij65] et
les moniteurs. Par ailleurs, avec l'évolution des systèmes
informatiques on a vue ce problème se transformé de point de vue
centralisé à un point de vue réparti.
La première définition du problème
de l'exclusion mutuelle a été donnée par Dijkstra
[Dij65]. On peut résumer son propos dans les cinq
assertions suivantes :
1. A tout moment, il n'y a qu'un site du système
qui puisse exécuter la section critique.
2. La solution doit être symétrique,
c'est-à-dire que l'on ne "peut pas introduire de priorité
statique".
3. On ne peut pas faire d'hypothèse sur la
vitesse des participants.
4. En dehors de la section critique, tout site peut
quitter le système sans pour autant bloquer les autres.
5. Si plus d'un site désire entrer en section
critique, on doit pouvoir décider en un temps fini de l'identité
du site qui accédera à celle-ci.
Cette définition n'a pas évolué
jusqu'à aujourd'hui, et on la retrouve dans les principales
propriétés des algorithmes d'exclusion mutuelle.
2.1.4 Les classes de solutions d'exclusion mutuelle
C'est en 1977 avec l'algorithme de Le
Lann [Lan77] et en 1978 avec celui de Lamport
[Lam78] que l'on a commencé à considérer
pour l'exclusion mutuelle dans des systèmes répartis. Dans ces
systèmes les processus s'exécutent sur des sites distants et ne
peuvent communiquer entre eux que par envoi de messages.
Les algorithmes d'exclusion mutuelle se classent
usuellement en deux grandes familles : les algorithmes basés sur les
permissions et ceux basés sur l'utilisation des jetons.
Cette
classification a été introduite en
1991 par Raynal [Ray91]. On peut
illustré cette classification dans la figure
2.2
Figure 2.2 - Les
catégories des solutions d'exclusion mutuelle. 2.1.4.1 Les
algorithmes à permissions
Les algorithmes à permissions reposent sur une
idée simple et naturelle : chaque site demande aux autres, s'il le
désire, l'autorisation d'entrer en SC. Il ne pourra alors entrer en SC
qu'à la seule condition d'avoir bien reçu toutes les permissions
nécessaires.
Dans ce type d'algorithmes, la propriété
de sûreté de l'exclusion mutuelle est assurée par
l'invariant suivant : "À tout moment au plus un site possède
toutes les permissions nécessaires".
Pour garantir cet invariant, chaque algorithme à
permissions définit les conditions nécessaires à l'envoi
d'une permission à un autre site du système.
On peut diviser les algorithmes à permissions en
trois groupes selon le type de permission, la permission individuelle, la
permission d'arbitre et la permission
mixtes.[Sop08]
2.1.4.1.a Permissions individuelles
Dans ce type, un site peut donner sa permission
à plusieurs autres sites simultanément. S'il n'est pas demandeur,
il envoie son autorisation à tous les sites demandeurs, dans le cas
contraire, c'est-à-dire s'il est demandeur, il ne donnera son
autorisation qu'aux sites dont les requêtes sont plus anciennes.
(quelques algorithmes : [Lam78], [RA81],
[CR83], [CM84]).
2.1.4.1.b Permissions d'arbitres
Contrairement aux algorithmes à permissions
individuelles où un site finissait par recevoir l'accord explicite ou
tacite de tous les sites pour chaque entrée en SC, un site i
n'attend plus qu'un ensemble réduit de permissions.
Cet ensemble de sites Ri est propre à
chaque site i.
La deuxième différence des permissions
d'arbitres par rapport aux permissions individuelles, est qu'un site n'envoie
qu'une permission à la fois. Cet envoi n'est plus seulement
conditionné par l'état de l'application vis-à-vis de la
SC, mais aussi des permissions déjà émises par le site.
(exemple :[Mae85]).
Pour assurer la propriété de
sûreté il faut et il suffit que tous ces ensembles de diffusion
soient en intersection deux à deux, autrement dit :
V(i,
j), Ri n Rj =6
Ø
2.1.4.1.c Permissions mixtes
Cette dernière sous-classe d'algorithme
utilise, comme pour les permissions d'arbitres, des sous-ensembles Ri
pour diffuser ses requêtes diminuant ainsi la complexité en
nombre de messages. Mais, à l'instar des algorithmes à
permissions individuelles, les processus peuvent ici émettre plusieurs
permissions simultanément, ce qui écarte tout risque
d'interblocage.[Sop08]
La vivacité étant ainsi naturellement
assurée, ils peuvent s'affranchir du coûteux mécanisme de
reprise d'une permission. Le prix de cette économie est une contrainte
plus forte sur les ensembles Ri pour garantir la
propriété de sûreté :
V(i,
j),i E Rj V j E
Ri
Ce type d'algorithme a été introduit par
Mukesh Singhal en 1991 dans [Sin91]. Il a
noté que certaines taxonomies le classe comme un algorithme à
permissions d'arbitres "sans interblocage". C'est d'ailleurs le titre de
l'article. Le terme de permissions mixtes, utilisé ici, a
été introduit par Michel Raynal
[CM92].
2.1.4.2 Les algorithmes à jeton
Étudions maintenant la deuxième grande
famille que constituent les algorithmes à jeton. En considérant
un historique global des accès à la section critique, le
problème de l'exclusion mutuelle apparaît comme celui de la
séquentialisation de ces accès. Comme dans une course de relais,
la section critique passe de site en site. L'idée des algorithmes de
cette famille est alors de considérer un témoin appelé
"jeton" (token). Il peut être vu comme une super permission dont la seule
possession permet d'exécuter une section critique. Cette abstraction de
l'exclusion mutuelle permet d'obtenir facilement la propriété de
sûreté. Il suffit pour cela de maintenir l'invariant suivant " A
tout moment il n'y a dans le système qu'au plus un jeton ". Reste
à assurer la vivacité, c'est-à-dire la circulation du
jeton ainsi que celle des requêtes vers ce dernier.
Pour retrouver le jeton on distingue deux
stratégies : la première utilise des mécanismes de
diffusion, tandis que la deuxième repose sur l'utilisation des
propriétés de topologie particulière.
2.1.4.2.a Les algorithmes à diffusion (non
structuré)
Dans ce groupe d'algorithmes, un processus qui veut
demander la SC peut envoyer sa requête en parallèle à tous
les autres sites.
Ces algorithmes basés sur la diffusion de la
demande peuvent être aussi divisés en deux groupes :
- Les algorithmes statiques : un site qui a besoin du
jeton pour entrer en SC adresse sa demande à tous les autres
sites.[SK85], [HPR88].
- Les algorithmes dynamiques : le site qui veut
exécuter la SC doit envoyer sa requête de demande uniquement au
site qui a le jeton ou qui va l'avoir incessamment.[Sin89],
[CSL91].
2.1.4.2.b Les algorithmes à structure logique
(Structuré)
Dans ce groupe, les sites forment une configuration
logique grâce à leurs variables locales. Ces algorithmes peuvent
être aussi statiques ou dynamiques.
- Les algorithmes statiques : la structure logique
demeure inchangée et c'est uniquement le sens des arêtes qui
change. Les algorithmes statiques utilisent des graphes fixes qui
n'évoluent pas avec le système tels que l'arbre, l'anneau et
d'autres graphes.[Lan78], [Mar85],
[Ray89], [NM91], [vdS87]...
etc.
- Les algorithmes dynamiques : la configuration
logique adoptée au réseau change lorsqu'un processus demande et
exécute la SC. Grâce à cette structure logique dynamique,
on peut remonter l'historique des exécutions de la ressource critique.
Le fait de connaître celui qui détient le jeton ou celui qui va le
détenir nous permet de gagner beaucoup en nombre de messages et par
conséquent améliorer les performances de
l'algorithme.[NT87], [BAA89].
- Les algorithmes hybrides : D'après Hilary et
mostfaoui [HM94] ils proposent un algorithme hybride
basé sur une structure en "open-cube". Cet algorithme per-met de
s'adapter dynamiquement aux requêtes, tout en maintenant les
propriétés de symétries de cette structure arborescente
particulière. L'idée est ensuite d'utiliser ces
propriétés structurelles pour faciliter la mise en oeuvre de la
tolérance aux pannes.
| 
