Précédent Table des matières

5  Applications à des exemples concrets

L’objectif de cette section est de mettre en œuvre des threads sur quelques cas concrets. Vous trouverez sur le portail des canevas de code correspondant à ces exercices.


Exercice 12
 (Calcul du taux de GC)   Étant donné un génome (c’est-à-dire un fichier contenant une liste de bases qui peuvent être A, C, G ou T), il est intéressant de calculer le taux d’apparition des bases G et C sur le nombre total de bases.
Question 1   Implémentez une commande prenant en argument le nom d’un fichier contenant un génome et un nombre n de threads telle que :
Question 2   Expérimentez la commande précédente, en faisant varier la taille du génome à analyser et le nombre de threads pour trouver le nombre optimal de threads suivant la taille du génome.

Dans cet exercice, on supposera que le génome peut être placé entièrement en mémoire, pour éviter les conflits entre les threads dans l’accès aux entrées/sorties.

Code initial pour le calcul du taux de GC & Expérimentation

Vous trouverez sur le portail un code calculant séquentiellement le taux de G et C. Vous pourrez ainsi vous concentrer sur l’ajout des threads à ce code. Vous pourrez aussi vérifier le résultat de votre code multithreadé.

Par ailleurs, vous trouverez aussi un générateur de génome aléatoire qui vous permettra d’expérimenter sur des génomes de toutes les tailles (plus petites que la mémoire de votre machine, vu le modèle très simple de chargement du génome...).

Vous expérimenterez en lançant time ./compteur-gc pour observer comment se passe le temps écoulé pendant le calcul. Vous pourrez aussi utiliser la commande /usr/bin/time -f %e ./compteur-gc pour n’afficher que le temps réel écoulé.

Comprenez-vous comment ont été placés les appels à clock_gettime dans le code initial ?

Pour mener la campagne d’expériences, vous devez faire varier à la fois la taille n des génomes et le nombre t de threads (par exemple pour n=102 à 109 et t=20 à 25 cela donnera 48 expérimentations). En principe, pour qu’une mesure de temps soit valable il faut, pour chaque expérience taille de génome/nombre de threads, réaliser la moyenne sur plusieurs tests.

Vous pourrez avantageusement utiliser Gnuplot pour représenter votre graphique en 3 dimensions. En admettant disposer d’un fichier res.dat contenant sur chaque ligne la taille du génome, le nombre de threads et le temps (séparés par des espaces), vous pourrez avec les commandes suivantes obtenir une belle courbe.
gnuplot> set logscale x
gnuplot> set dgrid3d 30,30
gnuplot> set pm3d
gnuplot> splot ’res.dat’ using 1:2:3 with lines


Exercice 13
 (Tri rapide multithreadé)   Le principe du tri rapide est bien connu1. Rappelons juste qu’à chaque étape la partie du tableau en cours de tri est découpée en deux sous-tableaux : les éléments inférieurs au pivot et ceux supérieurs au pivot. Les deux sous-tableaux sont ensuite eux-mêmes triés, de façon indépendante l’un de l’autre. Il est donc possible de charger deux threads différents d’effectuer le tri de chaque sous-tableau.

On peut aussi imaginer implémenter le tri rapide en remplaçant chaque appel récursif par la création d’un nouveau thread. Mais cette stratégie est très coûteuse en nombre de threads, donc en temps (créer un thread prend du temps, etc.) et en mémoire.

Une stratégie plus efficace est d’utiliser une pile des tâches à faire, c’est-à-dire des sous-tableaux (que nous appellerons des blocs) du tableau à trier. Chaque thread répète alors les opérations suivantes :

jusqu’à ce que le tableau soit entièrement trié.

Comment un thread peut-il savoir que le tableau est entièrement trié ?

Les threads doivent s’arrêter lorsqu’il n’y a plus de bloc à trier et qu’aucun autre thread n’est en train de découper un bloc. Nous utiliserons donc un compteur du nombre de threads qui sont en train de découper un bloc.

