TP Java Concurrence

Bertrand Dupouy

Ce TP ne présente pas tous les outils proposés par Java pour gérer les threads et la concurrence. Il illustre le fonctionnement de quelques uns parmi ceux-ci, en commençant par ceux de plus bas niveau.

Envoyer les réponses à dupouy@enst.fr.

SOMMAIRE

I. Synchronisation : barrière
II. Sémaphores

II.1 Avant JDK-1.5 : Réalisation d'un sémaphore
II.2 Schéma producteur/consommateur
II.3 Schéma producteur/consommateur (2)

III. Autour des threads

III.1 Threads : `runnable`, `callable`, interface `Future`
III.2 Utilisation des pools de threads

Pour accéder à la documentation :

La documentation Sun Java 1.5
Le site Sun.

I. Synchronisation : barrière

On va ici écrire une application très simple qui illustre la gestion d'un pool de thread.
Un pool de thread fonctionne de la façon suivante : n travaux à effectuer sont en attente, ils vont être pris en charge par m threads (m < n). L'objectif est de borner le nombre de threads d'une application.
On verra, en deuxième partie, les outils de haut niveau proposés par Java, pour gérer des pools de threads.

Nous utiliserons ici wait et notify.

Scénario :
Comme on l'a vu, il s'agit d'affecter des travaux à un nombre restreint de threads. Deux types de threads sont utilisés: Chef et Travailleur.

les threads du type Travailleur, au nombre de m, attendent qu'il y ait des travaux à effectuer, ces travaux sont au nombre de n.
n et m sont des paramètres donnés sur la ligne de commande.
un thread du type Chef initialise le nombre de travaux à faire et débloque tous les threads du type Travailleur,
tant qu'il y a des travaux à effectuer, les threads Travailleurs les prennent en charge.
Il y a n travaux pour m threads, et n est supérieur à m,
lorsque tous les travaux sont pris en charge, les threads Travailleurs qui n'ont rien à faire se mettent en attente de nouveaux travaux.

On utilisera deux objets de synchronisation :

une barrière sur laquelle attendent les Travailleurs quand ils n'ont rien à faire et qui est levée par le thread Chef,
Un objet qui contient le nombre de travaux à faire sur lequel se bloque le chef en attendant que tous les travaux aient été pris en charge.

Le canevas détaillé du programme réalisant cette application se trouve ici .
Le support de cours sur les threads se trouve ici .

A faire :

On vous demande de compléter ce programme, c'est à dire d'écrire les méthodes de synchronisation.
Que peut-il se passer si les threads ne sont pas démarrés dans l'ordre des start ?

On trouve ici la documentation Sun sur wait et notify : ici.

II.1Sémaphores

II.1 Avant JDK-1.5 : Réalisation d'un sémaphore

Les sémaphores tels que définis par Dijkstra sont maintenant disponibles dans le JDK-1.5, cet exercice montre comment utiliser les méthodes de base pour créer des outils de plus haut niveau.

On se propose de réaliser en Java les opérations classiques P et V sur les sémaphores.
Pour l'opération P :

on utilisera la méthode wait pour bloquer les threads.
en plus du compteur (appelée ici Compteur) , on tiendra également à jour le nombre de threads bloqués en utilisant une variable appelée Bloques qui indique le nombre de threads qui n'ont pas accès à la ressource.

Pour l'opération V :

on utilisera notify pour débloquer l'un des threads bloqués

On partira des canevas proposés dans les fichiers Semaphore.java et SemaphoreExemple.java disponibles : ici , et ici .

Après avoir complété ces fichiers, on vérifiera que l'exécution de la commande :
java SemaphoreExemple 3 1
Donne une séquence d'exécution de la forme suivante :

Fin de main
Thread_2 VEUT entrer en SC
Thread_2      Entre en SC
Thread_0 VEUT entrer en SC
    Nbre de threads bloques : 1
Thread_1 VEUT entrer en SC
    Nbre de threads bloques : 2
Thread_2      Fin SC
Thread_0      Entre en SC
Thread_0      Fin SC
Thread_1      Entre en SC
Thread_2 VEUT entrer en SC
    Nbre de threads bloques : 1
