Ecole Polytechnique






Cours : ``Parallélisme''
Travaux dirigés
E. Goubault & M. Martel

TD 4

4 février 2002




1  Points morts

2  Ordonnanceur à tourniquet

On cherche à implémenter un ordonnanceur à tourniquet pour les threads JAVA en JAVA.

L'idée est que l'on doit définir un thread ordonnanceur qui gère une file d'attente de threads ``utilisateurs'' JAVA et les ordonnancer un à un pour un quantum de temps élémentaire donné (une constante de votre programme). Cet ordonnanceur ne gèrera pas de notion de priorité.

Chaque thread utilisateur devra s'enregistrer auprès de l'ordonnanceur en appelant la méthode addThread() (à écrire). On pourra aussi écrire une méthode removeThread qui désinscrit un thread auprès de cet ordonnanceur. On utilisera la classe CircularList donnée sur la page web du cours, qui fournit une implémentation de liste circulaire, avec les méthodes: Avant de commencer, on répondra aux questions suivantes: quelle doit être la priorité du thread ordonnanceur? du thread utilisateur actif? des threads non encore actifs?

3  Barrières de synchronisation

Ecrire (avec wait et notify/notifyall) une classe Barrier qui implémente les barrière de synchronisation. Une barrière de synchronisation est un mécanisme qui permet d'attendre que n (quelconque, donné à la construction) processus s'attendent à un point donné de leur exécution, avant de tous repartir ensemble. On programmera:

4  Programmer l'algorithme de tri de Batcher

On associera un processus JAVA par comparateur.

5  Lecteurs/rédacteurs

On considère maintenant une base de données partagée accédée par des threads JAVA de deux types. L'un est le type lecteur, l'autre le type rédacteur.

Les lecteurs sont des threads qui par définition ne peuvent que lire (interroger) la base de données. Les rédacteurs par contre peuvent lire et écrire. On suppose que la lecture parallèle de la même location dans la base de données est autorisée, par contre l'écriture en parallèle avec soit une lecture soit une autre écriture sur la même location doit être effectuée en section critique (exclusion mutuelle).

On simulera (il ne sera pas nécessaire d'avoir une vraie donnée, une simple simulation des actions à l'écran suffit) le début de l'accès en lecture par la méthode (à écrire) startRead(), la fin par end Read(), le début de l'accès en écriture par startWrite() et la fin par endWrite().

On veut implémenter un tel système avec au moins la propriété suivante: aucun lecteur ne doit rester en attente sauf si un rédacteur a obtenu la permission d'utiliser la base de données. Peut-il y avoir des cas de famine?

On pourra également (optionnel) se poser la contrainte supplémentaire suivante: dès qu'un rédacteur est prêt, il doit effectuer son écriture ``aussi vite que possible''.

Remarque: on pourra soit utiliser la classe Semaphore du cours (combien en faut-il et de quel type alors?), soit directement les mots-clés JAVA wait() et notify().


This document was translated from LATEX by HEVEA.