Consignes

Projet à réaliser en groupe de 5 étudiants (5 groupes par groupe de TD), encadré par Nathalie Furmento, Damien Martin-Guillerez et Brice Goglin. Les groupes devront être formés et indiqués par mail à votre encadrant et à Brice Goglin avant la fin de la première semaine (vendredi 17 février 2012).

Le langage de programmation devra être le C. L'utilisation d'une forge pour maintenir le projet est vivement recommandée.

Rapport et démonstration intermédiaires

Une démonstration des fonctionnalités implémentées devra être présentée lors de la 5ème séance (du 26 au 30 mars 2012). Un rapport intermédiaire (4-5 pages) sera de plus rendu 3 jours avant.

Rapport et soutenance de fin de projet

La soutenance finale aura lieu le mercredi 16 mai 2011. Elle durera environ 13 minutes suivies d'environ 5mn de questions, et consistera en une présentation sur vidéoprojecteur et une démonstration. Les ordinateurs de la salle pourront être utilisés pour la démonstration, mais il sera préférable de présenter une démo vidéoprojetée depuis un portable.

Un rapport d'environ 8 pages devra être rendu le mercredi 9 mai, au format PDF par mail à votre encadrant et à Brice Goglin. Le rapport décrira ce qui a été implémenté, comment et pourquoi. Il sera accompagné d'une archive tar.gz contenant tout le code source et un minimum de documentation permettant de compiler et tester le projet. Une version papier du rapport devra de plus être disponible le jour de la soutenance.

Les rapports et soutenance devront notamment expliquer comment vos tests montrent la validité du comportement de votre bibliothèque et indiquer les différents coûts que vous avez mesurés (voir la partie premiers objectifs ci-dessous). Inutile d'écrire des pages pour rappeler le sujet, il faudra se concentrer sur les choses utiles et prêtant à discussion (complexité, modification de l'interface de programmation, ...).

Soutenances

Le matin, groupes 1 et 4, avec Brice Goglin et Damien Martin-Guillerez:

• 09h00-09h20 Boutin Cheippe Gueye Lux
• 09h20-09h40 Abid Bilange Boe Ferriere Song
• 09h40-10h00 Blanchemain ElHassani Juan Mollard Rahhali Schmidt
• 10h00-10h20 Beati Cardoso Herbreteau Machurey Valli
• 10h20-10h40 Caneill Destigny Laturaze Laverny Navarro Pussacq
• 10h40-11h00 Boudinet Galvao Mizony Oriou Rouxel
• 11h00-11h20 Baudet Dallago DiQual Dubouchez ElMohib Laneyrie
• 11h20-11h40 Loubet Maoubouh Montanari Oustlant Seunes
• 11h40-12h00 Cheimanoff Ferry Guillou Savigny
• 12h00-12h20 Gharsalli Hailass Kesmi Shitit Stefani

L'après-midi, groupes 2 et 3, avec Brice Goglin et Nathalie Furmento:

• 14h00-14h20 Besnard Georges Jiang Lambert
• 14h20-14h40 Bizac Durant Vandenberghe Youbi Zheng
• 14h40-15h00 Barfety Julien Maaoui Meli Najar
• 15h00-15h20 Boust Chuquillanqui Piacibello Retrain Verdier
• 15h20-15h40 Bouallou Chapron Fournier Lalanne Malinowski
• 15h40-16h00 Aigron Caleca Ouidani Slimani Sribti
• 16h00-16h20 Bernard Dupont Menand Morel Plans
• 16h20-16h40 Cibois Delente Donon Fleurey Fort
• 16h40-17h00 Carrere Morillon Elhatimi Delaunay Nedelec
• 17h00-17h20 Elwahbi FalkowiezDeMortain Haddoun Laurent Pottier

Introduction

Ce projet vise à construire une bibliothèque de threads en espace utilisateur. On va donc fournir une interface de programmation plus ou moins proche des pthreads, mais en les exécutant sur un seul thread noyau. Les intérêts sont:

