Adrianistán

El blog de Adrián Arroyo


¿Cómo funcionan los sistemas de archivos basados en FAT?

- Adrián Arroyo Calle

Voy a dedicar unas entradas en el blog a hablar del funcionamiento de los sistemas de archivos, un componente fundamental en la gran mayoría de sistemas informáticos. Voy a empezar con los basados en FAT sin centrarme en ninguno en concreto (FAT16, FAT32, exFAT,...). Intentaré escribir también sobre inodos y mecanismos más raros y avanzados.

En esencia un sistema de archivos es un método ordenado que permite guardar datos sobre un soporte físico para luego poder acceder a ellos. Históricamente ha habido muchos enfoques a este problema: los sistemas más usados usan archivos, directorios y enlaces.

Bloques y sectores: la división del disco


Esta parte es común a muchos sistemas de archivos, tanto FAT como inodos, como otros. A nivel físico los dipositivos están divididos. En el caso del disco duro, el dispositivo de almacenamiento más común, los discos se dividen en sectores de N bytes, según parámetros de la fabricación. Estos sectores cuentan con código de control de errores incorporado y todo ello es manejado por la controladora de disco que opera ajena al sistema operativo. Los sistemas de archivos dividen a su vez el disco en bloques. Es importante dejar claro que bloque no es igual a sector. El bloque es una división que hace el sistema de archivos y los sectores los hace la controladora de disco. Usualmente un bloque equivale a varios sectores, aunque la equivalencia real depende del sistema de archivos en concreto.

Algunos bloques especiales: boot y superbloque y raíz


Antes de entrar en el mecanismo específico de FAT es necesario comentar que en un disco existirán dos bloques de vital importancia ajenos a FAT. El primero es el bloque de boot o arranque (también llamado MBR). Normalmente situado en el sector 0 del disco duro, contiene código para iniciar el sistema operativo. El superbloque suele ser el bloque siguiente, contiene metadatos del sistema de archivos (por ejemplo, puede decir que usamos FAT con bloques de 32KiB, etc). Además en FAT es necesario que exista un fichero siempre, el fichero del directorio raíz.

Directorios


Los directorios o carpetas son archivos como otros cualquiera, solamente que en sus metadatos se indica que es un directorio y no un fichero corriente. Los ficheros de directorios son los encargados de almacenar los metadatos de los ficheros (paras saber si son ficheros, otros directorios, su fecha de modificación, propietario y tamaño entre otros) que se encuentran en el directorio así como una referencia al bloque.

Un fichero en FAT


Vamos al asunto. Supongamos que en un determinado bloque N tenemos un fichero. Este bloque es de 64 KiB. Si un fichero ocupa menos de 64 KiB, perfecto, todos los datos entran en el bloque. Simplemente ajustamos los metadatos de tamaño con el valor correcto y el resto del espacio que queda en el bloque queda inutilizado.

Este espacio perdido se denomina fragmentación interna y dependiendo de los datos que se almacenen en un disco duro, el porcentaje de pérdida puede ser mayor o menor. Evidentemente si tenemos bloques muy grandes y ficheros muy pequeños perderemos mucho espacio debido a la fragmentación interna. Tener bloques muy pequeños y ficheros muy grandes también es problemático pero por otros motivos.
Tipos de fragmentación

En un sistema de archivos existen 3 tipos de fragmentación: interna, externa y de datos. La interna se refiere al espacio perdido en bloques asignados a ficheros que no están llenos por completo. La externa se refiere al espacio que perdemos por no tener un espacio libre contiguo lo suficientemente grande como para guardar el fichero allí. Ningún sistema FAT o de inodos tiene fragmentación externa al usar todos bloques de tamaño predefinido. Por último la fragmentación de datos, o fragmentación a secas, se refiere a que los bloques asignados estén contiguos o no. Esto tiene implicaciones a nivel de rendimiento pero no al número de bytes que se vuelven inútiles como los otros dos tipos de fragmentación.

¿Pero qué pasa si el contenido de nuestro fichero no puede entrar en el tamaño de bloque? Aquí viene la gracia de FAT, la File-Allocation-Table. La FAT es una tabla compuesta por entradas que indican el siguiente bloque del archivo. La tabla está indexada por bloque y además de indicar cuál es el siguiente bloque del archivo también indica si el archivo acaba ahí o si ese bloque está libre y puede usarse para un archivo nuevo.

En la foto el archivo /home/user/hola.txt tiene una longitud menor al tamaño de bloque. Así que miramos en la FAT la entrada 150 y efectivamente comprobamos que no hay bloque siguiente ya que es un End-of-File.



Pongamos un ejemplo con un archivo largo. Cada celda de la tabla correspondiente al índice del bloque actual indica el siguiente bloque a leer. Estos bloques pueden estar en cualquier parte. Si en un disco duro muchos ficheros tienen los bloques muy dispersos, se dice que necesita ser desfragmentado.

