Algorithme De La Boulangerie

Algorithme de la boulangerie

Les méthodes de synchronisation

Barrière de synchronisation - Futex - Moniteur

Mutex - Sémaphore - Spinlock


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 QUE

Sortie 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 Portail de l’informatique
Ce document provient de « Algorithme de la boulangerie ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme De La Boulangerie de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme de la boulangerie — L algorithme de la boulangerie (Lamport s bakery algorithm en anglais) est un algorithme d exclusion mutuelle découvert par Leslie Lamport[1], dans le cadre général de machines multi processeurs à mémoire partagée ne fournissant aucune opération… …   Wikipédia en Français

  • Algorithme de Lamport — Algorithme de la boulangerie Les méthodes de synchronisation Barrière de synchronisation  Futex  Moniteur Mutex  Sémaphore  Spinlock L …   Wikipédia en Français

  • Liste Des Algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique …   Wikipédia en Français

  • Liste des algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique …   Wikipédia en Français

  • Leslie Lamport — est un chercheur en informatique américain, spécialiste de l algorithmique répartie. Il est né en 1941 à New York et a fait des études en mathématiques au Massachusetts Institute of Technology (MIT) puis à l université de Brandeis. Il a notamment …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”