Projet Système - Threads en espace utilisateur


Déroulement

Consignes

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.

Rapport et démonstration intermédiaires

Une démonstration des fonctionnalités implémentées devra être présentée pendant la 6ème séance le vendredi 16 avril. L'encadrant passera une dizaine de minutes avec chaque équipe pour faire un point détaillé sur ce qui marche ou ne marche pas, notamment en faisant tourner les différents programmes de tests.

Un rapport intermédiaire (environ 4 pages) sera rendu 3 jours avant (mardi 13 avril à 23h59) en PDF sur le serveur Thor. Le rapport décrira ce qui marche ou ne marche pas, pourquoi, et ce que vous avez prévu de faire pour la suite du projet. Inutile de rappeler le sujet ou d'expliquer l'interface thread.h!

Rapport et soutenance de fin de projet

La soutenance finale aura lieu le lundi 17 mai.

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 12 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.

Evaluation

A partir des rapports (intermédiaire et final), de la démo à mi-parcours et de la soutenance finale, on jugera :

Contenu du projet

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 :


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 (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.

Objectifs pour les 2-3 premières séances

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 :

Tests de robustesse et performance

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 :


Check-list avant de passer aux objectifs avancés

Seulement une fois que tous ces points sont satisfaits, vous pouvez passer aux objectifs avancés.

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 !).

Ressources

Listes

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

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);
...
 

Pour aller plus loin, setjmp/longjmp

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.