Ramasse-miettes (informatique)

Illustration d'un ramasse-miette compactant

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 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.

Définition et fonctionnement

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

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

Il n'est pas toujours possible de déterminer à l'avance à 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. Cependant, il est possible de découvrir à 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, à savoir que le fait qu'il existe une référence vers un objet ne signifie pas obligatoirement qu'il sera 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 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.

Bien évidemment, 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 passage à un endroit donné - et des ressources mémoires associées, à cause de boucles, sauts, etc.), non soluble dans les cas d'une mémoire infinie. 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 (= rendre au pool) 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 deux familles d'algorithmes :

• Les algorithmes à comptage de références. Ces algorithmes maintiennent pour chaque objet un compteur indiquant le nombre de référence 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 en partant des racines pour distinguer les objets accessibles (à conserver) des objects inaccessibles (à recycler).

La famille des algorithmes traversants peut être décomposée en deux sous-familles :

• Les algorithmes marquants et nettoyants. (à compléter)
• Les algorithmes copiants, dont l'archétype est l'algorithme de Cheney (à compléter).

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 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-miette a "vus", mais pas encore traversés. Pour initier un cycle, le ramasse-miette colorie les objets-racines en gris.
• Les objets noirs sont les objets que le ramasse-miette a traversés.

A chaque itération de la boucle principale d'un algorithme traversant, le ramasse-miette choisit un objet gris, le colorie en noir et colorie tous ses 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. A contrario, les objets noirs sont accessibles et sont conservés.

Variantes d'implémentation

Les algorithmes de bases peuvent être implémentés selon trois variantes.

• Les ramasse-miettes bloquants (en anglais stop-the-world) arrêtent l'application (ou le système) pour la durée d'un cycle de collection entier.
• Les ramasse-miettes incrémentaux permettent d'exécuter des pas d'un cycle en alternance avec l'exécution de l'application
• Les algorithmes dits concurrents s'exécutent parallèlement à l'application. Les algorithmes de ce type ne peuvent s'exécuter que sur des machines avec plusieurs processeurs.

Avantage/Inconvénient. A faire. Mot clés: temps-réel, mécanisme de synchronisation, invariant de trois-couleurs, violation de l'invariant, barrière en écriture, barrière en lecture. Algorithme de baker

Ramasse-miettes exacts et conservateurs

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.

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 ; l'ensemble gris est maintenu soit comme une liste séparée soit 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 souvent différencie les objets noirs des objets gris en bi-partitionnant l'espace de copie (dans le cas le plus simple en maintenant 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 quand il y a beaucoup d'objets alloués, dont la plupart sont temporaires et meurent rapidement.

Conservatif contre 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 Boehm considère tout mot mémoire comme un pointeur potentiel à suivre, y compris sur la pile d'appel, et s'utilise facilement 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 uniquement 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 forcément 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 fournir 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 alors sur une hiérarchie de plusieurs générations, étagées de la plus « jeune » à la plus « âgée ». Les données nouvellement créées sont (en général) placées dans la génération la plus jeune. On ramasse assez fréquemment 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 placé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 plupart, pas la génération supérieure (elles peuvent l'atteindre si elles viennent d'être allouées quand le ramassage de miettes les repère dans la génération jeune, mais c'est un cas rare).

On utilise généralement 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 : en raison 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, altérée ou détruite. Lorsque le compteur associé à une zone mémoire atteint zéro, la zone peut être libérée. Cette méthode est très efficace dans la plupart des cas.

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é.

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^{[réf. nécessaire]} 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 parfois implémentés. Cela donne le meilleur des deux mondes, mais toujours au prix d'un coût élevé en termes de performances^{[réf. nécessaire]}.

Langages dotés 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, Lisaac, Objective-C, C#, Eiffel, D, C++/CLI
• Perl, Javascript, Ruby, ActionScript, PHP
• 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 réduire l'impact, tandis que l'utilisation d'un ramasse-miettes permet de les éliminer presque complètement – les fuites de mémoire restent possibles, bien que plus rares. Cette simplification du travail de programmation peut présenter quelques inconvénients, principalement 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, alors que dans d'autres cas le contraire se produit. Le choix des paramètres du ramasse-miettes peut aussi altérer ou améliorer significativement les performances d'un programme. Lorsque 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 souvent coûteuse.

Il est difficile de borner le temps d'exécution de la phase de collection des objets non atteignables. L'utilisation d'un ramasse-miettes standard peut donc rendre difficile l'écriture de programmes temps réel ; un ramasse-miettes spécialisé (temps-réel) doit être utilisé pour cela, comme dans JamaicaVM, une implémentation de Machine Virtuelle Java Temps-Réel.

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 fournit 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 le but d'un ramasse-miettes son implémentation peut aussi faciliter l'implémentation de la Persistance d'objet (certains algorithmes sont partagés).

Voir aussi

Liens externes

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

Notes et références

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, juillet 1996. (ISBN 0-471-94148-4)

• Fridtjof Siebert, Realtime Garbage Collection in the JamaicaVM 3.0. JTRES 2007, 26-28 September 2007, Vienna, Austria