Sesión 13 · Estrategias de Asignación de Espacio y Estructura de Directorios

De la “carpeta llena” a entender cómo el SO reparte el disco.

Hoy estudiamos cómo el sistema operativo asigna bloques de disco a los archivos: asignación contigua, enlazada e indexada, y qué efectos tienen en el tiempo de búsqueda, la fragmentación y la eficiencia general de E/S.

Navegación: ← → para cambiar de diapositiva, Home / End para ir al inicio/fin, F pantalla completa.

Términos mínimos para analizar asignación de espacio

Bloque (o cluster): unidad mínima de asignación en disco. Si el bloque es de 4 KB, un archivo de 1 KB igual ocupa 1 bloque completo.
Fragmentación interna: espacio desperdiciado dentro del último bloque asignado a un archivo.
Fragmentación externa: espacio libre total suficiente, pero dividido en huecos pequeños no contiguos.
Acceso secuencial: lectura de bloques en orden; clave en archivos de video, logs y copias de respaldo.
Acceso aleatorio: lectura de posiciones salteadas; clave en bases de datos e índices.
Tiempo de acceso a disco (modelo simplificado): suma de posicionamiento del cabezal, espera de giro y transferencia de datos.

T_acceso ≈ T_busqueda + T_latencia + T_transferencia

Interpretación didáctica:
- T_busqueda (seek): mover cabezal a la pista correcta.
- T_latencia: esperar a que el sector deseado pase bajo el cabezal.
- T_transferencia: tiempo efectivo de lectura/escritura de bytes.

Resultado esperado: al finalizar, podrás justificar con criterio técnico y con cálculos básicos por qué una estrategia de asignación mejora o degrada el rendimiento según el patrón de acceso, el crecimiento del archivo y la ocupación del disco.

De “qué es un archivo” a “dónde vive en el disco”

En la Sesión 12 definimos archivo, atributos, tipos y directorios.
Sabemos que los datos se guardan en bloques o clusters de un dispositivo físico.
Falta responder: ¿cómo decide el SO qué bloques usar y en qué orden?
También falta responder: ¿cómo influye la estructura de directorios en la localización y administración de esos archivos?

Idea clave: diferentes estrategias de asignación producen patrones distintos de acceso al disco, lo que cambia el tiempo de búsqueda (seek time) y el rendimiento de E/S.

Estructura de directorios: por qué importa aquí

Un directorio no es una carpeta "mágica": es una estructura de datos que mapea nombre de archivo a metadatos.
Si la búsqueda en directorios es costosa, el sistema tarda más en llegar al primer bloque del archivo.
Una jerarquía profunda sin buena indexación aumenta accesos de metadatos antes de la lectura real de datos.
Conclusión: rendimiento final = costo de navegar directorios + costo de ubicar y leer bloques.

Definición e idea básica

El archivo se almacena en bloques consecutivos del disco.
La tabla de archivos guarda posición inicial y longitud (número de bloques).
Muy eficiente para lecturas secuenciales: una sola búsqueda inicial y luego lectura continua.

Ventaja fuerte: acceso aleatorio sencillo, porque el bloque i se calcula como direccion = inicio + i en términos de bloques lógicos.

Ejemplo rápido (bloques de 4 KB):
Archivo A = 40 KB → 10 bloques.
Si inicio = bloque 120, entonces A[0] está en 120 y A[9] en 129.

Acceso al bloque i:
direccion(i) = 120 + i

Problemas típicos

Fragmentación externa: difícil encontrar huecos grandes contiguos para archivos que crecen.
Requiere conocer o estimar el tamaño máximo del archivo al crearlo.
Costoso mover archivos grandes solo para “compactar” el disco.

Si hay huecos libres de 6, 8 y 12 bloques, un archivo nuevo de 20 bloques no cabe en forma contigua, aunque el espacio libre total sea 26 bloques. Este es el efecto clásico de fragmentación externa.

Definición e idea básica

