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

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

fragmentation de la mémoire est quand la plupart de votre mémoire est attribuée dans un grand nombre de blocs non contigus, ou morceaux-laissant un bon pourcentage de votre mémoire totale non attribué, mais inutilisable pour la plupart des scénarios typiques. Il en résulte des exceptions de mémoire, ou des erreurs d'allocation (c'est-à-dire que malloc retourne null).

la façon la plus facile de penser c'est pour imaginer que vous avez un grand mur vide que vous devez mettre des images de tailles variables sur. Chaque image prend une certaine taille et vous ne pouvez évidemment pas le diviser en plus petits morceaux pour le rendre apte. Vous avez besoin d'une place vide sur le mur, la taille de l'image, ou bien vous ne pouvez pas l'afficher. Maintenant, si vous commencez à accrocher des photos sur le mur et vous n'êtes pas prudent sur la façon dont vous les arranger, vous finirez bientôt avec un mur qui est partiellement couvert de photos et même bien que vous puissiez avoir des taches vides la plupart des nouvelles photos ne seront pas adaptés parce qu'ils sont plus grands que les taches disponibles. Vous pouvez toujours accrocher de très petites photos, mais la plupart d'entre elles ne rentrent pas. Vous devrez donc réorganiser (compact) ceux qui sont déjà sur le mur pour faire de la place pour plus..

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

Comment savoir si la fragmentation de la mémoire est un problème pour mon application? Quel genre de programme est le plus susceptible de souffrir?

un signe révélateur que vous pouvez être confrontés à la fragmentation de la mémoire est si vous obtenez beaucoup d'erreurs d'allocation, en particulier lorsque le pourcentage de mémoire utilisée est élevé - mais pas 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.

quand la mémoire est fortement fragmentée, les allocations de mémoire sera probablement prendre plus de temps parce que l'allocateur mémoire doit faire plus de travail pour trouver un espace approprié pour le nouvel objet. Si à votre tour vous avez beaucoup d'allocations de mémoire (ce que vous faites probablement puisque vous avez fini avec la fragmentation de la mémoire) le temps d'allocation peut même causer des retards notables.

quelles sont les bonnes façons courantes de gérer la fragmentation de la mémoire?

utilisez un bon algorithme pour allouer la mémoire. Au lieu d'allouer de la mémoire pour beaucoup de petits objets, pré-allouer de la mémoire pour un tableau contigu de ces petits objets. Parfois être un peu gaspilleur lors de l'attribution de la mémoire peut aller le long pour la performance et peut vous épargner la peine d'avoir à faire face à la fragmentation de la mémoire.

fragmentation de la mémoire est le même concept que la fragmentation du disque: il se réfère à l'espace gaspillé parce que les zones utilisées ne sont pas assez emballés ensemble.

supposons pour un exemple de jouet simple que vous avez dix octets de mémoire:

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

attribuons maintenant trois blocs de trois octets, nommez A, B, et C:

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

désalloquer le bloc B:

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

maintenant ce qui se passe si nous essayons d'attribuer un bloc de quatre octets d? Eh bien, nous avons quatre octets de mémoire libre, mais nous n'avons pas quatre contigus octets de mémoire libre, donc nous ne pouvons pas allouer D! C'est l'utilisation inefficace de la mémoire, car nous aurions été en mesure de magasin de D, mais nous n'avons pas pu. Et nous ne pouvons pas déplacer C pour faire de la place, parce que très probablement certaines variables dans notre programme pointent vers C, et nous ne pouvons pas automatiquement trouver et changer toutes ces valeurs.

Comment faire vous savez que c'est un problème? Eh bien, le plus grand signe est que la taille de 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 du monde réel, vous auriez beaucoup plus de dix octets de mémoire, donc D serait simplement attribué à partir d'un octet 9, et les octets 3-5 resteraient inutilisés à moins que vous n'allouiez plus tard quelque chose de trois octets de long ou plus petit.

Dans cet exemple, 3 octets n'est pas un tas de déchets, mais imaginez un plus cas pathologique où deux attributions de quelques octets sont, par exemple, séparées de dix mégaoctets en mémoire, et vous devez allouer un bloc de taille 10 mégaoctets + 1 octet. Vous devez aller demander au système d'exploitation pour plus de dix mégaoctets plus de mémoire virtuelle pour le faire, même si vous êtes juste un octet timide d'avoir assez d'espace déjà.

