Le code à compléter pour ce TP se trouve ici
Votre mission: implémenter le verrou d’un gardien de parc. Des chiens et des chats peuvent demander à acquérir le verrou pour rentrer dans le parc, et le relâchent en sortant du parc. On suppose que tout animal qui rentre dans le parc finit par en sortir. Le nombre d’animaux est infini, il en arrive en continu. On veut garantir les propriétés suivantes:
Exclusion mutuelle Il n’y a qu’une seule sorte d’animaux dans le parc simultanément (chiens et chats ne se rencontrent jamais).
Absence d’interblocage Si au moins un animal demande le verrou et que le parc est vide, au moins un animal acquiert le verrou
Non exclusion Si les animaux qui demandent le verrou et ceux qui sont dans le parc sont de la même sorte, alors au moins un animal obtient le verrou.
Absence de famine Tout animal qui demande le verrou finit par l’avoir.
Implémentez un verrou qui garantit les trois premières propriétés, mais pas nécessairement l’absence de famine. Complétez le fichier SquareMutex.java et testez avec TestSquareMutex. Attention, le test permet de trouver des bugs, il ne garantit pas que votre réponse est juste. Lancez le test plusieurs fois pour vérifier que vous n’avez pas eu un coup de chance avec l’ordonnanceur.
Implémentez un verrou qui garantit les quatre propriétés. Complétez le fichier FairSquareMutex.java et testez avec TestFairSquareMutex. Vous pourrez utiliser ThreadId.get() pour générer un identifiant de thread si l’approche que vous adoptez vous conduit à en éprouver le besoin. On pourra aussi supposer que la gestion de l’attente sur une variable de condition se fait avec une file FIFO (cependant, si un thread est réveillé puis rendormi, il passe de la première à la dernière position de la file FIFO…) Une solution imparfaite rapportera des points, commentez votre code si vous avez identifié des limitations à votre solution.
Implémentez l’algorithme suivant de calcul en parallèle de la liste des nombres premiers. On se donne une liste concurrente mutable de nombres candidats pour être premiers. Au début il y a dans la liste les nombres 2,3,5,7,9,11,13,15,… (2 suivi des nombres impairs) jusqu’à un N impair fixé, en ordre croissant. Chaque nombre est dans l’un des deux états suivants: non assigné, ou assigné. Au début tous les nombres sont dans l’état non assigné. Chaque thread inactif se saisit du prochain nombre non assigné dans la liste et se l’assigne, puis parcourt la liste des candidat de 2 à \(\sqrt{n}\) à la recherche d’un éventuel diviseur de \(n\). S’il en trouve un, il retire \(n\) de la liste des candidats. Vous pourrez utiliser une ConcurrentLinkedQueue pour représenter la liste des candidats. Vous chercherez à écrire un code sans verrou (ni synchronized), uniquement avec des instructions atomiques.