¿Lidiar con la fragmentación en un grupo de memoria?

Question

Supongamos que tengo un objeto de grupo de memoria con un constructor que toma un puntero a un gran trozo de memoria ptr y tamaño N. Si hago muchas asignaciones aleatorias y desasignaciones de varios tamaños, puedo obtener la memoria en un estado tal que no puedo asigna un objeto de M byte contiguamente en la memoria, ¡aunque puede haber mucho gratis! Al mismo tiempo, no puedo compactar la memoria porque eso causaría un puntero oscilante en los consumidores. ¿Cómo se puede resolver la fragmentación en este caso?

Answer 1

Quería agregar mis 2 centavos solo porque nadie más señaló que por su descripción parece que está implementando un asignador de montón estándar (i.e lo que todos nosotros usamos cada vez que llamamos malloc() u operador nuevo).

Un montón es exactamente tal objeto, que va al administrador de memoria virtual y solicita una gran cantidad de memoria (lo que llama "un grupo"). Luego tiene todo tipo de algoritmos diferentes para lidiar con la forma más eficiente de asignar varios trozos de tamaño y liberarlos. Además, muchas personas han modificado y optimizado estos algoritmos a lo largo de los años. Durante mucho tiempo, Windows llegó con una opción llamada montón de baja fragmentación (LFH) que solía tener que habilitar manualmente. Comenzando con Vista LFH se usa para todos los montones de forma predeterminada.

Los montones no son perfectos y definitivamente pueden empantanar el rendimiento cuando no se usan correctamente. Como los proveedores de sistemas operativos no pueden anticipar cada escenario en el que utilizarán un montón, sus gestores de almacenamiento dinámico deben optimizarse para el uso "promedio". Pero si tiene un requisito que es similar a los requisitos para un montón normal (es decir, muchos objetos, diferentes tamaños ...) debe considerar simplemente usar un montón y no reinventarlo porque es probable que su implementación sea inferior a lo que OS ya provee para ti.

Con asignación de memoria, la única vez que puede obtener rendimiento no simplemente utilizando el montón es renunciando a algún otro aspecto (sobrecarga de asignación, duración de la asignación ...) que no es importante para su aplicación específica.

Por ejemplo, en nuestra aplicación teníamos un requisito para muchas asignaciones de menos de 1 KB pero estas asignaciones solo se usaban durante períodos de tiempo muy cortos (milisegundos). Para optimizar la aplicación, utilicé la biblioteca de Boost Pool pero la extendí para que mi "asignador" en realidad contuviera una colección de objetos de conjunto de impulso, cada uno responsable de asignar un tamaño específico de 16 bytes hasta 1024 (en pasos de 4). Esto proporcionó una asignación casi gratuita (O (1) complejidad)/libre de estos objetos, pero la pega es que a) el uso de memoria siempre es grande y nunca baja aunque no tengamos un solo objeto asignado, b) Boost Pool nunca libera la memoria que usa (al menos en el modo en que la estamos usando), así que solo usamos esto para objetos que no se quedan por mucho tiempo.

Entonces, ¿qué aspecto (s) de asignación normal de memoria está dispuesto a abandonar en su aplicación?

Answer 2

Según el sistema, hay varias formas de hacerlo.

Trate de evitar la fragmentación en primer lugar, si asigna bloques en potencias de 2 tiene menos posibilidades de causar este tipo de fragmentación. Hay un par de otras formas de hacerlo, pero si alguna vez llega a este estado, entonces solo OOM en ese punto porque no hay formas delicadas de manejarlo, aparte de matar el proceso que solicitaba memoria, bloquear hasta que pueda asignar memoria, o devuelve NULL como área de asignación.

Otra forma es pasar los punteros a los punteros de sus datos (por ejemplo, int **). Luego puede reorganizar la memoria debajo del programa (espero que sea segura) y compacte las asignaciones para que pueda asignar nuevos bloques y conservar los datos de los bloques antiguos (una vez que el sistema llega a este estado, se convierte en una carga pesada, pero rara vez hacerse)

También hay formas de "agrupar" la memoria para que tenga páginas contiguas, por ejemplo, dedique 1 página solo a asignaciones de 512 y menos, otra para 1024 y menos, etc. Esto facilita la toma de decisiones sobre qué bin usar y, en el peor de los casos, se divide del siguiente bin más alto o se fusiona desde un bin inferior, lo que reduce la posibilidad de fragmentación en varias páginas.

Answer 3

• escriba el grupo para que funcione como una lista de asignaciones, luego puede ampliar y destruir según sea necesario. esto puede reducir la fragmentación.
• y/o implemente el soporte de transferencia de asignación (o movimiento) para que pueda compactar las asignaciones activas. Es posible que el objeto/titular deba ayudarlo, ya que es posible que el grupo no sepa cómo transferir los tipos. si el grupo se utiliza con un tipo de colección, entonces es mucho más fácil lograr compactación/transferencias.

Answer 4

La implementación de object pools para los objetos que asigna con frecuencia disminuirá la fragmentación considerablemente sin la necesidad de cambiar el asignador de memoria.

Answer 5

Sería útil saber más exactamente lo que realmente está tratando de hacer, porque hay muchas maneras de lidiar con esto.
Pero, la primera pregunta es: ¿esto está sucediendo realmente, o es una preocupación teórica?

Una cosa a tener en cuenta es que normalmente tiene mucho más espacio de direcciones de memoria virtual disponible que la memoria física, por lo que incluso cuando la memoria física está fragmentada, todavía hay mucha memoria virtual contigua. (Por supuesto, la memoria física no es contigua por debajo, pero su código no lo ve).

Creo que a veces existe un temor injustificado a la fragmentación de la memoria y, como resultado, las personas escriben un asignador de memoria personalizado (o peor, confeccionar un esquema con asas y memoria móvil y compactación). Creo que rara vez se necesitan en la práctica, y en ocasiones puede mejorar el rendimiento para descartarlo y volver a utilizar malloc.