Prog Distr TP 2

Université Louis Pasteur

LICENCE 3ème année

Travaux Pratiques
de
Programmation Distribuée

(sujet n°2)

Threads java, Moniteurs

Télécharger ces exemples.

Exercice 1

Rendez-vous dans le répertoire 'ExemplesDuCours'.

Lancer le programme ExempleConcurrent plusieurs de fois de suite. Constater que le résultat n'est pas toujours identique. Comprendre pourquoi.
Lancer le programme EvtGenerator plusieurs de fois de suite. Comprendre les appels à wait() et notifyall() realise's dans le code.

Exercice 2

Rendez-vous dans le répertoire 'ProdCons'.

Il y a dans ce systeme deux types de threads :

un thread "producteur" qui produit periodiquement un objet (qui correspond ici à ajouter un entier quelconque à la fin d'un tableau)
un thread "consommateur" qui consomme périodiquement un objet (le dernier entier du tableau est supprimé)

Tous les threads communiquent par l'intermediaire d'un entrepot global, de taille fixee, initialement vide. Le probleme consiste à synchroniser tous les threads en jeu, de facon à ce que les contraintes suivantes soient vérifiées :

un thread producteur reste bloqué tant que l'entrepot ne dispose pas de place libre
un thread consommateur reste bloqué tant que l'entrepot ne contient pas d'objet à consommer.

Completez le squelette de programme 'ProdCons.java' pour qu'il ait les fonctionnalités décrites ci-dessus.

Rappels :

synchronized(obj) : signifie qu'un seul thread à la permission de rentrer dans le moniteur de obj.
wait : relache le moniteur et attend l'émission d'un notify ou notifyall : à la sortie du wait, le thread reprend le moniteur.
notify : reveille un thread en attente. Attention : lorsque notify est appelée et qu'il n'y a aucun thread en attente, cette notification est perdue (elle ne sera pas réémise).
notifyall : reveille tous les threads en attente.

Exercice 3

Rendez-vous dans le répertoire 'LecteurEcrivain'.

On se place ici dans le cadre d'un système disposant d'une donnée partagée et comportant deux types de threads :

un thread "lecteur" est un thread qui ne fait que consulter l'état de la donnée
un thread "écrivain" est un thread qui modifie l'état de la donnée.

Le problème de synchronisation est ici défini par les contraintes suivantes :

à tout moment, il peut y avoir plusieurs threads lecteurs utilisant la donnée partagée (ils n'entrent pas en conflit)
à tout moment, il ne peut y avoir qu'un seul thread écrivain utilisant la donnée partagée, et ce thread y dispose d'un accès exclusif (c'est-à-dire qu'il n'admet ni un autre écrivain, ni un autre lecteur).

Tel qu'il est défini, ce système peut se trouver dans une situation dite "de famine". En effet, imaginons qu'il y ait beaucoup de threads lecteurs, à un point tel qu'il y ait à tout moment au moins un thread lecteur utilisant la donnée partagée. Dans ce cas, un éventuel thread écrivain n'aura jamais accès à la donnée : il sera en situation de famine.

(Notez que dans certains cas particuliers la situation est symétrique. Si il y a "beaucoup" d'écrivains, les lecteurs risquent de rester à l'état de famine. Toutefois, si l'attribution des accès est équitable, cela ne devrait pas arriver.)

Nous allons ici choisir de régler ce problème en énoncant une règle de priorité :

à partir du moment où un écrivain a demandé un accès exclusif à la donnée globale (même si il ne peut pas l'obtenir immédiatement pour cause de présence de lecteurs), aucun lecteur ne peut obtenir d'accès à la donnée jusqu'à ce que l'écrivain ait terminé son accès.

Pour comprendre l'influence de cette règle, examinons un exemple impliquant 3 threads, deux lecteurs L1 et L2 et un écrivain E1, dans la séquence suivante :

L1 demande l'accès à la donnée : accordé
E1 demande l'accès à la donnée : bloqué
L2 demande l'accès à la donnée

Dans ce cas, la règle de priorité modifie le comportement global. En effet :

sans la règle de priorité, L2 obtient son accès, et "dépasse" E1, qui risque la famine
avec la règle de priorité, L2 est bloqué, et E1 obtiendra l'accès lorsque L1 aura terminé le sien ; L2 quant à lui obtiendra l'accès après que E1 aura fini le sien.

   (Tout ceci suppose qu'il n'y a pas d'autre demande d'accès entre temps.)

   Completez le squelette de programme 'LecteurEcrivain.java' pour qu'il ait les fonctionnalités décrites ci-dessus.

Exercice 4

    Rendez-vous dans le répertoire 'Tri'.

Paralleliser l'algorithme de Tri du fichier 'Tri.java' en utilisant les threads. Avec des mesures de temps sur une grande liste d'entiers, vous montrerez que votre solution est efficace sur une machine multiprocesseur. Pour cela vous utiliserez 'turing' (quadri pro) comme machine finale de test.

[Page réalisée à partir d'un document de Guillaume Latu]