[Conocimientos de programación] Cómo asignar memoria Tecnología de fragmentación de memoriaLa fragmentación de la memoria es un problema espinoso. La forma en que se asigna la memoria determina si, cuándo y cómo la fragmentación de la memoria se convierte en un problema. La fragmentación de la memoria puede eventualmente conducir al agotamiento de la misma, incluso si todavía hay mucha memoria libre en el sistema. Un sistema que fragmenta constantemente la memoria, por pequeña que sea, se quedará sin memoria con el tiempo suficiente. Esta situación es inaceptable en muchos sistemas integrados, especialmente en los sistemas de alta disponibilidad. Algunos entornos de software, como el sistema operativo en tiempo real OSE, tienen buenas herramientas para evitar la fragmentación de la memoria, pero las elecciones individuales de los programadores aún pueden tener un impacto en el resultado final. "Memoria fragmentada" se refiere a toda la memoria libre no utilizada en el sistema. Estos recursos no se utilizan porque el asignador responsable de asignar la memoria los hace no disponibles. Este problema suele producirse porque existe memoria libre en fragmentos pequeños y no contiguos en diferentes ubicaciones. Dado que el método de asignación determina si la fragmentación de la memoria será un problema, el asignador de memoria juega un papel importante para garantizar la disponibilidad de recursos libres. Tiempo de compilación versus tiempo de ejecución Los problemas de asignación de memoria surgen en muchas situaciones. Los programadores pueden asignar memoria para datos como estructuras, conexiones, matrices y escalares (usados como variables locales, estáticas o globales) compilando y vinculando el programa, o asignar memoria dinámicamente en tiempo de ejecución usando comandos como llamadas malloc(). Cuando la función de asignación de memoria se implementa a través del compilador y el vinculador, no se produce fragmentación de la memoria porque el compilador comprende el ciclo de vida de los datos. El beneficio de comprender el ciclo de vida de los datos disponibles es que permite apilarlos de forma que sean los últimos en entrar, los primeros en salir. Esto permite que el asignador de memoria funcione de manera más eficiente sin fragmentación de la memoria. En términos generales, la asignación de memoria en tiempo de ejecución no es apilable. Las asignaciones de memoria son independientes en el tiempo, lo que dificulta la resolución de los problemas de fragmentación. Figura 1: Varias formas de fragmentación de la memoria. Hay tres formas básicas en que los asignadores de memoria desperdician memoria: sobrecarga, fragmentación interna y fragmentación externa (Figura 1). El asignador de memoria necesita almacenar algunos datos que describan el estado de su asignación. Esta información de almacenamiento incluye la ubicación, el tamaño y la propiedad de los bloques de memoria libres, así como otros detalles del estado interno. En términos generales, el mejor lugar para que el asignador de tiempo de ejecución almacene esta información adicional es la memoria que administra. Los asignadores de memoria deben seguir algunas reglas básicas de asignación de memoria. Por ejemplo, todas las asignaciones de memoria deben comenzar en una dirección divisible por 4, 8 o 16 (según la arquitectura del procesador). Puede haber otras razones por las que el asignador de memoria solo asigna bloques de memoria de un tamaño predeterminado a los clientes. Cuando un cliente solicita un bloque de memoria de 43 bytes, puede obtener 44 bytes, 48 bytes o incluso más. El espacio extra resultante de redondear el tamaño requerido se llama fragmentación interna. La fragmentación externa ocurre cuando hay diferencias no utilizadas entre los bloques de memoria asignados. Por ejemplo, una aplicación asigna tres bloques de memoria consecutivos y luego libera el bloque del medio. El asignador de memoria puede reutilizar los bloques de memoria intermedios en asignaciones futuras, pero es poco probable que asigne un bloque de memoria tan grande como todos los bloques de memoria libres. Si el asignador de memoria no cambia su implementación y estrategia de redondeo durante la operación, la sobrecarga y la fragmentación interna permanecerán constantes durante toda la vida útil del sistema. Si bien la sobrecarga y la fragmentación interna desperdician memoria y, por lo tanto, no son deseables, la fragmentación externa es el verdadero enemigo de los desarrolladores de sistemas integrados y es un problema de asignación que conduce a fallas del sistema. Hay varias formas de definir la fragmentación de la memoria, las más comunes son: Este método funciona para la fragmentación externa, pero la fórmula se puede modificar para incluir la fragmentación interna sumándola al denominador. La fragmentación de la memoria es una puntuación entre 0 y 1. Un sistema con un nivel de fragmentación de 1 (100) está utilizando toda su memoria. Si toda la memoria disponible está en un bloque de memoria (el bloque de memoria más grande), la tasa de fragmentación es 0. Cuando una cuarta parte de la memoria disponible está en el bloque de memoria más grande, la tasa de fragmentación es 75. A continuación se muestra un ejemplo: un sistema con 5 millones de bytes de memoria libre tiene una tasa de fragmentación de 99 cuando el bloque de memoria asignable más grande es de 50 kbytes.
Este ejemplo de fragmentación de memoria 99 proviene de una situación de la vida real que ocurre cuando se desarrollan sistemas integrados en tiempo real. Cuando este nivel de fragmentación apareció un segundo después, el sistema falló. El sistema fue probado en campo continuamente durante dos semanas antes de alcanzar una tasa de fragmentación de 99. ¿Cómo sucede esto? ¿Por qué se descubrió tan tarde? Por supuesto, el sistema se prueba, pero el tiempo de prueba rara vez supera las dos horas. La prueba de estrés final antes del parto duró más de un fin de semana. Es posible que la fragmentación de la memoria no sea consecuencia de un período de prueba tan corto, por lo que surge la pregunta de cuánto tiempo tarda la fragmentación de la memoria en alcanzar niveles críticos, y es difícil de responder. Para algunas aplicaciones, bajo ciertas circunstancias, el sistema alcanzará un estado estable antes de quedarse sin memoria. Para otras aplicaciones, el sistema no alcanza el estado estable en el tiempo (Figura 2). Al eliminar la incertidumbre y los factores de riesgo, el asignador de memoria no fragmentada (Figura 3) puede alcanzar rápidamente un estado estable, lo que ayuda a los desarrolladores a dormir más tranquilos por la noche. La rápida convergencia a un estado estable es un factor importante a la hora de desarrollar sistemas de larga duración que no se reinician durante meses o incluso años. El sistema debe probarse adecuadamente durante un período de tiempo que sea más corto que el período de funcionamiento continuo del sistema. Figura 2. Este estudio de caso utiliza el asignador de memoria First Fit en un proyecto de sistemas integrados. El sistema funcionó continuamente durante dos semanas en pruebas de campo antes de que la tasa de fragmentación alcanzara 99. Figura 3. El asignador de memoria no fragmentada alcanza un estado estable después de pruebas exhaustivas de la aplicación. Es difícil determinar qué algoritmo de asignación de memoria es superior porque cada algoritmo tiene sus propias ventajas en diferentes aplicaciones (Tabla 1). El algoritmo de asignación de memoria del primer ajuste es el algoritmo más utilizado. Utiliza cuatro punteros: MSTART apunta al comienzo de la memoria administrada; MEND apunta al final de la memoria administrada; MBREAK apunta al final de la memoria utilizada entre MSTART y MEND y PFREE apunta al primer bloque de memoria libre (si hay uno); ). Cuando se inicia el sistema, PFREE es NULL y MBREAK apunta a MSTART; cuando se recibe una solicitud de asignación, el asignador primero verifica PFREE para ver si hay un bloque de memoria libre. Debido a que PFREE está vacío, un bloque de memoria que contiene la cantidad solicitada de encabezados de administración y almacenamiento se libera de MBREAK y luego se actualiza MBREAK. Este proceso se repite hasta que el sistema libera un bloque de memoria y el encabezado de administración contiene el espacio de almacenamiento para ese bloque de memoria. En este punto, el PFREE se actualiza para que apunte al bloque de memoria a través de la entrada de inserción de la lista vinculada en el encabezado, y el bloque de memoria en sí se actualiza para que apunte a un puntero al contenido antiguo de PFREE para crear la lista vinculada. La próxima vez que se produzca una solicitud de asignación, el sistema busca en la lista vinculada de bloques de memoria libres el primer bloque de memoria libre que se ajuste a la cantidad de almacenamiento solicitada. Una vez que se encuentra un bloque de memoria adecuado, el sistema lo divide en dos partes, una parte se devuelve al sistema y la otra parte se envía a la lista libre. El algoritmo de asignación de memoria de primera coincidencia es sencillo de implementar y funciona bien inicialmente. Pero después de un tiempo, sucede lo siguiente: cuando el sistema entrega memoria a la lista libre, el bloque de memoria grande se elimina del principio de la lista libre y los bloques de memoria pequeños restantes se insertan. El primer algoritmo de coincidencia en realidad se convierte en un algoritmo de clasificación que coloca todos los bloques de memoria pequeños al comienzo de la lista libre. Como resultado, la lista libre se vuelve muy larga, con cientos o incluso miles de elementos. Como resultado, la asignación de memoria se vuelve larga e impredecible, y se necesita más tiempo para asignar bloques de memoria grandes que para asignar bloques de memoria pequeños. Además, la partición ilimitada de bloques de memoria puede provocar una alta fragmentación de la memoria. Al liberar memoria, algunas implementaciones concatenan bloques de memoria libres adyacentes. Aunque este método es más o menos útil, a diferencia de los algoritmos de colocalización temporal y espacial, el algoritmo de primer ajuste no puede mejorar la probabilidad de que los bloques de memoria adyacentes se liberen al mismo tiempo que se liberan. Procedimientos de asignación de mejor coincidencia y peor coincidencia El algoritmo de mejor coincidencia es funcionalmente similar al algoritmo de primera coincidencia, excepto que cuando el sistema asigna un bloque de memoria, busca en toda la lista libre el bloque de memoria más cercano a la cantidad de almacenamiento solicitada. Esta búsqueda lleva mucho más tiempo que el algoritmo de mejor ajuste, pero no hay diferencia en el tiempo necesario para asignar bloques de memoria pequeños y grandes.