qué que interna informatica fragmentación fragmentacion caracteristicas archivos c++ memory heap fragmentation

c++ - que - ¿Qué es la fragmentación de la memoria?



que es la fragmentacion en android (11)

He escuchado el término "fragmentación de la memoria" utilizado algunas veces en el contexto de la asignación de memoria dinámica C ++. He encontrado algunas preguntas sobre cómo lidiar con la fragmentación de la memoria, pero no puedo encontrar una pregunta directa que trate con ella. Asi que:

  • ¿Qué es la fragmentación de la memoria?
  • ¿Cómo puedo saber si la fragmentación de la memoria es un problema para mi aplicación? ¿Qué tipo de programa es más probable que sufra?
  • ¿Cuáles son las buenas formas comunes de lidiar con la fragmentación de la memoria?

También:

  • He escuchado que el uso de asignaciones dinámicas puede aumentar la fragmentación de la memoria. ¿Es esto cierto? En el contexto de C ++, entiendo que todos los contenedores estándar (std :: string, std :: vector, etc.) usan asignación de memoria dinámica. Si se utilizan en un programa (especialmente std :: string), ¿es más probable que la fragmentación de la memoria sea un problema?
  • ¿Cómo se puede tratar la fragmentación de memoria en una aplicación STL-heavy?

¿Qué es la fragmentación de la memoria?

Cuando su aplicación utiliza memoria dinámica, asigna y libera trozos de memoria. Al principio, todo el espacio de la memoria de su aplicación es un bloque contiguo de memoria libre. Sin embargo, cuando asigna y libera bloques de diferente tamaño, la memoria comienza a fragmentarse , es decir, en lugar de un gran bloque libre contiguo y una cantidad de bloques asignados contiguos, habrá bloques asignados y libres mezclados. Como los bloques libres tienen un tamaño limitado, es difícil reutilizarlos. Por ejemplo, puede tener 1000 bytes de memoria libre, pero no puede asignar memoria para un bloque de 100 bytes, porque todos los bloques libres tienen como máximo 50 bytes de longitud.

Otra fuente inevitable, pero menos problemática de fragmentación es que en la mayoría de las arquitecturas, las direcciones de memoria deben estar alineadas con 2, 4, 8, etc. límites de bytes (es decir, las direcciones deben ser múltiplos de 2, 4, 8, etc.) Esto significa que incluso si tiene, por ejemplo, una estructura que contiene 3 campos char , su estructura puede tener un tamaño de 12 en lugar de 3, debido al hecho de que cada campo está alineado con un límite de 4 bytes.

¿Cómo puedo saber si la fragmentación de la memoria es un problema para mi aplicación? ¿Qué tipo de programa es más probable que sufra?

La respuesta obvia es que obtienes una excepción de falta de memoria.

Aparentemente, no existe una buena forma portátil de detectar la fragmentación de la memoria en las aplicaciones de C ++. Vea esta respuesta para más detalles.

¿Cuáles son las buenas formas comunes de lidiar con la fragmentación de la memoria?

Es difícil en C ++, ya que utiliza direcciones de memoria directa en punteros y no tiene control sobre quién hace referencia a una dirección de memoria específica. Así que reorganizar los bloques de memoria asignados (la forma en que lo hace el recolector de basura de Java) no es una opción.

Un asignador personalizado puede ayudar administrando la asignación de objetos pequeños en una gran porción de memoria y reutilizando los espacios libres dentro de ese fragmento.

¿Qué es la fragmentación de la memoria?

La fragmentación de la memoria se produce cuando la mayor parte de la memoria se asigna en una gran cantidad de bloques no contiguos, o fragmentos, dejando un buen porcentaje de la memoria total sin asignar, pero inutilizable para la mayoría de los escenarios típicos. Esto da como resultado excepciones de memoria insuficiente o errores de asignación (es decir, malloc devuelve nulo).

La manera más fácil de pensar sobre esto es imaginar que tienes una gran pared vacía en la que necesitas colocar imágenes de distintos tamaños . Cada imagen ocupa un cierto tamaño y, obviamente, no se puede dividir en trozos más pequeños para que quepa. Necesitas un lugar vacío en la pared, el tamaño de la imagen, o bien no puedes subirlo. Ahora, si comienzas a colgar imágenes en la pared y no tienes cuidado con cómo las arreglas, pronto terminarás con una pared que está parcialmente cubierta con imágenes y, aunque tengas espacios vacíos, la mayoría de las imágenes nuevas no cabrán. porque son más grandes que los lugares disponibles. Todavía puede colgar imágenes realmente pequeñas, pero la mayoría no se ajustarán. Así que tendrás que reorganizar (compactar) los que ya están en la pared para dejar espacio para más ...

