Brevet FR2997773A1 — publié le 20140509

PROCEDE D'ORDONNANCEMENT AVEC CONTRAINTES D'ECHEANCE, EN PARTICULIER SOUS LINUX, REALISE EN ESPACE UTILISATEUR L'invention porte sur un procédé permettant la réalisation d'un ordonnancement monoprocesseur, multiprocesseur ou multicceurs de tâches 5 avec contraintes d'échéances. Ordonnanceur de tâches avec contraintes d'échéances signifie que chaque tâche possède un temps de terminaison qu'elles ne doit pas dépasser. L'ordonnancement réalisé supporte l'exécution sur un seul ou plusieurs processeurs. Il est réalisé sous Linux, ou tout autre système d'exploitation supportant la norme POSIX, et plus particulièrement son 10 extension POSIX.1c, mais n'est pas intégré au noyau : il fonctionne en effet en espace utilisateur. L'espace utilisateur est un mode de fonctionnement pour les applications utilisateur, par opposition à l'espace noyau qui est un mode de fonctionnement superviseur qui dispose de fonctionnalités avancées ayant tous 15 les droits, en particulier celui d'accéder à toutes les ressources d'un microprocesseur. La manipulation des ressources est néanmoins rendue possible en espace utilisateur par des fonctionnalités dites API (« Application Programming Interface », c'est-à-dire Interfaces de Programmation d'Applications), qui elles-mêmes s'appuient sur l'utilisation de pilotes 20 périphériques. Le développement d'une solution en espace utilisateur rend possible et facilite le développement d'ordonnanceurs à contraintes temporelles par rapport à -une intégration directe dans le noyau du système d'exploitation qui est rendue très difficile par sa complexité. Un autre avantage est d'apporter une stabilité accrue car une erreur d'exécution en espace utilisateur n'entraîne 25 pas de conséquence grave pour l'intégrité du reste du système. Pour réaliser un ordonnancement en espace utilisateur, le procédé de l'invention s'appuie en particulier sur les mécanismes définis par la norme POSIX (« Portable Operating System interface - X », c'est-à-dire « interface portable pour les systèmes d'exploitation », le « X » exprimant 30 l'héritage Unix) et son extension POSIX.1c, et notamment sur la structure de tâche POSIX, les threads POSIX (« pthreads ») et les API de gestion de tâche POSIX. Il convient de rappeler qu'un processus est une instance de programme en cours d'exécution, une « tâche » est un découpage d'un processus et un « thread » est la réalisation d'une tâche sous Linux aux moyen des API POSIX ; un thread ou tâche ne peut pas exister sans processus, mais il peut y avoir plusieurs threads ou tâches par processus. On pourra se rapporter à ce propos à l'ouvrage de Robert Love « LINUX system programming », O'Reilly, 2007. Linux est un système où la gestion du temps est dite à « temps partagé », par opposition à une gestion « temps réel ». Dans ce type de gestion, plusieurs facteurs liés au fonctionnement du système comme le partage des ressources, la gestion des entrées/sorties, les interruptions, l'influence de la mémoire virtuelle, etc. entraînent des incertitudes temporelles sur les temps d'exécution des tâches. Dès lors, il n'est pas possible de garantir une solution temps réel « dur » (en anglais « hard real time »), c'est-à-dire où l'exécution de chaque tâche est remplie dans des limites temporelles strictes et inviolables. La réalisation de l'ordonnanceur proposé convient néanmoins pour des systèmes temps réel dit « souple » (en anglais « soft real time »), ou « avec contraintes d'échéance », qui acceptent des variations dans le traitement des données de l'ordre de la seconde au maximum. C'est le cas d'un grand nombre d'applications temps réel, par exemple multimédia. N'étant pas nativement un système temps réel, plusieurs solutions techniques sont cependant possibles pour rendre le noyau Linux compatible avec les contraintes temps réel. La solution la plus courante consiste à lui associer un noyau temps réel auxiliaire disposant d'un véritable ordonnanceur temps réel (RT Linux, RTAI, XENOMAI). Ce noyau temps réel auxiliaire est prioritaire et traite directement les tâches temps réel. Les autres tâches (non temps réel) sont déléguées au noyau standard Linux qui est 25 considéré comme une tâche (ou un travail) de fond moins prioritaire. Cependant, le développement d'un ordonnanceur spécifique intégré au noyau est très difficile puisqu'il nécessite une connaissance approfondie du noyau et implique des développements noyau lourds, avec toute la complexité et instabilité que cela entraîne. Par ailleurs, les extensions temps réel Linux 30 sont supportées par un nombre plus réduit de plateformes. La solution proposée permet une réalisation en espace utilisateur de ce fait plus simple, plus stable et applicable à n'importe quelle plateforme supportant un noyau Linux standard. Cette approche ne permet pas de garantir les contraintes temps réel dures, mais simplifie considérablement le développement d'un ordonnanceur tout en convenant pour les applications temps réel souple (la grande majorité des applications). Un procédé d'ordonnancement selon l'invention convient en particulier à la mise en oeuvre de politiques d'ordonnancement orientées faible consommation, par exemple une politique EDF (« earliest deadline first », c'est-à-dire de priorité à l'échéance la plus proche) - qui est un type particulier d'ordonnancement avec contraintes d'échéances - avec changement dynamique de tension-fréquence (DVFS) afin de minimiser la consommation, ce qui est important dans les applications embarquées. Voir à ce propos les articles suivants : - R. Chéour et al. « EDF scheduler technique for wireless sensors networks: case study » Fourth international Con ference on Sensing Technology, 3 - 5 juin 2010, Lecce, Italie; - R. Chéour et al. « Exploitation of the EDF scheduling in the wireless sensors networks », Measurement Science Technology Journal (10P), Special Issue on Sensing Technology: Devices, Signais and Materials, 2011. Il existe de nombreux travaux sur l'ordonnancement faible consommation, mais qui restent pour l'essentiel théoriques et ne sont pratiquement jamais intégrés à un système d'exploitation à cause de la complexité de ce travail. La solution proposée, comme elle est entièrement réalisée en espace utilisateur, facilite grandement cette intégration. Un objet de l'invention est donc un procédé d'ordonnancement de tâches avec contraintes d'échéances, basé sur un modèle de tâches périodiques indépendantes et réalisé en espace utilisateur, dans lequel : - chaque tâche à ordonnancer est associée à une structure de données, définie en espace utilisateur et contenant au moins une information temporelle (échéance et/ou période) et une information indicative d'un état d'activité de la tâche, ledit état d'activité étant choisi dans une liste comprenant au moins : - un état de tâche en exécution ; - un état de tâche en attente de la fin de sa période d'exécution ; et - un état de tâche prête à être exécutée, en attente d'une condition de reprise; - au cours de son exécution, chaque tâche modifie ladite information indicative de son état d'activité et le cas échéant, en fonction d'une politique d'ordonnancement prédéfinie, appelle un ordonnanceur qui est exécuté en espace utilisateur ; - à chaque appel, ledit ordonnanceur : - établit une file d'attente des tâches prêtes à être exécutées, en attente d'une condition de reprise; trie ladite file d'attente en fonction d'un critère de priorité prédéfini ; - si nécessaire, préempte une tâche en exécution en lui envoyant un signal la forçant à passer dans ledit état de tâche prête à être exécutée, en attente d'une condition de reprise ; et envoie ladite condition de reprise au moins à la tâche se trouvant en tête de ladite file d'attente Selon différents modes de réalisation du procédé de l'invention : - Ladite politique d'ordonnancement peut être une politique préemptive, par exemple choisie parmi une politique de type EDF et ses dérivés tels que DSF (« Deterministic Stretch to Fit », c'est-à-dire « extension et ajustement déterministe de la fréquence ») et AsDPM (« Assertive Dynamic Power Management », ou « politique assertive de gestion dynamique des modes repos »), RM (« Rate Monotonic », ou « ordonnancement à taux monotone »), DM (« Deadline Monotonic » ou « ordonnancement en fonction de l'échéance »), LLF (« Least Laxity First » ou ordonnancement en fonction de la laxité la plus faible). - Le procédé peut être mis en oeuvre dans une plateforme multiprocesseur, ladite structure de données comprenant également une information relative à un processeur auquel la tâche correspondante est affectée, et dans lequel ledit ordonnanceur affecte à un processeur du système chaque tâche prête à être exécutée. - Ledit ordonnanceur peut modifier la fréquence d'horloge et la tension d'alimentation du ou d'au moins un processeur en fonction d'une politique DVFS. - Le procédé peut comporter une étape d'initialisation, au cours de laquelle : - les tâches à ordonnancer sont créées, affectées à un même processeur et placées dans un état d'attente d'une condition de reprise, une variable globale dite de rendez-vous étant incrémentée ou décrémentée lors de la création de chaque dite tâche ; - lorsque ladite variable de rendez-vous prend une valeur prédéfinie indiquant que toutes les tâches ont été créées, ledit ordonnanceur est exécuté pour la première fois. - Ladite structure de données peut contenir également des informations indicatives d'un pthread associé à ladite tâche et à son temps d'exécution dans le pire cas. Le procédé peut être exécuté sous un système d'exploitation compatible avec une norme POSIX.1c, qui peut en particulier être un système Linux. Dans ce cas : - A chaque appel de l'ordonnanceur, un «pthread» est crée pour assurer son exécution. - Le procédé peut comporter l'utilisation d'un MUTEX pour assurer l'exécution d'une seule instance à la fois de l'ordonnanceur. - L'affectation d'une tâche à un processeur peut être effectuée au moyen de l'API CPU Affinity. Un autre objet de l'invention est un produit programme d'ordinateur pour la mise en oeuvre d'un procédé d'ordonnancement selon l'une des revendications précédentes. D'autres caractéristiques, détails et avantages de l'invention ressortiront à la lecture de la description faite en référence aux dessins annexés donnés à titre d'exemple et qui représentent, respectivement : - La figure 1, le principe de réalisation d'un procédé d'ordonnancement selon l'invention en espace utilisateur Linux ; - La figure 2, un exemple d'un ensemble de tâches périodiques indépendantes ; et - La figure 3, un diagramme des états et des transitions des tâches applicatives dans un procédé d'ordonnancement selon l'invention. Le principe de réalisation d'un ordonnanceur en espace utilisateur selon un mode de réalisation de l'invention, basé sur un système d'exploitation Linux, est illustré à la figure 1. Une application est vue comme un ensemble de tâches à ordonnancer 2. L'ordonnanceur 1 contrôle l'exécution de ces tâches au moyen de trois fonctions spécifiques (référence 3) : « prempt(Task) », « resume(Task) » et « run on(Task, CPU) ». Ces fonctions - dont les noms sont arbitraires et donnés uniquement à titre d'exemple non limitatif - permettent la préemption d'une tâche, la reprise d'une tâche et l'allocation d'une tâche à un processeur, respectivement. Elles s'appuient sur l'utilisation de fonctionnalités fournies par les API Linux (référence 5) permettant le contrôle des tâches et des processeurs depuis l'espace utilisateur. Pour son fonctionnement, l'ordonnanceur doit disposer d'informations spécifiques qui découlent du modèle de tâches utilisé. Pour un modèle de tâches périodiques et indépendantes, il s'agit au moins d'informations relatives à l'échéance de chaque tâche, sa période et son état d'activité ; d'autres informations temporelles peuvent également être fournies : pire cas de temps d'exécution (WCET, de l'anglais « Worst Case Execution Time), échéance ultérieure (c'est-à-dire : temps courant plus échéance - pour éviter une confusion avec l' « échéance ultérieure », « échéance » est parfois appelée « échéance absolue »), etc. Dans le cas d'une plateforme multiprocesseur, l'ordonnanceur nécessite également une information indicative du processeur auquel la tâche est affectée. En outre, chaque tâche est associée à un thread POSIX («pthread»), qui doit également être connu de l'ordonnanceur. D'autres informations susceptibles d'être nécessaires à l'ordonnanceur sont : un MUTEX associé à la tâche, une condition associée à la tâche, un identifiant Linux de la tâche. Le meilleur cas du temps d'exécution (BCET, de l'anglais « Best Case Execution Time ») et loe temps d'exécution effectif (AET, de l'anglais « Actual Execution Time ») sont des informations qui, sans être indispensables pour réaliser l'ordonnancement, sont très utiles pour la mise au point car ils permettent (en particulier l'AET) de fixer le temps d'exécution d'une tâche (le temps d'exécution d'une tâche varie normalement d'une exécution à l'autre). Cela facilite la vérification de l'ordonnancement en permettant de le comparer à des résultats de simulations (avec des tâches ayant les mêmes paramètres et surtout exactement les mêmes temps d'exécution). Dans la structure de tâche standard POSIX Linux (pthread) ces informations ne sont pas accessibles en espace utilisateur. Pour cette raison, la mise en oeuvre de l'invention nécessite une extension de cette structure de tâche, par la création d'un type personnalisé à l'aide d'une structure de données. Le modèle applicatif est constitué de tâches périodiques et indépendantes. Un modèle de tâches périodiques se réfère à la spécification d'ensembles homogènes de travaux (« jobs ») qui se répètent à des intervalles périodiques ; un « travail » est une forme particulière de tâche, et plus précisément une tâche indépendante dont son exécution est strictement indépendante des résultats des autres « travaux ». Un modèle de tâches indépendantes se réfère à un ensemble de tâches pour lequel l'exécution d'une tâche n'est pas subordonnée à la situation d'une autre. Ce modèle supporte l'exécution synchrone et asynchrone de tâches, il est applicable dans un grand nombre d'applications réelles qui doivent respecter des contraintes temporelles. La connaissance des caractéristiques et contraintes temporelles des tâches (échéance, période, pire temps d'exécution, etc.) est donc nécessaire pour appliquer ce type d'ordonnancement. Comme expliqué plus haut, ces informations sont rajoutées dans une structure spécifique qui étend le type de tâche standard sous Linux. La figure 2 illustre un modèle applicatif de tâches périodiques et indépendantes comprenant quatre tâches Ti - T4. Les tâches Ti et T2 doivent s'exécuter avant leur échéance (« deadline » DDLN) de 21 ms (millisescondes), T3 avant son échéance de 31 ms et T4 avant son échéance de 40 ms. Chaque tâche s'exécute en un temps effectif AET (« Actual Execution Time ») f, qui est compris entre une valeur minimum BCET (« Best Case Execution Time ») et une valeur maximum WCET (« Worst Case Execution Time »). Au terme de son exécution, une tâche se met en attente jusqu'à atteindre sa période où elle devient à nouveau prête pour réexécution. Ainsi, une tâche prend à chaque instant un état parmi les suivants : un état de tâche en exécution ; un état de tâche en attente de la fin de sa période d'exécution ; et un état de tâche prête à être exécutée, en attente d'une condition de reprise; auxquels on peut ajouter un état de tâche inexistante, avant son activation. L'exemple de la figure 2 se réfère en particulier à une application vidéo où chacune des quatre tâches correspond à un traitement particulier d'une image. Ces quatre tâches sont donc répétées toutes les 40 ms (période) afin de pouvoir traiter 25 images par seconde. Une ou plusieurs files d'attente sont utilisées pour mémoriser les tâches. Au moins une file d'attente est nécessaire pour la réalisation d'un ordonnancement à contraintes d'échéances, pour mémoriser la liste des tâches prêtes. Une priorité est également associée à chaque tâche pour définir leur ordre d'exécution. Le critère de priorité dépend de la politique d'ordonnancement. Pour la politique EDF (« Earliest Deadline First », c'est-à-dire priorité à l'échéance la plus proche) par exemple, le critère de priorité est la proximité de l'échéance : la tâche ayant l'échéance la plus proche est la plus prioritaire. La file des tâches prêtes est généralement triée par ordre de priorité décroissante. Le critère de priorité considéré ici est différent des critères de priorité utilisés dans les ordonnanceurs Linux natifs (temps partagé). L'ordonnanceur est appelé à des instants précis, appelés instants d'ordonnancement, qui sont déclenchés par les tâches elles-mêmes à des moments caractéristiques de leur exécution. Ces moments sont appelés des évènements de tâche (référence 2 sur la figure 1), ils correspondent par exemple à leur activation (« onActivate »), leur fin d'exécution (« onBlock »), leur réactivation (« onUnBlock ») ou leur terminaison (« onTerminate ») - ces noms étant arbitraires et donnés uniquement à titre d'exemple non limitatif. Les évènements sont déclenchés, aux moments adéquats de l'exécution d'une tâche applicative, par des appels à des fonctions « onActivate() », « onBlock() », « onUnBlock() », « onTerminate() », insérés dans son code. Chaque évènement de tâche met à jour les champs de la structure de tâche pour la tâche concernée (état, échéance ultérieure, période, etc.) et appelle l'ordonnanceur si nécessaire. L'appel ou non de l'ordonnanceur par un évènement de tâche dépend de la politique d'ordonnancement. Pour une politique EDF par exemple, l'ordonnanceur est appelé sur les évènements « onActivate », « onBlock » et « onUnBlock ». L'évènement « onActivate » correspond à la création d'une tâche. Il marque le passage de l'état « inexistante » à « prête ». Pour des raisons de synchronisation à la création des tâches (expliquées en 15.), l'évènement onActivate incrémente, à la fin de son exécution, une variable « rendez-vous », puis met la tâche en attente d'une condition d'activation de l'ordonnanceur, par exemple en appelant la fonction « pthread_cond_wait » de l'API « Pthread Condition Variable » de la norme POSIX.1c. L'évènement « onBlock est » déclenché lorsqu'une tâche termine son exécution effective (AET). Elle passe alors à l'état « en attente » où elle se met en attente jusqu'à atteindre sa période. Lorsqu'elle atteint sa période, la tâche déclenche l'évènement « onUnBlock », qui la fait passer à l'état « prêt », puis la met en attente d'une condition de reprise, par exemple en appelant la fonction POSIX pthread_cond_wait. Cette condition sera signalée par l'ordonnanceur au moyen de la foncion « pthread_cond_broadcast » qui appartient elle aussi à l'API « Pthread Condition Variable » de la norme POSIX.1c. A tout moment de son exécution, une tâche peut être préemptée par une autre tâche devenue plus prioritaire (dans le cas d'un algorithme EDF, parce que son échéance est devenue plus proche de celle de la tâche en cours d'exécution). La préemption d'une tâche la fait passer de l'état « en exécution » à « prête ». Réciproquement, la tâche qui reprend à la suite d'une préemption passe de l'état « prête » à l'état « en exécution ». Les transitions entre états déclenchées par les événements de tâches sont illustrées par la figure 3. Pour éviter les phénomènes d'inter blocage, l'ordonnanceur n'est pas appelé directement par les évènements de tâches mais par l'intermédiaire d'un «pthread». En d'autres termes, la fonction qui réalise un événement de tâche (onActivate, onBlock, onUnBlock, onTerminate) appelle une autre fonction « cal/ scheduler» (nom donné à titre d'exemple non limitatif), qui crée un «pthread» d'ordonnancement pour exécuter I 'ordonnanceur. A chaque appel, l'ordonnanceur effectue, au moyen d'une fonction principale « select » (nom donné à titre d'exemple non limitatif) les actions suivantes : établissement d'une file d'attente des tâches prêtes, tri de la file d'attente par ordre de priorité décroissante (tâche la plus prioritaire en début de liste), préemption des tâches non prioritaires en cours d'exécution, allocation des tâches éligibles aux processeurs libres et démarrage des tâches éligibles par envoi d'une condition de reprise. La détermination des tâches éligible nécessite la connaissance par l'ordonnanceur de l'état de toutes les tâches existantes. La liste d'actions donnée ici correspond à un ordonnancement EDF, mais peut être modifiée - et en particulier enrichie - pour la réalisation d'autres politiques d'ordonnancement. Du fait de l'exécution multitâche et multiprocesseur, plusieurs instances de l'ordonnanceur pourraient être appelées à s'exécuter en même temps . Pour empêcher une telle éventualité, un Mutex (de l'anglais « MUTual Exclusion device », c'est-à-dire dispositif d'exclusion mutuelle) est utilisé pour protéger certaines variables partagées comme la file d'attente des tâches prêtes. Le Mutex est verrouillé au début de l'exécution de l'ordonnanceur, puis libéré à la fin de l'appel à l'ordonnanceur. Ce procédé garantit qu'une seule instance de l'ordonnanceur ne s'exécute à la fois, ce qui permet la modification sans risque des variables partagées. La première exécution de l'ordonnanceur intervient juste après la création des tâches. Afin de garantir le contrôle des tâches par l'ordonnanceur, une synchronisation doit être réalisée pour être sûr que toutes les tâches ont bien fini d'être créées avant d'exécuter l'ordonnanceur et que les tâches ne démarrent pas leur exécution tant que l'ordonnanceur ne leur en a pas donné l'ordre. Pour cela, tout d'abord, une variable globale de type rendez- vous est initialisée à 0 avant la création des tâches. Ensuite, toutes les tâches sont créées et placées sur le premier processeur du système. Au tout début de leur création, en d'autres termes à l'exécution l'évènement onActivate(), chaque tâche incrémente la variable « rendez-vous » puis suspend immédiatement son exécution en se mettant en attente d'une condition de reprise (utilisation de la fonction POSIX « pthread_cond_wait »). Lorsque la valeur de la variable « rendez-vous » est égale au nombre de tâches, l'ordonnanceur peut être exécuté. Au cours de cette exécution, l'ordonnanceur reprend l'exécution des tâches éligibles en leur signalant leur condition de reprise (fonction « pthread_cond_broadcast »). Pour contrôler l'exécution des tâches applicatives, l'ordonnanceur nécessite l'utilisation de deux fonctions spécifiques pour la suspension et la reprise d'une tâche, appelées respectivement « preempt(Task) » et « resume(Task) » sur la figure 1 (référence 3), ces noms étant donnés uniquement à titre d'exemple non limitatif. La fonction preempt(Task) se base sur l'utilisation de l'API « Signal » de la norme POSIX. Pour préempter une tâche, le signal SIGUSR1 est envoyé au pthread correspondant (fonction POSIX « pthread_kill »). Le gestionnaire de signal associé (« sigusr1 ») met la tâche en attente d'une condition de reprise (« pthread_cond_wait ») dès la réception du signal. Il existe une condition de reprise pour chaque tâche de l'application. La fonction resume(Task) signale la condition de reprise adéquate à la tâche concernée pour reprendre son exécution. Elle est donc strictement équivalente à appeler la fonction Linux pthread_cond_broadcast ; en fait, la création d'une fonction spécifique se justifie essentiellement pour des raisons de lisibilité du code. Ce mécanisme exploite le fait qu'en pratique, le gestionnaire de signal SIGUSR1 est exécuté par le «pthread» Linux qui reçoit le signal. Ainsi, le gestionnaire de signal peut identifier le «pthread» à suspendre (nécessaire pour envoyer la condition d'attente au «pthread» concerné par la fonction pthread_cond_wait) en comparant par exemple son propre identifiant de processus (tid) avec celui de tous les « pthreads » de l'application. Il importe de noter que l'ordonnanceur n'utilise pas les mécanismes de préemption et reprise de tâche fournis par le noyau, car ces derniers ne sont pas accessibles en espace utilisateur. Pour contrôler l'exécution des tâches applicatives dans une plateforme multiprocesseur, l'ordonnanceur nécessite une fonction explicite permettant de fixer l'exécution d'une tâche sur un processeur donné. Bien qu'il existe une API pour le contrôle des «pthread» Linux par les processeurs d'une plateforme multiprocesseur (« CPU affinity »), il n'existe pas de fonction spécifique pour l'allocation d'une tâche sur un processeur. La réalisation de cette fonction (indiquée par « run on » sur la figure 1, référence 3, ce nom étant donné à titre d'exemple non limitatif) affecte le processeur « CPU » à l'exécution de la tâche « Task » en s'appuyant sur l'API Linux « CPU affinity ». Ceci se base sur la spécification du processeur CPU (uniquement) dans le masque d'affinité de la tâche Task, ce masque d'affinité est ensuite affecté à la tâche (par la fonction pthread_setaffinity_np de l'API « CPU affinity »). Ensuite, pour garantir que l'ordonnanceur n'exécute jamais plus d'une tâche par processeur, on empêche toutes les autres tâches applicatives d'utiliser le processeur CPU. On vérifie par ailleurs qu'une tâche n'est jamais affectée à plus d'un seul processeur. Une fonction spécifique « change freq » (nom donné uniquement à titre d'exemple non limitatif) est utilisée dans le cas d'un ordonnanceur utilisant les techniques DVFS pour contrôler le changement dynamique de tension/fréquence des processeurs (figure 1, référence 3). Cette fonction utilise une API Linux appelée « CPUFreq » qui permet de changer la fréquence de chaque processeur par l'intermédiaire du système de fichier virtuel « sysfs ». Il suffit par exemple d'écrire la fréquence désirée dans un fichier - le fichier « /sysklevices/system/cpu/cpuO/cpufreq/scaling setspeed » sous Linux - pour modifier la fréquence du processeur O. L'ordonnanceur peut utiliser la fonction change freq pour permettre la modification de la fréquence en l'écrivant dans le système de fichier. Il nécessite par ailleurs d'utiliser préalablement le gouverneur « Userspace » qui est le seul mode DVFS sous Linux qui permette à un utilisateur ou à une application de changer la fréquence processeur à volonté. « Userspace » est un des cinq gouverneurs DVFS Unix et son nom indique que la fréquence (et donc la tension) peuvent être modifiées à volonté par l'utilisateur. Une technique possible d'ordonnancement à faible consommation consiste à exploiter le « slack » dynamique (temps fourni par une tâche après son exécution) pour ajuster la fréquence et la tension de fonctionnement du ou des processeurs (DVFS) afin d'économiser l'énergie tout en offrant des garanties de délai. Par exemple, l'ordonnanceur de l'invention a été appliqué à la réalisation d'un ordonnancement de type « DSF » (« Deterministic Stretch-to-Fit », dans lequel la fréquence des processeurs (et donc la tension, qui en dépend) est recalculée à chaque événement d'ordonnancement, en utilisant le temps d'exécution réel (AET - « Actual Execution Time ») pour les tâches accomplies et le pire délai d'exécution (WCET - « Worst Execution Time ») pour les autres, pour allouer le temps de battement de la tâche précédente à la tâche suivante, ce qui permet de diminuer la fréquence de fonctionnement du processeur concerné. L'annexe contient le code source, écrit en langage C, d'un 15 programme d'ordinateur permettant la mise en oeuvre d'un procédé d'ordonnancement selon l'invention, utilisant la technique DSF-DVFS décrite ci-dessus. Ce code est donné uniquement à titre d'exemple non limitatif. Le code se compose d'une pluralité de fichiers contenus dans deux répertoires : DSF_Scheduler et pm_drivers. 20 Le répertoire DSF_Scheduler contient le coeur du code de l'ordonnanceur DSF. Il comprend notamment le fichier prototype N schedulerh qui contient la définition des types nécessaires (structure de tâche, structure processeur, etc.), les variables globales (liste de tâches, liste de processeurs, paramètres de l'ordonnanceur, etc.), et les prototypes des fonctions exportées. 25 Le fichier DSF Scheduler.c décrit ensuite les fonctions principales de l'ordonnanceur. La plus importante est la fonction select , c'est elle qui décrit tout le processus d'ordonnancement réalisé à chaque instant d'ordonnancement. Les évènements de tâches onActivate, onBlock, onUnBlock et onTerminate qui déclenchent les instants d'ordonnancement sont également 30 décrits dans ce fichier. La fonction d'ordonnancement s'appuie sur une fonction slow down qui calcule et applique le changement de fréquence. Enfin, les particularités de l'ordonnanceur au démarrage de l'application ont nécessité le développement d'une fonction spécifique start sched. Celle-ci ne s'exécute qu'une seule fois au tout début du lancement de l'application et se base en grande partie sur le code de l'ordonnanceur principal (select_). Pour tous les autres instants d'ordonnancement, c'est la fonction select qui est appelée, via la fonction call scheduler. Le fichier Make file est utilisé pour la compilation. L'application à ordonnancer est décrite dans le fichier N application.c. C'est aussi le fichier contenant le « main » du programme. Celui-ci réalise les diverses initialisations nécessaires, créé les tâches POSIX, lance l'ordonnanceur et synchronise le tout. Il convient de préciser ici qu'une application est vue comme un ensemble de tâches, chacune comportant des caractéristiques temporelles telles que le pire cas du temps d'exécution (VVCET), la période, les échéances (deadlines), etc. Les tâches utilisées effectuent un traitement simple (multiplication des éléments d'un tableau d'entiers) jusqu'à un certain temps d'exécution (AET) - ce qui est décrit par la fonction usertask actualexec - puis se mettent en mode d'attente jusqu'à leur réactivation (usertask sleepexec) lorsqu'elles atteignent leur période. Enfin, pour garder une structure du code la plus claire possible en gardant uniquement les fonctions essentielles de l'ordonnanceur dans le fichier N Scheduter.c, les fonctions secondaires nécessaires ont été regroupées elles dans un autre dans un fichier : N utils.c. Celui-ci contient par exemple des fonctions d'initialisation, de préemption de tâches, d'allocation de tâches aux processeurs, de tri, d'affichage, etc. Le répertoire pm drivers contient les fonctions plus bas niveau sur lequel s'appuie l'ordonnanceur. Il s'agit plus précisément des fichiers prototypes intel core_i5 m520.h, pm typedef h et du fichier pm cpufreq.c. Le fichier prototype intel core_i5 m520.h contient la description de la plateforme cible dont il porte le nom. Il s'agit des informations sur le nombre de processeurs de la platforme et sur les fréquences possibles pour chacun des coeurs, représentés sous forme d'états. Les types utilisés (e.g. les états processeur) sont définis dans le fichier pm_typedefh. Le fichier pm_cpufreq.c contient en particulier les fonctions permettant le changement effectif dynamique de fréquence sur la plateforme d'exécution, en se basant sur l'API Linux CPUfreq. Le changement dynamique de tension fréquence est géré par des politiques appelées govemors (gouverneurs) sous Linux, connues en elles-mêmes. Plus précisément, pour pouvoir changer la (les) fréquence(s) processeur(s), il faut d'abord utiliser un gouverneur dit userspace. Une première fonction set govemor est présente pour cela. Ensuite, l'interaction avec le pilote Linux de changement de fréquence se fait via des fichiers d'échanges localisés dans /sysidevices/system/cpu/cpuX/cpufreq/ où X représente le numéro du processeur concerné. Les fonctions open_cpufreq et close_cpufreq permettent d'ouvrir et de fermer le fichier d'échange scaling setspeed. Le changement de fréquence se fait par la fonction CPU state_manager apply state. Les différentes fonctions utilisent notamment les API POSIX suivantes : - API Pthreads : - pthread create, pour la création d'un Pthread, - pthread_join, pour synchroniser la terminaison des Pthreads, - pthread exit, à la fin de l'exécution d'un Pthread, - pthread cancel, pour forcer la terminaison d'un Pthread. - API Signal : - pthread kiff - API Variables conditions - pthread cond wait - pthread cond broadcast - API Mutex - pthread mutex lock - pthread mutex unlock Les différentes fonctions utilisent également les APIs non POSIX suivantes : - API CPU affinity » - CPU ZERO pour vider la liste des processeurs alloués à une tâche, - CPU SET pour ajouter un processeur à la liste des processeurs alloués, - CPU_ CLR pour enlever un processeur à la liste des processeurs alloués, - CPU ISSET pour tester si une tâche est affectée à un processeur donné et - pthread setaffinity np pour fixer le masque d'affinité à une tâche. - API CPUfreq pour le changement dynamique de tension-fréquence. L'invention a été décrite en détail en référence à un mode de réalisation particulier : système multiprocesseur sous Linux, politique d'ordonnancement EDF avec changement dynamique de tension-fréquence (DVFS). Il ne s'agit pas, cependant, de limitations essentielles. Ainsi, le procédé d'ordonnancement de l'invention peut être appliqué à une plateforme monoprocesseur et/ou ne pas mettre en oeuvre de 15 mécanismes de réduction de la consommation. La mise en oeuvre de l'invention est particulièrement aisée sous LINUX, car les API décrites précédemment sont disponibles. Cependant, un ordonnanceur selon l'invention peut être réalisé sous un autre système d'exploitation compatible avec la norme POSIX et plus précisément avec la 20 norme IEEE POSIX 1.c (ou, ce qui est équivalent, POSIX 1003.1c), sous réserve qu'il supporte un équivalent des APIs CPU Affinity (pour les applications multiprocesseurs) et CPUfreq (pour les applications exploitant le changement dynamique de tension fréquence). D'autres politiques d'ordonnancement avec contraintes 25 d'échéance peuvent être mises en oeuvre, comme par exemple des politiques « Rate Monotonic » (ordonnancement à taux monotone, RM), « Deadline Monotonic » (ordonnancement en fonction de l'échéance des processus, DM) ou « Latest Laxity First » (ordonnancement en fonction de la laxité plus faible, LLF). 30 De même, diverses techniques de réduction de la consommation peuvent être mises en oeuvre. On peut citer à titre d'exemples non limitatifs la technique DSF (« Deterministic Stretch-to-Fit », c'est-à-dire « extension et ajustement déterministe de la fréquence »), exploitant le changement dynamique de tension fréquence (il s'agit de la technique utilisée dans l'exemple qui vient d'être décrit) et AsDPM (« Assertive Dynamic Power Mangement » c'est à dire « politique assertive de gestion dynamique des modes repos ») exploitant les modes repos processeur.5 ANNEXE : CODE SOURCE 1. DSF Scheduler N_scheduler.h #ifndef N_SCHEDULER #define N_SCHEDULER #include #include #include #include #include #include fi PRIORITE MAXIMALE POUR LA POLITIQUE SCHED_FIFO // UTILISEE POUR DONNER UNE PRIORITE MAXIMALE A L'ORDONNANCEUR #define MAX_PRIO 99 // NOMBRE DE TACHES DE L'APPLICATION 20 #define NUM_THREADS 4 // NOMBRE DE PROCESSEURS UTILISES PAR L'ORDONNANCEUR // (PEUT ETRE INFERIEUR OU EGAL AU NOMBRE DE PROCESSEUR TOTAL DISPONIBLE) #define CPU_size 2 25 // DEFINITION DU TYPE ENUMERE STATE_T: ETAT D'UNE TACHE enum state_t { unexisting, running, waiting, ready }; // unexisting = inexistante; running = en execution; waiting = en attente; ready = prête // DEFINITION DU TYPE TASK (EXTENSION DU TYPE PTHREAD) 30 typedef struct task short id; // identifiant de tâche utilisée seulement pour le débogage float wcet; // temps d'exécution au pire cas float bcet; // temps d'exécution au meilleur cas 35 float aet; // temps d'exécution effectif (wcet #include #include #include #include #include #include #include #include "N_utils.h" #include "../pm_drivers/intel_core_i5_m520.h" /ffidefine DEBUG // FONCTION PRINCIPALE DE L'ORDONNANCEUR, APPELEE DEPUIS "CALL_SCHEDULER" // LE COEUR DU TRAITEMENT DE L'ORDONNANCEUR SE TROUVE DANS CETTE FONCTION void *select _o int i,j,rc; double r_nxt; sched_time = get_time(); OTE == false; // DEFINITION DE LA LISTE DES TACHES PRETES (LIST_READY) // DEFINITION DE LA LISTE DES TACHES NON-PRETES (LIST_NO_READY) list_ready_size = 0; list_noready_size = 0; for(i=0; i state == ready) (T[i]->state == running)) { list_ready[list_ready_size] = T[i]; list_ready_size++; else { list_noready[list_noready_size] = T[i]; list_noready_size++; // TRI DES LISTES DE TACHES PAR ORDRE D'ECHEANCE CROISSANTE (LA PLUS PROCHE EN PREMIER) sort(list_ready, list_ready_size); sort(list_noready, list_noready_size); printfnn*************Sched point: %.4f***************\n",sched_time); // MESSAGES DE DEBUG QUI AFFICHE LA LISTE DES TACHES PRETES printf("Sorted Ready List: \t"); Display_list(list_ready, list_ready_size); // MESSAGES DE DEBUG QUI AFFICHE LA LISTE DES TACHES NON PRETES #ifdef DEBUG printfeSorted No_Ready List:\t"); Display_list(list_noready, list_noready_size); #endif // PREEMPTION DES TACHES NON PRIORITAIRES DE LA LISTE DES TACHES PRETES ET EN //COURS D'EXECUTION for (i=CPU_size; klist_ready_size; i++){ task *job = list_ready[i]; if (job->state == running) { abs_eet[job->id-1] = sched_time - last_resume_time[job->id-1]; total_abs_eet[job->id-1] = total_abs_eet[job->id-1] + abs_eet[job->id-1]; total_eet[job->id-1] = total_eet[job->id-1] + (abs_eet[job->id-1] / SR_total[job- >cpu]); if (!(sched_time begintime + job->offset)) T_preempt(job); // MISE A JOUR DU "RET" DE CHAQUE TACHE (REMAINING EXECUTION TIME) for (i=0; i preemption == 1) { job->preemptdelay = sched_time - job->last_preempt_time; job->total_preempt_duration = job->total_preempt_duration + job- >preemptdelay; if (job->state == running) job->ret = job->aet - total_eet[job->id-1]; else if(job->state == ready) { if (job->preemption == 1) job->ret = (job->aet - total_eet[job->id-1]); else job->ret = job->aet; else if(job->state == waiting) job->ret = 0.0; // Le mutex suivant permet d'éviter d'exécuter plusieurs instances de l'ordonnanceur // simultannément, ce qui conduirait à des accès concurrents et conflictuels sur certaines variables // partagées pthread_mutex_lock(&sched_mut_wait); // ALLOCATION DES TACHES PRETES AUX PROCESSEURS LIBRES for (i=0; (i state I= running) { cpu *P = NULL; for (j = 0; j cpu_id) == 0) { if(P->state == DEEP_SLEEP) DEEP_SLEEP_to_RUNNING++; if(P->state == IDLE) IDLE_to_RUNNING++; if(P->state == STAND_BY) STAND_BY_to_RUNNING++; if(P->state == SLEEP) SLEEP_to_RUNNING++; // CALCUL DU RALENTISSEMENT (FREQUENCE MINIMUM) DU PROCESSEUR ALLOUE if(nb_exec[P->cpuid] != 0) { slow_down(job, P); OTE = false; else SR_Iocal[P->cpu_id] = 1.0; SR_total[P->cpu_id] = 1.0; pthread_mutex_lock(&job->mut_wait); // sans ce, mutex, //parfois un travail serait recommence avant d'avoir été assigné à un processeur. T_runningOn(job, P->cpu_id); pthread_mutex_unlock(&job->mut_wait); #ifdef DEBUG printf("T%d is assigned to CPU%d\n",job->id,P->cpu_id); #endif if(job->preemption == 1) { job->preemption = 0; last_resume_time[job->id-1] = sched_time; else if(job->preemption == 0) { job->begintime = sched_time; job->last_preempt_time = job->begintime; last_resunne_time[job->id-1] = job->begintime; // DEMARRAGE DE LA TACHE PRETE SUR LE PROCESSEUR ALLOUE pthread_mutex_lock(&job->mut_wait); pthread_cond_broadcasejob->cond_resume); pthread_mutex_unlock(&job->mut_wait); break; pthread_mutex_unlock(&sched_mut_wait); int nb = 0; // MESSAGES DE DEBUG QUI AFFICHENT L'ETAT POUR CHAQUE PROCESSEUR (ACTIVITE // ET/OU TACHE ALLOUEE) #ifdef DEBUG printf("Processors State: \n"); #endif for (i=0; i " ,P->cpu_id); if (P->state RUNNING) { printfCRUNNING "); for 0=0; j state == running) && (T[j]->cpu == P->cpu_id) ) printf(T%d ", T[j]->id); printf('\n");40 else if (P->state == STAND_BY) printf("STAND BY\n"); else if (P->state == IDLE) printf("IDLE\n"); else if (P->state == SLEEP) printf("SLEEP\n"); else if (P->state == DEEP_SLEEP) printf("DEEP SLEEP\n"); else printf("UNDEFINED\n"); #endif if (P_isRunning(P->cpu_id) == 1) { nb++; else { slack_local[P->cpu_id] = 0; #ifdef DEBUG printf("-> slack_local[CPU%d] = 0\n", P->cpu_id); #endif #ifdef DEBUG printf("Total Preemptions = %ffin",Preemption_counter); #endif } // FONCTION D'APPEL DE L'ORDONNANCEUR // CREE UN THREAD AVEC LA FONCTION SELECT_ PRECEDENTE void call_scheduler() { int i, rc; pid_t pid; pthreadt sched_thread; begin_sched_time = get_time(); /* Création du pthread de l'ordonnanceur*/ if(pthread_create(&sched_thread, NULL, select_, "4") next_period = sched_time + task->period; task->next_deadline = task->deadline; // LE TEMPS D'EXECUTION (AET) EST TIRE AU HASARD ENTRE BCET ET WCET randomvalue = (double)rand()/RAND_MAX; task->aet = ( randomvalue* (task->wcet-task->bcet)+task->bcet ); // INITIALISATION DE TOUTES LES VARIABLES NECESSAIRE A L'ORDONNANCEUR // (DECLAREES/DETAILLEES DANS N_SCHEDULER.H) aet_Fn_1(task->id-1] = task->aet; abs_eet[task->id-1] = O.; task->ret = task->aet; task->preemptdelay = O.; task->state = ready; printf("T%d\t c/0.4f\t\t °/0.4f\t %.4f\t %.4f\n",task->id,task->wcet,task->deadline,task- >period,task->offset); // SYNCHRONISATION PAR RDV: UNE FOIS CREEE, LA TACHE INCREMENTE RDV PUIS // ATTEND LE SIGNAL D'ACTIVATION task->cond_resume // CE SIGNAL EST ENVOYE LORSQUE TOUTES LES TACHES SONT CREEES (I.E. RDV = // NB_THREADS) rdv++; pthread_cond_waietask->cond_resume, &task->mut_wait); task->begintime = sched_time; task->last_preempt_time = task->begintime; last_resume_time[task->id-1] = task->begintime; // ONBLOCK // CET EVENEMENT INTERVIENT A LA FIN DE L'EXECUTION D'UNE TACHE vold onBlock(task *task) { sched_time = get_tinne(); task->endtime = sched_time; task->state = waiting; slack_local[task->cpu] = task->wcet - task->aet; #ifdef DEBUG printf("T%d is terminated at lime = %.4f and generated slack_local[CPU%d] = task->id,task->endtime,task->cpu, slack_local[task->cpup; #endif CPUs[task->cpuj.state = I DLE; task->cpu = -1; #ifdef DEBUG printfeT%d FIN ISHES EXECUTION AT %.2f\n",task->id,sched_time); #endif // SCHEDULING POINT: APPEL DE L'ORDONNANCEUR call_scheduler(); } // ONUNBLOCK // CET EVENEMENT INTERVIENT A LA FIN DE LA PERIODE D'UNE TACHE (REACTIVATION) vold onUnBlock(task *task) { double randomvalue; sched_time = get_time(); // LE TEMPS D'EXECUTION (AET) EST TIRE AU HASARD ENTRE BCET ET WCET randomvalue = (double)randO/RAND_MAX; task->aet = ( randomvalue * (task->wcet-task->bcet)+task->bcet ); // RE-INITIALISATION DE TOUTES LES VARIABLES NECESSAIRE A L'ORDONNANCEUR // (DECLAREES/DETAILLEES DANS N_SCHEDULER.H) aet_Fn_1[task->id-1] = task->aet; wcet_Fn_l [task->id-1] = task->wcet; abs_eet[task->id-1] = 0.; total_eet[task->id-1] = 0.; total_abs_eet[task->id-1] = 0.; task->preemptdelay = 0.; task->state = ready; task->next_deadline = task->next_period + task->deadline; task->next_period = task->next_period + task->period; task->preemptdelay = 0.; task->total_preempt_duration = 0.; #ifdef DEBUG printf("T%d REACHES PERIOD AT %.2f \n", task->id, sched_time); #endif // SCHEDULING POINT: APPEL DE L'ORDONNANCEUR call_scheduler(); // LA TACHE EST ARRETEE, ELLE SERA REDEMARREE PAR L'ORDONNANCEUR AU MOMENT //OPPORTUN pthread_kill(*(task->pthread), SIGUSR1); // ONTERMINATE // CET EVENEMENT INTERVIENT A LA TERMINAISON D'UNE TACHE (FIN DE LA DERNIERE // EXECUTION) void onTerminate(task *task) { int i; sched_time = get_time(); task->state = unexisting; #ifdef DEBUG printf("T%d IS TERMINATED AT %.4f and generated a slack_local[CPU%d]= °/0.4f\n", task->id,sched_time,task->cpu, slack_local[task->cpu]); #endif // A CE STADE, LA SIMULATION EST TERMINEE. ON FORCE L'ARRET DE TOUTES LES // TACHES for (1=0; i pthread));40 // LE PREMIER APPEL A L'ORDONNANCEUR EST PARTICULIER DU FAIT DE LA CREATION ET DE // L'INITIALISATION DES TACHES // CE TRAITEMENT SPECIFIQUE EST CONFIE A LA FONCTION START_SCHED, CORRESPONDANT // AU PREMIER APPEL DE L'ORDONNANCEUR void start_sched() { int i, j, err, rc; pid_t pid; printf(\n*************Sched point:°/0.4f*"********\n",sched_time); gettimeofday(&start_time,NULL); // TOUTES LES TACHES SONT AFFECTEES AU CPUO cpu_set_t mask; for (j=0; j pthread), sizeof(cpu_set_t), &mask); // DEFINITION DE LA LISTE DES TACHES PRETES (LIST_READY) list_ready_size = 0; for (i=0; i beg intime = sched_time; job->last_preempt_time = job->begintime; last_resume_time[job->id-1] = job->begintime; // DEMARRAGE DES TACHES PRETES SUR LES PROCESSEURS ALLOUES for (i=0; (i mut_wait); pthread_cond_broadcasel ist_ready[i]->cond_resu me); pthread_mutex_unlock(&list_ready[i]->mut_wait); // CETTE FONCTION EST APPELEE PAR L'ORDONNANCEUR POUR CALCULER LE // CHANGEMENT DE FREQUENCE A PARTIR DU FACTEUR DE RALENTISSEMENT // POUR UNE TACHE ALLOUEE SUR UN PROCESSEUR, ON CALCULE LA FREQUENCE A LAQUELLE // LA TACHE PEUT ETRE EXECUTEE, ET ON CHANGE LA FREQUENCE PROCESSEUR A CETTE VALEUR void slow_down(task *job, cpu *P) { int i; int proc_id = P->cpu_id; char *setspeed_cpufilename; FILE *setspeed_cpu; // RECUPERER LA FREQUENCE COURANTE DU CPU CONCERNE Fn = (double)CPU_state_manager_query_current_freq(proc_id); #ifdef DEBUG printf("Frequency Adjustment on CPU%d before executing T%d: \n",proc_id,job->id); #endif // CALCUL DU FACTEUR DE RALENTISSEMENT (SR total et SRlocal) estimated_WCET_Fn_l [proc_id] = wcet_Fn_l [job->id-1] * SR_total[proc_id]; estimated_AET_Fn_l [proc_id] = aet_Fn_l [job->id-1] * SR_total[proc_id]; #ifdef DEBUG printf("slack_local[CPU%****\t\t\t\t\t\t\t***\t\t\t= %.4f\n", proc_id, slack_local[proc_id]); printf("SR_Iocal[CPU%d]\t\t***\t\t\t\t\t\t\t***\t\t\t= °/0.4f\n", proc_id, SRlocal[proc_id]); printf("SR_total[CPU%d]\t\t***\t\t\t\t\t\t\t***\t\t\t= %.4f\n", proc_id, SR_total[proc_id]); printf("estimated_WCET_Fn_1[CPU%d].= WCET[T%d]*SR_total[CPU%d]\t\t\t\t= %.4f"/0.4f1t\t= %.4f\n", proc_id, job->id, proc_id, wcet_Fn_1[job->id-1], SR_total[proc_id], estimated_WCET_Fn_1[proc_idp; printf("estimated_AET_Fn_1[CPU%d]= AET[T%d]*SR_total[CPU%d]\t\t\t\t= `)/0.4f"/0.4f\t\t= °/0.4f\n", proc_id, job->id, proc_id, aet_Fn_1[job->id-11, SR_total[proc_id], estimated_AET_Fn_1[proc_id]); #endif if(OTE == false) { t_available_Fn_1 [proc_id] = wcet_Fn_1 [job->id-1] + slack_local[proc_id]; #ifdef DEBUG printf("t_available_Fn_1[CPU%di\t= WCET[r/od]+slack_local[CPU%d]\t\t\t\t= %.4f-F%.4f \t= %.4f\n", proc_id, job->id, proc_id, wcet_Fn_1[job->id-1], slack_local[proc_id], t_available_Fn_1[proc_id]); #endif if (job->preemption == false) { SR_Iocal[proc_id] = (float) (t_available_Fn_1[proc_id] estimated_WCET_Fn_1[proc_id]); #ifdef DEBUG printfeNEW SR_Iocal[CPU%dl\t= t_available_Fn_1[CPU%d]/estimated_WCET_Fn_1[CPU%e= %.4f1/0.4f\t\t= %.4f \n", proc_id, proc_id, proc_id, t_available_Fn_1[proc_id], estimated_WCET_Fn_1[proc_id], SR_Iocal[proc_id]); #endif else if(job->preemption == true) { 1* mise à jour de slack, SR, ret. CPU mis à la fréquence maximale */ slack_local[proc_id] = 0.0; SR_Iocal[proc_id] = 1.0; SR_total[proc_id] = 1.0; Fn = (double) CPU_STATE[proc_id][0].freq; #ifdef DEBUG printf(" PREEMPTION BY T%d OCCURED AT TIME=%.4f, slack_local=0.0, SR_Iocal=1.0, SR_total=1.0, Fn=maxfreq\n", job->id, sched_time); #endif if (SR_Iocal[proc_id] >= 1.00) { #ifdef DEBUG printf("NEVV VVCET[T%d]\t\t= VVCET_Fn_l[T%d]*SR_Iocal[CPU%d]\t\t\t\t= °/0.4f*()0.4f\t\t= job->id, job->id, proc_id, wcet_Fn_1[job->id-1], SR_Iocal[proc_id]); #endif wcet_Fn_1[job->id-1] = (float)(wcet_Fn_1(job->id-1] * SR_Iocal[proc_id]); #ifdef DEBUG printf('/0.4f\n", wcet_Fn_1[job->id-1]); #endif #ifdef DEBUG printf("NEW AET[T%d]\t\t= AET_Fn_1[T`Yod]*SR_Iocal[CPU`Yodbt\t\t\t= %.4f*%.4t1t\t= job->id, job->id, proc_id, aet_Fn_1[job->id-1], SR_Iocal[proc_id]); #endif aet_Fn_1[job->id-1 ] = (double)(aet_Fn_1[job->id-1] * SR_Iocal[proc_id]); #ifdef DEBUG printfr/0.4f\n", aet_Fn_1[job->id-1]); #endif else if (SR_Iocal[proc_id] id, proc_id, proc_id, estimated_VVCET_Fn_1[proc_id], SR_Iocal[proc_id]); #endif wcet_Fn_1[job->id-1] = (estimated_VVCET_Fn_1[proc_id] * SR_Iocal[proc_id]); #ifdef DEBUG printf("%.4f\n", wcet_Fn_1[job->id-1]); #endif #ifdef DEBUG printf("NEVV AET[T%d] \t\t= est_AET_Fn_1[CPU%d]*SR_Iocal[CPU%d]\t\t\t= %.4f*%.4f\t\t= ", job->id, proc_id, proc_id, estimated_AET_Fn_1[proc_id], SR_Iocal[proc_id]); #endif aet_Fn_1[job->id-1] = (estimated_AET_Fn_1[proc_id] * SR_Iocal[proc_id]); #ifdef DEBUG printf("%.4f\n", aet_Fn_11job->id-1]); #endif /* CALCUL DE LA NOUVELLE FREQUENCE "THEORIQUE" */ double Fn_1 = (double)(Fn / SR_Iocal[proc_id]); // RECHERCHE DE LA NOUVELLE FREQUENCE EFFECTIVE (LES FREQUENCE PROCESSEUR // SONT PREDEFINIES, DONC DIFFERENTES DE LA FREQUENCE THEORIQUE) Elementary_state State; State = CPU_STATE[proc_id][0]; for (i=0; i #include #include #include #include #include #include #include #include "N_utils.h" #define TARGET_CPU_DEFINED #include "../pm_drivers/intel_core_15_m520.h" #define DEBUG // FONCTION D'INITIALISATION DES PROCESSEURS DE LA PLATEFORME void init_CPUs() { printrnIntializing CPUs... \n"); int i; // FAIRE LA LISTE DES PROCESSEURS DISPONIBLES ET METTRE A JOUR LES ETATS CPUs for (i=0;i pthread = &thread[i]; nb_exec[i] = 0; total_eet[i] = 0.0; total_abs_eet[i] = 0.0; // INITIALISATION DES PARAMETRES DE L'ORDONNANCEUR for (1=0; i id, task->cpu, sched_time, abs_eet[task->id-1]); Preemption_counter++; task->last_preempt_time = sched_time; task->preemption = 1; task->preemptdelay = O.; task->state = ready; CPUs[task->cpu].state = IDLE; task->cpu // LE MECANISME DE PREMPTION CONSISTE A ENVOYER UN SIGNAL A DESTINATION DE // LA TACHE pthread_kill(*(task->pthread), SIGUSR1); // LORSQUE CELLE-CI LE RECOIT, LE SIGNAL HANDLER sigusrl EXECUTE // PTHREAD_COND_WAIT QUI A POUR EFFET DE SUSPENDRE LA TACHE // VOIR sigusrl dans APPLICATION.0 // ALLOUE UNE TACHE A UN PROCESSUR void TrunningOn(task *task, int cpu_id) ( int i, j, err; cpu_set_t mask; CPU_ZER0(&mask); /* SET TASK TO CPU_ID */ // Alloue la tâche 'task' au processeur numéro 'cpu_id' CPU_SET(cpu_id, &mask); /* PREVENT TASK TO USE OTHER CPUs */ // Faire en sorte que la tâche 'task' ne puisse s'exécuter sur aucun autre processeur for (i=0; i pthread), sizeof(cpu_set_t), &mask); if (err != 0) { printf ("**** (1) PTHREAD_SETAFFINITY RETURNED: %d \n", err); exit(0); } task->cpu = cpu_id; task->state = running; CPUs[cpuid].state = RUNNING; nb_exec[cpu_id]++; /* PREVENT ALL OTHER TASK TO USE CPU_ID*/ // Faire en sorte que toute tâche autre que lask' ne puissent pas s'exécuter // sur le processeur numéro cpu_id for (i=0; i id I= task->id) { err = pthread_getaffinity_np(*(T[i]->pthread), sizeof(cpu_set_t), &mask); if (err 0) { printf ("**** (2) PTHREAD_SETAFFINITY RETURNED: %d \n", err); exit(0); } if ( (T[i]->id != task->id) ) CPU_CLR(cpu_id, &mask); /*CHECK THAT EACH THREAD CAN NOT USE MORE THAN ONE CPU (default: CPUO) */ // Verifier que chaque tache ne peut pas utiliser plus d'un seul CPU (par défaut, CPUO) short cpu_allocated = 0; for (j=0; j 1) printf("WARNING: T%d IS ALLOCATED MORE THAN ONE CPU\n", T[i]->id); err = pthread_setaffinity_np(*(TM->pthread), sizeof(cpu_set_t), &mask); if (err != 0) { printf ("**** (3) PTHREAD_SETAFFINITY RETURNED: %d \n", err); exit(0); } ) // FONCTION PERMETTANT DE TESTER SI UN PROCESSEUR EST UTILISE (1) OU NON (0) int P_isRunning(int cpu_id) int i; int cpu_isRunning = 0; if (CPUs[cpu_id].state == RUNNING) cpu_isRunning = 1; return cpu_isRunning; } // TRI D'UNE LISTE DE TACHES PAR ORDRE DE D'ECHEANCE CROISSANTE (LA PLUS PROCHE EN // PREMIER) void sort(task *list[], int list_size) task *temp; int i, j, min; for (i = 0; i next_deadline next_deadline) min=j; tem p=list[i]; list[i]=Iist[min]; list[min]=temp; 30 // FONCTION QUI RETOURNE LE TEMPS ECOULE DEPUIS LE DEBUT DE LA SIMULATION double get_time() double time; 35 struct timeval current_time; if (gettimeofday(&current_time,NULL) == -1) puts("ERROR : get_time_ofday"); 40 return -1; time = current_time.tv_sec - start_time.tv_sec \ +0.000001*(current_time.tv_usec - start_time.tv_usec); return time; // TACHES APPLICATIVES: // LES TACHES APPLICATIVES SE DIVISENT EN DEUX PHASES: - UNE PHASE D'EXECUTION EFFECTIVE (CORRESPONDANT A usertask_actualexec) // - UNE PHASE D'ATTENTE (CORRESPONDANT A usertask_sleepexec). LA TACHE DOIT ATTENDRE // LE TEMPS DE SA PERIODE AVANT DE POUVOIR ETRE A NOUVEAU PRETE POUR RE- EXECUTION int usertask_actualexec(task *task) { double duration; double data[262144]; int i = 0; nbTicks++; task->begintime = sched_time; #ifdef DEBUG printf("T%d Starts execution on CPU%d with AET = %.4f (*%.4f=%.4f) at `)/0.4f\n", task->id, task->cpu, task->ret, SR_total[task->cpu], task->ret*SR_total[task->cpu], 2 5 get_timeOrtask->begintime*/); #endif // LES TACHES EFFECTUENT UN SIMPLE ACCES TABLEAU / MULTIPLICATION ENTIERE // JUSQU'A ATTEINDRE l'AET // (EN TENANT COMPTE DES PREEMPTIONS ET CHANGEMENT DE FREQUENCE POSSIBLES) 30 do duration = get_time() - task->begintime; data[i%262144] = duration*i++; } while (duration id-1] + task->total_preempt_duration + (task->ret * 35 SR_total[task->cpu]) + offset_delay[task->id-1]); task_duration[task->id-1] = duration; return 0; 40 int usertask_sleepexec(task *task) double sleep = task->next_period - sched_time; if(sleep preemptdelay = 0; return 0; // FONCTIONS D'AFFICHAGE UTILISEE POUR LE DEBUG void Display() int i; sched_time=get_time(); printf("Scheduling point: %.4f", sched_time); printf("\nTask \t cpu \t thread_pid \t nxt ddlne \t prio \t starts at \t stops at \t idie until \t state\n"); for (i=0; i id, T[i]->cpu, T[i]->thread_pid, T[i]->next_deadline, T[i]->prio, T[i]->begintime, T[i]->endtime, sched_time, T[i]->state); printfr******************************************************************* ********************************* **\n11); void Display_list(task list[], int list_size) int i; printfnt Task \t Next_deadline\n"); for (i = 0; i id, list[i]->next_deadline); printf("\n"); N_application.c #define _GNU_SOURCE #include #include #include #include #include #include #include #include #include #include #include #include "N_utils.h" // L'EXEMPLE APLICATIF UTILISE ICI EST TIRE D'UNE APPLICATION VIDEO H264 ENCODEUR 1" 4 TASKS / 2 CPUS - T1 -> Motion Estimation #1 Estimation de mouvement sur la demi-image numéro 1 - T2 -> Motion Estimation #2 Estimation de mouvement sur la demi-image numéro 2 - T3 -> Inv. Prediction + Texture Encoding + Syntax Writing Prédiction inverse + Encodage Texture + Ecriture syntaxique - T4 -> Loop Filter Filtre de déblocage THIS VERSION REQUIRES 2 CPUs Cet exemple nécessite 2 CPUS 1c1 static task Task[NUM_THREADS]= { /* Task[0] = 1, // id 20.63e-1, // wcet 5.65e-1, // bcet 10.40e-1, // aet 0, //ret 21.0e-1, // deadline 0, // nex_deadline -1, // cpu 40.0e-1, // period 0, // next_period -1, // begintime -1, // endtime 0, // preemption 0, // preemptdelay 0.0, // last_preempt_time 0.0, // total_preempt_duration unexisting, // state PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER, NULL, // adresse du pthread associé 0 // thread_pid }, /*Task[1] = */{ 2, // id 20.63e-1, // wcet 5.65e-1, // bcet 10.50e-1, // aet 0, //ret 21.0e-1, // deadline 0, // next deadline -1, // cpu 40.0e-1, // period 0, // next_period -1, // begintime -1, // endtime 0, // preemption 0, // preemptdelay 0.0, // last_preempt_time 0.0, // total_preempt_duration unexisting, // state PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER, NULL, // adresse du pthread associé 0 // thread_pid }, /* Task[2] = */{ 3, // id 8.25e-1, // wcet 3.38e-1, // bcet 5.96e-1, // aet 0, //ret 31.0e-1, // deadline 0, // next deadline -1, // cpu 40.0e-1, // period 0, // next_period -1, // begintime -1, // endtime 0, // preemption 0, // preemptdelay 0.0, // last_preempt_time 0.0, // total_preempt_duration unexisting, // state PTHREAD_MUTEX_INITIALIZER, PTHREAD_CONDINITIALIZER, NULL, // adresse du pthread associé 0 // thread_pid /* Task[3] = */{ 4, // id 5.78e-1, // wcet 1.81e-1, // bcet 3.27e-1, // aet 0, //ret 40.0e-1, // deadline 0, // next deadline -1, // cpu 40.0e-1, // period 0, // next_period -1, // begintime -1, // endtime 0, // preemption 0, // preemptdelay 0.0, // last_preempt_time 0.0, // total_preempt_duration unexisting, // state PTHREAD_MUTEX _INITIALIZER, PTHREAD_COND_INITIALIZER, NULL, // adresse du pthread associé 0 // thread_pid // MECANISME UTILISE POUR PREEMPTER UNE TACHE void sigusrl(int dummy) int i; pid_t pid; // Récupérer le pid du thread courant pid = (long)syscall(SYS_gettid); // Comparer le pid du thread courant avec celui de tous les threads de l'application // afin d'identifier le thread à suspendre. On exploite ici le fait que le signal handler (sigusrl) // s'exécute avec le pid du thread qui l'a reçu. for (i=0; i #include #include #include "pm_typedef.h" #define DEBUG #define CPUFREQPATH "/sys/devices/system/cpu/cpu" #define GOVPATH "/cpufreq/scaling_governor" #define FREQPATH "/cpufreq/scaling_setspeed" FILE *setspeed_cpu[4]; void itoa (int n, char *u) { int i=0,j; char s[17]; do s[i++]=(char)( n%10 + 48); n-=re)/010; } while ((n1=10)>0); for (j=0;j \tCPU%d new governor%s\n", cpu, strbuf02); #endif fclose(cpu_governor); } void open_cpufreq(int cpu) { char cpufreq_filename[60]; #ifdef DEBUG printf ("Opening\t\t\t\t\t/sys/devices/system/cpu/cpu%d/cpufreq/scaling_setspeed\ n", cpu); #endif // initialisation du nom de fichier complet (incluant le chemin) // pour le fichier de spécification de fréquence (scaling_setspeed) du coeur numéro 'cpu' char cpu_freq_str[17]; itoa(cpu, cpufreq_str); strcpy(cpufreq_filename, CPUFREQPATH); strcat(cpu_freq_filename, cpu_freq_str); strcat(cpu_freq_filename, FREQPATH); setspeed_cpu[cpu] = fopen(cpu_freq_filename, "r+w"); void CPU_state_manager_apply_state( int cpu, Elementary_state *s) { il FILE *setspeed_cpu; int freq0, freq1; // AFFICHE LA FREQUENCE COURANTE DE CPU fscanf(setspeed_cpu[cpu], "%d", &freq0); fseek(setspeed_cpu[cpu], 0, SEEK_SET); #ifdef DEBUG printf("CPU%d CURRENT FREQUENCY:%d\t",cpu,freq0); #endif fprintf(setspeed_cpu[cpu], "%llu", s->freq); fseek(setspeed_cpu[cpu], 0, SEEK_SET); freq1=-1; fscanf(setspeed_cpu[cpu], "%d", &freq1); fseek(setspeed_cpu[cpu], 0, SEEK_SET); #ifdef DEBUG printf("->\tCPU%d NEW FREQUENCY:%d\n",cpu, freq1); #endif } int CPU_state_manager_query_current_freq(int cpu) { int freq0; fscanf(setspeed_cpu[cpu], "%d", &freq0); fseek(setspeed_cpu[cpu], 0, SEEK_SET); return freq0; void close_cpufreq(int cpu) { #ifdef DEBUG printf ("Closing\t\t\t\t/sysidevices/system/cpu/cpu%d/cpufreq/scaling_setspeed\n" , cpu); #endif fclose(setspeed_cpu[cpu]); } REVENDICATIONS1. Procédé d'ordonnancement de tâches avec contraintes d'échéances, basé sur un modèle de tâches périodiques indépendantes et réalisé en espace utilisateur, dans lequel : - chaque tâche à ordonnancer est associée à une structure de données, définie en espace utilisateur et contenant au moins une information temporelle et une information indicative d'un état d'activité de la tâche, ledit état d'activité étant choisi dans une liste comprenant au moins : un état de tâche en exécution ; un état de tâche en attente de la fin de sa période d'exécution ; et - un état de tâche prête à être exécutée, en attente d'une condition de reprise; - au cours de son exécution, chaque tâche modifie ladite information indicative de son état d'activité et le cas échéant, en fonction d'une politique d'ordonnancement prédéfinie, appelle un ordonnanceur qui est exécuté en espace utilisateur ; - à chaque appel, ledit ordonnanceur : établit une file d'attente des tâches prêtes à être exécutées, en attente d'une condition de reprise; - trie ladite file d'attente en fonction d'un critère de priorité prédéfini ; - si nécessaire, préempte une tâche en exécution en lui envoyant un signal la forçant à passer dans ledit état de tâche prête à être exécutée, en attente d'une condition de reprise ; et - envoie ladite condition de reprise au moins à la tâche se trouvant en tête de ladite file d'attente. 2. Procédé d'ordonnancement selon la revendication 1 dans lequel ladite politique d'ordonnancement est une politique préemptive, telle que EDF, RM, DM ou LLF. 3. Procédé d'ordonnancement selon l'une des revendications précédentes, mis en oeuvre dans une plateforme multiprocesseur, dans lequel ladite structure de données comprend également une information relative à un processeur auquel la tâche correspondante est affectée, et dans lequel ledit ordonnanceur affecte à un processeur du système chaque tâche prête à être exécutée. 4. Procédé d'ordonnancement selon l'une des revendications précédentes, dans lequel ledit ordonnanceur modifie la fréquence d'horloge et la tension d'alimentation du ou d'au moins un processeur en fonction d'une politique DVFS. 5. Procédé d'ordonnancement selon l'une des revendications précédentes comportant une étape d'initialisation, au cours de laquelle : - les tâches à ordonnancer sont créées, affectées à un même processeur et placées dans un état d'attente d'une condition de reprise, une variable globale dite de rendez-vous étant incrémentée ou décrémentée lors de la création de chaque dite tâche ; - lorsque ladite variable de rendez-vous prend une valeur prédéfinie indiquant que toutes les tâches ont été créées, ledit ordonnanceur est exécuté pour la première fois. 6. Procédé d'ordonnancement selon l'une des revendications précédentes, dans lequel ladite structure de données contient également des informations indicatives d'un thread associé à ladite tâche et à son temps d'exécution dans le pire cas. 7. Procédé d'ordonnancement selon l'une des revendications précédentes, exécuté sous un système d'exploitation compatible avec une 30 norme POSIX. 8. Procédé d'ordonnancement selon la revendication 7, dans lequel ledit système d'exploitation est un système Linux. 9. Procédé d'ordonnancement selon l'une des revendications 7 ou 8 dans lequel, à chaque appel de l'ordonnanceur, un «pthread» est créé pour assurer son exécution. 10. Procédé d'ordonnancement selon l'une des revendications 7 à 9, comportant l'utilisation d'un MUTEX pour assurer l'exécution d'une seule instance à la fois de l'ordonnanceur. 11. Procédé d'ordonnancement selon l'une des revendications 9 ou 10 lorsqu'elle dépend des revendications 3 et 8, dans lequel l'affectation d'une tâche à un processeur est effectuée au moyen de l'API CPU Affinity. 12. Produit programme d'ordinateur pour la mise en oeuvre d'un procédé d'ordonnancement selon l'une des revendications précédentes.