Comment amener le noyau à compacter la mémoire fragmentée

Je cours Fedora 26.

Ceci est pour une tâche très étrange donnée par mon professeur d'algorithmes. La mission dit:

Fragmentation de la mémoire en C:
Concevez, implémentez et exécutez un programme C qui fait ce qui suit: Il alloue de la mémoire pour une séquence de 3mtableaux de 800 000 éléments chacun; puis il désalloue explicitement tous les tableaux pairs et alloue une séquence de mtableaux de taille 900 000 éléments chacun. Mesurez le temps nécessaire à votre programme pour l'allocation de la première séquence et de la deuxième séquence. Choisissez md'épuiser la quasi-totalité de la mémoire principale disponible pour votre programme. "

L'objectif global de ceci est de fragmenter la mémoire puis de demander un peu plus que ce qui est disponible en tant que bloc contigu, forçant le système d'exploitation à compacter ou défragmenter la mémoire.

En classe, j'ai demandé comment procéder, car la mémoire est visualisée et non contiguë, ce à quoi il a répondu: "Eh bien, vous devrez désactiver [la mémoire virtuelle]." Certains autres étudiants ont demandé en classe comment nous devrions savoir quand nous avons atteint ce "ramassage des ordures", et il a dit que: "Le moment de la deuxième allocation devrait être supérieur au premier en raison du temps pris par le ramassage des ordures"

Après avoir cherché un peu, la chose la plus proche que j'ai pu trouver pour désactiver la mémoire virtuelle était de désactiver la mémoire d'échange avec swapoff -a. J'ai désactivé mon environnement de bureau et compilé et exécuté mon programme à partir du terminal natif (pour éviter toute interférence possible avec d'autres processus, en particulier un environnement lourd comme l'environnement de bureau). J'ai fait cela et j'ai exécuté mon programme en augmentant mjusqu'à ce que j'arrive à un point où le moment de la deuxième allocation était plus grand que le premier.

J'ai dirigé le programme avec une augmentation met finalement trouvé un point où le temps pour la deuxième allocation était plus long que le temps pour la première allocation. En cours de route, j'ai toutefois atteint un point où le processus a été tué avant la deuxième attribution. J'ai vérifié dmesget j'ai vu qu'il avait été tué par un oomtueur. J'ai trouvé et lu plusieurs articles sur oom-killer et découvert que vous pouviez désactiver la surallocation de mémoire par le noyau.

Je l'ai fait et j'ai relancé mon programme, mais cette fois, je n'ai pas pu trouver un mtel que le timing de la seconde était plus élevé que le premier. Finalement, avec m de plus en plus grand (bien que beaucoup plus petit que lorsque la surutilisation était activée) malloc échouerait et mon programme se terminerait.

J'ai trois questions, dont la première n'est pas vraiment importante:

1. La collecte des ordures est-elle le terme correct pour cela? Mon professeur est très catégorique en disant qu'il s'agit de la collecte des ordures, mais je pensais que la collecte des ordures était effectuée par des langages de programmation et que cela serait considéré comme plus défragmentant.

2. Le compactage comme il le souhaite est-il possible sur un système Linux?

3. Pourquoi ai-je pu atteindre un point où le temps pour la deuxième allocation était plus élevé que le premier lorsque j'ai désactivé l'échange mais que la surallocation de mémoire était toujours activée? Le compactage a-t-il réellement eu lieu? Si oui, pourquoi n'ai-je pas pu atteindre un point où le compactage s'est produit après avoir désactivé la surutilisation de la mémoire?

Bravo pour vos recherches jusqu'à présent, il s'agit en effet d'un ensemble de questions intéressant.

Il y a un aspect important à considérer ici de manière générale: l'allocation de mémoire est en partie la responsabilité du système d'exploitation, et en partie la responsabilité de chaque processus en cours d'exécution (en ignorant les anciens systèmes sans protection de la mémoire et les espaces d'adressage virtuels). Le système d'exploitation prend soin de fournir à chaque processus son propre espace d'adressage et d'allouer de la mémoire physique aux processus lorsque cela est nécessaire. Chaque processus prend soin de découper son espace d'adressage (dans une certaine mesure) et de s'assurer qu'il est utilisé de manière appropriée. Notez que la responsabilité d'un processus sera largement invisible pour les programmeurs, car l'environnement d'exécution s'occupe de la plupart des choses.

Maintenant, pour répondre à vos questions ...

