On voudrait réaliser en Java, un algorithme distribué de tri fusion afin d’en améliorer les
performances. Pour rappel, utiliser l’algorithme de tri fusion pour ordonner un ensemble E
d’éléments, c’est diviser (lorsque c’est possible) E en deux parties, trier chacune des parties
séparément (en utilisant le même algorithme), puis fusionner les résultats convenablement.
Puisque les tris des deux parties de E se font indépendamment l’un de l’autre, on peut les
réaliser en parallèle. On suppose qu’on dispose de la solution sur un poste basée sur la
notion de Thread suivante :
Une instance de la classe TriFusion (ci-dessus) est destinée à trier la portion du vecteur array
dont le premier élément a pour indice start et le dernier a pour indice end. Les constructeurs
de TriFusion doivent initialiser tous ses attributs. La méthode divide, divise la portion à
trier en deux, et retourne l’indice de l’élément se trouvant au centre de cette portion. La
méthode merge fusionne les deux parties de la portion à trier (supposées triée) en
conservant l’ordre des éléments : c'est-à-dire que le résultat est trié. La méthode run réalise
le tri fusion de la portion à trier.
Exercice 1 : Une solution multipostes basée sur la technologie Socket (9pts)
On désire à présent apporter une solution véritablement distribuée au problème précédent.
Pour ce faire, on décide de construire une application client-serveur grâce à la technologie
Socket. Notre application doit fonctionner de la manière suivante :
- Notre réseau est constitué de deux clients connectés à un serveur.
- Lorsqu’un client désire effectuer le tri d’un ensemble E, il sérialise E puis l’envoie au
serveur ;
- Lorsque le serveur reçoit le message émit par le client, il le desérialise, construit une
nouvelle tâche et la stocke dans une file de tâches qu’il tient à jour. Ensuite, il divise
l’ensemble E en deux parties qu’il sérialise et distribue à ses clients.
- A la réception d’une partie à trier, le client utilise la classe TriFusion écrite
précédemment pour la trier puis, renvoie l’ensemble trié au serveur.
- Lorsqu’une partie triée est reçue par le serveur, ce dernier identifie la tâche
correspondante dans sa file des tâches et y stocke ladite partie. Si toutes les parties triées
ont été reçues, le serveur les fusionne, sérialise le résultat et l’envoie au client ayant initié
la tâche.
On a donc besoin d’une classe Serializer disposant de deux méthodes de classe serialize et
deserialize permettant de transformer un tableau d’entiers en une chaine de caractère ([1,2,-
5,6] en "1_2_-5_6" par exemple) et vice versa. Cette classe sera présente sur le serveur et sur
le client.
« Je crois que l’avenir de l’humanité est dans le progrès de la raison par la science. » Emile ZOLA Page 1 sur 4
On a aussi besoin d’une classe ServeurTriFusion dont une partie du code est le suivant :
public class ServeurTriFusion {
private ServerSocket serverSocket;
private Service servClient1, servClient2;
private ArrayList<Task> tasks;
public ServeurTriFusion(int port){[Link](port);}
private void connexion(int port);
public void tri(int[] tab, int sender);
public void merge(int[] tab){
int[] sorted = [Link](0).addSortedPart(tab);
if(sorted != null){
String message = [Link](sorted, 0, [Link]);
Task task = [Link](0);
if([Link]() == 1) [Link]("Info>" + message);
else [Link]("Info>" + message);
}
}
public class Service extends Thread{
private Socket socket;
private BufferedReader entree;
private PrintWriter sortie;
private int sid;
public Service(Socket socket, int sid){
[Link] = sid;
[Link] = socket;
try {
entree = new BufferedReader(new
InputStreamReader([Link]()));
sortie = new PrintWriter([Link]());
} catch (IOException ex) {}
}
public void send(String message){
try {
[Link](message);
[Link]();
} catch (Exception ex) {}
}
@Override
public void run() {
while(true){
try {
String message = [Link]();
String[] cmds = [Link](">");
if(cmds[0].equals("Sort")){
[Link]("Task -> Sort " + cmds[1]);
int[] toSort = [Link](cmds[1]);
tri(toSort, sid);
}
if(cmds[0].equals("Sorted")){
[Link]("Info -> Sorted " + cmds[1]);
int[] sorted = [Link](cmds[1]);
merge(sorted);
}
} catch (Exception ex) {}
try{
[Link](100);
}catch(Exception e){}
}
}
}
public class Task{
private int sender;
private int[] toSort;
private ArrayList<int[]> sortedParts;
public Task(int sender, int[] toSort){
[Link] = sender;
[Link] = toSort;
sortedParts = new ArrayList<int[]>();
}
synchronized public int[] addSortedPart(int[] sortedPart){
if([Link]()){
[Link](sortedPart);
return null;
« Je crois que l’avenir de l’humanité est dans le progrès de la raison par la science. » Emile ZOLA Page 2 sur 4
}else{
int[] t1 = [Link](0);
int[] t2 = sortedPart;
return fusion(t1, t2);
}
}
public int getSender() {
return sender;
}
private int[] fusion(int[] t1, int[] t2) ;
}
Cette classe possède deux classes internes. L’une (Service) représente le service offert aux
clients tandis que l’autre (Task) représente une tâche de tri adressée au serveur par un client
donné. La méthode connexion (non implémentée ici) est celle qui permettra au serveur
d’établir la connexion avec exactement 2 clients puis de démarrer les services associés à ces
derniers. On supposera que le client qui se connecte en position k a pour sid le nombre k.
L’autre méthode non implémentée (tri) est celle qui est appelée lorsqu’un client initie une
nouvelle tâche. Celle-ci stocke donc la tâche dans la file des tâches puis divise le vecteur à
trier en deux et envoie chaque partie à un client donné pour tri. Pour terminer, nous aurons
besoin de la classe ClientTriFusion dont le diagramme UML est le suivant.
Le constructeur établit une connexion
(grâce à la méthode connexion) avec le
serveur puis démarre le Thread courant.
La méthode connexion établit une
connexion de type Socket avec le serveur
puis initialise l’entrée et la sortie. La
méthode tri est appelée pour initier une
nouvelle tâche de tri. Enfin, le client
récupère les messages qui lui sont
destinés dans la méthode run puis il agit en conséquence.
1- Proposer une implémentation de la classe Serializer sachant que la méthode serialize
prendra en paramètre deux nombres entiers en plus, représentant la portion à sérialiser
(i.e [Link]([8,5,6,9,2], 1, 4)="5_6_9"). 2pts
2- Proposer une implémentation de la méthode connexion du serveur. 1pt
3- Proposer une implémentation de la méthode tri du serveur. 1pt
4- Proposer une implémentation de la classe ClientTriFusion qui fonctionne parfaitement
avec le serveur présenté ici. 3.5pts
5- Proposer deux méthodes (une pour le serveur et une pour le client) main qui pourraient
nous aider à tester notre programme distribué. 1.5pts
Exercice 2 : Une solution multipostes basée sur la technologie RMI (11pts)
1- Expliquez brièvement pourquoi il n’est pas possible de construire le système décrit ici
grâce à la technologie RMI en mode client-serveur. 1pt
On décide alors de construire une solution en mode pair-à-pair. Pour simplifier, on
considère que le réseau est réduit à trois machines. Un pair est une instance de la classe
PairTri décrite comme suit :
- Elle implémente l’interface PairTriInterface qui contient le prototype des méthodes
susceptibles d’être invoquées à distance ;
« Je crois que l’avenir de l’humanité est dans le progrès de la raison par la science. » Emile ZOLA Page 3 sur 4
- Elle possède deux attributs addr_1 et addr_2 de type InetAddress qui représentent les
informations réseau sur les deux autres pairs ;
- Une méthode locale lookup qui prend en paramètre un objet de type InetAddress et
retourne un objet de type PairTriInterface représentant un objet distribué dont l’URL est
rmi://ip_addr:1001/pair_tri (dans laquelle ip_addr est l’adresse IP contenu dans l’objet pris
en paramètre).
- Une méthode triLocal pouvant être invoquée à distance et qui prend un tableau d’entiers
en paramètre, le trie grâce à la classe TriFusion définie dans le prélude de cet exercice
puis retourne le résultat ;
- Une méthode triDistant pouvant être invoquée à distance et qui prend un tableau
d’entiers en paramètre, le divise en deux tableaux d’entiers distincts, invoque les
méthodes triLocal des deux autres pairs avec une partie du tableau à chaque fois, puis
fusionne les résultats obtenus en un tableau qu’elle retourne ;
- Une méthode locale tri qui prend un tableau d’entiers en paramètre et invoque la
méthode triDistant du pair d’adresse addr_1.
2- Proposer le code de l’interface PairTriInterface. 1.5pts
3- Déclarer la classe PairTri (se limiter au prototype des différentes méthodes) 1.5pts
4- Donner le code de la méthode lookup. 1.5pts
5- Donner le code de la méthode triDistant. 2pts
6- Donner le code de la méthode triLocal. 1.5pts
7- Proposer un code pour la méthode tri de la classe PairTri. 1pt
8- Vos codes améliorent-ils le temps d’exécution du tri fusion ? Justifier votre réponse. 1pt
Une bonne présentation de la copie est conseillée !
Bon courage !!!
« Je crois que l’avenir de l’humanité est dans le progrès de la raison par la science. » Emile ZOLA Page 4 sur 4
