Définition - Que signifie l'algorithme Black-White Bakery?
L'algorithme de boulangerie noir-blanc est une amélioration de l'algorithme de boulangerie de Lamport qui satisfait toutes les conditions d'un algorithme exclusif mutuel. Cet algorithme préserve l'algorithme de Lamport original tout en utilisant un nombre fini de registres atomiques de taille limitée et satisfait l'équité FIFO. Il est également adaptatif et satisfait la filature locale. L'algorithme de boulangerie noir-blanc est conçu pour fournir une solution logicielle à l'exclusion mutuelle.
Definir Tech explique l'algorithme de boulangerie noir-blanc
L'algorithme de boulangerie noir-blanc limite principalement la nature illimitée de l'algorithme de boulangerie Lamport en ajoutant un bit supplémentaire, qui aura une valeur de blanc ou de noir. C'est le premier algorithme (utilisant uniquement des registres atomiques) qui satisfait à la fois la FIFO et la rotation locale, et c'est le premier algorithme d'espace borné qui satisfait à la fois la FIFO et l'adaptivité. Il fonctionne sur le même principe en satisfaisant la procédure FIFO mais délimite les registres atomiques à travers une série d'étapes différentes. Cela fonctionne en attribuant à chaque processus un numéro de tour et à chaque ticket une couleur. Chaque processus doit attendre pour entrer dans la section critique jusqu'à ce que son numéro de ticket coloré soit le plus bas de son groupe. Si la couleur et le numéro de ticket de deux processus sont identiques, le processus avec le plus petit identifiant entrera dans un état critique.