:: Enseignements :: ESIPE :: E4INFO :: 2016-2017 :: Concurrence ::

Examen de Concurrence - Deuxième Session

Vos sources Java produites pendant le TP devront être placées sous le répertoire EXAM de votre compte ($HOME) (qui est vierge dans l'environnement de TP noté); sinon, elles ne seront pas récupérées.

Tout document papier est proscrit. Vous pouvez consulter la javadoc à travers Eclipse (onglet Javadoc) ou en lançant la commande jdoc dans un shell. Les seuls documents électroniques autorisés sont les supports de cours à l'url http://igm.univ-mlv.fr/~forax/ens/java-avance/cours/pdf/.

Les deux exercices sont complètement indépendants et peuvent être traités dans n'importe quel ordre.

Exercice 1 - Réservation de sièges

Le but de cet exercice est d'implanter une classe SeatReservation qui permet de réserver des sièges pour un évènement. Les sièges sont représentés par un tableau de chaînes de caractères: lorsque l'on réserve un siège, on parcourt le tableau en cherchant un emplacement vide (je sais l'algo est stupide mais on va dire que l'on a pas le droit de le changer) et on marque celui-ci comme réservé en stockant le symbole (la chaîne) de celui qui a réservé le siège dans le tableau.
La classe SeatReservation possède une méthode tryToReserve(int seatCount, String symbol) qui essaye de réserver seatCount sièges en les marquant avec le symbole symbol/. La méthode renvoie le nombre de sièges qui ont pu être effectivement reservés (une valeur entre 0 dans le cas où il n'y a plus de siège disponible et seatCount si tous les sièges demandés ont pu être réservés).
Un de vos collègues, Kenny, a déjà écrit un prototype de la classe malheureusement, Oh mon Dieu !, Ils ont tué Kenny, avant que celui-ci ait pu terminer le code.

Compléter le code du main pour créer 10 threads qui exécutent chacune le code indiqué.
Puis exécuter le code plusieurs fois et persuadez-vous que le comportement est normal.
Modifier le code pour que la classe SeatReservation soit thread-safe en utilisant le mécanisme de verrou ré-entrant; dans cette question, on veut seulement qu'une thread ayant débuté un ensemble de réservations les termine avant qu'une autre ne puisse commencer les siennes.
Vérifier en exécutant plusieurs fois le code du main.
Dupliquer le code dans une classe SeatReservationBis, et modifiez-la pour qu'elle soit toujours thread-safe mais autorise le fait que deux threads puissent faire des parties de leur réservation chacune leur tour (exemple, t1 réserve 2 places, puis t2 réserve 1 place, puis t1 réserve 1 place et retourne avant que t2 réserve 3 places et retourne); cette version utilisera encore le mécanisme de verrou ré-entrant.
Vérifier en exécutant plusieurs fois le code du main.
Dupliquer le code de la classe SeatReservationBis dans une classe SeatReservationTer et rendre le code thread-safe en utilisant cette fois si un CompareAndSet.
Indication: il va falloir utiliser une classe du package java.util.concurrent.atomic.

Exercice 2 - SleepSort

On souhaite implanter un algorithme de tri appelé le sleep-sort. L'idée est la suivante: si pour chaque valeur entière positive d'un tableau, on démarre une thread qui attend le temps correspondant à la valeur puis affiche la valeur, alors les valeurs seront affichées dans un ordre croissant.

Ecrire dans une classe SleepSort une méthode sleepSort(int[] array) qui prend en paramètre un tableau d'entiers et affiche ceux-ci en utilisant le sleep-sort et tester avec le tableau suivant int[] array = { 32, 55, 17, 3 };.
Tester avec le tableau int[] array = { 5, 4, 3, 2, 1 };; que peut-on voir ? Si vous ne voyez pas, essayez plusieurs fois.
Pour corriger le problème, on peut se dire qu'une thread peut avoir fini alors qu'une thread n'a pas encore commencée. Pour éviter ce problème, écrire une méthode sleepSort2 utilisant un CountDownLatch pour n'exécuter le code des threads qu'une fois qu'elles ont toutes démarrées.
En fait, en testant, on voit que cela ne corrige pas le problème, c'est peut-être du à l'implantation de CountDownLatch, écrire une méthode sleepSort3 qui utilise une CyclicBarrier.
En fait, en testant, on voit que cela ne corrige pas le problème, c'est peut-être du à l'implantation de CyclicBarrier, vous allez donc essayer une nouvelle implantation qui utilise un ThreadPoolExecutor, en effet, un ThreadPoolExecutor possède une méthode prestartAllCoreThreads qui permet de démarrer toutes les threads avant d'exécuter du code.
Ecrire une méthode sleepSort4 qui utilise un ThreadPoolExecutor.
En fait, en testant, on voit que cela ne corrige toujours pas le problème, le problème vient du fait que sur les OS non temps réel, Thread.sleep() peut attendre plus longtemps que le temps que l'on demande, donc on ne peut pas écrire de sleep-sort qui marche sur les OS de vos machines habituelles.
Pour finir, écrire une méthode sleepSort5 qui prend en paramètre un tableau et renvoie un nouveau tableau sensé être trié par le sleep-sort puis modifier le main pour faire une boucle infinie autour de sleepSort5 qui détecte si le tableau renvoyé n'est pas trié et s'arrète das ce cas.
Rappel: en Java, Arrays.equals permet de comparer des tableaux.