2. Corrigé du TD numéro 2 : Java et les Threads

2.1. Exercice 1.

Il suffit de créer deux objets exécutables appartenant à la même classe (ici appelée CompteurBasique), on va passer le sens du compteur dans le créateur de l’objet. Ensuite on crée les 2 threads puis on le démarre. On peut soit faire un test sur la valeur du paramètre Direction (if,else) et gérer deux cas, ou avoir une seule boucle avec des bornes dépendant de Direction. Enfin on peut tout simplement afficher un message différent, ici \((maxIter-1)*( (1-Direction)/2 )+Direction*i)\) vaut \(i\) si Direction=1 et \(maxiter -i\) si \(Direction=-1\).

  • Exemple avec deux Threads*
    • public class CompteurBasique  implements Runnable{
    String nom="Toto";
    int maxIter= 1000 ;
    int Direction=0;
    public CompteurBasique(String  nom, int laDirection)    {
	this.nom=nom;
       this.Direction=laDirection;
    }
    public void run()
    {
	    System.out.format("Ici le  thread %s, je debute!\n", nom);
	    for (int i = 0; i < maxIter; i++) {
	    System.out.format("[%s] dit %d\n",nom,(maxIter-1)*( (1-Direction)/2 )+Direction*i);
    	}
    }
    public static void main(String[] args)  throws  Exception {
	CompteurBasique   objetA  = new CompteurBasique("TA",1);
	Thread TA = new Thread(objetA);
        CompteurBasique   objetB  = new CompteurBasique("TB",-1);
        Thread TB = new Thread(objetB);
	TA.start();
	TB.start();
	System.out.format("Thread principal terminé  !\n");
    }
}

    2.2. Exercice 2.

    L’affichage est de fait apparement aléatoire, l’ordonnanceur de la JVM donne la main à chacun des Threads d’une facon indéterminée que nous ne pouvons pas prévoir. Même si apparement le thread qui démarre en premier peut souvent se terminer le premier et si un thread semble conserver la main un certain temps. Quand on ajoute des délai cette absence de déterminisme est renforcée. L’ordonnanceur de la machine Java essaie à la fois d’optimiser le calcul (ce qui ici implique de ne pas faire alterner les deux threads) mais aussi d’être équitable en donnant la main aux deux threads. Au final on peut seulement supposer que tout thread qui ne dort pas aura la main de temps à autre.

    Les deux Threads sont en concurrence bien entendu pour le CPU (sauf éventuellement sur un ordinateur multi-coeur), la mémoire, mais aussi pour l’accès au flux de sortie qui permet d’écrire sur la console (i.e. System.out), la JVM assure que ce flux est bien géré et que les deux threads accèdent exclusivement à cette ressource. Par ailleurs la concurrence n’est pas forte car les deux threads ne partagent aucun objet ou variable, mis à part bien entendu les objets systemes tels que Systeme,out.

    2.3. Exercice 3.

    Le programme met en concurrence deux threads qui manipulent le même ObjetEntier qui se nomme Compteur. La première tache (tache1) incrémente Compteur tandis que la seconde (tache2) le décrémente, ceci 1 million de fois chacune.

    À la fin du calcul la valeur du compteur devrait être zéro.

    Le programme contient deux erreurs :

    1. La valeur du compteur affichée par le thread principal est provisoire car tache1 et tache2 sont en cours. Ainsi si on affiche plusieurs fois la valeur de Compteur à la fin du code du thread principal, la valeur affichée va varier.
    2. Les tâches 1 et 2 manipulent et modifient le même objet (ici Compteur) et cela crée des inconsistances, dans le cas qui nous occupe il s’agit d’un problème dit de race condition (qui est décrit dans la fiche 2). Même si on attend que les tâches 1 et 2 aient terminé leur calcul, le compteur final ne vaudra souvent pas zéro. Si on change \(10^6\) en 100 on peut très bien avoir un programme qui fonctionne apparement bien. C’est bien là l’aspect le plus délicat des problèmes de concurrence : ils n’apparaissent pas toujours et un programme apparement satisfaisant peut contenir des erreurs cachées. Bien entendu les programmes déterministes utilisant un seul fil de calcul eux aussi peuvent contenir des erreurs cachées, mais elles sont bien plus faciles à décéler.

    2.4. Exercice 4.

    Pour protéger le compteur et garantir un accès cohérent il suffit de synchroniser la méthode add. Ce qui se fait simplement en écrivant :

    public class ObjetEntier {
           ...........
           ................
public  int val(){ return ma_valeur;}
public synchronized   void add(int i) { ma_valeur+=i;}

  }

    La valeur du compteur sera alors correcte, cependant pour l’afficher il faut soit placer une très longue boucle à la fin du thread principal ou encore l’afficher à la fin des tâches 1 et 2. Par exemple on peut ajouter une ligne à la fin de la méthode run() des threads.

    public void run() {
      for (int i = 0; i < 1e7; i++)
        {
                  notre_entier.add(increment);
        }
 System.out.format("Thread faisant %d terminé. Compteur= %s\n" , increment,notre_entier);
  }

    2.5. Exercice 5.

    Les codes complets sont disponibles ici Classe Voiture.java et classe Parking.java.

    On commence par écrire le code pour une voiture, pour en simuler plusieurs on lancera simplement plusieurs threads.

    Chaque voiture sera donc simulée par un thread. Une voiture dispose d’un nom et pointe sur le Parking qui ici est partagé. Le comportement de chaque voiture est cyclique et peut se décrire comme suit:

    Répéter:

    • Se déplacer à l’extérieur un certain temps.
    • Demander et obtenir l’accès au parking.
    • Rentrer dans le parking se garer et y rester un certain temps
    • Sortir du parking.
    Exemple pour la classe voiture
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    public class Voiture implements Runnable { 
	String nom; 
	Parking park;
    public Voiture(String name, Parking park){
	this.nom=name; 
	this.park=park; 

	public void run(){ 
	System.out.format("[%s]: Je débute !  \n", this.nom);
	try {
	    while(true){
		Thread.sleep((long)  (50000* Math.random()));
		System.out.format("[%s]: Je demande à rentrer  \n", this.nom);
		this.rentrer();
		System.out.format("[%s]: Je viens d'entrer \n", this.nom);
		Thread.sleep((long)  (50000* Math.random()));
		System.out.format("[%s]: Je demande à sortir  \n", this.nom);
		this.park.leave(this);  
	}}

    Dans ce code :

    • la ligne 5 attends à l extérieur.
    • la ligne 7 demande l autorisation de rentrer, elle est bloquante.
    • la ligne 9 simule le temps passé dans le garage,
    • la ligne 10 quiite le parking.

    Le Parking est simpliste, on le crée en passant sa taille au constructeur. Il propose deux méthodes atomiques (synchronized), leave() et accept().

    • accept() retourne vrai si il y a de la place et reserve la place (incrémente le nombre de places occupées), et faux sinon.
    • leave laisse sortir la voiture et décrémente le nombre de places occupées.

    J ai ajouté une structure qui maintient l’ensemble des voitures situées dans le parking mais ce n’etait pas demandé. Il serait facile de comptabiliser de manière analogue le temps passé par chaque voiture dans le parking.

    Exemple pour la classe Parking
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    import java.util.*;
public class Parking {
    int PlacesOccupees; 
    int Capacite ; 
    public HashSet<Voiture> infoVoitures = new HashSet<Voiture>();
    Parking(int size){ this.Capacite = size;} 
    int places(){ return (this.Capacite - this.PlacesOccupees); }  
	
    synchronized boolean  accept(Voiture myVoit) {
	if  (this.places() >0 )
	    { 
		this.PlacesOccupees ++ ;
		infoVoitures.add(myVoit); 
		System.out.format("[Parking] :%s acceptée, il reste %d places \n", myVoit.nom, this.places());
		System.out.format("Voiture Garees\n");
		System.out.println(infoVoitures);
		return (true) ; 
	    }
	else {
	    System.out.format("Parking : %s refusée, il reste  %d places \n", myVoit.nom,this.places());
	    return(false) ;
	}
    }
    synchronized void leave(Voiture myVoit) {
	PlacesOccupees --; 
	infoVoitures.remove(myVoit);
	System.out.format("Parking :[%s] est sortie, reste  %d places\n", myVoit.nom, places());
    }}

    La méthode rentrer qui bloque la voiture tant qu’il n y a pas de places innonde le parking de demandes, entre chaque demande la voiture attend un peu. On verra plus tard comment éviter cela.

    Méthode rentrer
    public class Voiture implements Runnable { 
	public void rentrer() throws InterruptedException{	
		while (!(this.park.accept(this)))
		{
		    Thread.sleep((long)  (1000* Math.random()));
		    System.out.format("[%s]  : Je redemande à rentrer  \n", this.nom);
		}
	}

    Le programme principal se contente de créer le parking ainsi que les thread associés aux voitures tout en démarramt ces threads.

    Main du simulateur de parking
    public class Voiture implements Runnable { 
    public static void main(String[] args) {
	int TailleParking=8;
	int nbVoitures=15; 
	Parking leParking = new Parking(TailleParking);
	Thread MesVoitures[] = new Thread[nbVoitures];
	for (int i =0; i< nbVoitures; i++){
	    MesVoitures[i]= new Thread(new Voiture(String.format("Voit %d ", i) , leParking));
	    MesVoitures[i].start();}}}

    2.6. Exercice 6.

    Afin que la valeur affichée par la thread principal soit toujours correcte il suffit de lui demander d’attendre les tâches 1 et 2. En Java ceci donne le morceau de code suivant, que l’on utilise pour la méthode main du thread principal.

     public static void main(String[] args) {
 ObjetEntier Compteur = new ObjetEntier();
 PetitJob objex1= new PetitJob(Compteur, 1);
 PetitJob objex2= new PetitJob(Compteur, -1);
 Thread tache1 = new Thread(objex1 ,"incrementeur");
 Thread tache2 = new Thread(objex2, "decrementeur");

 tache1.start();
 tache2.start();

 try {
 tache1.join();
 tache2.join();
 }
 catch (InterruptedException e) {
 e.printStackTrace();}

 System.out.format("Le compteur vaut %s\n" , Compteur);
 System.out.format("Le compteur vaut %s\n" , Compteur);

  }
}

    2.7. Exercice 7.

    Un Exemple de solution est donné ci dessous. Un Objet de la classe Dormeur à un antécédent qui est un thread. La méthode run() commence par attendre que l’antécédent ai terminé.

    Ensuite il suffit de créer les Threads et de définr pour chacun son antécedent.

  • Exemple avec deux Threads*
    • import java.util.*;
public class Dormeur implements Runnable {
	String nom = null;
	Thread antecedent = null;

	public Dormeur(String nom, List<Thread> list_antecedents) {
		this.nom = nom;
		for (Thread t : list_antecedents) {
			this.antecedent = t;
		}
	}
	public void run() {
		System.out.format("%s, started !\n", nom);
		if (antecedent != null)
			try {
				antecedent.join();
				System.out.format("%s: %s a fini !!\n", nom,antecedent.getName());
			} catch (InterruptedException e) {
				System.out.format("Issue with %s inte while waiting\n", nom);
			}
		System.out.format("%s dit: Super je peux enfin demarrer! !\n", nom);
		zzzz(); 
				System.out.format("%s dit: Super j'ai FINI!!! !\n", nom);
	}
	public static void main(String[] args) throws Exception {
		List<Thread> mon_antecedent = new ArrayList();

		Dormeur OC = new Dormeur("Glandeur C", mon_antecedent);
		Thread TC = new Thread(OC, "Mister C");

		mon_antecedent = Arrays.asList(TC);
		Dormeur OB = new Dormeur("Glandeur B", mon_antecedent);
		Thread TB = new Thread(OB, "Mister B");

		mon_antecedent = Arrays.asList(TB);
		Dormeur OA = new Dormeur("Glandeur A", mon_antecedent);
		Thread TA = new Thread(OA, "Mister A");

		TA.start();
		TB.start();
		TC.start();

		System.out.format("Main :Fini ici  !\n");
	}

	
	
	private void zzzz(){
		
		try {
			Thread.sleep((int) (1e3 * Math.random()));
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
}

    2.8. Exercice 8.

    • Il suffit de passer à chaque thread la liste des threads qu’il doit attendre, on peut le faire via le constructeur ou via une méthode SetAntecedent.
    • Ensuite tant que la liste des predecesseurs est non vide, on dépile un thread T, et on effectue T.join()
    • Le code final se trouve ici : Classe redormeur

    2.9. Exercice 9.

    Le code final se trouve ici : Classe TreeTask et classe MutableInt. Le code est commenté ci dessous, il est un peu long, nous verrons plus tard comment faire un code minimal en utilisant une librairie de graphe. En effet l’exercice 9 est une généralisation de cet exercice qui porte sur un graphe de dépendance particulier.

    Dans cette exercice on commence par déclarer la classe TreeTask censée représenter une tâche.

    2.9.1. La Classe TreeTask

    Cette classe possède les attributs suivants :

    1. myIndex l’index de la tâche dans la table des tâches.
    2. une référence TreeTask au tableau des tâches.
    3. l’index de la tâche précédente predIndex, si cette tâche est inexistante (ce qui est le cas de la tâche racine) predIndex vaudra -1.
    4. Une chaine myName le nom de la tâche.
    public class TreeTask  implements  Runnable
{
  Integer predIndex;
  TreeTask[] TasksArray;
  String myName;
  int myIndex;
  Thread myThread;

    2.9.2. La méthode run()

    1. Attends que la tâche précédente soit terminée (ligne 5)
    2. Affiche quelle commence à travailler (ligne 12)
    3. Simule un temps aléatoire (ligne 13)
    4. Annonce qu’elle se termine et se termine (ligne 14).
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    public void run() {
  System.out.format("%s Started\n", myName);
  Thread previousTask= null;
  if (predIndex>=0){
    previousTask=  TasksArray[predIndex].myThread;
    try       {
      previousTask.join();
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
    System.out.format("%s Running\n", myName);
    zzzz();
    System.out.format("%s Completed\n", myName);
  }

    2.9.3. Le Constructeur de Tâche

    Dans ce constructeur on recopie simplement quelques info : la référence au tableau, le nom, l’index de la tâche précédente, l’index de la tâche (respectivement lignes 3,4,5,6).

    L’index courant est un entier déguisé car on veut qu’il soit modifiable (ie passable par référence) car on l’incrémente à chaque fois que l’on crée une tâche. Java est un langage stupide qui ne propose pas d’entiers mutables (sauf en utilisant la librairie apache).

    Ce qui est un peut particulier ce sont les lignes 7,8,9:

    1. Ligne 7, on place aussi une référence à notre tâche dans le tableau des tâches.
    2. Ligne 8 on incrémente l’index courant.
    3. Ligne 9 on crée le thread associé à la tâche.
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
     public TreeTask(String Name, MutableInt index,  TreeTask[] TA, int pred )
  {
    TasksArray=TA;
    myName= Name;
    predIndex=pred;
    myIndex = index.val();
    TasksArray[myIndex]=this;
    index.increment(1);
    myThread= new Thread(this);
    System.out.format("Creating Runnable %s with index %d, pred=%s\n", myName,myIndex,predIndex);
   }

    2.9.4. La Construction Récursive des Tâches

    Afin de créer les tâches récursivement on utilise la récursion suivante, qui est basée sur le fait suivant:

    Un arbre binaire de profondeur \(i\) est formé de deux arbres binaires de profondeur \(i-1\) attachés à une même racine.
    • Une tâche au niveau \(i>0\) crée deux tâches filles : une tache droite et une tâche gauche toutes deux de niveau \(i-1\). Puis elle demande aux deux tâches filles de créer leur descendance.
    • Une tâche de niveau \(0\) ne fait rien.

    Remarque : Pour un arbre on crée la racine puis récursivement on crée les deux arbres fils, mais ici la tâche mère ne peut pas se créer elle même, la récursion classique est donc quelque peu décalée. Et la tâche racine est elle crée par la méthode main.

    Ceci conduit au code de génération suivant :

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    public void generateSon(int depth, MutableInt firsfreeindex)
      {
              if (depth==0) return;
              String  leftName= myName+ "0";
              String  rightName= myName+ "1";

              TreeTask Left=new TreeTask(leftName, firsfreetindex,TasksArray, myIndex);
              TreeTask Right=new TreeTask(rightName, firsfreetindex,TasksArray, myIndex);

              Left.generateSon(depth-1, firsfreeindex);
              Right.generateSon(depth-1,firsfreeindex);
      }

    2.9.5. La Méthode main() de la Classe

    La méthode se contente de :

    1. De déclarer la profondeur de l´arbre (ici 4).
    2. De Créer le tableau des tâches, l’index entier modifiable (lignes 3-4)
    3. De créer la tâche racine (ligne 6)
    4. D’engendrer la descendance de la tache racine (ligne 8).
    1
2
3
4
5
6
7
8
    public static void main(String[] args) {
    int depthofTree=4;
    TreeTask[] MyExObjects= new TreeTask[256];
    MutableInt index= new MutableInt(0);

    TreeTask RootTask = new TreeTask( "R", index, MyExObjects, -1);

    RootTask.generateSon(depthofTree, index);

    Le code final se trouve ici : Classe TreeTask elle utilise la classe MutableInt.