Thread_1      Fin SC
Thread_2      Entre en SC
Thread_0 VEUT entrer en SC
    Nbre de threads bloques : 1
Thread_2      Fin SC
Thread_0      Entre en SC
Thread_0      Fin SC

Vérifier également le bon fonctionnement des scénarii suivants :

```
java SemaphoreExemple 0 1
Fin de main
```
```
java SemaphoreExemple 0 0
Fin de main
```


java SemaphoreExemple 2 0
Fin de main
Thread_1 VEUT entrer en SC
    Nbre de threads bloques : 1
Thread_0 VEUT entrer en SC
    Nbre de threads bloques : 2


java SemaphoreExemple 2 3
Fin de main
Thread_0 VEUT entrer en SC
Thread_0      Entre en SC
Thread_0      Fin SC
Thread_1 VEUT entrer en SC
Thread_1      Entre en SC
Thread_0 VEUT entrer en SC
Thread_0      Entre en SC
...

II.2 Schéma producteur/consommateur

En reprenant le sémaphore réalisé dans l'exemple précédent, on va illuster le schéma producteur/consommateur dans le cas où un seul producteur et un seul consommateur travaillent en utilisant un tampon de dimension N.

Rappel du schéma producteur/consommateur géré par deux sémaphores SP et SC, le tampon contient N cases.
Il y a un seul producteur et un seul consommateur.

Init(SP, N)
Init(SC, 0)

Producteur	Consommateur
... P(SP) Mettre info. dans tampon V(SC) ...	... P(SC) Prendre info. dans tampon V(SP) ...

On partira du squelette proposé dans le fichier SemaphoreExemplePC.java qui se trouve : ici ,

A FAIRE :

Expliquer les rôles et l'utilisation de Tab_Semaphore[0] et Tab_Semaphore[1] .

Compléter ce fichier et vérifier que l'exécution de la commande :
java SemaphoreExemplePC 4
Donne une séquence d'exécution de la forme suivante : Fin de main Nbre de threads bloques : 1 prod : Mon_Tamp[0] = 0 conso : Mon_Tamp[0] = 0 prod : Mon_Tamp[1] = 1 conso : Mon_Tamp[1] = 1 prod : Mon_Tamp[2] = 2 conso : Mon_Tamp[2] = 2 prod : Mon_Tamp[3] = 3 prod : Mon_Tamp[0] = 4 conso : Mon_Tamp[3] = 3 prod : Mon_Tamp[1] = 5 conso : Mon_Tamp[0] = 4 prod : Mon_Tamp[2] = 6 conso : Mon_Tamp[1] = 5 conso : Mon_Tamp[2] = 6 prod : Mon_Tamp[3] = 7 prod : Mon_Tamp[0] = 8 conso : Mon_Tamp[3] = 7

II.3 Schéma producteur/consommateur (2)

On va maintenant écrire un scénario producteur/consommateur impliquant N producteurs et M consommateurs partageant un tampon circulaire à P cases.
Après S secondes d'attente les consommateurs abandonnent l'accès au tampon.

On partira du squelette proposé dans le fichier TampCirc.java qui se trouve : ici ,

Des threads du type Producteur et Consommateur font accès à un objet du type TampCirc doté des méthodes suivantes :

Méthode Produire :
- Si le tampon est plein, attendre.
- Sinon,
  - verrouiller l'accès à la ressource,
  - faire un dépôt dans la première case libre, (indexée par IndProd), mettre à jour IndProd, incrémenter le nombre de cases non lues,
  - rendre l'accès à la ressource, ce qui va avoir pour effet de réveiller les éventuels consommateurs. Ainsi tous les producteurs et tous les consommateurs peuvent maintenant accéder au tampon.
Méthode Consommer :
- Si le tampon est vide, attendre pendant AU PLUS timeout secondes.
- Sinon,
  - lire la première case libre, (indexée par IndCons), mettre à jour IndCons, décrémenter le nombre de cases non lues
  - rendre l'accès à la ressource, ce qui va avoir pour effet de réveiller les éventuels producteurs. Ainsi tous les producteurs et tous les consommateurs peuvent maintenant accéder au tampon.
    On indique le temps d'attente.

