Ramasse-miettes (informatique) - Définition

Introduction

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 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 idéal de libération des valeurs ne servant plus : certaines valeurs peuvent fort bien être accessibles depuis les racines mais ne plus jamais être utilisées. Cet objectif minimaliste est cependant inaccessible algorithmiquement : déterminer quelles valeurs serviront dans le futur est équivalent au problème de l'arrêt. D'autre part, le comportement du programme dépend des données en entrée, par définition non définies à 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 tout au long de l'exécution du programme. 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'effacer les pointeurs vers des structures inutilisées, afin d'éviter de conserver des références inutiles.

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