Sistemas de archivos — teoría con la carpeta de tu práctica de IC2, FAT, i-nodos y enlaces (y el pendrive que no quiso el vídeo de la defensa)

La noche antes de defender la práctica de IC2 quise llevarme todo en un pendrive: la carpeta de la práctica y la grabación del ensayo, un vídeo de 4,3 GB. El pendrive tenía 20 GB libres. Arrastro, espero… y Windows me suelta: «El archivo es demasiado grande para el sistema de archivos de destino». ¿Demasiado grande? ¡Si sobraban 15 GB!

El problema no era el espacio, era cómo guardaba los archivos ese pendrive. Venía formateado en FAT32, y FAT32 apunta el tamaño de cada archivo en un campo de 32 bits: como mucho 2^32 − 1 = 4 294 967 295 bytes. Mi vídeo tenía 4 300 000 000. Le sobraban 5 MB para ser imposible. Lección: lo que puedes guardar no depende solo de los gigas libres, sino de la estructura que el sistema operativo monta encima del disco.

Este es el último tema de la teoría de IC2 (el bloque T6, archivos). En Memoria virtual viste cómo el SO hace que la RAM parezca más grande usando el disco; hoy toca lo que vive en ese disco: qué es un archivo, cómo lo ves tú (nombres, carpetas, enlaces) y cómo lo guarda el SO por dentro (bloques, FAT, i-nodos). El ejemplo guía es la carpeta de la práctica de IC2 en el portátil: practica.c, Makefile, datos.csv e informe.pdf. Al final tienes un simulador en Python y, después, los ejercicios tipo examen.

Del disco de bloques al archivo

El almacenamiento secundario (discos, SSD, pendrives, tarjetas) es más barato y más lento que la RAM, pero no es volátil: lo que guardas sigue ahí al apagar. Ahí van los programas, tus documentos, las copias de seguridad y hasta la zona de intercambio de la memoria virtual.

El núcleo ve cualquier dispositivo de almacenamiento como algo muy simple: un array de bloques de tamaño fijo, numerados desde 0. Para escribir, algo del estilo de write_block(42, datos). ¿Te imaginas guardar tu práctica así? «Lee los bloques 357, 48 y 13 y júntalos». Nadie trabaja de esa forma: nosotros pensamos en documentos, fotos, programas.

Por eso el SO ofrece una abstracción más cercana a lo que tú manejas, el archivo (o fichero, file):

Lo curioso es que el mismo archivo es una cosa distinta según quién lo mire. Fíjate en el dibujo con informe.pdf:

• Para ti (el usuario): una estructura de datos duradera, un documento con su nombre.
• Para la interfaz de llamadas al sistema: una colección de bytes. A read() le da igual si es un PDF o una canción (así lo ve Unix).
• Para el núcleo: una colección de bloques, la unidad lógica de transferencia, que es mayor que un sector del disco.

Atributos, directorio y «sistema de archivos»

Los atributos de un archivo

Además del contenido, cada archivo lleva una ficha con sus características. Los atributos que debes saberte son siete:

Atributo	Qué guarda	En informe.pdf
Nombre	La cadena con la que lo identificas	informe.pdf
Tipo	Necesario en los sistemas que distinguen tipos	PDF
Localización	Dónde están sus bloques en el dispositivo	depende de la asignación (lo verás más abajo)
Tamaño	Cuántos bytes tiene	18 000 B
Protección	Quién puede hacer qué	sergio lee y escribe, laura solo lee
Fechas y horas	Creación, modificación, último acceso	—
Versión	En los sistemas que guardan historial	—

Cada SO decide su conjunto de atributos y sus límites (por ejemplo, la longitud máxima del nombre… o el tamaño máximo, como le pasó a mi vídeo).

El directorio: el índice del disco

Cuando abres informe.pdf, ¿cómo sabe el SO que existe y dónde está? Con el directorio (o tabla de contenidos): una estructura con el catálogo de archivos. Cada entrada guarda los atributos de un archivo y su localización. Y ojo: el directorio también vive en el disco (si acaso, con una copia en RAM mientras se usa).

En el dibujo, el directorio dice que practica.c empieza en el bloque 2, Makefile en el 7, datos.csv en el 8 e informe.pdf en el 12. La diferencia que piden en examen: el archivo es el grupo de bloques que el usuario ve como una secuencia; el directorio es la estructura de nombres que el usuario ve.

Las dos caras de «sistema de archivos»

