Titre de l'invention : [Procédé de gestion de données échantillonnées partagées entre plusieurs unités de traitemenlj

[Domaine technique

L’invention concerne le domaine des calculateurs comprenant plusieurs unités de traitement, tel un processeur multi-cœur. Un tel calculateur exécute un logiciel, implémentant les fonctions applicatives, découpé en tâches logicielles récurrentes cycliques (à période fixe) ou acycliques (apériodiques, tel une récurrence déterminée par un évènement lié à la rotation du moteur). Chacune de ces tâches peut être exécutée sur l’un des cœurs. Les informations traitées sont stockées sous forme de données et certaines doivent être échangées entre les tâches. Ces données sont typiquement stockées dans une mémoire d’échange globale. Les tâches étant récurrentes, les données sont, de manière récurrente, lues et écrites, par des tâches pouvant s’exécuter en parallèle et selon des récurrences différentes ou de type différent. De plus une tâche peut être préemptée par au moins une interruption prioritaire. Ceci interdit tout déterminisme ou du moins rends difficile toute prévision fiable de la charge des cœurs.

Technique antérieure

Des accès simultanés ou concurrents à une même donnée sont préjudiciables en ce qu’ils peuvent conduire à des situations d’inconsistance des données. Des problèmes de stabilité et/ou de cohérence peuvent survenir si une donnée est écrite par une tâche alors qu’elle est en train d’être lue par une autre tâche.

Il est connu, pour éviter ces situations d’inconsistance, de protéger les données utilisées par une tâche, au moyen d’une copie dans un buffer, pendant au moins le temps du traitement par la tâche.

Aussi, tel qu’illustré à la figure 3, une commande de remplissage, nommée FILL (ici FILL1), recopie (flèche vers le haut), typiquement depuis la mémoire d’échange globale MG, les données utiles à une tâche T1 dans un buffer B1 de travail dédié à la tâche T 1 , avant que la tâche T1 ne réalise son traitement. La tâche T1 lit r1 , r2 les données dont elle a besoin depuis le buffer B1 , réalise son traitement en travaillant sur ces données, éventuellement les modifie et écrit les résultats w1 , w2 dans le buffer B1. A l’issue du traitement, les données contenues dans le buffer B1 sont restituées en recopiant (flèche vers le bas) le buffer B1 dans la mémoire d’échange globale MG, par une commande de vidage, nommée FLUSH (ici FLUSH1).

Ainsi durant tout le traitement par une tâche T1 , elle dispose de ses données cohérentes en ce qu’elles sont protégées dans un espace mémoire propre, constitué par le buffer B1.

Les commandes FILL et FLUSH peuvent être centralisées et automatisées, par le système d’exploitation. Elles concentrent avantageusement toute la gestion des accès concurrents aux données.

Afin de gérer les accès concurrents, il convient, pendant qu’une commande FLUSH recopie un buffer B1 en mémoire globale MG (écriture, vidage), d’empêcher toute commande FILL de recopier des données depuis la mémoire globale MG vers le buffer B1 (lecture, remplissage) et réciproquement empêcher toute écriture pendant une lecture. Aussi il est connu d’utiliser au moins un sémaphore pour protéger les données.

Tel qu’illustré à la figure 1 , montrant deux tâches T1 , T2 s’exécutant respectivement sur deux coeurs C1 , C2, un sémaphore SEM1 est un mécanisme, gérant un jeton unique, autorisant un accès en lecture ou en écriture à une donnée ou ensemble de données à l’entité qui détient ledit jeton. Une tâche T1, T2 ou commande FILL, FLUSH désirant accéder à une donnée doit préalablement prendre P(SEM1) le sémaphore SEM1 correspondant à la donnée. Lorsqu’elle a pris le sémaphore SEM1 , la tâche T1 , T2 peut réaliser l’accès. Ensuite la tâche T1 , T2 rend ou libère L(SEM1) le sémaphore SEM1 qui peut alors être utilisé par une autre tâche. Un sémaphore SEM1, en ce qu’il ne comprend qu’un unique jeton et n’est disponible que pour un seul demandeur, ne peut être pris que par une seule tâche ou commande, à la fois, ce qui garantit un seul accès à un instant donné. Une tâche T 1 , T2 ou commande FILL, FLUSH qui souhaite prendre un sémaphore SEM1, effectue une ou plusieurs tentatives SEM17, et tant qu’il est déjà pris, se le voit refuser. Aussi elle doit attendre DT qu’il se libère avant de pouvoir le prendre à son tour, et pouvoir réaliser un accès. Un sémaphore SEM1 protège au moins une donnée, mais le plus souvent plusieurs données regroupées dans un jeu de données, ledit jeu étant protégé par un sémaphore SEM1. Aussi une commande FILL, FLUSH nécessite généralement une prise de plusieurs sémaphores concernés, de manière à pouvoir accéder à toutes les données utiles à la tâche T1, T2, en ce que lesdites données peuvent appartenir à des jeux différents.

Classiquement la prise des sémaphores correspondant aux données nécessaires à une tâche T1 , T2 s’effectue en séquence, l’une après l’autre, la tâche T1 , T2 ou commande FILL, FLUSH restant en attente DT lorsqu’un sémaphore SEM1 n’est pas disponible, jusqu’à sa libération.

La durée de prise et d’occupation d’un sémaphore SEM1 par une commande est généralement courte, puisque limitée au temps nécessaire à la recopie des données. Mais il peut arriver, tel qu’illustré à la figure 2, que durant une prise de sémaphore SEM1, la commande FILL ou FLUSH, soit interrompue et ce éventuellement de manière répétée. Les interruptions 11, I2, I3, I4 étant prioritaires, ceci peut drastiquement prolonger la durée d’occupation du sémaphore SEM1. Ceci retarde la tâche T1 en cours d’exécution d’une commande de protection FILL, FLUSH, mais peut encore ocasionner un retard DT sur une autre tâche T2, y compris une tâche T2 indépendante de la première tâche T 1 , mais nécessitant ce même sémaphore SEM1.

Résumé de l'invention

Afin d’éviter de bloquer une tâche alors que celle-ci attend un sémaphore indisponible, le traitement des différents sémaphores est réalisé en parallèle. Ainsi si un sémaphore est indisponible, plutôt que d’attendre qu’il se libère, une commande de protection selon l’invention est autorisée à tester la disponibilité d’un autre sémaphore correspondant à une de ses données.

Aussi l’invention a pour objet un procédé de gestion de données partagées entre plusieurs unités de traitement, les données étant parties entre au moins un jeu, chaque jeu comprenant au moins une donnée, chaque jeu étant au préalable copié dans un buffer au moyen d’une commande de remplissage, chaque jeu copié étant ensuite utilisé par un traitement et chaque jeu copié et éventuellement modifié par le traitement, étant restitué, à l’issue du traitement, au moyen d’une commande de vidage, où une commande de remplissage et/ou une commande de vidage utilisent un sémaphore univoquement associé à chaque jeu / buffer, pour garantir un unique accès, à un instant donné, à une donnée dudit jeu, où pour une commande de remplissage ou pour une commande de vidage, toutes les mises à jour des différents buffers concernés sont exécutées en parallèle, itérativement jusqu’à ce que toutes les mises à jour soient réalisées.

Des caractéristiques ou des modes de réalisation particuliers, utilisables seuls ou en combinaison, sont :

- le procédé comprend un indicateur de réalisation pour chacun des N buffers associés à une commande de remplissage ou à une commande de vidage et un compteur de réalisation, où le procédé comprend les étapes suivantes : initialisation des indicateurs de réalisation à FAUX, initialisation du compteur à ZERO, initialisation à ZERO de l’indice i, variant de 0 à N-1 , itération, jusqu’à ce que le compteur soit égal à N, en variant l’indice i, des étapes suivantes : si l’indicateur de réalisation courant est FAUX, et si le sémaphore correspondant est disponible, prise du sémaphore, mise à jour du buffer correspondant, libération du sémaphore, mise à VRAI de l’indicateur de réalisation courant, et incrémentation du compteur,

- le procédé comprend encore une étape de mise à jour de buffers non protégés par un sémaphore, réalisée après la mise à jour des buffers protégés par sémaphore,

- la mise à jour de buffers non protégés par un sémaphore, est réalisée lorsque l’indice i vaut une valeur donnée modulo N, préférentiellement ZERO,

- le nombre de sémaphores est configurable,

- le nombre de données est de l’ordre du millier et le nombre de sémaphores est sensiblement égal à 12.

Dans un deuxième aspect, l’invention concerne une application dudit procédé à un contrôle commande de moteur à explosion exécuté sur un processeur multi-cœur.

Brève description des dessins

L’invention sera mieux comprise à la lecture de la description qui suit, faite uniquement à titre d’exemple, et en référence aux figures en annexe dans lesquelles : [Fig. 1] déjà décrite, illustre le principe d’un sémaphore,

[Fig. 2] déjà décrite, illustre le problème de retard d’une tâche en cas de préemption par des interruptions,

[Fig. 3] déjà décrite, illustre le principe de protection des données par buffer,

[Fig. 4] montre un synoptique du procédé selon l’invention.

Description des modes de réalisation

L’invention concerne un procédé de gestion de données échantillonnées partagées entre plusieurs unités de traitement C1, C2. Avantageusement, les données sont parties, elles forment une partition, entre un et avantageusement plusieurs jeux. Un jeu est un ensemble de données permettant un traitement commun, notamment en termes de protection : remplissage, vidage et sémaphore en commun. Chaque jeu comprend au moins une donnée. Afin de protéger les données d’un jeu, préalablement à un traitement, typiquement réalisé par une tâche T1 , T2, un jeu de données, nécessaire à ladite tâche T1 , T2, est copié dans un buffer B1 depuis la mémoire globale MG. Ceci est réalisé par une commande de remplissage FILL1 , typiquement exécutée par la tâche T1 , T2 qui nécessite lesdites données. Ainsi, un jeu copié peut ensuite être utilisé par un traitement ou tâche T1 qui travaille et éventuellement modifie les données ainsi protégées dans ledit buffer B1. A l’issue du traitement, les données du buffer B1 sont restituées au moyen d’une commande de vidage FLUSH1 qui recopie les données du buffer B1 dans la mémoire globale MG.

Afin de ne pas se chevaucher, les différentes commandes de remplissage FILL1 et les différentes commandes de vidage FLUSH1 utilisent au moins un sémaphore SEM1 , un sémaphore SEM1 étant univoquement associé à chaque jeu / buffer B1. Ceci permet de garantir un unique accès, à un instant donné, à une donnée d’un jeu quelconque.

Alors que dans l’art antérieur, une tâche, commande ou traitement rencontrant un sémaphore SEM1 occupé se met en attente DT jusqu’à ce qu’il soit disponible, selon une caractéristique de l’invention, une commande de remplissage FILL, FILL1 ou une commande de vidage FLUSH, FLUSH1 exécute, toutes les mises à jour des différents buffers B1 en parallèle. Ainsi une commande de remplissage ou de vidage lorsqu’elle rencontre un sémaphore SEM1 indisponible, n’attend pas et tente de trouver un autre sémaphore disponible ou libre, et réalise la mise à jour du buffer correspondant lorsqu’un autre sémaphore est trouvé disponible. Ceci est itéré, en repassant sur tous les sémaphores non encore trouvés libres, jusqu’à ce que toutes les mises à jour soient réalisées. Ainsi un sémaphore SEM1 indisponible à un instant donné ne retarde pas le fonctionnement, une autre mise à jour pouvant être réalisée pendant le temps d’attente DT. A charge pour le procédé de revenir tester les sémaphores non encore trouvés libres, pour s’assurer de réaliser la mise à jour de tous les buffers.

Selon un mode de réalisation possible, le procédé peut implémenter cette caractéristique au moyen d’un indicateur de réalisation Fi, i=0 à N-1 , pour chacun des N buffers associés à une commande de remplissage FILL1 ou à une commande de vidage FLUSFI1 et d’un compteur de réalisation CTR. Fi est un indicateur booléen associé à chaque buffer/sémaphore. Il est FAUX ou égal à 0 initialement et tant que le sémaphore associé n’a pas été trouvé libre ou ce qui est équivalent tant que le buffer n’a pas été mis à jour. Il devient VRAI ou égal à 1 lorsque le sémaphore a été trouvé libre et que le buffer a été mis à jour. Le compteur CTR compte le nombre de sémaphores trouvés libres ou ce qui est équivalent le nombre de buffers mis à jour.

Le procédé comprend les étapes suivantes, plus particulièrement illustrées à la figure 4. Une étape d’initialisation est réalisée préalablement. Elle comprend : initialisation de tous les indicateurs de réalisation Fi à FAUX ou 0, initialisation du compteur CTR à ZERO ou 0, et initialisation à ZERO ou 0 d’un indice i, variant de 0 à N-1. Ensuite il est procédé à une itération, jusqu’à ce que le compteur CTR soit égal à N, en variant l’indice i, des étapes suivantes. Si l’indicateur de réalisation courant Fi, est FAUX, et si le sémaphore correspondant SEMi est disponible, prise du sémaphore SEMi, mise à jour du buffer Bi correspondant, libération du sémaphore SEMi, mise à VRAI de l’indicateur de réalisation Fi correspondant à la valeur courante de l’indice i, et incrémentation du compteur CTR. Sinon, si l’indicateur de réalisation Fi courant est VRAI, indiquant un buffer correspondant déjà mis à jour, ou si le sémaphore SEMi courant est indisponible, parce qu’il est pris par un autre traitement, rien n’est fait, la fin de boucle est atteinte et l’itération reprend, pour l’indice i suivant. A noter que l’indice i est incrémenté modulo N et qu’il peut être nécessaire de réaliser un nombre important, nettement supérieur à N, d’itérations.

A titre illustratif, la première itération, suite à l’initialisation, débute avec i=0. Le premier indicateur de réalisation correspondant au premier buffer et à l’indice i=0 est testé. Il est FAUX puisqu’aucune mise à jour n’a encore été réalisée. On suppose ici que le premier sémaphore est indisponible. Il s’ensuit que la branche itérée est terminée. Le test final CTR = N est faux, puisque CTR vaut toujours 0. L’indice i est incrémenté et vaut i=1.

L’indicateur de réalisation F1 correspondant au buffer B1 est testé. Il est FAUX puisqu’aucune mise à jour n’a encore été réalisée. On suppose ici que le sémaphore associé SEM1 est disponible. Aussi, ledit sémaphore SEM1 est pris, le buffer B1 peut être et est mis à jour, puis le sémaphore SEM1 peut être libéré. L’état de mise à jour réussie est acté en changeant l’état de l’indicateur de réalisation F1 de FAUX ou 0 à VRAI ou 1 et en incrémentant le compteur CTR de 1. La branche itérée est terminée. Le test final CTR = N est faux, puisque CTR vaut maintenant 1.

Le procédé se poursuit avec i=2 modulo N, jusqu’à ce que toutes les mises à jour soient réalisées et que le compteur CTR soit en conséquence égal N.

Une donnée n’est pas nécessairement protégée par sémaphore, par exemple lorsqu’elle n’est utilisée que par une unique tâche ou lorsqu’il s’agit d’une donnée atomique. On nomme donnée atomique, une donnée codée sur un longueur lisible par le processeur en un coup d’horloge, tel que par exemple un octet pour un processeur 8 bits. Cependant même ces données non protégées par sémaphore font avantageusement l’objet d’une protection par buffer.

La mise à jour de ces buffers en lecture, FILL, ou en écriture FLUSH, est avantageusement réalisée à l’issue de la mise à jour des buffers protégés par sémaphore, tel qu’illustré à la figure 4, soit après toutes les itérations.

Selon une autre caractéristique alternative, la mise à jour de buffers non protégés par un sémaphore, peut être réalisée au cours de l’itération. Ainsi une fois que les N sémaphores ont été testés, avec ou sans succès, il peut être intéressant d’intercaler tout ou partie de la mise à jour de buffers non protégés par un sémaphore, avant de reboucler sur un nouveau test des sémaphores, principalement lorsque ledit test est négatif, tous les sémaphores restants étant indisponibles. Aussi selon cette caractéristique, tout ou partie de la mise à jour de buffers non protégés par un sémaphore est avantageusement réalisé lorsque l’indice i vaut une valeur donnée modulo N. Cette valeur peut, par exemple, être la valeur ZERO ou 0, rencontrée après un balayage complet de l’ensemble des buffers/sémaphores.

Le nombre de sémaphores est un paramètre délicat à déterminer. Un sémaphore par donnée conduit à un trop grand nombre de sémaphores et à des temps de traitement prohibitifs. Trop peu de sémaphores conduit à contrario à augmenter les temps d’attente DT. Aussi regroupe-t-on avantageusement les données en jeux, chaque jeu étant associé à un sémaphore SEM1. Avantageusement le paramètre nombre de jeux et donc le paramètre nombre de sémaphores est configurable.

Selon une autre caractéristique, pour un nombre de données de l’ordre du millier, un nombre de sémaphores sensiblement égal à 12 apparaît constituer une bonne mesure.

Le procédé selon l’invention est avantageusement appliqué à un contrôle commande de moteur à explosion exécuté sur un processeur multi-cœur, chaque cœur constituant une unité de traitement C1 , C2.

L’invention a été illustrée et décrite en détail dans les dessins et la description précédente. Celle-ci doit être considérée comme illustrative et donnée à titre d’exemple et non comme limitant l’invention à cette seule description. De nombreuses variantes de réalisation sont possibles.

Liste des signes de référence

C1, C2 : unité de traitement, cœur,

T 1 , T2 : tâche,

SEM1, SEMi : sémaphore,

DT : attente,

11, I2, I3, I4 : interruption,

P( ) : prise de sémaphore,

L( ) : libération de sémaphore,

? : interrogation disponibilité sémaphore,

B1 : buffer, MG : mémoire globale,

FO, F1 , Fi : indicateur de réalisation, i : indice, r1 , r2 : lecture d’une donnée, w1 , w2 : écriture d’une donnée,

CTR : compteur de réalisation,

N : nombre de buffers, sémaphores,

FILL, FILL1 : commande de remplissage, FLUSFI, FLUSFI1 : commande de vidage.]