Qu'est-ce que la fragmentation de la mémoire ?

Question

J'ai entendu le terme "fragmentation de la mémoire" utilisé à plusieurs reprises dans le contexte de l'allocation dynamique de la mémoire en C++. J'ai trouvé quelques questions sur la façon de gérer la fragmentation de la mémoire, mais je n'ai pas trouvé de question directe qui la traite elle-même. Donc :

• Qu'est-ce que la fragmentation de la mémoire ?
• Comment puis-je savoir si la fragmentation de la mémoire est un problème pour mon application ? Quel type de programme est le plus susceptible d'en souffrir ?
• Quelles sont les bonnes méthodes courantes pour traiter la fragmentation de la mémoire ?

Aussi :

• J'ai entendu dire qu'utiliser beaucoup d'allocations dynamiques peut augmenter la fragmentation de la mémoire. Est-ce vrai ? Dans le contexte du C++, je comprends que tous les conteneurs standard (std::string, std::vector, etc.) utilisent l'allocation dynamique de la mémoire. Si ces conteneurs sont utilisés tout au long d'un programme (en particulier std::string), la fragmentation de la mémoire est-elle plus susceptible de poser problème ?
• Comment gérer la fragmentation de la mémoire dans une application à forte composante STL ?

Answer 1

Imaginez que vous disposez d'une "grande" étendue de mémoire libre (32 octets) :

----------------------------------
|                                |
----------------------------------

Maintenant, attribuez-en une partie (5 attributions) :

----------------------------------
|aaaabbccccccddeeee              |
----------------------------------

Maintenant, libérez les quatre premières allocations mais pas la cinquième :

----------------------------------
|              eeee              |
----------------------------------

Maintenant, essayez d'allouer 16 octets. Oups, je ne peux pas, même s'il y a presque deux fois plus d'espace libre.

Sur les systèmes dotés d'une mémoire virtuelle, la fragmentation est moins problématique que vous ne le pensez, car les allocations importantes ne doivent être contiguës qu'en virtuel et non dans l'espace d'adressage physique espace d'adressage. Ainsi, dans mon exemple, si j'avais de la mémoire virtuelle avec une taille de page de 2 octets, je pourrais effectuer mon allocation de 16 octets sans problème. La mémoire physique ressemblerait à ceci :

----------------------------------
|ffffffffffffffeeeeff            |
----------------------------------

alors que la mémoire virtuelle (étant beaucoup plus grande) pourrait ressembler à ceci :

------------------------------------------------------...
|              eeeeffffffffffffffff                   
------------------------------------------------------...