La expresión tiene dos significados, y en el test te pueden pedir los dos:

1. El módulo del sistema operativo que ofrece todo lo relacionado con archivos y directorios.
2. La estructura de información que se crea en el almacenamiento secundario para guardarlos (lo que haces al formatear: ext4, NTFS, FAT32…).

Operaciones sobre archivos

Las operaciones básicas son seis:

1. Crear un archivo (y su entrada de directorio).
2. Escribir.
3. Leer.
4. Reposicionar: mover la posición actual dentro del archivo sin leer ni escribir.
5. Borrar: desaparecen la entrada y el contenido.
6. Truncar: se borra solo el contenido; el archivo y sus atributos se quedan.

La diferencia entre las dos últimas cae mucho:

Abrir y cerrar: no ir al directorio cada vez

Casi todas las operaciones necesitan los atributos y la localización del archivo. Si en cada read() el SO tuviera que buscar el nombre en el directorio del disco, iría lentísimo. La solución:

• Abrir un archivo guarda en memoria principal su información de control.
• Cerrar libera esos recursos de la memoria.

En Unix, cada proceso tiene una tabla de archivos abiertos, y el descriptor que devuelve open() no es más que el índice de la entrada reservada para ese archivo (si ya programaste con llamadas al sistema en C, es el famoso fd):

¿Por qué sale 3? Porque 0, 1 y 2 ya están ocupados por la entrada estándar, la salida estándar y la de errores.

Tipos de archivo

¿Cómo sabe el SO si un archivo es una foto o un programa?

• Windows: por las últimas letras del nombre, la extensión (.pdf, .exe).
• Unix: el SO no reconoce tipos; para él todo son bytes (son los programas los que interpretan el contenido).
• Mac (versiones antiguas): unos atributos marcaban el tipo.

Pero hay uno que todos tienen que reconocer: el archivo ejecutable, porque el SO tiene que saber cargarlo y ponerlo en marcha.

Métodos de acceso

Una vez abierto, ¿cómo recorres los bloques del archivo? Hay tres métodos:

• Secuencial — «el archivo es una cinta»: lees o escribes a partir de donde te quedaste y la posición avanza sola; solo puedes avanzar o volver atrás (rebobinar). Es el modelo básico de Unix y Windows: open → read → read → ….
• Directo — «el archivo es un array de bloques»: cada operación dice a qué posición quiere ir. En Unix se hace con lseek(), que mueve la posición antes del siguiente read().
• Indexado (ISAM) — «el archivo es una tabla de una base de datos»: los registros están ordenados por una clave y buscas por ella (o por número de orden).

En el indexado, el SO mantiene uno o varios archivos índice ocultos para que la búsqueda sea rápida y cada escritura mantenga el orden. Lo tenían sistemas antiguos (IBM OS/360, OpenVMS); hoy esto se hace fuera del núcleo, en las bases de datos.

Método	Cómo llegas al dato	Ejemplo
Secuencial	Siguiendo desde donde te quedaste	leer datos.csv línea a línea
Directo	Diciendo la posición (lseek)	saltar al bloque 6 de un vídeo
Indexado	Por el valor de una clave	buscar a «Ruiz» en una lista de notas

Directorios: de un cajón a un árbol con atajos

Un directorio es una tabla de nodos con información sobre los archivos, y tanto los directorios como los archivos residen en memoria secundaria. Sobre un directorio se puede: buscar un archivo por nombre, listar, crear un archivo (vacío), eliminar, renombrar, copiar o mover a otro directorio y recorrer el sistema de archivos.

Lo interesante es cómo se organizan. Hay cinco modelos, de más simple a más general: nivel único → dos niveles → árbol → grafo acíclico → grafo general.

1. Nivel único

Todos los archivos en un único directorio principal (la volume table of contents):

Problemas: no se adapta a varios usuarios (conflictos de nombres, permisos) y, con muchos archivos, cada búsqueda es más lenta.

2. Dos niveles

El directorio principal (directorio maestro) no tiene archivos, solo un subdirectorio por usuario (o por aplicación, o para el sistema):

Ventajas: mejor organización, permisos por directorio y sin conflictos de nombres. Además aparece el concepto de ruta (path): sergio:practica.c.

3. Árbol

La generalización: un directorio puede contener archivos y otros directorios, todo lo hondo que quieras. Es lo que usas cada día:

