1. El problema: elegir el hueco
En particiones variables, cuando llega un proceso de tamaño n, el sistema busca un hueco libre de tamaño ≥ n. Si hay varios, ¿cuál elegir? La elección afecta a la fragmentación futura y al tiempo de búsqueda.
Las tres estrategias clásicas son:
- Primer ajuste: el primer hueco que quepa.
- Mejor ajuste: el hueco más pequeño que quepa.
- Peor ajuste: el hueco más grande.
2. Primer ajuste (first fit)
Se recorre la lista de huecos desde el principio y se usa el primero que sea suficientemente grande. Es la estrategia más simple y rápida.
- Ventaja: búsqueda rápida (se detiene al encontrar el primero).
- Inconveniente: los huecos pequeños al principio se fragmentan; los grandes al final se conservan.
3. Mejor ajuste (best fit)
Se recorre toda la lista de huecos y se elige el más pequeño que quepa. Deja los huecos más grandes para procesos futuros grandes.
- Ventaja: minimiza el desperdicio inmediato.
- Inconveniente: búsqueda lenta (recorre toda la lista); genera muchos huecos muy pequeños (inutilizables).
4. Peor ajuste (worst fit)
Se elige el hueco más grande. La idea es que el hueco restante sea lo suficientemente grande para ser útil.
- Ventaja: el hueco restante suele ser utilizable.
- Inconveniente: búsqueda lenta; desperdicia más espacio inmediatamente.
En la práctica, el peor ajuste es el menos usado.
5. Comparación
| Estrategia | Velocidad | Fragmentación | Uso típico |
|---|---|---|---|
| Primer ajuste | Rápida | Media | La más común en la práctica |
| Mejor ajuste | Lenta | Alta (muchos huecos pequeños) | Poco usada |
| Peor ajuste | Lenta | Media | Rara |
Estudios empíricos (Knuth) mostraron que el primer ajuste y el mejor ajuste producen resultados similares en fragmentación, pero el primer ajuste es mucho más rápido. Por eso el primer ajuste es el más usado.
6. La regla del 50 %
La regla del 50 % (50% rule) es un resultado empírico de Knuth: en promedio, con cualquiera de las estrategias, aproximadamente la mitad de la memoria libre está en forma de huecos inutilizables (fragmentación externa). Es decir, si hay 100 MiB libres, unos 50 MiB estarán en huecos demasiado pequeños.
Regla del 50 %: con asignación contigua, aproximadamente la mitad de la memoria libre se pierde en fragmentación externa, independientemente de la estrategia de ajuste.
Esta regla motiva la búsqueda de mejores esquemas (paginación, segmentación) que eliminen la fragmentación externa.
7. Compactación como remedio
La compactación (tema 12) une los huecos moviendo los procesos. Con primer/mejor/peor ajuste, la compactación se puede aplicar cuando la fragmentación es alta. El costo es el tiempo de mover los procesos y actualizar sus direcciones.
En la práctica, la compactación se evita mediante la paginación, que no requiere bloques contiguos.
8. Ejemplo numérico
Huecos libres: 10 MiB, 4 MiB, 20 MiB, 8 MiB. Llega un proceso de 6 MiB.
| Estrategia | Hueco elegido | Hueco restante |
|---|---|---|
| Primer ajuste | 10 MiB (primero que quepa) | 4 MiB |
| Mejor ajuste | 8 MiB (el más pequeño que quepa) | 2 MiB |
| Peor ajuste | 20 MiB (el más grande) | 14 MiB |
El mejor ajuste deja un hueco pequeño (2 MiB) que probablemente no será útil. El peor ajuste deja un hueco grande (14 MiB) utilizable. El primer ajuste es un compromiso.
9. Experimento en C
El programa siguiente simula las tres estrategias sobre una lista de huecos y un proceso nuevo:
#include <stdio.h>
int main(void)
{
int huecos[] = {10, 4, 20, 8}; /* MiB */
int n = 4;
int pedido = 6;
int first = -1, best = -1, worst = -1;
int bestSize = 9999, worstSize = -1;
for (int i = 0; i < n; i++) {
if (huecos[i] >= pedido) {
if (first == -1) first = i;
if (huecos[i] < bestSize) { bestSize = huecos[i]; best = i; }
if (huecos[i] > worstSize) { worstSize = huecos[i]; worst = i; }
}
}
printf("Pedido: %d MiB\\n", pedido);
printf("Primer ajuste: hueco %d (%d MiB) -> restante %d MiB\\n", first, huecos[first], huecos[first]-pedido);
printf("Mejor ajuste: hueco %d (%d MiB) -> restante %d MiB\\n", best, huecos[best], huecos[best]-pedido);
printf("Peor ajuste: hueco %d (%d MiB) -> restante %d MiB\\n", worst, huecos[worst], huecos[worst]-pedido);
return 0;
}$ gcc -std=c17 -Wall -Wextra -o ajuste ajuste.c
$ ./ajuste
Pedido: 6 MiB
Primer ajuste: hueco 0 (10 MiB) -> restante 4 MiB
Mejor ajuste: hueco 3 (8 MiB) -> restante 2 MiB
Peor ajuste: hueco 2 (20 MiB) -> restante 14 MiBPeor ajuste: hueco 2 (20 MiB) -> restante 14 MiB10. Probar con un simulador
Este simulador aplica las tres estrategias a una lista de huecos y un pedido. Cambia los huecos y el pedido, y observa qué hueco elige cada estrategia y cuánto sobra.
Simulador · estrategias de ajuste
| Estrategia | Hueco elegido (MiB) | Restante (MiB) |
|---|---|---|
| Primer ajuste | ||
| Mejor ajuste | ||
| Peor ajuste |
11. En Linux hoy
Linux no usa estas estrategias para la memoria física (usa paginación), pero sí para el heap del asignador (glibc). El asignador mantiene listas de huecos libres y usa variantes de first fit y best fit para elegir dónde colocar cada bloque. La compactación del heap (coalescing) se hace al liberar bloques adyacentes.
12. Resumen
- Primer ajuste: el primer hueco que quepa. Rápido, fragmentación media.
- Mejor ajuste: el hueco más pequeño que quepa. Lento, genera huecos pequeños.
- Peor ajuste: el hueco más grande. Lento, deja huecos grandes.
- La regla del 50 %: aproximadamente la mitad de la memoria libre se pierde en fragmentación externa.
- La compactación es el remedio: une los huecos moviendo procesos.
13. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es el primer ajuste?
La estrategia que usa el primer hueco libre suficientemente grande, recorriendo la lista desde el principio.
2. ¿Qué es el mejor ajuste?
La estrategia que elige el hueco más pequeño que pueda contener el proceso, recorriendo toda la lista.
3. ¿Qué es el peor ajuste?
La estrategia que elige el hueco más grande, para que el restante sea utilizable.
4. ¿Cuál es la más rápida?
El primer ajuste, porque se detiene al encontrar el primer hueco válido.
5. ¿Qué dice la regla del 50 %?
Que aproximadamente la mitad de la memoria libre se pierde en fragmentación externa, con cualquiera de las estrategias.
6. ¿Por qué el mejor ajuste genera muchos huecos pequeños?
Porque al elegir el hueco más ajustado, el resto es mínimo e inutilizable.
7. ¿Cuál es el remedio a la fragmentación externa?
La compactación: mover los procesos para unir los huecos.
8. ¿Se usan estas estrategias en Linux para la RAM física?
No para la RAM física (se usa paginación), pero sí para el heap del asignador de glibc.
Para practicar
- Modifica
ajuste.cpara implementar las tres estrategias sobre una lista de huecos y varios pedidos secuenciales. - Simula 100 pedidos aleatorios con cada estrategia y compara la fragmentación final.
- Implementa la compactación: dado un mapa con huecos, mueve los procesos para unir los huecos.
- Explica por qué el primer ajuste es el más usado en la práctica.
- Calcula la fragmentación con la regla del 50 % para 64 MiB de memoria libre.
- Investiga cómo glibc elige el hueco para un bloque del heap (first fit en bins).
- Dibuja un mapa con huecos de 5, 3, 8, 2 MiB y aplica las tres estrategias para un pedido de 4 MiB.