INF223: Travaux Pratiques sur la Programmation Concurrente en Java

$Id: index.html,v 1.22 2010/09/29 13:18:22 pautet Exp $

Bertrand Dupouy (dupouy@telecom-paristech.fr) Jérôme Hugues (hugues@telecom-paristech.fr) Laurent Pautet (pautet@telecom-paristech.fr)

Index

1 TP de Concurrence en Java

Vous n'avez pas à rendre ce TP. Cependant, vous devez impérativement terminer la partie Synchronisation - Sémaphore car elle sera ré-utilisée dans le cas d'étude. Vous pouvez éventuellement terminer la partie Synchronisation - Barrière car elle porte sur des constructions concurrentes évoluées mais utiles pour la bonne compréhension du domaine.

1.1 Introduction

Ce TP ne présente pas tous les outils proposés par Java pour gérer la concurrence. Il illustre le fonctionnement de quelques uns d'entre eux, en commençant par ceux de plus bas niveau, wait() et notify() documentés ici. Le support de cours sur les threads se trouve ici.

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

Pour accéder à :

Vous trouverez dans cette archive compressée l'intégralité des sources.

Pour décompresser, utiliser GNU tar:

     /usr/local/bin/tar zxf src.tar.gz

1.2 Synchronisation - Sémaphore (obligatoire)

1.2.1 Réalisation d'un sémaphore

Les sémaphores tels que définis par Dijkstra sont maintenant disponibles dans le JDK-1.5. Nous ne les utiliserons pas et au contraire, cet exercice vise à utiliser les méthodes de bas niveau, comme wait() et notify(), pour créer ces outils de plus haut niveau que sont les sémaphores. Nous nous proposons de réaliser en Java les opérations classiques P (ou acquire) et V (ou release) des sémaphores.

Pour l'opération P (ou acquire):

Pour l'opération V (ou release):

Nous partirons des canevas proposés dans les fichiers Semaphore.java, Agent.java et SemaphoreMain.java.

Questions

Après avoir complété ces fichiers, nous vérifierons que l'exécution de la commande :

     javac SemaphoreMain.java
     java SemaphoreMain 3 1

Donne une séquence d'exécution de la forme suivante :

     main terminated
     Agent 1 WANTS to acquire resource
     Agent 1 ACQUIRE resource
     Agent 1 RELEASE resource
     Agent 0 WANTS to acquire resource
     Agent 0 ACQUIRE resource
     Agent 0 RELEASE resource
     Agent 2 WANTS to acquire resource
     Agent 2 ACQUIRE resource
     Agent 2 RELEASE resource
     Agent 0 WANTS to acquire resource
     Agent 0 ACQUIRE resource
     Agent 0 RELEASE resource
     Agent 2 WANTS to acquire resource
     Agent 2 ACQUIRE resource
     Agent 1 WANTS to acquire resource
     Agent 2 RELEASE resource
     Agent 1 ACQUIRE resource
     Agent 1 RELEASE resource
     Agent 0 WANTS to acquire resource
     Agent 0 ACQUIRE resource
     Agent 0 RELEASE resource
     Agent 0 completed
     Agent 2 WANTS to acquire resource
     Agent 2 ACQUIRE resource
     Agent 2 RELEASE resource
     Agent 2 completed
     Agent 1 WANTS to acquire resource
     Agent 1 ACQUIRE resource
     Agent 1 RELEASE resource
     Agent 1 completed

Puis vérifier également le bon fonctionnement des scénarii suivants.

1.2.2 Schéma producteur / consommateur avec Sémaphores

En reprenant le sémaphore réalisé dans l'exemple précédent, nous allons illuster le schéma producteur/consommateur dans le cas où P producteurs et C consommateurs travaillent en utilisant un tampon de dimension N. Dès lors, un producteur ne produit que si le tampon n'est pas plein et le consommateur ne consomme que si le tampon n'est pas vide.

Nous rappellons le schéma producteur/consommateur géré par deux sémaphores emptySlots et fullSlots, le tampon contenant N cases. Il faut également une exclusion mutuelle pour assurer que plusieurs consommateurs ou plusieurs producteurs ne modifient pas le tampon en même temps. Cette exclusion mutuelle sera mise en oeuvre directement à partir de Java.

Init (EmptySlots, N);
Init (FullSlots, 0);

Producteur Consommateur
...
P (EmptySlots)
remplir une case
de manière atomique
V (FullSlots)
...
...
P (FullSlots)
vider une case
de manière atomique
V (EmptySlots)
...

Nous partirons des squelettes proposés dans les fichiers BoundedBuffer.java, SemConsumer.java, SemProducer.java, SemBoundedBuffer.java et SemBoundedBufferMain.java.

Questions

1.2.3 Schéma producteur / consommateur sans Sémaphores

Nous allons écrire de nouveau le scénario producteur/consommateur impliquant P producteurs et C consommateurs partageant un tampon de taille fixe à N cases. Cependant, nous ne souhaitons pas cette fois réaliser l'implantation à l'aide de sémaphores mais directement à l'aide des méthodes wait(), notify() et notifyAll().

Par ailleurs, nous souhaitons que les méthodes get() et put() disposent d'une version qui permette de ne pas attendre au delà d'un certain nombre de milli-secondes, un paramètre supplémentaire timeout indiquant le temps d'attente.

Nous partirons des squelettes proposés dans les fichiers TimedConsumer.java, TimedProducer.java, TimedBoundedBuffer.java et TimedBoundedBufferMain.java.

Questions

1.3 Synchronisation - Barrière (optionnel)