comment l'empêcher? Les cas les plus graves ont tendance à se produire lorsque vous créez et détruisez fréquemment de petits objets, car cela tend à produire une "Suisse" cheese " effet avec de nombreux petits objets séparés par de nombreux petits trous, ce qui rend impossible d'allouer des objets plus grands dans ces trous. Quand vous savez que vous allez faire cela, une stratégie efficace est de pré-allouer un grand bloc de mémoire comme un pool pour vos petits objets, et ensuite gérer manuellement la création des petits objets à l'intérieur de ce bloc, plutôt que de laisser l'allocateur par défaut s'en charger.

en général, moins il y a d'affectations, moins il y a de chances la mémoire est d'être fragmenté. Toutefois, le STL s'en occupe assez efficacement. Si vous avez une chaîne qui utilise la totalité de son allocation actuelle et que vous lui ajoutez un caractère, il ne se contente pas de réattribuer à sa longueur actuelle plus un, il double sa longueur. Il s'agit d'une variation par rapport à la stratégie de "mise en commun pour des affectations fréquentes de faible envergure". La chaîne saisit un grand morceau de mémoire pour qu'il puisse traiter efficacement avec de petites augmentations répétées de la taille sans procéder à de petites réaffectations répétées. Tous les conteneurs STL en fait font ce genre de chose, donc généralement vous n'aurez pas à vous soucier trop de la fragmentation causée par automatiquement réattribuer les conteneurs STL.

bien que, bien sûr, les conteneurs STL ne mettent pas en commun la mémoire entre l'un l'autre, donc si vous allez créer de nombreux petits conteneurs (plutôt que quelques conteneurs qui sont redimensionnés fréquemment) , vous pourriez avoir à vous soucier de prévenir la fragmentation de la même manière que vous le feriez pour n'importe quels petits objets fréquemment créés, STL ou non.

• 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 même si elle est théoriquement disponible. Il existe deux types de fragmentation: fragmentation interne est une mémoire qui est attribuée mais ne peut pas être utilisée (par exemple, lorsque la mémoire est attribuée en 8 octets, mais que le programme fait plusieurs fois des allications simples alors qu'il n'a besoin que de 4 octets). la fragmentation externe est le problème de la mémoire libre de devenir divisée en de nombreux petits morceaux de sorte que les grandes demandes d'allocation ne peut pas être respecté, même si il est assez globale de la mémoire libre.

• Comment savoir si la fragmentation de la mémoire est un problème pour mon application? Quel genre de programme est le plus susceptible de souffrir?

fragmentation de la mémoire est un problème si votre programme utilise beaucoup plus de mémoire système que ses données paylod actuelles nécessiteraient (et vous avez exclu les fuites de mémoire).

• quelles sont les bonnes façons courantes de gérer la fragmentation de la mémoire?

utilisez un bon allocateur mémoire. IIRC, ceux qui utilisent une stratégie de" meilleur ajustement " sont généralement beaucoup mieux pour éviter la fragmentation, si un peu plus lent. Toutefois, il a également été démontré que, pour toute stratégie de répartition, sont les pires cas pathologiques. Heureusement, les patrons d'allocation typiques de la plupart des applications sont en fait relativement bénins pour les allocateurs à manipuler. Il y a un tas de papiers là-bas si vous êtes intéressé par les détails:

• Paul R. Wilson, Mark S. Johnstone, Michael Neely and David Boles. Dynamique d'Allocation de Stockage: Une Enquête et de l'Examen Critique. Dans les actes de l'année 1995 Atelier International sur la gestion de la mémoire, Springer Verlag LNC, 1995
• Mark S. Johnstone, Paul R. Wilson. Le Problème De Fragmentation De La Mémoire: Résolu? In ACM SIG-PLAN Notices, volume 34 No. 3, pages 26-36, 1999
• M. R. Garey, R. L. Graham et J. D. Ullman. Analyse du pire scénario de l'allocation de la mémoire des algorithmes. Dans le Quatrième rapport Annuel de l'ACM Symposium sur la Théorie de l'Informatique, de 1972

Update:

Google TCMalloc: Fil De Cache Malloc

Il a été constaté que il est assez bon à la manipulation de fragmentation dans un processus de longue durée.

j'ai développé une application serveur qui avait des problèmes avec la 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 de mémoire et des désallocations et a fonctionné pendant des jours. Et même s'il n'y avait pas de fuites de mémoire, la consommation de mémoire du processus ne cessait d'augmenter.

à propos de mon expérience. Sur HP-UX, il est très facile de trouver la fragmentation de la mémoire en utilisant HP-UX gdb. Vous définissez un point de rupture et quand vous le frappez vous exécutez cette commande: info heap et voir toutes les allocations de mémoire pour le processus et la taille totale de tas. Puis vous continuez votre programme et puis quelque temps plus tard votre nouveau frapper le point de rupture. Tu refais info heap . Si la taille totale du tas est plus grande mais le nombre et la taille des allocations séparées sont les mêmes, alors il est probable que vous avez des problèmes d'allocation de mémoire. Si nécessaire, effectuer cette vérification quelques fois.

