- Algorithme de Lamport
-
Algorithme de la boulangerie
Les méthodes de synchronisation
L'algorithme de la boulangerie est un algorithme d'exclusion mutuelle inventé par Leslie Lamport. Il utilise de l'attente active pour garantir l'exclusion mutuelle.Sommaire
L'algorithme
L'algorithme reprend le principe de la file d'attente dans un petit magasin (boulangerie) le dernier arrivé s'attribue lui-même un numéro d'ordre derrière les arrivants précédents.
Pour garantir l'exclusion mutuelle avec N tâches, on dispose de deux tableaux de dimension N (nommés par la suite CHOIX et COMPTEUR). L'algorithme est en trois parties: l'initialisation, l'entrée en section critique et la sortie de la section critique.
Initialisation
Initialiser toutes les cases de COMPTEUR à -1. Initialiser toutes les cases de CHOIX à 0. Initialiser CHOIX_EN_COURS à 0
Entrée en section critique
i indique le numéro du thread souhaitant entrer en section critique.
' On ne s'attribue un ticket que si personne n'est en train de s'attribuer un ticket TANT QUE CHOIX_EN_COURS=1 rien FIN TANT QUE ' On s'attribue un ticket CHOIX_EN_COURS = 1 CHOIX[i]=1 POUR J=0 A N-1 FAIRE SI COMPTEUR[i]<=COMPTEUR[j] ALORS COMPTEUR[i]=COMPTEUR[j] +1 FIN SI FIN POUR J CHOIX[i]=0 CHOIX_EN_COURS = 0 ' On attend notre tour : on attend que tous les numéros inférieurs soient passés J = (i + 1) modulo N TANT QUE J <> i FAIRE ' Pendant qu'un thread s'attribue un ticket, la valeur du ticket n'est pas fiable TANT QUE CHOIX[j]=1 rien FIN TANT QUE SI COMPTEUR[i] > COMPTEUR[j] ET COMPTEUR[j] <> -1 ALORS TANT QUE COMPTEUR[j] <> -1 FAIRE rien FIN TANT QUE FIN SI J = (J + 1) modulo N FIN TANT QUESortie de la section critique
i indique le numéro du thread souhaitant sortir de la section critique.
COMPTEUR[i]=-1
Voir aussi
Portail de l’informatique
Catégories : Algorithme d'exclusion mutuelle | Attente active
Wikimedia Foundation. 2010.
