Tri pair-impair

On suppose que l'on dispose d'un réseau linéaire de p processeurs P1,...,Pp, c'est à dire que les processeurs sont organisés sur une ligne, et que chacun peut communiquer avec son voisin de gauche et son voisin de droite s'il en a un. On veut trier n entiers, avec p qui divise n. Chaque processeur a au départ n/p entiers, et on veut trouver un algorithme parallèle qui permette de faire en sorte que la sous-suite sur P_i soit ordonnée et inférieure à la sous-suite ordonnée P_j, pour tout i<j. C'est à dire tout simplement que l'on veut trier en parallèle les données réparties sur les processeurs P_i.

En s'inspirant du réseau de tri pair-impair vu en cours, écrire un tel algorithme en JAVA. Pour ce faire, on utilisera la classe Buffer suivante, pour coder les échanges de données entre chaque processus, chacun implémentant un comparateur du réseau de tri.

class Buffer {
    int val;
    Buffer() { val = -1; } 

    synchronized void write(int v) {
        while (val!=-1) {
            try { wait(); } catch (InterruptedException e) {};
        }; 
        val = v;
        notifyAll();
    }

    synchronized int read() {
        while (val==-1) {
            try { wait(); } catch (InterruptedException e) {};
        }; 
        int n = val;
        val = -1;
        notifyAll();
        return n;
    }
}

Ordonnanceur à tourniquet (exo facultatif)

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, qui fournit une implémentation de liste circulaire, avec les méthodes:

• public synchronized void insert(Object o) d'insertion d'un objet dans la file,
• public synchronized void delete(Object o) qui efface l'objet de la liste,
• public synchronized Object getNext() qui prend l'élément suivant dans la file.

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?