Simulador de asignación contigua

1. Qué vamos a simular

El simulador gestiona un mapa de memoria lineal dividido en unidades. Cada unidad puede estar libre o asignada a un bloque. Las operaciones son:

• Pedir (malloc): busca un hueco libre suficientemente grande según la estrategia elegida y lo asigna.
• Liberar (free): marca un bloque como libre, fusionándolo con huecos adyacentes (coalescing).
• Compactar: mueve todos los bloques al principio para unir los huecos.

El usuario controla el tamaño del bloque pedido, la estrategia y qué bloque liberar.

2. El programa de ejemplo

Este programa en C simula la asignación contigua con las tres estrategias y mide la fragmentación:

#include <stdio.h>
#include <stdlib.h>

#define MEM 64

typedef struct { int inicio, tam, libre; } Bloque;

Bloque mem[MEM];
int nmem = 1;  /* un bloque libre inicial */

void init(void) { mem[0].inicio = 0; mem[0].tam = MEM; mem[0].libre = 1; }

int buscar(int tam, int estrategia)
{
    int idx = -1, best = 9999, worst = -1;
    for (int i = 0; i < nmem; i++) {
        if (mem[i].libre && mem[i].tam >= tam) {
            if (estrategia == 0 && idx == -1) idx = i;          /* first fit */
            if (estrategia == 1 && mem[i].tam < best) { best = mem[i].tam; idx = i; }  /* best fit */
            if (estrategia == 2 && mem[i].tam > worst) { worst = mem[i].tam; idx = i; }  /* worst fit */
        }
    }
    return idx;
}

void asignar(int idx, int tam)
{
    if (mem[idx].tam > tam) {
        /* dividir el bloque */
        mem[nmem].inicio = mem[idx].inicio + tam;
        mem[nmem].tam = mem[idx].tam - tam;
        mem[nmem].libre = 1;
        nmem++;
        mem[idx].tam = tam;
    }
    mem[idx].libre = 0;
}

int main(void)
{
    init();
    int peds[] = {10, 5, 8, 6, 4};
    for (int e = 0; e < 3; e++) {
        init();
        printf("Estrategia %d:\\n", e);
        for (int i = 0; i < 5; i++) {
            int idx = buscar(peds[i], e);
            if (idx >= 0) { asignar(idx, peds[i]); printf("  pedir %d -> asignado\\n", peds[i]); }
            else printf("  pedir %d -> NO CABE\\n", peds[i]);
        }
    }
    return 0;
}

3. El mapa de memoria

El mapa se representa como una barra horizontal dividida en unidades. Cada unidad puede ser:

• Libre: color claro (hueco disponible).
• Asignada: color sólido (bloque de un proceso).

La barra muestra la fragmentación de un vistazo: muchos huecos pequeños entre bloques asignados indican fragmentación externa.

4. Pedir y liberar bloques

Al pedir un bloque, el simulador busca un hueco según la estrategia y lo divide si es mayor que el pedido. Al liberar, el bloque se marca como libre y se fusiona con los huecos adyacentes (coalescing) para evitar fragmentación artificial.

La compactación (opcional) mueve todos los bloques asignados al principio, uniendo todos los huecos en uno solo.

5. El simulador interactivo

Memoria de 64 unidades. Usa los controles para pedir bloques, liberarlos y cambiar la estrategia.

6. Qué observar

• Primer ajuste: rápido, pero los huecos se acumulan al principio.
• Mejor ajuste: deja huecos muy pequeños (inutilizables) al elegir el más ajustado.
• Peor ajuste: deja huecos grandes, pero desperdicia más espacio.
• Compactación: unifica todos los huecos en uno solo, eliminando la fragmentación externa.
• Coalescing: al liberar un bloque adyacente a huecos libres, se fusionan.

7. Limitaciones del simulador

Este simulador es una simplificación. No modela:

• Los metadatos del asignador (cabeceras).
• La reutilización real de bloques liberados en glibc.
• La concurrencia.
• El crecimiento dinámico de la memoria (brk).

8. En Linux hoy

Linux no usa asignación contigua para la memoria física (usa paginación), pero el asignador del heap (glibc) sí usa variantes de estas estrategias para elegir huecos libres. La compactación del heap (coalescing) se hace automáticamente al liberar bloques adyacentes.

9. Resumen

• La asignación contigua gestiona un mapa de memoria con bloques asignados y huecos libres.
• Pedir un bloque busca un hueco según la estrategia; liberar marca como libre y fusiona huecos adyacentes.
• La compactación une todos los huecos en uno solo.
• Cada estrategia (first/best/worst fit) produce distinta fragmentación.
• El asignador del heap de glibc usa variantes de estas estrategias.

10. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Pide bloques de 8, 4, 8, 4 unidades con primer ajuste y observa la fragmentación. Libera el segundo y el cuarto, y pide uno de 6. ¿Cabe?
2. Repite con mejor ajuste y peor ajuste. ¿Cuál deja menos huecos?
3. Usa la compactación y observa cómo se unifican los huecos.
4. Implementa en C la fusión de huecos adyacentes (coalescing) al liberar.
5. Compara la fragmentación con y sin coalescing tras 10 operaciones.
6. Investiga cómo glibc fusiona bloques libres adyacentes en el heap.
7. Dibuja un mapa con bloques de 5, 3, 8, 2 y huecos, y calcula si un bloque de 4 cabe con cada estrategia.