L'étudiant trouvera une description de FRED à travers les sections qui suivent : La description de l'interface applicative( L'interface applicative de FRED ) :comment écrire un programme concurrent FRED, comment lancer des threads etc.. Il trouvera aussi une description de l'implémentation( Implantation de FRED ) et des mécanismes de base nécessaires. Dans la version html de ce document, il pourra naviguer à son gré dans la description des différents modules de FRED.
FRED offre les fonctionnalités primitives d'un noyau de threads gérées en temps partagé. Un noyau de thread réaliste doit offrir des fonctions plus élaborées. Toutes ces fonctions ne sont cependant que des extensions des mécanismes de base de FRED. Ces fonctions sont présentées en plusieurs sections :
Pour utiliser FRED, il faut inclure le fichier fred.h pour disposer de toutes les déclaration de types et profils de procédures de l'interface. Il est aussi nécessaire dans la procédure initiale main() du programme principal concurrent d'initialiser les variables statiques de FRED. C'est le rôle de FredInitialize(). Puis le programmeur peut initialiser ses propres variables globales et lancer ses threads initiaux, se synchroniser etc.... FredWaitTerminate() lui permet d'attendre la terminaison des threads initiaux (et des threads créés par ceux-ci et etc....). Quand la procédure main() termine, tout le programme concurrent termine.
#include <fred.h> int main( int argc, char** argv) {/* FRED n'est pas utilisable. Seul du code C séquentiel est exécutable */ <....> FredInitialize(); /* FRED est partiellement utilisable. On peut créer des threads, intialiser des objets satiques, se synchroniser .... */ <....> FredWaitTerminate(); /* Attente de la terminaison de tous les threads. A la reprise, FRED n'est plus utilisable. Seul du code C séquentiel est exécutable. */ <....> }
Un thread est l'exécution concurrente d'une procedure C à un paramètre de type (void*) et un résultat de type (void*). Son type est défini par FredRunnable. On rappelle que tout pointeur (T*)étant "castable" en (void*) et réciproquement, le type (void *) veut dire référence sur n'importe quel type. Pour s'exécuter, un thread a besoin d'une pile pour ses contextes (trames) de procédure. La création d'un thread nécessite donc de donner de :
Un thread se termine par terminaison normale de sa procédure initiale ou par suicide. La procédure FredThreadExit() permet à un thread de se terminer en rendant un résultat de type (void*).
Un thread peut connaitre son identité (reférence sur son descripteur (type FredThread)) par la fonction FredThreadCurrent().
Le thread courant peut spontanément abandonner le processeur au profit d'un autre thread prêt au sens des règles d'ordonnancement par FredThreadYield().
FRED n'offre qu'un mécanisme d'exclusion mutuelle basé sur les mécanismes matériel : inhibition des interruption sur monoprocesseur qui doit être étendu par un verrouillage de type "TestAndSet" sur multiprocesseur. L'utilisation d'un verrouillage matériel n'est utilisable que sur des durées très courtes pour éviter de retarder ou perdre des signaux externes ou bloquer les autres processeurs(cas multiprocesseur). Dès que la durée d'exclusion mutuelle devient importante, il faut recourir à des mécanismes de synchronisation plus élaborés (sémaphore, verrou Posix etc..).
L'exclusion mutuelle repose sur les 2 procédures FredMutexOn() et FredMutexOff().
/* code incorrect */ ....FredMutexOn();....; FredMutexOn();....FredMutexOff();....FredMutexOff();....
L'exclusion mutuelle ne suffit pas pour exprimer toutes les relations de dépendance et de synchronisation entre threads. Il est nécessaire de bloquer un thread si sa continuation falsifierait un invariant d'état global et, réciproquement, de réveiller les threads dès que leurs continuations préservent cet invariant. FRED offre le type FredQueue qui permet de définir une file d'attente de threads gérée selon la statégie FIFO. On initialise une queue par FredQueueInit().
Le thread courant peut se bloquer dans une file d'attente c.à.d. il s'inscrit en dernier dans cette file et donne le processeur à un autre thread prêt. C'est la procédure FredThreadSuspend().
Une fois bloqué dans une file, un thread peut être sorti de la file par FredQueueGetFirst(), remis dans une autre file par FredQueuePutLast(). On peut réveiller le premier d'une file d'attente c.à.d. le remettre dans la file des threads prêts par FredThreadWakeUp().
Utilisées nécessairement dans une portion de code en exclusion mutuelle (entre FredMaskOn() et FredMaskOff()), ces procédures permettent de réaliser des opérateurs de sunchronisation plus élaborés (Un exemple d'outil de synchronisation : le sémaphore).
La création des threads comme la programmation concurrente en C nécessitent d'allouer et libérer dynamiquement des blocs de mémoire. Les procédures d'allocation et libération modifient la description de l'état d'occupation de la mémoire. Ce sont des procédures qui doivent s'exécuter en exclusion mutuelle. FRED fournit un carrossage de la gestion mémoire standard de C pour assurer l'atomicité de l'allocation/ libération des blocs mémoires.
FredAtomicAlloc(),FredAtomicCalloc() et FredAtomicFree()sont fonctionnellement identiques aux procédures malloc(),calloc() et free() de la libC.
Les trois macros FredNEW(), FredNEW_VECTOR() et FredDELETE() sont de simples carrossages des précédentes.
Pour des raisons identiques à la gestion mémoire, l'accès aux fichiers par les threads doit aussi être synchronisé. FRED ne fournit des procédures atomiques que pour les procédures de type printf() et scanf() de la libC.
L'exclusion mutuelle par masquage et la gestion de files de threads sont suffisantes pour reconstruire des opérateurs de synchronisation plus souples et evitant de masquer les interruption trop longtemps. C'est le cas du sémaphore de Dijkstra.
On peut ensuite traiter un problème classique de synchronisation comme les N philosophes.
Un sémaphore est un simple sac où l'on prend ou remet des jetons un à un. Un thread demandant un jeton doit attendre qu'il y en ait un de disponible. Tout thread déposant un jeton doit réveiller le plus ancien thread en attente de jeton s'il en existe. Le sémaphore doit être déclaré de type FredSemaphore, alloué en variable globale ou sur le tas. Dans tousles cas, il doit être initialisé à une valeur >=0 via FredSemaphoreInit().
FredSemaphore GlobalS ; /* sémaphore global */ struct S1 { /* struct globale */ Semaphore member; /* avec sémaphore membre */ ... } void exemple() { S1 * s; FredSemaphore LocalS ; /* sémaphore local */ FredSemaphore* DynaS ; /* sémaphore dynamique */ ..... FredSemaphoreInit(&LocalS,0); /* initialisation */ .... DynaS = FredNEW(FredSemaphore); /* allocation */ FredSemaphoreInit(DynaS,3); /* initialisation */ ..... FredSemaphoreInit(&GlobalS,25); /* initialisation */ ..... s= FredNEW(S1); /* allocation d'une structure */ FredSemaphoreInit(&(s->member),33); /* initialisation du membre*/ ..... }
Il peut ensuite être utilisé pour prendre FredSemaphoreP() ou déposer un jeton FredSemaphoreV()
L'implantation nécessite un compteur et une queue de threads en attente (cf. FredSemaphore). Le compteur représente le nombre de jetons si le compteur est >=0 et le nombre de threads en attente s'il est <0. Le test du compteur, sa modification et la manipulation de la file d'attente doivent être atomiques et se font donc masqués. (cf. Interface sémaphore)
Le programme principal initie :
#define NBphilo FredThread philosophe[NBphilo]; FredSemaphore fourchette[NBphilo]; int main ( int argc, char** argv) { FredInitialize(); for( i=0;i<NBphilo;i++) FredSemaphoreInit(&fourchette[i],1); for( i=0;i<NBphilo;i++) philosophe[i]= FredThreadSpawn(20000,codephilo,(void*)i,(void**)0); FredWaitTerminate(); /* C'est termine */ return 0; }/
L'interblocage se produit dès que les philosophes utilisent un ordre horaire ou antihoraire pour prendre leurs fourchettes. Par exemple un philosophe i prend la fourchette i puis la fourchette (i+1)%NBphilo. La stratégie d'évitement du blocage est l'allocation des ressources selon un ordre total universel. Ceci veut dire que si les philosophes doivent prendre les fourchettes par numéro toujours croissant ou décroissant. Ceci implique que le philosophe de rang le plus grand (i==NBphilo-1) prendra la fourchette 0==(i+1)%NBphilo puis la fourchette i c'est à dire un comportement inverse des autres.
void* codephilo(void * x) { int j; int i = (int)x; /* numero du philosophe */ for( j=0;j<100;j++){ /* 100 iterations de penser/manger */ /* ça pense ..*/ /* ça pense à manger ..*/ if(i<(NBphilo-1)){ /* un droitier */ FredSemaphoreP(&fourchette[i]);FredSemaphoreP(&fourchette[i+1]); /* ça mange ..*/ FredSemaphoreV(&fourchette[i]);FredSemaphoreV(&fourchette[i+1]); }else{ /* le gaucher */ FredSemaphoreP(&fourchette[0]);FredSemaphoreP(&fourchette[NBphilo-1]); /* ça mange ..*/ FredSemaphoreV(&fourchette[0]);FredSemaphoreV(&fourchette[NBphilo-1]); } } return (void*) 0; /* suicide */ }
Pour plus de détails, voir le fichier exemple des N philosophes.
Le principe d'implantation d'un noyau de gestion de thread sur un monoprocesseur est d'entrelacer l'exécution des procédures associées à des threads au gré de synchronisation explicite ( sémaphore, verrou,..) ou des interruptions ( temps partagé, E/S). Il faut donc être capable de trier entre les threads suspendus en attente d'un signal externe (E/S, fin de quantum,..) ou interne ( sémaphore passant, réveil par un autre thread,..), ceux prêts à tourner et celui qui s'exécute sur le processeur : le thread actif ou courant. La technique classique est l'utilisation de listes que l'on appelle queues ou files d'attente (Gestion de listes ).
L'autre mécanisme nécessaire est le mécanisme qui permet de passer d'une exécution de procédure à une autre puis faire l'opération inverse. Pour ce faire, il suffit de sauvegarder l'état du processeur (registres) d'un thread et de relancer un autre thread depuis un état sauvé. Il faut de plus savoir créer un nouvel état d'exécution lors de la création d'un nouveau thread. A tout thread sera associée une zone de sauvegarde pour ses registres (compteur ordinal, stack pointeur, registres généraux etc...). La taille et l'organisation de cette zone dépend donc du processeur et de la façon de sauvegarder les registres. Pour passer d'un thread à un autre, il suffira de sauver les registres dans la zone du thread en cours d'exécution puis de recharger les registres à partir de la zone de sauvegarde d'un autre thread qui reprend alors sont exécution( Commutation de contexte ).
Enfin,il faut disposer d'un mécanisme permettant de faire ces commutation entre threads de façon atomique. Comme sur un monoprocesseur, la seule possibilité pour empêcher qu'une suite d'instructions de s'exécuter complètement est une interruption, l'atomicité est simplement réalisée en inhibant les interruptions au début de cette séquence( Inhibition des interruptions )
FRED est un noyau où les threads sont gérés en temps partagé. Il faut donc d'une part récupérer des interruptions( Traitement des interruptions ) et gérer un mécanisme de décomptage du temps pour provoquer une interruption périodique permettant de changer le thread actif( Gestion du décompteur )
La réalisation et mise en oeuvre du noyau de threads utilise des fonctions d'allocation mémoire et d'E/S. Les fonctions offertes par la bibliothèque standard C n'ont pas toujours été prévues pour être partagées entre des threads. Il est prudent de les rendre compatibles ( thread safe )avec les threads ( E/S et gestion de mémoire "thread-safe" ).
L'implantation d'un noyau de thread est alors l'utilisation coordonnée de toutes ces fonctions( Gestion des threads ).
Du point de vue de l'entrelacement des exécutions sur le processeur des différentes procédures que sont les threads, un descripteur de thread doit inclure une zone de sauvegardes pour ses registres (compteur ordinal, stack pointeur, registres généraux etc...). La taille et l'organisation de cette zone dépend donc du processeur et de la façon de sauvegarder les registres. Pour passer d'une exécution de thread à un autre, il suffira de sauver les registres dans la zone du thread en cours d'exécution puis de recharger les registres à partir de la zone de sauvegarde d'un autre thread qui reprend alors son exécution.
En plus des opération de sauvegarde restauration, il faut pouvoir initialiser une zone de sauvegarde de façon qu'un thread puisse démarrer correctement sa procédure initiale avec sa pile.
La gestion de Contexte est proposée en plusieurs variantes pour des systèmes UNIX . La première est basée sur les procédures setjmp()-\c lonjmp() qui sont fournies avec la librairie standard C et qui réalisent une forme de sauvegarde/restauration de contexte permettant d'écrire une commutation contexte de faççn portable. Par contre, l'initialisation d'un contexte reste à faire en fonction de la machine hôte et de l'implantation de la structure "jmpbuf" utilisée par la lib C. On trouvera une variation à destination de Linux IA32 ( Gestion de contexte pour Linux IA32 par setjmp/longjmp ) et l'autre d'un Sparc32 sous Solaris ( Gestion de contexte pour Solaris Sparc32 par setjmp/longjmp )
La seconde façon consiste à écrire directement la commutation de contexte en code natif pour une machine donnée.L'exemple ( Gestion de contexte pour Linux IA32 (code natif) ) proposé est à destination de Linux et l'architecture IA32 d'Intel (386/486/Pentium etc.et clones..). La méthode proposée sauve tous les registres dans la pile d'un thread et sauve donc le seul pointeur de pile dans le contexte. Ces procédures dépendent de la machine hôte mais aussi des conventions de passage de paramètres entre procédures C, des prologues et épilogues des procédures générés par le compilateur C. Pour les connaitre, il faut analyser le code assembleur engendré par le compilateur ( option -S ). La version proposé est conforme au code généré par le compilateur gcc 3.2
Le choix de l'implantation à utiliser pour FRED est fixé par une macro variable du préprocesseur C qui permet d'inclure l'implantation choisi. (cf le fichier makefile et le début du fichier contextswitch.h )
La gestion des autorisations/inhibitions des interruptions est nécessaire pour plusieurs raisons :
Une procédure de traitement de signal est une procédure C sans résultat à paramètre numéro de signal. On associe un traitant d'interruption à une interruption par FredSignalAttach(). Par défaut à l'initialisation( FredSignalsInit() ), on installe pour les interruptions un traitant par défaut : defaultFredSignalHandler() .
Pour voir la liste des signaux UNIX : "man -S 7 signal"
Sur un monoprocesseur interruptible par des évènements internes ou externes, le mécanisme de base pour assurer l'exclusion mutuelle est d'inhiber temporairement les interruptions. Dans FRED, on gardera cependant la possibilite de tuer le process UNIX (par Ctrl_C ) même en cas de programme en boucle infinie en exclusion mutuelle donc masquée.
FRED n'offre qu'un simple mécanisme de masquage/démasquage des interruptions utilisable via les 2 procédures FredMaskOn() et FredMaskOff(). Les masques utilisés sont initialisés par FredMasksInit().
/* code incorrect */ ....FredMaskOn();....; FredMaskOn();....FredMaskOff();....FredMaskOff();....
Il est alors possible de lancer un décomptage en microsecondes( FredCountDownStart() ) ou de l'arrêter ( FredCountDownStop() ). Dans les deux cas, on récupère la valeur résiduelle du décompte en cours au moment de ces invocations. On peut directement lire la valeur résiduelle par FredCountDownGet() . Par FredCountDownAttach() , on peut attacher un traitant d'interruption à la fin décomptage.
Pour rendre thread safe , les procédures de la bibliothèque standard C, il suffit de les mettre en exclusion mutuelle. Dans le cadre de FRED, cela est fait par inhibition des interruptions( cf. Interface de gestion mémoire et Interface d'entrée/Sortie )
Une fois la commutation de contexte établie, la gestion des threads est relativement simple. Le cycle de vie d'un thread est le suivant :
La libération de la mémoire contenant pile par une procédure s'exécutant dans cette pile engendre des erreurs. Il est nécessaire d'exécuter ce code de libération dans une pile différente. FRED utilise pour cela un thread spécialisé dans le nettoyage de la mémoire leon qui est créé au départ du programme concurrent. Les threads qui se terminent s'inscrivent dans une file de décédés deadQ et réveillent leon.
Le moteur du noyau de thread est donc le mécanisme qui relance systématiquement le thread en tête de la file des prêts readyQ. Si la file est vide, le moteur est en panne. Pour éviter cette situation, on introduit un thread qui ne se termine jamais et ne fait que passer la main aux autres threads. Ce chien de garde watchdog est démarré au lancement de FRED ( FredInitialize())
Le programme FRED démarre comme un programme C standard. FRED est disponible après son initialisation FredInitialize(). Pour que l'on puisse utiliser toute l'API FRED dans la procédure main(), il est nécessaire de lui adjoindre un thread mainThread que l'on pourra interrompre et synchroniser comme tout autre thread.
Enfin, la gestion de la terminaison nécessite la mise en place d'un protocole entre leon qui détruit effectivement les threads et FredWaitTerminate() qui permet au thread principal d'attendre la fin des autres threads (sauf leon et watcdog ).
Pour plus de détails, voir Interface de gestion de threads et Implantation des threads
1.2.17