Ahora, imagina que la pared es tu memoria (montón) y las imágenes son objetos ... Esa es la fragmentación de la memoria ...

¿Cómo puedo saber si la fragmentación de la memoria es un problema para mi aplicación? ¿Qué tipo de programa es más probable que sufra?

Una señal reveladora de que puede estar lidiando con la fragmentación de la memoria es si obtiene muchos errores de asignación, especialmente cuando el porcentaje de memoria usada es alto, pero no ha agotado toda la memoria, por lo que técnicamente debe tener suficiente espacio para los objetos que intentas asignar

Cuando la memoria está muy fragmentada, es probable que las asignaciones de memoria tarden más porque el asignador de memoria tiene que trabajar más para encontrar un espacio adecuado para el nuevo objeto. Si a su vez tiene muchas asignaciones de memoria (lo cual probablemente ocurra desde que terminó con la fragmentación de la memoria), el tiempo de asignación puede incluso causar demoras notables.

¿Cuáles son las buenas formas comunes de lidiar con la fragmentación de la memoria?

Use un buen algoritmo para asignar memoria. En lugar de asignar memoria para muchos objetos pequeños, preasignar memoria para una matriz contigua de esos objetos más pequeños. A veces, es un poco derrochador cuando asignar memoria puede mejorar el rendimiento y puede ahorrarte el problema de tener que lidiar con la fragmentación de la memoria.

  • ¿Qué es la fragmentación de la memoria?

La fragmentación de la memoria es el problema de la memoria inutilizable a pesar de que está teóricamente disponible. Hay dos tipos de fragmentación: la fragmentación interna es la memoria que se asigna pero no se puede utilizar (por ejemplo, cuando la memoria se asigna en fragmentos de 8 bytes, pero el programa realiza repeticiones únicas cuando solo necesita 4 bytes). La fragmentación externa es el problema de que la memoria libre se divida en muchos fragmentos pequeños, por lo que las solicitudes de asignación grandes no se pueden cumplir aunque haya suficiente memoria libre en general.

  • ¿Cómo puedo saber si la fragmentación de la memoria es un problema para mi aplicación? ¿Qué tipo de programa es más probable que sufra?

la fragmentación de la memoria es un problema si su programa usa mucha más memoria de sistema de la que requerirían los datos reales de paylod (y ha descartado fugas de memoria).

  • ¿Cuáles son las buenas formas comunes de lidiar con la fragmentación de la memoria?

Use un buen asignador de memoria. IIRC, aquellos que usan una estrategia de "mejor ajuste" generalmente son mucho mejores para evitar la fragmentación, aunque un poco más lento. Sin embargo, también se ha demostrado que para cualquier estrategia de asignación, existen los peores casos patológicos. Afortunadamente, los patrones de asignación típicos de la mayoría de las aplicaciones son en realidad relativamente benignos para los asignadores. Hay muchos papeles disponibles si le interesan los detalles:

  • Paul R. Wilson, Mark S. Johnstone, Michael Neely y David Boles. Asignación dinámica de almacenamiento: una encuesta y revisión crítica. En Actas del Taller Internacional de 1995 sobre Gestión de la Memoria, Springer Verlag LNCS, 1995
  • Mark S. Johnstone, Paul R. Wilson. El problema de la fragmentación de la memoria: ¿Resuelto? En Avisos ACM SIG-PLAN, volumen 34, n.º 3, páginas 26-36, 1999
  • MR Garey, RL Graham y JD Ullman. Análisis del peor caso de algoritmos de asignación de memoria. En el cuarto Simposio Anual ACM sobre la Teoría de la Computación, 1972

Cuando desea agregar un elemento en el montón, lo que sucede es que la computadora tiene que hacer una búsqueda de espacio para acomodar ese elemento. Es por eso que las asignaciones dinámicas cuando no se realizan en un grupo de memoria o con un asignador agrupado pueden "ralentizar" las cosas. Para una aplicación pesada de STL, si está haciendo multi-threading existe el asignador Hoard o la versión TBB Intel .

