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. Vous pouvez créer un repository SVN ou 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 mardi 12 février. 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 la veille (lundi 11 février), envoyé en PDF par mail à votre encadrant et à Brice Goglin, en précisant l'URL du dépôt de code. 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 lors de la dernière séance (vendredi 22 février).

Elle durera environ 15 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 ensuite être rendu (vendredi 9 mars), 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 (pas de .rar!) contenant tout le code source et un minimum de documentation permettant de compiler et tester le projet.

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

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 :


Objectifs avancés

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

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 vous ne voulez pas les utiliser, ou s'il y a un problème de complexité, on pourra éventuellement 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 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);
...
 
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.

Archives
Pour le sujet 2015/2016 sur le système de fichiers de tags, c'est ici.
Updated on 2019/02/12.