thumb|Illustration d'un ramasse-miette compactant. En informatique, un ramasse-miettes., ou récupérateur de mémoire, ou nettoyeur de mémoire, ou nettoyeur, ou glaneur de cellules (en anglais , abrégé en GC), est un sous-système de gestion automatique de la mémoire. Il est responsable du recyclage de la mémoire préalablement allouée puis inutilisée.

Historique

Lorsqu'un système dispose d'un ramasse-miettes, ce dernier fait généralement partie de l'environnement d'exécution associé à un langage de programmation particulier. Le ramassage des miettes a été inventé par John McCarthy comme faisant partie du premier système Lisp et le premier programme de ramasse-miettes a été écrit par son étudiant Daniel J. EdwardsComme il le dit dans son interview par Jeffrey R. Yost .

Le terme français de ramasse-miettes apparaît vers 1970 dans les communications de Claude Pair aux écoles d'été de l'AFCETEn particulier les comptes-rendus de l'école d'été de Neuchâtel (Suisse) en 1972. ainsi qu'à la même époque dans ses cours d'informatique à l'université de Nancy. Il est rapidement adopté les années suivantes par Jean-Claude Derniame (Nancy), Louis Bazerque (Toulouse), Jean Cea (Nice), Jean-Pierre Verjus (Rennes), Claude Hans (Grenoble), Olivier Lecarme (Montréal) et Jacques Arsac (Paris).

Définition et fonctionnement

Le principe de base de la récupération automatique de la mémoire consiste : à déterminer quels objets ne peuvent plus être utilisés par le programme ; et à récupérer l'espace utilisé par ces objets.

Il n'est pas toujours possible de déterminer à l'avance (avant exécution) à quel moment un objet ne sera plus utilisé. En effet, les instructions qui seront exécutées dépendent des données en entrée, et aussi de la structure du programme qui peut être complexe. Il s'agit même d'un problème indécidable comme conséquence immédiate du théorème de Rice. Cependant, il est possible de découvrir au moment de l'exécution que certains objets ne peuvent plus être utilisés. En effet, un objet sur lequel le programme ne maintient plus de référence, donc devenu inaccessible, ne sera plus utilisé. Cependant, le contraire n'est pas vrai : le fait qu'il existe une référence vers un objet ne signifie pas obligatoirement qu'il sera utilisé.

Lorsque les langages sont typés, les récupérateurs peuvent correctement identifier toutes les références à un objet : ils sont appelés des récupérateurs exacts.

Dans le cas des langages faiblement typés, les récupérateurs sont conservatifs : le ramasse-miettes doit présumer que n'importe quelle suite de bits en mémoire interprétée comme un pointeur est une référence accessible. En effet, les langages faiblement typés ne permettent pas complètement à un observateur extérieur à l'application en cours d'exécution de déterminer le type des objets, et donc de connaître leur taille et l'emplacement des pointeurs qu'ils peuvent contenir. Un ramasse-miettes conservatif considère toutes les hypothèses plausibles compatibles avec ce qu'il sait des typages possibles et de l'organisation de la mémoire. De ce fait, il peut y avoir des faux positifs et le ramasse-miettes est incomplet.

Principe d'accessibilité d'un objet

Les ramasse-miettes utilisent un critère d'accessibilité pour déterminer si un objet peut être potentiellement utilisé. Les principes sont : un ensemble distinct d'objets accessibles : ce sont les racines. Dans un système typique ces objets sont les registres machine, la pile, le pointeur d'instruction, les variables globales. En d'autres termes tout ce qu'un programme peut atteindre directement. tout objet référencé depuis un objet accessible est lui-même accessible ;

Dit autrement : un objet accessible peut être obtenu en suivant une chaîne de pointeurs ou de références. Un tel algorithme est une approximation conservatrice de l'objectif idéal de libération de toutes les valeurs (ou plutôt zones mémoire) ne servant plus : certaines valeurs peuvent fort bien être accessibles depuis les racines mais ne plus jamais être utilisées. Cet objectif idéal est jugé trop complexe : déterminer quelles valeurs serviront dans le futur est équivalent au problème de l'arrêt (indécidabilité de l'arrêt, et par extension, du nombre de passages à un endroit donné - et des ressources mémoires associées, à cause de boucles, sauts, etc.), non soluble dans les cas d'une mémoire infinieSi la mémoire était réellement infinie, le ramasse-miettes serait alors inutile.. D'autre part, le comportement du programme dépend des données en entrée, par définition non connues à l'avance.

Cette approximation conservatrice est la raison de la possibilité de fuites de mémoire, c'est-à-dire de l'accumulation de blocs de mémoire qui ne seront jamais réutilisés, mais jamais libérés non plus au long de l'exécution du programme : un programme peut conserver un pointeur sur une structure de données qui ne sera jamais réutilisée. Il est pour cette raison recommandé de libérer (autrement dit autoriser le recyclage) les structures inutilisées et leurs pointeurs, afin d'éviter de conserver des références inutiles. Pour des raisons de modularité, les couches conceptuelles où l'inutilité est constatée ne sont cependant pas toujours celles où la libération peut s'effectuer sans danger.

Algorithmes de base On distingue trois familles d'algorithmes : les algorithmes à comptage de références. Ces algorithmes maintiennent pour chaque objet un compteur indiquant le nombre de références sur cet objet. Si le compteur d'un objet devient nul, il peut être recyclé ; les algorithmes traversants. Ces algorithmes traversent le graphe des objets accessibles en partant des racines pour distinguer ces objets accessibles (à conserver) des autres objets considérés donc comme inaccessibles (à recycler) ; les algorithmes à générations.

La famille des algorithmes traversants est souvent décomposée en deux sous-familles : les algorithmes marquants et nettoyants ( en anglais) ; les algorithmes copiants ( en anglais), dont l'archétype est l'. En fait, certains algorithmes peuvent combiner diverses méthodes traversantes car elles suivent toutes un modèle abstrait commun.

Comptage de références

Une solution qui vient vite à l'esprit pour la libération automatique de zones de mémoire est d'associer à chacune un compteur donnant le nombre de références qui pointent sur elle. Ces compteurs doivent être mis à jour à chaque fois qu'une référence est créée, altérée ou détruite. Lorsque le compteur associé à une zone mémoire atteint zéro, la zone peut être libérée.

Cependant, cette technique a un inconvénient lors de l'usage de structures cycliques : si une structure A pointe sur une structure B qui pointe sur A (ou, plus généralement, s'il existe un cycle dans le graphe des références), mais qu'aucun pointeur extérieur ne pointe ni sur A ni sur B, les structures A et B ne sont jamais libérées : leurs compteurs de références sont strictement supérieurs à zéro (et comme il est impossible que le programme accède à A ou B, ces compteurs ne peuvent jamais repasser à zéro).

