Cómo diseñar un asignador de memoria
Sin embargo, puedes probarlo tú mismo mientras lees este libro, lo escribes y juegas con él como si fuera un juguete.
1. La implementación del asignador de memoria en el libro de texto:
Haga una lista vinculada que apunte a la memoria libre. Para asignar, saque una parte, reescriba la lista vinculada y regrese. y liberar significa volver a colocarlo en la lista vinculada y hacer un buen trabajo fusionándolo. Preste atención al marcado y la protección para evitar la liberación secundaria. También puede dedicar algo de tiempo a encontrar el tamaño de memoria más adecuado y buscar rápidamente para reducir la fragmentación de la memoria. Cuando esté libre, también puede cambiar la lista vinculada al socio. algoritmo. Juguemos con él.
2. Implemente un asignador de memoria fijo:
Es decir, implemente una FreeList. Cada FreeList se utiliza para asignar un bloque de memoria de tamaño fijo, como objetos fijos de 32 bytes. asignador de memoria, etc. Hay dos listas vinculadas dentro de cada asignador de memoria fijo. OpenList se usa para almacenar objetos libres no asignados y CloseList se usa para almacenar objetos de memoria asignados. Por lo tanto, la llamada asignación consiste en tomar un objeto de OpenList y colocarlo en CloseList y. devuélvalo al usuario y suelte los movimientos de CloseList a OpenList. Si la memoria asignada es insuficiente, debe aumentar OpenList: solicite un bloque de memoria más grande, luego córtelo en 64 objetos del mismo tamaño y agréguelos a OpenList. Cuando se recupera el asignador de memoria anclado, devuelve al sistema todos los bloques de memoria solicitados previamente del sistema.
3. Implemente el grupo FreeList:
Según la implementación de FreeList, cree más de una docena de tamaños diferentes (8 bytes, 16 bytes, 32, 64, 128, 256, 512). , 1K, 64K) grupo de objetos. 64K), construya más de diez asignadores de memoria fijos, asigne memoria de acuerdo con el tamaño de la tabla de búsqueda de memoria, decida qué asignador es responsable y, una vez completada la asignación, el encabezado de la tabla (el encabezado en ptr [-sizeof(char* )]) Escriba una cookie para indicar qué asignador la asignó para que pueda devolverse correctamente cuando se libere. Si es mayor que 64K, puede usar el malloc del sistema para asignar. De esta manera, a costa de desperdiciar memoria, obtendrá un asignador de memoria con un tiempo de asignación de aproximadamente O (1). , pero no seas complaciente todavía. Esta sección no es una sección (para el kernel sunos/solaris/linux). Sigue siendo una lista libre para débiles mentales que no puede devolver memoria al sistema operativo, y una lista libre que ocupa mucha memoria en su punto máximo no puede admitir otras listas libres que no tienen suficiente memoria, incluso si no se usa más adelante. , entonces lo que estamos haciendo es algo así como que el asignador de Memcached está bastante roto y necesitarás optimizarlo aún más.
4. Implemente una losa ortodoxa (pseudo-losa almacenada en caché sin memoria) en lugar de FreeList:
En este momento, debe leer http://citeseer.ist.psu. edu El documento en /bonwick94slab.html es la base de la tecnología moderna de asignación de memoria, que incluye cómo administrar objetos en la losa, cómo administrar direcciones, cómo administrar los ciclos de vida de diferentes losas y cómo recuperar memoria del sistema. Luego comencé a darme cuenta de algo similar. Aunque los conceptos básicos de los sectores tradicionales en el artículo no han cambiado hoy, en realidad existen muchos métodos mejores para las estructuras de datos y los métodos de control utilizados. no funciona, puede consultar el código fuente del kernel.
Pero hay muchas cosas que las aplicaciones no pueden hacer y hay muchos métodos de implementación que no se pueden copiar, como el proveedor de páginas, que puede proporcionar páginas con direcciones lineales continuas, o el propio núcleo registra la sección correspondiente de cada página. Al consultar la sección, el sistema en realidad obtiene el número de página basándose en el cambio lineal de direcciones y luego busca en la tabla, pero es imposible que su aplicación haga esto. Debe hacer un poco de trabajo adicional para resolver estos problemas y también debe escribir algunas cookies adicionales para realizar el etiquetado. Haz un buen trabajo de reducción de memoria. Si se queda sin memoria, reduzca todos los mosaicos de asignadores antes de intentar reasignarlos. Luego, haga un buen trabajo de reciclaje de memoria para devolver al sistema operativo el exceso de memoria que no se ha utilizado durante un período de tiempo.
5. Implemente una estrategia de asignación mixta:
Después de haber implementado muchos de los algoritmos comunes mencionados anteriormente, debe leer el código de varios asignadores de memoria probados y verdaderos, como como asignador de memoria de libc, o consulte varios proyectos de código abierto que tienen su propia administración de memoria, como el código fuente de Python, y haga algunos experimentos para comparar sus pros y sus contras, y luego use diferentes estrategias de asignación según el tamaño del objeto asignado . Luego, según el tamaño del objeto asignado, puede utilizar diferentes estrategias de asignación para tratar distintas situaciones de manera diferente. Después de probar estos métodos, puede introducir soporte para subprocesos múltiples y hacer que el bloqueo sea más pequeño. Cabe señalar que existen muchas políticas de seguridad de subprocesos a nivel del sistema en las que no puede involucrarse. Por ejemplo, el sistema operativo puede desactivar las interrupciones y prohibir el cambio de tareas en la CPU durante un corto período de tiempo. aplicaciones, y debes usar más candado pequeño para reemplazarlo. Cuando el candado es demasiado pequeño, también puede optar por introducir STM en varias listas vinculadas para reemplazar el candado.
6. Implementar caché por CPU:
Una optimización importante de los asignadores de memoria modernos en multinúcleo es agregar caché para múltiples núcleos para evitar aún más subprocesos. Para bloquear la competencia, es necesario introducir el almacenamiento en caché por CPU. Al asignar memoria, primero busque la CPU donde se encuentra el subproceso correspondiente y asigne el caché correspondiente de esa CPU. Si el caché no es suficiente, asigne algunos objetos más de su asignador de memoria subyacente para llenar el caché de una vez. , vuelva a colocarlo en el caché primero. El caché Si hay demasiados objetos, el asignador subyacente realizará una acción de reducción de memoria para permitir que otros cachés de CPU lo aprovechen. Por lo tanto, muchas asignaciones y lanzamientos frecuentes con ciclos de vida cortos se completan en el caché, sin competencia de bloqueo. Al mismo tiempo, la lógica de asignación del caché es simple y rápida. El código en el sistema operativo a menudo lee directamente qué CPU es la actual, y la implementación de la capa de aplicación se puede reemplazar con almacenamiento local de subprocesos. Actualmente, estas cosas no son compatibles con el malloc de CRT (no se puede descartar que lo sean). aumentará en versiones futuras), para obtener más información, consulte tc/jemalloc.
7. Implementación de coloración de direcciones
Los asignadores de memoria modernos deben considerar la presión del bus. En muchos modelos, si los accesos a la memoria se concentran en el mismo desplazamiento de la línea de caché, habrá Put. carga y presión adicionales sobre el autobús. Por ejemplo, a menudo es necesario asignar un objeto FILE, y cada objeto FILE se utilizará para acceder de forma centralizada a la variable miembro int FILE::flag; Si la dirección de página proporcionada por el proveedor de la página está alineada en 4K, es posible que los miembros de banderas de múltiples objetos FILE estén ubicados en el mismo desplazamiento de línea de caché. La misma dirección de desplazamiento supondrá una gran carga para el bus, por lo que debe agregar algunos desplazamientos adicionales a cada objeto para que puedan distribuirse uniformemente en la dirección de desplazamiento de la línea de caché correspondiente a la dirección lineal para reducir la sobrecarga del conflicto del bus.
8. Optimice la contención de caché:
En la era de múltiples núcleos, muchos códigos de un solo núcleo deben optimizarse y reescribirse para este propósito. El más básico de ellos es la contención de caché. , que es incluso peor que la contención de bloqueo: si dos CPU acceden a la misma línea de caché o página física al mismo tiempo, para garantizar la coherencia de la memoria, se debe realizar una gran cantidad de trabajo de comunicación entre las CPU, por ejemplo, cpu0. use este bloque de memoria, se descubre que cpu1 también está en uso. En este momento, es necesario notificar a cpu1 para que escriba los datos de la caché L1-L2 de cpu1 nuevamente en la memoria física y luego libere los derechos de control. La operación continua durante este período, el protocolo de comunicación entre cpu0-cpu1 es más complejo y costoso, y la competencia de caché es más aterradora que la competencia de bloqueo. Durante este período, el protocolo de comunicación entre cpu0 y cpu1 es más complejo y costoso, y la contención de caché es más grave que la contención de bloqueo. Para evitar la competencia de caché, necesitamos un mecanismo de página por CPU más completo que el caché por CPU anterior para resolver este problema, permitiendo directamente que diferentes CPU usen diferentes páginas para la asignación secundaria, evitando por completo la competencia de caché. El enfoque específico de la capa de aplicación es usar direcciones lineales para determinar la propiedad de la página (porque las páginas físicas asignadas a las direcciones de proceso también están alineadas en 4k), mientras continúa usando el almacenamiento local de subprocesos o usa la API proporcionada por el sistema para leer qué implementación de CPU tiene. pertenece actualmente. Para evitar el desperdicio innecesario causado por demasiadas páginas por núcleo, puede consultar el último algoritmo de asignación de memoria slub de Linux. Sin embargo, slub también tiene algunos trabajos sin terminar. Varias distribuciones de Linux han descubierto que todavía hay algunos problemas en slub (. no errores), sino el mecanismo), por lo que la mayoría de las distribuciones tienen slub desactivado de forma predeterminada, sin embargo, aún puedes probarlo. Aún puedes probarlo.
9. Depuración y lanzamiento:
Continúe consultando varios asignadores de memoria modernos, aprenda de sus fortalezas y debilidades y luego agregue algunos mecanismos de depuración a su asignador para diagnosticar problemas más fácilmente. . Después de aprender de muchos proyectos de código abierto, realizar algunas de las llamadas optimizaciones usted mismo y jugar con ellas durante tanto tiempo, puede pensar que su asignador puede competir con varios asignadores de código abierto y los resultados de la prueba parecen ser bastante buenos. No se preocupe, siga observando y vea si la utilización de la memoria, la frecuencia de las solicitudes/devoluciones de memoria desde/hacia el sistema operativo y otras métricas que fácilmente se pasan por alto son las mismas. Al mismo tiempo, ¿cambiar los casos de prueba y ver si los resultados siguen siendo los mismos que antes en más casos? Cuando son similares, encontrará que sin uno o dos años de uso continuo a gran escala, es difícil encontrar algunos posibles peligros y errores ocultos. Puede pensar que no hay ningún problema con el código después de dos años de ejecución. , el código seguirá informando errores. Esto es normal. Si tienes más paciencia, ¿tal vez será más estable después del tercer año?
¿Cuál es el punto de esto?
Hace más de diez años, cuando libc aún era inmaduro, la mayoría de los programadores tenían que implementar un asignador de memoria específico para sus aplicaciones para garantizar que el programa durara mucho tiempo. En ese momento, si no administra su propia memoria, una gran cantidad de clientes, si realiza muchas asignaciones frecuentes computacionalmente intensivas, puede no tener mucho impacto al principio, pero si lo ejecuta durante unas horas, el el rendimiento se degradará inmediatamente; si excede Si no reinicia el proceso del servidor durante 10 días, la velocidad será cada vez más lenta y habrá cada vez más fragmentos.
Hoy en día, el malloc de libc se ha mejorado mucho y este tipo de situaciones son raras, entonces, ¿qué más es el grupo de memoria?
A medida que su juguete se vuelve cada vez más estable, finalmente es hora de generar algo de valor. Dado que algunas métricas de rendimiento no tienen lo mejor de ambos mundos, el asignador estándar tiende a proporcionar algo así como conservador y A moderado. enfoque, y el primer paso que puede tomar es romper el equilibrio y hacer que su asignador atienda ciertas situaciones, tales como:
1. La memoria de la computadora moderna es enorme, ¿no se puede sacrificar la utilización de la memoria? ¿Intercambiar por una devolución/reutilización de memoria más eficiente? ¿Se puede cambiar por una velocidad de distribución más rápida? Quizás descubra que puede duplicar con creces el desperdicio de memoria promedio de 30 del malloc de libc a cambio de una ganancia de rendimiento, lo que puede tener un efecto positivo en aplicaciones donde la asignación de memoria es el cuello de botella.
2. Por ejemplo, puede ajustar la proporción de memoria pequeña a memoria grande. Si libc trata 8K o menos memoria como memoria pequeña, entonces puede tratarla como memoria grande.
3. Por ejemplo, si su sistema es un sistema de un solo subproceso, ¿puede proporcionar un interruptor para que se ejecute completamente en modo de un solo subproceso, evitando así por completo varios bloqueos y varios cambios realizados para múltiples núcleos? ¿Algo redundante?
4. Por ejemplo, si su máquina tiene memoria limitada y su aplicación consume mucha memoria, puede introducir otros mecanismos y sacrificar una pequeña cantidad de rendimiento para obtener un mejor reciclaje y utilización de la memoria.
5. ¿Puede la memoria asignada recientemente ser lo más contigua posible en direcciones lineales? ¿Es posible evitar al máximo los fallos de página en la dirección?
6. Por ejemplo, si es necesario rastrear algunos objetos en el programa, ¿puede implementar el mecanismo de seguimiento de objetos directamente en el asignador para rastrear varias fugas y problemas fuera de límites?
7. Cada asignación de memoria persigue una equidad óptima. ¿Qué equidad le preocupa?