ALLOCATION DE TÂCHES DÉPENDANTES

ALLOCATION DE TÂCHES DÉPENDANTES

L’état de l’art sur l’ordonnancement de tâches temps réel met en évidence un nombre important de travaux où des ensembles de tâches indépendantes sont considérés. L’hy- pothèse faite par ces modèles est que les tâches ne sont en concurrence que pour l’accès aux processeurs. Elles ne partagent aucune autre ressource (périphériques, mémoire, …). L’étude de tels modèles de tâches peut paraître surprenante car elle ne reflète pas les modèles d’architectures existantes. Pourtant, les modèles de tâches indépendantes sont essentiels pour l’étude des systèmes temps réel car ils permettent de formaliser plus simplement les problèmes d’ordonnancement ou d’allocation des tâches. Le test d’ordonnançabilité pour EDF dans le cas de tâches à échéances implicites proposé par Liu et Layland ( Néanmoins, une fois que les bases algorithmiques ont été posées, il convient d’éten-dre les modèles pour que la représentation des systèmes se rapproche au mieux des ar- chitectures existantes. Les plates-formes multiprocesseurs récentes embarquent pour la plupart des mémoires partagées, ainsi que de nombreux périphériques. Ainsi, les tâches vont pouvoir échanger des données avec le monde extérieur, mais surtout entre elles. C’est la motivation qui nous pousse à nous intéresser à des modèles de tâches partageant des données. Si une tâche est préemptée alors qu’elle utilise des données partagées, ces données peuvent se retrouver dans un état incohérent. Pour résoudre ce problème, les instructions qui utilisent des ressources partagées sont exécutées dans des sections critiques. L’entrée dans ces sections critiques est protégée par un méca- nisme de synchronisation. Un mécanisme simple de synchronisation consiste à poser un verrou lors de l’entrée dans la section critique. Ce verrou doit être commun à toutes les sections critiques utilisant la même ressource. La prise du verrou ne peut se faire que si ce dernier est libre. Dans le cas contraire, l’instance est bloquée en attente de libération de ce verrou.

Le principe de la synchronisation est simple, il doit toutefois être manipulé avec attention. En effet, une tâche de haute priorité peut se retrouver en attente de libéra- tion d’un verrou pour une durée qui peut ne pas être bornée. Ce dernier problème, bien qu’il puisse être acceptable dans le cas d’un ordonnancement classique, pose un souci majeur dans le cas des systèmes temps réel lors de leur analyse. C’est pourquoi des protocoles de synchronisation ont été mis en place afin de définir des règles pour la prise des verrous, et ainsi éviter les inversions de priorités non bornées. En plus du protocole de synchronisation, il est nécessaire de fournir une borne sur le pire temps de blocage que peut subir une tâche. Il devient alors possible de borner le pire temps de réponse de cette tâche, et ainsi d’établir une condition d’ordonnançabilité pour un al- gorithme d’ordonnancement donné. Notre contribution est de proposer un algorithme de partitionnement de tâches dépendantes qui optimise la robustesse temporelle du système en maximisant la marge des tâches.Ce chapitre est organisé de la manière suivante. Dans la section 4.2, nous définis- sons la terminologie et les notations utilisées dans ce chapitre. Dans la section 4.3, nous faisons l’état de l’art des principaux protocoles de synchronisation temps réel multi- processeurs. Dans la section 4.4, nous présentons quelques approches proposées pour le problème du partitionnement de tâches dépendantes. Dans la section 4.5, nous pro- posons une solution de partitionnement qui optimise le critère de robustesse tempo- relle. Nous évaluons cette solution dans la section 4.6. La section 4.7 fait la synthèse de ce chapitre.

Dans cette étude, nous considérons que chaque tâche i peut utiliser un ensemble de ressources R(i) qui lui sont accessibles. Lorsqu’une tâche accède à la ressource Rk, elle entre dans une section critique sk. Le WCET d’une tâche est donc composé d’un ensemble de sections d’exécution indépendante et de sections critiques. Les protocoles de synchronisation décrivent l’entrée dans une section critique par l’utilisation d’un sémaphore ou la prise d’un verrou. Dans le but de ne pas surcharger la description des protocoles de synchronisation, nous dirons qu’une instance peut utiliser une ressource lorsqu’elle est en mesure de mettre en place les mécanismes nécessaires à la synchro- nisation de cette ressource.Avec MPCP, deux types de ressources partagées sont distingués. Les ressources lo- cales sont partagées par des tâches assignées sur le même processeur tandis que les ressources globales sont partagées par des tâches assignées sur des processeurs diffé- rents. La différence avec PCP est qu’une ressource globale RGk a une priorité plafond p(RGk) égale à la somme de la plus haute priorité du système pG et de la priorité de la tâche la plus prioritaire qui peut utiliser cette ressource. Une instance utilisant une ressource globale est exécutée à la priorité plafond de celle-ci.