Gestion de mémoire par régions

En informatique, la gestion de mémoire par région est un type de gestion de mémoire avec lequel chaque objet alloué est assigné à une région. Une région, alias une zone, une arène, ou un contexte mémoire, est une collection d’objets alloués qui peut être efficacement désallouée en bloc. Comme l’allocation par pile, les régions facilitent l’allocation et la désallocation de la mémoire à faible coût ; mais elles sont plus flexibles, permettant aux objets de vivre plus longtemps que la pile d’activation dans laquelle ils ont été alloués. Dans une implémentation typique, tous les objets d'une région sont alloués dans une plage contiguë d’adresses mémoire.

Comme exemple simple, examinons le pseudocode suivant, qui alloue et puis désalloue une structure de donnée de type liste chaînée :

r ← créeRégion()
ListeDeNœuds tête ← null
pour i de 1 à 1000
    nouveauNœud ← alloueDansRégion(r, tailleDe(ListeDeNœuds))
    nouveauNœud.next ← tête
    tête ← nouveauNœud
détruitRégion(r)

Bien que la construction de la liste chaînée requière beaucoup d’opérations, elle peut être rapidement détruite par une unique opération, en détruisant la région dans laquelle ses nœuds ont été alloués. Il n’est pas nécessaire de parcourir la liste entière pour cela.

Implémentation

L’implémentation de régions simples explicites est triviale ; la description suivante est basée sur Hanson^[1]. Chaque région est implémentée comme une liste chaînée de vastes blocs de mémoire ; chaque bloc devrait être assez grand pour permettre beaucoup d’allocations. Le bloc courant comporte un pointeur vers sa prochaine position libre, et si le bloc est plein, un nouveau bloc est alloué et ajouté à la liste chaînée. Quand la région est désallouée, le pointeur vers la prochaine position libre pointe à nouveau sur le premier bloc, et la liste des blocs peut être réutilisée pour une région ultérieurement créée. Alternativement, quand une région est désallouée, sa liste de blocs peut être ajoutée en fin d’une liste globale de blocs disponibles dans laquelle d’autres régions peuvent ultérieurement allouer de nouveaux blocs. Par ce procédé simple, il n’est pas possible de désallouer des objets individuels dans une région.

Le coût total par octet alloué par ce procédé est très faible ; presque toutes les allocations ne demandent qu’une comparaison et une mise-à-jour de pointeur vers la prochaine position libre. La désallocation d’une région est une opération à durée fixe et est rarement effectuée. Contrairement aux systèmes classiques de ramasse-miettes (informatique), il n’est pas nécessaire d’étiqueter les données avec leur type.

Histoire et concepts

Le concept de base des régions est très ancien, sa première apparition date de 1967 dans le paquetage de stockage libre AED de Douglas T. Ross, dans lequel la mémoire était partitionnée en une hiérarchie de zones ; chaque zone avait son propre alloueur et une zone pouvait être libérée en une fois, rendant ces zones utilisables comme régions^[2]. En 1990, Hanson démontra que les régions explicites en C (qu’il appelait arènes) offraient une performance par octet alloué supérieure au plus rapide des mécanismes d’allocation par tas binaire^[1]. Les régions explicites étaient partie intégrante de la conception de nombreux projets précoces de logiciels écrits en C, au nombre desquels le serveur HTTP Apache, qui les appelle arènes, et le SGBD PostgreSQL, qui les appelle contextes mémoriels^[3]. Comme l’allocation par tas binaire traditionnelle, ce procédé ne garantit pas la sécurité mémoire; il est possible pour un programmeur d’accéder à une région, après qu’elle ait été désallouée, par un pointeur pendant, ou bien d’oublier de désallouer une région, provoquant une fuite de mémoire.

Inférence de régions

En 1988, des chercheurs commencèrent à étudier comme utiliser les régions pour une allocation sécurisée de la mémoire en introduisant le concept d’inférence de région, où la création et la désallocation de régions, tout comme l’affectation d’expressions d’allocation statique individuelle à des régions précises, sont insérées par le compilateur au moment de la compilation. Le compilateur en est capable de façon à garantir que les pointeurs pendants et les fuites mémoires ne se produisent pas.

Dans les premiers travaux de Ruggieri et Murtagh^[4], une région est créée au début de chaque fonction et désallouée à la fin. Ils effectuent alors une analyse de flux de données pour déterminer la durée de vie de chaque expression d’allocation statique et l’assignent à la région la plus récente qui inclue sa durée de vie complète.

En 1994 ce travail fut généralisé par un travail fécond de Tofte and Talpin pour prendre en charge le polymorphisme de type et les fonctions d'ordre supérieur dans Standard ML, un langage de programmation fonctionnelle qui utilise un algorithme différent basé sur l’inférence de types et les concepts théoriques de types de région polymorphiques et de calcul de région^[5],[6]. Leurs travaux introduisirent une extension du λ-calcul qui inclut les régions en ajoutant deux constructions :

e₁ at ρ : calcule le résultat de l’expression e₁ et la stocke dans la région ρ;

letregion ρ in e₂ end : Crée une région and la lie à ρ ; évalue e₂; et désalloue la région.

À cause de cette structure syntaxique, les régions sont imbriquées, c’est-à-dire que si r₂ est créée après r₁, elle doit aussi être désallouée avant r₁ ; cela équivaut à une pile de régions. De plis, les régions doivent être désallouées par la fonction même dans laquelle elles sont créées. Ces restrictions ont été abandonnées par Aiken et al.^[7].