Ma façon d'améliorer la situation était présent. 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'ai utilisé std::vector pour stocker certains types d'informations à partir d'une base de données. std::vector exige que ses données doivent être conservées dans un seul bloc. J'avais quelques conteneurs basés sur std::vector . Ces conteneurs étaient régulièrement recréés. Il y avait souvent des situations où de nouveaux enregistrements étaient ajoutés à la base de données et après que les conteneurs ont été recréés. Et comme les containers recréés étaient plus grands, ils ne s'adaptaient pas aux blocs de mémoire libre disponibles et le runtime demandait un nouveau plus grand - bloc de l'OS. En conséquence, même s'il n'y avait pas de fuites de mémoire, la consommation de mémoire du processus a augmenté. J'ai amélioré la situation en changeant les conteneurs. Au lieu de std::vector j'ai commencé à utiliser std::deque qui a une façon différente d'allouer la mémoire pour les données.

je sais que l'un des moyens d'éviter la fragmentation de la mémoire sur HP-UX est d'utiliser soit un petit allocateur de bloc, soit MallocNextGen. Sur RedHat Linux l'allocator par défaut semble gérer pretty bien allouer de beaucoup de petits blocs. Sur Windows il y a Low-fragmentation Heap et il adresse le problème du grand nombre de petites allocations.

ma compréhension est que dans une application STL-heavy vous devez d'abord identifier les problèmes. Les allocateurs de mémoire (comme dans libc) gèrent en fait le problème de beaucoup de petites attributions, ce qui est typique pour std::string (par exemple dans mon application serveur il y a beaucoup de chaînes STL mais comme je le vois à partir de l'exécution info heap ils ne sont pas la cause de tous les problèmes). J'ai l'impression que vous devez éviter les affectations fréquentes et importantes. Malheureusement, il y a des situations où vous ne pouvez pas les éviter et devez changer votre code. Comme je l'ai dit dans mon cas, j'ai amélioré la situation en passant à std::deque . Si vous identifiez votre mémoire fragmention il pourrait être possible d'en parler plus précisément.

la fragmentation de la mémoire est le plus susceptible de se produire lorsque vous attribuez et deallocate beaucoup d'objets de tailles différentes. Supposons que vous ayez la disposition suivante en mémoire:

obj1 (10kb) | obj2(20kb) | obj3(5kb) | unused space (100kb)

maintenant, quand obj2 est libéré, vous avez 120kb de mémoire inutilisée, mais vous ne pouvez pas allouer un bloc complet de 120kb, parce que la mémoire est fragmentée.

les techniques les plus courantes pour éviter cet effet sont les tampons annulaires . et objet pools . Dans le contexte de la STL, des méthodes comme std::vector::reserve() peuvent aider.

une réponse très détaillée sur la fragmentation de la mémoire peut être trouvée ici.

http://library.softwareverify.com/memory-fragmentation-your-worst-nightmare /

C'est le point culminant de 11 années de réponses sur la fragmentation de la mémoire que j'ai fourni aux gens qui me posent des questions sur la fragmentation de la mémoire à softwareverify.com

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

lorsque votre application utilise de la mémoire dynamique, elle alloue et libère des morceaux de mémoire. Au début, l'ensemble de l'espace mémoire de votre application est un bloc contigu de mémoire libre. Cependant, lorsque vous attribuez et libérez des blocs de taille différente, la mémoire commence à obtenir fragmenté , i.e. au lieu d'un grand bloc libre contigu et un certain nombre de blocs alloués contigus, il y aura un alloués et des blocs libres mixtes. Depuis les blocs libres ont une taille limitée, il est difficile de les réutiliser. Par exemple: vous pouvez avoir 1000 octets de mémoire libre, mais ne pouvez pas allouer de mémoire pour un bloc de 100 octets, parce que tous les blocs libres sont au plus 50 octets de long.