En raison de ces limites, certains considèrent que le comptage de références n'est pas une technique de récupération de mémoire à proprement parler ; ils restreignent le terme de récupération de mémoire à des techniques basées sur l'accessibilité.

En plus de l'impossibilité de gérer les références circulaires, ce système souffre d'autres problèmes sérieux, comme son coût élevé en temps de calcul et aussi en espace mémoire. Pour chaque zone mémoire allouée, il faut en effet maintenir à jour le nombre de références qui y accèdent, ce qui nécessite quelques octets supplémentaires spécifiquement destinés à cet usage. D'un autre côté, il récupère les « miettes » assez rapidement, ce qui présente des avantages s'il y a des destructeurs à exécuter pour libérer les ressources rares (…) autres que le tas (mémoire).

Des systèmes hybrides utilisant le comptage de références pour obtenir la libération quasi immédiate des ressources, et appelant à l'occasion un récupérateur de type pour libérer les objets contenant des cycles de références, ont été proposés et parfois implémentés. Cela donne le meilleur des deux mondes, mais .

Les ramasse-miettes traversants Modélisation des algorithmes traversants Les algorithmes traversants peuvent être modélisés à l'aide de l'abstraction des trois couleurs, publiée par Dijkstra, Lamport en 1978.

L'abstraction des trois couleurs permet de décrire l'avancement d'un cycle de ramassage. Au cours d'un cycle de ramassage, les objets peuvent prendre successivement trois couleurs : les objets blancs sont les objets que le ramasse-miette n'a pas encore vus. Au début d'un cycle, tous les objets sont blancs ; les objets gris sont les objets que le ramasse-miettes a vus, mais pas encore traversés. Pour commencer un cycle, le ramasse-miettes colorie les objets-racines en gris. les objets noirs sont les objets que le ramasse-miettes a traversés.

À chaque itération de la boucle principale d'un algorithme traversant, le ramasse-miettes choisit un objet gris, le colorie en noir et colorie tous ses objets fils blancs en gris. L'algorithme se termine quand il n'y a plus d'objets gris. Les objets sont alors soit blancs soit noirs. Les blancs ne sont pas accessibles à partir des objets racines et peuvent donc être recyclés : l'espace qu'ils occupent est récupéré. A contrario, les objets noirs sont accessibles et sont donc conservés.

Implémentation des algorithmes traversants Les différences entre les algorithmes traversants sont souvent fondées sur la façon dont la coloration des objets est réalisée en pratique dans l'implémentation des ramasse-miettes. Les méthodes les plus courantes sont l'utilisation de bits de coloration placés dans les objets ou dans des cartes de la mémoire, l'utilisation de listes d'objets correspondant à une couleur donnée, ou la détermination de la couleur en fonction de la zone de mémoire où l'objet se trouve, ce qui peut nécessiter de le recopier.

Par exemple on peut réaliser un algorithme marquant et nettoyant classique en utilisant pour chaque objet un bit qui est à 0 pour les objets blancs, et à 1 pour les objets gris ou noirs. Les objets gris sont distingués des noirs en listant leurs adresses, ce qui facilite le choix d'un objet gris au début de chaque itération et la détermination de la fin du cycle de récupération par absence d'objets gris. Mais, au lieu d'une liste, on pourrait aussi utiliser un deuxième bit pour chaque objet.

Au lieu de ce bit (ou ces bits), on peut recopier les objets reconnus comme accessibles (donc gris, puis noirs) dans une zone de mémoire nouvelle, lespace de copie, réservée à cet effet. La distinction entre blanc d'une part et gris ou noir d'autre part se fait alors en regardant dans quelle zone l'objet est rangé. On réalise ainsi un algorithme copiant. La distinction entre gris et noir peut être faite par une liste d'adresses, par un bit de coloration, ou en bi-partitionnant l'espace de copie. Dans ce dernier cas, le plus simple consiste à utiliser un unique pointeur qui indique l'adresse de la frontière entre les objets noirs et les gris, frontière que l'on déplace à mesure que les objets gris sont traités.

Avantages et inconvénients