Ce λ-calcule devait servir comme une représentation intermédiaire prouvant la sécurité mémoire de programmes compilés de Standard ML vers du code machine, mais la construction d’un traducteur qui produise de bons résultats avec de gros programmes a fait face à nombre de limitations pratiques qui nécessitaient de nouvelles analyses pour être résolues, en particulier les appels récursifs, les récursions terminales et l’élimination des régions ne contenant qu’une valeur isolée. Ce travail fut complété en 1995^[8] et intégré dans le Kit ML Kit, une version de ML basée sur l’allocation par région à la place du ramasse-miettes. Ceci permit une comparaison directe entre deux des programmes-tests de taille moyenne, produisant des résultats très variables (« entre 10 fois plus rapide de quatre fois plus lent ») selon que le programme tirait parti ou non des régions ; les temps de compilation, cependant, étaient de l’ordre de plusieurs minutes^[9]. Le Kit ML a finalement été utilisé avec de grosses applications avec deux additions : un mécanisme pour compiler séparément les modules et une technique hybride combinant l’inférence de région avec un ramasse-miettes^[10],[11].

Généralisation à l’environnement de nouveaux langages

À la suite du développement du Kit ML, les régions ont commencées à être généralisées à l’environnement d’autres langages :

• Extensions diverses du langage de programmation C:
  • Le dialecte C « sécurisé » Cyclone qui, parmi bien d’autres caractéristiques, ajoute la prise en charge de régions explicites et évalue l’impact de la migration d’applications C existantes pour les utiliser^{[12],[13],[14]}.
  • Une extension de C applée RC^[15] a été implementée qui utilise des régions gérées explicitement, mais utilise aussi le comptage de référence sur les régions pour garantir la sécurité mémoire en assurant qu’aucune région n’est libérée prématurément^[16],[17]. Regions decrease the overhead of reference counting, since references internal to regions don't require counts to be updated when they're modified. RC includes an explicit static type system for regions that allows some reference count updates to be eliminated^[18].
  • Une restriction de C appelée Control-C et qui force par construction les programmes à utiliser les régions (et une seule région à la fois) afin d’assurer statiquement la sécurité mémoire^[19].
• Les régions ont été implementées pour un sous-ensemble de Java^[20], et est devenu un composant critique de gestion de la mémoire pour Java temps réel, qui les combine avec les types de possession pour détecter l’encapsulation d’objects et éliminer les vérifications à l’exécution concernant la désallocation de régions^{[21],[22],[23]}. Plus récemment, un système semi-automatique a été proposé pour les régions inférantes dans des applications Java temps-réel embarquées, qui combine une analyse statique à la compilation, une politique d’allocation de régions à l’exécution et des indications venant du programmeur^[24],[25]. Les régions conviennent bien pour la programmation temps-réel car leur surcoût temporel est statiquement prédictible, sans la complexité des ramasse-miettes incrémentiels.
• Elles ont été implémentées pour les langages de programmation logique Prolog^{[26],[27],[28]} et Mercury^[29],[30] en étendant le modèle d’inférence de régions de Tofte and Talpin à la prise en charge la rétrospective et les abattements.

Désavantages

Les systèmes utilisant les régions peuvent être amenés à accumuler beaucoup de données (dont une proportion élevée de données mortes) dans les régions avant de pouvoir les désallouer ; ces cas sont communément appelés « fuites » (même si au final ces régions sont libérées). Éliminer les fuites peut nécessiter de restructurer le programme, par exemple en introduisant de nouvelles régions à la durée de vie plus courte. Débuguer ce type de problème est particulièrement difficile avec des systèmes utilisant l’inférence de région : le programmeur doit alors comprendre l’algorithme d’inférence sous-jacent ou examiner la représentation intermédiaire commentée pour diagnostiquer le problème. Les ramasse-miettes traçants sont plus efficaces pour désallouer ce genre de données dans un temps raisonnable sans nécessiter pour autant de bouleverser la programmation ; cela a d’ailleurs été une justification des systèmes hybrides région/ramasse-miettes^[10]. D’un autre côté, les ramasse-miettes traçants peuvent aussi montrer des fuites subtiles, si des références aux données sont conservées alors qu’elles ne seront plus jamais utilisées.

La gestion de mémoire basée sur les régions marche mieux quand le nombre de régions est relativement petit et que chaque région contient beaucoup d’objets ; les programmes qui s’appuient sur beaucoup de régions clairsemées montreront des signes de fragmentation interne de mémoire, conduisant à un gâchis de mémoire et à un surcoût temporel pour la gestion des régions. À nouveau, en présence d’une inférence de régions, un tel problème peut être plus difficile à diagnostiquer.

Méthodes hybrides

Comme mentionné ci-dessus, RC utilise un hybride régions / comptage de référence qui limite le surcoût du comptage de références dans la mesure où les références internes aux régions ne nécessitent pas de comptage pour être mises à jour quand elles sont modifiées. De même, quelques méthode hybrides à marquage de région combinent les ramasse-miettes avec les régions ; elles fonctionnent en divisant le tas binaire en régions, en effectuant une passe balaie-marque dans laquelle chaque région contenant des objets vivants est marquée puis en libérant les régions non marquées. Cela nécessite une défragmentation continuelle pour rester efficace^[31].

Références

Sources

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Region-based memory management » (voir la liste des auteurs)

• Portail de l’informatique