• La ruta (pathname) localiza un objeto en el árbol. La absoluta sale de la raíz: /home/sergio/ic2/practica/informe.pdf.
• El directorio de trabajo es donde «estás»; desde él puedes usar una ruta relativa: si estás en /home/sergio/ic2, basta con practica/informe.pdf.
• Borrar un directorio plantea una pregunta: ¿se borra todo su subárbol? (En el dibujo, borrar practica se llevaría los cuatro archivos).

La desventaja del árbol: no permite compartir. Si laura y tú queréis trabajar sobre el mismo datos.csv, cada una tendría su copia.

4. Grafo acíclico: enlaces

La idea es que un mismo objeto (no una copia) esté enlazado desde varias rutas:

El directorio deja de ser un árbol y pasa a ser un grafo acíclico. Hay dos tipos de enlace, y su diferencia es pregunta segura:

• Enlace simbólico (ln -s datos.csv atajo.csv): un puntero al archivo original, que guarda su ruta. Puede tener permisos distintos y apuntar a directorios (los accesos directos de Windows son parecidos). Si se borra el original, el enlace apunta a nada.
• Enlace duro (ln datos.csv copia-laura.csv, menos usado): otra entrada que comparte el mismo i-nodo que el original. Solo para archivos, no para directorios.

Compartir trae dos preguntas. ¿Qué hacemos si se borra un objeto compartido? Si borras los datos sin más, quedan punteros colgantes (y peor: el sitio se puede reutilizar para otro archivo, y el enlace llevaría a él). La solución: borrar los punteros uno a uno y el archivo solo cuando el contador de enlaces llegue a 0. ¿Y al recorrer el grafo? Hay varias rutas al mismo archivo: un programa que cuente el espacio ocupado podría sumarlo dos veces si no recuerda por dónde ha pasado.

5. Grafo general: cuando aparecen ciclos

¿Y si enlazo con un directorio que está más arriba? Se forma un ciclo:

Aparecen infinitas rutas (ic2/practica/atajo/practica/atajo/…) y un programa que recorra el árbol sin saberlo se queda atascado. Soluciones: permitir enlaces solo a archivos, no a subdirectorios; recolección de basura (para liberar lo que quede inalcanzable); o algoritmos que detecten ciclos.

Modelo	Qué añade	Su pega
Nivel único	Lo más simple	Choques de nombres, lento con muchos archivos
Dos niveles	Un directorio por usuario, rutas	No hay subcarpetas
Árbol	Subdirectorios, rutas absolutas y relativas	No se puede compartir
Grafo acíclico	Enlaces: compartir sin copiar	Borrar y recorrer se complican
Grafo general	Enlaces sin restricciones	Ciclos

Montar un sistema de archivos

Antes de usar un sistema de archivos hay que montarlo: su árbol se cuelga de un directorio del árbol que ya existe, el punto de montaje. Es lo que pasa al conectar un pendrive:

Protección

Muchos sistemas definen privilegios: cada usuario solo puede hacer ciertas operaciones. En un archivo se protegen leer, escribir, ejecutar, añadir al final y eliminar; en un directorio, listar, crear un archivo, renombrar… Los mecanismos típicos:

• Listas de control de acceso (ACL): una lista de pares <usuario, permisos> por archivo.
• Contraseñas.
• Cifrado: para que no se pueda leer aunque alguien se lleve el dispositivo físico.

(Los permisos rwx de Unix, que viste en permisos en Linux, son una versión compacta de esta idea con tres clases: dueño, grupo y otros).

Cómo se implementa: el sistema de archivos por capas

Hasta aquí, lo que ves. Ahora, lo que hace el SO por debajo. El disco proporciona reescritura y acceso aleatorio, y las transferencias se hacen en bloques de sectores (normalmente de 512 o 4096 bytes). Sobre esa fila de bloques, el sistema de archivos tiene que conseguir tres cosas: asignar bloques a cada archivo, administrar el espacio libre e implementar los directorios. Lo organiza en capas:

El bloque de control de archivo (en Unix, el i-nodo) es la estructura que guarda la información de un archivo, y el controlador de dispositivo es quien habla con el hardware.

Asignación de espacio: dónde van los bloques de cada archivo

Cada archivo necesita un conjunto de bloques de datos. ¿Cuáles? Hay tres técnicas básicas (contigua, enlazada e indexada) y dos casos particulares (la FAT, variante de la enlazada, y la contigua con extensiones, extents, que usa NTFS).

