Le code à compléter pour ce TP se trouve ici

Exercice 1 : exclusion k-mutuelle

On se fixe un entier k>0. Le problème de l’exclusion k-mutuelle consiste à permettre jusqu’à k threads de se retrouver simultanément en section critique, mais jamais plus. Pour rendre les choses plus concrètes, on prend l’exemple d’un parking disposant de k places. Chaque thread peut demander une place pour se garer. Quand une place lui est accordée, il dispose de cette place exclusivement. Il doit ensuite la libérer explicitement pour qu’un autre thread puisse s’y garer après lui. On suppose que les places sont numérotées de 1 à k. Il s’agit donc d’implémenter l’interface suivante

interface Parking {
    int get_free_place();
    void leave_place();
}

Question 1.1

Complétez le fichier ParkingBloquant.java pour donner une implémentation bloquante de l’interface Parking: un appel à get_free_place peut endormir le thread pour une durée indéterminée, et renvoie toujours une valeur comprise entre 1 et k. Un appel à leave_place par un thread qui n’est pas garé dans le parking est sans effet.

Votre implémentation devra satisfaire aux critères suivants:

• Exclusion k-mutuelle: chaque thread est seul sur sa place de parking

• Absence d’interblocage Si au moins un thread demande une place et que le parking n’est pas plein, au moins un thread obtient une place

• Absence de famine Un thread ne se fait pas doubler par d’autres threads infiniment souvent. Dit autrement, tout appel à get_free_place termine, même si infiniment souvent d’autres threads demandent une place, du moment qu’un thread qui a une place ne la garde jamais pour un temps infini.

Vous pourrez utiliser une approche par moniteur de Hoare (mot-clé synchronized, wait, notify). Pour identifier chaque thread (et ainsi retrouver quelle place a été attribuée à un thread qui appelle leave_place), vous pourrez utiliser Thread.currentThread().getId().

NOTE le programme TestExo1 est donné pour vous aider, il permet de vérifier que vous avez (probablement) bien satisfait au premier critère. Il ne vérifie pas que votre solution est sans interblocage ni famines. Ce programme teste aussi la question 1.2 ci-dessous.

Question 1.2

Complétez le fichier ParkingNonBloquant.java pour donner une implémentation non-bloquante de l’interface Parking: cette fois-ci, un appel à get_free_place ne peut pas endormir le thread; si aucune place n’est libre, la fonction renvoie 0. Vous pourrez utiliser une approche basée sur des instructions atomiques (entiers atomiques, compare and swap, etc)

Exercice 2 : Produit scalaire parallèle

Soit \(a=(a_1,\ldots,a_n)\) et \(b=(b_1,\ldots,b_n)\) deux vecteurs de dimension n. On rappelle que leur produit scalaire vaut \(\sum_{i=1}^n a_ib_i\).

Question 2

Complétez la fonction prodScal(int []a, int []b, int n, int nbThreads) du fichier Exo2.java de sorte à calculer le produit scalaire des deux vecteurs passés en paramètres, en parallèle avec nbThreads en équilibrant la charge au mieux, et en réduisant la synchronisation entre threads au minimum.