• Les coûts d'ordonnancement sont beaucoup plus faibles
• Les politiques d'ordonnancement sont configurables
• On peut enfin expérimenter le changement de contexte pour de vrai

Mise en route

Pour commencer, on va construire un petit programme qui manipule différents threads sous la forme de différents contextes. On commencera par exécuter ce programme et comprendre comment il fonctionne (ne pas compiler avec -std=c89 ou -std=c99). Ensuite, on l'étendra pour manipuler plusieurs contextes à la fois et passer de l'un à l'autre sans forcément revenir dans le main à chaque fois. En clair, il faut montrer qu'on peut exécuter plusieurs tâches complexes et indépendantes en les découpant en morceaux et en entrelaçant l'exécution réelle de ses morceaux.

Premiers objectifs

L'objectif du projet est tout d'abord de construire une bibliothèque de gestion de threads proposant un ordonnancement coopératif (sans préemption). On devra donc tout d'abord définir une interface de threads permettant de créer, détruire, passer la main (éventuellement à un thread particulier), attendre la/une terminaison, ...
On commencera par l'interface proposée ici et on pourra éventuellement s'en écarter si nécessaire. On veillera cependant à rester relativement proche de pthread.h afin de pouvoir facilement comparer les deux implémentations avec des programmes similaires.
Le premier objectif sera d'être capable d'exécuter correctement ce programme d'exemple. On vérifiera que sa sortie est cohérente avec celle de la version pthread du même programme.

Il faudra ensuite notamment:

• Ajouter au projet des programmes utilisant cette interface et bibliothèque pour:
  • Montrer le bon fonctionnement du projet (équivalent du make check dans de nombreux projets):
    • Lancer puis attendre la terminaison d'un thread et montrer que toutes les ressources sont bien libérées.
    • Vérifier que le changement de contexte se passe bien s'il n'y a aucun autre thread à exécuter.
    • Vérifier que plusieurs threads s'exécutent bien tous en alternance et dans l'ordre prévu par votre ordonnanceur.
    • Vérifier que la terminaison du thread courant provoque bien le passage de la main à un autre thread.
    • Faire une boucle infinie de création+destruction et vérifier que la consommation mémoire est stable. On pourra utiliser valgrind pour trouver les fuites mémoire (voir plus bas).
    • Bien d'autres!
  • Mesurer les performances et mettre en évidences les avantages et inconvénients de votre implémentation, en comparant notamment aux pthreads:
    • Coût de la création et destruction d'un thread, en fonction du nombre de threads dejà existants.
    • Coût du changement de contexte, vers soi-même et vers un autre thread, en fonction du nombre de threads dejà existants.
    • Nombre de threads pouvant être lancés en même temps et influence sur les performances du changement de contexte.
    • D'autres!
  • Tester des vraies applications parallèles créant beaucoup de threads. On ne cherchera pas à optimiser le programme lui-même, on conservera un modèle simple créant beaucoup de threads simultanément afin de tester l'ordonnanceur. Cela implique notamment de faire tous les create puis tous les join plutôt qu'un join directement après chaque create. Dans le rapport, on pourra présenter une courbe de temps d'exécution en fonction du paramètre d'entrée.
    • Calcul de la somme de tous les éléments d'un grand tableau par diviser-pour-régner.
    • Calcul de la suite de Fibonacci.
    • Tri de très grand tableau (rapide, fusion, ...).
    • D'autres!
  On veillera de plus à ce que les tests de performance soient suffisamment longs pour être significatifs: inutile de mesurer la durée d'exécution d'un programme si son initialisation est dix fois plus longue que ce qu'on cherche à comparer, ou si son exécution prend un milliseconde.
  Lors de la présentation de ces résultats dans le rapport, on précisera bien la machine utilisée (combien de processeurs?) afin que la comparaison avec pthreads soit significative. Si nécessaire, on pourra binder les programmes pour controller finement le nombre de processeurs physiques réellement utilisés.


• Mettre en place un système de compilation construisant une bibliothèque partagée basé sur des Makefile (en utilisant éventuellement les autotools ou cmake). Cette bibliothèque et le fichier d'entête de l'interface devront pouvoir être installés pour que des programmes externes puissent les utiliser facilement.