Nous allons écrire une application qui gère un groupe de N travaux en les faisant traiter par un groupe de M travailleurs (threads). L'objectif est de limiter le nombre de threads (donc M < N).

Nous utiliserons ici wait(), notify() et notifyAll() documentés ici.

Scénario :

Comme indiqué, il s'agit d'affecter des travaux à un nombre restreint de threads. Deux types de threads sont utilisés : Master et Worker.

  1. Les threads du type Worker, au nombre de nWorkers, attendent qu'il y ait des travaux à effectuer, au nombre de nJobs. Ces deux nombres sont des paramètres donnés sur la ligne de commande.
  2. Un thread du type Master fournit les travaux à faire. Lorsqu'il est prêt, il débloque tous les threads du type Worker.
  3. Tant qu'il y a des travaux à effectuer, les Workers les prennent en charge.
  4. Un Worker est averti du fait que tous les travaux ont été effectués lorsqu'il obtient un numéro de travail égal à 0. Dans un premier temps, les Workers se terminent lorsque tous les travaux ont été effectués.

Nous allons utiliser des barrières pour assurer les points de synchronisation entre Master et Worker.

Définition et utilisation d'une barrière :

Une barrière est un outil de synchronisation qui fournit les fonctionnalités suivantes :

Un cas classique d'utilisation est de considérer comme ressource la présence d'un thread à un point de rendez-vous. Pour s'assurer que N threads sont présents à un même point de synchronisation, nous définissons une barrière initialisée à N. Chaque thread arrivant au point de synchronisation enchaînera les appels à Countdown pour signaler sa présence, puis à Await pour attendre l'arrivée des autres threads. Naturellement, si nous voulons réutiliser cette barrière, se posera le problème de la réinitialisation de la barrière. En effet, il faudra s'assurer que la réinitialisation n'a pas lieu alors que certains threads n'ont pas encore franchi le point de synchronisation.

Approche de la conception :

Dans un premier temps, Master ne fournit des travaux qu'une seule fois (pas de fonctionnement en boucle). Dans un deuxième temps, nous rajouterons des barrières pour clairement identifier le début et la fin des travaux. Dans un dernier temps, nous ferons en sorte que Master et Worker effectuent leur travail en boucle.

1.3.1 Barrière - Sans boucle - Sans synchronisation de début et de fin

Nous voulons faire en sorte que les Workers ne s'activent que lorsque Master a fourni ses travaux. Nous allons définir deux barrières :

Nous partirons des squelettes proposés dans les fichiers Barrier.java, Master.java, Worker.java et BarrierMain.java.

Questions

  1. Compléter le canevas Barrier.java pour que les fonctionnalités Countdown et Await soient assurées.
  2. Complèter le canevas de BarrierMain.java pour que la barrière ActivatedWorkers soit correctement initialisée.
  3. Complèter les canevas de Master.java et Worker.java pour que la barrière ActivatedWorkers serve à bloquer les Workers en attendant que Master ait défini les travaux à effectuer.
  4. Cette définition des travaux à effectuer correspond dans Master à un appel à Initialize de AvailableJobs.
  5. Vérifiez le bon fonctionnement en construisant l'exemple et en le testant :
              javac BarrierMain.java
              java BarrierMain 3 10
    

1.3.2 Barrière - Sans boucle - Avec synchronisation de début et de fin

Nous voulons exécuter en boucle Master et Workers pour produire et traiter des travaux indéfiniment.

Mais avant de réaliser cette fonctionnalité, nous allons faire en sorte que Master et Worker démarrent en même temps et se terminent en même temps (afin de synchroniser Master et Worker sur le début et la fin de la boucle).

Nous allons donc rajouter deux nouvelles barrières :

Questions

  1. Compléter les classes précédentes Master et Worker en positionnant les appels aux barrières ActivatedThreads et CompletedThreads.
  2. Complèter la classe précédente Master pour qu'elle devienne responsable de l'initialisation d'ActivatedWorkers. On conservera toutefois l'initialisation d'ActivatedWorkers faite dans main.
  3. Vérifiez le bon fonctionnement en construisant l'exemple et en le testant :
              javac BarrierMain.java
              java BarrierMain 3 10
    

1.3.3 Barrière - Avec boucle - Avec synchronisation de début et de fin

Désormais, Master et Worker s'exécutent en boucle. Les méthodes run de Master et Worker sont donc identiques à ceci près qu'elles s'exécutent sans fin.

Les problèmes que nous allons devoir traiter portent sur la réinitialisation des barrières au cours des différentes boucles.

Questions

  1. Compléter les classes précédentes Master et Worker pour qu'ils effectuent leur activité en boucle.
  2. Effectuer dans la classe Master la réinitialisation de ActivatedWorkers (déjà fait normalement) et de ActivatedThreads (avant de reprendre l'exécution de la boucle).
  3. Rajouter dans la classe Master la barrière CompletedWorkers qui deviendra passante pour Master une fois que tous les processus auront terminé leur travail. Ce point de synchronisation permettra de s'assurer que ActivatedThreads n'est pas réinitialisée alors que certaines threads n'ont pas encore franchi cette barrière.
  4. Effectuer dans la classe Master la réinitialisation de CompletedWorkers et de CompletedThreads. Comme précédemment, nous prendrons soin d'effectuer ces réinitialisations en vérifiant qu'aucun thread n'est encore en train de les utiliser.
  5. Vérifiez le bon fonctionnement en construisant l'exemple et en le testant :
              javac BarrierMain.java
              java BarrierMain 3 10