Escribiendo tu propio buen administrador de memoria

Buen día lector. Quizás ya haya leído mis artículos anteriores y sepa que estoy escribiendo mi propio sistema operativo. Hoy hablaremos y consideraremos un algoritmo simple y bastante rápido para administrar la memoria: el administrador de memoria es una parte crítica del sistema operativo, porque el trabajo rápido, confiable y sin desperdicio con la memoria es la clave para un buen sistema operativo.
Estaba buscando ideas simples y adecuadas para el gerente, tanto en Runet como en sitios en inglés, todavía no podía encontrar buenos artículos sobre un asignador adecuado, no un O (N). Bueno, hoy consideraremos una mejor idea para un administrador de memoria, puse la continuación en cat.

Teoría

De la wiki: Administrador de memoria: parte de un programa de computadora (tanto la aplicación como el sistema operativo) que procesa las solicitudes de asignación y liberación de RAM o (para algunas arquitecturas de computadora) las solicitudes para incluir un área de memoria determinada en el espacio de direcciones del procesador.

Sugiero también antes de continuar leyendo este artículo .

Asignador Watermak

Bueno, probablemente el más simple de todos los asignadores es Watermark Allocator. Su esencia es aproximadamente la siguiente: toda la memoria se divide en bloques, el bloque tiene un encabezado que contiene el tamaño de este y el bloque anterior, el estado del bloque (ocupado / libre), conociendo la dirección del bloque, podemos obtener la dirección del bloque siguiente y anterior para O (1).

Asignación de memoria

Para asignar memoria, simplemente necesitamos ejecutar los bloques y buscar un bloque cuyo tamaño sea mayor o igual que el tamaño de la memoria requerida para la asignación. Como ya entendió, el comportamiento asintótico de O (N) es malo.

Liberación de memoria

Para liberar memoria, es suficiente para nosotros establecer el estado del bloque como "libre" - O (1) - super!

Pero, como comprenderá, pueden comenzar a formarse agujeros en los que se desfragmentan 2 o más bloques libres, cuando se liberan, se pueden ver los bloques vecinos, y si uno o dos están libres, combínelos en uno.

Asignador logarítmico

Sabemos que necesitamos buscar solo entre bloques libres. Correr solo gratis mejora la velocidad en promedio dos veces, pero sigue siendo una línea. Bueno, ¿por qué deberíamos recorrer todos los bloques, buscando el tamaño, si podemos organizar un árbol a partir de bloques libres! Inicialmente, solo tenemos un bloque libre, y luego agregamos bloques libres al árbol de búsqueda binario, la clave será el tamaño del bloque. Por lo tanto, para asignar memoria, es suficiente para nosotros encontrar un bloque en un árbol cuyo tamaño sea mayor o igual a lo que necesitamos. Hacemos esto silenciosamente para O (log N), simplemente bajando del árbol. Además, cortamos el bloque en dos o se lo damos completamente al que solicitó la memoria. A continuación, eliminamos el bloque del árbol para O (1). Y, si es necesario, inserte el resto del bloque detrás de O (log N). Para el lanzamiento, solo necesitamos insertar el bloque de nuevo y no olvidarnos de la fragmentación.

Es lógico que no necesite usar un árbol simple, debe usar un árbol de equilibrio automático, Rojo-Negro o AVL. Puede almacenar el árbol de bloques en una matriz estática, o puede descubrir cómo hacerlo de manera diferente.

En realidad, el código:

char * malloc(size_t size) { if (!size) { return 0; } char * addr = 0; int i; for (i = 0; i < allocationAvlTree.size; ) { int r; node_t *n; n = &allocationAvlTree.nodes[i]; /* couldn't find it */ if (!n->key) { return NULL; } r = allocationAvlTree.cmp(n->key, size); if (r <= 0) { //We're lucky today. //Get memory block header alloc_t * block = (size_t)n->val - sizeof(alloc_t); //Set to used block->status = 1; //Set size block->size = size; alloc_t * next = (size_t)n->val + size; next->prev_size = size; next->status = 0; next->size = n->key - size - 16; avltree_remove(&allocationAvlTree, n->key, n->val); if (n->key - size - 16) avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t)); memset((size_t)block + sizeof(alloc_t), 0, block->size); block->signature = 0xDEADBEEF; unlockTaskSwitch(); return (size_t)block + sizeof(alloc_t); } else if (r > 0) i = __child_r(i); else assert(0); } return 0; } void free(void * mem) { if (!mem) return; //Get current alloc alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t)); if (alloc->signature != 0xDEADBEEF) return; alloc->status = 0; alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size); if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size) { //Merge blocks if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) { left->size += sizeof(alloc_t) + alloc->size; alloc = left; } else assert(0); } alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size; if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF) { if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t))) alloc->size += sizeof(alloc_t) + right->size; else assert(0); } avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t)); } 

¡Buena suerte y piratería ética! Cualquier crítica objetiva es bienvenida, el propósito del artículo no es decir que es algún tipo de asignador, sino simplemente hablar de un asignador que será mejor que implementaciones tontas de asignadores simples.