Quels sont les algorithmes derrière GC à faible pause?

Certaines langues, par exemple java, ont introduit un GC à faible pause.

Ces GC peuvent faire la plupart du travail sans interrompre le monde entier. C'est évidemment un problème assez difficile car il nécessite d'analyser la mémoire lorsque le thread le modifie, ce qui entraîne des données qui peuvent être utilisées au début du processus et non plus à la fin, ou des données qui semblent être des ordures mais parce que le la référence a été déplacée dans la mémoire et n'est jamais apparue là où le GC regardait.

Donc, en gros, quel est l'algorithme derrière cela?

Les articles de recherche ou le lien d'un article vraiment technique seraient considérés comme une réponse valable, car ce sujet est vraiment technique.

Donc, en gros, quel est l'algorithme derrière cela?

Il s'agit essentiellement d'un algorithme de marquage et de balayage qui s'exécute "simplement" simultanément dans un thread séparé.

Quant aux articles de recherche sur ce sujet:

• Ramassage très ordonné des marques et des balayages sans synchronisation à grain fin

• Collectionneur de garbabe à balayage simultané (contient des liens vers deux articles, l'un répertorié ci-dessous)

• Implémentation d'un ramasse-miettes à la volée pour Java

• Collecte des ordures portable et discrète pour les systèmes multiprocesseurs (Doligez Leroy, présentation PowerPoint)

• Collecte des ordures à la volée: un exercice de coopération (par Edsger Wybe Djikstra)

d'après ce que je comprends, le garbage collector Java G1 utilise des régions dites de tas pour éviter de faire une pause dans le monde entier. Selon moi, alors que l'une des régions est verrouillée par GC lors du nettoyage, l'allocation de mémoire est effectuée dans une autre région.

Voici une explication de Jeremy Manson :

Le principe est simple: le collecteur divise le tas en régions de taille fixe et suit les données en direct dans ces régions. Il conserve un ensemble de pointeurs - "l'ensemble mémorisé" - dans et hors de la région. Lorsqu'un GC est jugé nécessaire, il recueille d'abord les régions avec moins de données en direct (d'où «les ordures en premier»). Souvent, cela peut signifier la collecte d'une région entière en une seule étape: si le nombre de pointeurs dans une région est nul, alors il n'est pas nécessaire de marquer ou de balayer cette région ...

• voici un document technique des ingénieurs de Sun expliquant leur conception: Garbage-First Garbage Collection

La JVM en temps réel d'IBM utilise un garbage collector appelé Metronome qui divise l'activité GC en quanta discrets et les entrelace avec le traitement des applications. Donc, fondamentalement, au lieu de pauses d'arrêt du monde périodiques (et non déterministes), l'application s'exécute plutôt légèrement plus lentement tandis que le GC se fait en parallèle.

Il existe un autre GC qui effectue une défragmentation dynamique et répond aux exigences en temps réel difficile, mais la seule référence que je peux trouver est ici (adhésion ACM requise).

Un garbage collector en temps réel intéressant est sans fin . Il utilise l'approche traditionnelle de marquage et de balayage, mais est conçu pour être utilisé sur des systèmes multiprocesseurs et prend en charge le multithreading simultané sans verrouillage.

La raison pour laquelle cela fonctionne est que, en Java, seul le GC peut libérer de la mémoire qui pourrait contenir des références GC. Cela signifie que tant que vous pouvez lire des objets dans un thread séparé en toute sécurité, vous n'aurez qu'à suspendre le programme pour observer les références sur la pile.

Je suggérerais pour la mutation qu'ils mettent en œuvre une certaine forme de copie sur écriture pour informer le GC du changement.