Para comparar, vamos a guardar la carpeta de la práctica en el mismo disco con cada técnica. El disco tiene 32 bloques de 4 KiB, y algunos ya están ocupados por otros archivos:

Los cuatro archivos: practica.c (9300 B), Makefile (410 B), datos.csv (12 288 B, justo 3 × 4096) e informe.pdf (18 000 B). Bloques = tamaño / 4096 redondeando hacia arriba: 3, 1, 3 y 5 (18 000 / 4096 = 4,39 → 5). Total: 12 bloques, y hay 18 libres. ¿Cabe todo? Depende de la técnica.

Asignación contigua

Cada archivo ocupa bloques seguidos. El directorio solo guarda el bloque inicial y la longitud. Usamos el primer hueco donde quepa:

practica.c va del 2 al 4 (hueco de 3, exacto); Makefile al 7; datos.csv del 8 al 10. Y informe.pdf pide 5 bloques seguidos… y no hay ningún hueco de 5. Quedan 11 bloques libres, pero el mayor tramo tiene 4. Es la fragmentación externa, el mismo problema que la asignación contigua de memoria del Tema 9.

• Ventajas: cualquier acceso, secuencial o directo, es muy eficiente (el bloque k está en inicio + k) y, en discos magnéticos, los cabezales apenas se mueven.
• Problemas: la fragmentación y el crecimiento: si datos.csv crece, ¿dónde va? ¿Reservas el máximo desde el principio (y desperdicias) o vas reservando (y a lo mejor no cabe)?

Asignación enlazada

Los bloques no tienen por qué ser contiguos: forman una lista enlazada. Cada bloque guarda, al final, el número del siguiente. El directorio guarda el bloque inicial, la longitud y, a veces, el bloque final (para que crecer sea fácil):

Ahora informe.pdf cabe sin problema: 13 → 17 → 18 → 19 → 21. Pero mira el recuadro verde: con enlaces de 4 bytes, cada bloque solo tiene 4092 bytes útiles, y datos.csv, que encajaba justo en 3 bloques, necesita 4 (3 × 4092 = 12 276 < 12 288). Por 12 bytes.

• Ventaja: se acaban de raíz la fragmentación externa y la reserva previa de espacio.
• Problemas: el acceso directo es caro (para llegar al bloque k hay que leer los k anteriores), se gasta espacio en enlaces y es frágil: si se daña un bloque a mitad del archivo, se pierde todo lo que viene detrás.

Variantes para ganar rendimiento y robustez: enlaces dobles (hacia delante y hacia atrás) y un retroenlace en cada bloque que apunte a la entrada del directorio. Cada enlace extra resta bytes útiles.

La FAT: los enlaces, todos juntos

La FAT (File Allocation Table) es una variación de la enlazada que nació en MS-DOS y sigue en las memorias flash (VFAT, exFAT… y el FAT32 de mi pendrive). La idea: sacar los enlaces de los bloques y reunirlos en una tabla al principio del disco, con una entrada por bloque. La entrada b dice cuál es el bloque que sigue a b:

Para leer informe.pdf, el directorio dice «empieza en 12»; la entrada 12 dice 13; la 13 dice 17… hasta un código especial de fin de archivo. Como los bloques ya no guardan enlaces, datos.csv vuelve a ocupar 3.

• Ventajas: el acceso mejora respecto a la enlazada porque los enlaces se pueden guardar en caché; en dispositivos pequeños la FAT entera cabe en RAM; y para recorrer un archivo solo hacen falta los bloques de la FAT con sus enlaces.
• Problema: si se daña un bloque de la FAT, se pierden enlaces de muchos archivos a la vez. Solución: el disco guarda varias copias de la FAT.

Asignación indexada

Otra forma de juntar los enlaces: cada archivo tiene su propio bloque de índices, y la entrada k de ese bloque es la dirección del bloque k del archivo. El directorio guarda el número del bloque de índices (y la longitud, para saber cuántas entradas son útiles):

• Ventajas: sin fragmentación externa ni reserva previa, y el acceso directo en tiempo constante: bloque de índices + bloque de datos.
• Problemas: un bloque extra por archivo, que pesa en los pequeños (Makefile, con 410 bytes, gasta 2 bloques); un acceso más que la contigua (aunque el bloque de índices se puede tener en caché); y la fragilidad: si se daña el bloque de índices, se pierde todo el archivo.

¿Cuántas lecturas cuesta leer el bloque 4 de informe.pdf?

