Algorithmique Distribuée

Exclusion mutuelle distribuée

Laurent PHILIPPE

Master 2 Informatique

UFR des Sciences et Techniques

2013/2014

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 1 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Références

Distributed Systems, Principle and Paradigms, A.Tanenbaum,

Pearson Ed.

M.Raynal, Une introduction aux principes des systèmes

répartis (3 tomes), EyrollesEd. (1991)

Cours de C.Kaiser du Cnam.

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 2 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Sommaire

1 Introduction

2 Mécanisme de synchronisation centralisé

3 Synchronisation distribuée avec des horloges logiques

4 Synchronisation distribuée utilisant un jeton

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 3 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Sommaire

1 Introduction

2 Mécanisme de synchronisation centralisé

3 Synchronisation distribuée avec des horloges logiques

4 Synchronisation distribuée utilisant un jeton

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 4 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Exclusion mutuelle : rappels

Une ressource partagée ou une section critique n'est accédée

que par un processus à la fois

Un processus est dans les trois états possibles, par rapport à

l'accès à la ressource :
demandeur
dedans
dehors
Changement d'états par un processus :
de dehors à demandeur
de dedans à dehors
Couche middleware gère le passage de l'état demandeur à
l'état dedans

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 5 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Exclusion mutuelle : rappels

Propriétés

Accès en exclusion mutuelle doit respecter 2 propriétés :

Sûreté : un processus au maximum en section critique (état

dedans)

Vivacité : toute demande d'accès à la section critique est

satisfaite en un temps ni

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 6 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Mécanismes d'exclusion mutuelle distribuée

En système distribué, nous présentons deux classes de mécanismes

d'exclusion mutuelle

les mécanismes centralisés

les mécanismes distribués

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 7 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Sommaire

1 Introduction

2 Mécanisme de synchronisation centralisé

3 Synchronisation distribuée avec des horloges logiques

4 Synchronisation distribuée utilisant un jeton

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 8 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Mécanisme de synchronisation centralisé

Synchronisation centralisée : dénition

Mécanisme centralisé de synchronisation en système distribué

regroupe les algorithmes qui utilisent un coordinateur pour gérer
l'exclusion mutuelle. Ce coordinateur :

centralise les requêtes des diérents processus de l'application

réalise l'exclusion mutuelle en accordant la permission d'entrée

en Section Critique

gère une le des requêtes en attente de Section Critique.

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 9 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

L'algorithme

Processus Pi
Quand un processus Pi veut entrer en Section Critique, il
envoie au coordinateur un message de "demande d'entrée en
Section Critique". Il attend la permission du coordinateur,
avant d'entrer en Section Critique.

Lorsque Pj reçoit la permission, il entre en Section Critique.

Quand Pi quitte la Section Critique, il envoie un message de

sortie de Section Critique au coordinateur.

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 10 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

L'algorithme

Coordinateur

Si personne en Section Critique, à la réception d'une demande

d'accès de Pi , il retourne "permission d'accès à Pi .

Si un processus Pj est déjà en Section Critique. Le

coordinateur refuse l'accès. La méthode dépend de
l'implantation :
soit il n'envoie pas de réponse, le processus P est bloqué. j

soit il envoie une réponse : "Permission non accordée".

Dans les deux cas, le coordinateur dépose la demande de Pj
dans une le d'attente.

A la réception d'un message de sortie de Section Critique, le

coordinateur prend la première requête de la le d'attente de
la Section Critique et envoie au processus un message de
permission d'entrée en Section Critique.

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 11 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Mécanisme de synchronisation centralisé

Avantages

Algorithme garantit l'exclusion mutuelle,

Algorithme juste (les demandes sont accordées dans l'ordre de

réception)

Pas de famine (aucun processus ne reste bloqué)

Solution facile à implanter

Pas de supposition sur l'ordre des messages

Complexité : maximum 2 ou 3 messages

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 12 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Mécanisme de synchronisation centralisé

Inconvénients

Si coordinateur a un problème, tout le système s'eondre

Si processus bloqués lors de demande d'accès à une Section

Critique occupée : impossibilité de détecter la panne du
coordinateur

Dans de grands systèmes, le coordinateur = goulet

d'étranglement

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 13 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Sommaire

1 Introduction

2 Mécanisme de synchronisation centralisé

3 Synchronisation distribuée avec des horloges logiques

