11  Unidad 5, sesión 2: Implementación física de archivos

Introducción: ¿Dónde se guardan realmente los bytes?

En la Sesión 1, establecimos que un archivo es una abstracción. Ahora, en la Sesión 2, vamos a responder: ¿cómo se almacenan y organizan físicamente esos bytes en un dispositivo?

El disco es como una estantería dividida en casilleros de tamaño fijo llamados bloques. La estrategia del SO para decidir en qué bloques pone el contenido de cada archivo se conoce como método de asignación de espacio.

11.1 Métodos de asignación de espacio

11.1.1 Asignación contigua 📏

Todos los bloques de un archivo se almacenan en una secuencia de bloques adyacentes.

Diagrama de asignación contigua

El directorio guarda: archivo.txt: Inicia en bloque 1, longitud 4.

Bloque 0 Bloque 1 Bloque 2 Bloque 3 Bloque 4
Libre archivo.txt archivo.txt archivo.txt archivo.txt
  • Ventajas: Acceso muy rápido.
  • Desventajas: Sufre de fragmentación externa y los archivos no pueden crecer fácilmente.
  • Uso: Ideal para medios de solo lectura como CD-ROMs.

11.1.2 Asignación enlazada ⛓️

Los bloques de un archivo están dispersos y cada uno contiene un puntero al siguiente.

Diagrama de asignación enlazada

Directorio: archivo.txt -> Inicia en Bloque 1.

Bloque 1 (-> B4) … Bloque 4 (-> NULL)
archivo.txt … archivo.txt
  • Ventajas: Cero fragmentación externa, crecimiento flexible.
  • Desventajas: Acceso directo muy lento, poca fiabilidad si un puntero se daña.
  • Uso: Base del sistema de archivos FAT.

11.1.3 Asignación indexada 📇

Un bloque de índice contiene la lista de todos los bloques de datos del archivo.

Diagrama de asignación indexada

Directorio: archivo.txt -> Bloque de Índice 20.

Disco: * Bloque 20 (Índice): [1, 4, 8, 9] * Los bloques de datos (1, 4, 8, 9) están dispersos.

  • Ventajas: Soporta acceso directo rápido y no sufre de fragmentación externa.
  • Desventajas: Overhead del bloque de índice.
  • Uso: Base de los sistemas modernos: NTFS, ext4, APFS.

11.2 2. Gestión del espacio libre

Ya sabemos las estrategias para organizar los bloques de un archivo. Ahora, enfrentamos una pregunta igual de importante: ¿cómo sabe el sistema de archivos cuáles de los millones de bloques en un disco están libres y cuáles ya están en uso?

Para gestionar esto, el sistema de archivos debe mantener una lista o registro de todos los bloques libres. Las dos técnicas más conocidas para lograrlo son el mapa de bits y la lista enlazada.

11.2.1 2.1. Mapa de bits (Bitmap)

Es la técnica más común y visual utilizada en sistemas de archivos modernos como ext4 y NTFS.

  • Concepto: Consiste en un vector o array de bits, donde cada bit representa un bloque del disco. La correspondencia es directa: el primer bit representa al bloque 0, el segundo al bloque 1, y así sucesivamente.

  • Funcionamiento: Se establece una convención simple:

    • 0: El bloque está libre.
    • 1: El bloque está ocupado.

    Cuando el sistema necesita asignar un bloque, busca un 0 en el mapa. Al asignarlo, cambia ese bit a 1. Cuando borra un archivo, los bits correspondientes a los bloques liberados vuelven a ser 0.

Ejemplo de un mapa de bits

Imaginemos un disco simple con 16 bloques. Su mapa de bits podría ser:

1110100111010011

  • Análisis: Al leer este mapa, el SO sabe instantáneamente que los bloques 3, 5, 6, 10, 12 y 13 están disponibles para ser usados.
  • Búsqueda: Si se necesita crear un archivo que requiere 2 bloques contiguos, el SO escanearía el mapa y encontraría rápidamente la secuencia 00 en las posiciones 5 y 6.
  • Ventajas:
    • Simplicidad y eficiencia: Es relativamente simple de implementar y es muy eficiente para encontrar bloques libres, especialmente si se necesitan bloques contiguos.
  • Desventajas:
    • Consumo de espacio: Aunque eficiente, el mapa de bits consume espacio. Para un disco grande, el mapa puede llegar a ser considerable. Por ejemplo, para un disco de 4 TB con bloques de 4 KB, el mapa de bits ocuparía 128 MB. Sin embargo, con la cantidad de RAM actual, mantenerlo en memoria no suele ser un problema.

11.2.2 2.2. Lista enlazada

Esta técnica organiza todos los bloques libres del disco como si fueran un único archivo, usando una lista enlazada.

  • Concepto: Todos los bloques libres están encadenados. Un puntero en una zona especial del disco (a veces llamada “superbloque”) apunta al primer bloque libre. Este bloque, a su vez, contiene un puntero que apunta al siguiente bloque libre, y así hasta el último, que tiene un puntero nulo.

  • Funcionamiento:

    • Asignación: Para asignar un bloque, el SO simplemente toma el primer bloque de la lista y modifica el puntero de la cabecera para que apunte al segundo. Es una operación muy rápida.
    • Liberación: Cuando un bloque se libera, se añade al principio de la lista de bloques libres.
Ejemplo de una lista enlazada de espacio libre

Usando los mismos bloques libres del ejemplo anterior (3, 5, 6, 10, 12, 13):

Puntero inicial -> [Bloque 3]

  • El bloque 3 contiene los datos “basura” y un puntero al siguiente bloque libre: [Bloque 5].
  • El bloque 5 contiene un puntero al [Bloque 6].
  • …y así sucesivamente hasta el [Bloque 13], que contendría un puntero NULL.
  • Ventajas:
    • No desperdicia espacio: No se necesita una estructura de datos separada (como el mapa de bits), ya que la información de la lista se guarda en los propios bloques libres.
  • Desventajas:
    • Ineficiencia: Aunque obtener un solo bloque libre es rápido, las operaciones se vuelven muy lentas si se necesita más de uno. Para obtener n bloques, hay que seguir la cadena n veces. Es especialmente malo para encontrar bloques contiguos, ya que requeriría recorrer gran parte de la lista.