Le symptôme classique de la fragmentation de la mémoire est que vous essayez d'allouer un grand bloc et que vous n'y arrivez pas, même si vous semblez avoir suffisamment de mémoire libre. Une autre conséquence possible est l'incapacité du processus à restituer de la mémoire au système d'exploitation (parce que chacun des grands blocs qu'il a alloués depuis le système d'exploitation, pour des raisons de sécurité, n'est pas disponible). malloc etc. à subdiviser, il lui reste quelque chose, même si la majeure partie de chaque bloc est désormais inutilisée).

Les tactiques visant à empêcher la fragmentation de la mémoire en C++ fonctionnent en allouant des objets à partir de différentes zones en fonction de leur taille et/ou de leur durée de vie prévue. Ainsi, si vous avez l'intention de créer un grand nombre d'objets et de les détruire tous ensemble plus tard, allouez-les à partir d'un pool de mémoire. Toutes les autres allocations que vous ferez entre eux ne proviendront pas du pool, et ne seront donc pas situées entre eux dans la mémoire, de sorte que la mémoire ne sera pas fragmentée en conséquence. Ou, si vous avez l'intention d'allouer un grand nombre d'objets de la même taille, allouez-les à partir du même pool. Ainsi, une portion d'espace libre dans le pool ne peut jamais être plus petite que la taille que vous essayez d'allouer à partir de ce pool.

En général, vous n'avez pas besoin de vous en préoccuper, sauf si votre programme est long et qu'il effectue beaucoup d'allocations et de libérations. C'est lorsque vous avez un mélange d'objets à courte et longue durée de vie que vous êtes le plus à risque. malloc fera de son mieux pour vous aider. En gros, ignorez-le jusqu'à ce que votre programme ait des problèmes d'allocation ou que le système se retrouve inopinément à court de mémoire (attrapez cela lors des tests, par préférence !).

Les bibliothèques standard ne sont pas pires que toute autre chose qui alloue de la mémoire, et les conteneurs standard ont tous une fonction Alloc paramètre de modèle que vous pourriez utiliser pour affiner leur stratégie d'allocation si cela est absolument nécessaire.

Answer 2

Qu'est-ce que la fragmentation de la mémoire ?

On parle de fragmentation de la mémoire lorsque la majeure partie de votre mémoire est allouée dans un grand nombre de blocs non contigus, ou chunks - laissant un bon pourcentage de votre mémoire totale non allouée, mais inutilisable pour la plupart des scénarios typiques. Il en résulte des exceptions de manque de mémoire ou des erreurs d'allocation (par exemple, malloc renvoie null).

La façon la plus simple d'y penser est d'imaginer que vous avez un grand mur vide sur lequel vous devez mettre des photos de tailles différentes on. Chaque tableau occupe une certaine taille et vous ne pouvez évidemment pas le diviser en petits morceaux pour le faire rentrer. Il vous faut un espace vide sur le mur, de la taille de la photo, sinon vous ne pouvez pas l'accrocher. Si vous commencez à accrocher des photos au mur et que vous ne faites pas attention à la façon dont vous les disposez, vous vous retrouverez bientôt avec un mur partiellement recouvert de photos et, même si vous avez des espaces vides, la plupart des nouvelles photos ne rentreront pas car elles sont plus grandes que les espaces disponibles. Vous pouvez toujours accrocher de très petites photos, mais la plupart d'entre elles ne rentreront pas. Vous devrez donc réorganiser (compacter) les photos déjà accrochées au mur pour faire de la place

Maintenant, imaginez que le mur est votre mémoire (tas) et que les images sont des objets C'est la fragmentation de la mémoire..

Comment puis-je savoir si la fragmentation de la mémoire est un problème pour mon application ? Quel type de programme est le plus susceptible d'en souffrir ?

Un signe révélateur de la fragmentation de la mémoire est l'apparition de nombreuses erreurs d'allocation, en particulier lorsque le pourcentage de mémoire utilisée est élevé - mais vous n'avez pas encore utilisé toute la mémoire - donc techniquement, vous devriez avoir beaucoup de place pour les objets que vous essayez d'allouer.

Lorsque la mémoire est fortement fragmentée, les allocations de mémoire sont susceptibles de prendre plus de temps, car l'allocateur de mémoire doit effectuer un travail plus important pour trouver un espace approprié pour le nouvel objet. Si, à son tour, vous avez de nombreuses allocations de mémoire (ce qui est probablement le cas puisque vous vous êtes retrouvé avec la fragmentation de la mémoire), le temps d'allocation peut même entraîner des retards notables.

Quelles sont les bonnes méthodes courantes pour traiter la fragmentation de la mémoire ?

Utiliser un bon algorithme d'allocation de la mémoire. Au lieu d'allouer de la mémoire pour un grand nombre de petits objets, préallouez de la mémoire pour un tableau contigu de ces petits objets. Parfois, le fait de gaspiller un peu de mémoire peut améliorer les performances et vous éviter d'avoir à gérer la fragmentation de la mémoire.

Answer 3

La fragmentation de la mémoire est le même concept que la fragmentation du disque : il s'agit d'un gaspillage d'espace dû au fait que les zones utilisées ne sont pas suffisamment rapprochées les unes des autres.

Supposons, pour un simple exemple de jouet, que vous disposiez de dix octets de mémoire :

 |   |   |   |   |   |   |   |   |   |   |
   0   1   2   3   4   5   6   7   8   9

Maintenant, allouons trois blocs de trois octets, nommés A, B, et C :

 | A | A | A | B | B | B | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Maintenant, désallouez le bloc B :

 | A | A | A |   |   |   | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Maintenant, que se passe-t-il si nous essayons d'allouer un bloc de quatre octets D ? Eh bien, nous avons 4 octets de mémoire libre, mais nous n'avons pas 4 octets de mémoire libre. contiguës octets de mémoire libre, donc nous ne pouvons pas allouer D ! C'est une utilisation inefficace de la mémoire, car nous aurions dû pouvoir stocker D, mais nous n'avons pas pu. Et nous ne pouvons pas déplacer C pour faire de la place, car il est très probable que certaines variables de notre programme pointent vers C, et nous ne pouvons pas trouver et changer automatiquement toutes ces valeurs.

Comment savez-vous que c'est un problème ? Eh bien, le plus grand signe est que la taille de la mémoire virtuelle de votre programme est considérablement plus grande que la quantité de mémoire que vous utilisez réellement. Dans un exemple concret, vous disposeriez de beaucoup plus de dix octets de mémoire, de sorte que D serait alloué à partir de l'octet 9, et que les octets 3 à 5 resteraient inutilisés, à moins que vous n'allouiez ultérieurement quelque chose de trois octets ou moins.

Dans cet exemple, 3 octets ne représentent pas un grand gaspillage, mais considérons un cas plus pathologique où deux allocations de quelques octets sont, par exemple, séparées de dix mégaoctets en mémoire, et où vous devez allouer un bloc de taille 10 mégaoctets + 1 octet. Pour ce faire, vous devez demander au système d'exploitation plus de dix mégaoctets de mémoire virtuelle supplémentaire, alors que vous n'êtes qu'à un octet près d'avoir déjà assez d'espace.

Comment l'éviter ? Les pires cas tendent à se produire lorsque vous créez et détruisez fréquemment de petits objets, car cela tend à produire un effet "fromage suisse" avec de nombreux petits objets séparés par de nombreux petits trous, rendant impossible l'allocation d'objets plus grands dans ces trous. Lorsque vous savez que vous allez faire cela, une stratégie efficace consiste à pré-allouer un grand bloc de mémoire comme pool pour vos petits objets, puis à gérer manuellement la création des petits objets dans ce bloc, plutôt que de laisser l'allocateur par défaut s'en charger.

En général, moins vous faites d'allocations, moins la mémoire risque d'être fragmentée. Cependant, la STL gère ce problème de manière assez efficace. Si vous avez une chaîne de caractères qui utilise la totalité de son allocation actuelle et que vous lui ajoutez un caractère, elle n'est pas simplement réallouée à sa longueur actuelle plus un. doubles sa longueur. Il s'agit d'une variante de la stratégie du "pool pour les petites allocations fréquentes". La chaîne s'empare d'une grande partie de la mémoire afin de pouvoir gérer efficacement les petites augmentations de taille répétées sans avoir à effectuer de petites réallocations répétées. En fait, tous les conteneurs STL font ce genre de choses, donc en général vous n'aurez pas à vous soucier de la fragmentation causée par les conteneurs STL à réallocation automatique.

Bien sûr, les conteneurs STL ne mettent pas la mémoire en commun. entre Par conséquent, si vous créez de nombreux petits conteneurs (plutôt que quelques conteneurs qui sont fréquemment redimensionnés), vous devrez peut-être vous préoccuper de la prévention de la fragmentation de la même manière que vous le feriez pour tout petit objet fréquemment créé, STL ou non.

Answer 4

• Qu'est-ce que la fragmentation de la mémoire ?

La fragmentation de la mémoire est le problème de la mémoire qui devient inutilisable alors qu'elle est théoriquement disponible. Il existe deux types de fragmentation : fragmentation interne est la mémoire qui est allouée mais qui ne peut pas être utilisée (par exemple, lorsque la mémoire est allouée par tranches de 8 octets mais que le programme effectue des allocations uniques répétées alors qu'il n'a besoin que de 4 octets). fragmentation externe est le problème de la mémoire libre qui se divise en de nombreux petits morceaux de sorte que les demandes d'allocation importantes ne peuvent être satisfaites bien que la mémoire libre globale soit suffisante.

• Comment puis-je savoir si la fragmentation de la mémoire est un problème pour mon application ? Quel type de programme est le plus susceptible d'en souffrir ?

La fragmentation de la mémoire est un problème si votre programme utilise beaucoup plus de mémoire système que ce que ses données payantes réelles requièrent (et que vous avez exclu les fuites de mémoire).

• Quelles sont les bonnes méthodes courantes pour traiter la fragmentation de la mémoire ?

Utilisez un bon allocateur de mémoire. IIRC, ceux qui utilisent une stratégie de "meilleure adaptation" sont généralement bien meilleurs pour éviter la fragmentation, même s'ils sont un peu plus lents. Cependant, il a également été démontré que pour toute stratégie d'allocation, il existe des pires cas pathologiques. Heureusement, les modèles d'allocation typiques de la plupart des applications sont en fait relativement bénins à gérer pour les allocateurs. Il existe un grand nombre d'articles sur le sujet si vous êtes intéressé par les détails :

• Paul R. Wilson, Mark S. Johnstone, Michael Neely et David Boles. Dynamic Storage Allocation : A Survey and Critical Review. In Proceedings of the 1995 International Workshop on Memory Management, Springer Verlag LNCS, 1995.
• Mark S.Johnstone, Paul R. Wilson. The Memory Fragmentation Problem : Solved ? Dans ACM SIG-PLAN Notices, volume 34 n° 3, pages 26-36, 1999.
• M.R. Garey, R.L. Graham et J.D. Ullman. Worst-Case analysis of memory allocation algorithms. Dans Fourth Annual ACM Symposium on the Theory of Computing, 1972.

Answer 5

Mise à jour :
Google TCMalloc : Thread-Caching Malloc
Il a été constaté que il est assez bon pour gérer la fragmentation dans un processus de longue haleine.

---

J'ai développé une application serveur qui avait des problèmes de fragmentation de la mémoire sur HP-UX 11.23/11.31 ia64.

Ça ressemblait à ça. Il y avait un processus qui faisait des allocations et des désallocations de mémoire et qui tournait pendant des jours. Et même s'il n'y avait aucune fuite de mémoire, la consommation de mémoire du processus ne cessait d'augmenter.

A propos de mon expérience. Sous HP-UX, il est très facile de trouver une fragmentation de la mémoire en utilisant HP-UX gdb. Vous définissez un point d'arrêt et lorsque vous l'atteignez, vous exécutez cette commande : info heap et voir toutes les allocations de mémoire pour le processus et la taille totale du tas. Puis vous continuez votre programme et quelque temps plus tard, vous atteignez à nouveau le point d'arrêt. Vous faites à nouveau info heap . Si la taille totale du tas est plus grande mais que le nombre et la taille des allocations séparées sont les mêmes, il est probable que vous ayez des problèmes d'allocation de mémoire. Si nécessaire, effectuez cette vérification plusieurs fois.

Ma façon d'améliorer la situation était la suivante. Après avoir fait quelques analyses avec HP-UX gdb, j'ai vu que les problèmes de mémoire étaient causés par le fait que j'utilisais std::vector pour stocker certains types d'informations à partir d'une base de données. std::vector exige que ses données soient conservées en un seul bloc. J'avais quelques conteneurs basés sur std::vector . Ces conteneurs ont été régulièrement recréés. Il arrivait souvent que de nouveaux enregistrements soient ajoutés à la base de données et que les conteneurs soient ensuite recréés. Et comme les conteneurs recréés étaient plus grands, ils ne tenaient pas dans les blocs de mémoire libre disponibles et le runtime demandait un nouveau bloc plus grand au système d'exploitation. En conséquence, même s'il n'y avait pas de fuite de mémoire, la consommation de mémoire du processus augmentait. J'ai amélioré la situation en changeant les conteneurs. Au lieu de std::vector J'ai commencé à utiliser std::deque qui a une manière différente d'allouer de la mémoire pour les données.

Je sais que l'une des façons d'éviter la fragmentation de la mémoire sous HP-UX est d'utiliser soit le Small Block Allocator, soit MallocNextGen. Sous RedHat Linux, l'allocateur par défaut semble gérer assez bien l'allocation d'un grand nombre de petits blocs. Sous Windows, il existe Low-fragmentation Heap et permet de résoudre le problème du grand nombre de petites allocations.

Je crois savoir que dans une application à forte composante STL, il faut d'abord identifier les problèmes. Les allocateurs de mémoire (comme dans la libc) gèrent en fait le problème d'un grand nombre de petites allocations, ce qui est typique pour les applications STL. std::string (par exemple, dans mon application serveur, il y a beaucoup de chaînes STL mais comme je le vois en exécutant info heap ils ne posent aucun problème). Mon impression est que vous devez éviter les allocations fréquentes et importantes. Malheureusement, il y a des situations où vous ne pouvez pas les éviter et où vous devez modifier votre code. Comme je l'ai dit, dans mon cas, j'ai amélioré la situation lorsque j'ai adopté le code suivant std::deque . Si vous identifiez votre fragment de mémoire, il sera peut-être possible d'en parler plus précisément.