1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
Sujet de projet - Système IN115
Le but de ce projet est de réaliser un environnemet multithread en espace utilisateur. Le développement de deux programmes faisant usage de cet environnement est également demandé.
Les programmes doivent être écrits en langage C, et doivent faire usage des appels système UNIX que vous connaissez. L'utilisation de tout autre environnement multithread, tel que les threads POSIX, est interdite.
Ce projet doit être réalisé en binômes.
Description générale
Comme son nom l'indique, un environnement multithread en espace utilisateur fonctionne dans un environnement de processus. L'utilisateur a donc toute latitude pour programmer ses threads à sa manière. Il n'a aucune prise sur les autres processus du système, et encore moins sur le système lui-même.
Un contexte de thread se limite à la valeur des registres du processus, et à une pile de thread. Le basculement d'un thread vers un autre par l'ordonnanceur se limite simplement à sauvegarder le contenu des registres (ce qui inclut le pointeur de pile) dans une zone mémoire réservée du thread appelant, et à restaurer le contenu des registres tel qu'ils étaient lorsque ce second thread avait précédemment fait appel à l'ordonnanceur.
Le pointeur de pile, ainsi que le compteur ordinal étant eux-mêmes des registres, le fait de modifier leur valeur permet de changer la pile courante, et de sauter l'exécution vers la position définie par le compteur ordinal du nouveau contexte. Ainsi, un thread interrompu peut reprendre son exécution exactement dans l'état où il était au moment de l'appel à l'ordonnanceur.
Indications
Contextes de thread
Sous UNIX, la gestion de contextes s'effectue à l'aide de l'API ucontext, disponible en utilisant le fichier d'en-tête ucontext.h.
Cette API contient entre autres les structures de données et fonctions suivantes :
typedef struct {
void *ss_sp; /* adresse de base de la pile */
int ss_flags; /* flags */
size_t ss_size; /* taille de la pile en octets */
} stack_t;
typedef struct ucontext {
struct ucontext *uc_link;
sigset_t uc_sigmask;
stack_t uc_stack;
mcontext_t uc_mcontext;
...
} ucontext_t;
void makecontext(ucontext_t *ucp, void *func(), int argc, ...);
int swapcontext(ucontext_t *oucp, ucontext_t *ucp);
int getcontext(ucontext_t *ucp);
int setcontext(const ucontext_t *ucp);
* setcontext permet de définir le contexte courant en utilisant le contenu de la structure pointée par ucp. Il en résulte un saut vers la position désignée par le compteur ordinal.
* getcontext permet de récupérer le contexte courant. On peut donc revenir à la position qui suit directement l'appel à getcontext, en fournissant le contexte obtenu à setcontext.
* swapcontext effectue à la fois la sauvegarde du contexte courant et le basculement vers un autre contexte.
* makecontext est une fonction qui permet de construire un contexte pour un nouveau thread. On part en principe d'un contexte déjà existant (obtenu avec getcontext), et on lui associe une nouvelle pile et une fonction à appeler, comme dans l'exemple ci-dessous :
/* taille de la pile du nouveau thread, ici 64 ko */
#define STACK_SIZE 65536
/* contexte où l'on va sauvegarder le contexte courant avant le saut vers le
* nouveau contexte */
ucontext_t ici;
/* obtenir le contexte courant */
ucontext_t labas;
getcontext(&labas);
/* taille de la pile associée au thread */
labas.uc_stack.ss_size = STACK_SIZE;
/* le bloc mémoire correspondant à la pile */
labas.uc_stack.ss_sp = malloc(STACK_SIZE);
/* on ignore les flags */
labas.uc_stack.ss_flags = 0;
/* le contexte sur lequel basculer quand la fonction_thread sera terminée.
* Idéalement, la fonction à exécuter devra libérer les ressources allouées
* pour le thread, comme la pile, et exécuter l'ordonnanceur pour poursuivre
* l'exécution d'un autre thread.
*/
labas.uc_link = &contexte_fin_thread;
/* modification du contexte en donnant comme point d'entrée la fonction
* fonction_thread, prenant n arguments : argument1, ... , argumentn
*/
makecontext(&labas, &fonction_thread, n, &argument1, ..., &argumentn);
/* sauvegarde du contexte courant, et basculement vers le nouveau contexte */
swapcontext(&ici, &labas);
L'API multi-thread
Les appes de votre API multi-thread devront ressembler à ceux que vous connaissez dans les threads POSIX.
Vous définirez les fonctions suivantes :
* gestion des threads
o int thread_create(thread_t * thread, void *(*start_routine)(void *), void * arg);
qui crée un thread te place son identifiant dans la variable pointée par thread.
o int thread_join(thread_t th, void **thread_return);
qui attend la fin de l'exécution du thread th, et place sa valeur de retour dans la variable pointée par thread_return.
o int thread_yield(void);
qui appelle l'ordonannceur pour basculer l'exécution d'un thread à un autre.
* gestion des mutex
o int thread_mutex_init(mutex_t *mutex);
qui initialize un mutex (une allocation statique est également possible en affectant une constante THREAD_MUTEX_INITIALIZER à la déclaration d'un mutex)
o int thread_mutex_lock(mutex_t *mutex);
qui verrouille un mutex
o int thread_mutex_unlock(mutex_t *mutex);
qui déverrouille un mutex
* gestion des conditions
o int thread_cond_init(cond_t *cond);
qui initialise une variable de condition
o int thread_cond_signal(cond_t *cond);
qui relance un des threads bloqués en attente de la condition cond
o int thread_cond_broadcast(cond_t *cond);
qui relance tous les threads bloqués en attente de la condition cond
o int thread_cond_wait(cond_t *cond, mutex_t *mutex);
qui déverrouille atomiquement le mutex et attend que la variable de condition cond soit signalée;
Vous devrez définir les types thread_t, mutex_t, et cond_t. Par exemple, comme un thread ordonnancé peut avoir plusieurs états (en attente, bloqué sur un mutex, bloqué sur un thread_join, ...), doit également posséder son propre contexte, et possède très certainement d'autres attributs, vous pourriez définir un structure de thread et définir le type thread_t comme un pointeur vers cette structure.
L'ordonnanceur
L'ordonnanceur est de type coopératif, c'est-à-dire que les threads lui font volontairement appel pour basculer de l'exécution d'un thread à un autre, contrairement à un ordonnanceur préemptif, qui est exécuté à intervalles réguliers, même si les threads ne lui font pas appel. Des situations de conditions de concurrence pouvant être induites par la préemption sont inexistantes dans un contexte de threads coopératifs.
Nous l'avons vu auparavant, l'appel à thread_yield pour basculer de l'exécution d'un thread à un autre est relativement peu utilisé directement par les programmes utilisateur multi-thread. Cet appel est plutôt réservé aux fonctions de bibliothèques compatibles avec l'environnement multi-thread. Par exemple, la gestion de mutex peut s'effectuer en vérifiant la valeur d'une variable partagée, et tant que cette valeur est non-nulle, on boucle en effectuant des appels à thread_yield.
La stratégie d'ordonnancement sera un simple round-robin.
Votre ordonnanceur doit gérer des listes de threads : liste des threads bloqués, prêts, en attente d'un thread_join, d'un mutex, etc. À tout moment, un thread est dans une et une seule liste seulement.
Entrées/sorties avec read et write
Vos programmes seront capables d'effectuer des entrées/sorties avec des appels comparables au read et au write. Vous devrez tenir compte du fait que read et write peuvent être bloquants : cela risque donc de bloquer tout le processus sans possiblité de basculer l'exécution vers un autre thread. Vous devrez donc définir deux fonctions read2 et write2, semblables de l'extérieur à read et write, mais qui effectueront un test de disponbilité de données (cf. appel système select) sur les descripteurs de fichiers concernés avant de lancer une lecture ou une écriture (ou sinon, un basculement de thread).
De cette manière, vos threads seront normalement capables de faire des accès disques non bloquants, et même de communiquer entre eux par l'intermédiaire de tubes !
Endormissement de threads (optionnel)
Si vous vous en sentez le courage, vous pouvez réimplémenter le sleep, sachant que le thread faisant appel à votre fonction ne devra pas bloquer les autres, et que plusieurs threads auront la possiblité de faire des appels à sleep en même temps.
Travail demandé
Le programme
* Vous devez programmer le projet en langage C.
* Vous incluerez à votre projet un fichier Makefile, afin d'automatiser la compilation par une simple commande make. Le Makefile doit également inclure une cible clean, afin de nettoyer le répertoire des fichiers générés.
* Toute la configuration du programme (valeur des constantes, éventuellement la compilation conditionnelle) devra pouvoir être effectuée en ne modifiant que le fichier Makefile.
* Prenez un soin particulier pour l'efficacité de votre programme :
o pas de code inutile ;
o pas de copier/coller de code (quelques lignes code servant plusieurs fois dans le programme doivent être intégrées dans une fonction) ;
o prenez un soin particulier pour l'efficacité des entrées/sorties : faites un usage optimal de buffers de fichiers.
* Suivez correctement les recommandations pour les projets de votre annexe de cours.
Les tests
Vous testerez votre bibliothèque de threads à l'aide de deux programmes (ou trois si vous avez réimplémenté le sleep) :
1. Un algorithme de tri de type quicksort ou tri rapide. Au lieu d'effectuer des appels récursifs, l'algorithme créera des threads pour le tri des sous-tableaux.
Vous implémenterez votre tri avec un programme d'exemple triant un tableau de 1000 valeurs aléatoires comprises entre 0 et 10000.
2. Un programme créant un chaîne de 10 threads communiquant par 9 tubes. Le premier thread lit les caractères lus sur l'entrée standard, les écrit à l'entrée du tube de sortie, puis les caractères sont relayés par les tubes de thread en thread, jusqu'au dernier, qui les écrira sur la sortie standard.
3. Si vous avez réimplémenté le sleep, vous ferez un programme qui lance une dizaine de threads effectuant chacun une attente différente entre 1 et 10 secondes, et montrant que les threads se réveillent bien au moment voulu.
Le rapport
Votre travail devra être accompagné d'un rapport, dans un format de texte courant (PostScript, Acrobat (pdf), OpenDocument, ...), décrivant votre travail, les problèmes posés et les réponses que vous y avez apportées.
Vous attacherez une importance particulière pour montrer que ce que vous avez réalisé effectue bien ce qui était demandé : donnez les algorithme utilisés, les mécanismes employés, etc. Justifiez également vos choix pour les structures de données.
Expliquez comment les allocations faites au moment de la création d'un thread sont bien libérées à la terminaison de ce même thread.
Le rapport n'a pas besoin d'être volumineux, allez à l'essentiel. Merci de ne pas inclure l'intégralité du code dans le rapport ; n'incluez que des parties de code, et seulement si elles sont nécessaires dans vos explications.
Remise du projet
La date de remise du projet est fixée au lundi 14 janvier 2008, à 23h59 au plus tard. |