Cada archivo es una lista enlazada de bloques dispersos en el disco.
Cada bloque contiene un puntero al siguiente bloque del archivo.
No requiere bloques contiguos, reduce la fragmentación externa.

Si queremos leer el bloque lógico i de un archivo enlazado:
1) Se lee el primer bloque.
2) Se sigue su puntero al segundo.
3) Se repite hasta llegar a i.

Costo aproximado de acceso aleatorio:
O(i) en número de saltos de puntero.

Ventajas y desventajas

Ventaja: fácil crecer archivos; basta con encontrar cualquier bloque libre y enlazarlo.
Desventaja: acceso aleatorio costoso; para llegar al bloque i hay que recorrer los anteriores.
Desventaja técnica: si se daña un puntero, se pierde el resto de la cadena.

Sistemas tipo FAT mejoran esto separando punteros en una tabla global, pero mantienen la idea de asignación enlazada.

Definición e idea básica

Cada archivo tiene un bloque índice que contiene una tabla con las direcciones de todos sus bloques.
Los bloques de datos pueden estar dispersos; el índice los referencia.
Permite acceso directo a cualquier bloque usando el índice.

Acceso al bloque lógico i en esquema indexado:
1) Leer bloque índice del archivo.
2) Obtener direccion_fisica = indice[i].
3) Leer bloque de datos en direccion_fisica.

Costo típico: 2 accesos (sin caché) o 1 acceso (si índice está en memoria).

Ventajas y consideraciones

Ventaja: acceso aleatorio eficiente y sin fragmentación externa severa.
Costo: se necesita espacio adicional para el bloque(s) índice y más lecturas si éste no está en caché.
Los sistemas de archivos modernos combinan índices directos, indirectos y estructuras jerárquicas (ej. i-nodos).

Resumen de estrategias e impacto en el rendimiento

Estrategia	Ventajas	Desventajas	Fragmentación
Contigua	Muy rápida para lectura secuencial. Cálculo simple de direcciones de bloque.	Dificultad para crecer archivos. Requiere huecos grandes contiguos.	Fuerte fragmentación externa; requiere compactación periódica.
Enlazada	Fácil crecimiento de archivos. Aprovecha huecos pequeños dispersos.	Acceso aleatorio lento. Riesgo si se corrompen punteros.	Minimiza fragmentación externa, pero puede aumentar tiempo de búsqueda por saltos.
Indexada	Acceso aleatorio eficiente. Gestión flexible de bloques dispersos.	Costo extra de bloques índice. Diseño más complejo.	Fragmentación manejable por el índice; buena base para sistemas modernos.

La elección de estrategia influye en el seek time promedio y en cuánta “basura” de fragmentación acepta el sistema antes de degradar el rendimiento percibido.

Modelo comparativo simplificado para leer N bloques:
Contigua: T ≈ 1*(T_busqueda + T_latencia) + N*T_transferencia
Enlazada: T ≈ N*(T_busqueda + T_latencia + T_transferencia)
Indexada: T ≈ (1 acceso índice) + N*(costo de datos)

Lectura didáctica:
- Contigua minimiza reposicionamientos.
- Enlazada incrementa saltos físicos.
- Indexada balancea flexibilidad y costo de metadatos.

Guía de decisión ingenieril (sin memorizar, con criterio)

Si el patrón dominante es secuencial y el tamaño del archivo es estable, contigua suele ofrecer mejor rendimiento bruto.
Si el archivo crece de forma impredecible, enlazada evita fallos de asignación por continuidad, a costa de acceso aleatorio más lento.
Si se requiere acceso aleatorio frecuente y buen equilibrio global, indexada es normalmente la opción más robusta.
La estructura de directorios debe evaluarse junto con la asignación: una mala organización de metadatos puede ocultar ventajas del método de bloques.
No existe método universalmente mejor: la decisión depende de carga de trabajo, tamaño medio de archivos y presión de espacio libre.

