Algorithme de Lamport

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 Lamport de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme de Ricart et Agrawala — L Algorithme Ricart Agrawala est un algorithme d exclusion mutuelle sur un système distribué. Cet algorithme est une extension et une optimisation de l algorithme de Lamport, en supprimant la nécessité de communiquer un messages de libération. Il …   Wikipédia en Français

  • 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

  • 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 Naimi-Trehel — L algorithme de Naimi Trehel assure l exclusion mutuelle dans les systèmes distribués. Cet algorithme réduit le nombre moyen de messages à log(n)en introduisant une structure arborescente logique et un jeton. L algorithme a été présenté en 1987… …   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

  • Liste D'informaticiens Et Précurseurs De L'informatique — Cette liste regroupe des informaticiens (concepteur, développeur, chercheur en informatique) ainsi que des mathématiciens ou théoriciens dont les travaux ont établi, avant l invention des ordinateurs, les bases de l informatique moderne (travaux… …   Wikipédia en Français

  • Liste d'informaticiens et precurseurs de l'informatique — Liste d informaticiens et précurseurs de l informatique Cette liste regroupe des informaticiens (concepteur, développeur, chercheur en informatique) ainsi que des mathématiciens ou théoriciens dont les travaux ont établi, avant l invention des… …   Wikipédia en Français

  • Liste d'informaticiens et précurseurs de l'informatique — Cette liste regroupe des informaticiens (concepteur, développeur, chercheur en informatique) ainsi que des mathématiciens ou théoriciens dont les travaux ont établi, avant l invention des ordinateurs, les bases de l informatique moderne (travaux… …   Wikipédia en Français

  • Autostabilisation — L autostabilisation, ou auto stabilisation, est la propriété d un système réparti, composé de plusieurs machines capables de communiquer entre elles, qui consiste, lorsque le système est mal initialisé ou perturbé, à retourner automatiquement à… …   Wikipédia en Français

  • Parallélisme (informatique) — Pour les articles homonymes, voir parallèle. Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000 En informatiqu …   Wikipédia en Français

Share the article and excerpts

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