Ahora, cuando la memoria está fragmentada, pueden ocurrir dos cosas:

  1. Tendrán que haber más búsquedas para encontrar un buen espacio para pegar objetos "grandes". Es decir, con muchos objetos pequeños diseminados para encontrar un buen pedazo de memoria contundente, bajo ciertas condiciones podría ser difícil (estos son extremos).
  2. La memoria no es una entidad fácil de leer. Los procesadores están limitados a cuánto pueden contener y dónde. Lo hacen intercambiando páginas si un elemento que necesitan es un lugar, pero las direcciones actuales son otro. Si constantemente tiene que intercambiar páginas, el procesamiento puede ralentizarse (una vez más, situaciones extremas donde esto afecta el rendimiento). Consulte esta publicación en la memoria virtual .

Esta es una versión súper simplificada para dummies.

A medida que los objetos se crean en la memoria, se agregan al final de la porción utilizada en la memoria.

Si se elimina un objeto que no está al final de la porción de memoria utilizada, lo que significa que este objeto estaba entre otros 2 objetos, creará un "agujero".

Esto es lo que se llama fragmentación.

La fragmentación de la memoria es el mismo concepto que la fragmentación del disco: se refiere al desperdicio de espacio porque las áreas en uso no están suficientemente juntas.

Supongamos para un ejemplo de juguete simple que tiene diez bytes de memoria:

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

Ahora asignemos tres bloques de tres bytes, nombre A, B y C:

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

Ahora desasignar el bloque B:

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

¿Qué ocurre si tratamos de asignar un bloque de cuatro bytes D? Bueno, tenemos cuatro bytes de memoria libre, pero no tenemos cuatro bytes contiguos de memoria libre, por lo que no podemos asignar D! Este es un uso ineficiente de la memoria, porque deberíamos haber podido almacenar D, pero no pudimos. Y no podemos mover C para dejar espacio, porque muy probablemente algunas variables en nuestro programa apuntan a C, y no podemos encontrar y cambiar automáticamente todos estos valores.

¿Cómo sabes que es un problema? Bueno, la señal más importante es que el tamaño de la memoria virtual de su programa es considerablemente mayor que la cantidad de memoria que está usando realmente. En un ejemplo del mundo real, tendría muchos más de diez bytes de memoria, por lo que D se asignaría comenzando con un byte 9 y los bytes 3-5 permanecerían sin usar a menos que luego asignara algo de tres bytes de longitud o menos.

En este ejemplo, 3 bytes no es mucho para perder, pero considere un caso más patológico donde dos asignaciones de un par de bytes son, por ejemplo, diez megabytes separados en memoria, y necesita asignar un bloque de 10 megabytes de tamaño + 1 byte Tienes que pedirle al sistema operativo más de diez megabytes más de memoria virtual para hacer eso, aunque estés a un paso de tener suficiente espacio.

¿Cómo lo previenen? Los peores casos tienden a surgir cuando crea y destruye objetos pequeños con frecuencia, ya que esto tiende a producir un efecto de "queso suizo" con muchos objetos pequeños separados por muchos agujeros pequeños, por lo que es imposible asignar objetos más grandes en esos agujeros. Cuando sepa que va a hacer esto, una estrategia efectiva es preasignar un gran bloque de memoria como grupo para sus objetos pequeños, y luego administrar manualmente la creación de los objetos pequeños dentro de ese bloque, en lugar de dejarlo el asignador predeterminado lo maneja.

En general, cuantas menos asignaciones hagas, menos probable es que la memoria se fragmente. Sin embargo, STL trata esto de manera bastante efectiva. Si tiene una cadena que está utilizando la totalidad de su asignación actual y le agrega un carácter, no se reasigna a su longitud actual más uno, sino que duplica su longitud. Esta es una variación de la estrategia del "grupo para pequeñas asignaciones frecuentes". La cuerda está agarrando un gran trozo de memoria para que pueda manejar eficientemente pequeños aumentos de tamaño repetidos sin realizar reasignaciones repetidas y pequeñas. De hecho, todos los contenedores STL hacen este tipo de cosas, por lo que, en general, no tendrá que preocuparse demasiado por la fragmentación causada por la reasignación automática de contenedores STL.

