SE205: Travaux Pratiques sur la Programmation Concurrente en Java

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

Laurent Pautet (pautet@telecom-paristech.fr)

Index

1 TP de Concurrence en Java

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.

Pour accéder à :

• La documentation de Sun Java 1.2
• La documentation de Sun Java 1.5

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

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

• Nous utiliserons la méthode wait() pour bloquer les threads.
• Nous tiendrons à jour la valeur du compteur (appelée ici count) qui indique le nombre de resources disponibles ou manquantes.

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

• Nous utiliserons notify() pour débloquer l’un des threads bloqués.

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.

• Scénario 1

  java SemaphoreMain 0 1
  

  main terminated
  

• Scénario 2

  java SemaphoreMain 0 0
  

  main terminated
  

• Scénario 3

  java SemaphoreMain 2 3
  

  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 0 WANTS to acquire resource
  Agent 0 ACQUIRE resource
  Agent 0 RELEASE resource
  Agent 0 WANTS to acquire resource
  Agent 0 ACQUIRE resource
  Agent 1 WANTS to acquire resource
  Agent 1 ACQUIRE resource
  Agent 0 RELEASE resource
  Agent 0 completed
  Agent 1 RELEASE resource
  Agent 1 WANTS to acquire resource
  Agent 1 ACQUIRE resource
  Agent 1 RELEASE resource
  Agent 1 completed
  

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);

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

Questions

• Regarder l’implémentation du tampon de taille fixe qui se trouve dans la classe BoundedBuffer. Cette implémentation ne fournit aucune fonctionnalité de synchronisation notamment lorsque le tampon est vide ou lorsqu’il est plein.
• Complèter l’extension du tampon de taille fixe décrit dans SemBoundedBuffer pour qu’il fournisse les fonctionnalités de synchronisation décrites plus haut à l’aide de sémaphores.

  javac SemBoundedBufferMain.java
  java SemBoundedBufferMain 4 4 2 
  

  donne une séquence d’exécution de la forme suivante :

  java BoundedBufferMain 4 4 2
  Producer 0 want to put value
  Producer 0 put value 1
  main completed
  Producer 1 want to put value
  Producer 1 put value 1
  Producer 2 want to put value
  Consumer 0 want to get value
  Consumer 0 got value 1
  Producer 2 put value 4
  Consumer 1 want to get value
  Consumer 1 got value 1
  Producer 0 want to put value
  Producer 0 put value 9
  Producer 2 want to put value
  Consumer 3 want to get value
  Consumer 3 got value 4
  Producer 2 put value 2
  Consumer 0 want to get value
  Consumer 0 got value 9
  Producer 1 want to put value
  Producer 1 put value 4
  ...
  

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

• Compléter la classe TimedBoundedBuffer.
• En premier lieu, complèter les méthodes get et put sans paramètre timeout. Nous ne ferons pas appel cette fois-ci à des sémaphores.
• En second lieu, complèter les méthodes get et put avec paramètre tiemout sachant que System.currentTimeMillis() permet d’obtenir l’heure en milli-secondes. Lorsque ces méthodes ont dépassé le temps imparti, elles doivent lever l’exception InterruptedException.
• Vérifier que le fonctionnement du tampon dans le cas où il y a trop de producteurs (des timeouts chez les producteurs doivent survenir). Vérification identique avec les consommateurs.

• java TimedBoundedBufferMain 2 4 2
  main completed
  Producer 0 want to put value
  Producer 0 put value 4
  Producer 2 want to put value
  Producer 2 put value 0
  Producer 3 want to put value
  Producer 2 want to put value
  Producer 0 want to put value
  Consumer 0 want to get value
  Consumer 0 got value 4
  Producer 3 put value 5
  Producer 1 want to put value
  Consumer 1 want to get value
  Consumer 1 got value 0
  Producer 2 put value 8
  Consumer 0 want to get value
  Consumer 0 got value 5
  Producer 0 put value 6
  Producer 3 want to put value
  Producer 2 want to put value
  Consumer 1 want to get value
  Consumer 1 got value 8
  Producer 1 INTERRUPTED
  Producer 3 INTERRUPTED
  Producer 2 put value 7
  Consumer 0 want to get value
  Consumer 0 got value 6
  Producer 0 want to put value
  Producer 0 put value 8
  ...
  

1.3 Synchronisation - Barrière

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 :

• Une barrière est bloquante tant que N resources (ou thread) ne sont pas présentes. Dit autrement, dès que plus aucune ressource n’est manquante (ou thread), tout thread en attente est débloqué.
• La fonction Countdown diminue le nombre de ressources manquantes s’il est positif. Cette fonction retourne le nombre de ressources manquantes tel qu’il était avant l’appel à Countdown.
• La fonction Await permet de bloquer en attendant que toutes les ressources soient présentes (ou qu’aucune ressource soit manquante).

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 :

• La barrière AvailableJobs ne sera pas utilisée comme objet de synchronisation en tant que tel. Il s’agit de réutiliser le concept de barrière pour assigner des travaux grâce à Countdown sans jamais exploiter la méthode bloquante Await.
• Les Worker obtiendront donc toutes les valeurs allant de N à 0. Pour simplifier l’exercice, nous supposerons que ces valeurs représentent les ressouces à traiter par Worker.
• La barrière ActivatedWorkers se charge de bloquer un Worker tant que Master n’a pas terminé de définir les travaux à effectuer.

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 :

• La barrière ActivatedThreads se charge de bloquer Master et Worker afin qu’elles démarrent ensemble ce qui est actuellement obtenu par l’appel à la méthode start. Ceci marquera plus tard le début de la boucle.
• La barrière CompletedThreads se charge de bloquer Master et Worker afin qu’ils se terminent ensemble ce qui est actuellement obtenu par la terminaison du processus Unix. Ceci marquera plus tard la fin de la boucle.

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.

• La réinitialisation d’une barrière B2 sera effectuée uniquement par Master (jamais dans Worker) afin d’éviter des réinitialisations multiples.
• La réinitialisation d’une barrière B2 ne doit pas avoir lieu alors que des threads sont encore en train d’utiliser celle-ci.
• Nous allons définir deux phases d’exécution pour Master et Worker autour d’une barrière B2 :
  1. la phase d’utilisation
  2. la phase de réinitialisation.
• Elles seront séparées à l’aide de deux points de synchronisation communs (à Master et à Worker) représentés par le passage de deux barrières B1 et B3.
• Avant de réinitialiser une barrière B2, nous devons nous assurer que tous les threads l’utilisant :
  • ont passé une barrière B1 (aucun processus n’est encore en train d’utiliser B2)
  • n’ont pas encore franchi une barrière B3 (aucun processus n’est déjà en train d’utiliser B2).

  L’utilisation de la barrière se fera donc après avoir passé la barrière B3 et avant d’avoir passé la barrière B1.

  Par soucis de simplication, nous conserverons toutefois les initialisations de barrières faites dans main (en plus de celles qui seront faites dans Master).

• Pour illustrer cette isolation de la phase de réinitialisation vis à vis de celle d’utilisation, ActivateWorkers doit être initialisée avant que Master débloque ActivatedThreads mais après que tous les processus aient passé CompletedThreads.
• Pour réinitialiser ActivatedThreads et CompletedThreads, nous aurons besoin d’une dernière barrière que nous nommerons CompletedWorkers qui deviendra passante pour Master une fois que tous les processus auront terminé leur travail.

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