1. Dans mon esprit, la collecte des ordures est à une étape de ce que vous faites ici. J'imagine que vous écrivez en C, en utilisant malloc()et free(). La récupération de place , lorsqu'elle est prise en charge par le langage de programmation et l' environnement d'exécution, prend en charge la dernière partie: elle identifie les blocs de mémoire qui étaient précédemment alloués mais ne sont plus utilisés (et, surtout, ne peuvent plus jamais être utilisés), et les renvoie à l'allocateur. La question liée dans le commentaire de JdeBP fournit un certain contexte, mais je la trouve surtout intéressante car elle démontre que différentes personnes ont des opinions très différentes sur la collecte des ordures, et même ce qui constitue la collecte des ordures.

   Dans le contexte qui nous intéresse, j'utiliserais le «compactage de la mémoire» pour parler du processus en discussion.

2. Du point de vue de la programmation en espace utilisateur, ce que votre professeur demande n'est pas possible, en C, sous Linux, pour une raison simple: ce qui nous intéresse ici, ce n'est pas la fragmentation de la mémoire physique, c'est la fragmentation de l'espace d'adressage. Lorsque vous allouez vos nombreux blocs de 800 000 octets, vous vous retrouverez avec autant de pointeurs vers chaque bloc. Sous Linux, à ce stade, le système d'exploitation lui-même n'a pas fait grand-chose, et vous n'avez pas nécessairement de mémoire physique pour chaque allocation (en passant, avec des allocations plus petites, le système d'exploitation ne serait pas impliqué du tout, juste votre L'allocateur de la bibliothèque C; mais les allocations ici sont suffisamment importantes pour que la bibliothèque C utilisemmap, qui est géré par le noyau). Lorsque vous libérez les blocs impairs, vous récupérez ces blocs d'espace d'adressage, mais vous ne pouvez pas changer les pointeurs que vous avez vers les autres blocs. Si vous imprimez les pointeurs au fur et à mesure, vous verrez que la différence entre eux n'est pas beaucoup plus que la demande d'allocation (802 816 octets sur mon système); il n'y a pas de place entre deux pointeurs pour un bloc de 900 000 octets. Parce que votre programme a des pointeurs réels vers chaque bloc, plutôt qu'une valeur plus abstraite (dans d'autres contextes, un handle), l'environnement d'exécution ne peut rien y faire, et il ne peut donc pas compacter sa mémoire pour fusionner les blocs libres.

   Si vous utilisez un langage de programmation où les pointeurs ne sont pas un concept visible par le programmeur, alors le compactage de la mémoire est possible, sous Linux. Une autre possibilité serait d'utiliser une API d'allocation de mémoire où les valeurs renvoyées ne sont pas des pointeurs; voir par exemple les fonctions d'allocation de tas basées sur des descripteurs sous Windows (où les pointeurs ne sont valides que lorsqu'un descripteur est verrouillé).

3. L'exercice de votre professeur mesure efficacement les performances de mmap, ce qui inclut son algorithme de marche libre. Vous allouez d'abord 3 × m blocs, puis en libérez la moitié, puis recommencez à allouer m blocs; libérer tous ces blocs vide une énorme charge de blocs libres sur l'allocateur du noyau, dont il a besoin de garder une trace (et le temps pris par les freeappels montre qu'aucune optimisation n'est en cours à ce stade). Si vous suivez les temps d'allocation de chaque bloc individuel, vous verrez alors que la première allocation de 900k prend beaucoup, beaucoupplus long que les autres (trois ordres de grandeur sur mon système), le second est beaucoup plus rapide mais prend encore beaucoup plus de temps (deux ordres de grandeur), et la troisième allocation est de retour aux niveaux de performance typiques. Il se passe donc quelque chose, mais les pointeurs renvoyés montrent qu'il ne s'agissait pas de compactage de mémoire, du moins pas de compactage de blocs alloué (ce qui, comme expliqué ci-dessus, est impossible) - vraisemblablement, le temps correspond au temps de traitement des structures de données utilisées par le noyau pour garder une trace de l'espace d'adressage disponible dans le processus (je vérifie cela et mettra à jour plus tard). Ces longues allocations peuvent se multiplier pour éclipser les séquences d'allocation globales que vous mesurez, c'est-à-dire lorsque les allocations de 900k finissent par prendre plus de temps que les allocations de 800k.

   La surcharge excessive modifie le comportement que vous voyez est qu'elle modifie l'exercice de la simple manipulation de l'espace d'adressage à l'allocation réelle de la mémoire et réduit ainsi la taille de votre terrain de jeu. Lorsque vous pouvez surcharger, le noyau n'est limité que par l'espace d'adressage de votre processus, vous pouvez donc allouer beaucoup plus de blocs et mettre beaucoup plus de pression sur l'allocateur. Lorsque vous désactivez la surcharge, le noyau est limité par la mémoire disponible, ce qui réduit la valeur que vous pouvez avoir pour mdes niveaux où l'allocateur n'est pas suffisamment stressé pour que les temps d'allocation explosent.