Ramasse-miettes

Un ramasse-miettes, ou récupérateur de mémoire, ou glaneur de cellules (en anglais garbage collector, abrégé en GC) est un sous-système informatique de gestion automatique de la mémoire. Il est responsable du recyclage de la mémoire préalablement allouée puis inutilisée.

Lorsqu'un système dispose d'un ramasse-miettes, ce dernier fait le plus souvent partie de l'environnement d'exécution associé à un langage de programmation spécifique. Le ramassage des miettes a été inventé par John McCarthy comme faisant partie du premier système Lisp.

Définition et fonctionnement

Le principe de base de la récupération automatique de la mémoire est simple :

• déterminer quels objets dans le programme ne peuvent pas être utilisés,
• récupérer le stockage utilisé par ces objets.

Bien qu'en général il soit impossible de déterminer à l'avance à quel moment un objet ne sera plus utilisé, il est possible de le découvrir à l'exécution : un objet sur lequel le programme ne maintient plus de référence, par conséquent devenu inaccessible, ne sera plus utilisé.

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 différent d'objets qui sont supposés atteignables, 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 atteignable est lui-même atteignable.

Dit autrement : un objet atteignable peut être obtenu en suivant une chaîne de pointeurs ou de références.

Bien évidemment, un tel algorithme est une approximation conservatrice de l'objectif parfait de destruction des valeurs ne servant plus : certaines valeurs peuvent fort bien être accessibles depuis les racines mais ne plus jamais être utilisées. Cet objectif parfait est cependant inaccessible algorithmiquement : déterminer quelles valeurs serviront dans le futur est équivalent au problème de l'arrêt.

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. Par exemple, un programme peut conserver un pointeur sur une structure de donnée qui ne sera jamais réutilisée. Il est pour cette raison recommandé d'écraser les pointeurs vers des structures inutilisées, afin d'éviter de conserver des références inutiles.

Algorithme de base

L'algorithme du ramasse-miettes est dû à Schorr et Waite. Les ramasse-miettes effectuent des cycles de ramassage. Un cycle est démarré quand le récupérateur décide (ou est notifié) qu'il doit récupérer de l'espace de stockage. Un cycle est formé des étapes suivantes :

• Créer des ensembles dit noir, gris et blanc. Originellement, la totalité noir est vide, la totalité gris contient les objets «racines» et peut-être certains objets supplémentaires choisis en fonction de l'algorithme spécifique employé, et la totalité blanc contient tout le reste. À tout moment dans l'exécution de l'algorithme, un objet ne peut être que dans un seul des trois ensembles. L'ensemble blanc peut être vu comme la totalité des objets dont nous essayons de récupérer l'espace mémoire ; au cours du cycle, l'algorithme ôtera des objets de la totalité blanc, y laissant les objets dont il peut réclamer l'espace mémoire.
• Choisir un objet de la totalité gris, déplacer cet objet vers la totalité noir, déplacer tous les objets blancs référencés directement par cet objet vers la totalité gris. Cette étape est répétée jusqu'à ce qu'il n'y ait plus d'objets dans la totalité gris.
• Lorsque il n'y a plus d'objets dans la totalité gris, dans ce cas tous les objets restant dans la totalité blanc ne sont pas atteignables, et l'espace mémoire qu'ils utilisent peut être réclamé.

L'invariant des trois couleurs peut être traduit comme ceci : aucun objet noir ne pointe directement sur un objet blanc.

Observons que l'algorithme ci-dessus préserve l'invariant des trois couleurs. La partition initiale n'a pas d'objet noir, de sorte que l'invariant est trivialement respecté. Par la suite, si un objet devient noir, tous ses fils directs (les objets qu'il référence) deviennent gris, ceci préservant l'invariant. Quand la dernière étape de l'algorithme est réalisée, parce que l'invariant est préservé, aucun des objets de la totalité noir ne pointe vers un objet de la totalité blanc (et il n'y a plus d'objet gris) ce qui veut dire que les objets blancs résiduels sont inatteignables depuis les racines. Le système peut dans ce cas appeler leurs destructeurs et libérer leur espace mémoire.

Certaines variantes de l'algorithme ne respectent pas l'invariant des trois couleurs, mais ils utilisent un principe différent par lequel toutes les propriétés importantes sont respectées.

Variantes

L'algorithme de base a plusieurs variantes.

• Les ramasse-miettes qui déplacent les objets en mémoire (qui changent leur adresse), dits stop and copy.

• Certains récupérateurs peuvent correctement identifier toutes les références à un objet : ils sont appelés des récupérateurs «exacts», par opposition avec des récupérateurs «conservateurs» ou «partiellement conservateurs». Les ramasse-miettes «conservateurs» doivent présumer que n'importe quelle suite de bits en mémoire est un pointeur si (lorsqu'ils sont interprétées comme un pointeur) il pointe sur un quelconque objet instancié. Ainsi, les récupérateurs conservateurs peuvent avoir des faux négatifs, où l'espace mémoire n'est pas réclamé à cause des faux pointeurs accidentels. En pratique ceci est rarement un gros inconvénient.

