Projet à réaliser en équipe de 4 ou 5 étudiants. Les équipes ont été tirées au sort et sont disponibles sur le serveur Thor/ruby.
Le langage de programmation devra être le C (pas de C++ !). Vous devez utiliser le repository GIT sur le serveur Thor/ruby.
La soutenance finale aura lieu le mardi 31 mai 2022 matin.
Elle durera environ 13 minutes suivies d'environ 5 mn de questions, et consistera en une présentation sur vidéoprojecteur et une démonstration. Vérifiez avant de venir que vous savez utiliser un vidéoprojecteur avec votre ordinateur, et allumez votre ordinateur avant d'entrer dans la salle (et amenez un adaptateur VGA si nécessaire).
Un rapport d'environ 8 pages devra être rendu la semaine précédente (mercredi 25 mai à 23h59), au format PDF. 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. Les deux fichiers doivent être uploadés sur le serveur Thor.
Les rapports et soutenances 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. Montrez la complexité de votre code en traçant graphiquement ses performances pour plusieurs tests.
A partir des rapports (intermédiaire et final), de la démo à mi-parcours et de la soutenance finale, on jugera :
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 :
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
(ne pas compiler avec -std=c89 ou -std=c99).
Comment fonctionne-t-il et que se passe-t-il ?
Etendre le programme pour manipuler plusieurs contextes à la fois et passer de l'un à l'autre sans forcément revenir dans le main à chaque fois. En clair, 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.
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) à politique FIFO. Cela nécessitera une bibliothèque de gestion de liste (voir les ressources en bas de cette page au lieu de réinventer une roue bugguée). 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, ...
Concrètement, il faudra :
pthread.h afin de pouvoir facilement
comparer les deux implémentations avec des programmes de test similaires.
-DUSE_PTHREAD
pour utiliser les pthreads à la place de votre bibliothèque
(elle pourra être légèrement différente, pourquoi ?).
main du programme :
Être capable de le manipuler comme n'importe quel autre thread,
sinon vous aurez rapidement des problèmes
(pour que thread_self marche,
pour qu'il puisse reprendre la main plus tard pendant l'exécution,
ou s'il doit faire un join sur ses fils,
ou le contraire).
pthread.
Vous êtes libres d'utiliser le système que vous souhaitez (Bash et gnuplot, Python et Matplotlib, R, ...), mais il faut que ce soit pratique : vous
allez utiliser ce système de nombreuses fois. Dans l'idéal, une commande (invoquer un script shell / Python / ...) devrait permettre de lancer tous
les programmes d'exemples avec les deux implémentations des threads, faire varier leurs arguments, mesurer leur durée d'exécution et tracer les
courbes correspondantes. Une séance devrait être suffisante à mettre en place ce système.
make (cible par défaut) : Compiler votre bibliothèque et les tests.make check : Exécuter les tests, avec des valeurs raisonnables pour les tests qui veulent des arguments en ligne de commande.make valgrind : Exécuter les tests sous valgrind avec les options --leak-check=full --show-reachable=yes --track-origins=yes.make pthreads : Compiler les tests pour les pthreads.make graphs : Lancer votre système pour tracer les graphes.make install : Installe les fichiers compilés dans le répertoire install avec l'arborescence suivante :
install à la racine pour que le serveur Thor puisse par exemple lancer ./install/bin/22-create-many-recursive.
make check dans de nombreux projets).
-DUSE_PTHREAD).
fibonacci.c,
tester d'autres applications parallèles créant beaucoup de threads :
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.
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 une milliseconde.
Lors de la présentation de ces résultats dans le rapport, on précisera bien la machine utilisée
(combien de coeurs ?) afin que la comparaison avec pthreads soit significative.
Si nécessaire, on pourra binder les programmes pour controller finement le nombre de
coeurs physiques réellement utilisés.
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 :
pthread.Seulement une fois que tous ces points sont satisfaits, vous pouvez passer aux objectifs avancés.
Une fois ce travail de base réalisé, chaque groupe devra s'intéresser à certaines des idées suivantes. Pensez à mesurer l'impact sur les performances de chaque changement important dans votre bibliothèque (make graphs !).
71-preemption).
join.
On pourra utiliser les pthread_spinlock_t.
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?).
mprotect,
on détectera quand un thread déborde de sa pile
et on le supprimera le thread fautif sans gêner les autres.
On pourra utiliser sigaltstack pour donner une pile au traitant de segfault quand
la pile du thread est déjà pleine.
join pour signaler l'erreur proprement.
81-deadlock.
sigwait pour dormir jusqu'à la réception d'un signal.
Pour éviter de réimplémenter vous même des listes et de passer des heures à les débugguer, regarder
les Queue BSD (un peu obscur au premier abord mais très efficace).
Si vraiment on ne veut pas les utiliser, regarder aussi
les CCAN list.h (similaire aux listes du noyau Linux)
ou éventuellement les GList (mais attention à la gestion des fuites mémoire).
Valgrind va vous être indispensable pour trouver les fuites ou corruptions 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);
/* sauver ce valgrind_stackid pour plus tard */
...
...
/* juste avant de libérer la pile de ce thread */
VALGRIND_STACK_DEREGISTER(valgrind_stackid);
...
Le projet est conçu et tester pour fonctionner sur Linux. Le projet peut
fonctionner sur d'autres systèmes, mais sans garanties ; l'utilisation d'un
système Linux est donc très fortement recommandée.
Juste à titre d'information, sur MacOS, il est nécessaire de compiler ainsi :
gcc -std=gnu89 -D_XOPEN_SOURCE contextes.c (et même comme ça, gcc
affiche beaucoup d'avertissements...).
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.