Gestión de memoria LiteOS: algoritmo TLSF

El algoritmo TLSF se propone principalmente para sistemas operativos en tiempo real. Para RTOS, la certeza del tiempo de ejecución es la más fundamental (el rendimiento no es necesariamente alto, pero el asignador de memoria dinámica tradicional (DMA). , Hay dos problemas principales con el asignador de memoria dinámica

La propuesta de TLSF ha resuelto mejor los dos problemas anteriores: reducir la complejidad temporal de la asignación de memoria dinámica y reciclar a una complejidad temporal O (1), y una buena Se adopta una estrategia de asignación adecuada para garantizar que el sistema no genere demasiada fragmentación cuando se ejecuta.

TLSF (nombre completo Two-Level Segregated Fit), desde el punto de vista del nombre, se divide principalmente en tres partes

TLSF utiliza principalmente mapa de bits de dos niveles (Two-Level Bitmap) y bloques libres jerárquicos La estructura de datos de la lista vinculada (Lista libre segregada) administra el grupo de memoria dinámica (grupo de memoria) y sus bloques libres (bloques libres), que se asignan mediante la estrategia Good-Fit. Presentemos brevemente estos tres a continuación.

Aún utilizando el método de comprensión dividida, continúe desarmando la Lista libre segregada para explorar sus ideas de diseño y proceso de desarrollo.

Las listas vinculadas son la estructura de datos más común en la administración de memoria. Se agrega un nodo principal al encabezado de un bloque de memoria para registrar la información del bloque en sí y la relación entre los bloques anterior y posterior.

La más simple es la lista vinculada implícita, que vincula todos los bloques de memoria y solo registra el tamaño del bloque de memoria. Dado que los bloques de memoria están estrechamente conectados, la siguiente memoria se puede obtener agregando el puntero del nodo principal. el tamaño del bloque de memoria. Dado que la dirección del bloque de memoria no se especifica explícitamente sino que se calcula, también se denomina lista vinculada implícita.

Cuando es necesario asignar memoria, es necesario recuperarla del primer bloque de memoria, verificando si el bloque de memoria está asignado y si se satisface el tamaño del bloque de memoria, hasta que se encuentre un bloque libre de tamaño adecuado. y asignado.

El principal problema con la lista enlazada implícita y la lista enlazada explícita mencionadas anteriormente es que cuando el número de bloques libres es n, la complejidad de recuperación está en el nivel O (n) y la velocidad es lenta. La lista enlazada de bloques libres jerárquicos está optimizada. La complejidad de la recuperación de bloques libres se calcula aproximadamente para reducirse al nivel O (log (n)).

La idea de diseño de Lista libre segregada es clasificar los bloques libres según su tamaño, formando clases con diferentes rangos de tamaño de bloque, y los bloques libres del grupo están vinculados mediante listas enlazadas. Durante cada asignación, primero se busca en la lista vinculada correspondiente de acuerdo con el rango de tamaño jerárquico y luego se recuperan uno por uno los bloques libres adecuados de la lista vinculada correspondiente. Si no se encuentran, la búsqueda se realiza en un nivel con un rango de tamaño mayor. hasta que se encuentre y asigne un bloque adecuado.

Arriba introdujimos el principio de la lista enlazada de bloques libres jerárquicos, pero no mencionamos cómo jerarquizar según el tamaño del bloque de memoria. El algoritmo TLSF introduce un mapa de bits para resolver este problema.

Cuando la lista jerárquica enlazada de bloques libres se encuentra con el mapa de bits, la estructura de administración de memoria dinámica cambia ligeramente. La siguiente imagen es bastante clara (es bueno si puede ver vagamente la sombra de la lista jerárquica enlazada de bloques libres: -PAG) .

TLSF utiliza un mapa de bits de dos niveles para gestionar listas de bloqueo libres de diferentes rangos de tamaño.

La imagen de arriba contiene tres cuadros rectangulares punteados:

Ahora que tenemos el concepto general del marco de TLSF, primero podemos echar un vistazo al breve proceso de asignación y liberación de memoria. (Los detalles se discutirán en la siguiente sección combinados con el código fuente)

Proceso de asignación de memoria

Proceso de liberación de memoria

Ya tenemos una comprensión general de la estructura de la memoria y el proceso de asignación y liberación, pero también hay un pequeño problema que no se explica:

La idea general es: para encontrar el bloque libre más pequeño que pueda cumplir con el tamaño de la solicitud de memoria, habrá el siguiente proceso (tomando como ejemplo la búsqueda de un bloque libre con un tamaño de 69 bytes)

Parece que Best-fit ya es muy bueno, pero todavía hay margen de mejora. El principal problema de la estrategia Best-fit radica en el tercer paso: todavía necesita recuperar la lista de bloques libres del rango correspondiente, lo que tiene una posible complejidad temporal.

La diferencia entre la idea Good-fit y Best-fit es que Good-fit no garantiza encontrar el bloque libre más pequeño que satisfaga la demanda, sino que sea lo más cercano posible al tamaño a asignar .

Tomando como ejemplo la búsqueda anterior de un bloque libre con un tamaño de 69 bytes, Good-fit no encuentra el rango [68 ~ 70], sino un rango ligeramente mayor que este rango (por ejemplo [71 ~ 73]). La ventaja de este diseño es que cada bloque en la cadena de bloques libre correspondiente a [71 ~ 73] puede satisfacer la demanda. No es necesario buscar en la lista de cadenas de bloques libres para encontrar el más pequeño. en la cadena de bloques libre directamente. En general, no causa demasiados escombros.

En esta sección, echamos un vistazo al código fuente de LiteOS y analizamos su estructura de datos y diseño de memoria.

Los bloques libres y los bloques usados ​​reutilizan la misma estructura de datos, pero no todos los campos se utilizan cuando se utilizan.

Consulte principalmente los dos blogs siguientes. Desde la instalación de eclipe, la configuración hasta la compilación y ejecución del proyecto, está bastante completo. No hay ningún problema en Mac, ¡pero eclipse está un poco atascado -_-!

Cómo instalar el entorno de desarrollo LiteOS en Windows 10 (1)

Cómo instalar el entorno de desarrollo LiteOS en Windows 10 (2)

Solo un recordatorio: