Y a-t-il des récupérateurs qui prennent en compte la pagination?

12

Les ramasse-miettes doivent visiter tous les objets vivants, afin de trouver la mémoire qui peut être récupérée. (Avoir de nombreuses générations retarde juste un peu cela)

Toutes choses étant égales par ailleurs, il est clairement préférable de visiter d'abord l'objet qui est déjà paginé dans la RAM, avant de paginer un autre bloc et donc de paginer un objet.

Une autre possibilité est que lorsque le système d'exploitation souhaite retirer une page de RAM du processus, il est d'abord demandé au GC s'il a une page qui peut être abandonnée sans avoir besoin d'être paginée. Le GC peut être principalement effectué avec le déplacement d'objets d'une page, donc peut effacer cette page dans le délai imparti au système d'exploitation pour avoir besoin d'une page.

Pourtant, je ne me souviens d'aucun garbage collector qui s'intègre au système de pagination du système d'exploitation qui détermine l'ordre dans lequel le GC fonctionne.

Ian Ringrose
la source
Pas exactement la pagination, mais le gc de ruby enterprise edition a été réécrit pour réduire l'effet du gc sur la copie sur les pages d'écriture en déplaçant les métadonnées d'objet sur des pages séparées.
user1937198
Question quelque peu connexe à propos des implémentations malloc / libres: les implémentations malloc renverront-elles de la mémoire libre au système? , en particulier cette réponse . Aussi: free () démappe-t-il la mémoire d'un processus?
Paul A. Clayton
étonnamment, afaik / afaict, presque toute la littérature (?) gc ne semble analyser la pagination du système d'exploitation que de manière abstraite. idée: un système d'allocation de mémoire qui garde une trace des pointeurs entre les objets dans une structure distincte des objets eux-mêmes pourrait être plus convivial / pagination car seuls les pointeurs eux-mêmes sont traversés (pendant gc) dans un espace étroitement compacté au lieu de tous les objets de tailles variables qui peuvent être réparties dans la mémoire (et certaines rarement consultées et donc paginées). il pourrait y avoir quelques frais généraux modestes, mais cela pourrait entraîner des économies globales en fonction de la mise en œuvre.
vzn
Les lecteurs flash doivent utiliser une forme de copie de la récupération de place qui prend en compte l'agencement de la mémoire en blocs, bien que je ne sache pas à quel point ces choses sont discutées dans la littérature universitaire. Les problèmes à résoudre sont très différents (les lecteurs flash ont besoin de GC car l'espace ne peut être recyclé que dans de très gros blocs, donc si un bloc a quelques pages en direct et beaucoup de pages mortes, les données en direct doivent être copiées ailleurs avant la page peut être recyclé) mais les principes de consolidation des données pourraient être utiles.
supercat
1
Un modèle que j'ai utilisé dans les cas où les éléments de données étaient tous petits par rapport à ma taille de bloc de mémoire consistait à ce que chaque élément de données se compose d'un en-tête de taille fixe qui était alloué de l'avant vers l'arrière et de données de taille variable qui être alloué de front à l'avant. Une table a conservé les adresses des blocs logiques mappés aux adresses physiques et la quantité d'espace libre dans chaque bloc; après chaque scan, il identifiait également combien d'espace était mort. Les références étaient stockées en flash, et chaque référence avait la forme "Item # 3 du bloc logique # 7". Un cycle GC copierait toutes les données en direct d'un morceau vers un nouveau, et ...
supercat

Réponses:

8

Si je me souviens bien, les collecteurs de copie sont censés être compatibles avec la pagination, car le traçage par copie a tendance à améliorer la localisation des références de pointeur. Cela a un effet positif sur le programme (mutateur) qui causera moins de défauts de page lors du suivi des liens, et améliorera également le prochain cycle de collecte car le traçage provoquera également moins de défauts de page. Le programme de suivi (quels pointeurs doivent être traités en premier) peut avoir un impact sur l'efficacité de l'amélioration de la localisation des données. Cela peut être amélioré en mesurant les statistiques sur le nombre d'accès à différents pointeurs dans différents types de cellules.

Maintenant, si vous envisagez un collecteur de traçage en général, vous devez généralement conserver une structure qui conserve la trace des pointeurs qui n'ont pas encore été tracés. Il peut être possible d'organiser cette structure afin que tous les pointeurs en attente pointant sur la même page soient conservés ensemble (bien que cela puisse prendre plus de place, dans certains cas, selon les techniques disponibles pour conserver la liste de ces pointeurs). Une stratégie possible consiste alors à toujours tracer d'abord le plus grand ensemble de pointeurs en attente pointant vers la même page, lorsqu'il n'y a plus de pointeur en attente vers les pages en mémoire.

En ce qui concerne la question du troisième paragraphe, qui a été ajoutée après que j'ai répondu, la collecte de copies est à nouveau une réponse. Le système d'exploitation peut réduire le nombre de pages physiques allouées au moment de la collecte, car les pages sont entièrement libérées. Avec un collecteur de marques et de balayages, l'événement d'une page entière gratuite est probablement beaucoup plus rare, ne valant donc pas un machanisme spécifique à prendre en compte.

Ce genre d'idées est naturel et est probablement décrit dans certains articles. Mais je ne m'en souviens pas tout de suite. Je pense que les premiers articles sur Lisp GC contiennent certaines de ces idées (telles que: voiture ou cdr doit-il être suivi en premier?).