Aunque, por supuesto, los contenedores STL no agrupan la memoria entre ellos, por lo que si va a crear muchos contenedores pequeños (en lugar de unos pocos contenedores que cambian de tamaño con frecuencia) puede que tenga que preocuparse por evitar la fragmentación de la misma manera que sería para cualquier objeto pequeño creado con frecuencia, STL o no.

La fragmentación de la memoria es más probable que ocurra cuando asigna y desasigna muchos objetos de diferentes tamaños. Supongamos que tiene el siguiente diseño en la memoria:

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

Ahora, cuando se lanza obj2 , tiene 120kb de memoria no utilizada, pero no puede asignar un bloque completo de 120kb, porque la memoria está fragmentada.

Las técnicas comunes para evitar ese efecto incluyen búferes de anillo y grupos de objetos . En el contexto del STL, métodos como std::vector::reserve() pueden ayudar.

La fragmentación de la memoria ocurre porque se solicitan bloques de memoria de diferentes tamaños. Considere un buffer de 100 bytes. Solicitas dos caracteres, luego un número entero. Ahora liberas los dos caracteres, luego solicitas un nuevo entero, pero ese número entero no cabe en el espacio de los dos caracteres. Esa memoria no se puede reutilizar porque no se encuentra en un bloque contiguo suficientemente grande para reasignarla. Además de eso, has invocado una gran cantidad de sobrecarga del asignador para tus caracteres.

Esencialmente, la memoria solo viene en bloques de un cierto tamaño en la mayoría de los sistemas. Una vez que se dividen estos bloques, no se pueden volver a unir hasta que se libere todo el bloque. Esto puede conducir a bloques enteros en uso cuando en realidad solo se usa una pequeña parte del bloque.

La principal forma de reducir la fragmentación del montón es hacer asignaciones más grandes y menos frecuentes. En el extremo, puede usar un montón administrado que sea capaz de mover objetos, al menos, dentro de su propio código. Esto elimina por completo el problema, desde el punto de vista de la memoria, de todos modos. Obviamente mover objetos tiene un costo. En realidad, realmente solo tiene un problema si asigna cantidades muy pequeñas fuera del montón a menudo. El uso de contenedores contiguos (vector, cadena, etc.) y la asignación en la pila tanto como sea humanamente posible (siempre una buena idea para el rendimiento) es la mejor manera de reducirlo. Esto también aumenta la coherencia del caché, lo que hace que su aplicación se ejecute más rápido.

Lo que debe recordar es que en un sistema de escritorio x86 de 32 bits, tiene una memoria completa de 2GB, que se divide en 4KB "páginas" (bastante seguro de que el tamaño de página es el mismo en todos los sistemas x86). Tendrá que invocar alguna fragmentación omgwtfbbq para tener un problema. La fragmentación realmente es un problema del pasado, ya que los montones modernos son excesivamente grandes para la gran mayoría de las aplicaciones, y hay una prevalencia de sistemas que son capaces de resistirlo, como montones administrados.

Actualizar:
Google TCMalloc: Thread-Caching Malloc
Se ha encontrado que es bastante bueno en el manejo de la fragmentación en un proceso de larga ejecución.

He estado desarrollando una aplicación de servidor que tenía problemas con la fragmentación de la memoria en HP-UX 11.23 / 11.31 ia64.

Se veía así. Hubo un proceso que hizo asignaciones de memoria y desasignaciones y se ejecutó durante días. Y a pesar de que no hubo pérdidas de memoria, el consumo de memoria del proceso siguió aumentando.

Sobre mi experiencia En HP-UX, es muy fácil encontrar la fragmentación de memoria utilizando HP-UX gdb. Establece un punto de inflexión y, cuando lo alcanza, ejecuta este comando: info heap y ver todas las asignaciones de memoria para el proceso y el tamaño total del montón. Luego, continúa con tu programa y luego, un tiempo después, vuelves a alcanzar el punto de ruptura. Lo haces de nuevo info heap . Si el tamaño total del montón es mayor, pero el número y el tamaño de las asignaciones por separado son los mismos, es probable que tenga problemas de asignación de memoria. Si es necesario, haga esto pocas veces.