• Le ramasse-miettes peut s'exécuter en alternance ou en parallèle avec le reste du système ; les récupérateurs les plus simples suspendent l'exécution du système lorsqu'ils exécutent un cycle ; ils ne sont pas incrémentaux ; les récupérateurs incrémentaux entrelacent leur travail pour s'exécuter pendant les temps d'inactivité du reste du système. Certains récupérateurs incrémentaux peuvent s'exécuter totalement en parallèle dans un thread séparé ; ils peuvent en théorie s'exécuter sur un processeur différent, mais le coût de la mise en cohérence des caches rend cette approche moins pratique qu'il n'y paraît.

Classification des ramasse-miettes

Les récupérateurs peuvent être classés en considérant la façon dont ils implémentent les trois ensembles d'objets blancs, gris et noirs.

Marquage et nettoyage

Ou mark and sweep en anglais. Un ramasse-miettes de ce type maintient un bit (ou deux) associé à chaque objet pour indiquer s'il est blanc ou noir ; la totalité gris est maintenu soit comme une liste séparée ou en utilisant un autre bit. Un récupérateur copieur distingue les objets gris et noirs en les copiant vers d'autres zones mémoire (l'espace de copie) et fréquemment différencie les objets noirs des objets gris en bi-partitionnant l'espace de copie (dans le cas le plus simple en désormais un unique pointeur qui indique la séparation entre les objets noirs et gris). Un avantage des ramasse-miettes copieurs est que la libération des objets blancs (morts) se fait en vrac, en libérant en une seule fois la zone ancienne, et que le coût du ramasse-miettes est proportionnel aux nombres d'objets vivants. Ceci est particulièrement utile lorsque il y a énormément d'objets alloués, dont la majorité sont temporaires et meurent rapidement.

Conservatif vs Précis

Ou conservative vs precise en anglais. Un ramasse-miettes est conservatif lorsqu'il ne libère pas certaines zones de mémoire devenues inutiles. Par exemple, le ramasse-miettes de Bœhm considère tout mot mémoire comme un pointeur potentiel à suivre, y compris sur la pile d'appel, et s'utilise aisément en C. Au contraire, les ramasse-miettes précis distinguent partout les pointeurs des autres données (y compris sur la pile d'appel) et nécessitent pour ce faire la coopération du compilateur (qui va génèrer les descripteurs de cadre d'appels) ou du programmeur. Généralement, les ramasse-miettes conservatifs sont marqueurs et ne modifient pas l'adresse des zones utilisées.

Récupérateur à générations

Ou generational GC en anglais. Toutes les données d'un programme n'ont pas la même durée de vie. Certaines sont éliminables très peu de temps après leur création (par exemple, une structure de donnée créée seulement pour retourner une valeur d'une fonction, et démantelée dès que les données en ont été extraites). D'autres persistent pendant toute la durée d'exécution du programme (par exemple, des tables globales créées pendant l'initialisation). Un ramasse-miettes traitant toutes ces données de la même façon n'est pas nécessairement des plus efficaces.

Une solution serait de demander au programmeur d'étiqueter les données créées selon leur durée de vie probable. Cependant, cette solution serait lourde à utiliser ; par exemple, il est courant que les données soient créées dans des fonctions de bibliothèque (par exemple, une fonction créant une table de hachage), il faudrait leur apporter les durées de vie en paramètre.

Une méthode moins invasive est le système des générations. Le ramasse-miettes opère dans ce cas sur une hiérarchie de 2 ou plus générations, étagées de la plus «jeune» à la plus «âgée». Les données nouvellement créées sont (en général) positionnées dans la génération la plus jeune. On ramasse assez souvent les miettes dans cette génération jeune ; les données encore présentes à l'issue de la destruction des données inaccessibles de cette génération sont positionnées dans la génération d'âge supérieur, et ainsi de suite. L'idée est que les données de plus courte durée de vie n'atteignent, pour la majorité, pas la génération supérieure (elle peuvent l'atteindre si elles viennent d'être allouées lorsque le ramassage de miettes les repère dans la génération jeune, mais c'est un cas rare).

On utilise le plus souvent 2 ou 3 générations, de tailles croissantes. Généralement, on n'utilise pas le même algorithme de ramasse-miettes pour les diverses générations. Il est ainsi courant d'utiliser un algorithme non incrémental pour la génération la plus jeune : à cause de sa faible taille, le temps de ramasse-miettes est faible et l'interruption momentanée de l'exécution de l'application n'est pas gênante, même pour une application interactive. Les générations plus anciennes sont plutôt ramassées avec des algorithmes incrémentaux.

Le réglage des paramètres d'un ramasse-miettes à génération peut être délicat. Ainsi, la taille de la génération la plus jeune peut influencer de façon importante le temps de calcul (un surcoût de 25%, par exemple, pour une valeur mal choisie)  : temps de ramasse-miettes, impact sur la localité du cache... Par ailleurs, le meilleur choix dépend de l'application, du type de processeur et d'architecture mémoire.

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, alterée ou détruite. Quand le compteur associé à une zone mémoire atteint zéro, la zone peut être libérée.

Cette technique souffre d'un inconvénient certain lors de l'usage de structures cycliques : si une structure A pointe sur une structure B qui pointe sur A (ou, d'une façon plus générale, 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é.

Le comptage de références souffre de certains problèmes sérieux, comme son coût élevé en temps de calcul et aussi en espace mémoire et, comme on l'a vu, l'impossibilité de gérer les références circulaires. D'un autre côté, il récupère les «miettes» plutôt vite, ce qui présente des avantages s'il y a des destructeurs à exécuter pour libérer les ressources rares (sockets... ) 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 Mark and Sweep pour libérer les objets contenant des cycles de références, ont été proposés et quelquefois implémentés. Cela donne le meilleur des deux mondes, mais systématiquement au prix d'un coût élevé en termes de performances.

Langages pourvus de ramasse-miettes

• Common Lisp, Scheme, Smalltalk, Caml, Haskell, Prolog, Oz, Io
• interpréteurs de commandes et langages de scripts comme Bash, Csh, Korn shell, etc.
• Java, Objective-C (système de comptage de références), C#, Eiffel, D, C++/CLI
• Perl,, Ruby, ActionScript
• Python utilise un mécanisme de comptage de références doublé depuis la version 2.2 d'un ramasse-miettes Mark and Sweep pour la destruction des cycles.

Avantages et inconvénients des ramasse-miettes

Les langages utilisant un ramasse-miettes permettent d'écrire des programmes plus simples et plus sûrs. La mémoire étant gérée automatiquement par l'environnement d'exécution, le programmeur est libéré de cette tâche, source de nombreuses erreurs difficiles à débusquer. La gestion manuelle de la mémoire est l'une des sources les plus courantes d'erreur.

Trois types principaux d'erreurs peuvent se produire :

• l'accès à une zone non allouée, ou qui a été libérée,
• la libération d'une zone déjà libérée,
• la non-libération de la mémoire inutilisée (fuites mémoire).

L'utilisation d'outils et de méthodologie appropriés permet d'en diminuer l'impact, alors que l'utilisation d'un ramasse-miettes permet de les éliminer quasi totalement – les fuites de mémoire restent possibles, bien que plus rares. Cette simplification du travail de programmation peut présenter quelques inconvénients, essentiellement au niveau des performances des programmes les utilisant.

Des mesures montrent que dans certains cas l'implémentation d'un ramasse-miettes augmente les performances d'un programme, dans d'autre cas le contraire se produit. Le choix des paramètres du ramasse-miettes peut aussi altérer ou perfectionner significativement les performances d'un programme. Quand le ramasse-miettes effectue de nombreuses opérations de copies en tâche de fond (cas de l'algorithme stop-and-copy), il tend à défragmenter la mémoire. Le ramasse-miettes peut ainsi se révéler plus rapide qu'un codage ad-hoc de l'allocation/désallocation. Les meilleures implémentations peuvent aussi optimiser l'utilisation des caches mémoires, accélérant ainsi l'accès aux données. A contrario, l'opération de collection est fréquemment coûteuse.

Il est difficile de limiter le temps d'exécution de la phase de collection des objets non atteignables. L'utilisation d'un ramasse-miettes standard peut par conséquent rendre difficile l'écriture de programmes temps réel ; un ramasse-miettes spécialisé (temps-réel) doit être utilisé pour cela.

Sans intervention du programmeur, un programme utilisant un ramasse-miettes a tendance à utiliser plus de mémoire qu'un programme où la gestion est manuelle (en admettant que, dans ce cas, il n'y a pas de fuites, d'erreur d'accès ou de libération). Toutefois, rien n'interdit d'employer des stratégies de pré-allocation des objets utilisés, dans des pools, lorsqu'on veut minimiser le taux d'allocation/désallocation. Dans ce cas, le ramasse-miettes apporte toujours le bénéfice d'une programmation sans erreur grave de gestion de la mémoire (une assurance).

Bien que ce ne soit pas l'objectif d'un ramasse-miettes son implémentation peut aussi favoriser l'implémentation de la Persistance d'objet (certains algorithmes sont partagés).

Citations

«Il est dit que les programmeurs Lisp savent que la gestion de la mémoire est si importante qu'elle ne peut être laissée aux programmeurs, et que les programmeurs C savent que la gestion de la mémoire est si importante qu'elle ne peut être laissée au système» -- Bjarne Stroustrup peut-être tiré d'une source antérieure.

Voir aussi

Liens externes

• (en) Ramasses-miettes de Bœhm-Demers-Weiser
• (fr) Ramasses-miettes de. NET et Java
• (fr) Récupération automatique de la mémoire
• (en) memorymanagement. org
• (en) Publications du groupe OOPS de l'Université du Texas
• (en) Resources sur les ramasses-miettes
• (fr) Ramasses-miettes de Java jdk6 / jdk7
• (fr) Présentation du Garbage Collector de Java

Références

H. Schorr, W. M. Waite, An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures. CACM Août 1967

R. E. Jones and R. Lins. Garbage Collection : Algorithms for Automatic Dynamic Memory Management. Wiley, Chichester, July 1996.

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Ramasse-miettes.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 17/11/2008.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.