Aquí se ve la diferencia de verdad. Queremos el quinto bloque (el 4, contando desde 0):

Asignación	Qué guarda el directorio	Lecturas para el bloque k	Fragmentación externa	Si se daña un bloque…
Contigua	inicio y longitud	1 (inicio + k)	Sí	se pierde ese bloque
Enlazada	primer (y último) bloque	k + 1	No	se pierde todo lo de detrás
FAT	primer bloque	1 si la FAT está en RAM	No	si es de la FAT, muchos archivos
Indexada	bloque de índices	2	No	si es el de índices, todo el archivo

El i-nodo de Unix: índices en varios niveles

La indexada tiene una trampa: el tamaño del bloque limita cuántos índices caben, y con eso, el tamaño máximo del archivo. El ejemplo de los apuntes: bloques de 1 KiB (1024 bytes) y enlaces de 16 bits (2 bytes). En un bloque de índices caben 1024 / 2 = 512 entradas, así que un archivo tiene como mucho 512 bloques: 512 × 1 KiB = 512 KiB. Ni un vídeo corto.

¿Soluciones? Índices en varios bloques contiguos (vuelve la fragmentación), una lista enlazada de bloques de índices (ineficiente) o una estructura multinivel: un bloque de índices que apunta a otros bloques de índices. Esta fue la solución de Unix, y la estructura que la guarda es el i-nodo:

El i-nodo guarda los atributos (modo, propietarios, marcas de tiempo, tamaño, contador de enlaces) y los punteros:

• 12 punteros directos: cada uno apunta a un bloque de datos. Los archivos pequeños (la mayoría) no gastan ni un bloque de índices.
• Indirecto simple: apunta a un bloque de índices lleno de punteros a datos.
• Indirecto doble: a un bloque de índices cuyos punteros llevan a otros bloques de índices.
• Indirecto triple: un nivel más.

Calcular el tamaño máximo

La receta: punteros por bloque N = tamaño de bloque / tamaño de puntero, y el máximo es (directos + N + N² + N³) × tamaño de bloque. Con bloques de 4 KiB y punteros de 4 B, N = 4096 / 4 = 1024:

• Directos: 12 × 4 KiB = 48 KiB.
• Simple: 1024 × 4 KiB = 4 MiB (acumulado: 4,05 MiB).
• Doble: 1024² × 4 KiB = 2^20 × 2^12 B = 2^32 B = 4 GiB.
• Triple: 1024³ × 4 KiB = 2^30 × 2^12 B = 2^42 B = 4 TiB.

Fíjate en que, con bloques de 1 KiB (N = 256), el máximo baja a unos 16 GiB: el bloque grande gana por dos lados a la vez, más punteros por bloque y más bytes por bloque. Y vuelve a mi pendrive: con i-nodos y bloques de 4 KiB, el límite está en los terabytes. El de FAT32 no venía de la asignación, sino del campo de 32 bits donde apunta el tamaño.

Qué puntero lleva a cada bloque

Con el i-nodo ya en memoria, cada nivel de indirección es una lectura de disco más. Los directos cubren los bloques 0-11; el simple, los 1024 siguientes (12-1035); el doble, del 1036 al 1 049 611; y el triple, el resto:

Para el bloque 50 000: 50 000 − 12 − 1024 = 48 964 → está en el doble, así que 3 lecturas (índice de arriba, índice de abajo y datos). Y un vídeo de 300 MiB son 300 × 2^20 / 2^12 = 76 800 bloques de datos, que gastan 76 de índices: 1 del simple y, en el doble, el de arriba más ⌈(76 800 − 1036) / 1024⌉ = 74 de abajo.

Administración del espacio libre

Para asignar bloques, el SO tiene que saber cuáles están libres. Tres estructuras:

• Mapa de bits: una tabla en una zona fija del disco con un bit por bloque (libre u ocupado). Es lo que usaba el Unix tradicional. (Qué valor significa «libre» depende del sistema: aquí usamos 1 = ocupado).
• Lista enlazada: el SO guarda un puntero al primer bloque libre, que apunta al siguiente libre, y así. Variante: el primer libre hace de bloque de índices con la lista de los demás.
• FAT: si un bloque está libre, su entrada en la FAT lo indica. La propia FAT es la estructura de libres.

Cálculos de tamaño: todo en potencias de 2

En el examen te piden cuánto ocupan estas estructuras. El truco es pasar todo a potencias de 2: 1 KiB = 2^10, 1 MiB = 2^20, 1 GiB = 2^30, 1 TiB = 2^40.

