Algo Peterson : Erreur d'exclusion mutuelle
Résolu
efelant
Messages postés
15
Date d'inscription
Statut
Membre
Dernière intervention
-
efelant Messages postés 15 Date d'inscription Statut Membre Dernière intervention -
efelant Messages postés 15 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
Je cherche à utiliser l'algorithme de Peterson pour 2 threads. Cependant, à l'affichage j'obtiens que les deux threads se trouvent au même moment dans la section critique.
Le code de l'algorithme m'a été donné par mon professeur et sur internet, j'ai trouvé exactement le même. Je me demande donc à quel moment j'utilise mal la classe.
Sachant que je crée juste 2 threads.
Voilà mon code :
******************* Donné par le professeur et vu sur internet *******************
*************************************************************
Problème : J'obtiens à des moments en console :
Tache 1 est en section critique
Tache 2 est en section critique
Tache 1 est sorti de la section critique
Tache 2 est sorti de la section critique
Voyez-vous l'endroit d'où le problème pourrait venir ?
Merci d'avance.
Je cherche à utiliser l'algorithme de Peterson pour 2 threads. Cependant, à l'affichage j'obtiens que les deux threads se trouvent au même moment dans la section critique.
Le code de l'algorithme m'a été donné par mon professeur et sur internet, j'ai trouvé exactement le même. Je me demande donc à quel moment j'utilise mal la classe.
Sachant que je crée juste 2 threads.
Voilà mon code :
public class MainPeterson { public static void main(String[] args) { Peterson f = new Peterson(); Action thread1 = new Action("Tache 1", f); thread1.start(); Action thread2 = new Action("Tache 2", f); thread2.start(); } }
******************* Donné par le professeur et vu sur internet *******************
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; } }
*************************************************************
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); } }
import java.util.concurrent.locks.Lock; public class Action extends Thread { private String name; private Lock section; public Action(String n,Lock s) { name = n; section = s; } public void run() { while (true) { section.lock(); System.out.println(name+" est en section critique"); Action.Critique(); section.unlock(); System.out.println(name+" est sorti de la section critique"); Action.nonCritique(); } } public static void Critique() { try { Thread.sleep((int) (Math.random()*30)); } catch (InterruptedException e) { } } public static void nonCritique() { try { Thread.sleep((int) (Math.random()*30)); } catch (InterruptedException e) { } } }
Problème : J'obtiens à des moments en console :
Tache 1 est en section critique
Tache 2 est en section critique
Tache 1 est sorti de la section critique
Tache 2 est sorti de la section critique
Voyez-vous l'endroit d'où le problème pourrait venir ?
Merci d'avance.
A voir également:
- Algo Peterson : Erreur d'exclusion mutuelle
- Algo prono - Télécharger - Sport
- Aide : algo palindrome - Forum Programmation
- Demande d'algo Mastermind - Forum Programmation
- Aide pour exercice algo - Forum Algorithmes / Méthodes
- Algo arbre/graph ✓ - Forum Programmation
3 réponses
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();
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 ?
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.
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.
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...
"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à.
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.
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); } }
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 ^_^ )