CHAPITRE 2
Synchronisation dans les systèmes distribués
2.1 Introduction
La synchronisation dans les systèmes distribués fournit des solutions aux problèmes de
compétition et de coopération entre processus.
Dans les problèmes de compétition, les processus s’exécutent de manière indépen-
dante ; des algorithmes d’exclusion mutuelle et d’allocation de ressources sont appliqués
pour gérer les conflits d’utilisation des ressources.
Dans les problèmes de coopération, les processus collaborent pour atteindre un but
commun ; la coopération entre processus d’un système réparti est réglée à l’aide de la
coordination par rendez-vous, le maintien d’invariant, et la construction d’un temps
global [Raynal, 1992].
L’exclusion mutuelle est considérée comme le problème de synchronisation le plus
important, elle consiste à garantir qu’au plus un processus à la fois est autorisé à
accéder à des ressources critiques (physiques ou logiques). Vu l’absence d’une mémoire
commune et d’une horloge physique globale dans les systèmes répartis, les solutions de
synchronisation des systèmes centralisés (les variables partagées, les sémaphores, les
régions critiques et les moniteurs) ne sont pas applicables.
Dans ce chapitre, nous décrivons le principe de base des solutions au problème
d’accès à des ressources critiques en réparti.
Chapitre 2 : Synchronisation dans les systèmes distribués
2.2 Exclusion mutuelle distribuée
L’exclusion mutuelle est un problème de compétition entre processus, où plusieurs
processus sont en concurrence pour accéder à des ressources critiques partageables à
un seul point d’accès.
Les solutions au problème d’exclusion mutuelle distribuée décrites dans ce chapitre
utilisent des outils algorithmiques tels que les jetons, l’estampillage, la structure arbo-
rescente, etc. Ces mécanismes permettent de créer un ordre total entre les demandes et
le faire évoluer. En effet, ces mécanismes peuvent être appliqués pour résoudre d’autres
problèmes de synchronisation.
En supposant que l’état d’un processus appartient à l’ensemble {dehors, demandeur,
dedans}, la mission d’un algorithme distribué d’exclusion mutuelle est de faire passer
un processus de l’état demandeur vers l’état dedans (voir le schéma de la figure 2.1).
Opération acquérir demandeur
dehors
dedans
Opération libérer
Figure 2.1: Comportement d’un processus [Raynal, 1992]
Au cours de ce chapitre, nous adoptons les conventions suivantes :
• Le système est composé de n sites.
• Un seul processus s’exécute sur tout site, on confond alors les deux termes : site
et processus.
• Les sites (processus) sont reliés par des canaux de communication fiables.
Les algorithmes étudiés visent à assurer les deux propriétés [Raynal, 1992] :
• Propriété de sûreté : à tout instant il y a au maximum un processus accédant à
la ressource (état dedans).
15
Chapitre 2 : Synchronisation dans les systèmes distribués
• Propriété de vivacité : tout processus passe au bout d’un temps fini à l’état
dedans.
Dans ce chapitre, nous étudions deux classes d’algorithmes répartis :
• Algorithmes basés sur la demande de permission : tout processus doit demander
à d’autres processus la permission d’utiliser la ressource critique.
• Algorithmes fondés sur la circulation d’un jeton : utilisation d’un jeton qui circule,
le processus (site) possédant le jeton a le droit d’utiliser la ressource.
2.3 Performance des solutions
La performance des solutions d’accès à des ressources critiques en réparti est mesurée
au moyen de [Kshemkalyani et Singhal, 2011] (voir figure 2.2) :
Le dernier site Le site suivant
quitte la SC Entre en SC
Le temps
Délai de synchronisation
Demande de
SC arrive Le site exécute
Requêtes de
SC envoyées la SC Le site quitte
la SC
Le temps
Temps
d’exécution de
la SC
Temps de réponse
Figure 2.2: Mesures de la performance des algorithmes d’exclusion mutuelle
• Complexité en messages : cette mesure correspond au nombre de messages
nécessaires pour une exécution de la section critique par un site.
16
Chapitre 2 : Synchronisation dans les systèmes distribués
• Délai de synchronisation (temps protocole) : est le temps nécessaire pour
utiliser la section critique par un site après sa libération par le site précédent.
• Temps de réponse : est le temps qui s’écoule entre l’envoi des requêtes et la
fin d’utilisation de la ressource critique.
• Rendement du système : correspond à la vitesse à laquelle le système traite les
requêtes d’utilisation de la ressource critique. Si DS est le délai de synchronisation
et E est la durée moyenne d’exécution de la section critique, alors le rendement
1
du système est donné par : rendement = (DS+E)
.
2.4 Exclusion mutuelle fondée sur la permission
Dans un algorithme d’exclusion mutuelle fondée sur les permissions, un processus ne
peut utiliser la ressource critique qu’après recevoir les permissions requises. Les algo-
rithmes basées permissions peuvent être subdivisés en deux catégories : les algorithmes
basés permissions individuelles et les algorithmes basés permissions d’arbitres.
2.4.1 Algorithmes basés permissions individuelles
Dans un algorithme basé permission individuelle, un site peut donner son autorisa-
tion à plusieurs sites simultanément. Plus exactement, un site i répond favorablement
uniquement aux requêtes prioritaires. Une permission accordée par un site à un autre
fait intervenir uniquement le site sollicité, elle exprime : “en ce qui me concerne vous
pouvez entrer en SC”.
Pour garantir la propriété de sûreté, les ensembles Ri de sites auxquels le site i
demande les permissions sont caractérisés par ∀i, j : i ∈ Rj ou j ∈ Ri .
En ce qui concerne le calcul de la priorité entre les requêtes des sites, étant donné que
les sites du système distribué n’ont pas une horloge physique commune, les algorithmes
à base de permission individuelle établissent un ordre total à l’aide des couples (identité
du site, horloge logique du site). Les requêtes de demandes d’accès à la section critique
sont servies selon l’ordre total établi entre ces couples, c’est-à-dire qu’un site est déclaré
prioritaire si et seulement si son horloge est minimale ; dans le cas où les sites ont
la même valeur de l’horloge logique, le site prioritaire est celui ayant un identifiant
inférieur.
17
Chapitre 2 : Synchronisation dans les systèmes distribués
Plusieurs algorithmes à base de permissions individuelles ont été proposés, on peut
citer par exemple les algorithmes de Ricart et Agrawala, de Carvalho et Roucairol et
de Chandy et Misra.
Dans l’algorithme de [Ricart et Agrawala, 1981], un site demandeur doit avoir la
permission de tous les autres sites (Ri = {1, ..., n}\{i}). Un site sollicité répond favo-
rablement s’il n’est pas prioritaire ou s’il est à l’état dehors. À sa sortie de la section
critique, le site prioritaire envoie ses permissions aux sites demandeurs moins priori-
taires.
L’algorithme de [Carvalho et Roucairol, 1983] est une amélioration de l’algorithme
de [Ricart et Agrawala, 1981] qui diminue le nombre de messages échangés. Une permis-
sion accordée par un site à un autre l’autorise à l’utilisation courante et aux utilisations
ultérieures de la section critique. Plus concrètement, tout couple de processus partage
une permission, cette dernière est gardée par le site détenteur jusqu’à ce que l’autre
processus désire utiliser la ressource critique.
Dans l’algorithme de [Carvalho et Roucairol, 1983], la cardinalité de l’ensemble Ri
(Ri = { j| permission(i,j) est chez le processus j}) varie entre 0 (le site a toutes les
permissions) et n − 1 (le site n’a aucune permission), où n est le nombre total de sites
du système.
Une autre amélioration des algorithmes basés permission individuelle a été pro-
posée dans [Chandy et Misra, 1984]. L’algorithme est caractérisé par être adaptatif
et il utilise des variables bornées. En outre, les identités des processus sont rempla-
cées par les identités des canaux de communication. Comme dans l’algorithme de
[Carvalho et Roucairol, 1983], tout couple de processus partage une permission, et
chaque processus doit acquérir les n − 1 permissions (partagées avec les autres pro-
cessus) pour pouvoir exécuter la section critique. Pour assurer la propriété de vivacité,
les messages de permission sont dotés d’états. Tout message de permission reçu est à
l’état non-utilisé, après utilisation de la ressource critique l’état du message permission
devient utilisé. En plus, l’algorithme utilise un graphe acyclique pour gérer la priorité
entre processus.
2.4.2 Algorithmes basés permissions d’arbitre
Dans cette classe d’algorithmes, tout site doit obtenir les permissions de tous les sites
de son ensemble Ri . La différence importante par rapport aux algorithmes basés per-
18
Chapitre 2 : Synchronisation dans les systèmes distribués
missions individuelles est qu’une permission accordée à un site fait intervenir tous les
processus demandeurs, elle exprime “en ce qui concerne tous les sites qui me demandent
la permission vous pouvez entrer en section critique”, c’est-à-dire tout site n’accorde
sa permission qu’à une des requêtes reçues à un instant donné. Par conséquent, un site
qui a obtenu toutes les autorisations doit les rendre dès qu’il sort de la section critique
[Raynal, 2013].
Dans un algorithme basé permissions d’arbitre, la propriété de sûreté est assurée si
et seulement si ∀i, j : Ri ∩ Rj 6= ∅. Les processus de l’ensemble Ri ∩ Rj jouent le rôle
d’arbitres pour les conflits entre les processus demandeurs.
L’exemple type des algorithmes à base de permissions d’arbitre est celui de [Maekawa, 1985],
l’algorithme est symétrique, c’est-à-dire chacun des sites a les mêmes responsabilités
d’arbitrage et il fournit le même effort pour accéder à la section critique. Malheu-
reusement, l’interblocage peut se produire, pour gérer la situation d’interblocage des
solutions basées estampillage et récupération de permissions accordées sont à employer.
2.5 Exclusion mutuelle fondée sur l’unicité d’un jeton
Dans les algorithmes basés jeton, un seul jeton est échangé par les différents sites. Un
site ne peut utiliser la ressource critique que s’il possède le jeton. L’unicité du jeton
garantit la propriété de sûreté. Le problème avec cette classe d’algorithme est comment
garantir la vivacité. Pour assurer l’absence des situations d’interblocage et de famine
le jeton doit visiter équitablement tous les sites demandeurs.
Dans cette section, nous rappelons le principe des deux types d’algorithmes d’ex-
clusion mutuelle basée jetons : les algorithmes basés sur les mouvements perpétuels du
jeton et les algorithmes dont les sites effectuent des requêtes pour atteindre le jeton.
2.5.1 Algorithmes basés mouvement perpétuel
Pour ce type d’algorithmes, les sites sont placés sur une structure de communication
que parcourt le jeton. Le jeton se déplace d’un site à l’autre, jusqu’à arriver sur un site
dont l’état est demandeur, le site entre alors en section critique, le jeton n’est passé au
site suivant que lors du passage du site déteneur à l’état dehors.
L’algorithme de [Le Lann, 1977] est basé sur le mouvement perpétuel d’un jeton.
Un jeton unique circule en permanence entre les processus au moyen d’une topologie
19
Chapitre 2 : Synchronisation dans les systèmes distribués
en anneau. L’algorithme a l’avantage d’être simple et performant dans les cas où les
demandes d’accès à la ressource critique sont fréquents. Cependant, l’algorithme né-
cessite des échanges de messages même si aucun site ne veut accéder à la ressource
critique.
2.5.2 Algorithmes basés diffusion de requêtes
Dans ce type d’algorithmes, les sites envoient des requêtes pour atteindre le jeton. Les
algorithmes de cette classe se différencient par la topologie de l’ensemble des sites. On
peut distinguer des algorithmes basés diffusion systématique qui suppose l’existence
des liens directs entre tous les sites ; et des algorithmes dont les sites sont logiquement
organisés sous forme d’un arbre à caractère statique ou dynamique.
Dans l’algorithme de [Suzuki et Kasami, 1985], le site demandeur diffuse ses re-
quêtes vers tous les autres sites pour avoir le jeton. Tout site mémorise dans un tableau
local le nombre de ses requêtes et le nombre des requêtes faites par les autres sites.
Le jeton est aussi un tableau de n entrées, contenant le nombre de fois d’accès des
processus à la section critique. Pour assurer la propriété de vivacité, un site quittant la
section critique envoie tout d’abord le jeton aux sites demandeurs ayant un identifiant
supérieur, ensuite il effectue une recherche d’un site demandeur à partir du site ayant
l’identifiant minimal.
Comme exemple d’algorithmes utilisant une structure d’arbres, nous avons les deux
algorithmes [Naimi et Trehel, 1987] et [Raymond, 1989].
L’algorithme [Naimi et Trehel, 1987] utilise un arbre à caractère dynamique (arbre
des parents) et une file d’attente distribuée (file des requêtes). Au début de l’exécution
de l’algorithme tous les sites pointent sur le même nœud (la racine) qui possède le je-
ton. Ensuite, les requêtes des sites se propagent d’un site à un autre jusqu’à la racine.
Pendant la propagation des requêtes l’arbre se modifie et le dernier site demandeur
devient la racine. Pour satisfaire les requêtes selon leurs dates de formulation, l’algo-
rithme emploie une file des requêtes gérée selon la politique “premier arrivé premier
servi”. Dès que le site racine de l’arbre quitte la section critique il transmet le jeton au
site suivant de la liste.
L’algorithme de [Raymond, 1989] ressemble à l’algorithme de [Naimi et Trehel, 1987],
il repose aussi sur un jeton qui circule entre les nœuds d’un arbre dirigé, tout site (nœud
de l’arbre) doit avoir le jeton et être racine de l’arbre pour entrer en section critique.
20
Chapitre 2 : Synchronisation dans les systèmes distribués
Cependant, une file locale est employée pour assurer la vivacité, elle garde le nombre
de requêtes formulées ou reçues des sites. En plus, un site (nœud de l’arbre) ne peut
retransmettre une requête vers la racine que s’il n’a pas déjà fait une demande d’accès
à la section critique.
2.6 Conclusion
Dans ce chapitre, nous avons étudié le problème d’exclusion mutuelle en réparti. Nous
avons présenté la classe des algorithmes basés sur les permissions individuelles et les
permissions d’arbitres, et la classe des algorithmes basés sur l’unicité d’un jeton. La
figure 2.3 récapitule les algorithmes décrits dans ce chapitre et montre leurs classes.
Il est important de noter que les techniques utilisées par les algorithmes décrits
dans ce chapitre peuvent être employées pour résoudre d’autres problèmes du calcul
distribué.
Algorithme de Ricart et
Agrawala
Algorithme de Carvalho et
Permission individuelle
Roucairol
Algorithme de Chandy et
Algorithmes basés jeton
Misra
Permission d’arbitre Algorithme de Maekawa
Exclusion mutuelle en
réparti
Mouvement perpétuel Algorithme de Le Lann
Algorithmes basés Algorithme de Suzuki et
permission Kasami
Algorithme de Naimi et
Envoi de requêtes
Trehel
Algorithme de Raymond
Figure 2.3: Classes des algorithmes d’exclusion mutuelle en réparti
21
Chapitre 2 : Synchronisation dans les systèmes distribués
2.7 Questions
1. Quels sont les avantages et les inconvénients de l’approche centralisée pour la
gestion de l’exclusion mutuelle en réparti ?
2. Comparez les algorithmes étudiés dans ce chapitre selon la complexité en nombre
de messages et le délai de synchronisation.
3. Quelle est l’incidence du caractère non fifo des canaux de communication sur le
comportement de l’algorithme de Ricart et Agrawala basé permission ?
4. Dans l’algorithme de Carvalho et Roucairol, est-il possible qu’un message requête
double un autre message de requête sur le même canal ? Justifier.
22