4 Synchronisation distribuée utilisant un jeton

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 14 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Synchronisation distribuée

Rappel

Processus ne communiquent que par échange de messages

Chaque processus connaît l'ensemble des processus du système

Chaque processus a ses propres variables, pas de partage de

variables

On ne considère pas les cas de pertes de messages ni les

pannes de machines

Les échanges de messsages sont FIFO : les messages ne se

doublent pas.

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 15 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Synchronisation distribuée

Principe

Diuser la demande

Il faut l'accord de tous les autres

Une fois le consensus obtenu on accède à la SC

Diculté : demandes concurrentes

Algorithme de Lamport

Utilise les horloges logiques pour ordonner les évènements

Pi incrémente son horloge entre deux évènements locaux ou

distants

A la réception d'un message par Pi d'horloge H, l'horloge Hi

devient max (Hi , H ) + 1
Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 16 / 68
 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Variables pour chaque processus Pi

Horloge locale Hi
Tableau des horloges des autres processus, initialisé à 0

Chaque processus maintient un tableau de requêtes : état de

demande des autres processus ( ACK , REL, REQ )
Initialement, chaque processus connaît tous les autres
participants : liste des voisins

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 17 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Principe de l'algorithme(1)

Quand Pi veut entrer en Section Critique, il incrémente son

horloge, envoie le message REQ (Hi :Pi ) de demande de SC à
tous les autres processus et dépose ce message dans tableau
des requêtes

Quand un processus Pi reçoit le message REQ (Hj :Pj ) de

demande de SC, il synchronise son horloge, met le message
dans son tableau de requêtes et envoie un message ACK daté
de bonne réception à Pj

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 18 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Principe de l'algorithme (2)

P i accède à la SC quand les deux conditions suivantes sont réalisées :

Il existe un message REQ (H :P ) dans son tableau de requêtes

i i

qui est ordonné devant tout autre requête selon la relation de

précédence
Le processus P a reçu un message de tous les autres processus
i

ayant une date supérieure à H i

Ces 2 conditions sont testées localement par P i

Quand P quitte la SC, il enlève sa requête REQ (H : P ) de demande de

i i i

SC de son tableau de requêtes, incrémente son horloge et envoie un

