SDR

Jetons

Olivier Lemer

Mutex à jeton unique

Rappels

Suppositions

Pas de duplication de message

Pas de perte de message

Pas de changement d'ordre de message

Pas de panne de processus

Concepts

Horloge logique

Heure virtuelle donnée à tout évènement, tel qu'un ordre strict existe.

Mutex

Un seul processus à la fois ne peut être dans l'état SC.

Lamport

"Si ma requête est le plus ancien message que j'aie reçu, je peux entrer en SC"

Ricart et Agrawala

"Si tout le monde est OK que je le fasse, je peux entrer en SC"

Carvalho et Roucairol

"Si j'ai les jeton de tout le monde, je peux entrer en SC"

"Je suis responsable de maintenir une idée de l'état des autres."

"Je ne suis responsable que de dire quand c'est bon pour moi qu'un autre soit en SC."

"Je ne suis responsable que de donner mon jeton si je n'en ai pas besoin"

Carvalho et Ricairol

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.

Carvalho et Roucairol

Remise en jambes

Suppositions:

Un délai de transite 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

Jetons : un ou plusieurs ?

Programmation par jetons

Algorithme par jetons

Un jeton par paire de voisins.

"Il me faut le jeton de tout le monde

pour avoir le droit d'être en SC."

Algorithme par jetons

Un jeton, tout court.

"Il me faut le jeton

pour avoir le droit d'être en SC."

Algorithme par jeton unique

Enjeux

Unicité (Correctness)

Transmission

Progrès

Assurer que le jeton ne sera pas dupliqué ni perdu

Gérer le transit du jeton d'un demandeur à un autre

Assurer que tout demandeur aura le jeton un jour

En général, trouver un protocole de transmission assurant unicité et progrès.

Mutex sur un cercle

Idée

Solution simple

Jeton transite sur la boucle infiniment

Solution simple

Jeton transite sur la boucle infiniment

Solution simple

Jeton transite sur la boucle infiniment

Un demandeur attend que le jeton lui arrive

Solution simple

Jeton transite sur la boucle infiniment

Un demandeur attend que le jeton lui arrive

Solution simple

Jeton transite sur la boucle infiniment

Un demandeur attend que le jeton lui arrive

Inefficace

Temps d'attente linéaire après requête.

Avantages

Correctness évidente

Un seul jeton, donc une seule SC

Progrès évident

Jeton passe chez tout le monde périodiquement

Inhérent à tout algo à jeton unique

Inévitable

Évitable

Mutex sur un arbre

Idée

L'arbre - une autre structure

Efficacité

S'il est équilibré, distances logarithmiques.

Simplicité

Un seul chemin entre tous deux points.

Réalisme

Les vrais réseaux sont rarement des cliques.

(Pourra être intégré sur un réseau plus complet)

Mutex sur un arbre

Trouver où se trouve le jeton

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

A

B

C

D

E

F

"E m'a fait la demande"

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

"B m'a fait la demande"

Mutex sur un arbre

Implications du choix de l'arbre

Transmettre les requêtes via ces liens.

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

A

B

C

D

E

F

"E m'a fait la demande"

Les maintenir ainsi.

Mutex sur un arbre

Implications du choix de l'arbre

"tiens"

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

A

B

C

D

E

F

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

Mutex sur un arbre

Implications du choix de l'arbre

Les maintenir ainsi.

"tiens"

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

A

B

C

D

E

F

"D demande le jeton"

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

"B demande le jeton"

Mutex sur un arbre

Implications du choix de l'arbre

Les maintenir ainsi.

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

A

B

C

D

E

F

"D demande le jeton"

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

sous forme de FIFO

"A demande le jeton"

"B demande le jeton"

Mutex sur un arbre

Implications du choix de l'arbre

Les maintenir ainsi.

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

A

B

C

D

E

F

"D demande le jeton"

"A demande le jeton"

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

sous forme de FIFO

Mutex sur un arbre

Implications du choix de l'arbre

Les maintenir ainsi.

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

A

B

C

D

E

F

"A demande le jeton"

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

sous forme de FIFO

Mutex sur un arbre

Implications du choix de l'arbre

Les maintenir ainsi.

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

A

B

C

D

E

F

"A demande le jeton"

"B demande le jeton"

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

sous forme de FIFO

Et envoyer une requête après le jeton s'il y en a d'autres dans la queue

Mutex sur un arbre

Implications du choix de l'arbre

Les maintenir ainsi.

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

A

B

C

D

E

F

"A demande le jeton"

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

sous forme de FIFO

Et envoyer une requête après le jeton s'il y en a d'autres dans la queue

Mutex sur un arbre

Implications du choix de l'arbre

Les maintenir ainsi.

Repasser à un système de requêtes

REQ

"Donne-moi le jeton"

OK

"Tiens"

Trouver où se trouve le jeton

Rendre les liens dirigés

vers le voisin le plus proche du jeton.

A

B

C

D

E

F

Se souvenir d'où la requête vient

Se souvenir de "qui m'a demandé le jeton"

sous forme de FIFO

Et envoyer une requête après le jeton s'il y en a d'autres dans la queue

Mutex sur un arbre

Implications du choix de l'arbre

Les maintenir ainsi.

Mutex sur un arbre

Résumé

Algorithme par jeton unique

Résumé

Deux messages

REQ

"Donne-moi le jeton"

OK

"Tiens"

Une file d'attente par processus

Des liens toujours dirigés vers le jeton

Maintenu à jour quand le jeton bouge.

Permet de savoir où envoyer une requête.

