Algorithmes de marquage et balayage

Les algorithmes de cette catégorie marquent les objets balayés comme étant vivants.

Une deuxième phase, la phase de balayage, parcourt la mémoire linéairement. Lorsqu'un objet non marqué est trouvé, - il n'est donc pas vivant - la mémoire qu'il occupe est récupérée, par exemple par stockage dans une liste de blocs libres (en Anglais : free list).

L'avantage de cet algorithme est qu'il nécessite relativement peu de mémoire supplémentaire par rapport à la mémoire nécessaire pour stocker les objets vivants.

L'inconvénient principal est que le temps d'exécution de l'algorithme est proportionnel à la taille de la mémoire entière. Cet algorithme a aussi tendance à disperser les objets dans la mémoire, ce qui nuit parfois à la localité spatiale des objets. Les systèmes de gestion manuelle de la mémoire ont le même inconvénient.



Irene DURAND
2011-10-14