SDR

Estampilles

Olivier Lemer

Exclusion Mutuelle (Lamport)

Exclusion Mutuelle ?

Exclusion Mutuelle

Définition

Situation lors de laquelle un bloc d'opérations ne doit être éxecuté que par un processus à la fois.

Ce bloc d'opérations est appelé Section Critique (SC).

  • par locks (shared memory), ou

Synchronisation nécessaire

  • par messages (systèmes répartis).

Exemple

Copie synchronisée d'un même compte en banque. Certaines opérations doivent être séquentielles.

synchronized {

}

Section Critique

Exemple inspiré de la syntaxe Java

Comment ?

Synchronisation par messages

A

?

request

accept

release

}

synchronized {

En dehors

En attente

En SC

En dehors

A

request

accept

release

Controller

X

On request

Push demandeur dans la file

On release

Pop tête de file

Envoi de accept à nouvelle tête

La tête de la file est toujours celle actuellement en SC.

push(A)

pop()

pop()

X A

A

.

release

(from X)

Solution centralisée

File d'attente

X en SC

A ensuite.

B

A

C

C B

push(B)

B

pop()

.

pop()

.

pop()

B

pop()

C B

push(B)

C B

push(B)

B

pop()

.

pop()

release

request

request

C

C

C

release

release

Solution répartie

Version naïve

On request

Push demandeur dans la file

On release

Pop tête de file

Si je suis nouvelle tête, entrer en SC.

La tête de la file est toujours celle actuellement en SC.

Problème ?

Solution répartie

Version naïve - Résumé

C

request

release

B

pop()

release

.

pop()

B

C B

push(B)

B

A

C

A

A

A

request

request

request

request

A B

A B

A C

A B C

A B C

A C B

B C

B C

C B

release

Solution répartie

Version naïve - Problème

B

A

C

A

A

A

request, 2

request, 2

request, 2

request, 2

A B

A B

A C

2 2

2 2

2 2

A B C

A B C

A B C

2 2 2

2 2 2

2 2 2

B C

B C

B C

2 2

2 2

2 2

release, 4

t=1

t=1

t=1

Reorder par les estampilles

Solution répartie

Version naïve corrigée

Ajout d'une estampille

Envoi de son estampille avec.

Sauvegarde des estampilles reçues

Problème ?

Trie la file par heure de Lamport.

On request

Push demandeur dans la file

On release

Pop tête de file

La tête de la file est toujours celle actuellement en SC.

Si je suis nouvelle tête, entrer en SC.

avec son timestamp.

(avec résolution arbitraire des égalités)

Solution répartie

Version naïve corrigée - Résumé

C

A

request, 2

request, 2

t=1

release, 4

B C

2 2

A B C

2 2 2

A C

2 2

B

A

C

.

.

.

request, 2

request, 2

request, 2

request, 2

B

B

C

2

2

2

B C

B C

C B

2 2

2 2

2 2

t=1

t=1

t=1

Reorder ?

Problème : 

Ils assurent seulement qu'un ordre strict sera obtenu un jour.

Les timestamps de Lamport n'ordonnancent pas les messages immédiatement.

Solution répartie

Version naïve corrigée - Problème

Je suis la tête !

Je suis la tête !

Solution répartie

Version naïve corrigée - Problème

Question

Quand être sûr que mon message a été reçu par tout le monde ?

Un message avec estampille t dit "cet événement a eu lieu à l'heure logique t".

B

C

.

.

request, 2

request, 2

B

C

2

2

B C

B C

2 2

2 2

t=1

t=1

ack, 3

ack, 3

ack, 3

B C

2 2

B C

2 2

Solution répartie

Version naïve corrigée corrigée

Attente que mon message soit reçu.

Ack plus récent que mon message. Je peux y aller.

Réordonne la file par heure de Lamport.

avec son timestamp.

On request

Push demandeur dans la file

On release

Pop tête de file

La tête de la file est celle actuellement en SC,

Entrer en SC

Envoie ack avec nouveau timestamp.

si je suis la nouvelle tête, et

que j'ai reçu tous les acks.

si elle a reçu un ack de toutes les autres machines.

Problème ?

Solution répartie

Version naïve corrigée corrigée - Résumé

La structure de donnée n'est plus adaptée

B

C

request, 2

request, 2

t=1

t=1

ack, 3

ack, 3

REL

A B C

REL

REL

1

1

1

REL

A B C

REL

REL

1

1

1

REL

A B C

REQ

REL

1

2

1

REL

A B C

REL

REQ

1

1

2

REL

A B C

REQ

REQ

1

2

2

REL

A B C

REQ

REQ

1

2

2

ACK

A B C

REQ

REQ

3

2

2

ACK

A B C

REQ

REQ

3

2

2

ACK

A B C

REQ

REQ

3

2

2

ACK

A B C

REQ

REQ

3

2

2

Amélioration :

File remplacée par tableau.

Pour chaque processus,

initialement {REL, 1}, puis

  • le dernier message reçu
  • le timestamp associé

Un processus entre en SC si

  • son dernier message est REQ,
  • et son heure logique est

sauf si ACK remplacerait REQ.

ack, 3

ack, 3

Solution répartie

Version finale (?)

strictement la plus petite.

On REQ

On REL

Stocke message dans tableau.

Suggestions ?

On ACK

Après chaque message

Entre en SC, si

  • j'ai la plus petite heure logique, et
  • c'est un REQ

Envoi ack avec nouveau timestamp.

Stocke message dans tableau.

Stocke message dans tableau,

sauf si un REQ y est déjà.

To be continued...

Solution répartie

Version finale (?) - Résumé

Question : Comment être sûr que j'ai le droit d'entrer en SC ?

Solution répartie

Réflexions

Entre en SC, si

  • j'ai la plus petite heure logique, et
  • c'est un REQ

Par l'absurde :

  • J'envoie un REQ avec un timestamp t1.
  • Si un autre, p, serait plus légitime que moi, son REQ aurait eu un timestamp t2 plus ancien.
    • Soit je n'ai pas reçu ce REQ, et le TS de p dans mon tableau est encore plus petit que t2.
    • Soit je l'ai reçu, et le TS de p dans mon tableau est t2, qui est plus petit que t1.
  • Dans les deux cas, t1 n'est pas le plus petit dans mon tableau ; je n'essaie pas d'entrer en SC.

Remarque : cette phrase n'est correcte que si j'interdis de remplacer un REQ par un ACK. D'où cette règle.

Exclusion Mutuelle

B

Exclusion Mutuelle

Mode réparti

A

C

push(B)

pop()

pop()

push(B)

push(B)

pop()

pop()

pop()

pop()

C

C B

B

.

request

request

release

release

release

C

C B

B

.

C

C B

B

.

Exclusion Mutuelle

Controller

A

B

C

←

B

C

D

←

B

C

A

A

B

C

←

D

1

1

3

X Y Z

A

A

X

A

request

accept

release

1

1

3

Algorithme

a.k.a. Algorithme de Lamport

Résumé

Le timestamp est incrémenté en entrée et sortie de SC,

Au sortir de SC, le processus

  • envoie un REL à tous, lui-même compris.

À la réception d'un REQ, le processus

  • envoie un ACK à l'émetteur.

À la réception de tout message, le processus

  • stocke ce message dans le tableau, dans la case de l'envoyeur,

sauf si cela remplacerait un REQ par un ACK.

  • entre en SC si sa case est REQ et a la plus petite heure logique.

Pour demander l'entrée en SC, le processus

  • envoie un REQ à tous, lui-même compris, puis attend.

Les N processus maintiennent un tableau de taille N, et

un timestamp ts de Lamport.

et à toute réception de la part d'un autre processus.

Pseudocode

Variables

n

self

ts

enSC

tab

entier, constant

entier, entre 0 et n-1

entier, initialement 0

booléen

tableau de messages

nombre de processus

numéro de ce processus

timestamp Lamport de ce processus

vrai ssi autorisé à être en SC

messages de chaque processus

de format {[REQ|ACK|REL], ts},

initialement {REL, 0}.

Initialisation

Écouter infiniment les événements suivants :

Demande de SC de la couche applicative

Passage de enSC à true

Sortie de SC dans la couche applicative

Réception REQ(ts)

Réception ACK(ts)

Réception REL(ts)

(Avec traitement séquentiel de chaque événement)

Pseudocode

Traitement : Sortie de SC dans la couche applicative.

ts incrémenté.

Envoi de {REL, ts} à tous les processus, self inclus.

Traitement : Passage de enSC à true.

Autorisation de la couche applicative à entrer en SC.

Traitement : Demande de SC de la couche applicative.

ts incrémenté.

Envoi de {REQ, ts} à tous les processus, self inclus.

Pseudocode

Traitement : Réception {REL, tsi} du processus i.

Traitement : Réception {REQ, tsi} du processus i.

ts ← max(tsi, ts) + 1, si i n'est pas self.

tab[i] ← {REQ, tsi}.

Envoi de {ACK, ts} à i.

Tentative d'entrée en SC.

ts ← max(tsi, ts) + 1, si i n'est pas self.

tab[i] ← {REL, tsi}.

Tentative d'entrée en SC.

Traitement : Réception {ACK, tsi} du processus i.

ts ← max(tsi, ts) + 1, si i n'est pas self.

Si tab[i] n'a pas comme type REQ,

    tab[i] ← {ACK, tsi}.

Tentative d'entrée en SC.

Pseudocode

Tentative d'entrée en SC.

Si tab[self] est de type REQ

Extraire toutes les heures logiques dans tab.

Si la plus ancienne appartient à self,

    enSC ← true

Pseudocode

Propriétés

Propriétés

Algorithme de Lamport

Correctness  Jamais plus d'un processus sera en SC à un instant T.

Progrès  Toute demande d'entrée en SC sera autorisée un jour.

Complexité

Communication par SC par processus :

Calcul  par événement :

3n(n-1)

O(n)  par réception de message

O(1) pour le reste.

Implémentation logicielle

Implémentation logicielle

Process i

Application

}

