Threads

1.16 Threads

1.16.1 Le dîner des philosophes

Les programmes peuvent être décomposés en processus légers (eng. threads) s’exécutant en parallèle de façon asynchrone. Ils sont susceptibles d’accéder à des ressources communes pour se transmettre des données. Le dîner des philosophes est une illustration des problèmes se posant lorsque l’on manipule des processus.

(Illustration par Benjamin D. Esham / Wikimedia Commons, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=56559)

Un philosophe, pour manger, va utiliser les deux couverts qui sont à côté de son assiette. De la sorte, ses deux voisins ne peuvent pas manger en même temps que lui. Ce modèle est une transposition de ce qui se produit lorsque des programmes (les philosophes) ont besoin de ressources communes (les couverts). Un philosophe se comportera de la façon suivante une fois face à son assiette :

L’interblocage

Si jamais un des couverts qu’il doit prendre n’est pas disponible, il devra attendre que celui-ci se libère. Dans le cas où le couvert gauche serait disponible mais pas le droit, le philosophe prendra le couvert gauche et le tiendra jusqu’à ce que le droit se libère, empêchant de la sorte un autre philosophe, à sa gauche, de manger.

La pire situation est celle dans laquelle les philosophes arrivent tous en même temps, prennent chacun le couvert se trouvant à leur gauche, et attendent tous que leur couvert droit se libère. Ils resteront tous bloqués sur la première étape de leur algorithme, formant ce que l’on appelle un interblocage, (eng. deadlock).

La famine

Une solution pourrait être de libérer le couvert gauche si le droit n’est pas disponible. Mais malheureusement cela pourrait conduire à un autre problème s’appelant la famine. Dans le cas où des philosophes se relaierait pour toujours manger à côté de notre philosophe fair-play, celui-ci se retrouverait en attente indéfiniment.

1.16.2 Lancement

En java, on définit un thread de deux façons :

En héritant de la classe Thread
En implémentant l’interface Runnable

Bien que la première solution soit généralement plus commode, la deuxième est quelquefois le seul moyen d’éviter l’héritage multiple. Nous détaillerons le premier cas, le deuxième est décrit dans la documentation.

La classe `Thread`

La classe Thread dispose entre autres de deux méthodes

public void start() qui est la méthode permettant de démarrer l’exécution du thread.
public void run() qui est la méthode automatiquement invoquée par start quand le thread est démarré.

package threads;

public class BinaireAleatoire extends Thread
{
 private int value;
 private int nbIterations;

 public BinaireAleatoire(int value, int nbIterations)
 {
  this.value = value;
  this.nbIterations = nbIterations;
 }

 @Override
 public void run()
 {
  for (int i = 1; i <= nbIterations; i++)
   System.out.print(value);
 }

 public static void main(String[] args)
 {
  Thread un = new BinaireAleatoire(1, 30);
  Thread zero = new BinaireAleatoire(0, 30);
  un.start();
  zero.start();
 }
}

Télécharger le fichier

L’interface `Runnable`

Le constructeur de la classe Thread est surchargé pour prendre un paramètre une instance Runnable. Runnable est une interface contenant une méthode public void run(), celle-ci sera invoquée par le thread au moment de son lancement.

1.16.3 Synchronisation

Le modèle producteur/consommateur

Le modèle producteur/consommateur se construit à l’aide de deux programmes :

Le producteur transmet des données en les faisant transiter par une mémoire tampon.
Le consommateur traite les données produites en les récupérant dans la mémoire tampon.

Lorsque la mémoire tampon est pleine, le producteur doit se mettre en sommeil, et lorsque la mémoire tampon est vide, c’est au consommateur de se mettre en sommeil. Lorsque le producteur place une donnée dans une mémoire tampon vide, il réveille le consommateur, et lorsque le consommateur libère de la place dans une mémoire tampon pleine, il réveille le producteur. Le comportement du producteur est décrit par l’algorithme suivant :

Et celui du consommateur est le suivant :

Le problème des réveils perdus

La commutation entre les processus peut avoir lieu à n’importe quel moment. Si par exemple, le producteur est interrompu à l’endroit indiqué l’étoile (*), le signal de réveil risque d’être envoyé par le consommateur avant que le producteur ne s’endorme. Le signal de réveil étant perdu, le producteur ne se réveillera pas. Le consommateur pendant se temps va vider la mémoire tampon pour s’endormir à son tour. A la fin, chacun des deux processus sera en sommeil et attendra que l’autre le réveille.

Section critique

Une section critique est un bloc d’instructions qu’il est impossible d’interrompre. Une section critique se construit avec le mot-clé synchronized.

Méthodes synchronisées

Une méthode synchronisée verrouille un objet pendant son exécution, et met en attente les autres threads tentant d’accéder à l’objet. On synchronise une méthode en plaçant le mot clé synchronized dans sa définition.

Instructions synchronisées

On synchronise des instructions en les plaçant dans un bloc

synchronized(o)
{ 
  /* ... */ 
}

Où o est l’objet ne pouvant être accédé par deux threads simultanément.

1.16.4 Mise en Attente

Un thread peut décider de se mettre en attente s’il a besoin pour s’exécuter de données qui ne sont pas encore disponibles. On gère cela avec les instructions suivantes :

public void wait() throws InterruptedException met le thread en attente.
public void notify() réveille un thread en attente.
public void notifyAll() réveille tous les threads en attente.

On place en général ces instructions dans une section critique. Un wait() libère le verrou pour autoriser d’autres threads à accéder à la ressource. Un notify() choisit un des objets placés en attente sur la même ressource, lui rend le verrou, et relance son exécution. Par exemple,

package threads;

public class Counter
{
 private int value = 0;
 private int upperBound;
 private int lowerBound;

 public Counter(int lowerBound, int upperBound)
 {
  this.upperBound = upperBound;
  this.lowerBound = lowerBound;
  value = (upperBound + lowerBound) / 2;
 }

 public synchronized void increaseCounter() throws InterruptedException
 {
  while (value == upperBound)
   wait();
  value++;
  System.out.println("+ 1 = " + value);
  if (value == lowerBound + 1)
   notify();
 }

 public synchronized void decreaseCounter() throws InterruptedException
 {
  while (value == lowerBound)
   wait();
  value--;
  System.out.println("- 1 = " + value);
  if (value == upperBound - 1)
   notify();
 }

 public static void main(String[] args)
 {
  Counter c = new Counter(0, 100);
  Thread p = new Plus(c);
  Thread m = new Moins(c);
  p.start();
  m.start();
 }
}

class Plus extends Thread
{
 private Counter c;

 Plus(Counter c)
 {
  this.c = c;
 }

 @Override
 public void run()
 {
  while (true)
   try{c.increaseCounter();}
   catch (InterruptedException e){}
  
 }
}

class Moins extends Thread
{
 private Counter c;

 Moins(Counter c)
 {
  this.c = c;
 }

 @Override
 public void run()
 {
  while (true)
   try{c.decreaseCounter();}
   catch (InterruptedException e){}
 }
}