SDR

Jetons

Olivier Lemer

Mutex optimisées

Exercices

Fin de la semaine dernière

Exercice 2

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

 

  • 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é 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.

Amélioration 1

Motivation et algorithme

Amélioration 1

Repenser les messages

3 types de messages

REL

"Si jamais, j'ai fini ma SC."

ACK

"Je note que tu veux entrer en SC."

REQ

"Si jamais, moi je veux entrer en SC."

Remarques ?

Significations assez indirectes par rapport au but : entrer en SC.

REQ

"Si jamais, moi je veux entrer en SC."

OK

"Pour moi, tu peux entrer en SC."

Simplifier et aller droit au but.

Suggestion

Quantité d'information par message sous-optimale.

→ "Quand j'ai tous les OK, je peux entrer en SC."

App veut entrer en SC

App sort de SC

Réception d'un REQ

Réception d'un OK

J'envoie un REQ à tout le monde

Si je suis en SC

  • J'attends d'avoir fini, puis je réponds avec OK.

Si je ne suis pas en SC

  • Si je veux entrer en SC
  • Si je ne veux pas entrer en SC
  • Si j'ai la priorité, j'attends d'avoir fini, puis je réponds avec OK.
  • Si je n'ai pas la priorité, je réponds avec OK.

Je réponds par OK à tous les REQ en attente.

Je le comptabilise.

  • Si j'ai le OK de tout le monde, alors je peux entrer en SC.
  • Je réponds avec OK

Amélioration 1

Algorithme avec messages simplifiés

Amélioration 1

Exemple

B

A

C

REQ 2

Je ne suis pas en SC,

je ne veux pas y entrer,

A peut y aller.

t=1

t=1

t=1

Exemple

OK 3

OK 3

OK de tout le monde, je peux entrer

t=4

t=5

B

A

C

REQ 2

OK 3

OK 3

REQ 4

REQ 4

t=1

t=1

t=1

t=5

t=4

Exemple

Je suis en SC, pas OK pour moi que B entre.

t=6

OK 5

OK 7

J'ai fini, B peut entrer.

J'ai tous les OK, je peux entrer.

B

A

C

REQ 2

OK 3

REQ 4

REQ 4

t=1

t=4

t=1

t=1

t=5

Exemple

OK 3

t=6

OK 5

t=6

OK 7

J'ai fini, B peut entrer.

J'ai tous les OK, je peux entrer.

t=7

J'attends la SC et je suis prioritaire, je dis pas encore OK.

B

A

C

REQ 2

REQ 2

OK 3

OK 4

t=1

t=1

t=1

REQ 2

Exemple

J'attends la SC et je suis prioritaire, je dis pas encore OK.

OK 5

J'attends la SC mais ne suis pas prioritaire, A peut y aller.

OK 7

J'ai fini, B peut entrer.

J'ai tous les OK, je peux entrer.

Amélioration 1

Propriétés

Amélioration 1

a.k.a. Ricart et Agrawala, 1981

Propriétés

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é de communication

2(n-1) messages par processus souhaitant entrer en SC.

Ricart et Agrawala

Pseudocode

Pseudocode

Variables

n

entier, constant

nombre de processus

self

entier, entre 0 et n-1

mon numéro de processus

ts

entier, init 0

mon timestamp Lamport actuel

hasRequested

booléen, init false

ssi j'ai fait une demande de SC

selfRequestTs

entier

timestamp de cette demande

missingOKs

entier

nombre de OKs que j'attends encore

waitingPs

ensemble d'entiers

numéros des processus qui attendent mon OK.

Initialisation

Écouter infiniment les événements suivants:

Demande de SC de la couche applicative

Sortie de SC dans la couche applicative

Passage de missingOKs à 0

Réception de {REQ, tsi} du processus i

Réception de {OK, tsi} du processus i

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

Pseudocode

Traitement : Demande de SC de la couche applicative.

ts += 1

hasRequested ← true

selfRequestTs ← ts

missingOKs ← n-1

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

Traitement : Passage de missingOKs à 0.

Autorisation de la couche application d'entrer en SC.

Traitement : Sortie de SC par la couche applicative.

ts += 1

hasRequested ← false

Envoi de {OK, ts} à tous les processus de waitingPs

Réinitialisation de waitingPs

Pseudocode

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

ts ← max(tsi, ts) + 1

Si hasRequested et

  (selfRequestTs < tsi ou

  (SelfRequestTs == tsi et self < i))

    Ajout de i dans waitingPs

Sinon

    Envoi de {OK, ts} à i

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

ts ← max(tsi, ts) + 1

waitingOKs -= 1

Pseudocode

Exercices

Ricart et Agrawala

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 numéro d'é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.

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 numéro d'émetteur sert à trier deux messages reçus simultanément

 

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 2

Exercice 2

Voyez-vous une opportunité d'amélioration ?

Un scénario dans lequel on envoie plus de messages que nécessaire.

Exercice 3

Amélioration 1

Observations

Ricart et Agrawala, 1981

B

A

C

REQ

OK

Un cas particulier

REQ

OK

REQ

OK

REQ

OK

Amélioration 2

Ce cas particulier

2 types de messages

REQ

"Si jamais, moi je veux entrer en SC"

OK

"Pour moi, tu peux entrer en SC"

Suggestion

Tant qu'on ne m'a rien dit depuis "tu peux entrer en SC", je me permets.

Remarque

C'est comme partager un "jeton de permission" unique avec son voisin