A FAIRE :

Compléter la méthode main,
Compléter la méthode Consommer pour traiter le timeout de wait,
Compléter la méthode Produire,
... et vérifier que le scénario est bien respecté.

III. Autour des threads

Nous allons présenter quelques un des outils proposés depuis la version 1.5 du JDK.

III.1 Threads : `runnable`, `callable`, interface `Future`

On va voir ici l'utilisation de threads qui implémentent, non pas runnable, mais callable. Ces threads disposent d'une méthode call qui remplace la méthode run, la méthode call permettant de renvoyer une valeur, ces threads pourront alors renvoyer un résultat.

Par exemple, pour renvoyer un objet Integer :
class ... implements Callable<Integer>

Mais alors, comment savoir, lorsque l'on consulte l'objet contenant ce résultat, s'il contient bien la valeur écrite par le thread chargé de sa mise à jour ?
C'est à dire : est-on sûr que la nouvelle valeur a bien été déposée dans l'objet quand on va le consulter (cf. modèle producteur/consommateur)?
Pour soulager l'utilisateur de la résolution de ce problème, les objets renvoyés par callable sont des objets du type Future. Ces derniers encapsulent une méthode get() qui est bloquante tant que la méthode call de l'objet callable correspondant ne s'est pas terminée, de façon normale ou non. Dans ce dernier cas get() remonte l'exception.

Exercice

Pour illustrer ces fonctionnalités, nous allons mettre en oeuvre le programme suivant : compter, à partir d'un répertoire de départ, le nombre de fichiers qui contiennent au moins une occurence d'un mot donné.

Scénario :

Une tâche du type callable est créée pour scruter un répertoire dont on a donné le nom, elle renverra le nombre de fichiers, accessibles à partir de ce répertoire, où se trouve au moins une occurrence du mot cherché. Voici le fonctionnement de cette tâche :

Cette tâche créé un compteur et un tableau de <Future<Integer>> :
```
 ArrayList<Future<Integer>> Resultats = new ArrayList<Future<Integer>>();
```
En effet, ce tableau sera mis à jour par des objets callables (cf. 2.2 ci-dessous).
Elle scrute le répertoire courant et teste le type de chaque fichier qui s'y trouve :
1. si le fichier est un fichier ordinaire, on y cherche le mot. A la première occurrence de ce mot, on incrémente le compteur et on passe au fichier suivant,
2. si le fichier est un répertoire, on créé récursivement une nouvelle tâche pour scruter ce répertoire, cette tâche ajoute dynamiquement un élément au tableau de <Future<Integer>>.
Ainsi, après avoir testé tous les fichiers du répertoire courant, la tâche va attendre la fin de celles créées pour scruter les sous-répertoires.
Pour ce faire, elle se bloque successivement sur toutes les cases du tableau de <Future<Integer>> (appel à la méthode get) pour attendre leur mise à jour et ajouter la valeur obtenue au compteur.

Illustration :

Figure -1-

Remarque sur l'utilisation des objets callables :
Si on a une classe du type :
class Objet_Callable implements Callable<Integer>
et si on veut exécuter cet objet en tant que thread, on peut faire comme suit :

	  Integer Retour;
	  FutureTask<Integer> La_Tache;
	  ... 
	  Objet_Callable Mon_Callable = new Objet_Callable();
	  ... 
	 /* creer et demarrer un thread "callable" qui renvoie un Integer */
	  La_Tache  = new FutureTask<Integer>(Mon_Callable);
	  Thread Ma_Tache = new Thread(La_Tache);
	  Ma_Tache.start(); 
	  ...
	/* Attendre le resultat renvoye par le thread du type callable */
	  Retour =  La_Tache.get();

Documentation :

pour Future : Future
pour callable : callable
pour Sun Java 1.5. : Sun Java 1.5

On partira du canevas proposé dans le fichier Chercher-V1.java qui se trouve : ici .

Exemple d'exécution avec le répertoire suivant :

Figure -2-

les disques noirs sont des répertoires,
les disques blancs sont des fichiers ordinaires, ils ne sont pas tous représentés,

