Aller au contenu
Accueil » Actualités » Dynamic garbage collector

Dynamic garbage collector

Introduction

Les langages informatiques modernes incluent majoritairement un système de gestion de mémoire automatique appelé ramasse-miettes ou garbage collector (GC). Cette fonctionnalité réduit le risque d’erreurs comme les fuites mémoires ou les erreurs de segmentation. La complexité croissante des logiciels et algorithmes proposés impose l’usage de ce genre de fonctionnalité afin d’assurer un niveau minimum de qualité de fonctionnement. Cependant la gestion déléguée de la mémoire induit des effets indésirables en terme de performance ou de consommation mémoire.

Le langage CLAIRE étant conçu pour élaborer des algorithmes complexes de manière élégante en proposant notamment des fonctionnalités avancées dans le domaine des langage informatiques comme le « versionning », il dispose logiquement d’un ramasse-miettes.

Nous avons étudié le rammasse-miette de CLAIRE et avons recherché à l’améliorer.

Le ramasse-miettes de CLAIRE

CLAIRE est un langage dédié notamment aux algorithmes d’exploration d’arbres, de propagation de contraintes et de raisonnement hypothétique. Ces techniques de programmation impliquent un grand nombre d’allocations mémoire. Le temps d’allocation mémoire est donc primordial pour les performances.

Il a donc été implémenté par les concepteur un ramasse-miette de type « mark and sweep » combiné à une allocation spécialisée utilisant une zone mémoire pré-allouée. La mémoire comporte deux zones d’égales dimensions : chunk & short.

La première zone de type « chunk » est adaptée à l’allocation d’objets de dimensions variables. Elle est composée de cellules chainées dont la taille double d’une cellule à l’autre. La seconde zone « short » est composé de cellules d’égales dimensions. Elle est principalement utilisée pour stocker les données de petite taille (nombres …).

Chunk Short

Le ramasse-miette est appelé quand toutes les cellules sont utilisées. Comme son nom l’indique, il fonctionne en deux étapes, marquant les cellules utilisées dans un premier temps à partir des variables protégées, puis libérant les cellules non marquées.

Si ce système est performant en terme d’allocation, il ne permet pas d’étendre la mémoire disponible et donc demande de calibrer la mémoire statiquement à la création du processus. Idéal pour des applications universitaires, ou à dimension fixe, ce système est un handicap dans le cadre de processus distribués calculant des requêtes utilisateurs aboutissant à des problèmes de dimensions très variables.

La taille de la mémoire est définie au lancement du processus avec l’option « -s ». Le chiffre fourni correspond à une taille mémoire de 2(10+x)

claire -s <taille mémoire> <taille pile d’appel>

Allocation dynamique

Nous avons recherché à doter CLAIRE d’un nouveau ramasse-miettes permettant plus de souplesse de fonctionnement. L’ensemble des différentes techniques connues a été étudié, notamment les techniques de comptage de références et de copies, comme la possibilité de paralléliser le traitement.

Nos différentes analyses et expérimentations nous ont mené à une solution hybride, permettant de garder les performances actuelles, tout en gardant un contrôle sur la mémoire utilisée.

Le système retenu consiste à exploiter la gestion moderne de la mémoire des systèmes d’exploitation. En effet lors d’une demande d’allocation mémoire, les systèmes modernes réservent simplement un espace d’adressage continu (si possible) et crée des pages de données associées au moment de l’écriture.

Nous avons ainsi modifié le système d’allocation en allouant une grande zone mémoire et contraignant les allocations dans une partie de cette zone mémoire jusqu’à la congestion mémoire.

Nouvelle zone mémoire allouée par CLAIRE :

En hachuré, la zone allouée au système mais interdite à l’allocation CLAIRE. Si congestion, nous doublons la mémoire disponible :

Le mécanisme est activé avec l’option « -auto ».

Conclusion

Le nouveau système combine les avantages du système précédent, en terme d’efficacité et de contrôle de la mémoire, tout en gagnant une grande souplesse de fonctionnement dans un environnement serveur.

Références

  • Spécification et compilation d’un langage de haut niveau pour l’Optimisation Combinatoire : CLAIRE vers Java – François Xavier Josset -2002
  • CLAIRE: Combining Sets, Search And Rules To Better Express Algorithms : Yves Caseau, François-Xavier Josset, François Laburthe – 2004
  • Automatic Garbage Collection – Wikipedia, the free encyclopedia. – 2011
  • Java theory and practice: A brief history of garbage collection – Goetz, Brian – IBM – 2003
  • Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors – Bill McCloskey, David F. Bacon, Perry Cheng, David Grove – 2008