Ramasse-miettes (informatique)

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[4]. 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.

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 (mark and sweep collector en anglais) ;
• les algorithmes copiants (copy collector en anglais), dont l'archétype est l'algorithme de Cheney (en).

En fait, certains algorithmes peuvent combiner diverses méthodes traversantes car elles suivent toutes un modèle abstrait commun.

Les algorithmes traversants peuvent être modélisés à l'aide de l'abstraction des trois couleurs, publiée par Dijkstra, Lamport et al. 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.

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, l'espace 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.

Un avantage des ramasse-miettes copieurs est que la libération de l'espace des objets blancs (morts) se fait d'un coup en récupérant la zone ancienne : le coût d'un cycle du ramasse-miettes est donc proportionnel au nombre 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. En outre, tous les objets vivants sont rassemblés, et l'espace pour les nouveaux objets peut être alloué facilement à partir d'un unique bloc, quelle que soit la taille de l'objet désiré. Par contre, le déplacement des objets lors de la copie impose la mise à jour des pointeurs vers ces objets, ce qui a un coût et peut être complexe dans le cas des variantes incrémentielles ou concurrentes, car l'application doit pouvoir trouver les objets et suivre les pointeurs en dépit du fait que le ramasse-miettes les déplace. Par ailleurs, l'algorithme impose à l'application de n'utiliser en principe qu'une moitié de la mémoire, l'autre moitié étant réservée à la copie du prochain cycle de ramassage et à l'allocation de mémoire entre ce cycle et le suivant : la moitié de mémoire utilisée par l'application change à chaque cycle de ramassage.

Les ramasse-miettes marquants et nettoyants ne posent pas de problème de localisation des objets dû à leur déplacement. En outre, ils permettent d'utiliser la mémoire entière, au lieu de se limiter à une moitié. Cependant, la récupération impose une phase de balayage de toute la mémoire pour récupérer l'espace des objets inaccessibles (et donc toujours blancs). Le coût de cette phase est proportionnel à la taille de la zone mémoire utilisée, passant sur tous les objets accessibles ou non. Cela peut être très coûteux par rapport à la phase de marquage si la plupart des objets sont devenus inaccessibles. Par ailleurs, la mémoire disponible n'est pas récupérée en un seul morceau, mais sous forme d'une collection de fragments de tailles variables. La gestion de ces fragments et leur usage optimal en fonction de leur taille pour allouer de l'espace à de nouveaux objets peut être complexe, surtout si l'application utilise des objets de taille variable. C'est pourquoi certaines implémentations prévoient également une phase de compactage de la mémoire à la fin de chaque cycle de ramassage ou combinent ce compactage avec la phase de balayage. Cependant le compactage requiert un déplacement des objets, avec les mêmes problèmes que pour les algorithmes copieurs.

Les algorithmes de base peuvent être implémentés selon diverses 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émentiels 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. Les problèmes diffèrent selon que ces processeurs partagent ou non leur espace mémoire.
• Les ramasse-miettes peuvent également opérer sur un mode réparti, sur des réseaux locaux ou non.

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

• Herbert Schorr, William M. Waite, An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures. CACM, août 1967 DOI 10.1145/363534.363554
• Edsger Dijkstra, Leslie Lamport, A. J. Martin, Carel S. Scholten, Elisabeth F. M. Steffens, On-the-Fly Garbage Collection: An Exercise in Cooperation. CACM, V.21, N. 11, pp. 966-975, novembre 1978. DOI 10.1145/359642.359655
• 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
• (en) Antony L. Hosking et Jiawan Chen, « Mostly-copying reachability-based orthogonal persistence », OOPSLA '99 Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, vol. 34, n^o 10,‎ octobre 1999, p. 384-385 (ISBN 1-58113-238-7, DOI 10.1145/320385.320427)

• (en) Hezi Azatchi, Yossi Levanoni, Harel Paz et Erez Petrank, « An on-the-fly mark and sweep garbage collector based on sliding views », OOPSLA '03 Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, vol. 38, n^o 11,‎ novembre 2003, p. 270 (ISBN 1-58113-712-5, DOI 10.1145/949343.949329)

• (en) David F. Bacon, Perry Cheng et V. T. Rajan, « A unified theory of garbage collection », OOPSLA '04 Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, vol. 39, n^o 10,‎ octobre 2004, p. 51 (ISBN 1-58113-831-8, DOI 10.1145/1028976.1028982)

• (en) Stephen M. Blackburn et Kathryn S. McKinley, « A Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance », PLDI '08 Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, vol. 43, n^o 6,‎ juin 2008, p. 24 (ISBN 978-1-59593-860-2, DOI 10.1145/1375581.1375586)

• (en) Rifat Shahriyar, Stephen M. Blackburn et Kathryn S. McKinley, « Fast conservative garbage collection », OOPSLA '14 Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, vol. 49, n^o 10,‎ octobre 2014, p. 121-136 (ISBN 978-1-4503-2585-1, DOI 10.1145/2660193.2660198)

• (en) Rick Byers, « Garbage Collection Algorithms », Project for CSEP 521, Winter,‎ 2007, p. 3-4