L'examen est composé de 3 exercices indépendants qui peuvent être traités dans l'ordre que vous voulez.
Rappel : si ce n'est pas déjà fait, vous devez configurer le workspace d'Eclipse (File > Switch WorkSpace) pour qu'il corresponde au répertoire EXAM présent dans le home de votre session de TP noté.
Vérifier que tous vos fichiers sont bien dans le répertoire EXAM. Tout ce qui n'est pas dans ce répertoire est perdu quand vous vous déconnectez.
La javadoc 23 est là : https://igm.univ-mlv.fr/~juge/javadoc-23/.
Vous avez le droit de consulter les transparents du cours pendant l'examen.
Cet exercice comporte 5 questions.
Dans cet exercice, on se propose de créer une classe TheLastOfUs permettant à plusieurs threads de participer à une compétition par équipes. Les threads vont marquer un nombre de points proportionnel à leur ordre d'arrivée et la meilleure équipe sera celle qui obtiendra le moins de points.
Bien entendu, dans tout l'exercice la (ou les) classe(s) que vous écrirez doivent être thread-safe.
La classe TheLastOfUs.java fournie contient un constructeur qui prend en paramètre le nombre d'équipes et le nombre de co-équipiers par équipe. Chaque équipe est désignée par un numéro. Lorsqu'un thread veut participer à la compétition, on va lui attribuer un numéro d'équipe et il est bloqué jusqu'à ce que toutes les équipes soient au complet.
TheLastOfUs possède les champs suivants :
private final int numberOfteams; le nombre d'équipes.
private final int teamSize; le nombre de co-équipiers par équipe.
private final ArrayDeque numbers; une file contenant à tout instant les numéros d'équipe encore disponibles pour être attribués aux threads. Le constructeur la remplit avec teamSize fois les numéros de 0 à numberOfteams-1 au début. numberOfteams vaut 2) et que chaque équipe contient 3 co-équipiers (teamSize vaut 3), le constructeur remplit numbers avec [0, 0, 0, 1, 1, 1]. Il suffira au thread de retirer le premier élément de la file pour obtenir son numéro d'équipe.
private final HashMap<Thread, Integer> numbersByThread; c'est la structure de données qui va vous permettre de conserver le numéro de l'équipe dans laquelle se trouve chaque thread.
public record Score(int team, String names, int score) {}; un record qui permet de stocker un numéro d'équipe, une chaîne représentant les noms des co-équipiers (pour l'affichage) et le score de l'équipe.
private List<Thread> team(int number) pour obtenir les threads d'une équipe à partir du numéro d'équipe.
private List<String> teamNames(int number) pour obtenir les noms des threads d'une équipe à partir du numéro d'équipe.
TheLastOfUs possédera également les méthodes suivantes (qui seront écrites au fur et à mesure des questions).
int getNumber() elle permet à un thread de récupérer son numéro d'équipe pour participer à la compétition. Cette méthode bloque jusqu'à ce que toutes les équipes soient complètes. Si c'est déjà le cas quand un thread l'appelle, elle lève une IllegalStateException. En interne, elle met à jour le champ numbersByThread. Elle utilise le champs numbers pour savoir quelles équipes sont encore disponibles.
Map<Thread, Integer> numbersByThread() elle permet d'obtenir les threads déjà présents avec leur numéro d'équipe.
List<Score> participate() elle permet de participer à la compétition (pour les threads déjà ayant un numéro d'équipe) et renvoie les scores des équipes qui ont déjà fini. On expliquera plus tard comment sont calculés les scores.
Implanter la classe thread-safe TheLastOfUs décrite précédemment avec ses méthodes getNumber et numbersByThread, en utilisant des blocs synchronized. Vous les utiliserez pour tout cet exercice.
Pour tester votre code, nous vous fournissons un main dans la classe TheLastOfUsTest.java qui crée un objet TheLastOfUs pour 4 équipes de 3 et démarre 30 threads qui essaient d'y participer (avec un délai aléatoire). S'il n'y a plus de place, le code affiche que le thread est "late for the party" et sinon, le thread affiche son numéro d'équipe et la composition des équipes.
Voici un exemple d’exécution possible :
T-8 asks for his number T-4 asks for his number T-1 asks for his number T-10 asks for his number T-12 asks for his number T-15 asks for his number T-0 asks for his number T-11 asks for his number T-2 asks for his number T-7 asks for his number T-3 asks for his number T-14 asks for his number T-14 got 3, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-4 got 0, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-7 got 3, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-0 got 2, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-8 got 0, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-11 got 2, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-15 got 1, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-10 got 1, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-12 got 1, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-3 got 3, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-2 got 2, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-1 got 0, teams are [T-4=0, T-12=1, T-1=0, T-10=1, T-2=2, T-11=2, T-7=3, T-0=2, T-15=1, T-3=3, T-8=0, T-14=3] T-5 asks for his number Warning: T-5 is late for the party T-9 asks for his number Warning: T-9 is late for the party T-6 asks for his number Warning: T-6 is late for the party T-13 asks for his number Warning: T-13 is late for the party T-16 asks for his number Warning: T-16 is late for the party
Après avoir recopié votre classe TheLastOfUs dans une classe TheLastOfUsQ2, modifier votre code pour que si un thread est interrompu lorsqu'il est en attente dans getNumber, alors la méthode lance une InterruptedException pour le thread en question et tous ses co-équipiers, mais pas pour les autres threads. Les numéros qu'on avait attribués aux threads ainsi interrompus redeviennent disponibles.
Pour tester, vous pouvez modifier le code du main pour que le premier soit interrompu au bout de 1_000 millisecondes. Dans certains cas, ça ne changera rien et dans d'autres, ses co-équipiers seront interrompus également. Faites en sorte que les thread s'arrêtent proprement.
Si vous n'arrivez pas à faire cette question, vous pouvez passer à la suite.
Après avoir recopié votre classe TheLastOfUs (de la première question) dans une classe TheLastOfUsQ3, on va ajouter la méthode List<Score> participate(). Elle permet de participer à la compétition et renvoie les scores de équipes qui ont déjà fini. Si le thread qui l'appelle n'a pas de numéro, elle lève une IllegalStateException.
Cette méthode attribue des points aux threads dans leur ordre d'arrivée : 1 point pour le premier, 2 pour le second et ainsi de suite... Lorsqu'un thread appelle cette méthode, il est bloqué jusqu'à ce qu'un autre thread l'appelle. Le premier thread est relâché et c'est ce nouveau thread qui est bloqué. Attention, le dernier thread ne doit pas rester bloqué. On ne vous demande pas de gérer le cas où un thread appellerait la méthode plusieurs fois.
Lorsqu'un thread est relâché il renvoie la liste des scores des équipes qui ont déjà fini (tous leurs threads on terminé), dans l'ordre croissant de leur score.
Conseil : utiliser une Map pour associer à un numéro d'équipe la liste des points marqués. Ça permet de savoir si tout les co-équipiers ont fini et de calculer le score facilement.
Et ce code permet d'ordonner une liste de scores :
scores.stream().sorted(Comparator.comparingInt(Score::score)).toList()
Pour tester, vous pouvez compléter votre main en ajoutant le code suivant dans le Runnable de chaque thread :
... time = ThreadLocalRandom.current().nextInt(500, 3500); Thread.sleep(time); var finish = waitTillTheLast.participate(); System.out.println(name + " participates " + finish);
Voici un exemple d’exécution possible :
T-9 asks for his number T-6 asks for his number T-4 asks for his number T-3 asks for his number T-7 asks for his number T-12 asks for his number T-15 asks for his number T-1 asks for his number T-0 asks for his number T-16 asks for his number T-5 asks for his number T-8 asks for his number T-1 got 2, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-15 got 2, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-8 got 3, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-3 got 1, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-0 got 2, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-5 got 3, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-12 got 1, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-16 got 3, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-4 got 0, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-9 got 0, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-6 got 0, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-7 got 1, teams are [T-1=2, T-6=0, T-7=1, T-16=3, T-15=2, T-0=2, T-12=1, T-8=3, T-3=1, T-5=3, T-4=0, T-9=0] T-10 asks for his number Waring: T-10 is late for the party T-11 asks for his number Waring: T-11 is late for the party T-2 asks for his number Waring: T-2 is late for the party T-13 asks for his number Waring: T-13 is late for the party T-14 asks for his number Waring: T-14 is late for the party T-0 participates [] T-6 participates [] T-1 participates [] T-16 participates [] T-8 participates [] T-3 participates [] T-4 participates [Score[team=0, names=[T-6, T-9, T-4], score=17]] T-9 participates [Score[team=2, names=[T-0, T-15, T-1], score=13], Score[team=0, names=[T-6, T-9, T-4], score=17]] T-15 participates [Score[team=2, names=[T-0, T-15, T-1], score=13], Score[team=0, names=[T-6, T-9, T-4], score=17]] T-7 participates [Score[team=2, names=[T-0, T-15, T-1], score=13], Score[team=0, names=[T-6, T-9, T-4], score=17], Score[team=1, names=[T-3, T-12, T-7], score=27]] T-12 participates [Score[team=2, names=[T-0, T-15, T-1], score=13], Score[team=0, names=[T-6, T-9, T-4], score=17], Score[team=3, names=[T-16, T-5, T-8], score=21], Score[team=1, names=[T-3, T-12, T-7], score=27]]
Comme on peut le voir sur l'exemple précédent, tant que tous le monde n'a pas fini, le classement des équipes peut changer. Pour éviter d'avoir un classement partiel faux,
après avoir recopié votre code précédent dans une classe TheLastOfUsQ4, on va modifier le comportement de la méthode participate. Désormais, quand le dernier thread d'une équipe arrive, il doit resté bloqué jusqu'à ce que la compétition soit finie. Et seulement à ce moment là, la méthode renvoie la liste des scores dans l'ordre. Si un thread n'est pas le dernier de son équipe, il va être débloqué par le prochain participant et dans ce cas il renverra une liste vide. Tous les autres threads renvoient la même liste qui est le classement final.
Faites la modification demandée.
Voici un exemple d’exécution possible :
T-4 asks for his number
T-16 asks for his number
T-14 asks for his number
T-1 asks for his number
T-9 asks for his number
T-13 asks for his number
T-2 asks for his number
T-12 asks for his number
T-11 asks for his number
T-15 asks for his number
T-7 asks for his number
T-10 asks for his number
T-5 asks for his number
T-9 got 1, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-10 got 3, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-11 got 2, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-14 got 0, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-15 got 3, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-12 got 2, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-4 got 0, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-7 got 3, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-16 got 0, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-1 got 1, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-13 got 1, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
T-2 got 2, teams are [T-11=2, T-2=2, T-16=0, T-9=1, T-13=1, T-12=2, T-10=3, T-4=0, T-7=3, T-14=0, T-15=3, T-1=1]
Warning: T-5 is late for the party
T-6 asks for his number
Warning: T-6 is late for the party
T-0 asks for his number
Warning: T-0 is late for the party
T-8 asks for his number
Warning: T-8 is late for the party
T-3 asks for his number
Warning: T-3 is late for the party
T-1 participates, team not complete
T-12 participates, team not complete
T-14 participates, team not complete
T-11 participates, team not complete
T-9 participates, team not complete
T-4 participates, team not complete
T-15 participates, team not complete
T-7 participates, team not complete
T-2 participates, [Score[team=2, names=[T-11, T-2, T-12], score=12], Score[team=1, names=[T-13, T-9, T-1], score=14], Score[team=0, names=[T-4, T-16, T-14], score=20], Score[team=3, names=[T-15, T-7, T-10], score=32]]
T-10 participates, [Score[team=2, names=[T-11, T-2, T-12], score=12], Score[team=1, names=[T-13, T-9, T-1], score=14], Score[team=0, names=[T-4, T-16, T-14], score=20], Score[team=3, names=[T-15, T-7, T-10], score=32]]
T-13 participates, [Score[team=2, names=[T-11, T-2, T-12], score=12], Score[team=1, names=[T-13, T-9, T-1], score=14], Score[team=0, names=[T-4, T-16, T-14], score=20], Score[team=3, names=[T-15, T-7, T-10], score=32]]
T-16 participates, [Score[team=2, names=[T-11, T-2, T-12], score=12], Score[team=1, names=[T-13, T-9, T-1], score=14], Score[team=0, names=[T-4, T-16, T-14], score=20], Score[team=3, names=[T-15, T-7, T-10], score=32]]
Bonus
Recopier votre code précédent dans une classe TheLastOfUsQ5, et modifier le comportement de la méthode participate pour gérer les cas où un thread en attente dans la méthode est interrompu.
Soit c'est un thread qui est le dernier de sont équipe et la méthode lance une simple une InterruptedException. Soit le thread appartient à une équipe qui n'a pas fini et tous les threads (de toutes les équipes) encore en attente sont interrompus (la méthode lance une InterruptedException pour eux aussi).
Dans cet exercice, on vous fournit une petite API factice Loto.java qui simule un système permettant d'acheter des jeux à gratter, de les gratter et de recevoir les gains correspondants.
Dans cet exercice, vous devez utiliser le pattern producteur-consommateur et toute autre forme de synchronisation sera considérée comme hors-sujet.
Un ticket non-gratté UnscratchedTicket possède un identifiant unique (id). La méthode UnscratchedTicket Loto.buy() permet d'acheter un ticket non-gratté. La méthode Ticket Loto.scratch(UnscratchedTicket unscratchedTicket) permet de gratter un ticket non-gratté et de recevoir le Ticket correspondant. Un Ticket contient un identifiant unique (id) et un gain (winnings).
La méthode int Loto.cashOut(List<Ticket> tickets) permet d'encaisser un nombre quelconque de tickets et de percevoir le gain total.
Le code suivant permet d'acheter un ticket non-gratté, de le gratter et de percevoir le gain si c'est un ticket gagnant :
public static void main(String[] args) throws InterruptedException {
UnscratchedTicket unscratchedTicket = Loto.buy();
Ticket ticket = Loto.scratch(unscratchedTicket);
if (ticket.winnings > 0) {
int gain = Loto.cashOut(List.of(ticket));
System.out.println("Gain : " + gain);
} else {
System.out.println("Ticket non gagnant");
}
}
En résumé, l'API Loto définit deux records UnscratchedTicket(long id) et Ticket(long id, int winnings) et trois méthodes statiques :
UnscratchedTicket Loto.buy() simule l'achat d'un ticket non-gratté,Ticket Loto.scratch(UnscratchedTicket unscratchedTicket) simule le grattage d'un ticket non-gratté et de recevoir le Ticket correspondant,int Loto.cashOut(List<Ticket> tickets) permet d'encaisser un nombre quelconque de tickets et de percevoir le gain total.Dans cet exercice, vous devez utiliser un producteur-consommateur dans le main d'une classe Application pour faire communiquer les threads suivants :
Loto.cashOut) individuellement les tickets gagnants de plus de 1000€.Tous les threads doivent afficher leurs actions de manière à obtenir un affichage semblable à celui donné ci-dessous :
Buyer 0 bought ticket 6230334469895862563
Buyer 1 bought ticket 7034992451699452248
Buyer 2 bought ticket 2834602399081465197
Buyer 1 bought ticket 6725390245171931389
Buyer 2 bought ticket 6294496788461333930
Buyer 0 bought ticket 5091053054577280093
High-value cashier 1 cashed out ticket 6766604967769256457 for 1741€
Scratcher 1 scratched ticket 4988541897350285537 (winnings: 0€)
Scratcher 0 scratched ticket 274056399543571770 (winnings: 0€)
Buyer 2 bought ticket 4569239964647772489
Buyer 1 bought ticket 3996208870647215347
Buyer 0 bought ticket 3542428410107182027
Buyer 2 bought ticket 8839186517321274328
Buyer 1 bought ticket 9222895136996824478
Buyer 0 bought ticket 2096711829013788634
Scratcher 1 scratched ticket 3421986219118201247 (winnings: 995€)
Scratcher 0 scratched ticket 4435354418528063640 (winnings: 0€)
Buyer 1 bought ticket 8963613502976412350
Buyer 2 bought ticket 9116712151417597651
Buyer 0 bought ticket 6290152877137165501
Buyer 1 bought ticket 7965145801116948257
Buyer 2 bought ticket 5392780764633993952
Buyer 0 bought ticket 6867440969681835175
Low-value cashier 0 cashed out 2 tickets for 1588€
Scratcher 1 scratched ticket 6056876699124827347 (winnings: 8739€)
Écrire la classe Application demandée.
Dans cet exercice, on cherche à créer une classe Fighter thread-safe qui maintient les informations d'un combattant dans un jeu vidéo. Le combattant est construit à partir d'un nom (name), un niveau (level) et un nombre de points de magie (magicPoints).
Cette classe possède trois méthodes :
attack() qui consomme 1 point de magie si le combattant a entre 1 et 10 points de magie et qui consomme 2 points de magie si le combattant a plus de 10 points de magie.
Si le combattant n'a pas assez de points de magie, la méthode ne fait rien.
sleep() qui rajoute 10 points de magie si le combattant a un niveau inférieur à 100 et qui rajoute 20 points de magie si son niveau est au moins 100.toString() qui permet d'afficher les informations du combattant au format suivant : Arnaud 100 (level) 10 (magicPoints). Donner une implémentation thread-safe dans une classe Fighter qui n'utilise ni section critique, ni verrou, en utilisant le système de VarHandle et la méthode compareAndSet.
Vous pouvez utiliser le code suivant pour tester votre implémentation :
public static void main(String[] args) {
Fighter arnaud = new Fighter("Arnaud", 200, 5);
Thread.ofPlatform().start(() -> {
for (;;) {
arnaud.attack();
System.out.println("After attack: " + arnaud);
try {
Thread.sleep(500);
} catch (InterruptedException e) {
throw new AssertionError(e);
}
}
});
Thread.ofPlatform().start(() -> {
for (;;) {
arnaud.sleep();
System.out.println("After sleep: " + arnaud);
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
throw new AssertionError(e);
}
}
});
}
On veut maintenant rajouter des points d'expérience (experience) au combattant. Initialement, le combattant a 0 point d'expérience. Chaque fois que le combattant attaque, il gagne 1 point d'expérience. Chaque fois que le combattant dort, il gagne 10 point d'expérience. La méthode toString() doit maintenant afficher les informations du combattant au format suivant : Arnaud 100 (level) 10 (magicPoints) 0 (experience).
Donner une implémentation thread-safe dans une classe FighterExperience qui n'utilise ni section critique, ni verrou, en utilisant le système de VarHandle.