¿Gestión inteligente de la memoria con operaciones de tiempo constante?

18

Consideremos un segmento de memoria (cuyo tamaño puede crecer o reducirse, como un archivo, cuando sea necesario) en el que puede realizar dos operaciones básicas de asignación de memoria que involucran bloques de tamaño fijo:

  • asignación de un bloque
  • liberando un bloque previamente asignado que ya no se usa.

Además, como requisito, el sistema de administración de memoria no puede moverse alrededor de los bloques asignados actualmente: su índice / dirección debe permanecer sin cambios.

El algoritmo de administración de memoria más ingenuo incrementaría un contador global (con valor inicial 0) y usaría su nuevo valor como dirección para la próxima asignación. Sin embargo, esto nunca permitirá acortar el segmento cuando solo quedan unos pocos bloques asignados.

Mejor enfoque: mantenga el contador, pero mantenga una lista de bloques desasignados (que se puede hacer en tiempo constante) y úselo como fuente para nuevas asignaciones siempre que no esté vacío.

¿Qué sigue? ¿Hay algo inteligente que se pueda hacer, aún con restricciones de asignación de tiempo constante y desasignación, que mantenga el segmento de memoria lo más corto posible?

(Un objetivo podría ser rastrear el bloque no asignado actualmente con la dirección más pequeña, pero no parece ser factible en tiempo constante ...)

Stéphane Gimenez
fuente
¿la comprobación de una lista ya no sería de tiempo constante, ya que la lista podría crecer o reducirse debido a algunas asignaciones / dislocaciones realizadas anteriormente?
Sim
@ Sim, estaba asumiendo que es una lista vinculada y con ella las operaciones serían , porque siempre trabajas solo con la cabeza. O(norte)
svick
Creo que su "mejor enfoque" ya utilizará una cantidad óptima de memoria, es decir, nunca asignará memoria adicional si hay un bloque libre. ¿Cómo imagina que el enfoque "inteligente" mejoraría en eso? ¿Quiere decir que debería asignarse cerca del principio para que haya una mayor probabilidad de que pueda reducir el segmento después de las desasignaciones?
svick
@Sim: Lo siento, tal vez debería haber usado el término stack (pero pensé que podría ser confuso), 'deallocate' es push y 'allocate' es pop, o en el caso de que falle, simplemente retroceda al incremento del contador. Ambos son tiempo constante.
Stéphane Gimenez
¿Tiene restricciones de tiempo real o está bien con el tiempo constante amortizado? Es probable que las respuestas sean bastante diferentes.
Gilles 'SO- deja de ser malvado'

Respuestas:

11

Con bloques de tamaño fijo, lo que ha descrito es una lista gratuita . Esta es una técnica muy común, con el siguiente giro: la lista de bloques libres se almacena en los bloques libres. En el código C, se vería así:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

Esto funciona bien siempre que todos los bloques asignados tengan el mismo tamaño, y ese tamaño es un múltiplo del tamaño de un puntero, de modo que se conserva la alineación. La asignación y la desasignación son de tiempo constante (es decir, tan constante como el acceso a la memoria y las adiciones elementales; en una computadora moderna, el acceso a la memoria puede implicar errores de caché e incluso memoria virtual, por lo tanto, accesos al disco, por lo que el "tiempo constante" puede ser bastante grande) No hay sobrecarga de memoria (no hay punteros adicionales por bloque o cosas por el estilo; los bloques asignados son contiguos). Además, el puntero de asignación alcanza un punto dado solo si, en un momento, se tuvieron que asignar muchos bloques: dado que la asignación prefiere usar la lista libre, el puntero de asignación se incrementa solo si el espacio debajo del puntero actual está lleno de reloj. En ese sentido, técnica.

Decrecienteel puntero de asignación después de un lanzamiento puede ser más complejo, ya que los bloques libres se pueden identificar de manera confiable solo siguiendo la lista libre, que los revisa en un orden impredecible. Si es importante para usted reducir el tamaño del segmento grande cuando sea posible, puede usar una técnica alternativa, con más sobrecarga: entre dos bloques asignados, coloca un "agujero". Los agujeros están vinculados entre sí con una lista doblemente vinculada, en orden de memoria. Necesita un formato de datos para un agujero de manera que pueda localizar la dirección de inicio del agujero sabiendo dónde termina, y también el tamaño del agujero si sabe dónde comienza el agujero en la memoria. Luego, cuando liberas un bloque, creas un agujero que fusionas con el siguiente y el anterior, reconstruyendo (aún en tiempo constante) la lista ordenada de todos los agujeros. La sobrecarga es entonces de aproximadamente dos palabras de tamaño de puntero por bloque asignado; pero, a ese precio, puede detectar de manera confiable la aparición de un "agujero final", es decir, una ocasión para disminuir el tamaño del segmento grande.

Hay muchas variaciones posibles. Un buen artículo introductorio es Dynamic Storage Allocation: A Survey and Critical Review de Wilson et al.

Thomas Pornin
fuente
44
¿Cómo encuentra los agujeros más cercanos a un sitio de desasignación en tiempo constante?
Raphael
1
En el segundo método que describo, un agujero es un encabezado (un par de punteros, para la lista de agujeros) junto con espacio para cero, uno o más bloques de datos. Entre cualquiera de los dos bloques asignados, siempre hay un agujero, incluso si es un microagujero que consta de solo un encabezado de agujero. Por lo tanto, localizar los agujeros más cercanos es fácil: están justo antes y justo después de la ranura. Por supuesto, los microagujeros no forman parte de la lista gratuita (la lista de agujeros elegibles para la asignación). Otra forma de verlo es que agrega un encabezado a cada bloque y a cada agujero (no micro) (la asignación bajo Ms-Dos de 16 bits funcionó así).
Thomas Pornin
4

Esta respuesta es sobre técnicas genéricas de administración de memoria. Olvidé que la pregunta se refiere al caso en el que todos los bloques tienen el mismo tamaño (y están alineados).


Las estrategias básicas que debe conocer son el primer ajuste, el siguiente ajuste, el mejor ajuste y el sistema de compañeros . Escribí un breve resumen una vez para un curso que impartí, espero que sea legible. Señalo allí una encuesta bastante exhaustiva .

En la práctica, verá varias modificaciones de estas estrategias básicas. ¡Pero ninguno de estos es un tiempo realmente constante! No creo que sea posible en el peor de los casos, mientras se usa una cantidad limitada de memoria.

rgrig
fuente
Interesante, tengo que leer esto en detalle. Sin embargo, parece que estos sistemas tratan específicamente con asignaciones de tamaño no constantes, lo cual no es un problema al que me enfrento.
Stéphane Gimenez
Correcto. Lo siento, leí demasiado rápido tu pregunta.
rgrig
O(lgnorte)
s / bloque libre más pequeño / bloque libre en la dirección más pequeña /
rgrig
2

Es posible que desee echar un vistazo al análisis amortizado y, en particular, a las matrices dinámicas. Incluso si las operaciones no se realizan realmente en tiempo constante en cada paso, a la larga parece ser el caso.

gallais
fuente
2
¿Y cómo ayudarán exactamente las matrices dinámicas a la asignación de memoria?
svick
¿(Des) asignaría trozos de celdas contiguas utilizando el mismo tipo de algoritmo? Su archivo completo sería una lista vinculada de fragmentos cada vez más grandes.
gallais