Question 1   Mettez en œuvre cet algorithme en :

Vous veillerez à ce que les accès aux structures de données partagées soient protégés par un ou plusieurs verrous et que les endormissements (quand la pile est vide au moment où un thread veut dépiler un bloc) et les réveils (quand de nouveaux blocs doivent être traités) soient gérés grâce à une ou plusieurs conditions.

Quand les blocs sont petits, les threads passent leur temps à se synchroniser pour dépiler et empiler des blocs dans la structure de données partagée.

Question 2   Modifiez votre implémentation pour que les blocs qui sont plus petits qu’une valeur seuil soient triés en utilisant l’algorithme séquentiel plutôt que l’algorithme multithreadé.

Mettez en place une série de tests pour mesurer la vitesse de votre algorithme en fonction de la taille choisie comme seuil et du nombre de threads utilisés.

Expérimentations du tri rapide

Pour tester votre tri rapide, vous pourrez utiliser dd if=/dev/urandom of=/tmp/alea bs=1048576 count=128 qui permet de créer un fichier /tmp/alea contenant 128Mo de données aléatoires. Vous choisirez des tailles de données assez grandes mais toujours plus petites (au maximum la moitié ?) que la mémoire de votre machine.

Vous testerez aussi votre algorithme sur des données déjà triées.

Quel gain de performance arrivez-vous à obtenir par rapport à l’algorithme séquentiel ?

Serveur de chat multithreadé

Squelette d’un serveur de chat multithreadé

Les fichiers sources d’un squelette de serveur de chat multithreadé sont accessibles sur le portail.

Vous y trouverez :

La version fournie de la fonction manage_cnct() n’est pas multithreadée ; la connexion d’un client bloque le serveur...

Seul le fichier cnct.c est à modifier. Vous fournirez aussi des fichiers stat.h et stat.c pour la gestion des statistiques.

Il est possible d’activer la production de traces d’exécution du serveur par l’option -v. Utilisez les fonctions pgrs*() pour ce faire.

Utilisation du serveur de chat multithreadé

Au démarrage du serveur, le numéro du port d’écoute est affiché :

% ./mtcs
Server open on port 8012
...

il faut repérer ce numéro de port d’écoute (ici 8012), il faut aussi identifier aussi le nom de la machine ! (localhost pour la machine locale peut suffire).

On peut alors lancer des clients. Depuis un autre terminal :

% telnet localhost 8012
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
mtcs : bienvenu
foooooooooooooooo
foooooooooooooooo
FOOOOOOOOOOOOOOOOooooooooooooooooooooooooooooooo.............
FOOOOOOOOOOOOOOOOooooooooooooooooooooooooooooooo.............

on termine par control-] puis quit:

^]
telnet> quit
Connection closed.

Exercice 14
 (Serveur de chat)   Un serveur de chat multithreadé est basé sur le principe suivant : Dans une version initiale non multithreadée, l’implémentation de manage_cnct() repose sur un simple appel à repeater().
Question 1   Donnez une implantation de la fonction manage_cnct() déléguant à un thread l’appel à la fonction.

On se préoccupera aussi de la terminaison de ce thread.

Question 2   Quelle structure de données doit être partagée entre les threads pour réaliser cette répétition des flux d’entrée ? Identifiez les accès qui seront réalisés à cette structure de données. Comment les protéger ?

On désire ajouter le maintien de statistiques au serveur de chat. Les informations suivantes seront mémorisées :

De plus, on désire pouvoir interroger le serveur sur ces statistiques en lui envoyant un signal SIGUSR1.

Question 3   Comment garder et mettre à jour ces informations de statistiques ?
Question 4   Pourquoi est-il dangereux de contrôler par un verrou mutex POSIX l’accès partagé aux informations de statistiques entre les threads produisant ces statistiques et le handler de signaux affichant ces statistiques ?
Question 5   Implantez cette prise de statistiques et leur affichage.

Précédent Table des matières