Algo Peterson : Erreur d'exclusion mutuelle
Résolu/Fermé
efelant
Messages postés
15
Date d'inscription
dimanche 3 février 2013
Statut
Membre
Dernière intervention
4 février 2013
-
Modifié par efelant le 3/02/2013 à 16:58
efelant Messages postés 15 Date d'inscription dimanche 3 février 2013 Statut Membre Dernière intervention 4 février 2013 - 4 févr. 2013 à 00:20
efelant Messages postés 15 Date d'inscription dimanche 3 février 2013 Statut Membre Dernière intervention 4 février 2013 - 4 févr. 2013 à 00:20
A voir également:
- Algo Peterson : Erreur d'exclusion mutuelle
- Telecharger algo pour pc - Télécharger - Édition & Programmation
- Algo prono - Télécharger - Sport
- ALGO ET PASCAL - Forum Pascal
- Aide : algo palindrome - Forum Programmation
- Demande d'algo Mastermind - Forum Programmation
3 réponses
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
3 févr. 2013 à 23:48
3 févr. 2013 à 23:48
La réponse est toute simple, même s'il m'a fallu longtemps pour m'en apercevoir !
Il n'y a pas d'erreur, mais l'affichage est trompeur...
Voici donc un affichage correct, et normalement la résolution de ton problème :
Il n'y a pas d'erreur, mais l'affichage est trompeur...
section.lock(); System.out.println(name+" est en section critique"); Action.Critique(); section.unlock(); // à ce niveau là, il est tout à fait possible que l'autre thread entre en section critique et affiche son message, on a donc l'impression que les deux sont entrés en même temps, parce qu'on n'a pas encore eu le temps d'afficher le message suivant : System.out.println(name+" est sorti de la section critique"); Action.nonCritique();
Voici donc un affichage correct, et normalement la résolution de ton problème :
section.lock(); { System.out.println(name+" Début section critique"); Action.Critique(); System.out.println(name+" Fin de section critique"); } section.unlock(); Action.nonCritique();
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
3 févr. 2013 à 16:48
3 févr. 2013 à 16:48
Déjà ça ne compile pas :
1) Qu'est-ce que la classe ThreadID ?
2) Où sont les méthodes lockInterruptibly(), tryLock(), tryLock(long,TimeUnit), et newCondition(), de Peterson ?
De manière générale, qu'est censé faire ce code ?
1) Qu'est-ce que la classe ThreadID ?
2) Où sont les méthodes lockInterruptibly(), tryLock(), tryLock(long,TimeUnit), et newCondition(), de Peterson ?
De manière générale, qu'est censé faire ce code ?
efelant
Messages postés
15
Date d'inscription
dimanche 3 février 2013
Statut
Membre
Dernière intervention
4 février 2013
3 févr. 2013 à 16:56
3 févr. 2013 à 16:56
Ah oui pardon, j'ai oublié la class ThreadID :
Pour les méthodes lockInterruptibly(), tryLock(), tryLock(long,TimeUnit), je ne les ai pas implémenté. Et je ne vous les ai pas affiché pour ne pas mettre trop de code sur le forum mais je mets la classe entièrement.
(Je modifie le code du premier post pour une lecture plus simple, avec toutes les classes.)
Je dois simplement simuler le fait qu'il y ait bien exclusion mutuelle. C'est pour cela que dans Critique et NonCritique, je mets seulement le Thread en pause. Car ce n'est pas ce qui m'importe.
public class ThreadID { private static volatile int nextID = 0; private static class ThreadLocalID extends ThreadLocal<Integer>{ protected synchronized Integer initialValue(){ return nextID ++; } } private static ThreadLocalID threadID = new ThreadLocalID(); public static int get(){ return threadID.get(); } public static void set (int index){ threadID.set(index); } }
Pour les méthodes lockInterruptibly(), tryLock(), tryLock(long,TimeUnit), je ne les ai pas implémenté. Et je ne vous les ai pas affiché pour ne pas mettre trop de code sur le forum mais je mets la classe entièrement.
import java.util.concurrent.TimeUnit; import java.util.concurrent.locks.*; public class Peterson implements Lock{ private volatile boolean[] flag = new boolean[2]; private volatile int victim = -1 ; public Peterson(){ for(int i=0 ; i<flag.length ; ++i) flag[i] = false; } @Override public void lock() { int i = ThreadID.get()%2; // ThreadID is a ThreadLocal field int j= 1 - i; flag[i] = true; // I'm Interested victim = i; // You go first while(flag[j] && victim == i){}; //wait } @Override public void unlock() { int i = ThreadID.get()%2; flag[i] = false; // I m not interested } @Override public void lockInterruptibly() throws InterruptedException { } @Override public Condition newCondition() { return null; } @Override public boolean tryLock() { return false; } @Override public boolean tryLock(long arg0, TimeUnit arg1) throws InterruptedException { return false; } }
(Je modifie le code du premier post pour une lecture plus simple, avec toutes les classes.)
Je dois simplement simuler le fait qu'il y ait bien exclusion mutuelle. C'est pour cela que dans Critique et NonCritique, je mets seulement le Thread en pause. Car ce n'est pas ce qui m'importe.
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
3 févr. 2013 à 20:45
3 févr. 2013 à 20:45
J'avoue ne jamais avoir fait ça (utiliser un Lock), mais j'émet des réserves sur la partie "identification" du Thread, c'est à dire que pour moi chaque Thread devrait avoir un identifiant unique (1 et 2), or ici avec int i = ThreadID.get()%2, je ne suis pas du tout convaincu que le i identifie correctement le Thread.
efelant
Messages postés
15
Date d'inscription
dimanche 3 février 2013
Statut
Membre
Dernière intervention
4 février 2013
3 févr. 2013 à 21:40
3 févr. 2013 à 21:40
J'avais aussi fait le test sans le %2. Et le résultat était le même.
C'est juste là pour garantir que la valeur sera 0 ou 1, puisqu'on est dans le cas de deux Threads, et qu'on ne veut donc pas qu'il cherche dans le tableau flag, à un indice plus grand que sa taille (même si bien sûr dans le cas de plus de 2 threads, la logique de l'algorithme ne fonctionnera plus, mais au moins, il n'y aura pas d'erreur à l'exécution).
L'erreur du programme reste toujours un grand mystère...
C'est juste là pour garantir que la valeur sera 0 ou 1, puisqu'on est dans le cas de deux Threads, et qu'on ne veut donc pas qu'il cherche dans le tableau flag, à un indice plus grand que sa taille (même si bien sûr dans le cas de plus de 2 threads, la logique de l'algorithme ne fonctionnera plus, mais au moins, il n'y aura pas d'erreur à l'exécution).
L'erreur du programme reste toujours un grand mystère...
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
3 févr. 2013 à 21:50
3 févr. 2013 à 21:50
"garantir que la valeur sera 0 ou 1" ne suffit pas, il faut que ce soit toujours 0 pour un thread et toujours 1 pour l'autre. Or je ne vois pas en quoi le ThreadID.get() permet d'identifier le thread qui effectue le lock ou le unlock. Et si cela donne 0 ou 1 sans respecter la logique que l'on attend, cela veut dire qu'il peut débloquer un thread en croyant en bloquer un autre et inversement...
Je regarderais plus en détail demain, mais je pense que c'est une erreur par là.
Je regarderais plus en détail demain, mais je pense que c'est une erreur par là.
efelant
Messages postés
15
Date d'inscription
dimanche 3 février 2013
Statut
Membre
Dernière intervention
4 février 2013
3 févr. 2013 à 21:55
3 févr. 2013 à 21:55
c'est grâce à
Qui récupère le thread qui a appelé la fonction.
Donc
si le thread est 1 alors 1-1 = 0 => On a bien l'autre thread
si le thread est 0 alors 1 - 0 = 1 => On a bien l'autre thread aussi.
Dans tous les cas, on obtient l'autre Thread.
Sachant qu'il y a 2 threads seulement.
int i = ThreadID.get()%2 ;
Qui récupère le thread qui a appelé la fonction.
Donc
int j= 1 - i;
si le thread est 1 alors 1-1 = 0 => On a bien l'autre thread
si le thread est 0 alors 1 - 0 = 1 => On a bien l'autre thread aussi.
Dans tous les cas, on obtient l'autre Thread.
Sachant qu'il y a 2 threads seulement.
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
>
efelant
Messages postés
15
Date d'inscription
dimanche 3 février 2013
Statut
Membre
Dernière intervention
4 février 2013
3 févr. 2013 à 22:11
3 févr. 2013 à 22:11
Ce n'est pas cette partie là qui m'embête, mais le code de ThreadID.get(), d'autant qu'il n'y a jamais d'appel à ThreadID.set()...
public class ThreadID { private static volatile int nextID = 0; private static class ThreadLocalID extends ThreadLocal<Integer> { protected synchronized Integer initialValue() { return nextID++; } } private static ThreadLocalID threadID = new ThreadLocalID(); public static int get() { return threadID.get(); } public static void set (int index) { threadID.set(index); } }
4 févr. 2013 à 00:20
J'ai passé des jours dessus... à essayer de comprendre pourquoi ça ne fonctionnait pas.
Sincèrement MERCI !
(On peut sûrement sentir mon désespoir dans ce message ^_^ )