REQ

"Passe-moi le jeton de permission"

OK

"Tiens"

Si j'ai tous les jetons de tous mes voisins, je fais ce que je veux.

Amélioration 2

Avec des jetons ?

Jeton de permission

Exemple 1

A

B

C

3 jetons :

A ↔︎ B : A

A ↔︎ C : A

B ↔︎ C : B

A a tous les jetons

A est en SC

A

B

C

3 jetons :

A ↔︎ B : A

A ↔︎ C : A

B ↔︎ C : B

REQ

"Je veux entrer en SC mais il me manque un jeton"

"J'ai encore besoin du jeton, B attendra"

Jeton de permission

Exemple 1

A

B

C

3 jetons :

A ↔︎ B : B

A ↔︎ C : A

B ↔︎ C : B

OK

"J'ai fini ma SC, tiens"

"J'ai tous les jetons,   je peux entrer en SC"

Jeton de permission

Exemple 1

A

B

C

3 jetons :

A ↔︎ B : B

A ↔︎ C : A

B ↔︎ C : B

"J'ai fini, personne n'a envie de mes jetons, je les garde."

Jeton de permission

Exemple 1

A

B

C

3 jetons :

A ↔︎ B : B

A ↔︎ C : A

B ↔︎ C : B

"Je veux entrer en SC,

j'ai encore tous les jetons,

je peux y aller."

Jeton de permission

Exemple 1

Exemple 2

A

B

C

Jeton de permission

Exemple 2

A

B

C

"Je veux entrer en SC,

j'ai besoin du jeton de B"

"Je veux entrer en SC,

j'ai besoin des deux jetons"

REQ,4

REQ,2

REQ,2

"J'ai encore besoin des jetons,

ils attendront."

Jeton de permission

Exemple 2

A

B

C

"Tu as la priorité sur moi, donc d'accord, prends"

REQ,2

Jeton de permission

Exemple 2

A

B

C

"Tu as la priorité sur moi, donc d'accord, prends"

OK,5

"Mais je le re-veux après"

REQ,4

Jeton de permission

Exemple 2

Amélioration 2

Algorithme & Propriétés

Algorithme

Avec 1 jeton par voisin

App veut entrer en SC

App sort de SC

Réception d'un REQ

Réception d'un OK

J'envoie un REQ à ceux qui ont le jeton.

Si je suis en SC

  • J'attends d'avoir fini, puis je passe le jeton.

Si je ne suis pas en SC

  • Si je veux entrer en SC
  • Si je ne veux pas entrer en SC
  • Si j'ai la priorité, j'attends d'avoir fini, puis je passe le jeton.
  • Si je n'ai pas la priorité, je passe le jeton, et je renvoie mon REQ.

Je passe mon jeton à tous les demandeurs.

Je note avoir reçu le jeton.

  • Je passe le jeton.

Le req initial est renvoyé, avec son timestamp d'origine.

Si j'ai tous les jetons

Je peux entrer en SC quand je veux.

Amélioration 2

a.k.a. Carvalho et Roucairol, 1982

Propriétés

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é de communication

Entre 0 et 2(n-1) messages par processus souhaitant entrer en SC.

Carvalho et Roucairol

Pseudocode

Pseudocode

Variables

n

entier, constant

nombre de processus

self

entier, entre 0 et n-1

mon numéro de processus

ts

entier, init 0

mon timestamp Lamport actuel

hasRequested

booléen, init false

ssi j'ai fait une demande de SC

selfRequestTs

entier

timestamp de cette demande

requesters

ensemble d'entiers

numéros des processus

qui attendent mon jeton.

jetons

ensemble d'entiers

numéros des processus

Initialement arbitraire.

dont j'ai le jeton.

Initialisation

Écouter infiniment les événements suivants:

Demande de SC de la couche applicative

Sortie de SC dans la couche applicative

Réception de {REQ, tsi} du processus i

Réception de {OK, tsi} du processus i

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

Pseudocode

Traitement : Demande de SC de la couche applicative.

ts += 1

hasRequested ← true

selfRequestTs ← ts

Pour chaque processus i qui n'est pas dans jetons :

    Envoi de {REQ, ts}

Si jetons a une taille n, entrer en SC

Traitement : Sortie de SC par la couche applicative.

ts += 1

hasRequested ← false

Pour tout i dans requesters :

    Envoi de {OK, ts}

    jetons.remove(i)

Réinitialisation de requesters

Pseudocode

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

ts ← max(tsi, ts) + 1

Si hasRequested et

  (selfRequestTs < tsi ou

  (SelfRequestTs == tsi et self < i))

    Ajout de i dans requesters

Sinon

    Envoi de {OK, ts} à i

    jetons.remove(i)

    Si hasRequested

        Envoi de {REQ, selfRequestTs} à i

Pseudocode

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

ts ← max(tsi, ts) + 1

jetons.add(i)

Si jetons a une taille n et hasRequested :

    Entrer en SC

Pseudocode

Carvalho et Roucairol

Exercices

Exercice

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 numéro d'émetteur sert à trier deux messages reçus simultanément

 

Trois processus dans le système, et initialement

  • A a un timestamp à 5, et possède les jetons de B et C,
  • B a un timestamp à 2, et possède le jeton de C,
  • C a un timestamp à 8.

 

Les demandes d'entrée en section critiques sont faites :

  • par A : au bout de 4s
  • par B : au bout de 1s
  • par C : au bout de 4s