TP-systemes-concurrents/TP1/CC_README.md

Concurrence et cohérence

Objectifs

• évaluer le gain, le coût et le contexte approprié à la mise en œuvre multi-activités d'un traitement
• mettre en évidence les problèmes de cohérence induits par _ l'exécution d'activités concurrentes _ les mécanismes d'optimisation matériels (caches, pipelines) et logiciels (réordonnancement des instructions)

Préparation

Cette partie présente quelques constructions et outils disponibles sur la plateforme Java, en se limitant aux éléments nécessaires à la réalisation des exercices.

Les activités (threads) Java

La brève présentation qui suit peut être illustrée et par la lecture de la partie correspondante du cours sur les processus légers (6ème partie, planches 10-13). Les planches suivantes et la documentation présentent plus de détails, leur lecture n'est pas nécessaire dans l'immédiat.

• la classe Thread, intégrée au langage (paquetage java.lang), permet de définir un processus (léger), ou thread au sein d'une application Java (JVM)
• la classe Thread fournit (en particulier)
  • une méthode start qui permet de lancer l'instance de thread auquel elle est appliquée
  • une méthode join (void join() throws InterruptedException), qui permet d'attendre la terminaison l'instance de thread auquel elle est appliquée _ une méthode de classe, static Thread currentThread() qui fournit la référence du thread en cours d'exécution _ une méthode de classe, static void sleep(long ms) throws InterruptedException qui suspend le thread appelant pour une durée de ms millisecondes
• le constructeur de la classe Thread prend un paramètre d'une classe implémentant l'interface Runnable. Cette interface expose une méthode public void run(). La méthode run() définit le code qui sera exécuté par le thread correspondant.

Les planches 10 et 11 fournissent des exemples simples du schéma standard de création de threads

Le modèle de cohérence Java

Par défaut, Java n'offre pas de garantie de cohérence pour les variables partagées, utilisées simultanément par un ensemble de threads. En particulier, les instructions sont susceptibles d'être réordonnées, et la cohérence des caches n'est pas assurée.

Cependant Java offre quelques outils de base pour faciliter la programmation multiactivités avec des variables partagées :

• le mot-clé volatile associé à un attribut élémentaire ou une référence garantit que (tout se passe comme si) les accès à cet attribut ne sont pas effectués dans le cache, mai directement en mémoire, ce qui permet de considérer que les accès concurrents ont été effectués en suivant un ordre total global. En outre, l'accès à des variables volatile inhibe le réordonnancement des instructions
• le paquetage java.util.concurrent.atomic propose un ensemble de classes « atomiques », qui fournissent un ensemble de méthodes dont l'exécution est garantie sans interférences. La différence avec des méthodes synchronized (vues tout de suite après) est que l'absence d'interférences est obtenue sans qu'il y ait à faire attendre (bloquer) des activités en conflit. L'algorithmique de la mise en œuvre de tels objets est abordée dans la dernière partie du cours. La documentation Java en ligne fournit le détail de ces classes et de leur interface.

Les verrous Java

Historiquement, il s'agit du premier outil de synchronisation proposé en Java, disponible dès les premières versions du langage. Le service rendu, très élémentaire, s'avère pratique et adapté pour exprimer l'exclusion mutuelle, ce qui fait qu'il reste largement utilisé, même actuellement, car la simple exclusion mutuelle représente le schéma de synchronisation le plus souvent rencontré. En revanche, il se révèle lourd et malcommode dès qu'il s'agit de réaliser des schémas un peu plus évolués que l'exclusion mutuelle. D'où les objets de synchronisation plus classiques et robustes apparus à partir de la version 5 de Java.

La rapide présentation qui suit porte essentiellement sur la syntaxe. Elle peut être complétée par la lecture de la partie correspondante du cours sur les processus légers (planches 36-40) pour les notions et sur la documentation Java en ligne pour les détails techniques.

Principe

Tout objet Java peut être utilisé comme un verrou pour contrôler l'accès à une section critique.

Syntaxe