Checklist de análisis para un caso real:
1) ¿Predomina lectura secuencial o aleatoria?
2) ¿Los archivos crecen mucho después de creados?
3) ¿Cuál es el tamaño típico de archivo?
4) ¿Qué porcentaje del disco está ocupado?
5) ¿Se prioriza rendimiento o simplicidad de implementación?

Profundización inmediata

A continuación profundizaremos el análisis cuantitativo de fragmentación interna y del impacto del tamaño de bloque.
También compararemos el mismo caso de archivo bajo estrategias contigua, enlazada e indexada para medir costo de acceso.
Luego integraremos algoritmos de selección de huecos y estructura de directorios para completar la visión de rendimiento extremo a extremo.
Objetivo inmediato: pasar de definiciones a criterios de decisión reproducibles con cálculos simples.

Esta síntesis marca un punto de control conceptual antes de continuar con los bloques de profundización de la sesión.

Cómo medir fragmentación interna

Si el tamaño de bloque es B y el tamaño del archivo es S, bloques requeridos = ceil(S/B).
Espacio asignado = ceil(S/B) x B.
Fragmentación interna = ceil(S/B) x B - S.
Este desperdicio aparece incluso con asignación perfecta, porque el último bloque rara vez se llena al 100%.

Ejemplo:
B = 4096 bytes, S = 10 000 bytes
Bloques = ceil(10000/4096) = 3
Asignado = 3 x 4096 = 12 288 bytes
Desperdicio interno = 12 288 - 10 000 = 2 288 bytes

Implicación de ingeniería

Bloques grandes: menos metadatos y mejor transferencia secuencial, pero mayor desperdicio interno para archivos pequeños.
Bloques pequeños: menor desperdicio interno, pero más punteros, más entradas de metadatos y potencialmente más operaciones de E/S.
No existe tamaño de bloque perfecto para todos los escenarios; depende del perfil de carga del sistema.

Esta decisión afecta directamente el rendimiento percibido y el aprovechamiento total del almacenamiento.

Escenario base para comparar contigua, enlazada e indexada

Parámetro	Valor
Tamaño de bloque	4 KB
Tamaño del archivo	48 KB (12 bloques)
Operación de interés	Leer los bloques lógicos 0, 6 y 11
Estado del disco	70% de ocupación, huecos medianos dispersos

Resumen de costo esperado (sin caché):
- Contigua: acceso directo por fórmula direccion = inicio + i.
- Enlazada: para leer bloque 11 hay que seguir cadena desde el inicio.
- Indexada: leer índice + saltar al bloque físico indicado por indice[i].

Con una misma carga de trabajo, el costo no lo define solo el tamaño del archivo: lo define la combinación entre estrategia de asignación y patrón de acceso.

Estimación simple de costo por lectura

Contigua: 1 posicionamiento inicial + transferencia continua.
Enlazada: potencialmente un salto por cada bloque leído si hay dispersión física.
Indexada: costo inicial del índice y luego acceso directo a bloques de datos.

Si N = 12 bloques y queremos leerlos todos:
Contigua   -> ~1 búsqueda importante + 12 transferencias
Enlazada   -> ~12 búsquedas + 12 transferencias (peor caso)
Indexada   -> 1 lectura de índice + ~12 accesos a datos

Lectura crítica del modelo

El modelo no es exacto al milisegundo, pero permite justificar decisiones de diseño.
Para ingeniería de sistemas, esta aproximación es útil para comparar arquitecturas antes de medir en laboratorio.
Luego, en sistemas reales, se valida con métricas de throughput, latencia media y percentiles.

Un buen análisis combina teoría de costos y observación empírica, no solo intuición.

First Fit, Best Fit y Worst Fit (visión operativa)