Un disco de 2 TiB con bloques de 32 KiB:

• Bloques: 2^41 / 2^15 = 2^26 = 67 108 864.
• Mapa de bits: 2^26 bits = 2^26 / 2^3 = 2^23 bytes = 8 MiB.
• FAT con entradas de 4 bytes: 2^26 × 2^2 = 2^28 bytes = 256 MiB (32 veces el mapa de bits, porque cada entrada tiene 32 bits en lugar de 1).

Y el número de bloques de un archivo con enlazada: un archivo de 2 MiB (2 097 152 B) con bloques de 1 KiB y enlaces de 4 B tiene 1020 bytes útiles por bloque: 2 097 152 / 1020 = 2056,03 → 2057 bloques. Con FAT o contigua serían 2048 justos.

Implementación de directorios

Queda una pregunta: ¿cómo se guarda la lista de nombres y atributos de un directorio?

• Lista lineal: nombres con sus punteros a los bloques y otros atributos. Sencilla (una tabla), pero el rendimiento es desastroso con miles de entradas: buscar es comparar una a una.
• Tabla hash: a partir del nombre se calcula la casilla y se va directo.
• Árboles B (NTFS, ext4…): funcionan muy bien con muchas entradas y, aunque son más complejos, no penalizan demasiado el espacio ni la complejidad del núcleo.

Errores típicos

Compruébalo con Python

Dos simuladores con los datos del artículo, sin nada que teclear. Cópialos en un archivo .py y ejecútalos.

Simulador 1: la misma carpeta con las cuatro asignaciones

# La carpeta de la práctica de IC2 en un disco de 32 bloques: contigua, enlazada, FAT e indexada
B, P = 4096, 4                        # bloque de 4 KiB y enlace de 4 bytes
libres = [2, 3, 4, 7, 8, 9, 10, 12, 13, 17, 18, 19, 21, 22, 23, 24, 28, 29]   # el resto, ocupado
archivos = {'practica.c': 9300, 'Makefile': 410, 'datos.csv': 12288, 'informe.pdf': 18000}
K = 4                                 # leeremos el bloque 4 (el quinto) de informe.pdf