Conclusiones


FAT es muy rápido si la tabla FAT consigue ser cargada en memoria, ya que obtener los datos necesarios de ella será muy rápido. Desgraciadamente, dependiendo del tamaño del disco duro y del tamaño de los bloques, esta tabla puede ocupar mucho y ser impráctico.

El mecanismo FAT como vemos es simple pero efectivo. Dispone de una fragmentación interna limitada y carece de fragmentación externa. Un inconveniente es que FAT cuando busca un archivo necesita empezar siempre desde el directorio raíz. Esto implica accesos cada vez más lentos a medida que vayamos haciendo carpetas, aunque con sistemas de caché se puede reducir.

El esquema FAT tampoco impone restricciones propiamente dichas al número archivos de un sistema ni a su tamaño. Sin embargo en la práctica suelen existir límites.

Edito: He explicado mejor que significa la fragmentación y sus tipos

Comentarios

rfog
Hola. Se te ha olvidado la tabla de particiones en el disco, que suele venir después del MBR (aunque también puede estar al final, o repartida por el disco si hay más de 4 particiones o es algún formato de los nuevos). Aparte de eso, cometes bastantes errores describiendo el sistema de archivos FAT. De hecho es uno de los que más fragmentación interna y externa tienen, y de hecho, a partir de cierto nivel de fragmentación y espacio ocupado, revientan. Y por eso está la segunda copia de la FAT, que es la solución que Microsoft encontró para "resolver" el problema, pero en general también termina reventando. Y el sistema FAT también tiene restricciones de tamaño, tanto de bloque como de entradas, ya que está limitado a 64K entradas de cualquier tipo, eso sin contar los límites de tamaño de archivo y partición.
aarroyoc
Hola rfog, El MBR sí lo he incluido, es lo que llamo "sector boot" pero no puse el término MBR porque siempre ha estado ligado a IBM PC y no es tan genérico. Por otro lado, respecto a la fragmentación. La fragmentación externa es el espacio que queda inútil en un disco por no tener suficiente tamaño para ser ocupado por el archivo que vamos a guardar. El esquema FAT demuestra claramente que no puede tener fragmentación externa, ya que todos los huecos disponibles son del mismo tamaño y hay que asociarlos de forma arbitraria para conseguir trozos más grandes. La fragmentación externa aparece únicamente en sistemas de archivos de tipo contiguo, incluyendo aquellos con extents como Veritas FS (no son muy habituales en PC de todos modos. En cuenta a fragmentación interna, es decir, espacio dentro del bloque asignado a un fichero pero que no se usa, la ratio es similar tanto los sistemas FAT como los basados en inodos y habría que irse a sistemas más avanzados para reducir este valor. Es cierto que la "fragmentación" de FAT es un problema pero realmente se trata de otro concepto. Cuando los bloques de FAT están muy dispersos se dice coloquialmente que FAT está fragmentado y efectivamente, supone graves penalizaciones en las lecturas y escrituras debido a los desplazamientos que tienen que hacer las cabezas dentro del disco. Sin embargo no me sientp cómodo llamando a esto fragmentación ya que no tiene que ver con la fragmentación interna y externa que en definitiva son problemas relativos al aprovechamiento del espacio y no tanto a su rendimiento. Las "soluciones" como la segunda copia no son solo de sistemas basados en FAT, si puedo entrar a fondo con los inodos en el siguiente post intentaré describir como existen soluciones similares en ext4 mismamente. Lo de que FAT esté limitado a 64k entradas es más un tema de la implementación en concreto que otra cosa, en este post no he querido centrarme en un sistema en concreto (FAT12, FAT16, FAT32, exFAT, FATX, FAT+,...) sino en las ideas fundamentales. De hecho FAT32 permite 268.173.300 entradas en la tabla usando bloques de 32 KiB. Para detalles más técnicos siempre está <a href="https://wiki.osdev.org/FAT" rel="nofollow">OSDev</a> Saludos!
Arturo
Gracias por la explicación, no todos tenemos conocimientos en la materia, y hacerlo sencillo y entendible no es nada fácil.
Mad Hatter
Interesante artículo. Aprovecho que editas el artículo para dejar constancia de un fallo cosmético: "ha medida" debería ser "a medida".
Jose
Muchas gracias por el post, muy interesante. Sólo decirte que quites la "h" de "ha medida". Gracias!
[&#8230;] de ver como funcionan de forma genérica los sistemas FAT, saltamos a los sistemas de inodos. Estos se han usado tradicionalmente en sistemas UNIX (UFS, [&#8230;]
aarroyoc
Corregido, gracias!

Añadir comentario

Todos los comentarios están sujetos a moderación