gestión de memoria inteligente con operaciones constantes en el tiempo?

Question

Vamos a considerar un segmento de memoria (cuyo tamaño puede aumentar o reducir, como un archivo, cuando sea necesario) sobre la que se pueden realizar dos operaciones básicas de asignación de memoria que implica bloques de tamaño fijo:

• asignación de un bloque
• liberando un bloque previamente asignado que no se usa más.

Además, como requisito, el sistema de gestión de memoria no se le permite moverse alrededor de los bloques asignados actualmente:. Su índice / dirección debe permanecer sin cambios

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

enfoque mejor:. Mantener el mostrador, pero mantener una lista de bloques desasignado (que se puede hacer en un tiempo constante) y usarlo como fuente para nuevas asignaciones, siempre y cuando no está vacío

¿Qué sigue? ¿Hay algo inteligente que se puede hacer, aún con las limitaciones de la asignación de tiempo constante y cancelación de asignación, que mantendría el segmento de memoria lo más corto posible?

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

Answer 1

Con los bloques de tamaño fijo, lo que se ha descrito es una lista libre . Esta es una técnica muy común, con la siguiente peculiaridad: la lista de bloques libres se almacena en los propios 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 y cuando todos los bloques asignados tienen el mismo tamaño, y que el tamaño es un múltiplo del tamaño de un puntero, por lo que la alineación se conserva. Asignación y desasignación son de constante de tiempo (es decir, tan constante en tiempo como accesos de memoria y adiciones elementales - en una computadora moderna, un acceso a memoria puede implicar errores de caché e incluso la memoria virtual, por lo tanto, los accesos al disco, por lo que la "constante de tiempo" puede ser bastante grande). No hay una sobrecarga de memoria (no extra por punteros de bloque o cosas por el estilo; los bloques asignados son contiguos). Además, el puntero de asignación alcanza un punto dado sólo si, al mismo tiempo, que muchos bloques tuvieron que ser asignados: ya que la asignación prefiere el uso de la lista libre, el puntero de la asignación se incrementa sólo si el espacio debajo del puntero actual es el reloj completo. En ese sentido, se trata de un óptima técnica.

La disminución el puntero de asignación después de la liberación puede ser más complejo, ya que los bloques libres se pueden identificar de forma fiable sólo siguiendo la lista libre, que pasa a través de ellos con el fin impredecible. Si la disminución del tamaño grande segmento cuando sea posible es importante para usted, usted podría querer usar una técnica alternativa, con más sobrecarga: entre dos bloques asignados, se pone un "agujero". Los agujeros están unidos entre sí con una lista doblemente enlazada, con el fin de memoria. Es necesario un formato de datos para un agujero de tal manera que se puede localizar la dirección de inicio agujero por saber dónde termina, y también el tamaño del agujero si se sabe dónde comienza el agujero en la memoria. Entonces, cuando se suelta un bloque, se crea un orificio que se fusionan con la siguiente y los agujeros anteriores, la reconstrucción (todavía en tiempo constante) la lista ordenada de todos los agujeros. La sobrecarga es entonces de dos palabras de tamaño de puntero por bloque asignado; pero, a ese precio, se puede detectar de forma fiable la aparición de un "hoyo final", es decir, una ocasión para disminuir el tamaño del segmento grande.

Hay muchas variaciones posibles. Un buen estudio introductorio es asignación de almacenamiento dinámico: un estudio y revisión crítica por Wilson et al.

Answer 2

Esta respuesta es acerca de las técnicas genéricas de gestión de memoria. Echaba de menos 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 de primer ajuste, al lado de ajuste, mejor ajuste, y el compañero sistema. Escribí un breve resumen una vez para un curso que enseñé, me espero que sea legible. Señalo allí para una bastante exhaustiva encuesta .

En la práctica verá diversas modificaciones de estas estrategias básicas. Pero ninguno de ellos es realmente constante de tiempo! No creo que eso sea posible en el peor de los casos, mientras que el uso de una cantidad limitada de memoria.

Answer 3

Es posible que desee echar un vistazo a amortizado análisis y en particular matrices dinámicas. Incluso si las operaciones no se hacen realmente en tiempo constante en cada paso, en el largo plazo parece que es el caso.