Mi forma de mejorar la situación fue esta. Después de hacer algunos análisis con HP-UX gdb, vi que los problemas de memoria se debían al hecho de que utilicé std::vector para almacenar algunos tipos de información de una base de datos. std::vector requiere que sus datos se mantengan en un bloque. Tenía algunos contenedores basados ​​en std::vector . Estos contenedores fueron recreados regularmente. A menudo hubo situaciones en las que se agregaron nuevos registros a la base de datos y luego se recrearon los contenedores. Y dado que los contenedores recreados eran más grandes, no encajaban en los bloques disponibles de memoria libre y el tiempo de ejecución solicitó un nuevo bloque más grande del sistema operativo. Como resultado, aunque no hubo pérdidas de memoria, el consumo de memoria del proceso creció. Mejoré la situación cuando cambié los contenedores. En lugar de std::vector , comencé a usar std::deque que tiene una forma diferente de asignar memoria para los datos.

Sé que una de las maneras de evitar la fragmentación de la memoria en HP-UX es utilizar el Localizador de bloques pequeños o usar MallocNextGen. En RedHat Linux, el asignador predeterminado parece manejar bastante bien la asignación de una gran cantidad de bloques pequeños. En Windows hay Low-fragmentation Heap y aborda el problema de una gran cantidad de pequeñas asignaciones.

Según tengo entendido, en una aplicación STL-heavy primero debe identificar los problemas. Los asignadores de memoria (como en libc) realmente manejan el problema de muchas asignaciones pequeñas, lo cual es típico para std::string (por ejemplo, en mi aplicación de servidor hay muchas cadenas de STL pero como veo en el info heap ejecución no están causando cualquier problema). Mi impresión es que debe evitar las grandes asignaciones frecuentes. Lamentablemente, hay situaciones en las que no puede evitarlos y tiene que cambiar su código. Como digo en mi caso, mejoré la situación cuando cambié a std::deque . Si identifica la fragmentación de su memoria, podría ser posible hablar de ella con mayor precisión.

Imagine que tiene una extensión "grande" (32 bytes) de memoria libre:

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

Ahora, asigna algo de eso (5 asignaciones):

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

Ahora, libere las primeras cuatro asignaciones pero no la quinta:

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

Ahora intenta asignar 16 bytes. Vaya, no puedo, aunque hay casi el doble de esa cantidad gratis.

En los sistemas con memoria virtual, la fragmentación es un problema menor de lo que podría pensar, porque las asignaciones grandes solo necesitan ser contiguas en el espacio de direcciones virtuales , no en el espacio de direcciones físicas . Entonces en mi ejemplo, si tuviera memoria virtual con un tamaño de página de 2 bytes, podría hacer mi asignación de 16 bytes sin ningún problema. La memoria física se vería así:

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

mientras que la memoria virtual (que es mucho más grande) podría verse así:

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

El síntoma clásico de la fragmentación de la memoria es que intentas asignar un bloque grande y no puedes, a pesar de que pareces tener suficiente memoria libre. Otra posible consecuencia es la incapacidad del proceso para liberar memoria de vuelta al sistema operativo (porque todavía hay algún objeto en uso en todos los bloques que ha asignado desde el sistema operativo, aunque esos bloques están ahora en su mayoría sin usar).

Tácticas para evitar la fragmentación de la memoria en el trabajo de C ++ mediante la asignación de objetos de diferentes áreas de acuerdo con su tamaño y / o la duración esperada. Entonces, si va a crear muchos objetos y destruirlos todos juntos más tarde, asígnelos desde un grupo de memoria. Cualquier otra asignación que haga entre ellos no será del grupo, por lo tanto, no se ubicará entre ellos en la memoria, por lo que la memoria no se fragmentará como resultado.

En general, no necesita preocuparse demasiado, a menos que su programa sea de larga ejecución y le otorgue mucha asignación y liberación. Es cuando tienes mezclas de objetos efímeros y de larga vida que corres mayor riesgo, pero incluso entonces malloc hará todo lo posible para ayudar. Básicamente, ignórelo hasta que su programa tenga fallas de asignación o inesperadamente provoque que el sistema se quede sin memoria (¡tómelo en prueba, por favor!).

Las bibliotecas estándar no son peores que cualquier otra cosa que asigna memoria, y los contenedores estándar tienen todos un parámetro de plantilla Alloc que puede usar para ajustar su estrategia de asignación si es absolutamente necesario.