Algoritmo	Regla de decisión	Ventaja	Riesgo
First Fit	Toma el primer hueco que alcance.	Rápido de ejecutar.	Puede dejar fragmentación irregular al inicio del disco.
Best Fit	Toma el hueco más pequeño que sea suficiente.	Reduce desperdicio inmediato por asignación.	Genera muchos huecos muy pequeños con el tiempo.
Worst Fit	Toma el hueco más grande disponible.	Tiende a dejar huecos medianos reutilizables.	Puede degradar rápidamente los huecos grandes.

Idea clave:
Estrategia de bloques + algoritmo de selección de huecos
= comportamiento final de fragmentación a mediano plazo.

Formas de organizar nombres y rutas

Nivel único: todos los archivos en un mismo espacio de nombres. Simple, pero poco escalable.
Dos niveles: separación básica por usuario; mejora orden, pero limita colaboración cruzada.
Árbol jerárquico: estructura dominante en sistemas modernos por su equilibrio entre claridad y escalabilidad.
Grafo acíclico: permite enlaces compartidos sin duplicar contenido, con mayor complejidad de gestión.

Relación con rendimiento

La operación "abrir archivo" no empieza leyendo datos; empieza resolviendo ruta en directorios.
Si la ruta tiene muchos niveles, pueden aumentar accesos a metadatos.
Estructuras indexadas de directorio reducen tiempo de búsqueda por nombre.
Buen diseño de directorio reduce latencia percibida incluso sin cambiar la estrategia de bloques.

Secuencia lógica para resolver una ruta

Ruta ejemplo: /proyectos/so/unidad2/informe.pdf

1) Leer metadatos del directorio raíz.
2) Buscar entrada "proyectos".
3) Cargar metadatos de "proyectos".
4) Buscar entrada "so".
5) Repetir hasta "informe.pdf".
6) Obtener referencia al archivo y su esquema de bloques.

Cada paso puede implicar E/S adicional si la información no está en caché.

Conclusión operativa

Parte del tiempo de acceso no está en los datos del archivo, sino en encontrarlo.
Por eso se estudian juntas la asignación de espacio y la estructura de directorios en esta misma unidad temática.
Ambas capas participan en la latencia final de abrir, leer y actualizar archivos.
Diseñar bien una sola capa no compensa por completo una mala decisión en la otra.

Qué estrategia favorece cada escenario

Escenario	Patrón dominante	Estrategia más conveniente	Justificación breve
Video y respaldos masivos	Lectura secuencial larga	Contigua (si hay espacio suficiente)	Minimiza reposicionamientos y favorece throughput.
Archivos que crecen continuamente	Escritura incremental	Enlazada o híbrida	Evita fallos por falta de continuidad física.
Consultas con saltos frecuentes	Acceso aleatorio	Indexada	Permite localizar bloques sin recorrer toda la cadena.
Sistemas de propósito general	Mixto y variable	Esquemas indexados/híbridos	Balancean rendimiento, crecimiento y mantenibilidad.

Criterio universitario esperado: no elegir por memoria mecánica, sino justificar con patrón de acceso, costo de metadatos y comportamiento de fragmentación.

Lo que ya queda cubierto con claridad

Definición y operación de asignación contigua, enlazada e indexada.
Diferencia entre fragmentación interna y externa.
Modelos matemáticos básicos de costo para comparar rendimiento.
Relación entre directorios, metadatos y tiempo total de acceso a archivo.
Criterios de decisión según escenarios reales de uso.

Estructura lógica final de la sesión:
Fundamentos -> Modelos de asignación -> Costo de E/S
-> Fragmentación -> Directorios -> Decisión técnica
-> Puente directo a sistemas reales (Sesión 14)

Preparación intelectual para la Sesión 14

Cuando aparezcan FAT, NTFS, Ext y HFS+, ya tendrás criterios para comparar diseño y no solo definiciones.
Podrás identificar qué parte del rendimiento depende del manejo de bloques y qué parte depende de metadatos/directorios.
También podrás analizar por qué el journaling mejora recuperación sin asumir que mejora todo rendimiento.

Con esto, la sesión queda completa, progresiva y alineada con los objetivos académicos de la unidad.