Gestión de Memoria: Técnicas con Bloques Marcados y División Fija

4 Estructura de Bloques Marcados

Estructura de los bloques: La zona de datos incluye la zona libre y los enlaces.

Alojamiento

Admite las mismas estrategias que la estructura simple.

Desalojo

1. Bloques anterior y posterior ocupados: Se marca el bloque como libre y se asignan los enlaces para insertar el bloque al comienzo de la lista de bloques libres.
2. Bloque anterior libre y posterior ocupado: Se amplía el bloque anterior uniéndole el bloque a liberar. Los valores de los enlaces corresponden a los del bloque anterior (ahora ampliado).
3. Bloque anterior ocupado y posterior libre: Se amplía el bloque posterior uniéndole el bloque a liberar. Los valores de los enlaces corresponden a los del bloque posterior (ahora ampliado y reposicionado lógicamente).
4. Bloques anterior y posterior libres: Se extrae el bloque posterior de la lista de libres (actualizando los enlaces correspondientes). Se amplía el bloque anterior con el espacio del bloque a liberar y el del bloque posterior. Los enlaces son los correspondientes al bloque anterior (ahora ampliado).

5 Estructura de División Fija

Solo admite bloques de ciertos tamaños predefinidos y mantiene listas doblemente enlazadas para cada uno de los tamaños disponibles.

Tamaños Disponibles

Se definen generalmente mediante series:

• Bytes de control (C): Información necesaria en cada bloque (estado libre/ocupado, tamaño, código de división, enlaces).
• Serie de Fibonacci: F_n = F_n-1 + F_n-2 + C.
• Serie de división binaria (Buddy System): F_n = F_n-1 + F_n-1 + C (tamaños potencia de 2).

Alojamiento

• Dada una petición de tamaño L, buscar el tamaño F_n en la serie que sea igual o inmediatamente superior (F_n-1 < L <= F_n).
• Si no hay bloques libres de tamaño F_n, buscar el primer bloque disponible de tamaño mayor (F_m, donde m > n).
• Si se encuentra un bloque F_m > F_n, dividir recursivamente el bloque F_m en subbloques ("compañeros" o "buddies") siguiendo la serie (binaria o Fibonacci) hasta obtener un bloque de tamaño F_n. Actualizar los enlaces para mantener las listas de libres de cada tamaño.
• Cada vez que se divide un bloque, se marca adecuadamente cada subbloque (por ejemplo, con un código de división o identificando si es izquierdo/derecho).

Desalojo

• Marcar el bloque como libre.
• Determinar el tamaño del bloque liberado y buscar su bloque "compañero" (el otro bloque resultante de la división que los originó). La forma de encontrarlo depende de si es un bloque izquierdo o derecho y de la serie utilizada (binaria o Fibonacci).
• Si el bloque compañero también está libre, fusionar ambos bloques para formar el bloque original de mayor tamaño del que provenían.
• Repetir el proceso de fusión hacia arriba (con el nuevo bloque fusionado y su compañero) hasta que el compañero esté ocupado o se alcance el tamaño máximo.
• Actualizar los enlaces de las listas de libres a medida que se realizan las operaciones de liberación y fusión.