/** \htmlonly \endhtmlonly \author J. Briat \date Janvier 2004 \mainpage PHIL : Noyau temps réel simple PHIL est un gros TP d'implantation d'une version simplifié du standard Posix à partir de la base FRED. Il donne un exemple d'implantation dit N::1 ou en mode utilisateur. Un processus lourd ( process UNIX ici) est vu comme une machine monoprocesseur dont on va partager les ressources (temps d'exécution et mémoire) entre plusieurs threads. Un thread sera simplement l'exécution d'une procédure C. L'exécution des threads par le processeur virtuel (processus lourd) se fera périodiquement en temps partagé avec \b priorité ou au gré des synchronisations entre ces threads. PHIL offre les fonctionnalités primitives d'un noyau temps réel réaliste où les threads sont gérés en temps partagé avec \b priorité. Ses fonctions plus élaborées que celles de FRED sont des extensions des mécanismes de base de FRED. Ces fonctions sont présentées en plusieurs sections : - \ref Spthread : comment créer des threads - \ref Spmutex : comment faire une section critique - \ref Spcond : comment synchroniser des threads - \ref Spinit : comment définir un programme concurrent PHIL - \ref Sputil : comment utiliser PHIL \htmlonly
\endhtmlonly \subsection Spthread Gestion des threads \htmlonly
\endhtmlonly 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 ::PhilRunnable. On rappelle que tout pointeur (T*)étant \b "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. La création d'un thread nécessite de donner de : - une procédure de type ::FredRunnable - un mode \b détaché ou \b joignable - une priorité - une taille de pile - un paramètre de type (void*) La procédure PhilThreadCreate() crée et lance donc un thread ((c.à.d. le met dans la file des threads prêts à s'exécuter). Le type d'un thread influe sur le critère de terminaison du programme concurrent ( \ref Spinit ). Un thread se termine par terminaison normale de sa procédure initiale ou par suicide. La procédure PhilThreadExit() permet à un thread de se terminer en rendant un résultat de type (void*). Un thread peut attendre la fin d'un thread \b joignable et récupérer son résultat par PhilThreadJoin(). Un thread peut connaitre son identité (reférence sur son descripteur (type ::PhilThread)) par la fonction PhilThreadCurrent(). 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 priorité par PhilThreadYield(). \sa Gpthread \htmlonly
\endhtmlonly \subsection Spmutex Exclusion mutuelle \htmlonly
\endhtmlonly PHIL offre un mécanisme d'exclusion mutuelle de type verrou ( ::PhilMutex ). L'usage des mécanismes matériels (inhibition des interruption par exemple) est ainsi réduit à des durées très courtes (implantation des verrous) pour éviter de retarder ou perdre des signaux externes ou bloquer les autres processeurs dans le cas de multiprocesseur. L'exclusion mutuelle repose sur les 2 procédures PhilMutexLock() et PhilMutexUnlock(). Le verrou ne peut être fermé que par un seul thread qui en devient alors propriétaire. Un verrou ne peut être déverrouillé que par son propriétaire. Il est toujours possible d'imbriquer les sections critiques contrôlées par un même verrou. \code /* code correct */ ....PhilMutexLock(&V1);....; PhilMutexLock(&V1);....PhilMutexUnlock(&V1);....PhilMutexUnlock(&V1);.... \endcode Un verrou s'initialise PhilMutexInit() et se libère PhilMutexDestroy() signalant à cette occasion s'il y des threads en attente sur le verrou à ce moment. Les threads en attente sont réveillés et prévenus de la raison de ce réveil. \sa Gpmutex \htmlonly
\endhtmlonly \subsection Spcond File ou condition d'attente \htmlonly
\endhtmlonly Les relations de dépendance et de synchronisation entre threads nécessite de bloquer et réveiller les threads au gré des circonstances. Phil offre le type ::PhilCond qui permet de définir une file d'attente de threads gérée selon la statégie FIFO à priorité. On initialise une condition par PhilCondInit(). Le thread courant peut se bloquer sur une condition PhilCondWait() jusqu'à ce qu'un thread le réveille. Un thread peut réveiller un thread bloqué sur une condition par PhilCondSignal(). Le thread réveillé est le + prioritaire. On peut aussi réveiller tous les threads bloqués par PhilCondBroadcast(). Ces procédures doivent toujours être utilisées en exclusion mutuelle. Le thread courant peut se bloquer sur une condition PhilCondTimedWait() jusqu'à ce qu'un thread le réveille ou qu'une durée limite soit écoulée. Une condition doit s'initialiser par PhilCondInit() et se libérer par PhilCondDestroy() signalant à cette occasion s'il y des threads en attente sur la condition. \sa Gpcond \htmlonly
\endhtmlonly \subsection Spinit Initialisation & terminaison \htmlonly
\endhtmlonly Pour utiliser PHIL, il faut inclure le fichier phil.h pour disposer de toutes les déclaration de types et profils de procédures. La procédure main() du programme doit initialiser les variables statiques de PHIL. C'est le rôle de PhilInitialize(). Puis le programmeur peut initialiser ses propres variables globales et lancer ses threads initiaux, se synchroniser etc.... PhilTerminate() lui permet d'attendre la terminaison des threads de calcul (et des threads de calcul créés par ceux-ci et etc....). Sinon, la procédure main() termine et tout le programme concurrent aussi. La décision de terminaison ignore les threads \b détachés qui sont alors détruit. \code #include int main( int argc, char** argv) {/* PHIL n'est pas utilisable. Seul du code C séquentiel est exécutable */ <....> PhilInitialize(); /* PHIL est partiellement utilisable. On peut créer des threads, intialiser des objets satiques, se synchroniser .... */ <....> PhilTerminate(); /* Attente de la terminaison de tous les threads. A la reprise, PHIL n'est plus utilisable. Seul du code C séquentiel est exécutable. */ <....> } \endcode N'importe quel thread peut terminer brutalement le programme concurrent par PhilAbort() en passant en paramètre une chaine de caractère précisant la raison de l'arrêt brutal. \sa Gpinit \htmlonly
\endhtmlonly \section Sputil Exemples d'utilisation \htmlonly
\endhtmlonly L'exclusion mutuelle par verrou et les conditions sont suffisantes pour reconstruire des opérateurs de synchronisation classique comme le sémaphore de Dijkstra. On peut ensuite traiter un problème classique de synchronisation comme les N philosophes. \htmlonly
\endhtmlonly \subsection Spsema Un exemple d'utilisation : le sémaphore \htmlonly
\endhtmlonly Un sémaphore est un simple sac de jetons que l'on prend ou remet 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 thread le + prioritaire 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 PhilSemaphoreInit() et détruit via PhilSemaphoreDestroy(). Il peut ensuite être utilisé pour prendre PhilSemaphoreP() ou déposer un jeton PhilSemaphoreV() L'implantation nécessite un compteur et une queue de threads en attente (cf. ::PhilSemaphore). 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 atomique et se font donc verrouillés. (cf. \ref Gpsema). La suspension se fait via une condition. \htmlonly
\endhtmlonly \subsection Spphilo Les N philosophes \htmlonly
\endhtmlonly Le programme principal initie : - les sémaphores représentant les fourchettes - les philosophes \code #define NBphilo 5 FredThread philosophe[NBphilo]; FredSemaphore fourchette[NBphilo]; int main ( int argc, char** argv) { int i; PhilInitialize(); for( i=0;i \endhtmlonly \section ISimpl Implantation de PHIL \htmlonly
\endhtmlonly L'implantation de PHIL introduit quelques difficultés par rapport à celle de FRED. - La première porte sur la gestion des priorités. Cela se traduit par l'utilisatioin d'une gestion de liste triée par priorité \ref Sprio . - La seconde porte sur une gestion plus fine du temps. On doit en effet gérer le temps partagé, la date (cf PhilNow() ) et des attentes de durée bornée (cf PhilCondTimedWait() ). Ceci implique la gestion d'un échéancier \ref Sech . - Le dernier problème porte sur l'évitement du phénomène dit \b inversion \b de \b priorité. La solution à implanter est celle du \b plafonnement \b dynamique. L'implantation de PHIL s'appuie sur des modules intermédiaires ou de modification des modules de FRED. \htmlonly
\endhtmlonly \subsection Sprio Gestion de listes triées \htmlonly
\endhtmlonly Il suffit de modifier la gestion de liste de FRED pour en faire une gestion de liste triée par priorité. On retire toujours en tête mais on trie à l'insertion c'est à dire qu'on trie par priorité et qu'on insère un thread en queue de la sous-liste de priorité égale à sa priorité. \ref Gprio La priorité est un entier >=0. La priorité maximum est 0. \htmlonly
\endhtmlonly \subsection Sech Gestion d'un échéancier \htmlonly
\endhtmlonly La gestion d'un échéancier se ramène à une gestion de date et une gestion d'échéances. Une échéance est une action (::PhilEventHandler) à effectuer à une date donnée. Ainsi, la fin d'un quantum est une échéance tout comme le réveil d'un thread sur une condition. Le paramètre de l'action est le descripteur (::PhilEvent) de l'échéance qui se termine. L'implantation de l'échéancier ( \ref Gech ) s'appuiera sur la définition du décompteur que l'on trouvera dans FRED. La gestion de la date implique une utilisation permanente du décompteur. La gestion de la date est relativement simple : la date courante est la date de chargement du décompteur + temps écoulé depuis cette date c'est à dire la valeur de chargement du compteur - le temps résiduel de décompage. A chaque interruption de décomptage, on relance un décomptage. 2 variables d'état suffisent à mémoriser la date de lancement du décomptage et la valeur de décomptage. Si seule la date était à gérer, il suffirait de charger le décompteur avec la valeur maximum. Ce n'est plus le cas lorsqu'il existe des échéances. Le décompteur doit être chargé avec la valeur exacte qui correspond à l'échéance la plus proche dans le futur de façon à pouvoir exécuter l'action associée à l'échéance. A l'interruption de décomptage correspondant à cette échéance, on doit exécuter l'action et relancer le décomptage s'il y des échéances postérieures. L'action peut aussi avoir rajouter de nouvelles échéances. Un échéancier va donc se présenter comme une liste triée par date croissante de cellules décrivant une échéance ou plutot une liste triée par date croissante de sous listes d'échéances tombant à la même date. Le décompteur sera toujours relancé à partir de la tête de liste. Sur une interruption de fin de décomptage, toutes les actions échues seront exécutées. Des échéances peuvent être annulées avant la date prévue. Il faut les retirer de l'échéancier. On doit éventuellement relancer le décomptage si cette échéance était la + proche. \htmlonly
\endhtmlonly \subsection SIpthread Gestion par priorité des threads \htmlonly
\endhtmlonly La gestion par priorité des threads implique de maintenir la propriété que le thread actif est le + prioritaire des threads prêts. Ceci implique que lors de tout réveil de thread, on évalue la priorité du thread courant contre la priorité du thread réveillé pour savoir si le processeur doit être donné au réveillé plutot que conservé par le thread actif. Lorsqu'un verrou est relaché, ce verrou est donné au + prioritaire des demandeurs qui peut être aussi + prioritaire que le libérateur du verrou. Cette situation implique aussi une commutation de thread. La complication principale provient du phénomène \b d'inversion \b de \b priorité. Il est demandé d'implanter une solution par \b plafonnement \b dynamique. Le principe est de détecter une situation de conflit entre un thread propriétaire du verrou et un thread demandant le verrou. Ce conflit peut se produire lors d'un PhilMutexLock() fait par le thread + prioritaire ou lors d'un PhilCondSignal() ou PhilCondBroadcast() fait par le thread - prioritaire. Dans ce cas, il réveille un(tous les) thread(s) qui redemandent le verrou. La solution est de hausser la priorité du thread propriétaire au niveau de celle du + prioritaire pour accélérer sa sortie de l'exclusion mutuelle. Lorsque le conflit est détecté par le thread le plus prioritaire, celui-ci se bloque après avoir hausser la priorité du propriétaire. Si celui-ci est dans la file des prêts, il peut tourner s'il est remonté en tête des prêts. Ce n'est pas toujours le cas car il peut être aussi en attente sur un autre verrou ou une condition. La aussi, il doit être reclassé dans la liste d'attente. Il est donc \b nécessaire de connaitre la file dans laquelle se trouve un thread (chainage inverse). L'accroisement de priorité n'est pas la seule difficulté. C'est aussi le cas du rétablissement de la priorité antérieure. En effet, du fait de l'inclusion possible des sections critiques et du caractère dynamique des conflits d'inversion, il est nécessaire de recalculer la priorité d'un thread à la libération d'un verrou. Pour ce faire, il faut gérer par thread la \b liste \b des \b verrous \b pris par ce thread. Sa priorité doit être la priorité maximum des threads en attente sur ces verrous. A la libération d'un verrou, on doit parcourir la liste des verrous pris par le thread pour calculer la priorité maximum des threads en attente. \htmlonly
\endhtmlonly \section ISplan Organisation du travail \htmlonly
\endhtmlonly Le travail comprend plusieurs actions permettant de faire une démonstration de l'état de la réalisation. Voici un exemple de découpage : - \b action1.1 : Modifier FRED pour implanter l'API PHIL ( \ref Gpthread ). La statégie de gestion du processeur de FRED est inchangée. Il s'agit d'implanter le verrou récursif, la condition (sans le PhilCondTimedWait() ), la création et la synchronisation de terminaison des threads. - \b action1.2 : Modification de la gestion de liste FRED pour faire la gestion de liste triée au sens de PHIL ( \ref Gprio ) - \b action2.1 <== Fusion action1.1 et action1.2. On obtient une gestion de thread par priorité sans traitement de l'inversion de priorité et sans le PhilCondTimedWait() - \b action2.2 Réalisation de la gestion d'échéancier ( \ref Gech ) à partir du décompteur de FRED et de la gestion de liste triée de PHIL - \b action3.1 <== Fusion action2.1 et action2.2 En traitant la fin de quantum comme une fin d'échéance et le réveil d'une condition sur fin d'échéance, on obtient un noyau PHIL sans traitement de l'inversion de priorité. - \b action3.2 Extension de action2.1 pour traiter l'inversion de priorité. - \b action4 <== Fusion action3.1 et 3.2 Le noyau PHIL complet Il y a une activité parallèle et continue de développement des tests destinés à vérifier la correction de la réalisation. Indépendemment des tests unitaires de fonctions, on réalisera un test de l'API PHIL via l'implantation d'exemples \b classiques : - producteur consommateur - lecteur rédacteur - N philosophes (directement avec verrous et conditions) Les tests d'échéancier et de priorités sont laissés à la discrétion des implémenteurs. \warning La fusion est une opération délicate qui demande à avoir été préparée!!! */ // DON'T REMOVE /*----------------------------- END OF MANUAL ---------------------------- ------------------------------------------------------------------------ ------------------------------------------------------------------------*/ // Group definition /*---------------------------------------------------------------------*/ // Description of modules. /*---------------------------------------------------------------------*/ /** \defgroup Gphil Interface PHIL \brief Ce module définit l'interface applicative de PHIL */ /** \defgroup Gpinit Interface d'initialisation & terminaison \ingroup Gphil \brief Ce module définit comment initier et terminer un programme concurrent PHIL. Pour savoir comment l'utiliser, voir \ref Spinit */ /** \defgroup Gpthread Interface de gestion de threads \ingroup Gphil \brief Ce module définit comment créer des threads, terminer un thread ou un programme concurrent et connaitre le thread courant. Pour savoir comment l'utiliser, voir \ref Spsema \ref Spphilo */ /** \defgroup Gpmutex Interface d'exclusion mutuelle \ingroup Gphil \brief Ce module définit comment créer des verrous, les prendre ou les libérer. Pour savoir comment l'utiliser, voir \ref Spsema \ref Spphilo */ /** \defgroup Gpcond Interface de gestion des conditions d'attente \ingroup Gphil \brief Ce module définit comment se bloquer ou réveiller dans une file d'attente. Pour savoir comment l'utiliser, voir \ref Spsema \ref Spphilo */ /** \defgroup Gpsema Interface sémaphore \brief Une implémentation classique du classique sémaphore de Dijkstra. */ /** \defgroup Gpimpl Implémentation de PHIL \brief Ce module regroupe les sous modules nécessaire à la mise en oeuvre de PHIL. */ /** \defgroup Gprio Interface de gestion de listes \ingroup Gpimpl C'est une gestion de liste circulaire doublement chaînée triée par priorité croissante. La priorité est un entier >=0. La priorité maximum est 0. */ /** \defgroup Gech Interface d'un échéancier \ingroup Gpimpl */