Algorithme de la boulangerie - Définition

Intuition

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:

1. Attribution d'un numéro d'ordre (ticket).
2. Attente de son tour avant l'entrée en section critique.
3. 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.

Historique et Propriétés

L'algorithme de la boulangerie a été introduit par Leslie Lamport en 1974, comme une solution à un problème initialement posé et résolu par Edsger Dijkstra en 1965 (voir Algorithme d'exclusion mutuelle de Dijkstra).

Le problème original était de fournir un algorithme réalisant l'exclusion mutuelle de N processus, utilisant uniquement des opérations atomiques simples (une seule lecture ou écriture à la fois) et vérifiant certaines propriétés :

• Symétrie de l'algorithme (aucun processus n'est favorisé a priori).
• Interblocage apparent impossible (pas de séquence du type: après vous, après vous).
• Support de processus aux vitesses d'exécution différentes.
• Un processus bloqué hors de la section critique ne doit pas empêcher d'autres processus d'y entrer.

L'algorithme de la boulangerie est en réalité une solution à un problème plus large, puisque, en plus des propriétés précédentes, il possède les suivantes :

• Aucune famine n'est possible.
• Les opérations de lecture et d'écriture dans les tableaux partagés n'ont pas besoin d'être atomiques.

Le premier point résulte de l'obligation pour un fil d'obtenir un nouveau ticket afin de rentrer dans la section critique une nouvelle fois. Ce nouveau ticket a nécessairement un numéro d'ordre strictement supérieur à celui de l'ancien ticket, à moins que les autres fils ne soient tous hors de la section critique et ne cherchent pas à y entrer. Un fil qui cherche à entrer dans la section critique est donc certain d'y entrer au plus tard lorsque tous les autres fils ayant exécuté la première phase de manière concurrente vis-à-vis de lui sont passés dans la section critique une seule fois.

Le second point est particulièrement remarquable et délicat à assimiler. Il résulte de plusieurs caractéristiques de l'algorithme. En premier lieu, ce dernier n'utilise pas d'écritures concurrentes aux mêmes adresses mémoire. Le fil ID, et lui seul, peut écrire dans CHOIX[ID] et COMPTEUR[ID]. En second lieu, les valeurs de CHOIX[ID] sont booléennes, ce qui implique que n'importe quel changement de valeur est visible au travers d'un seul bit, et la modification de ce dernier est nécessairement atomique. Autrement dit, les changements de CHOIX[ID] sont perçus de manière atomique. En troisième lieu, l'utilisation de CHOIX sérialise tout accès concurrent à COMPTEUR[J], à l'exception de ceux se produisant entre fils en train d'exécuter la première phase en même temps. Dans ce dernier cas, les fils peuvent obtenir des numéros de tickets différents, mais ils attendront tous mutuellement que leurs valeurs soient visibles dans la deuxième phase, et un seul fil finira par accéder à la section critique. Par ailleurs, si un fil K était déjà dans la deuxième phase avant que les premiers ne commencent l'exécution de la première phase, alors son COMPTEUR[K] a nécessairement été lu correctement pour le calcul du maximum et les nouveaux tickets sont nécessairement supérieurs à celui-ci, même si on ne peut prévoir leur ordre relatif. Une démonstration plus formelle est disponible dans l'article original de Leslie Lamport.

La littérature présente parfois sous le nom d'algorithme de la boulangerie de légères variantes qui, en réalité, sont plus faibles que l'original, car elles ne vérifient pas toutes les propriétés énoncées plus haut, et notamment la dernière (lecture et écriture non nécessairement atomiques). La variante consistant, par exemple, à supprimer le tableau CHOIX et à le remplacer par l'utilisation d'une nouvelle valeur spéciale dans les cases de COMPTEUR, ne fonctionne pas sans opération atomique.