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
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 :
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:

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
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...

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();
1
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
Merci... le code était correct et mon utilisation aussi alors.
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 ^_^ )
0
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
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 ?
0
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
Ah oui pardon, j'ai oublié la class ThreadID :
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.
0
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
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.
0
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
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...
0
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
"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à.
0
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
c'est grâce à
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.
0
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
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);
	}
}
0