Deux lectures simultanées de la dernière place → deux ventes
★ À maîtriser
📌 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.
Le ticket décide d’abord ; l’identifiant départage seulement l’égalité
★ À maîtriser
📌 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
Signaler, prendre un numéro, attendre, entrer, remettre à zéro
★ À 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.
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.
★ À 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 tolère la panne d’un processus à condition que ses variables retombent à number[i] = 0 et choosing[i] = faux.
★ À 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.
File jamais vide → numéros sans fin et dépassement possible
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) :
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.
Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.
Générateur de fiches