Systèmes Distribués
Chapitre 2 : Synchronisation dans les systèmes distribués
Introduction à l’exclusion mutuelle en réparti
Fateh Latreche
NTIC
[Link]@[Link]
Université Constantine 2 2020/2021. Semestre 1
Systèmes Distribués
Chapitre 2 : Synchronisation dans les systèmes distribués
Introduction à l’exclusion mutuelle en réparti
Fateh Latreche
NTIC
[Link]@[Link]
Étudiants concernés :
Faculté/Institut Département Niveau Spécialité
Nouvelles technologies TLSI Master 1 GL
Université Constantine 2 2020/2021. Semestre 1
Introduction
Vivacité et sûreté
Intérêts Exclusion centralisée VS Exclusion distribuée
Difficultés États des processus (sites)
Modèle du système répartie Propriétés des solutions
Performance des solutions
Classes d’algorithmes
Dans un système centralisé plusieurs processus partagent la
mémoire centrale,
Les variables partagées, Les sémaphores ou les moniteurs
peuvent être utilisés pour régler l’accès aux ressources
critiques.
Mais :
Dans un système réparti (distribué) pas de mémoire partagée,
L’interraction dans un système réparti n’est faite que par
échange de messages,
Les durées de transmission des messages entre sites sont
variables (à cause par exemple de la retransmission en cas
d’erreurs).
Université Constantine 2 c Fateh Latreche
2 / 12
Introduction
Vivacité et sûreté
Intérêts Exclusion centralisée VS Exclusion distribuée
Difficultés États des processus (sites)
Modèle du système répartie Propriétés des solutions
Performance des solutions
Classes d’algorithmes
L’exclusion est un problèmes de compétition entre processus
(sites),
Tout processus P1,...,Pn est doté d’un état ∈ { dehors,
demandeur, dedans}.
Figure – Etats des processus
Université Constantine 2 c Fateh Latreche
3 / 12
Introduction
Vivacité et sûreté
Intérêts Exclusion centralisée VS Exclusion distribuée
Difficultés États des processus (sites)
Modèle du système répartie Propriétés des solutions
Performance des solutions
Classes d’algorithmes
Résoudre le problème de l’exclusion mutuelle consiste à définir
les règles permettant de faire passer les processus de l’état
demandeur à l’état dedans ;
L’algorithme de passage à l’état dedans doit vérifier les deux
propriétés :
P1 : A tout instant il y a au maximum un processus Pi tel que
état(Pi)=dedans,
P2 : Tout processus qui se trouve à l’état demandeur passe au
bout d’un temps fini à l’état dedans .
Université Constantine 2 c Fateh Latreche
4 / 12
Introduction
Vivacité et sûreté
Intérêts
Difficultés
Modèle du système répartie
Performance des solutions
Classes d’algorithmes
Vivacité (Liveness) : «quelque chose de bon finira par arriver»
(a good thing will hapen during the execution) ;
Sûreté (Safety) : «quelque chose de mauvais n’arrivera
jamais» (some bad thing does not happen during the
execution)
P1 est une propriété de Sûreté
P2 est une propriété de Vivacité
La propriété P2 (de vivacité) garantit l’absence d’interblocage
et garantit l’absence de famine.
Université Constantine 2 c Fateh Latreche
5 / 12
Introduction
Vivacité et sûreté
Intérêts
Difficultés
Modèle du système répartie
Performance des solutions
Classes d’algorithmes
Plusieurs processus peuvent accéder à des ressources partagées
qui ont un seul point d’accès,
Un algorithme d’exclusion mutuelle crée un ordre total, peut
être utilisé pour réaliser un contrôle particulier.
Les solutions du problème d’exclusion mutuelle utilisent des
outils algorithmiques (jeton, estampille, ...) qui peuvent être
utilisés pour résoudre d’autres problèmes.
Université Constantine 2 c Fateh Latreche
6 / 12
Introduction
Vivacité et sûreté
Intérêts
Difficultés
Modèle du système répartie
Performance des solutions
Classes d’algorithmes
Les algorithmes d’exclusion mutuelle doivent créer une
asymétrie entre les processus demandeurs (sureté),
Les algorithmes d’exclusion mutuelle doivent évolué l’asymétrie
adoptée afin que tout processus en compétition (demandeur)
soit un jour déclaré vainqueur(vivacité).
Université Constantine 2 c Fateh Latreche
7 / 12
Introduction
Vivacité et sûreté
Intérêts
Difficultés
Modèle du système répartie
Performance des solutions
Classes d’algorithmes
Le système est composé de n sites ;
Chaque site a un seul processus et on confondra les deux
termes ;
Les sites sont liés par des liens de communication (ou canaux)
fiables, c’est à dire ne perdent ni altèrent les messages ;
Les canaux sont le seul moyen de communication entre sites ;
Aucune mémoire partagée ;
Pas d’horloge physique commune ;
Les canaux peuvent ou pas être FIFO.
Université Constantine 2 c Fateh Latreche
8 / 12
Introduction
Vivacité et sûreté
Intérêts
Difficultés
Modèle du système répartie
Performance des solutions
Classes d’algorithmes
La performance d’un algorithme distribué est déterminée par :
Complexité en messages : nombre des messages nécessaires pour
un accès à la section critique par un site.
Délai de synchronisation (temps protocole) : la durée 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 l’intervalle de temps qui sépare
l’établissement de la requête et la fin d’exécution de la section
critique.
Le Rendement du système : la vitesse à laquelle le système traite
les requêtes d’accès à la section 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 débit du système est donné par :
1
rendement = .
(DS + E )
Université Constantine 2 c Fateh Latreche
9 / 12
Introduction
Vivacité et sûreté
Intérêts
Difficultés
Modèle du système répartie
Performance des solutions
Classes d’algorithmes
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 – performance des solutions
Université Constantine 2 c Fateh Latreche
10 / 12
Introduction
Vivacité et sûreté
Intérêts
Difficultés
Modèle du système répartie
Performance des solutions
Classes d’algorithmes
Algos fondés sur la Algos fondés sur la
permission circulation d’un jeton
Pour entrer en SC, Pi Utilisation d’un jeton,
demande la permission à l’unicité du jeton
d’autres sites (- nombre garantie l’exclusion, celui
de permissions qui possède le jeton peut
attendues ; - structure de exécuter la SC. (
l’ensemble des comment assurer la
processus) vivacité)
Université Constantine 2 c Fateh Latreche
11 / 12
Introduction
Vivacité et sûreté
Intérêts
Difficultés
Modèle du système répartie
Performance des solutions
Classes d’algorithmes
Références
Ajay D. Kshemkalyani, Mukesh Singhal, Distributed Computing Principles, Algorithms, and
Systems.
Raynal M., Synchronisation et état global dans les systèmes répartis.
Université Constantine 2 c Fateh Latreche
12 / 12