• Veiller à conserver une complexité satisfaisante du code afin d'assurer de bonnes performances pour les différentes opérations. Ces éléments seront mis en valeur dans les tests de performance. Cela implique notamment de:
  • Ne pas parcourir plusieurs fois la même longue liste (ou long tableau) dans une même opération.
  • Ne pas parcourir de longue liste ou long tableau inutilement: par exemple il est inutile de parcourir une liste contenant tous les threads (prêts, bloqués voire morts) quand on cherche uniquement un thread prêt.

Objectifs avancés

Une fois ce travail de base réalisé, chaque groupe devra s'intéresser à certaines des idées suivantes:

• Régler le cas du thread principal (le main du programme): Etre capable de le manipuler comme n'importe quel autre thread. Ceci sera très rapidement nécessaire, en particulier pour que le main puisse reprendre proprement la main plus tard dans l'exécution, ou encore pour que le main puisse faire un join sur ses fils.


• Ajouter des fonctions de synchronisation de type sémaphores et/ou mutex pour permettre aux threads de manipuler des données partagées de manière sécurisée. Les sémaphores pourront consister en une généralisation du join. On pourra utiliser cette implémentation de spinlock (attention à bien définir X86_32 ou X86_64 selon l'architecture cible), ou utiliser une bibliothèque dédiée aux opérations atomiques. On réfléchira à la validité de passer la main lorsqu'on tient un verrou et l'impact que cela peut avoir sur l'implémentation (attente active ou passive?).


• Support des machines multiprocesseur : Utiliser plusieurs threads noyau pour exécuter vos threads utilisateur en même temps. Cela nécessitera notamment l'ajout de fonctions de verrouillage et synchronisation. On observera également à l'impact de ce support sur les performances de l'ordonnanceur. Va-t-on vraiment deux fois plus vite avec deux processeurs ? Pour quel type d'applications ? On pourra également ajouter des fonctions permettant de verrouiller un thread sur certain(s) coeur(s).


• Détecter les débordements de pile des threads (par exemple en utilisant mprotect) puis être capable de tuer le thread fautif sans gêner les autres. On pourra utiliser sigaltstask pour donner une pile au traitant de signal quand la pile du thread est déjà pleine.


• Préemption : On pourra commencer par une préemption pseudo-coopérative cachée dans toutes les fonctions de la bibliothèque (par exemple dans thread_self, avant de s'intéresser à une vraie préemption utilisant par exemple des signaux.


• Annulation d'un autre thread : Une interface similaire aux pthreads... ou pas?


• Gestion des appels-système bloquants : Comment bloquer sur une entrée-sortie sans bloquer l'exécution des autres threads du même processus?


• Signaux : Par exemple permettre d'envoyer un signal à un thread particulier.


• Amélioration l'ordonnancement des threads : Si vous avez implémenté des priorités (pas obligatoire), proposer différentes politiques d'ordonnancement avec un choix à la compilation (voire à l'exécution).

Ressources

Notez que setjmp/longjmp sont une variante un peu plus hardcore de l'interface makecontext/swapcontext. Elle est souvent utilisée dans les implémentations "sérieuses", mais le principe reste le même.

• GNU C library manual: System V contexts
• Combining setjmp()/longjmp() and Signal Handling.
• Implementing a Thread Library on Linux
• Un TP sur le même sujet
• La page du cours

Valgrind est très utile pour trouver les fuites ou corruption mémoire, mais il va falloir l'aider un peu en lui disant où se trouvent les piles de vos threads. Pour ce faire:

#include <valgrind/valgrind.h>
...

...
/* juste après l'allocation de la pile */
int valgrind_stackid = VALGRIND_STACK_REGISTER(context.uc_stack.ss_sp,
                                               context.uc_stack.ss_sp + context.uc_stack.ss_size);
/* stocker valgrind_stackid dans votre structure thread */
...

...
/* juste avant de libérer la pile */
VALGRIND_STACK_DEREGISTER(valgrind_stackid);
...