Comment fonctionne Boehm GC pour le programme C?

Question

J'ai vérifié Boehm GC. Le GC pour C / C ++.

Je sais algorithme de marquage et de balayage. Ce que je suis curieux comment il prend seulement des pointeurs dans la mémoire entière C. Ma compréhension de la mémoire C est juste un tableau d'octets ordinaire. Est-il possible de déterminer une valeur en mémoire est pointeur ou non?

Answer 1

Le GC Boehm est un collecteur conservatrice, ce qui signifie assume tout est un pointeur. Cela signifie qu'il peut trouver de fausses références positives, comme un entier qui a par hasard la valeur d'une adresse dans le tas. En conséquence, certains blocs peuvent rester en mémoire plus longtemps qu'ils ne le feraient avec un collecteur non-conservateur.

Voici une description de la page de Boehm :

Le ramasse-miettes utilise un jour algorithme de marquage-balayage. conceptuellement fonctionne à peu près en quatre phases, qui sont parfois effectuées dans le cadre de une allocation de mémoire:

1. Préparation Chaque objet a un bit de marque associée. Effacer tout marque les bits, ce qui indique que tous les objets sont potentiellement injoignable.
2. Phase Mark Marque tous les objets qui peuvent être accessibles via des chaînes de pointeurs à partir de variables. souvent, la collecteur n'a pas d'informations réel sur l'emplacement du pointeur variables dans le tas, il voit tout Les zones de données statiques, des piles et registres comme contenant potentiellement pointeurs. Tous les modèles de bits représenter les adresses à l'intérieur de tas objets gérés par le collecteur sont considérés comme des pointeurs. À moins que le client programme a fait l'objet de mise en page tas informations dont dispose la collecteur, tous les objets tas constaté être accessible à partir de variables sont à nouveau De la même façon numérisée.
3. phase de balayage scanne le tas pour inaccessible, et donc non marqué, des objets, et les renvoie à un appropriés liste libre pour la réutilisation. Ce est pas vraiment une phase séparée; même en mode non incremental est opération est généralement effectuée sur la demande lors d'une allocation qui découvre une liste libre vide. Ainsi, le phase de balayage est très peu susceptible de toucher une page qui n'aurait pas été touché peu après de toute façon.
4. objets de phase Finalisation injoignables qui avaient été enregistrés pour finalisation sont pour en file d'attente finalisation en dehors du collecteur.

Vous devez également savoir que le Boehm GC doit être donné un ensemble de « racines », qui sont des points de départ pour l'algorithme de marquage et de balayage. La pile et les registres sont automatiquement racines. Vous devez ajouter explicitement pointeurs globaux comme les racines.

---

EDIT: Dans les commentaires, certaines préoccupations ont été signalées sur les collecteurs conservateurs en général. Il est vrai que les entiers qui ressemblent à des pointeurs de tas au collecteur peut causer la mémoire ne doivent pas être libérés. Ce n'est pas aussi grand d'un problème que vous pourriez penser. La plupart des entiers scalaires dans un programme sont utilisés pour le comptage et tailles et sont assez petites (pour ne pas ressembler à des pointeurs de tas). Vous la plupart du temps un problème avec des tableaux contenant des bitmaps, des chaînes, des données en virgule flottante, ou quoi que ce soit de ce genre. GC Boehm vous permet d'allouer un bloc avec GC_MALLOC_ATOMIC qui indique au collecteur que le bloc ne contiendra pas de pointeurs. Si vous regardez dans gc_typed.h , vous trouverez également des moyens de spécifier les parties de un bloc peut contenir des pointeurs.

Cela dit, une limitation fondamentale d'un collecteur conservateur est qu'il ne peut pas se déplacer en toute sécurité autour de la mémoire lors de la collecte depuis ré-écriture de pointeur n'est pas sûr. Cela signifie que vous n'obtiendrez l'un des avantages de compactage comme réduit la fragmentation et l'amélioration des performances du cache.