La bonne nouvelle dans ce rôle de copie-collection est également que la pagination est conviviale pour copier la collection car elle augmente l'espace de stockage disponible. Rappelons que le collecteur de copie nécessite en principe deux fois plus d'espace que celui utilisé pour le stockage réel des données. Désormais, l'effet de la pagination dépend également de l'espace d'adressage de la machine et de la mémoire physique disponible. Dans les ordinateurs plus anciens, la mémoire physique était bien inférieure à l'espace d'adressage disponible, de sorte que la pagination était vraiment un bonus d'espace, permettant des politiques telles que la copie du GC. Même lorsque l'espace physique est aussi grand que l'espace d'adressage, on peut vouloir le partager, de sorte que le processus utilisant un GC ait moins d'espace d'adressage sans pagination (voir pagination). Ces remarques sont quelque peu dépassées par l'utilisation de collecteurs générationnels. Ils utilisent généralement la collection de copies pour la jeune génération précisément en raison de ces qualités et parce que la jeune génération est généralement de courte durée.

Ensuite, vous avez toutes les interactions du GC générationnel avec le système de cache, qui ont été discutées dans une question précédente: les récupérateurs de génération sont - ils intrinsèquement compatibles avec le cache?

Pour plus d'informations sur ces problèmes, je rechercherais sur le Web avec, par exemple, les mots clés garbage collection et locality .

babou
la source
Je doute que les collectionneurs soient plus «locaux» que le traçage. les collecteurs de copie semblent conceptuellement assez similaires dans la dynamique d'accès à la mémoire (peut-être presque indiscernables) au traçage dans «l'ancien espace». pense que cela a besoin d'une référence. cela dit, il est possible que le mécanisme de copie améliore la contiguïté dans le nouvel espace. le nouvel espace commence parfaitement contigu, mais alors cette «localité» diminue ou se dégrade avec le temps.
vzn
Eh bien, vous avez trouvé la plupart de la réponse. Alors ne soyez pas douteux. C'est dans les références de base sur le sujet. Localité du fait que le stockage est compacté, et de la copie qui remplacent les unes les autres les cellules de données qui sont logiquement proches selon la structure du pointeur (qui peut évoluer avec la réaffectation du pointeur).
babou
suis toujours sceptique / douteux. il semble intuitivement que l'ancien espace aura une mauvaise localisation et / ou contiguïté lorsque le cycle de copie / gc est lancé. la localité est liée aux lectures (depuis l'ancien espace) et aux écritures (vers le nouvel espace). pour l'analyser, il faut étudier le comportement gestalt / émergent. peut-être qu'une grande partie de cela ne peut être étudiée de manière efficace / précise / réaliste que empiriquement et pas beaucoup en théorie.
vzn
Je dis que c'est dans la littérature, comme beaucoup d'autres choses. Mais je n'ai pas le temps de le chercher et je pense que ma réponse est longue et pleine d'informations., Vous pouvez google: garbage collection copy locality, et il y a une référence à une question précédente. Désolé d'être laconique, j'ai pris un train à attraper.
babou
Désolé ... confondez cette question avec une autre ... qui en a plus.
babou
8

Emery Berger, Matthew Hertz et Yi Feng ont travaillé sur ce sujet.

La récupération de place offre de nombreux avantages en matière d'ingénierie logicielle, mais interagit mal avec les gestionnaires de mémoire virtuelle. Les récupérateurs de place existants nécessitent beaucoup plus de pages que l'ensemble de travail et les pages tactiles de l'application, sans tenir compte de celles qui sont en mémoire, en particulier lors de la récupération de place complète. La pagination qui en résulte peut faire chuter le débit et les temps de pause atteindre des secondes, voire des minutes.

Je présente un ramasse-miettes qui évite la pagination. Ce collecteur de signets coopère avec le gestionnaire de mémoire virtuelle pour guider ses décisions d'expulsion.

Ceci est une vidéo de la conversation d'Emery à ce sujet, et il a écrit un document Garbage Collection Without Paging

Pour certaines raisons, il ne semble pas y avoir beaucoup de travail plus tard, ni aucune utilisation du «monde réel». À la fin de l'article, il est écrit «Nous développons une variante simultanée de l'algorithme de collecte de signets» , mais je ne peux pas le retrouver.

CRAMM: la prise en charge de la mémoire virtuelle pour les applications récupérées sur les déchets cherche à modifier le système d'exploitation pour que le GC crée moins de pagination.

Utilisation de Page Residency pour équilibrer les compromis dans le traçage de la récupération de place

Nous introduisons une extension de la plupart de la collection de copie qui utilise la résidence de page pour déterminer quand déplacer les objets. Notre collectionneur fait la promotion des pages avec une haute résidence en place, en évitant les travaux inutiles et le gaspillage d'espace. Il prédit la résidence de chaque page, mais lorsque ses prédictions s'avèrent inexactes, notre collecteur récupère l'espace inoccupé en l'utilisant pour satisfaire les demandes d'allocation.L'utilisation de la résidence permet à notre collecteur d'équilibrer dynamiquement les compromis de la copie et de la non-copie. Notre technique nécessite moins d'espace qu'un collecteur à copie pure et prend en charge l'épinglage d'objet sans pour autant sacrifier la capacité de déplacer des objets.Contrairement à d'autres hybrides, notre collecteur ne dépend pas de la configuration spécifique à l'application et peut réagir rapidement au changement de comportement de l'application. Nos mesures montrent que notre hybride fonctionne bien dans diverses conditions; il préfère copier la collection lorsqu'il y a suffisamment d'espace de tas, mais retombe sur la collection non copiante lorsque l'espace devient limité.

Ian Ringrose
la source