Algorithme De La Boulangerie

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.

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 QUE

Sortie de la section critique

i indique le numéro du thread souhaitant sortir de la section critique.

COMPTEUR[i]=-1

Voir aussi

• Attente active

• Portail de l’informatique