frechou% javac Chercher-V1.java frechou% java ChercherV1 Donner repertoire de depart . Mot a chercher a partir de ce repertoire : main Thread-0 Debut Thread-0 Lance une tache pour ./Rep21 Thread-1 Debut Thread-1 Fin Thread-0 Lance une tache pour ./Rep22 Thread-2 Debut Thread-2 Fin Thread-0 Lance une tache pour ./Rep23 Thread-3 Debut Thread-0 attendre resultats Thread-0 obtient : 12 Thread-0 attendre resultats Thread-0 obtient : 14 Thread-0 attendre resultats Thread-3 Lance une tache pour ./Rep23/Rep31 Thread-4 Debut Thread-4 Fin Thread-3 attendre resultats Thread-3 obtient : 5 Thread-3 Fin Thread-0 obtient : 19 Thread-0 Fin Le mot main se trouve dans 19 fichiers.

III.2 Utilisation des pools de threads

Pour éviter de créer un grand nombre de threads, utilisés chacun seulement pendant une très courte durée, on peut créer un pool de threads. (cf. le premier exercice).
Le gestionnaire du pool gère un nombre (le plus souvent) limité de threads et affecte les threads inactifs aux nouvelles tâches. Ainsi, au lieu de créer un thread chaque fois qu'il va lancer une nouvelle tâche, le programme soumet cette tâche au gestionnaire du pool qui l'exécutera en recyclant les threads inactifs dans le pool.

Les différents types de pools sont les suivants :

FixedThreadPool : pool de taille fixe,
CachedThreadPool : pool dont la taille s'adapte à la demande,
ScheduledThreadPool : pool qui lance les threads à intervalles réguliers (FixedRate , FixedDelay)

Remarque :
On sépare ainsi la soumission d'une tâche de son ordonnancement. L'appel à la méthode start appliquée à un thread sera remplacé par un appel à la méthode submit sur le pool en lui passant en argument un objet runnable ou callable .

Documentation

Exemple de base illustrant le fonctionnement d'un pool du type FixedThreadPool: ici .
Exécuter et commenter la trace.
Consulter la documentation Sun sur la concurrence, et, en particulier : celle sur les executors

Question 1:
Modifier le programme Chercher-V1.java en remplaçant la création de threads par à l'appel à un pool de threads à chaque fois qu'un répertoire est rencontré. (ceci simplifiera le code).

On utilisera un FixedThreadPool, par exemple :
ExecutorService Mon_Executor = Executors.newFixedThreadPool(10);
puis un FixedThreadPool, par exemple :
ExecutorService Mon_Executor = Executors.newCachedThreadPool();

On partira du canevas proposé dans le fichier Chercher-V2.java qui se trouve : ici .

On reprend l'exemple de la Figure 2 : la trace suivante montre la réutilisation des threads inactifs par le gestionnaire du pool :


frechou% java ChercherV2 
Donner repertoire de depart .
Mot a chercher a partir de ce repertoire : main
Thread-0 Debut
Thread-0 Lance une tache pour ./Rep21
pool-1-thread-1 Debut
pool-1-thread-1 Fin
Thread-0 Lance une tache pour ./Rep22
pool-1-thread-1 Debut
Thread-0 Lance une tache pour ./Rep23
pool-1-thread-2 Debut
pool-1-thread-1 Fin
Thread-0 attendre resultats 
Thread-0 obtient :  12
Thread-0 attendre resultats 
Thread-0 obtient :  14
Thread-0 attendre resultats 
pool-1-thread-2 Lance une tache pour ./Rep23/Rep31
pool-1-thread-1 Debut
pool-1-thread-1 Fin
pool-1-thread-2 attendre resultats 
pool-1-thread-2 obtient :  5
pool-1-thread-2 Fin
Thread-0 obtient :  19
Thread-0 Fin
Le mot main se trouve dans 19 fichiers.

Question 2:
Dans le cas de l'utilisation d'un FixedThreadPool, l'application peut se bloquer parce qu'elle ne dispose pas d'un assez grand nombre de threads.
Modifiez la utilisant la méthode get avec un timeout.