Fiche de révision : Algorithme de la boulangerie

Plan du Cours

  1. Concurrence et section critique
  2. Tickets et ordre de passage
  3. Variables et étapes de l’algorithme
  4. Choix du numéro et attente
  5. Garanties et conditions de panne
  6. Limites et origine de l’algorithme

1. Concurrence et section critique

Notions clés & Définitions

  • Section critique : Partie du code qui utilise la ressource partagée.
  • Exclusion mutuelle : Garantit qu’un seul processus à la fois se trouve dans la section critique.
  • Processus : Programme en cours d’exécution.
  • Ressource partagée : Donnée utilisée par plusieurs processus.
  • Concurrence : Plusieurs processus exécutés en même temps ou de façon entrelacée.

Points essentiels

  • Dans une billetterie avec une dernière place, deux clics peuvent lire chacun « 1 place » avant qu’un des deux n’écrive « 0 », ce qui peut provoquer la vente de deux billets.

Astuce mémo

Deux lectures simultanées de la dernière place → deux ventes

2. Tickets et ordre de passage

★ À maîtriser

  • Dans l’analogie de la boulangerie, chaque processus prend un ticket et le plus petit numéro passe en premier.

📌 Lorsque deux processus ont le même numéro, celui dont l’identifiant fixe et unique est le plus petit passe en premier.

Compléments

  • L’identifiant est l’indice i des tableaux et peut être assimilé à un PID, sans être nécessairement le PID du système d’exploitation.

  • L’arrivée, au sens du premier arrivé premier servi, correspond au moment où le processus a fini de prendre son ticket.

Astuce mémo

Le ticket décide d’abord ; l’identifiant départage seulement l’égalité

3. Variables et étapes de l’algorithme

Notions clés & Définitions

  • choosing[i] : Variable qui indique si le processus i est en train de choisir son numéro.
  • number[i] : Variable qui contient le numéro attribué au processus i, la valeur 0 signifiant qu’il ne demande pas l’accès.

★ À maîtriser

  • 🔄 Chaque processus suit six étapes :
    1. Signaler qu’il choisit son numéro avec choosing[i] = vrai.
    2. Prendre number[i] = max + 1.
    3. Terminer son choix avec choosing[i] = faux.
    4. Attendre son tour.
    5. Exécuter la section critique.
    6. Remettre number[i] à 0.

📌 Pour choisir son numéro, un processus prend le maximum des valeurs du tableau number, lu case par case, sans compter les zéros, puis ajoute 1.

Compléments

  • Pour number = [1, 0, 2], le maximum pris en compte est 2 et le nouveau numéro attribué est 3.

Astuce mémo

Signaler, prendre un numéro, attendre, entrer, remettre à zéro

4. Choix du numéro et attente

★ À maîtriser

📌 Avant de comparer les numéros, un processus attend que chaque autre processus j ait terminé son choix, c’est-à-dire que choosing[j] soit faux.

📌 Après cette attente, le processus i attend j seulement si number[j] est non nul et si le couple (number[i], i) est supérieur au couple (number[j], j) dans l’ordre lexicographique.

  • Le tableau choosing empêche un processus de comparer avec le numéro d’un autre processus qui est encore en train de le calculer.

Compléments

  • Pour un processus C de couple (2, id 3), un processus B de couple (2, id 2) est devant lui, tandis qu’un processus A dont le numéro vaut 0 ne le gêne pas.

  • Sans choosing, C peut voir number[B] = 0 et entrer après avoir choisi le numéro 2, puis B peut écrire lui aussi 2 et entrer, ce qui laisse deux processus dans la section critique.

5. Garanties et conditions de panne

Notions clés & Définitions

  • Opération atomique : Action matérielle non interruptible, comme test-and-set.

★ À maîtriser

  • L’algorithme garantit l’exclusion mutuelle, c’est-à-dire qu’un seul processus accède à la section critique à la fois.

  • L’algorithme vise l’équité selon le principe du premier arrivé premier servi, l’arrivée étant définie par la fin de la prise du ticket.

Compléments

  • L’algorithme organise la coordination de l’accès à la ressource partagée sans opération matérielle atomique, car chaque processus n’écrit que dans ses propres cases et lit celles des autres.

📌 L’algorithme tolère la panne d’un processus à condition que ses variables retombent à number[i] = 0 et choosing[i] = faux.

  • Si un processus plante en conservant un ticket non nul, les autres processus peuvent attendre indéfiniment.

6. Limites et origine de l’algorithme

Notions clés & Définitions

  • Attente active : Attente durant laquelle le processus ne dort pas, mais boucle et vérifie sans cesse si son tour est arrivé.

★ À maîtriser

  • L’algorithme de la boulangerie a été imaginé par Leslie Lamport en 1974.

  • L’algorithme est inspiré des tickets d’une boulangerie et organise l’accès à une ressource partagée afin d’éviter les conflits.

  • Les numéros peuvent croître indéfiniment lorsque la file ne se vide jamais, ce qui peut entraîner un dépassement.

Compléments

  • Leslie Lamport a reçu le prix Turing en 2013 pour ses travaux sur les systèmes répartis.

  • L’exemple de la billetterie illustre le problème de concurrence, mais ne prouve pas que les plateformes utilisent cet algorithme.

Astuce mémo

File jamais vide → numéros sans fin et dépassement possible

Teste tes connaissances

Teste tes connaissances sur Algorithme de la boulangerie avec 9 questions à choix multiples et corrections détaillées.

1. Concernant les notions liées à la concurrence :

2. Dans une billetterie affichant une dernière place, deux clics lisent « 1 place » avant toute écriture. Concernant cette situation, cochez la (les) proposition(s) exacte(s) :

Faire le QCM →

Révisez avec les flashcards

Mémorisez les concepts clés de Algorithme de la boulangerie avec 10 flashcards interactives.

Dans l’analogie de la boulangerie, quel ticket donne la priorité ?

Le ticket portant le plus petit numéro.

Pour départager deux processus ayant le même numéro, quelle règle s’applique ?

Le processus dont l’identifiant fixe et unique est le plus petit passe en premier.

Qu’est-ce qu’un processus en informatique ?

Un programme en cours d’exécution.

Voir les flashcards →

Cours similaires

Crée tes propres fiches de révision

Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.

Générateur de fiches