Ramasse-miettes Article, Signification, Explication
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-miette, 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.
Les principes sont :
Bien évidemment, un tel algorithme est une approximation conservatrice de l'objectif idéal 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 idéal 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.
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.
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-miette opère alors 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) 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 (elle 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-miette 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-miette 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-miette, 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.
Cette technique souffre d'un inconvénient certain lors de l'usage de structures mutuellement récursives : 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èdent à 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, ls difficulté à 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 autres (sockets...) 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.
Trois types principaux d'erreur peuvent se produire :
Des mesures montrent que dans certain 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-miette peut aussi altérer ou améliorer significativement les performances d'un programme. Lorsque le ramasse-miette 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. À 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.
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).
C'est un article concernant le Ramasse-miettes. La page contient la signification du Ramasse-miettes , Description et explication au sujet de Ramasse-miettes Principe
Le principe de base de la récupération automatique de la mémoire est simple :
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 ne sera plus utilisé.Atteignabilité d'un objet
Les ramasse-miettes utilisent un critère d'atteignabilité pour déterminer si un objet peut-être potentiellement utilisé.
Dit autrement : un objet atteignable peut être obtenu en suivant une chaîne de pointeurs ou de références.Algorithme de base
L'algorithme du ramasse-miettes est du à Schorr et Waite. Les ramasse-miettes effectuent des cycles de ramassage. Un cycle est démarré lorsque le récupérateur décide (ou est notifié) qu'il doit récupérer de l'espace de stockage. Un cycle est constitué des étapes suivantes :
L'invariant des trois couleurs peut ĂŞtre traduit comme ceci :
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. Lorsque la dernière étape de l'algorithme est réalisée, parce que l'invariant est préservé, aucun des objets de l'ensemble noir ne pointe vers un objet de l'ensemble blanc (et il n'y a plus d'objet gris) ce qui signifie que les objets blancs résiduels sont inatteignables depuis les racines. Le système peut alors appeler leurs destructeurs et libérer leur espace mémoire.Algorithme
L'algorithme de base a plusieurs variantes.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 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 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).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-miette traitant toutes ces données de la même façon n'est pas forcément des plus efficaces.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 dovent être mis à jour à chaque fois qu'une référence est créée, alterée ou détruite. Lorsque le compteur associé à une zone mémoire atteint zéro, la zone peut être libérée. Cette technique est notamment utilisée dans le langage Perl.Langages utilisant la récupération automatique de mémoire
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.
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. 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
Références
H. Schorr, W.M. Waite, An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures. CACM Août 1967