Discussion:Algorithme de la boulangerie

Anciennes versions

L'algorithme présent présentait plusieurs erreurs : Affectation à CHOIX au lieu de CHOIX[i] oublie du modulo sur le J=i+1 Erreurs sur l'attente en début de boucle TANT QUE J : on attend pas tant que choix[i] <> 1 (ce qui est garanti au dessus), mais bien tant que choix[j]=1

Par ailleurs, j'ai détaillé la ligne COMPTEUR = 1 + max(COMPTEUR) qui voulait dire COMPTEUR[i]=1 + max (COMPTEUR[0],...,COMPTEUR[N-1]) et rajouté une exclusion en début de d'algorithme. En effet, si on considère que l'auto attribution du compteur est non-interruptible, cette section est inutile mais aussi la boucle TANTQUE CHOIX[j]=1, puisque que COMPEUR[i] est certes indéterminé mais égal soit à -1 soit à une valeur supérieur que compteur[j] donc l'effet est le même par la suite. Si elle est interruptible, deux thread pourraient s'attribuer le même ticket

Maintenant, j'espère qu'il n'y a plus d'erreur dans l'algorithme... (à relire !!) Ulrich Von Beck 7 mars 2008 à 15:00 (CET)

Réécriture de la page

Bonjour,

J'ai réécrit la page entièrement pour 2 raisons: l'algorithme présenté était toujours incorrect et il y avait trop peu d'explications (ou bien elles étaient fausses) concernant ses prérequis et son fonctionnement.

J'en ai profité pour y ajouter un petit historique ainsi qu'une comparaison (implicite) avec l'algorithme de Dijkstra. Ce dernier mérite une page à lui tout seul, qu'il faudra créer ultérieurement (ce que je finirai par faire quand j'aurai le temps).

Si vous pensez qu'il y a une erreur conceptuelle dans la description de l'algorithme, je vous saurais gré d'en discuter AVANT de faire des modifications. Le plus probable est en effet que vous soyiez vous-même en train de commettre une erreur. Il ne s'agit pas de prétention déplacée de ma part, mais simplement la conséquence d'avoir passé énormément de temps à décortiquer l'algorithme, à l'implémenter et à l'enseigner. Je sais donc d'expérience directe (mais aussi par d'autres lectures) que beaucoup de gens ne le comprennent pas vraiment.

La présentation est sûrement améliorable. Du point de vue du contenu, il faudrait rajouter une section sur l'interaction de l'algorithme avec les modèles de consistence mémoire (là encore, dès que j'aurai le temps, si personne ne l'a fait d'ici là).

Merci!

--OlCe (d) 23 février 2010 à 18:27 (CET)

Demande de relecture en vue de proposer l'article comme bon article

Je souhaiterais proposer cet article comme étant un bon article. Avant de lancer la procédure officielle, cependant, je préfèrerais que d'autres personnes y jettent un coup d'oeil.

Merci d'avance pour vos commentaires!

--OlCe (d) 23 février 2010 à 20:05 (CET)

Commentaires

Bravo, l'article prend une autre dimension.

En vue d'une proposition comme bon article je proposerai les amélioration suivantes :

Je trouve la première phrase ardue, elle devrait d'accès plus facile. En la lisant telle quelle, on a l'impression que l'algorithme a pour condition nécessaire qu'il n'existe pas d'opération atomique. Alors que c'est juste qu'il fonctionne même s'il n'existe pas d'opération atomique (évidement s'il en existe il pourrait être simplifié) De toute façon, l'affirmation est contredite en fin d'article "...la modification de ce dernier est nécessairement atomique" donc il y a bien une opération atomique.

En fait je pense que la notion d'atomicité devrait être abordé dans le paragraphe Utilité. En effet la complexité et l'intérêt de l'algorithme est de garantir qu'une section de code soit exécutée par un seul fil, alors que le système ne donne aucune garantie quand à la coordination des fils et que pendant l'exécution d'une instruction d'un fil, les valeurs des variables peuvent changer (ainsi y=x+x peut donner une valeur impaire à y si un autre fil exécute x=x+1 en même temps)

Ensuite (mais je chipote peut-être) le début de phrase "Le second point est particulièrement remarquable et délicat à assimiler" n'est-il pas l'expression d'une impression personnelle et donc non encyclopédique ?

Ulrich Von Beck (d) 25 février 2010 à 14:56 (CET)

Merci pour le compliment!

Effectivement, la première phrase pourrait être reformulée pour éviter l'ambiguïté soulignée. "aucune opération atomique" signifie en fait aucun support matériel particulier pour des opérations atomiques. Toute opération sur un bit est nécessairement atomique, le bit étant une unité d'information indivisible. D'où l'apparente contradiction dans le texte.

Pour la notion d'atomicité, je mentionne déjà "opérations atomiques" ou "section critique" à plusieurs reprises. L'article commence en insistant sur le fait que l'algorithme réalise une exclusion mutuelle, qui est réellement ce que vous décrivez plus haut. On peut éventuellement rajouter une courte périphrase d'explication juste après le concept. Par contre, décrire plus avant le concept ou rajouter des exemples me paraît relever de l'article Exclusion mutuelle (qui a d'ailleurs grand besoin d'être réécrit!), et non pas de celui-ci. Qui plus est, cela éviterait d'avoir à décrire ce qu'est l'exclusion mutuelle dans chaque article qui traite d'une de ses implémentations, avec les inconvénients que cela comporte (nombreuses duplications de texte, divergences des explications...).

Pour votre dernière question, je répondrais plutôt non. Le fait que la propriété citée par ce passage soit remarquable provient de ce que l'algorithme de la boulangerie est le seul pour lequel cette propriété ait été prouvée. Il s'agit donc d'une information objective, mais dont la formulation n'est peut-être pas satisfaisante. Quant à "délicat à assimiler", il provient de l'observation de ce que les étudiants butent la plupart du temps sur ce point. C'est donc plus qu'une impression strictement personnelle. Son but ici est d'ailleurs d'attirer l'attention du lecteur sur la difficulté du reste du paragraphe, ce qui lui permet de choisir de lire les explications ou de les sauter en connaissance de cause. Amha, c'est un balisage utile du texte, non? On pourrait peut-être trouver une autre façon de le dire, j'en conviens.

Je ferai une nouvelle passe sur l'article quand j'aurai un peu plus de temps, pour tenir compte de vos remarques. Merci!!

--OlCe (d) 1 mars 2010 à 12:07 (CET)

Sémantique séquentielle et atomicité

Je trouve la présentation vraiment didactique. Bravo ! Néanmoins la revendication que l'algorithme puisse s'exécuter sans support d'opérations atomiques me parait un peu trompeuse en présence de caches. L'algorithme semble imposer que l'ordre des écritures/lectures soit proche de la sémantique séquentielle habituelle (dépendance causale des lectures et des écritures). Donc il faut que le matériel ait une gestion de la cohérence des caches fonctionnelle (sauf erreur de ma part, elle est désactivable sur ARM) ou des opérations atomiques de barrières mémoires (si les caches ne sont jamais écrits en mémoire tout le monde passe ensemble dans la section critique). Sans opérations atomiques et sans précautions le code me semble aussi très sensible à des optimisations agressives du compilateur (déplacement ou suppression du code si les deux tableaux partagés ne sont pas indiqués comme VOLATILE).

Mounieg (discuter) 29 mars 2014 à 01:55 (CET)