une autre source inévitable, mais moins problématique de fragmentation est que dans la plupart des architectures, les adresses mémoire doivent être alignées à 2, 4, 8 etc. les limites des octets (c.-à-d. les adresses doivent être des multiples de 2, 4, 8, etc. Cela signifie que même si vous avez par exemple une structure contenant 3 char champs, votre structure peut avoir une taille de 12 au lieu de 3, en raison du fait que chaque champ est aligné à une limite de 4 octets.

Comment savoir si la fragmentation de la mémoire est un problème pour mon application? Quel genre de programme est le plus susceptible de souffrir?

la réponse évidente est que vous obtenez une exception de mémoire.

apparemment, il n'y a pas de bon moyen portable pour détecter la fragmentation de la mémoire dans les applications C++. Voir cette réponse pour plus de détails.

quelles sont les bonnes façons courantes de traiter la fragmentation de la mémoire?

c'est difficile en C++, puisque vous utilisez des adresses mémoire directes dans les pointeurs, et vous n'avez aucun contrôle sur qui renvoie une adresse mémoire spécifique. Le réarrangement de l'enveloppe les blocs mémoire (comme le Java garbage collector) ne sont pas une option.

un allocateur personnalisé peut aider en gérant l'allocation de petits objets dans un plus grand morceau de mémoire, et en réutilisant les fentes libres dans ce morceau.

C'est une version Super-simplifiée pour les nuls.

lorsque les objets sont créés en mémoire, ils sont ajoutés à la fin de la partie utilisée en mémoire.

si un objet qui n'est pas à la fin de la partie utilisée de la mémoire est supprimé, ce qui signifie que cet objet était entre deux autres objets, il créera un"trou".

c'est ce qu'on appelle la fragmentation.

quand vous voulez ajouter un élément sur le tas ce qui se passe est que l'ordinateur doit faire une recherche d'espace pour correspondre à cet élément. C'est pourquoi les répartitions dynamiques, lorsqu'elles ne sont pas faites sur un pool de mémoire ou avec un allocateur groupé, peuvent "ralentir" les choses. Pour une application STL lourde si vous faites multi-threading, il y a la version Hoard allocator ou la version TBB Intel .

Maintenant, quand la mémoire est fragmentée deux choses peuvent se produire:

1. Il faudra plus de recherches pour trouver un bon espace de bâton "gros" objets. C'est-à-dire que, avec de nombreux petits objets éparpillés sur la recherche d'un joli morceau contiguë de mémoire pourrait être difficile dans certaines conditions (ceux-ci sont extrêmes.)
2. la mémoire n'est pas une entité facile à lire. Les transformateurs sont limités à ce qu'ils peuvent garder et où. Ils font cela en échangeant des pages si un élément dont ils ont besoin est un endroit mais les adresses actuelles sont une autre. Si vous devez constamment échanger des pages, le traitement peut ralentir (encore une fois, les scénarios extrêmes où cela affecte la performance.) Voir cette publication sur mémoire virtuelle .

la fragmentation de la mémoire se produit parce que des blocs de mémoire de différentes tailles sont demandés. Considérons un tampon de 100 octets. Vous demandez deux caractères, puis un entier. Maintenant vous libérez les deux caractères, puis vous demandez un nouvel entier - mais cet entier ne peut pas tenir dans l'espace des deux caractères. Cette mémoire ne peut pas être réutilisée parce qu'elle ne se trouve pas dans un bloc contigu assez grand pour être réattribué. En plus de cela, vous avez invoqué beaucoup d'allocator overhead pour vos chars.

essentiellement, la mémoire est en blocs d'une certaine taille sur la plupart des systèmes. Une fois que vous avez divisé ces blocs, ils ne peuvent pas être rejoints jusqu'à ce que le bloc entier soit libéré. Cela peut conduire à des blocs entiers en cours d'utilisation alors qu'en réalité, seule une petite partie du bloc est en cours d'utilisation.

le principal moyen de réduire la fragmentation des tas consiste à effectuer des répartitions plus importantes et moins fréquentes. Dans l'extrême, vous pouvez utiliser un tas géré qui est capable de déplacer des objets, au moins, à l'intérieur de votre propre code. Cela élimine complètement le problème - du point de vue de la mémoire, en tout cas. Il est évident que déplacer des objets a un coût. En réalité, vous avez seulement vraiment un problème si vous répartissez de très petites quantités sur le tas souvent. Utiliser des conteneurs contigus (vecteur, chaîne, etc) et allouer sur la pile autant que possible (toujours une bonne idée pour la performance) est le meilleur moyen de la réduire. Cela augmente également la cohérence du cache, ce qui accélère le fonctionnement de votre application.

ce que vous devriez rappelez-vous est que sur un système de bureau 32bit x86, vous avez un 2Go entier de mémoire, qui est divisé en 4KB "pages" (assez sûr que la taille de la page est la même sur tous les systèmes x86). Vous devrez invoquer une certaine fragmentation omgwtfbbq pour avoir un problème. La Fragmentation est vraiment un problème du passé, car les tas modernes sont excessivement grands pour la grande majorité des applications, et il y a une prévalence de systèmes qui sont capables de le supporter, tels que les tas gérés.