• Le mot-clé synchronized permet de définir très simplement une section critique contrôlée par (le verrou d')un objet unObj, avec la syntaxe suivante synchronized (unObj) { section critique }

• Le mot-clé synchronized peut aussi être utilisé pour qualifier une méthode. Il indique alors que la méthode sera exécutée en exclusion mutuelle, et que (le verrou de l'instance de) l'objet fournissant cette méthode est utilisé pour contrôler cette exclusion mutuelle.

• Enfin, il est possible de qualifier des méthodes de classe (statiques) comme synchronized. Dans ce cas, le verrou est associé à la classe, non à ses instances.

Autres classes, méthodes et remarques utiles

• la classe System fournit deux méthodes, System.nanoTime() et System.currentTimeMillis() qui fournissent une durée écoulée (en ns et ms) depuis une date d'origine non spécifiée. La différence entre les valeurs retournées par deux appels successifs permet d'évaluer le temps écoulé entre ces deux appels.
• Le constructeur de la classe Thread peut prendre un paramètre de classe String, qui permet de donner un nom à l'instance de Thread créée. Le nom peut être accédé via les méthodes getName() et setName()
• Selon votre configuration, il est possible que le format par défaut pour les fichiers source Java soit le format ASCII. Dans ce cas, des erreurs apparaitront lors de la compilation des fichiers de l'archive, qui sont codés en UTF8. Pour remédier à cela, il est possible de positionner la variable d'environnement JAVA_TOOL_OPTIONS (en bash : export JAVA_TOOL_OPTIONS=-Dfile.encoding=UTF8), ou encore de lancer la compilation avec l'option -encoding UTF8, ce qui donne ici : javac -encoding UTF8 *.java
• l'interpréteur Java (commande java) founit deux options qui ne seront pas forcément nécessaires ici, mais qui peuvent être utiles dans un contexte d'évaluation de performances :
  • -Xint force le passage en mode interprété pur (pas de compilation à la volée, ni par conséquent d'optimisation)
  • -Xprof fournit des statistiques sur les temps d'exécution des threads.

Exercices

Efficacité de la parallélisation

Il s'agit d'évaluer le gain de temps apporté par la décomposition d'un traitement en plusieurs threads. On considère le traitement réalisé par la classe IncrMes fournie dans l'archive, qui consiste en une boucle qui incrémente un compteur global. Le nombre important d'itérations est destiné à permettre des mesures significatives, mais va nécessiter l'emploi d'entiers longs.

Comparer le temps d'exécution de l'exécution séquentielle de la boucle (lignes 93-107 du code fourni) avec le temps d'exécution d'une application où N threads effectuent chacun 1/N ème de l'itération, N étant un paramètre fourni au lancement de l'application (lignes 114-117 du code fourni).

• Quel résultat « idéal » peut-on a priori espérer ?

• Mesurer le temps d'exécution réel, en fonction de N (en faisant varier N entre 1 et 50, sans nécessairement prendre toutes les valeurs :) )

  • Expliquez les différences observées entre le temps mesuré et le temps attendu.
  • Evaluer le surcoût induit par la gestion des threads, au moins en principe (Il est possible que cette valeur soit trop faible pour être mesurée ainsi, les différents mécanismes d'optimisation au niveau du matériel ou du compilateur et le contexte d'exécution nuisant à la précision des mesures, cf remarque finale)

Coût de la cohérence

Vérifier la correction des résultats obtenus par l'application précédente. Pour cela, chaque thread affichera la valeur du compteur avant de démarrer sa (fraction de) boucle, ainsi que la valeur du compteur après. (Il suffit pour cela de décommenter les affichages placés dans la méthode run(), à la fin du texte du programme.)

• Quelles seront a priori les valeurs affichées dans le cas où il n'y a pas préemption du processeur entre threads ?

• Quelles seront a priori les valeurs affichées dans le cas où la gestion des activités partage le temps processeur par quantum de temps entre threads ?

• Quelle est la politique effectivement suivie par la JVM utilisée pour le test ?

• La valeur finale du compteur devrait être égale au nombre total d'itérations. Vérifier que ce n'est pas le cas avec la version actuelle, et expliquer pourquoi.

• Afin de garantir la cohérence du résultat final, on effectue les incrémentations du compteur en exclusion mutuelle, en plaçant l'incrémentation dans un bloc synchronized, associé à un objet global quelconque. (Déclarer par exemple un attribut static Object mutex = new Object(); dans la classe principale). Vérifier que le résultat est maintenant effectivement correct, et évaluer le coût de l'utilisation de ce mécanisme.

  • en plaçant uniquement l'incrémentation de la boucle interne dans le bloc synchronized
  • en plaçant la boucle interne dans le bloc synchronized

• La correction du résultat est-elle garantie a priori si l'on utilise un objet de la classe java.util.concurrent.atomic.AtomicLong pour le compteur ? Argumenter, puis vérifier cet a priori. Evaluer le coût de l'utilisation de ce mécanisme

• La correction du résultat est-elle garantie a priori si l'on déclare le compteur comme volatile ? Argumenter, puis vérifier cet a priori. Evaluer le coût de l'utilisation de ce mécanisme.

• Conclure globalement sur les conditions d'utilisation (ou pas) de ces différents mécanismes.

Supplément

L'archive fournie contient une classe PCA, qui propose un exercice supplémentaire, dans un but de variété. Cet exercice porte sur les mêmes notions que les exercices autour de la classe IncrMes, et n'introduit rien de nouveau.

Tester les performances d'applications concurrentes en Java : quelques remarques pratiques

• sources de perturbation : cache, compilateur à la volée, ramasse miettes et optimiseur, charge de l'environnement (matériel, réseau) -> répéter les mesures et écarter les valeurs extrêmes (en général, les premières mesures). L'application fournie répète les mesures 10 fois par défaut, ce qui est un paramètre raisonnable (qui peut éventuellement être un peu réduit).
• tester sur des volumes de données significatifs
• connaître le nombre de processeurs réels disponibles