Brevet FR2791444A1 — publié le 20000929

Procédé et dispositif de gestion automatique des allocations-mémoire d'une mémoire vive principale L'invention concerne la gestion automatique des allocations- mémoire d'une mémoire vive principale et plus particulièrement la récupération automatique de place mémoire libre au sein d'une mémoire ayant subi une fragmentation au cours de l'exécution d'un programme implémenté dans un système de traitement de données numériques, par exemple un processeur ou une machine virtuelle, accédant à ladite mémoire. De la mémoire fragmentée est un espace mémoire inutilisé et qui ne peut pas être utilisé par le système de traitement de données pour satisfaire une requête d'allocation mémoire. Plus précisément, la mémoire fragmentée due à une fragmentation, dite externe, est une partie disponible de l'espace mémoire mais qui se compose de segments non contigus, de telle sorte qu'une requête d'allocation- mémoire d'une taille supérieure au plus grand des segments disponibles, ne peut pas être satisfaite même si la taille totale de la mémoire fragmentée serait suffisante pour satisfaire à ladite requête. Cette fragmentation externe conduit donc à une perte de la capacité mémoire. Le pourcentage de capacité mémoire ainsi perdue à cause de la fragmentation externe peut être très élevé, et ainsi, quelques éléments seulement, stockés dans la mémoire peuvent empêcher de larges espaces de mémoire d'être utilisés pour satisfaire à des requêtes d'allocation mémoire de grande taille. Un moyen classique pour remédier aux inconvénients de la fragmentation externe est d'implémenter une récupération automatique des espaces mémoire libres (dite "ramasse miettes" ou "Garbage Collector" en langue anglaise) capable de déplacer les segments stockés à certains endroits de la mémoire pour les stocker à d'autres endroits de façon à regrouper les segments-mémoire libres pour former un bloc continu disponible pour toute requête d'allocations-mémoire continu dont la taille n'excède pas celle du bloc-mémoire ainsi libéré. Ceci étant, pour éviter de remettre à jour toutes les références d'un élément qui a été bougé au sein de l'espace mémoire, des cellules ou "poignées" spécifiques (handles en langue anglaise) sont utilisées et tous les accès aux segments de mémoire sont effectués via une telle poignée spécifique. Ceci a cependant pour conséquence de doubler le nombre des accès mémoire imposant ainsi une durée d'exécution plus importante pour le programme. Par ailleurs, déplacer des éléments dans l'espace mémoire, et par conséquent modifier les adresses de ces éléments complique de façon significative l'optimisation des compilateurs puisque la détermination des adresses pour ces éléments, qui sont effectuées dans un code de compilation ou code-machine, peuvent devenir invalides lors de la mise en oeuvre du module de récupération automatique de place mémoire. En outre, déplacer des éléments de taille importante, comme des tableaux importants, provoque des pauses non prédictibles dans l'exécution du programme, pauses dont la durée dépend de la taille des éléments et qui ne sont pas compatibles avec un système temps réel, comme par exemple un calculateur embarqué. L'invention vise à apporter une solution à ces problèmes. L'invention a pour but d'éliminer toute fragmentation externe de mémoire, et ce sans nécessiter de déplacement des éléments stockés en mémoire. Un autre but de l'invention est de s'affranchir de l'utilisation de "poignées" spécifiques (handles) et par conséquent d'éviter de prévoir une capacité mémoire supplémentaire pour l'implémentation de telles poignées. L'invention a également pour but de proposer une gestion automatique de mémoire qui soit compatible avec un traitement temps réel. L'invention propose donc un procédé de gestion automatique des allocations-mémoire d'une mémoire vive principale par un système de traitement de données numériques, notamment un processeur ou une machine virtuelle, exécutant un programme implémenté dans ledit système, par exemple une machine virtuelle utilisant le langage JAVA (marque déposée) bien connu de l'homme du métier. Selon une caractéristique générale de l'invention, on partitionne l'espace mémoire de la mémoire vive princpale en au moins un groupe composé de plusieurs blocs-mémoire de taille mémoire identique et fixe pendant au moins une période temporelle de ladite exécution. Et, en présence d'une requête d'allocation-mémoire au cours de ladite période temporelle pour le stockage d'un élément dans ladite mémoire, on applique automatiquement un graphe de décomposition sur ledit élément de façon à le décomposer en au moins une partie élémentaire ayant une taille inférieure ou égale à ladite taille mémoire, et on stocke chaque partie élémentaire dans un bloc-mémoire totalement disponible, tous les blocs-mémoire alloués pour cette requête étant reliés conformément à un graphe de blocs identique au graphe de décomposition. En d'autres termes, la mémoire est divisée en blocs de taille égale. Les requêtes d'allocation mémoire de petite taille peuvent être satisfaites en allouant un seul bloc-mémoire tandis que des requêtes de tailles plus importantes requièrent plusieurs blocs. Cependant, les blocs-mémoire de l'espace mémoire ne bougent jamais et tout bloc totalement disponible peut être utilisé pour toute requête d'allocation mémoire, quelle que soit la taille de la requête. Ainsi, de part l'utilisation automatique de blocs-mémoire identiques ayant une taille fixée, aucune fragmentation externe de la mémoire ne se produit, et tout bloc-mémoire disponible est toujours directement utilisable pour de nouvelles allocations-mémoire. Les compilateurs peuvent ainsi optimiser et réutiliser des calculs d'adresse puisque les adresses des éléments mémorisés ne changent jamais. Par ailleurs, un tel procédé de gestion de mémoire est compatible avec une exécution d'un programme temps réel puisque aucun élément mémorisé dans la mémoire n'est mobile. Il n'y a donc plus de problèmes dûs à de longues pauses provoquées par le déplacement d'éléments de grande taille mémorisés dans la mémoire afin de rassembler des segments-mémoire disponibles. Par ailleurs, puisque le dispositif de gestion automatique des allocations-mémoire ne fonctionne que sur des blocs de taille identique, il devient facile à implémenter et à vérifier. Ceci est particulièrement intéressant lorsque des certifications sont requises pour des systèmes o la sécurité est particulièrement importante. Au sens de la présente invention, l'expression "graphe de décomposition" ou "graphe de blocs" doit être prise dans un sens très large. En effet, le type d'accès mémoire le plus fréquent est un accès à un élément de petite taille. Dans ce cas, ces accès peuvent être effectués directement en utilisant un seul bloc-mémoire disponible de taille fixée. Plus précisément, lorsque la taille de l'élément est inférieure ou égale à un seuil prédéterminé, le graphe de décomposition conserve l'élément dans son intégralité, cet élément étant alors stocké dans son intégralité dans un seul bloc-mémoire totalement disponible. Par contre, pour des éléments de grande taille notamment, on décompose l'élément en plusieurs parties élémentaires que l'on stocke respectivement dans plusieurs blocs-mémoire disponibles, certains des blocs-mémoire du graphe de bloc contenant une information de lien permettant de désigner automatiquement le bloc suivant dans le graphe. Le graphe de décomposition peut être simplement une chaîne. Une telle chaîne peut être appliquée pour des objets de type JAVA. En variante, le graphe de décomposition peut être une arborescence. Il en est ainsi en particulier lorsque l'élément à stocker est un tableau. Dans certaines applications, on peut partitionner l'espace mémoire en plusieurs groupes de blocs-mémoire. Tous les blocs- mémoire d'un groupe ont la même taille fixe pendant au moins ladite période temporelle d'exécution du programme. Par contre, la taille- mémoire des blocs d'un groupe est différente de la taille mémoire des blocs d'un autre groupe. On stocke alors un élément dans des blocs- mémoire appartenant à ces groupes. A cet égard on peut stocker un élément dans des blocs mémoire appartenant tous à un même groupe ou à des groupes différents. Il est également possible de modifier la taille mémoire au cours de l'exécution du programme, la nouvelle taille mémoire restant identique et fixe pour tous les blocs-mémoire de chaque groupe pendant au moins une autre période temporelle de l'exécution du programme. L'invention a également pour objet un dispositif de gestion automatique des allocations-mémoire d'une mémoire vive principale, comprenant, outre ladite mémoire, un système de traitement de données numériques, par exemple un processeur, une machine virtuelle, un compilateur ou un interpréteur, apte à accéder à la mémoire pendant l'exécution d'un programme implémenté dans ledit système. Selon une caractéristique générale de l'invention, l'espace mémoire de la mémoire est partitionné en au moins un groupe composé de plusieurs blocs-mémoire de taille- mémoire identique et fixe pendant au moins une période temporelle de ladite exécution. Le système comprend des moyens aptes, en présence d'une requête d'allocation-mémoire au cours de ladite période temporelle pour le stockage d'un élément dans ladite mémoire, à appliquer automatiquement un graphe de décomposition sur ledit élément de façon à le décomposer en au moins une partie élémentaire ayant une taille inférieure ou égale à ladite taille mémoire. Le système comporte également des moyens aptes à stocker chaque partie élémentaire dans un bloc-mémoire totalement disponible de la mémoire, tous les blocs-mémoire alloués pour cette requête étant reliés conformément à un graphe de blocs identique au graphe de décomposition. Selon un mode de réalisation préféré de l'invention, le système est une machine virtuelle, par exemple une machine virtuelle JAVA, comportant un compilateur apte, en présence d'une instruction de requête d'allocation mémoire, à générer automatiquement le code- machine permettant d'accéder à ladite mémoire conformément audit graphe de bloc ou de décomposition. En d'autres termes, la décomposition des éléments ainsi que la construction du graphe de blocs pour les accès mémoire, sont totalement transparents pour l'utilisateur. D'autres avantages et caractéristiques de l'invention apparaîtront h l'examen détaillé de modes de réalisation et de mise en oeuvre, nullement limitatifs, et des dessins annexés sur lesquels: - la figure 1 illustre schématiquement un mode de mise en oeuvre d'un moyen de récupération de place disponible dans une mémoire, appartenant à l'art antérieur, - la figure 2 illustre très schématiquement un mode de réalisation d'un dispositif de gestion automatique d'allocations- mémoire selon l'invention, permettant une mise en oeuvre du procédé selon l'invention, et, - les figures 3 à 5 illustrent des mises en oeuvre du procédé selon l'invention permettant le stockage d'éléments de types différents et de grande taille dans une mémoire selon l'invention. Sur la figure 1, la référence MM désigne une mémoire vive principale dans laquelle sont stockés des éléments ou objets OB1, OB2 et OB3, à des adresses différentes. Au cours de l'exécution d'un programme implémenté dans un processeur accédant à ladite mémoire, les segments SM1, SM2 et SM3 de l'espace mémoire de la mémoire MM, qui étaient précédemment affectés à d'autres objets, ont ét6 lib6rés. L'algorithme de r6cupération de place-mémoire disponible (Garbage Collector) d6tecte alors de façon classique et connue par l'homme du métier les segments disponibles SM1-SM3 et déplace les objets OB2 et OB3 de façon à former à partir des segments fragmentés SM1, SM2 et SM3 un segment de m6moire disponible continu SM4, illustr6 sur la partie droite de la figure 1, segment SM4 qui est alors capable de recevoir un nouvel objet de grande taille OB4. Selon l'invention, comme illustr6 plus particulièrement sur la figure 2, on ne déplace pas les objets m6moris6s de façon à lib6rer de la place mémoire, mais, comme on va le voir plus en d6tails maintenant, on partitionne la m6moire vive principale MM en un jeu de blocs-mémoire BMi de taille identique et fixée, et chaque bloc BMi totalement disponible pourra être utilisé pour une allocation mémoire de taille quelconque par le système de traitement de données SYS. Ce système de traitement de données SYS peut être un processeur ou bien une machine virtuelle. Une machine virtuelle est une machine de traitement abstraite qui, d'une façon analogue à une machine de traitement réelle, possède un jeu d'instructions et utilise différentes zones de mémoire. En général, l'implémentation d'une machine virtuelle peut être réalisée de façon matérielle, par exemple par un processeur matériel, ou bien de façon logicielle par des implémentations de compilateur ou d'interpréteur, ou bien de façon mixte logiciel et matériel. Chaque instruction de machine virtuelle définit une opération spécifique qui doit être effectuée. La machine virtuelle n'a pas besoin de comprendre le langage informatique qui est utilisé pour générer les instructions de la machine virtuelle ou les implémentation de niveaux inférieurs à la machine virtuelle. Seul un format particulier d'instructions de machine virtuelle doivent être comprises. A titre d'exemple, des instructions de machines virtuelles peuvent être des instructions de machine virtuelles JAVA. Chaque instruction de machine virtuelle JAVA inclut un ou plusieurs octets qui codent des informations identifiant des instructions, des opérandes et toutes autres informations requises. On suppose maintenant dans l'exemple qui va être décrit que le système SYS est une machine virtuelle JAVA de 32 bits qui comporte des moyens logiciels MP de partitionnement de la mémoire MM, des moyens MD de détection des blocs-mémoire BMi disponibles (ces moyens de détection étant des moyens de structure classique et connue de l'homme du métier) ainsi que des moyens MG, dont on reviendra plus en détails ci-après sur la fonction, et dont le rôle est d'effectuer une décomposition des éléments de grande taille devant être stockés dans la mémoire MM. Tous ces moyens MP, MD et MG sont réalisés de façon logicielle. On suppose ici que chaque bloc-mémoire BMI a une taille fixe de 16 octets c'est à dire 4 mots machine de 4 octets chacun. On suppose également, en faisant référence plus particulièrement à la figure 3, qu'au cours de l'exécution du programme implément6 dans le système SYS, des objets OB1, OB2, OB4 et OB7 occupent les blocs-m6moire BM1, BM3, BM5 et BM7 tandis que les moyens de d6tection MD ont détecté que les blocs- m6moire BM2, BM4, BM6, BM8, BM9 et BM10 étaient disponibles pour une éventuelle autre allocation-mémoire. On suppose également, en faisant r6férence plus particulièrement à la figure 4, qu'un objet OB6 composé de 7 champs ou mots de 4 octets F1-F7 doit être stocké dans la m6moire MM. Les moyens MG appliquent alors automatiquement un graphe de décomposition sur l'objet OB6 de façon à le d6composer en trois parties 6élémentaires P1, P2, P3. La première partie P1 comporte un premier mot comprenant le type TY de l'objet, suivi des deux premiers mots de l'objet OB6, et d'un mot final LK1 contenant une information de lien. Cette information de lien rattache la première partie élémentaire P1 à la deuxième partie élémentaire P2 dont les trois premiers mots contiennent les trois autres mots F3, F4 et F5 de l'objet OB6 et dont le quatrième mot contient une information de lien LK2 qui rattache cette deuxième partie à la troisième partie élémentaire P3 contenant les deux derniers mots F6 et F7 de l'objet OB6. Les moyens MG stockent alors respectivement les trois parties P1, P2, P3 dans par exemple les trois blocs de mémoire disponibles BM2, BM4 et BM6. Les blocs BM2, BM4 et BM6 ne sont pas des blocs contigus et sont organis6s en un graphe de blocs analogue au graphe de décomposition de l'objet OB6. Plus particulièrement, dans le cas présent, les blocs BM2, BM4 et BM6 sont chaînés, le dernier mot ou champ de chacun des deux premiers blocs est utilisé pour désigner le bloc suivant dans la chaîme. Plus précisément, le mot LK1 contient par exemple l'adresse du premier mot du bloc BM4 tandis que le mot LK2 contient l'adresse du premier mot du bloc BM6. On remarque ici que les deux derniers mots du bloc BM6 ne sont pas occupés. Ceci étant, selon l'invention, ces deux derniers mots ne pourront pas être utilisés pour une autre allocation de mémoire tant que tous les mots du bloc ne seront pas déclarés disponibles. Pour l'implémentation de la gestion automatique des allocations-mémoire, il est nécessaire de disposer d'une information indiquant à quel endroit sont stockées les informations de type référence et de liens dans les blocs (en effet certains champs des objets peuvent également contenir des références à d'autres objets). Cette information peut être stockée dans un vecteur à un bit qui existe classiquement en parallèle avec la mémoire principale MM et qui fournit un bit par mot. Ce bit indique si le mot correspondant est une information de type référence ou de lien ou non. Ainsi, à titre indicatif, une valeur logique 1 signifiera que le mot correspondant est une information de lien ou de référence. Le code qui est requis pour accéder à l'objet ainsi décomposé est créé automatiquement par l'interpréteur ou le compilateur de la machine virtuelle, cette décomposition de l'objet mémorisé restant transparente pour l'utilisateur. Seule l'adresse du premier bloc stockant l'objet est nécessaire pour accéder à l'objet dans sa totalité. Bien entendu, pour de petits objets, dont les champs ne requièrent par exemple que 8 octets de mémoire, l'objet complet peut être stocké en totalité dans un seul bloc de 16 octets. Les tableaux sont des types particuliers d'éléments. Bien qu'il soit possible d'utiliser une arborescence du type chaîne pour décomposer et stocker des tableaux dans la mémoire, il est préférable, pour des tableaux de grande taille, d'utiliser une décomposition du type arborescence comme illustré plus particulièrement sur la figure 5. Ceci permet d'accéder plus rapidement aux données du tableau. Sur cette figure 5, un tableau TB du type JAVA, contenant 16 mots de données D1 à D16 est décomposé en six parties élémentaires P1 àP6. Plus précisément, la partie P1 est la partie de tête du tableau qui contient une information TY relative au type de l'élément mémorisé. Une information LH relative à la longueur du tableau est stockée dans le deuxième mot du bloc. Une information DH relative à la profondeur du tableau est stockée dans le troisième mot du bloc, et enfin, une information de lien LK1 permettant de pointer la deuxième partie P2 du tableau décomposé, est stock6e dans le dernier mot du bloc. Les quatre mots de la deuxième partie P2 contiennent respectivement quatre informations de liens LK2-LK5 permettant respectivement d'accéder aux quatre parties P3 à P6 contenant les données D1 à D16 du tableau. Ces parties P1 à P6 sont respectivement stockées dans les blocs-mémoire totalement disponibles BM2, BM4, BM6, BM8, BM9 et BM10. Les mots LK2, LK3, LK4 et LK5 contiennent respectivement les adresses des blocs-mémoire BM6, BM8, BM9 et BM10. Pour accéder aux éléments d'un tel tableau, il est donc nécessaire de traverser l'arborescence jusqu'à ce que les blocs d'extrémités (ou "blocs feuilles") contenant les éléments désirés aient été atteints. Bien entendu, cette structure d'arborescence n'est pas visible pour l'utilisateur de la machine virtuelle, et l'interpréteur ou le compilateur génère automatiquement le code requis pour gérer les accès à ce tableau. A titre indicatif, le code requis peut utiliser une courte boucle pour traverser la profondeur de l'arborescence jusqu'à ce que la donnée d'un bloc feuille puisse être atteinte. Ceci peut être aisément implément6 en code-machine. A titre d'exemple le pseudo-code C pour une telle boucle est le suivant: block * ptr = &array. data; for (int i = array. depth; i > o; i--)t ptr = ptr [index / node-width Ai % node- width]; } data = ptr [index % node-width]; Le coefficient node-width est une puissance constante de 2 indiquant le nombre de mots à un noeud de l'arborescence (4 dans l'exemple décrit). Bien entendu, l'homme du métier saura ajuster le code si la taille des éléments stockés dans le tableau est différente de la taille du mot machine. Il REVENDICATIONS 1. Procédé de gestion automatique des allocations-mémoire d'une mémoire vive principale par un système de traitement de données numériques exécutant un programme implémenté dans ledit système, caractérisé par le fait qu'on partitionne l'espace mémoire de la mémoire vive principale (MM) en au moins un groupe composé de plusieurs blocs-mémoire (BMi) de taille-mémoire identique et fixe pendant au moins une période temporelle de ladite exécution, et en présence d'une requête d'allocation de mémoire au cours de ladite période temporelle pour le stockage d'un élément (OB6) dans ladite mémoire, on applique automatiquement un graphe de décomposition sur ledit élément de façon à le décomposer en au moins une partie élémentaire (P1,P2,P3) ayant une taille inférieure ou égale à ladite taille- mémoire et on stocke chaque partie élémentaire (P1,P2,P3) dans un bloc- mémoire totalement disponible, tous les blocs-mémoire (BM2,BM4,BM6) alloués pour cette requête étant reliés conformément à un graphe de blocs identique au graphe de décomposition. 2. Procédé selon la revendication 1, caractérisé par le fait que lorsque la taille de l'élément est inférieure ou égale à un seuil prédéterminé, le graphe de décomposition conserve l'élément dans son intégralité, celui-ci étant alors stocké dans son intégralité dans un seul bloc-mémoire totalement disponible (BMi). 3. Procédé selon la revendication 1, caractérisé par le fait qu'on décompose l'élément en plusieurs parties élémentaires que l'on stocke respectivement dans plusieurs blocs-mémoire disponibles, certains des blocs-mémoire du graphe de blocs contenant une information de lien (LKi) permettant de désigner automatiquement le bloc suivant dans le graphe. 4. Procédé selon la revendication 3, caractérisé par le fait que le graphe de décomposition est une chaîne. 5. Procédé selon la revendication 3, caractérisé par le fait que le graphe de décomposition est une arborescence. 6. Procédé selon l'une des revendications précédentes, caractérisé par le fait qu'on partitionne l'espace mémoire (MM) en plusieurs groupes de blocs-mémoire, tous les blocs-mémoire d'un groupe ayant la même taille-mémoire fixe pendant au moins ladite période temporelle, la taille-mémoire des blocs d'un groupe étant différente de la taille-mémoire des blocs d'un autre groupe, et par le fait qu'on stocke un élément dans des blocs-mémoire appartenant à ces groupes. 7. Procédé selon l'une des revendications précédentes, caractérisé par le fait qu'on modifie la taille-mémoire au cours de l'exécution dudit programme, la nouvelle taille-mémoire restant identique et fixe pour tous les blocs-mémoire (BMi) de chaque groupe pendant au moins une autre période temporelle de l'exécution du programme. 8. Dispositif de gestion automatique des allocations-mémoire d'une mémoire vive principale, comprenant outre ladite mémoire, un système de traitement de données numériques apte à accéder à la mémoire pendant l'exécution d'un programme implémenté dans ledit système, caractérisé par le fait que l'espace-mémoire de la mémoire vive principale (MM) est partitionné en au moins un groupe composé de plusieurs blocs-mémoire (BMi) de taille-mémoire identique et fixe pendant au moins une période temporelle de ladite exécution, et par le fait que le système (SYS) comprend des moyens (MG) aptes, en présence d'une requête d'allocation de mémoire au cours de ladite période temporelle pour le stockage d'un élément dans ladite mémoire, à appliquer automatiquement un graphe de décomposition sur ledit élément de façon à le décomposer en au moins une partie élémentaire ayant une taille inférieure ou égale à ladite taille-mémoire et des moyens (MG) aptes à stocker chaque partie élémentaire dans un bloc- mémoire totalement disponible de la mémoire, tous les blocs-mémoire alloués pour cette requête étant reliés conformément à un graphe de blocs identique au graphe de décomposition. 9. Dispositif selon la revendication 8, caractérisé par le fait que le système (SYS) est une machine virtuelle comportant un compilateur apte, en présence d'une instruction de requête d'allocation mémoire, à générer automatiquement le code-machine permettant d'accéder à ladite mémoire conformément audit graphe de blocs ou de décomposition.