Maintient la liste des demandes de jeton.

Permet de savoir à qui renvoyer le jeton.

Renvoi d'une requête après le jeton si besoin

Permet d'informer le nouveau possesseur qu'il s'appelle "reviens".

App veut entrer en SC

App sort de SC

Réception d'un REQ

Réception d'un OK

Envoie d'un REQ à moi-même

Si ma file est vide, ne rien faire

Si c'est moi

Décider quoi faire du jeton

Algorithme par jeton unique

Si c'est un autre processus p

J'entre en SC

Je lui passe le jeton

Mon parent devient p

Si ma file d'attente n'est pas vide

J'envoie un REQ à p

Décider quoi faire du jeton

Push l'envoyeur dans ma file

Si je n'ai pas le jeton

Si j'ai le jeton

Si je n'ai pas de REQ en attente

Décider quoi faire du jeton

J'envoie un REQ à mon parent

On push le voisin qui nous a fait le requête, pas le processus qui en est à l'origine

Sinon, pop la tête de ma file

Mutex sur un arbre

Exemple

A

B

C

D

F

E

[]

Exemple

A

B

C

D

F

E

[]

Exemple

A

B

C

D

F

E

REQ

[A]

[B]

[D]

[A]

[]

REQ

Exemple

A

B

C

D

F

E

[A]

[B,C]

[D]

[A]

[C]

[]

REQ

"Déjà envoyé une requête à F"

Exemple

A

B

C

D

F

E

[A]

[B,C,D]

[D]

[A]

[C]

[]

"Déjà envoyé une requête à F"

Exemple

A

B

C

D

F

E

[A]

[B,C,D]

[]

[A]

[C]

[]

OK

Exemple

A

B

C

D

F

E

[A]

[C,D]

[]

[A]

[C]

[]

OK

"B est pop, je lui passe, mais il doit me le rendre"

REQ

Exemple

A

B

C

D

F

E

[]

[C,D]

[]

[A]

[C]

[]

OK

REQ

"Je forward le jeton"

Exemple

A

B

C

D

F

E

[D]

[C,D]

[]

[C]

[]

REQ

"Je reçois une requête,

je la passe plus loin"

Exemple

A

B

C

D

F

E

[D]

[C,D]

[]

[B]

[C]

[]

REQ

Exemple

A

B

C

D

F

E

[D]

[C,D]

[]

[C]

[]

OK

Exemple

A

B

C

D

F

E

[]

[C,D]

[]

[C]

[]

OK

Exemple

A

B

C

D

F

E

[]

[D]

[]

OK

REQ

Exemple

A

B

C

D

F

E

[]

[D]

[]

[D]

[]

Exemple

A

B

C

D

F

E

[]

REQ

Exemple

A

B

C

D

F

E

[]

Exemple

B

A

C

D

E

F

[A]

[B]

[D]

[C]

[B,C]

[]

[C,D]

[]

[B]

[D]

[]

[D]

[B,C,D]

REQ

OK

REQ

OK

REQ

OK

REQ

[]

[D]

[]

OK

[]

Algorithme de Raymond

Propriétés & Pseudocode

Algorithme par jeton unique

aka : Raymond, 1989

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

2log(n) par demande d'entrée en SC si l'arbre est équilibré.

Pseudocode

Variables

self

entier, constant

mon numéro de processus

hasRequested

booléen, init false

ssi j'ai fait une demande de SC

parent

entier

id du processus parent dans l'arbre

queue

FIFO

Processus ayant fait une requête

inSC

booléen, init false

ssi je suis actuellement en SC

Note : on appelle parent le processus dans la direction duquel aller pour se diriger vers le jeton.

Ainsi, si parent est nil, alors on peut dire qu'on a le jeton.

Initialisation

Écouter infiniment les événements suivants :

Demande d'entrée en SC

Réception de REQ

Réception de OK

Sortie de SC

Pseudocode

Traitement : Demande de SC de la couche applicative

Envoi de REQ à self

hasRequested ← true

Traitement : Réception de REQ de la part de i

Push i dans queue

Si parent est nil

Exécuter handleJeton

Sinon, si hasRequested est false

Envoyer REQ à parent

Pseudocode

Traitement : Réception de OK de la part de i

Exécuter handleJeton

Traitement : Sortie de SC de la couche applicative

Exécuter handleJeton

Pseudocode

Fonction handleJeton

Si queue est vide, sortir de cette fonction.

p ← queue.pop()

Si p vaut self

parent ← nil

Entrer en SC

hasRequested ← false

Sinon

Envoyer OK à p

parent ← p

Si queue n'est pas vide

Envoyer REQ à p

Pseudocode

Exercice

Algorithme de Raymond

Exercice

Graphe initial ci-contre.

Durées :

1s par transit de message
5s par SC
1s entre l'envoi de tous 2 messages

Deux événements arrivant au même moment sont traités dans l'ordre suivant :

demande de SC, fin de SC, message (dans l'ordre des IDs de l'émetteur).

D, E, B demandent la SC après 1s
A demande la SC après 2s

A

B

C

D

[]

E

[]

Correction

Algorithme de Raymond

Réflexion pour la prochaine fois

Un processus qui a fait une demande de SC peut être forcé de faire passer le jeton à sa tête de file, puis envoyer une requête pour qu'on le lui rende ensuite.

Ceci rend l'algorithme équitable, mais est sous-optimal en terme de communication.

Proposez une solution qui réduise le nombre de déplacements du jeton dans ce genre de situation, sans risquer la famine (qu'un demandeur ne puisse jamais entrer en SC).