L'exécution des threads par le processeur virtuel (processus lourd) se fera périodiquement en temps partagé avec 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 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 :
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 "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 :
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 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().
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 correct */ ....PhilMutexLock(&V1);....; PhilMutexLock(&V1);....PhilMutexUnlock(&V1);....PhilMutexUnlock(&V1);....
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.
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 détachés qui sont alors détruit.
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. */ <....> }
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.
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. Interface sémaphore). La suspension se fait via une condition.
Le programme principal initie :
#define NBphilo FredThread philosophe[NBphilo]; FredSemaphore fourchette[NBphilo]; int main ( int argc, char** argv) { int i; PhilInitialize(); for( i=0;i<NBphilo;i++) PhilSemaphoreInit(&fourchette[i],1); for( i=0;i<NBphilo;i++) philosophe[i]= PhilThreadCreate(0, O, ,20000,codephilo,(void*)i); for(i=0;i<NBphilo;i++)PhilThreadJoin(philosophe[i], 0); PhilWaitTerminate(); 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,k; int i = (int)x; for( j=0;j<100;j++){ /* ça pense ..*/ if(i<(NBphilo-1)){ /* un droitier */ PhilSemaphoreP(&fourchette[i]);PhilSemaphoreP(&fourchette[i+1]); /* ça mange ..*/ PhilSemaphoreV(&fourchette[i]);PhilSemaphoreV(&fourchette[i+1]); }else{ /* le gaucher */ PhilSemaphoreP(&fourchette[0]);PhilSemaphoreP(&fourchette[NBphilo-1]); /* ça mange ..*/ PhilSemaphoreV(&fourchette[0]);PhilSemaphoreV(&fourchette[NBphilo-1]); } } return (void*) 0; }
L'implantation de PHIL introduit quelques difficultés par rapport à celle de FRED.
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é. Interface de gestion de listes La priorité est un entier >=0. La priorité maximum est 0.
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 ( Interface d'un échéancier ) 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.
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 d'inversion de priorité. Il est demandé d'implanter une solution par plafonnement 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 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 liste des verrous 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.
Le travail comprend plusieurs actions permettant de faire une démonstration de l'état de la réalisation. Voici un exemple de découpage :
1.2.17