memory-management - sistemas - memoria particionada

¿Qué estructura de datos se usa para implementar el montón de asignación de memoria dinámica? (2)

Siempre asumí que un montón (estructura de datos) se utiliza para implementar un montón (asignación de memoria dinámica) , pero me han dicho que estoy equivocado.

¿Cómo se implementan los montones (por ejemplo, el implementado por rutinas típicas de malloc , o HeapCreate de Windows, etc.), normalmente? ¿Qué estructuras de datos usan?

Lo que no estoy preguntando

Mientras buscaba en línea, he visto toneladas de descripciones de cómo implementar montones con severas restricciones .
Para nombrar algunos, he visto muchas descripciones de cómo implementar:

Montones que nunca liberan memoria al sistema operativo (!)
Montones que solo ofrecen un rendimiento razonable en bloques pequeños de tamaño similar
Montones que solo proporcionan un rendimiento razonable para bloques grandes y contiguos
etc.

Y es gracioso, todos evitan la pregunta más difícil:
¿Cómo se implementan montones "normales" de uso general (como el que está detrás de malloc , HeapCreate )?

¿Qué estructuras de datos (y quizás algoritmos) usan?

Los asignadores tienden a ser bastante complejos y a menudo difieren significativamente en cómo se implementan.

Realmente no puede describirlos en términos de una estructura de datos común o algoritmo, pero hay algunos temas comunes:

La memoria se toma del sistema en grandes porciones, a menudo megabytes a la vez.
Estos fragmentos se dividen en varios trozos más pequeños a medida que realizas las asignaciones. No es exactamente del mismo tamaño que usted asigna, pero generalmente en ciertos rangos (200-250 bytes, 251-500 bytes, etc.). A veces esto tiene varios niveles, donde tendrías una capa adicional de "fragmentos medianos" que vienen antes de tus solicitudes reales.
Controlar qué "porción grande" para romper una pieza es una cosa muy difícil e importante, esto afecta en gran medida la fragmentación de la memoria.
Uno o más pools libres (también llamados "free list", "pool de memoria", "lista de lookaside") se mantienen para cada uno de estos rangos. A veces, incluso grupos de subprocesos locales. Esto puede acelerar en gran medida un patrón de asignación / desasignación de muchos objetos de tamaño similar.
Las grandes asignaciones se tratan de forma un poco diferente para no desperdiciar mucha RAM y no agruparse tanto o nada.

Si quería verificar algún código fuente, jemalloc es un asignador moderno de alto rendimiento y debería ser representativo en complejidad de otros comunes. TCMalloc es otro asignador de propósito general común, y su sitio web va a todos los detalles de implementación sangrientos. Los bloques de construcción de subprocesos de Intel tienen un asignador creado específicamente para alta concurrencia.

Se puede ver una diferencia interesante entre Windows y * nix. En * nix, el asignador tiene un control de muy bajo nivel sobre el espacio de direcciones que usa una aplicación. En Windows, básicamente tiene un allocator de VirtualAlloc lenta y VirtualAlloc para basar su propio asignador.

Esto da como resultado asignadores compatibles con * nix que le dan directamente una implementación malloc / free donde se supone que solo usará un asignador para todo (de lo contrario, se pisotearían entre sí), mientras que los asignadores específicos de Windows proporcionan funciones adicionales, dejando malloc / free alone, y se puede usar en armonía (por ejemplo, puede usar HeapCreate para hacer montones privados que pueden funcionar junto con otros).

En la práctica, este intercambio de flexibilidad otorga a los asignadores de * nix una ventaja pequeña en términos de rendimiento. Es muy raro ver una aplicación usar intencionalmente montones múltiples en Windows, principalmente por accidente debido a diferentes DLL que usan diferentes tiempos de ejecución, cada uno tiene su propio malloc / free y puede causar muchos dolores de cabeza si no se es diligente en el rastreo. de qué montón vino algún recuerdo.

Nota: La siguiente respuesta supone que está utilizando un sistema típico y moderno con memoria virtual. Los estándares C y C ++ no requieren memoria virtual; por lo tanto, por supuesto, no puede confiar en tales suposiciones en el hardware sin esta característica (por ejemplo, las GPU generalmente no tienen esta característica, ni el hardware extremadamente pequeño como el PIC).

Esto depende de la plataforma que estés usando. Los montones pueden ser bestias muy complicadas; no usan solo una estructura de datos única; y no hay una estructura de datos "estándar". Incluso donde se encuentra el código de pila es diferente dependiendo de la plataforma. Por ejemplo, el código de heap es típicamente proporcionado por C Runtime en cajas Unix; pero normalmente lo proporciona el sistema operativo en Windows.

Sí, esto es común en máquinas Unix; debido a la forma en que operan las API subyacentes * nix y el modelo de memoria. Básicamente, la API estándar para devolver memoria al sistema operativo en estos sistemas solo permite devolver la memoria en la "frontera" entre el lugar donde se asigna la memoria del usuario y el "orificio" entre la memoria del usuario y las instalaciones del sistema como la pila. (La API en cuestión es brk o sbrk ). En lugar de devolver la memoria al sistema operativo, muchos montones solo intentan reutilizar la memoria que el programa ya no utiliza y no intenta devolver la memoria al sistema. Esto es menos común en Windows, porque su equivalente a sbrk ( VirtualAlloc ) no tiene esta limitación. (Pero al igual que sbrk , es muy costoso y tiene advertencias, como asignar trozos de tamaño de página y alineados a la página. Por lo tanto, los montones intentan llamar con la sbrk posible)
Esto suena como un "asignador de bloque", que divide la memoria en trozos de tamaño fijo, y luego simplemente devuelve uno de los trozos libres. Para mi (aunque limitado) entendimiento, Windows '' RtlHeap mantiene una cantidad de estructuras de datos como esta para diferentes tamaños de bloque conocidos. (Por ejemplo, tendrá uno para bloques de tamaño 16, por ejemplo) RtlHeap llama a estas "listas de lookaside".
Realmente no conozco una estructura específica que maneje bien este caso. Los bloques grandes son problemáticos para la mayoría de los sistemas de asignación porque provocan la fragmentación del espacio de direcciones.

La mejor referencia que he encontrado para analizar las estrategias comunes de asignación empleadas en las principales plataformas es el libro Secure Coding in C and C ++ , de Robert Seacord . Todo el capítulo 4 está dedicado a estructuras de datos de montón (y problemas causados cuando los usuarios usan dichos sistemas de montón incorrectamente).