Discussion:Algorithme de Peterson
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Faible |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Évaluation modifier
Bonjour,
j'ai évalué l'article à faible dans le domaine informatique.
Bonne journée,
Algorithme pour n processus modifier
L'algorithme pour n processus est faux (bien que beaucoup plus simple que celui de la version anglaise). Chaque tâche se contente de vérifier l'état de la tâche suivante, mais pas des autres!
--Efyks (discuter) 23 août 2017 à 11:08 (CEST)
- @Efyks Ça me choque aussi. Ci-dessous, un contre-exemple simple pour convaincre les autres qui pourraient passer par là (mais ça doit pas se bousculer, à en juger par la date du message précédent…).
- Je rappelle et annote le pseudo-code actuellement dans l’article :
/* Phase d’initialisation : */
États[NumeroTache] = VEUX
Autre = (NumeroTache + 1) % NombreTaches
/* Attente active : */
REPETER
Ne rien faire
JUSQU'À États(Autre)==VEUXPAS OU Autre==NumeroTache
/* Section Critique : */
...
/* Fin : */
États[NumeroTache] = VEUXPAS
- Prenons trois processus T0, T1, T2. Une exécution possible (séquentiellement cohérente (en)) est la suivante.
-
- T2 effectue sa phase d’initialisation puis commence son attente active. À ce stade,
Autre == 0. - T1 effectue sa phase d’initialisation puis commence son attente active. À ce stage,
Autre == 2. - T2 sort de sa boucle d’attente (il le peut car
Autre == 2) et entre dans sa section critique. - T0 effectue sa phase d’initialisation puis commence son attente active. À ce stage,
Autre == 1. - T1 sort de sa boucle d’attente (il le peut car
Autre == 1) et entre dans sa section critique.
- T2 effectue sa phase d’initialisation puis commence son attente active. À ce stade,
- On a deux processus en section critique en même temps !
- — Maëlan 3 avril 2019 à 16:26 (CEST)
Problèmes multiples modifier
Salut,
Cet article a plusieurs problèmes.
- L’algorithme présenté pour n processus est complètement faux, comme vu ci-dessus.
- L’article ne dit rien du (ou des) modèle(s) mémoire(s) (en) dans lequel l’algorithme est correct, ou quel mode d’accès aux variables partagées est nécessaire. À priori, sauf preuve que l’algorithme est valide dans un cadre plus général, il faut se restreindre au modèle séquentiellement cohérent (en) ou, du moins, s’assurer que les accès aux variables de cet algorithme sont séquentiellement cohérents (on parle souvent de variables « atomiques », mais c’est une propriété plus forte que l’atomicité). C’est ce que fait l’article anglophone : « The algorithm satisfies the three essential criteria to solve the critical section problem, provided that changes to the variables
turn,flag[0], andflag[1]propagate immediately and atomically. » À vrai dire, à en juger par tous ces liens rouges, on dirait que le domaine n’est pas très populaire sur la Wikipédia francophone… - L’article est pratiquement dépourvu de sources. Citer l’article initial de Peterson aurait été le minimum vital !
Je m’attellerai à refondre cet article quand j’aurais plus de temps, muni de mon exemplaire du très excellent livre The Art of Multiprocessor Programming de Herlihy & Shavit et en gardant un œil sur l’article anglophone (qui utilise également ce livre comme source).