Ramasse-miettes (informatique) - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (L'informatique de gestion est le domaine de l'informatique se concentrant sur la programmation de logiciels tournés vers la gestion : comptabilité, finances, ressources...) automatique (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la modélisation, de l'analyse, de la commande et, de la régulation des systèmes dynamiques. Elle...) de la mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.). Il est responsable du recyclage (Le recyclage est un procédé de traitement des déchets industriels et des déchets ménagers qui permet de réintroduire, dans le cycle de production d'un produit, des matériaux qui le...) 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 (L'environnement est tout ce qui nous entoure. C'est l'ensemble des éléments naturels et artificiels au sein duquel se déroule la vie humaine. Avec les enjeux écologiques actuels, le terme environnement tend actuellement à prendre une...) d'exécution associé à un langage de programmation (Un langage de programmation est un langage informatique, permettant à un être humain d'écrire un code source qui sera analysé par une machine, généralement un...) particulier. Le ramassage des miettes a été inventé par John McCarthy (John McCarthy (né le 4 septembre 1927, à Boston, Massachusetts) est le principal pionnier de l'intelligence artificielle avec Marvin Minsky ; il incarne le courant...) 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 (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction précise, et qui peut être désigné par une étiquette verbale. Il est...) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout »,...) 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 (Une instruction est une forme d'information communiquée qui est à la fois une commande et une explication pour décrire l'action, le comportement, la méthode...), les variables globales. En d'autres termes tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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 (Le mot chaîne peut avoir plusieurs significations :) de pointeurs ou de références.

Bien évidemment, un tel algorithme est une approximation (Une approximation est une représentation grossière c'est-à-dire manquant de précision et d'exactitude, de quelque chose, mais encore assez...) conservatrice de l'objectif idéal (En mathématiques, un idéal est une structure algébrique définie dans un anneau. Les idéaux généralisent de façon...) 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 (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 (Le mot graphe possède plusieurs significations. Il est notamment employé :) 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 (Le mot implantation peut avoir plusieurs significations :)

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.

Page générée en 0.089 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique