Collecte des ordures ménagères (informatique) - Garbage collection (computer science)

Le ramasse-miettes stop-and-copy dans une architecture Lisp : la mémoire est divisée en mémoire de travail et mémoire libre ; de nouveaux objets sont alloués dans l'ancien. Lorsqu'il est plein (représenté), le ramasse-miettes est effectué : toutes les structures de données encore utilisées sont localisées par traçage de pointeur et copiées dans des emplacements consécutifs dans la mémoire libre.
Après cela, le contenu de la mémoire de travail est rejeté au profit de la copie compressée, et le rôle de mémoire de travail et libre est échangé (représenté).

En informatique , le ramasse - miettes ( GC ) est une forme de gestion automatique de la mémoire . Le ramasse-miettes tente de récupérer la mémoire qui a été allouée par le programme, mais qui n'est plus référencée, également appelée ordures . La collecte des ordures a été inventée par l'informaticien américain John McCarthy vers 1959 pour simplifier la gestion manuelle de la mémoire dans Lisp .

La récupération de place dispense le programmeur d'effectuer une gestion manuelle de la mémoire où le programmeur spécifie quels objets désallouer et retourner au système de mémoire et quand le faire. D'autres techniques similaires incluent l' allocation de pile , l' inférence de région , la propriété de la mémoire et des combinaisons de plusieurs techniques. Le ramassage des ordures peut prendre une part importante du temps de traitement total d'un programme et, par conséquent, peut avoir une influence considérable sur les performances .

Ressources autres que la mémoire, telles que les sockets réseau , base de données poignées , fenêtres d'interaction utilisateur , fichier et descripteurs de périphériques, ne sont généralement pas prises en charge par la collecte des ordures. Les méthodes de gestion de ces ressources, en particulier les destructeurs , peuvent également suffire à gérer la mémoire, ne laissant aucun besoin de GC. Certains systèmes GC permettent à ces autres ressources d'être associées à une région de mémoire qui, lorsqu'elle est collectée, provoque le travail de récupération de ces ressources.

Des principes

Les principes de base du ramasse-miettes consistent à trouver des objets de données dans un programme auquel il sera impossible d'accéder à l'avenir et à récupérer les ressources utilisées par ces objets.