message daté REL(H :P

i i pour signaler qu'il quitte la SC à tous les

processus

Quand P i reçoit le message REL(H : P ) (quitte SC), il synchronise son

j j

horloge et enlève le message REQ (H :P ) (demande de SC) de son

j j

tableau de requêtes

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 19 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Variables utilisées par chaque processus Pi

Hi : entier indiquant l'horloge locale. Initialement Hi =0
F _Hi [] : tableau contenant les horloges des diérents processus. La
taille du tableau correspond au nombre de participants.
F _Mi [] : tableau contenant les messages correspondant
Vi : ensemble de tous les voisins de Pi
Messages utilisés

REQ(H) : demande d'entrée en SC

ACK(H) : acquittement d'une demande d'entrée en SC
REL(H) : sortie de SC

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 20 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Règle 1

Accepte la demande de Section Critique Faire

Hi := Hi + 1
∀ j ∈ Vi Envoyer REQ( Hi ) à j
F _Hi [i ] := Hi
F _Mi [i ] := REQ
Attendre
∀j ∈ Vi ((F _Hi [i ] < F _Hi [j ]) ∨ ((F _Hi [i ] = F _Hi [j ]) ∧ i < j ))
<Section Critique>
Fait

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 21 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Règle 2

Accepte le message REQ(H) depuis j Faire

Hi := Max(Hi ,H) + 1
F _Hi [j ] = H
F _Mi [j ] = REQ
Envoyer ACK(Hi ) à j
Fait

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 22 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Règle 3

Accepte le message ACK(H) depuis j Faire

Hi := Max( Hi ,H) + 1
Si F _Mi [j ] 6= REQ Alors
F _Hi [j ] = H
F _Mi [j ] = ACK
Fsi
Fait

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 23 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Règle 4

Accepte la libération de la Section Critique Faire

Hi := Hi + 1
∀j ∈ Vi Envoyer REL( Hi ) à j
F _Hi [i ] = Hi
F _Mi [i ] = REL
Fait
Règle 5

Accepte le message REL(H) depuis j Faire

Hi := Max(Hi ,H) + 1
F _Hi [j ] = H
F _Mi [j ] = REL
Fait
Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 24 / 68
 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Déroulement de l'algorithme de Lamport

Exercice avec 3 processus : P ,P

0 1 et P
2

1 P0 demande à entrer en section critique. Dérouler l'algorithme

jusqu'à ce que P0 sorte de SC.
2 P1 demande. Dérouler l'algorithme jusqu'à ce que P1 sorte de SC.
3 Les processus P0 et P2 demandent la SC en même temps. Dérouler
l'algorithme jusqu'à ce que le premier des deux sorte de SC.
4 P1 demande à entrer en SC à ce moment là. Dérouler l'algorithme
jusqu'à ce que P1 sorte de SC.
5 Les processus P1 et P2 demandent la SC en même temps. Dérouler
l'algorithme jusqu'à ce que P1 et P2 sortent de SC.

Exercice

Que se passe-t-il si la propriété FIFO n'est pas respectée ?

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 25 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Propriétés de l'algorithme

Sûreté : exclusion mutuelle garantie

Vivacité garantie

Algorithme exempt d'inter-blocage

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 26 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport : Preuve sûreté

Par contradiction :

Supposons que P i et P j sont en même temps dans la SC à l'instant t,

Alors la condition d'accès doit être valide sur les deux processus en même temps

et ils sont tous les deux dans l'état REQ

On peut supposer sans perte de généralité qu'à un instant t , H (S ) < H (S ) (ou
i j

l'inverse, ce qui revient au même) puisque deux horloges logiques ne sont jamais

identiques

A partir de l'hypothèse de communication FIFO, il est clair que le message de

requête de S i est dans le tableau F _M au moment où P entre en SC puisque

j j

P j attend toutes les réponses ( ACK ) des processus avant d'entrer, donc celui de
de P.
i

Or l'acquittement de P i a été généré après que P i ait émis le message REQ

puisque H (S ) < H (S )
i j

Donc P
j est entré en SC alors que H (S ) < H (S ) → contradiction
i j

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 27 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Lamport

Vivacité

Toute demande d'entrée en Section Critique sera satisfaite au

bout d'un temps ni.

En eet, après la demande d'un processus Pi , au plus, N − 1

processus peuvent entrer avant lui

Complexité

3 ∗ (N − 1) messages par entrée en Section Critique, où N est le

nombre de processus

N − 1 Requêtes
N − 1 Acquittements
N − 1 Libérations
Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 28 / 68
 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Objectif

Algorithme proposé dans le but de diminuer le nombre de messages

par rapport à l'algorithme de Lamport

Changements

Regrouper information de sortie de SC et accord

Pas de retour systématique de ACK

N'informer que les processus en attente à la sortie de SC

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 29 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Principe de l'algorithme

Lorsqu'un processus Pi demande la Section Critique, il diuse

une requête datée à tous les autres processus.

Lorsqu'un processus Pi reçoit une requête de demande

d'entrée en Section Critique de Pj , deux cas sont possibles :
Cas 1 : si le processus P n'est pas demandeur de la Section
i

Critique, il envoie un accord à P . j

Cas 2 : si le processus P est demandeur de la Section Critique

i

et si la date de demande de P est plus récente que la sienne,

j

alors la requête de P est diérée, sinon un message d'accord

j

est envoyé à P . j

Lorsqu'un processus Pi sort de la Section Critique, il diuse à

tous les processus dont les requêtes sont diérées, un message
de libération.

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 30 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Variables utilisées par chaque processus P : i

H : entier, estampille locale. Initialement H = 0

i i

HSC : entier, estampille de demande de SC. Initialement HSC = 0

i i

R : booléen, le processus est demandeur de SC. Init à R = FAUX

i i

X : ensemble, processus dont l'accord est diéré. Init à X := ∅

i i

Nrel : entier, nombre d'accords attendus. Init à Nrel = 0.

i i

V : voisinage de i
i

Messages utilisés :
REQ (H ) : demande d'entrée en SC
REL() : message de permission

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 31 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Règle 1

Accepte la demande de SC Faire

Ri := VRAI
HSCi := Hi + 1
Nreli := cardinal (Vi )
∀j ∈ Vi Envoyer REQ(HSCi ) à j
tant que (Nreli 6= 0)
< SC>
Fait

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 32 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Règle 2

Accepte le message REQ(H) depuis j Faire

Hi := Max( HSCi ,H) + 1
Si Ri ∧ ((HSCi < H ) ∨ ((HSCi = H ) ∧ i < j )) Alors
Xi := Xi ∪ j
Sinon
Envoyer REL() à j
FSi
Fait

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 33 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Règle 3

Accepte le message REL( ) depuis j Faire

Nreli := Nreli − 1
Fait
Règle 4

Accepte la libération de la SC Faire

Ri := FAUX
∀j ∈ Xi Envoyer REL() à j
Xi := ∅
Fait

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 34 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Déroulement avec 3 processus : P ,P ,P

0 1 2

1 Le processus P 1 demandent l'accès à la Section Critique,

jusqu'à sa sortie de SC

2 Le processus P 2 demande l'accès à la Section Critique, une fois

qu'il est entré, P 1 demande, jusqu'à la sortie des deux.

3 P 0 demande la SC en même temps que P 2, lorsque l'un des

deux processus est en SC, P 1 demande, jusqu'à la sortie des
trois.

Question

Pourquoi deux horloges logiques ?

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 35 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Preuve
Par contradiction
On suppose que P et P sont les deux en section critique.
i j

On peut supposer sans perte de généralité que la requête de P a i

une horloge plus petite que celle de P j

Puisque l'horloge de P est plus petite que celle de P cela signie

i j

qu'il a reçu la requête de P après avoir fait sa demande

j

D'après l'algorithme P ne peut entrer en section critique que si P

j i

lui a envoyé un message REL

Puisque P est en section critique alors il a envoyé ce message REL
i

avant d'entrer en section critique

Ce qui est impossible puisque l'horloge de P est supérieure à celle
j

de P , or d'après l'algorithme P n'envoie REL que si l'horloge reçue

i i

est plus petite Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 36 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Ricart et Agrawala

Complexité

Une utilisation de la Section Critique nécessite 2 ∗ (N − 1)

messages :

N − 1 Requêtes
N − 1 Permissions

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 37 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Synchronisation distribuée utilisant la notion d'horloges

logiques

Algorithme de Carvalho et Roucairol

Algorithme proposé dans le but de diminuer le nombre de messages

par rapport à l'algorithme de Ricart et Agrawala

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 38 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Carvalho et Roucairol

Principe de l'algorithme

Soit le cas où Pi demande l'accès à la Section Critique plusieurs

fois de suite (état demandeur plusieurs fois de suite) alors que Pj
n'est pas intéressé par celle-ci (état dehors )
Avec l'algorithme de Ricart et Agrawala, Pi demande la
permission de Pj à chaque nouvelle demande d'accès à la
Section Critique

Avec l'algorithme de Carvalho et Roucairol, puisque Pj a

donné sa permission à Pi , ce dernier la considère comme
acquise jusqu'à ce que Pj demande sa permission à Pi : Pi ne
demande qu'une fois la permission à Pj

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 39 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Carvalho et Roucairol

Variables utilisées par chaque processus Pi

HSCi : entier, estampille de demande d'entrée en SC, initialisée à 0
Hi : entier, estampille locale, initialisée à 0
Ri : booléen, le processus est demandeur de SC, init à FAUX
SCi : booléen, le processus est en SC, init à SCi = FAUX
Xi : ensemble, processus dont l'envoi de l'avis de libération est
diéré. Init à Xi := ∅
XAi : ensemble des processus desquels i attend une autorisation.
Init à XAi := Vi
Nreli : nombre d'avis de libération attendus, init à 0.
Vi : voisinage de i

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 40 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Carvalho et Roucairol

Messages utilisés

REQ(H) : demande d'entrée en SC

REL() : message de permission

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 41 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Carvalho et Roucairol

Règle 1

Accepte la demande de SC Faire

Ri := VRAI
HSCi := Hi + 1
Nreli := cardinal (XAi )
∀j ∈ XAi Envoyer REQ(HSCi ) à j
Tant que (Nreli 6= 0)
SCi =VRAI
< SC>
Fait

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 42 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Carvalho et Roucairol

Règle 2

Accepte le message REQ(H) depuis j Faire

Hi := Max( HSCi ,H) + 1
Si SCi ∨ (Ri ∧ ((HSCi < H ) ∨ ((HSCi = H ) ∧ i < j ))) Alors
Xi := Xi ∪ j
Sinon
Envoyer REL() à j
Si Ri ∧ (¬SCi ) ∧ j ∈/ XAi Alors
Envoyer REQ( HSCi ) à j
FSi
XAi := XAi ∪ j
FSi
Fait
Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 43 / 68
 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Carvalho et Roucairol

Règle 3

Accepte le message REL( ) depuis j Faire

Nreli := Nreli − 1
Fait
Règle 4

Accepte la libération de la SC Faire

Ri := FAUX
SCi := FAUX
XAi := Xi
∀j ∈ Xi Envoyer REL() à j
Xi := ∅
Fait
Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 44 / 68
 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Carvalho et Roucairol

Déroulement de l'algorithme avec 3 processus : P ,P

0 1 et P
2

1 Les horloges logiques de chaque processus sont à 0

2 Les processus P2 et P1 demandent l'accès à la Section Critique

en même temps

3 Déroulement de l'algorithme jusqu'à ce que les deux processus

P 1 et P
2 soient entrés et sortis de Section Critique

4 Les processus P 0 et P 1 demandent la section critique

5 Arrêt du déroulement de l'algorithme lorsque les trois

processus P 0 et P 1 seront entrés et sortis de Section Critique

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 45 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Carvalho et Roucairol

Question

Pourquoi un processus qui reçoit une REQ renvoie-t-il parfois une

REQ ?

Complexité

Le nombre de messages requis pour une utilisation de la Section

Critique est :

pair car à toute requête d'entrée en SC correspond un envoi de

permission

fonction de la structure du système : varie entre 0 et 2*(N-1)

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 46 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Sommaire

1 Introduction

2 Mécanisme de synchronisation centralisé

3 Synchronisation distribuée avec des horloges logiques

4 Synchronisation distribuée utilisant un jeton

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 47 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Synchronisation distribuée utilisant un jeton

Algorithmes

Diérentes structures de communication :

Anneau : Le Lann

Diusion : Suzuki-Kazami

Arbre : Naimi-Trehel

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 48 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Le Lann

Système structuré en anneau

Algorithme utilisant un jeton pour gérer l'accès à une Section

Critique

Jeton (unique pour l'application) = permission d'entrer en

Section Critique

Un seul processus détient le jeton à un moment donné

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 49 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Le Lann

Construction de l'anneau

Construction d'un anneau avec l'ensemble des processus de

l'application de façon logique

Attribution d'une place à chacun des processus

Chaque processus connaît son successeur dans l'anneau

Initialisation : jeton attribué à un processus (exemple :

Processus P 0)

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 50 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Le Lann

Principe de l'algorithme

Quand un processus reçoit le jeton de son prédécesseur dans

l'anneau :
s'il est demandeur de Section Critique, il garde le jeton et
entre en Section Critique
s'il n'est pas demandeur de Section Critique, il envoie le jeton
à son successeur dans l'anneau
A la sortie de Section Critique, le processus envoie le jeton à
son successeur dans l'anneau

Pour des raisons d'équité, un processus ne peut pas entrer

deux fois de suite en Section Critique

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 51 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Le Lann

Exercice

Quelles sont les données nécessaires ?

Quels sont les messages échangés ?

Quelles règles doivent être mises en place ?

Écrire les règles

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 52 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Le Lann

Avantages de l'algorithme

Simple à mettre en ÷uvre

Intéressant si nombreux demandeurs de la ressource

Équitable en terme de nombre d'accès et de temps d'attente

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 53 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Le Lann

Inconvénients (1)

Nécessite des échanges de messages même si aucun processus

ne veut accéder à la Section Critique

Temps d'accès à la Section Critique peut être long

Perte du jeton :
diculté de détecter un tel cas
impossibilité de prendre en compte le temps écoulé entre deux
passages du jeton (temps passé en Section Critique est très
variable)
des algorithmes gèrent ce problème de perte et régénération de
jeton sur un anneau (non vu dans ce cours)

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 54 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Le Lann

Inconvénients(2)

Problème de la panne d'un processus

plus facile à gérer que dans les algorithmes précédents
envoi d'un acquittement à la réception du jeton : permet de
détecter la panne de l'un des processus
le processus mort peut être retiré de l'anneau et le suivant
prend alors sa place
pour implanter ceci : chaque processus doit connaître la
conguration courante de l'anneau.

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 55 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Synchronisation distribuée utilisant un jeton

Modication de l'algorithme avec anneau

Jeton symbolise le droit d'entrée en section critique

Un seul processus détient le jeton à un moment donné

Pas forcément besoin de la structure d'anneau

Exercice

Ecrire un algorithme où les participants échangent un jeton

pour accéder à la section critique.

Dénir les données, les messages et les règles.

Quelles propriétés possède cet algorithme : sûreté, vivacité,

équité ?

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 56 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Suzuki-Kasami

Principe de l'algorithme

Chaque processus connaît l'ensemble des participants

Quand Pi veut accéder à la Section critique, il envoie un

message REQ(H) à tous les participants

Le jeton contient l'estampille de la dernière visite qu'il a

eectué à chacun des processus

Quand Pi sort de Section Critique, il cherche le premier

processus Pk tel que l'estampille de la dernière requête de Pk
soit supérieure à celle mémorisée dans le jeton (correspondant
à la dernière visite du jeton à Pk )

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 57 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Synchronisation distribuée utilisant un jeton

Exercice

Quelles sont les propriétés de l'algorithme ?

Comment améliorer l'équité ?

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 58 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Eviter de diuser la requête initiale

Principe

Les processus sont logiquement organisés en arbre construit à

partir des requêtes de demande d'accès en Section Critique

Seul le processus qui possède le jeton peut accéder à la section

critique

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 59 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Structures de données

Ces structures de données sont gérées de façon distribuée :

Une le de requêtes : next

Un arbre de chemins vers le dernier demandeur de SC : owner

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 60 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

File de requêtes : next

Processus en tête de le possède le jeton

Processus en queue de le est le dernier processus qui a fait

une demande d'entrée en SC

Chaque nouvelle requête de SC est placée en queue de le

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 61 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Arbre de chemins vers le dernier demandeur de SC : owner

Racine de l'arbre : dernier demandeur de SC (= queue de la
le des next)
Une nouvelle requête est transmise suivant le chemin des
pointeurs de owner jusqu'à la racine de l'arbre (owner = nil)
reconguration dynamique de l'arbre : nouveau demandeur
devient la racine de l'arbre
les processus faisant partie du chemin entre la nouvelle racine
et les anciennes racines modient leurs pointeurs owner :
owner = nouvelle racine

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 62 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Principe de l'algorithme (1)

Chaque processus Pi gère localement les éléments suivants :

owner : processus qui possède probablement le jeton. Toute

demande de Pi d'accès à la Section Critique sera envoyée à ce
processus.

next : processus à qui Pi devra transmettre le jeton à sa sortie

de Section Critique. next est le dernier processus qui a envoyé
à Pi une requête d'entrée en Section Critique.

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 63 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Principe de l'algorithme (2)

Initialisation :

elected-site : processus désigné comme étant le propriétaire

du jeton. C'est la racine de l'arbre.

owner : initialisé à elected-site

next : initialisé à nil

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 64 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Principe de l'algorithme (3)

Quand un processus Pi demande l'accès à la Section Critique

S'il ne possède pas le jeton, il envoie sa requête à owner et

attend de recevoir le jeton

S'il possède déjà le jeton, il entre en Section Critique

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 65 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Principe de l'algorithme (4)

Quand un processus Pi reçoit une requête d'entrée en SC de la part

de Pj
S'il possède le jeton et qu'il n'est pas en SC alors il envoie le
jeton à Pj et met à jour sa variable owner
S'il possède le jeton et s'il est en SC, il met à jour next
S'il ne possède pas le jeton et qu'il attend la section critique :
il transmet la requête à owner
S'il ne possède pas le jeton et qu'il attend la section critique :
il enregistre la demande dans next

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 66 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Principe de l'algorithme (5)

Quand un processus Pi sort de SC, si next est initialisé il envoie le

jeton à next et réinitialise next à nil

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 67 / 68

 Introduction
Mécanisme de synchronisation centralisé
Synchronisation distribuée avec des horloges logiques
Synchronisation distribuée utilisant un jeton

Algorithme de Naimi-Trehel

Déroulement de l'algorithme

Soient 5 processuss A, B, C, D et E

Initialisation : le processus A possède le jeton (electednode)

Le processus B demande l'accès à la section critique

Lorsque le processus B est en Section Critique, le processus C

en demande l'accès

Lorsqu'ils sont sortis de la section critique le processus E

demande.

Quel est l'état de l'arbre des demandeurs au cours de ces

demandes ?

Laurent PHILIPPE Chapitre 2: Exclusion mutuelle distribuée 68 / 68