Fiche de révision : Algorithme de la boulangerie

Plan du Cours

  1. Accès concurrent à une ressource
  2. Tickets et variables de coordination
  3. Étapes de l’algorithme
  4. Garanties et limites

1. Accès concurrent à une ressource

Notions clés & Définitions

  • Exclusion mutuelle : Garantit qu’un seul processus à la fois accède à la section critique d’une ressource partagée.
  • Section critique : Partie du code qui utilise la ressource partagée.
  • Processus : Programme en cours d’exécution.
  • Concurrence : Exécution de plusieurs processus au même moment.

Points essentiels

  • Dans une billetterie, vendre simultanément la dernière place à deux clients illustre le risque de conflit sur une ressource partagée.

Astuce mémo

Un seul processus en section critique, jamais deux

2. Tickets et variables de coordination

Notions clés & Définitions

  • number[i] : Contient le numéro de ticket du processus i, et vaut 0 lorsque ce processus ne demande pas l’accès.
  • choosing[i] : Indique si le processus i est en train de choisir son numéro de ticket.

★ À maîtriser

📌 Si deux processus ont le même numéro de ticket, l’identifiant du processus, comme un PID, départage l’égalité.

  • L’analogie de l’algorithme est celle de clients qui prennent un ticket et où le plus petit numéro passe en premier.

Compléments

  • L’algorithme de la boulangerie est attribué à Leslie Lamport en 1974, et Lamport a reçu le prix Turing en 2013.

3. Étapes de l’algorithme

★ À maîtriser

  • Pour accéder à la section critique, le processus met choosing[i] à vrai, attribue à number[i] le maximum des numéros plus 1, remet choosing[i] à faux, attend que chaque autre processus ait fini de choisir puis que son tour arrive, entre en section critique et remet number[i] à 0 en sortant.

Compléments

  • La variable choosing empêche un processus de se comparer à un numéro qu’un autre processus est encore en train de calculer.

  • Deux processus peuvent prendre le même numéro, et un processus ne connaît pas instantanément le numéro encore en cours de calcul par un autre.

Astuce mémo

Choisir, annoncer, attendre, entrer, libérer

4. Garanties et limites

Notions clés & Définitions

  • Attente active : Fait qu’un processus boucle en attendant son tour.

★ À maîtriser

  • L’algorithme assure l’exclusion mutuelle et l’équité selon le principe du premier arrivé, premier servi.

  • Sans coordination, des résultats faux peuvent survenir même si chaque programme est correct.

Compléments

  • L’algorithme ne nécessite pas de matériel spécial ni d’opération atomique.

  • Si un processus tombe en panne, son numéro retombe à 0.

  • Les numéros de ticket peuvent croître indéfiniment.

Astuce mémo

L’identifiant départage les égalités, il ne donne pas une priorité

Teste tes connaissances

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

1. Deux processus tentent d’accéder à une ressource partagée dont une opération ne peut pas être exécutée simultanément sans conflit. Quelle règle d’accès assure l’exclusion mutuelle ?

2. Un processus constate qu’un autre processus est encore en train de calculer son numéro de ticket. Quel rôle joue alors la variable « choosing » ?

Faire le QCM →

Révisez avec les flashcards

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

Que garantit l’exclusion mutuelle concernant l’accès à une section critique ?

Un seul processus à la fois y accède.

Qu’est-ce qu’une section critique ?

La partie du code qui utilise la ressource partagée.

Dans l’analogie de l’algorithme de la boulangerie, qui passe en premier ?

Le client ayant le plus petit numéro de ticket.

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