def bloques_para(tam, util):          # redondeo hacia arriba: medio bloque ocupa un bloque entero
    return -(-tam // util)

def tramos(lista):                    # agrupa los libres en huecos contiguos [inicio, largo]
    h = []
    for b in lista:
        if h and h[-1][0] + h[-1][1] == b:
            h[-1][1] += 1             # b sigue al hueco anterior: lo alarga
        else:
            h.append([b, 1])          # b empieza un hueco nuevo
    return h

print('CONTIGUA (primer hueco que quepa)')
huecos = tramos(libres)
for n, tam in archivos.items():
    k = bloques_para(tam, B)
    x = next((x for x in huecos if x[1] >= k), None)
    if x:                             # cabe: ocupa el principio del hueco
        print(f'  {n:<12} inicio {x[0]:>2}  bloques {k}  sobran {k * B - tam:>4} B')
        x[0] += k; x[1] -= k
    else:                             # hay sitio en total, pero no seguido
        print(f'  {n:<12} NO CABE: pide {k}, mayor hueco {max(x[1] for x in huecos)},'
              f' libres {sum(x[1] for x in huecos)}')
# enlazada: cada bloque guarda el enlace (4 B menos de datos); FAT: los enlaces van en la tabla
for nombre, util, indice, lect in (('ENLAZADA', B - P, 0, K + 1), ('FAT', B, 0, 1), ('INDEXADA', B, 1, 2)):
    lista = list(libres); print(nombre)
    for n, tam in archivos.items():
        k = bloques_para(tam, util) + indice    # la indexada gasta además un bloque de índices
        bs, lista = lista[:k], lista[k:]
        print(f'  {n:<12} ' + (f'índice {bs[0]:>2} | ' if indice else '') + ' -> '.join(map(str, bs[indice:])))
        if n == 'informe.pdf':
            leer = f'  bloque {K} de {n}: disco {bs[indice + K]}, lecturas {lect}'
    print(f'  usados {len(libres) - len(lista)}, libres {len(lista)}'); print(leer)

La función que más cuesta leer es tramos(), que convierte la lista de libres en huecos [inicio, largo]:

def tramos(lista):                    # agrupa los libres en huecos contiguos [inicio, largo]
    h = []
    for b in lista:
        if h and h[-1][0] + h[-1][1] == b:
            h[-1][1] += 1             # b sigue al hueco anterior: lo alarga
        else:
            h.append([b, 1])          # b empieza un hueco nuevo
    return h

Recorre los libres en orden: si el bloque b es justo el siguiente al final del último hueco (inicio + largo == b), alarga ese hueco; si no, empieza uno nuevo. Con 2, 3, 4, 7… sale [2, 3], después [7, …], y así. Esta es la salida real:

CONTIGUA (primer hueco que quepa)
  practica.c   inicio  2  bloques 3  sobran 2988 B
  Makefile     inicio  7  bloques 1  sobran 3686 B
  datos.csv    inicio  8  bloques 3  sobran    0 B
  informe.pdf  NO CABE: pide 5, mayor hueco 4, libres 11
ENLAZADA
  practica.c   2 -> 3 -> 4
  Makefile     7
  datos.csv    8 -> 9 -> 10 -> 12
  informe.pdf  13 -> 17 -> 18 -> 19 -> 21
  usados 13, libres 5
  bloque 4 de informe.pdf: disco 21, lecturas 5
FAT
  practica.c   2 -> 3 -> 4
  Makefile     7
  datos.csv    8 -> 9 -> 10
  informe.pdf  12 -> 13 -> 17 -> 18 -> 19
  usados 12, libres 6
  bloque 4 de informe.pdf: disco 19, lecturas 1
INDEXADA
  practica.c   índice  2 | 3 -> 4 -> 7
  Makefile     índice  8 | 9
  datos.csv    índice 10 | 12 -> 13 -> 17
  informe.pdf  índice 18 | 19 -> 21 -> 22 -> 23 -> 24
  usados 16, libres 2
  bloque 4 de informe.pdf: disco 24, lecturas 2

Qué observar:

1. La contigua falla con espacio libre: informe.pdf pide 5, el mayor hueco es de 4 y quedan 11 libres. Fragmentación externa en estado puro.
2. El enlace se come bytes: en la enlazada, datos.csv pasa de 3 bloques a 4 (8 -> 9 -> 10 -> 12) y se usan 13 bloques en total frente a los 12 de la FAT.
3. La indexada gasta un bloque por archivo: 16 usados (12 de datos + 4 de índices); Makefile ocupa 2 bloques para 410 bytes.
4. El mismo bloque lógico vive en sitios distintos: el bloque 4 de informe.pdf es el 21, el 19 o el 24 del disco según la técnica, y cuesta 5, 1 o 2 lecturas.
5. La columna sobran es la fragmentación interna: Makefile desperdicia 3686 de sus 4096 bytes.

Simulador 2: el tamaño máximo con un i-nodo

# Tamaño máximo de un archivo con un i-nodo: 12 punteros directos + indirecto simple, doble y triple
P, D = 4, 12                          # puntero de 4 bytes y 12 punteros directos

def legible(b):                       # bytes -> la mayor unidad binaria que no se queda corta
    for u, e in (('TiB', 40), ('GiB', 30), ('MiB', 20), ('KiB', 10)):
        if b >= 2 ** e:
            return f'{b / 2 ** e:.2f} {u}'
    return f'{b} B'

def niveles(B):                       # bloques de datos que alcanza cada puntero del i-nodo
    N = B // P                        # punteros que caben en un bloque de índices
    return [('directos', D), ('simple', N), ('doble', N ** 2), ('triple', N ** 3)]

for B in (1024, 4096):
    print(f'Bloque de {B} B -> {B // P} punteros por bloque de índices')
    total = 0
    for nombre, n in niveles(B):
        total += n                    # el máximo es la suma de los cuatro niveles
        print(f'  {nombre:<9}{n:>14} bloques  acumulado {legible(total * B):>11}')

B, N = 4096, 1024
def camino(k):                        # qué puntero lleva al bloque lógico k y cuántas lecturas cuesta
    for lect, (nombre, n) in enumerate(niveles(B), start=1):
        if k < n:
            return nombre, lect       # con el i-nodo en RAM: 1 + un bloque de índices por nivel
        k -= n                        # k no está en este nivel: pasa al siguiente

print('Bloque de 4096 B, i-nodo ya en memoria:')
for k in (5, 500, 50000, 2000000):
    nombre, lect = camino(k)
    print(f'  bloque {k:>7}: puntero {nombre:<9} lecturas {lect}')
datos = -(-300 * 2 ** 20 // B)        # un vídeo de 300 MiB de la defensa de la práctica
resto, indices = datos - D, 0
if resto > 0:
    indices += 1; resto -= N          # el indirecto simple: un bloque de índices
if resto > 0:                         # el doble: el bloque de arriba + los que hagan falta debajo
    indices += 1 + -(-min(resto, N * N) // N); resto -= N * N
print(f'Vídeo de 300 MiB: {datos} bloques de datos + {indices} de índices ({legible(indices * B)})')

niveles() devuelve cuántos bloques de datos alcanza cada puntero (12, N, N², N³), y camino() va restando niveles hasta encontrar en cuál cae el bloque k: el mismo método de la pista de arriba. Salida real:

Bloque de 1024 B -> 256 punteros por bloque de índices
  directos             12 bloques  acumulado   12.00 KiB
  simple              256 bloques  acumulado  268.00 KiB
  doble             65536 bloques  acumulado   64.26 MiB
  triple         16777216 bloques  acumulado   16.06 GiB
Bloque de 4096 B -> 1024 punteros por bloque de índices
  directos             12 bloques  acumulado   48.00 KiB
  simple             1024 bloques  acumulado    4.05 MiB
  doble           1048576 bloques  acumulado    4.00 GiB
  triple       1073741824 bloques  acumulado    4.00 TiB
Bloque de 4096 B, i-nodo ya en memoria:
  bloque       5: puntero directos  lecturas 1
  bloque     500: puntero simple    lecturas 2
  bloque   50000: puntero doble     lecturas 3
  bloque 2000000: puntero triple    lecturas 4
Vídeo de 300 MiB: 76800 bloques de datos + 76 de índices (304.00 KiB)

Qué observar:

1. Con 1 KiB, el triple llega a 16,06 GiB; con 4 KiB, a 4,00 TiB: cuadruplicar el bloque multiplica el máximo por unas 256.
2. Los directos aportan casi nada (48 KiB) pero hacen que los archivos pequeños no necesiten bloques de índices.
3. Las lecturas suben de una en una con cada nivel: 1, 2, 3 y 4.
4. Los 76 bloques de índices del vídeo ocupan 304 KiB: menos de un 0,1 % de sus 300 MiB.

Resumen

Concepto	Lo esencial
Archivo	Objeto con nombre que guarda información persistente; 7 atributos
Operaciones	Crear, escribir, leer, reposicionar, borrar, truncar; abrir/cerrar para no ir al directorio cada vez
Acceso	Secuencial (cinta), directo (lseek), indexado (clave)
Directorios	Nivel único → dos niveles → árbol → grafo acíclico (enlaces) → grafo general (ciclos)
Enlaces	Duro: mismo i-nodo y contador; simbólico: guarda la ruta, se rompe al borrar el original
Asignación	Contigua (fragmentación), enlazada (acceso directo caro), FAT (enlaces en tabla), indexada (bloque extra)
i-nodo	12 directos + simple + doble + triple; máximo = (12 + N + N² + N³) × bloque
Espacio libre	Mapa de bits, lista enlazada o la propia FAT
Directorios por dentro	Lista lineal, tabla hash, árbol B

Tres ideas para llevarte:

1. Un archivo es una abstracción: tú ves un nombre, la API ve bytes y el núcleo ve bloques.
2. Cada técnica de asignación decide dónde viven los enlaces (en el directorio, en los bloques, en una tabla o en un bloque de índices), y de eso depende el acceso directo, la fragmentación y la fragilidad.
3. Los cálculos siempre salen igual: todo a potencias de 2, restar lo que no son datos y redondear hacia arriba.

Con esto termina la teoría de IC2. Ahora toca practicar. Primero, en la práctica guiada de sistemas de archivos resolvemos paso a paso cálculos de i-nodos y de cuántos bloques hay que leer; después, en los ejercicios de sistemas de archivos tienes un test con todos los formatos del examen, cálculos de bloques, i-nodos y mapas de bits con casillas que se corrigen solas, preguntas de desarrollo y el chuletario. ¡Nos vemos allí!

Siguiente paso: prácticaSistemas de archivos — práctica con problemas guiados paso a paso: bloques y fragmentación interna, lecturas según la asignación, el i-nodo y un ejercicio con el formato del examen (y el bloque que conté desde 1)

¿Te ha servido este artículo? Así puedes apoyar SergioLearns →