De nombreux langages de programmation nécessitent un ramasse-miettes, soit dans le cadre de la spécification du langage (par exemple, Java , C# , D , Go et la plupart des langages de script ) soit efficacement pour une implémentation pratique (par exemple, des langages formels comme le lambda calcul ); on dit que ce sont des langues ramassées . D'autres langages ont été conçus pour être utilisés avec la gestion manuelle de la mémoire, mais disposent d'implémentations de récupération de place (par exemple, C et C++ ). Certains langages, comme Ada , Modula-3 et C++/CLI , permettent à la fois la récupération de place et la gestion manuelle de la mémoire dans la même application en utilisant des tas séparés pour les objets collectés et gérés manuellement ; d'autres, comme D , font l'objet d'une récupération de place mais permettent à l'utilisateur de supprimer manuellement des objets et de désactiver entièrement la récupération de place lorsque la vitesse est requise.

Alors que l'intégration du ramasse-miettes dans le compilateur et le système d'exécution du langage permet un choix beaucoup plus large de méthodes, des systèmes GC post-hoc existent, tels que le comptage automatique de références (ARC), dont certains ne nécessitent pas de recompilation. ( Le GC post-hoc est parfois distingué comme une collecte de déchets .) Le ramasse-miettes sera presque toujours étroitement intégré à l' allocateur de mémoire .

Avantages

Le ramassage des ordures libère le programmeur de la désallocation manuelle de la mémoire. Cela élimine ou réduit certaines catégories d' erreurs :

  • Les pointeurs pendants , qui se produisent lorsqu'un morceau de mémoire est libéré alors qu'il y a encore des pointeurs vers celui-ci, et que l'un de ces pointeurs est déréférencé . D'ici là, la mémoire peut avoir été réaffectée à un autre usage, avec des résultats imprévisibles.
  • Double bogues libres , qui se produisent lorsque le programme essaie de libérer une région de mémoire qui a déjà été libérée, et peut-être déjà été allouée à nouveau.
  • Certains types de fuites de mémoire , dans lesquelles un programme ne parvient pas à libérer la mémoire occupée par des objets devenus inaccessibles , ce qui peut entraîner un épuisement de la mémoire.

Désavantages

La récupération de place consomme des ressources informatiques pour décider de la mémoire à libérer, même si le programmeur connaît peut-être déjà cette information. La pénalité pour la commodité de ne pas annoter manuellement la durée de vie de l'objet dans le code source est la surcharge , ce qui peut entraîner une diminution ou des performances inégales. Un article évalué par des pairs de 2005 est arrivé à la conclusion que GC a besoin de cinq fois plus de mémoire pour compenser cette surcharge et pour fonctionner aussi vite que le même programme en utilisant une gestion de mémoire explicite idéalisée, en insérant des annotations à l'aide d'un oracle implémenté en collectant des traces à partir de programmes exécuter sous un profileur. Cependant, des programmeurs tels que Jon Harrop affirment qu'une telle ligne de base est irréaliste, car les programmeurs écrivent rarement un code de gestion de mémoire explicite optimal. L'interaction avec les effets de la hiérarchie de la mémoire peut rendre cette surcharge intolérable dans des circonstances difficiles à prévoir ou à détecter dans les tests de routine. L'impact sur les performances a également été invoqué par Apple comme raison de ne pas adopter le ramasse-miettes dans iOS alors qu'il s'agit de la fonctionnalité la plus souhaitée.

Le moment où les ordures sont réellement collectées peut être imprévisible, ce qui entraîne des blocages (pauses pour déplacer/libérer de la mémoire) dispersés tout au long d'une session. Les blocages imprévisibles peuvent être inacceptables dans les environnements en temps réel , dans le traitement des transactions ou dans les programmes interactifs. Les ramasse-miettes incrémentiels, simultanés et en temps réel résolvent ces problèmes, avec des compromis variés.

Stratégies

Tracé

Le traçage du ramasse-miettes est le type de ramasse-miettes le plus courant, à tel point que le « ramasse-miettes » fait souvent référence au traçage du ramasse-miettes, plutôt qu'à d'autres méthodes telles que le comptage de références . La stratégie globale consiste à déterminer quels objets doivent être ramassés en retraçant quels objets sont accessibles par une chaîne de références à partir de certains objets racine, et en considérant le reste comme des ordures et en les collectant. Cependant, il existe un grand nombre d'algorithmes utilisés dans la mise en œuvre, avec des caractéristiques de complexité et de performance très variables.

Comptage de références

Le garbage collection de comptage de références est l'endroit où chaque objet a un compte du nombre de références à lui. Les ordures sont identifiées en ayant un compte de référence de zéro. Le nombre de références d'un objet est incrémenté lorsqu'une référence à celui-ci est créée et décrémenté lorsqu'une référence est détruite. Lorsque le compte atteint zéro, la mémoire de l'objet est récupérée.

Comme avec la gestion manuelle de la mémoire, et contrairement au traçage du ramasse-miettes, le comptage de références garantit que les objets sont détruits dès que leur dernière référence est détruite, et n'accède généralement qu'à la mémoire qui se trouve soit dans les caches CPU , dans les objets à libérer, soit directement pointés vers par ceux-ci, et a donc tendance à ne pas avoir d'effets secondaires négatifs importants sur le cache du processeur et le fonctionnement de la mémoire virtuelle .

Le comptage de références présente un certain nombre d'inconvénients ; cela peut généralement être résolu ou atténué par des algorithmes plus sophistiqués :

Cycles
Si deux objets ou plus se réfèrent l'un à l'autre, ils peuvent créer un cycle dans lequel aucun ne sera collecté car leurs références mutuelles ne laissent jamais leurs comptes de références devenir nuls. Certains systèmes de récupération de place utilisant le comptage de références (comme celui de CPython ) utilisent des algorithmes de détection de cycle spécifiques pour traiter ce problème. Une autre stratégie consiste à utiliser des références faibles pour les "backpointers" qui créent des cycles. Sous le comptage de références, une référence faible est similaire à une référence faible sous un ramasse-miettes de traçage. Il s'agit d'un objet de référence spécial dont l'existence n'incrémente pas le nombre de références de l'objet de référence. De plus, une référence faible est sûre dans la mesure où lorsque l'objet référent devient inutile, toute référence faible à celui-ci devient caduque , plutôt que d'être autorisée à rester suspendue, ce qui signifie qu'elle se transforme en une valeur prévisible, telle qu'une référence nulle.
Surcharge d'espace (nombre de références)
Le comptage de références nécessite que de l'espace soit alloué à chaque objet pour stocker son comptage de références. Le compte peut être stocké à côté de la mémoire de l'objet ou dans une table d'appoint ailleurs, mais dans les deux cas, chaque objet compté par référence nécessite un stockage supplémentaire pour son compte de référence. Un espace mémoire de la taille d'un pointeur non signé est couramment utilisé pour cette tâche, ce qui signifie que 32 ou 64 bits de stockage de comptage de références doivent être alloués pour chaque objet. Sur certains systèmes, il peut être possible d'atténuer cette surcharge en utilisant un pointeur étiqueté pour stocker le nombre de références dans les zones inutilisées de la mémoire de l'objet. Souvent, une architecture ne permet pas réellement aux programmes d'accéder à la gamme complète d'adresses mémoire qui pourraient être stockées dans sa taille de pointeur natif ; un certain nombre de bits de poids fort dans l'adresse est ignoré ou doit être égal à zéro. Si un objet a de manière fiable un pointeur à un certain emplacement, le compteur de références peut être stocké dans les bits inutilisés du pointeur. Par exemple, chaque objet en Objective-C a un pointeur vers sa classe au début de sa mémoire ; sur l' architecture ARM64 utilisant iOS 7 , 19 bits inutilisés de ce pointeur de classe sont utilisés pour stocker le nombre de références de l'objet.
Surcharge de vitesse (incrément/décrément)
Dans les implémentations naïves, chaque affectation d'une référence et chaque référence sortant du champ d'application nécessitent souvent des modifications d'un ou plusieurs compteurs de références. Cependant, dans un cas courant lorsqu'une référence est copiée d'une variable de portée externe dans une variable de portée interne, de sorte que la durée de vie de la variable interne est limitée par la durée de vie de la variable externe, l'incrémentation de la référence peut être éliminée. La variable externe "possède" la référence. Dans le langage de programmation C++, cette technique est facilement implémentée et démontrée à l'aide de constréférences. Le comptage de références en C++ est généralement implémenté à l'aide de " pointeurs intelligents " dont les constructeurs, les destructeurs et les opérateurs d'affectation gèrent les références. Un pointeur intelligent peut être passé par référence à une fonction, ce qui évite d'avoir à copier-construire un nouveau pointeur intelligent (ce qui augmenterait le nombre de références à l'entrée dans la fonction et le diminuerait à la sortie). Au lieu de cela, la fonction reçoit une référence au pointeur intelligent qui est produit à peu de frais. La méthode de comptage de références Deutsch-Bobrow capitalise sur le fait que la plupart des mises à jour de comptage de références sont en fait générées par des références stockées dans des variables locales. Il ignore ces références, ne comptant que les références dans le tas, mais avant qu'un objet avec un compteur de références à zéro puisse être supprimé, le système doit vérifier avec un balayage de la pile et enregistre qu'aucune autre référence à celui-ci n'existe encore. Une autre diminution substantielle de la surcharge sur les mises à jour des compteurs peut être obtenue par la fusion des mises à jour introduite par Levanoni et Petrank . Considérons un pointeur qui dans un intervalle donné de l'exécution est mis à jour plusieurs fois. Il pointe d'abord vers un objet O1, puis vers un objet O2, et ainsi de suite jusqu'à ce qu'à la fin de l'intervalle il pointe vers un objet On. Un algorithme de comptage de références exécuterait généralement rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Mais la plupart de ces mises à jour sont redondantes. Pour que le décompte de référence soit correctement évalué à la fin de l'intervalle, il suffit d'effectuer rc(O1)--et rc(On)++. Levanoni et Petrank ont ​​mesuré une élimination de plus de 99% des mises à jour de compteur dans les benchmarks Java typiques.
Nécessite une atomicité
Lorsqu'elles sont utilisées dans un environnement multithread , ces modifications (incrémentation et décrémentation) peuvent nécessiter des opérations atomiques telles que compare-and-swap , au moins pour tous les objets partagés ou potentiellement partagés entre plusieurs threads. Les opérations atomiques sont chères sur un multiprocesseur, et encore plus chères si elles doivent être émulées avec des algorithmes logiciels. Il est possible d'éviter ce problème en ajoutant des décomptes de références par thread ou par CPU et en n'accédant au décompte de références global que lorsque les décomptes de références locaux deviennent ou ne sont plus nuls (ou, à défaut, en utilisant un arbre binaire de décomptes de références, ou même renoncer à une destruction déterministe en échange de l'absence de décompte global de références), mais cela ajoute une surcharge mémoire importante et a donc tendance à n'être utile que dans des cas particuliers (il est utilisé, par exemple, dans le décompte des références des modules du noyau Linux ). La fusion des mises à jour par Levanoni et Petrank peut être utilisée pour éliminer toutes les opérations atomiques de la barrière d'écriture. Les compteurs ne sont jamais mis à jour par les threads du programme au cours de l'exécution du programme. Ils ne sont modifiés que par le collecteur qui s'exécute comme un seul thread supplémentaire sans synchronisation. Cette méthode peut être utilisée comme mécanisme d'arrêt du monde pour les programmes parallèles, ainsi qu'avec un collecteur de comptage de références concurrent.
Pas en temps réel
Les implémentations naïves du comptage de références ne fournissent généralement pas de comportement en temps réel, car toute affectation de pointeur peut potentiellement entraîner la libération récursive d'un certain nombre d'objets limités uniquement par la taille totale de la mémoire allouée alors que le thread est incapable d'effectuer d'autres travaux. Il est possible d'éviter ce problème en déléguant la libération d'objets non référencés à d'autres threads, au prix d'un surcoût supplémentaire.

Analyse de fuite

L'analyse d'échappement est une technique de compilation qui peut convertir les allocations de tas en allocations de pile , réduisant ainsi la quantité de récupération de place à effectuer. Cette analyse détermine si un objet alloué à l'intérieur d'une fonction est accessible à l'extérieur de celle-ci. Si une allocation locale de fonction s'avère accessible à une autre fonction ou thread, l'allocation est dite « échapper » et ne peut pas être effectuée sur la pile. Sinon, l'objet peut être alloué directement sur la pile et libéré au retour de la fonction, en contournant le tas et les coûts de gestion de mémoire associés.

Disponibilité

De manière générale, les langages de programmation de niveau supérieur sont plus susceptibles d'avoir la récupération de place en standard. Dans certains langages qui n'ont pas de ramasse-miettes intégré, il peut être ajouté via une bibliothèque, comme avec le ramasse-miettes Boehm pour C et C++.

La plupart des langages de programmation fonctionnels , tels que ML , Haskell et APL , intègrent le ramasse-miettes. Lisp est particulièrement remarquable en tant que premier langage de programmation fonctionnel et premier langage à introduire le ramasse-miettes.

D'autres langages dynamiques, tels que Ruby et Julia (mais pas Perl  5 ou PHP avant la version 5.3, qui utilisent tous deux le comptage de références), JavaScript et ECMAScript ont également tendance à utiliser GC. Les langages de programmation orientés objet tels que Smalltalk et Java fournissent généralement un ramasse-miettes intégré. Les exceptions notables sont C++ et Delphi , qui ont des destructeurs .

DE BASE

BASIC et Logo ont souvent utilisé le ramasse-miettes pour les types de données de longueur variable, tels que les chaînes et les listes, afin de ne pas surcharger les programmeurs avec des détails de gestion de la mémoire. Sur l' Altair 8800 , les programmes avec de nombreuses variables de chaîne et peu d'espace de chaîne peuvent provoquer de longues pauses en raison de la récupération de place. De même, l' algorithme de récupération de place de l'interpréteur Applesoft BASIC analyse à plusieurs reprises les descripteurs de chaîne pour la chaîne ayant l'adresse la plus élevée afin de la compacter vers une mémoire élevée, ce qui entraîne des performances et des pauses allant de quelques secondes à quelques minutes. Un ramasse-miettes de remplacement pour Applesoft BASIC par Randy Wigginton identifie un groupe de chaînes à chaque passage sur le tas, réduisant considérablement le temps de collecte. BASIC.System, publié avec ProDOS en 1983, fournit un ramasse-miettes de fenêtrage pour BASIC qui est beaucoup plus rapide.

Objectif c

Alors que l' Objective-C n'avait traditionnellement pas de récupération de place, avec la sortie d' OS X 10.5 en 2007, Apple a introduit la récupération de place pour Objective-C  2.0, en utilisant un collecteur d'exécution développé en interne. Cependant, avec la version 2012 d' OS X 10.8 , la récupération de place a été dépréciée en faveur du compteur de référence automatique (ARC) de LLVM qui a été introduit avec OS X 10.7 . De plus, depuis mai 2015, Apple interdit même l'utilisation du ramasse-miettes pour les nouvelles applications OS X dans l' App Store . Pour iOS , la récupération de place n'a jamais été introduite en raison de problèmes de réactivité et de performances des applications ; à la place, iOS utilise ARC.

Environnements limités

La collecte des ordures est rarement utilisée sur les systèmes embarqués ou en temps réel en raison du besoin habituel d'un contrôle très strict sur l'utilisation de ressources limitées. Cependant, des ramasse-miettes compatibles avec de nombreux environnements limités ont été développés. Le Microsoft .NET Micro Framework , .NET nanoFramework et Java Platform, Micro Edition sont des plates-formes logicielles intégrées qui, comme leurs cousins ​​plus grands, incluent la récupération de place.

Java

Les récupérateurs de place disponibles dans les JDK Java incluent :

Utilisation au moment de la compilation

Le ramasse-miettes au moment de la compilation est une forme d' analyse statique permettant de réutiliser et de récupérer la mémoire en fonction des invariants connus lors de la compilation.

Cette forme de ramasse-miettes a été étudiée dans le langage de programmation Mercury , et elle a connu une plus grande utilisation avec l'introduction du compteur de référence automatique (ARC) de LLVM dans l'écosystème d'Apple (iOS et OS X) en 2011.

Systèmes temps réel

Des ramasse-miettes incrémentiels, simultanés et en temps réel ont été développés, tels que l' algorithme de Baker ou l'algorithme de Lieberman .

Dans l'algorithme de Baker, l'allocation se fait dans l'une ou l'autre moitié d'une seule région de mémoire. Lorsqu'il est à moitié plein, un ramasse-miettes est effectué qui déplace les objets vivants dans l'autre moitié et les objets restants sont implicitement désalloués. Le programme en cours d'exécution (le « mutateur ») doit vérifier que tout objet auquel il fait référence est dans la bonne moitié, et sinon le déplacer, pendant qu'une tâche en arrière-plan trouve tous les objets.

Les schémas de collecte de déchets générationnels sont basés sur l'observation empirique que la plupart des objets meurent jeunes. Dans le garbage collection générationnel, deux ou plusieurs régions d'allocation (générations) sont conservées, qui sont séparées en fonction de l'âge de l'objet. De nouveaux objets sont créés dans la "jeune" génération qui est régulièrement collectée, et lorsqu'une génération est pleine, les objets qui sont encore référencés à partir de régions plus anciennes sont copiés dans la génération suivante la plus ancienne. Parfois, une analyse complète est effectuée.

Certaines architectures informatiques de langage de haut niveau incluent une prise en charge matérielle pour la récupération de place en temps réel.

La plupart des implémentations de ramasse-miettes en temps réel utilisent le traçage . De tels récupérateurs de place en temps réel répondent à des contraintes strictes en temps réel lorsqu'ils sont utilisés avec un système d'exploitation en temps réel.

Voir également

Les références

Lectures complémentaires

Liens externes