FR 2676845 A1 19921127 FR 9106674 A 19910523 DISPOSITIF POUR LA GESTION DE PLUSIEURS FILES D'ATTENTE INDEPENDANTES DANS UN ESPACE MEMOIRE COMMUN ET BANALISE. La présente invention concerne un dispositif pour la gestion de plusieurs files d'attente indépendantes dans un espace mémoire commun et banalisé, sans allocation statique, a priori, d'une partie de l'espace alloué à chaque file d'attente. Elle a plus particulièrement pour objet un dispositif de ce type permettant une allocation dynamique des cases mémoire au fur et à mesure des besoins, de manière à assurer une optimisation globale de la ressource mémoire. Elle propose un dispositif structurellement simple, effi- cace et qui ne met pas en oeuvre de mécanisme à base de listes de pointeurs chaînes comme c'est le cas dans les solutions traditionnelles. Elle s'adresse principalement à des applications dans lesquelles l'ordre de dépilement des files d'attente n'est pas forcément le même que l'ordre d'empilement, étant entendu qu'une identité entre ces deux ordres pourra être éventuellement garantie moyennant des contraintes d'utilisation appropriées. 2 - On sait qu'un dispositif de ce genre doit comprendre des moyens permettant de déterminer à tout instant les posi- tions de l'espace mémoire qui sont libres et celles qui sont utilisées par les files d'attente, ainsi que l'appartenance des positions déjà utilisées, à l'une ou l'autre des files d'attente. Ce dispositif doit en outre comprendre des moyens permet- tant de rechercher, pour chacune des files, le contenu mémoire de la position la plus anciennement réservée, des moyens de libérer cette position mémoire et de la prendre en compte dans la liste des positions mémoire disponibles lorsque son contenu a été pris en compte (dépilé). Pour parvenir à ces résultats, le dispositif selon l'invention met en oeuvre, avec un séquencement appro- prié: un ensemble de vecteurs d'utilisation des ressources, à raison de un vecteur par file d'attente, chaque vecteur comportant un nombre N de bits égal à celui des ressources élémentaires disponibles dans l'espace mémoire dédiée au stockage des mots constituant la file d'attente; un vecteur définissant la liste des positions libres de l'espace mémoire; un registre pointeur d'écriture d'une dynamique de g 2 (n) bits qui conserve l'adresse codée en binaire de l'espace mémoire o il a écrit pour la dernière fois; un ensemble de registres pointeurs de lecture (un par file d'attente), ces registres ayant également une dynamique de log 2 (n) bits, chacun de ces pointeurs conservant l'adresse codée en binaire de l'espace mémoire qu'il a lu pour la dernière fois; un circuit de logique combinatoire spécifique, appelé circuit d'évaluation du plus proche successeur, conçu de manière à permettre au dispositif d'exécuter les séquences de lecture et d'écriture suivantes: 3 - 1 une séquence d'écriture dans une file d'attente déterminée au cours de laquelle il prend en compte la position occupée de l'espace mémoire o il a écrit la dernière fois, cette position étant codée en un parmi n, il confronte cette adresse ainsi codée aux adresses des positions libres de l'espace mémoire de manière à déterminer l'adresse d'une position libre constituant le plus proche successeur de ladite posi- tion occupée, il alloue l'adresse de cette position libre au pointeur d'écriture, il procède à l'écriture à cette adresse, puis il procède à la mise à jour du vecteur d'utilisation des ressources correspondant à la file d'attente considérée et, en conséquence, à la mise à jour du registre définissant les positions libres de l'espace mémoire, 2 une séquence de lecture au cours de laquelle il prend en compte la position du dernier mot qui a été lu dans la file, il recherche ensuite parmi les positions occupées par la file, le plus proche successeur à cette dernière position, il alloue l'adresse de cette position au pointeur de lecture de manière à procéder à la lecture de l'espace mémoire correspondant à cette position et, parallè- lement, il procède à la mise à jour du vecteur d'utilisation des ressources correspondant à la file d'attente considérée et du registre définissant les positions libres de l'espace mémoire. Il importe de noter que dans la définition qui précède, ainsi que dans la suite de la description, un "vecteur" est un mot binaire de N bits à chacun desquels est asso- ciée la signification "occupé" ou "libre" d'une ressource matérielle, ce vecteur étant modifiable bit à bit. Il apparaît donc que le dispositif précédemment décrit présente l'avantage de permettre d'utiliser toutes les ressources mémoire, une même ressource pouvant être uti- lisée par n'importe quelle file d'attente. 4 - Selon une caractéristique de l'invention, le processus d'évaluation du plus proche successeur est basé sur une relation d'ordre cyclique de l'ensemble des ressources élémentaires E (de cardinal n) disponibles dans l'espace mémoire alloué à la gestion des files d'attente, cette relation étant telle que chaque élément de l'ensemble E ait un prédécesseur unique et un successeur unique. Les éléments de l'ensemble E sont alors ordonnés selon cette relation d'ordre en une chaîne rebouclée et dispo- sant d'une orientation. Si on ouvre la chaîne matérialisant la relation d'ordre cyclique entre un élément quelconque de E et son prédé- cesseur immédiat, on peut définir une relation d'ordre strict (notée >) sur l'ensemble E dont e est le plus petit élément. Le plus proche successeur de e dans le sous ensemble E' est l'élément e' de E' (noté PPSET(e)) tel que, quel que soit l'élément a appartenant à E' et distinct de E, on ait la relation a > e' > e Cette définition devra être utilisée dans la suite chaque fois qu'il sera question de la notion de "plus proche successeur". Un mode d'exécution de l'invention sera décrit ci-après, à titre d'exemple non limitatif, avec référence aux dessins annexés dans lesquels La figure 1 est un schéma théorique illustrant la structure d'un circuit interface entre un processeur et plusieurs voies de transmission (émission/réception), cet interface assurant la gestion des files d'attente associées à chacune de ces voies; - La figure 2 est un schéma synoptique du circuit de gestion utilisé dans l'interface représenté figure 1; La figure 3 est un schéma du circuit de déter- mination du plus proche successeur de la posi- tion mémoire occupée la dernière fois; La figure 4 est un schéma du circuit de déter- mination des positions libres ou réservées, selon le cas, de l'espace mémoire utilisé dans le circuit de la figure 2; La figure 5 est une représentation schématique, dans l'espace du circuit représenté figure 3. Le circuit représenté sur la figure 1 est destiné à assu- rer l'interface d'entrée/sortie entre des lignes de transmission de type série sur lesquelles circulent des informations conformes à la norme ARINC 429 en vigueur dans l'aéronautique, qui se présentent sous la forme d'une succession de mots de trente deux bits comprenant chacun, successivement: un premier nombre de huit bits (de O à 7) définissant une étiquette ou "label", un second nombre de deux bits ( 8 et 9) servant à iden- tifier la source ou la destination du mot (SDI), un troisième nombre de vingt et un bits ( 10 à 30) contenant les données à transmettre et, un bit de parité (bit 31). Dans cet exemple, le circuit d'interface, qui est repré- senté par un bloc 1, est connecté, d'une part à une unité locale à microprocesseur P associé à une mémoire vive 6 2676845 RAM 1 par l'intermédiaire d'un BUS de données 2, de contrôle 3 et d'adressage 4 et, d'autre part à deux voies , 6 de réception d'informations conformes à la norme ARINC 429, par l'intermédiaire d'un démodulateur 7, et à deux voies 8, 9 d'émission d'informations par l'intermédiaire d'un modulateur de ligne 10. Ce circuit fait plus précisément intervenir, connectés par un BUS interne Il un bloc d'émission 12 connecté au modulateur 10 et uti- lisant une mémoire tampon formée de deux registres 13 de seize bits permettant de stocker le demi-mot en cours d'émission sur chacune des voies (ces tampons constituant un prolongement de la zone mémoire Zl décrite ci-après), dans laquelle les mots correspondant à chacune des voies sont organisés en file d'attente, un bloc de réception 14 connecté au démodulateur 7 et utilisant une mémoire tampon formée de deux registres de seize bits permettant d'accumuler les bits des demi-mots ARINC reçus sur chacune des deux voies avant leur transfert dans la zone mémoire Z 2 décrite ci- après, un interface de liaison 16 (seize bits) avec l'unité locale à microprocesseur P, une mémoire vive RAM 2 associée à un circuit de gestion des données 17, cette mémoire vive pouvant constituer le prolongement des deux mémoires tampon 13, 15, un automate 19 servant à piloter un générateur d'adresse 10 associé à la mémoire RAM 2 par l'intermédiaire d'un pointeur d'émission 21 et d'un pointeur de réception 22. Les mots à émettre sur les voies 8 et 9 sont fournis par le processeur P et stockés dans la zone Zl de la RAM 2 avant leur sérialisation. Cette zone mémoire Zl est gérée à la façon d'une pile FIFO, avec allocation dynamique, afin d'optimiser son occupation en fonction de la vitesse de transmission programmée pour chacune des deux voies 8, 9 (la capacité de cette zone mémoire est, par exemple, de trente deux mots ARINC pour l'ensemble des deux voies). Le chargement d'un mot ARINC (trente deux bits) dans la zone mémoire Zl est déclenché par l'unité centrale P et s'effectue en deux temps successifs: transfert des seize bits de poids faible puis des seize bits de poids fort. La sérialisation d'un mot ARINC sur une voie 8, 9 désirée ne peut s'effectuer que lorsque: ses demi-mots ont été chargés par l'unité centrale (processeur P) dans la zone mémoire Zl, l'ensemble des mots précédemment transmis vers cette voie ont été totalement émis. L'émission débute sur une voie dès qu'un mot complet a été chargé dans une paire de mots de seize bits d'adresses consécutives allouée en zone Zl à la voie considérée par le dispositif d'allocation dynamique contenu dans le pointeur d'émission 21. La réception des mots ARINC provenant des voies 5, 6 s'effectue comme suit: Chaque mot reçu ayant satisfait aux contrôles demandés est mis en mémoire, après substitution de son trente deuxième bit de parité par le numéro de voie sur lequel il est arrivé, dans une zone Z 2 de la mémoire RAM 2 gérée 7 - en pile FIFO de capacité de soixante quatre demi- mots ARINC. La restitution complète d'un mot ARINC ainsi stocké est déclenchée par le processeur P et nécessite deux phases de lecture successives de cette dernière, à savoir: une phase de lecture des seize bits de poids faible pf, une phase de lecture des seize bits de poids fort PF. Lorsque la zone de mémoire Z 2 gérée en pile FIFO est vide, les deux lectures déclenchées par l'unité centrale se concluront par la restitution d'un code spécial, par exemple OOO Oh. Le circuit de gestion des files d'attente utilisé par l'interface précédemment décrit fait intervenir: des moyens permettant d'effectuer la mise à jour d'un vecteur d'utilisation des ressources, ici d'une largeur de trente deux bits, dont chaque bit indique l'état, libre ou occupé, d'une position mémoire et des vecteurs permettant d'indiquer l'appartenance de chaque position mémoire occupée à l'une des files d'attente gérée, un registre pointeur d'écriture (matérialisé par la bascule DE sur la figure 2) qui contient l'adresse de la position mémoire o est réalisée une écriture et qui est mise à jour avant chaque nouvelle écriture, des registres pointeurs de lecture (matérialisés par des bascules DL 1, DL 2 sur la figure 2), à raison de un par file d'attente gérée, chacun de ces pointeurs indi- quant la position du dernier mot qui est lu ou émis sur la voie correspondante, et qui sont mis à jour avant chaque lecture dans la file associée, 8 - un réseau de logique combinatoire LC destiné à détermi- ner le plus proche successeur de la position précédem- ment sélectionnée dans les vecteurs d'utilisation des ressources. Ce circuit de gestion comprend en outre des moyens logiques (bloc Cl figure 2) ayant pour but: d'une part, d'envoyer, avant chaque écriture, sur l'entrée d'horloge H du registre d'écriture DE, une impulsion d'horloge destinée à provoquer la mise en mémoire de l'adresse de la prochaine écriture, qui a été déterminée par le circuit de logique combinatoire, et d'autre part, d'envoyer avant chaque lecture, sur l'entrée d'horloge H du registre de lecture DL 1, DL 2 correspondant à la voie à traiter, une impulsion d'horloge de manière à mémoriser l'adresse de la posi- tion mémoire o s'effectuera la prochaine lecture sur la même voie. Dans l'exemple représenté sur la figure 2, les registres DE, DL 1, DL 2 sont des registres parallèles à cinq bits qui transmettent les informations qu'ils contiennent, par l'intermédiaire d'un circuit d'aiguillage, à un conver- tisseur DEC apte à effectuer une conversion 5/32 bits avec un codage 1 parmi 32 (un seul bit à l'état 1 sur les trente deux bits de sortie) Les trente deux sorties de ce convertisseur DEC sont connectées aux trente deux entrées REF du circuit de logique combinatoire LC, de la façon qui sera précisée dans la suite de la description en regard des figures 3 et 5. Le circuit d'aiguillage utilisé en sortie des registres DE, DL 1, DL 2 comprend deux circuits sélecteurs en cascade, à savoir: 9 - - un circuit sélecteur de voie SV dont les entrées (deux fois cinq) sont respectivement connectées aux sorties des deux registres DL 1, DL 2 et, un circuit sélecteur lecture/écriture SLE 1 dont les entrées (deux fois cinq) sont respectivement connectées aux sorties du registre d'écriture DE et aux sorties du sélecteur de voies SV. Les sorties de ce sélecteur SLE 1 sont respectivement connectées aux cinq entrées du convertisseur DEC. Les entrées des registres DE, DL 1, DL 2 sont connectées à la sortie d'un convertisseur COD 32/5 bits par l'intermédiaire d'un BUS commun BC à cinq conducteurs. Les trente deux entrées de ce convertisseur COD qui sont destinées à recevoir l'adresse de la position mémoire du plus proche successeur de la position de référence, cette adresse étant codée selon le code 1 parmi 32, sont reliées aux trente deux sorties TAB OUT du circuit de logique combinatoire. Tel que représenté sur les figures 3 et 5, ce circuit de logique combinatoire se compose de trente deux circuits élémentaires (circuits 0, 1 n-l) comprenant chacun: une première porte ET El dont une entrée est connectée, par l'intermédiaire d'un inverseur Il, à l'une des trente deux sorties TAB IN d'un circuit de détermina- tion des positions selon le cas libres ou occupées par la file considérée de l'espace mémoire PL, et dont la deuxième entrée chain(i) est rebouclée sur une sortie chain(i+l) du circuit élémentaire précédent, une porte OU dont une entrée est connectée à la sortie de la première porte ET El, E 2 En, et dont l'autre entrée est connectée à l'une des trente deux sorties il - REF du convertisseur DEC, la sortie de cette porte OU constituant la sortie chain(i+l) qui est reliée à l'entrée chain(i) du circuit élémentaire suivant, une deuxième porte ET E 2 dont une entrée est reliée à la sortie de la porte OU par l'intermédiaire d'un inverseur I 2 et dont l'autre entrée est connectée à la deuxième entrée chain(i) du premier circuit ET El. un rebouclage de la sortie chain(n) du n-lème et dernier circuit sur l'entrée chain(O) du premier circuit élémentaire. Le circuit PL de détermination des positions libres ou réservées par la voie considérée de l'espace mémoire comprend, comme représenté sur la figure 4, deux vecteurs DT 1, DT 2 de trente deux bits (un par file d'attente gérée) qui indiquent chacun les positions de la mémoire occupées par la file d'attente correspondante La mise à jour de ces deux vecteurs DT 1, DT 2 est assurée par un circuit logique approprié C 2 Les entrées D des bascules qui composent ces vecteurs reçoivent un signal représen- tatif d'une commande de lecture ou d'écriture (lecture -, mise à zéro, écriture -à mise à 1 du bit correspondant). Les horloges de chaque bascule constituant le vecteur étant indépendantes et actionnées par la logique C 2 de manière à ce que seule une bascule soit activée à la fois: celle correspondant à la position sur laquelle est effectuée le traitement en cours. Les sorties de même rang des vecteurs DT 1 et DT 2 sont connectées, d'une part, aux deux entrées respectives d'un circuit OU complémenté OC, et d'autre part, aux deux entrées d'un sélecteur de voie SV 2. 12 2676845 Les sorties de ce circuit OU complémenté OC et de ce sélecteur de voie SV 2 sont reliées aux deux entrées d'un deuxième sélecteur lecture/écriture SLE 2. La sortie du sélecteur lecture/écriture SLE 2 est connec- tée à une entrée TAB IN correspondante du circuit de logique combinatoire LC. Compte tenu du fait que les registres ont chacun trente deux bits, on aura donc trente deux circuits OU complé- mentés OC, trente deux sélecteurs de voie SV 2 et trente deux sélecteurs lecture/écriture SLE 2 dont les sorties sont respectivement connectées aux trente deux entrées TAB IN. Il est clair qu'en position écriture, ce circuit de détermination va fournir les positions libres de l'espace mémoire (bits à un des trente deux sorties). En position lecture, le circuit indiquera sur sa sortie les positions mémoire occupées par la file d'attente associée à la voie correspondante. Le fonctionnement des circuits précédemment décrits est le suivant: En position écriture, c'est-à-dire lorsque le processeur P veut écrire dans la file d'attente correspondant à une voie déterminée, il transmet sur les sélecteurs SLE 1, SLE 2, un signal de sélection correspondant à la position écriture et, sur les sélecteurs SV 1, SV 2, un signal de sélection indiquant la voie. Il dispose, grâce au registre DE, de l'adresse de la position mémoire o s'est effectuée la dernière écriture. Cette adresse est appliquée sur l'entrée REF du circuit de logique combinatoire sous la forme 1 parmi 32. 13 2676845 Parallèlement, le circuit PL indique sur les trente deux entrées TAB IN du circuit de logique combinatoire LC, les positions libres de l'espace mémoire alloué aux files d'attente. Grâce au rebouclage chain(i), chain(i 1), le circuit de logique combinatoire LC va traiter successivement chaque bit de son entrée TAB IN avec son bit correspondant de l'entrée REF(i) Le circuit permet de déterminer parmi les positions libres de l'espace mémoire, celle qui constitue le plus proche successeur de la position indi- quée à l'entrée REF du circuit logique LC. Cette position est indiquée à la sortie TAB OUT du circuit logique, sous la forme d'un mot de trente deux bits code 1 parmi 32. Le mot présent à la sortie TAB OUT du circuit logique LC est converti en un mot de cinq bits appliqué au BUS commun BC, pour être ensuite mémorisé dans le registre DE. Le contenu de DE peut alors être utilisé pour pointer dans l'espace mémoire, de manière à procéder à une écri- ture. Parallèlement, est mis à jour le vecteur DT 1 ou DT 2 correspondant à la file qui vient de faire l'objet d'une écriture. En position lecture, c'est-à-dire lorsqu'il veut trans- mettre une information contenue dans une file d'attente sur une voie correspondante, le dispositif dispose de la position du dernier mot qui vient d'être émis dans cette voie Le circuit de logique combinatoire LC recherche parmi les positions prises par la voie correspondante, le plus proche successeur de manière à pouvoir l'allouer au 14 - pointeur de lecture PTR LEC 1 T, PT LEC O T pour la lecture à effectuer sur cette file. Le processus de recherche du plus proche successeur est le même que celui précédemment décrit, à la différence que le circuit PL applique à l'entrée TAB IN un signal représentatif des positions occupées par la file corres- pondante (et non des positions laissées libres par toutes les files). Bien entendu, dans le vecteur DTI, DT 2 correspondant à la file, on remet à zéro le bit qui correspond à la position qui vient d'être libérée. - Revendications 1 Dispositif pour la gestion de plusieurs files d'attente indépendantes dans un espace mémoire commun et banalisé, sans allocation statique, a priori, d'une partie de l'espace alloué à chaque file d'attente, ce dispositif mettant en oeuvre: un ensemble de vecteurs d'utilisation des ressources, à raison de un vecteur par file d'attente, chaque vecteur comportant un nombre N de bits égal à celui des ressources élémentaires dans l'espace mémoire dédié au stockage des mots constituant la file d'attente, un vecteur déduit des précédents définissant la liste des positions libres de l'espace mémoire, un registre pointeur d'écriture qui conserve l'adresse codée en binaire de l'espace mémoire o il a écrit pour la dernière fois, un ensemble de registres pointeurs de lecture (un par file d'attente), chacun de ces pointeurs conservant l'adresse codée en binaire de l'espace mémoire qu'il a lu pour la dernière fois, caractérisé en ce qu'il comprend un circuit (LC) d'évaluation du plus proche successeur grâce auquel le dispositif peut exécuter les séquences de lecture et d'écriture suivantes: une séquence d'écriture dans une file d'attente déter- minée, au cours de laquelle il prend en compte l'adresse de la position occupée de l'espace mémoire o il a écrit la dernière fois, il confronte cette adresse aux adresses des positions libres de l'espace mémoire de manière à déterminer l'adresse d'une position libre constituant le plus proche successeur de ladite posi- 16 - tion occupée, il alloue l'adresse de cette position libre au pointeur d'écriture, il procède à l'écriture à cette adresse, puis il procède à la mise à jour du vecteur d'utilisation des ressources correspondant à la file d'attente qui vient de faire l'objet d'une écri- ture et, par conséquent du vecteur définissant les positions libres de l'espace mémoire, une séquence de lecture au cours de laquelle il prend en compte la position du dernier mot qui a été lu dans la file d'attente considérée, il recherche ensuite, parmi les positions occupées par la file, le plus proche successeur à cette dernière position, il alloue l'adresse de cette position au pointeur de lecture de manière à procéder à la lecture de l'espace mémoire correspondant à cette position et, parallèlement, il procède à la mise à jour du vecteur d'utilisation des ressources correspondant à la file d'attente considérée et du registre définissant les positions libres de l'espace mémoire. 2 Dispositif selon la revendication 1, caractérisé en ce que l'adresse de la position occupée de l'espace mémoire o le processeur a écrit pour la der- nière fois est présentée sous la forme d'un chiffre binaire de N bits codé en 1 parmi n, N étant le nombre de positions mémoire de l'espace mémoire alloué aux files d'attente. 3 Dispositif selon l'une des revendications précédentes, caractérisé en ce que le circuit de logique combinatoire (LC) se compose de N circuits élémentaires comprenant la combinaison des éléments suivants, ou une combinaison fonctionnellement équivalente: une première porte ET (El) dont une entrée est connec- tée, par l'intermédiaire d'un inverseur (Il), à l'une des N sorties TAB IN d'un circuit (PL) de détermination des positions libres de l'espace mémoire, dont la deuxième entrée chain(i) est rebouclée sur une sortie chain(i+l) du circuit élémentaire précédent, une porte OU dont une entrée est connectée à la sortie de la première porte ET et dont l'autre entrée est connectée à l'une des trente deux sorties du convertis- seur DEC, la sortie de cette porte OU constituant la sortie chain(i+l) qui est reliée à l'entrée chain(i) du circuit élémentaire suivant, une deuxième porte ET dont une entrée est reliée à la sortie de la porte OU, par l'intermédiaire d'un inver- seur (I 2), et dont l'autre entrée est connectée à la deuxième entrée chain(i) du premier circuit ET, un rebouclage de la sortie chain(n) du nlème et dernier circuit sur l'entrée chain(O) du premier circuit élémentaire. 4 Dispositif selon la revendication 3 pour la gestion d'au moins deux files d'attente, caractérisé en ce que le circuit de détermination des positions libres de l'espace mémoire comprend au moins deux vecteurs de N bits (DT 1, DT 2), à raison de un par file d'attente gérée, qui indiquent chacun les positions de la mémoire occupées par la file d'attente correspon- dante, et dont les sorties de même rang sont connectées, d'une part, aux deux entrées respectives d'un circuit OU complémenté (OC), et d'autre part, aux deux entrées d'un sélecteur de voie (SV 2), en ce que les sorties de ce circuit OU complémenté (OC) et de ce sélecteur de voie (SV 2) sont reliées aux deux entrées d'un deuxième sélec- teur lecture/écriture (SLE 2) et en ce que la sortie du sélecteur lecture/écriture (SLE 2) est connectée à une entrée TAB IN correspondante du circuit de logique combi- natoire (LC). 17 - 18 - Dispositif selon l'une des revendications précédentes, caractérisé en ce que la sortie TAB OUT du circuit de logique combinatoire (LC) est appliquée à travers un encodeur 32/5 (code) à un registre pointeur d'écriture (DE) et à un ensemble de pointeurs de lecture (DL 1, DL 2), à raison de un pointeur par file d'attente gérée, la sortie de ces registres étant connectée à l'entrée REF du circuit de logique combinatoire par l'intermédiaire d'un circuit d'aiguillage comprenant au moins un sélecteur de voie (SV 1) et un sélecteur lecture/écriture (SLE 1) suivi d'un dispositif d'encodage 1/32 (DEC).