synchronized {

Abstraction mutex

request

release

accept

Abstraction réseau

REQ

ACK

REL

Implémenté comme une couche d'abstraction de mutex.

Couche d'abstraction réseau : indépendance de l'abstraction mutex et du système de communication choisi (tcp, udp, channels, etc).

Exercices

Exercice 1

Suppositions:

  • Un délai de transit de 2s existe pour toute communication.
  • Tout autre délai est relativement négligeable (e.g. traitement, copie, etc.)
  • Une SC dure 5s.

 

  • Les événements simultanés sont priorisés dans l'ordre suivant :
    • demande de SC, sortie de SC, gestion de message
    • le nom de l'émetteur sert à trier deux messages reçus simultanément

 

  • Deux processus dans le système, et initialement
    • A a un timestamp à 2,
    • B a un timestamp à 10.

 

A demandera la SC au bout d'une seconde, et B au bout de 4s.

Exercice 2

Mêmes conditions, mais

 

Trois processus, et initialement

  • A a un timestamp à 10,
  • B a un timestamp à 6,
  • C a un timestamp à 4.

 

Demandes de SC

  • A au bout de 1 seconde,
  • C au bout de 2 secondes.

Exercice 3

Amélioration ?

Ça fait beaucoup de messages...

 

Y a-t-il des messages qui peuvent être omis ?

 

Modifiez le pseudocode en conséquence.

Corrigé 1

Les cases inchangées sont laissées vides

Corrigé 2

Corrigé 3

Un ACK peut être omis si le message le plus récemment envoyé par l'émetteur est un REQ. En effet, Si un processus a envoyé un REQ, alors il sait que tout ACK qu'il enverra ensuite sera ignoré chez le destinataire, jusqu'à ce qu'il envoie un REL.

 

L'algorithme peut donc être changé de manière à ce qu'un ACK ne soit envoyé que si le tableau ne contient pas de REQ dans la position self.