Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de la boulangerie
Résumé
L'algorithme de la boulangerie (Lamport's bakery algorithm en anglais) est un algorithme d'exclusion mutuelle inventé par Leslie Lamport, dans le cadre général de machines multi-processeurs à mémoire partagée ne fournissant aucune opération atomique.
Dans sa forme originelle, il utilise de l'attente active avant l'entrée en section critique.
L'algorithme de la boulangerie peut être utilisé afin de réaliser une exclusion mutuelle sur toute machine multi-processeur, y compris celles qui ne fournissent pas d'opérations atomiques, ou qui en fournissent de simples ne permettant de réaliser qu'une seule opération mémoire (lecture ou écriture) à la fois.
Cependant, toutes les architectures modernes proposent des opérations atomiques combinant à la fois la lecture et l'écriture en une seule opération (comme Test And Set, Fetch And Add ou Compare And Swap). Ces dernières autorisent des implémentations de l'exclusion mutuelle plus efficaces.
L'algorithme de la boulangerie présente donc aujourd'hui principalement un intérêt théorique et pédagogique (lire la section Historique et propriétés pour plus de détails).
L'algorithme reprend l'intuition de la gestion d'une file d'attente dans un petit commerce (boulangerie) ou une administration (préfecture). Des numéros d'ordre croissants sont attribués (implicitement ou par des tickets) aux clients / usagers au fur et à mesure qu'ils se présentent, et ces derniers sont servis dans l'ordre des numéros.
Les différents fils d'exécution (ou processus) souhaitant entrer en section critique sont donc les analogues des clients / usagers. L'algorithme comporte schématiquement 3 phases:
Attribution d'un numéro d'ordre (ticket).
Attente de son tour avant l'entrée en section critique.
Sortie de la section critique.
L'analogie ne peut cependant être poursuivie car, contrairement à ce qui se passe dans la vie courante, plusieurs fils d'exécution peuvent occasionnellement obtenir le même numéro d'ordre lors de la première phase, ce qui nécessite un arbitrage ultérieur.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.